1 Introduction↩︎

Graph databases [1], [2] have gained significant popularity and are used in areas such as Knowledge Graph management [3], Semantic Web applications [4], and Biology [5]. There are roughly two generations of query languages for handling graph data. The first is SPARQL [6], which is being developed by the W3C since 2004 and became an official W3C standard in 2008. The second generation originated with Neo4j’s Cypher [7], which was initially released in 2011. Cypher heavily inspired SQL/PGQ and GQL, which were standardized by ISO in 2023 and 2024, respectively.

All these languages have path queries as a core feature. In SPARQL, these are supported through property paths, which are a variant of regular path queries (RPQs) [8]–[11]. Intuitively, an RPQ is an expression \((?x,\texttt{regex},?y)\), where regex is a regular expression and \(?x,?y\) are variables. When evaluated over an edge-labeled graph \(G\) (e.g., RDF or property graph), it extracts all node pairs \((n_1, n_2)\) such that there is a path in \(G\) from \(n_1\) to \(n_2\), whose edge labels form a word that matches regex. SPARQL property paths therefore return endpoints of paths. In important applications such as money laundering detection [12] or in investigative journalism [13], retrieving the entire paths that match the expression is of crucial importance. To accommodate this use case, Cypher, GQL, and SQL/PGQ all extend RPQs with a mechanism for returning paths.

1.0.0.1 Path Modes By Example.

We illustrate how these languages allow returning paths. Consider the social network example in Figure [fig:introNew]. Here, we have node identifiers (such as Joe or Rome), edge identifiers (such as e1), and edge labels (for instance, edge e7 has the label follows).² A natural task would be to explore the network that influences Joe, i.e., finding the people that Joe follows, then people they follow, and so on, transitively traversing follows-edges. This can be written as an RPQ of the form \((\texttt{Joe}, \texttt{follows}^+,?x)\), signaling that we wish to start at Joe, and traverse any nonzero number of follows-edges. In this case, the query returns all the people in the database. If we also wish to return paths witnessing these connections, we might run into some issues. Most notably, given the cycle formed by the edges e1 and e2, there is an infinite number of paths from Joe to John. To avoid having to return an infinite number of paths, GQL and SQL/PGQ let the user specify restrictions on the type of paths to be returned through so-called path modes.

We give a few examples of path modes and provide comprehensive details later. Two common path modes are \(\mathit{SIMPLE}\) and \(\mathit{TRAIL}\). Whereas \(\mathit{SIMPLE}\) requires the paths to not repeat any node (apart from the first and last one), \(\mathit{TRAIL}\), requires to not repeat any edge. For instance, our example has one path satisfying \(\mathit{SIMPLE}\) from Joe to Lily (only taking edge e4), but two paths satisfying \(\mathit{TRAIL}\)(the additional one being e2 \(\rightarrow\) e1 \(\rightarrow\) e4).

Another common way to force the number of paths to be finite is by selecting only the shortest paths. The \(\mathit{ANY}\) \(\mathit{SHORTEST}\) mode in GQL and SQL/PGQ will return a single shortest path for each different pair of endpoints in the answer, whereas \(\mathit{ALL}\) \(\mathit{SHORTEST}\) will return all such shortest paths. For instance, there are five paths matching the RPQ \((\texttt{Joe},\texttt{follows}^+\cdot \texttt{works},?x)\). Incidentally they are all from Joe to ENS PARIS. The \(\mathit{ALL}\) \(\mathit{SHORTEST}\) mode returns the three shortest ones, which are \(\texttt{e3}\rightarrow \texttt{e5}\rightarrow \texttt{e11}\), \(\texttt{e4}\rightarrow \texttt{e7}\rightarrow \texttt{e10}\), and \(\texttt{e3}\rightarrow \texttt{e6}\rightarrow \texttt{e10}\)). \(\mathit{ANY}\) \(\mathit{SHORTEST}\) would return an arbitrary path among these. We note that these modes select the shortest paths among all paths that match. For instance, \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \((\texttt{Joe},\texttt{follows}\cdot\texttt{follows}\cdot\texttt{follows},?x)\) returns the path \(\texttt{e2}\rightarrow \texttt{e1}\rightarrow \texttt{e4}\) from Joe to Lily and \(\texttt{e2}\rightarrow \texttt{e1}\rightarrow \texttt{e3}\) from Joe to Paul, even though shorter paths (that, crucially, do not match the RPQ) between these end-nodes exist. The standard supports a total of twenty seven path modes, most of which use the ingredients we outlined here, thus giving the user fine-grained control over which paths should be returned as path of the query answer.

1.0.0.2 Support for Path Modes is Lacking.

While Cypher, GQL, and SQL/PGQ all recognize the need to return paths that match regular path queries, the support for these features in modern graph databases is still lacking. As already stated, in SPARQL engines, RPQ matching is supported for all regular languages, but paths cannot be returned. In property graph engines that implement (fragments of) GQL or SQL/PGQ, only a handful of path modes is supported, and no property graph engine to date supports all regular path queries like SPARQL engines do. For reference, we summarize the support for path features in several popular SPARQL and property graph engines in Table ¿tbl:tab:intro? below. Here, “RPQ” means the support for all regular languages in RPQs, while the other columns signal which types of paths can be returned.

The overall picture tells us that SPARQL engines support all RPQs, but do not return paths. On the other hand, while several property graph engines can return some (but not all) types of paths, they only support a limited number of regular expressions in RPQs. PathFinder is the first engine that can return paths for every RPQ.

In addition, both SPARQL engines and property graph engines are known to exhibit slow execution times when dealing with path queries [22], [23]. We believe that this is the case because of scalability. In particular, the number of paths that match an RPQ can be exponential in the size of the graph [24] and existing engines don’t have a principled method to tackle this issue. In this paper, we tackle these problems and show that:

1. Regular path queries can be evaluated efficiently while at the same time returning paths under all the path modes in the GQL standard at the point of writing this paper.

2. Adding these implementations on top of an existing property graph engine can be done with ease.

3. One can extend these algorithms to the RDF/SPARQL context and extend existing SPARQL engines with the ability to return paths.

Our Contribution. To achieve the three points above, we introduce PathFinder, a unified framework for returning paths in graph query answers. Our concrete contributions can be summarized as follows:

• We describe implementable algorithms for evaluating RPQs and returning paths under each GQL path mode.

• We show how all these algorithms can share a common core and can build on the same fundamental principle: the product graph [9], [24]. Indeed, each of the algorithms is a modification of classical graph search on the product graph, with extra bookkeeping. As such, our algorithms always produce a path multiset representation [24], a compact representation of all paths that need to be returned. We show how this compact representation can be constructed lazily, such that paths can be returned as soon as they are detected, allowing for seamless incorporation into a database pipeline.

• We provide a full implementation of PathFinder, which is the first property graph engine to support returning entire paths in all 27 modes in the GQL and SQL/PGQ standards, for all RPQs.

• PathFinder is the first graph database engine that supports returning paths for all regular languages.

• We extend the SPARQL syntax with the ability to return paths and implement this extension on top of an existing RDF engine, showing that our approach is a feasible extension for existing triplestores.

• We perform a detailed experimental evaluation of our solution, using both synthetic and real-world data and queries. Most notably, we test our approach over Wikidata [25] using real world queries [26] and show remarkably scalable performance, even for worst-case intractable queries.

Our work shows that it is possible to extend SPARQL with path returning features, while keeping query evaluation performant. Importantly for a clean design, however, is that the semantics of path returning queries is consistent with standard constructions in automata theory [27]. We discuss this in more depth in Section 8.

Remark. This manuscript is an extension of Farias et al. [28], which appeared in the International Semantic Web Conference 2024. Compared to the conference version, we extend the work to also cover group modes of GQL, thus covering all path modes that are prescribed by the standard. Additionally, we provide more details to the algorithmic solutions and additional examples illustrating how these operate. We also discuss the complexity of our algorithms and extend the experimental setup to include more use cases and to illustrate finer points about our algorithms.

Code Availability. All of the code and experimental data is available in our repository [29].

Organization. We define GQL path queries in Section 2. PathFinder and the way it handles arbitrary paths is presented in Section 3. Paths satisfying the \(\mathit{TRAIL}\) and \(\mathit{SIMPLE}\) modes are treated in Section 4. Implementation details are presented in Section 5. Experimental evaluation is performed in Section 6. Related work is discussed in Section 7. We conclude in Section 8. Additional details, code, and experiments can be found in our repository [29].

2 Graph Databases and Path Queries↩︎

We define graph databases and path queries as supported by the GQL and SQL/PGQ standard.

Graph Databases. Let \(\mathit{Nodes}\) be a set of node identifiers and \(\mathit{Edges}\) be a set of edge identifiers, with \(\mathit{Nodes}\) and \(\mathit{Edges}\) being disjoint. Additionally, let \(\mathit{Lab}\) be a set of labels. Following [4], [13], [24], [30], we define graph databases as follows.

Intuitively, \(\rho(e)=(v_1,v_2)\) means that \(e\) is a directed edge going from \(v_1\) to \(v_2\). We use a simplified version of property graphs that omits node and edge properties (with their associated values). This is done since the type of queries we consider only use nodes, edges, and edge labels. However, all of our results transfer to the full version of property graphs. We also remark that our results apply directly to RDF graphs [31] and edge-labeled graphs [9], [10], which do not use explicit edge identifiers.

Paths. A sequence \(p = v_0 e_1 v_1 e_2 v_2 \cdots e_n v_n\) is called a path in a graph database \(G=(V,E,\rho,\lambda)\), if \(n \geq 0\), \(e_i \in E\), and \(\rho(e_i) = (v_{i-1},v_i)\) for \(i = 1,\ldots ,n\). If \(p\) is a path in \(G\), we write \(\mathit{lab}(p)\) for the sequence of labels \(\lambda(e_1) \cdots \lambda(e_n)\) occurring on the edges of \(p\). We write \(\mathit{src}(p)\) for the starting node \(v_0\) of \(p\), and \(\mathit{tgt}(p)\) for the end node \(v_n\) of \(p\). The length of a path \(p\), denoted \(\mathit{len}(p)\), is defined as the number \(n\) of edges it uses. We say that a path \(p\) is

• a walk, for every \(p\) (as per GQL and SQL/PGQ terminology);

• a trail, if \(p\) does not repeat an edge (that is, \(e_i\neq e_j\) for every \(i\neq j\));

• acyclic, if \(p\) does not repeat a node (that is, \(v_i\neq v_j\) for every \(i\neq j\)); and

• simple, if \(p\) does not repeat a node, except that possibly \(\mathit{src}(p) = \mathit{tgt}(p)\).

