Output-sensitive Conjunctive Query Evaluation
Shaleen Deep

Jim Gray Systems Lab

Hangdong Zhao

Department of Computer Sciences
University of Wisconsin-Madison

Austen Z. Fan

Department of Computer Sciences
University of Wisconsin-Madison

Paraschos Koutris

Department of Computer Sciences
University of Wisconsin-Madison

Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of join algorithms have been developed, and commercial database engines use finely tuned join heuristics that take into account many factors including the selectivity of predicates, memory, IO, etc. However, most of the results have catered to either full join queries or non-full join queries but with degree constraints (such as PK-FK relationships) that make joins easier to evaluate. Further, most of the algorithms are also not output-sensitive.
In this paper, we present a novel, output-sensitive algorithm for the evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free variables. Our result is based on a novel generalization of the  Yannakakis algorithm and shows that it is possible to improve the running time guarantee of Yannakakis algorithm by a polynomial factor. Importantly, our algorithmic improvement does not depend on the use of fast matrix multiplication, as a recently proposed algorithm does. The upper bound is complemented with matching lower bounds conditioned on two variants of the $k$-clique conjecture. The application of our algorithm recovers known prior results and improves on known state-of-the-art results for common queries such as paths and stars.

§ INTRODUCTION

Join query evaluation is the workhorse of commercial database systems to support complex data analytics, data science, and machine learning tasks, to name a few. Decades of research in the database community (both theoretical and practical) have sought to improve join query evaluation performance to scale up processing to large-scale datasets.

In terms of the theoretical guarantees offered by the state-of-the-art algorithms, several existing results are known for acyclic and cyclic queries. For acyclic queries, Yannakakis proposed an elegant framework for query evaluation <cit.>. Yannakakis showed that for a database $\mD$ of size $|\mD|$ and any acyclic Conjunctive Query (CQ) $Q(\bx_\mF)$ with output $\tOUT = Q(\mD)$ and free variables $\bx_\mF$, we can evaluate the query result in time $O(|\mD|+|\mD| \cdot |\tOUT|)$ in terms of data complexity. Depending on the structure of free variables in the query, it is possible to obtain a better runtime bound for the algorithm. For example, for the class of free-connex acyclic CQs, the algorithm is optimal with running time $O(|\mD| + |\tOUT|)$. Beyond acyclic queries, worst-case optimal joins (WCOJs) provide worst-case guarantees on query evaluation time for any full CQ (i.e., all variables are free). For non-full CQs, WCOJs are combined with the notion of tree decompositions to obtain tighter guarantees on the running time. In particular, <cit.> showed that any CQ can be evaluated in $O(|\mD|^\mw + |\tOUT|)$ time, where $\mw$ generalizes the fractional hypertree width from Boolean to CQs with arbitrary free variables. Abo Khamis et al. <cit.> showed that using the  algorithm and combining it with the Yannakakis framework, any CQ can be evaluated in $\tilde{O}(|\mD|+|\mD|^\subw\ \cdot |\out|)$ time[$\tilde{O}$ notation hides a polylogarithmic factor in terms of $|\mD|$]. Notably, the  algorithm itself uses the Yannakakis algorithm as the final step for join evaluation once the cyclic query has been transformed into a set of acyclic queries.

inner sep=1pt
shorten >= 1pt,
shorten <= 1pt
[mydot,label=left:$a_1$,xshift=-2 cm] (a1) ;
[mydot,below=of a1,yshift=0.5cm,label=left:$a_2$] (a2) ;
[below=of a2,yshift=0.5cm,label=left:$\vdots$] (a3) ;
[mydot,below=of a3,yshift=0.5cm,label=left:$a_{|\tOUT|/2}$] (a4) ;

[mydot,right=3 cm of a1,label=below:$b_1$] (b1) ;
[mydot,below=of b1,yshift=0.5cm,label=below:$b_2$] (b2) ;
[below=of b2,yshift=0.5cm,xshift=-5pt,label=right:$\vdots$] (b3) ;
[mydot,below=of b3,yshift=0.5cm,label=below:$b_{|\mD|/{|\tOUT|}}$] (b4) ;

[mydot,right=2cm of b1,label=below:$c_1$,xshift=cm] (c1) ;
[mydot,below=of c1,yshift=0.5cm,label=below:$c_s$] (c2) ;
[below=of c2,yshift=0.5cm,xshift=-5pt,label=right:$\vdots$] (c3) ;
[mydot,below=of c3,yshift=0.5cm,label=below:$c_{|\mD|/{|\tOUT|}}$] (c4) ;

[mydot,right=2cm of c2,yshift=-0.5cm,label=right:$d_1$,xshift=cm] (d1) ;

[] (a1) edge node[above, yshift=5pt]$R_{12}(x_1, x_2)$ (b1)
edge (b2)
edge (b4);
[] (a2) edge (b1)
edge (b2)
edge (b4);
[] (a4) edge (b1)
edge (b2)
edge (b4);

[] (b1) edge node[above, yshift=5pt]$R_{23}(x_2, x_3)$ (c1);
[] (b2) edge (c2);
[] (b4) edge (c4);

[] (c1) edge node[above, yshift=20pt]$R_{34}(x_3, x_4)$ (d1);
[] (c2) edge (d1);
[] (c4) edge (d1);

[mydot,below=of a4,yshift=-1.5cm,label=left:$a_{|\tOUT|/2 + 1}$] (a5) ;

[mydot,below=of b4,yshift=-0.5cm,label=above:$b_{|\mD|/{|\tOUT| + 1}}$] (b5) ;
[mydot,below=of b5,yshift=0.5cm,label=below:$b_{|\mD|/{|\tOUT|} + 2}$] (b6) ;
[below=of b6,yshift=0.5cm,label=right:$\vdots$] (b7) ;
[mydot,below=of b7,yshift=0.5cm,label=below:$b_{(2|\mD|/|\tOUT)|}$] (b8) ;

[mydot,below=of c4,yshift=-0.5cm,label=above:$c_{|\mD|/{|\tOUT| + 1}}$] (c5) ;
[mydot,below=of c5,yshift=0.5cm,label=below:$c_{|\mD|/{|\tOUT|} + 2}$] (c6) ;
[below=of c6,yshift=0.5cm,label=right:$\vdots$] (c7) ;
[mydot,below=of c7,yshift=0.5cm,label=below:$c_{(2|\mD|/|\tOUT)|}$] (c8) ;

[mydot,right=2cm of c5,label=below:$d_2$,xshift=cm] (d5) ;
[mydot,below=of d5,yshift=0.5cm,label=below:$d_3$] (d6) ;
[below=of d6,yshift=0.5cm, xshift=-5pt,label=right:$\vdots$] (d7) ;
[mydot,below=of d7,yshift=0.5cm,label=below:$d_{|\tOUT|/2+1}$] (d8) ;

[] (a5) edge (b5);
[] (a5) edge (b6);
[] (a5) edge (b8);

[] (b5) edge (c5);
[] (b6) edge (c6);
[] (b8) edge (c8);

[] (c5) edge (d5)
edge (d6)
edge (d8);

[] (c6) edge (d5)
edge (d6)
edge (d8);

[] (c8) edge (d5)
edge (d6)
edge (d8);

Database instance showing relations $R_{12}(x_1, x_2), R_{23}(x_2, x_3),$ and $R_{34}(x_3, x_4)$ for the three path query.

Despite its fundamental importance, no known improvements have been made to Yannakakis result until very recently. In an elegant result, Hu <cit.> showed that using fast matrix multiplication (i.e., a matrix multiplication algorithm that multiplies two $n \times n$ matrices in $O(n^\omega)$ time, $\omega < 3$), we can evaluate any acyclic CQ in $O(|\mD|+ |\tOUT| + |\mD| \cdot |\tOUT|^{5/6})$ (if $\omega=2$, which gives the strongest result in their framework). The key insight is to use the star query as a fundamental primitive that benefits from fast matrix multiplication, an insight also explored by prior work <cit.>, and evaluate any acyclic CQ in a bottom-up fashion by repeatedly applying the star query primitive. However, Hu's result has two principal limitations. First, the runtime guarantee of the algorithm degenerates to $O(|\mD|+|\mD| \cdot |\tOUT|)$ for $\omega=3$, which is the same guarantee as that of Yannakakis's algorithm. Second, the algorithm does not support general aggregations (aka FAQs cf. <ref>), a common usecase in SQL <cit.>. It is also open whether the upper bound obtained is optimal. Therefore, the tantalizing question of whether Hu's upper bound can be improved and whether the improvement can be made using a combinatorial[Although combinatorial algorithm does not have a formal definition, it is intuitively used to mean that the algorithm does not use any algebraic structure properties. A key property of combinatorial algorithms is that they are practically efficient <cit.>. Nearly all practical/production join algorithms known to date are combinatorial in nature.] algorithm remains open.

In this paper, we show that it is possible to evaluate any acyclic CQ $Q$ combinatorially in time $O(|\mD|+ |\tOUT|+|\mD| \cdot |\out|^{1-\epsilon})$ where $0 < \epsilon \leq 1$ is a query-dependent constant. An important class of queries that we consider is the path query $P_k(x_1, x_{k+1}) \leftarrow R_{12}(x_1, x_2) \wedge R_{23}(x_2, x_3)\wedge \dots \wedge R_{k, k+1}(x_k, x_{k+1})$. To give the reader an overview of our key ideas, we show our techniques on the  three path query $P_3(x_1, x_4)$.

Consider the database instance as shown in <ref>. This example instance was also used by Hu to show the limitations of Yannakakis algorithm. For any $1 \leq |\tOUT| \leq |\mD|$, Hu showed that any join order chosen by the Yannakakis algorithm for evaluating the query must incur a materialization cost of $\Omega(|\mD| \cdot |\tOUT|)$. However, their argument assumes that the entire relation is used to do the join.

We demonstrate an algorithm for this query that bypasses the assumption. First, partition $R_{12}(x_1, x_2)$ into $R_{12}^H(x_1, x_2)$ and $R_{12}^L(x_1, x_2)$ based on the degree threshold of $x_2$ values. In particular, for any choice of $\Delta > 1$, we define

$$ R_{12}^L(x_1, x_2) = \{ t \in R_{12} \mid |\sigma_{x_2 = t(x_2)} R_{12}| \leq \Delta\} $$

Let $R_{12}^H(x_1, x_2) =  R \setminus R_{12}^L(x_1, x_2)$. Now, the original query can be answered by unioning the output of $P^H_4 = \pi_{x_1, x_4} (R_{12}^H(x_1, x_2) \wedge R_{23}(x_2, x_3) \wedge R_{34}(x_3, x_4))$ and $P^L_4 = \pi_{x_1, x_4} (R_{12}^L(x_1, x_2) \wedge R_{23}(x_2, x_3) \wedge R_{34}(x_3, x_4))$.

Both of the join queries can be evaluated in $O(|\mD|)$ time, regardless of the value of $|\tOUT|$. For both queries, we first apply a semijoin filter to remove all tuples from the input that do not participate in the join, a linear time operation. $P^L_4$ is evaluated by first joining $R_{12}^L(x_1, x_2) \wedge R_{23}(x_2, x_3)$, materializing the intermediate result, and then join the result with $R_{34}(x_3, x_4)$. $P^H_4$ is evaluated in the opposite order by first joining $R_{23}(x_2, x_3) \wedge R_{34}(x_3, x_4)$, followed by joining with $R^L_{12}(x_1, x_2)$.

Building upon the idea in <ref>, we show that by carefully partitioning the input and evaluating queries in a specified order, it is possible to improve the running complexity of join evaluation for a large class of CQs.

Our Contribution In this paper, we develop a combinatorial algorithm for evaluating any CQ $Q$. We present a recursive algorithm that generalizes the Yannakakis algorithm and obtains a provable improvement in running time. The generalization is clean enough for teaching at a graduate level. Our results are easily extensible to support aggregations and commutative semirings. To characterize the running time of CQs, we also present a new simple width measure that we call the projection width, $\wout(Q)$, that closely relates to existing width measures known for acyclic queries. As an example, our generalized algorithm when applied to the path query $P_k(x_1, x_{k+1})$ can evaluate it in time ${O}(|\mD|+ |\tOUT| + |\mD| \cdot |\tOUT|^{1-1/k})$. Rather surprisingly, this result (which is combinatorial and thus, assumes $\omega=3$) is already polynomially better than Hu's result for $k \leq 5$ even if we assume that $\omega=2$ to obtain the strongest possible result in their setting. At the heart of our main algorithm is a technical result (which may be of independent interest) that allows tighter bounding of the cost of materializing intermediate results when executing Yannakakis. We demonstrate the usefulness of our tighter bounding by proving that for path queries, we can further improve the running time to ${O}(|\mD|+ |\tOUT| + |\mD| \cdot |\tOUT|^{1-1/\lceil (k+1)/2 \rceil})$. For $k=3$, this result matches the lower bound of $\Omega(|\mD|+ |\tOUT| +|\mD| \cdot \sqrt{|\tOUT|})$ that holds for evaluating any $P_k$ for $k \geq 2$.

Further, we establish tightness of our results by demonstrating a matching lower bound on the running time for a class of acyclic and cyclic queries. Our lower bounds are applicable to both join processing (aka Boolean semiring) and FAQs.

Worst case optimal joins (WCOJ) provide worst case guarantees on query evaluation time for any CQ. However, WCOJ are not output sensitive, i.e., the big-O complexity expression does not contain the output size as a parameter. Further, WCOJ do not provide any meaningful guarantees for queries that are not full. For such queries, WCOJ are combined with the notion of tree decompositions to obtain tighter guarantees on the running time. In particular, <cit.> showed that using the idea of factorization, it is possible to evaluate any query in time $O(|D|^\fhw + |\out|)$ time. This result was later improved by <cit.> who showed that the running time can be further improved to $O(|D|^\subw\ + |\out|)$. These results have one principal limitation. First, the additive term only holds for full queries. If the query is not full, the $|\out|$ terms becomes multiplicative instead of additive. For non-full queries, both algorithms require an application of the celebrated Yannakakis algorithm. In <cit.>, Yannakakis showed that for any acyclic CQ $Q$ (not necessarily full) and database $D$, there exists an algorithm that can evaluate $Q(D)$ in time $O(|D| \cdot |\out|)$, where $\out$ denotes $Q(D)$. Remarkably, Yannakakis algorithm achieves optimal guarantees for the class of free-connex queries where a tighter running time guarantee of $O(|D| + |\out|)$ can be achieved. However, for arbitrary acyclic CQs, it remains unknown if Yannakakis algorithm can be improved or not.

