Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries

None of the existing evaluation algorithms for CRPQs is output-sensitive: Their complexity is not only a function of the input data graph and query output sizes but also of the output sizes of the RPQs in the query, yet the RPQ outputs can be asymptotically larger than the query output. In the following, we overview the state-of-the-art algorithms for CRPQ evaluation and show that, for problem instances where the query output is asymptotically smaller than the largest output size of any of the RPQs in the query, our algorithm can outperform them.

The classical evaluation algorithm for RPQs, called PG, computes the product graph of the data graph and the non-deterministic finite automaton defined by the given RPQ and runs in $𝒪(|V|\cdot |E|)$ data complexity [5, 22, 23]. This cannot be improved by combinatorial algorithms: There is no combinatorial²²2This term is not defined precisely. A combinatorial algorithm does not rely on Strassen-like fast matrix multiplication. Using fast matrix multiplication, the data complexity of PG can be improved to $𝒪({|V|}^{\omega })$, where $\omega$ is the matrix multiplication exponent [10] and currently $\omega =2.37$. algorithm to compute RPQs with $𝒪({(|V|\cdot |E|)}^{1-ϵ})$ data complexity³³3The lower bound in [10] has $|V|+|E|$ instead of $|E|$, but the proof also holds for the formulation that just uses $|E|$. for any $ϵ>0$, unless the combinatorial Boolean Matrix Multiplication conjecture fails [10].⁴⁴4The combinatorial Boolean Matrix Multiplication conjecture is as follows: Given two $n\times n$ Boolean matrices $A,B$, there is no combinatorial algorithm that multiplies $A$ and $B$ in $𝒪(n^{3-ϵ})$ for any $ϵ>0$. When taking the query output into consideration, however, PG’s complexity can be improved. The output-sensitive variant of PG, called OSPG, evaluates any RPQ with $𝒪(|E|+|E|\cdot {\text{OUT}}^{1/2})$ data complexity, where OUT is the output size of the RPQ [20].⁵⁵5The data complexity of OSPG is $𝒪(|E|\cdot \mathrm{\Delta }+\min (\text{OUT}/\mathrm{\Delta },|V|)\cdot |E|)$ [20]. The user-defined threshold $\mathrm{\Delta }$ was set to ${|E|}^{1/2}$ in [20], yielding $𝒪({|E|}^{3/2}+\min (\text{OUT}\cdot {|E|}^{1/2},|V|\cdot |E|))$. For $\mathrm{\Delta }={\text{OUT}}^{1/2}$, we obtain instead $𝒪(|E|\cdot {\text{OUT}}^{1/2}+|E|)$, where the additive term $|E|$ is necessary to scan the input data even when for $\text{OUT}=0$. The complexity of OSPG is at most the complexity of PG, since $\text{OUT}\le {|V|}^2$.

The state-of-the-art evaluation algorithm for CRPQs proceeds in two stages [11]. Using PG, it first materializes the binary relations representing the output of the RPQs in the given CRPQ $Q$. This stage turns the CRPQ into an equivalent conjunctive query $Q^{\prime }$ over materialized binary relations. The algorithm then evaluates $Q^{\prime }$ using a worst-case optimal join algorithm [28, 24]. For acyclic CRPQs with arbitrary free variables, we can immediately improve this state-of-the-art. First, we use OSPG instead of PG to materialize the RPQs with $𝒪(|E|+|E|\cdot {\text{OUT}}_a^{1/2})$ data complexity, where ${\text{OUT}}_a\le {|V|}^2$ is the maximum size of the non-calibrated output of the RPQs.⁶⁶6${\text{OUT}}_a$ is not to be confused with ${\text{OUT}}_c$, which is the maximum size of the calibrated output of any RPQ in $Q$. It holds that ${\text{OUT}}_c\le {\text{OUT}}_a$ and there can be instances for which ${\text{OUT}}_c=0$ yet ${\text{OUT}}_a={|V|}^2$. Then, $Q^{\prime }$ can be evaluated using the classical Yannakakis algorithm, called here Yan, [30] with $𝒪({\text{OUT}}_a\cdot \text{OUT})$ data complexity, or using its output-sensitive refinement [19], called here OSYan, in $𝒪({\text{OUT}}_a\cdot {\text{OUT}}^{1-1/\mathrm{𝖿𝖼}\text{-}\mathrm{𝖿𝗁𝗍𝗐}(Q^{\prime })}+\text{OUT})$ data complexity, where $\mathrm{𝖿𝖼}\text{-}\mathrm{𝖿𝗁𝗍𝗐}(Q^{\prime })$ is the free-connex fractional hypertree width of $Q^{\prime }$ and OUT is the output of $Q^{\prime }$ (and also of $Q$). Overall, the best complexity for evaluating acyclic CRPQs using prior work can therefore be achieved by combining OSPG and OSYan: $𝒪(|E|+|E|\cdot {\text{OUT}}_a^{1/2}+{\text{OUT}}_a\cdot {\text{OUT}}^{1-1/\mathrm{𝖿𝖼}\text{-}\mathrm{𝖿𝗁𝗍𝗐}(Q^{\prime })}+\text{OUT})$. Yet this approach, as well as all previous approaches, are not output-sensitive: Indeed, one can easily construct data graphs for which the output of some RPQs in $Q$ consists of all quadratically many pairs of vertices in the data graph, i.e., ${\text{OUT}}_a=𝒪({|V|}^2)$, while the query output is empty, i.e., $\text{OUT}=0$. In that case, our algorithm takes time $𝒪(|E|)$, whereas OSPG+OSYan takes $𝒪(|E|\cdot |V|)$.

