Database Theory in Action:
Cypher, GQL, and Regular Path Queries

Assume pairwise disjoint countable sets $𝒩$ of node ids, $ℰ$ of edge ids and $ℒ$ of labels. A graph database is a tuple $G=⟨N,E,\lambda ,\sigma ,\tau ⟩$ where

• $\mathrm{■}$

  $N\subset 𝒩$ is a finite set of node ids used in $G$;

• $\mathrm{■}$

  $E\subset ℰ$ is a finite set of directed edge ids used in $G$;

• $\mathrm{■}$

  $\lambda :N\cup E\to ℒ$ is a labeling function that associates with every id a label from $ℒ$;

• $\mathrm{■}$

  $\sigma ,\tau :E\to N$ define source and target of an edge.

In real Cypher, $\lambda$ can assign sets of labels to a node, and in GQL it can assign sets of labels to edges as well, but since the separating example does not depend on these features (which can also be modeled by considering $2^{ℒ}$ as the new set of labels), we do not use them here.

A path in $G$ is an alternating sequence $n_0{e}_1{n}_1{e}_2\mathrm{\cdots }{e}_k{n}_k$, for $k\ge 0$, of nodes and edges that starts and ends with a node and so that each edge $e_i$ connects $n_{i-1}$ to $n_i$ for $i\le k$. That is, either $e_i$ is a forward edge with $\sigma (e_i)=n_{i-1}$ and $\tau (e_i)=n_i$, or a backward edgewith $\sigma (e_i)=n_i$ and $\tau (e_i)=n_{i-1}$. If $k=0$, the path consists of a single node $n_0$. We explicitly write out paths as $⟨⟨n_0,e_1,n_1,\mathrm{\cdots },e_k,n_k⟩⟩$. Two paths $p=⟨⟨n_0,e_0,\mathrm{\dots },n_k⟩⟩$ and $p^{\prime }=⟨⟨n_0^{\prime },e_0^{\prime },\mathrm{\dots },n_j^{\prime }⟩⟩$ concatenate, if $n_k=n_0^{\prime }$, in which case their concatenation $p\cdot p^{\prime }$ is defined as $⟨⟨n_0,e_0,\mathrm{\dots },n_k,e_0^{\prime },\mathrm{\dots },n_j^{\prime }⟩⟩$.

We refine an abstraction of patterns of GQL from [4], omitting the GQL specific features, and adding Cypher patterns matching repeated edges of a given label. Let $𝒱$ be a countably infinite set of variables. Patterns are defined by

Let $𝒱(\pi )$ be the set of all variables mentioned in $\pi$. The syntactic conditions are:

• $\mathrm{■}$

  conditions in $\pi ⟨\theta ⟩$ are given by $\theta ,{\theta }^{\prime }:=(x=x^{\prime })\mid \theta \vee {\theta }^{\prime }\mid \theta \wedge {\theta }^{\prime }\mid \neg \theta$; all variables mentioned in $\theta$ must occur in $𝒱(\pi )$.

• $\mathrm{■}$

  ${\pi }_1+{\pi }_2$ is only defined when $𝒱({\pi }_1)=𝒱({\pi }_2)$.

In Cypher variables and labels in edge/node patterns are optional, but we include them for simplicity. This does not affect the separating example in which we assume one fixed label for all nodes/edges; the use of variables does not affect expressibility of RPQs. Also, Cypher’s repetitions of labeled edges of the form $n..m$ (between $n$ and $m$) or $n..$ (at least $n$), or $..m$ (at most $m$) are all expressible with concatenation, union, and Kleene star.

The semantics $⟦\pi ⟧$ of a path pattern $\pi$, with respect to a graph database $G$, is a set of pairs $(p,\mu )$ where $p$ is a path and $\mu$ is a mapping $𝒱(\pi )\to N\cup E$ as defined in Fig. 1. Two partial mappings $\mu ,{\mu }^{\prime }:𝒱\to N\cup E$ are joinable if $\mu (x)={\mu }^{\prime }(x)$ for each shared $x$. Their join $\mu \bowtie {\mu }^{\prime }$ is then unambiguously defined as the mapping that coincides with $\mu (x)$ for $x$ in the domain of $\mu$ and ${\mu }^{\prime }(x)$ for $x$ in the domain of ${\mu }^{\prime }$. In the figure, we omit the standard conditions for $\mu \vDash \theta$ for Boolean connectives.

