Graph or relational databases - Revision history

DavidStables: /* Conclusions */

2021-01-10T16:09:17Z

Conclusions

← Older revision		Revision as of 16:09, 10 January 2021
Line 108:		Line 108:
	In the Discovery data service, as of May 2020, the conclusion has been drawn that:		In the Discovery data service, as of May 2020, the conclusion has been drawn that:

	"'''<span style="color:#27ae60;">We should design and implement the data model in graph and enable implementation in relational</span>t'''."		"'''<span style="color:#27ae60;">We should design and implement the data model in graph and enable implementation in relational</span>'''"


	"'''<span style="color:#27ae60;">The health record store should be implemented in relational, until such time as the evidence of native graph databases providing an improve cost/ benefit ratio is provided</span>t'''."		"'''<span style="color:#27ae60;">The health record store should be implemented in relational, until such time as the evidence of native graph databases providing an improve cost/ benefit ratio is provided</span>'''"


	"'''<span style="color:#27ae60;">It is very likely that an relational model will be replaced by graph</span>t'''."		"'''<span style="color:#27ae60;">It is very likely that an relational model will be replaced by graph.</span>'''"

DavidStables: /* Conclusions */

2021-01-10T16:08:47Z

Conclusions

← Older revision		Revision as of 16:08, 10 January 2021
Line 108:		Line 108:
	In the Discovery data service, as of May 2020, the conclusion has been drawn that:		In the Discovery data service, as of May 2020, the conclusion has been drawn that:

	"'''<span style="color:#27ae60;">We should design in graph and ~~implement~~ in relational, until such time as the evidence of native graph databases providing an improve cost/ benefit ratio is ~~presen~~</span>t'''."		"'''<span style="color:#27ae60;">We should design and implement the data model in graph and enable implementation in relational</span>t'''."


			"'''<span style="color:#27ae60;">The health record store should be implemented in relational, until such time as the evidence of native graph databases providing an improve cost/ benefit ratio is provided</span>t'''."


			"'''<span style="color:#27ae60;">It is very likely that an relational model will be replaced by graph</span>t'''."

DavidStables: /* Graph and relational relationships */

2021-01-10T16:05:39Z

Graph and relational relationships

← Older revision		Revision as of 16:05, 10 January 2021
Line 18:		Line 18:
	The Graph approach is much clearer and much more intuitive. It is great for explicit relationships. A graph seems to be more relational than a relational database. Conclusion : <span style="color:#27ae60;">Graph wins for intuitiveness.</span>		The Graph approach is much clearer and much more intuitive. It is great for explicit relationships. A graph seems to be more relational than a relational database. Conclusion : <span style="color:#27ae60;">Graph wins for intuitiveness.</span>

	The following diagram illustrates the processes involved in a graph traversing from a patient to an observation via an encounter, versus a join between a patient and an observation, via an encounter,  in both case using the encounter as an intermediate entity (accepting that in reality there may be  more direct relationship).		The following diagram illustrates the processes involved in a graph traversing of a kind that uses "index adjacency" from a patient to an observation via an encounter, versus a join between a patient and an observation, via an encounter,  in both case using the encounter as an intermediate entity (accepting that in reality there may be  more direct relationship).

	[[File:Graph vs relational traverse.jpeg\|800x400px\|Graph vs relational traverse.jpeg]]		[[File:Graph vs relational traverse.jpeg\|800x400px\|Graph vs relational traverse.jpeg]]

	It can be seen that in Graph, the relationship indexes are immediately available to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)		It can be seen that in Graph, the relationship indexes are immediately available to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for).

	~~ ~~


			It should be noted that pure Graph databases would index the relationships rather than the nodes and therefore graph traversal may not include the above.
	= Health query patterns =		= Health query patterns =