For free-connex acyclic CRPQs, which have free-connex fractional hypertree width 1, OSPG+OSYan needs $𝒪(|E|+|E|\cdot {\text{OUT}}_a^{1/2}+{\text{OUT}}_a+\text{OUT})$, which simplifies to $𝒪(|E|+|E|\cdot {\text{OUT}}_a^{1/2}+\text{OUT})$, since the time $𝒪(|E|\cdot {\text{OUT}}_a^{1/2})$ to compute the RPQs cannot be smaller than the maximum output size of the RPQs. In contrast, our algorithm needs $𝒪(|E|+|E|\cdot {\text{OUT}}_c^{1/2}+\text{OUT})$ (Proposition 16). Since ${\text{OUT}}_c\le {\text{OUT}}_a$, this implies that for free-connex acyclic queries, our algorithm performs at least as good as OSPG+OSYan and outperforms OSPG+OSYan in case ${\text{OUT}}_a$ is larger than ${\text{OUT}}_c$. The next examples compare our algorithm with OSPG+OSYan on CRPQs that are not free-connex acyclic. Further examples are given in Appendix A.

The rest of the paper is organized as follows. Section 2 introduces basic concepts. Section 3 defines and illustrates the contraction width for CRPQs. Sections 4 and 5 detail our algorithms for free-connex and general acyclic CRPQs, respectively. We conclude in Section 6. Appendix A compares our algorithm with prior approaches via illustrating examples. Appendix B gives the proof of one of our main statements. Further details are deferred to the extended technical report [2].

Consider a cycle-free undirected graph $G=(V,E)$. The degree of a vertex $u$ in $G$ is the number of its neighbors, i.e., the number of vertices $v\in V$ with $u\ne v$ and $\{u,v\}\in E$. We define two contraction operations on $G$ that eliminate vertices of degree 1 or 2:

• $\mathrm{■}$

  Elimination of a degree-2 vertex: A graph $G^{\prime }$ is the result of the elimination of a degree-2 vertex $u$ in $G$ if $\{u,v_1\},\{u,v_2\}\in E$ for distinct $v_1,v_2\in V$ and $G^{\prime }=(V\setminus \{u\},E\setminus \{\{u,v_1\},\{u,v_2\}\}\cup \{\{v_1,v_2\}\})$. That is, $G^{\prime }$ is obtained from $G$ by removing $u$ and the two edges to its only neighbors $v_1$ and $v_2$ and adding a new edge connecting $v_1$ and $v_2$.

• $\mathrm{■}$

  Elimination of a degree-1 vertex: A graph $G^{\prime }$ is the result of the elimination of a degree-1 vertex $u$ in $G$ if $\{u,v\}\in E$ for some $v\in V$ and $G^{\prime }=(V^{\prime },E^{\prime })$, such that: (1) $E^{\prime }=E\setminus \{\{u,v\}\}$ and; (2) $V^{\prime }=V\setminus \{u,v\}$ if there is no $v^{\prime }$ with $\{v,v^{\prime }\}\in E^{\prime }$, or $V^{\prime }=V\setminus \{u\}$ otherwise. In other words, $G^{\prime }$ results from $G$ by removing the vertex $u$, the edge to its only neighbor $v$, and also $v$ if $v$ has no neighbor other than $u$.

