Formal Semantics of the Language Cypher
Nadime Francis Alastair Green Paolo Guagliardo Leonid Libkin Tobias Lindaaker Victor Marsault Stefan Plantikow Mats Rydberg Martin Schuster Petra Selmer Andrés Taylor




#1
    #1
    December 30, 2023
=====================






Cypher is a query language for property graphs. It was originally designed
and implemented as part of the Neo4j graph database, and it is currently used
in a growing number of commercial systems, industrial applications and research
projects. In this work, we provide denotational semantics of the core fragment
of the read-only part of Cypher, which features in particular pattern matching,
filtering, and most relational operations on tables.








§ INTRODUCTION


In the last decade, property graph databases <cit.>
such as Neo4j, JanusGraph and Sparksee have become more widespread
in industry and academia.
They have been used in multiple domains,
such as master data and knowledge management, recommendation engines, fraud detection,
IT operations and network management, authorization and access control <cit.>,
bioinformatics <cit.>, social networks <cit.>,



software system analysis
<cit.>, and in investigative journalism <cit.>.

Using graph databases to 
manage graph-structured data confers many benefits
such as explicit support for modeling graph data,
native indexing and storage for fast graph traversal operations,
built-in support for graph algorithms (e.g.,
Page Rank, subgraph matching and so on), and
the provision of graph languages, allowing users to express complex
pattern-matching operations.





This paper is about Cypher, a well-established language for
querying and updating property graph databases, which began life in
the Neo4j product, but has now been implemented commercially in other
products such as SAP HANA Graph, Redis Graph, Agens Graph (over
PostgreSQL) and Memgraph.


























The data model  that is used by Cypher is that of property graphs.


It is the most popular graph data model in
industry, and is becoming increasingly prevalent in academia <cit.>.  The
model comprises nodes, representing entities (such as people,
bank accounts, departments and so on), and relationships
(synonymous with edges), representing the connections or
relationships between the entities.  In the graph model, the
relationships are as important as the entities themselves.  Moreover,
any number of attributes (henceforth termed properties), in the
form of key-value pairs, may be associated with the nodes and
relationships.  This allows for the modeling and querying of complex
data.

The goal of this document is to provide denotational semantics for a core fragment of the read-only
part of Cypher, which features pattern matching, filtering, and most relational operations on tables.
Notable parts that are excluded from this work include all update (write) clauses, line-ordering
and aggregation.
Covered value types include trilean values, integers, strings, lists, maps and paths.



The need for a formal semantics stems from the fact that
Cypher, in addition to being implemented in an industrial product with
a significant customer base, has been picked up by others, and
several implementations  of it exist.

Given the lack of
a standard for the language (which can take many years to
complete, as it did for SQL), it has become pressing to agree on the
formal data model and the meaning of the main constructs.
A formal semantics has other advantages too;
for example, it allows one to reason about the equivalence of queries,
and prove correctness of existing or discover new optimizations. The
need of the formal semantics has long been accepted in the field of
programming languages <cit.> and for several common
languages their
semantics has been fully worked out
<cit.>.
Recently similar efforts have been made for the core SQL constructs
<cit.> with the goal of proving
correctness of SQL optimizations and understanding the expressiveness
of its features. The existence of the formal semantics of Cypher makes
it possible for different implementations to agree on its core features,
and paves a way to a reference implementation against which others
will be compared. We also note that providing semantics for an
existing real-life language like Cypher that accounts for all of its
idiosyncrasies is much harder than for theoretical calculi underlying
main features of languages, as has been witnessed by previous work on
SQL <cit.> and on many programming languages.
















The document is organized as follows.

Section <ref> is an overview of the semantics.

Section <ref> defines the data model that
will be used throughout the document. This includes base data values that
can occur in property graphs or be returned by queries, as well as property
graphs themselves, and finally records and tables on which the semantics of queries
are based.

Section <ref> defines the core mecanism of Cypher that is, pattern matching.

It provides the syntax of patterns, defines the notion of rigid patterns
and explicits how to compute the bag of the paths that satisfy a pattern.

Then, section <ref> provides a formal grammar that defines the syntax
of the fragment of Cypher that is considered in this work.

It is organized around the three main constructs of a Cypher statement: expressions, clauses and queries.

Finally, Section <ref> defines the semantics of Cypher over the
syntax provided in Section <ref>.

More specifically, this section defines how to evaluate an expression as a value, and
to formally specify a Cypher query as a mathematical function that returns tables of values.



It is important to note that the sole purpose of this work is to formally
specify the intended behaviour of Cypher.

It should not be considered as a user's
guide and the reader is assumed to already possess a good understanding of Cypher.





§ GENERAL PRINCIPLES OF THE SEMANTICS




This section provides an overview of the semantics.

Most of the object we refer to are only briefly described here.

All the proper definitions will be given later on.






The key elements of Cypher are as
follows:


  * data model, that includes values, graphs, and tables;

  * query language, that includes expressions, patterns, clauses, and queries.



Values can be simple, such as strings and integers, or composite, such as lists and maps.

Cypher is a language to query data from property graphs.

As usual, such a graph consists of nodes that are linked by directed
edges, called relationships but in addition, relationships bear
types, nodes bear labels and both may bear properties, i.e.
key-value pairs.



Expressions
denote values; patterns occur in MATCH clauses; and queries
are sequences of clauses.

Tables are bags of records, which are partial functions
from (column-)names to values; in other words, tables
are neither line-ordered nor column-ordered.

Each clause denotes a function from tables
to tables and each query returns a table.