Line 35:		Line 33:
	The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last 10 years and then for each concept recorded in each observation, determine whether it is an infectious Disease.		The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last 10 years and then for each concept recorded in each observation, determine whether it is an infectious Disease.

	To do this, the general approach is to start with a set of infectious diseases. This usually involves using an ontology that has concepts with definitions, which include the fact that something is a disease, and has a pathological process which is infectious i.e. would use inference to generate the list.  This would result in a list of around 10,000 concepts i.e.. lots of infectious diseases.		To do this, the general approach is to start with a set of infectious diseases. This usually involves using an ontology that has concepts with definitions, which include the fact that something is a disease, and has a pathological process which is infectious i.e. would use inference to generate the initial list of things to look for; a value set.   This would result in a list of around 10,000 concepts i.e.. lots of infectious diseases.

	Rather than examine the billions of observations in total, it would be beneficial to use some form of index.		Rather than examine the billions of observations in total, it would be beneficial to use some form of index.

	In a relational query this would mean joining the 10,000 disease concepts (likely to be in a table prepared for the query) against the observations  via an index on the observation instance of the disease.  In a graph query this would involve ~~matching~~ 10,000 disease nodes with ~~observation~~ nodes that are indicators of disease. The difference can be illustrated as follows:		In a relational query this would mean joining the 10,000 disease concepts (likely to be in a table prepared for the query) against the observations  via an index on the observation instance of the disease.  In a graph query this would involve linking 10,000 disease nodes with the disease nodes that are indicators of disease via the property that links the disease record to the disease. The difference can be illustrated as follows:


Line 49:		Line 47:


	The logic of each is somewhat similar. In the above example, an additional traverse is needed by the graph in order to match the patient. In the relational approach, because the value of the patient is implicit in the foreign key in the observation, no additional join is needed. Furthermore, it is likely that both the patient and concept would be included in a 'covering index' in a relational model, (as well as an index on the diseases) whereas in graph, the patient would need to be assigned in the observation node to achieve the same.		The logic of each is somewhat similar. In the above example, an additional traverse is needed by the graph in order to match the patient. On the other hand. if you need something in relation to the patient e.g. an NHS number, then it is accessible. In the relational approach, because the value of the patient is implicit in the foreign key in the observation, no additional join is needed. Furthermore, it is likely that both the patient and concept would be included in a 'covering index' in a relational model, (as well as an index on the diseases) whereas in graph, the patient would need to be assigned in the observation node to achieve the same.

	Thus in this particular case the <span style="color:#27ae60;">relational model appears to outperform the graph model. </span>But not by much.		Thus in this particular case the <span style="color:#27ae60;">relational model appears to outperform the graph model. </span>But not by much.
Line 59:		Line 57:
	Graph appears to be more logically simpler and more efficient at patient level if the retrieval pattern is at the full record level, as it takes account of the relationship optimisation.		Graph appears to be more logically simpler and more efficient at patient level if the retrieval pattern is at the full record level, as it takes account of the relationship optimisation.

	However, many queries at patient level operate on subsets of records e.g. observation or medications and the ~~partioning~~ by table provides an advantage over node filtering by the use of c clustered BTree on the table.		However, many queries at patient level operate on subsets of records e.g. observation or medications and the partitioning by table provides an advantage over node filtering by the use of c clustered BTree on the table.

	At the level of as single patient, whether graph or relational is probably secondary to where the the record query business logic operates. if for example the business ~~logc~~ occurs in the ~~applicaion~~ tier then a simpler document style structured such as JSON would probably win over both.		At the level of as single patient, whether graph or relational is probably secondary to where the the record query business logic operates. if for example the business logic occurs in the application tier then a simpler document style structured such as JSON would probably win over both.

	= Relational as graph =		= Relational as graph =

DavidStables at 15:54, 10 January 2021

2021-01-10T15:54:19Z

