1 Introduction↩︎

Graph databases are data models with a multitude of natural applications including social networks, semantic web, biology, ecology, supply chain management, and business process modeling. With graphs as one of the main repositories of data, graph querying has become a major component in data wrangling. Indeed, graph database systems – like Neo4j, Oracle, TigerGraph, among many others – have increasingly found usage in a plethora of application domains.

One important feature in graph query languages is the ability to query for paths over a given database. In fact, much of the effort in the study of graph query languages in database theory has been motivated by the need to support path queries. For example, in real world query languages (like Neo4j Cypher queries) one uses patterns like:

    (?x)=[:friend*]=>(Erdos)

to find nodes that are connected to Erdos by the friend relation (assuming it is symmetric). Similar capabilities are also supported by SPARQL property paths. A systematic study of query languages supporting “path patterns” has been undertaken in database theory since the 1990s, resulting in a plethora of query languages over graphs. The core of such languages can be classified into three categories: (1) extensions of regular path queries [1]–[3], (2) walk logic [4], [5], and (3) first-order logic with transitive closure operators [2], [6]. In addition, while the original query languages were studied within the basic graph database setting of edge-labelled graphs with finitely many labels, recent developments suggest the importance of supporting data in the model, not just topology. For example, if a node represents a person (with data including age, firstname, lastname, etc.) in a social network and an edge represents a “friend-of” relation, then we might be interested in a pair of friend-of-friends (i.e. transitive closure of friend relations) with the same data component lastname. To support such queries, an extended graph data model of data graphs [2], [7] was proposed, wherein additional binary relations \(\equiv_{\mathrm{\small data} ,i} \subseteq V \times V\) for \(1 \leq i \leq n\) over nodes in the graph check whether two nodes have the same \(i^{th}\) data component (e.g. lastname). The bulk of graph queries can be (and have been) extended to the setting of data graphs [2], [5], [7], [8].

Zoo of query languages over data graphs. We proceed by first surveying the categories (1)–(3) of graph query languages. The first category of query language is based on the idea of using regular languages to describe “path patterns”. This originates in the seminal paper of Mendelzon and Wood [1], which introduces the so-called Regular Path Queries (RPQ). For example, to describe the friend-of-friends relation, one may simply write the path pattern \((\texttt{friend})^*\), where \(\texttt{friend}\) is a name of a relation in the database describing the friend-of relation. The class RPQ has been extended to operate over data graphs [2], [7], and to support unions/conjunctions [9]–[11]. For example, the query language Conjunctive Regular Path queries denoted CRPQ arose as part of the language GraphLog [12]. It has also been extended to support regular path comparisons [3], utilized in the language Extended CRPQ(ECRPQ). In particular, register automata – or, equivalently, regular expressions with memory – are used to extend the notion of regular path patterns to data paths, an alternating sequence of data and edge labels. In register automata an unbounded register/memory is required to store data. For example, to enforce that the start node \(v\) and end node \(w\) correspond to persons with the same lastname attribute, an automaton can save the last name of the first person \(v\) in the register and then check if it is the same as the last name of the last person \(w\). The idea of using register automata to express regular patterns over data paths, or tuples of data paths, can also be easily extended to CRPQ and ECRPQ, as well as their extensions with negations CRPQ\(_\neg\), and ECRPQ\(_\neg\). To emphasize the data model used by the query languages, on which they operate, we denote RPQ, CRPQ, etc. by RDPQ, CRDPQ, etc., as suggested by [2].

The second paradigm is that of Walk Logic (WL) [4], which takes paths within graphs as the fundamental data item referenced within query variables. Paths are manipulated through first-order predicate logic operations: roughly the paradigm is “relational calculus for paths”. As explained in [5], WL can be construed as a query language over data graphs.

The third paradigm is inspired by first-order logic with transitive closure operators [6]. This logic was studied in the setting of data graphs in [2], where additional binary relations \(\equiv_{\mathrm{\small data} ,i}\subseteq V \times V\) over nodes in the graph are introduced that check whether two nodes have the same \(i^{th}\) data component. This resulting logic (called FO\(^*(\equiv_{\mathrm{\small data} })\)) subsumes GXPath [2] and also regular (data) queries [13].

Finally, we mention another language that can be related to the first paradigm, the recently proposed Graph Pattern Calculus (GPC) [14], [15], which arose during the ongoing standardization efforts [16] of SQL/PGQ and GQL for the more expressive graph data model of property graphs.

Contributions: We begin by studying the prior proposals for graph query languages in the framework of data graphs. We analyze the expressiveness of these languages, identifying which containments hold: see Figure 1. In the figure, the containment results indicated by red edges are either known or trivial, while other containment and incomparability results are new. Specifically, we show that over data graphs the most expressive existing language FO(ERDPQ) from the first paradigm strictly subsumes WL, RDPQ, as well as GPC. Although we show that FO\(^*(\equiv_{\mathrm{\small data} })\), from Category (3), subsumes RDPQ, we prove that it is incomparable with FO(ERDPQ), as well as GPC. This leaves the question of whether there is a natural way to reconcile FO(ERDPQ) and FO\(^*(\equiv_{\mathrm{\small data} })\). Towards resolving this, we propose a language that subsumes all the existing ones. A summary of the revised landscape in terms of expressive power can be found in Figure 2.

At a high level, our proofs utilize the usual expressiveness toolbox in finite model theory – e.g. automata and complexity-theoretic arguments. But their application to some of the finer-grain comparisons we consider here requires some subtlety. For example, since FO(ERDPQ) combines regular expression power with some arithmetic, in separating FO(ERDPQ) from MWL – an extension of WL introduced in this paper with expressiveness between FO(ERDPQ) and WL – we require a combination of circuit complexity bounds and rewriting techniques; in showing RDPQ is not subsumed by GPC, we need to bound the expressiveness of GPC, and thus require a variation of the pumping lemma for automata that is tailored towards the fine points of the GPC syntax.

Limitations: Deviations from other proposals and standards. This paper is a step towards a better understanding of the expressiveness landscape for these languages. In doing so, we have made a number of simplifications both at the data model and query language level, relative to languages considered by both practitioner query languages and the evolving standards. One of these simplifications is at the data model level. There is a more flexible (and complex) data model called property graphs [16], [17], which allows both edge and node labels, both of which can be varying or bound by a specific “schema”. This model has been in the spotlight in database theory in recent years, and property graphs will serve as the data model for GQL, the standard graph query language that is currently under intense development (e.g. see [14]–[16]).

Another simplification involves directionality in navigating a graph. We deal with a directed graph model, but in our formalization of the regular path query and walk logic paradigms, we allow only navigation in the forward direction. This is consistent with formalization of traditional query languages like R(D)PQ [2], ECRPQ [3], and Walk Logic [4]. On the other hand, queries in \(GPC\) allow navigation in both directions. Such a small “mismatch” would immediately render \(GPC\) to be incomparable with the aforementioned languages for trivial reasons. For a fair comparison, one could either (i) extend RDPQ, ECRPQ, and Walk Logic with bidirectional navigations, or (ii) allow only a forward direction in \(GPC\). We opted for (ii). See further discussion in Section 7.

A third deviation concerns support for trails: one of our considered languages, \(GPC\), allows one to restrict to paths with no repetition among nodes. We omit this feature, but only to keep the exposition briefer: we show in Section 7 that all the results still hold when the syntax of \(GPC\) is extended to include this. Although our work assumes a simpler data and query model, we believe our results will be useful in considering the expressiveness of languages making use of the full property graph data model.

2 Preliminaries↩︎

General notation. We use \(\mathbb{N}\) and \(\mathbb{Z}_{>0}\) to denote the sets of non-negative integers and positive integers, respectively. For any two \(i\) and \(j\) in \(\mathbb{N}\) where \(i<j\), the notation \([i,j]\) represents the set \(\{i, i+1, \dots, j\}\). If \(i=1\), we simply write \([j]\), abbreviating \([1,j]\). Let \(m\) be a mapping, and let \(d\) and \(i\) be elements in the domain and image of \(m\), respectively. The notation \(m[d\mapsto i]\) represents the mapping equivalent to \(m\), except that \(d\) is now mapped to \(i\).

Data model. In this work, we are concerned with graphs that incorporate data, referred to as data graphs. Specifically, each node corresponds to a unique id and is accompanied by additional attributes. For instance, as shown in Figure 3, nodes possess attributes such as Name (with the data type string) and Age (with the data type natural number). To denote the sets of ids and other pertinent attributes (“properties”), we use \(\mathcal{D}_{\mathrm{\small id} }\) and \(\mathcal{D}_{\mathrm{\small prop} }\), respectively. Here, \(\mathcal{D}_{\mathrm{\small prop} }\) represents a \(k\)-ary relation, where \(k\) is the number of attributes that nodes have, excluding the id. For the example shown in Figure 3, \(k\) is 2. The data domain, denoted as \(\mathcal{D}\), is the Cartesian product of \(\mathcal{D}_{\mathrm{\small id} }\) and \(\mathcal{D}_{\mathrm{\small prop} }\) when \(k > 0\); otherwise, when \(k = 0\), \(\mathcal{D}\) is equal to \(\mathcal{D}_{\mathrm{\small id} }\).