In this paper, we will show that it is indeed possible to evaluate every acyclic CQ $Q$ in time $O(|D| \cdot |\out|^{1-f(Q)})$ where $f(Q)$ is a constant smaller than one and depends only on the query $Q$.

§ PRELIMINARIES AND NOTATION

change into hypergraphs notations - i.e. the ones used in  paper

use $\chi(s) \cap \chi(t)$ for join variables

use $P$ for head variables

use $P_t$ for head variables present at the subtree rooted at $t$

Conjunctive Queries We associate a Conjunctive Query ($\cq$) $Q$ to a hypergraph
$\mH = (\mV,\mE)$, where $\mV = [n]=\{1,\ldots,n\}$ and $\mE$ is a set of hyperedges; each hyperedge is a subset of $[n]$. The relations of the query are $R_J(\bx_J), J \in \mE$, where $\bx_J = (x_j)_{j\in J}$ is the schema (or variables) of $R_J$, for any $J \subseteq [n]$
The $\cq$ is:

\begin{equation}
Q(\bx_{\mF}) \cd \bigwedge_{J \in \mE} R_J(\bx_J) \label{eqn:conjunctive:query}
\end{equation}

The variables in the head of the query $\bx_\mF$ ($\mF \subseteq [n]$) are the free variables (or the projection variables). A CQ is
full if $\mF = [n]$, and it is Boolean
if $\mF = \emptyset$, simply written as $Q()$. The size $|R_J|$ of a relation $R_J$ is the number of its tuples. A database $\mD$ is a finite set of relations and the size of a database $|\mD|$ is the sum of the sizes of its relations.

We will say that a variable $x \in \mV(\mH)$ that is present in at least two relations is a join variable, while a variable that is present in exactly one relation is isolated.

Natural Joins
If a CQ is full, has no constants and no repeated variables in the same atom, then we
say it is a natural join query. For instance,
the triangle query $\Delta(x,y,z) = R(x,y), S(y,z), T(z,x)$ is a natural join query.
A natural join can be represented equivalently as a hypergraph
$\mathcal{H} = (\nodes, \edges)$, where $\nodes$ is the set of variables, and
for each hyperedge $F \in \edges$ there exists a relation $R_F$ with variables $F$.
We write the join as $\Join_{F \in \edges} R_F$.
The size of relation $R_F$ is denoted by $|R_F|$. Given a set of variables $I \subseteq \nodes$, we define $\edges_{I} = \setof{F \in \edges}{F \cap I \neq \emptyset}$.

Valuations A valuation $v$ over a set of variables $\bx$ is a total function that maps each variable $x \in \bx$ to a value $v(x) \in \domain$, where $\domain$ is a domain of constants. Given a relation $R$ over variables $\bx$, a threshold $\Delta$, and a set $\mS \subset \bx$, we say that a valuation $v(\mS)$ is heavy if $|\sigma_{\mS = v[\mS]} (R)| > \Delta$, and light otherwise. We will use $d(v, \mS, R)$ to denote the degree  of the restriction of valuation $v$ on $\mS$ (i.e. $v[\mS]$) in relation $R$ (i.e. $|\sigma_{\mS = v[\mS]} (R)|$).

Acyclicity A CQ is said to be acyclic if it admits a join tree where each node is an atom and if any two nodes have variables in common, then all nodes along the path between them also have these variables.

Tree Decomposition A tree decomposition of a hypergraph $\mH = ([n], \mE)$ is a pair $(\tree, \chi)$ where $\tree$ is a tree and $\chi: V(\tree) \to 2^{[n]}$ maps each node
$t$ of the tree to a subset $\chi(t)$ of vertices such that

(1) Every hyperedge $F\in \mE$ is a subset of some $\chi(t)$, $t\in V(\tree)$,

(2) For every vertex $v \in [n]$,
the set $\{t \mid v \in \chi(t)\}$ is a non-empty
(connected) sub-tree of $\tree$.

