Most of the current graph database systems have been designed to support property graphs. Surprisingly, there is no standard speci cation of the database model behind such systems. This paper presents a formal de nition of the property graph database model. Specifically, we de ne the property graph data structure, basic notions of integrity constraints (e.g. graph schema), and a graph query language.
A graph database system, or just graph database, is a system speci cally designed
for managing graph-like data following the basic principles of database systems
[
The fundamental abstraction behind a database system is its database model.
A Database Model should de ne three main components: a set of data structure
types (i.e. the data model), a set of query operators or inference rules (i.e. the
query language), and a set of integrity rules [
Despite all of the work already developed around graph databases, the current market of graph databases is fragmented, starting with the lack of consensus about a unique graph data model over which all the systems could be developed. Although most of the systems are designed to store property graphs (i.e. labeled multigraphs where both nodes and edges can contain pairs of the form propertyvalue), there could be considerable di erences among the provided components and their features, specially the de nition of query languages and integrity constraints. The absence of such standardization causes several problems. In particular, the research on methods and techniques applicable to all the systems is very restricted due to the absence of a common theoretical foundation.
The main contribution of this paper is a formal de nition of the property graph database model. Speci cally, we de ne the property graph data structure (Section 2), propose basic notions of integrity constraints (Section 3), and describe a graph query language (Section 4). 1.1
The notion of property graph was introduced by Rodriguez and Neubauer in
[
Informally, a property graph is a directed labelled multigraph with the special characteristic that each node or edge could maintain a set (possibly empty) of property-value pairs. From a data modeling point of view, a node represents an entity, an edge represents a relationship between entities, and a property represents an speci c feature of an entity or relationship. Next we present a formal de nition of the abstract notion described above.
Assume that L is an in nite set of labels (for nodes and edges), P is an in nite set of property names, V is an in nite set of atomic values, and T is a nite set of datatypes (e.g., integer ). Given a set X, we assume that SET+(X) is the set of all nite subsets of X, excluding the empty set. Given a value v 2 V, the function type(v) returns the data type of v. The values in V will be distinguished as quoted strings.
De nition 1. A property graph is a tuple G = (N; E; ; ; ) where: 1. N is a nite set of nodes (also called vertices); 2. E is a nite set of edges such that E has no elements in common with N ; 3. : E ! (N N ) is a total function that associates each edge in E with a pair of nodes in N (i.e., is the usual incidence function in graph theory); 4. : (N [ E) ! SET+(L) is a partial function that associates a node/edge with a set of labels from L (i.e., is a labeling function for nodes and edges); 5. : (N [E) P ! SET+(V) is a partial function that associates nodes/edges with properties, and for each property it assigns a set of values from V.
Given two nodes n1; n2 2 N and an edge e 2 E, such that (e) = (n1; n2), we will say that n1 and n2 are the \source node" and the \target node" of e respectively. Additionally, given a property (o; p) 2 (N [ E) P and the assignment (o; p) = fv1; : : : ; vng, we will use (o; p) = vi with 1 i n as a shorthand representation for a single property where o is the \property owner", p is the \property name" and v is the \property value". Note that our de nition supports multiple labels for nodes and edges, and multiple values for the same property.
Integrity constraints are general statements and rules that de ne the set of
consistent database states or changes of state or both [
A data schema is a powerful data modeling feature that allows to describe the structure of the data and enforce its consistency. In this sense, a graph schema allows to de ne the graph structure by specifying the types of nodes, the types of edges, and the properties for such types. Next, we introduce a basic notion of property graph schema which is enough to be supported by current graph databases. Additionally, we present a set of special constraints that can be added to de ne more strict schemas. Recall that L is an in nite set of labels, P is an in nite set of property names, and T is a nite set of datatypes (e.g., String, Integer, etc.). Informally, a property graph schema de nes the node types, the edge types, and the properties for such types (including the corresponding datatypes).
De nition 2. A property graph schema is a tuple S = (TN ; TE ; ; ) where: 1. TN L is a nite set of labels representing node types; 2. TE L is a nite set of labels representing edge types, satisfying that TE and TN are disjoint; 3. : (TN [ TE ) P ! T is a partial function that de nes the properties for node and edge types, and the datatypes of the corresponding values; 4. : (TN ; TN ) ! SET+(TE ) is a partial function that de nes the edge types allowed between a given pair of node types. Schema-instance consistency. The notion of schema-instance consistency implies that an instance property graph satis es the structural restrictions stablished by a given property graph schema. Such notion is formally de ned as follows. De nition 3. Given a property graph G = (N; E; ; ; ) and a property graph schema S = (TN ; TE ; ; ), we say that G is valid with respect to S when:
3. For each node or edge property (o; p) = v in G, it satis es that there exists (to; p) = dt in S such that to 2 (o) and type(v) = dt; 4. For each edge e 2 E such that (e) = (n; n0), it satis es that there exist le 2 (t; t0) such that le 2 (e), t 2 (n) and t0 2 (n0).
Assume that a graph database is a pair D(S; G) where S is a property graph schema and G is a property graph. We will say that D satis es the schemainstance consistency constraint if G is valid with respect to S. 3.2
Note that the de nition of property graph schema is basic in the sense of allowing the description of the minimal characteristics for the data in a graph database. However, such basic de nition can be extended to support additional constraints. Mandatory and optional properties / edges. Note that the function in De nition 2 does not di erentiate between required and optional properties. In order to support such feature, we can de ne that the domain of can be divided in two sets Pm and Po, i.e. Pm [ Po = dom( ), where Pm is the set of mandatory properties and Po the set of optional properties. Additionally, we need to include the following restriction in De nition 3: \For each pair (t; p) 2 Pm, and every node / edge o in G such that t 2 (o), it applies that (o; p) 2 dom( ), i.e. the node / edge o contains the property p". A similar approach could be applied to introduce mandatory and optional edges.
Unique attributes. Given a node (or edge) type t, it could be useful to de ne an attribute whose value is unique for each instance of t. Given a property graph schema S = (TN ; TE ; ; ), assume that Pu dom( ) is the set of unique properties. Given a property graph G = (N; E; ; ; ), we say that G satis es a unique property (t; p) 2 Pu i , for each pair of distinct objects o1; o2 such that t 2 (o1) and t 2 (o2) it applies that (o1; p) 6= (o2; p).
Cardinality constraints. A cardinality constraint could de ne the number of occurrences of a given property (for a node or edge type), or the precise number of outgoing edges for a given node type. Mandatory and optional constraints could be viewed as cardinality constraints (e.g. an optional property is de ned by a minimal cardinality of 0 and a maximum cardinality of 1). 4
In this section we present a basic graph query language for the property graph data model de ned above. In general terms, a query takes as input a graph (called the target graph), applies graph pattern matching, and returns a table of values as output. The syntax of the language is a combination of three representative query languages (i.e. SQL, SPARQL and Cypher). The semantics of the language are de ned in terms of a transformation to non-recursive safe Datalog with negation. 4.1
The syntax of the query language is based on four main clauses: SELECT, FROM, MATCH and WHERE. These clauses allow to express basic pattern matching queries. Additionally, the query language introduces the UNMATCH and UNION clauses in order to support the negation and union of graph patterns respectively. Pattern matching. The core feature of the language is the support to express a graph pattern which is matched against the target graph. Example 1 shows an example of pattern matching query. In general terms, the SELECT clause de nes the output of the query (speci cally, a table of values), the FROM clause de nes the input graph, the MATCH clause de nes a graph pattern, and the WHERE clause de nes conditions over the graph pattern. Next we describe each clause in detail. Example 1. Example of pattern matching query. The query returns the names of authors which have papers in common, i.e. the co-authorship relationship.
Assume that a property graph database is a collection of property graphs, each one having a name. Hence, the FROM clause de nes a comma separated list of graph names that conforms the graph to be queried. In the Example 1, the FROM clause de nes a single target graph named \biblio" which corresponds to the one presented in Figure 1. In the case of having multiple graphs, the target graph will be the union of nodes and edges occurring in all the graphs.
The MATCH clause allows to de ne a graph pattern which is a collection of basic graph patterns. A basic graph pattern (BGP) is an expression of the form (v1 : t1) [v2 : t2] > (v3 : t3) where v1 and v3 are variables referencing nodes, v2 is a variable referencing an edge, t1 and t3 are node type labels, and t2 is an edge type label. The expression (v1 : t1) is also a valid BGP which allows to obtain the nodes in the graph. To be valid, a BGP must contain at least a node variable. A set of BGPs is called a join graph pattern. In our example, the join GP matches the nodes n1, n2 and n3 such that n1 is of type Entry, n2 is of type Author, n3 does not specify a type. Both n2 and n3 are connected with n1 by an edge has author, and the corresponding edges are bound by variables e1 and e2.
The WHERE clause allows to de ne a lter condition that restrict the subgraphs obtained by the pattern matching step. A lter condition is de ned as a set of equality conditions and build-in functions, connected by the operators AND, OR and NOT. The expressions v1 v2, v1:p1 v2:p2 and v1:p1 a are equality conditions where v1 and v2 are variables, p1 and p2 are property names, a is an atomic value, and is an equality operator in the set f=; ! =; >; >=; <; <=g. In our example, the lter condition indicates that the Authors n2 and n3 must be distinct, and the order of Author n2 is lower than the Author n3. Note that the former condition applies to a node variable, and the latter applies to an edge variable.
Finally, the SELECT clause de nes the output of the query called the result table. A result table is a tabular structure (equivalent to a relational table) where the head contains property names and the body contains atomic values. The SELECT clause de nes a comma separated list of expressions of the form v:p AS c where, v is a variable ocurring in the MATCH clause, p is a property name, and c is the name of the corresponding column in the result table. Hence, the SELECT clause in Example 1 allows to return the following result table.
Author1 Author2 EntryTitle "Mariano" "Alberto" "GraphLog: a Visual Formalism ..." "Alberto" "Peter" "Finding regular simple paths ..." Negation. The negation of graph patterns is supported by including the UNMATCH clause, which also includes a graph pattern expression. In general terms, the MATCH clause is evaluated as a positive graph pattern matching whereas UNMATCH is evaluated as a safe negation of graph patterns. In order to satisfy such safe condition, it is mandatory that at least one node variable of the UNMATCH clause also occurs in the MATCH clause. The UNMATCH clause can be accompanied by its own WHERE clause.
Example 2 shows a negation of graph patterns. First, the MATCH and the WHERE clauses allow to obtain all the pairs of nodes (n2, n3) of type Author (i.e. the cartesian product of authors). Then, the UNMATCH clause allows to remove the pairs of authors having a paper in common. Hence, the result of the pattern matching step is the set of pairs of authors having no papers in common. Example 2. Negation of graph patterns. The query returns the names of authors having no papers in common.
SELECT n2.fname AS Author1, n3.fname AS Author2 FROM "biblio" MATCH (n2:Author), (n3:Author) WHERE n2 != n3
UNMATCH (n1)-[:has_author]->(n2), (n1)-[:has_author]->(n3) Union. Given two join graph patterns, P1 and P2, a union graph pattern is an expression of the form P1 UNION P2. In general terms, the UNION operator combines the solution of P1 with the solutions of P2, the variables of P1 plus the variables of P2. Example 3 shows a query expressing the union of graph patterns. Example 3. Union of graph patterns. The query returns the list of entries in the database, and for each entry it includes the conference's title or the journal's title when necessary.
SELECT n1.title AS EntryTitle, n2.title AS Booktitle, n3.title AS Journal FROM "biblio" MATCH (n1:Entry)-[:booktitle]->(n2:Proceedings)
UNION (n1:Entry)-[:published_in]->(n3:Journal) The result of the query in Example 3 is the following result table:
EntryTitle "GraphLog: a Visual Formalism ..." "Finding regular simple paths ..."
Booktitle "PODS" null
Journal
null "SIAM J. Comput."
Note that above result table contains null values. It occurs when the set of variables of the join graph patterns, connected by the UNION, are di erent. In order to provide a semantics for our query language, we present a method to translate a property graph and a query into a Datalog program. The query transformation allows to show the expressive power of our query language. For the sake of space, the method will be informally presented by using examples. Data transformation. Assume that G is the property graph presented in Figure 1. Then, G could be transformed into the set of Datalog facts presented in Example 4.
Example 4. Datalog rules obtained from a property graph.
Let us explain the meaning of all the facts shown in Example 4. The fact Node(10) encodes a node where 10 is the node identi er. Label(10,"Author") encodes the type of the node having identi er 10 (the same applies to edges). The fact Prop(101,10,"fname","Mariano") encodes a property where 101 is the property identi er and 10 is the identi er of the node having the property (the same applies to edges). edge(20,13,10) encodes an edge where 20 is the edge identi er, 13 is the source node identi er, and 10 is the target node identi er. Note that there are identi ers for nodes, edges and properties. In the case of the properties, the identi ers are fundamental to support multivalued properties. Query transformation. Given the extensional database (of facts) presented above, we can add intentional predicates to query the data, i.e. a Datalog query. For each example graph query Q presented above, we will present a Datalog query Q0 satisfying that Q and Q0 are equivalent, i.e. their results are equivalent.
Example 5 shows a datalog query which is equivalent to the graph query presented in Example 1. The datalog query de nes speci c predicates to represent the main clauses in the graph query, i.e. select(...), match(...) and where(...). Additionally, the predicate gp(...) indicates a graph pattern, jpgX(...) indicates a join graph pattern, and condX(...) indicates a lter condition. In general terms, a pattern matching query is transformed into a set of positive rules.
Example 5. Datalog query equivalent to the query presented in Example 1. Example 6. Datalog query equivalent to the query presented in Example 2. select(v1,v2):- match(n2,n3), Prop(p1,n2,"fname",v1), Prop(p2,n3,"fname",v2) match(n2,n3):- gp(n2,n3), where(n2,n3), not unmatch(n2,n3) gp(n2,n3):- jgp1(n2,n3) jgp1(n2,n3):- bgp1(n2), bgp2(n3) bgp1(n2):- Node(n2), Label(n2,"Author") bgp2(n3):- Node(n3), Label(n3,"Author") where(n2,n3):- cond1(n2,n3) cond1(n2,n3):- jgp1(n2,n3), n2 != n3 unmatch(n2,n3):- jgp2(n1,n2,n3) jgp2(n1,n2,n3):- bgp3(n1,n2), bgp4(n1,n3) bgp3(n1,n2):- Node(n1), Node(n2), Edge(e,n1,n2) Label(e,"has_author") bgp4(n1,n3):- Node(n1), Node(n3), Edge(e,n1,n3) Label(e,"has_author") Example 7. Datalog query equivalent to the query presented in Example 3. Null("null")
Example 6 shows a datalog query which is equivalent to the graph query presented in Example 2. The main di erence is given by the use of the predicate unmatch(...) to implement the negation of graph patterns. In the line 10, we can see that the bindings for unmatch(n2,n3) are given by the join graph pattern jgp2(n1,n2,n3). Additionally, the rule presented in line 3 shows the use of the not operator to implement the \negation by failure" of the predicate unmatch. In order to generate a safe datalog program, we need to ensure that all the variables occurring in unmatch(...) also occur in gp(...).
Example 7 shows a datalog query which is equivalent to the graph query presented in Example 3. In this case, the predicate ugp1(n1,n2,n3) encodes a union graph pattern that combines the predicates bgp1(n1,n2) and bgp2(n1,n3). Considering that bgp1 and bgp2 have disjoint variables, we need to use the Null predicate in order to assign the "null" value when necessary. In this sense, the datalog program must contain the fact Null(null) (see line 13).
The examples presented above show that any graph query can be transformed into a Datalog query. Moreover, it is possible to see that our language supports the same types of queries provided by Datalog, i.e. join, union and equalities. Acknowledgments. Renzo Angles is funded by the Millennium Nucleus Center for Semantic Web Research under Grant NC120004.