In examples, we will often use the lighter notation \(e_1 \rightarrow \cdots \rightarrow e_n\) for paths. Given a set of paths \(P\) over a graph database \(G\), we say that \(p\in P\) is a shortest path in \(P\), if \(\mathit{len}(p)\leq \mathit{len}(p')\) for each \(p'\in P\). We use \(\mathit{Paths}(G)\) to denote the (possibly infinite) set of all paths in a graph database \(G\). By \(\mathit{Paths}(G,\mathit{walk})\), \(\mathit{Paths}(G,\mathit{trail})\), \(\mathit{Paths}(G,\mathit{acyclic})\), and \(\mathit{Paths}(G,\mathit{simple})\), we denote the subsets of \(\mathit{Paths}(G)\) that are walks, trails, acyclic paths, and simple paths, respectively. Notice that \(\mathit{Paths}(G,\mathit{walk}) = \mathit{Paths}(G)\).

Path Queries in GQL and SQL/PGQ. To define path queries, we assume the existence of a set \(\mathit{Var}\) of variables, disjoint from \(\mathit{Nodes}\), \(\mathit{Edges}\), and \(\mathit{Lab}\). Following the GQL [32] and SQL/PGQ [33] standards, we define path queries as expressions of the form \[\mathit{sel}?\; \mathit{res}\; (X,\mathit{rgx},Y)\] where \(\mathit{sel}\) is called a selector, \(\mathit{res}\) is called a restrictor, and \(\mathit{rgx}\) is a regular expression. We define all these ingredients next. Furthermore, \(\mathit{sel}\)? means that the selector is optional.

In this paper, regular expressions are inductively defined as follows. Each element of \(\mathit{Lab}\) is a regular expression, \(\varepsilon\) is a regular expression, and if \(r\), \(r_1\), and \(r_2\) are regular expressions, then so are their disjunction \((r_1 + r_2)\), their concatenation \((r_1 \cdot r_2)\), and the Kleene closure \(r^*\). By standard convention, we omit brackets and (usually) omit the sign \(\cdot\) to simplify notation. We use \(r?\) to abbreviate \((r+\varepsilon)\) and \(r^+\) to abbreviate \((r \cdot r^*)\). The language \(\mathcal{L}(r)\) of the regular expression \(r\) is inductively defined as \(\mathcal{L}(\varepsilon) = \{\varepsilon\}\) and \(\mathcal{L}(a) = \{a\}\) for every \(a \in \mathit{Lab}\). Furthermore, \(\mathcal{L}(r_1 + r_2) = \mathcal{L}(r_1) \cup \mathcal{L}(r_2)\), \(\mathcal{L}(r_1 \cdot r_2) = \mathcal{L}(r_1) \cdot \mathcal{L}(r_2)\), and \(\mathcal{L}(r^*) = \cup_{k=0}^\infty \mathcal{L}(r)^k\). Here, for a set of words \(S\), we denote by \(S^k\) the \(k\)-fold concatenation of \(S\). The size of a regular expression, which we write as \(|r|\), is the number of occurrences of symbols of \(\mathit{Lab}\cup \{\varepsilon\}\) it contains. We will refer to the subexpression \((X,\mathit{rgx},Y)\) as a regular path query or RPQ [10]. In regular path queries, the symbols \(X\) and \(Y\) represent variables or nodes in the graph. To distinguish these cases, we will always write variables using question marks (e.g., \(?x\), \(?y\)) and nodes without question marks (e.g., \(v,v',n,n'\)).

Selectors and restrictors are used to specify which paths are to be returned. Their grammar is: \[\begin{align} \mathit{sel}\quad ::= \quad & \;\mathit{ANY}\;|\;\mathit{ANY}\;\mathit{SHORTEST}\;| \;\mathit{ALL}\;\mathit{SHORTEST}\;| \; \mathit{ANY}\;k \;| \; \mathit{SHORTEST}\;k \;| \; \mathit{SHORTEST}\;k\;\mathit{GROUPS}\\ \mathit{res}\quad ::= \quad & \;\mathit{WALK}\;|\;\mathit{TRAIL}\;|\; \mathit{SIMPLE}\;|\;\mathit{ACYCLIC} \end{align}\] Here, \(k \in \{1,2,3,\ldots\}\) is a natural number.

A path mode is either a restrictor or a combination of a selector and a restrictor. This gives us 28 path modes: 6 selectors times 4 restrictors, plus the 4 restrictors without selector. However, \(\mathit{WALK}\) needs to be preceded by a selector [13] to avoid the need to return infinitely many paths in some cases, which gives 27 relevant modes.

2.0.0.1 Semantics of Path Queries.

Let \(G\) be a graph database. We first consider path queries \(q\) of the form \[\mathit{res}\;(?x,\mathit{rgx},?y)\;,\] that is, we omit the optional selector \(\mathit{sel}\) and assume that the RPQ uses two different variables \(?x\) and \(?y\). By slight abuse of notation, we use \(\mathit{Paths}(G,\mathit{res})\) to denote the set of all paths in \(G\) that are valid according to \(\mathit{res}\). That is, we also use \(\mathit{Paths}(G,\mathit{TRAIL})\) to denote \(\mathit{Paths}(G,\mathit{trail})\), etc. We then define the semantics of \(q\) over \(G\), denoted \(\llbracket q\rrbracket_{G}\), as \[\llbracket \mathit{res}\; (?x,\mathit{rgx},?y)\rrbracket_{G} = \{ (v,v',p) \;\mid\; p\in \mathit{Paths}(G,\mathit{res}),\;\mathit{src}(p) = v,\;\mathit{tgt}(p) = v',\;\mathit{lab}(p)\in \mathcal{L}(\mathit{rgx})\} \;.\] For example, the semantics of “\(\mathit{TRAIL}\;(?x, \mathit{rgx},?y)\)” over \(G\) is the set of triples \((v,v',p)\) such that \(p\) is a trail in \(G\) from \(v\) to \(v'\) and \(\mathit{lab}(p)\in \mathcal{L}(\mathit{rgx})\). If \(G\) has cycles and the restrictor is \(\mathit{WALK}\), this set can be infinite.

In order to define the semantics of selectors, we need some additional notation. We write

• \(\mathit{EndPoints}(\llbracket q\rrbracket_{G})\) for the set \(\{(v,v') \mid (v,v',p) \in \llbracket q\rrbracket_{G}\}\),

• \(\mathit{Paths}(\llbracket q\rrbracket_{G},v,v')\) for the set \(\{p \mid (v,v',p) \in \llbracket q\rrbracket_{G}\}\),

• for a set \(P\) of paths,

  • \(\mathit{Shortest}(P)\) for the set \(\{p \in P \mid \nexists p' \in P\) such that \(\mathit{len}(p') < \mathit{len}(p)\}\), and

  • \(k\text{-}\mathit{ShortestLength}(P)\) for the \(k\)-th smallest element of the set \(\{\mathit{len}(p) \mid p \in P\}\).

We now define the semantics of selectors and use \(q\) to denote the selector-free query \(\mathit{res}\; (?x,\mathit{rgx},?y)\). Let \(S \subseteq \llbracket q\rrbracket_{G}\), which means that \(S\) only contains triples of the form \((v,v',p)\) such that \(p\) is a path from \(v\) to \(v'\) that matches \(\mathit{rgx}\). For nodes \(v\) and \(v'\), we denote by \(S|_{v,v'}\) the subset \(\{(u,u',p) \in S \mid u = v\) and \(u' = v'\}\) of \(S\). We define when \(S\) satisfies \(q\) under \(\mathit{sel}\) in \(G\), denoted as \(S \models (\mathit{sel}\;q)_{G}\), on a case-by-case basis:

• \(S \models (\mathit{ANY}\;q)_{G}\) if for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\) the set \(S|_{v,v'}\) contains a single tuple \((v,v',p)\).

• \(S \models (\mathit{ANY}\;\mathit{SHORTEST}\;q)_{G}\) if for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\) the set \(S|_{v,v'}\) contains exactly one tuple \((v,v',p)\) and, additionally, \(p \in \mathit{Shortest}(\mathit{Paths}(\llbracket q\rrbracket_{G},v,v'))\).

• \(S \models (\mathit{ALL}\;\mathit{SHORTEST}\;q)_{G}\) if, for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\), we have \(S|_{v,v'} = \{(v,v',p) \mid p \in \mathit{Shortest}(\mathit{Paths}(\llbracket q\rrbracket_{G},v,v'))\}\).

• \(S \models (\mathit{ANY}\;k\;q)_{G}\) if, for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\), either

  • \(S|_{v,v'} = \{(v,v',p) \mid p \in \mathit{Paths}(\llbracket q\rrbracket_{G},v,v')\}\), if \(|\mathit{Paths}(\llbracket q\rrbracket_{G},v,v')| \leq k\); or

  • \(S\) has exactly \(k\) tuples of the form \((v,v',p)\), otherwise.

• \(S \models (\mathit{SHORTEST}\;k\;q)_{G}\) if, for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\), either

  • \(S|_{v,v'} = \{(v,v',p) \mid p \in \mathit{Paths}(\llbracket q\rrbracket_{G},v,v')\}\), if \(|\mathit{Paths}(\llbracket q\rrbracket_{G},v,v')| \leq k\); or

  • \(S\) has exactly \(k\) tuples of the form \((v,v',p)\), all of which have \(|\{p'\in \mathit{Paths}(\llbracket q\rrbracket_{G},v,v') \mid \mathit{len}(p') < \mathit{len}(p)\}| < k\), otherwise.

• \(S \models (\mathit{SHORTEST}\;k\;\mathit{GROUPS}\;q)_{G}\) if, for each pair \((v,v') \in \mathit{Endpoints}(\llbracket q\rrbracket_{G})\), we have that \(S|_{v,v'} = \{(v,v',p) \mid \mathit{len}(p) \leq k\text{-}\mathit{ShortestLength}(\mathit{Paths}(\llbracket q\rrbracket_{G},v,v'))\}\).

Notice that the \(\mathit{SHORTEST}\) modes select shortest paths grouped by endpoints. That is, the selected paths do not need to be the shortest in the entire output, they only need to be the shortest matching paths from \(v\) to \(v'\). The rationale for \(\mathit{SHORTEST}\) \(k\) \(\mathit{GROUPS}\) is similar.

Finally, if \(X\) is a node \(u\) in \(G\), then the semantics is defined exactly as above, but requires all answers \((v,v',p)\) to have \(v = u\). (The case where \(Y\) is a node in \(G\) is analogous.) As such, one can also use queries of the form \(\mathit{ALL}\;\mathit{TRAILS}\;(u,\texttt{a}^+,?y)\) or \(\mathit{ALL}\;\mathit{TRAILS}\;(u,\texttt{a}^+,u')\), where \(u\) and \(u'\) are elements of \(\mathit{Nodes}\).

Notice that the semantics of \(\mathit{ANY}\), \(\mathit{ANY}\) \(\mathit{SHORTEST}\), \(\mathit{ANY}\) \(k\), and \(\mathit{SHORTEST}\) \(k\) is non-deterministic in the sense that there can be multiple subsets \(S\) of \(\llbracket q\rrbracket_{G}\) that satisfy the condition. Terminologically, we deal with this as follows. By slight abuse of notation, we say that \(S = \llbracket \mathit{sel}\;q\rrbracket_{G}\) if \(S\) is the only subset of \(\llbracket q\rrbracket_{G}\) such that \(S \models (\mathit{sel}\;q)_G\). Otherwise, we say that \(\llbracket \mathit{sel}\;q\rrbracket_{G}\) can be \(S\). We use analogous terminology for describing \(S\), for instance, we can say that \(S\) can contain a given answer.

Remark. While we define the semantics of queries as sets of answers, the GQL specification requires answers to be returned grouped by endpoints \((v,v')\). For instance, when answering a query of the form \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(q\), if there are multiple matching paths from \(v\) to \(v'\), these should be returned one after the other before moving to another pair of nodes. All algorithms we present in the paper enumerate the results in such a fashion.

Output-Linear Delay. Returning paths can result in a large number of outputs. Therefore, to measure the efficiency of our algorithms, we will use the paradigm of enumeration algorithms [24], [34]–[38]. Such algorithms work in two phases: a pre-processing phase, which constructs a data structure allowing us to output the solutions; and the enumeration phase, which enumerates these solutions without repetitions. The efficiency of an enumeration algorithm is measured by the complexity of the pre-processing phase, and the delay between any two outputs produced during the enumeration phase. We will say that an enumeration algorithm works with output-linear delay, when the delay is linear in the size of each output element. This means that the time needed to output a single path is linear in the number of nodes in the path, after which we immediately start to output the next path. Notice that this is optimal in a sense that to return a path to the user, we have to at least write down each element of the path.

Regular Expressions and Automata. We assume basic familiarity with regular expressions and finite state automata [39]. We use \(\mathcal{A} = (Q,\Sigma,\delta,q_0,F)\) to denote a non-deterministic finite automaton (NFA). Here, \(Q\) is a set of states, \(\Sigma\) a finite alphabet of edge labels, \(\delta\) the transition relation over \(Q\times \Sigma\times Q\), \(q_0\) the initial state, and \(F\) the set of final states, respectively. An NFA is deterministic (or a DFA for short) if \(\delta\) is a function. A regular expression \(\mathit{rgx}\) can be converted into an equivalent \(\varepsilon\)-free NFA of size quadratic in \(|\mathit{rgx}|\) (see [39]). Here, the quadratic factor only depends on the size of the alphabet \(\Sigma\). There are several standard ways of converting an expression to an automaton, for instance using Thompson’s or Glushkov’s construction [39]. In this paper, we assume that the automaton has a single initial state and that no \(\varepsilon\)-transitions are present. An NFA is called unambiguous if it has at most one accepting run for every word. Every DFA is unambiguous, but the converse is not necessarily true.

3 Backbone of PathFinder and the WALK Semantics↩︎

We describe the main idea behind PathFinder and show how it can be used to evaluate RPQs under the \(\mathit{WALK}\) semantics. That is, we show how to treat queries of the form \[\mathit{sel}\;\mathit{WALK}\;(v,\mathit{rgx},?x)\;.\] Recall that the selector \(\mathit{sel}\) for such queries is obligatory in GQL, since the set of all walks can be infinite. For simplicity of exposition, we assume for now that the starting point of the RPQ is fixed (i.e., we start from a concrete node \(v \in \mathit{Nodes}\)) and discuss the other cases for endpoints later. Our approach relies heavily on the product automaton construction [40], but we apply it to an automaton for the RPQ and the graph database, as in [9]. We call the resulting structure the product graph. We will present how the product graph is built in its entirety, but in practice it is important to construct it lazily, i.e., only construct the part of it that is needed to evaluate the query.

Product Graph. Given a graph database \(G = (V,E,\rho,\lambda)\) and an expression of the form \(q = (v,\mathit{rgx},?x)\), the product graph is constructed by first converting the regular expression \(\mathit{rgx}\) into an equivalent non-deterministic finite automaton \(\mathcal{A}= (Q,\Sigma,\delta,q_0,F)\). The automaton consists of a set of states \(Q\), the finite subset \(\Sigma\) of \(\mathit{Lab}\) that is used in \(\mathit{rgx}\), the transition relation \(\delta \subseteq Q\times \Sigma\times Q\), the initial state \(q_0\), and the set of final states \(F\). The product graph \(G_\times(\mathcal{A},G)\), which is obtained from \(\mathcal{A}\) and \(G\) is then defined as the graph database \((V_\times, E_\times, \rho_\times, \lambda_\times)\), where

• \(V_\times = V\times Q\);

• \(E_\times = \{(e,(q_1,a,q_2)) \in E\times \delta \mid \lambda(e) = a\}\);

• \(\rho_\times((e,d)) = ((x,q_1),(y,q_2))\) if:

  • \(d = (q_1,a,q_2)\) and

  • \(\rho(e)=(x,y)\);

• \(\lambda_\times((e,d)) = \lambda(e)\).

We sometimes write \(G_\times\) when \(\mathcal{A}\) and \(G\) are clear from the context. Each node of the form \((u,q)\) in \(G_\times\) corresponds to the node \(u\) in \(G\) and, furthermore, each path \(P\) of the form \((v,q_0) (e_1,(q_0,a_1,q_1)) (v_1,q_1) \cdots (e_n,(q_{n-1},a_n,q_n)) (v_n,q_n)\) in \(G_\times\) corresponds to a path \(p = v e_1 v_1 \cdots e_n v_n\) in \(G\) that (a) has the same length as \(P\) and (b) brings the automaton from state \(q_0\) to \(q_n\). As such, when \(q_n \in F\), then the path \(p\) in \(G\) matches \(\mathit{rgx}\). In other words, all nodes \(v'\) that can be reached from \(v\) by a path that matches \(\mathit{rgx}\) can be found by using standard graph search algorithms (e.g., BFS/DFS) on \(G_\times\) starting in the node \((v,q_0)\).

While this approach allows finding pairs \((v,v')\) in answers to an RPQ, we show next how it can be used to also find paths. Our approach is rooted in this fairly standard construction in automata theory and has important advantages: (a) the product graph can indeed be explored lazily for all 27 path modes, (b) paths can be always returned on-the-fly, allowing pipelined execution, and (c) the approach is highly efficient (Section 6). We point out in which cases subtleties such as unambiguity of the automaton need to be taken into account to achieve a correct algorithm.

3.1 ANY (SHORTEST) WALK↩︎

We first treat the \(\mathit{WALK}\) restrictor combined with selectors \(\mathit{ANY}\) and \(\mathit{ANY}\) \(\mathit{SHORTEST}\), that is, queries of the form: \[\begin{gather} \label{lab:anywalk} Q = \mathit{ANY}\;(\mathit{SHORTEST})?\;\mathit{WALK}\;(v,\mathit{rgx},?x) \end{gather}\tag{1}\] Let \(\mathcal{A}= (S,\Sigma,\delta,q_0,F)\) be an NFA for \(\mathit{rgx}\). The idea is that, for queries \(Q\) of the form 1 , we can perform a classical graph search algorithm such as BFS or DFS starting at the node \((v,q_0)\) of the product graph \(G_\times(\mathcal{A},G)\). Since both BFS and DFS support reconstructing a single (shortest in the case of BFS) path to any reached node, we obtain the desired semantics for queries of the form (1 ). Query evaluation is presented in Algorithm 2. The algorithm is a straightforward adaptation of BFS and DFS on a lazily constructed \(G_\times\) with modifications that eliminate multiple paths reaching the same node and multiple accepting runs in an automaton. We present the algorithm in detail since we extend the approach to support different semantics later.

The basic object we manipulate is a search state, i.e., a quadruple of the form \((n,q,e,prev)\), where \(n\) is the node of \(G\) we are currently exploring, \(q\) is the current state of \(\mathcal{A}\), while \(e\) is the edge of \(G\) we used to reach \(n\), and \(prev\) is a pointer to the search state we used to reach \((n,q)\) in \(G_\times\). Intuitively, the \((n,q)\)-part of the search state allows us to track the node of \(G_\times\) we are traversing, while \(e\), together with \(prev\) allows to reconstruct the path from \((v,q_0)\) that we used to reach \((n,q)\). The algorithm uses four data structures:

• Open, which is a queue (in case of BFS), or stack (in case of DFS) of search states, with usual push() and pop() methods.

• Visited, which is a dictionary of search states we have already visited in our traversal. It prevents us from entering an infinite loop. We assume that \((n,q)\) can be used as a search key to check if some \((n,q,e,prev)\in \textit{Visited}\). We remark that \(prev\) always points to a state stored in Visited.

• Solutions, which is a set containing (pointers to) search states in Visited that encode a solution path to be returned; and

• ReachedFinal, a set containing nodes we already returned as query answers, in case we re-discover them via a different end state (recall that an NFA can have several end states).

The algorithm explores the product \(G_\times(\mathcal{A},G)\) using either BFS (if Open is a queue) or DFS (if Open is a stack), starting from \((v,q_0)\). It starts by initializing the data structures and setting up the start node in \(G_\times\) (lines 2–5). The main loop of line 6 is the classical BFS/DFS algorithm that pops an element \((n,q,e,prev)\) from Open (line 7) and starts exploring its neighbors in \(G_\times\) (lines 11–14). When exploring \((n,q,e,prev)\), we scan all the transitions \((q,a,q')\) of \(\mathcal{A}\) that originate from state \(q\), and look for neighbors of \(n\) in \(G\) reachable by an \(a\)-labeled edge (line 11). The test \((n',q',\mathit{edge}')\in\) Neighbors\(((n,q,\mathit{edge},\mathit{prev}),G,\mathcal{A})\) in line 11 checks whether \(\rho(\mathit{edge}')=(n,n')\) in \(G\), and whether \((q,\lambda(\mathit{edge}'),q')\) is a transition of \(\mathcal{A}\). If the pair \((n',q')\) has not been visited yet, we add it to \(\textit{Visited}\) and \(\textit{Open}\) (lines 12–14), which allows it to be expanded later on in the algorithm. When popping from Open in line 7, we also check if \(q\) is a final state and that \(n\) has not been reached by a solution path yet (line 8). In this case we found a new solution; i.e., a walk from \(v\) to \(n\) whose label is in the language of \(\mathit{rgx}\), so we add it to Solutions (line 10) and record it as reached (line 9). The \(\textit{ReachedFinal}\) set is used to ensure that each solution is returned only once. Basically, since our automaton is non-deterministic and can have multiple final states, two things can happen:

• The automaton might be ambiguous, that is, it could have multiple accepting runs on the same word. This, in turn, could result in the same path being returned twice, which is incorrect.

• There could be two different paths \(p\) and \(p'\) in \(G\) from \(v\) to some \(n\), such that both \(\mathit{lab}(p)\in \mathcal{L}(\mathit{rgx})\) and \(\mathit{lab}(p')\in \mathcal{L}(\mathit{rgx})\), but the accepting runs of \(\mathcal{A}\) on these two words end up in different end states of \(\mathcal{A}\). Again, this could result with \(n\) and a path to it being returned twice.

Both issues are handled using the ReachedFinal set, which allows a solution to be recorded only once (lines 8–10). So, for each node that is a query answer, a single path is returned, without any restrictions on the automaton used for modeling the query.

The procedure continues until \(\textit{Open}\) is empty, meaning that there are no more states to expand and all reachable nodes have been found with a walk from the starting node \(v\). We note that Solutions stores the pointers to states in Visited, which define a solution path. So, for each tuple \((n,q,e,prev)\) in Solutions after running the algorithm, a path from \(v\) to \(n\) can be reconstructed using the \(prev\) part of search states stored in Visited. Furthermore, solutions can be enumerated once the algorithm terminates, or returned as soon as they are detected (line 10). This approach allows for a pipelined execution of the algorithm. Using BFS guarantees that the returned path is indeed shortest.

Example 2. Consider again the graph \(G\) in Figure [fig:introNew], and let \(Q\) be the query \[\mathit{ANY}\;\mathit{SHORTEST}\;\mathit{WALK}\;(\texttt{John},\;\texttt{follows}^+\cdot \texttt{lives},\;?x).\] So, we wish to find places where people that John (transitively) follows live. Considering Figure [fig:introNew], we see that Rome is such a place, and the shortest path reaching it starts with John, and loops back to the same node using the edges e1 and e2, before reaching Rome (via e8), as required. To compute the answer, Algorithm 2 first converts the regular expression \(\texttt{follows}^+\cdot \texttt{lives}\) into the following automaton:

To find shortest paths, we use the BFS version of Algorithm 2 and explore the product graph starting at \((\texttt{John},q_0)\). The algorithm then explores the only reachable neighbor \((\texttt{Joe},q_1)\), and continues by visiting \((\texttt{John},q_1), (\texttt{Paul},q_1)\) and \((\texttt{Lily},q_1)\). When expanding \((\texttt{John},q_1)\) the first solution, Rome, is found and recorded in Solutions. The algorithm continues by reaching \((\texttt{Anne},q_1)\) and \((\texttt{Jane},q_1)\) from \((\texttt{Paul},q_1)\). When the \((\texttt{Lily},q_1)\) node is then expanded, it would revisit \((\texttt{Jane},q_1)\) and \((\texttt{Paul},q_1)\), which are blocked in line 12. Expanding \((\texttt{Anne},q_1)\) would try to revisit Rome, but since this solution was already returned, we ignore it. The structure of Visited upon executing the algorithm is illustrated in Figure 4. Here we represent the pointer \(prev\) as an arrow to other search states in Visited, and annotate the arrow with the edge witnessing the connection. Notice that we can revisit a node of \(G\) (e.g. John), but not a node of \(G_\times\) (e.g. \((\texttt{Jane},q_1)\)). Since Solutions* contains only \((\texttt{Rome},q_F)\), we enumerate a single path, namely \(\texttt{e1}\rightarrow \texttt{e2}\rightarrow \texttt{e8}\). 0◻*

Enumerating the Results. Conceptually, paths can be enumerated by following backward edges from any state in the set Solutions created by Algorithm 2. For completeness, we now provide an enumeration procedure that can be applied to the set Solutions once Algorithm 2 had finished executing.

We note that solutions can be returned at the moment they are found (line 7), but we first construct the entire solution set for simplicity of presentation.

Algorithm 2 is fairly simple, but shows in detail how to manipulate the product graph in an efficient manner and how to handle arbitrary RPQs while finding a single (shortest) path between each pair of nodes in the result set. In addition, it eliminates duplicate results in the sense that, for every node \(n\) of \(G\), it only computes a single tuple of the form \((n,q,e,prev)\) in Solutions if \(q\) is accepting. In the following sections, we show how this approach can be extended for more complex path modes, starting with finding all shortest paths.

Runtime. Given that Algorithm 2 runs the standard BFS/DFS algorithm on the product graph to construct the set Solutions which allows enumerating the output paths, it runtime is \(O(|\mathcal{A}|\cdot |G|)\). Notice that, since we only return a single answer, this also means that the algorithm runs in output-linear delay.

3.2 ALL SHORTEST WALKS↩︎

We next show how to evaluate queries of the form \[\begin{gather} \label{lab:allwalk} Q = \textit{ALL SHORTEST WALK}\;(v,\mathit{rgx},?x). \end{gather}\tag{2}\] For this, we extend the BFS version of Algorithm 2 in order to find all shortest paths between pairs \((v,v')\) of nodes, instead of a single path — see Algorithm 5. The intuition simple: to obtain all shortest paths, upon reaching \(v'\) from \(v\) by a path conforming to \(\mathit{rgx}\) for the first time, BFS always does so using a shortest path. The length of this path can then be recorded together with \(v'\). When a new path reaches the same node \(v'\) later, it is also an answer to our query \(Q\) if its length equals the recorded length for \(v'\).

As before, we use \(\mathcal{A}\) to denote an NFA for \(\mathit{rgx}\). We will additionally require that \(\mathcal{A}\) is unambiguous (it has at most one accepting run for every word), which we need to ensure that we do not return the same path twice. This condition is easy to enforce for real-world RPQs [41], [42]. Indeed, a recent study of almost 150 million RPQs, found in over 900 million real-world SPARQL queries discovered that essentially all RPQs allow linear-time translations to unambiguous NFAs [43], although the worst-case blow-up is exponential [44], [45]. The main difference to Algorithm 2 is in the search state structure. A search state is now a quadruple of the form \((n,q,\mathit{depth},\mathit{prevList})\), where \(n\) is a node of \(G\) and \(q\) a state of \(\mathcal{A}\), the length of the shortest path from \((v,q_0)\) to \((n,q)\) is \(\mathit{depth}\), and \(\mathit{prevList}\) is a list of pointers to a previous search state that allows us to reach \(n\) via a shortest path from \(v\). We assume that \(\mathit{prevList}\) is a linked list, which we initialize empty, and to which we insert pairs of the form \(\langle \mathit{searchState},\mathit{edge}\rangle\) using add(). Intuitively, \(\mathit{prevList}\) allows us to reconstruct all shortest paths that reach a node.

When adding a pair \(\langle \mathit{searchState},\mathit{edge}\rangle\), we assume \(\mathit{searchState}\) to be a pointer to a previous search state, and \(\mathit{edge}\) will be used to reconstruct the path passing through the node in this previous search state. Again, Visited is a dictionary of search states with search key \((n,q)\). So, for each \((n,q)\), there can be at most one tuple \((n,q,\mathit{depth},\mathit{prevList})\) in Visited. This tuple will be returned by calling Visited.get(\(n,q\)) if it exists.

Algorithm 5 explores the product graph of \(G\) and \(\mathcal{A}\) using BFS, so Open is a queue. The main difference to Algorithm 2 is as follows: if a node \((n',q')\) of the product graph \(G_\times\) has already been visited (line 15), we do not discard the new path, but keep it if and only if it is shortest (line 17). In this case, the \(\mathit{prevList}\) for \((n',q')\) is extended by adding the new path (line 18). If a new pair \((n',q')\) is discovered for the first time, a fresh \(\mathit{prevList}\) is created (lines 20–23). As in Algorithm 2, we check for solutions after a state has been removed from \(\textit{Open}\) (lines 8–13). Basically, when a state is popped from the queue, the structure of the BFS algorithm assures that we already explored all shortest paths to this state. Notice that solutions can actually be returned before (i.e., after line 16 we can test if \(q'\in F\)). Returning answers when popping from the queue in lines 8–13 has the benefit that the paths are grouped for a pair \((v,n)\) of connected nodes, which is required by the GQL standard. Notice that this is also a natural place to perform enumeration of paths to achieve pipelined execution instead of enumerating them after the entire graph had been explored. As in Algorithm 2, we need to make sure that reaching the same node \(n\) via different accepting states of \(\mathcal{A}\) is permitted only when this results in a shortest path. To achieve this, ReachedFinal is now a dictionary storing pairs \(\langle n, \mathit{depth}\rangle\), where \(n\) is a solution node and \(\mathit{depth}\) the length of a shortest path from \(v\) to \(n\). We assume \(n\) to be the dictionary key. If a solution is reached the first time (lines 9–11) we record this information. When reaching the same node with another accepting path (lines 12–13), we record the solution only if the length of the path is shortest, that is, the same as the length already recorded. Finally, we can enumerate the solutions by a depth-first traversal the DAG stored in Visited, starting from the nodes in Solutions.

Interestingly, Algorithm 10 explores precisely the same portion of the product graph \(G_\times\) as Algorithm 2. Intuitively, the reason is that even if we only need to find one witnessing path for each \((v,v')\) where \(v\) is fixed and \(v'\) variable, neither algorithm can predict whether the next step is going to arrive at a new or already seen node \(v'\) without taking a look. (Indeed, even when answering queries with \(\mathit{ANY}\) \(\mathit{SHORTEST}\), we need to continue searching for other nodes \(v'' \neq v'\) that are reachable from \(v\) with a matching path.)

Enumerating the Results. Similarly as in Algorithm 2, results can be enumerated by following backward edges from any state in the set Solutions. However, we need some extra steps, since Algorithm 5 records multiple paths between a pair of nodes. The full enumeration procedure is as follows:

Notice that here a single search state in Solutions can produce multiple output paths. This is handled in lines 7–8 of GetAllPaths by traversing each node’s \(\mathit{prevList}\).

Runtime. For Algorithm 5 to work correctly, we need \(\mathcal{A}\) to be unambiguous. This can be achieved by a standard determinization procedure, but any algorithm that produces an unambiguous automaton is fine. Concerning run-time, Algorithm 5 indeed explores precisely the same subgraph of \(G_\times\) as Algorithm 2, since the nodes of \(G_\times\) that we revisit do not get added to Open again (lines 15–18). However, we can potentially add extra edges to Visited, so \(\llbracket Q\rrbracket_{G}\) can be exponentially larger [24], [46]. Additionally, when enumerating the output paths, each path is returned in time proportional to its length, which is known as output-linear delay [37]. It is optimal in the sense that, to return a path we need to at least write it down. In short, we can conclude that Algorithm 5 runs with \(O(|\mathcal{A}|\cdot |G|)\) pre-processing time, after which the results can be enumerated in time proportional to their total length.

3.3 ANY \(k\) WALKS and SHORTEST \(k\) WALKS↩︎

We now present an algorithm that returns \(k\) paths in increasing length. Given that ANY \(k\) is automatically solved by the SHORTEST \(k\) case, we will focus on the queries of the form: \[\begin{gather} \label{lab:shortestwalk} Q = \textit{SHORTEST}\;k\;\textit{WALK}\;(v,\mathit{rgx},?x). \end{gather}\tag{3}\] The code is described in Algorithm 6. We idea is similar as for ALL SHORTEST WALKS, but instead of keeping track of only the shortest walks from \((v,q_0)\) to every pair \((n,q)\) in the product graph \(G_\times\), we keep track of all paths of increasing lengths reaching each \((n,q)\), until we find at least \(k\) paths for \((n,q)\). Intuitively, this is similar to running Algorithm 5 (that is, we use BFS), but not discarding new paths when they are not shortest. To achieve this, our search state is going to be the tuple \((n,q,\mathit{depth},\mathit{numPaths},\mathit{prevList})\), where \(n\) is a node in the graph, \(q\) a state of the automaton for our query, \(\mathit{depth}\) the length of the paths reaching \((n,q)\) in the product graph \(G_\times\), while \(\mathit{numPaths}\) is the total number of paths of length \(\mathit{depth}\) from \((v,q_0)\) to \((n,q)\) and \(\mathit{prevList}\) the list of pointers to predecessors of \((n,q)\) on any such path. The parameter \(\mathit{numPaths}\) is used to keep count of up to \(k\) paths (to each \((n,q)\)) and to ensure termination when loops are present.

To achieve the correct behavior, Algorithm 6 uses Open as a queue and Visited as a dictionary of search states. We now use Visited so that its search key is the triple \((n,q,\mathit{depth})\), which will allow to track all the paths reaching \((n,q)\) of particular length. In addition, we will need the following three dictionaries which will allow us to keep track of encountered paths and tracking their total number:

• CountPaths is a dictionary searchable by the pair \((n,q)\), which stores the total number of paths reaching \((n,q)\) from \((v,q_0)\) in the product graph. (These paths can be longer than the shortest length.) This number will be used to prevent revisiting any \((n,q)\) with more than \(k\) paths (where \(k\) is specified by the query) in order to ensure that the algorithm always terminates.

• CountSolutions is a dictionary searchable by a node \(n\) of our graph. CountSolutions[\(n\)] stores the total number of paths reaching this node with a final state of the automaton.

• Solutions, a dictionary searchable by \(n\) which contains an ordered list of (pointers to) search states that are used to enumerate the solutions that reach \(n\). Order is needed so that shortest paths are returned before longer ones. We use the Solutions[\(n\)].append(current) to denote that current is added to the end of the list in Solutions[\(n\)].

We already gave the main idea: Algorithm 6 explores the product graph from \((v,q_0)\) using BFS, but keeps track of paths in increasing length until we find at least \(k\) of them. In detail, when a node \((n',q')\) of the product graph is revisited by path of any length, this is recorded as long as the total number of paths to \((n',q')\) is less than \(k\) (lines 17–28). Here, we consider two cases. First, when \((n',q')\) has already been visited by a path of length \(\mathit{depth}+1\) (lines 18–22), we increase the CountPaths[\((n',q')\)] by the total number of paths reaching \((n,q)\). Basically, by adding the single edge \(\mathit{edge}'\), we can traverse every such path, since we can reach \((n,q)\). We also update the count of paths to \((n',q')\) of length \(\mathit{depth} + 1\) by updating the \(\mathit{numPaths}'\) parameter of the search state, and we add \(\langle \textit{current}, \mathit{edge}'\rangle\) to \(\mathit{prevList}'\) thus updating its value in Visited. The second case, when a path to \((n',q')\) of length \(\mathit{depth}+1\) is considered for the first time (lines 24–28) is similar, but this time we also update Visited and Open with the newly created search state in order to continue looking for more solutions. Notice that Algorithm 6 always terminates, since in line 17 we check that no more than \(k\) paths to each pair \((n',q')\) in the product graph are added. In particular, this means that no edge in the product graph can be traversed more than \(k\) times. In lines 22 and 27 we can end up with more than \(k\) paths to \((n',q')\) due to the existence of many paths of the same length. When enumerating solutions, we need to keep track of this as explained below.

The solutions are recorded in lines 12–15. We ensure that, when \(k\) solution paths to a particular node \(n\) have already been discovered, no new solutions are recorded for \(n\) (line 13). Given that we run BFS, and assuming that Solutions[\(n\)].append(current) creates an ordered list, paths reaching node \(n\) will be given in increasing length. To achieve pipelinining, we could check whether CountSolutions[\(n\)] \(> k\) after line 15 and immediately return \(k\) paths to \(n\). Notice that since more than \(k\) paths might be recorded (if CountSolutions[\(n\)] + \(\mathit{numPaths}\) \(> k\) in line 15), when enumerating the paths to any particular \(n\) we should return \(k\) path if more than \(k\) are available. It is also important to notice how this might require extra computation since we cannot return the first batch of shortest paths before finding all \(k\) shortest paths. Of course, returning the paths as they are encountered in line 12 could potentially result in the results not being grouped by endpoints of the paths, as required by the GQL standard. Next we illustrate how Algorithm 6 works by an example.

Example 4. Consider again the graph of Figure [fig:introNew] and the following query: \[Q = \mathit{SHORTEST}\;5\;\mathit{WALK}\;(\texttt{Joe},\;\texttt{follows}^*\cdot \texttt{works},\;?x).\]

Algorithm 6 creates the structure in Figure 7. Here, each search state is depicted as a tuple \((n,q,\mathit{depth},\mathit{numPaths})\) with the \(\mathit{prevList}\) being represented by outgoing edges. Above each search state, we show the total number of paths reaching the node \((n,q)\) in the product graph at this stage of the execution; namely, the content of CountPaths[\((n,q)\)].

The algorithm starts in \((\texttt{Joe},q_0)\) and records that there is a single path of length zero to this node. Then, three paths of length one are discovered, going to \((\texttt{Paul},q_0)\), \((\texttt{Lily},q_0)\) and \((\texttt{John},q_0)\), respectively.

Expanding \((\texttt{Paul},q_0)\) now visits \((\texttt{Anne},q_0)\) and \((\texttt{Jane},q_0)\) with paths of length two. If we expand \((\texttt{Lily},q_0)\), we find a second (shortest) path to \((\texttt{Jane},q_0)\), and a second (non-shortest) path to \((\texttt{Paul},q_0)\). Since this is a new path to this node of the product graph, the \(\mathit{numPaths}\) component of \((\texttt{Lily},q_0,1,1)\), that is, 1, gets added to CountPaths[\((\texttt{Paul},q_0)\)], correctly tracking the total number of paths to be two: one of length one and another of length two. Next, we expand \((\texttt{John},q_0)\) to \((\texttt{Joe},q_0)\), but now with a path of length two. Again, this is a new path to this node of the product graph. Analogously to \((\texttt{Paul},q_0)\), we add 1 to CountPaths[\((\texttt{Joe},q_0)\)], for which we now have two paths: one of length zero and another of length two.

Next, we explore paths of length three. Here \((\texttt{ENS}\;\texttt{Paris},q_F)\) is reached with three paths, so CountSolutions[ENS``Paris] also gets updated to three. From \((\texttt{Paul},q_0,2,1)\) and from \((\texttt{Joe},q_0,2,1)\), the algorithm does analogous steps as for \((\texttt{Paul},q_0,1,1)\) and \((\texttt{Joe},q_0,0,1)\), respectively, resulting in new values for Anne, Jane, Paul, Lily, and John. However, since we still haven’t found five paths required by the query in any of these nodes, the exploration continues.

For paths of length four, the same nodes as before are being explored, but now with paths of longer lengths. When we reach \((\texttt{ENS}\;\texttt{Paris},q_F,4,2)\) we actually found five solutions for ENS``Paris. Notice that the dictionary Solutions[ENS]* contains two search states allowing for enumeration: \((\texttt{ENS}\;\texttt{Paris},q_F,3,3)\) and \((\texttt{ENS}\;\texttt{Paris},q_F,4,2)\). We can output the three paths for the first element of the list (paths of length three) and only the two paths of length four. (If there were more results of length four, we would only need to output two of them.)*

Despite that we already have all the results, the algorithm will continue until each node of the product graph is visited at least five times or no further expansion is possible. Indeed, in principle, it is possible that there are other nodes we will still reach in state \(q_F\). For example, if there were two more nodes in the graph: Ted and Berkeley, with edges stating that Anne follows Ted and that Ted works in Berkeley, then we would need to continue this exploration until a sufficient number of paths from Joe to Berkeley had been found.

However, when we would expand \((\texttt{Anne},q_0,4,1)\), we discover that we only reach \((\texttt{ENS}\;\texttt{Paris})\), for which we already found the required five paths, so the exploration stops there. For the same reason (but with Jane instead of ENS Paris, the expansion no longer follows e6 out of \((\texttt{Paul},q_0,4,1)\) to add \((\texttt{Jane},q_0,5,1)\). 0◻

Enumeration and Runtime. The enumeration of results is similar as in Section 3.2. The main difference is that now Solutions is a dictionary which contains, for each solution node \(n\), a search state that needs to be enumerated using the same procedure as in Section 3.2 when generating all shortest walks. Since the search states in Solutions\([n]\) are added in order of increasing length, these will even be enumerated as required by the GQL standard. Since the algorithm sometimes discovers a number of paths of the same length in bulk, the algorithm sometimes finds more than the required number (for instance in lines 22 and 27 of Algorithm 6). Therefore, when returning paths, we simply need to keep count of the exact number we return. Enumeration with output-linear delay is also very similar. There is a small change in the pre-processing phase, which can now run in time \(O(k\cdot |\mathcal{A}|\cdot |G|)\), since each node in the product graph is allowed to be revisited up to \(k\) times (line 17 of Algorithm 6, and as illustrated in Example 4).

3.4 SHORTEST \(k\) GROUPS↩︎

We now explain how to evaluate queries of the form \[\begin{gather} \label{lab:shortestgroups} Q = \textit{SHORTEST}\;k\;\textit{GROUPS WALK}\;(v,\mathit{rgx},?x)\;. \end{gather}\tag{4}\] The task is to return, for each node \(v'\) such that the \(k\)-th smallest length of paths from \(v\) to \(v'\) that match \(\mathit{rgx}\) is \(\ell\) (see Section 2 for a formal definition), all tuples \((v,v',p)\) such that \(p\) is matching path from \(v\) to \(v'\) of length at most \(\ell\).

The solution is presented in Algorithm 8. It follows a similar logic as our solution for SHORTEST \(k\) WALK, but now it tracks how many different lengths of paths reach each pair \((n,q)\) in the product graph. To do this, we need to make some changes to search states. Now they are tuples of the form \((n,q,\mathit{depth},\mathit{prevList})\), where \(n\) is the graph node, \(q\) a state of the automaton \(\mathcal{A}\), and \(\mathit{depth}\) the length of the path in the product graph that starts in \((v,q_0)\) and ends in \((n,q)\) (where \(q_0\) is the start state of \(\mathcal{A}\)). As before, \(\mathit{prevList}\) is a list of pointers to search states that are immediate predecessors of \((n,q)\) on this path. As in Section 3.3, we assume that Visited is a dictionary of search states that has \((n,q,\mathit{depth})\) as the search key. We also use the following three data structures, which we use to track the number of groups and solutions encountered during the execution of the algorithm:

• NumGroups, a dictionary searchable by \((n,q)\) contains a pair \((\mathit{numGrps}, \mathit{lastDepth})\), where \(\mathit{numPaths}\) is the number of different path groups that have visited \((n,q)\) thus far, while \(\mathit{lastDepth}\) is the length of paths in the last group that visited \((n,q)\) at this point. We use the notation NumGroups[\((n,q)\)] = \((\mathit{numGrps},\mathit{lastDepth})\).

• NumFinalGroups, a dictionary searchable by \(n\) again contains a pair \((\mathit{numGrps}, \mathit{lastDepth})\), where the numbers have similar meaning as in NumGroups, but now track the number of groups to the node \(n\) reached via any final state of the automaton, and the length of paths in the final group discovered thus far. We use the notation NumGroups[\(n\)] = \((\mathit{numGrps},\mathit{lastDepth})\).

• Solutions, a dictionary searchable by \(n\), which contains an ordered list of (pointers to) search states that are used to enumerate the solutions that reach \(n\). The ordering in Solutions is needed so that shortest paths are returned prior to longer ones. We use the syntax Solutions[\(n\)].append(sState) to denote that sState is added to the end of the list in Solutions[\(n\)].

Algorithm 8 starts from \((v,q_0)\) and scans its neighbors \((n',q')\) in the product graph using the triple \((n',q',\mathit{depth}+1)\) as the search key. Whenever \((n',q')\) was not visited at \(\mathit{depth}+1\) (lines 24–31), a new group is created, making sure that no more than \(k\) groups have been defined (lines 25–26). We remark that we might have already visited \((n',q')\) with paths of smaller length, so we need to check that no unnecessary groups will be created. If we already visited \((n',q')\) at \(\mathit{depth} + 1\), we add these paths since they are paths of an existing group (lines 21–23). We check for solutions after popping from the queue (lines 9–19). The first time we detect that a node \(n\) is a solution, we update the dictionary Solutions, and update NumSolutions[\(n\)] to record that a single group had been detected thus far, and record the length of paths in this group (lines 10–12). When a node \(n\) is discovered as a query answer again, we might be visiting it either with paths of a previously undiscovered length (lines 15–17), or with ones of length that we had already seen (lines 18–19). In the former case, we check that only \(k\) groups will be created and record the new group, adding its paths to Solutions[\(n\)]. In the latter case, we add the discovered paths to the final group for \(n\).

If one would like to achieve pipelining, one can check in line 15 whether we are trying to create the group \(k+1\) for the first time and in that case enumerate the results. If not, we can simply use Solutions when the algorithm terminates, to see which nodes are in the solution set and enumerate their respective groups. Due to the fact that we use BFS style exploration, solutions have always been added in increasing order of path length. As a final remark, notice that we can have \(k\) groups to some nodes \(n\) reached by a final state of our automaton (stored in NumFinalGroups[\(n\)]), but we might still need to discover \(k\) groups to different pairs \((n,q')\) in the product graph, since these might lead to solutions for nodes other than \(n\). This is the reason why we keep track of NumGroups[\((n,q)\)]. Next, we illustrate how the algorithm operates via an example.

Enumeration and Runtime. The enumeration procedure in this case is identical as in Section 3.3, but now more items might be present in Solutions\([n]\). Output-linear delay is guaranteed by this method of enumeration and no tracking of the number of returned solutions is needed due to the fact that each solution within the group needs to be returned. Regarding the pre-processing phase, a bound of \(O(k\cdot |\mathcal{A}|\cdot |G|)\) is achieved as when comparing a single shortest to all shortest path runtime. Namely, for each group here we run the all-shortest algorithm for every path length in the group. As in that case, many more solutions are potentially recorded compared to the case of shortest \(k\) paths.

4 TRAIL, SIMPLE, and ACYCLIC↩︎

We now devise algorithms for finding trails, simple paths, or acyclic paths. It is well known that even checking whether there is a single path between two nodes that conforms to a regular expression and is a simple path, trail, or acyclic path is NP-complete [9]–[11], [47], [48], even for undirected graphs [49], so we do not know any worst-case polynomial time algorithms. These hardness results already hold for fixed regular expressions, such as \((aa)^*\) or \(a^*ba^*\) [9], [47], [48]. On the other hand, regular expressions for which these problems are NP-hard are rare in practice [38], [41], [43], [50] and, moreover, regular expressions for which these problems are tractable can be evaluated by cleverly enumerating paths in the product graph [38], [51]. Our algorithms will follow this intuition and prune the search space whenever possible. In the worst case, all such algorithms will be exponential but we will show that, on real-world graphs, the number of paths is manageable. (That said, queries that ask to return a potentially large number of paths are at the responsibility of the user. If the user wants to see a large output, the system should do its best to give it to them.) Our pruning technique technique will ensure that all dead ends are discarded and we keep the computational overhead under control. We begin by showing how to find all trails and simple/acyclic paths.

4.1 Returning All Paths↩︎

We start with queries of the form \[Q = (\mathit{ALL}\;\mathit{SHORTEST})?\; \mathit{res}\; (v,\mathit{rgx},?x)\] where the restrictor \(\mathit{res}\) is \(\mathit{TRAIL}\), \(\mathit{SIMPLE}\), or \(\mathit{ACYCLIC}\). Algorithm 10 shows how to evaluate such queries. Intuitively, the algorithm explores the product graph by enumerating all paths starting in \((v,q_0)\) but pruning as soon as the respective paths are no longer trails, simple, or acyclic. This time, our search state is a tuple \((n, q, \mathit{depth}, e, \mathit{prev})\), where \(n\) is a node in the input graph, \(q\) is a state automaton of the automaton \(\mathcal{A}\) for \(\mathit{rgx}\), the length of a shortest path from \((v,q_0)\) to \((n,q)\) in \(G_\times\) is \(\mathit{depth}\), the edge \(e\) is the edge we used to arrive in node \(n\), and \(\mathit{prev}\) is a pointer to another search state stored in Visited. The latter is a set containing search states that we have already visited. Similarly to Algorithm 5, we use a dictionary ReachedFinal containing pairs \((n,\mathit{depth})\), with key \(n\). Here, \(n\) is a node reached in some query answer and \(\mathit{depth}\) is the length of a shortest path from \(v\) to \(n\) in \(G\).

The execution is similar to Algorithm 2, but Visited is not used to discard solutions. Instead, when checking whether the current node can be extended to a neighbor (lines 18–21), we call isValid, which checks whether restrictor \(\mathit{res}\) allows the path to the current node \(n\) in Visited to be extended to the next node \(n'\). Notice that we need to check whether the path in the original graph \(G\) satisfies \(\mathit{res}\), and not the path in the product graph. If isValid confirms that this extension to \(e'\) still satisfies \(\mathit{res}\), we add the new search state to Visited and Open (line 21). When popping from Open, we also check if a potential solution is reached (line 8).

If \(\mathit{ALL}\) \(\mathit{SHORTEST}\)is not present in the query, we simply add the newly found solution. If it is, we need to make sure to add only shortest paths. The ReachedFinal dictionary ReachedFinal is used to track the already discovered nodes. If the node is seen for the first time, the dictionary is updated and a new solution is added (lines 11–13). Upon discovering the same node again (lines 14–17), a new solution is added only if it is shortest. Once all paths have been explored (\(\mathit{Open}=\emptyset\)), we can enumerate the solutions, just as in the previous algorithms.

Enumeration and Runtime. When dealing with \(\mathit{TRAIL}\), \(\mathit{SIMPLE}\), and \(\mathit{ACYCLIC}\), we need to distinguish between the complexity to construct Solutions and enumerating the output once Solutions has been constructed. Constructing Solutions takes time \(O\big((|\mathcal{A}|\cdot |G|)^{|G|}\big)\), which is exponential. Unless P \(=\) NP, getting rid of the exponential is impossible, since already deciding whether a trail, simple path, or acyclic path exists that matches a (fixed) regular expression is NP-complete [11], [48], [52]. The algorithm for constructing Visited and Solutions terminates since eventually all paths that are valid according to the restrictor \(\mathit{res}\) will be explored, and no new search states will be added to Open. Once Visited is constructed, the enumeration algorithm is essentially the same as in Section 3.1. Output-linear complexity of enumeration (after Solutions has been constructed) is achieved analogously to Algorithm 2 since each solution defines a single path.

Due to the fundamental NP-hardness of the problem, the pipelined version of the algorithm does not achieve linear delay or output-linear complexity. Indeed, the worst-case delay or computation time for the next output is exponential, which is unavoidable unless P \(=\) NP.

4.2 Adding \(\mathit{ANY}\) and \(\mathit{ANY}\) \(\mathit{SHORTEST}\)↩︎

Treating queries of the form \[Q = \mathit{ANY}\;(\mathit{SHORTEST})?\; \mathit{res}\; (v,\mathit{rgx},?x)\] can be done with minimal changes to Algorithm 10. Namely, we would use ReachedFinal as a set that stores the node first time a solution is found in order to not repeat any results. In addition, we would replace lines 8–17 with:

Enumeration and Runtime. The analysis is the same as for Algorithm 10. Its worst-case runtime is \(O\big((|\mathcal{A}|\cdot |G|)^{|G|}\big)\), which is also the best known runtime due to NP-completeness of the problem [11]. Enumeration is analogous to Algorithm 10.

4.3 \(\mathit{SHORTEST}\) \(k\) and \(\mathit{ANY}\) \(k\)↩︎

Here we show how to deal with queries of the form \[\mathit{SHORTEST}\;k\;\mathit{res}\;(v,\mathit{rgx},?x)\;,\] where \(\mathit{res}\) is one of \(\mathit{TRAIL}\), \(\mathit{SIMPLE}\), or \(\mathit{ACYCLIC}\). We note that solving these cases also solves the \(\mathit{ANY}\) \(k\) case with a restriction to \(\mathit{TRAIL}\), \(\mathit{SIMPLE}\), or \(\mathit{ACYCLIC}\).

The idea is presented in Algorithm 12 and is similar to finding all paths according to one of the three restrictors (Algorithm 10). The difference is that we only track up to \(k\) solutions for each node \(n\) that is reachable from \(v\) by a path that matches \(\mathit{rgx}\). As before, Visited will be a set allowing us to reconstruct solution paths. To find shortest paths, we require Open to be a queue, meaning that we do a BFS-style exploration. The structure of search state is again \((n,q,e,\mathit{prev})\), with \(n\) a node in the graph, \(q\) a state of the automaton, \(e\) an edge used to reach \(n\) and \(\mathit{prev}\) a pointer to the predecessor search state in Visited used to reach the current state. Additionally, we will use the following structures to keep track of \(k\) shortest paths for each reachable node:

• Reachable is a set that keeps track of each node \(n\) reachable from \(v\) by our query.

• ReachedFinal is a dictionary with \(n\) being the search key and storing the number of paths reaching \(n\) with an accepting state. For example, ReachedFinal[\(n\)] = 5 means we found five paths that are an answer to our query reaching the node \(n\).

• Solutions is a dictionary with \(n\) being the search key. Each entry Solutions[\(n\)] stores a list of search states which visit the node \(n\) via an accepting state of our automaton.

Enumeration and Runtime. Basically, we do the same exploration as in Algorithm 10, but when we find a solution, we check that no more than \(k\) shortest solutions are stored (lines 8–15). The program relies on the unambiguity on \(\mathcal{A}\), which can be achieved by determinizing it. Since we need to enumerate all the paths, the program’s worst-case complexity is again \(O\big((|\mathcal{A}|\cdot |G|)^{|G|}\big)\). Notice that no factor \(k\) is present in this bound since it already includes exploring all possible paths and we only need to count the number of solutions to each reached node. For enumeration, once Solutions is computed, we can traverse the list Solutions\([n]\), which stores a search state with a single path which can again be enumerated with output-linear delay.

Similarly to Algorithm 10, output-linear delay for pipelined execution is impossible unless P \(\neq\) NP.

4.4 Shortest \(k\) Groups↩︎

The final class of queries we cover is of the form \[\text{\mathit{SHORTEST}k \mathit{GROUPS}\mathit{res} (v,\mathit{rgx},?x)},\] where \(\mathit{res}\) is one of \(\mathit{TRAIL}\), \(\mathit{SIMPLE}\), \(\mathit{ACYCLIC}\). The corresponding algorithm, shown in Algorithm 13 is virtually identical to Algorithm 12, but keeps track of groups instead of paths. Its main data structures are:

• Reachable is a set that keeps track of each node \(n\) reachable from \(v\) by our query.

• Groups is a dictionary using nodes \(n\) of our graph as the search key, and storing two components: (i) Groups[\(n\)].numGroups is the number of different path lengths that we discovered reaching \(n\) in a final state of the automaton; and (ii) Groups[\(n\)]. is the length of the longest/last path we discovered reaching \(n\) in a final state of the automaton.

• Solutions is a dictionary with search key \(n\). Each entry Solutions[\(n\)] is a list of search states that visit the node \(n\) in an accepting state of our automaton.

To ensure that only \(k\) groups are returned for each \(n\), we limit Groups[\(n\)].numGroups to at most \(k\) (line 14). When a solution \(n\) is discovered for the first time (lines 9–13), the first solution group for \(n\) is created. If we already discovered \(n\) and no more than \(k\) groups have been created (line 14), we consider the two viable options: (i) we are creating a new group, in which case the recorded number of solution groups needs to be strictly less than \(k\) (lines 15–18); or (ii) we are extending the last group we created (lines 19–20). For correctness, we need the automaton to be unambiguous and the complexity and enumeration is the same as for Algorithm 12.

5 Syntax for Returning Paths and Implementation Details↩︎

PathFinder is implemented as the path processing engine of MillenniumDB, an open-source graph database engine [53]. MillenniumDB provides the infrastructure necessary to process generic queries such as RPQs and takes care of parsing, generation of execution plans, and data storage, while PathFinder executes path queries as described in this paper. MillenniumDB supports both the property graph data model coupled with an expressive fragment of Cypher [7] and RDF with a fairly complete implementation of SPARQL 1.1 query (see the system documentation for a list of currently unsupported features). The system also provides updates and a light transactional management mechanism in terms of multi-version concurrency control with a single writer thread. While the Cypher-like syntax supports returning paths as described in this paper, we also extended the SPARQL syntax to allow it.

Syntax for Returning Paths in Property Graphs. We extend MillenniumDB’s Cypher-like syntax with a new construct that allows returning paths in RPQ query answers by adding patterns of the following form into the MATCH clause:

Here src and tgt are either graph nodes or variables, PathMode can be any GQL path mode, PathVariable is the variable used to bind and return the path, and RegularPathQuery is an arbitrary regular expression constructed from edge labels (\(\mathit{rgx}\) in Section 2). MillenniumDB uses a the =[]=> arrows for path queries, instead of the usual -[]-> used in Cypher and GQL. For example, MillenniumDB’s syntax for a query that returns all shortest paths starting at node Joe in Figure [fig:introNew] that match :follows+/:works is

    MATCH (?src  {name:"Joe"})=[ALL SHORTEST ?p :follows+/:works*]=>(?tgt)
    RETURN ?tgt.name, ?p

Here, we assume that nodes in Figure [fig:introNew] have an attribute name that identifies their value as commonly used in property graphs.

Extending SPARQL with Path Returning Capabilities. To support returning paths in SPARQL, we introduce a new triple pattern with the following abstract definition:

Similarly as in the case of property graphs, src and tgt are either nodes (i.e., IRIs or literals) or variables, PathMode is a GQL path mode, PathVariable is the variable used to bind and return the path, and PropertyPath is a property path pattern. Our implementation currently supports property path patterns that do not use negated property sets. Furthermore, we do not yet implement the \(\mathit{TRAIL}\) mode, as it is not clear whether a triple in RDF represents an edge, or whether a more subtle definition should be made, as in the case of property graphs. Path variables are used only to return paths. Such triple patterns can then be added to the SPARQL WHERE clause. An example query that extracts the names of people connected to Joe in an RDF dataset similar to the one in Figure [fig:introNew] would be:

SELECT ?name ?p
WHERE {
  ex:Joe ANY SHORTEST (:follows+/:works AS ?p) ?tgt .
  ?tgt :hasName ?name .
}

Data Access. By default, MillenniumDB stores graph data on disk using B+trees and loads the necessary pages into a main memory buffer during query execution. The B+trees we use are clustered on initial loading of data and their leaves store the required relations using node/edge IDs. All literal values (strings, numbers, etc.) are also represented via numeric IDs and converted to their original representation as needed. All B+trees in MillenniumDB are accessed using the standard linear iterator interface used in relational databases [54]. Depending on the data model used, a different set of relations is stored as we explain next.

Property Graphs.

To represent property graphs, MillenniumDB indexes several relations, however, our algorithms only use the following two:

The first relation allows us to find neighbors of a certain node reachable by an edge with a specific label, as used, for instance, in Algorithm 2 (line 14). The second table keeps track of nodes that are materialized in the database. In essence, the table Nodes is only used when checking whether the start node of an RPQ actually exists in the database (see e.g., Algorithm 2, line 9).

Two-Way Navigation for Property Graphs.

All algorithms in this paper can be easily extended with the ability to traverse edges backwards, as required, for instance, by C2RPQs [8] and SPARQL property paths [6]. To support this, we also index the inverse Edges relation \(\mathrm{\small Edges^-(NodeTo, Label, NodeFrom, EdgeId)}.\) Using this index, all of the described algorithms can be extended by using the EDGES\(^-\) table whenever looking for a neighbor accessed via a backward edge.

RDF Data.

When storing RDF data we use four different permutations of the \(\mathrm{\small Triples(s,p,o)}\) relation. Most important for us are the \(\mathit{SPO}\) and \(\mathit{OPS}\) permutations, which mimic the EDGES and EDGES\(^-\) relations from property graphs.

Pipelined Execution. In PathFinder, all the algorithms are implemented in a pipelined fashion using linear iterators. This means that the solution is returned to the user as soon as it is encountered. This requires, for instance, that the main while loop of Algorithm 2 be halted as soon as a new solution is detected in lines 9–10, and similarly for Algorithm 10. In the case of Algorithm 5 the situation is a bit more complex, as solutions can be detected while scanning the neighbors (lines 14–23), instead of upon popping an element from the queue (lines 11-13). All of these issues can be resolved by noting that linear iterators for neighbors of a node can be paused, and their execution resumed. For completeness, we include expanded pseudo-code for pipelined execution of our algorithms in our online appendix [55]. The main benefit of the pipelined execution is that paths can be encountered on demand and the entire solution set does not need to be constructed in advance.

Query Variables. Throughout the paper, we assumed that the RPQ part of our query takes the form \((v,\mathit{rgx},?x),\) where \(v\) is a node identifier, and \(?x\) is a variable. In other words, we were searching for nodes reachable from a fixed node \(v\). It is straightforward to extend our algorithms to patterns of the form \((v,\mathit{rgx},v')\), where both endpoints of the path are known: we can run any of the algorithms as described in the paper, and check whether \(v'\) is a query answer. The case when both ends are variables; namely, \((?x,\mathit{rgx},?y)\), is more challenging to handle, and the techniques we developed only allow supporting it by iterating over all relevant start nodes. Some immediate optimizations are possible here; for instance, by only considering start nodes of edges labeled by transitions that leave the initial state of the automaton for \(\mathit{rgx}\). We leave the study of this problem for future work.

6 Experimental Evaluation↩︎

We empirically evaluate PathFinder and show that the approach scales on a broad range of real-world and synthetic data sets and queries. We describe our experimental setup and discuss of the obtained results. For our code, data and queries see [29].

6.1 Experimental Setup↩︎

We perform three sets of experiments:

• Pokec, which tests the effect of path length on performance;

• Wikidata, which tests the performance over a large real-world graph and user supplied queries; and

• Diamond, which tests the effect of having a large number of paths in the graph.

Next we describe each set of experiments in more detail.

(1) Pokec. This set of experiments uses the Pokec social network graph from the SNAP graph collection [56]. Pokec is a Slovakian social network which records (directed) user connections, similar to the graph of Figure [fig:introNew], but with a single type of edge label (we call this label follows). The graph contains around 1.6 million nodes and 30 million edges. In our experiment, we select the node that is median in terms of a simple centrality measure,³ and traverse follows-edges from this node. We run our algorithms until 100,000 paths that witness these connections are returned. We explore paths of length 1 through \(k\), where \(k\) ranges from 1 to 12. Longer paths are not very interesting in this graph, since the graph’s diameter is 11. We pair these queries with the path modes described in Section 2. The idea behind this experiment is to test what happens with query performance as we seek longer paths in a real-world graph of intermediate size.

(2) Wikidata. Here, we want to check performance over a large real-world graph. For this we use Wikidata [25] and queries from its public SPARQL query log [26]. We use WDBench [57], a recently proposed Wikidata SPARQL benchmark. WDBench provides a curated version of the data set based on the truthy dump of Wikidata [58], which is an edge-labeled graph with 364 million nodes and 1.257 billion edges, using more than 8,000 different edge labels. The data set is publicly available [59]. WDBench provides multiple sets of queries extracted from the Wikidata’s public endpoint query log. We use the Paths query set, which contains 659 2RPQs patterns.⁴ From these, 592 have a fixed starting point or ending point (or both), while 67 have both endpoints free. We note that these queries require general regular expressions which cannot be expressed in some of the tested systems. The 659 patterns are then used in our tests under the restrictor and selector options described in Section 2.

(3) Diamond. Here we test what happens when there is a large number of paths present in our graph. The database we use, taken from [24], is presented in Figure 14. The queries we consider look for paths from start to end using a-labeled edges. Notice that all such paths are, at the same time, shortest, trails and simple paths, and have length \(2n\). Furthermore, there are \(2^n\) such paths, while the graph only has \(3n+1\) nodes and \(4n\) edges. We test our query with the path modes from Section 2, while scaling \(n\) (and thus path length) from \(1\) to \(40\). While returning all these paths is unfeasible for any algorithm, we test whether a portion of them (100,000 in our experiments) can be retrieved efficiently.

Tested Systems. In all the experiments, we use the property graph version of PathFinder. Recall that PathFinder supports both BFS traversal and DFS traversal. We denote the two versions as PathFinder-BFS and PathFinder-DFS, respectively. When there is only one algorithm (e.g., for all shortest walks), we simply write PathFinder. All the versions assume the data to be stored on disk and being buffered into main memory as required. In order to compare with state of the art in the area, we selected six publicly available graph database systems that allow for benchmarking with no legal restrictions. These are:

• Neo4j: Neo4J Community Edition version 5.26.26 [17];

• Nebula: NebulaGraph version 3.5.0 [18];

• Kuzu: Kuzu version 0.0.6 [20];

• Jena: Jena TDB version 4.1.0 [15];

• BlazeGraph: Blazegraph version 2.1.6 [14]; and

• Virtuoso: Virtuoso version 7.2.6 [16].

From these systems, Neo4j and Nebula use the \(\mathit{ALL}\) \(\mathit{TRAIL}\) semantics by default. Neo4j and Kuzu support \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) and \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) modes. Kuzu also supports \(\mathit{ALL}\) \(\mathit{WALK}\), but limits paths to length at most 30. SPARQL systems (Jena, BlazeGraph, Virtuoso) support arbitrary RPQs but do not return paths. Following the SPARQL semantics [6], they detect pairs of nodes connected by an arbitrary walk. A brief summary of supported features can be found in Table ¿tbl:tab:intro? in the Introduction. Other systems we considered are DuckDB [21], Oracle Graph Database [60] and Tiger Graph [61], which support (parts of) SQL/PGQ. Unfortunately, [60] and [61] are commercial systems with limited free versions, while the SQL/PGQ module for DuckDB [21] is still in development. We note that none of the existing systems support path variables to the extent that our system does. This is essentially because SPARQL systems don’t have path variables and systems based on GQL or SQL/PGQ don’t deal with all regular expressions or cap the maximal path length as a hardcoded value. Since the current GQL standard consider nesting of Kleene star as a language opportunity, existing systems simply don’t implement it. PathFinder shows that, when it comes to path variables, nesting of Kleene star is, in principle, not an issue.

Experimental Setup. The experiments were run on a commodity server with an Intel®Xeon®Silver 4110 CPU, and 128GB of DDR4/2666MHz RAM, running Linux Debian 10 with the kernel version 5.10. The hard disk used to store the data was a SEAGATE model ST14000NM001G with 14TB capacity. Note that this is a classical HDD, and not an SSD. Custom indexes for speeding up the queries were created for Neo4j, Nebula and Kuzu, and the four systems were run with the default settings and no limit on RAM usage. Jena, BlazeGraph, Virtuoso and PathFinder were assigned 64GB of RAM for buffering. Since we run large batches of queries, these are executed in succession, in order to simulate a realistic load to a database system.

6.2 Pokec: Scaling Path Length↩︎

Here we take a highly connected graph of medium size and test what happens if we ask for paths of increasing length. All tested systems easily loaded this data set. Given that SPARQL systems cannot return paths, we compare with them when the system is only asked to retrieve the reachable nodes (the ENDPOINTS experiment). Given that other systems only support trails and walks, we retrieve paths according to these two modes. Our results are presented in Figures 15 and 16.

ENDPOINTS. Figure 15 (left) shows our results for retrieving reachable nodes, that is, the set of nodes \(v'\) for that bind to \(?x\) in RPQs of the form \((v,\mathit{rgx},?x)\). We see that SPARQL systems handle this use case relatively well (only BlazeGraph timed out for the largest path length). Likewise, Neo4j shows no timeouts. In contrast, Nebula and Kuzu start timing out for paths of length 5 and 6, respectively.

PathFinder and several other systems exhibit a spike in runtime for lengths 3 and 4. For PathFinder, this happens due to a large portion of pages being fetched from disk into the buffer. Once the data needed to compute 100,000 paths has been fetched, the performance stabilizes. PathFinder shows superior performance (around 10x–100x faster than the other systems) once the runtime stabilizes when all data required to run the queries is loaded from disk. We note that PathFinder does not use caching but rather recomputes the query for each length larger than 5.

WALKS. The results for \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) are given in Figure 15 (right). As we can see, Kuzu has a highly performant algorithm that handles this use case well, while Neo4j times out quickly. PathFinder is around 100x faster than all other systems, with stable performance for longer lengths. Again, the performance spike for PathFinder around lengths 3 and 4 happens because much data is still being loaded onto disk during these first experiments. This data stays in the buffer for longer paths, which causes the run-time to stabilize. The case of \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) is presented in Figure 16 (right). The picture here is similar. PathFinder scales very well, while no other system is able to handle paths of length 6 or more within the 1-minute timeout. The data loading spike is again present for length 3 and 4, but it still results in fast performance. Whereas the present experiment aims at returning the paths of length at most \(k\) (for \(k = 1 , \ldots,12\)), we also conducted an experiment where we look for paths of length precisely \(k\). Since the latter experiment generated virtually identical plots, we omit it. Overall, we can conclude that PathFinder offers stable performance, and unlike the other systems, does not get into issues as the path lengths increaase. Nebula is not used in this experiment since it does not support the \(\mathit{WALK}\) semantics.

TRAILS. The results for \(\mathit{ALL}\) \(\mathit{TRAIL}\) are shown in Figure 16 (left). The performance of Neo4j is significantly better here than for \(\mathit{SHORTEST}\) \(\mathit{WALK}\), with timeouts occurring later. Nebula started timing out for paths of length 5. For PathFinder, we see the performance of PathFinder of the BFS version of Algorithm 10. For the DFS version (not shown in the figure) the picture is similar. As in other experiments, we see that PathFinder handles the query load with no major issues. It is about 100x faster than all other systems.

6.3 Wikidata: The Effect of Big Graphs↩︎

In this experiment, we test whether returning paths is feasible in big real-world graphs. We encountered significant issues when loading the data set into some engines. For Nebula we ran into the well documented storage issue NebulaIssue? that we could not resolve, while Kuzu ran out of memory while loading the data set. We even tried splitting the data set into smaller chunks, with one file for each distinct edge label. In this case we only managed to load the ten biggest edge sets into Kuzu, but this amounts to less than a third of the total number of edges, so we excluded Kuzu from this experiment. The systems that could load the data were PathFinder, Neo4j, BlazeGraph, Jena, and Virtuoso. Given that Neo4j only supports the \(\mathit{WALK}\) and \(\mathit{TRAIL}\) restrictors by default, we ran our queries under these two path modes. Out of 659 queries, 20 could not be expressed in Neo4j since they were complex RPQs. The experiment results are in Figure 17.

WALKS. In Figure 17 (left) we show the results for the \(\mathit{WALK}\) restrictor. Since we run 659 different queries, we present box plots of our results. The first two columns represent the BFS and DFS version of Algorithm 2 in PathFinder, which corresponds to \(\mathit{ANY}\)(\(\mathit{SHORTEST}\)) \(\mathit{WALK}\) mode. It is around 10x faster than the SPARQL engines (the next three columns). We find this difference remarkable, because the SPARQL engines only return endpoint pairs, whereas PathFinder returns more information: it additionally returns a witnessing path for each such endpoint pair. The number of timeouts we observed tell a similar story. Here both PathFinder-BFS and PathFinder-DFS had 12 timeouts. In contrast, Jena timed out 95 times, and BlazeGraph and Virtuoso 86 and 24 times, respectively. We remark that while Neo4j supports \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) mode, it timed out in 657 out of 659 queries, so we did not include it in the graphs.

The rightmost column in Figure 17 (left) shows the performance of PathFinder for the \(\mathit{ALL}\) \(\mathit{SHORTEST}\) mode of Algorithm 5. Again, surprisingly, despite having to fulfil a more complex task (returning all matching endpoint pairs, together with all shortest witnessing paths), finding 100,000 paths under this mode shows almost identical performance to finding a single shortest path for each reached node. The number of timeouts for PathFinder was 10. This number is lower than for the \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) mode because we only search for 100,000 paths. Under \(\mathit{ALL}\) \(\mathit{SHORTEST}\), we do not need to find as many node pairs to find this amount of paths. Again, while Neo4j does support this path mode, it could only complete 2 out of 659 queries.

TRAILS. The results for the \(\mathit{TRAIL}\) semantics are shown in Figure 17 (right). The first two columns correspond to \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{TRAIL}\) and \(\mathit{ANY}\) \(\mathit{TRAIL}\) in PathFinder. This performance is almost identical to the \(\mathit{ANY}\) \(\mathit{WALK}\) case, with only 26 and 27 timeouts for the BFS and DFS versions, respectively. The next three columns correspond to the \(\mathit{ALL}\) \(\mathit{TRAIL}\) mode, which is only supported by PathFinder-BFS, PathFinder-DFS, and Neo4j. Here we compare only with Neo4j since it is the only engine that could load the dataset and supports the \(\mathit{TRAIL}\) semantics. PathFinder performs around 10x faster than Neo4j. This is reflected in the number of timeouts with 134 for Neo4j, and only 11 for PathFinder-BFS and 13 for PathFinder-DFS. The rightmost column corresponds to \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(\mathit{TRAIL}\) mode in PathFinder, which again shows similar performance to other \(\mathit{TRAIL}\)-based modes, with only 21 timeouts.

Overall, we see that PathFinder shows remarkably stable performance when returning trails. Interestingly, while the theoretical literature classifies the \(\mathit{TRAIL}\) mode as intractable [47], [51], and algorithms proposed in Section 4 take a brute-force approach to solving them, over real-world data they do not seem to fare significantly worse than algorithms for the \(\mathit{WALK}\) restrictor. This is most likely due to the fact that they can either detect 100,000 results rather fast, or because the theoretical hardness requires a certain kind of interaction between the query and the data that does not occur in this experiment.

We remark that we also ran the experiments for \(\mathit{SIMPLE}\) and \(\mathit{ACYCLIC}\) restrictors in PathFinder, with identical results as in the \(\mathit{TRAIL}\) case, showing that Algorithm 10 is indeed a good option for real-world use cases.

6.4 Diamond: Scaling the Number of Paths↩︎

In this experiment, we test the performance of the query looking for paths between the node start and the node end in the graph of Figure 14. We scale the size of the database by setting \(n=1,\ldots ,40\). This allows us to test how the algorithms perform when the number of paths is large, i.e., \(2^n\). For each value of \(n\) we will look for the first 100,000 results. To compare with other engines, we focus on the \(\mathit{WALK}\) restrictor and the \(\mathit{TRAIL}\) restrictor. All the other paths modes in PathFinder, which is the only system supporting them, have identical performance as in the \(\mathit{TRAIL}\) case, since they are all derivatives of Algorithm 10. Since SPARQL systems cannot return paths, we exclude them from this experiment.

SHORTEST WALKS. The runtimes for the \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) and \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\) modes is presented in Figure 18. Here we compare PathFinder, Neo4j, and Kuzu, since Nebula does not support the mode and the SPARQL systems do not return paths. Due to the small size of the graph, we run each query twice and report the second result. This is due to minuscule runtimes which get heavily affected by initial data loading. As we can observe, for \(\mathit{ANY}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\)(Figure 18 (left)) all the engines perform well. We even pushed this experiment to \(n=1000\) with no issues for Neo4j and PathFinder. Kuzu only works up to \(n=15\) since the longest paths it supports are of length 30. In the case of \(\mathit{ALL}\) \(\mathit{SHORTEST}\) \(\mathit{WALK}\)(Figure 18 (right)), Neo4j times out for \(n=16\). Kuzu stops at \(n=15\) with a successful execution because of its hard limit of path length 30. PathFinder seems to have a linear time curve in this experiment, which is in line with its theoretical principles [24]. The the other engines’ run times grow exponentially, showing the full power of Algorithm 5 when returning 100,000 paths. We scaled to \(n=1000\) and the results for PathFinder were quite similar.

TRAILS. In addition to comparing with other systems, this experiment allows to determine which traversal strategy (BFS or DFS) is better suited for Algorithm 10 in extreme cases such as the graph of Figure 14. We present the results for \(\mathit{ANY}\) \(\mathit{TRAIL}\) and \(\mathit{TRAIL}\) in Figure 19. Considering first the \(\mathit{ANY}\) \(\mathit{TRAIL}\) case, which is only supported by PathFinder, the BFS-based algorithm will time out for \(n=26\). This is to be expected, since it constructs all paths of length \(1,2,\ldots ,25\), before considering the first path of length 26. In contrast, DFS will find the required paths rather quickly. Concerning the \(\mathit{TRAIL}\) mode, which retrieves all trails, the situation is similar. Here we also compare with other engines that find trails. As we can see, only PathFinder-DFS could handle the entire query load. All others exhibit an exponential performance curve. This illustrates that, for a huge number of trails, DFS is the strategy of choice.

6.5 Top-\(k\) Paths and Top-\(k\) Groups↩︎

To test the top-\(k\) and top-\(k\) groups modes we run all of the query patterns described above, but now returning top-\(k\) paths and top-\(k\) groups with different values for \(k\). In order not to overcrowd the section, we present only a selection of the obtained results.

The Pokec Dataset. We begin by testing what is the cost of retrieving shortest \(k\) walks and trails over the Pokec dataset with \(k\) equal to 1, 100, and 1000, respectively. The results are presented in Figure 20. The value of \(k=1\) is equivalent to returning a single shortest walk or trail and is there for comparison with base algorithms. As expected, requiring more results requires more time, with the \(\mathit{WALK}\) semantics slightly outperforming the \(\mathit{TRAIL}\) semantics. If comparing to all shortest walks in Figure 16, we can see that the algorithm is actually slower when many paths are required (100 or more). This is consistent with comparing the code of Algorithm 5 (all shortest) vs Algorithm 6 (shortest \(k\)). Namely, the latter does significantly more book keeping and is required to expand over longer and longer paths as discussed in Example 4. Again, we stress here that \(\mathit{SHORTEST}\) \(k\) can contain many more paths than \(\mathit{ALL}\) \(\mathit{SHORTEST}\). This is because \(\mathit{SHORTEST}\) \(k\) contains paths of varying lengths, requiring the search algorithm to continue its operation until \(k\) paths are discovered. On the other hand, \(\mathit{SHORTEST}\) only considers shortest paths (of which there is generally only a few). This illustrates that the correct implementation of \(\mathit{SHORTEST}\) \(k\) could lead to unintuitive slowdowns, given that it will require further graph exploration.

The results for shortest \(k\) groups of walks and trails is given in Figure 21. Here we test for values of \(k=1,2,3\). The line for \(k=1\) is again our baseline experiment which returns all shortest walks/trails. As expected, more groups requires more runtime.

The Wikidata Experiment. Over Wikidata, we obtain similar results as for Pokec. For shortest \(k\) walks and trails, the results are in Figure 22. The conclusion here is similar as in the case of the Pokec dataset, however the execution time is much more similar to the \(\mathit{ALL}\) \(\mathit{SHORTEST}\) mode, particularly in the mean, as Wikidata usually contains many more paths than Pokec. Interestingly, it becomes apparent here that the \(\mathit{WALK}\) semantics can be (marginally) slower than the \(\mathit{TRAIL}\) semantics when shortest \(k\) paths are required. This is most likely due to the fact that for the \(\mathit{WALK}\) semantics (Section 3.3) one might be required to keep expanding paths between a pair of nodes to a length that is longer than the number of nodes in the graph, which is prohibited for \(\mathit{TRAILS}\)(Section 4.3). The results for the group modes are very similar, so we omit them for brevity.

6.6 Conclusions of the Experiments↩︎

Based on our experiments, we believe that one can conclude that PathFinder offers a sound strategy for dealing with path-returning queries in graphs. It is highly performant on all the query loads we considered, and runs faster than every other system in every scenario we tested, typically with a 10x or 100x increase in speed. This is particularly true for the \(\mathit{WALK}\) semantics, which runs very fast and with few timeouts, even on huge datasets such as Wikidata. When it comes to \(\mathit{TRAIL}\), one has to be careful selecting breadth-first search (BFS) or depth-first search (DFS). The former is a good candidate for highly connected graphs with few hops, and the latter is better able to handle a huge number of paths. Finally, we remark that PathFinder was tested only as a disk-based system that loads data into a main memory buffer as required by the queries. Our code [29] also includes an in-memory version of PathFinder, which uses the Compressed Sparse Row representation of graphs [62] in order to store the data in memory, and which runs about twice as fast as the results we presented (results not included for brevity).

7 Related Work↩︎

The topic of returning paths that match regular path queries is fairly new. To the best of our knowledge, the complexity of the problem was first formally studied in [38]. Most existing work focuses on finding node pairs connected by a path that conforms to the regular path query [8], [47], [48], [63]–[68]. The most notable exceptions are Eppstein’s algorithm for returning the \(k\) shortest walks [69] and Yen’s algorithm [70], which returns \(k\) shortest simple paths. None of these match these paths against a regular path query. Extensions of Yen’s algorithm that simultaneously check if the paths match a regular path query have been developed in [51], [52], both for simple paths and for trails. The corresponding problems for undirected paths were studied in [49]. Returning shortest paths that match a given RPQ was studied in [51], but not specifically using Eppstein’s data structure.

A closely related problem to ours is deciding if there exists a simple path or trail from a given source to target node for a regular path query. If the regular path query is part of the input, the problem is trivially NP-hard because it generalizes the Hamiltonian Path problem, but a closer analysis reveals fixed-parameter tractability in many real-world cases [51]. For fixed regular path queries \(r\), several studies aimed at understanding which regular expressions \(r\) make the problem hard or polynomial-time solvable. In these problems, one is only given as input the graph \(G\), a source node \(s\), a target node \(t\), and the question is if there exists a simple path or trail from \(s\) to \(t\) that matches \(r\). In this context, Bagan et al. [48] provided a complete trichotomy for simple paths, whereas Martens et al. [52] provided one for trails. For undirected paths, pinning down for which regular path queries the problem is easy versus hard is much more challenging [49]. Resolving this problem required solving the 30-year open problem of deciding if an undirected graph has a simple path of length zero modulo \(k\) [71], which was recently shown to be in polynomial time [72]. A complete classification in the style of [48], [52] is still open.

On the systems side, Gubichev et al. [73] focused on returning paths in graphs, but not according to an RPQ pattern, and [74] uses a BFS-style exploration to find the first \(k\) paths, which means that some non-shortest paths will be returned. A similar approach for top-\(k\) results is presented in [75], but not preferring shortest paths. Furthermore, we should mention that Neo4j’s system implementing Cypher has been returning paths since its early release in 2010–2011. These path returning capabilities focused on returning trails and were implemented for a restricted class of regular path queries, for example, disallowing concatenation under Kleene star.

Closest to our work is [24], where a compact representation of RPQ-conforming paths (called a path multiset representation or PMR) is presented. In a nutshell, a PMR consists of a graph \(R\), a homomorphism \(h\) from \(R\) to the graph database \(G\), and sets of start and end nodes. PMRs can represent the resulting paths for all GQL path modes. Whereas [24] only studied how to compute the PMRs for variants of the \(\mathit{SHORTEST}\) mode, the present work supports all GQL path modes and presents implementable algorithms. To make this more concrete, the Visited structure of our algorithms in fact encodes a PMR of [24] for any GQL path mode.

Additional important approaches that share similarity with our algorithmic toolbox are [66], where a graph crawl based on the product graph construction is also exploited, and [76], [77], where frameworks for proposing witnesses to an RPQ answer (or the lack thereof) is explored. Finally, we mention that [78] studied an equivalent of Algorithm 5 which removes the restriction of unambiguity on the automaton used to find all shortest walks between a fixed pair of nodes.

8 Conclusions↩︎

We present PathFinder, a unifying framework for returning paths in answers to regular path queries (RPQs). To the best of our knowlede, PathFinder is the first system that allows returning paths under every mode prescribed by the GQL and SQL/PGQ query standards [13]. Our experimental evaluation shows the approach to be highly competitive on realistic workloads, outperforming other engines by one or two orders of magnitude. While our work was developed in the context of property graphs, it is straightforward to implement it on top of an existing SPARQL engine (see [29] for an example).

We showed that returning paths that match RPQs can be practically viable, which opens the question to which extent we want to explore similar functionality for SPARQL [6]. While our initial results do show that supporting path retrieval in SPARQL is feasible, it remains to be studied how this functionality mixes with the property path syntax and semantics (which differs significantly from RPQs) and how such an extension could be incorporated in the SPARQL standard. In the future, we plan to look at more expressive GQL path queries that take into consideration the data residing in nodes and edges and try to develop a toolbox of algorithms to handle these cases.

References↩︎