We refer to the graph $G^{\prime }$ obtained from $G$ after eliminating a vertex $u$ by $\mathrm{𝖾𝗅𝗂𝗆𝗂𝗇𝖺𝗍𝖾}(G,u)$.

Any elimination order leads to the same contracted query graph:

We denote the contracted query graph of a CRPQ $Q$ by $\mathrm{𝖼𝗀}(Q)$.

The CRPQ $Q_{ℬ}$ induced by a bag $ℬ$ has the same body as $Q$ and has the free variables $\text{free}(Q)\cap ℬ$.⁸⁸8Our definition of induced query is tailored to CRPQs and differs from the standard notion of induced conjunctive queries. Given a tree decomposition for a conjunctive query $Q(𝑭)={\bigwedge }_{i\in [n]}{R}_i({𝑿}_i)$, the query induced by a bag $ℬ$ is defined as $Q(ℬ)={\bigwedge }_{i\in [n]}{R}_i({𝑿}_i\cap ℬ)$. Applying this definition to CRPQs can lead to induced queries that are not CRPQs, since their atoms can have less than two variables. A tree decomposition $𝒯$ is free-connex if $𝒯$ contains a connected subtree such that the union of the bags in this subtree is the set $\text{free}(Q)$ of free variables. We use $\text{F}\text{TD}(Q)$ to denote the set of all free-connex tree decompositions of the query $Q$.

The contraction width of a tree decomposition is the maximal number of bound variables in the contracted query graph of any induced query. The contraction width of a CRPQ is the minimal contraction width of any of its free-connex tree decompositions:

Note that two induced queries with different sets of free variables can impact differently the contraction width of the decomposition, even though they have the same body. This is because fewer free variables can enable the elimination of a larger number of bound variables.

The next example shows that a decomposition with several bags can lead to a lower contraction width compared to a trivial decomposition consisting of a single bag.

The next example illustrates that the contraction width of free-connex acyclic queries is 0, as claimed in Proposition 3:

Another well-known width measure based on tree decompositions is the fractional hypertree width ($\mathrm{𝖿𝖼}\text{-}\mathrm{𝖿𝗁𝗍𝗐}$). Its definition is given in the extended technical report [2].

Given a free-connex acyclic CRPQ, we construct a free-top join tree for the query and perform, analogous to the Yannakakis algorithm [30], a bottom-up and a top-down pass over the tree to compute the calibrated outputs of the RPQs occurring in the query. We then join these output relations to obtain the final output. The key difference from the Yannakakis algorithm is that the outputs of the RPQs are not materialized prior to calibration. In what follows, we first present our evaluation strategy and subsequently illustrate it in Example 17.

The procedure EvalFreeConnex in Figure 4 describes our evaluation strategy for a free-connex acyclic CRPQ $Q$ and an edge-labeled graph $G$. It starts with constructing a free-top join tree $J$ for $Q$, which means that the atoms containing a free variable form a connected subtree in $J$ including the root. The bottom-up and top-down passes are described by the subprocedures BottomUp and TopDown, respectively. During these passes, the procedure computes, among other relations, a set $ℛ$ of relations $R_i$ whose join is the output of $Q$. This set consists of the calibrated output of the root atom and of all atoms that have a free variable. Next, we describe the procedures BottomUp and TopDown in more detail.

The main purpose of BottomUp is to materialize the calibrated output of the root atom in the join tree. It computes at each non-root atom $r_i(X_i,Y_i)$ a relation $B_{i\to p}$ that joins $r_i(X_i,Y_i)$ with the relations $B_{c\to i}$ computed at the children of $r_i(X_i,Y_i)$ and projects the result onto the common variables of $r_i(X_i,Y_i)$ and its parent atom (Lines 7-8 of BottomUp). If $r_i(X_i,Y_i)$ is the root, the procedure computes the relation $R_i$, defined analogously to $B_{i\to p}$ except that its set of variables is the intersection of $\{X_i,Y_i\}$ with the free variables of $Q$ (Lines 3–4 of BottomUp). The relation $R_i$ is the calibrated output of $r_i(X_i,Y_i)$.

