MnLargeSymbols’164 MnLargeSymbols’171

# Enumeration Algorithms for Conjunctive Queries with Projection

Shaleen Deep  Department of Computer Sciences, University of Wisconsin-
Madison, Madison, Wisconsin, USA<EMAIL_ADDRESS>,  Xiao Hu  Department
of Computer Sciences, Duke University, Durham, North Carolina, USA
<EMAIL_ADDRESS>and  Paraschos Koutris  Department of Computer Sciences,
University of Wisconsin-Madison, Madison, Wisconsin, USA<EMAIL_ADDRESS>
###### Abstract.

We investigate the enumeration of query results for an important subset of CQs
with projections, namely star and path queries. The task is to design data
structures and algorithms that allow for efficient enumeration with delay
guarantees after a preprocessing phase. Our main contribution is a series of
results based on the idea of interleaving precomputed output with further join
processing to maintain delay guarantees, which maybe of independent interest.
In particular, for star queries, we design combinatorial algorithms that
provide instance-specific delay guarantees in linear preprocessing time. These
algorithms improve upon the currently best known results. Further, we show how
existing results can be improved upon by using fast matrix multiplication. We
also present new results involving tradeoff between preprocessing time and
delay guarantees for enumeration of path queries that contain projections.
Boolean matrix multiplication is an important query that can be expressed as a
CQ with projection where the join attribute is projected away. Our results can
therefore also be interpreted as sparse, output-sensitive matrix
multiplication with delay guarantees.

##  1\. Introduction

The efficient evaluation of join queries over static databases is a
fundamental problem in data management. There has been a long line of research
on the design and analysis of algorithms that minimize the total runtime of
query execution in terms of the input and output size [Yan81, NRR13, NPRR12].
However, in many data processing scenarios it is beneficial to split query
execution into two phases: the preprocessing phase, which computes a space-
efficient intermediate data structure, and the enumeration phase, which uses
the data structure to enumerate the query results as fast as possible, with
the goal of minimizing the delay between outputting two consecutive tuples in
the result. This distinction is beneficial for several reasons. For instance,
in many scenarios, the user wants to see one (or a few) results of the query
as fast as possible: in this case, we want to minimize the time of the
preprocessing phase, such that we can output the first results quickly. On the
other hand, a data processing pipeline may require that the result of a query
is accessed multiple times by a downstream task: in this case, it is better to
spend more time during the preprocessing phase, to guarantee a faster
enumeration with smaller delay.

Previous work in the database literature has focused on finding the class of
queries that can be computed with $O(|D|)$ preprocessing time (where $D$ is
the input database instance) and constant delay during the enumeration phase.
The main result in this line of work shows that full (i.e., without
projections) acyclic Conjunctive Queries (CQs) admit linear preprocessing time
and constant delay [BDG07]. If the CQ is not full but its free variables
satisfy the free-connex property, the same preprocessing time and delay
guarantees can still be achieved. It is also known that for any (possibly non-
full) acyclic CQ, it is possible to achieve linear delay after linear
preprocessing time [BDG07]. Prior work that uses structural decomposition
methods [GS13] generalized these results to arbitrary CQs with free variables
and showed that the projected solutions can be enumerated with
$O(|D|^{\texttt{fhw}})$ delay. Moreover, a dichotomy about the classes of
conjunctive queries with fixed arities where such answers can be computed with
polynomial delay (WPD) is also shown. When the CQ is full but not acyclic,
factorized databases uses $O(|D|^{\texttt{fhw}})$ preprocessing time to
achieve constant delay, where fhw is the fractional hypertree width [GGS14] of
the query. We should note here that we can always compute and materialize the
result of the query during preprocessing to achieve constant delay enumeration
but at the cost of using exponential amount of space in general.

The aforementioned prior work investigates specific points in the
preprocessing time-delay tradeoff space. While the story for full acyclic CQs
is relatively complete, the same is not true for general CQs, even for acyclic
CQs with projections. For instance, consider the simplest such query:
$Q_{\texttt{two-path}}=\pi_{x,z}(R(x,y){\Join}S(y,z))$, which joins two binary
relations and then projects out the join attribute. For this query, [BDG07]
ruled out a constant delay algorithm with linear time preprocessing unless the
boolean matrix multiplication exponent is $\omega=2$. However, we can obtain
$O(|D|)$ delay with $O(|D|)$ preprocessing time. We can also obtain $O(1)$
delay with $O(|D|^{2})$ preprocessing by computing and storing the full
result. It is worth asking whether there are other interesting points in this
tradeoff between preprocessing time and delay. Towards this end, seminal work
by Kara et al. [KNOZ20] showed that for any hierarchical CQ111Hierarchical CQs
are a strict subset of acyclic CQs. (possibly with projections), there always
exists a smooth tradeoff between preprocessing time and delay. This is the
first improvement over the results of Bagan et al. [BDG07] in over a decade
for queries involving projections. Applied to the query $Q_{\texttt{two-
path}}$, the main result of of [KNOZ20] shows that for any $\epsilon\in[0,1]$,
we can obtain $O(|D|^{1-\epsilon})$ delay with $O(|D|^{1+\epsilon})$
preprocessing time.

In this article, we continue the investigation of the tradeoff between
preprocessing time and delay for CQs with projections. We focus on two classes
of CQs: star queries, which are a popular subset of hierarchical queries, and
a useful subset of non-hierarchical queries known as path queries. We focus
narrowly on these two classes for two reasons. First, star queries are of
immense practical interest given their connections to set intersection, set
similarity joins and applications to entity matching (we refer the reader to
[DHK20] for an overview). The most common star query seen in practice is
$Q_{\texttt{two-path}}$ [BMT20]. The same holds true for path queries, which
are fundamental in graph processing. Second, as we will see in this article,
even for the simple class of star queries, the tradeoff landscape is complex
and requires the development of novel techniques. We also present a result on
another subset of hierarchical CQs that we call left-deep. Our key insight is
to design enumeration algorithms that depend not only on the input size $|D|$,
but are also aware of other data-specific parameters such as the output size.
To give a flavor of our results, consider the query $Q_{\texttt{two-path}}$,
and denote by $\texttt{OUT}_{\Join}$ the output of the corresponding query
without projections, $R(x,y){\Join}S(y,z)$. We can show the following result.

######  Theorem 1.

Given a database instance $D$, we can enumerate the output of $Q_{\texttt{two-
path}}=\pi_{x,z}(R(x,y){\Join}S(y,z))$ with preprocessing time $O(|D|)$ and
delay $O(|D|^{2}/|\texttt{OUT}_{\Join}|)$.

At this point, the reader may wonder about the improvement obtained from the
above result. [KNOZ20] implies that with preprocessing time $O(|D|)$, the
delay guarantee in the worst-case is $O(|D|)$. This raises the question
whether the delay from Theorem 1 is truly an algorithmic improvement rather
than an improved analysis of [KNOZ20]. We answer the question positively.
Specifically, we show that there exists a database instance where the delay
obtained from Theorem 1 is a polynomial improvement over the actual guarantee
[KNOZ20] and not just the worst-case. When the preprocessing time is linear,
the delay implied by our result is dependent on the size of the full join. For
the worst-case output size where $|\texttt{OUT}_{\Join}|=\Theta(|D|^{2})$, we
actually obtain the best possible delay, which will be constant. Compare this
to the result of [KNOZ20], which would require nearly $O(|D|^{2})$
preprocessing time to achieve the same guarantee. On the other hand, if
$|\texttt{OUT}_{\Join}|=\Theta(|D|)$, we obtain only a linear delay guarantee
of $O(|D|)$222We do not need to consider the case where
$|\texttt{OUT}_{\Join}|\leq|D|$, since then we can simply materialize the full
result during the preprocessing time using constant delay enumeration for
queries without projections [OZ15].. The reader may wonder how our result
compares in general with the tradeoff in [KNOZ20] in the worst-case; we will
show that we can always get at least as good of a tradeoff point as the one in
[KNOZ20]. Figure 1 summarizes the prior work and the results present in this
article.

Queries | Preprocessing | Delay | Source
---|---|---|---
Arbitrary acyclic CQ | $O(|D|)$ | $O(|D|)$ | [BDG07]
Free-connex CQ (projections) | $O(|D|)$ | $O(1)$ | [BDG07]
Full CQ | $O(|D|^{\texttt{fhw}})$ | $O(1)$ | [OS16]
Full CQ | ${O}(|D|^{\texttt{subw}}\log|D|)$ | $O(1)$ | [AKNS17]
Hierarchical CQ (with projections) | $O(|D|^{1+(\mathsf{w}-1)\epsilon})$ |  $O(|D|^{1-\epsilon})$, $\epsilon\in[0,1]$ | [KNOZ20]
Star query with $k$ relations (with projections) | $O(|D|)$ | $O(\frac{|D|^{k/(k-1)}}{|\texttt{OUT}_{\Join}|^{1/(k-1)}})$ | this article
Path query with $k$ relations (with projections) | $O(|D|^{2-\epsilon/(k-1)})$ |  $O(|D|^{\epsilon}),$ $\epsilon\in[0,1)$ | this article
Left-deep hierarchical CQ (with projections) | $O(|D|)$ | $O(|D|^{k}/|\texttt{OUT}_{\Join}|)$ | this article
Two path query (with projections) | $O(|D|^{\omega\cdot\epsilon})$ |  $O(|D|^{1-\epsilon}),$ $\epsilon\in[\frac{2}{\omega+1},1]$ | this article
Figure 1. Preprocessing time and delay guarantees for different queries.
$|\texttt{OUT}_{\Join}|$ denotes the size of join query under consideration
but without any projections. subw denotes the submodular width of the query.
For each class of query, the total running time is
$O(\min\\{|D|\cdot|\texttt{OUT}_{\pi}|,|D|^{\mathtt{subw}}\log|D|+|\texttt{OUT}_{\pi}|\\})$
where $|\texttt{OUT}_{\pi}|$ denotes the size of the query result.

#### Our Contribution

In this article, we improve the state-of-the-art on the preprocessing time-
delay tradeoff for a subset of CQs with projections. We summarize our main
technical contributions below (highlighted in Figure 1):

  1. (1)

Our main contribution consists of a novel algorithm (Theorem 6) that achieves
output-dependent delay guarantees for star queries after linear preprocessing
time. Specifically, we show that for the query
$\pi_{x_{1},\dots,x_{k}}(R_{1}(x_{1},y)\Join\dots\Join R_{k}(x_{k},y))$ we can
achieve delay $O(|D|^{k/(k-1)}/|\texttt{OUT}_{\Join}|^{1/k-1})$ with linear
preprocessing. Our key idea is to identify an appropriate degree threshold to
split a relation into partitions of heavy and light, which allows us to
perform efficient enumeration. For star queries, our result implies that there
exists no smooth tradeoff between preprocessing time and delay guarantees as
stated in [KNOZ20] for the general class of hierarchical queries.

  2. (2)

We introduce the novel idea of interleaving join query computation in the
context of enumeration algorithms which forms the foundation for our
algorithms, and may be of independent interest. Specifically, we show that it
is possible to union the output of two algorithms $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ with $\delta$ delay guarantee where $\mathcal{A}$
enumerates query results with $\delta$ delay guarantees but
$\mathcal{A}^{\prime}$ does not. This technique allows us to compute a subset
of a query on-the-fly when enumeration with good delay guarantees is
impossible.

  3. (3)

We show how fast matrix multiplication can be used to obtain a tradeoff
between preprocessing time and delay that further improves upon the tradeoff
in [KNOZ20]. We also present an algorithm for left-deep hierarchical queries
with linear preprocessing time and output-dependent delay guarantees.

  4. (4)

Finally, we present new results on preprocessing time-delay tradeoffs for a
non-hierarchical query with projections, for the class of path queries. A path
query has the form $\pi_{x_{1},x_{k+1}}(R_{1}(x_{1},x_{2})\Join\dots\Join
R_{k}(x_{k},x_{k+1}))$. Our results show that we can achieve delay
$O(|D|^{\epsilon})$ with preprocessing time $O(|D|^{2-\epsilon/(k-1)})$ for
any $\epsilon\in[0,1)$.