← Older revision		Revision as of 15:54, 10 January 2021
Line 6:		Line 6:
	The starting point is to examine a few key logical differences in structure then move on to some technical differences. Following this the two are compared and contrasted from the perspective of the type of queries needed. Subsequently other approaches are considered, as well as a list of the additional factors that should be taken into account when making the decision.		The starting point is to examine a few key logical differences in structure then move on to some technical differences. Following this the two are compared and contrasted from the perspective of the type of queries needed. Subsequently other approaches are considered, as well as a list of the additional factors that should be taken into account when making the decision.

	Firstly, its worth noting that a 'pure' Graph model is not included for consideration. There are known problems at scale with pure graphs. If one were to adopt Graph then a property graph is the most likely variant. A property graph has properties on the vertices (nodes), and in the case of NEO4J, also has properties on the edges (which are called relationships).


Line 23:		Line 22:
	[[File:Graph vs relational traverse.jpeg\|800x400px\|Graph vs relational traverse.jpeg]]		[[File:Graph vs relational traverse.jpeg\|800x400px\|Graph vs relational traverse.jpeg]]

	It can be seen that in Graph, the relationship indexes are ~~adjacent~~ to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)		It can be seen that in Graph, the relationship indexes are immediately available to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)

DavidStables at 14:46, 6 May 2020

2020-05-06T14:46:55Z

← Older revision		Revision as of 14:46, 6 May 2020
Line 26:		Line 26:




	= Health query patterns =		= Health query patterns =

	The above section illustrates the power of graph over relational. The question is whether this is helpful in health query.		The above section illustrates the power of graph over relational. The question is whether this is helpful in health query at population level, with a supplementary issue around patient level.

			== Population query ==

	The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last 10 years and then for each concept recorded in each observation, determine whether it is an infectious Disease.		The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last 10 years and then for each concept recorded in each observation, determine whether it is an infectious Disease.
Line 53:		Line 56:
	So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors		So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors

			== Single patient query ==

			Graph appears to be more logically simpler and more efficient at patient level if the retrieval pattern is at the full record level, as it takes account of the relationship optimisation.

			However, many queries at patient level operate on subsets of records e.g. observation or medications and the partioning by table provides an advantage over node filtering by the use of c clustered BTree on the table.

			At the level of as single patient, whether graph or relational is probably secondary to where the the record query business logic operates. if for example the business logc occurs in the applicaion tier then a simpler document style structured such as JSON would probably win over both.

	= Relational as graph =		= Relational as graph =

DavidStables at 14:41, 6 May 2020

2020-05-06T14:41:01Z

← Older revision		Revision as of 14:41, 6 May 2020
Line 9:		Line 9:




	= Graph and relational relationships =		= Graph and relational relationships =

	Taking some very simple entity relationships from a health record, the following illustrates the different logical approach.  Graph is on the left, relational is on the right.		Taking some very simple entity relationships from a single patient health record, the following illustrates the different logical approach.  Graph is on the left, relational is on the right.

	[[File:Graph versus relational.jpeg\|center\|800x300px\|Graph versus relational.jpeg]]The logical difference is that a graph is explicit about a type of relationship between entities, whereas a relational model uses foreign keys to ''implicitly'' relate entities  i.e... on the right the field on the encounter "patient id" points to the patient entity on the left, but does not state the semantic reason for the link. On the left, the graph states that a patient is a subject of an encounter, and could conversely indicate that an encounter 'has a subject' that is a patient.		[[File:Graph versus relational.jpeg\|center\|800x300px\|Graph versus relational.jpeg]]The logical difference is that a graph is explicit about a type of relationship between entities, whereas a relational model uses foreign keys to ''implicitly'' relate entities  i.e... on the right the field on the encounter "patient id" points to the patient entity on the left, but does not state the semantic reason for the link. On the left, the graph states that a patient is a subject of an encounter, and could conversely indicate that an encounter 'has a subject' that is a patient.

DavidStables at 14:40, 6 May 2020

2020-05-06T14:40:26Z