Consider graphs $G_n$ with $N=\{v_1,\mathrm{\dots },v_n\}$ and $E=\{e_1,\mathrm{\dots },e_{n-1}\}$ so that $\sigma (e_i)=v_i$ and $\tau (e_i)=v_{i+1}$ for (i.e., directed paths), with each edge labelled $\mathrm{\ell }$. We can therefore assume that all edge labels used in patterns are $\mathrm{\ell }$ (if not, such a pattern is not matched, and thus the entire subpattern in which it occurred cannot be matched, up to $+$ in the parse tree, and thus can be removed). We can also further assume that no variable is used as both a node variable and an edge variable (as this would falsify the pattern), nor any explicit equality between such variables is used in conditional patterns.

We now represent such graphs $G_n$ as first-order structures $S_n$ in the vocabulary $R,R^{\ast }$ with the universe $N$, and relations interpreted as follows:

• $\mathrm{■}$

  is the edge relation;

• $\mathrm{■}$

  $R^{\ast }=\{(v_i,v_j)\mid 1\le i\le j\le n\}$ is the reflexive transitive closure of $R$.

We next show how patterns are translated into first-order formulae over this vocabulary. We use $R$ for convenience, as it is definable from $R^{\ast }$ which is isomorphic to a linear order on $\{1,\mathrm{\dots },n\}$. We will then easily obtain the inexpressibility results since FO cannot define even cardinality of linear orders.

For the translation, with each pattern $\pi$ we associate two new variables $x_{\pi }^s,x_{\pi }^t$ (intuitively, to be witnessed by the endpoints of patterns), and with each edge variable $z$ used in a pattern we associate two first-order variables $z^s,z^t$ to be used in FO formulas (for source and target of edges). Then a pattern $\pi$ with node variables $y_1,\mathrm{\dots },y_m$ and edge variables $z_1,\mathrm{\dots },z_k$ (all distinct) is translated into an FO formula ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y_1,\mathrm{\dots },y_m,z_1^s,z_1^t,\mathrm{\dots },z_k^s,z_k^t).$ The condition on the translation is that for a path $p=⟨⟨u_0,f_0,u_1,\mathrm{\dots },f_{r-1},u_r⟩⟩$ we have

Now suppose the pattern ${(\mathrm{\ell }\mathrm{\ell })}^{\ast }$ is definable in Cypher over graphs $G_n$ by a pattern $\pi$ as above. Then $\beta (x_{\pi }^s,x_{\pi }^t):=\exists y_1,\mathrm{\dots },y_m,z_1^s,\mathrm{\dots },z_k^t{\alpha }_{\pi }$ is true for $v_i,v_j$ iff the path between them is of even length and therefore the sentence $\gamma :=\exists s,t\left(\neg \exists s^{\prime }R(s^{\prime },s)\wedge \neg \exists t^{\prime }R(t,t^{\prime })\wedge \beta (s,t)\right)$ states the path from $v_1$ to $v_n$ is of even length, which is impossible.

Next, to conclude the proof, we present the translation, recursively.

• $\mathrm{■}$

  If $\pi =(y)$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y):=x_{\pi }^s=x_{\pi }^t\wedge x_{\pi }^t=y$.

• $\mathrm{■}$

  If $\pi =(y_1)\stackrel{z:\mathrm{\ell }}{\to }(y_2)$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y_1,y_2,z^s,z^t):=x_{\pi }^s=y_1\wedge x_{\pi }^t=y_2\wedge z^s=y_1\wedge z^t=y_2\wedge R(y_1,y_2)$.

• $\mathrm{■}$

  If $\pi =(y_1)\stackrel{z:\mathrm{\ell }}{\leftarrow }(y_2)$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y_1,y_2,z^s,z^t):=x_{\pi }^s=y_2\wedge x_{\pi }^t=y_1\wedge z^s=y_2\wedge z^t=y_1\wedge R(y_2,y_1)$.