This article is the full version of a conference publication [DHK21]. We have
added all of the proofs and intermediate results that were excluded from the
paper. In particular, we have added the full proof of our main result –
enumeration delay obtained for star queries(Theorem 6, Theorem 12, and Theorem
13) as well as the proofs of all the helper lemmas in Section 3. Additionally,
we have also added the full algorithm for the helper lemmas. We have also
added Example 4.1 and Example 4.2 to improve the exposition. Finally, we have
added a new result in Section 4.4 that transfers a result for static
enumeration to the dynamic setting.

The remainder of the article is organized as follows. In the next section, we
give preliminary concepts, definitions and notation. In Section 3, we present
useful lemmas that are used frequently throughout the article. In Section 4,
we state the main result and compare it against prior work. As a warm-up step,
we present the intuition and main ideas for the two-path query, which are then
generalized to star queries. Towards the end of the section, we also discuss
how matrix multiplication can be useful. Section 5 and Section 6 are dedicated
to the study of a class of hierarchical queries that we call left-deep and
path queries respectively. Finally, we discuss past contribution measures in
Section 7 and conclude in Section 8.

##  2\. Problem Setting

In this section, we present the basic notation and terminology.

###  2.1. Conjunctive Queries

We will focus on the class of conjunctive queries (CQs), which we denote as

$Q=\pi_{\mathbf{y}}(R_{1}(\mathbf{x}_{1})\Join
R_{2}(\mathbf{x}_{2})\Join\ldots\Join R_{n}(\mathbf{x}_{n}))$

Here, the symbols $\mathbf{y},\mathbf{x}_{1},\dots,\mathbf{x}_{n}$ are vectors
that contain variables or constants. We say that $Q$ is full if there is no
projection. We will typically use the symbols $x,y,z,\dots$ to denote
variables, and $a,b,c,\dots$ to denote constants. We use $Q(D)$ to denote the
result of the query $Q$ over input database $D$.

In this paper, we will focus on CQs that have no constants and no repeated
variables in the same atom (both cases can be handled within a linear time
preprocessing step, so this assumption is without any loss of generality).
Such a query can be represented equivalently as a hypergraph
$\mathcal{H}_{Q}=(\mathcal{V}_{Q},\mathcal{E}_{Q})$, where $\mathcal{V}_{Q}$
is the set of variables, and for each hyperedge $F\in\mathcal{E}_{Q}$ there
exists a relation $R_{F}$ with variables $F$.

We will be particularly interested in two families of CQs that are fundamental
in query processing, star and path queries. The star query with $k$ relations
is expressed as:

$Q^{*}_{k}=R_{1}(\mathbf{x}_{1},\mathbf{y})\Join
R_{2}(\mathbf{x}_{2},\mathbf{y})\Join\dots\Join
R_{k}(\mathbf{x}_{k},\mathbf{y})$

where $\mathbf{x}_{1},\dots,\mathbf{x}_{k}$ have disjoint sets of variables.
The path query with $k$ (binary) relations is expressed as:

$P_{k}=R_{1}(x_{1},x_{2})\Join R_{2}(x_{2},x_{3})\Join\dots\Join
R_{k}(x_{k},x_{k+1})$

In $Q^{*}_{k}$, variables in each relation $R_{i}$ are partitioned into two
sets: variables $\mathbf{x}_{i}$ that are present only in $R_{i}$ and a common
set of join variables $\mathbf{y}$ present in every relation.

#### Hierarchical Queries

A CQ $Q$ is hierarchical if for any two of its variables, either the sets of
atoms in which they occur are disjoint or one is contained in the other
[SORK11]. For example, $Q^{*}_{k}$ is hierarchical for any $k$, while $P_{k}$
is hierarchical only when $k\leq 2$.

#### Join Size Bounds

Let $\mathcal{H}=(\mathcal{V},\mathcal{E})$ be a hypergraph, and
$S\subseteq\mathcal{V}$. A weight assignment
$\mathbf{u}=(u_{F})_{F\in\mathcal{E}}$ is called a fractional edge cover of
$S$ if $(i)$ for every $F\in\mathcal{E},u_{F}\geq 0$ and $(ii)$ for every
$x\in S,\sum_{F:x\in F}u_{F}\geq 1$. The fractional edge cover number of $S$,
denoted by $\rho^{*}_{\mathcal{H}}(S)$ is the minimum of
$\sum_{F\in\mathcal{E}}u_{F}$ over all fractional edge covers of $S$. We write
$\rho^{*}(\mathcal{H})=\rho^{*}_{\mathcal{H}}(\mathcal{V})$.

#### Tree Decompositions

Let $\mathcal{H}=(\mathcal{V},\mathcal{E})$ be a hypergraph of a CQ $Q$. A
tree decomposition of $\mathcal{H}$ is a tuple
$(\mathcal{T},(\mathcal{B}_{t})_{t\in V(\mathcal{T})})$ where $\mathcal{T}$ is
a tree, and every $\mathcal{B}_{t}$ is a subset of $\mathcal{V}$, called the
bag of $t$, such that

  1. (1)

each edge in $\mathcal{E}$ is contained in some bag; and

  2. (2)

for each variable $x\in\mathcal{V}$, the set of nodes $\\{t\mid
x\in\mathcal{B}_{t}\\}$ form a connected subtree of $\mathcal{T}$.

The fractional hypertree width of a decomposition is defined as $\max_{t\in
V(\mathcal{T})}\rho^{*}(\mathcal{B}_{t})$, where $\rho^{*}(\mathcal{B}_{t})$
is the minimum fractional edge cover of the vertices in $\mathcal{B}_{t}$. The
fractional hypertree width of a query $Q$, denoted $\texttt{fhw}(Q)$, is the
minimum fractional hypertree width among all tree decompositions of its
hypergraph. We say that a query is acyclic if $\texttt{fhw}(Q)=1$.

#### Computational Model

To measure the running time of our algorithms, we will use the uniform-cost
RAM model [HUA75], where data values as well as pointers to databases are of
constant size. Throughout the paper, all complexity results are with respect
to data complexity, where the query is assumed fixed.

###  2.2. Fast Matrix Multiplication

Let $A$ be a $U_{1}\times U_{3}$ matrix and $C$ be a $U_{3}\times U_{2}$
matrix over any field $\mathcal{F}$. $A_{i,j}$ is the shorthand notation for
entry of $A$ located in row $i$ and column $j$. The matrix product is given by
$(AC)_{i,j}=\sum_{k=1}^{U_{3}}A_{i,k}C_{k,j}$. Algorithms for fast matrix
multiplication are of extreme theoretical interest given its fundamental
importance. We will frequently use the following folklore lemma about
rectangular matrix multiplication.

######  Lemma 2.

Let $\omega$ be the smallest constant such that an algorithm to multiply two
$n\times n$ matrices that runs in time $O(n^{\omega})$ is known. Let
$\beta=\min\\{U,V,W\\}$. Then fast matrix multiplication of matrices of size
$U\times V$ and $V\times W$ can be done in time $O(UVW\beta^{\omega-3})$.

Observe that in Lemma 2, matrix multiplication cost dominates the time
required to construct the input matrices (if they have not been constructed
already) for all $\omega\geq 2$. Fixing $\omega=2$, rectangular matrix
multiplication can be done in time $O(UVW/\beta)$. A long line of research on
fast square matrix multiplication has dropped the complexity to
$O(n^{\omega})$, where $2\leq\omega<3$. The current best known value is
$\omega=2.3729$ [GU18], but it is believed that the actual value is $2$.

###  2.3. Problem Statement

Given a Conjunctive Query $Q$ and an input database $D$, we want to enumerate
the tuples in $Q(D)$ in any order. We will study this problem in the
enumeration framework similar to that of [Seg15a], where an algorithm can be
decomposed into two phases:

  * •

Preprocessing phase: it computes a data structure that takes space $S_{p}$ in
preprocessing time $T_{p}$.

  * •

Enumeration phase: it outputs $Q(D)$ with no repetitions. This phase has
access to any data structures constructed in the preprocessing phase and can
also use additional space of size $S_{e}$. The delay $\delta$ is defined as
the maximum time duration between outputting any pair of consecutive tuples
(this includes the time to output the first tuple, and the time to notify that
the enumeration phase has completed).

In this work, our goal is to study the relationship between the preprocessing
time $T_{p}$ and delay $\delta$ for a given CQ $Q$. Ideally, we would like to
achieve constant delay in linear preprocessing time. As Table 1 shows, when
$Q$ is full, with $T_{p}=O(|D|^{\texttt{fhw}})$, we can enumerate the results
with constant delay [OS16]. In the particular case where $Q$ is acyclic i.e.
$\texttt{fhw}=1$, we can achieve constant delay with only linear preprocessing
time. On the other hand, [BDG07] shows that for every acyclic CQ, we can
achieve linear delay $O(|D|)$ with linear preprocessing time $O(|D|)$.

Recently, [KNOZ20] showed that it is possible to get a tradeoff between the
two extremes, for the class of hierarchical queries. Note that hierarchical
queries are acyclic but not necessarily free-connex. This is the first non-
trivial result that improves upon the linear delay guarantees given by [BDG07]
for queries with projections.

[[KNOZ20]] Consider a hierarchical CQ $Q$ with factorization width
$\mathsf{w}$, and an input instance $D$. Then, for any $\epsilon\in[0,1]$
there exists an algorithm that can preprocess $D$ in time
$T_{p}={O}(|D|^{1+(\mathsf{w}-1)\epsilon})$ and space
$S_{p}={O}(|D|^{1+(\mathsf{w}-1)\epsilon})$ such that we can enumerate the
query output with

$\text{delay }\delta=O(|D|^{1-\epsilon})\quad\quad\text{space }S_{e}=O(1).$

The factorization width $\mathsf{w}$ of a query, originally introduced as
$s^{\uparrow}$ [OZ15], is a generalization of the fractional hypertree width
from boolean to arbitrary CQs. For
$\pi_{\mathbf{x}_{1},\dots,\mathbf{x}_{k}}(Q^{*}_{k})$, the factorization
width is $\mathsf{w}=k$. Observe that preprocessing time $T_{p}$ must always
be smaller than the time required to evaluate the full join result. This is
because if $T_{p}=\Theta(|\texttt{OUT}_{\Join}|)$, we can evaluate the full
join and deduplicate the projection output, allowing us to obtain constant
delay in the enumeration phase. Therefore, the tradeoff is more meaningful
when $\epsilon$ can only take values between $0$ and
$(\log_{|D|}|\texttt{OUT}_{\Join}|-1)/(\mathsf{w}-1)$. In the worst-case,
$|\texttt{OUT}_{\Join}|=|D|^{\mathsf{w}}$ and $\epsilon$ can take any value
between $0$ and $1$ (both inclusive), which is captured by the general result
above.

##  3\. Helper Lemmas

Before we present the proof of our main results, we discuss three useful
lemmas which will be used frequently, and may be of independent interest for
enumeration algorithms. The first two lemmas are based on the key idea of
_interleaving query results_ which we describe next. We note that idea of
interleaving computation has been explored in the past to develop dynamic
algorithms with good worst-case bounds using static data structures [OVL81].

We say that an algorithm $\mathcal{A}$ provides no delay guarantees to mean
that its delay guarantee can be as large as its total execution time. In other
words, if an algorithm requires time $T$ to complete, its delay guarantee is
upper bounded by $T$. Since we are using the uniform-cost RAM model, each
operation takes one unit of time.

######  Lemma 3.

Consider two algorithms $\mathcal{A},\mathcal{A}^{\prime}$ and two positive
integers $T$ and $T^{\prime}$ provided as a part of the input such that

  1. (1)

$\mathcal{A}$ enumerates query results in total time at most $T$ with no delay
guarantees.

  2. (2)

