In spite of the extensive literature on graph databases (GDBs), temporal GDBs have not received too much attention so far. Temporal GBDs can capture, for example, the evolution of social networks across time, a relevant topic in data analysis nowadays. We propose a data model and query language (denoted TEG-QL) for temporal GDBs, based on the notion of attribute graphs. This allows a straightforward translation to Neo4J, a well-known GBD.
Graphs, and, particularly, attributed graphs [
Among the work on temporal graphs, Catutto et al. [
Our running example is a network containing two kinds of nodes, representing persons and buildings. Edges are of two kinds: One, representing friendship relationships between people across time; the other one, telling the buildings where people had lived in through time. Besides information about the name, type of building, number of bedrooms in the apartment, etc., nodes have a temporal attribute, which is a temporal element indicating the periods of validity of the node. Edges are also labeled with temporal attributes. 2
We now de ne our temporal data model, based on the notion of attribute graphs. De nition 1 (Temporal graph). A temporal graph is a structure G(N o; N e; N a; N v; E) where G is the name of the graph, E is a set of edges, and N o; N e; N a; and N v are sets of nodes, denoted object nodes, edge nodes, attribute nodes,and value nodes, respectively. Every node is associated with a tuple (name, interval), where name represents the content of the node, and interval is a temporal element representing the period(s) in which the node is (was) valid. tu
Object nodes represent entities, edge nodes represent relationships between object nodes, attribute nodes describe entities, and value nodes represent the value of an attribute. Figure 1 depicts a portion of a graph, using our running example. The properties labeling the nodes are, from top to bottom, id, name and interval. This way, the node with id=4 (in light green) is an Edge node, the node with id=1 (in red) is an Object node, the node with id=2 (purple) is an Attribute node, and the one with id=3 (grey) is a Value node. tu De nition 2 (Constraints). Consider the following notation. We denote edge nodes as nefna; nbg, where ne is an edge node connected to object nodes na and nb; efna; nbg represent edges, where na and nb are nodes connected by edge e; nafng represent attribute nodes, where n is the object or edge node connected to na; nvfnag denote value nodes, where na is the attribute node connected to nv.
For the graph in De nition 1, the following constraints hold: 1. 8n; n0 2 N o; n = n0 _ n:id 6= n0:id 2. 8n; n0 2 N e; n = n0 _ n:id 6= n0:id 3. 8n; n0 2 N a; n = n0 _ n:id 6= n0:id 4. 8n; n0 2 N v; n = n0 _ n:id 6= n0:id 5. 8nvfnag; nv0fnag 2 N v; nv = nv0 _ nv:value 6= nv0:value 6. 8n 2 N o; efn; n0g 2 E ) n0 2 N e S N a 7. 8n 2 N e; efn; n0g 2 E ) n0 2 N o S N a 8. 8n 2 N a; efn; n0g 2 E ) n0 2 N o S N e S N v 9. 8n 2 N v; efn; n0g 2 E ) n0 2 N v 10. 8ne 2 N e; if 9 efno; neg ^ 9e0fne; no0g )6 9e00 2 E; 6 9no00 2 N o ^ no00 6= no ^ no00 6= no0 ^ e00fno00; neg ^ e00fne; no00g 11. 8n 2 N a(9no 2 N o9e 2 E(e(no; n) _ 9ne 2 N e ^ efne; ng ^ (6 9n0 2 (N a S N e S N v S N o) ^ e0 2 E ^ e0fn0; ng) 12. 8n 2 N v ^efn0; ng^n 2 N a )6 9!n00 2 (N a S N e S N v S N o)^(e00fn00; ng 2
E _ e00fn; n00g 2 E 13. 9efn; n0g; e0fn; n0g 2 E ) e = e0 14. 8nefn; n0g 2 N e; ne:interval n:interval \ n0:interval 15. 8nafng 2 N a; na:interval n:interval 16. 8nvfnag 2 N v; nv:interval nv:interval 17. 8nvfnag; nv0fnag; nv 6= nv0; nv:interval \ nv0:interval = ; Constraints 1 through 4 state that no two nodes can have the same id. Constraint 5 requires coalescing all nodes with the same value; Constraints 6 through 9 state that Object nodes can only be connected to edge nodes or attribute nodes; Edge nodes can only be connected to object nodes or attribute nodes; Attribute nodes can be connected to non-attribute nodes; and Value nodes can only be connected to attribute nodes. The cardinalities of these connections is stated by Constraints 10 through 13 (e.g., Edge nodes must be connected to exactly two di erent object nodes through exactly one edge). Constraints 14 to 16 restrict the values of the interval property. Finally, constraint 17 forces value nodes connected to the same attribute node to have non-overlapping intervals. tu 3
The syntax of TEG-QL resembles the one of SQL, but queries, as usual in graphs,
are based on pattern matching. Thus, the FROM clause contains one or more paths
(of xed or variable length), over which a selection is performed. The SELECT
clause may either mention just attributes or paths. The temporal semantics in
embedded in the language, i.e., the answer to the query is a temporal graph,
although the query may not mention temporal attributes. This can be changed
by the SNAPSHOT modi er, which allows to retrieve the state of the graph at a
certain point in time, or the IN modi er, which allows retrieving the status of
the graph in a certain interval. Further details can be found in [
Consider the query People and buildings such that a person named John Smith has lived in such buildings. The TEG-QL query is shown on the left hand side of Figure 2. We can see that we take the paths matching the FROM clause, and lter them using the condition in the WHERE clause. Figure 3 (left) shows the result. The center node (in orange) is the Person node that represents John
WHERE Person.Name = 'John Smith'
WHERE Person.Name = 'John Smith' Smith, middle nodes (yellow) nodes are the edge nodes representing the Lived In relationships; and outer nodes (blue) are the Building nodes.
The TEG-QL expression for the query Friends of someone called John Smith is shown in Figure 2 (right); Figure 3 (right) depicts the clusters of people in the result (the ones who know someone with the name \John Smith").
Queries showing the use of the SNAPSHOT and IN modi ers are depicted in Figure 4. The query on the left returns all the people named John Smith, and the buildings where they lived during 1990. Note that we assume a temporal granularity at the year level here (We do not get into the details of how to manipulate granularities here). The IN predicate allows selecting nodes and edges valid in a given interval. The query on the right hand side of Figure 4 is similar to the one above, just selecting those paths existing between 1986 and 1989.
WHERE Person.Name = 'John Smith' SNAPSHOT 1990 SELECT *
WHERE Person.Name = 'John Smith'
IN [1986-1989]
To translate TEG-QL queries into Cypher, we rst translate each path in the
FROM clause. The term element.alias:OBJECTftitle:element.nameg results
from the translation of an object node; an Edge node is translated analogously.
We then expand the SELECT clause with the corresponding attributes. Finally,
the WHERE clause is addressed splitting conjunctions and disjunctions. Details of
the translation process can be found in [
Future work will focus on expanding the temporal capabilities of TEG-QL, and, most of on addressing the problem of query optimization.