← Older revision		Revision as of 14:40, 6 May 2020
Line 1:		Line 1:

	A question arises as to whether the Discovery Data Service should use relational, property graph, document, or key value based database management systems  in its main patient record data stores.		A question arises as to whether the Discovery Data Service should use relational, property graph, document, or key value based database management systems  in its main population patient record data stores.

	This article considers the differences between graph and relational from the perspective of the known information requirements of health query and goes on to consider other factors involved in deciding which to go for.  It reaches a temporary conclusion as a result.		This article considers the differences between graph and relational from the perspective of the known information requirements of health query and goes on to consider other factors involved in deciding which to go for.  It reaches a temporary conclusion as a result.
Line 8:		Line 8:
	Firstly, its worth noting that a 'pure' Graph model is not included for consideration. There are known problems at scale with pure graphs. If one were to adopt Graph then a property graph is the most likely variant. A property graph has properties on the vertices (nodes), and in the case of NEO4J, also has properties on the edges (which are called relationships).		Firstly, its worth noting that a 'pure' Graph model is not included for consideration. There are known problems at scale with pure graphs. If one were to adopt Graph then a property graph is the most likely variant. A property graph has properties on the vertices (nodes), and in the case of NEO4J, also has properties on the edges (which are called relationships).



	= Graph and relational relationships =		= Graph and relational relationships =
Line 23:		Line 24:
	It can be seen that in Graph, the relationship indexes are adjacent to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)		It can be seen that in Graph, the relationship indexes are adjacent to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)



	= Health query patterns =		= Health query patterns =
Line 50:		Line 52:
	So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors		So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors



	= Relational as graph =		= Relational as graph =

DavidStables at 13:45, 6 May 2020

2020-05-06T13:45:20Z

← Older revision		Revision as of 13:45, 6 May 2020
Line 49:		Line 49:

	So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors		So it seems that there is little to choose in this type of health query between the logic of a graph query and the logic of a table query. In the end it may boil down to other factors


	= Relational as graph =		= Relational as graph =