$\mathcal{A}^{\prime}$ enumerates query results with delay $\delta$ and runs
in total time at least $T^{\prime}$.

  3. (3)

The outputs of $\mathcal{A}$ and $\mathcal{A}^{\prime}$ are disjoint.

Then, the union of the outputs of $\mathcal{A}$ and $\mathcal{A}^{\prime}$ can
be enumerated with delay $c\cdot\delta\cdot\max\\{1,T/T^{\prime}\\}$ for some
constant $c$.

######  Proof 3.1.

Let $\eta$ and $\gamma$ denote two positive values to be fixed upon later.
Note that after $\delta$ time has passed, we can emit one output result from
$\mathcal{A}^{\prime}$. But since we also want to compute the output from
$\mathcal{A}$ that takes overall time $T$, we need to slow down the
enumeration of $\mathcal{A}^{\prime}$ sufficiently so that we do not run out
of output from $\mathcal{A}^{\prime}$. This can be done by interleaving the
two algorithms in the following way: we run $\mathcal{A}^{\prime}$ for
$\gamma$ operations, pause $\mathcal{A}^{\prime}$, then run $\mathcal{A}$ for
$\eta$ operations, pause $\mathcal{A}$ and resume $\mathcal{A}^{\prime}$ for
$\gamma$ operations, and so on. The pause and resume takes constant time (say
$c_{\textsf{pause}}$ and $c_{\textsf{resume}}$) in RAM model where the state
of registers and program counter can be stored and retrieved enabling pause
and resume of any algorithm. Our goal is to find a value of $\eta$ and
$\gamma$ such that $\mathcal{A}^{\prime}$ does not terminate until
$\mathcal{A}$ has finished. This condition is satisfied when the number of
iterations of $\mathcal{A}^{\prime}$ is equal to the number of iterations of
$\mathcal{A}$. This gives us the condition that,

$T^{\prime}/\gamma\leq\text{(Time taken by
}\mathcal{A}^{\prime}\text{)}/\gamma=\text{(Time taken by
}\mathcal{A}\text{)}/\eta\leq T/\eta$

Thus, any value of $\eta\leq T\cdot\gamma/T^{\prime}$ is acceptable. We fix
$\eta$ to be any positive integer constant and then set $\gamma$ to be the
smallest positive integer that satisfies the condition. The delay is bounded
by the product of worst-case number of iterations between two answers of
$\mathcal{A}^{\prime}$ and the work done between each iteration which is
$(\delta/\gamma)\cdot(\gamma+\eta+c_{\textsf{pause}}+c_{\textsf{resume}})\leq\delta\cdot(1+T/T^{\prime}+(c_{\textsf{pause}}+c_{\textsf{resume}})/\gamma)=O(\delta\cdot\max\\{1,T/T^{\prime}\\})$.

Lemma 3 tells us that as long as $T=O(T^{\prime})$, the output of
$\mathcal{A}$ and $\mathcal{A}^{\prime}$ can be combined without giving up on
delay guarantees by pacing the output of $\mathcal{A}^{\prime}$. Note that we
need to know the exact values of $T$ and $T^{\prime}$. This can be
accomplished by calculating the number of operations in the algorithms
$\mathcal{A}$ and $\mathcal{A}^{\prime}$ to bound their running time. The next
lemma introduces our second key idea of interleaving stored output result with
_on-the-fly_ query computation. Algorithm 1 describes the detailed algorithm
for Lemma 4.

######  Lemma 4.

Consider an algorithm $\mathcal{A}$ that enumerates query results in total
time at most $T$ with no delay guarantees, where $T$ is known in advance.
Suppose that $J$ output tuples have been stored apriori with no duplicate
tuples, where $J\leq T$. Then, there exists an algorithm that enumerates the
output with delay guarantee $\delta=O(T/J)$.

######  Proof 3.2.

Let $\delta$ be a parameter to be fixed later. Suppose the $J$ output results
are already stored in a hash set and create an empty hash set $H$ that will be
used for deduplication. Using a similar interleaving strategy as above, we
emit one result from $J$ and allow algorithm $\mathcal{A}$ to run for $\delta$
time. Whenever $\mathcal{A}$ wants to emit an output tuple, it probes the hash
set $H$ and $J$, emits $t$ only if $t$ does not appear in $H$ and $J$,
followed by inserting $t$ in $H$. Inserting $t$ in $H$ will ensure that
$\mathcal{A}$ does not output duplicates333If $\mathcal{A}$ guarantees that it
will generate results with no duplicates, then there is no need to use $H$..
Each probe takes $O(1)$ time, so the total running time of $\mathcal{A}$ is
$O(T)$. Our goal is to choose $\delta$ such that $\mathcal{A}$ terminates
before the materialized output $J$ runs out. This condition is satisfied when
$\delta\cdot J\geq O(T)$ which gives us $\delta=O(T/J)$. It can be easily
checked that no duplicated result is emitted and $O(\delta)$ delay is
guaranteed between every pair of consecutive results. Again, observe that we
need the algorithm $\mathcal{A}$ to be pausable, which means that we should be
able to resume the execution from where we left off. This can be achieved by
storing the contents of all registers in the memory and loading it when
required to resume execution.

Input : Materialized output list $J$, Algorithm $\mathcal{A}$ with known
completion time $T$

Output : Deduplicated result of $\mathcal{A}$

1 $\delta\leftarrow O(T/J),\textnormal{{{ptr}}}\leftarrow
0,\textnormal{{{dedup}}}\leftarrow 0$

$H\leftarrow\emptyset$

/* empty hash-set */

2 while  _$\textnormal{{{ptr}}} <|J|$_ do

output $J[\textnormal{{{ptr}}}]$

/* output result from $J$ to maintain delay guarantee */

3
$\textnormal{{{ptr}}}\leftarrow\textnormal{{{ptr}}}+1,\textnormal{{{counter}}}\leftarrow
0$

4 while  _$\textnormal{{{counter}}}\leq\delta$_ do

5 if  _$\mathcal{A}$ has not completed_ then

Execute $\mathcal{A}$ for $c$ time

/* $c$ is a constant */

_ _ foreach  _$t\in\mathbf{t}$_

__ /* let $\mathbf{t}$ be the output tuples generated (if any) */

6 do

7 if  _$t\not\in J$ and $t\not\in H$_ then

8 output $t$

9 insert $t$ in $H$

10

11 $\textnormal{{{counter}}}\leftarrow\textnormal{{{counter}}}+c$;

12

Algorithm 1 Deduplicate$(J,\mathcal{A})$

The final helping lemma allows us to enumerate the union of (possibly
overlapping) results of $m$ different algorithms where each algorithm outputs
its result according to a total order $\preceq$, such that the union is also
enumerated in sorted order according to $\preceq$. This lemma is based on the
idea presented as Fact $3.1.4$ in [Kaz13].

######  Lemma 5.

Consider $m$ algorithms
$\mathcal{A}_{1},\mathcal{A}_{2},\cdots,\mathcal{A}_{m}$ such that each
$\mathcal{A}_{i}$ enumerates its output $L_{i}$ with delay $O(\delta)$
according to the total order $\preceq$. Then, the union of their output can be
enumerated (without duplicates) with $O(m\cdot\delta)$ delay and in sorted
order according to $\preceq$.

######  Proof 3.3.

We describe Algorithm 2. For simplicity of exposition, we assume that
$\mathcal{A}_{i}$ outputs a null value when it finishes enumeration. Note that
results enumerated by one algorithm are in order, thus it always outputs the
locally minimum result ($e_{i}$) over the remaining result to be enumerated.
Algorithm 2 goes over all locally minimum results over all algorithms and
outputs the smallest one (denoted $w$) as globally minimum result (Algorithm
2). Once a result is enumerated, each $\mathcal{A}_{i}$ needs to check whether
its $e_{i}$ matches $w$. If yes, then $\mathcal{A}_{i}$ needs to update its
locally minimum result by finding the next one. Then, Algorithm 2 just repeats
this loop until all algorithms finish enumeration.

Observe that one distinct result is enumerated in each iteration of the while
loop. It takes $O(m)$ time to find the globally minimum result and
$O(m\cdot\delta)$ to update all local minimum results (Algorithm 2-Algorithm
2). Thus, Algorithm 2 has a delay guarantee of $O(m\cdot\delta)$.

1

2$S\leftarrow\\{1,2,\cdots,m\\}$;

3 foreach  _$i\in S$_ do

4 $e_{i}\leftarrow\mathcal{A}_{i}.first()$ ;

5

6while  _$S\neq\emptyset$_ do

$w\leftarrow\min_{i\in S}e_{i}$ ;

/* finds the smallest output (using $\preceq$) over all algorithms */

7 output $w$ ;

8 foreach  _$i\in S$ _ do

9 if  _$e_{i}=w$_ then

10 $e_{i}\leftarrow\mathcal{A}_{i}.next()$ ;

11

12 if  _$e_{i}=null$_ then

$S\leftarrow S-\\{i\\}$

/* the algorithm completes its output */

13

Algorithm 2 Merge$(\mathcal{A}_{1},\mathcal{A}_{2},\cdots,\mathcal{A}_{m})$

Directly implied by Lemma 5 is the fact that the list merge problem can be
enumerated with delay guarantees: Given $m$ lists $L_{1},L_{2},\cdots,L_{m}$
whose elements are drawn from a common domain, if elements in $L_{i}$ are
distinct (i.e. no duplicates) and ordered according to $\preceq$, then the
union of all lists $\bigcup_{i=1}^{m}L_{i}$ can be enumerated in sorted order
given by $\preceq$ with delay $O(m)$. Note that the enumeration algorithm
$\mathcal{A}_{i}$ degenerates to going over elements one by one in list
$L_{i}$, which has $O(1)$ delay guarantee as long as indexes/pointers within
$L_{i}$ are well-built. Throughout the paper, we use this primitive as
ListMerge$(L_{1},L_{2},\cdots,L_{m})$.

##  4\. Star Queries

Figure 2. Worst-case tradeoffs given by Theorem 2.3 without (left) and with
(right) taking $|\texttt{OUT}_{\Join}|$ into consideration.

In this section, we study enumeration algorithms for the star query
$\pi_{r}(Q^{*}_{k})$ where
$r\subseteq\bigcup_{i\in\\{1,2,\cdots,k\\}}\mathbf{x}_{i}$. Our main result is
Theorem 6 that we present below. We first present a detailed discussion on how
our result is an improvement over prior work in Section 4.1. Then, we present
a warm-up proof for $\pi_{r}(Q^{*}_{k})$ in Section 4.2, followed by the proof
for the general result in Section 4.3.

######  Theorem 6.

Consider the star query444We assume that $r$ contains at least one variable
from each $\mathbf{x}_{i}$. Otherwise, we can remove relations with no
projection variables after the preprocessing phase. with projection
$\pi_{r}(Q^{*}_{k})$ where
$r\subseteq\bigcup_{i\in\\{1,2,\cdots,k\\}}\mathbf{x}_{i}$ and an instance
$D$. There exists an algorithm with preprocessing time $T_{p}=O(|D|)$ and
preprocessing space $S_{p}=O(|D|)$, such that we can enumerate $Q^{*}_{k}(D)$
with

$\textrm{delay
}\delta=O\bigg{(}\frac{|D|^{k/k-1}}{|\texttt{OUT}_{\Join}|^{1/k-1}}\bigg{)}\textrm{
and space }S_{e}=O(|D|).$

Figure 3. Theorem 6 for $k=2$.

Figure 4. Trade-off in the worst-case for star query.

In the above theorem, the delay depends on the full join result size
$|\texttt{OUT}_{\Join}|=|Q^{*}_{k}(D)|$. As the join size increases, the
algorithm can obtain better delay guarantees. In the extreme case when
$|\texttt{OUT}_{\Join}|=\Theta(|D|^{k})$, it achieves constant delay with
linear time preprocessing. In the other extreme, when
$|\texttt{OUT}_{\Join}|=\Theta(|D|)$, it achieves linear delay.

