PVLDB Reference Format:
Amelie Gheerbrant, Leonid Libkin, Liat Peterfreund, and Alexandra Rogova. . PVLDB, 18(6): 1798 - 1810, 2025.
doi:10.14778/3725688.3725707

¹

1 Introduction↩︎

In the past two years, ISO published two new international standards. SQL/PGQ, released in 2023, as Part 16 of the SQL standard, provides a mechanism for representing and querying property graphs in relational databases using SQL. GQL, released in 2024, is a standalone graph query language that does not rely on a relational representation of graphs. SQL/PGQ and GQL are developed in the same ISO committee that has been maintaining and enhancing the SQL standard for decades. These developments reflect the interest of relational vendors in implementing graph extensions and the emergence of a new native graph database industry.

There is however a notable difference between this standardization effort and that of SQL as it happened in the 1980s. Before SQL was designed, strong theoretical and practical foundations of relational databases had been developed. Equivalence of relational algebra and calculus (first-order logic) had been known; these provided very clean abstractions of relational languages that served as the basis of relational database theory. This has had a profound impact on both the theory and the practice of database systems. For example, a question of central importance in the early days of relational databases was expressiveness of query languages, with Fagin, Aho, Ullman, Gaifman, and Vardi independently showing that relational calculus cannot define the transitive closure of a relation [1]–[3]. This led to subsequent development of Datalog and culminated in the inclusion of linear recursive queries by the SQL standard in 1999 [4].

When it comes to graphs, the adoption of languages by industry runs well ahead of the development of their foundational underpinnings. For many years, work on graph queries concentrated on regular path queries (RPQs) [5] and their multiple extensions (e.g., [6]–[9], crpq?). These however assume a much simplified model in which neither nodes nor edges have properties, unlike property graphs preferred in industry. A step in that direction is the model of data graphs in which nodes but not edges carry data [10]. To this day, these models are the basis of work on query language expressiveness [11], [12]. But we will see soon that from the point of view of GQL and SQL/PGQ, a full property graph model makes a huge difference. Existing theoretical languages such as GXPath [10], regular queries [13], STRUQL [14], while having a direct influence on the design of GQL [15], are not a good reflection of it.

At the same time, extensive discussions in the standards committees are already under way to identify new features of SQL/PGQ and GQL, based on their perceived, rather than proved, shortcomings [16], [17]. These considerations motivate our main contributions:

1. We provide concise formal models of SQL/PGQ and GQL;

2. We confirm the intuition that certain queries of interest to customers of graph databases cannot be expressed by SQL/PGQ and GQL patterns;

3. We compare GQL with recursive SQL and show that the latter is more powerful; and

4. We show experimentally that methods currently allowed in SQL/PGQ and GQL to overcome these limitations are impractical, even for small-sized graphs.

We now elaborate more on these goals.

1.0.0.1 Formal models of GQL and SQL/PGQ

The workhorse of graph query languages is pattern matching. In Cypher, PGQ, GQL and others, pattern matching turns a graph into a table; the remaining operations of the language manipulate that table. In fact in GQL and SQL/PGQ pattern matching is identical; it is only how its results are processed that is different. In SQL/PGQ, a graph is a view defined on a relational database. The result of pattern matching is simply a table in the clause of a SQL query that may use other relations in the database. GQL, on the other hand, is oblivious to how a graph is stored, and the table resulting from pattern matching is manipulated by a sequence of operators that modify it, in an imperative style that is referred to as “linear composition”.

To produce a formal model of these languages, we use the relationship between SQL and relational calculus/algebra as the guiding principle. SQL has a multitude of features: bag semantics, nulls, arithmetic operations, aggregate functions, outerjoins, complex datatypes such as arrays. Some of these break the theoretical model of First Normal Form (1NF) relations which are sets of tuples of atomic values. Relational algebra and calculus get rid of the extra baggage that SQL is forced to add to be usable in practice, and yet provide a simple core over sets of tuples of atomic values.

Although some mathematical abstractions of GQL and SQL/PGQ exist [18], [19], they are not yet at the same level as RA or relational calculus, in terms of their simplicity and utility in formally proving results. For example, their formalizations of pattern matching come with a complex typing system and the use of conditional and group variables that create nulls and set-valued attributes. To achieve our goal of creating a simple and usable abstraction, we need to: simplify the model of pattern matching, to avoid outputting non-1NF relations, and to formalize the linear composition of Cypher and GQL. This allows us to define two languages – Core PGQ and Core GQL – as RA or linear composition of relational operators on top of pattern matching outputs.

1.0.0.2 Limitations of pattern matching

Many pattern matching tasks require iterating patterns, notably when we do not know a priori the length of a path we are searching for (a basic example is reachability in graphs). The way pattern matching is designed in Cypher, GQL, and SQL/PGQ, makes it easy to compare two consecutive iterations of a pattern based on property values of their nodes, but at the same time it is very hard to compare property values in edges.

To illustrate this, assume we have a chain of transfers between accounts: accounts are nodes, with property values such as “balance”, and transfers are edges, with property values such as “amount” and “timestamp”, between accounts. It is very easy to write a query looking for a chain of transfers such that the balance increases in accounts along the chain. It appears to be very hard or impossible to write a query looking for a chain of transfers such that the timestamp increases along the path.

Demand for these queries occurs often in practice, which forced several companies participating in GQL design in ISO to start thinking of language extensions that will permit such queries [16], [17]. However, before making non-trivial language enhancements, it would be good to actually know that newly added features cannot be achieved with what is already in the language.

We show that this is indeed the case. Equipped with our formalization of the pattern language, we prove that it cannot express a large class of queries that analyze how property values of edges change along matched paths; of these the increasing value in edges query is the simplest. This follows in fact from a more general property that is akin to a pumping lemma for paths that can be selected by GQL and PGQ patterns.

1.0.0.3 GQL vs Recursive SQL vs Datalog

When the ubiquitous CRPQs was introduced in crpq?, it was shown that a Datalog-like language based on CRPQs has the power of transitive closure logic [20] and captures the complexity class \(\mathrm{\small NLogSpace}\)of problems solved by nondeterministic Turing machines whose work tape used logarithmic number of bits in terms of the size of the input (this class is contained in polynomial time). Since then, \(\mathrm{\small NLogSpace}\)is the yardstick complexity class we compare graph languages to, and Datalog – that subsumes the transitive closure logic – is a typical language used to understand the power of graph querying.

Datalog is also the basis of SQL’s recursive common table expressions (CTE) introduced by the clause. In fact, in SQL only linear Datalog rules are allowed: in them, the recursively defined predicate can be used at most once.

Motivated by this, we compare the power of GQL with recursive SQL and linear Datalog. We show that there are queries that are expressible in the latter, have very low data complexity, and yet are not expressible in GQL. We explain how this points out deficiencies of GQL design that will hopefully be addressed in the future.

1.0.0.4 Experimental evaluation: can graph DBMSs overcome these limitations?

Real-life systems go beyond basic calculi; SQL with recursion and aggregates is in fact Turing-complete and thus can express all computable queries. Similarly, GQL, PGQ, Cypher and others have many tools at their disposal to let users write very powerful queries. In fact queries such as increasing value in edges are expressible in real-life Cypher and PGQ, though in a very convoluted way. Since the complement of the query is easily expressible, one can look for all the paths and then subtract the complement. Intuitively, such a way should not work in practice as the number of paths in a graph grows exponentially.

This is precisely what we confirm using three different implementation of graph database queries: Neo4j and Memgraph for Cypher, and DuckDB for SQL/PGQ. Native graph systems can handle just a few dozen nodes before 100% timeout rate is observed; DuckDB does marginally better as it computes fewer paths to start with. It is important to note that this is not a critique of the systems tested, as the indirect method of computing the query inherently requires an exponential number of paths. Instead, this confirms that no workaround can bypass the inherent expressibility limitations.

Since inexpressibility results are commonly used to identify deficiencies in language design, and serve as a motivation to increase language expressiveness, we shall at the end of the paper discuss what these results tell us in terms of new features of GQL and SQL/PGQ that will be required.

Related work↩︎

While industry is dominated by property graphs (Neo4j cypher?, Oracle [21], Amazon [22], TigerGraph [23], etc), much of academic literature still works with the model of labeled graphs and query languages based on RPQs, with some exceptions [10], [24], [25]. However, the rare models focused on property graphs appeared before the new standards became available, and their analyses of expressiveness and language features do not apply to GQL and SQL/PGQ. The first commercial language for property graphs was Cypher, and it was fully formalized in cypher?. As GQL and SQL/PGQ were being developed, a few academic papers appeared. For example, [26] gave an overview of their pattern matching facilities, which was then further analyzed in [19], and [27] provided a description of an early implementation of SQL/PGQ.

In [18], a digest of GQL suitable for the research community was presented. While a huge improvement compared to the actual standard from the point of view of clarity, the presentation of [18] replaced 500 pages of the text of the Standard (notoriously hard to read) by a one-page long definition of the syntax, followed by a four-pages long definition of the semantics. It achieved a two orders of magnitude reduction in the size of the definition of the language, but 5 pages is still way too long for “Definition 1”. The language of [19] is closer to our goal, but it is not well-suited to the level reasoning we require here as it still contains still too much of the GQL and PGQ baggage, for example non-1NF relations, and a complex type system for singleton, conditional, and group variables that we avoid here entirely and replace by the very familiar definition of free variables.

Another element missing from the literature is a proper investigation of linear composition. Initially introduced in Cypher, it was then adopted in a purely relational language PRQL [28] (positioned as “pipelined” alternative to SQL), embraced by GQL, and influenced the designed of the piped SQL syntax [29]; however formal analyses of this way of building complex queries are lacking.

2 GQL and SQL/PGQ by examples↩︎

We illustrate GQL and SQL/PGQ capabilities using the graph from Figure 1 and the following money-laundering query: Find a pair of friends in the same city who transfer money to each other via a common friend who lives elsewhere. Notice that we assume that friendship is a symmetric relation.

In GQL, it will be expressed as query:

In SQL/PGQ, a graph is a view of a tabular schema. The graph from Figure 1 can be represented by the following set of tables:

• Person(p_id,name,city) for people,

• Acc(a_id,type) for accounts,

• Friend(p_id1,p_id2,since) for friendships,

• Owns(a_id,p_id) for ownership and

• Transfer(t_id,a_from,a_to,amount) for transfers.

The property graph view is then defined by a \(\text{\normalfont\small\renewcommand{\ttdefault}{pcr}\ttfamily\bfseries\color{darkblue} CREATE}\) statement, part of which is shown below:

This view defines nodes (vertices) and edges of the graph, specifies endpoints of edges, and defines their labels and properties. We can then query it, using pattern matching to create a subquery:

Note that in GQL, a sequence of operators can continue after the \(\text{\normalfont\small\renewcommand{\ttdefault}{pcr}\ttfamily\bfseries\color{darkblue} RETURN}\) clause. For example, if we want to find large transfers between the two potential offenders we could simply continue the first GQL query with extra clauses:

This is what is referred to as linear composition: we can simply add clauses to the already existing query which apply new operations to the result of already processed clauses.

In SQL/PGQ, such an operation is also possible, though perhaps a bit more cumbersome as we would need to put the above PGQ query as a subquery in and create another subquery for the second match, then join them on name1 and name2.

3 Pattern Matching: Turning Property Graphs into Relations↩︎

We define property graphs and pattern matching, the key component of GQL and SQL/PGQ, that extracts relations from graphs.

3.1 Property Graphs↩︎

We use the standard definition (cf. [19]), and only consider directed edges. Assume pairwise disjoint countable sets \(\mathcal{L}\) of labels, \(\mathcal{K}\) of keys, \(\mathsf{Const}\) of constants, \(\mathsf{N}\) of node ids, and \(\mathsf{E}\) of edge ids.

A path in \(G\) is an alternating sequence \(u_0 e_1 u_1 e_2 \cdots e_{n} u_n\), for \(n \geq 0\), of nodes and edges that starts and ends with a node and so that each edge \(e_i\) connects the nodes \(u_{i-1}\) and \(u_i\) for \(i \leq n\). More precisely, for each \(i \leq n\), either \(\mathsf{src}(e_i)=u_{i-1}\) and \(\mathsf{tgt}(e_i)=u_i\) (a forward edge), or \(\mathsf{src}(e_i)=u_{i}\) and \(\mathsf{tgt}(e_i)=u_{i-1}\) (a backward edge). Note that \(n=0\) is possible, in which case the path consists of a single node \(u_0\). We shall explicitly spell out paths as \(\textsf{path}(u_0,e_1,u_1,\cdots, e_n,u_n)\).

Two paths \(p = \textsf{path}(u_0,e_0,\ldots,u_k)\) and \(p' = \textsf{path}(u'_0,e'_0,\ldots,u'_j)\) concatenate, written as \(p \odot p'\), if \(u_k = u'_0\), in which case their concatenation \(p \cdot p'\) is defined as \(\textsf{path}(u_0,e_0,\ldots,u_k,e'_0,\ldots,u'_j)\). Note that a single-node path is a unit of concatenation: \(p \cdot\textsf{path}(u)\) is defined iff \(u=u_k\) and is equal to \(p\).

3.2 Pattern Matching↩︎

Pattern matching is the key component of graph query languages. As already mentioned, an early abstraction of GQL and PGQ patterns was given in [19], but it retained too much of the baggage of the actual language (non-1NF outputs, nulls, a complex type system) for language analysis. Thus, here we refine the definitions from [19] to capture the core concepts of pattern matching, similarly to relational algebra for relational databases. To this end, we fix an infinite set \(\mathsf{Vars}\) of variables and define Core GQL and Core PGQ pattern matching as follows:

where

• \(x \in \mathsf{Vars}\) and \(0 \leq n \leq m \leq \infty\);

• variables \(x\) in node and edge patterns \((x)\), \(\overset{x}{\rightarrow}\), and \(\overset{x}{\leftarrow}\) are optional,

• \(\psi\langle\theta \rangle\) is a conditional pattern, and conditions are given by \(\theta, \theta' \;:=\;x.k=x'.k' \mid x.k<x'.k' \mid \ell(x) \mid \theta \vee \theta' \mid \theta \wedge \theta' \mid \neg \theta\) where \(x,x'\in\mathsf{Vars}\) and \(k,k'\in\mathcal{K}\);

• \(\psi_1+\psi_2\) is only defined when their sets of free variables \(\mathsf{FV}\left(\psi_1\right)\) and \(\mathsf{FV}\left(\psi_2\right)\) are equal.

The sets of free variables are defined as follows:

• \(\mathsf{FV}\Big((x)\Big) = \mathsf{FV}\left(\overset{x}{\rightarrow}\right) = \mathsf{FV}\left( \overset{x}{\leftarrow}\right) \;:=\;\{x\}\);

• \(\mathsf{FV}\left(\psi_1 + \psi_2\right) \;:=\; \mathsf{FV}\left(\psi_1\right)\)

• \(\mathsf{FV}\left( \psi_1\, \psi_2 \right) \;:=\;\mathsf{FV}\left(\psi_1\right)\cup\mathsf{FV}\left( \psi_2 \right)\)

• \(\mathsf{FV}\left( \psi^{n..m} \right) \;:=\;\emptyset\)

• \(\mathsf{FV}\left(\psi\langle\theta \rangle\right) \;:=\;\mathsf{FV}\left(\psi\right)\)

A pattern produces an output that consists of graph elements and their properties. Such an output \(\Omega\) is a (possibly empty) tuple whose elements are either variables \(x\) or properties \(x.k\). A pattern with output, or, pattern, for simplicity, is an expression \(\psi_\Omega\) such that every variable present in \(\Omega\) is in \(\mathsf{FV}\left(\psi\right)\).

3.2.0.1 Correspondence with Cypher and GQL

For the reader familiar with Cypher and/or GQL, we explain how our fomalization compares with these languages’ patterns.

• \((x)\) is a node pattern that binds the variable \(x\) to a node;

• \(\overset{x}{\rightarrow}\) and \(\overset{x}{\leftarrow}\) are forward edge and backward edge patterns, that also bind \(x\) to the matched edge;

• \(\psi_1\, \psi_2\) is the concatenation of patterns,

• \(\psi^{n..m}\) is the repetition of \(\psi\) between \(n\) and \(m\) times (with a possibility of \(m=\infty\))

• \(\psi\langle\theta \rangle\) corresponds to \(\text{\normalfont\small\renewcommand{\ttdefault}{pcr}\ttfamily\bfseries\color{darkblue} WHERE}\) in patterns, conditions involve (in)equalities between property values, checking for labels, and their Boolean combinations;

• \(\psi_1 + \psi_2\) is the union of patterns;

• \(\psi_\Omega\) corresponds to the output forming clauses of Cypher and GQL and of SQL/PGQ, with \(\Omega\) listing the attributes of returned relations.

3.2.0.2 Semantics

To define the semantics, we use set \(\mathsf{Values}\) which is the union of \(\mathsf{Const}\cup \mathsf{N}\cup \mathsf{E}\). That is, its elements are node and edge ids, or values of properties, i.e., precisely the elements that can appear as outputs of patterns.

The semantics of a path pattern \(\psi\), with respect to a graph \(G\), is a set of pairs \((p,\mu)\) where \(p\) is a path and \(\mu\) is a mapping \(\mathsf{FV}\left(\psi\right)\rightarrow \mathsf{Values}\). Recall that we write \(\mu_\emptyset\) for the unique empty mapping with \(\mathsf{dom}(\mu)=\emptyset\).

For the semantics of path patterns with output \(\psi_\Omega\) we define \(\mu_\Omega:\Omega\to \mathsf{Values}\) as the projection of \(\mu\) on \(\Omega\): \[\mu_\Omega(\omega) := \begin{cases} \mu(x) & \text{if } \omega= x\in \mathsf{Vars}\\ \mathsf{prop}(\mu(x),k) & \text{if } \omega= x.k\,. \end{cases}\] Full definitions are presented in Figure 2. For node and edge patterns with no variables, the mapping part of the semantics changes to \(\mu_\emptyset\). The satisfaction of a condition \(\theta\) by a mapping \(\mu\), written \(\mu\models\theta\), is defined as follows: \(\mu\models x.k = x'.k'\) if both \(\mathsf{prop}(\mu(x),k)\) and \(\mathsf{prop}(\mu(x'),k')\) are both defined and are equal (and likewise for \(<\)), and \(\mu\models\ell(x)\) if \(\ell\in\mathsf{lab}(\mu(x))\). It is then extended to Boolean connectives \(\wedge, \vee, \neg\) in the standard way.

None

3.2.0.3 Pattern languages vs GQL and PGQ patterns

Compared to GQL and PGQ patterns as described in [18], [19], [26], we make some simplifications. First and foremost, they are to ensure that outputs of pattern matching are 1NF relations. Similarly to formal models of SQL by means of relational algebra and calculus over sets of tuples, we do not include bags, nulls, and relations whose entries are not atomic values. The differences manifest themselves in four ways.

First, we use set semantics rather than bag semantics. GQL and PGQ pattern can return tables with duplicate patterns; we follow their semantics up to multiplicity.

Second, in disjunctions \(\psi_1 + \psi_2\) we require that free variables of \(\psi_1\) and \(\psi_2\) be the same. In GQL this is not the case, but then for a variable \(x \in \mathsf{FV}\left(\psi_1\right)-\mathsf{FV}\left(\psi_2\right)\), a match for \(\psi_2\) would generate a null in the \(x\) attribute. Following the 1NF philosophy, we omit features that can generate nulls.

Third, repeated patterns \(\psi^{n..m}\) have no free variables. In GQL and PGQ, free variables of \(\psi\) become group variables in \(\psi^{n..m}\), leading to both a complex type system [19] and crucially non-flat outputs. Specifically such variables are evaluated to lists. For example, in the pattern \(()\xrightarrow{x}^{0..\infty}()\), the variable \(x\) would be mapped to the list of edge ids traversed by the path. These lists would be typically represented as values of an type in implementations (cf. [27]) thus again violating 1NF.

Fourth, we do not impose any conditions on paths that can be matched. In GQL and PGQ they can be simple paths (no repeated nodes), or trails (no repeated edges), or shortest paths. In GQL, PGQ, and Cypher, paths themselves may be returned, and such restrictions therefore are necessary to ensure finiteness of output. Since we can only return graph nodes or edges, or their properties, we never have the problem of infinite outputs, and thus we chose not to overcomplicate the definition of core languages by deviating from flat tables as outputs.

In what might look like a simplification w.r.t. GQL and PGQ, we do not have explicit joins of patterns, i.e., \(\psi_1, \psi_2\) with the semantics \(\left\llbracket\psi_1,\psi_2\right\rrbracket_{G} = \left\{\big((p_1,p_2),\mu_1 \bowtie\mu_2\big) \mid (p_i,\mu_i)\in \left\llbracket\psi_i\right\rrbracket_G, \; i=1,2\right\}\). This is because such joins are definable with RA operations. This simplification is in the same spirit as not including the natural join in the definition of RA, since it can already be expressed with product, selection, and projection.

4 SQL/PGQ: Theoretical Abstractions↩︎

Having defined patterns shared by SQL/PGQ and GQL, we can proceed to provide a theoretical abstraction of SQL/PGQ. Recall that in PGQ, the statement is embedded in . In fact results of matches over a graph are simply treated as relations, or subqueries, over which the usual SQL can be asked. Taking again the view that our goal is to provide the core abstraction of the language, on top of which others can be built, we look at the essential core of relational languages, namely relational algebra. With this in mind, we define (for now informally):

To make this definition formal, we define some very standard concepts. We assume an infinite countable set \(\mathcal{S}\) of relation symbols, such that each \(S\in \mathcal{S}\) is associated with a sequence \(\mathsf{attr}(S):=A_1, \ldots, A_n\) of attributes for some \(n>0\); here attributes \(A_i\) come from a countably infinite set \(\mathcal{A}\) of attributes. By \(\mathsf{arity}(S)\) we mean \(n\), and to be explicit about names of attributes write \(S(A_1, \ldots, A_n)\).

Fix an infinite domain \(\mathbf{U}\) of values. A relation over \(S(A_1,\ldots, A_n)\) is a set of tuples \(\mu:\{A_1,\ldots, A_n\} \rightarrow \mathbf{U}\). The domain of \(\mu\) is denoted \(\mathsf{dom}(\mu)\), and we often represent tuples as sets of pairs \((A,\mu(A))\) for \(A\in \mathsf{dom}(\mu)\). A relational database \(\mathcal{D}\) is a partial function that maps symbols \(S\in \mathcal{S}\) to relations \(\mathcal{D}(S)\) over \(S\) (if \(\mathcal{D}\) is clear from the context we refer to \(\mathcal{D}(S)\) simply as \(S\), by a slight abuse of notation.) We say that \(\mathcal{D}\) is over its domain \(\mathsf{dom}(\mathcal{D})\).

Let \(\mu\) be a tuple and \(\pmb{A} \subseteq \mathsf{dom}(\mu)\). We use \(\mu\restriction \pmb{A}\) to denote the restriction of \(\mu\) to \(\pmb{A}\), that is, the mapping \(\mu'\) with \(\mathsf{dom}(\mu') = \pmb{A}\) and \(\mu'(A) :=\mu(A)\) for every attribute \(A\in \pmb{A}\). Two tuples \(\mu_1,\mu_2\) are compatible, denoted by \(\mu_1 \sim \mu_2\), if \(\mu_1(A) = \mu_2(A)\) for every \(A\in \mathsf{dom}(\mu_1) \cap \mathsf{dom}(\mu_2)\). For such compatible tuples define \(\mu_1 \bowtie\mu_2\) as the mapping \(\mu\) with \(\mathsf{dom}(\mu):=\mathsf{dom}(\mu_1) \cup \mathsf{dom}(\mu_2)\), and \(\mu(A):=\mu_1(A)\) if \(A\in\mathsf{dom}(\mu_1)\) and \(\mu(A):=\mu_2(A)\) otherwise.

If \(A\in\mathsf{dom}(\mu)\) then the renaming \(\rho_{ A\rightarrow B}(\mu)\) of \(A\) to \(B\) is the mapping \(\mu'\) with \(\mathsf{dom}(\mu')= (\mathsf{dom}(\mu) \setminus\{A \})\cup\{B\}\) where \(\mu'(B):=\mu(A)\) and \(\mu'(A')= \mu(A')\) for every other \(A'\in\mathsf{dom}(\mu')\).

4.0.0.1 Relational Algebra (RA)

We use a standard presentation of RA. Given a schema \(\mathbf{S}\) which is a finite subset of \(\mathcal{S}\), the expressions \(\mathcal{Q}\) of \(\mathsf{RA}(\mathbf{S})\) and selection conditions \(\theta\) are defined as

\[\begin{array}{rcl} \mathcal{Q}, \mathcal{Q}' & \!\!:=\!\! & R \; \mid \;\pi_{\pmb{A}}(\mathcal{Q}) \; \mid \;\sigma_{\theta}(\mathcal{Q}) \; \mid \;\mathcal{Q}\bowtie\mathcal{Q}' \; \mid \;\mathcal{Q}\cup \mathcal{Q}' \; \mid \;\mathcal{Q}- \mathcal{Q}' \\ \theta & \!\!:=\!\! & A = A' \mid \neg \theta \mid \theta \vee \theta \mid \theta \wedge \theta \end{array}\] where \(R\) ranges over relations in \(\mathbf{S}\). The sets of attributes of expressions \(\mathsf{attr}(\mathcal{Q})\) are defined by extending \(\mathsf{attr}(R)\), namely \(\mathsf{attr}(\pi_{\pmb{A}}(\mathcal{Q}))\) is \(\pmb{A}\), while both of \(\mathsf{attr}(\sigma_{\theta}(\mathcal{Q}))\) and \(\mathsf{attr}( \mathcal{Q}\circ\mathcal{Q}')\) are \(\mathsf{attr}(Q)\), for \(\circ\) being union and difference; \(\mathsf{attr}( \mathcal{Q}\bowtie\mathcal{Q}') = \mathsf{attr}( \mathcal{Q}) \cup \mathsf{attr}( \mathcal{Q}')\) and \(\mathsf{attr}(\rho_{ A \rightarrow A'}(\mathcal{Q})) = (\mathsf{attr}(\mathcal{Q}) \setminus \{ A \})\cup \{ A'\}\).

The expressions of RA must satisfy the usual well-definedness rules: \({\pi_{\pmb{A}}(\mathcal{Q})}\) is well-defined if \(\pmb{A}\subseteq \mathsf{attr}(\mathcal{Q})\); set operations are defined if \(\mathsf{attr}(\mathcal{Q})=\mathsf{attr}(\mathcal{Q}')\), and for renaming from \(A\) to \(A'\) we must have \(A\in\mathsf{attr}(\mathcal{Q})\) and \(A'\not\in\mathsf{attr}(\mathcal{Q})\).

The result of evaluation of a query \(\mathcal{Q}\) on a database \(\mathcal{D}\) is a relation \(\left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}\) over \(\mathsf{attr}(\mathcal{Q})\) defined as: \[\begin{align} \left\llbracket R\right\rrbracket_{\mathcal{D}} :=\;\;\; & {\mathcal{D}}(R)&\\ \left\llbracket\pi_{\pmb{A}}(\mathcal{Q})\right\rrbracket_{\mathcal{D}} :=\;\;\; & \{ \mu\restriction_{\pmb{A}} \;\mid \;\mu\in \mathcal{Q}\}&\\ \left\llbracket\sigma_{\theta}(\mathcal{Q})\right\rrbracket_{\mathcal{D}} :=\;\;\; & \{ \mu\;\mid\;\mu\in \mathcal{Q}\text{ and } \mu\models \theta\}&\\ \left\llbracket\rho_{ A \rightarrow A'}(\mathcal{Q})\right\rrbracket_{\mathcal{D}}:=\;\;\; &\{ \rho_{ A \rightarrow A'}(\mu) \mid \mu\in \mathcal{Q}\}&\\ \left\llbracket\mathcal{Q}\bowtie\mathcal{Q}'\right\rrbracket_{\mathcal{D}} :=\;\;\; & \{\mu \bowtie\mu' \;\mid \;\mu\in\mathcal{Q}, \;\mu'\in \mathcal{Q}' \}&\\ \left\llbracket\mathcal{Q}\circ\mathcal{Q}'\right\rrbracket_{\mathcal{D}} :=\;\;\; & \left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}} \circ\left\llbracket \mathcal{Q}'\right\rrbracket_{\mathcal{D}}& \text{ for }\circ\in \{\cup,\setminus \} \end{align}\]

