Graph databases are one of the most popular type of NoSQL databases [2]. Those databases are specially useful to store data with many relations among the entities, like social networks, provenance datasets or any kind of linked data. One way to store graphs is property graphs, which is a type of graph where nodes and edges can have attributes [1]. A popular graph database system is Neo4j [4]. Neo4j is used in production by many companies, like Cisco, Walmart and Ebay [4]. The data model is like a property graph but with small di erences. Its query language is Cypher. The expressive power is not known because currently Cypher does not have a formal de nition. Although there is not a standard for querying graph databases, this paper proposes a comparison between Cypher, because of the popularity of Neo4j, and conjunctive queries which are arguably the most popular language used for pattern matching.
1.1
Preliminaries
Graph Databases. Graphs can be used to store data. The nodes represent
objects in a domain of interest and edges represent relationships between these
objects. We assume familiarity with property graphs [
A Neo4j graph G is a tuple (V; E; ; ; ; ) where: 1. V is a nite set of nodes, and E is a nite set of edges such that V \ E = ;. 2. ( ; ; ) V E V is a relation such that if (v1; e; v2) 2 there exists a directed edge e from node v1 to v2. 3. ( ; ) V Lab is a relation such that if (x; l) 2 then the label of x is l. is a relation because the Neo4j documentation states that a node can have multiple labels. Lab denotes a set of labels. 4. ( ) : E ! Lab is a total function that maps every edge to its type. 5. is a set of partial functions property : (V [ E) ! Lab. Each function in the set is such that if p(v) = l, then the property p in v has the value l. Conjunctive queries. We assume familiarity with rst order logic and conjunctive queries (CQ). In this paper CQs are stated using the vocabulary of Neo4j graphs, that is, using predicates (V; E; ; ; ; ) and may also use equalities between terms. Conjunctive queries with inequalities (CQ6=) adds to CQs the posibility of using inequalities between terms, and conjunctive queries with negation (CQ6=) extend CQ6= with negated relational atoms.
: 2
Roughly, a Cypher query describes a pattern we want to nd in a graph. The
core of Cypher is based on MATCH and RETURN statements. In order to give the
syntax and semantics for the core of Cypher, we need to de ne a basic graph
pattern (bgp). Our de nition of basic graph patterns is founded on the given
in [
The semantic for a bgp is de ned using mappings. Intuitively a mapping M
represents an homomorphism from the bgp to the Neo4j graph, where constants
are mapped to themselves and variables are mapped to elements in the domain.
When M is applied to Q, the result is a sub-graph of G. The semantic used
in Cypher is a No-repeated-edge semantics [
MATCH queries. In Cypher, the way to declare a pattern that we want to
nd in a graph is to declare a MATCH query, which is de ned below.
De nition 2. Let bgp1; : : : ; bgpn be basic graph patterns. A MATCH query is an
expression with the form MATCH bgp1 : : : MATCH bgpn RETURN v1; : : : ; vm.
The semantics for a pattern matching query in Cypher is de ned as to apply
the RETURN expression over the set of mappings S resulting from the MATCH
expression. Let Si be the set of mappings satisfying the basic graph pattern
bgpi. The result of the expression MATCH bgp1 : : : MATCH bgpn is S1 ./ : : : ./ Sn1,
where the join ./ is de ned over the notion of compatible mappings [
The result of the RETURN v1; : : : ; vm expression applied over the set of mappings S is de ned as the inclusion of only the variables v1; : : : ; vm for each mapping in S (i.e. is the projection of such variables). Also in Cypher it is possible to have unnamed variables that will not be returned. This behaviour can be captured by variables in the bgp that are not returned. 3
In this chapter we provide our results about the comparison between conjunctive queries and pattern matching in Cypher. First we show an example of how a conjunctive query looks like.
Example 1. The following query represents all nodes receiving an edge from a node with label `Montevideo'.
9x19y1V (x1) ^ E(y1) ^ V (x2) ^ (x1; y1; x2) ^
(x1; `City') ^ name(x1) = `Montevideo' Proposition 1. For each conjunctive query over the vocabulary (V; E; ; ; ; ; ), there exists an equivalent MATCH query.
The Proposition 1 holds because an answer for a bgp uses the No-repeatededge semantic. For that reason we cannot transform the conjunctive query into a Cypher query with a single MATCH. So for each appearance of (x1; x2; x3) in the formula, we need a MATCH statement with a di erent bgp.
Proposition 2. There exists a MATCH query that is not equivalent to any conjunctive query over the vocabulary (V; E; ; ; ; ; ).
Since conjunctive queries preserves homomorphisms and a MATCH query does not preserve homomorphisms, there exists queries which are not expressible as conjunctive queries. Then we need to add inequalities to conjunctive queries, in order to express all MATCH queries as a conjunctive query.
Proposition 3. For each MATCH query, there exists an equivalent conjunctive query with inequalities over the vocabulary (V; E; ; ; ; ; ).
The formula that represents the conjunctive query enforces each one of the necessary conditions to satisfy the MATCH query, including the No-repeated-edge semantics. This is because now we can explicitly demand that edges must be di erent in the conjunctive query. Now we present an example. 1 Note that a query with more than one MATCH is useful to avoid the constraint of no repeat edges Example 2. To obtain the paintings in museums located in \Montevideo", we create the following bgp painting bgp:
x1: City fname: Montevideog
y1 `located in' y2 `has' x2: Museum x3: Painting
The query is MATCH painting bgp RETURN x3, and its equivalent CQ is: 9x19x29y19y2 V (x1) ^ V (x2) ^ V (x3) ^ E(y1) ^ E(y2) ^ y1 6= y2 ^ (x2; y1; x1) ^ (x2; y2; x3) ^ (x1; `City') ^ (x2; `Museum') ^ (x3; `Painting') ^ (y1) = `located in' ^ (y2) = `has' ^ name(x1) = `Montevideo' 4
Since we added inequalities to CQs in order to express MATCH queries, we wanted to know the results of the comparison when MATCH queries have also inequalities. This can be done in Cypher through the WHERE statement. This statement lters or puts a constraint to the patterns, which can be any inequality or equality between labels or variables, ask for a bgp representing an eulerian path2, a restriction for only selecting nodes with a xed label, or a negation3. MATCH - WHERE queries. A MATCH - WHERE query in Cypher has at least one MATCH statement, a single WHERE statement and a single RETURN. The de nition is as follows.
De nition 3. Let bgp1; :::; bgpn be bgps. A MATCH - WHERE query is an expression with the form MATCH bgp1 : : : MATCH bgpn WHERE 1 : : : p RETURN v1; : : : ; vm.
The intuition is that only mappings that comply all the restrictions are considered. The RETURN statement is applied as before. Also, it is quite straightforward to construct a conjunctive query with inequalities and negation from a MATCH - WHERE query. Our main result is the following: Theorem 1. MATCH - WHERE queries without negation are equivalent to conjunctive queries with inequalities over the vocabulary (V; E; ; ; ; ; ).
Considering that any conjunctive query can be expressed as a MATCH query, it is not hard to note that if we add inequalities to a query, these can be written in the WHERE statement. If we include negation to the Cypher queries and to the conjunctive queries the result does not hold in one direction.
Proposition 4. Each MATCH - WHERE query (including negation and inequalities) can be expressed as a conjunctive query with inequalities and negation over the vocabulary (V; E; ; ; ; ; ). 2 We use the eulerian path restriction because Neo4j forces the bgps in WHERE clauses to be written in a single statement. 3 Note that Cypher permits more constraints. In particular, Cypher allows nesting of boolean conditions, which will be studied in a future work.
In the other direction, the equivalence is weaker.
Proposition 5. Each query in CQ6= can be expressed as a MATCH - WHERE : query, as long as their negated statements ask for graphs (regardless the direction of the edges) representing an eulerian path.
Finally, we conjecture that there exists a conjunctive query with inequalities and negation over the vocabulary (V; E; ; ; ; ; ) that is not equivalent to any MATCH - WHERE query. The intuition behind is that in Cypher it is impossible to specify a bgp without an eulerian path in the WHERE statement, while a CQ does not have this restriction. We want to prove such proposition in future work. 5
The comparison between Cypher and conjunctive queries can be a starting point for a future formalization for that query language. Despite the di erence between the No-repeated-edge semantic of Cypher and the homomorphisms of conjunctive queries, the core of Cypher based on the MATCH, WHERE without negation, and RETURN statements was proved to be equivalent to conjunctive queries with inequalities. However, the non existence of an equivalence between Cypher with respect to conjunctive queries with union, intersection and di erence is a disadvantage respect to other languages that are de ned over a formal model.
As future work we will study all the open problems presented through the
paper. Also, we are interested in studying another Neo4j functions not covered
by this work, for instance, path functions. It is not clear the semantics given to
a path function in Cypher, but paths are one of the most distinctive features of
this query language with respect to other ones. We would like to compare path
queries against regular path queries, since regular path queries are considered
the core of languages made for querying semistructured data [