When $|\texttt{OUT}_{\Join}|$ has linear size, we can compute and materialize
the result of the query in linear preprocessing time and achieve constant
delay enumeration. Generalizing this observation, when $T_{p}$ is sufficient
to evaluate the full join result, we can always achieve constant delay.

###  4.1. Comparison with Prior Work

It is instructive now to compare the  worst-case delay guarantee obtained by
Theorem 2.3 for $Q^{*}_{k}(D)$ with Theorem 6. Suppose that we want to achieve
delay $\delta=O(|D|^{1-\epsilon})$ for some
$\epsilon\in[0,(\log_{|D|}|\texttt{OUT}_{\Join}|-1)/(k-1)]$. Theorem 2.3 tells
us that this requires $O(|D|^{1+\epsilon(k-1)})$ preprocessing time. Then, it
holds that:

$|D|^{1-\epsilon}\geq|D|^{1-\frac{(\log_{|D|}|\texttt{OUT}_{\Join}|-1)}{k-1}}=|D|^{\frac{k-\log_{|D|}|\texttt{OUT}_{\Join}|}{k-1}}=|D|^{k/k-1}/|\texttt{OUT}_{\Join}|^{1/k-1}$

In other words, either we have enough preprocessing time to materialize the
output and achieve constant delay, or we can achieve the desirable delay with
linear preprocessing time.

Figure 2, 4 and 4 show the existing and new tradeoff results. Figure 2 shows
the tradeoff curve obtained from Theorem 2.3 by adding
$|\texttt{OUT}_{\Join}|$ as a third dimension, and adding the optimization for
constant delay when $T_{p}\geq O(|\texttt{OUT}_{\Join}|)$. Figure 4 shows the
tradeoff obtained from our result, while Figure 4 shows other existing results
for a fixed value of $|\texttt{OUT}_{\Join}|$. For a fixed value of
$|\texttt{OUT}_{\Join}|$, the delay guarantee does not change in Figure 4 as
we increase $T_{p}$ from $|D|$ to $|\texttt{OUT}_{\Join}|$. It remains an open
question to further decrease the delay if we allow more preprocessing time.
Such an algorithm would correspond to a curve connecting the red point(
$\bullet$) and the green triangle( ) in Figure 4.

Our results thus imply that, depending on $|\texttt{OUT}_{\Join}|$, one must
choose a different algorithm to achieve the optimal tradeoff between
preprocessing time and delay. Since $|\texttt{OUT}_{\Join}|$ can be computed
in linear time (using a simple adaptation of Yannakakis algorithm [Yan81,
PP06]), this can be done without affecting the preprocessing bounds.

$R(x,y)$$S(y,z)$$d_{2}$$e_{1}$$f_{2}$$d_{1}$$f_{1}$$\boldsymbol{\vdots}$$\boldsymbol{\vdots}$$d_{{N}}$$f_{{N}}$

(a) Database $D_{0}$ with full join size $N^{2}$.

$R(x,y)$$S(y,z)$$a_{2}$$b_{2}$$c_{2}$$a_{1}$$b_{1}$$c_{1}$$\boldsymbol{\vdots}$$\boldsymbol{\vdots}$$\boldsymbol{\vdots}$$a_{\sqrt{N}}$$b_{\sqrt{N}}$$c_{\sqrt{N}}$

(b) Database $D_{1}$ with full join size $N^{3/2}$.

Figure 5. $D_{0}\cup D_{1}$ forms a database where Theorem 6 improves the
delay guarantee of Theorem 2.3.

Next, we show how our result provides an algorithmic improvement over Theorem
2.3. Consider the instances $D_{0},D_{1}$ depicted in Figure 5(a) and Figure
5(b) respectively, and assume we want to use linear preprocessing time.

For $D_{1}$, the algorithm of Theorem 2.3 materializes nothing, since no $y$
valuation has a degree of $O(|D|^{0})$, and the delay will be
$\Theta(\sqrt{N})$. No materialization also occurs for $D_{0}$, but here the
delay will be $O(1)$. It is easy to check that our algorithm matches the delay
on both instances. Now, consider the instance $D=D_{0}\cup D_{1}$. The input
size for $D$ is $\Theta(N)$, while the full join size is
$N^{3/2}+N^{2}=\Theta(N^{2})$. The algorithm of Theorem 2.3 will again achieve
only a $\Theta(\sqrt{N})$ delay, since after the linear time preprocessing no
$y$ valuations can be materialized. In contrast, our algorithm still
guarantees a constant delay. This algorithmic improvement is a result of the
careful overlapping of the constant-delay computation for instance $D_{0}$
with the computation for $D_{1}$.

The above construction can be generalized as follows. Let $\alpha\in(0,1)$ be
some constant. $D_{0}$ remains the same. For $D_{1}$, we construct $R$ to be
the cross product of $N^{\alpha}$ $x$-values and $N^{1-\alpha}$ $y$-values,
and $S$ to be the cross product of $N^{\alpha}$ $z$-values and $N^{1-\alpha}$
$y$-values. As before, let $D=D_{0}\cup D_{1}$. The input size for $D$ is
$\Theta(N)$, while the full join size is $N^{2-\alpha}+N^{2}=\Theta(N^{2})$.
Hence, our algorithm achieves constant delay with linear preprocessing time.
In contrast, the algorithm of Theorem 2.3 achieves $\Theta(N^{1-\alpha})$
delay with linear preprocessing time. In fact, the $\Theta(N^{1-\alpha})$
delay occurs even if we allow $O(N^{1+\epsilon})$ preprocessing time for any
$\epsilon<\alpha$. We can now use the same idea to show that there also exists
an instance where achieving constant delay using Theorem 2.3 requires near
quadratic preprocessing time as shown Example 4.1 below.

We construct an instance where achieving constant delay with Theorem 2.3 would
require close to $\Theta(|D|^{2})$ computation. Let us fix $N$ to be a power
of $2$. We will fix $|\mathbf{dom}(x)|=|\mathbf{dom}(z)|=N\log N$. Let $D_{i}$
be the database constructed by setting $N^{\alpha}=2^{i}$ for
$i\in\\{1,2,\dots,\log N\\}$ where relation $R$ is the cross product of
$N^{\alpha}$ $x$-values and $N^{1-\alpha}$ $y$-values, and $S$ is the cross
product of $N^{\alpha}$ $z$-values and $N^{1-\alpha}$ $y$-values.. We also
construct a database $D^{*}$ which consists of a single $y$ that is connected
to all $x$ and $z$ values. Let $D=D^{*}\cup D_{1}\cup D_{2}\cup\dots\cup
D_{\log N}$. It is now easy to see that $|D|=N\cdot\log
N,|\mathbf{dom}(y)|=\sum_{\alpha}N^{1-\alpha}\leq 2N=\Theta(|D|/\log|D|)$ and
$|\texttt{OUT}_{\Join}|=\sum_{\alpha}N^{1+\alpha}+N^{2}\log^{2}N=\Theta(|D|^{2})$.
On this instance, Theorem 2.3 achieves $\Theta(|D|/\log|D|)$ after linear time
preprocessing. Suppose we wish to achieve constant delay enumeration. Let us
fix this constant to be $c^{*}$ (which is also a power of $2$, for
simplicity). Then, we need enough preprocessing time to materialize the join
result of all database instances $D_{i}$ where
$i\in\\{1,2,\dots,\log(N/c^{*})\\}$ to ensure that the number of heavy $y$
values that remain is at most $c^{*}$. This requires time
$T_{p}>\sum_{i\in\\{1,2,\dots,\log(N/c^{*})\\}}N\cdot
2^{i}>N^{2}/c^{*}=\Theta(|D|^{2}/\log|D|)$. This example shows that Theorem
2.3 requires near quadratic computation to achieve constant delay enumeration.

In the rest of the paper, for simplicity of exposition, we assume that all
variable vectors $\mathbf{x}_{i},\mathbf{y}$ in $Q^{*}_{k}$ are singletons
(i.e, all the relations are binary) and $r=\\{x_{1},x_{2},\dots,x_{k}\\}$. The
proof for the general query is a straightforward extension of the binary case.

###  4.2. Warm-up: Two-Path Query

As a warm-up step, we will present an algorithm for the query $Q_{\texttt{two-
path}}=\pi_{x,z}(R(x,y){\Join}S(y,z))$ that achieves
$O(|D|^{2}/|\texttt{OUT}_{\Join}|)$ delay with linear preprocessing time.

At a high level, we will decompose the join into two subqueries with disjoint
outputs. The subqueries will be generated based on whether a valuation for $x$
is _light_ or not based on its degree in relation $R$. For all light
valuations of $x$ (degree at most $\delta$), we will show that their
enumeration is achievable with delay $\delta$. For the heavy $x$ valuations,
we will show that they also can be computed on-the-fly while maintaining the
delay guarantees.

#### Preprocessing Phase

We first process the input relations such that we remove any dangling tuples.
During the preprocessing phase, we will store the input relations as a hash
map and sort the valuations for $x$ in increasing order of their degree. Using
any comparison based sorting technique requires $\Omega(|D|\log|D|)$ time in
general. Thus, if we wish to remove the $\log|D|$ factor, we must use non-
comparison based sorting algorithms. In this paper, we will use count sort
[CLRS09] which has complexity $O(|D|+r)$ where $r$ is the range of the non-
negative key values. However, we need to ensure that all relations in the
database $D$ satisfy the bounded range requirement. This can be easily
accomplished by introducing a bijective function
$f:\mathbf{dom}(D)\rightarrow\\{1,2,\dots,|D|\\}$ that maps all values in the
active domain of the database to some integer between $1$ and $|D|$ (both
inclusive). Both $f$ and its inverse $f^{-1}$ can be stored as hash tables as
follows: suppose there is a counter $c\leftarrow 1$. We perform a linear pass
over the database and check if some value $v\in\mathbf{dom}(D)$ has been
mapped or not (by checking if there exists an entry $f(v)$). If not, we set
$f(v)=c,f^{-1}(c)=v$ and increment $c$. Once the hash tables $f$ and $f^{-1}$
have been created, we modify the input relation $R$ (and $S$ similarly) by
replacing every tuple $t\in R$ with tuple $t^{\prime}=f(t)$. Since the mapping
is a relabeling scheme, such a transformation preserves the degree of all the
values. The codomain of $f$ is also equipped with a total order $\preceq$ (we
will use $\leq$). Note that $f$ is not an order-preserving transformation in
general but this property is not required in any of our algorithms.

Next, for every tuple $t\in R(x,y)$, we create a hash map with key
$\pi_{x}(t)$ and the value is a list to which $\pi_{y}(t)$ is appended; and
for every tuple $t\in S(y,z)$, we create a hash map with key $\pi_{y}(t)$ and
the value is a list to which $\pi_{z}(t)$ is appended. For the second hash
map, we sort the value list using sort order $\preceq$ for each key, once each
tuple $t\in S(y,z)$ has been processed. Finally, we sort all values in
$\pi_{x}(R)$ in increasing order of their degree in $R$ (i.e
$|\sigma_{x=v_{i}}R(x,y)|$ is the sort key). Let
$\mathcal{L}=\\{v_{1},\dots,v_{n}\\}$ denote the ordered set of these values
sorted by their degree and let $d_{1},\dots,d_{n}$ be their respective
degrees. Creating the sorted list $\mathcal{L}$ takes $O(|D|)$ time since the
degrees $d_{i}$ satisfy the bounded range requirement (i.e $1\leq
d_{i}\leq|D|$). Next, we identify the smallest index $i^{*}$ such that

$\displaystyle\sum_{v:\\{v_{1},v_{2},\dots,v_{i^{*}}\\}}|R(v,y)\Join
S(y,z)|\geq\sum_{v:\\{v_{i^{*}+1},\dots,v_{n}\\}}|R(v,y)\Join S(y,z)|$ (1)

This can be computed by doing a linear pass on $\mathcal{L}$ using a simple
adaptation of Yannakakis algorithm [Yan81, PP06]. This entire phase takes time
$O(|D|)$.