To provide a formal semantics of Cypher, we will define one relation and two
functions:


  * The pattern matching relation checks if a path p in a graph G
  satisfies a pattern π, under an assignment u of values to the free
  variables of the pattern. This is written as (p,G,u) π.

  * The semantics of expressions associates an expression , a
  graph G and an assignment u 
  with a value _G,u.

  * The semantics of queries (resp., clauses) associates a query
  Q (resp., clause C) and a graph G with a function Q_G (resp.,
  C_G) that takes a table and returns a table (perhaps with more rows or
  with wider rows).


Note that the semantics of a query Q is a function; thus it should not
be confused with the output of Q.


The evaluation of a query starts with the table containing one empty tuple,
which is then progressively changed by applying functions that provide
the semantics of  Q's clauses. The composition of such functions, i.e., the
semantics of Q, is a
function again, which defines the output as

    output(Q,G)  = Q_G(T_unit)

where T_unit is the table containing a single empty record.



With this basic understanding of the data model and the semantics of the
language, we now explain it in detail. Throughout the description of the
semantics, we shall use the notational conventions in Table <ref>
(they will be explained in the following sections; they are summarized here for
a convenient reference).






§ DATA MODEL





 §.§ Values

We consider three disjoint sets  of property keys,
 of node identifiers and  of relationship identifiers (ids
for short). These sets are all assumed to be countably infinite (so we never run
out of keys and ids). For this presentation of the model, we assume two base
types: the integers , and the type of finite strings over a finite alphabet
Σ (this does not really affect the semantics of queries; these two types
are chosen purely for illustration purposes).

The set  of values is inductively defined as follows:


  * Identifiers (i.e., elements of  and ) are values;

  * Base types (elements of  and Σ^*) are values;

  * ,  and  are values;

  *  is a value (empty list), and if v_1,…,v_m are
  values, for m>0, then v_1,…,v_m is a value. 
  

  *  is a value (empty map), and if k_1,…,k_m are
  distinct property keys and v_1,…,v_m are values, for m > 0, then
  (k_1,v_1),…,(k_m,v_m) is a value. 
  

  * If n is a node identifier, then n is a value. If
  n_1,…,n_m are node ids and r_1,…,r_m-1 are relationship ids,
  for m > 1, then n_1,r_1,n_2,…,n_m-1,r_m-1,n_m is a
  value. We shall use shorthands n and n_1r_1n_2… n_m-1r_m-1n_m.


In the Cypher syntax, lists are [v_1,…,v_m] and maps
are {k_1:v_1,…,k_m:v_m}; we use explicit notation for them to
make clear the distinction between the syntax and the
semantics of values.

We use the symbol “·” to denote concatenation of 
paths, which is possible 
only if the first path ends in a node
where the second starts, i.e., if p_1 = n_1r_1 … r_j-1n_j and p_2 =
n_j r_j … r_m-1n_m then p_1 · p_2 is n_1r_1n_2 …
n_m-1r_m-1n_m.

Every real-life query language will have a number of functions defined on its
values, e.g., concatenation of strings and arithmetic operations on numbers. To
model this, we assume a finite set  of predefined functions that can be
applied to values (and produce new values). The semantics is parameterized by
this set, which can be extended whenever new types and/or basic functions are
added to the language.



























 §.§ Property graphs


Let  and  be countable sets of node labels and relationship types,
respectively. 

A property graph is a tuple G = ⟨ N,R,,,ι,λ,τ⟩ where:


  * N is a finite subset of , whose elements are referred to as the
  nodes of G.

  * R is a finite subset of , whose elements are referred to as the
  relationships of G.

  * R → N is a function that maps each relationship to
  its source node.

  * R → N is a function that maps each relationship to its
  target node.

  * ι (N ∪ R) ×→ is a
  function that maps a (node or relationship) identifier and a property key to
  a value.
  

  
  It is assumed that ι is a total function but that its “non- support” is
  finite: there are only finitely many j∈(N ∪ R) and k∈ such that ι(j,k)≠.

  
  
  
  

  * λ N → 2^ is a function that maps each node id
  to a finite (possibly empty) set of labels.

  * τ R → is a function that maps each relationship
  identifier to a relationship type. 
  
  





  We now refer to the property graph in Figure <ref> and show
  how, for a sample of its nodes and relationships, it is formally represented
  in this model as a graph G = (N,R,,,ι,λ,τ).
  
  
  * N = n_1,…,n_10;
  
  * R = r_1,…,r_11;
  
  * = { 
        r_1    ↦ n_1  ,     r_4    ↦ n_5  ,     
        r_7    ↦ n_6  ,     r_10   ↦ n_6 

        r_2    ↦ n_2  ,     r_5    ↦ n_6  ,     
        r_8    ↦ n_10 ,     r_11   ↦ n_9 

        r_3    ↦ n_4  ,     r_6    ↦ n_6  ,     
        r_9    ↦ n_9     } ;
  
  * = { 
        r_1    ↦ n_2  ,     r_4    ↦ n_2  ,     
        r_7    ↦ n_8  ,     r_10   ↦ n_9 

        r_2    ↦ n_3  ,     r_5    ↦ n_5  ,     
        r_8    ↦ n_7  ,     r_11   ↦ n_5 

        r_3    ↦ n_2  ,     r_6    ↦ n_7  ,    
        r_9    ↦ n_49 ,    } ;
  
  * ι(n_1,name) = Nils, ι(n_2,acmid) = 220,
    ι(n_3,acmid) = 190, …, ι(n_10,name) =
    Thor;
  
  * λ(n_1) = λ(n_6) = λ(n_10) = {Student},  
    λ(n_2) = λ(n_3) = λ(n_4) = λ(n_5) = λ(n_9) =
    {Publication}, 
    λ(n_7) = λ(n_8) = {Researcher};
  
  * τ(r) = 
    authors   for  r ∈{r_1,r_5,r_10} ,
