Conjunctive two-way regular path queries (C2RPQs) are a common abstraction of the core of query languages for graph databases, much like conjunctive queries (CQs) in the relational case. As in the case of CQs, their evaluation is NP-complete. Also, similarly to the CQ case, existing work on eficient evaluation showed that bounded semantic treewidth (TW) is a suficient condition for fixed-parameter tractable (fpt) evaluation. This has been achieved by providing witnesses for bounded semantic TW, i.e., equivalent queries of bounded syntactic TW. In subsequent steps, a witness of TW up to twice the semantic TW of the query has been constructed, followed more recently by a witness of TW equal to the semantic TW of the query. Both witnesses can be exploited to obtain fpt evaluation algorithms, the latter giving better data complexity due to the optimal treewidth. However, while the size of the suboptimal-TW witness is exponential in the size of the query, the size of the optimal-TW witness is doubly exponential, which leads to an evaluation algorithm doubly exponential in the size of the query. We show that the additional blow-up in combined complexity can be avoided by exploiting the connection between the two witnesses. We devise an evaluation algorithm that fully exploits the equivalent witness of minimal TW without actually computing it, and runs in time singly exponential in the size of the query.
Graph databases are nowadays mainstream [
In the case of CQs, there is a long line of research concerning eficient evaluation. This spans
from the well-known polynomial time Yannakakis’ algorithm for evaluating acyclic CQs [
In the context of the semantic TW of C2RPQs, Romero, Barcelo, and Vardi introduced two
notions of equivalence of C2RPQs [
It remained open how to decide semantic TW of C2RPQs under the logical equivalence notion, and, in particular, how to construct a witness of optimal TW. This has been settled recently by Figueira and Morvan [13], by constructing a witness for semantic TW of size doubly exponential in the size of the original query. This leads to an algorithm for evaluating C2RPQs of semantic TW which runs in time ( (Φ) ||+1), with being a doubly exponential function. While this is a significant improvement in data complexity compared to existing algorithms, the algorithm is impractical due to its high combined complexity.
Here we describe a more eficient algorithm for evaluating C2RPQs of semantic treewidth which runs in time ((|Φ |)||+1), where is an exponential function. We observe that the TW- witness query from [13] can be seen as a specialization of the TW-(2 + 1) query from [14]. This enables us to encode the evaluation of the TW- witness query into a Datalog program of width + 1 without explicitly constructing the query. As the size of the Datalog program is exponential in the size of the original query, we obtain the desired result.
We assume familiarity with CQs, databases, treewidth, pathwidth, Datalog, and non-deterministic
ifnite automata (NFA). We note that every CQ of TW can be evaluated over database in
time ((||)||+1), where is a polynomial [
Let us fix a countable alphabet Σ . A graph database over Σ is a finite directed graph with edges labeled with symbols from Σ . A path in a graph database is a sequence (1 →−1 2 . . . →− +1). The label of as above, denoted (), is the word 1 . . . from Σ * .
A regular path query (RPQ) is a query of the form (, ) where is a regular language over Σ , expressed as an NFA. Assuming and ′ are states of the NFA , [, ′] is the NFA obtained from by having as initial state and ′ as a unique final state. For a graph database and nodes , in , |= (, ) if there exists a path in from to such that () ∈ . When is over the extended alphabet Σ ± = Σ ∪ {− | ∈ Σ }, we say that (, ) is a two-way RPQ (2RPQ); it is evaluated over the completion ± of with edges of the form →− − − , whenever →− ∈ .
A Boolean conjunctive (two-way) regular path query, abbreviated as C(2)RPQ, is a query of the form = ∃z ⋀︀1≤ ≤ (, ) where each (, ) is a (2)RPQ and z is the set of variables occurring in the query. We write |= if there is a mapping ℎ : z → dom() such that |= (ℎ(), ℎ()), for every 1 ≤ ≤ . Unions of C(2)RPQs, abbreviated as UC(2)RPQs, as well as satisfaction of UC(2)RPQs and containment (⊆ ) of (U)C(2)RPQs are defined as expected.
In this section, we provide an overview of the witness queries from [
Definition 1. A UC2RPQ Φ ′ is a TW- approximation of a C2RPQ Φ if: (i) Φ ′ has TW , (ii) Φ ′ ⊆ Φ , and (iii) there is no UC2RPQ Φ ′′ of TW such that Φ ′ ⊂ Φ ′′ ⊆ Φ .
In the limit case, when Φ has semantic TW , a TW- approximation is equivalent to Φ and thus a witness for semantic TW. The following lemma describes a suficient condition for a TW- query to be an approximation.
Lemma 1. Let Φ be a C2RPQ and Φ ′ be a TW- UC2RPQ s.t. Φ ′ ⊆ Φ and Φ ′ is equivalent to Φ on TW- databases. Then Φ ′ is a TW- approximation of Φ .
In the spirit of Lemma 1, the approach from [
As explained in the introduction, Φ has TW up to 2 + 1: this is due to the fact that each of its C2RPQs has as the underlying graph a pseudo-tree decomposition of width , i.e. a tree decomposition from which some non-branching nodes are removed and the remaining nodes are re-connected via new atoms. We will refer to such a sub-query induced by two bags in a tree decomposition and some interconnecting atoms as a segment.
The UC2RPQ Φ constructed in [13] as a witness of semantic TW can be seen as a specialization of the query Φ in the sense that atoms connecting endpoints of segments in C2RPQs in Φ are replaced by actual queries of pathwidth (see Figure 1, middle), thus recovering TW of the witness query. This is achieved by first considering the infinitary UC2RPQ which contains all C2RPQs induced by mappings of Φ into a TW- database (this time, all elements of are considered relevant and induce splittings and variable identifications in Φ ). Clearly, this query is a specialization of Φ in the sense described above. Then, in a second step, using a pumping argument, it can be shown that it is enough to consider C2RPQs with segment realizations up to a certain size (exponential in Φ ).
As the size of Φ is exponential in |Φ | and the size of Φ is doubly exponential in |Φ |, and each C2RPQ can be evaluated by first materializing (in polynomial time) each 2RPQ in the database and then simply regarding the query as a CQ over the materialized database, one obtains the fpt algorithms with the complexities mentioned in the introduction.
Our algorithm for eficient evaluation of C2RPQs of semantic TW is based on evaluating Φ without actually computing it. This is possible due to the fact that for queries of semantic TW , Φ ≡ Φ and each segment query from Φ is equivalent to the union of all of its realizations in some C2RPQ in Φ . Under this assumption, we can actually evaluate Φ instead of Φ . As explained in Section 3, the realization of a segment from Φ in Φ is a query of pathwidth . Each bag from such a path query can be seen as having a certain type induced by atoms which cross it, i.e. atoms for which at least one of the arguments belongs to the bag. The important thing is that for each atom (, ) in the original query Φ , there is at most one atom of the form [1, 2](′, ′) that crosses such a bag (derived from a splitting of the original atom). Thus, we can type each bag based on the signature of such atoms. There is an exponential number of types and a natural notion of bags/type compatibility: Figure 1 (right) depicts how two bags with compatible types are matched in a segment. In this view, each segment query from Φ can be seen as a reachability query between two ( + 1)-types and thus can be encoded using Datalog rules with at most + 1 variables.
For joining the segments in a C2RPQ of Φ , the algorithm performs bottom-up evaluation.
On an abstract level, it can be seen as a Yannakakis-style procedure [
There are several open questions regarding eficient evaluation of C2RPQs. The first one concerns the precise complexity of deciding semantic treewidth: for now it is known that it is ExpSpace-hard and in 2ExpSpace. Another major step would be achieving a full characterisation of fixed parameter tractability of UC2RPQs, in particular establishing lower bounds.
Supported by Poland’s NCN grant 2018/30/E/ST6/00042. [13] D. Figueira, R. Morvan, Approximation and semantic tree-width of conjunctive regular path queries, in: ICDT, volume 255 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 15:1–15:19. [14] P. Barceló, M. Romero, M. Y. Vardi, Semantic acyclicity on graph databases, SIAM Journal on Computing 45 (2016) 1339–1376.