#### Enumeration Phase

The enumeration algorithm interleaves the following two loops using the
construction in Lemma 3. Specifically, it will spend an equal amount of time
(a constant) before switching to the computation of the other loop.

1 for  _$i=1,\dots,i^{*}$_ do

2 Let $\pi_{y}(\sigma_{x=v_{i}}(R))=\\{u_{1},u_{2},\cdots,u_{\ell}\\}$;

3 output
$(v_{i},f^{-1}($ListMerge$(\pi_{z}\sigma_{y=u_{1}}S,\pi_{z}\sigma_{y=u_{2}}S,\cdots,\pi_{z}\sigma_{y=u_{\ell}}S)))$555Abusing
the notation, $f^{-1}(\mathcal{B})$ for some ordered list (or tuple)
$\mathcal{B}$ returns an ordered list (tuple) $\mathcal{B}^{\prime}$ where
$\mathcal{B}^{\prime}(i)=f^{-1}(\mathcal{B}(i))$.

4 run for $O(1)$ timethen switchrun for $O(1)$ timethen switch for
_$i=i^{*}+1,\dots,n$_ do

5 Let $\pi_{y}(\sigma_{x=v_{i}}(R))=\\{u_{1},u_{2},\cdots,u_{\ell}\\}$;

6 output
$(v_{i},f^{-1}($ListMerge$(\pi_{z}\sigma_{y=u_{1}}S,\pi_{z}\sigma_{y=u_{2}}S,\cdots,\pi_{z}\sigma_{y=u_{\ell}}S)))$

Algorithm 3 EnumTwoPath

The algorithm alternates between low-degree and high-degree values in
$\mathcal{L}$. The main idea is that, for a given $v_{i}\in\mathcal{L}$, we
can enumerate the result of the subquery $\sigma_{x=v_{i}}(Q_{\texttt{two-
path}})$ with delay $O(d_{i})$. This can be accomplished by observing that the
subquery is equivalent to list merging and so we can use Algorithm 2.

$\mathbf{X}$ | $\mathbf{Y}$
---|---
$a_{1}$ | $b_{1}$
$a_{1}$ | $b_{2}$
$a_{1}$ | $b_{3}$
$a_{2}$ | $b_{1}$
|
(a) Table $R$

$\mathbf{Y}$ | $\mathbf{Z}$
---|---
$b_{1}$ | $c_{1}$
$b_{1}$ | $c_{2}$
$b_{2}$ | $c_{2}$
$b_{3}$ | $c_{3}$
|
(b) Table $S$

$a_{2}$$b_{1}$$a_{1}$$b_{2}$$b_{3}$$[c_{1},c_{2}]$$S[b_{1}]$$[c_{2}]$$S[b_{2}]$$[c_{3}]$$S[b_{3}]$$\downarrow$$\downarrow$$\downarrow$$\downarrow$
(c) output $(a_{1},c_{1})$

$b_{1}$$a_{1}$$b_{2}$$b_{3}$$[c_{1},c_{2}]$$[c_{2}]$$[c_{3}]$$\downarrow$$\downarrow$$\downarrow$
(d) output $(a_{1},c_{2})$

$b_{1}$$a_{1}$$b_{2}$$b_{3}$$[c_{1},c_{2}]$$[c_{2}]$$[c_{3}]$$\downarrow$$\downarrow$$\downarrow$
(e) output$(a_{1},c_{3})$

Figure 6. Example for two path query enumeration

Consider relations $R$ and $S$ as shown in 6(a) and 6(b). 6(c) shows the
sorted valuations $a_{2}$ and $a_{1}$ by their degree and the valuations for
$Z$ as sorted lists $S[b_{1}],S[b_{2}]$ and $S[b_{3}]$. For both $a_{1}$ and
$a_{2}$, the pointers point to the head of the lists. We will now show how
ListMerge$(S[b_{1}],S[b_{2}],S[b_{3}])$ is executed for $a_{1}$. Since there
are three sorted lists that need to be merged, the algorithm finds the
smallest valuation across the three lists. $c_{1}$ is the smallest valuation
and the algorithm outputs $(a_{1},c_{1})$. Then, we need to increment pointers
of all lists which are pointing to $c_{1}$ ($S[b_{1}]$ is the only list
containing $c_{1}$). 6(d) shows the state of pointers after this step. The
pointer for $S[b_{1}]$ points to $c_{2}$ and all other pointers are still
pointing to the head of the lists. Next, we continue the list merging by again
finding the smallest valuation from each list. Both $S[b_{1}]$ and $S[b_{2}]$
pointers are pointing to $c_{2}$ and the algorithm outputs $(a_{1},c_{2})$.
The pointers for both $S[b_{1}]$ and $S[b_{2}]$ are incremented and the
enumeration for both the lists is complete as shown in 6(e). In the last step,
only $S[b_{3}]$ list remains and we output $(a_{1},c_{3})$ and increment the
pointer for $S[b_{3}]$. All pointers are now past the end of the lists and the
enumeration is now complete.

######  Theorem 7.

For the query $Q_{\texttt{two-path}}$ and an instance $D$, we can enumerate
$Q_{\texttt{two-path}}(D)$ with delay
$\delta=O(|D|^{2}/|\texttt{OUT}_{\Join}|)$ and $S_{e}=O(|D|)$.

######  Proof 4.1.

To prove this result, we will apply Lemma 3, where $\mathcal{A}^{\prime}$ is
the first loop (the one with light-degree values), and $\mathcal{A}$ is the
second loop (the one with high-degree values).

Let $\delta$ denote the degree of the valuation $v_{i^{*}}$. First, we claim
that the delay of $\mathcal{A}^{\prime}$ will be $O(\delta)$. Indeed,
ListMerge will output a result every $O(\delta)$ time since the degree of each
valuation in the first loop is at most $\delta$. Let
$J_{h}=\sum_{i>i^{*}}|R(v_{i},y){\Join}S(y,z)|$ and $J_{\ell}=\sum_{i\leq
i^{*}}|R(v_{i},y){\Join}S(y,z)|$. Then, $\mathcal{A}^{\prime}$ runs in time at
least $J_{\ell}$, and $\mathcal{A}$ in time at most $c^{\star}\cdot J_{h}$.
Here, $c^{\star}$ is an upper bound on the number operations in each iteration
of the loop in Algorithm 3. Since by construction $J_{\ell}\geq J_{h}$, Lemma
3 obtains a total delay of $O(\delta)$.

It now remains to bound $\delta$. First, observe that, since $i^{*}$ is the
smallest index that satisfies Equation 1, it must be that
$J_{\ell}-J_{h}\leq|D|$ (if not, shifting the smallest index by one decreases
the LHS by at most $|D|$ and increases the RHS by at most $|D|$ while still
satisfying the condition that $J_{\ell}\geq J_{h}$). Combined with the
observation that $J_{\ell}+J_{h}=|\texttt{OUT}_{\Join}|$, we get that
$J_{h}\geq|\texttt{OUT}_{\Join}|/2-|D|/2\geq 1/4\cdot|\texttt{OUT}_{\Join}|$
assuming $|\texttt{OUT}_{\Join}|\geq 2\cdot|D|$. The final observation is that
$J_{h}\leq|D|^{2}/\delta$ since there are most $|D|/\delta$ heavy values, and
each heavy value can join with at most $|D|$ tuples for the full join.
Combining the two inequalities gives us the claimed delay guarantee.

The reader should note that the delay of
$\delta=O(|D|^{2}/|\texttt{OUT}_{\Join}|)$ is only an upper bound. Depending
on the skew present in the database instance, it is possible that Algorithm 3
achieves much better delay guarantees in practice as shown in Example 4.2
below.

Consider a relation $R(x,y)$ of size $O(N)$ that contains values
$v_{1},\dots,v_{N}$ for attribute $x$. Suppose that each of
$v_{1},\dots,v_{N-1}$ have degree exactly 1, and each one is connected to a
unique value of $y$. Also, $v_{N}$ has degree $N-1$ and is connected to all
$N-1$ values of $y$. Suppose we want to compute $Q_{\texttt{two-path}}$. It is
easy to see that $\texttt{OUT}_{\Join}=\Theta(N)$. Thus, applying the bound of
$\delta=O(N^{2}/|\texttt{OUT}_{\Join}|)$ gives us $O(N)$ delay. However,
Algorithm 3 will achieve a delay guarantee of $O(1)$. This is because all of
$v_{1},\dots,v_{N-1}$ are processed by the left pointer in $O(1)$ delay as
they produce exactly one output result, while the right pointer processes
$v_{N}$ on-the-fly in $O(N)$ time.

###  4.3. Proof of Main Theorem

We now generalize Algorithm 3 for any star query. At a high level, we will
decompose the join query $\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ into a union of
$k+1$ subqueries whose output is a partition of the result of original query.
These subqueries will be generated based on whether a value for some $x_{i}$
is _light_ or not. We will show if any of the values for $x_{i}$ is light, the
enumeration delay is small. The $(k+1)$-th subquery will contain heavy values
for all attributes. Our key idea again is to interleave the join computation
of the heavy subquery with the remaining light subqueries.

#### Preprocessing Phase

Assume all relations are reduced without dangling tuples, which can be
achieved in linear time [Yan81]. The full join size $|\texttt{OUT}_{\Join}|$
can also be computed in linear time. Similar to the preprocessing phase in the
previous section, we construct the hash tables $f,f^{-1}$ to perform the
domain compression and modify all the input relations by replacing tuple $t$
with $f(t)$. Set
$\Delta=({2\cdot|D|^{k}}/{|\texttt{OUT}_{\Join}|})^{\frac{1}{k-1}}$. For each
relation $R_{i}$, a value $v$ for attribute $x_{i}$ is heavy if its degree
(i.e $|\pi_{y}\sigma_{x_{i}=v}R(x_{i},y)|$) is greater than $\Delta$, and
light otherwise. Moreover, a tuple $t\in R_{i}$ is identified as heavy or
light depending on whether $\pi_{x_{i}}(t)$ is heavy or light. In this way,
each relation $R$ is divided into two relations $R^{h}$ and $R^{\ell}$,
containing heavy and light tuples respectively in time $O(|D|)$. The original
query can be decomposed into subqueries of the following form:

$\pi_{x_{1},x_{2},\cdots,x_{k}}(R^{?}_{1}\Join R^{?}_{2}\Join\cdots\Join
R^{?}_{k})$

where $?$ can be either $h,\ell$ or $\star$. Here, $R^{\star}_{i}$ simply
denotes the original relation $R_{i}$. However, care must be taken to generate
the subqueries in a way so that there is no overlap between the output of any
subquery. In order to do so, we create $k$ subqueries of the form

$Q_{i}=\pi_{x_{1},\dots,x_{k}}(R^{h}_{1}\Join\cdots\Join R^{h}_{i-1}\Join
R^{\ell}_{i}\Join R^{\star}_{i+1}\Join\cdots\Join R^{\star}_{k})$

In subquery $Q_{i}$, relation $R_{i}$ has superscript $\ell$, all relations
$R_{1},\dots,R_{i-1}$ have superscript $h$ and relations $R_{i+1},\dots,R_{k}$
have superscript $\star$. The $(k+1)$-th query with all $?$ as $h$ is denoted
by $Q_{H}$. Note that each output tuple $t$ is generated by exactly one of the
$Q_{i}$ and thus the output of all subqueries is disjoint. This implies that
each $f^{-1}(t)$ is also generated by exactly one subquery. Similar to the
preprocessing phase of two path query, we store all $R^{\ell}_{i}$ and
$R^{h}_{i}$ in hashmaps where the values in the maps are lists sorted in
lexicographic order.

#### Enumeration Phase