The sets $e = \chi(t)$ are called the bags of the tree decomposition. We use $\chi^{-1}(e)$ to recover the node of the tree with bag $e$. A query is said to be $\alpha$-acyclic[Throughout the paper, we will use acyclic to mean $\alpha$-acyclic.] if there exists a tree decomposition such that every bag $B$ of the tree decomposition corresponds uniquely to an input relation $R_B$. Such a tree decomposition is referred to as the join tree of the query. It is known that an $\alpha$-acyclic query can be evaluated in time $O(|\mD| + |\tOUT|)$. For simplicity, we will sometimes refer to the node of a join tree through the relation assigned to the node since there is a one-to-one mapping. A rooted tree decomposition is a tree decomposition that is rooted at some node $r \in V(\tree)$ (denoted by $(\tree, \chi, r)$. Different choices of $r$ change the orientation of the tree. We will use $\mL(\tree) \subseteq V(\tree)$ to denote the set of leaf nodes of a rooted tree decomposition and $\mI(\tree) = V(\tree) \setminus \mL(\tree)$ as the set of internal nodes (i.e. all non-leaf nodes) of the rooted tree decomposition. For any node $t \in V(\tree)$ in a rooted tree decomposition, we use $\mF_t$ to denote the set of free variables that appear in the subtree rooted at $t$ (including free variables in $\chi(t)$). The subtree rooted at $t$ is denoted via $\tree_t$.

A CQ $Q$ with free variables $\mF$ is called free-connex acyclic it is $\alpha$-acyclic and the hypergraph $([n], \mE \cup \{\mF\})$ is also $\alpha$-acyclic.

Valuations and Operators A valuation $v$ over a set of variables $\bx$ is a total function that maps each variable $x \in \bx$ to a value $v(x) \in \domain$, where $\domain$ is a domain of constants. Given a tuple $t$ over schema $\mS \subseteq \bx$, $t(\mS)$ is the restriction of $t$ onto $\mS$. For a relation $R_J$ over variables $\bx_J$, a schema $\mS \subseteq \bx_J$, and a tuple $s = v(\mS)$, we define $\sigma_{\mS = s} (R) = \{t \mid t \in R_J \land t[\mS] = s\}$ as the set of tuples in $R_J$ that agree with $s$ over variables in $\mS$, and $\pi_{\mS}(R_J) = \{t(\mS) \mid t \in R_J\}$ as the set of restriction of the tuples in $R_J$ to the variables in $\mS$. The output or result of evaluating a CQ $Q$ over $\mD$ (denoted $Q(\mD$) can be defined as $\pi_{\bx_\mF} (\{ v(\bx_{[n]}) \mid v(\bx_J) \in R_J, \forall J \in \edges  \})$.
We denote by $\tOUT$ the result of running $Q$ over database $\mD$ (i.e., $\tOUT = Q(D)$) and we use $|\tOUT|$ to denote the number of tuples in $Q(D)$.

For relation $R_J$ over variables $\bx_J$, a threshold $\Delta$, and a set $\mS \subset \bx_J$, we say that a valuation $v(\mS)$ is heavy if $|\sigma_{\mS = v(\mS)} (R_J)| > \Delta$, and light otherwise. We will use $d(v, \mS, R_J)$ to denote the degree  of the restriction of valuation $v$ on $\mS$ (i.e. $v(\mS)$) in relation $R_J$ (i.e. $|\sigma_{\mS = v(\mS)} (R_J)|$).

Model of Computation We use the standard RAM model with uniform cost measure. For an instance of size $N$, every register has length $O(\log N)$. Any arithmetic operation (such as addition,
subtraction, multiplication and division) on the values of two registers can be done in $O(1)$ time. Sorting the values of $N$ registers can be done in $O(N \log N)$ time.

§ PROJECTION WIDTH

Consider a CQ $Q$ with hypergraph $\mH$ and free variables  $\bx_\mF$.
We first define the reduced query  of $Q$, denoted $\textsf{red}[Q]$ (in <cit.>, this is called a cleansed query) via Algorithm <ref>. The while-loop of the procedure essentially follows the GYO algorithm <cit.>, with the difference that we can remove isolated variables only if they are not free. The reduced query is well-defined because the resulting hypergraph after the while-loop terminates is the same independent of the sequence of vertex and hyperedge removals.
If $\mF = V(\mH)$, the procedure does not remove any variables (but may potentially remove hyperedges). If $\mF = \emptyset$, the while-loop is identical to the GYO algorithm and will return the hypergraph $(\emptyset,\{\{\}\})$.

We say that $Q$ is reduced if $Q = \textsf{red}[Q]$, i.e., the query cannot be further reduced.

acyclic $Q$ with hypergraph $\mH$ and free variables $\bx_\mF$
$\mH' \leftarrow $multihypergraph of $\mH$ *Edges $\mE'$ in $\mH'$ are a multiset
$\mH'$ has changed
$\exists$ isolated variable $x \notin \bx_\mF$$V(\mH') \gets V(\mH) \setminus \{x\}$
$\exists$ $e, f \in E(\mH')$ such that $e \subseteq f$$E(\mH') \gets E(\mH') \setminus \{e\}$

Reduced CQ

(A) [draw=black, ellipse, align=center] $x_1 {x}_2$;
[draw=none, left of=A] $R_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_4 {x}_3$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_5 {x}_2$;
[draw=none, left of=C] $R_{34}$;
[draw=none, left of=D] $R_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);
(E) [draw=black, ellipse,below of=C] ${x}_4 {x}_6$;
[draw=none, left of=E] $R_{46}$;
(F) [draw=black, ellipse,below of=D] ${x}_5 {x}_7$;
[draw=none, left of=F] $R_{57}$;

The graph $G^\exists_Q$.

(A) [draw=black, ellipse, align=center] ${x}_2$;
[draw=none, left of=A] $R'_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R'_{23}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_3$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_2$;
[draw=none, left of=C] $R'_{34}$;
[draw=none, left of=D] $R'_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);
(E) [draw=black, ellipse,below of=C] $ $;
[draw=none, left of=E] $R'_{46}$;
(F) [draw=black, ellipse,below of=D] $ $;
[draw=none, left of=F] $R'_{57}$;

Hypergraph after removing free variables.

(A) [draw=black, ellipse, align=center] $x_1 {x}_2$;
[draw=none, left of=A] $R_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[draw=none, right of=B, xshift = 80pt] $Q_1(\bx_{145}) \leftarrow R_{12} \wedge R_{23} \wedge R_{34} \wedge R_{25}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_4 {x}_3$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_5 {x}_2$;
[draw=none, left of=C] $R_{34}$;
[draw=none, left of=D] $R_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);
(E) [draw=black, ellipse,below of=C] ${x}_4 {x}_6$;
[draw=none, left of=E] $R_{46}$;
(F) [draw=black, ellipse,below of=D] ${x}_5 {x}_7$;
[draw=none, left of=F] $R_{57}$;
[draw=none, left of=E, xshift = -50pt] $Q_2(\bx_{46}) \leftarrow R_{46}$;
[draw=none, right of=F, xshift = 30pt] $Q_3(\bx_{57}) \leftarrow R_{57}$;

Depiction of the graph $G^\exists_Q$ and the decomposition of the running example query $Q(\bx_{14567}) \leftarrow R_{12}(\bx_{12}) \wedge R_{23}(\bx_{23}) \wedge R_{34}(\bx_{34}) \wedge R_{25}(\bx_{25}) \wedge R_{46}(\bx_{46}) \wedge R_{57}(\bx_{57})$

The following two properties of reduced queries will be important in this section.

An acyclic $Q$ is free-connex acyclic if and only if all the variables of $\textsf{red}[Q]$ are free.

Let $Q$ be a reduced acyclic CQ, and $\tree$ be a join tree of $Q$.

Then, every leaf node of $\tree$ has an isolated free variable.

Suppose there exists a leaf node $t$ that violates the desired property. First, we establish that $\chi(t)$ contains free variable(s). For the sake of contradiction, let us assume that $\chi(t)$ contains no free variable. Since all isolated variables have already been removed, it must be the case that all remaining variables in $\chi(t)$ are also present in its parent and thus are join variables. However, such hyperedges are removed by <ref> of <ref>. Therefore, $\chi(t)$ must contain free variable(s).

Next, suppose that the free variable is not isolated. Then, it must be the case that the free variable is also present in the parent (otherwise it would be isolated). By the same argument as before, since all other variables in $\chi(t)$ are also present in the parent, we get a contradiction since such hyperedges are removed by <ref>. This concludes the proof.

Second, we define the decomposition of a CQ $Q$ following <cit.>. Define the graph $G^\exists_Q$, where each hyperedge is a vertex, and there is an edge between $e,e'$ if they share a non-free variable. Let $E_1, \dots, E_k$ be the connected components of $G^\exists_Q$. Then, the decomposition of $Q$, denoted $\textsf{decomp}(Q)$, is a set of queries $\{Q_1, \dots, Q_k\}$, where $Q_i$ is the CQ with hypergraph $(\bigcup_{e \in E_i} e, E_i)$ and free variables $\mF \cap \bigcup_{e \in E_i} e$. If the decomposition of $Q$ has exactly one query, we say that $Q$ is existentially connected.

Consider an acyclic CQ $Q$. Then, $\wout(Q)$ is the maximum number of relations across all queries in $\textsf{decomp}(\textsf{red}[Q])$.

Consider the query

$$Q^\star_\ell(x_1, \dots, x_\ell) \leftarrow R_1(x_1,y) \wedge \dots \wedge R_k(x_\ell,y).$$

One can observe that $\textsf{red}[Q^\star_\ell] = Q^\star_\ell$. The decomposition of the reduced query has only one connected component with $\ell$ atoms, hence $\wout(Q^\star_\ell) = \ell$.

Consider the query $Q(\bx_{14567}) \leftarrow R_{12}(\bx_{12}) \wedge R_{23}(\bx_{23}) \wedge R_{34}(\bx_{34}) \wedge R_{25}(\bx_{25}) \wedge R_{46}(\bx_{46}) \wedge R_{57}(\bx_{57})$. Note the query is already reduced since there are no isolated variables or any hyperedges that are contained in another. To compute the projection width of the query, <ref> shows the graph $G^\exists_Q$ where each atom of the query becomes a vertex. Note that there is no edge between $R_{34}$ and $R_{46}$ because $x_4$ is a free variable. This graph has three connected components, and the largest connected component contains four hyperedges, hence $\wout(Q(\bx_{14567})) = 4$. <ref> also shows the three queries corresponding to each connected component of $G^\exists_Q$.

We observe that $1 \leq \wout(Q) \leq |E(\mH)|$, and also that $\wout(Q)$ is always an integer. When $Q$ is full, every hyperedge of the reduced hypergraph forms its own connected component of size one; in this case, $\wout(Q)=1$. More generally:

An acyclic CQ $Q$ is free-connex acyclic if and only if $\wout(Q)=1$.

Suppose that $Q$ is free-connex. From Proposition <ref>, $\textsf{red}[Q]$ has only free variables. Hence, in the decomposition every hyperedge forms a connected component of size one. Thus, $\wout(Q)=1$.

For the other direction, suppose that $\wout(Q)=1$. Let us examine the reduced query $Q' = \textsf{red}[Q]$. Then, every query in the decomposition of $Q'$ has size one. However, this implies in turn that all variables of $Q'$ are free; indeed, if there exists a non-free variable $x$, the variable $x$ would be isolated and that would violate the fact that $Q'$ is reduced.  From Proposition <ref>, we now have that $Q$ is free-connex acyclic.

Hu <cit.> defined a notion similar to $\wout(Q)$, called free-width, $\textsf{freew}(Q)$. To compute free-width, we define the free-width of an exisentially connected query to be the size of the smallest set of hyperedges that covers all isolated variables in. Then, $\textsf{freew}(Q)$ is the maximum freewidth over all queries in the decomposition of $Q$. It is easy to see that $\textsf{freew}(Q) \leq \wout(Q)$.

§ MAIN RESULT

In this section, we describe our main result that builds upon the celebrated Yannakakis's algorithm. First, we recall the algorithm and its properties as outlined in <cit.>.
Yannakakis showed two key properties of <ref>. First, when the processing of a node $s$ is over (i.e. when the algorithm has finished execution of <ref> for node $s$), it holds that

$$T_{\chi(s)} = \pi_{\mF_{s} \cup \chi(s)} (\wedge_{B \in V(\tree_{s})} R_{\chi(B)})$$

Therefore, when only node $r$ is left in the tree, then $T_{\chi(r)} = \pi_{F_{r} \cup \chi(r)} (\wedge_{B \in V(\tree)} R_{\chi(B)})$, and thus, $\pi_{\bx_\mF} (T_{\chi(r)})$ gives the desired result. Second, Yannakakis showed that the entire algorithm takes time $O(|\mD|+|\mD| \cdot |\tOUT|)$, which is the time taken to execute <ref> in each iteration.

acyclic query $Q(\bx_\mF)$, database instance $\mD$, rooted join tree $(\tree, \chi,r)$
$\mD \leftarrow $ apply a full reducer for $\mD$

$K \leftarrow \text{a queue of } V(\tree)$ following a post-order traversal of $\tree$

$K \neq \emptyset$
$s \leftarrow K.\textit{pop}()$
$s$ is a leaf
$T_{\chi(s)}(\bx_{\chi(s)}) \leftarrow R_{\chi(s)}(\bx_{\chi(s)})$

$T_{\chi(s) \cup \mF_s}(\bx_{\chi(s) \cup \mF_s}) \leftarrow R_{\chi(s)} \wedge \left(\bigwedge_{(s, t) \in E(\tree)} \pi_{F_t \cup (\chi(s) \cap \chi(t))} T_{\chi(t)} \right)$

$\chi(s) \leftarrow \chi(s) \cup \mF_s$

Yannakakis Algorithm <cit.>

§.§ Output-sensitive Yannakakis

This section presents a general lemma that forms the basis of our main result. In particular, we will show that under certain restrictions of the instance and the root of the join tree, <ref> (Yannakakis algorithm) achieves a better runtime by a factor of $\Delta$. In the next section, we will present an algorithm that takes advantage of this observation.

The first condition is that the root node must contain an isolated free variable. This is not necessarily true for any node in the join tree, but we can make it happen by choosing the root to be a leaf (recall that in a reduced instance, every leaf node has an isolated free variable). The second condition is that all valuations in the root node over the join variables are heavy w.r.t. a degree threshold $\Delta$. This is not generally true (unless $\Delta=1$), so we will need to partition the instance to achieve this requirement.

For a join tree $(\tree,\chi)$, we define $\chi^\Join(s) \subseteq \chi(s)$ to return only the join variables of $\chi(s)$.

Let $Q(\bx_\mF)$ be a reduced acyclic CQ, $(\tree, \chi,r)$ a rooted join tree of $Q$, and $\mD$ be a database instance. Suppose that

* $R_{\chi(r)}$ has at least one isolated free variable

* for every $v \in R_{\chi(r)}$, we have $d(v, \chi^\Join(r), R_{\chi(r)}) > \Delta$ for some integer $\Delta \geq 1 $.

Then, <ref> runs in time $O(|\mD| + (\sum_{t \in \mI(\tree)} |R_{\chi(t)}|) \cdot |\tOUT|/\Delta)$.

(V) [draw=black, ellipse, minimum width=50pt,align=center,label=left:$R_{\chi(r)}$] $\chi(r)$;
(E) [draw=none, below of=V] $\vdots$;
[->] (V) edge node[draw=none]  (E);
(F) [draw=black, ellipse, below of=E, minimum width=50pt,align=center,label=left:$R_{\chi(s)}$] $\chi(s)$;
(G) [draw=black, ellipse, below of=F, xshift=-120pt, yshift=-20pt, minimum width=50pt,align=center,label=left:$R_{\chi(t_1)}$] $\chi(t_1)$;
[->] (F) edge node[draw=none, xshift=-5pt, label=left:$\chi(t_1) \cap \chi(s)$]  (G) ;
(H) [draw=black, ellipse, below of=F, yshift=-20pt,minimum width=50pt,align=center,label=left:$R_{\chi(t_2)}$] $\chi(t_2)$;
[->] (F) edge node[draw=none,xshift=5pt, label=left:$\chi(t_2) \cap \chi(s)$]  (H);
(I) [draw=none, right of=H, xshift=25pt] $\dots$;
(J) [draw=black, ellipse, right of=I, xshift=40pt, minimum width=50pt,align=center,label=left:$R_{\chi(t_k)}$] $\chi(t_k)$;
[->] (F) edge node[draw=none, label=right:$\chi(t_k) \cap \chi(s)$, minimum width=50pt,xshift=10pt]  (J);

A join tree with root node $r$. Edge labels show the common variables between bag $\chi(s)$ and bag $\chi(t_i)$.

To prove this result, we will show that the size of the intermediate result that is materialized in <ref> for an internal node $s$ is bounded by $|\tOUT| \cdot (|R_{\chi(s)}| / \Delta)$.

Consider the point in the algorithm where we join the node $s$ with its children nodes $t_1, \dots, t_k$, as shown in Figure <ref>. Let $v$ be any valuation over the variables $\bx$ such that $v(\bx_\mF) \in Q(\mD)$. We first claim the following inequality:

$$\prod_{i \in [k]}d(v, \chi(t_i) \cap \chi(s), R_{\chi(t_i)}) \leq |\tOUT|/\Delta$$

To show this, let $Z$ be the set of all variables except for the isolated free variables in the nodes $r,t_1, \dots, t_k$. Then, the number of output tuples that agree with valuation $v$ on $Z$ is:

$$A_v = d(v, \chi^\Join(r), R_{\chi(r)}) \cdot \prod_{i \in [k]}d(v, \chi(t_i) \cap \chi(s), R_{\chi(t_i)}) $$

To see why this holds, note that $R_{\chi(r)}$ has at least one isolated free variable, and $Z$ fixes all join variables in the relation, hence we can extend $v(Z)$ in node $r$ exactly $d(v, \chi^\Join(r), R_{\chi(r)})$ times. Additionally, $Z$ fixes all join variables in $R_{\chi(t_i)}$, which are $\chi(t_i) \cap \chi(s)$. Since the query is reduced, every leaf node has an isolated free variable; hence, we can extend $v(Z)$ in node $t_i$ exactly  $d(v, \chi(t_i) \cap \chi(s), R_{\chi(t_i)})$ times.
To finish the claim, note that $|A_v| \leq |\tOUT|$ and also from assumption (2) of the lemma, we have that $d(v, \chi^\Join(r), R_{\chi(r)}) > \Delta$.

To complete the proof, let $W = \chi(s) \cap (\bigcup_{t \in [k]} \chi(t_i))$. We observe that the size of the intermediate bag  $\pi_{\chi(s) \cup \mF_s} (R_{\chi(s)} \wedge  R_{\chi(t_1)} \wedge \dots \wedge R_{\chi(t_k)})$ can be bounded by

\begin{align*}
&  \sum_{v \in \pi_{W} (R_{\chi(s)})} d(v, W, R_{\chi(s)}) \cdot \prod_{i \in [k]} d(v, \chi(t_i) \cap \chi(s), R_{\chi(t_i)}) \\ &\leq \frac{|\tOUT|}{\Delta} \cdot \sum_{v \in \pi_{W} (R_{\chi(s)})} d(v, W, R_{\chi(s)})
\leq \frac{|\tOUT|}{\Delta} \cdot |R_{\chi(s)}|
\end{align*}

Here, the first inequality holds since we argued that for the degree product bound holds for all valuations. Observe that the time bound requires only using the size of the relation assigned to the parent of the leaf nodes (and not the sizes of the relations in the leaf nodes itself).

Discussion Observe that <ref> degenerates to the standard bound of Yannakakis algorithm for $\Delta = 1$. However, as we will show in the next part, choosing $\Delta > 1$ can lead to better overall join processing algorithms. It is also interesting to note that the running time bound obtained in <ref> can only be achieved when the root of the decomposition is a relation with the two properties as outlined in the statement. It can be shown that no other choice of the root node achieves a time better than $O(|\mD| \cdot |\tOUT|)$.

§.§ Our Algorithm

In this section, we will present the algorithm for our main result. We will first consider a CQ $Q$ that is existentially connected and reduced.

Algorithm <ref> shows the improved procedure. It processes the nodes of the join tree in a leaf-to-root order just like Yannakakis algorithm. However, our algorithm departs in its processing of each leaf. In particular, we start from node $s$ whose children are all leaves. For every leaf node $t$ that is a child of $s$, we partition the relation $R_t$ assigned to the node into two disjoint partitions (the heavy partition $R^H_t$ and the light partition $R^L_t$) using a chosen degree threshold. Then, we use <ref> to process $R^H_t$ and add the produced output into a set $\mJ$. This processing is done in lines <ref>-<ref> of the while loop. The crucial detail is that the processing of the heavy partition is done by reorienting the join tree to be rooted at $t$, and then applying Yannakakis in a bottom-up fashion.

Once all heavy sub-relations of the leaf nodes are processed, we are left with all light parts of the relations for the children of node $s$. At this point, we join the relations in the subtree rooted at $s$ (line <ref>) and then remove the nodes for children of $s$ from the join tree $\tree$(line <ref>). These two steps are identical to the steps in line <ref> and line <ref> of the Yannakakis algorithm respectively. We next state and prove the main result.

OInputOptional Input
acyclic query $Q(\bx_\mF)$, instance $\mD$, join tree  $(\tree, \chi)$, $1 \leq \Delta \leq |\mD|$

$Q(\mD), (\tree, \chi), \mD$

choose an arbitrary root $r$ for $\tree$

$\mD := (T_{\chi(s)})_{s \in V(\tree)} \leftarrow $ apply a full reducer for $\mD$

$N \leftarrow |\mD|$ *storing the size of the input

$K \leftarrow \text{a stack of } s \in V(\tree)$ following a post-order traversal of $\tree$

$K \neq \emptyset$
$s \leftarrow K.\textit{pop}()$

( )$s$ is a leaf
$s \neq r$*every leaf contains isolated free variable(s)
$\Delta_s \leftarrow \Delta \cdot (|T_{\chi(s)}| + N)/ N$
$T_{\chi(s)}^H \leftarrow \{\bv \in T_t \mid |\sigma_{ \bv[\chi^\Join(t)]}(R_t)| > \Delta_s \}, \; T_{\chi(s)}^L \leftarrow T_{\chi(s)} \setminus T_{\chi(s)}^H$
$\mD^H_s \leftarrow (\mD \setminus T_{\chi(s)}) \cup T_{\chi(s)}^H$
let $Q_s(\mD^H_s)$ be the output of <ref> with input as $\mD^H_s$ and $\tree$ rooted at $s$
$\mathcal{J} \leftarrow \mathcal{J} \cup Q_s(\mD^H_s)$
$T_{\chi(s)} \leftarrow T_{\chi(s)}^L$
$\mD \leftarrow $ apply a full reducer for $(\mD \setminus T_{\chi(s)}) \cup T_{\chi(s)}^L$

$T_{\chi(s) \cup \mF_s}(\bx_{\chi(s) \cup \mF_s}) \leftarrow T_{\chi(s)} \wedge \left(\bigwedge_{(s, t) \in E(\tree)} \pi_{F_t \cup (\chi(s) \cap \chi(t))} T_{\chi(t)} \right)$
$\chi(s) \leftarrow \chi(s) \cup \mF_s$
truncate all children of $s$ and directed edges $(s, t) \in E(\tree)$ from $\tree$
$K \neq \emptyset$
$K.\textit{push}(s)$ *$s$ is now a leaf,  process $s$ in the  next iteration

$\mathcal{J} \leftarrow \mathcal{J} \cup \pi_{\mF}(T_{\chi(r)})$  *$s$ is the only node left

$\mathcal{J}, (\tree, \chi), \mD$ *Return output, tree decomposition, and instance
Generalized Yannakakis Algorithm

Given an acyclic join query $Q(\bx_\mF)$ that is existentially connected and reduced, database $\mD$, and an integer threshold $1 \leq \Delta \leq |\mD|$, <ref> computes the join result $Q(\mD)$ in time $O(|\mD| \cdot \Delta^{k-1} + |\mD| \cdot |\tOUT|/\Delta)$, where $k$ is the number of atoms in $Q$.

We begin with a simple observation: the only step in the algorithm that modifies the join tree is the join operation on line <ref>. In any given iteration of the while loop, once the join on line <ref> is computed, node $s$ becomes a leaf node in the join tree since we delete all its children right after. Let $N$ denote the size of the input database[We do not use $|\mD|$ in the proof to avoid any confusion since the algorithm modifies $\mD$ repeatedly.]. Then, we get the following.

After every iteration of the while loop, it holds that all relations corresponding to the internal nodes of the join tree have size $O(N)$.

Let us now bound the time required to process all leaf nodes. Fix a leaf node $s$. Except the operation on line <ref>, all other operations take at most $O(N)$ time (note that $\mD$ is also modified in every iteration of the inner loop). We claim that  line <ref> takes time $O(N \cdot |\tOUT|/\Delta)$. By our choice of root node (which is $s$) for calling Lemma <ref>, $\tree$ is rooted at $s$. Further, note that the leaves of $(\tree,s)$ are the same leaves as $(\tree,r)$ (except for $s$, which is now the root). Further, by <ref>, it is also guaranteed that the bag of $s$ contains isolated free variable(s). Thus, the conditions of applying Lemma <ref> are satisfied. Since our choice of threshold for the partition is $\Delta_s$, Lemma <ref> tells us that the evaluation time required is at most big-O of

$$\left(\sum_{B \in \mI(\tree)} |T_{\chi(B)}|\right)  \cdot |\tOUT|/\Delta_s = (|T_\chi(s)| + N) \cdot |\tOUT|/\Delta_s = N \cdot |\tOUT|/\Delta $$

Here, the first equality holds because of <ref> which guarantees that only $s$ can have $\Omega(N)$ size. The reader can verify that $\Delta \leq \Delta_s$, and thus, is well-defined.

Next, we will bound the time required for the join operation on line <ref>. For any node $s$, let $\#s$ denote the number of nodes in the subtree rooted at $s$ (including $s$). We will show by induction that time required for the join is $O(N \cdot \Delta^{\#s-1})$.

Base Case. In the base case, consider the leaf nodes with relations of size $N$. Consider such a leaf $\ell$ and note that the relation size satisfies $O(N \cdot \Delta^{\#\ell - 1}) = O(N)$ since the number of nodes a subtree rooted at a leaf is one (the leaf itself).

Inductive Case. Now, consider a node $s$ that is not a leaf.  The size of the relation for its child node $t$ is $O(N \cdot \tau^{\#t-1})$. For $t$, the degree threshold for partitioning the relation is $\Delta_t = \Delta \cdot (N \cdot \Delta^{\#t-1} +N) / N \leq 2 \Delta^{\#t}$. Therefore, by making the same argument as in the proof of <ref>, we get the degree product as $\Pi_{t \in \text{child of } s} \Delta_{t} = O(\Delta^{\sum_{t \in \text{child of } s} \#t}) = \Delta^{\#s-1}$. Thus, the join time and the size of $R_{\chi(s)}$ is  $O(N \cdot \Delta^{\#s-1})$. Since the tree contains $|\tree|$ number of nodes, the total time required is dominated by the last iteration, giving us $O(N \cdot \Delta^{|\tree|-1})$.

In each iteration of the while loop, one node of the tree is processed. Thus, the total number of iterations is $|\tree|=k$ and the total running time of the algorithm is $O(N \cdot \Delta^{k-1} + N \cdot |\tOUT|/\Delta)$.

(A) [draw=black, ellipse, align=center] $x_1 {x}_2$;
[draw=none, left of=A] $R_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[draw=none, above of=A, yshift = -10pt] $Q_1(\bx_{145}) \leftarrow R_{12} \wedge R_{23} \wedge R_{34} \wedge R_{25}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_4 {x}_3$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_5 {x}_2$;
[draw=none, left of=C] $R_{34}$;
[draw=none, left of=D] $R_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);

The Join tree for query ${Q_1}$

(A) [draw=black, ellipse, align=center] $x_3 {x}_4$;
[draw=none, left of=A] $R^H_{34}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_1 {x}_2$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_5 {x}_2$;
[draw=none, left of=C] $R_{12}$;
[draw=none, left of=D] $R_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);

Applying <ref> with $R^H_{34}$ as root node.

(A) [draw=black, ellipse, align=center] $x_2 {x}_5$;
[draw=none, left of=A] $R^H_{25}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_1 {x}_2$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_3 {x}_4$;
[draw=none, left of=C] $R_{12}$;
[draw=none, left of=D] $R^L_{34}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);

Applying <ref> with $R^H_{25}$ as root node.

(A) [draw=black, ellipse, align=center] $x_1 {x}_2$;
[draw=none, left of=A] $R_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_3$;
[draw=none, left of=B] $R_{23}$;
[-] (A) edge node[draw=none]  (B);
(C) [draw=black, ellipse,below of=B, xshift = -40pt] ${x}_4 {x}_3$;
(D) [draw=black, ellipse,below of=B, xshift = 40pt] ${x}_5 {x}_2$;
[draw=none, left of=C] $R^L_{34}$;
[draw=none, left of=D] $R^L_{25}$;
[-] (B) edge node[draw=none]  (C);
[-] (B) edge node[draw=none]  (D);
(rect) at (B) [draw,thick,dashed,minimum width=5.5cm,minimum height=2.15cm,yshift=-0.5cm,xshift=-0.2cm] ;
[draw=none, left of=rect,xshift=-1.2cm, yshift=0.8cm] $R_{245}$;

Joining the relations in subtree rooted at $R_{23}$

(A) [draw=black, ellipse, align=center] $x_2 {x}_4 x_5$;
[draw=none, left of=A,xshift=-10pt] $R^H_{245}$;
(B) [draw=black, ellipse, below of=A] ${x}_1 {x}_2$;
[draw=none, left of=B] $R_{12}$;
[-] (A) edge node[draw=none]  (B);

Applying <ref> with $R^H_{245}$ as root node.

(A) [draw=black, ellipse, align=center] $x_1 {x}_2$;
[draw=none, left of=A] $R_{12}$;
(B) [draw=black, ellipse, below of=A] ${x}_2 {x}_4 x_5$;
[draw=none, left of=B,xshift=-10pt] $R^L_{245}$;
[-] (A) edge node[draw=none]  (B);

Joining the remaining relations.

Evaluating the running example query using <ref>. Each figure shows a rooted join tree.

We use the query $Q_1$ shown in <ref> as an example to demonstrate the execution of <ref>. The join tree will be visited in the order $K = \{\chi^{-1}(\bx_{34}), \chi^{-1}(\bx_{25}), \chi^{-1}(\bx_{23}), \chi^{-1}(\bx_{12})\}$.
We first visit node for $R_{34}$ and since it is a leaf node, we apply <ref> with the root node as the heavy partition $R^H_{34}$ as shown in <ref>. Once the heavy partition has been processed, we replace $R_{34}$ with $R^L_{34}$ in the input database (<ref>), which will be used in all subsequent iterations of the algorithm. Next, we process leaf node $R_{25}$ by again calling <ref> with heavy partition $R^H_{25}$ as the root. $R_{25}$ is then replaced with $R^L_{25}$ in $\mD$.

Now, both leaf nodes have their relations replaced by the light partitions. When we process node $R_{23}$, a non-leaf relation, we join all relations in the subtree rooted at $R_{23}$ (shown in dashed rectangle in <ref>). Thus, the query $Q'(\bx_{245}) \leftarrow R^L_{34} \wedge R^L_{25} \wedge R_{23}$ is evaluated, the variables in the bag for the node are replaced with $\bx_{245}$ and the relation is the output of the query $Q'(\bx_{245})$. Leaf nodes $R^L_{25}$ and $R^L_{34}$ are deleted, and $R_{245}$ becomes a leaf node. $\chi^{-1}(\bx_{245})$ is added to the front of $K$ on line <ref>. Therefore, in the next iteration, we take the heavy partition $R^{H}_{245}$ and apply <ref>. Finally, we visit the node for $R_{12}$, process the join $Q''(\bx_{145}) \leftarrow R_{12} \wedge R^L_{245}$ (<ref>) and the root node bag is modified to $\bx_{145}$ with relation as the result $R_{145} = Q''(\bx_{145})$. $R^L_{245}$ is deleted. At this point $K = \emptyset$, and we union $Q''(\bx_{145})$ and $\mJ$ on <ref>. Since the entire tree is now processed, the while loop terminates, and the final result $\mJ$ is returned.

Finding the optimal threshold $\Delta$ To find the optimal threshold that minimizes the running time of <ref>, we can equate the two terms in the running time expression of <ref> to obtain $\Delta = |\tOUT|^{1/k}$, giving us the running time as $O(|\mD| \cdot |\tOUT|^{1 - 1/k})$. However, the value of $|\tOUT|$ is not known apriori. To remedy this issue, we use the oft-used doubling trick <cit.> that was first introduced in the context of multi-armed bandit algorithms. The key idea is to guess the value of $|\tOUT|$. Suppose the guessed output size is $T$ and let $\alpha$ be a constant value that is an upper bound of the constant hidden in the big-O runtime complexity of <ref>. We start with an estimate of $T_1 = 2^0$ in the first round and run the algorithm. If the algorithm does not finish execution in $\alpha \cdot |\mD| \cdot T_i^{1 - 1/k}$ steps, then we terminate the algorithm and pick the new estimate to be $T_{i+1} = 2 \cdot T_{i}$ and re-run the algorithm. However, if the algorithm finishes, then we have successfully computed the query result. Note that $\alpha$ can be determined by doing an analysis of the program and counting the number of RAM model operations required for each line. It is easy to see that the algorithm will terminate within $2 \cdot |\tOUT|$ rounds and the total running time is $\alpha \cdot |\mD| \cdot \sum_{i \in [\lceil \log_2 (2 \cdot |\tOUT|) \rceil]} T_i^{1 - 1/k} = \alpha \cdot |\mD| \cdot \sum_{i \in [ \lceil \log_2 (2 \cdot |\tOUT|) \rceil]} 2^{i \cdot (1 - 1/k)} = O(|\mD| \cdot |\tOUT|^{1 - 1/k})$ for any $k \geq 2$. Formally:

Given an reduced and existentially connected acyclic query $Q(\bx_\mF)$, and a database $\mD$, we can compute $Q(\mD)$ in time $O(|\mD| + |\mD| \cdot |\tOUT|^{1 - 1/k})$, where $k$ is the number of atoms in $Q$.

We note that the doubling trick argument for join evaluation is not a novelty and it has been used in prior works as well <cit.>. This idea can also be applied to the results obtained in <cit.>, allowing us to shave the polylog factors theoretically in the total running time and removing the need to estimate the output size via sophisticated algorithms.

General CQs Finally, we discuss what happens for a general acyclic CQ that may not be reduced or existentially connected. In this case, we can relate the runtime of the algorithm to the projection width we defined in the previous section. Note that for a CQ that is reduced and existentially connected, $\wout$ is exactly the number of atoms in the query.

Given an acyclic CQ $Q$ and a database $\mD$, we can compute the output $Q(\mD)$ in time $O(|\mD| + |\tOUT|+|\mD| \cdot |\tOUT|^{1 - 1/\wout(Q)})$.

This result follows exactly the argument in <cit.>, which shows that the runtime of an evaluation algorithm for $Q$ can be reduced to the computation of each query in $\textsf{decomp}(\textsf{red}[Q])$. In particular, as a first step it can be shown that we can compute in linear time an instance $\mD'$ such that $Q(\mD) \leftarrow \textsf{red}[Q](\mD')$; this is done by doing semijoins in the same order as the GYO algorithm.

As a second step, we use <ref> to compute each query $Q_i \in \textsf{decomp}(\textsf{red}[Q])$ in time $O(|\mD| + |\mD| \cdot |Q_i(\mD)|^{1 - 1/k_i})$, where $k_i$ is the number of atoms in $Q_i$. Then, we materialize each query and compute $Q(\mD)$ by doing the join $\bigwedge_i Q_i(\mD)$. This join query corresponds to a free-connex acyclic CQ, so it can be evaluated in time $O(|\mD| + \sum_i |Q_i(\mD)| + |Q(\mD)|) = O(|\mD| + |\tOUT|)$. The desired claim follows from the fact that projection width is defined as the maximum number of atoms in any query $Q_i$ of the decomposition.

acyclic hypergraph $\mH$, free variables $\mF$, Database $\mD$
Query result
$\mD \leftarrow $ apply a full reducer for $\mD$

$Q \in \textsf{decomp}(\textsf{red}[Q])$
$R^C(\mF_C) \leftarrow Q^C(D)$

$\pi_{\mF} (\wedge_{C \in \{C_1, \dots, C_\ell\}} R^C(\mF_C))$  *Query is a full acyclic CQ
CQ Evaluation

§ EXTENSION TO AGGREGATION

Semirings  A tuple $\bS = (\boldsymbol{D}, \oplus, \otimes, \mathbf{0}, \mathbf{1})$ is a (commutative) semiring if $\oplus$ and $\otimes$ are binary operators over $\boldsymbol{D}$ for which:

* $(\boldsymbol{D}, \oplus, \zerobf)$ is a commutative monoid with additive
identity $\zerobf$ (i.e., $\oplus$ is associative and commutative, and $a \oplus 0 = a$ for all $a \in D$);

* $(\boldsymbol{D}, \otimes, \onebf)$ is a (commutative) monoid with multiplicative
identity $\onebf$ for $\otimes$;

* $\otimes$ distributes over $\oplus$, i.e., $a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$ for $a, b, c \in \boldsymbol{D}$; and

* $a \otimes \zerobf = \zerobf$ for all $a \in \boldsymbol{D}$.

Such examples include the Boolean semiring $\mathbb{B}$ = $(\{ \textsf{false}, \textsf{true} \} , \vee, \wedge, \textsf{false}, \textsf{true})$, the natural numbers semiring $(\mathbb{N}, +, \cdot, 0, 1)$, and the tropical semiring $\mathsf{Trop}^{+}=\left(\mathbb{R}_{+} \cup\{\infty\}, \min ,+, \infty, 0\right)$.

Functional Aggregate Queries
Green et al. <cit.> developed the idea of using annotations of a semiring to reason about provenance over natural joins. That is, every relation $R_J$ is now a $\bS$-relation, i.e., each tuple in $R_J$ is annotated by an element from the domain $\boldsymbol{D}$ of $\bS$. Tuples not in the relation are annotated by $\zerobf \in \boldsymbol{D}$ implicitly. Standard relations are essentially $\mathbb{B}$-relations. Abo Khamis et al. <cit.> introduced the functional aggregate queries ($\faq$) that express join-aggregate queries via semiring annotations. A $\faq$ $\varphi$ (over a semiring $\bS$) is the following:

\begin{equation} \label{eq:sumprod-rule}
\varphi(\bx_\mF) \leftarrow \bigoplus_{\bx_{[n] \setminus \mF}} \bigotimes_{J \in \mE} R_J(\bx_J),
\end{equation}

where $(i)$ $([n], \mE)$ is the associated hypergraph of $\varphi$ (the hyperedges $\mathcal{E} \subseteq 2^{[n]}$), $(ii)$ $\bx_\mF$ are the head variables ($\mF \subseteq [n]$), and $(iii)$ each $R_J$ is an input $\bS$-relation of schema $\bx_J$ and we use $\mD = (R_J)_{J \in \mE}$ to denote an input database instance. The acyclicity notion for $\faq$s is identical to $\cq$s, through its associated hypergraph. Similar to $Q(\mD)$, we use $\varphi(\mD)$ to denote the query result of $\varphi(\bx_\mF)$ evaluated with input $\mD$, i.e. the resulting $\bS$-relation of schema $\bx_\mF$. A modification of Yannakakis algorithm (Algorithm <ref>) can handle acyclic $\faq$s  <cit.>, by lifting the natural joins at line <ref> to multiplications over the semiring domains, i.e.,

\begin{align} \label{eq:semiring-join}
T_{\chi(s) \cup F_s} \leftarrow R_{\chi(s)} (\bx_{\chi(s)})\otimes \bigoplus_{\chi(t) \setminus (F_t \cup (\chi(s) \cap \chi(t)))}T_{\chi(t)}(\bx_{\chi(t)}).
\end{align}

In this following, we show that our algorithm (<ref>) can be similarly extended to evaluate acyclic $\faq$s. We obtain the following result.

Given an acyclic $\faq$ query $\varphi(\bx_\mF)$ over a semiring $\bS$, database $\mD$, we can compute the output $\varphi(\mD)$ in time $O(|\mD| + |\tOUT|+|\mD| \cdot |\tOUT|^{1 - 1/\wout(Q)})$.

The algorithm needs three simple augmentations from <ref>. First, for processing a heavy leaf at line <ref>, call the modified Yannakakis algorithm for the sub-$\faq$. Second, use (<ref>) again for line <ref> instead of the natural joins. Lastly, we replace the unions for line <ref> and <ref> by $\oplus$ to aggregate back the query results of $\varphi(\bx_\mF)$. The correctness of this algorithm stems from the disjoint partitions of relations corresponding to each leaf on line <ref> of <ref>. In other words, it holds that $T_{\chi(s)} = T_{\chi(s)}^H \oplus T_{\chi(s)}^L$ and by distributivity, we have

\varphi(\mD) = \varphi \left((\mD \setminus T_{\chi(s)} ) \cup T_{\chi(s)}^H \right) \oplus \varphi \left((\mD \setminus T_{\chi(s)}) \cup T_{\chi(s)}^L \right),

where the first sub-query is evaluated upfront at line <ref>. For the latter sub-query, if the leaf $s$ is the last leaf of its parent being processed, the sub-query is directly evaluated in the next for-loop iteration at its parent level (i.e. the else branch at line <ref>). Otherwise, the relations in the database $(\mD \setminus T_{\chi(s)}) \cup T_{\chi(s)}^L$ will be further partitioned by the next sibling of $s$ in the post-order traversal. The runtime argument follows exactly from the proof of Theorem <ref>.

§ APPLICATIONS

In this section, we we apply our framework to recover state-of-the-art results, as well as obtain new results, for queries of practical interest.

§.§ Path Queries

We will first study the path queries, a class of queries that has immense practical importance. The projection width of a path query $P_k(x_1, x_{k+1})$ is $k$. Therefore, applying our main result, we get:

Given a path query $P_k(x_1, x_{k+1})$ and a database $\mD$, there exists an algorithm that can evaluate the path query in time $O(|\mD| \cdot |\tOUT|^{1-1/k})$.

For $k=2$, our result matches the bound shown in <cit.>. Comparing our result to Hu, the bound obtained in <ref> strictly improves the results obtained by Hu for $3 \leq k \leq 5$ and matches for $k=6$ even if we assume $\omega=2$. This result suggests there is room for further improvement in the use of fast matrix multiplication to obtain tighter bounds. For $k=7$, our running time is better than the one obtained by Hu assuming the current best known value of $\omega = 2.371552$ <cit.>.

§.§ Hierarchical Queries

We show here the application of our result to hierarchical queries.  A CQ is hierarchical if for any two of its variables, either their sets of atoms are disjoint or one is contained in the other. All hierarchical queries are acyclic, and all star queries $Q^\star_\ell$ are hierarchical queries. They have $\wout(Q^\star_\ell) = \ell$, thus:

Given a star query $Q^\star_\ell(x_{[\ell]})$ and a database $\mD$, the star query can be evaluated in time $O(|\mD|+ |\mD| \cdot |\tOUT|^{1-1/\ell})$.

<ref> recovers the bound from <cit.> for star queries and thus, provides an alternate proof of the combinatorial result in <cit.> for star queries. We note that for star queries the results merely improve the analysis of the Yannakakis algorithm. In other words, Yannakakis algorithm also achieves the time bound as specified by <ref> but the routinely used upper bound of $O(|\mD| \cdot |\tOUT|)$ does not reflect that.

[xscale=1.15, yscale=1]
at (0.0, 0.0) (A)  $x_1$;
at (-1.8, -0.8) (B)  $x_2$ edge[-] (A);
at (1.8, -0.8) (C)  $x_3$ edge[-] (A);
at (-2.7, -1.6) (D)  $x_4$ edge[-] (B);
at (-1, -1.6) (E)  $x_5$ edge[-] (B);
at (0.9, -1.6) (F)  $x_6$ edge[-] (C);
at (2.7, -1.6) (G)  $x_7$ edge[-] (C);
at (-2.7, -2.4) (R)  $R_{124}(\bx_{124})$ edge[-] (D);
at (-1, -2.4) (S)  $R_{125}(\bx_{125})$ edge[-] (E);
at (0.9,  -2.4)(T)  $R_{136}(\bx_{136})$ edge[-] (F);
at (2.7,  -2.4)(U)  $R_{137}(\bx_{137})$ edge[-] (G);

Relations formed by variables arranged as a complete binary tree. Every root-to-leaf path forms a relation (labeled).

As another example, consider the query $Q(\bx_{1234}) \leftarrow R_{124}(\bx_{124}) \wedge R_{125}(\bx_{125}) \wedge R_{136}(\bx_{136}) \wedge R_{137}(\bx_{137})$ formed by the relations shown in <ref>. For this query, the projection width is four and thus, we obtain an evaluation time of $O(|\mD|+|\mD| \cdot |\tOUT|^{3/4})$. <cit.> proposed an algorithm for enumerating the results of any hierarchical query (not necessarily full) with delay guarantees after preprocessing the input. Any algorithm with preprocessing and delay guarantees can be converted into a join evaluation algorithm. Our algorithm matches the time required to evaluate hierarchical queries by converting the enumeration with delay guarantees results of <cit.> into an evaluation algorithm.

§.§ General Queries

Submodular width A function $f : 2^{\nodes} \mapsto \mathbb{R}_+$ is a non-negative set function on $\nodes$ ($\ell \geq 1$).

The set function is monotone if $f(X) \leq f(Y)$ whenever $X \subseteq Y$, and is submodular if $f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y)$
for all $X,Y\subseteq \nodes$. A non-negative, monotone, submodular set function $h$ such that $h(\emptyset)=0$ is a polymatroid.
Let $Q$ be a CQ and let $\Gamma_{\ell}$ be the set of all polymatroids $h$ on $\nodes$ such that $h(J) \leq 1$ for all $J \in \mE$. The submodular width of $Q$ is

\begin{equation} \label{eq:subw}
% \fhw(\varphi)  & \defeq \; \min_{(\mathcal{T}, \chi) \in \mathcal{F}}  \max_{h \in \Gamma_{\ell}} \max_{t \in V(\mathcal{T})} h(\chi(t)) \\
\subw(Q)  \defeq \; \max_{h \in \Gamma_{\ell}} \min_{(\mathcal{T}, \chi) \in \mathfrak{F}} \max_{t \in V(\mathcal{T})} h(\chi(t)),
\end{equation}

where $\mathfrak{F}$ is the set of all non-redundant tree decompositions of $Q$. A tree decomposition is non-redundant if no bag is a subset of another. Abo Khamis et al. <cit.> proved that non-redundancy ensures that $\mathfrak{F}$ is finite, hence the inner minimum is well-defined.

Similar to $\subw(Q)$ (<ref>), the fractional hypertree-width of a query, $\fhw(Q)$, is defined as

\begin{align*}
\fhw(Q) \defeq \; \min_{(\mathcal{T}, \chi) \in \mathcal{F}}  \max_{h \in \Gamma_{\ell}} \max_{t \in V(\mathcal{T})} h(\chi(t))
\end{align*}

For every CQ, it is known that $\subw(Q) \leq \fhw(Q)$ and $\subw(Q) = \fhw(Q) = 1$ if the query is acyclic. We can show the following result for arbitrary queryes.

Prior work <cit.> showed that given any CQ $Q$ and database $\mD$, the  algorithm can decompose the query and database instance into a constant number of pairs $(Q_i, \mD_i)$ such that $Q(D) \leftarrow \bigcup_i Q_i(\mD_i)$. Further, it is also guaranteed that each $Q_i$ is acyclic, $|\mD_i| = |\mD|^{\subw(Q)}$ (each $\mD_i$ can be computed in $\tilde{O}(|\mD|^{\subw(Q)})$ time), and $|Q_i(\mD_i)| \leq |Q(\mD)|$. Since each $Q_i$ is acyclic, we can apply our main result and obtain the following theorem.

Given a CQ $Q$ and database $\mD$, there exists an algorithm to evaluate $Q(\mD)$ in time $\tilde{O}(|\mD|^{\subw(Q)}+|\mD|^{\subw(Q)} \cdot |\tOUT|^{1-1/\max_i \wout(Q_i)})$, where $(Q_i, \mD_i)$ is the set of decomposed queries generated by $\mathsf{PANDA}$.

Consider the 4-cycle query $Q^\diamond(\bx_{123}) \leftarrow R_{12}(\bx_{12}) \wedge R_{23}(\bx_{23}) \wedge R_{34}(\bx_{34}) \wedge R_{14}(\bx_{14})$. For this query , $\subw(Q^\diamond(\bx_{123})) = 3/2$ and $\mathsf{PANDA}$ partitions $Q^\diamond(\bx_{123})$ into two queries, $Q^\diamond_1(\bx_{123}) \leftarrow S_{123}(\bx_{123}) \wedge S_{134}(\bx_{134})$ and $Q^\diamond_2(\bx_{123}) \leftarrow S_{124}(\bx_{124}) \wedge S_{234}(\bx_{234})$. It is easy to see that $\wout(Q^\diamond_1) = 1$ and $\wout(Q^\diamond_2) = 2$. Thus, the query can be evaluated in time $\tilde{O}(|\mD|^{3/2} \cdot |\tOUT|^{1/2})$. We note that <cit.> requires $\tilde{O}(|\mD|^{3/2} \cdot |\tOUT|^{5/6})$ time for the 4-cycle query $Q^\diamond(\bx_{123})$.

§ A FASTER ALGORITHM FOR PATH QUERIES

Path query $P_k$, database instance $\mD$
$\mD \leftarrow $ apply a full reducer for $\mD$

$K, K' \leftarrow $ empty stack;  $N \leftarrow |\mD|; \mJ_1, \mJ_2, \mJ_3, \mJ_4 \leftarrow \emptyset; (\tree, \chi) \leftarrow $ join tree for $P_k$
$i \in \{ \lfloor   {k}/{2} \rfloor, \dots, 1\}$

$i \in \{ \lfloor \frac{k}{2} \rfloor + 1, \dots, k \}$

$\mJ_1, (\tree',\chi'), \mD' \leftarrow$ Call <ref> with $K$ as bag  order, $(\tree, \chi), \mD$, root node as bag $\chi^{-1}(\bx_{k,k+1})$, and threshold $\Delta$
$R_{1,\lfloor   {k}/{2} \rfloor + 1}$ is the relation assigned to the leaf node in $\tree'$
$\Delta' \leftarrow |R_{1,\lfloor   {k}/{2} \rfloor + 1}(\bx_{1, \lfloor   {k}/{2} \rfloor + 1})| \cdot \Delta / |\tOUT|$
Partition $R_{1,\lfloor   {k}/{2} \rfloor + 1}$ into heavy and light subrelations
$R^H_{1, \lfloor   {k}/{2} \rfloor + 1}(\bx_{1, \lfloor   {k}/{2} \rfloor + 1}) \leftarrow \{\bv \in R_{1, \lfloor   {k}/{2} \rfloor + 1} \mid |\sigma_{ \bv[\bx_1]}(R_{1, \lfloor   {k}/{2} \rfloor + 1})| > \Delta' \}$
$\mD^H \leftarrow (\mD' \setminus R_{1, \lfloor   {k}/{2} \rfloor + 1}) \cup R^H_{1, \lfloor   {k}/{2} \rfloor + 1}$
$\mJ_2 \leftarrow $ Call <ref> on $(\tree',\chi')$ with root node as $\chi'^{-1}(\bx_{k, k+1})$ and $\mD^H$
$R^L_{1, \lfloor   {k}/{2} \rfloor + 1}(\bx_{1, \lfloor   {k}/{2} \rfloor + 1}) \leftarrow R_{1, \lfloor   {k}/{2} \rfloor + 1} \setminus R^H_{1, \lfloor   {k}/{2} \rfloor + 1}$
$\mD^L \leftarrow (\mD' \setminus R_{1, \lfloor   {k}/{2} \rfloor + 1}) \cup R^L_{1, \lfloor   {k}/{2} \rfloor + 1}$
$\mJ_3, (\tree'',\chi''), \mD'' \leftarrow$ Call <ref> with $K'$ as bag order, $(\tree', \chi'), \mD^L$, root node as bag $\chi'^{-1}(\bx_{1,\lfloor   {k}/{2} \rfloor + 1})$, and threshold $\Delta$
$\mJ_4 \leftarrow \pi_{\bx_{1, k+1}} (R^L_{1, \lfloor   {k}/{2} \rfloor + 1}(\bx_{1, \lfloor   {k}/{2} \rfloor + 1}) \wedge R_{\lfloor   {k}/{2} \rfloor + 1, k+1}(\bx_{\lfloor   {k}/{2} \rfloor + 1, k+1}))$
$\bigcup_{i \in [4]} \mJ_i$
Improved Path Query Evaluation

In this section, we show a better algorithm that improves upon <ref>.
<ref> shows the steps for evaluating a path query $P_k$. The key idea of the algorithm is to carefully choose the ordering of how the nodes in a join tree are processed. This is in contrast with <ref> and the Yannakakis algorithm where any leaf-to-root order is sufficient to get join time guarantees. Before we present the result, we note that the improved result is only applicable to path queries and its generalization to arbitrary acyclic CQs is non-trivial due to the branching structure in an acyclic CQ, which creates technical challenges for bounding intermediate result sizes. Nevertheless, the result is an exciting development for reasons outlined at the end of the section.

Given query $P_k$ and database $\mD$, there exists an algorithm to evaluate $P_k(\mD)$ in time $O(|\mD|+|\mD| \cdot |\tOUT|^{1 - 1/ \lceil (k+1)/2 \rceil})$ for any $k \geq 1$.

We analyze the running time of <ref>. It is easy to see that other than <ref>, <ref>, <ref>, and <ref>, all other steps take at most $O(|\mD|)$ time.

To compute $\mJ_1$, it takes $O(|\mD| \cdot |\tOUT|/\Delta + |\mD| \cdot \Delta^{\lfloor   {k}/{2} \rfloor - 1})$ since $K$ restricts the processing to only $\lfloor   {k}/{2} \rfloor$ relations. After $\mJ_1$ has been computed, the leaf bag of the join tree $\tree'$ will contain variables $\{1, \lfloor   {k}/{2} \rfloor + 1\}$ and the assigned relation will be $R_{1, \lfloor   {k}/{2} \rfloor + 1}$. The size of the relation is $O(|\mD| \cdot \Delta^{\lfloor   {k}/{2} \rfloor - 1})$.

Next, we partition relation $R_{1, \lfloor   {k}/{2} \rfloor + 1}$ on variable $x_1$ with degree threshold $\Delta ' =
|R_{1,\lfloor   {k}/{2} \rfloor + 1}| \cdot \Delta / |\tOUT|
=O(|\mD| \cdot \Delta^{\lfloor   {k}/{2} \rfloor} / |\tOUT|)$. After partitioning, the active domain of $x_1$ in heavy-partition $R^H_{1, \lfloor   {k}/{2} \rfloor + 1}$ is $O(|R^H_{1, \lfloor   {k}/{2} \rfloor + 1}| / \Delta') = O(|\tOUT| / \Delta)$ and thus, calling Yannakakis algorithm on <ref> takes time $O(|\mD| \cdot |R^H_{1, \lfloor   {k}/{2} \rfloor + 1}| / \Delta') = O(|\mD| \cdot |\tOUT| / \Delta)$.

At this point, all valuations for variable $x_1$ in $R^L_{1, \lfloor   {k}/{2} \rfloor + 1}$ have degree at most $\Delta'$. The next call on <ref> requires time $O(|\mD| \cdot |\tOUT|/\Delta + |\mD| \cdot \Delta^{\lceil   {k}/{2} \rceil - 1})$. This is because except the root node, all other relations are of size $O(|\mD|)$ and thus, when <ref> invokes <ref>, $R_{1, \lfloor   {k}/{2} \rfloor + 1}$ becomes a leaf node and  its size is not used in the running time expression (recall that <ref> only uses the sum of sizes of internal nodes of the join tree in its time complexity analysis). Further, observe that by the choice of $K'$, when the algorithm terminates, the join tree $\tree''$ returned will contain $R_{\lfloor   {k}/{2} \rfloor + 1, k}$ as the leaf relation and $R_{1, \lfloor k /2 \rfloor + 1}$ as the root relation.

Finally, <ref> joins the two remaining relations in $\tree''$ and returns the output to the user. The key insight here is that since $x_1$ is light, the join time can be bound as $O(|\tOUT| \cdot \Delta') = O(|\mD| \cdot \Delta^{\lfloor   {k}/{2} \rfloor})$. Putting all things together, the total running time is big-O of

$$ |\mD| \cdot |\tOUT|/\Delta + |\mD| \cdot \Delta^{\lceil   {k}/{2} \rceil - 1} + |\mD| \cdot \Delta^{\lfloor   {k}/{2} \rfloor}$$

By using the fact that $\lceil   {k}/{2} \rceil - 1 \leq \lfloor   {k}/{2} \rfloor$ and minimizing the expression, we get the optimal value of $\Delta = |\tOUT|^{1 / (\lfloor   {k}/{2} \rfloor + 1)} = |\tOUT|^{1 / \lceil   (k+1)/{2} \rceil}$ since $\lceil   (k+1)/{2} \rceil = \lfloor   {k}/{2} \rfloor + 1$ for any positive integer $k$. Observe that for the optimal choice of $\Delta$, $1 \leq \Delta' = |\mD| / |\tOUT|^{1 / (1 + \lfloor k/2 \rfloor)} \leq |\mD|$ for all values of $k$ and $|\tOUT|$, and therefore is well-defined. Thus, the total running time of the algorithm is $O(|\mD| \cdot |\tOUT|^{1 - 1/ \lceil   (k+1)/{2} \rceil})$.

Consider the $P_4(x_1, x_5) \leftarrow R_{12}(\bx_{12}) \wedge R_{23}(\bx_{23})\wedge R_{34}(\bx_{34}) \wedge R_{45}(\bx_{45})$. The algorithm sets $K = \{\chi^{-1}(\bx_{12}), \chi^{-1}(\bx_{23})\}$ and $K' = \{\chi^{-1}(\bx_{45}), \chi^{-1}(\bx_{34})\}$. First, <ref> computes the join output when variable $x_2$ is heavy and stores it in $\mJ_1$ and the returned join tree $\tree'$ contains $\bx_{13}$ as the leaf node bag with a materialized relation that corresponds to the join of $R_{12}(\bx_{12})$ and $R_{23}(\bx_{23})$ but when $x_2$ is light in $R_{12}$. In other words, we  get the relation $R_{13}$ of size $|\mD| \cdot \Delta$. Then, we partition $R_{13}$ into two sub-relations: $R^H_{13}$ and $R^L_{13}$ based on degree of $x_1$ with degree threshold $\Delta' = |\mD| \cdot \Delta^2 / |\tOUT|$. Once the partitioning is done, we compute $\mJ_2 = \pi_{x_1, x_5} (R^H_{13}(\bx_{13}) \wedge R_{34}(\bx_{34}) \wedge R_{45}(\bx_{45}))$ using Yannakakis algorithm. In the third step, we take the join tree of the subquery $\pi_{x_1, x_5} (R^L_{13}(\bx_{13}) \wedge R_{34}(\bx_{34}) \wedge R_{45}(\bx_{45}))$ rooted at bag $\bx_{13}$ and generate output $\mJ_3$ when $x_4$ is heavy in relation $R_{45}$. This step takes $O(|\mD| \cdot |\tOUT| / \Delta)$ time according to <ref>. For all light $x_4$ valuations in $R_{45}$, <ref> will compute the join of $R_{34}(\bx_{34})$ and $R_{45}(\bx_{45})$, and store the materialized result in $R_{35}(\bx_{35})$ in time $O(|\mD| \cdot \Delta)$. The final step is to compute $\pi_{x_1, x_5}(R^L_{13}(\bx_{13}), R_{35}(\bx_{35}))$ which takes $O(|\tOUT| \cdot \Delta')$ time. Balancing all the costs, we obtain $\Delta = |\tOUT|^{1/3}$ and a total running time of $O(|\mD| \cdot |\tOUT|^{2/3})$.

<ref> has important implications in the evaluation of path queries. Observe that for $k=3$, we get the running time as $O(|\mD| + |\mD| \cdot \sqrt{|\tOUT|})$, matching the lower bound shown by Hu. It is also remarkable that the optimal algorithm does not require fast matrix multiplication. Using the same ideas from <ref>, it is straightforward to adapt <ref> to allow FAQs over path queries as well.

§ LOWER BOUNDS

In this section, we demonstrate several lower bounds that show optimality for a subclass of CQs. To do this, we will use the following well-established conjectures from fine-grained complexity.

There is no real $\epsilon >0$ such that computing the $k$-clique problem (with $k \geq 3$) over the Boolean semiring in an (undirected) $n$-node graph requires time $O(n^{k-\epsilon})$ using a combinatorial algorithm.

There is no real $\epsilon >0$ such that computing the $k$-clique problem (with $k \geq 3$) over the tropical semiring in an (undirected) $n$-node graph with integer edge weights can be done in time $O(n^{k-\epsilon})$.

Our first lower bound tells us that the dependence in the bound of <ref> on both the submodular width and projection width is somewhat necessary.

Take any integer $\ell \geq 2$ and any rational $w \geq  1$ such that $\ell \cdot w$ is an integer. Then, there exists a query $Q$ with projection width $\ell$ and submodular width $w$ such that no combinatorial algorithm can compute it over input $\mD$ in time $O(|\mD|^{w} \cdot |\tOUT|^{1-1/\ell - o(1)})$ assuming the Boolean $k$-Clique Conjecture.

Consider the graph $G = (V,E)$ for which we need to decide whether there exists a clique of size $k = (\ell-1)+\ell \cdot w$. Let $n = |V|$. It will be helpful to distinguish the $k$ variables of the clique into $\ell$ variables $x_1, \dots, x_\ell$ and the remaining $k-\ell$ variables $y_1, \dots, y_{k-\ell}$. Note that $k-\ell = \ell \cdot w -1$ is an integer $\geq 1$; hence, there exists at least one $y$-variable.

We will first compute all the cliques of size $\ell$ in $G$ and store them in a relation $C(v_1, \dots, v_\ell)$; this forms the input database $\mD$. Note that this step needs $O(n^\ell)$ time, and moreover the size of $C$ is $n^\ell$. Now, consider the following query:

$$ Q (x_1, \dots, x_\ell)= U_1[x_1, y_1, \dots, y_{k-\ell}] \wedge U_2[x_2, y_1, \dots, y_{k-\ell}] \wedge \dots \wedge U_\ell[x_\ell, y_1, \dots, y_{k-\ell}]$$

where $U_i[x_i, y_1, \dots, y_{k-\ell}]$ stands for the join of following atoms:

$$ \{C(v_1, \dots, v_\ell) \mid v_1, \dots, v_\ell \text{ are all possible sets of size $\ell$ from} \{x_i, y_1, \dots, y_{k-\ell}\} \}$$

This is a well-defined expression, since $k-\ell = \ell \cdot w -1$ and $w \geq 1$. The submodular width of this query is $w$, as proved in <cit.>. It is also easy to see that its projection width is $\ell$.

Suppose now we can compute $Q$ in time $O(|\mD|^{\subw} \cdot |\tOUT|^{1-1/\ell-\epsilon} )$ for some $\epsilon > 0$. Note that $|\mD| \leq n^\ell$ and $|\tOUT| \leq n^\ell$. Hence, this implies that we can compute $Q$ on the above input in time $O(n^{w \cdot \ell + \ell -1 -\epsilon})= O(n^{k-\epsilon})$.

Once the output has been evaluated, for each tuple $t \in Q (x_1, \dots, x_\ell)$, we can verify in constant time that any two vertices $t(i)$ and $t(j)$ ($1 \leq i, j \leq \ell$) are connected via an edge. Thus, in $O(n^\ell)$ time, we can verify whether the vertices form an $\ell$-clique. Further, by our join query construction, each of the $\ell$ vertices is guaranteed to connect with a common vertex $v'$ (which corresponds to a valuation of the remaining variables $y_1, \dots, y_{k-\ell}$).

All together, this obtains a (combinatorial) algorithm that computes whether a $k$-clique exists in time $O(n^{k-\epsilon} + n^\ell) = O(n^\ell)$, contradicting the lower bound conjecture.

We next prove a general result that gives output-sensitive lower bounds for arbitrary CQs. To this end, we introduce the notion of clique embedding <cit.>. We say that two sets of vertices $X,Y \subseteq V(H)$ touch in $\mH$ if either $X \cap Y \neq \emptyset$ or there is a hyperedge $e \in E(\mH)$ that intersects both $X$ and $Y$.

Let $k \geq 3$ and $\mH$ be a hypergraph. A $k$-clique embedding, denoted as $C_k \mapsto \mH$, is a mapping $\psi$ that maps every $v \in \{1, \dots, k\}$ to a non-empty subset $\psi(v) \subseteq V(\mH)$ such that the following hold:

* $\psi(v)$ induces a connected subgraph;

* for any two $u \neq v \in \{1, \dots, k\}$ then $\psi(u), \psi(v)$ touch in $\mH$.

It is often convenient to describe a clique embedding $\psi$ by the reverse mapping $\psi^{-1}(x) = \{i \mid x \in \psi(i) \}$, for $x \in V(\mH)$.
For a hyperedge $J \in E(\mH)$, its weak edge depth is $d_{\psi}(J) := |\{v \mid  \psi(v) \cap J \neq \emptyset \}|$, i.e., the number of vertices from $V(\mH)$ that map to some variable in $J$. We also define the edge depth of $J\in E(\mH)$ as $d^+_{\psi}(J) := \sum_{v \in J} d_\psi(v)$, i.e. weak edge depth but counting multiplicity.
For an embedding $\psi$ and a hyperedge $\mF \in E(\mH)$, the $\mF$-weak edge depth of $\psi$ is defined as $\mathsf{wed}^\mF(\psi):= \max\limits_{J \in E(\mH) \setminus \mF} d_{\psi}(J)$, i.e. the maximum of weak edge depths excluding $\mF$.

Given any CQ $Q(\bx_\mF) \leftarrow \bigwedge_{J \in \mE} R_J(\mathbf{x}_J)$ and database $\mD$,
let $\psi$ be a $k$-clique embedding of the hypergraph $\mH' = ([n],E(\mH) \cup \{\mF\})$ such that $x\cdot \mathsf{wed}^\mF(\psi) + y \cdot d^+_{\psi}(\mF) \leq k$ for positive $x,y >0$.
Then, there is no combinatorial algorithm with running time $O(|\mD|^{x-\epsilon} \cdot |\tOUT|^{y-\epsilon'})$ for evaluating $Q(\mD)$ assuming the Boolean $k$-Clique Conjecture, where $\epsilon, \epsilon'$ are non-negative with $\epsilon + \epsilon' > 0$.

Construct the instance as Theorem 11 in <cit.> and observe that there exists a $k$-clique if and only if there exists a tuple in the output that is consistent with the domains in variables $\mF$. By a consistent tuple, we mean a tuple whose values associated to the same partitions of the input graph for finding $k$-clique are the same. The time and size to construct such instance $\mD$ is bounded by $O(n^{\mathsf{wed}^\mF(\psi)})$, and observe the size of $|\tOUT|$ is bounded by  $O(n^{d^+_{\psi}(\mF)})$. Thus, such output-sensitive combinatorial algorithm will yield a combinatorial algorithm for $k$-clique that runs in time
$O(n^{x\cdot (\mathsf{wed}^\mF(\psi)-\epsilon)} \cdot n^{y\cdot (d^+_{\psi}(\mF)-\epsilon')}) = O(n^{k-\epsilon''})$ for some $\epsilon'' >0$, contradicting the Boolean $k$-Clique Conjecture.

We can show an analogous result for $\faq$ queries over the tropical semiring.

Given any $\faq$ $\varphi(\bx_\mF)$ as (<ref>) and database $\mD$, let $\psi$ be a $k$-clique embedding of the hypergraph $\mH' = ([n],E(\mH) \cup \{\mF\})$ such that $x\cdot \mathsf{wed}^\mF(\psi) + y \cdot d^+_{\psi}(\mF) \leq k$ for positive $x,y >0$. Then, there exists no algorithm that evaluates $\varphi(\mD)$ over the tropical semiring in time $O(|\mD|^{x-\epsilon} \cdot |\tOUT|^{y-\epsilon'})$ assuming the Min-Weight $k$-Clique Conjecture, where $\epsilon, \epsilon'$ are non-negative with $\epsilon + \epsilon' > 0$.

Construct the instance as Theorem 11 in <cit.>. Given the output tuples, we simply check for the consistency of domains in variables $\bx_\mF$ and return the smallest annotation among consistent tuples after sorting. Observe that this procedure correctly solves the Min-Weight $k$-clique problem. The time analysis is then identical as the proof of Theorem <ref>.

Hu defined the notion of $\sfreew$ of any acyclic query and proved that any "semiring algorithm" requires $\Omega(|\mD|\cdot|\tOUT|^{1-\frac{1}{\sfreew(Q)}} + |\tOUT|)$  <cit.>. Our lower bound results subsume Hu's lower bound results. Specifically, our technique gives meaningful lower bounds for any CQ, not necessarily acyclic, where Hu's $\sfreew(Q)$ is not defined for non-acyclic CQs. Moreover, we can show that, when specializing $x=1$, there always exists a clique embedding for $Q'$ such that $y = 1-\frac{1}{\sfreew(Q)}$, matching Hu's lower bound (see Proposition <ref>).
We now apply Theorem <ref> and Theorem <ref> to get tight lower bounds for star queries (and can be extended to hierarchical queries easily).

Given any CQ $Q(\bx_\mF) \leftarrow \bigwedge_{J \in \mE} R_J(\mathbf{x}_J)$, define $Q'(\bx_\mF) \leftarrow \bigwedge_{J \in \mE} R_J(\bx_J) \wedge R(\bx_\mF)$. Then, there exists a $k$-clique embedding $\psi$ such that $\frac{k-\mathsf{wed}^\mF(\psi)}{d^+_{\psi}(\mF)} = 1 - \frac{1}{\sfreew(Q)}$.

It suffices to construct a clique embedding on the connected components that achieves $\sfreew(Q)$ after Hu's cleanse and decomposition steps <cit.>. It is straightforward to see that one can assign each element in $S$ an isolated output variable <cit.>. Consider the $(\sfreew(Q)+1)$-clique embedding $\psi$ where $\psi$ maps $\sfreew(Q)$ distinct colors to each one of those distinguished isolated output variables, and map an additional fresh color to all other variables (including all join variables and possibly some isolated output variables that are not assigned to $S$). Clearly, $\psi$ is a $(\sfreew(Q)+1)$-clique embedding for $Q'$. Moreover, $\mathsf{wed}^\mF(\psi) = 2$ and $d^+_{\psi}(\mF) = \sfreew(Q)$, and thus  $\frac{k-\mathsf{wed}^\mF(\psi)}{d^+_{\psi}(\mF)} = \frac{\sfreew(Q)+1 - 2}{\sfreew(Q)} = 1-\frac{1}{\sfreew(Q)}$, completing the proof.

Consider a star query $Q^\star_\ell$ with $\ell$ relations. Then, there exists a database $\mD$ such that no algorithm can have runtime of $O(|\mD| \cdot |Q^\star_\ell(\mD)|^{1-1/\ell-o(1)})$ subject to the Boolean $k$-clique conjecture.

The star query $Q^\star_\ell$ is defined as $Q^\star_\ell (x_1, \dots, x_\ell) = R_1(x_1,y) \wedge \dots \wedge R_\ell(x_\ell, y)$. Consider the query $(Q^\star_\ell)' (x_1, \dots, x_\ell) = R_1(x_1,y) \wedge \dots \wedge R_\ell(x_\ell, y) \wedge R(x_1, x_2, \dots, x_\ell)$. Observe that $\psi(i) = x_i$ for $1\leq i \leq \ell$ and $\psi(\ell+1) = y$ is a $(\ell+1)$-clique embedding of $(Q^\star_\ell)'$. This has $\mathsf{wed}^\mF(\psi) = 2$ and $d^+_{\psi}(\mF) = \ell $. For $x=1$ and $y = 1-1/\ell$, we have $x\cdot \mathsf{wed}^\mF(\psi) + y \cdot d^+_{\psi}(\mF) \leq \ell+1$.
Now apply Theorem <ref>.

Consider the star query $Q^\star_\ell$ with $\ell$ relations over the tropical semiring. Then, there exists a database $\mD$ such that no algorithm can have runtime of $O(|\mD|\cdot |Q^\star_\ell(\mD)|^{1-1/\ell-o(1)})$ subject to the Min-Weight $k$-Clique Conjecture.

While star and hierarchical query evaluation is optimal as shown by our lower bounds, results in Section <ref> show that it is possible to further improve the query evaluation runtime for other subclasses of queries. We leave the exciting problem of improving both upper and lower bounds for arbitrary CQ as an open problem.

The following theorem gives conditional lower bounds for $\ell$-paths for any integer $\ell\geq 2$ assuming the Boolean $k$-clique conjecture. This can be seen as an output-sensitive version of the lower bound results in <cit.>. At a high level, we “close” the $\ell$-path into a $\ell$-cycle by examining the join output. For the ease of readers, we don't introduce the whole machinery of clique embedding power in <cit.> but provide a self-contained proof specialized to the case of $\ell$-path.

When plugged into $\ell = 4$, this gives $\Omega(|\mD| \cdot |\tOUT|^{1/2})$ lower bound for 3-path, which tightly matched Shaleen's new algorithm. When $\ell = 5$, this gives $\Omega(|\mD| \cdot |\tOUT|^{2/3})$ lower bound for 4-path, which is also tight due to the new discovery. However, when $\ell = 6$, i.e. 5-path, we don't have a matching upper bound yet.

For any $(\ell-1)$-path query $Q(x_1,x_\ell):- U_1(x_1,x_2), U_2(x_2,x_3), \dots, U_{\ell-1}(x_{\ell-1},x_\ell)$, there exists no combinatorial algorithm in time $O(|\mD|\cdot |\tOUT|^{1 - 1 / \lceil \ell / 2 \rceil - \epsilon})$ for any $\epsilon > 0$ assuming the Boolean $k$-clique conjecture.

We start with the case when $\ell$ is odd. Let $\lambda = (\ell+1)/2$. Consider the following mapping $\psi$ from $[\ell]$ to variables $x_i$'s, $1 \leq i \leq \ell$, uniquely defined by the following:

\begin{equation}
\begin{aligned}
\psi^{-1}(x_1) & = \{ 1,2, \dots, \lambda-1\} \\
\psi^{-1}(x_2) & = \{ 2, 3, \dots, \lambda\} \\
& \dots \\
\psi^{-1}(x_\ell) & = \{ 2\lambda-1, 1, \dots, \lambda-2\}
\end{aligned}
\end{equation}

In other words, $\psi$ maps each $i \in [\ell]$ into a consecutive segment consisting of $\lambda-1$ vertices in the $\ell$-cycle, if we were to add the atom $U_{\ell} (x_\ell, x_1)$. Observe that for any $i,j \in [\ell]$, there exists $p \in [\ell]$ such that $\{i,j\} \in \psi^{-1}(x_p) \cap \psi^{-1}(x_{p+1})$. Also, observe that for any $p \in [\ell]$, we have $|\psi^{-1}(x_p) \cup \psi^{-1}(x_{p+1})| = \lambda = (\ell+1) /2$.

Without loss of generality, we can assume that the input graph for deciding $\ell$-clique is $\ell$-partite. Indeed, given any graph $G = (V,E)$ where $V = \{v_1, v_2, \dots, v_n\}$, consider the $\ell$-partite graph $G^\ell = (V^\ell,E^\ell)$ where $V^\ell = \{v_i^j \mid 1 \leq i \leq n, 1 \leq j \leq k\}$ and for any two vertices $v_i^j, v_p^q \in V^k$, $\{v_i^j, v_p^q\} \in E^k $ iff $\{v_i, v_p\} \in E$ and $j \neq q$. Then there is a one-to-one mapping from a $\ell$-clique in $G$ to a $\ell$-clique in $G^\ell$.

We now construct an instance for $Q(x_1, x_\ell)$. The domain of each variable $x_i$ is the set of vectors over $[n]^{|\psi^{-1}(x_i)|}$, where  $n$ is the number of input graph $G$. Let $S_e = \{ i\in [\ell] \mid \psi(i) \cap e \neq \emptyset \}$ where $e = (x_p, x_{p+1})$ for some $p\in [\ell-1]$. By our construction, we have $|S_e| \leq \lambda$. We now compute all cliques in graph $G$ between the partitions $V_i$ where $i \in S_e$; these cliques will be of size $|S_e|$ and can be computed in time $O(n^\lambda)$ by brute force. Finally, for every clique $\{a_i \in V_i \mid i \in S_e\}$, add the tuple $t:= \prod_{i \in S_e} \mathsf{Dom}(x_i)$ where the value for variable $x$ is $\langle a_i \mid i \in \psi^{-1}(x) \rangle$ into the atom corresponding to $e$. Observe that the size of the instance $|\mD|$ and output $|\tOUT|$ are both bounded by $O(n^\lambda)$.

When $\ell$ is odd, we have $\lceil \ell / 2 \rceil = (\ell + 1)/2 = \lambda$. Assume that we have a combinatorial algorithm running in time $O(|\mD|\cdot |\tOUT|^{1 - 1 / \lambda - \epsilon})$ for some $\epsilon >0$. Then, we can solve this instance in time $O(n^\lambda \cdot n^{\lambda\cdot(1-1/\lambda - \epsilon )}) = O(n^{\lambda\cdot (2-1/\lambda) - \epsilon'}) = O(n^{2\lambda-1-\epsilon'}) = O(n^{\ell-\epsilon'}).$ Finally, we  check if there exists a tuple in the output that has identical entries on $\psi^{-1}(x_1)$ and $\psi^{-1}(x_\ell)$ and this can be done in $|\tOUT| = O(n^\lambda)$ time. Observe that such a tuple exists if and only if there exists an $\ell$-clique in $G$. This contradicts the Boolean $k$-clique conjecture.

The case when $\ell$ is even is done by changing the mapping $\psi$ to be from $[\ell-1]$ to variables $x_i$'s, $1 \leq i \leq \ell$, uniquely defined by the following:

\begin{align*}
\psi^{-1}(x_1) & = \{ 1,2, \dots, \lambda-1\} \\
\psi^{-1}(x_2) & = \{ 2, 3, \dots, \lambda\} \\
& \dots \\
\psi^{-1}(x_{\ell - 1}) & = \{ 2\lambda-2, 2\lambda-1, 1, \dots, \lambda-3\}  \\
\psi^{-1}(x_\ell) & = \psi^{-1}(x_{\ell - 1})
\end{align*}

The proof is now complete by following the same construction when $\ell$ is odd.

This can generalize to any semiring. Also, this can generalize to $|\mD| \cdot |\tOUT|^{\textsf{clemb}(Q')-1}$ where $Q'$ is $Q$ union  an atom with $Q$'s free variables. See sketch in the appendix.

§ RELATED WORK

Several prior works have investigated problems related to output sensitive evaluation. Deng et al. <cit.> presented a dynamic index structure for output sensitive join sampling. Riko and Stöckel <cit.> studied output-sensitive matrix multiplication (which is the two path query), a result that built upon the join-project query evaluation results from <cit.>. Deng et al. <cit.> presented output-sensitive evaluation algorithms for set similarity, an important practical class of queries used routinely in recommender systems, graph analytics, etc. An alternate way to evaluate join queries is to use delay based algorithms. In particular, given an algorithm with preprocessing time $T_p$ and allows for $\delta$ delay enumeration (i.e. the time difference between any two consecutive output tuples is at most $\delta$) of the query result, one can obtain an evaluation algorithm that takes time $O(T_p + \delta \cdot |\tOUT|)$ time. As we saw in Section <ref>, our result is able to match the join running time obtained via <cit.> for star queries. Recent work <cit.> has also studied the problem of reporting $t$ patterns in graphs when the input is temporal, i.e., the input is changing over time. Output-sensitive algorithms has also been developed for the problem of maximal clique enumeration <cit.>. Outside the database community, several interesting results have been known for listing $k$-cliques and $k$-cycles in output-sensitive way. <cit.> designed output-sensitive algorithms
for listing $t$ triangles, the simplest $k$-clique, using fast matrix multiplication.The work of <cit.> and <cit.> show algorithms for list $t$ 4-cycles, and <cit.> shows how to list $t$ 6-cycles. The upper bounds were shown to be tight under the 3SUM hypothesis.

§ CONCLUSION

In this paper, we presented a novel generalization of Yannakakis algorithm that is provably faster for a large class of CQs. We show several applications of the generalized algorithm (which is combinatorial in nature) to recover state-of-the-art results known in existing literature, as well as new results for popular queries such as star queries and path queries. At the heart of our technical development is a novel lemma that allows for a tighter bound on the intermediate result size as we process the join tree in a bottom-up fashion. Surprisingly, our results show that for several queries, our combinatorial algorithm is better than known results that use fast matrix multiplication. We complement our upper bounds with matching lower bounds for a class of queries for both Boolean semirings (a.k.a joins) as well as aggregations.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abboud et al(2022)]
authorpersonAmir Abboud, personSeri Khoury, personOree Leibowitz, and personRon Safier. year2022.
Listing 4-cycles.
journalarXiv preprint arXiv:2211.10022 (year2022).

[Abo Khamis et al(2016)]
authorpersonMahmoud Abo Khamis, personHung Q. Ngo, and personAtri Rudra. year2016.
FAQ: Questions Asked Frequently (seriesPODS '16). publisherAssociation for Computing Machinery, addressNew York, NY, USA.

[Abo Khamis et al(2017)]
authorpersonMahmoud Abo Khamis, personHung Q Ngo, and personDan Suciu. year2017.
What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?. In booktitleProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pages429–444.

[Agarwal et al(2024)]
authorpersonPankaj K Agarwal, personXiao Hu, personStavros Sintos, and personJun Yang. year2024.
On reporting durable patterns in temporal proximity graphs.
journalProceedings of the ACM on Management of Data volume2, number2 (year2024), pages1–26.

[Amossen and Pagh(2009)]
authorpersonRasmus Resen Amossen and personRasmus Pagh. year2009.
Faster join-projects and sparse matrix multiplications. In booktitleProceedings of the 12th International Conference on Database Theory. pages121–126.

[Auer et al(1995)]
authorpersonPeter Auer, personNicolo Cesa-Bianchi, personYoav Freund, and personRobert E Schapire. year1995.
Gambling in a rigged casino: The adversarial multi-armed bandit problem. In booktitleProceedings of IEEE 36th annual foundations of computer science. IEEE, pages322–331.

[Björklund et al(2014)]
authorpersonAndreas Björklund, personRasmus Pagh, personVirginia Vassilevska Williams, and personUri Zwick. year2014.
Listing triangles. In booktitleInternational Colloquium on Automata, Languages, and Programming. Springer, pages223–234.

[Chang et al(2013)]
authorpersonLijun Chang, personJeffrey Xu Yu, and personLu Qin. year2013.
Fast maximal cliques enumeration in sparse graphs.
journalAlgorithmica  volume66 (year2013), pages173–186.

[Conte et al(2016)]
authorpersonAlessio Conte, personRoberto Grossi, personAndrea Marino, and personLuca Versari. year2016.
Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques. In booktitle43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Vol. volume148. pages1–148.

authorpersonChris J Date. year1989.
booktitleA Guide to the SQL Standard.
publisherAddison-Wesley Longman Publishing Co., Inc.

[Deep et al(2020)]
authorpersonShaleen Deep, personXiao Hu, and personParaschos Koutris. year2020.
Fast Join Project Query Evaluation using Matrix Multiplication. In booktitleProceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (seriesSIGMOD '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1213–1223.

[Deng et al(2018)]
authorpersonDong Deng, personYufei Tao, and personGuoliang Li. year2018.
Overlap set similarity joins with theoretical guarantees. In booktitleProceedings of the 2018 International Conference on Management of Data. pages905–920.

[Deng et al(2023)]
authorpersonShiyuan Deng, personShangqi Lu, and personYufei Tao. year2023.
On join sampling and the hardness of combinatorial output-sensitive join algorithms. In booktitleProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pages99–111.

[Fan et al(2023)]
authorpersonAusten Z. Fan, personParaschos Koutris, and personHangdong Zhao. year2023.
The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems. In booktitleICALP (seriesLIPIcs, Vol. volume261). publisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik, pages127:1–127:20.

[Green et al([n. d.])]
authorpersonTodd J. Green, personGrigoris Karvounarakis, and personVal Tannen. year[n. d.].
Provenance semirings. In booktitleProceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (seriesPODS '07). publisherAssociation for Computing Machinery, addressNew York, NY, USA.

authorpersonXiao Hu. year2024.
Fast Matrix Multiplication for Query Processing.
journalProceedings of the ACM on Management of Data volume2, number2 (year2024), pages1–25.

[Jacob and Stöckel(2015)]
authorpersonRiko Jacob and personMorten Stöckel. year2015.
Fast output-sensitive matrix multiplication. In booktitleAlgorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, pages766–778.

[Jin et al(2024)]
authorpersonCe Jin, personVirginia Vassilevska Williams, and personRenfei Zhou. year2024.
Listing 6-Cycles. In booktitle2024 Symposium on Simplicity in Algorithms (SOSA). SIAM, pages19–27.

[Jin and Xu(2023)]
authorpersonCe Jin and personYinzhan Xu. year2023.
Removing additive structure in 3sum-based reductions. In booktitleProceedings of the 55th Annual ACM Symposium on Theory of Computing. pages405–418.

[Kara et al(2020)]
authorpersonAhmet Kara, personMilos Nikolic, personDan Olteanu, and personHaozhe Zhang. year2020.
Trade-offs in static and dynamic evaluation of hierarchical queries. In booktitleProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pages375–392.

[Khamis et al(2017)]
authorpersonMahmoud Abo Khamis, personHung Q. Ngo, and personDan Suciu. year2017.
What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?. In booktitlePODS. publisherACM, pages429–444.

[Makino and Uno(2004)]
authorpersonKazuhisa Makino and personTakeaki Uno. year2004.
New algorithms for enumerating all maximal cliques. In booktitleAlgorithm Theory-SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings 9. Springer, pages260–272.

authorpersonHG Marc. year1979.
booktitleOn the universal relation.
typeTechnical Report. institutionTechnical report, University of Toronto.

[Olteanu and Závodnỳ(2015)]
authorpersonDan Olteanu and personJakub Závodnỳ. year2015.
Size bounds for factorised representations of query results.
journalACM Transactions on Database Systems (TODS) volume40, number1 (year2015), pages1–44.

[Williams and Williams(2018)]
authorpersonVirginia Vassilevska Williams and personR Ryan Williams. year2018.
Subcubic equivalences between path, matrix, and triangle problems.
journalJournal of the ACM (JACM) volume65, number5 (year2018), pages1–38.

[Williams et al(2024)]
authorpersonVirginia Vassilevska Williams, personYinzhan Xu, personZixuan Xu, and personRenfei Zhou. year2024.
New bounds for matrix multiplication: from alpha to omega. In booktitleProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pages3792–3835.

authorpersonMihalis Yannakakis. year1981.
Algorithms for acyclic database schemes. In booktitleVLDB, Vol. volume81. pages82–94.

[Yu and Ozsoyoglu(1979)]
authorpersonClement Tak Yu and personMeral Z Ozsoyoglu. year1979.
An algorithm for tree-query membership of a distributed query. In booktitleCOMPSAC 79. Proceedings. Computer Software and The IEEE Computer Society's Third International Applications Conference, 1979. IEEE, pages306–312.

[Zhao et al(2024)]
authorpersonHangdong Zhao, personShaleen Deep, personParaschos Koutris, personSudeepa Roy, and personVal Tannen. year2024.
Evaluating Datalog over Semirings: A Grounding-based Approach.
journalProceedings of the ACM on Management of Data volume2, number2 (year2024), pages1–26.

We show the following output-sensitive lower bounds for any given conjunctive query. To this end, we introduce the notion of clique embedding power in <cit.>.

We say that two sets of vertices $X,Y \subseteq V(H)$ touch in $\mH$ if either $X \cap Y \neq \emptyset$ or there is a hyperedge $e \in E(\mH)$ that intersects both $X$ and $Y$.

Let $k \geq 3$ and $\mH$ be a hypergraph. A $k$-clique embedding, denoted $C_k \mapsto H$, is a mapping $\psi$ that maps every $v \in \{1, \dots, k\}$ to a non-empty subset $\psi(v) \subseteq V(\mH)$ such that the following hold:

* $\psi(v)$ induces a connected subgraph;

* for any two $u \neq v \in \{1, \dots, k\}$ then $\psi(u), \psi(v)$ touch in $\mH$.

It will often be convenient to describe a clique embedding $\psi$ by the reverse mapping $\psi^{-1}(x) = \{i \mid x \in \psi(i) \}$, where $x$ is a vertex  in $V(\mH)$.

We define the edge depth of $e\in E(\mH)$ as $d^+_{\psi}(e) = \sum_{v \in e} d_\psi(v)$, i.e. the numer of colors from $[k]$ that map to some variable in $e$, counting multiplicity. Additionally, we define as $\mathsf{ed}(C_k \mapsto H)$ the minimum edge depth of any clique embedding $\psi$. We can now define the following quantity, which we call the edge-depth clique embedding power:

$$ \mathsf{clemb}^+(\mH) := \sup_{k \geq 3} \frac{k}{\mathsf{ed}(C_k \rightarrow \mH)}$$

It is straightforward to adapt the argument of Section 5 in <cit.> to show that this quantity is well-defined and decidable (and thus can be computed in $O(1)$ for data complexity).

We are now ready to state and prove the output-sensitive lower bounds for any conjunctive query.

Given any conjunctive query $Q(U)\leftarrow \bigwedge\limits_{e \in \mathcal{E}} R_e(\mathbf{x}_e)$, let $Q'$ be the Boolean conjunctive query $Q(U) \wedge R(U)$. Then, there exists no combinatorial algorithm in time $O(|D| \cdot |OUT|^{\mathsf{clemb^+(Q')}-1-\epsilon})$ for any $\epsilon > 0$ assuming the Boolean $k$-Clique Conjecture.

Construct the instance as in <cit.> and observe that there exists $k$-clique, where $\mathsf{clemb}(\mH)$ achieves supreme at $k$, if and only if there exists a tuple in the output that is consistent with the domains in variables $U$. The time and size to construct such instance is bounded by $O(n^{\mathsf{ed}(C_k \rightarrow \mH})$ (even $O(n^{\mathsf{wed}(C_k \rightarrow \mH})$ where $\mathsf{wed}$ stands for the weak edge depth as defined in <cit.>), and observe the size of $|OUT|$ is bounded by  $O(n^{\mathsf{ed}(C_k \rightarrow \mH})$. Thus such output-sensitive combinatorial algorithm will yield a combinatorial algorithm for $k$-clique that runs in time $O(n^{(\mathsf{wed}(C_k \rightarrow \mH)) \cdot (\mathsf{clemb}(\mH) -\epsilon)}) = O(n^{k-\epsilon'})$ for some $\epsilon' >0$, contradicting the Boolean $k$-Clique Conjecture.

By the same semiring-oblivious technique in <cit.>, which assigning each clique uniquely into an atom $e$ whose $S_e$ contains the partitions of the clique, we obtain lower bounds from $k$-clique conjecture over any semiring. In particular, we can leverage the Min-Weight $k$-Clique Conjecture. This is formalize in the following theorem.

Given any conjunctive query $Q(U)\leftarrow \bigwedge\limits_{e \in \mathcal{E}} R_e(\mathbf{x}_e)$, let $Q'$ be the conjunctive query $Q(U) \wedge R(U)$. Then, there exists no randomized algorithm that computes $Q'$ over the tropical semiring in time $O(|D| \cdot |OUT|^{\mathsf{clemb^+(Q')}-1-\epsilon})$ for any $\epsilon > 0$ assuming the Min-Weight $k$-Clique Conjecture.