Line 56:		Line 57:
	1. Conventional pattern. Fields are fixed and explicit, and where their values are foreign keys, the entity they point to is implicit in the field name, perhaps further constrained by a foreign key constraint.		1. Conventional pattern. Fields are fixed and explicit, and where their values are foreign keys, the entity they point to is implicit in the field name, perhaps further constrained by a foreign key constraint.

	2. Triple tables. These are link tables that have 3 main fields. The ~~fist~~ field is a "source or owner" and points to a main entity record (the source table). The second field  is the "relationship or property" field, and whose value is the type of relationship or property.  A third field "value or target" ,whose value depends on the type of Relationship (e.g.. points to another table, an object value, or a data value.		2. Triple tables. These are link tables that have 3 main fields. The first field is a "source or owner" and points to a main entity record (the source table). The second field  is the "relationship or property" field, and whose value is the type of relationship or property.  A third field "value or target" ,whose value depends on the type of Relationship (e.g.. points to another table, an object value, or a data value.

	This approach enables a designer to think graph and implement relational.		This approach enables a designer to think graph and implement relational.

DavidStables at 13:44, 6 May 2020

2020-05-06T13:44:26Z

← Older revision		Revision as of 13:44, 6 May 2020
Line 22:		Line 22:

	It can be seen that in Graph, the relationship indexes are adjacent to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)		It can be seen that in Graph, the relationship indexes are adjacent to the connecting nodes and therefore 4 direct file address pointers are used,  whereas in the relational model the foreign key of the observation table is searched for in the encounter primary root and leaf index pages, back to the encounter, and up again making a total of 5 searches i.e... each index block must be searched to find the destination of the record in each table.  Conclusion, <span style="color:#27ae60;">Graph wins for multi-hop traversals over relational joins</span>. (which is of course what graph databases are for)


	= Health query patterns =		= Health query patterns =
Line 27:		Line 28:
	The above section illustrates the power of graph over relational. The question is whether this is helpful in health query.		The above section illustrates the power of graph over relational. The question is whether this is helpful in health query.

	The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last ~~2 weeks~~ and then for each concept recorded in each observation, determine whether it is an infectious Disease.		The main characteristics of health query over standard business query is the idea of [[Subsumption_test\|subsumption testing]]. Subsumption testing involves the examination of concepts that are recorded in health events to see if they are subtypes of a high level type. For example, a query such as "<span style="color:#8e44ad;">find me the incidence of all infectious diseases in the population of London in the last 10 years</span>" involves (in theory) the examination of billions of observations in patient records, determine that the dates are in the last 10 years and then for each concept recorded in each observation, determine whether it is an infectious Disease.

	To do this, the general approach is to start with a set of infectious diseases. This usually involves using an ontology that has concepts with definitions, which include the fact that something is a disease, and has a pathological process which is infectious. This would result in a list of around 10,000 concepts i.e.. lots of infectious diseases.		To do this, the general approach is to start with a set of infectious diseases. This usually involves using an ontology that has concepts with definitions, which include the fact that something is a disease, and has a pathological process which is infectious i.e. would use inference to generate the list.  This would result in a list of around 10,000 concepts i.e.. lots of infectious diseases.

	Rather than examine the billions of observations in total, it would be beneficial to use some form of index.		Rather than examine the billions of observations in total, it would be beneficial to use some form of index.

DavidStables at 13:41, 6 May 2020

2020-05-06T13:41:00Z

← Older revision		Revision as of 13:41, 6 May 2020
Line 7:		Line 7:

	Firstly, its worth noting that a 'pure' Graph model is not included for consideration. There are known problems at scale with pure graphs. If one were to adopt Graph then a property graph is the most likely variant. A property graph has properties on the vertices (nodes), and in the case of NEO4J, also has properties on the edges (which are called relationships).		Firstly, its worth noting that a 'pure' Graph model is not included for consideration. There are known problems at scale with pure graphs. If one were to adopt Graph then a property graph is the most likely variant. A property graph has properties on the vertices (nodes), and in the case of NEO4J, also has properties on the edges (which are called relationships).


	= Graph and relational relationships =		= Graph and relational relationships =
Line 12:		Line 13:
	Taking some very simple entity relationships from a health record, the following illustrates the different logical approach.  Graph is on the left, relational is on the right.		Taking some very simple entity relationships from a health record, the following illustrates the different logical approach.  Graph is on the left, relational is on the right.

	[[File:Graph versus relational.jpeg\|center\|800x300px\|Graph versus relational.jpeg]]The logical difference is that a graph is explicit about a type of relationship between entities, whereas a relational model uses foreign keys to ''implicitly'' relate entities  i.e... the field on the encounter "patient id" points to the patient entity on the left, but does not state the semantic reason for the link. On the left, the graph states that a patient is a subject of an encounter, and could conversely indicate that an encounter 'has a subject' that is a patient.		[[File:Graph versus relational.jpeg\|center\|800x300px\|Graph versus relational.jpeg]]The logical difference is that a graph is explicit about a type of relationship between entities, whereas a relational model uses foreign keys to ''implicitly'' relate entities  i.e... on the right the field on the encounter "patient id" points to the patient entity on the left, but does not state the semantic reason for the link. On the left, the graph states that a patient is a subject of an encounter, and could conversely indicate that an encounter 'has a subject' that is a patient.

	The Graph approach is much clearer and much more intuitive. It is great for explicit relationships. A graph seems to be more relational than a relational database. Conclusion : <span style="color:#27ae60;">Graph wins for intuitiveness.</span>		The Graph approach is much clearer and much more intuitive. It is great for explicit relationships. A graph seems to be more relational than a relational database. Conclusion : <span style="color:#27ae60;">Graph wins for intuitiveness.</span>