We next describe how enumeration is performed. The key idea is the following:
We will show that for $Q_{L}=Q_{1}\cup\dots\cup Q_{k}$, we can enumerate the
result with delay $O(\Delta)$. Since $Q_{H}$ contains all heavy valuations
from all relations, we compute its join _on-the-fly_ by alternating between
some subquery in $Q_{L}$ and $Q_{H}$. This will ensure that we can give some
output to the user with delay guarantees and also make progress on computing
the full join of $Q_{H}$. Our goal is to reason about the running time of
enumerating $Q_{L}$ (denoted by $T_{L}$) and the running time of $Q_{H}$
(denoted by $T_{H}$) and make sure that while we compute $Q_{H}$, we do not
run out of the output from $Q_{L}$.

Next, we introduce the algorithm that enumerates output for any specific
valuation $v$ of attribute $x_{i}$, which is described in Lemma 8. This
algorithm can be viewed as another instantiation of Algorithm 2.

######  Lemma 8.

Consider an arbitrary value $v\in\mathbf{dom}(x_{i})$ with degree $d$ in
relation $R_{i}(x_{i},y)$. Then, its query result
$\pi_{x_{1},x_{2},\cdots,x_{k}}\sigma_{x_{i}=v}R^{h}_{1}(x_{1},y)\Join
R^{h}_{2}(x_{2},y)\Join\cdots\Join R_{i}(x_{i},y)\Join\cdots\Join
R^{\star}_{k}(x_{k},y)$ can be enumerated with $O(d)$ delay guarantee.

######  Proof 4.2.

Consider some tuple $(v_{i},u)\in R_{i}$. Each $u$ is associated with a list
of valuations over attributes $(x_{1},\cdots,x_{i-1},x_{i+1},\cdots,x_{k})$,
which is a cartesian product of $k-1$ sub-lists $\sigma_{y=u}R_{j}(x_{j},y)$.
Note that such a list is not materialized as that for two-path query, but
present in a factorized form.

We next define the enumeration algorithm $\mathcal{A}_{u}$ for each
$u\in\pi_{y}\sigma_{x_{i}=v}R_{i}(x_{i},y)$, with lexicographical ordering of
attributes $(x_{1},\cdots,x_{i-1},x_{i+1},\cdots,x_{k})$. Note that elements
in each list $\pi_{x_{j}}\sigma_{y=u}R^{?}_{j}(x_{j},y)$ can be enumerated
with $O(1)$ delay. Then, $\mathcal{A}_{u}$ enumerates all results in
$\times_{j\neq i:j\in\\{1,2\cdots,k\\}}\sigma_{y=u}R^{?}_{j}(x_{j},y)$ by
$k-1$ level of nested loops in lexicographic order
$(x_{1},\cdots,x_{i-1},x_{i+1},\cdots,x_{k})$, which has $O(k-1)=O(1)$ delay.
After applying Algorithm 2, we can obtain an enumeration algorithm that
enumerates the union of query results over all neighbors with $O(d)$ delay
guarantee. For each output tuple $t$ generated by Algorithm 2, we return
$f^{-1}(t)$ to the user.

Let $c^{\star}$ be an upper bound on the number of operations in each
iteration of ListMerge. This can be calculated by counting the number of
operations in the exact implementation of the algorithm. Directly implied by
Lemma 8, the result of any subquery in $Q_{L}$ can be enumerated with delay
$O(\Delta)$. Let $Q_{H}^{*}$ denote the corresponding full query of $Q_{H}$,
i.e, the head of $Q_{H}^{*}$ also includes the variable $y$ ($Q_{L}^{*}$ is
defined similarly). Then, $Q_{H}^{*}$ can be evaluated in time $T_{H}\leq
c^{\star}\cdot|Q_{H}^{*}|\leq c^{\star}\cdot|\texttt{OUT}_{\Join}|/2$ by using
ListMerge on subquery $Q_{H}$. This follows from the bound
$|Q_{H}^{*}|\leq|D|\cdot(|D|/\Delta)^{k-1}$ and our choice of
$\Delta=({2\cdot|D|^{k}}/{|\texttt{OUT}_{\Join}|})^{\frac{1}{k-1}}$. Since
$|Q_{H}^{*}|+|Q_{L}^{*}|=|\texttt{OUT}_{\Join}|$, it holds that
$|Q_{L}^{*}|\geq|\texttt{OUT}_{\Join}|/2$ given our choice of $\Delta$. Also,
the running time $T_{L}$ is lower bounded by $|Q_{L}^{*}|$ (since we need at
least one operation for every result). Thus,
$T_{L}\geq|\texttt{OUT}_{\Join}|/2$.

We are now ready to apply Lemma 3 with the following parameters:

  1. (1)

$\mathcal{A}$ is the full join computation of $Q_{H}$ and
$T=c^{\star}\cdot|\texttt{OUT}_{\Join}|/2$.

  2. (2)

$\mathcal{A}^{\prime}$ is the enumeration algorithm applied to $Q_{L}$ with
delay guarantee $\delta=O(\Delta)$ and $T^{\prime}=|\texttt{OUT}_{\Join}|/2$.

  3. (3)

$T$ and $T^{\prime}$ are fixed once $|\texttt{OUT}_{\Join}|,\Delta$, and the
constant $c^{\star}$ are known.

By construction, the outputs of $Q_{H}$ and $Q_{L}$ are also disjoint. Thus,
the conditions of Lemma 3 apply and we obtain a delay of $O(\Delta)$.

###  4.4. Interleaving with Join Computation

Theorem 6 obtains poor delay guarantees when the full join size
$|\texttt{OUT}_{\Join}|$ is close to input size $|D|$. In this section, we
present an alternate algorithm that provides good delay guarantees in this
case. The algorithm is an instantiation of Lemma 4 on the star query, which
degenerates to computing as many distinct output results as possible in
limited preprocessing time. An observation is that for each valuation $u$ of
attribute $y$, the cartesian product
$\times_{i\in\\{1,2,\cdots,k\\}}\pi_{x_{i}}\sigma_{y=u}R_{i}(x_{i},y)$ is a
subset of output results without duplication. Thus, this subset of output
result is readily available since no deduplication needs to be performed.
Similarly, after all relations are reduced, it is also guaranteed that each
valuation of attribute $x_{i}$ of relation $R_{i}$ generates at least one
output result. Thus, $\max_{i=1}^{k}|\mathbf{dom}(x_{i})|$ results are also
readily available that do not require deduplication. We define $J$ as the
larger of the two quantities, i.e,
$J=\max\left\\{\max_{i=1}^{k}|\mathbf{dom}(x_{i})|,\max_{u\in\mathbf{dom}(y)}\prod_{i=1}^{k}|\sigma_{y=u}R_{i}(x_{i},y)|\right\\}$.
Together with these observations, we can achieve the following theorem.

######  Theorem 9.

Consider star query $\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ and an input database
instance $D$. There exists an algorithm with preprocessing time $O(|D|)$ and
space $O(|D|)$, such that $\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ can be
enumerated with $\text{delay
}\delta=O\bigg{(}{|\texttt{OUT}_{\Join}|}/{|\texttt{OUT}_{\pi}|^{1/k}}\bigg{)}\text{and
space }S_{e}=O(|D|)$

In the above theorem, we obtain delay guarantees that depend on both the size
of the full join result $\texttt{OUT}_{\Join}$ and the projection output size
$\texttt{OUT}_{\pi}$.

However, one does not need to know $|\texttt{OUT}_{\Join}|$ or
$|\texttt{OUT}_{\pi}|$ to apply the result. We first compare the result with
Theorem 6. First, observe that both Theorem 9 and Theorem 6 require $O(|D|)$
preprocessing time. Second, the delay guarantee provided by Theorem 9 can be
better than Theorem 6. This happens when $|\texttt{OUT}_{\Join}|\leq|D|\cdot
J^{1-1/k}$, a condition that can be easily checked in linear time.

We now proceed to describe the algorithm. First, we compute all the statistics
for computing $J$ in linear time. If $J=|\mathbf{dom}(x_{j})|$ for some
integer $j\in\\{1,2,\cdots,k\\}$, we just materialize one result for each
valuation of $x_{j}$. Otherwise,
$J=\prod_{i=1}^{k}|\sigma_{y=u}R_{i}(x_{i},y)|$ for some valuation $u$ in
attribute $y$. Note that we do not need to explicitly materialize the
cartesian product but only need to store the tuples in
$\bigcup_{i\in\\{1,2,\cdots,k\\}}\sigma_{y=u}R_{i}(x_{i},y)$. As mentioned
before, each output in
$\times_{i=1}^{k}\left(\pi_{x_{i}}\sigma_{y=u}R_{i}(x_{i},y)\right)$ can be
enumerated with $O(1)$ delay. This preprocessing phase takes $O(|D|)$ time and
$O(|D|)$ space. We can now invoke Lemma 4 to achieve the claimed delay. The
final observation is to express $J$ in terms of $|\texttt{OUT}_{\pi}|$. Note
that $|\texttt{OUT}_{\pi}|\leq\Pi_{i\in[k]}|\mathbf{dom}(x_{i})|$ which
implies that
$\max_{i\in[k]}|\mathbf{dom}(x_{i})|\geq|\texttt{OUT}_{\pi}|^{1/k}$. Thus, it
holds that $J\geq|\texttt{OUT}_{\pi}|^{1/k}$ which gives us the desired bound
on the delay guarantee.

#### Dynamic Setting

Remarkably, it is also possible to do a simple adaptation of the algorithm for
the dynamic setting but only in the case of self-joins, where
$R_{1}=R_{2}=\dots R_{k}=R$. In this setting, single tuple updates are allowed
to the underlying relation, i.e., a tuple $t$ over variables $x,y$ can be
either inserted or deleted from the relation $R(x,y)$ (note that a relation
does not allow duplicates). The preprocessing phase in this case simply stores
$R(x,y)$ is stored as bidirectional hash map (one map with key as $y$
valuation and the value as the sorted list of $x_{i}$ valuations connected to
it and other map with key as $x_{i}$ valuation and the value as the sorted
list of $y$ valuations). This hash map can be maintained in amortized constant
time under single-tuple updates. We also store a hash set called $J$
containing $(a,a)$ for all $a\in\mathbf{dom}(x)$. $J$ can also be maintained
under updates in amortized constant time. Indeed, whenever the degree of some
$x$ valuation becomes zero and it is removed from the hash maps of $R$, we can
also remove it from $J$. Similarly, whenever a new domain value is added for
the first time to $R$, we can update insert it into $J$.

For the enumeration phase, we simply apply Lemma 4 with stored hash set $J$.
Applying the same reasoning as above, we can delay
$\delta=O({|\texttt{OUT}_{\Join}|}/{|\texttt{OUT}_{\pi}|^{1/k}})$. We can now
state the result formally.

######  Theorem 10.

Consider a self-join star query $\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ over a
single relation $R(x,y)$ and an input database instance $D$. There exists an
algorithm with preprocessing time $O(|D|)$ and space $O(|D|)$, such that
$\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ can be enumerated with $\text{delay
}\delta=O\bigg{(}{|\texttt{OUT}_{\Join}|}/{|\texttt{OUT}_{\pi}|^{1/k}}\bigg{)}\\\
\text{and space }S_{e}=O(|D|)$ with $O(1)$ amortized update time for single-
tuple updates.

To achieve constant amortized update time, the main result that applies to all
hierarchical queries (including self-joins) from [KNOZ20] requires linear
preprocessing time and achieves worst-case linear delay. Since
${|\texttt{OUT}_{\Join}|}/{|\texttt{OUT}_{\pi}|^{1/k}}\leq|D|$ [AP09], our
strategy provides an alternate algorithm that achieves the same worst-case
linear delay but may perform better on certain database instances. Modifying
our algorithm for the non self-join case is a non-trivial problem and likely
requires development of new technical machinery that we leave as a problem for
future work.

###  4.5. Fast Matrix Multiplication

Both Theorem 6 and Theorem 2.3 are combinatorial algorithms. In this section,
we will show how fast matrix multiplication can be used to obtain a tradeoff
between preprocessing time and delay that is better than Theorem 2.3 for some
values of delay.

######  Theorem 11.