The main purpose of the subprocedure TopDown is to materialize at each atom $r_i(X_i,Y_i)$ that is not the root of the join tree and contains at least one free variable of $Q$, the calibrated output $R_i$ of the RPQ $r_i$. For this, the procedure computes at each such atom $r_i(X_i,Y_i)$ with parent $r_p(X_p,Y_p)$, a relation $T_{p\to i}$ that is the projection of the relation $R_p$, computed at the parent atom, onto the common variables of $R_p$ and $r_i(X_i,Y_i)$. Then, it materializes the relation $R_i$ by computing the projection of the join of $r_i(X_i,Y_i)$ and $T_{p\to i}$ onto the free variables of $Q$ (Lines 4–6 of TopDown).

After the execution of BottomUp and TopDown, the set $ℛ=\{R_{i_1},\mathrm{\dots },R_{i_k}\}$ consists of the calibrated outputs of the root atom of the join tree and all other atoms that have at least one free variable. The procedure returns the output of the conjunctive query $Q^{\prime }(𝑭)={\bigwedge }_{j\in [k]}{R}_{i_j}$, which is the output of $Q$ (Line 5 of EvalFreeConnex). We can show:

We sketch the proof of the time complexity in Proposition 16. The full proof is given in the extended technical report [2]. Since the query size is considered fixed, a free-top join tree for $Q$ can be constructed in constant time. The relations $R_{i_1},\mathrm{\dots },R_{i_k}$ occurring in the query $Q^{\prime }$ in Line 4 of the procedure EvalFreeConnex are the calibrated outputs of RPQs that appear in a connected subtree of the join tree for $Q$. This means that the query $Q^{\prime }$ forms a full acyclic conjunctive query. Hence, its output can be computed in $𝒪({\max }_{j\in [k]}|R_{i_j}|+\text{OUT})$ time using the Yannakakis algorithm [30]. Since the relations $R_{i_j}$ are calibrated, the time complexity simplifies to $𝒪(\text{OUT})$. It remains to show that all relations constructed by the subprocedures BottomUp and TopDown can be computed in $𝒪(|E|+|E|\cdot {\text{OUT}}_c^{1/2})$ time. To show this, we use the following lemma:

Since the query is acyclic, it cannot contain two atoms with the same set of variables. Hence, the definition of each relation $B_{i\to p}$ computed in the procedure BottomUp is of the form $V(𝑿)=r_i(X_i,Y_i)\wedge {\bigwedge }_{j\in [k]}{U}_j(X_i)$ $\wedge$ ${\bigwedge }_{j\in [\mathrm{\ell }]}{W}_j(Y_i)$ $\wedge$ ${\bigwedge }_{j\in [m]}{Z}_j()$ for some relations $U_j$, $W_j$, and $Z_j$ and $k,\mathrm{\ell },m\in \mathbb{N}$, where $𝑿\subset \{X_i,Y_i\}$. By Lemma 18, the relation can be computed in time $𝒪(|E|)$.

The definition of the relations $R_i$ computed in the procedures BottomUp and TopDown is of the same form, except that the set of variables $𝑿$ is not necessarily a strict subset of $\{X_i,Y_i\}$. By Lemma 18, each relation $R_i$ can be computed in $𝒪(|E|+|E|\cdot {\text{OUT}}^{1/2})$ time. Since $R_i$ is the calibrated output of $r_i(X_i,Y_i)$, we can write the complexity as $𝒪(|E|+|E|\cdot {\text{OUT}}_c^{1/2})$.

Each relation $T_{p\to i}$ computed in TopDown is a projection of the relation $R_p$ and can thus be computed by a single pass over $R_p$. Since $R_p$ is computed in $𝒪(|E|+|E|\cdot {\text{OUT}}_c^{1/2})$ time, its size is upper-bounded by the same asymptotic complexity. Hence, each relation $T_{p\to i}$ can be computed in $𝒪(|E|+|E|\cdot {\text{OUT}}_c^{1/2})$ time.

Given a CRPQ and an input graph, we explain how to eliminate bound variables following an elimination order and adapt the input graph in linear time while preserving the output of the query. We illustrate our strategy by an example.