• $\mathrm{■}$

  If $\pi =(y_1)\stackrel{:{\mathrm{\ell }}^{\ast }}{\to }(y_2)$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y_1,y_2):=x_{\pi }^s=y_1\wedge x_{\pi }^t=y_2\wedge R^{\ast }(y_1,y_2)$

• $\mathrm{■}$

  if $\pi =(y_1)\stackrel{:{\mathrm{\ell }}^{\ast }}{\leftarrow }(y_2)$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,y_1,y_2):=x_{\pi }^s=y_2\wedge x_{\pi }^t=y_1\wedge R^{\ast }(y_2,y_1)$.

• $\mathrm{■}$

  If $\pi ={\pi }_1{\pi }_2$ with ${\pi }_1,{\pi }_2$ translated as ${\alpha }_{{\pi }_1}(x_{{\pi }_1}^s,x_{{\pi }_1}^t,{\overline{v}}_1)$ and ${\alpha }_{{\pi }_2}(x_{{\pi }_2}^s,x_{{\pi }_2}^t,{\overline{v}}_2)$ respectively (where ${\overline{v}}_i$ list variables in those formulae corresponding to node and edge variables in patterns), then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,{\overline{v}}_1,{\overline{v}}_2)$ is defined as

  $$\exists x_{{\pi }_1}^s,x_{{\pi }_1}^t,x_{{\pi }_2}^s,x_{{\pi }_2}^t\left({\alpha }_{{\pi }_1}(x_{{\pi }_1}^s,x_{{\pi }_1}^t,{\overline{v}}_1)\wedge {\alpha }_{{\pi }_2}(x_{{\pi }_2}^s,x_{{\pi }_2}^t,{\overline{v}}_2)\wedge x_{\pi }^s=x_{{\pi }_1}^s\wedge x_{\pi }^t=x_{{\pi }_2}^t\wedge x_{{\pi }_1}^t=x_{{\pi }_2}^s\right)$$

  where in ${\overline{v}}_1,{\overline{v}}_2$ repeated variables are mentioned only once.

• $\mathrm{■}$

  If $\pi ={\pi }_1+{\pi }_2$ with ${\pi }_1,{\pi }_2$ translated as ${\alpha }_{{\pi }_1}(x_{{\pi }_1}^s,x_{{\pi }_1}^t,\overline{v})$ and ${\alpha }_{{\pi }_2}(x_{{\pi }_2}^s,x_{{\pi }_2}^t,\overline{v})$ (note that variables must be the same as the schemas of ${\pi }_1$ and ${\pi }_2$ coincide), then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,\overline{v}):={\alpha }_{{\pi }_1}(x_{\pi }^s,x_{\pi }^t,\overline{v})\vee {\alpha }_{{\pi }_2}(x_{\pi }^s,x_{\pi }^t,\overline{v})$.

• $\mathrm{■}$

  If $\pi ={\pi }_1⟨\theta ⟩$ then ${\alpha }_{\pi }(x_{\pi }^s,x_{\pi }^t,\overline{v}):={\alpha }_{{\pi }_1}(x_{\pi }^s,x_{\pi }^t,\overline{v})\wedge {\theta }^{\prime }$ where ${\theta }^{\prime }$ is obtained from $\theta$ by the following transformations:

  • –

    each condition $y_i=y_j$ stays;

  • –

    each condition $z_i=z_j$ is replaced by $z_i^s=z_j^s\wedge z_i^t=z_j^t$;

  • –

    these are propagated through the Boolean connectives.

It is straightforward to verify that these translations satisfy (1), completing the proof. $◀$

The proof shows that on graphs $G_n$, Cypher patterns fall far short of RPQs. The latter can express every regular property of languages in ${\mathrm{\ell }}^{\ast }$, or in other words test if $n$ belongs to a set which is a finite union of arithmetic progressions. For Cypher patterns, on the other hand, the first-order definability of a pattern $\pi$ in the theory of order implies the existence of the threshold $t$ such that either $(v_1,v_n)$ is selected by $\pi$ for all $n>t$, or $(v_1,v_n)$ is not selected by $\pi$ for all $n>t$.