with \(\mu\models \theta\) having the standard semantics \(\mu \models A=A'\) iff \(A,A'\in\mathsf{dom}(\mu)\) and \(\mu(A) = \mu(A')\), extended to Boolean connectives \(\wedge, \vee, \neg\).

4.0.0.2 Core PGQ

Assume that for each variable \(x\in\mathsf{Vars}\) and each key \(k\in\mathcal{K}\), both \(x\) and \(x.k\) belong to the set of attributes \(\mathcal{A}\). For each pattern \(\psi\) and each output specification \(\Omega\), we have a relation symbol \(R_{\psi,\Omega}\) whose set of attributes are the elements of \(\Omega\). Let \(\mathsf{Pat}\) contain all such relation symbols.

To define the semantics of Core PGQ queries, assume without loss of generality that \(\mathsf{Values}\subseteq \mathbf{U}\). This ensures that results of pattern matching are relations of the schema \(\mathsf{Pat}\), because for every path pattern with output \(\psi_{\Omega}\) and a property graph \(G\), the table \(\left\llbracket\psi_{\Omega}\right\rrbracket_{G}\) is an instance of relation \(R_{\psi,\Omega}\) from \(\mathsf{Pat}\).

Then the semantics of Core PGQ is simply the extension of the semantics of \(\mathsf{RA}\) defined above where for base relations we have

\(\left\llbracket R_{\psi,\Omega}\right\rrbracket_G\;:=\;\left\llbracket\psi_\Omega\right\rrbracket_G\,.\)

5 GQL: Theoretical Abstractions↩︎

We next provide a formal model of GQL. Recall that it shares patterns with PGQ. What is different is the way GQL processes results of pattern matching: not in a bottom-up way with \(\mathsf{RA}\) operators like PGQ, but rather in sequential, or pipelined way where the output of each operation in a sequence serves as the input for the next operation. Using terminology adopted by Cypher cypher?, GQL calls this linear composition. Unlike \(\mathsf{RA}\), it lacks proper formalization, and thus next we provide a formal description of a different flavor of \(\mathsf{RA}\), obtained by linear composition.

5.1 LCRA: Linear Composition RA↩︎

This language captures the sequential (linear) application of relational operators as seen in Cypher, GQL, and also PRQL. Its expressions over a schema \(\mathbf{S}\), denoted by \(\mathsf{LCRA}(\mathbf{S})\), are defined as: \[\begin{align} \textit{Linear Clause: }\,\,\, \mathbf{L}, \mathbf{L}' :=&~ S \mid \pi_{\pmb{A}} \mid \sigma_{\theta} \mid \rho_{ A\rightarrow A'} \mid \mathbf{L}\, \mathbf{L}' \mid \{\mathcal{Q}\} &\\ \textit{Query: }\,\,\, \mathcal{Q}, \mathcal{Q}' :=&~ \mathbf{L}\mid \mathcal{Q}\cap \mathcal{Q}' \mid \mathcal{Q}\cup \mathcal{Q}' \mid\mathcal{Q}\setminus \mathcal{Q}' \end{align}\]

where \(S\) ranges over \(\mathbf{S}\), while \(\pmb{A} \subseteq \mathcal{A},\) and \(A,A'\in\mathcal{A}\), and \(\theta\) is defined as for RA. Unlike for RA, the output schema of LCRA clauses and queries can be determined only dynamically.

To define the semantics of a query \(\mathcal{Q}\) on a database \(\mathcal{D}\) we need a starting value of the driving table \(\mathbf{R}\), and this is taken to be \(I_{\emptyset}\), the relation containing only one empty tuple \(\mu_{\emptyset}\) where \(\mathsf{dom}(\mu_{\emptyset}):=\emptyset\), cf. [18], cypher?.

The semantics \(\left\llbracket\,\right\rrbracket_{\mathcal{D}}\) of LCRA clauses \(\mathbf{L}\) and queries \(\mathcal{Q}\) is a mapping from relations into relations (known as driving tables for Cypher and GQL). It is defined as follows:

\[\begin{align} \left\llbracket S\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \mathbf{R}\bowtie\mathcal{D}(S) \\ \left\llbracket\pi_{\pmb{A}}\right\rrbracket_{\mathcal{D}}(\mathbf{R}):=&~ \{\mu\restriction_{\pmb{A}\cap \mathsf{attr}(\mathbf{R})} \; \mid \;\mu\in \mathbf{R}\}\\ \left\llbracket\sigma_{\theta}\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \{\mu\; \mid \;\mu\in \mathbf{R},\, \mu\models \theta \} \\ \left\llbracket\rho_{ A \rightarrow A'}\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \{\rho_{ A \rightarrow A'}(\mu) \mid \mu\in \mathbf{R},\, A'\not\in \mathsf{dom}(\mu) \}\\ \left\llbracket\mathbf{L}\mathbf{L}'\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \left\llbracket\mathbf{L}'\right\rrbracket_{\mathcal{D}}(\left\llbracket\mathbf{L}\right\rrbracket_{\mathcal{D}}(\mathbf{R}))\\ \left\llbracket\{\mathcal{Q}\}\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \mathbf{R}\bowtie\left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}(I_{\emptyset}) \\ \left\llbracket\mathcal{Q}\circ\mathcal{Q}'\right\rrbracket_{\mathcal{D}}(\mathbf{R}) :=&~ \left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}(\mathbf{R}) \circ\left\llbracket\mathcal{Q}'\right\rrbracket_{\mathcal{D}}(\mathbf{R}), \quad \text{ for } \circ\in\{\cup,\cap,-\} \end{align}\]

A clause or a query of \(\mathsf{LCRA}\) always looks at a unique input relation \(\mathbf{R}\). If a clause is a name of a relation \(S\) or an entire query \(\{\mathcal{Q}\}\), then it is joined with \(\mathbf{R}\). Projection, selection, and renaming clauses behave in the usual way, and apply to the input relation \(\mathbf{R}\). The meaning of set operations – union, intersection, difference – is also standard, and two clauses \(\mathbf{L}\mathbf{L}'\) are simply executed in sequence, with the result of \(\mathbf{L}\) on \(\mathbf{R}\) becoming the input to \(\mathbf{L}'\).

This semantics determines (dynamically) the set of attributes of outputs of clauses and queries; for completeness we present it here:

\[\begin{align} \mathsf{attr}(\left\llbracket S\right\rrbracket_{\mathcal{D}}(\mathbf{R})) :=&~ \mathsf{attr}(S) \cup \mathsf{attr}(R) &\\ \mathsf{attr}( \left\llbracket\pi_{\mathbf{A}}\right\rrbracket_{\mathcal{D}}(\mathbf{R})):=&~ \mathbf{A} \cap \mathsf{attr}( \mathbf{R}) &\\ \mathsf{attr}(\left\llbracket\sigma_{\theta}\right\rrbracket_{\mathcal{D}}(\mathbf{R})) :=&~ \mathsf{attr}(\mathbf{R}) &\\ \mathsf{attr}(\left\llbracket\rho_{ A \rightarrow A'}\right\rrbracket_{\mathcal{D}}(\mathbf{R}) ) :=&~\mathsf{attr}(\mathbf{R}) \setminus\{A'\} \cup \{ A\}&\\ \mathsf{attr}(\left\llbracket\{\mathcal{Q}\}\right\rrbracket_{\mathcal{D}}(\mathbf{R})) :=&~ \mathsf{attr}(\left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}(\mathbf{R})) \cup \mathsf{attr}(\mathbf{R})&\\ \mathsf{attr}(\left\llbracket\mathcal{Q}\circ \mathcal{Q}'\right\rrbracket_{\mathcal{D}}(\mathbf{R})) :=&~ \mathsf{attr}(\left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}(\mathbf{R}))& \end{align}\] Query output on a database is defined as \(\left\llbracket\mathcal{Q}\right\rrbracket_{\mathcal{D}}( I_{\emptyset})\).

5.2 Core GQL↩︎

Just as we defined Core PGQ as \(\mathsf{RA}\) over output of patterns, we now define Core GQL as \(\mathsf{LCRA}\) over the same.

As with Core PGQ, we define the semantics of Core GQL by \(\left\llbracket R_{\psi,\Omega}\right\rrbracket_G:=\left\llbracket\psi_\Omega\right\rrbracket_G\) and then use the semantic of \(\mathsf{LCRA}\) above.

We now present an example to explain how GQL’s linear composition works.

We use a simplified query based on the money laundering query from the introduction. It looks for someone who has two friends in a city different from theirs, and outputs the person’s name and account (Porthos and a2 in our example):

The equivalent Core GQL formula is

\(R_{\psi_1,\Omega_1} \quad R_{\psi_2, \Omega_2} \; \quad \sigma_{y.\text{city}\neq x.\text{city} \wedge x.\text{city}=z.\text{city}} \quad\pi_{y.\text{name},\text{acc}\_y}\\ {} \quad\quad\quad\quad\rho_{y.\text{name} \to \text{name}} \quad\rho_{acc\_y \to \text{account}}\)

where \[\begin{array}{rcl} \psi_1 & :=& \big((x) \overset{e_1}{\rightarrow} (y) \;(y) \overset{e_2}{\rightarrow}(z)\big)\langle \text{Friends}(e_1) \wedge \text{Friends}(e_2)\rangle \\ \psi_2 & :=& \big((y) \overset{e_3}{\rightarrow} (\text{acc}\_y)\big)\langle \text{Owns}(e_3)\rangle \\ \Omega_1 & :=& (x,\;y,\;z,\;x.\text{city},\;y.\text{city},\;z.\text{city}) \\ \Omega_2 & :=& (y, \;\text{acc}\_y)\,. \end{array}\]

5.3 Equivalence of Core PGQ and Core GQL↩︎

We say that two queries \(\mathcal{Q}_1, \mathcal{Q}_2\) (possibly from different languages) are equivalent if \(\left\llbracket\mathcal{Q}_1\right\rrbracket_{\mathcal{D}} = \left\llbracket\mathcal{Q}_2\right\rrbracket_{\mathcal{D}}\) for every database \(\mathcal{D}\). A query language \(L_1\) is subsumed by \(L_2\) if for each query \(\mathcal{Q}_1\) in \(L_1\) there is an equivalent query \(\mathcal{Q}_2\) in \(L_2\). If there is also a query \(\mathcal{Q}_2 \in L_2\) for which there is no equivalent query \(\mathcal{Q}_1\in L_1\) then \(L_1\) is said to be strictly less expressive than \(L_2\). Finally \(L_1\) and \(L_2\) are equivalent if \(L_1\) is subsumed by \(L_2\) and \(L_2\) is subsumed by \(L_1\).

Thus, \(\mathsf{LCRA}\) proposed as the relational processing engine of graph languages like Cypher and GQL is the good old \(\mathsf{RA}\) in a slight disguise. As an immediate consequence of Theorem 1 we have:

Notice that the definition of linear clauses and queries of \(\mathsf{LCRA}\) are mutually recursive as we can feed any query \(\mathcal{Q}\) back into clauses via \(\{\mathcal{Q}\}\) (this corresponds to the feature of Cypher and GQL). If this option is removed, and linear clauses are not dependent on queries, we get a simplified language \(\mathsf{sLCRA}\) (simple \(\mathsf{LCRA}\)). Specifically, in this language linear clauses are given by the grammar \(\mathbf{L}:=S \mid \pi_{\mathbf{A}} \mid \sigma_{\theta} \mid \rho_{ A\rightarrow A'} \mid \mathbf{L}\mathbf{L}\). To see why the \(\{\mathcal{Q}\}\) clause was necessary in the definition of \(\mathsf{LCRA}\), we show

5.4 The origins of linear composition↩︎

Linear composition features prominently in graph languages (Cypher, GQL) and also some relational languages (PRQL); at the same time it had not been formalized nor studied as its non-linear relational algebra analog (until now). Thus we use this short section to briefly explain the origins of linear composition. Linear composition was introduced in the design of Cypher cypher? as a way to bypass the lack of a compositional language for graphs. Specifically, pattern matching transforms graphs into relational tables, and other Cypher operations modify these tables. If we have two such read-only queries \(G\to \mathbf{T}_1\) and \(G\to \mathbf{T}_2\) from graphs to relational tables, it is not clear how to compose them. To achieve composition, Cypher read-only queries are of the form \(\mathcal{Q}: G\times \mathbf{T} \to \mathbf{T}'\) (and its read/write queries are of the form \(\mathcal{Q}: G\times \mathbf{T} \to G' \times \mathbf{T}'\)). In other words, they turn a graph and a table into a table. Thus, the composition of two queries \(\mathcal{Q}_1, \mathcal{Q}_2: G\times \mathbf{T} \to \mathbf{T}'\) is their linear composition \(\mathcal{Q}_1 \;\mathcal{Q}_2\) which on a graph \(G\) and table \(\mathbf{T}\) returns \(\mathcal{Q}_2\big(G,\mathcal{Q}_1(G,\mathbf{T})\big)\).

Independently, the same approach was adopted by a relational language PRQL [28], where P stands for “pipelined” but the design philosophy is identical. For example one could write

``R`` A=1 S B=2 C, D

with each clause applied to the output of the previous clause. The above query is the same as relational algebra query

\[\pi_{C,D}\Big(\sigma_{B=2}\big(\sigma_{A=1}(R) \Join S\big)\Big)\]

Though PRQL design is relations-to-relations, the motivation for pipelined or linear composition comes from creating a database analog of dplyr [30], a data manipulation library in R, that can be translated to SQL. While dplyr’s operations are very much relational in spirit, it is integrated into a procedural language, and hence the imperative style of programming was inherited by PRQL and also adopted by the piped syntax of SQL [29].

To recap, we defined simple theoretical abstractions Core PGQ of SQL/PGQ and Core GQL of GQL, that share the same pattern matching language turning graphs into relations; then on top of pattern matching outputs we use \(\mathsf{RA}\) for PGQ and \(\mathsf{LCRA}\) for GQL. It should be kept in mind that these abstractions capture the essense of SQL/PGQ and GQL in the same way as \(\mathsf{RA}\) and first-order logic capture the essence of SQL: they define a theoretical core that is amenable to a formal study, but real languages, be it 500 pages of the GQL standard or over 4000 pages of the SQL standard, have many more features.

6 Limitations of Patterns: a theoretical investigation↩︎

A common pattern of query language development is this: first, a small core language is designed; its focus is on declarativeness and optimizability. As a consequence the expressiveness of such a language is limited. These limitations are typically observed in practice by programmers’ inability to write certain queries and often later proven formally, for a theoretical language that defines the key features of the practical one. Using these inputs as motivations, extra features are added to the real-life language if practical applications warrant this and user demands.

A classical example of this development cycle is SQL and recursion. In this case, we had a “canonical” query whose inexpressibility it was important to show in order to justify additions to the language. The query was transitive closure of relation (or, equivalently, testing for graph connectivity [1]–[3]). Thus, before embarking on the study of the expressiveness of GQL and SQL/PGQ, we ask for an analog of such “canonical” queries for them that users want to express but appear to be unable to.

Fortunately, we have such queries, thanks to the discussions already happening in the ISO committee that maintains both SQL and GQL standards [16], [17]. In fact much of recent effort tries to repair what appears to be a hole in the expressiveness of the language. Specifically, it seems to be impossible to express queries that impose conditions on how values of edges properties change along the paths, even if the same conditions can be expressed for properties of nodes. To give a simple example of such a condition, consider the following:

• we can check, by a very simple pattern, if there is a path of transfers between two accounts where balance in intermediary accounts (values held in nodes) increases, but

• it appears that we cannot check if there is a path of transfers between two accounts where timestamp (values held in edges) increases.

This perceived deficiency has already led to early proposals to significantly enhance pattern matching capabilities of the language [16], [17], in a way whose complexity implications appear significant but are not fully understood.

Before such a dramatic expansion of the language gets a stamp of approval, it would be nice to know whether it is actually needed. The goal of this section is to provide both theoretical and experimental evidence that we do need extra language features to express queries such as “increasing values in edges”.

6.1 What can be expressed↩︎

A pattern \(\psi\) can be viewed as a query \(\big((x_s)\;\psi\; (x_t)\big)_{x_s,x_t}\) that returns endpoints (source and target) of the paths matched by \(\psi\) as values of attributes \(x_s\) and \(x_t\).

Earlier queries are defined formally as:

• \(Q^{\mathsf{N}}_{\uparrow}\) returns endpoints of a path along which the value of property \(k\) of nodes increases. It returns pairs \((u_0,u_n)\) of nodes such that there is path \(\textsf{path}(u_0,e_1,u_1,\ldots,e_n,u_n)\) so that \(u_0.k < u_1.k < \cdots < u_n.k\).

• \(Q^{\mathsf{E}}_{\uparrow}\) returns endpoints of a path along which the value of property \(k\) of edges increases. It returns pairs \((u_0,u_n)\) of nodes such that there is path \(\textsf{path}(u_0,e_1,u_1,\ldots,e_n,u_n)\) so that \(e_1.k < e_2.k < \cdots < e_n.k\).

It is a simple observation that \(Q^{\mathsf{N}}_{\uparrow}\) is expressible by the Core PGQ and GQL pattern with output \[(x_s) \;\Big(\, \big((x)\rightarrow(y)\langle x.k<y.k \rangle \big)^{0..\infty}\,\Big)\;(x_t).\,\] In fact this can be generalized to order motifs which are defined as strings over the alphabet \(\{\uparrow,\downarrow\}\). Given such a string \(w\), the query \(Q^{\mathsf{N}}_w\) matches paths which can be decomposed according to \(w\) so that in each segment corresponding to \(\uparrow\) values of property \(k\) increase and in each segment corresponding to \(\downarrow\) these values decrease. For example, \(Q^{\mathsf{N}}_{\uparrow\downarrow\uparrow}\) matches arbitrary length paths where values of property \(k\) of nodes first increases, then decreases, and then increases again. With the same approach as the above query, we can see that \(Q^{\mathsf{N}}_w\) is expressible for every order motif \(w\).

What happens when we move from nodes to edges? The same approach will not work for \(Q^{\mathsf{E}}_{\uparrow}\): if we (erroneously) express it by \[\big(\,()\overset{x}{\rightarrow}()\overset{y}{\rightarrow}()\langle x.k<y.k \rangle\, \big)^{0..\infty}\] it fails: on the input \(()\overset{3}{\rightarrow}()\overset{4}{\rightarrow}()\overset{1}{\rightarrow}()\overset{2}{\rightarrow}()\) (where the numbers on the edges are values of property \(k\)) it returns the start and the end node of the path, even though values in edges do not increase. This is due to the semantics of path concatenation: two paths concatenate if the last node of the first path equals the first node of the second, and therefore conditions on edges in two concatenated or repeated paths are completely “local” to those paths.

In some cases, where graphs are of special shape, we can obtain the desired patterns by resorting to tricks that a normal query language user would be rather unlikely to find. Specifically, consider property graphs whose underlying graph structures are just paths. That is, we look at annotated paths \(P_n\), which are of the form

where \(v_0,\ldots,v_n\) are distinct nodes, \(e_0, \ldots, e_{n-1}\) are distinct edges (for \(n > 0\)), and each edge \(e_i\) has property \(e_i.k\). Let \(\psi^{\mathsf{E}}_{<}\) be \[\begin{array}{cl} & (x_s) \left(\big( (u)\overset{x}{\rightarrow}(z) \overset{y}{\rightarrow}(v) \overset{w}{\leftarrow} (z)\big) \langle x.k < y.k \rangle\right)^{1..\infty} \to (x_t)\\ + & (x_s)\to(x_t) \end{array}\] A pattern with output \(\psi_\Omega\) expresses a query \(Q\) on \(G\) if \(\left\llbracket\psi_\Omega\right\rrbracket_G = Q(G)\).

In the first disjunct, the forward edge \(\overset{y}{\rightarrow}\) serves as a look-ahead that enables checking whether the condition holds, and the backward edge \(\overset{w}{\leftarrow}\) enables us to continue constructing the path in the next iteration from the correct position \((z)\). The fact that the query operates on \(P_n\) ensures that the last edge to \(x_t\) does not violate the condition of the query as it was already traversed in the iterated subpattern. The second disjunct takes care of paths of length \(1\).

6.2 What cannot be expressed with patterns↩︎

To achieve expressibility of \(Q^{\mathsf{E}}_{\uparrow}\) in Proposition [prop:e60express] we made two strong assumptions: not only is the input of a very special shape (a directed path with forward edges), but also the pattern uses backwards edges; the latter would be natural for an oriented path (in which edges can go in either direction [31]), but looks rather unnatural in this setting. Thus, we ask ourselves whether \(Q^{\mathsf{E}}_{\uparrow}\) can be expressed in a natural way. In fact we can pose a more general question about queries \(Q^{\mathsf{E}}_w\) for arbitrary order motifs; in Section 6.1 we saw that on nodes, all order motifs can be expressed.

To formalize what we mean by “natural”, define one-way path patterns by a restriction of the grammar: \[\begin{align} \psi\;:=\;& (x) \;\mid\;\overset{x}{\rightarrow} \;\mid \; \psi_1 + \psi_2 \;\mid \; \psi^{n..m} \;\mid \;\psi_{\langle \theta \rangle} \;\mid\; \psi_1\, \psi_2 \end{align}\] where we require that \(\mathsf{FV}\left( \psi_1\right)\cap \mathsf{FV}\left(\psi_2\right) = \emptyset\) in \(\psi_1\, \psi_2\) (and variables \(x\), as before, are optional). The omission of backward edges \(\overset{x}{\leftarrow}\) in one-way patterns is quite intuitive. The restriction on variable sharing in concatenated patterns is because backward edges can be simulated by simply repeating variables, as done above in \(\psi^{\mathsf{E}}_{<}\).

If there is a natural way, easily found by programmers, of writing the \(Q^{\mathsf{E}}_{\uparrow}\) query in PGQ and GQL, one would expect it to be done without backward edges. Yet, this is not the case.

In fact, no order motif on edges can be captured by GQL and PGQ patterns.

The inexpressibility of \(Q^{\mathsf{E}}_{\uparrow}\) is then an immediate corollary for \(w=\uparrow\).

This result is a direct consequence of a general pumping argument applied to annotated paths accepted by one-way patterns.

Note that in the newly constructed path with repetitions, we assign new ids to the different occurrences of the elements in \(p_2\), while keeping the data (annotations) unchanged. The idea behind the proof is as follows: Since, by definition, there are infinitely many annotated paths that conform to \(\psi\), it must exhibit unbounded repetition. However, because the semantics disregard variables that occur within unbounded repetitions, the transfer of information between iterations is limited. This restriction allows us to repeat parts of the annotated path while preserving the same semantics and, consequently, still conforming to \(\psi\).

We can derive a further corollary of this theorem that reinforces the intuition that GQL and PGQ patterns are incapable of capturing data values along a path “as a whole.”

A canonical example of such a condition is checking whether all values of a specific property of nodes or edges along a path are distinct. Formally, we define:

• \(Q^{\mathsf{N}}_{\neq}\) returns pairs \((u_0,u_n)\) of nodes such that there is path \(\textsf{path}(u_0,e_1,u_1,\ldots,e_n,u_n)\) so that \(u_i.k \neq u_j.k\) for all \(0 \leq i < j \leq n\).

and \(Q^{\mathsf{E}}_{\neq}\) is defined likewise but for edges in place of nodes. One-way path patterns do not have enough power to express such queries.

6.3 What cannot be expressed in full GQL↩︎

Having examined the expressiveness of patterns, we now look at the entire query languages Core GQL and Core PGQ and compare them with recursive SQL and linear Datalog. Recursive SQL is a good comparison target as the most natural relational language into which graph queries involving pattern with arbitrary length paths are translated [32], [33]. The theoretical basis for recursive SQL common table expressions is linear Datalog, i.e., the fragment of Datalog in which definitions can refer to recursively defined predicates at most once. This is precisely the restriction of recursive SQL: a recursively defined table can appear at most once in .

Of course recursive SQL can be enormously powerful: as already mentioned, combining recursion and arithmetic/aggregates one can simulate Turing machines [34]. Thus, to make the comparison fair, we look at positive recursive SQL: this is the fragment of recursive SQL where subqueries can only define equi-joins. In other words, they only use conjunctions of equalities in . Such a language just adds recursion on top of unions of conjunctive queries, and ensures termination and tractable data complexity [35]. We show that even these simple fragments of SQL and Datalog can express queries that Core GQL and PGQ cannot define.

At the end of the section, we explain why this is quite surprising in view of what we know about Core GQL and PGQ: complexity-theoretic considerations strongly suggest these should define all queries from linear Datalog, and yet this is not the case due to subtle deficiencies in the language design, which we outline in Section 8.

To talk about expressing property graph queries in relational languages, we must represent graphs as relations. There are many possibilities, and it does not matter (for showing Theorem 4) which one we choose, as these different representations are inter-definable by means of unions of select-project-join queries. Since graphs in the separating example have labels and do not have property values, we use an encoding consisting of unary relations \(N_\ell\) storing \(\ell\)-labeled nodes, and binary relations \(E_\ell\) storing pairs of nodes \((n_1,n_2)\) with an \(\ell\)-labeled edge between them.

To sketch the idea of the separating query, we define dataless paths as graphs \(G_n\), \(n > 0\), with nodes \(v_0,\ldots,v_n\), edges \((v_0,v_1), \;(v_1,v_2), \ldots, (v_{n-1},v_n)\), where \(v_0\) has label \(\mathit{min\_elt}\) and \(v_n\) has label \(\mathit{max\_elt}\). The separating query asks: is \(n\) a power of 2?

The inexpressibility proof of this is based on showing that GQL queries can only define Presburger properties of lengths of dataless paths, by translating Core GQL queries on such paths into formulae of Presburger Arithmetic (i.e., the first-order theory of \(\langle \mathbb{N}, +, <\rangle\)). Therefore the only definable properties of lengths are semilinear sets [36]. Semi-linear subsets of \(\mathbb{N}\) are known to be ultimately periodic: that is, for such a set \(S\subseteq \mathbb{N}\), there exists a threshold \(t\) and a period \(p\) such that \(n\in S\) if and only if \(n+p\in S\), as long as \(n>t\). Clearly the set \(\{2^k \mid k \in \mathbb{N}\}\) is not such.

The query can be expressed in positive recursive SQL:

The path is given by a binary relation P containing pairs \((v_i,v_{i+1})\) while minimal/maximal elements \(v_0\) and \(v_n\) are given by unary relations MIN_ELT and MAX_ELT. The first common table expression defines a ternary relation ADD with tuples \((v_i,v_j,v_k)\) such that \(i+j=k\). If \(v_i\) is in MIN_ELT, then \((v_i,v_j,v_j)\) and \((v_j,v_i,v_j)\) are in ADD for all \(j\) (the basis of recursion), and if \((v_i,v_j,v_k)\) is in ADD then so is \((v_{i+1},v_j,v_{k+1})\) (the recursive step). After that POW2 builds a relation with tuples \((v_i,v_j)\) for \(j = 2^i\). Indeed, if \((v_i,v_j)\) is in POW2, then so is \((v_{i+1},v_k)\) for \(k=2\cdot j\), which is tested by \((v_j,v_j,v_k)\in\texttt{ADD}\). The length of the path is a power of 2 if the second projection of POW2 contains MAX_ELT.

Note that ADD is defined by a linear Datalog program and POW2 is defined by a linear Datalog program that uses ADD as EDB. Hence, the entire query is defined by a piece-wise linear program (where already defined predicates can be used as if they were EDBs). It is known that such programs can be expressed in linear Datalog [37].

6.3.0.1 Complexity-theoretic considerations.

We now explain why the inexpressibility result is quite unexpected. Note that all graph pattern languages can express the reachability query. It is complete for the complexity class \(\mathrm{\small NLogSpace}\) via first-order reductions [38]: an extension of first-order logic with the reachability predicate capturtes precisely all \(\mathrm{\small NLogSpace}\)queries. Since GQL and PGQ can emulate relational algebra (and thus first-order logic) over pattern matching results, it appears that they should be able to express all \(\mathrm{\small NLogSpace}\)queries. In fact graph query languages expressing all \(\mathrm{\small NLogSpace}\)queries have been known for a long time, starting with GraphLog crpq?, which introduced the ubiquitous notion of CRPQs.

However, Theorem 4 not only refutes the complexity-based intuition, but in fact the separating query has an even lower \(\mathrm{\small DLogSpace}\) complexity. Indeed, one can traverse the dataless path graph while maintaining the counter that needs a logarithmic number of bits. This limitation highlights a deficiency of the language design: despite having access to reachability and full power of first-order logic on top of it, Core GQL and PGQ fall short of a declarative language that is first-order logic with the reachability predicate. The reason for this deficiency, that should ideally be addressed in future revisions of the standards, is discussed below in Section 8.

7 Limitations of Patterns: an experimental investigation↩︎

We have shown that many queries tracing changes in property values of edges cannot be expressed in Core GQL and PGQ, among them the simple query \(Q^{\mathsf{E}}_{\uparrow}\) that generated significant interest in the GQL standardization committee of ISO [16], [17]. Of course real-life languages have more expressiveness than their theoretical counterparts, and thus real-life GQL, SQL/PGQ, and also Cypher can express this query. However, they do so in a rather convoluted way. We now show experimentally that this way of expressing simple graph queries has no realistic chance to work, as it generates enormous (exponential size) intermediate results, and the query would not terminate even on tiny graphs.

The idea of expressing \(Q^{\mathsf{E}}_{\uparrow}\) is that its complement is easily definable in Core GQL. In GQL, PGQ, and Cypher, paths can be named and output. This is an advanced feature that we omitted in our core language: since paths are represented as lists, it results in non-flat outputs.

The complement of \(Q^{\mathsf{E}}_{\uparrow}\) is expressed by the pattern \(\psi^\neg\):

testing for a pair of consecutive edges that break the increasing motif; it can also be expressed by CoreGQL as \[\psi^\neg :=(v_1) \to^{0..\infty} \big(\;() \overset{x}{\rightarrow} () \overset{y}{\rightarrow} ()\;\big)\langle x.k \geq y.k\rangle \to^{0..\infty}(v_2)\,.\]

Thus, the query below

finds all nodes \(v_1, v_2\) and path \(p\) between them satisfying \(Q^{\mathsf{E}}_{\uparrow}\). The mere fact of expressing something does not yet mean it will work – for example, despite SQL having the capability to simulate Turing machines, we do not expect it to perform well with complex graph algorithms. Likewise here, the first subquery enumerates paths between two different nodes, and even the number of simple paths between two nodes in a graph can grow as fast as \(O(n!/n^2)\).

We now show experimentally that queries of this kind have no chance to work even on very small graphs. A small obstacle is that there is not yet any available implementation of GQL, and Cypher, the closest language, chose not to have \(\text{\normalfont\small\renewcommand{\ttdefault}{pcr}\ttfamily\bfseries\color{darkblue} EXCEPT}\). However, there is a way around it in Cypher by using list functions that can detect the violation of the “value in edges increases” condition:

We then tested its median running time in Neo4j², as well as the percentage of queries that time out (the timeout is set at 300 seconds). When more than 50% of queries time out, the median is shown as \(\infty\)ms. Otherwise the running time is computed as the median over 10 different graphs, with 1 run per graph (and an additional run 0 to generate the appropriate indices).

The graphs on which we tested the query are the random graphs \(G(n,p)\) [39] on \(n\) nodes where an edge exists between two nodes with probability \(p\). We considered values \(p\) between 0.1 and 0.5, with the step 0.1. As for data values in edges, they are also randomly generated, between 0 and 100. The reason we used this simple model of synthetic property graphs is that it very convincingly demonstrates that the above implementation of \(Q^{\mathsf{E}}_{\uparrow}\) has no chance to work in practice. Even with the smallest probability of 0.1, with a mere 24 nodes timeout was observed in more than 50% of all cases, and with just 30 nodes in all cases. As the probability \(p\) increases (meaning that there are more edges in the graph, and thus the number of paths increases), the cutoff for everything-times-out dropped to fewer than 10 nodes!

We add two notes here. Queries \(Q^{\mathsf{N}}_{\neq}\) and \(Q^{\mathsf{E}}_{\neq}\) can be similarly expressed, with the bottleneck query matching all paths being identical to the above, hence resulting in a very similar behavior. But behavior is not observed with \(Q^{\mathsf{N}}_{\uparrow}\) as it can be expressed directly with Cypher and GQL pattern matching, without having to find an exponential number of paths.

7.0.0.1 Other systems

Even though it appears that bypassing expressivity bounds by generating exponentially many queries should not have a chance to work (as our Neo4j tests confirm), we wanted to completely exclude the possibility that this behavior could be due to one specific implementation. Thus, to confirm the above results, we ran the same tests on two other systems: Memgraph, a graph-only database that uses Cypher as its query language, and DuckDB, a relational database that implements SQL/PGQ as an extension [27].

The results confirm that the problem is the way the query is written rather than a particular implementation. In fact, the limits of Neo4j and Memgraph are almost identical as shown in Fig. 5 which reports numbers of nodes at which 50% and 100% of runs timeout.

However, it must be noted that for the configurations that do not timeout, the performance of Memgraph appears to be much more efficient than that of Neo4j, with almost all test cases taking less than 1 ms. This might be explained by the fact that the timing procedures are different for the two systems as Memgraph does not make query execution time available to the driver.

The performance of DuckDB was tested using the SQL/PGQ query below; it first finds the shortest paths in the graph using the PGQ pattern matching syntax (the inner query), then checks, in SQL, that the edge weights appear in sorted order (the outer query).

While the results for DuckDB appear to be better than for native graph systems (it can handle 164 nodes with the lowest probability \(p=0.1\) before running out of memory), there is a simple explanation for it: the difference in path semantics. The only path semantics available for repeated patterns in DuckDB is shortest path, whereas the only one available in Neo4j and Memgraph is trail, which matches paths that do not go through the same edge twice. In most graphs there are significantly more trails than shortest paths between any given nodes, hence the number of candidate paths to be checked is much higher for Neo4j and Memgraph than for DuckDB. Even with this, however, the way of bypassing expressivity bounds by generating a large number of paths can only handle very small graphs, not even reaching 200 nodes.

8 What we learned about language design problems↩︎

A common way of enhancing the capabilities of query languages is: (1) an initial design is produced; (2) user-demanded queries that are not expressible in this initial design are identified; (3) their inexpressibility is formally confirmed; (4) language deficiencies that led to (3) are identified; (5) these deficiencies are fixed. Note that (5) is often an iterative process that involves a deep analysis of possible language design enhancements. Returning to the example of recursive queries in SQL, note that while it was quite clear that programmers cannot write queries such as transitive closure, it took a significant effort to confirm this formally. Subsequently hundreds of papers analyzed the expressiveness and complexity of datalog and fixed-point extensions of relational calculus, until the linear datalog approach was adopted by the SQL standard.

Where does this workflow put us with respect to the new graph standards, SQL/PGQ and GQL? Prior to this paper we were at stage (2); the results of this paper complete step (3) and put us at the beginning of stage (4). Thus, in this last section we outline further developments as we envision them now: what language deficiencies cause limited expressiveness, and how they could be addressed.

The main limitation of current graph query languages is that they lack compositionality. They are essentially graphs-to-relations languages, as opposed to graph-to-graph languages (though some ad hoc functionalities exist for viewing relational outputs into graphs, such as the Neo4j browser or its data science library facilities [40] that can extract graphs from relations for analytics tasks; also the study of graph views is in its infancy [41]). The lack of compositionality also manifests itself in the information flow in graph query languages. It happens in one direction, from graphs to relations: patterns turn graphs into relations, but there are no natural ways of going in the other direction, and use results of relational operations of either \(\mathsf{RA}\) or \(\mathsf{LCRA}\) to create new graphs. Of course real-life languages with their extended functionalities provide such ways (e.g., via libraries as mentioned above, or by writing data and using it to create new graph views in PGQ) – but the main point is that these lie outside the realm of a declarative query language.

With the understanding of causes of limitations, the focus needs to be shifted to ways to remedy those, i.e., step (5) above. If the story of SQL is any indication, this will require a considerable research effort. Still, we can outline what we think are possible approaches to fixing the non-compositionality issues.

8.0.0.1 Pattern matching restricted to matched paths

While graph-to-graph languages are the ultimate long-term goal, in the short term some of non-compositionality can be fixed by letting pattern matching operate on previously matched patterns. We explain this idea by the query \(Q^{\mathsf{E}}_{\uparrow}\). To find such paths from \(\ell_1\)-labeled nodes to \(\ell_2\)-labeled nodes, we can first match paths from \(\ell_1\)-nodes to \(\ell_2\)-nodes and then exclude those where the “increasing value in edges” condition is violated. Specifically, we start with the pattern \(\psi:=(x) \to^{1..\infty} (y) \langle{\ell_1(x) \wedge \ell_2(y)}\rangle\) and then create a new pattern \[\label{eq-for-concl} \psi\;| \;\neg\exists(\overset{u}{\to} \;() \;\overset{v}{\to}\langle u.k \geq v.k\rangle)\tag{1}\] The pipe operator \(|\) means that the pattern \(\overset{u}{\to} () \overset{v}{\to}\langle u.k \geq v.k\rangle\) is evaluated on the result of the match of pattern \(\psi\), and the condition \(\neg\exists\) says that there are no matches for it. This will ensure that in the match for \(\psi\) there are no consecutive edges for which the value of their property does not increase.

8.0.0.2 Constructing graph elements from tables

In current graph languages the flow of information is in the direction from graph to constructed relations. What if we could reverse it as well and construct new graph elements from relations? As an example of this, suppose we could construct new nodes with label old_edge whose ids are edge ids in a graph \(G\), and a new edge with a lable new_edge which connects two such nodes coming from edges \(e_1\) and \(e_2\) of \(G\) if the target of \(e_1\) is the source of \(e_2\). Then \[(x) \big( (u) \overset{e}{\to} (v)\langle u.k<v.k \wedge \textit{new\_edge}(e)\rangle \big) (y)\] (i.e., \(Q^{\mathsf{N}}_{\uparrow}\) on the constructed graph) expresses \(Q^{\mathsf{E}}_{\uparrow}\) on \(G\). This powerful idea was already present in an early theoretical language of crpq? but never properly explored in the context of practical graph languages.

Language design is a delicate process in which the right balance must be struck between expressivity and complexity. It is not simple “add these features”; much new research is required as they come with complexity consequences. To give one example, in (1 ) replace \(\overset{u}{\to} () \overset{v}{\to}\langle u.k \geq v.k\rangle\) with \((u) \to^{1..\infty} (v)\langle u.k = v.k\rangle\). This results in query \(Q^{\mathsf{N}}_{\neq}\) known to be NP-hard in data complexity [10]. Thus, such extensions are very sensitive to small syntactic changes. This however should simply be viewed as an invitation to start a research investigation into extensions of GQL and PGQ that allow desirable queries without unmanageable computational overhead. Once again, the past history of SQL tells us that such research could be very productive and have a great influence on the language.

Acknowledgments↩︎

This research was supported by ANR-21-CE48-0015 Project VeriGraph, a grant from RelationalAI to IRIF, Poland’s National Science Centre grant 2018/30/E/ST6/00042, and Israel Science Foundation grant 2355/24.

9 Proof of theorem [prop:SLRA-vs-LRA]↩︎

At first, observe that simple linear clauses (without \(\{\mathcal{Q}\}\)) can only express conjunctive queries, as their semantics applies operations \(\bowtie, \pi, \sigma\) and renaming to base relations. Hence, queries of sLCRA are Boolean combinations of conjunctive queries, known as BCCQs. While it appears to be folklore that BCCQs are strictly contained in first-order logic, we were unable to find the simple proof explicitly stated in the literature, hence we offer ohe here.

Consider a vocabulary of a single unary predicate \(U\) and databases \(\mathcal{D}_1\) and \(\mathcal{D}_2\) such that \(\mathcal{D}_1(U) = \{a_1\}\) and \(\mathcal{D}_2(U) = \{a_1,a_2\}\) for two different constants \(a_1\) and \(a_2\). Since \(\mathcal{D}_1\) and \(\mathcal{D}_2\) are homomorphically equivalent, they agree on all conjunctive queries, and therefore on all BCCQs, but they do not agree on first-order (and hence \(\mathsf{RA}\)) query that checks if relation \(U\) has exactly one element.

10 Proof of theorem 1↩︎

We first prove that \(\mathsf{RA}(\mathbf{S})\) is subsumed by \(\mathsf{LCRA}(\mathbf{S})\). Let \(Q\) be a query in \(\mathsf{RA}(\mathbf{S})\). We show that there exists an equivalent query \(Q^{\mathsf{LCRA}}\) in \(\mathsf{LCRA}(\mathbf{S})\), i.e. such that for every database \(\mathcal{D}\) over \(\mathbf{S}\) it holds that \(\left\llbracket Q\right\rrbracket_{\mathcal{D}} = \left\llbracket Q_L\right\rrbracket_{\mathcal{D}}\) by induction on the structure of \(Q\).

• (base case) If \(Q = R\) then \(Q_L = S\) where \(S = \{R\}\)

• If \(Q = \psi_{\bar{A}} (Q')\) and \(Q'_L\) is the LRA query equivalent to \(Q'\) then \(Q_L = Q'_L~\pi_{\bar{A}}\)

• If \(Q = \sigma_{\theta}(Q')\) and \(Q'_L\) is the LRA query equivalent to \(Q'\) then \(Q_L = Q'_L ~ \sigma_{\theta}\)

• If \(Q = \rho_{\bar{A} \rightarrow \bar {B}}(Q')\) and and \(Q'_L\) is the LRA query equivalent to \(Q'\) then \(Q_L = Q'_L~\rho_{\bar{A} \rightarrow \bar {B}}\)

• For the three following cases, \(Q'\) (resp. \(Q''\)) is systematically translated as \(\{Q'_L\}\) (resp. \(\{Q_L''\}\))

• If \(Q = Q' \cup Q''\) and \(Q'_L\) (resp. \(Q''_L\)) is the LRA query equivalent to \(Q'\) (resp. \(Q''\)) then \(Q_L = \{Q'_L\} \cup \{Q''_L\}\)

• If \(Q = Q' \setminus Q''\) and \(Q'_L\) (resp. \(Q''_L\)) is the LRA query equivalent to \(Q'\) (resp. \(Q''\)) then \(Q_L = \{Q'_L\} \setminus \{Q''_L\}\)

• If \(Q = Q' \bowtie Q''\) and \(Q'_L\) (resp. \(Q''_L\)) is the LRA query equivalent to \(Q'\) (resp. \(Q''\)) then \(Q_L = \{Q'_L\} \{Q''_L\}\) as, by definition of RA, it must be that \(\mathsf{attr}(Q') \cap \mathsf{attr}(Q'') = \emptyset\)

We now prove that \(\mathsf{LCRA}(\mathbf{S})\) is subsumed by \(\mathsf{RA}(\mathbf{S})\). Let \(Q\) be a query in \(\mathsf{LCRA}(\mathbf{S})\). We show that there exists a query \(Q^{RA} \in \mathsf{RA}(\mathbf{S})\) such that for every database \(\mathcal{D}\) over \(\mathbf{S}\) it holds that \(\left\llbracket Q\right\rrbracket_{\mathcal{D}} = \left\llbracket Q^{RA}\right\rrbracket_{\mathcal{D}}\) by induction on the structure of \(Q\).

We start with the linear clauses. Since their structure is not tree-shaped, but indeed linear, the query must be parsed from left to right, while the equivalent \(\mathsf{RA}\) query will be built bottom-up. Let \(C = c_0, \ldots, c_n\) be a linear clause in \(\mathsf{LCRA}(\mathbf{S})\). We build the induction on the number of clauses of \(C\).

• (base case) If \(n=1\) and \(C\) is an instance of the \(S\) rule, i.e. \(C = R\) for some \(R\) then the \(\mathsf{RA}\) query equivalent to \(C\) is \(R\)

• (base case) If \(n=1\) and \(C\) is one of \(\pi_{\bar{A}}, \sigma_{\theta}\) or \(\rho_{\bar{A} \rightarrow \bar {B}}\) then the \(\mathsf{RA}\) query equivalent to \(C\) is \(I_{\emptyset}\) (the empty tuple relation)

• (base case) If \(n=1\) and is \(C\) is an instance of the \(\{Q\}\) rule, then the \(\mathsf{RA}\) query equivalent to \(C\) is the one equivalent to \(Q\) (see induction for queries below)

• For the inductive cases, let \(C_i^{RA}\) be the \(\mathsf{RA}\) query such that \(\left\llbracket c_0, \ldots, c_i\right\rrbracket = \left\llbracket C_i^{RA}\right\rrbracket\)

• If \(n > 1\) and \(c_{i+1}\) is an instance of the \(S\) rule, i.e. \(c_{i+1} = R\), then \(C_{i+1}^{RA} = C_i^{RA} \bowtie R\)

• If \(n > 1\) and \(c_{i+1} = \pi_{\bar{A}}\), then \(C_{i+1}^{RA} = \pi_{\bar{A}} (C_i^{RA})\)

• If \(n > 1\) and \(c_{i+1} = \sigma_{\theta}\), then \(C_{i+1}^{RA} = \sigma_{\theta} (C_i^{RA})\)

• If \(n > 1\) and \(c_{i+1} = \rho_{\bar{A} \rightarrow \bar{B}}\), then \(C_{i+1}^{RA} = \rho_{\bar{A} \rightarrow \bar{B}} (C_i^{RA})\)

• If \(n > 1\), \(c_{i+1} = \{Q\}\) and \(C_Q^{RA}\) is the \(\mathsf{RA}\) query equivalent to \(Q\), then \(C_{i+1} = C_i^{RA} \bowtie C_Q^{RA}\)

We now treat the queries. Let \(Q\) be an \(\mathsf{LCRA}\) query. We build the induction on the structure of \(Q\).

• (base case) If \(Q = L\) then the \(\mathsf{RA}\) query equivalent to \(Q\) is the one equivalent to \(L\) (see above for induction on linear clauses).

• If \(Q = Q_1 \cap Q_2\) and \(Q_1^{RA}\) (resp. \(Q_2^{RA}\)) is the \(\mathsf{RA}\) query equivalent to \(Q_1\) (resp. \(Q_2\)) then the \(\mathsf{RA}\) query equivalent to \(Q\) is \(Q_1^{RA} \cap Q_2^{RA}\)

• If \(Q = Q_1 \cup Q_2\) and \(Q_1^{RA}\) (resp. \(Q_2^{RA}\)) is the \(\mathsf{RA}\) query equivalent to \(Q_1\) (resp. \(Q_2\)) then the \(\mathsf{RA}\) query equivalent to \(Q\) is \(Q_1^{RA} \cup Q_2^{RA}\)

• If \(Q = Q_1 \setminus Q_2\) and \(Q_1^{RA}\) (resp. \(Q_2^{RA}\)) is the \(\mathsf{RA}\) query equivalent to \(Q_1\) (resp. \(Q_2\)) then the \(\mathsf{RA}\) query equivalent to \(Q\) is \(Q_1^{RA} \setminus Q_2^{RA}\)

11 Proof of Theorem 2↩︎

For an annotated path \(p\), we define \(w_p\) as the sequence \(e_0.k\cdots e_{n-1}.k\).

For two annotated paths \(p:=\)

and \(p':=\)

we use \({p'}\sqsubseteq p\) to denote that \(p'\) is contained within \(p\). Formally, \({p'}\sqsubseteq p\) if there is \(j\) such that \(v'_0 = v_j, \ldots, v'_{n'} = v_{j+n'}\), and \(e'_0 = e_j,\ldots , e'_{n'-1} = e_{j+n'-1}\).

Let \(\psi\) be a path pattern. We define \[\mathcal{L}(\psi) = \{w \mid \forall\,p: \left(w=w_p \rightarrow \exists\, \mu:(p,\mu )\in \left\llbracket\psi\right\rrbracket_{p} \right) \}\]

For concatenation, we have:

For repetition, we have:

We can further generalize this lemma by replacing \(2\) with any \(k\ge 1\).

To apply the above lemmas to our settings we first present a Normal Form for path patterns. We say that a one-way path pattern is in \(+\)NF if \(+\) occurs only under unbounded repetition.

We are now ready to move to the main proof.

11.1 Generalizing Theorem 2↩︎

We define generalized annotated paths as paths whose nodes and edges are annotated each with one data value attached to a key \(k\). We define the language of these paths as sets of words, which we also refer to as path annotations, that are obtained by concatenating the data values according to their position. In particular, each word in the language starts with a data value of the first node and ends with that of the last one. In between it alternates between data of edge and node. For example, the language \(\mathcal{L}()\) of a generalized path is an .…

We define the operator \(\odot\) on path annotations \(p_1,p_2\) whenever the last letter of \(p_1\) equals to the first letter of \(p_2\) as follows: \[p_1 \odot p_2 :=n_0.k\, e_0.k\, \cdots n_{m-1}.k\, e_{m-1}.k\, n_m.k\, e'_0.k\, \cdots n'_{\ell-1}.k\, e'_{\ell-1}.k\, n_{\ell}.k\] We generalize this definition to sets of path annotations in the standard way: \[P_1 \odot P_2 :=\{ p_1\cdot p_2 \,\vline \, p_1 \in P_1, p_2 \in P_2, p_2\text{ concatenates to } p_1 \}\]

With this, we can move to prove a pumping-lemma for one-way path patterns. This lemma shows that whenever we have a path pattern that accepts paths of unbounded length, we can obtain infinitely many paths that are also accepted by the pattern.

Based on this pumping argument we are now ready to prove the main inexpressibility result.

12 Proof of Corollary 2↩︎

The claim on \(Q^{\mathsf{E}}_{\neq}\) is proved similarly to Theorem 2. Assume by contradiction that there is a one-way path pattern \(\psi\) that expresses \(Q^{\mathsf{N}}_{\neq}\). Using the same notation as in the proof of Theorem 2 we get a contradiction since if \(p_1,\ldots,p_k\) consists of three symbols it has to be the case that the first and last are the same, and otherwise the pumping results in a path annotation that does not satisfy the condition.

13 Proof of Theorem 2↩︎

First, notice that if a path contains a cycle, it cannot be an answer to \(Q^{\mathsf{N}}_{\neq}\) as the value in the node the path comes back to would be repeated (at least) twice, so we can safely consider only "path shaped" graphs with values on the nodes. Formally, we look at node-annotated paths of the form

where \(v_0, \ldots, v_n\) are distinct nodes, \(e_0, \ldots, e_{n-1}\) are distinct edges (for \(n > 0\)) and each \(v_i\) has the property \(v_i.k\) defined. The node-value word of a node-annotated path is defined as \(w^N_p = v_1.k \cdot v_2.k \cdots v_n.k\).

As in Section 11, we define the node-value language of a one-way path pattern \(\psi\) as \(\mathcal{L}^N(\psi) = \{w \mid \exists (p, \mu) \in \left\llbracket\psi\right\rrbracket_p, w^N_p = w\}\).

The above lemma can be easily extended to concatenations of arbitrary size.

We can now prove Theorem 2.

Assume, by contradiction, that there is a one-way path pattern \(\psi\) equivalent to \(Q^{\mathsf{N}}_{\neq}\). By lemma 6, we can assume that \(\psi\) is in +NF, and so of the shape \(\psi_1+\cdots+\psi_m\), and since the language of \(Q^{\mathsf{N}}_{\neq}\) is infinite, we can further assume that at least one of the \(\psi_i\) is of the shape \(\rho_1 \ldots \rho_j^{n..\infty} \ldots \rho_k\). Let \(w\) be a word in \(\mathcal{L}^N(\rho_j^{n..\infty})\). By lemma 8, we have that \(ww\) also belongs to \(\mathcal{L}^N(\rho_j^{n..\infty})\) and, by lemma 9 we can conclude that there exists a path \(p\) and an assignment \(\mu\) such that \(ww\) is a subword of \(w^N_p\) and \((p, \mu) \in \mathcal{L}^N(\rho_1 \ldots \rho_j^{n..\infty} \ldots \rho_k)\). Since all values in \(ww\) are repeated twice, \(\psi\) cannot be equivalent to \(Q^{\mathsf{N}}_{\neq}\).

14 Proof of Theorem 4↩︎

In what follows, we focus on data-less paths which are, as before, graphs whose underlying structures are paths, without properties and labels.

where \(n\ge 0\), and \(v_i \ne v_j\in\mathsf{N}, e_i \ne e_j\in \mathsf{E}\) for every \(i \ne j\), and \(\mathsf{lab}(v_1) = \mathsf{first},\,\mathsf{lab}(v_n)= \mathsf{last}\).

We then show that no Boolean Core GQL query returns true on \(G_n\) iff \(n\) is a power of 2.

14.1 Proof of Theorem 6↩︎

For a data-less path \(\mathbf{p}_\epsilon\), we define the function \(\mathsf{pos}\) that maps each node in \(\mathbf{p}_\epsilon\) to its position (where the position of the first node in \(\mathbf{p}_\epsilon\) is \(1\)) and each edge in \(\mathbf{p}_\epsilon\) to the tagged position of its source node. We do so to distingush whether a position correspond to a node or an edge. For example, if \(\mathbf{p}_\epsilon\) is

then \(\mathsf{pos}(n_j) = j\) and \(\mathsf{pos}(e_j) = j'\). We treat tagged integers as integers wrt to arithmetics and equality.

Before proving the translation from path patterns to PA, we first show that path patterns without variables can be translated to automata.

We obtain the following connection:

14.2 Datalog on Graphs↩︎

Datalog↩︎

Let \(\mathcal{S}\) be a schema. An atom over \(\mathcal{S}\) is an element of the form \(S(x_1,\ldots, x_k)\) where \(S\in\mathcal{S}\), \(\mathsf{arity}(S)=k\) and \(x_1,\ldots x_k\) is a sequence of variables with no repetitions. A Datalog program is a tuple \((\mathcal{E},\mathcal{I},\Phi,\mathtt{Out})\) where \(\mathcal{E}\) and \(\mathcal{I}\), namely the IDB and EDB signatures, respectively, are disjoint schemas, \(\mathtt{Out}\) is a designated relation symbol in \(\mathcal{I}\), and \(\Phi\) is a set of rules \(\rho\) of the form \[\varphi\leftarrow \varphi_1 , \ldots, \varphi_m\] where \(\varphi\) is an atom over \(\mathcal{I}\), and each \(\varphi_i\) is an atom over \(\mathcal{I}\cup \mathcal{E}\). We restrict further the rules by allowing only cases in which each variable in the head \(\varphi\) of \(\rho\) occurs also in its body, namely \(\varphi_1, \ldots, \varphi_m\).

The semantics \(\left\llbracket P\right\rrbracket_{\mathcal{D}}\) of a Datalog program \(P :=(\mathcal{E},\mathcal{I},\Phi,\mathtt{Out})\) over a database \(\mathcal{D}\) is defined in the standard way  as we recall now: Given a database \(\mathcal{D}\) over a schema \(\mathbf{S}\), a partial mapping \(\mu:\mathsf{Vars}\rightarrow \mathbf{U}\) satisfies an atom \(\varphi(x_1,\ldots,x_k)\) (w.r.t. \(\mathcal{D}\)) if \(\varphi\in \mathbf{S}\) and \((\mu(x_1),\ldots,\mu(x_k))\in \mathcal{D}({\varphi})\). A database \(\mathcal{D}'\) satisfies a rule \(\rho\) if every partial mapping \(\mu\) that satisfies each of \(\rho\)’s body atoms w.r.t. \(\mathcal{D}'\), also satisfies its head atom. A database \(\mathcal{D}'\) satisfies a set \(\Phi\) of rules if it satisfies every \(\rho\in \Phi\). We define the semantics \(\left\llbracket P\right\rrbracket_{\mathcal{D}} :=\mathcal{D}'\) such that (1) \(\mathcal{D}'\) satisfies \(\Phi\) and (2) every \(\mathcal{D}''\) that satisfies \(\Phi\) has the following property: every relation symbol \(R \in \mathcal{I}\cup \mathcal{E}\), the set \(\mathcal{D}'(R) \subseteq \mathcal{D}''(R)\). We say that \(P\) is Boolean if \(\mathsf{arity}(\mathtt{Out}) = 0\), and in this case, we say it outputs \(\boldsymbol{true}\) if \(\mathtt{Out}() \in\left\llbracket P\right\rrbracket_{\mathcal{D}}\).

Datalog over property graphs

We view property graphs \(G :=\langle N, E, \mathsf{lab}, \mathsf{src}, \mathsf{tgt}, \mathsf{prop}\rangle\) as relational structures \(\mathcal{D}_G\) over the relational schema consisting of relation symbols \(N, E, \mathsf{lab}, \mathsf{src}, \mathsf{tgt}, \mathsf{prop}\) with the straightforward interpretation.

Using a straightforward induction, we can show that:

We denote \(\mathcal{D}_p\) by the \(\mathcal{D}_n\) where \(n\) is the length of \(p\). We can view Boolean Datalog Programs as queries on the quotient space \(P/\sim\) and define \[\mathsf{len}(P) :=\{n \mid \left\llbracket P\right\rrbracket_{\mathcal{D}_{n}} = \boldsymbol{true}\}.\] We can conclude:

14.3 Proof of Theorem 4↩︎

The proof follows directly from Theorem 6 and Corollary [cor:dl2pown].

References↩︎

---

1. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment.
   

   Proceedings of the VLDB Endowment, Vol. 18, No. 6ISSN 2150-8097.
   doi:10.14778/3725688.3725707
   ↩︎

2. The testing program is written in Go and communicates with Neo4j (v5.18.1) via the Neo4j Go driver. All tests were executed on a machine with the following configuration: 16 Intel i7-10700 @ 2.90GHz CPUs, 16GB RAM, Ubuntu 22.04.3 LTS↩︎

3. Notice that it can be the case that \(\mathcal{L}(\psi_i) = \mathcal{L}(\rho_1) \mathcal{L}( \rho)^{n..\infty} \mathcal{L}(\rho_2) \langle \theta \rangle\) in which case the sequel of the proof still holds since the condition \(\theta\) can only refer to variables in \(\rho_1,\rho_2\).↩︎

4. Liat: Can elaborate more depending on which part of \(w\) the pumped part conforms to.…↩︎