Consider the star query $\pi_{x_{1},\dots,x_{k}}(Q^{*}_{k})$ and an input
database instance $D$. Then, there exists an algorithm that requires
preprocessing $T_{p}=O((|D|/\delta)^{\omega+k-2})$ and can enumerate the query
result with delay $O(\delta)$ for
$1\leq\delta\leq|D|^{(\omega+k-3)/(\omega+2\cdot k-3)}$.

######  Proof 4.3.

We sketch the proof for $k=2$. Let $\delta$ be the degree threshold for
deciding whether a valuation is heavy or light. We can partition the original
query into the following subqueries:
$\pi_{x,z}(R_{1}(x^{?},y^{?}){\Join}R_{2}(y^{?},z^{?}))$ where $?$ can be
either $h,\ell$ or $\star$. The input tuples can also be partitioned into four
different cases (which can be done in linear time since $\delta$ is fixed). We
handle each subquery separately.

  * •

$x$ has $?=\ell$, $y$ has $?=\star$ and $z$ has $?=\star$. In this case, we
can just invoke ListMerge$(v_{i})$ for each valuation $v_{i}$ of attribute $x$
and enumerate the output.

  * •

$x$ has $?=h$, $y$ has $?=\star$ and $z$ has $?=\ell$. In this case, we can
invoke ListMerge$(v_{i})$ for each valuation $v_{i}$ of attribute $z$ and
enumerate the output. Note that there is no overlap of output between this
case and the previous case.

  * •

both $x,z$ have $?=h$. We compute the output of $\pi_{x,z}R(x^{h},y^{?})\Join
S(y^{?},z^{h})$ in preprocessing phase and obtain $O(1)$-delay enumeration. In
the following, we say that $y$ has $?=\ell$ to mean that the join considers
all $y$ valuations that have degree at most $\delta$ in both $R$ and $S$.

    * –

$y$ has $?=\ell$. We compute the full join $R(x^{h},y^{\ell})\Join
S(y^{\ell},z^{h})$ and materialize all distinct output results, which takes
$O(|D|\cdot\delta)$ time.

    * –

$y$ has $?=h$. There are at most $|D|/\delta$ valuations in all attributes. We
now have a square matrix multiplication instance where all dimensions have
size $O(|D|/\delta)$. Using Lemma 2, we can evaluate the join in time
$O((|D|/\delta)^{\omega})$.

Overall, the preprocessing time is
$T_{p}=O((|D|/\delta)^{\omega}+|D|\cdot\delta)$. The matrix multiplication
term dominates whenever $\delta\leq O(|D|^{(\omega-1)/(\omega+1)})$ which
gives us the desired time-delay tradeoff.

For the two-path query and the current best value of $\omega=2.373$, we get
the tradeoff as $T_{p}=O((|D|/\delta)^{2.373})$ and a delay guarantee of
$O(\delta)$ for $|D|^{0.15}<\delta\leq|D|^{0.40}$. If we choose
$\delta=|D|^{0.40}$, the worst-case preprocessing time is
$T_{p}=O(|D|^{1.422})$. In contrast, Theorem 2.3 requires a worst-case
preprocessing time of $T_{p}=O(|D|^{1.6})$, which is suboptimal compared to
the above theorem. On the other hand, since $T_{p}=O(|D|^{1.422})$,  we can
safely assume that $|\texttt{OUT}_{\Join}|>|D|^{1.422}$, otherwise one can
simply compute the full join in time $c^{\star}\cdot|D|^{1.422}$ using
ListMerge, deduplicate and get constant delay enumeration. Applying Theorem 6
with $|\texttt{OUT}_{\Join}|>|D|^{1.422}$ tells us that we can obtain delay as
$O(|D|^{2}/|\texttt{OUT}_{\Join}|)=O(|D|^{0.58})$. Thus, we can offer the user
both choices and the user can decide which enumeration algorithm to use.

##  5\. Left-Deep Hierarchical Queries

In this section, we will apply our techniques to another subset of
hierarchical queries, which we call left-deep. A left-deep hierarchical query
is of the following form:

$Q_{\texttt{leftdeep}}^{k}=R_{1}(w_{1},x_{1}){\Join}R_{2}(w_{2},x_{1},x_{2}){\Join}\dots\Join
R_{k-1}(w_{k-1},x_{1},\dots,x_{k-1}){\Join}R_{k}(w_{k},x_{1},\dots,x_{k})$

It is easy to see that $Q_{\texttt{leftdeep}}^{k}$ is a hierarchical query for
any $k\geq 1$. Note that for $k=2$, we get the two-path query. For $k=3$, we
get $R(w_{1},x_{1})\Join S(w_{2},x_{1},x_{2})\Join T(w_{3},x_{1},x_{2})$. We
will be interested in computing the query
$\pi_{w_{1},\dots,w_{k}}(Q_{\texttt{leftdeep}}^{k})$, where we project out all
the join variables. We show that the following result holds:

######  Theorem 12.

Consider the query $\pi_{w_{1},\dots,w_{k}}(Q_{\texttt{leftdeep}}^{k})$ and
any input database $D$. Then, there exists an algorithm that enumerates the
query after preprocessing time $T_{p}=O(|D|)$ with delay
$O(|D|^{k}/|\texttt{OUT}_{\Join}|)$.

######  Proof 5.1.

Once again, we will use the same steps of the preprocessing phase as in Lemma
7. We index all the input relations in a hash table where the values are
sorted lists after applying the domain compression trick using $f$ and
$f^{-1}$. Thus, count sort now runs in $O(|D|)$ time. We also compute
$|\texttt{OUT}_{\Join}|$ using Yannakakis algorithm.

The algorithm is based on ListMerge subroutine from Lemma 5. We distinguish
two cases based on the degree of valuations of variable $w_{k}$. If some
valuation of $w_{k}$ (say $v$) is light (degree is at most $\delta$), then we
can enumerate the join result with delay $O(\delta)$. Since there are at most
$\delta$ tuples $U=\sigma_{w_{k}=v}R_{k}$, each $u\in U$ is associated with a
list of valuations over attributes $(w_{1},w_{2},\dots,w_{k-1})$, which is a
cartesian product of $k-1$ sorted sub-lists
$\pi_{w_{i}}\sigma_{x_{1}=u[x_{1}],\dots,x_{i}=u[x_{i}]}R_{i}$. The elements
of each list can be enumerated in $O(1)$ delay in lexicographic order. Thus,
we only need to merge the $\delta$ sublists which can be accomplished in
$O(\delta)$ time using Lemma 5. Let $T_{L}$ denote the total time required to
enumerate the query result for all light $w_{k}$ valuations.

We now describe how to process all $w_{k}$ valuations that are heavy. The key
observation here is that the full-join result with no projections for this
case can be upper bounded by $|D|^{k}/\delta$ since there are at most
$|D|/\delta$ heavy $w_{k}$ valuations.  The full-join result of the heavy
subquery can be done in time $T_{H}\leq c^{\star}\cdot|D|^{k}/\delta$ using
ListMerge. Fixing $\delta=2\cdot|D|^{k}/|\texttt{OUT}_{\Join}|$ gives us
$T_{H}\leq c^{\star}\cdot|\texttt{OUT}_{\Join}|/2$. Since
$|Q^{*}_{L}|+|Q^{*}_{H}|=|\texttt{OUT}_{\Join}|$, our choice of $\delta$
ensures that $T_{L}\geq|Q^{*}_{L}|\geq|\texttt{OUT}_{\Join}|/2$.

We can now apply Lemma 3 with $(i)$ $\mathcal{A}^{\prime}$ is the list-merging
algorithm for the light case with $T^{\prime}=|\texttt{OUT}_{\Join}|/2$;
$(ii)$ $\mathcal{A}$ is the worst-case optimal join algorithm for the heavy
case with $T=c^{\star}\cdot|\texttt{OUT}_{\Join}|/2$; $(iii)$ $T,T^{\prime}$
are fixed once $|\texttt{OUT}_{\Join}|,\delta,c^{\star}$ have been
computed.Once again, in order to know the exact values of $T,T^{\prime}$, we
need to analyze the exact constant that is used in the join algorithm for
ListMerge. By construction, the output of $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ is different. Note that for each output tuple $t$
generated, we return $f^{-1}(t)$ to the the user, a constant time operation.

In the above theorem, $\texttt{OUT}_{\Join}$ is the full join result of the
query $Q_{\texttt{leftdeep}}^{k}$ without projections. The AGM exponent for
$Q_{\texttt{leftdeep}}^{k}$ is $\rho^{*}=k$. Observe that Theorem 12 is of
interest when $|\texttt{OUT}_{\Join}|>|D|^{k-1}$ to ensure that the delay is
smaller than $O(|D|)$. When the condition $|\texttt{OUT}_{\Join}|>|D|^{k-1}$
holds, the delay obtained by Theorem 12 is also better than the one given by
the tradeoff in Theorem 2.3. In the worst-case when
$|\texttt{OUT}_{\Join}|=\Theta(|D|^{k})$, we can achieve constant delay
enumeration after linear preprocessing time, compared to Theorem 2.3 that
would require $\Theta(|D|^{k})$ preprocessing time to achieve the same delay.
The decision of when to apply Theorem 12 or Theorem 2.3 can be made in linear
time by checking whether $|D|^{k}/|\texttt{OUT}_{\Join}|$ is smaller or larger
than the actual delay guarantee obtained by the algorithm of Theorem 2.3 after
linear time preprocessing.

##  6\. Path Queries

In this section, we will study path queries. In particular, we will present an
algorithm that enumerates the result of the query
$\pi_{x_{1},x_{k+1}}(P_{k})$, i.e., the CQ that projects the two endpoints of
a path query of length $k$. Recall that for $k\geq 3$, $P_{k}$ is not a
hierarchical query, and hence the tradeoff from [KNOZ20] does not apply. A
subset of path queries, namely 3-path and 4-path counting queries were
considered in [KNN+19]. The algorithm used for counting the answers of 3-path
and 4-path queries under updates constructed a set of views that can be used
for the task of enumerating the query results under the static setting. Our
result extends the same idea to apply to arbitrary length path queries, which
we state next.

######  Theorem 13.

Consider the query $\pi_{x_{1},x_{k+1}}(P_{k})$ with $k\geq 2$. For any input
instance $D$ and parameter $\epsilon\in[0,1)$ there exists an algorithm that
enumerates the query with preprocessing time (and space)
$T_{p}=O(|D|^{2-\epsilon/(k-1)})$ and delay $O(|D|^{\epsilon})$.

######  Proof 6.1.

Let $\Delta$ be a parameter that we will fix later. In the preprocessing
phase, we first perform a full reducer pass to remove dangling tuples, apply
the domain transformation technique by creating $f$ and $f^{-1}$ and then
create a hash map for each relation $R_{i}(x_{i},x_{i+1})$ with key $x_{i}$,
and all its corresponding $x_{i+1}$ values sorted for each key entry. (We also
store the degree of each value.) Next, for every $i=1,\dots,k$, and every
heavy value $a$ of $x_{i}$ in $R_{i}$ (with degree $>\Delta$), we compute the
query $\pi_{x_{k+1}}(R_{i}(a,x_{i+1})\Join\dots\Join R_{k}(x_{k},x_{k+1}))$,
and store its result sorted in a hash map with key $a$. Note that each such
query can be computed in time $O(|D|)$ through a sequence of semijoins and
projections, and sorting in linear time using count sort. Since there are at
most $|D|/\Delta$ heavy values for each $x_{i}$, the total running time (and
space necessary) for this step is $O(|D|^{2}/\Delta)$.

We will present the enumeration algorithm using induction. In particular, we
will show that for each $i=k,\dots,1$ and for every value $a$ of $x_{i}$, the
subquery $\pi_{x_{k+1}}(R_{i}(a,x_{i+1})\Join\dots\Join R_{k}(x_{k},x_{k+1}))$
can be enumerated (using the same order) with delay $O(\Delta^{k-i})$. This
implies that our target path query can be enumerated with delay
$O(\Delta^{k-1})$, by simply iterating through all values of $x_{1}$ in
$R_{1}$. Finally we can obtain the desired result by choosing
$\Delta=|D|^{\epsilon/(k-1)}$.