Formally, a data graph is a directed graph in which each node corresponds to a data value. To define the data value of a node, we introduce two key functions, \(\mathrm{\small id}\) and \(\nodedata\). The function \(\mathrm{\small id}\) maps each node \(v\) to its unique id. For example, in Figure 3, we have \(\mathrm{\small id} (n_2) = 07\), \(\mathrm{\small id} (n_9) = 24\), and \(\mathrm{\small id} (n_{13}) = 29\). When \(k > 0\), for each \(i \in [k]\), we define \(\nodedata_i\) as the function that maps each node \(v\) to the \(i^{\text{th}}\) component of \(\nodedata[v]\). In other words, if \(\nodedata[v] = (d_1, \dots, d_i, \dots, d_k)\), then \(\nodedata_i(v) = d_i\). For instance, for nodes \(n_2\), \(n_9\), and \(n_{13}\), we have \(\nodedata(n_9) = (\textit{Paul}, 5) = \nodedata(n_{13})\), and \(\nodedata_2(n_2) = 66\). Since the function \(\mathrm{\small id}\) is injective, for any two nodes \(v\) and \(v'\) in \(V\), \(\mathrm{\small id} (v) = \mathrm{\small id} (v')\) if and only if \(v = v'\). The tuple \((\mathrm{\small id} (v), \nodedata(v)) \in \mathcal{D}\) represents the data value of node \(v\). For simplicity, we often treat a node’s id as synonymous with the node itself.

Our definition of data graphs extends the one provided in [7]. The primary distinction is that, in our definition, each node has a unique id as part of its data value, as is done in [5]. This slight modification allows us to model node identity in all our query languages without cluttering them with additional syntax. More importantly, treating ids as part of node data values is realized through the \(\mathrm{\small id}\) function, and this feature plays a significant role in the expressiveness of the regular data path query language (RDPQ) and its extensions, defined in Section 3.2. For example, the query “Does a node appear more than once along a path \(\pi\)?” would be inexpressible in RDPQ and its extensions if ids were not considered part of node data values, or if the \(\mathrm{\small id}\) function were removed from our definition. In such a case, these languages and other languages considered in this paper would become incomparable. However, this would contradict one of our goals: to characterize existing query languages for graphs with data and identify their core features.

The formal definition of data graphs is as follows:

A path \(\rho\) in the data graph \(G\) is a non-empty alternating sequence \[v_0 \thinspace a_1 \thinspace v_1 \thinspace\dots v_{n-1} \thinspace a_n \thinspace v_n\] where \(v_i \in V\), \(a_j \in \Sigma\), and \((v_{l-1},a_l,v_l)\) forms an edge in \(E\) for all \(i\), \(j\), and \(l\). The length of \(\rho\), denoted as \(|\rho|\), is \(n\). The set of positions of \(\rho\) is \([0,n]\), with \(v_i\) being the node at position \(i\) for every \(i \in [0,n]\). The data path corresponding to \(\rho\) is the string \(d_0 \thinspace a_1 \thinspace d_1 \dots a_n \thinspace d_n\), where \(d_i\) represents the data value associated with \(v_i\) for every \(i \in [0,n]\). This data path is denoted as \(\mathbf{dp}(\rho)\). The label of \(\rho\) is \(\mathbf{lb}(\rho) = a_1\dots a_n\). A path \(\rho\) is considered a simple path if \(v_i \neq v_j\) for every \(i,j \in [0,n]\) and \(i \neq j\). For example, consider the path in the graph from Figure 3: \[\rho = n_4 \thinspace{s} \thinspace n_3 \thinspace{p} \thinspace n_{11} \thinspace{p} \thinspace n_9 \thinspace{f} \thinspace n_{13}\] It is a simple path, with \(\mathbf{lb}(\rho) = {s \thinspace p \thinspace p \thinspace f}\) and \(\mathbf{dp}(\rho) = (03,\textit{Mary},56) \ldots\linebreak (29,\textit{Paul},5)\).

Given two paths \(\rho = v_0 ~ a_1 ~ v_1 \dots v_n\) and \(\rho' = v'_0 ~ a'_1 ~ v'_1 \dots v'_m\), \(\rho\) can be concatenated with \(\rho'\) if \(v_n = v'_0\). The concatenated path, denoted as \(\rho \cdot \rho'\), is given by \(v_0 ~ a_1 \dots v_n ~ a'_1 ~ v'_1 \dots v'_m\). A graph \(G\) is classified as a chain if it is connected and each node has at most one predecessor and at most one successor.

Queries. Informally, a query is a function that returns a Boolean value, taking as input a data graph over a given \(\Sigma, \mathcal{D}\), along with a valuation that maps a predetermined set of free variables of different types (paths, nodes, positions) to values of the appropriate kind. While these languages often vary in the types of free variables they accommodate, all our query languages support Boolean graph queries, where the input is solely a data graph over \(\Sigma, \mathcal{D}\). Usually, \(\Sigma, \mathcal{D}\) will be evident from the context, so we’ll omit them.

In previous discussions, we’ve addressed languages semantically as collections of queries, yet of course, languages of interest are usually defined using syntax for expressions. Often, we identify the expressions with their corresponding queries. Therefore, given a (syntactically defined) query language, a related problem is to evaluate an expression in the language on a given data graph. This is the query evaluation problem for the language.

3 Existing query languages for graphs with data↩︎

3.1 Graph querying based on path quantification↩︎

Walk logic (WL) is a first-order graph query language that quantifies over variables ranging paths and positions within paths [4]. With the capability to manipulate paths and positions, the query \(Q_H\): “Is there a Hamiltonian path in the graph?” can be readily expressed using WL. Before providing an exact definition, it is instructive to understand how WL expresses that a graph is Hamiltonian. A graph is Hamiltonian if it possesses a path that (1) is simple (with no repeated nodes) and (2) visits all nodes. This can be expressed using a logic that quantifies over paths and positions within a given path. We employ variables \(\pi\) and \(\omega\) for variables ranging over paths, and \(\ell^\pi\) and \(m^\pi\) variables ranging over positions within the path referenced by variable \(\pi\). Intuitively, each path variable \(\pi\) in WL is interpreted as a path \(\rho = v_0 \thinspace a_1 \dots a_i \thinspace v_i\) within the data graph \(G\). Each position variable \(\ell^\pi\) represents the position \(r \in [0, i]\) of a node along the path \(\rho\). Recall that \(v_r\) is the node at the position \(r\). Hence, the following WL formula captures that path \(\pi\) is simple: \[\phi_{\mathrm{\small simple} }(\pi):= \forall \ell^{\pi},m^{\pi}.\;\ell^{\pi} \neq m^{\pi} \rightarrow \neg(\ell^{\pi} \equiv_{\mathrm{\small id} } m^{\pi}),\] where \(\ell^{\pi} \equiv_{\mathrm{\small id} } m^{\pi}\) indicates that positions referenced by \(\ell^{\pi}\) and \(m^{\pi}\) point to the same node. A path \(\rho\) visits all nodes in a graph \(G\) if and only if for every path \(\rho'\) and a node \(n'\) in \(\rho'\), there exists a node \(n\) in \(\rho\) such that \(n\) is identical to \(n'\). Therefore, the subsequent WL formula verifies whether (2) is fulfilled: \[\phi_{\mathrm{\small visitall} }(\pi):= \forall \omega.\;\forall m^\omega.\;\exists \ell^\pi.\;\ell \equiv_{\mathrm{\small id} } m.\] Hence, formula \(\exists \pi.\;\phi_{\mathrm{\small simple} }(\pi) \wedge \phi_{\mathrm{\small visitall} }(\pi)\) expresses Hamiltonicity.

The syntax of WL assumes a countably infinite set \(\Pi\) of path variables, coupled with a set \(\Lambda\) of position variables indexed by path variables. A position variable \(\ell\) is of sort \(\pi\) and is usually denoted as \(\ell^\pi\) [4], [5], representing positions within the path \(\pi\). The \(\pi\) superscript is omitted when the context is clear.

Let \(\phi\) be a WL formula and \(\alpha\) be a mapping that assigns paths in \(G\) to path variables and node positions to position variables. Assume \(\alpha(\pi)=v_0 \thinspace a_1\dots a_i \thinspace v_i\), \(\alpha(\omega)=w_0 \thinspace b_1\dots b_{j} \thinspace w_{j}\), \(\alpha(\ell^\pi)=r, \alpha(m^\pi) = s \in [0,i]\), and \(\alpha(n^\omega) =t \in [0,j]\). We say \(G\) satisfies \(\phi\) under \(\alpha\), denoted by \((G,\alpha) \models \phi\), if one of the following holds:

1. \(\phi = E_a(\ell^\pi,m^\pi)\), \(s=r+1\), and \(a = a_s\).

2. \(\phi = \ell^\pi < m^\pi\) and \(r < s\).

3. \(\phi = \ell^\pi \equiv_{\mathrm{\small id} } n^\omega\) and \(\mathrm{\small id} (v_r)=\mathrm{\small id} (w_t)\).

4. \(\phi = \ell^\pi \equiv_{\mathrm{\small data} } n^\omega\) and \(\nodedata(v_r)=\nodedata(w_t)\).

5. \(\phi = \neg \psi\) and it is not the case that \((G, \alpha) \models \psi\).

6. \(\phi = \phi' \vee \phi''\) and we have \((G,\alpha) \models \phi'\) or \((G,\alpha) \models \phi''\).

7. \(\phi = \exists \ell^\pi. \psi\) and there is a node position \(r\) in \(\alpha(\pi)\) such that
   \((G, \alpha [\ell^\pi\mapsto r]) \models \psi\).

8. \(\phi = \exists \pi. \psi\) and there is a path \(\rho\) in \(G\) such that \((G,\alpha[\pi \mapsto \rho]) \models \psi\).

3.2 Querying graphs based on regular languages↩︎

The language discussed in the preceding section has limitations in expressing certain aspects of path label patterns. Consider the query: \[\begin{align} Q_{\boldsymbol{even}}:=&\textit{``Is there a node labelled a connected by a path of even length}\\ & \textit{to a node labelled b in graph G?''.} \end{align}\]

In WL the query cannot be expressed [4]. However, the set of paths satisfying this property can be described using a regular path query (RPQ). An RPQ comprises three elements: a source node \(v_s\), a target node \(v_t\), and a regular expression \(e\) (or an NFA \(A\)). A pair of nodes \((v_s, v_t)\) satisfies such a query if there exists a path from \(v_s\) to \(v_t\) with the label of \(\rho\) is in the language defined by \(e\), that is \(\mathbf{lb}(\rho)\in L(e)\).

Various extensions of regular path query languages have been introduced in the literature, initially for labelled graphs and later for graphs with data. For instance, conjunctive regular path queries, as in [3], allow conjunction as well as automata operating over vectors of paths. In contrast, [7] and [5] permit automata capable of detecting patterns involving data values.

We introduce a language that subsumes all languages in this paradigm, first order extended regular data path query language (FO(ERDPQ)).¹ We first describe the formalism informally. Regular languages are first expanded to languages defined by register automata.

Informally, when processing input symbols from an infinite alphabet, register automata compare symbols with register values, updating both registers and automaton state. The semantics are straightforward: see [18].

We now discuss register data path automata ( RDPAs ). These are modifications of register automata to accept data paths. First, the state space is partitioned into word states and data states. While in a word state, an RDPA\(A\) reads a symbol from \(\Sigma\) and transitions to a data state: there is no update and comparison with registers. In a data state, it reads an element from \(\mathcal{D}\), updates its registers, and reverts to a word state. The initial and final states are a data state and a word state, respectively. Transitions that are either of the form \(p \xrightarrow{a} q\), where \(p\) is a word state, \(q\) is a data state, and \(a \in \Sigma\), or \(r \xrightarrow{\boldsymbol{Pre}, \boldsymbol{Upd}} s\), where \(r\) is a data state and \(s\) is a word state, while \(\boldsymbol{Pre}\), the precondition, is a conjunction of equalities and inequalities among input data values, registers and constants. The update function \(\boldsymbol{Upd}\) is a conjunction of assignments of register values, input data values, or constants to registers.we allow the input alphabet to be a product space, and thus in \(\boldsymbol{Pre}\) and \(\boldsymbol{Upd}\) we can refer to the \(i^{th}\) input value. We can also fix infinite domains for each input value and register, and require \(\boldsymbol{Pre}\) and \(\boldsymbol{Upd}\) to be well-typed. Checking well-typedness – e.g. we only compare registers with the same domain – is straightforward. Thus in particular we will have certain registers that will only store ids, and we will assume that their domain is disjoint from the domains of other data values.

We now give the semantics more precisely. A data path automaton is simply an RDPA where the input words have components corresponding to \(\mathcal{D}_{\mathrm{\small id} }\) and \(\mathcal{D}_{\mathrm{\small prop} }\). Both the id and data domains contain a constant, denoted in each case by \(\sharp\) (“unset”), which can be assigned to id registers \(X_{\mathrm{\small id} }\) and \(\mathrm{\small data}\) registers \(X_{\mathrm{\small data} }\), respectively. The semantics of a data path automaton will assume that the initial value of each register is \(\sharp\). Assuming \(\mathcal{D}_{\mathrm{\small prop} }\) is a unary relation for simplicity, the data transitions will have a special shape, which we denote as \(r \xrightarrow{E,I,U} s\), where:

• \(r\) is a data state,

• \(s\) is a word state,

• \(E = (E_{\mathrm{\small id} }, E_{\mathrm{\small data} })\),

• \(I = (I_{\mathrm{\small id} }, I_{\mathrm{\small data} })\), and

• \(U = (U_{\mathrm{\small id} }, U_{\mathrm{\small data} })\).

Here:

• \(E_{\mathrm{\small id} }\) (“\(\mathrm{\small id}\) equality check registers”), \(I_{\mathrm{\small id} }\) (“\(\mathrm{\small id}\) inequality check registers”), and \(U_{\mathrm{\small id} }\) (“\(\mathrm{\small id}\) update registers”) are subsets of \(X_{\mathrm{\small id} }\),

• \(E_{\mathrm{\small data} }\), \(I_{\mathrm{\small data} }\), and \(U_{\mathrm{\small data} }\) are subsets of \(X_{\mathrm{\small data} }\).

We now give the semantics. Assuming \(\ell\) registers and a single variable domain \(\mathcal{U}\), a configuration of an RDPA\(A\) is a pair \((q,v)\) where \(q\) is a state, and \(v \in (\mathcal{U})^\ell\) is an \(\ell\)-tuple representing register content. A precondition corresponding to \(E\) and \(I\) above states that, when reading a symbol \((d_{\mathrm{\small id} }, d_{\mathrm{\small data} })\), we have

• \(v[i]=d_{\mathrm{\small id} }\) for each \(i\) in \(E_{\mathrm{\small id} }\),

• \(v[i]=d_{\mathrm{\small data} }\) for each \(i\) in \(E_{\mathrm{\small data} }\),

• \(v[i]\neq d_{\mathrm{\small id} }\) for each \(i\) in \(I_{\mathrm{\small id} }\)

• \(v[i]\neq d_{\mathrm{\small data} }\) for each \(i\) in \(I_{\mathrm{\small data} }\),

And the update corresponding to \(U\) above is:

• \(w[i]=d_{\mathrm{\small id} }\) for each \(i\) in \(U_{\mathrm{\small id} }\),

• \(w[i]=d_{\mathrm{\small data} }\) for each \(i\) in \(U_{\mathrm{\small data} }\),

• \(w[i]=v[i]\) for each \(i \not\in U_{\mathrm{\small id} }\cup U_{\mathrm{\small data} }\).

Given two configurations \((p,v), (q,w)\) and a transition \(\delta\), we write \((p,v) \linebreak \xrightarrow{(d_{\mathrm{\small id} }, d_{\mathrm{\small data} })}_\delta (q,w)\) if the precondition and update function are respected. \((q,v)\) is designated as the initial configuration if \(q\) is the initial state and \(v = (\sharp, \dots, \sharp)\). Similarly, \((q,v)\) is a final configuration if \(q\) is a final state. A sequence of configurations \(s=c_0 \dots c_n\) is a computation on a data path \(u=a_1 \dots a_n\) if there exists a sequence of transitions \(\delta_1 \dots \delta_n\) such that \(c_{i-1} \xrightarrow{a_i}_{\delta_i} c_i\) for each \(i \in [n]\). If \(c_0\) is the initial configuration and \(c_n\) is a final configuration, then \(s\) is an accepting computation, and \(u\) is accepted by \(A\). The language of regular data paths recognized by \(A\), denoted as \(L(A)\), comprises data paths \(u\) accepted by \(A\). Along the computation \(s\), we say register \(x_i\) is written at the \(j^{th}\) step where configuration \(c_j=(q_j,v_j)\) for \(1 \leq j \leq n\) if \(v_{j-1}[i]=\sharp\) and \(v_j[i]\neq \sharp\). Note that we can use states to keep track of which registers were written at the previous states, and whether the current content is \(\sharp\).

See Figure 4. The RDPA\(A\) has one register \(x \in X_\mathrm{\small data}\) and four states \(q_0, \dots, q_3\), where \(q_0\) is the initial state, and \(q_3\) is a final state. While reading a data path \(d_0 ~ a ~ d_1 \dots a ~ d_n\), it first stores the data value \(d_0\) (excluding its id) in the register \(x\) and transitions from state \(q_0\) to \(q_1\). At state \(q_2\), for each \(i \in [1,n]\), when reading the data value \(d_i\) (excluding its id), it checks whether the value is identical to the content of the register. If the values match, it transitions to the final state \(q_3\) and accepts the data path.

An \(n\)-ary RDPA\(A\) is an RDPA over an \(n\)-ary product alphabet. Let \(u_1,\dots, u_n\) be \(n\) data paths, where \(u_i=(d^{\mathrm{\small id} ,(i)}_0,d^{\mathrm{\small data} ,(i)}_0) \thinspace a^{(i)}_1\dots (d^{\mathrm{\small id} ,(i)}_{j_i},d^{\mathrm{\small data} ,(i)}_{j_i})\) for \(1\leq i \leq n\) and some \(j_1,\dots,j_n \in \mathbb{N}\). The convolution of \(u_1,\dots, u_n\) is an \(n\)-ary data path \(d_0a_1\dots d_m\), where:

• \(m = \max\{j_1,\dots,j_n\}\),

• \(a_j=(b_1,\dots,b_n)\) where \(b_i=a^{(i)}_j\) if \(j \leq j_i\); otherwise, \(b_i=\sharp\) for \(1 \leq i \leq n\) and \(1 \leq j \leq m\),

• \(d_j=(e^{\mathrm{\small id} }_1,\dots,e^{\mathrm{\small id} }_n,e^{\mathrm{\small data} }_1,\dots,e^{\mathrm{\small data} }_n)\) where \(e^{\mathrm{\small id} }_i=d^{\mathrm{\small id} ,(i)}_j\) and \(e^{\mathrm{\small data} }_i=d^{\mathrm{\small data} ,(i)}_j\) if \(j \leq j_i\); otherwise \(e^{\mathrm{\small id} }_i=e^{\mathrm{\small data} }_i=\sharp\) for \(1 \leq i \leq n\) and \(1 \leq j \leq m\).

The convolution of \(u_1, \dots, u_n\) converts the \(n\)-tuple of data paths into a single data path of tuples. This resulting data path is as long as the longest data path among \(u_1, \dots, u_n\) and is padded with \(\sharp\)’s for shorter paths. We say \((u_1,\dots, u_n)\) is accepted by \(A\) if their convolution is accepted by \(A\).

With this foundation, we proceed to define FO(ERDPQ).

A query in FO(ERDPQ) is referred to as a first order regular data path query (FO(RDPQ)) ² if all RDPAs in the query are unary. An FO(RDPQ) query is called a regular data path query (RDPQ) if it is of the form: \[\exists\pi.(x,\pi,y) \wedge \pi \in A.\] The semantics of FO(ERDPQ) is standard.

Let \(\phi\) be an FO(ERDPQ) formula, \(G\) a data graph, and \(\alpha\) be a mapping that assigns paths in \(G\) to path variables and nodes to node variables. We say that \(G\) satisfies \(\phi\) under \(\alpha\), denoted by \((G,\alpha) \models \phi\), if one of the following holds:

• \(\phi: \pi = \omega\) and \(\alpha(\pi) = \alpha(\omega)\).

• \(\phi: x=y\) and \(\alpha(x) = \alpha(y)\).

• \(\phi: (x,\pi,y)\) and \(\alpha(\pi)\) is a path from \(\alpha(x)\) to \(\alpha(y)\) in \(G\).

• \(\phi: (\pi_1,\dots,\pi_n) \in A\) and \((\mathbf{dp}(\alpha(\pi_1)), \dots, \mathbf{dp}(\alpha(\pi_n)))\) is in the \(n\)-ary relation of data paths defined by \(A\).

• \(\phi: \neg \psi\) and \(G\) does not satisfy \(\psi\) under \(\alpha\).

• \(\phi: \phi' \wedge \phi''\) and we have \((G,\alpha) \models \phi'\) and \((G,\alpha) \models \phi''\).

• \(\phi: \exists x. \psi\) and there is a node \(r\) in \(G\) such that \((G, \alpha [x\mapsto r]) \models \psi\).

• \(\phi: \exists \pi. \psi\) and there is a path \(\rho\) in \(G\) such that \((G,\alpha[\pi \mapsto \rho]) \models \psi\).

Obviously, \(Q_{\boldsymbol{even}}\) is expressible in FO(ERDPQ). It corresponds to formula \(\phi_{\boldsymbol{even}}(x,y):= \exists \pi. (x,\pi,y) \wedge \pi \in A_{\boldsymbol{even}}\), where \(A_{\boldsymbol{even}}\) recognizes the set of data paths of even length. Moreover, since ids are included as a part of data values, Hamiltonicity is expressible in FO(ERDPQ), as we show in the following example:

Graph pattern calculus (GPC). GPC is another query language based on regular expressions, designed for working with graphs containing data [14]. As discussed in the introduction, we make some simplifications to the language proposed in the standard, related to inverses and trails. We return to these simplifications in Section 7.

The most foundational GPC query takes the form \(\mathfrak{t}\;\mathfrak{p}\), where \(\mathfrak{t}\) is referred to as a restrictor, and \(\mathfrak{p}\) is called a pattern. Informally, a pattern can describe the label pattern of a path, which can be represented equivalently as a regular expression. It can also perform equality tests on data values of two nodes. A restrictor can constrain paths to have non-repeating vertices, and can also enforce the paths to be the shortest among the valid paths. The forms of a restrictor \(\mathfrak{t}\) are as follows:

• Restrictor: \(\mathfrak{t}::= \mathrm{\small simple} ~ | ~ \mathrm{\small shortest} ~| ~ \mathrm{\small shortestsimple}\)

Atomic GPC patterns are either:

• Node patterns: \(()\) and \((x)\); or

• Edge patterns: \(\rightarrow\) and \(\xrightarrow{a}\).

Here, \(x\) represents a node variable, and \(a \in \Sigma\).

We now give inductive rules for forming patterns, assuming two patterns \(\mathfrak{p}\) and \(\mathfrak{p}'\). We close under:

• Union: \(\mathfrak{p}+ \mathfrak{p}'\),

• Concatenation: \(\mathfrak{p}\mathfrak{p}'\),

• Repetition: \(\mathfrak{p}^{n..m}\), where \(n\) and \(m\) can take values in \(\mathbb{N}\cup\{\infty\}\).

• Conditioning: \(\mathfrak{p}_{\langle \theta \rangle}\), where \(\theta\) is a condition.

Conditions are defined as:

• Condition: \(\theta::= x \equiv_{\mathrm{\small data} } y \mid \neg\theta \mid \theta \wedge \theta\)

where \(x\) and \(y\) are node variables.

In [14], GPC is accompanied by a type system that imposes certain restrictions. Here, we consider the notion of free variables, as introduced in [19]. Given a pattern \(\mathfrak{p}\), a node variable \(x\) in \(\mathfrak{p}\) is bounded if it appears within a repetition sub-pattern \(\mathfrak{q}\); otherwise, \(x\) is free. An important restriction on the syntax is:

If a variable \(x\) is used in the repetition sub-pattern \(\mathfrak{q}\) of \(\mathfrak{p}\), it cannot appear anywhere else in \(\mathfrak{p}\) except within \(\mathfrak{q}\)

We use \(\mathrm{\small FV}(\mathfrak{p})\) to denote the set of free variables in the pattern \(\mathfrak{p}\). ³

Let \(G = (V, E, \mathrm{\small id} , \nodedata)\) be a data graph, and let \(\mathfrak{p}\) and \(\mathfrak{p}'\) be two GPC patterns. For any two mappings \(\mu: \mathrm{\small FV}(\mathfrak{p}) \to V \cup \{\sharp\}\) and \(\mu': \mathrm{\small FV}(\mathfrak{p}') \to V \cup \{\sharp\}\), the union \(\mu \cup \mu': \mathrm{\small FV}(\mathfrak{p}) \cup \mathrm{\small FV}(\mathfrak{p}') \to V \cup \{\sharp\}\) is defined if, for all \(x \in \mathrm{\small FV}(\mathfrak{p}) \cap \mathrm{\small FV}(\mathfrak{p}')\), it holds that \(\mu(x) = \mu'(x)\) whenever both \(\mu(x) \neq \sharp\) and \(\mu'(x) \neq \sharp\), where \(\sharp\) refers to a null value. If \(\mu \cup \mu'\) is defined, then it maps each \(x\) to:

• \(\mu(x)\) if \(\mu(x) \neq \sharp\) or \(x \not\in \mathrm{\small FV}(\mathfrak{p}')\);

• \(\mu'(x)\) if \(\mu'(x) \neq \sharp\) or \(x \not\in \mathrm{\small FV}(\mathfrak{p})\);

• \(\sharp\) if \(\mu(x) = \mu'(x) = \sharp\).

Given a condition \(\theta\) and a mapping \(\mu: \mathrm{\small FV}(\mathfrak{p}) \to V\), \(\mu \models \theta\) is defined recursively as follows:

• \(\mu \models x \equiv_{\mathrm{\small data} } y\) if \(\nodedata(\mu(x)) = \nodedata(\mu(y))\).

• \(\mu \models \neg \theta\) if \(\mu \not\models \theta\).

• \(\mu \models \theta \wedge \theta'\) if \(\mu \models \theta\) and \(\mu \models \theta'\).

Now, we are ready to define the semantics of GPC queries. Let \(\mathfrak{p}\) be a GPC pattern, and let \(G = (V, E, \mathrm{\small id} , \nodedata)\) be a data graph over \(\Sigma\). The semantics of \(\mathfrak{p}\) in \(G\), denoted \([\![{\mathfrak{p}}]\!]_{G}\), is a set of pairs \((\rho, \mu)\), where \(\rho\) is a path and \(\mu\) is a mapping from \(\mathrm{\small FV}(\mathfrak{p})\) to \(V\). The semantics is defined recursively as follows:

• \([\![{(x)}]\!]_{G} = \{(v, \{x \mapsto v\}) \mid v \in V\}\). Recall that \(v\) is a path of length zero in \(G\) if \(v \in V\).

• \([\![{()}]\!]_{G} = \{(v, \emptyset) \mid v \in V\}\).

• \([\![{\xrightarrow{a}}]\!]_{G} = \{(v \thinspace a \thinspace v', \emptyset) \mid (v, a, v') \in E\}\) for \(a \in \Sigma\). Recall that \(v \thinspace a \thinspace v'\) is a path of length one in \(G\) if \((v, a, v') \in E\).

• \([\![{\rightarrow}]\!]_{G} = \{(v \thinspace a \thinspace v', \emptyset) \mid (v, a, v') \in E\}\).

• \([\![{\mathfrak{p}+ \mathfrak{p}'}]\!]_{G} = \{(\rho, \mu') \mid (\rho, \mu) \in [\![{\mathfrak{p}}]\!]_{G}\) or \((\rho, \mu) \in [\![{\mathfrak{p}'}]\!]_{G}\}\), where \(\mu'\) is a mapping from \(\mathrm{\small FV}(\mathfrak{p}) \cup \mathrm{\small FV}(\mathfrak{p}')\) defined as follows:

  • \(\mu'(x) = \mu(x)\) if \(x\) is in the domain of \(\mu\);

  • \(\mu'(x) = \sharp\) otherwise.

  For example, suppose \(\mathrm{\small FV}(\mathfrak{p})=\{x,y\}\) and \(\mathrm{\small FV}(\mathfrak{p}')=\{y,z\}\). Then, we have \(\mathrm{\small FV}(\mathfrak{p}+ \mathfrak{p}') = \{x,y,z\}\). Additionally, if \((\rho,\mu) \in [\![{\mathfrak{p}'}]\!]_{G}\) with \(\mu(y)=v\) and \(\mu(z)=w\), then we have \((\rho,\mu') \in [\![{\mathfrak{p}\mathfrak{p}'}]\!]_{G}\), where:

  • \(\mu'(x) = \sharp\),

  • \(\mu'(y) = v\),

  • \(\mu'(z) = w\).

• \([\![{\mathfrak{p}\mathfrak{p}'}]\!]_{G} = \{(\rho \cdot \rho', \mu \cup \mu') \mid (\rho, \mu) \in [\![{\mathfrak{p}}]\!]_{G}, (\rho', \mu') \in [\![{\mathfrak{p}'}]\!]_{G}\text{, and the union } \mu\cup\mu' \text{ is defined}\}\).

• \([\![{\mathfrak{p}^{n..m}}]\!]_{G} = \bigcup_{i=n}^m [\![{\mathfrak{p}}]\!]_{G}^i\), where:

  • \([\![{\mathfrak{p}}]\!]_{G}^0 = [\![{()}]\!]_{G}\).

  • \([\![{\mathfrak{p}}]\!]_{G}^\ell = \{(\rho_1 \cdots \rho_\ell, \emptyset) \mid \exists \mu_1, \dots, \mu_\ell. \, (\rho_1, \mu_1), \dots, (\rho_\ell, \mu_\ell) \in [\![{\mathfrak{p}}]\!]_{G}\}\) for \(\ell \geq 1\).

• \([\![{\mathfrak{p}_{\langle \theta \rangle}}]\!]_{G} = \{(\rho, \mu) \mid (\rho,\mu) \in [\![{\mathfrak{p}}]\!]_{G} \text{ and }\mu \models \theta\}\).

Given a GPC pattern \(\mathfrak{p}\) and a restrictor \(\mathfrak{t}\), the semantics \([\![{\mathfrak{t}\;\mathfrak{p}}]\!]_{G}\) is defined recursively as follows:

• \(\{(\rho, \mu) \mid (\rho, \mu) \in [\![{\mathfrak{p}}]\!]_{G} \rho \text{ is simple}\}\) if \(\mathfrak{t}= \mathrm{\small simple}\).

• \(\{(\rho, \mu) \mid (\rho, \mu) \in [\![{\mathfrak{p}}]\!]_{G} ~ \rho \text{ shortest among paths } \rho' with (\rho', \mu') \in [\![{\mathfrak{p}}]\!]_{G} \\ and \rho' has the same endpoints as \rho \}\) if \(\mathfrak{t}= \mathrm{\small shortest}\).

• \(\{(\rho, \mu) \mid (\rho, \mu) \in [\![{\mathfrak{p}}]\!]_{G}, \rho \text{ is simple, and } |\rho| = \min \{ |\rho'| \mid (\rho', \mu') \in [\![{\mathfrak{p}}]\!]_{G},\linebreak \rho' \text{ is simple and has the same endpoints as } \rho \}\) if \(\mathfrak{t}=\mathrm{\small shortestsimple}\).

 

• \([\![{Q, Q'}]\!]_{G} = \{((\bar{\rho}, \bar{\rho}'), \mu \cup \mu') \mid (\bar{\rho}, \mu) \in [\![{Q}]\!]_{G}, (\bar{\rho}', \mu') \in [\![{Q'}]\!]_{G} \text{, and the union }\linebreak \mu\cup\mu' \text{ is defined}\}\).

We omit the subscript \(G\) when it is clear from the context. We adapt GPC queries to support graph queries in the obvious way: a non-empty data graph \(G\) satisfies a GPC query \(Q\) if \([\![{Q}]\!]_{G}\) is non-empty. For simplicity, we also say that a path \(\rho\) in \(G\) is in the semantics of \(Q\), denoted as \(\rho \in [\![{Q}]\!]_{G}\), if \((\rho, \mu) \in [\![{Q}]\!]_{G}\). We also say that a path \(\rho\) satisfies \(\mathfrak{p}\), if there exists a mapping \(\mu\) such that \((\rho,\mu) \in [\![{\mathfrak{p}}]\!]_{G}\).

We end this subsection with two examples. Consider the following GPC pattern over \(\Sigma=\{a,b\}\): \[\mathfrak{p}= (x) \xrightarrow{a} () \left[ \left[\xrightarrow{b}\xrightarrow{b}\xrightarrow{b}\right]^{1..\infty} + \left[[(y) \rightarrow^{3..7} (z)]_{y\equiv_{\mathrm{\small data} } z}\right]^{1..1} \right] () \xrightarrow{b} (x).\] Since variables \(y\) and \(z\) are used in a repetition sub-pattern, we have \(\mathrm{\small FV}(\mathfrak{p}) = \{x\}\). Pattern \(\mathfrak{p}\) refers to the set of paths \(\rho = v_0 ~ a_1 ~ v_1 \dots a_n ~ v_n\), where:

• \(v_0 = v_n\) where \(n>2\),

• \(a_1 = a\) and \(a_n = b\), and

• at least one of the following holds:

  (a) \(n-2\) is divisible by \(3\) and \(a_i = b\) for \(2\leq i \leq n-1\);

  (b) \(3\leq n-2 \leq 7\) and \(\mathrm{\small dataof} (v_1) = \mathrm{\small dataof} (v_{n-1})\).

See the data graph \(G\) in Figure 5. Let \(\mu\) be a mapping with \(\mu(x)=n_3\). By definition, we have \([\![{\mathfrak{p}}]\!]_{G}\) as the union of the following two sets:

1. \(P_1 = \{(n_3 ~ a ~ (n_4 ~ b ~ n_5 ~ b ~ n_6 ~ b ~ n_7~ b)^i ~ n_3, \mu) \mid 4i-1 \text{ is divisible by 3 and } i\geq 1\}\).

2. \(P_2 = \{(n_3 ~ a ~ n_1 ~ (a ~ n_2 ~ a ~n_1)^i ~ a ~ n_2 ~ b ~ n_3, \mu) \mid i=2,\dots, 6\}\).

Moreover, we find that \([\![{\mathfrak{t}\;\mathfrak{p}}]\!]_{G}\) is as follows:

• When \(\mathfrak{t}= \mathrm{\small simple} , \mathrm{\small shortestsimple}\), \([\![{\mathfrak{t}\;\mathfrak{p}}]\!]_{G}\) is empty, as there is no simple path in \(G\) matching pattern \(\mathfrak{p}\).

• When \(\mathfrak{t}= \mathrm{\small shortest}\), \([\![{\mathfrak{t}\;\mathfrak{p}}]\!]_{G} = \{(\rho,\mu) \mid \rho \text{ is a shortest path in } P_1\cup P_2\}\).

Finally, consider the following GPC pattern over \(\Sigma=\{a,b\}\): \[\mathfrak{q}=\;\xrightarrow{b}\xrightarrow{b}.\] Given the same data graph \(G\) in Figure 5, we have: \[[\![{\mathfrak{q}}]\!]_{G} = \{n_4~ b ~ n_5~ b ~ n_6, n_5 ~ b ~ n_6 ~ b ~ n_6, n_6 ~ b ~ n_7 ~ b ~ n_4, n_6 ~ b ~ n_7 ~ b ~ n_3, n_7 ~ b ~ n_4 ~ b ~ n_5\}.\] Since all paths in \([\![{\mathfrak{q}}]\!]_{G}\) are simple and have the same length, we have \([\![{\mathfrak{t}\;\mathfrak{q}}]\!]_{G}=[\![{\mathfrak{q}}]\!]_{G}\) for any restrictor \(\mathfrak{t}\).

3.3 Graph querying based on FO\(^*\)↩︎

Another category of languages revolves around first-order logic with only node variables. Instead of relying on operations rooted in automata or regular languages, these languages utilize a transitive closure operator.

A data graph \(G=(V,E, \mathrm{\small id} , \nodedata)\) over \(\Sigma\) can be viewed as a first-order structure \(\langle V, \{E_a\}_{a \in \Sigma}, \equiv_{\mathrm{\small data} }\rangle\). First-order logic over this structure is denoted as FO\((\equiv_{\mathrm{\small data} })\). In this structure, the set \(V\) of nodes forms the universe, \(E_a\) is interpreted as \(\{(v,v') \in V^2 \mid (v,a,v')\in E\}\), and \(\equiv_{\mathrm{\small data} }\) is interpreted as \(\{(v,v') \mid \nodedata(v)=\nodedata(v')\}\).

We extend FO\((\equiv_{\mathrm{\small data} })\) by introducing a transitive closure constructor. If \(\phi(\mathbf{x},\mathbf{y})\) is a formula, then \(\phi^*(\mathbf{x}, \mathbf{y})\) becomes a formula, where \(\mathbf{x}\) and \(\mathbf{y}\) represent two vectors of node variables of the same arity. The interpretation is such that \(G, \rho \models \phi^*(\mathbf{x}, \mathbf{y})\) for a data graph \(G\) and a valuation \(\rho\), if there exists a sequence of node vectors \(\mathbf{x}_1=\rho(\mathbf{x}), \mathbf{x}_2, \ldots, \mathbf{x}_n=\rho(\mathbf{y})\) satisfying the condition that for each \(1 \leq i < n\), \(G, \rho \models \phi(\mathbf{x}_i, \mathbf{x}_{i+1})\). ⁴ We denote the extension of FO\((\equiv_{\mathrm{\small data} })\) with transitive closures as FO\(^*(\equiv_{\mathrm{\small data} })\). In contrast to other languages that rely on transitive closure of edge relations,
FO\(^*(\equiv_{\mathrm{\small data} })\) permits the transitive closure of any definable relationship, not just the closure of the edge relation.

Within this paradigm, one prominent language family is GXPath, originating from query languages for graph databases initially introduced in [2], inspired by the XML query language XPath. Within this family,
GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) is the most powerful variant: [2] shows that it is equivalent to (FO\(^*_{3}\))\((\equiv_{\mathrm{\small data} })\), a restriction of FO\(^*(\equiv_{\mathrm{\small data} })\) allowing only formulas in which every subformula has at most three free variables, and the closure \(\phi^*\) of \(\phi(\mathbf{x},\mathbf{y})\) is allowed only if \(\mathbf{x}\) and \(\mathbf{y}\) have the same arity. Lastly, it is worth mentioning regular queries (RQ) [21], a query language for graphs without data, which extends unions of conjunctive 2-way regular path queries (UC2RPQ) by adding transitive closure. RQ can be defined as the closure of atomic queries under selection, projection, disjunction, conjunction, and transitive closure. By adding \(x \equiv_{\mathrm{\small data} } y\) to the set of atomic queries, RQ can be extended to handle graphs with data.

4 Expressiveness of existing languages↩︎

The languages discussed in Section 3 are illustrated in Figure 1. This section will be devoted to proving the following theorem, which justifies Figure 1:

It is straightforward, just chasing the definitions, to observe that RDPQ\(\subseteq\) FO(RDPQ)\(\subseteq\) FO(ERDPQ). To complete the proof, we still have to show:

(1) FO(ERDPQ) subsumes GPC.

(2) FO(ERDPQ) subsumes WL.

(3) FO\(^*(\equiv_{\mathrm{\small data} })\) subsumes RDPQ.

We will show the first and third item here. The proof of the middle item will be deferred to Section 6.

4.1 FO(ERDPQ) subsumption of GPC↩︎

We define a fragment of FO(ERDPQ) with lower data complexity which still subsumes GPC. The motivation is that there exists a substantial complexity gap between GPC and FO(ERDPQ). The data complexity of query evaluation for GPC is within PSPACE[14], whereas for FO(ERDPQ), it is non-elementary [3]. Our objective is to bridge this gap by introducing the fragment \(\forall\)(ERDPQ) of FO(ERDPQ), in which only universal quantifiers are allowed. The expressiveness of this fragment relative to others is depicted in Figure 6.

Formalizing the syntax, a \(\forall\)(ERDPQ) formula takes the form: \[\forall \bar{\omega}. \psi(\bar{\pi},\bar{\omega}),\] where \(\psi\) is a quantifier-free FO(ERDPQ) formula. We will demonstrate that this fragment contains GPC.

4.2 The data complexity of \(\forall\)(ERDPQ)↩︎

In the previous subsection, we introduced a fragment \(\forall\)(ERDPQ) of
FO(ERDPQ), which has no elementary bound on the data complexity, and showed that GPC is subsumed by \(\forall\)(ERDPQ). Additionally, we asserted that \(\forall\)(ERDPQ) has significantly lower data complexity than FO(ERDPQ), within PSPACE in terms of the size of the data graph \(G\) w.r.t. the standard encoding, which is basically polynomial in the number of the nodes and the number of edge labels. From this, we could conclude that \(\forall\)(ERDPQ) is strictly less expressive than FO(ERDPQ). We will now substantiate this data complexity claim.

Each quantifier-free FO(ERDPQ) formula \(\psi\) is a Boolean combination of atoms of the form \(\bar{\pi} \in A\) or \(\bar{\pi} \not\in A\). To check that a universally-quantified sentence does not hold on a given graph, we can negate it as an existentially-quantified Boolean combination, and then guess a conjunction of atoms of the above form that witness satisfiability.

Thus to show that \(\forall\)(ERDPQ) query evaluation is in PSPACE, it suffices to give a PSPACE algorithm for checking satisfiability of formulas: \[\label{eq:normal95form} \exists \bar{\omega}. \bigwedge_i \bar{\omega} \in A_i \wedge \bigwedge_j \neg \bar{\omega} \in B_j. \tag{1}\] Since we are concerned with data complexity, the sizes of the \(\forall\)(ERDPQ) formulas are treated as constants. Specifically, the number of variables, the number of RDPAs \(A_i\) and \(B_j\), the number of conjunctions, and the sizes of \(A_i\) and \(B_j\) are all considered constant, where the size of an RDPA refers to the number of states, transitions, and registers.

Combining the reduction to satisfiability of sentences of the form (Eq. 1 ), we have shown that \(\forall\)(ERDPQ) has much lower complexity than FO(ERDPQ):

4.3 RDPQ to FO\(^*(\equiv_{\mathrm{\small data} })\)↩︎

To show the inclusion of RDPQ in FO\(^*(\equiv_{\mathrm{\small data} })\), for every RDPA\(A\) we will construct an FO\(^*(\equiv_{\mathrm{\small data} })\) formula \(\phi_A\) simulating the computation of \(A\). Without loss of generality, assume \(A\) is a unary RDPA over \(\Sigma=\{a,b\}\) and it has \(n=2^t\) states for some positive integer \(t\). Similar to the translation of an \(n\)-ary NFA to an FO\(^*\) formula for arbitrary \(n\), the translation from an \(n\)-ary RDPA\(A\) to \(\phi_A\) follows a process analogous to the 1-ary case. First, let’s explore a simplified scenario of using an FO\(^*\) formula to emulate the computation of an NFA.

Let \(G\) be a graph with only ids as data, containing at least two nodes \(v\) and \(w\). Let \(A\) be an NFA. We can assume \(Q=\{\boldsymbol{r}_1,\dots,\boldsymbol{r}_n\}\), where each \(\boldsymbol{r}_i\) is a \(t\)-tuple over \(\{v,w\}\). We do this by taking \(t\) large enough so that the size of \(Q\) is at most \(2^t\). Since \(Q\) is finite, we can define first-order formulas \(\phi^{\boldsymbol{tran}}_a\) and \(\phi^{\boldsymbol{tran}}_b\) such that (i) \(\phi^{\boldsymbol{tran}}_a(\boldsymbol{r}_i,\boldsymbol{r}_j)\) holds if and only if \((\boldsymbol{r}_i,a,\boldsymbol{r}_j)\) is a transition in \(A\) for \(i,j \in [n]\) and (ii) \(\phi^{\boldsymbol{tran}}_b(\boldsymbol{r}_i,\boldsymbol{r}_j)\) holds if and only if \((\boldsymbol{r}_i,b,\boldsymbol{r}_j)\) is a transition in \(A\) for \(i,j \in [n]\).

For any path \(\rho\) in \(G\), with label \(\mathbf{lb}(\rho)=a_1\dots a_m \in L(A)\), there exist sequences of states \(p_0 \dots p_m\) and nodes \(v_0 \dots v_m\) in \(G\) such that \(p_0\) is the initial state, \(p_m\) is a final state, \((p_{i-1},a_i,p_i)\) is a transition in \(A\), and \((v_{i-1},a_i,v_i)\) forms an edge in \(G\) for \(i\in [m]\). We can define: \[\psi^{\boldsymbol{tran}}_?(\boldsymbol{z},\boldsymbol{z}'):= \phi^{\boldsymbol{tran}}_?(\boldsymbol{x},\boldsymbol{x}') \wedge E_?(y,y'),\] where \(\boldsymbol{z}=(\boldsymbol{x},y)\) and \(\boldsymbol{z}'=(\boldsymbol{x}',y')\) have the same arity, for \(?=a,b\) and \[\psi_{\boldsymbol{tran}} := \psi^{\boldsymbol{tran}}_a \vee \psi^{\boldsymbol{tran}}_b.\] Thus \(\mathbf{lb}(\rho) \in L(A)\) if and only if \(\psi^*_{\boldsymbol{tran}}(\boldsymbol{r},\boldsymbol{s})\) holds where \(\boldsymbol{r}=(\boldsymbol{r}_i,r)\), \(\boldsymbol{s}=(\boldsymbol{r}_j,s)\), \(\boldsymbol{r}_i\) is the initial state, \(\boldsymbol{r}_j\) is a final state, and \(\rho\) goes from node \(r\) to node \(s\).

Now, let’s consider the general case where \(A\) is an RDPA and \(G\) is a data graph. Suppose that \(A\) has registers \(\{1, \dots, \ell\}\) and \(u = d_1 \thinspace d_2 \dots d_m\) is a data path in \(G\). The data path \(u\) is accepted by \(A\) if there exists a sequence of accepting configurations \(c_0 \thinspace c_1 \dots c_m\) and a sequence of transitions \(\delta_1 \dots \delta_m\) such that \(c_{i-1} \xrightarrow{d_i}_{\delta_i} c_i\) for each \(i \in [m]\). Assume \(X_{\mathrm{\small id} }=\{1,\dots,\eta-1\}\) and \(X_{\mathrm{\small data} }=\{\eta,\dots,\ell\}\) for some index \(\eta\). A configuration of \(A\) takes the form \((q,r_1,\dots,r_\ell)\), where \(q\) is an \(A\)-state, \(r_i=\mathrm{\small id} (v_j)\) if \(i < \eta\), and \(r_i=\nodedata(v_j)\) if \(i\geq \eta\) for some \(v_j\) in \(G\). The value of \(r_i\) is uniquely determined once \(v_j\) is known. Thus \(u\) is accepted by \(A\) if and only if there exists a sequence \(\alpha_0 \dots \alpha_m\), where \(\alpha_i = (q_i,v^{(i)}_1,\dots,v^{(i)}_\ell)\) for some \(A\)-state \(q_i\) and \(G\)-nodes \(v^{(i)}_1,\dots,v^{(i)}_\ell\) such that \(c_i = (q_i,\mathrm{\small id} (v^{(i)}_1),\dots,\mathrm{\small id} (v^{(i)}_{\eta-1}),\nodedata(v^{(i)}_\eta),\dots,\nodedata(v^{(i)}_\ell))\) for \(i \in [m]\).

In the case of NFA emulation, we utilized tuples \(\boldsymbol{r}\) of nodes to carry the state information of the automaton. Likewise, for RDPAs, we can also employ tuples of nodes to carry \(\alpha_0, \dots, \alpha_m\) around. Recall that there are two kinds of transitions in \(A\): word transitions of the form \(\delta_w = p \xrightarrow{a} q\) and data transitions of the form \(\delta_d = r \xrightarrow{E,I,U} s\). When \(\delta_w\) is applied, the content of the registers is not modified. Therefore the RDPA-version formula \(\psi^{\boldsymbol{tran}}_{\delta_w}(\boldsymbol{x}, y, \boldsymbol{z}, \boldsymbol{x}', y', \boldsymbol{z}')\) corresponding to \(\delta_w\) can be defined as: \[\begin{align} \phi^{\boldsymbol{tran}}_a(\boldsymbol{x}, \boldsymbol{x}') \wedge E_a(y, y') \wedge \left(\bigwedge_{1 \leq i < \eta} (z_i = z'_i)\right) \wedge \left(\bigwedge_{\eta \leq i \leq \ell} (z_i \equiv_{\mathrm{\small id} } z'_i)\right). \end{align}\] When \(\delta_{\delta_d}\) is applied, the values of the registers are compared with the data value of a node and updated. We can define the RDPA-version formula \(\psi^{\boldsymbol{tran}}_d\) corresponding to \(\delta_d\) as follows: \[\psi^{\boldsymbol{tran}}_{\delta_d}(\boldsymbol{x}, y, \boldsymbol{z}, \boldsymbol{x}', y', \boldsymbol{z}', w) := \phi^{\boldsymbol{tran}}_d(\boldsymbol{x}, \boldsymbol{x}') \wedge \phi_{E}(\boldsymbol{z}, w) \wedge \phi_I(\boldsymbol{z}, w) \wedge \phi_U(\boldsymbol{z}, \boldsymbol{z'}, w),\] where:

• \(\phi^{\boldsymbol{tran}}_d\) is the formula such that \(\phi^{\boldsymbol{tran}}_d(\boldsymbol{r}, \boldsymbol{s})\) holds if and only if \(\delta_d=r \xrightarrow{E, I, U} s\) is a data transition from \(r\) to \(s\), and states \(r, s\) correspond to tuples \(\boldsymbol{r}, \boldsymbol{s} \in Q\), respectively.

• \[\phi_E(\boldsymbol{z}, w) := \left(\bigwedge_{x_i \in E_{\mathrm{\small id} }} z_i = w\right) \wedge \left(\bigwedge_{x_i \in E_{\mathrm{\small data} }} z_i \equiv_{\mathrm{\small data} } w\right)\] states that the id of node \(w\) is identical to the values of registers in \(E_{\mathrm{\small id} }\) and the data value excluding the id of node \(w\) is identical to the values of registers in \(E_{\mathrm{\small data} }\).

• \[\phi_I(\boldsymbol{z}, w) := \left(\bigwedge_{x_i \in I_{\mathrm{\small id} }} \neg(z_i = w)\right) \wedge \left(\bigwedge_{x_i \in I_{\mathrm{\small data} }} \neg(z_i \equiv_{\mathrm{\small data} } w)\right)\] states that the id of node \(w\) is different from the values of registers in \(I_{\mathrm{\small id} }\) and the data value excluding the id of node \(w\) is different from the values of registers in \(I_{\mathrm{\small data} }\).

• \[\phi_U(\boldsymbol{z}, \boldsymbol{z}', w) := \left(\bigwedge_{x_i \not\in U} z'_i = z_i\right) \wedge \left(\bigwedge_{x_i \in U} z'_i = w\right)\] states how the registers are updated.

Finally, let \[\psi_{\boldsymbol{tran}}(\boldsymbol{x},y,\boldsymbol{z},v,\boldsymbol{x}',y',\boldsymbol{z}',v'):= \bigvee_{\delta\in\Delta} \psi^{\boldsymbol{tran}}_{\delta} \wedge \phi_{\delta}(v,v'),\] where \(\phi_\delta(v,v')\) holds if \(\delta\) is a data transition with \((v,v')=(w,u)\), or if \(\delta\) is a word transition with \((v,v')=(u,w)\). Thus, we have \(\mathbf{dp}(\rho) \in L(A)\) if and only if \(\psi^*_{\boldsymbol{tran}}(\boldsymbol{x},y,\boldsymbol{z},w,\boldsymbol{x}',y',\boldsymbol{z}',u)\) holds, where \(\boldsymbol{x}\) is the initial state, \(\boldsymbol{x}'\) is a final state, \(\boldsymbol{z}\) specifies that all registers hold the null value \(\sharp\), and \(\rho\) is a path from node \(y\) to node \(y'\). This completes the proof.

4.4 Strictness of the inclusions in Figure 1↩︎

Since GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) and (FO\(^*_{3}\))\((\equiv_{\mathrm{\small data} })\) share the same expressive power [2], GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) is subsumed by full transitive closure logic, as shown in Figure 1. The following result states that the subsumptions in the diagram are all strict.

Since the diagram includes numerous containments, for the sake of clarity, we will initially enumerate a set of properties that we intend to derive.

A. Every pair from the following set is incomparable: GPC, WL, FO(RDPQ), FO\(^*(\equiv_{\mathrm{\small data} })\) under the assumption that NL\(\neq\) NP.

B. GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) is not subsumed by FO(ERDPQ).

C. RDPQ is not subsumed by GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\), GPC, or WL.

The assumption NL\(\neq\) NP will be used only in the first item, and there it will be used to derive that GPC and FO(RDPQ) are not subsumed by FO\(^*(\equiv_{\mathrm{\small data} })\) and GPC is not subsumed by FO(RDPQ). In the previous section, we showed that RDPQ, a query language based on regular languages, is subsumed by FO\(^*(\equiv_{\mathrm{\small data} })\). However, we cannot extend this result to GPC, although GPC is also inspired by regular languages. That is, GPC is not subsumed by FO\(^*(\equiv_{\mathrm{\small data} })\), due to the usage of restrictors in GPC. Specifically, it is unclear whether the notion of “simple” can be expressed in FO\(^*(\equiv_{\mathrm{\small data} })\).

These properties are sufficient to obtain the following, which implies that no other containments are derivable:

A. FO\(^*(\equiv_{\mathrm{\small data} })\) and FO(ERDPQ) are incomparable.

B. GPC, WL, FO(RDPQ) are strictly subsumed by FO(ERDPQ).

C. RDPQ is strictly subsumed by FO(RDPQ) and FO\(^*(\equiv_{\mathrm{\small data} })\).

D. GPC, WL, RDPQ, and GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) are incomparable.

E. GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) is incomparable with FO(RDPQ) and FO(ERDPQ).

F. GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) is strictly subsumed by FO\(^*(\equiv_{\mathrm{\small data} })\).

We start with P.[prop:sublanguage95incomparable]. We begin by showing that FO\(^*(\equiv_{\mathrm{\small data} })\) is not subsumed in any of the other languages considered in P.[prop:sublanguage95incomparable]. To give intuition for the separating example, consider an encoding of an ordinary graph \(G\), with arbitrary connectivity, as a highly disconnected data graph \(G'\), where in \(G'\) each node is linked to only two other nodes. The translation is shown in Figure 7. The edge connection between nodes \(v_2\) and \(v_4\) in \(G\) is represented in \(G'\) as an \(\mathrm{\small OUT}\)-labelled edge to a node carrying a certain data value, then an \(\mathrm{\small IN}\)-edge from another node with the same data value to \(v_4\).

Based on this, we create our separating example. We formulate an FO formula \(\mathrm{\small DataLink} (x, y)\) such that a pair of nodes \(v\) and \(w\) in \(G'\) satisfies \(\mathrm{\small DataLink}\) if there exists a node \(s\) linked to \(v\) through an \(\mathrm{\small OUT}\) edge and another node \(f\) linked to \(w\) through an \(\mathrm{\small IN}\) edge, with the data value of \(s\) equating the data value of \(f\). For instance, \((v_1, v_4)\) satisfies \(\mathrm{\small DataLink}\), while \((v_3, v_5)\) does not. Accordingly, we can create an FO\(^*(\equiv_{\mathrm{\small data} })\) formula \(\mathrm{\small DataConnection} (x, y)\) representing the transitive closure of \(\mathrm{\small DataLink}\). Consequently, a pair of nodes \((v, w)\) in \(G'\) satisfies \(\mathrm{\small DataConnection}\) if \(v\) and \(w\) are connected in \(G\).

We now argue that this formula cannot be expressed in the other languages mentioned in P.[prop:sublanguage95incomparable], like FO(ERDPQ). To see this, consider the family of graphs similar to \(G'\) in Figure 7, and note that path lengths are confined to \(2\). Therefore, fixing a vocabulary with three relations \(P_0, P_1, P_2\) over nodes – where \(P_0\), \(P_1\), and \(P_2\) are unary, binary, and ternary, respectively – we can convert any FO(ERDPQ) formula \(f\) into a first-order logic formula without path variables. But connectivity cannot be expressed using first-order logic [22]. Consequently, FO(ERDPQ) does not subsume FO\(^*(\equiv_{\mathrm{\small data} })\), and thus FO\(^*(\equiv_{\mathrm{\small data} })\) is not subsumed by any of the other three languages.

It is known that there is no elementary bound on the data complexity for WL, even for graphs with only ids as data [5]. But FO\(^*(\equiv_{\mathrm{\small data} })\), GPC, and FO(RDPQ) do have elementary bounds on data complexity, with FO\(^*(\equiv_{\mathrm{\small data} })\) having a NL bound [23]. Consequently, these languages cannot subsume WL.

What remains in P.[prop:sublanguage95incomparable] is to show that GPC and FO(RDPQ) cannot be subsumed by WL, by FO\(^*(\equiv_{\mathrm{\small data} })\), or by each other. It is known [24] that GPC can express NP-hard queries (in particular, \(Q_{\boldsymbol{even}}\)).

We now argue that FO(RDPQ) are both NP-hard in data complexity. Since FO\(^*(\equiv_{\mathrm{\small data} })\) is in NL, this will imply that FO\(^*(\equiv_{\mathrm{\small data} })\) cannot subsume either of these languages, assuming NP is not equal to NL.

While GPC and FO(RDPQ), which are based on regular languages, can express the query \(Q_{\boldsymbol{even}}\), we know from [4] that \(Q_{\boldsymbol{even}}\) is not expressible in WL for graphs with only ids as data. Thus neither of these languages is subsumed by WL.

To finish the derivation of Property P.[prop:sublanguage95incomparable], we need to show that neither of FO(RDPQ) and GPC subsumes the other. For one non-containment, we use that GPC is NP-hard even without data (Proposition 2), while FO(RDPQ) is in NL without data [3]. For the other, we show that even RDPQ is not subsumed by GPC: this is shown in the argument for Property P.[prop:languages95not95contain95rd] below.

We turn to P.[prop:edn95not95contain95gxpath]. Previously, we derived that FO\(^*(\equiv_{\mathrm{\small data} })\) is not subsumed by FO(ERDPQ) by showing that \(\mathrm{\small DataConnection}\) cannot be expressed within FO(ERDPQ). This example can be used to show non-containment of GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) within FO(ERDPQ). The languages GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) and (FO\(^*_{3}\))\((\equiv_{\mathrm{\small data} })\) are equivalent in expressiveness [2]. The language
(FO\(^*_{3}\))\((\equiv_{\mathrm{\small data} })\) allows us to express \(\mathrm{\small DataConnection} =\mathrm{\small DataLink} ^*\), where \(\mathrm{\small DataLink} (x,y)\) is \[\exists z. (\mathrm{\small OUT}(z,x) \wedge (\exists x. (\mathrm{\small IN}(x,y) \wedge x \equiv_{\mathrm{\small data} } z)))\] As a result, we have P.[prop:edn95not95contain95gxpath].

Next, we argue for P.[prop:languages95not95contain95rd]. Given that RDPQ is also based on regular languages, it can express the query \(Q_{\boldsymbol{even}}\). Consequently, we deduce that WL does not subsume RDPQ. Let’s define \(Q_{\mathrm{\small 4nodes}}\) as the query: \[\begin{align} Q_{\mathrm{\small 4nodes}}:= & \textit{``Is there a path from node s to node t}\\ & \textit{containing four distinct nodes?''.} \end{align}\] For any complete graph \(G\) with two nodes \(s\) and \(t\), there exists a path from \(s\) to \(t\) containing four distinct nodes if and only if \(G\) has at least four nodes. It was established that no GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) formula can differentiate between \(K_3\) and \(K_4\) [2], where \(K_n\) is the complete graph on \(n\) nodes for all \(n\in \mathbf{Z}_{>0}\). More specifically, there is no GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) sentence \(\phi\) such that \(K_4 \models \phi\), but \(K_3 \not\models \phi\). Therefore, \(Q_{\mathrm{\small 4nodes}}\) cannot be expressed using the language GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\). However, the query \(Q_{\mathrm{\small 4nodes}}\) is expressible using RDPQ. So we conclude that GXPath\(_{\mathrm{\small reg}}(\equiv_{\mathrm{\small data} })\) does not subsume RDPQ.

Lastly, to show that RDPQ is not subsumed by GPC, we require the notion of normal form patterns and their corresponding properties:

By applying the following two families of rules, we can normalize every GPC pattern. The first family pushes filters out of compositions:

A second family of normalization rules eliminates filters from Kleene star patterns:

Note also that \(\mathfrak{p}^{n...m}\) can be eliminated, since it can be seen as \(\mathfrak{p}^{n...n}+...+\mathfrak{p}^{m...m}\), and each \(\mathfrak{p}^{i...i}\) is equivalent to the concatenation of \(i\) copies of \(\mathfrak{p}\), with each copy using a fresh set of node variables. This allows us to consider only the case \(\mathfrak{p}^{0...\infty}\).

As a result, we have:

We will also rely on the fact that patterns cannot distinguish between two graphs that are isomorphic:

Now we are ready to show that RDPQ is not subsumed by GPC.

5 Unifying the Languages↩︎

A natural way to find a language subsuming all the languages in Figure 1 is to extend FO(ERDPQ) or FO\(^*(\equiv_{\mathrm{\small data} })\), which are shown to be the maximally expressive query languages within the diagram in the preceding section. Essentially, FO(ERDPQ) is a first-order logic. The extension of FO(ERDPQ) augmented with transitive closures then intuitively subsumes FO\(^*(\equiv_{\mathrm{\small data} })\). However, there is an issue we need to address. In FO(ERDPQ), there are two types of variables: node variables and path variables. Given a formula \(\phi(\boldsymbol{x},\boldsymbol{y})\), where \(\boldsymbol{x}\) and \(\boldsymbol{y}\) have the same arity, we cannot form \(\phi^*(\boldsymbol{x},\boldsymbol{y})\) without considering the types of variables in \(\boldsymbol{x}\) and \(\boldsymbol{y}\). For instance, it does not make sense to allow a formula \(\psi^*(x,\pi)\) from a formula \(\psi(x,\pi)\) where \(x\) is a node variable and \(\pi\) is a path variable. We address this by imposing the restriction that all the variables in vectors \(\boldsymbol{x}, \boldsymbol{y}\) of formula \(\phi\) are node variables.

Since FO\(^*\)(ERDPQ) is an extension of FO(ERDPQ), to define the semantics, we simply have to illustrate the meaning of \(\phi^*(\boldsymbol{x},\boldsymbol{y})\), where \(\boldsymbol{x}, \boldsymbol{y}\) are vectors of node variables with the same arity. Given a data graph \(G\), we write \(G \models \phi^*(\boldsymbol{v},\boldsymbol{v}')\) if there exists a sequence of vectors of nodes \(\boldsymbol{v}_1=\boldsymbol{v},\dots,\boldsymbol{v}_n=\boldsymbol{v}'\) such that \(G \models \phi(\boldsymbol{v}_i,\boldsymbol{v}_{i+1})\) for \(1\leq i < n\).

By the definition of FO\(^*\)(ERDPQ), we have the following theorem:

Next, we show that FO\(^*\)(ERDPQ) is well-behaved.

Figure 2 summarizes the results of this section.

6 Multi-Path Walk Logic, an extension of WL↩︎

In the previous section, we extended FO(ERDPQ) to unify the prior languages. Based on Theorem 3, we have that FO(ERDPQ) subsumes WL, GPC, RDPQ, and FO(RDPQ). The query languages RDPQ for data graphs and FO(ERDPQ) for graphs without data are well-studied [2], [3]. In this section, we examine WL and derive an extension of WL, still subsumed by FO(ERDPQ).

Consider a path \(\rho = v_0a_1v_1 \dots v_n\). Node \(v_i\) is at the \(i^{th}\) position in \(\rho\) for \(i\in [0,n]\). In other words, every node in \(\rho\) corresponds to a number in \([0,n]\). In WL, we can compare nodes’ data values through their positions. Additionally, we can compare node positions as numbers if they are on the same path. However, comparison across different paths is not allowed. That is, we can assert \(l^\pi < n^\omega\) only if \(\pi = \omega\). We call the extension of WL obtained by lifting this limitation multi-path walk logic (MWL). Note that \(\ell^\pi < n^\omega\) is expressible in WL for different \(\pi, \omega\) if \(\ell\) and \(n\) refer to some given constants. In this section, we study the properties of MWL. We relate it to the languages investigated in the preceding sections and derive the decidability of query evaluation.

Recall from Section 4 that to complete the proof of Theorem 1, we need to show that WL is contained in FO(ERDPQ). We will show something stronger: that MWL, an extension of WL, is contained in FO(ERDPQ).

In Theorem 1, we claimed that WL is subsumed by FO(ERDPQ), which follows directly from the following result:

On the other hand, MWL remains fundamentally a first-order language, unable to count the parity of a set. More specifically, we show that on \(\Sigma\)-words, MWL is subsumed by \(\mathrm{\small FO}[<, +, \{a\}_{a \in \Sigma}]\), a first-order logic where variables range over positions of words and the interpretations of \(<, +, \{a\}_{a \in \Sigma}\) are standard. Since checking whether the number of positions with a particular symbol \(a\) is even is not definable in \(\mathrm{\small FO}[<, +, \{a\}_{a \in \Sigma}]\) [20], it is also not definable in MWL.

Parity is a regular language, so it is in RDPQ and GPC. Thus:

As a result, we have:

7 Discussion↩︎

In this work, we have provided what we believe is a fairly complete picture of the landscape of expressiveness among query languages for data graphs. See Figure 2. We showed that the landscape of prior query languages lacked a single maximally expressive language. FO\(^*(\equiv_{\mathrm{\small data} })\), a first-order language augmented with transitive closure, and FO(ERDPQ) were maximally expressive query languages, but they are incomparable. To remedy this, we introduce FO\(^*\)(ERDPQ), which is FO(ERDPQ) extended with transitive closure. We show that it subsumes the prior languages.

Beyond exploring the landscape of query languages for data graphs, we examine the potential of WL, which only allows comparisons along a single path. We show that MWL, the extension of WL allowing multi-path comparisons, is more powerful than WL.

Although query evaluation of FO\(^*\)(ERDPQ) is decidable, we acknowledge that it is, in an important sense, too expressive, as the worst-case complexity of evaluation is extremely high, with no elementary bound in the size of the data. Identifying fragments with better evaluation complexity, as well as developing algorithmic techniques for implementing them, is a key piece of ongoing work.

Since RDPQ and its extensions, including FO\(^*\)(ERDPQ), manipulate data along the paths through register automata, we can easily extend these languages to include aggregates by replacing register automata with other automata such as register automata with linear arithmetic [25] and cost register automata [26]. This is another component of future work.

7.1 Other aspects of graph query languages↩︎

A number of aspects of graph querying have not been considered here.

Property graphs vs our data model. First, in our work we deal with a simplified data model. A commonly considered data model for graphs with data in recent years is the property graph model [14], and this data model is the basis for work on standards. In a property graph, both nodes and edges can have associated data. This data can be left unrestricted, including varying the number of attributes as well as their datatypes. Or it can be restricted by a schema. In our simplified data model, we require a fixed set of attributes for nodes, each with standard infinite datatypes, while we have a fixed set of edge relations, not associated with data values. While we believe that our results can be extended to the property graph model (e.g. by standard encoding of edge labels within node labels), we do not formalize this.

GPC. In this work, we have not considered several aspects of GPC, including inverse edges and trails.

Inverses. As mentioned earlier, inverse edges are not part of the definition of many of the classical graph query languages (including R(D)PQ and Walk Logic) and a sensible comparison would need to either include inverse edges in these languages, or consider the fragment of GPC without inverse edges. We have chosen the latter, to simplify our presentation. The former would also not change the subsumption of the query languages, and take us to languages like 2RPQ [9] and extension with data [8].

Trails. We now discuss trails, which restrict paths so that no edges are repeated. We do not consider trails in detail here. But we note that including trails does not change the subsumption of GPC in the other query languages that we considered in this paper. For example, we can assert that a path is a trail in Walk Logic as follows: \[\begin{align} \phi_{trail}(\pi) & := & \forall \ell^{\pi},m^{\pi}.\;\ell^{\pi} \neq m^{\pi} \wedge \ell^{\pi} \equiv_{\mathrm{\small id} } m^{\pi} \wedge \\ & & \bigvee_{a \in \Sigma} (E_a(\ell^{\pi},\ell^{\pi}+1) \wedge E_a(m^{\pi},m^{\pi}+1)) \rightarrow (\ell^{\pi}+1 \not\equiv_{\mathrm{\small id} } m^{\pi}+1). \end{align}\] Similarly, we can express trails in FO(ERDPQ) by using similar register automata as in Example 1, but with two registers instead of just one.

Joins. We have discussed GPCpattern queries here, which return paths. It is possible to extend these queries to return more complex objects, particularly tuple of paths. For two GPC queries \(Q\) and \(Q'\) with semantics \([\![{Q}]\!]_{G}\) and \([\![{Q'}]\!]_{G}\), respectively, we define their join as follows:

• \([\![{Q, Q'}]\!]_{G} = \{((\bar{\rho}, \bar{\rho}'), \mu \cup \mu') \mid (\bar{\rho}, \mu) \in [\![{Q}]\!]_{G}, (\bar{\rho}', \mu') \in [\![{Q'}]\!]_{G}\), and the union \(\mu\cup\mu' \text{ is defined}\}\).

Thus a join of two path patterns returns a pair of paths. We can close the syntax of GPC under join, allowing us to return \(k\)-tuples for any \(k\). In our paper we compare languages by considering the graph queries that return Booleans which they can express (Definition 2 in Section 2). Thus, since we do not consider queries that return tuples, and we cannot use joins to produce new paths or Booleans, the presence or absence of joins has no impact on our results.

References↩︎

---

1. In the literature, FO(ERDPQ) for graphs without data is known as ECRPQ\(^\neg\) [3].↩︎

2. In the literature, FO(RDPQ) for graphs without data is known as CRPQ\(^\neg\) [3].↩︎

3. The definitions of GPC provided in [14] and [19] are not identical. For instance, the pattern \(((x) + ()) \rightarrow (y)\) is valid in [14] but not in [19], because the node variable \(x\) appears in the node sub-pattern \((x)\) but not in the sub-pattern \(()\). In general, in [19] the use of variables is more complex. In this paper, we adopt the simpler definitions from [14].↩︎

4. In some prior literature [20], transitive closure operators are defined over formulas of the form \(\phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\), which involve three tuples of variables: \(\mathbf{x}\), \(\mathbf{y}\), and \(\mathbf{z}\), where \(\mathbf{z}\) represents free variables in \(\phi^*(\mathbf{x}, \mathbf{y}, \mathbf{z})\). These two variants of the language FO\(^*\) are equivalent in expressiveness. Specifically, \(\phi^*(\mathbf{x}, \mathbf{y}, \mathbf{z})\) from the alternative variant can be translated into the equivalent formula \(\exists \mathbf{z}'. {\phi'}^*(\mathbf{x}', \mathbf{y}')\) of the variant used in this paper, where \(\mathbf{x}' = (\mathbf{x}, \mathbf{z})\), \(\mathbf{y}' = (\mathbf{y}, \mathbf{z}')\), and \(\phi'(\mathbf{x}', \mathbf{y}') = \phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) \wedge \mathbf{z} = \mathbf{z}'\).↩︎