supervises   for  r ∈{r_6,r_7,r_8} ,
cites   for  r ∈{r_2,r_3,r_4,r_9,r_11} .
  






 §.§ Tables

Let  be a countable set of names.  A record is a
partial function from names to values, conventionally denoted as a tuple with
named fields u = (a_1 : v_1,…,a_n : v_n) where a_1,…,a_n are
distinct names, and v_1,…,v_n are values. The order in which the fields
appear is only for notation purposes. We refer to (u), i.e., the domain of
u, as the set a_1,…,a_m of names used in u. Two records u and
u' are uniform if (u)=(u').


If u = (a_1 : v_1,…,a_n : v_n) and u' = (a_1':v_1',…,a_m:v_m') are
two records, then (u,u')


denotes the
record (a_1 : v_1,…,a_n : v_n,a_1':v_1',…,a_m':v_m'), assuming that
all a_i, a_j' for i≤ n, j ≤ m are distinct.  If A =
a_1,…,a_n is a set of names v is a value, then (A:v) denotes the
record (a_1:v, …, a_n:v). We use () to denote the empty record, i.e.,
the 
partial function from names to values whose domain is empty.

If A is a set of names, then a table with fields A is a
bag, or multiset, of records u such that (u)=A. A table
with no fields
is just a bag of copies of the empty record. In most cases,
the set of fields of tables will be clear from the
context, and will not be explicitly stated. Given two tables T and
T', we use T ⊎ T' to denote their bag union, in which
the multiplicity of each record is
the sum of their multiplicities in  T and T'.
If B={b_1,…,b_n} is a bag, and T_b_1,…,T_b_n are
tables, then
_b∈ B T_b stands for T_b_1⊎…⊎ T_b_n.


Finally, we use (T) to denote the result of duplicate
elimination on T, i.e., each tuple of T is present just once in
(T).




§ PATTERN MATCHING












 §.§ Syntax of patterns
 It is important to remember that the Cypher grammar is defined
by mutual recursion of expressions, patterns, clauses, and queries. Here, the
description of patterns will make a reference to expressions, which we will
cover later on; all we need to know for now is that these will denote values.

The Cypher syntax of patterns is given in Figure <ref>, where
the highlighted symbols denote tokens of the language. Instead of the actual
Cypher syntax, here we use an abstract mathematical notation that lends itself
more naturally to a formal treatment.

A node pattern χ is a triple (a,L,P) where:


  * a ∈∪{} is an optional name;

  * L ⊂ is a possibly empty finite set of node labels;

  * P is a possibly empty finite partial map from  to expressions.


For example, the following node pattern in Cypher syntax:


  [style=cypher,mathescape]|(x:Person:Male name: _1, age: _2)|


is represented as (x,{Person,Male},{name↦
e_1,age↦ e_2}), where e_1 and e_2 are the representations of
expressions _1 and _2, respectively. The simplest node
pattern () is represented by (,∅,∅).

A relationship pattern ρ is a tuple (d,a,T,P,I) where:


  * d ∈{,,} specifies the direction of the
  pattern: left-to-right (), right-to-left (), or undirected
  ();

  * a ∈∪{} is an optional name,

  * T ⊂  is a possibly empty finite set of relationship types;

  * P is a possibly empty finite partial map from  to
  expressions; 

  * I is either  or (m,n) with m,n∈∪{}.


Table <ref> gives a few relationship patterns
and their mathematical representations.

As highlighted by these examples, I is  if and only if
the optional grammar token  does not appear in syntax of the pattern
(see Figure <ref>);
otherwise, I is equal to (,) if  derives to ∗ and
I is equal to (d,d), (d_1,), (,d_2), (d_1,d_2) if other
derivations rules are applied, respectively.









In general, I defines the range of the relationship pattern.

The range is [m,n] if I=(m,n) where  is
replaced by 1 and ∞ in the
place of the lower and upper bounds.

The range is [1,1] if I=.

A relationship pattern is said rigid if its range [m,n] satisfies: m=n ∈.




A path pattern is an alternating sequence of the form

    χ_1  ρ_1  χ_2  …  ρ_n-1  χ_n

where each χ_i is a node pattern and each ρ_i is a relationship
pattern. A path pattern π can be optionally given a name a,
written as π/a; we then refer to a named pattern. A path
pattern is rigid if all relationship patterns in it are rigid, and
variable length otherwise.

We shall now define the satisfaction relation for path patterns w.r.t. a
property graph G = (N,R,,,ι,λ,τ), a path with node ids
from N and relationship ids from R, and an assignment u.

We consider rigid patterns first as a special case, because they – unlike
variable length patterns – uniquely define both the length and the possible
variable bindings of the paths satisfying them. The satisfaction of variable
length patterns will then be defined in terms of a set of rigid patterns.




 §.§ Satisfaction of rigid patterns

As a precondition for a path p to satisfy any pattern (i.e. for (p,G,u) π to hold), it is necessary that all relationships in p are distinct.

Then, the definition is inductive, with the
base case given by node patterns (which are trivially rigid path patterns).

Let χ be a node pattern (a,L,P); then (n,G,u) χ if all of
the following hold:


  * either a is  or u(a)=n;

  * L ⊆λ(n);

  * nk = P(k)_G,u= for each k s.t. P(k) is defined.





  
  Consider the property graph G in Figure <ref> and the node
  patterns χ_1 = (x,{Teacher},∅) and χ_2 =
  (y,∅,∅). Then,
  
    (n_1,G,u)    χ_1       if u is an
          assignment that maps x to n_1 ,
    
        (n_2,G,u)    χ_1       for any assignment u ,
    
        (n_3,G,u)    χ_1       if u is an
          assignment that maps x to n_3 ,
    
        (n_4,G,u)    χ_1       if u is an
          assignment that maps x to n_4 .

  For i = 1,…,4 we have that (n_i,G,u_i) χ_2 whenever u_i
  is an assignment that maps y to n_i. 


For the inductive case, let χ be a node pattern, let π be a rigid
path pattern, and let ρ be the relationship pattern (d,a,T,P,I).







First we assume that I≠ nil, hence since ρ is rigid, the
range defined by I is [m,m] with m∈.

For m = 0, we have that (n · p,G,u) χρπ if


  * either a is  or u(a) =; and

  * (n,G,u)χ and (p,G,u)π.


For m ≥ 1, we have that (n_1 … r_mn_m+1· p,G,u) χρπ if all of the following hold:


  * either a is  or u(a) = r_1, …, r_m;





  * (n_1,G,u)χ and (p,G,u)π;


and, for every i ∈{ 1, …, m }, all of the following hold:


  * τ(r_i) ∈ T;

  * r_ik = P(k)_G,u = for every k s.t. P(k) is
  defined;

  * ((r_i),(r_i)) ∈{(n_i,n_i+1),(n_i+1,n_i)}   if d is  ,
{(n_i,n_i+1)}   if d is  ,
{(n_i+1,n_i)}   if d is  .



Second, the case I= is treated as if I=(1,1) with the exception that
item (a) is replaced by:  [label=(*'),start=1]
  
  * either a is  or u(a) = r_1



  
  Consider again the property graph G in Figure <ref> and the
  following rigid pattern π in Cypher syntax:
  

    [style=cypher]!(x:Teacher) -[:KNOWS*2]-> (y)!
  

  In our mathematical representation this amounts to:
  
    (x,{Teacher},∅)_χ_1 , (→,,{knows},∅,(2,2))_ρ , (y,∅,∅)_χ_2

  where χ_1 and χ_2 are the node patterns we have seen in
  Example <ref>. 
  Now, let u = { x ↦ n_1, y ↦ n_3 }; from that example we know
  that (n_1,G,u) χ_1 and (n_3,G,u) χ_2. 
  Then, following the definition of satisfaction given above, one can easily see
  that (p,G,u) π, where p = n_1r_1n_2r_2n_3 and π =
  χ_1ρχ_2.
  
  
  
  
  

  Observe that if there is another assignment u' s.t. (p,G,u')π,
  then u' maps x to n_1 and y to n_3.  This is the intuitive reason
  why rigid patterns are of interest: given a path and a rigid pattern, there
  exists at most one possible assignment of the free variables (which we
  shall formally define shortly) of the pattern w.r.t. which the path
  satisfies the pattern. We will see that for variable length patterns this is
  no longer the case. 


For named rigid patterns, we have that (p,G,u)π/a if u(a) = p and
(p,G,u)π.




 §.§ Satisfaction of variable length patterns
 
Informally, a variable length pattern is a compact representation for a possibly
infinite set of rigid patterns; e.g., a pattern of length at least 1 will
represent patterns of length 1, patterns of length 2, and so on.

To make this idea precise, let ρ = (d,a,T,P,(m,n)) be a variable length
relationship pattern, and ρ' = (d,a,T,P,(m',m')) be a rigid relationship
pattern.

We say that ρ subsumes ρ', and write ρ⊐ρ', if m' belongs to the range [m,n] defined by I.

If ρ is rigid, then it only subsumes itself.


all of the following hold:


  * m = 0 or n = 0, whenever m' = 0;

  * m ≥ m', whenever m ∈ and m' ≥ 1;

  * n ≥ m', whenever n ∈ and m' ≥ 1.

 
This subsumption relation is easily extended to path patterns. Given a variable
length pattern π=χ_1ρ_1χ_2…χ_k-1ρ_k-1χ_k and a
rigid pattern π'=χ_1ρ'_1χ_2 …χ_k-1ρ'_k-1χ_k, we
say that π subsumes π' (written π⊐π') if ρ_i
⊐ρ'_i for every i ∈{ 1, …, k-1 }.

Then, we define the rigid extension of π as

    (π) = { π' |π'  is rigid and π⊐π'  } ,

that is, the (possibly infinite) set of all rigid patterns subsumed by π.
For a named pattern, (π/a) = {π'/a |π' ∈(π)}.
Finally, (p,G,u) π if (p,G,u) π' for some π' ∈(π), and similarly for named patterns.




  
  Consider the following variable length pattern π:

(x:Teacher) -[:KNOWS*1..2]-> (z)
            -[:KNOWS*1..2]-> (y:Teacher)

  That is, π is the pattern χ_1ρχ_2ρχ_3 with
  
    χ_1    = (x,{Teacher},∅)  ,
           χ_3    = (y,{Teacher},∅)  ,
    χ_2    = (z,∅,∅)  ,
           ρ   = (,,{knows},∅,(1,2))  .

  Then, (π) is the set
  
    { χ_1ρ_1χ_2ρ_1χ_3_π_1 , χ_1ρ_1χ_2ρ_2χ_3_π_2 , χ_1ρ_2χ_1ρ_1χ_3_π_3 , χ_1ρ_2χ_2ρ_2χ_3_π_4 }

  where
  
    ρ_1 = (,,{knows},∅,(1,1)) ,  ρ_2 = (,,{knows},∅,(2,2)) .


  Consider again the property graph G in Figure <ref>. Let
  
    p_1    = n_1r_1n_2r_2n_3 
            u_1    = { x ↦ n_1, y ↦ n_3, z ↦ n_2 }
    
        p_2    = n_1r_1n_2r_2n_3r_3n_4 
            u_2    = { x ↦ n_1, y ↦ n_4, z ↦ n_2 }

  Then, (p_1,G,u_1) π_1 and (p_2,G,u_2) π_2; therefore,
  π is satisfied in G by p_1 under u_1 and by p_2 under u_2.  This
  shows the ability of a variable length pattern to match paths of varying
  length.

  In addition, variable length patterns may admit several assignments even for a
  single given path. To see this, note that p_2 satisfies π in G also under the assignment u'_2 that agrees with u_2 on x and y but
  maps z to n_3, because (p_2,G,u'_2) π_3.
  


In Cypher, we want to return the “matches” for a pattern in a graph, not
simply check whether the pattern is satisfied (i.e., there exists a match). This
is captured formally next.




 §.§ Pattern matching
 

The set of free variables of a node pattern χ=(a,L,P), denoted by
(χ), is {a} whenever a is not , and empty
otherwise. For a relationship pattern ρ, the set (ρ) is
defined analogously.  Then, for a path pattern π we define (π)
to be union of all free variables of each node and relationship pattern
occurring in it.  For example, for the pattern π of
Example <ref> we have (π) = {x,y,z}. 
For named patterns, (π/a)= (π) ∪{a}.

Then, for a path pattern π (optionally named),
a graph G and
an assignment u, we define

    (π,G,u)  = _
            p  in  G
    π' ∈(π)  {  u'  |[           (u')=(π)-(u); and  (p, G, u · u') π' ].}

Note that, even though both u' and π' range over infinite sets, only a
finite number of values contribute to a non-empty set in the final union. Thus
(π,G,u) is finite.

In (<ref>),  stands for bag union: whenever a new
combination of π' and p is found such that (p,G,u · u') π', a new occurrence of u' is added to (π,G,u). This is in line
with the way Cypher combines the MATCH clause and bag semantics,
which is not captured by the satisfaction relation alone.


  
  Consider once again the graph G in Figure <ref>, and let π
  be the following variable length pattern:

(x:Teacher) -[:KNOWS*1..2]-> ()
            -[:KNOWS*1..2]-> (y:Teacher)

  This is similar to the pattern in Example <ref>, but
 the middle node pattern is not given any name here:
  (π) = {x,y}. Indeed, (π) is the same as in the
  previous example, with χ_2 = (,∅,∅).

  Let p = n_1r_1n_2r_2n_3r_3n_4 and u = {x ↦ n_1,y ↦ n_4};
  it is easy to see that (p,G,u) π_3 ∈(π). However,
  observe that (p,G,u)π_2 as well (whereas π_1 and π_4 are
  not satisfied by any path of G). This shows that there may be multiple ways
  for a single path to satisfy a variable length pattern even under the same
  assignment. 
In our example, two
  copies of u will be added to (π,G,∅).  









 §.§ Matching tuples of path patterns
 
Cypher allows one to match a tuple π̅= (π_1,…,π_n) of path
patterns, each optionally named. We say that π̅ is rigid if all its
components are rigid, and (π̅) is defined as (π_1)
×…×(π_n). The set of free variables of π̅ is
defined as (π̅) = ⋃_π_i(π_i).

Let p̅ = (p_1,…,p_n) be a tuple of paths;
we write (p̅, G, u) π̅ if
no relationship id
occurs in more than one path in p̅ and (p_i,G,u)π_i
for each i ∈{1,…,n}.








Then, for a tuple of patterns π̅, a graph G and an assignment u,
(π̅,G,u) is defined as in (<ref>), with the difference
that the bag union is now over tuples π̅'∈(π)
and p̅ of paths.







§ COMPLETE SYNTAX




We now present the key components of Cypher, namely expressions, clauses, and queries, and define their formal semantics. Together with
pattern matching defined in the previous section, they will constitute the
formalization of the core of Cypher.


































The syntax of Cypher patterns was given in Figure <ref>.

Expressions derives from the token , whose derivation rules are shown
in Figure <ref>.

Similarly, queries derive from the token 
(Figure <ref>) and clauses from the token 
(Figure <ref>).














































§ COMPLETE SEMANTICS






 §.§ Semantics of expressions


The semantics of an expression e is a value e_G,u in 
determined by a property graph G and an assignment u that provides bindings
for the names used in e.

The rules here are fairly straightforward and given in details below.





Assume that we are given a fixed property graph
G = (N,R,s,t,ι,λ,τ) and a fixed record u = (a_1 : v_1,…,a_n : v_n) that
associates values v_1,…,v_n with names a_1,…,a_n.




  
Values and variables




	
  * v_G,u = v 

	where v is a value.
	
  * a_G,u = u(a) 

	where a is a name that belongs to the domain of u.
	
  * f(e_1,…,e_m)_G,u = f(e_1_G,u,…,e_m_G,u)

	where
		e_1,…,e_m are expressions, and f is any
          m-ary function in  from values to
		values.




  
Maps

	
  * e.k_G,u = {[                               ι(e_G,u,k)                                       if                                  e_G,u∈∪;                                      w_i                                       if e_G,u = (k_1,w_1),(k_2,w_2),…, (k_m,w_m);                                                                        and  k=k_i;                                                                                if e_G,u = (k_1,w_1),(k_2,w_2),…, (k_m,w_m);                                                                  and  k∉k_1,…,k_m;                                                                                or                                  e_G,u =;                                                                                or                                  e_G,u = ].

		where k and the k_i's are property keys, and w and the w_i's are values.

	
  * k_1:e_1,…,k_m:e_m_G,u = map((k_1,e_1_G,u),…,(k_m,e_m_G,u))

		where k_1,…,k_m are distinct property keys and e_1,…,e_m are expressions.

	
  * k_1:e_1,…,k_m:e_m_G,u = k_i_1:e_i_1,…,k_i_ℓ:e_i_ℓ_G,u

		where k_1,…,k_m are property keys, e_1,…,e_m are expressions, and
		i_1,…,i_ℓ are distinct indices such that k_i_1,…,k_i_ℓ = k_1,…,k_m
		and for each p such that i_p < m, k_i_p∉k_i_p+1,…,k_m. In other
		words, if there are repeated keys among k_1,…,k_m, only the last occurrence of each key
		is kept.

	
  * _G,u = map()




  
Explicit Lists


	
  * e_1,…,e_m_G,u = e_1_G,u,…,e_m_G,u

		where e_1,…,e_m are expressions.
	
  * _G,u =




  
Operations on non-empty lists Assume that e is an expression such that
e_G,u = w_0,…,w_m-1 for some values
w_0,…,w_m-1. Then the semantics of list expressions is as
follows.


	
  * e[e']_G,u = {[                   w_i          if  0≤ i < m;                 w_m+i        if  -m ≤ i < 0;                       if  i < -m  or  i ≥ m ].

		where e'_G,u = i, for some integer i.

	
  * e[e_1..e_2]_G,u = {[ w_max(0,i'),…,w_min(m-1,j'-1)   if  i' ≤ j', i' < m, j' > 0;                                                   otherwise ].

		where e_1_G,u = i for some integer i, e_2_G,u = j for some integer j,
		i' = i if i ≥ 0 and i' = m+i otherwise, j' = j if j ≥ 0 and j' = m+j
		otherwise.

	
  * e[e_1..]_G,u = e[e_1..m]_G,u

	
  * e[..e_2]_G,u = e[0..e_2]_G,u

	
  * e' IN e_G,u = {[                                                if  e' = w_i _G,u =  ,;                                          for some integer i, 0≤ i < n;                                    if the previous case does not hold;                                               and  e' = w_i _G,u =  ,;       for some integer i, 0≤ i < n;                                                             otherwise ].




  
Operations on empty lists Assume that e is an expression such that
e_G,u =.  Then the semantics of list expressions is as
follows.



	
  * e[e']_G,u =

          where e'_G,u = i for some integer i.

	
  * e[e_1..e_2]_G,u =

		where e_1_G,u = i for some integer i and e_2_G,u = j for some integer j.

	
  * e[e_1..]_G,u =

		where e_1_G,u = i for some integer i.

	
  * e[..e_2]_G,u =

		where e_2_G,u = j for some integer j.

	
  * e' IN e_G,u = 

	      where e'_G,u is defined.





  
Strings Assume that e and e' are expressions such that e_G,u
and e'_G,u belong to Σ^* ∪{}.


	
  * e  STARTS WITH e'_G,u =
		{[                           if ∃ s, e_G,u = e'_G,u· s;                                          if e_G,u =;               or e'_G,u =;                                           otherwise ].




	
  * e  ENDS WITH e'_G,u =
		{[                           if ∃ s, e_G,u = s ·e'_G,u;                                          if e_G,u =;               or e'_G,u =;                                           otherwise ].




	
  * e  CONTAINS e'_G,u =
		{[                             if e_G,u = s_1 ·e'_G,u· s_2;    for some strings s_1,s_2;                                              if e_G,u =;                 or e'_G,u =;                                               otherwise ].







  
Logic

Assume that e and e' are expressions such that e_G,u
and e'_G,u both belong to ,,.


	
  * e OR e'_G,u = {[                         if e_G,u =  or e'_G,u =;                             if e_G,u = e'_G,u =;                                       otherwise ].
	
  * e AND e'_G,u = {[                             if e_G,u = e'_G,u =;                         if e_G,u =  or e'_G,u =;                                       otherwise ].
	
  * e XOR e'_G,u = {[                                   if e_G,u =  or e'_G,u =;                              if e_G,u = e'_G,u and e_G,u≠;                                                 otherwise;                              ].
	
  * NOT e_G,u = {[            if e_G,u =;            if e_G,u =;            if e_G,u =;            ].




  
Value Comparisons



    Nulls
 The rules follow SQL: in an expression,
if an argument is , then the value of the expression is . The
semantics of IS NULL is also the same as for SQL.


	
  * e ⋆ e'_G,u = if either e_G,u = or e'_G,u =,
		for ⋆∈<,<=,>=,>,=,<>.

	
  * e  IS NULL_G,u = {[            if e_G,u =;             if e_G,u≠;            ].

	
  * e  IS NOT NULL_G,u = {[             if e_G,u≠;            if e_G,u =;            ].




    Base Types
 Assume that both e and e' are expressions
such that e_G,u  and e'_G,u are of the same base type.


	
  * e = e'_G,u =
		{[                   if e_G,u = e'_G,u;                           otherwise ].




    Identifiers
 Assume that both e and e' are expressions
such that e_G,u  and e'_G,u are both node identifiers
or both relationship identifiers.


	
  * e = e'_G,u =
		{[                   if e_G,u = e'_G,u;                           otherwise ].




    Empty maps


Assume that both e and e' are expressions such that both
e_G,u  and e'_G,u are maps, and one of
them is .


	
  * e = e'_G,u =
		{[                     if e_G,u = e'_G,u =;                               otherwise ].




    Non-empty maps, same number of keys


Assume that  e_G,u = k_1:w_1,…,k_m:w_m and
e'_G,u = k'_1:w'_1,…,k'_m:w'_m, where k_1,…,k_m,k'_1,…,k'_m are
keys, and w_1,…,w_m,w'_1,…,w'_m are values, and m ≥ 1.


	
  * e = e'_G,u =
		{[                                                                                                                                                                                    if                                                                    k_1,…,k_m = k'_1,…,k'_m;                                                                                                                                                                                                                                           and e.k_i = e'.k_i_G,u =  for all i≤ m;                                                                                                                                                                                    if                                                                    k_1,…,k_m = k'_1,…,k'_m;                                                                                                                                                                                        and e.k_i =
                          e'.k_i_G,u =  for some
                        i≤ m;                                                                                                                                                                                       and e.k_i =
                          e'.k_i_G,u≠  for
                          all i ≤ m;                                                                                                                                                                           2lotherwise ].





    Non-empty maps, different number of keys


Assume that  e_G,u = k_1:w_1,…,k_m:w_m and
e'_G,u = k'_1:w'_1,…,k'_l:w'_l, where k_1,…,k_m,k'_1,…,k'_l are
keys, and w_1,…,w_m,w'_1,…,w'_l are values, m,l ≥ 1,
and m ≠ l. In this case,  e = e'_G,u =.






    Lists


Assume that both e and e' are expressions such that both e_G,u  and e'_G,u
are list values.


	
  * e = e'_G,u = 
where e_G,u = e'_G,u =
	
  * e = e'_G,u = 
 where e_G,u = w_1,…,w_n and e'_G,u = w'_1,…,w'_m and n≠ m.
        
  * e = e'_G,u =
		{[                                                              if           ∀ i, w_i = w'_i_G,u =;                                                              if the previous case does not hold;                                                                       and ∀ i, w_i = w'_i_G,u∈,;                                                     2lotherwise ].

	where e_G,u = w_1,…,w_m , e'_G,u = w'_1,…,w'_m and w_1,…,w_m,w'_1,…,w'_m are values.




    Paths


Assume that both e and e' are expressions such that  both e_G,u  and e'_G,u
are path values.


	
  * e = e'_G,u =
		{[                   if e_G,u = e'_G,u;                           otherwise ].




    Mismatched composite types


If e and e' are expressions such that e_G,u is a value of a composite type (map, list, path) and e'_G,u is a non-null value of a different type, then e = e'_G,u =. Conversely, if e'_G,u is of a composite type and e_G,u is a non-null value of a different type, then e = e'_G,u =.



    Base types


If e and e' are expressions such that e_G,u and e'_G,u are non-null values of a non-composite type,
then e ⋆ e'_G,u is allowed to be
implementation-dependent, for ⋆∈<,<=,>=,>. That
is, for base types implementations have freedom when it comes to
defining ordering. It is assumed however that for types considered
here (numerical and strings), these are fixed and have their standard
interpretation as ordering on numbers, and lexicographic ordering for
strings.




















































 §.§ Semantics of queries


A query is either a sequence of clauses ending with the RETURN
statement, or a union (set of bag) of two queries. The RETURN statement
contains the return list, which is either ∗, or a sequence of
expressions, optionally followed by AS a, to provide their names.

To provide the semantics of queries, we assume that there exists an
(implementation-dependent) injective function α that maps expressions to
names. Recall that the semantics of both queries and clauses, relative to a
property graph G, is a function from tables to tables, so we shall describe
its value on a table T, i.e., _G(T).










  
Return We make the following assumptions. First, the fields of T are
b_1,…,b_q. Second, if we have a return list e_1  [AS a_1],
…, e_m  [AS a_m] with optional AS for some of the
expressions, then a_i'=a_i if AS a_i is present in the list, and
a_i'=α(e_i) otherwise, with the added requirement that all the a'_is
are distinct. In some rules for the semantics, some AS could be
optional. It is assumed that when such optional AS is present on the left
side, then it is also present on the right hand side.


  
  * RETURN *_G(T)  = T  if T has at least one
  field
  
  * RETURN *, e_1  [AS a_1], …, e_m
   [AS a_m]_G(T) =
RETURN b_1  AS b_1,…,b_q  AS b_q, e_1  [AS a_1], …, e_m  [AS a_m]_G(T)
  
  * RETURN e_1  [AS a_1], …, e_m
   [AS a_m]_G(T) =
_u∈ T{(a'_1 : e_1_G,u,
                   …, a'_m : e_m_G,u)}






  
Union  Let Q_1, Q_2 be queries.


  
  * Q_1  UNION ALL Q_2_G(T) = Q_1_G(T) ∪Q_2_G(T)

  
  * Q_1  UNION Q_2_G(T) = (Q_1_G(T) ∪Q_2_G(T)) 

  (Recall that  is the function computing duplicate elimination.)





  
Clause list


  
  * C Q_G(T) =  Q_G (C_G(T))

        where C is a clause and Q is a query.





























Thus, as was already informally explained, evaluation of a Cypher query starts
with the table containing one record with no fields, and consecutively applies
clauses, populating the table, by both expanding the fields of its records, and
adding records (how this is done will be seen shortly when we present the
semantics of clauses). Finally, one reach the RETURN clause, which
generates the return of the query, in a fashion similar to SQL's SELECT.


































































 §.§ Semantics of clauses


The meaning of Cypher clauses is again functions that take tables to
tables.

Matching clauses are essentially
pattern matching statements: they are of the form OPTIONALMATCH  WHERE. Both OPTIONAL
and WHERE could be omitted. The key to their semantics is pattern
matching, in particular (π̅, G, u) described in
Section <ref> (see Equation (<ref>), page match-eq).

The MATCH clause extends the set of field names of T by adding to it
field names that correspond to names occurring in the pattern but not in u. It
also adds tuples to T, based on matches of the pattern that are found in
graphs. UNWIND is another clause that expands the set fields, and
WITH clauses can change the set of fields to any desired one.

The WHERE subclause also defines a table-to-tables function that
filters lines according to the evaluation of an expression; it is not a proper
clause because of its interaction with OPTIONAL MATCH clauses.





  
Matching clause The semantics of MATCH clauses is defined below; the
semantics of WHERE subclause is defined afterwards.




  * MATCH π̅_G(T)  = _u∈ T{u · u' | u' ∈(π̅, G, u)}


  * MATCH π̅ WHERE e_G(T)
  = WHERE e(MATCH π̅_G(T) )


  * OPTIONAL MATCH π̅ WHERE e_G(T)
 = _u ∈ T{[       MATCH π̅ WHERE e_G(u) if MATCH π̅ WHERE e_G(u) ≠∅;           (u,(free(u,π̅):))                   otherwise;                             ].


  * OPTIONAL MATCH π̅_G(T)  = OPTIONAL MATCH π̅ WHERE _G(T)



  Let G be the property graph defined in Figure <ref>. consider
  the clause MATCH π, where π is the pattern
  

    [style=cypher]!(x) -[:KNOWS*]-> (y)!
  

  Let T be the table (x:n_1);(x:n_3) with a single field x. We show
  how to compute MATCH π_G(T).

  Note that (π) is the (infinite) set of all rigid paths
  π_m=(,,{knows},m,m), for m > 0.
  These can only be satisfied by paths with exactly m distinct
  relationships. Since G only contains 3 relationships, only
  π_1, π_2 and π_3 can contribute to the   result.

  Let u = (x:n_1), π' = π_1 and p =
  n_1r_1n_2. Then (π_1)-(u) = y, and thus u' must
  be a record over the field y. One can easily check that
  (n_1r_1n_2,G,(x:n_1,y:n_2))π_1. In fact n_2
  is the only suitable value for y, and thus the contribution of this
  specific triple u,π',p to the final result is precisely (x:n_1 ,
    y:n_2).

  No path p other than n_1r_1n_2 can contribute a record
  in the case where u = (x:n_1) and π' = π_1. Indeed, π_1 requires
  p to be of length 1,  and start at x, which u
  evaluates to be n_1.  By a similar reasoning,
  we can compute the  contribution of the following triples:
  
  
  * (x:n_1,y:n_3), π_2, n_1r_1n_2r_2n_3  yields  (x:n_1,y:n_3);
  
  * (x:n_1,y:n_4), π_3, n_1r_1n_2r_2n_3r_3n_4  yields  (x:n_1,y:n_4);
  
  * (x:n_3,y:n_4), π_1, n_3r_3n_4  yields  (x:n_3,y:n_4);
  
  and show that the contributions of all other possible combinations of records,
  paths and patterns are empty. This tells us that MATCHπ_G(T) is the following table:
  

    
      x     y 

      n_1     n_2 

      n_1     n_3 

      n_1     n_4 

      n_3     n_4 

      
  








  
Where subclause
  Although WHERE is not a clause per say, its semantics is also a table
  to table function.


  
  * WHERE e_G(T)  = u ∈ T  |
   e_G,u =




  
With clause


Similarly to the description of the semantics of RETURN queries, we make
the assumption that the fields of T are
b_1,…,b_q. Our convention about the names a_i' are exactly the same as
for queries (see above), except that a_i'=α(e_i) only if e_i is a name.


  
  * WITH *_G(T)  =  T  
 if T has a least one field

  
  * WITH e_1  [AS a_1], …, e_m
   [AS a_m]_G(T)
=
_u∈ T(a_1' : e_1_G,u, …, a_m' : e_m_G,u)

  
  * WITH *, e_1  [AS a_1], …, e_m
   [AS a_m]_G(T)
=
WITH b_1  AS b_1,…, b_q  AS b_q,
  e_1  [AS a_1], …, e_m  [AS a_m]_G(T)

  
  * WITH  WHERE e_G(T)
              =
WHERE e_G(WITH _G(T))





  
Unwind Clause


  
  * UNWIND e  AS a_G(T) = _u∈
  T_v∈ E_u(u,a:v) ,
 where E_u  = {[                _0 ≤ i < mv_i if e_G,u = list(v_0,…,v_m-1);                                         if e_G,u = list();                        e_G,u                    otherwise ].