Indeed, for the base case ($i=k$) it is trivial to see that we can enumerate
$\pi_{x_{k+1}}(R_{k}(a,x_{k+1}))$ in constant time $O(1)$ using the stored
hash map. For the inductive step, consider some $i$, and a value $a$ for
$x_{i}$ in $R_{i}$. If the value $a$ is heavy, then we can enumerate all the
$x_{k+1}$’s with constant delay by probing the hash map we computed during the
preprocessing phase. If the value is light, then there are at most $\Delta$
values of $x_{i+1}$. For each such value $b$, the inductive step provides an
algorithm that enumerates all $x_{k+1}$ with delay $O(\Delta^{k-i-1})$.
Observe that the order across all $b$’s will be the same. Thus, we can apply
Lemma 5 to obtain that we can enumerate the union of the results with delay
$O(\Delta\cdot\Delta^{k-i-1})=O(\Delta^{k-i})$. Finally, For each output tuple
$t$ generated, we return $f^{-1}(t)$ to the the user.

We should note here that for $\epsilon=1$, we can obtain a delay $O(|D|)$
using only linear preprocessing time $O(|D|)$ using the result of [BDG07]
since the query is acyclic, while for $\epsilon\rightarrow 1$ the above
theorem would give preprocessing time $O(|D|^{2-1/(k-1)})$. Hence, for $k\geq
3$, we observe a discontinuity in the time-delay tradeoff. A second
observation following from Theorem 13 is that as $k\rightarrow\infty$, the
tradeoff collapses to only two extremal points: one where we get constant
delay with $T_{p}=O(|D|^{2})$, and the other where we get linear delay with
$T_{p}=O(|D|)$.

##  7\. Related Work

We overview prior work on static query evaluation for acyclic join-project
queries. The result of any acyclic conjunctive query can be enumerated with
constant delay after linear-time preprocessing if and only if it is free-
connex [BDG07]. This is based on the conjecture that Boolean multiplication of
$n\times n$ matrices cannot be done in $O(n^{2})$ time. Acyclicity itself is
necessary for having constant delay enumeration: A conjunctive query admits
constant delay enumeration after linear-time preprocessing if and only if it
is free-connex acyclic [BB13]. This is based on a stronger hypothesis that the
existence of a triangle in a hypergraph of $n$ vertices cannot be tested in
time $O(n^{2})$ and that for any $k$, testing the presence of a
$k$-dimensional tetrahedron cannot be tested in linear time. We refer the
reader to an overview of pre-2015 for problems and progress related to
constant delay enumeration [Seg15b]. Prior work also exhibits a dependency
between the space and enumeration delay for conjunctive queries with access
patterns [DK18]. It constructs a succinct representation of the query result
that allows for enumeration of tuples over some variables under value bindings
for all other variables. As noted by [KNOZ20], it does not support enumeration
for queries with free variables, which is also its main contribution. Our work
demonstrates that for a subset of hierarchical queries, the tradeoff shown in
[KNOZ20] is not optimal. Our work introduces fundamentally new ideas that may
be useful in improving the tradeoff for arbitrary hierarchical queries and
enumeration of UCQs. There has also been some experimental work by the
database community on problems related to enumerating join-project query
results efficiently but without any formal delay guarantees. Seminal work
[XKD15, XD17, XSD17, DK21] has studied how compressed representations can be
created apriori that allow for faster enumeration of query results. For the
two path query, the fastest evaluation algorithm (with no delay guarantees)
evaluates the projection join output in time
$O(|D|\cdot|\texttt{OUT}_{\pi}|^{\frac{(\omega-1)}{(\omega+1)}}+|D|^{\frac{2(\omega-1)}{(\omega+1)}}\cdot|\texttt{OUT}_{\pi}|^{\frac{2}{(\omega+1)}})$
[DHK20, AP09]. For star queries, there is no closed form expression but fast
matrix multiplication can be used to obtain instance dependent bounds on
running time. Also related is the problem of dynamic evaluation of
hierarchical queries. Recent work [KNN+19, KNOZ20, BKS17, BKS18] has studied
the tradeoff between amortized update time and delay guarantees. Some of our
techniques may also lead to new insights and improvements in existing
algorithms. Prior work in differential privacy [RCWH+20] and directed
graphical models [CRJ20] may also benefit from some of our techniques.

##  8\. Conclusion and Open Problems

In this paper, we studied the problem of enumerating query results for an
important subset of CQs with projections, namely star and path queries. We
presented data-dependent algorithms that improve upon existing results by
achieving non-trivial delay guarantees in linear preprocessing time. Our
results are based on the idea of interleaving join query computation to
achieve meaningful delay guarantees. Further, we showed how non-combinatorial
algorithms (fast matrix multiplication) can be used for faster preprocessing
to improve the tradeoff between preprocessing time and delay. We also
presented new results on time-delay tradeoffs for a subset of non-hierarchical
queries for the class of path queries. Our results also open several new
tantalizing questions that open up possible directions for future work.

More preprocessing time for star queries. The second major open question is to
show whether Theorem 6 can benefit from more preprocessing time to achieve
lower delay guarantees. For instance, if we can afford the algorithm
preprocessing time $T_{p}=O(|\texttt{OUT}_{\Join}|/|D|^{\epsilon}+|D|)$ time,
can we expect to get delay $\delta=O(|D|^{\epsilon})$ for all
$\epsilon\in(0,1)$?

Sublinear delay guarantees for two-path query. It is not known whether we can
achieve sublinear delay guarantee in linear preprocessing time for
$Q_{\texttt{two-path}}$ query. This question is equivalent to the following
problem: for what values of $|\texttt{OUT}_{\pi}|$ can $Q_{\texttt{path}}$ be
evaluated in linear time. If $|\texttt{OUT}_{\pi}|=|D|^{\epsilon}$, then the
best known algorithms can evaluate $Q_{\texttt{two-path}}$ in time
$O(|D|^{1+\epsilon/3})$ (using fast matrix multiplication) [DHK20] but this is
still superlinear.

Space-delay bounds. The last question is to study the tradeoff between space
vs delay for arbitrary hierarchical queries and path queries. Using some of
our techniques, it may be possible to smartly materialize a certain subset of
joins that could be used to achieve delay guarantees by interleaving with join
computation. We also believe that the space-delay tradeoff implied by prior
work can also be improved for certain ranges of delay by using the ideas
introduced in this paper.

## References

  * [AKNS17] Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu.  What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?  In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 429–444, 2017.
  * [AP09] Rasmus Resen Amossen and Rasmus Pagh.  Faster join-projects and sparse matrix multiplications.  In Proceedings of the 12th International Conference on Database Theory, pages 121–126. ACM, 2009.
  * [BB13] Johann Brault-Baron.  De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre.  PhD thesis, Université de Caen, 2013.
  * [BDG07] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In International Workshop on Computer Science Logic, pages 208–222. Springer, 2007.
  * [BKS17] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 303–318. ACM, 2017.
  * [BKS18] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering fo+ mod queries under updates on bounded degree databases.  ACM Transactions on Database Systems (TODS), 43(2):7, 2018.
  * [BMT20] Angela Bonifati, Wim Martens, and Thomas Timm.  An analytical study of large sparql query logs.  The VLDB Journal, 29(2):655–679, 2020.
  * [CLRS09] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Chapter 8.2, Introduction to algorithms.  MIT press, 2009.
  * [CRJ20] Amrita Roy Chowdhury, Theodoros Rekatsinas, and Somesh Jha.  Data-dependent differentially private parameter learning for directed graphical models.  In International Conference on Machine Learning, pages 1939–1951. PMLR, 2020.
  * [DHK20] Shaleen Deep, Xiao Hu, and Paraschos Koutris.  Fast join project query evaluation using matrix multiplication.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1213–1223, 2020.
  * [DHK21] Shaleen Deep, Xiao Hu, and Paraschos Koutris.  Enumeration algorithms for conjunctive queries with projection.  In 24th International Conference on Database Theory (ICDT 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [DK18] Shaleen Deep and Paraschos Koutris.  Compressed representations of conjunctive query results.  In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 307–322. ACM, 2018.
  * [DK21] Shaleen Deep and Paraschos Koutris.  Ranked enumeration of conjunctive query results.  To appear in Joint 2021 EDBT/ICDT Conferences, ICDT ’21 Proceedings, 2021.
  * [GGS14] Georg Gottlob, Gianluigi Greco, and Francesco Scarcello.  Treewidth and hypertree width.  Tractability: Practical Approaches to Hard Problems, 1, 2014.
  * [GS13] Gianluigi Greco and Francesco Scarcello.  Structural tractability of enumerating csp solutions.  Constraints, 18(1):38–74, 2013.
  * [GU18] François Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029–1046. SIAM, 2018.
  * [HUA75] John E Hopcroft, Jeffrey D Ullman, and AV Aho.  The design and analysis of computer algorithms, 1975.
  * [Kaz13] Wojciech Kazana.  Query evaluation with constant delay.  PhD thesis, 2013.
  * [KNN+19] Ahmet Kara, Hung Q Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang.  Counting triangles under updates in worst-case optimal time.  In 22nd International Conference on Database Theory, 2019.
  * [KNOZ20] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang.  Trade-offs in static and dynamic evaluation of hierarchical queries.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 375–392, 2020.
  * [NPRR12] Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms.  In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 37–48. ACM, 2012.
  * [NRR13] Hung Q. Ngo, Christopher Ré, and Atri Rudra.  Skew strikes back: new developments in the theory of join algorithms.  SIGMOD Record, 42(4):5–16, 2013.
  * [OS16] Dan Olteanu and Maximilian Schleich.  Factorized databases.  ACM SIGMOD Record, 45(2):5–16, 2016.
  * [OVL81] Mark H Overmars and Jan Van Leeuwen.  Dynamization of decomposable searching problems yielding good worst-case bounds.  In Theoretical Computer Science, pages 224–233. Springer, 1981\.
  * [OZ15] Dan Olteanu and Jakub Závodnỳ.  Size bounds for factorised representations of query results.  ACM Transactions on Database Systems (TODS), 40(1):1–44, 2015.
  * [PP06] Anna Pagh and Rasmus Pagh.  Scalable computation of acyclic joins.  In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 225–232, 2006.
  * [RCWH+20] Amrita Roy Chowdhury, Chenghong Wang, Xi He, Ashwin Machanavajjhala, and Somesh Jha.  Crypt?: Crypto-assisted differential privacy on untrusted servers.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 603–619, 2020.
  * [Seg15a] Luc Segoufin.  Constant delay enumeration for conjunctive queries.  SIGMOD Record, 44(1):10–17, 2015.
  * [Seg15b] Luc Segoufin.  Constant delay enumeration for conjunctive queries.  ACM SIGMOD Record, 44(1):10–17, 2015.
  * [SORK11] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch.  Probabilistic databases, synthesis lectures on data management.  Morgan & Claypool, 2011.
  * [XD17] Konstantinos Xirogiannopoulos and Amol Deshpande.  Extracting and analyzing hidden graphs from relational databases.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 897–912. ACM, 2017.
  * [XKD15] Konstantinos Xirogiannopoulos, Udayan Khurana, and Amol Deshpande.  Graphgen: Exploring interesting graphs in relational data.  Proceedings of the VLDB Endowment, 8(12):2032–2035, 2015.
  * [XSD17] Konstantinos Xirogiannopoulos, Virinchi Srinivas, and Amol Deshpande.  Graphgen: Adaptive graph processing using relational databases.  In Proceedings of the Fifth International Workshop on Graph Data-management Experiences & Systems, GRADES’17, pages 9:1–9:7, New York, NY, USA, 2017. ACM.
  * [Yan81] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In VLDB, volume 81, pages 82–94, 1981.