MnLargeSymbols’164 MnLargeSymbols’171 Department of Computer Sciences,
University of Wisconsin-Madison, Madison, Wisconsin<EMAIL_ADDRESS>Department of Computer Sciences, Duke University, Durham, North Carolina,
<EMAIL_ADDRESS>Department of Computer Sciences, University of Wisconsin-
Madison, Madison, Wisconsin<EMAIL_ADDRESS>S. Deep, X. Hu and P.
Koutris

# Space-Time Tradeoffs for Answering Boolean Conjunctive Queries

Shaleen Deep  Xiao Hu  Paraschos Koutris

###### Abstract

In this paper, we investigate space-time tradeoffs for answering boolean
conjunctive queries. The goal is to create a data structure in an initial
preprocessing phase and use it for answering (multiple) queries. Previous work
has developed data structures that trade off space usage for answering time
and has proved conditional space lower bounds for queries of practical
interest such as the path and triangle query. However, most of these results
cater to only those queries, lack a comprehensive framework, and are not
generalizable. The isolated treatment of these queries also fails to utilize
the connections with extensive research on related problems within the
database community. The key insight in this work is to exploit the formalism
of relational algebra by casting the problems as answering join queries over a
relational database. Using the notion of boolean adorned queries and access
patterns, we propose a unified framework that captures several widely studied
algorithmic problems. Our main contribution is three-fold. First, we present
an algorithm that recovers existing space-time tradeoffs for several problems.
The algorithm is based on an application of the join size bound to capture the
space usage of our data structure. We combine our data structure with query
decomposition techniques to further improve the tradeoffs and show that it is
readily extensible to queries with negation. Second, we falsify two
conjectures proposed in the existing literature that relates to the space-time
lower bound for path queries and triangle detection by proposing an
unexpectedly better algorithm. This result opens a new avenue for improving
several algorithmic results that have so far been assumed to be
(conditionally) optimal. Finally, we prove new conditional space-time lower
bounds for star and path queries.

##  1 Introduction

Recent work has made remarkable progress in developing data structures and
algorithms for answering set intersection problems [13], reachability oracles
and directed reachability [4, 3, 10], histogram indexing [7, 19], and problems
related to document retrieval [2, 21]. This class of problems splits an
algorithmic task into two phases: the preprocessing phase, which computes a
space-efficient data structure, and the answering phase, which uses the data
structure to answer the requests to minimize the answering time. A fundamental
algorithmic question related to these problems is the tradeoff between the
space $S$ necessary for data structures and the answering time $T$ for
requests.

For example, consider the $2$-Set Disjointness problem: given a universe of
elements $U$ and a collection of $m$ sets $C_{1},\dots,C_{m}\subseteq U$, we
want to create a data structure such that for any pair of integers $1\leq
i,j\leq m$, we can efficiently decide whether $C_{i}\cap C_{j}$ is empty or
not. Previous work [10, 13] has shown that the space-time tradeoff for $2$-Set
Disjointness is captured by the equation $S\cdot T^{2}=N^{2}$, where $N$ is
the total size of all sets. The data structure obtained is conjectured to be
optimal [13], and its optimality was used to develop conditional lower bounds
for other problems, such as approximate distance oracles [4, 3]. Similar
tradeoffs have been independently established for other data structure
problems as well. In the $k$-Reachability problem [13, 9] we are given as an
input a directed graph $G=(V,E)$, an arbitrary pair of vertices $u,v$, and the
goal is to decide whether there exists a path of length $k$ between $u$ and
$v$. In the edge triangle detection problem [13], we are given an input
undirected graph $G=(V,E)$, the goal is to develop a data structure that takes
space $S$ and can answer in time $T$ whether a given edge $e\in E$
participates in a triangle or not. Each of these problems has been studied in
isolation and, as a result, the algorithmic solutions are not generalizable
due to a lack of comprehensive framework.

In this paper, we cast many of the above problems into answering Conjunctive
Queries (CQs) over a relational database. CQs are a powerful class of
relational queries with widespread applications in data analytics and graph
exploration [33, 32, 11]. For example, by using the relation $R(x,y)$ to
encode that element $x$ belongs to set $y$, $2$-Set Disjointness can be
captured by the following CQ: $\varphi(y_{1},y_{2})=\exists_{x}R(x,y_{1})\land
R(x,y_{2})$. As we will see later, $k$-Reachability can also be naturally
captured by a CQ.

The insight of casting data structure problems into CQs over a database allows
for a unified treatment for developing algorithms within the same framework,
which in turn allows for improved algorithms and data structures. In
particular, we can leverage the techniques developed by the data management
community through a long line of research on efficient join evaluation [34,
25, 24], including worst-case optimal join algorithms [24] and tree
decompositions [14, 28]. The use of these techniques has been a subject of
previous work [1, 15, 11, 26, 18, 17] for enumerating query results under
static and dynamic settings. In this paper, we build upon the aforementioned
techniques to develop a framework that allows us to obtain general space-time
tradeoffs for any Boolean CQ (a Boolean CQ is one that outputs only true or
false). As a consequence, we recover state-of-the-art tradeoffs for several
existing problems (e.g., $2$-Set Disjointness as well as its generalization
$k$-Set Disjointness and $k$-Reachability) as special cases of the general
tradeoff. We can even obtain improved tradeoffs for some specific problems,
such as edge triangles detection, thus falsifying existing conjectures.

Our Contribution. We summarize our main technical contributions below.

  1. 1.

A Comprehensive Framework. We propose a unified framework that captures
several widely-studied data structure problems. More specifically, we resort
to the formalism of CQs and the notion of Boolean adorned queries, where the
values of some variables in the query are fixed by the user (denoted as an
access pattern), and aim to evaluate the Boolean query. We then show how this
framework captures the $2$-Set Disjointness and $k$-Reachability problems. Our
first main result (Theorem 4.2) is an algorithm that builds a data structure
to answer any Boolean CQ under a specific access pattern. Importantly, the
data structure can be tuned to trade off space for answering time, thus
capturing the full continuum between optimal space and answering time. At one
extreme, the data structure achieves constant answering time by explicitly
storing all possible answers. At the other extreme, the data structure stores
nothing, but we execute each request from scratch. We show how to recover
existing and new tradeoffs using this general framework. The first main result
may sometimes lead to suboptimal tradeoffs since it does not take into account
the structural properties of the query. Our second main result (Theorem 4.8)
combines tree decompositions of the query structure with access patterns to
improve space efficiency. We then show how this algorithm can handle Boolean
CQs with negation.

  2. 2.

Improved Algorithms. In addition to the main result above, we explicitly
improve the best-known space-time tradeoff for the $k$-Reachability problem
for $k\geq 4$. For any $k\geq 2$, the tradeoff of $S\cdot
T^{2/(k-1)}=O(|E|^{2})$ was conjectured to be optimal by [13], where $|E|$ is
the number of edges in the graph, and was used to conditionally prove other
lower bounds on space-time tradeoffs. We show that for a regime of answer time
$T$, it can be improved to $S\cdot T^{2/(k-2)}=O(|E|^{2})$, thus breaking the
conjecture. To the best of our knowledge, this is the first non-trivial
improvement for the $k$-Reachability problem. We also refute a lower bound
conjecture for the edge triangles detection problem established by [13].

  3. 3.

Conditional Lower Bounds. Finally, we show a reduction between lower bounds
for the problem of $k$-Set Disjointness for different values of $k$, which
generalizes the $2$-Set Disjointness to computing the intersection between $k$
given sets, for $k\geq 2$.

Organization. We introduce the basic terminology and problem definition in
Section 2 and Section 3. We presents our main results for Boolean adorned
queries in Section 4 and our improved result for path queries in Section 5. We
discuss the lower bounds and related work in Section 6 and Section 7, and
finally conclude in Section 8 with promising future research directions and
open problems.

##  2 Preliminaries

In this section we present the basic notation and terminology.

Data Model. A schema $\mathbf{x}=(x_{1},\dots,x_{n})$ is a non-empty ordered
set of distinct variables. Each variable $x_{i}$ has a discrete domain
$\mathbf{dom}(x_{i})$. A tuple $t$ over schema $\mathbf{x}$ is an element from
$\mathbf{dom}(\mathbf{x})=\mathbf{dom}(x_{1})\times\dots\times\mathbf{dom}(x_{n})$.
A relation $R$ over schema $\mathbf{x}$ (denoted $R(\mathbf{x})$) is a
function $R:\mathbf{dom}(\mathbf{x})\rightarrow\mathbb{Z}$ such that the
multiplicity $R(t)$ is non-zero for finitely many $t$. A tuple $t$ exists in
$R$, denoted by $t\in R$, if $R(t)>0$. The size of relation $R$, denoted as
$|R|$, is the size of set $\\{{t}\mid{t\in R}\\}$. A database $D$ is a set of
relations and the size of the database $|D|$ is the sum of sizes of all its
relations. Given a tuple $t$ over schema $\mathbf{x}$ and a set of variables
$\mathbf{s}\subseteq\mathbf{x}$, $t[\mathbf{s}]$ denotes the restriction of
$t$ to $\mathbf{s}$ and the values of $t[\mathbf{s}]$ follows the same
variable ordering as $\mathbf{s}$. We also define the selection operator
$\sigma_{\mathbf{s}=t}(R)=\\{{u\in R}\mid{u[\mathbf{s}]=t}\\}$ and projection
operator $\pi_{\mathbf{s}}(R)=\\{{u[\mathbf{s}]}\mid{u\in R}\\}$.

Conjunctive Queries. A Conjunctive Query (CQ) is an expression of the form

$\varphi(\mathbf{y})=\exists_{\mathbf{z}}R_{1}(\mathbf{x}_{1})\land
R_{2}(\mathbf{x}_{2})\land\ldots\land R_{n}(\mathbf{x}_{n}).$

Expressions
$\varphi(\mathbf{y}),R_{1}(\mathbf{x}_{1}),R_{2}(\mathbf{x}_{2}),\ldots,R_{n}(\mathbf{x}_{n})$
are called atoms or relations. The atom $\varphi(\mathbf{y})$ is the head of
the query, while the atoms $R_{i}(\mathbf{x}_{i})$ form the body. Here
$\textsf{vars}(\varphi)$ is the set of all variables occurring in $\varphi$,
i.e, $\mathbf{y}\cup\mathbf{z}\cup\mathbf{x}_{1}\cup\dots\cup\mathbf{x}_{n}$.
The existential quantified variables $\mathbf{z}$ is the set of variables
$\textsf{vars}(\varphi)\setminus\mathbf{y}$. Throughout the paper, we will
omit the existential quantified part whenever $\mathbf{y}$ and
$\mathbf{x}_{i}$ are mentioned in the query. A CQ is full if every variable in
the body appears also in the head (a.k.a. quantifier-free), and Boolean if the
head contains no variables, i.e. it is of the form $\varphi()$ (a.k.a. fully-
quantified). We will typically use the symbols $x,y,z,\dots$ to denote
variables, and $a,b,c,\dots$ to denote constants. Given an input database $D$,
we use $\varphi(D)$ to denote the result of the query $\varphi$ over the
database. In this paper, we will consider CQs that have no constants and no
repeated variables in the same atom. Such a query can be represented
equivalently as a hypergraph
$\mathcal{H}_{\varphi}=(\mathcal{V}_{\varphi},\mathcal{E}_{\varphi})$, where
$\mathcal{V}_{\varphi}$ is the set of variables, and for each hyperedge
$F\in\mathcal{E}_{\varphi}$ there exists a relation $R_{F}$ with variables
$F$.

######  Example 2.1.

Suppose that we have a directed graph $G$ that is represented through a binary
relation $R(x,y)$: this means that there exists an edge from node $x$ to node
$y$. We can compute the pairs of nodes that are connected by a directed path
of length $k$ using the following CQ, which we call a path query:
$P_{k}(x_{1},x_{k+1})=R(x_{1},x_{2})\land R(x_{2},x_{3})\land\dots\land
R(x_{k},x_{k+1}).$

A CQ with negation, denoted as $CQ^{\neg}$, is a CQ where some of the atoms
can be negative, i.e., $\neg R_{i}(\mathbf{x}_{i})$ is allowed. For
$\varphi\in CQ^{\neg}$, we denote by $\varphi^{+}$ the conjunction of the
positive atoms in $\varphi$. A $CQ^{\neg}$ is said to be _safe_ if every
variable appears in at least some positive atom. In this paper, we restrict
our scope to class of safe $CQ^{\neg}$, a standard assumption [31, 23]
ensuring that query results are well-defined and do not depend on domains.

Join Size Bounds. Let $\mathcal{H}=(\mathcal{V},\mathcal{E})$ be a hypergraph.
A weight assignment $\mathbf{u}=(u_{F})_{F\in\mathcal{E}}$ is called a
fractional edge cover of $S\subseteq\mathcal{V}$ 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})$. In a celebrated
result, Atserias, Grohe and Marx [5] proved that for every fractional edge
cover $\mathbf{u}$ of $\mathcal{V}$, the size of join result is bounded by the
AGM inequality:

$|\Join_{F\in\mathcal{E}}R_{F}|\leq\prod_{F\in\mathcal{E}}|R_{F}|^{u_{F}}$

The above bound is constructive [25, 24]: there exists an algorithm that
computes the result of $\Join_{F\in\mathcal{E}}R_{F}$ in
$O(\prod_{F\in\mathcal{E}}|R_{F}|^{u_{F}})$ time for every fractional edge
cover $\mathbf{u}$ of $\mathcal{V}$.

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

  * •

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

  * •

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

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

Computational Model. To measure the running time of our algorithms, we will
use the uniform-cost RAM model [16], where data values and 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. Each
relation $R$ over schema $\mathbf{x}$ is implemented via a data structure that
stores all entries $t\in R$ in $O(|R|)$ space, which supports look-up,
insertion, and deletion entries in $O(1)$ time. For a schema
$\mathbf{s}\subseteq\mathbf{x}$, we use an index structure that for some $t$
defined over $\mathbf{s}$ can (i) check if $t\in\pi_{\mathbf{s}}(R)$; and
$(ii)$ return $|\sigma_{\mathbf{s}=t}(R)|$ in constant time.

##  3 Framework

In this section, we discuss the concept of adorned queries and present our
framework.

###  3.1 Adorned Queries

In order to model different access patterns, we will use the concept of
adorned queries introduced by [30]. In an adorned query, each variable in the
head of the query is associated with a binding type, which can be either bound
($\mathsf{b}$) or free ($\mathsf{f}$). We denote this as
$\varphi^{\eta}(x_{1},\dots,x_{k})$, where
$\eta\in\\{\mathsf{b},\mathsf{f}\\}^{k}$ is called the access pattern. The
access pattern tells us for which variables the user must provide a value as
input. Concretely, let $x_{1},x_{2},\dots,x_{\ell}$ be the bound variables. An
instantiation of the bound variables to constants, such as $\\{x_{i}\leftarrow
a_{i}:i\in\\{1,2,\cdots,\ell\\}\\}$, is an access request: we need to return
the query results where we have replaced each bound variable $x_{i}$ with the
corresponding constant $a_{i}$. In the next few examples, we demonstrate how
to capture several data structure problems by adorned queries.

######  Example 3.1 (Set Disjointness and Set Intersection).

In the set disjointness problem, we are given $m$ sets $S_{1},\dots,S_{m}$
drawn from the same universe $U$. Let $N=\sum_{i=1}^{m}|S_{i}|$ be the total
size of input sets. Each access request is a pair of indexes $(i,j),1\leq
i,j,\leq m$, for which we need to decide whether $S_{i}\cap S_{j}$ is empty or
not. To cast this problem as an adorned query, we encode the family of sets as
a binary relation $R(x,y)$, such that element $x$ belongs to set $y$. Note
that the relation will have size $N$. Then, the set disjointness problem
corresponds to:

$\varphi^{\mathsf{b}\mathsf{b}}(y,z)=R(x,y)\land R(x,z).$

An access request in this case specifies two sets $y=S_{i},z=S_{j}$, and
issues the (Boolean) query $\varphi()=R(x,S_{i})\land R(x,S_{j})$.

In the related set intersection problem, given a pair of indexes $(i,j)$ for
$1\leq i,j,\leq m$, we instead want to enumerate the elements in the
intersection $S_{i}\cap S_{j}$, which can be captured by the following adorned
query: $\varphi^{\mathsf{b}\mathsf{b}\mathsf{f}}(y,z,x)=R(x,y)\land R(x,z)$.

######  Example 3.2 ($k$-Set Disjointness).

The $k$-set disjointness problem is a generalization of 2-set disjointness
problem, where each request asks whether the intersection between $k$ sets is
empty or not. Again, we can cast this problem into the following adorned
query:

$\varphi^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{k})=R(x,y_{1})\land
R(x,y_{2})\land\dots\land R(x,y_{k})$

######  Example 3.3 ($k$-Reachability).

Given a direct graph $G$ , the $k$-reachability problem asks, given a pair
vertices $(u,v)$, to check whether they are connected by a path of length $k$.
Representing the graph as a binary relation $S(x,y)$ (which means that there
is an edge from $x$ to $y$), we can model this problem through the following
adorned query:

$\varphi^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})=S(x_{1},x_{2})\land
S(x_{2},x_{3})\land\dots\land S(x_{k},x_{k+1})$

Observe that we can also check whether there is a path of length at most $k$
by combining the results of $k$ such queries (one for each length
$1,\dots,k$).

######  Example 3.4 (Edge Triangles Detection).

Given a graph $G=(V,E)$, this problem asks, given an edge $(u,v)$ as the
request, whether $(u,v)$ participates in a triangle or not. This task can be
expressed as the following adorned query

$\varphi^{\mathsf{b}\mathsf{b}}_{\triangle}(x,z)=R(x,y)\land R(y,z)\land
R(x,z)$

In the reporting version, the goal is to enumerate all triangles participated
by edge $(x,z)$, which can also be expressed by the following adorned query
$\varphi^{\mathsf{b}\mathsf{b}\mathsf{f}}_{\triangle}(x,z,y)=R(x,y)\land
R(y,z)\land R(x,z)$.

We say that an adorned query is Boolean if every head variable is bound. In
this case, the answer for every access request is also Boolean, i.e., true or
false.

###  3.2 Problem Statement

Given an adorned query $\varphi^{\eta}$ and an input database $D$, our goal is
to construct a data structure, such that we can answer any access request that
conforms to the access pattern $\eta$ as fast as possible. In other words, an
algorithm can be split into two phases:

  * •

Preprocessing phase: we computes a data structure using space $S$.

  * •

Answering phase: given an access request, we compute the answer using the data
structure built in the preprocessing phase, within time $T$.

In this work, our goal is to study the relationship between the space of the
data structure $S$ and the answering time $T$ for a given adorned query
$\varphi^{\eta}$. We will focus on Boolean adorned queries, where the output
is just true or false.

##  4 General Space-Time Tradeoffs

###  4.1 Space-Time Tradeoffs via Worst-case Optimal Algorithms

Let $\varphi^{\eta}$ be an adorned query, and let
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ be the corresponding hypergraph. Let
$\mathcal{V}_{\mathsf{b}}$ denote the bound variables in the head of the
query. For any fractional edge cover $\mathbf{u}$ of $\mathcal{V}$, we define
the slack of $\mathbf{u}$ as:
$\alpha(\mathbf{u}):=\min_{x\in\mathcal{V}\setminus\mathcal{V}_{\mathsf{b}}}\left(\sum_{F:x\in
F}u_{F}\right).$ In other words, the slack is the maximum factor by which we
can scale down the fractional cover $\mathbf{u}$ so that it remains a valid
edge cover of the non-bound variables in the query111We will omit the
parameter $\mathbf{u}$ from the notation of $\alpha$ whenever it is clear from
the context.. Hence $\\{u_{F}/\alpha(\mathbf{u})\\}_{F\in\mathcal{E}}$ is a
fractional cover of the nodes in
$S=\mathcal{V}\setminus\mathcal{V}_{\mathsf{b}}$. We always have
$\alpha(\mathbf{u})\geq 1$.

######  Example 4.1.

Consider
$\varphi^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{k})=R_{1}(x,y_{1})\land
R_{2}(x,y_{2})\land\dots R_{k}(x,y_{k})$ with the optimal fractional edge
cover $\mathbf{u}$, where $u_{i}=1$ for $i\in\\{1,\dots,k\\}$. The slack is
$\alpha(\mathbf{u})=k$, since the fractional edge cover $\hat{\mathbf{u}}$,
where $\hat{u}_{i}=u_{i}/k=1/k$ covers the only non-bound variable $x$.

We can now state our first main theorem.

######  Theorem 4.2.

Let $\varphi^{\eta}$ be a Boolean adorned query with hypergraph
$(\mathcal{V},\mathcal{E})$. Let $\mathbf{u}$ be any fractional edge cover of
$\mathcal{V}$. Then, for any input database $D$, we can construct a data
structure that answers any access request in time $O(T)$ and takes space

$S={O}\left(|D|+\prod_{F\in\mathcal{E}}|R_{F}|^{u_{F}}/T^{\alpha}\right)$

We should note that Theorem 4.2 applies when the relation sizes are different;
this gives us sharper upper bounds compared to the case where each relation is
bounded by the total size of the input. Indeed, if using $|D|$ as an upper
bound on each relation, we obtain a space requirement of
$O(|D|^{\rho^{*}}/T^{\alpha})$ for achieving answering time $O(T)$, where
$\rho^{*}$ is the fractional edge cover number. Since $\alpha\geq 1$, this
gives us at worst a linear tradeoff between space and time, i.e., $S\cdot
T=O(|D|^{\rho^{*}})$. For cases where $\alpha\geq 1$, we can obtain much
better tradeoff.

######  Example 4.3.

Continue the example in this section
$\varphi^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{k})=R_{1}(x,y_{1})\land
R_{2}(x,y_{2})\land\dots\land R_{k}(x,y_{k})$. We obtain an improved tradeoff:
$S\cdot T^{k}=O(|D|^{k})$. Note that this result matches the best-known space-
time tradeoff for the $k$-Set Disjointness problem [13]. (Note that all atoms
use the same relation symbol $R$, so $|R_{i}|=|D|$ for every $i=1,\dots,k$. )

We next present a few more applications of Theorem 4.2.

######  Example 4.4 (Edge Triangles Detection).

For the Boolean version, it was shown in [13] that – conditioned on the strong
set disjointness conjecture – any data structure that achieves answering time
$T$ needs space $S=\Omega(|E|^{2}/T^{2})$. A matching upper bound can be
constructed by using a fractional edge cover $\mathbf{u}(R,S,T)=(1,1,0)$ with
slack $\alpha=2$. Thus, Theorem 4.2 can be applied to achieve answering time
$T$ using space $S=O(|E|^{2}/T^{2})$. Careful inspection reveals that a
different fractional edge cover $\mathbf{u}(R,S,T)=(1/2,1/2,1/2)$ with slack
$\alpha=1$, achieves a better tradeoff. Thus, Theorem 4.2 can be applied to
obtain the following corollary.

######  Corollary 4.5.

For a graph $G=(V,E)$, there exists a data structure of size
$S=O(|E|^{3/2}/T)$ that can answer the edge triangles detection problem in
$O(T)$ time.

The data structure implied by Theorem 4.2 is always better when
$T\leq\sqrt{|E|}$ 222All answering times $T>\sqrt{|E|}$ are trivial to achieve
using linear space by using the data structure for $T^{\prime}=\sqrt{E}$ and
holding the result back until time $T$ has passed. However, in certain
practical settings such as transmitting data structure over a network, it is
beneficial to construct a sublinear sized structures. In those settings,
$T>\sqrt{|E|}$ is useful., thus refuting the conditional lower bound in [13].
We should note that this does not imply that the strong set disjointness
conjecture is false, as we have observed an error in the reduction used by
[13].

######  Example 4.6 (Square Detection).

Beyond triangles, we consider the edge square detection problem, which checks
whether a given edge belongs in a square pattern in a graph $G=(V,E)$,
$\varphi^{\mathsf{b}\mathsf{b}}_{\square}(x_{1},x_{2})=R_{1}(x_{1},x_{2})\land
R_{2}(x_{2},x_{3})\land R_{3}(x_{3},x_{4})\land R_{4}(x_{4},x_{1}).$ Using the
fractional edge cover $\mathbf{u}=(1/2,1/2,1/2,1/2)$ with slack $\alpha=1$, we
obtain a tradeoff $S=O(|E|^{2}/T)$.

###  4.2 Space-Time Tradeoffs via Tree Decompositions

Theorem 4.2 does not always give us the optimal tradeoff. For the
$k$-reachability problem with the adorned query
$\varphi^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})=R_{1}(x_{1},x_{2})\land\dots\land
R_{k}(x_{k},x_{k+1})$, Theorem 4.2 gives a tradeoff $S\cdot
T=|D|^{\lceil(k+1)/2\rceil}$, by taking the optimal fractional edge covering
number $\rho^{*}=\lceil(k+1)/2\rceil$ and slack $\alpha=1$, which is far from
efficient. In this section, we will show how to leverage tree decompositions
to further improve the space-time tradeoff in Theorem 4.2.

Again, let $\varphi^{\eta}$ be an adorned query, and let
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ be the corresponding hypergraph. Given
a set of nodes $C\subseteq\mathcal{V}$, a $C$-connex tree decomposition of
$\mathcal{H}$ is a pair $(\mathscr{T},A)$, where $(i)$ $\mathscr{T}$ is a tree
decomposition of $\mathcal{H}$, and $(ii)$ $A$ is a connected subset of the
tree nodes such that the union of their variables is exactly $C$. For our
purposes, we choose $C=\mathcal{V}_{\mathsf{b}}$. Given a
$\mathcal{V}_{\mathsf{b}}$-connex tree decomposition, we orient the tree from
some node in $A$. We then define the bound variables for the bag $t$,
$\mathcal{V}^{t}_{\mathsf{b}}$ as the variables in $\mathscr{B}_{t}$ that also
appear in the bag of some ancestor of $t$. The free variables for the bag $t$
are the remaining variables in the bag,
$\mathcal{V}^{t}_{\mathsf{f}}=\mathscr{B}_{t}\setminus\mathcal{V}^{t}_{\mathsf{b}}$.

######  Example 4.7.

Consider the $5$-path query
$\varphi^{\mathsf{b}\mathsf{b}}(x_{1},x_{6})=R_{1}(x_{1},x_{2})\land\dots\land
R_{5}(x_{5},x_{6})$. Here, $x_{1}$ and $x_{6}$ are the bound variables. Figure
1 shows the unconstrained decomposition as well as the $C$-connex
decomposition for $\varphi^{\mathsf{b}\mathsf{b}}(x_{1},x_{6})$, where
$C=\\{x_{1},x_{6}\\}$. The root bag contains the bound variables
$x_{1},x_{6}$. Bag $\mathcal{B}_{t_{2}}$ contains $x_{1},x_{6}$ as bound
variables and $x_{2},x_{5}$ as the free variables. Bag $\mathcal{B}_{t_{3}}$
contains $x_{2},x_{5}$ as bound variables for $\mathcal{B}_{t_{3}}$ and
$x_{3},x_{4}$ as free variables.

$x_{1},x_{2}$$x_{2},x_{3}$$x_{3},x_{4}$$x_{4},x_{5}$$x_{5},x_{6}$

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x_{1},x_{6}}$$\mathscr{B}_{t_{1}}$${x_{2},x_{5}}\mid{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x_{1},x_{6}}$$\mathscr{B}_{t_{2}}$${x_{3},x_{4}}\mid{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x_{2},x_{5}}$$\mathscr{B}_{t_{3}}$

Figure 1: The hypergraph $\mathcal{H}$ for a length-5 path query, along with
two tree decompositions: the left is unconstrained, and the right is a
$C$-connex one with $C=\\{x_{1},x_{6}\\}$. Bound variables are colored red.
Nodes in $A$ are colored grey.

Next, we define a parameterized notion of width for the
$\mathcal{V}_{\mathsf{b}}$-connex tree decomposition. The width is
parameterized by a function $\delta$ that maps each node $t$ in the tree to a
non-negative number, such that $\delta(t)=0$ whenever $t\in A$. The intuition
here is that we will spend $O(|D|^{\delta(t)})$ in the node $t$ while
answering the access request. The parameterized width of a bag
$\mathscr{B}_{t}$ is now defined as:
$\rho_{t}(\delta)=\min_{\mathbf{u}}\left(\sum_{F}u_{F}-\delta(t)\cdot\alpha\right)$
where $\mathbf{u}$ is a fractional edge cover of the bag $\mathscr{B}_{t}$,
and $\alpha$ is the slack (on the bound variables of the bag). The
$\delta$-width of the decomposition is then defined as $\max_{t\notin
A}\rho_{t}(\delta)$. Finally, we define the $\delta$-height as the maximum-
weight path from the root to any leaf, where the weight of a path $P$ is
$\sum_{t\in P}\delta(t)$. We now have all the necessary machinery to state our
second main theorem.

######  Theorem 4.8.

Let $\varphi^{\eta}$ be a Boolean adorned query with hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E})$. Consider any
$\mathcal{V}_{\mathsf{b}}$-connex tree decomposition of $\mathcal{H}$. For
some parametrization $\delta$ of the decomposition, let $f$ be its
$\delta$-width, and $h$ be its $\delta$-height. Then, for any input database
$D$, we can construct a data structure that answers any access request in time
$T=O(|D|^{h})$ in space $S=O(|D|+|D|^{f})$.

The function $\delta$ allows us to trade off between time and space. If
setting $\delta(t)=0$ for every node $t$ in the tree, then the $\delta$-height
becomes $O(1)$, while the $\delta$-width equals to the fractional hypetree
width of the decomposition. As we increase the values of $\delta$ in each bag,
the $\delta$-height increases while the $\delta$-width decreases, i.e., the
answer time $T$ increases while the space decreases. Additionally, we note
that the tradeoff from Theorem 4.8 is at least as good as the one from Theorem
4.2. Indeed, we can always construct a tree decomposition where all variables
reside in a single node of the tree. In this case, we recover exactly the
tradeoff from Theorem 4.2. Due to a lack of space, we refer the reader to
Appendix B for details.

######  Example 4.9.

We continue with the $5$-path query. Since
$\mathscr{B}_{t_{1}}=\\{x_{1},x_{6}\\}\in A$, we assign $\delta(t_{1})=0$. For
$\mathscr{B}_{t_{2}}=\\{x_{1},x_{2},x_{5},x_{6}\\}$, the only valid fractional
edge cover assigns weight 1 to both $R_{1},R_{5}$ and has slack 1. Hence, if
we assign $\delta(t_{2})=\tau$ for some parameter $\tau$, the width is
$2-\tau$. For $\mathscr{B}_{t_{3}}=\\{x_{2},x_{3},x_{4},x_{5}\\}$, the only
fractional cover also assigns weight 1 to both $R_{2},R_{4}$, with slack $1$
again. Assigning $\delta(t_{3})=\tau$, the width becomes $2-\tau$ for $t_{3}$
as well. Hence, the $\delta$-width of the tree decomposition is $2-\tau$,
while the $\delta$-height is $2\tau$. Plugging this to Theorem 4.8, it gives
us a tradeoff with answering time $T=O(|E|^{2\tau})$ and space usage
$S=O(|E|+|E|^{2-\tau})$, which matches the state-of-the-art result in [13].
The above argument can be generalized to $k$-path query with answering time
$T=O(|E|^{(k-1)/2\tau})$ and space usage $S=O(|E|+|E|^{2-\tau})$.

######  Example 4.10.

Consider a variant of the square detection problem: given two vertice, the
goal is to decide whether they occur in two opposites corners of a square,
which can be captured by the following adorned query:

$\varphi^{\mathsf{b}\mathsf{b}}(x_{1},x_{3})=R_{1}(x_{1},x_{2})\land
R_{1}(x_{2},x_{3})\land R_{3}(x_{3},x_{4})\land R_{4}(x_{4},x_{1}).$

Theorem 4.2 gives a tradeoff with answering time $O(T)$ and space
$O(|E|^{2}/T)$. But we can obtain a better tradeoff using Theorem 4.8. Indeed,
consider the tree decomposition where we have a root bag $t_{1}$ with
$\mathscr{B}_{t_{1}}=\\{x_{1},x_{3}\\}$, and two children of $t_{1}$ with
Boolean $\mathscr{B}_{t_{2}}=\\{x_{1},x_{2},x_{3}\\}$ and
$\mathscr{B}_{t_{3}}=\\{x_{1},x_{3},x_{4}\\}$. For $\mathscr{B}_{t_{2}}$, we
can see that if assigning a weight of $1$ to both hyperedges, we get a slack
of $2$. Hence, if $\delta(t_{2})=\tau$, the $\delta$-width is $2-2\tau$.
Similarly for $t_{3}$, we assign $\delta(t_{3})=\tau$, for a $\delta$-width
with $2-2\tau$. Applying Theorem 4.8, we obtain a tradeoff with time
$T=O(\tau)$ (since both root-leaf paths have only one node), and space
$S=O(|E|+|E|^{2-2\tau})$. So the space usage can be improved from
$O(|E|^{2}/T)$ to $O(|E|^{2}/T^{2})$.

###  4.3 Extension to CQs with Negation

$\displaystyle\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{x_{1},x_{6}}$$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\
x_{2},\ x_{3},\ x_{4},\ x_{5}\
|}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\hskip
6.00006ptx_{1},x_{6}}$$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}|}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\hskip
6.00006ptx_{2},x_{3}}$$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}|}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\hskip
6.00006ptx_{4},x_{5}}$ Figure 2: $C$-connex decomposition for Example 4.11.

In this section, we present a simple but powerful extension of our result to
adorned Boolean CQs with negation. Given a query $\varphi\in CQ^{\neg}$, we
build the data structure from Theorem 4.8 for $\varphi^{+}$ but impose two
constraints on the decomposition: $(i)$ no leaf node(s) contains any free
variable, $(ii)$ for every negated relation $R^{-}$, all variables of $R^{-}$
must appear together as bound variables in some leaf node(s). In other words,
there exists a leaf node such that $\textsf{vars}(R^{-})$ are present in it.
It is easy to see that such a decomposition always exists. Indeed, we can fix
the root bag to be $C=\mathcal{V}_{\mathsf{b}}$, its child bag with free
variables as $\textsf{vars}(\varphi^{+})\setminus C$ and bound variables as
$C$, and the leaf bag, which is connected to the child of the root, with bound
variables as $\textsf{vars}(\varphi^{-})$ without free variables. Observe that
the bag containing $\textsf{vars}(\varphi^{+})$ free variables can be covered
by only using the positive atoms since $\varphi$ is safe. The intuition is the
following: during the query answering phase, we wish to find the join result
over all variables $\mathcal{V}_{\mathsf{f}}$ before reaching the leaf nodes;
and then, we can check whether there the tuples satisfy the negated atoms or
not, in $O(1)$ time. The next example shows the application of the algorithm
to adorned path queries containing negation.

######  Example 4.11.

Consider the query
$Q^{\mathsf{b}\mathsf{b}}(x_{1},x_{6})=R(x_{1},x_{2})\land\neg
S(x_{2},x_{3})\land T(x_{3},x_{4})\land\neg U(x_{4},x_{5})\land$
$V(x_{5},x_{6})$. Using the decomposition in Figure 2, we can now apply
Theorem 4.8 to obtain the tradeoff $S=O(|D|^{3}/\tau)$ and $T=O(\tau)$. Both
leaf nodes only require linear space since a single atom covers the variables.
Given an access request $x_{1}\leftarrow a,x_{6}\leftarrow b$, we check
whether the answer for this request has been materialized or not. If not, we
proceed to the query answering phase and find at most $O(\tau)$ answers after
evaluating the join in the middle bag. For each of these answers, we can now
check in constant time whether the tuples formed by values for $x_{2},x_{3}$
and $x_{4},x_{5}$ are not present in relations $S$ and $U$ respectively.

For adorned queries where
$\mathcal{V}_{\mathsf{b}}\subseteq\textsf{vars}(\varphi^{-})$, we can further
simplify the algorithm. In this case, we no longer need to create a
constrained decomposition since the check to see if the negated relations are
satisfied or not can be done in constant time at the root bag itself. Thus, we
can directly build the data structure from Theorem 4.8 using the query
$\varphi^{+}$.

######  Example 4.12 (Open Triangle Detection).

Consider the query
$\varphi^{\mathsf{b}\mathsf{b}}(x_{2},x_{3})=R_{1}(x_{1},x_{2})\land\neg
R_{2}(x_{2},x_{3})\land R_{3}(x_{1},x_{3})$, where $\varphi^{-}$ is $\neg
R_{2}(x_{2},x_{3})$ and $\varphi^{+}$ is $R_{1}(x_{1},x_{2})\land
R_{3}(x_{1},x_{3})$ with the adorned view as
$\varphi^{+\mathsf{b}\mathsf{b}}(x_{2},x_{3})=R_{1}(x_{1},x_{2})\land
R_{3}(x_{1},x_{3})$. Observe that
$\\{x_{2},x_{3}\\}\subseteq\textsf{vars}(\varphi^{-})$. We apply Theorem 4.8
to obtain the tradeoff $S=O(|E|^{2}/\tau^{2})$ and $T=O(\tau)$ with root bag
$C=\\{x_{2},x_{3}\\}$, its child bag with $\mathcal{V}_{\mathsf{b}}=C$ and
$\mathcal{V}_{\mathsf{f}}=\\{x_{1}\\}$, and the leaf bag to be
$\mathcal{V}_{\mathsf{b}}=C$ and $\mathcal{V}_{\mathsf{f}}=\emptyset$. Given
an access request $x_{2}\leftarrow a,x_{3}\leftarrow b$, we check whether the
answer for this request has been materialized or not. If not, we traverse the
decomposition and evaluating the join to find if there exists a connecting
value for $x_{1}$. For the last bag, we simply check whether $(a,b)$ exists in
$R_{2}$ or not in $O(1)$ time.

A note on optimality. It is easy to see that the algorithm obtained for
Boolean CQs with negation is conditionally optimal assuming the optimality of
Theorem 4.8. Indeed, if all negated relations are empty, the join query is
equivalent to $\varphi^{+}$ and the algorithm now simply applies Theorem 4.8
to $\varphi^{+}$. In example Example 4.12, assuming relation $R_{2}$ is empty,
the query is equivalent to set intersection whose tradeoffs are conjectured to
be optimal.

##  5 Path Queries

In this section, we present an algorithm for the adorned query
$P_{k}^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})=R_{1}(x_{1},x_{2})\land\dots\land
R_{k}(x_{k},x_{k+1})$ that improves upon the conjectured optimal solution.
Before diving into the details, we first state the upper bound on the tradeoff
between space and query time.

######  Theorem 5.1 (due to [13]).

There exists a data structure for solving
$P_{k}^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})$ with space $S$ and answering
time $T$ such that $S\cdot T^{2/(k-1)}=O(|D|^{2})$.

Note that for $k=2$, the problem is equivalent to SetDisjointness with the
space/time tradeoff as $S\cdot T^{2}=O(N^{2})$. [13] also conjectured that the
tradeoff is essentially optimal.

######  Conjecture 5.2 (due to [13]).

Any data structure for $P_{k}^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})$ with
answering time $T$ must use space $S=\tilde{\Omega}(|D|^{2}/T^{2/(k-1)})$.

If $k$ is not a constant, Conjecture 5.2 implies that $\Theta(|D|^{2})$ space
is needed for achieving $O(1)$ answering time. Building upon Conjecture 5.2,
[13] also showed a result on the optimality of approximate distance oracles.
Our results implies that Theorem 5.1 can be improved further, thus refuting
Conjecture 5.2. The first observation is that the tradeoff in Theorem 5.1 is
only useful when $T\leq|D|$. Indeed, we can always answer any boolean path
query in linear time using breadth-first search. Surprisingly, it is also
possible to improve Theorem 5.1 for the regime of small answering time as
well. In what follows, we will show the improvement for paths of length 4; we
will generalize the algorithm for any length in the next section.

###  5.1 Length-4 Path

######  Lemma 5.3.

There exists a parameterized data structure for solving
$P_{4}^{\mathsf{b}\mathsf{b}}(x_{1},x_{5})$ that uses space $S$ and answering
time $T\leq\sqrt{|D|}$ that satisfies the tradeoff $S\cdot T=O(|D|^{2})$.

For $k=4$, Theorem 5.1 gives us the tradeoff $S\cdot T^{2/3}=O(|D|^{2})$ which
is always worse than the tradeoff in Lemma 5.3. We next present our algorithm
in detail.

Preprocessing Phase. Consider
$P_{4}^{\mathsf{b}\mathsf{b}}(x_{1},x_{5})=R(x_{1},x_{2})\land
S(x_{2},x_{3})\land T(x_{3},x_{4})\land U(x_{4},x_{5})$. Let $\Delta$ be a
degree threshold. We say that a constant $a$ is heavy if its frequency on
attribute $x_{3}$ is greater than $\Delta$ in both relations $S$ and $T$;
otherwise, it is light. In other words, $a$ is heavy if
$|\sigma_{x_{3}=a}(S)|>\Delta$ and $|\sigma_{x_{3}=a}(T)|>\Delta$. We
distinguish two cases based on whether a constant for $x_{3}$ is heavy or
light. Let $\mathcal{L}_{\textsf{heavy}}(x_{3})$ denote the unary relation
that contains all heavy values, and $\mathcal{L}_{\textsf{light}}(x_{3})$ the
one that contains all light values. Observe that we can compute both of these
relations in time $O(|D|)$ by simply iterating over the active domain of
variable $x_{3}$ and checking the degree in relations $S$ and $T$. We compute
two views:

$\displaystyle\hskip 100.00015ptV_{1}(x_{1},x_{3})$
$\displaystyle=R(x_{1},x_{2})\land
S(x_{2},x_{3})\land\mathcal{L}_{\textsf{heavy}}(x_{3})$ $\displaystyle\hskip
100.00015ptV_{2}(x_{3},x_{5})$
$\displaystyle=\mathcal{L}_{\textsf{heavy}}(x_{3})\land T(x_{3},x_{4})\land
U(x_{4},x_{5})$

We store the views as a hash index that, given a value of $x_{1}$ (or
$x_{5}$), returns all matching values of $x_{3}$. Both views take space
$O(|D|^{2}/\Delta)$. Indeed, $|\mathcal{L}_{\textsf{heavy}}|\leq|D|/\Delta$.
Since we can construct a fractional edge cover for $V_{1}$ by assigning a
weight of 1 to $R$ and $\mathcal{L}_{\textsf{heavy}}$, this gives us an upper
bound of $|D|\cdot(|D|/\Delta)$ for the query output. The same argument holds
for $V_{2}$. We also compute the following view for light values:
$V_{3}(x_{2},x_{4})=S(x_{2},x_{3})\land\mathcal{L}_{\textsf{light}}(x_{3})\land
T(x_{3},x_{4}).$ This view requires space $O(|D|\cdot\Delta)$, since the
degree of the light constants is at most $\Delta$. We can now rewrite the
original query as
$P_{4}^{\mathsf{b}\mathsf{b}}(x_{1},x_{5})=R(x_{1},x_{2})\land
V_{3}(x_{2},x_{4})\land U(x_{4},x_{5}).$

The rewritten query is a three path query. Hence, we can apply Theorem 4.2 to
create a data structure with answering time $T=O(|D|/\Delta)$ and space
$S=O(|D|^{2}/(|D|/\Delta))=O(|D|\cdot\Delta)$.

Query Answering. Given an access request, we first check whether there exists
a 4-path that goes through some heavy value in
$\mathcal{L}_{\textsf{heavy}}(x_{3})$. This can be done in time
$O(|D|/\Delta)$ using the views $V_{1}$ and $V_{2}$. Indeed, we obtain at most
$O(|D|/\Delta)$ values for $x_{3}$ using the index for $V_{1}$, and
$O(|D|/\Delta)$ values for $x_{3}$ using the index for $V_{3}$. We then
intersect the results in time $O(|D|/\Delta)$ by iterating over the
$O(|D|/\Delta)$ values for $x_{3}$ and checking if the bound values for
$x_{1}$ and $x_{5}$ from a tuple in $V_{1}$ and $V_{2}$ respectively. If we
find no such 4-path, we check for a 4-path that uses a light value for
$x_{3}$. From the data structure we have constructed in the preprocessing
phase, we can do this in time $O(|D|/\Delta)$.

Tradeoff Analysis. From the above, we can compute the answer in time
$T=O(|D|/\Delta)$. From the analysis in the preprocessing phase, the space
needed is $S=O(|D|^{2}/\Delta+|D|\cdot\Delta)$. Thus, whenever
$\Delta\geq\sqrt{|D|}$, the space becomes $S=O(|D|\cdot\Delta)$, completing
our analysis.

###  5.2 General Path Queries

We can now use the algorithm for the 4-path query to improve the space-time
tradeoff for general path queries of length greater than four.

######  Theorem 5.4.

Let $D$ be an input instance. For $k\geq 4$, there is a data structure for
$P_{k}^{\mathsf{b}\mathsf{b}}(x_{1},x_{k+1})$ with space $S=O(|D|\cdot\Delta)$
and answer time $T=O\left((\frac{|D|}{\Delta})^{\frac{k-2}{2}}\right)$ for
$\Delta\geq\sqrt{|D|}$.

######  Proof 5.5.

Fix some $\Delta\geq\sqrt{|D|}$. We construct the data structure for a path of
length $k$ recursively. The base case is when $k=4$, with answer time
$T_{4}=|D|/\Delta$ and space $S_{4}=|D|\cdot\Delta$.

In the recursive step, similar to the previous section, we set
$\sqrt{\frac{|D|}{\Delta}}$ as the degree threshold for any constant that
variables $x_{1}$ and $x_{k+1}$ can take. Let
$\mathcal{L}_{\textsf{heavy}}^{1},\mathcal{L}_{\textsf{heavy}}^{k+1}$ be unary
relations that store the heavy values for $x_{1},x_{k+1}$ respectively. We
compute and store the result of

$V(x_{1},x_{k+1})=\mathcal{L}_{\textsf{heavy}}^{1}(x_{1})\land
R_{1}(x_{1},x_{2})\land\dots\land
R_{k}(x_{k},x_{k+1}),\mathcal{L}_{\textsf{heavy}}^{k+1}(x_{k+1}).$

This view has size bounded by
$\left(|D|\cdot\sqrt{\frac{\Delta}{|D|}}\right)^{2}=|D|\cdot\Delta$. We
consider the following queries:

$V_{1}^{\mathsf{b}\mathsf{b}}(x_{2},x_{k+1})=R_{2}(x_{2},x_{3})\land\dots\land
R_{k}(x_{k},x_{k+1}).$
$V_{2}^{\mathsf{b}\mathsf{b}}(x_{1},x_{k})=R_{1}(x_{1},x_{2})\land\dots\land
R_{k-1}(x_{k-1},x_{k}).$

both of which correspond to the $(k-1)$-path, so we can recursively apply the
data structure here. Let $S_{k},T_{k}$ be the space and time for $k$-path. For
space, we have following observation:

$S_{k}=|D|\cdot\Delta+S_{k-1}$

As $S_{4}=|D|\cdot\Delta$, we obtain $S_{k}=O(|D|\cdot\Delta)$.

Given an access request, we answer it by distinguishing two cases. If
$x_{1},x_{k+1}$ is heavy, we probe the stored view $V(x_{1},x_{k+1})$ in time
$O(1)$. If one of them is light (say w.l.o.g. $x_{1}$), we call recursively
the data structure $V_{1}$ for every one of the $\leq\sqrt{|D|/\Delta}$ values
connected with $x_{1}$. This gives us the following recurrence formula for
answer time:

$T_{k}=(|D|/\Delta)^{1/2}\cdot T_{k-1}$

Solving the recursive formula gives us $T_{k}=(|D|/\Delta)^{(k-2)/2}$.

The space-time tradeoff obtained from Theorem 5.4 is $S\cdot
T^{2/(k-2)}=O(|D|^{2})$, but only for $T\leq|D|^{(k-2)/4}$. To compare it with
the tradeoff of $S\cdot T^{2/(k-1)}=O(|D|^{2})$ obtained from Theorem 5.1, it
is instructive to look at Figures 3(a) and 3(b), which plot the space-time
tradeoffs for $k=4$ and $k=6$ respectively. For $k=4$, we can see that the new
tradeoff is better for $T\leq|D|^{1/2}$. Once $T$ exceeds $|D|^{1/2}$, it is
still better to use the data structure from Theorem 5.4 until Theorem 5.1
takes over. For $k=6$, the switch point also happens at $T=|D|^{1/2}$ but
requires more space. In general, as $k$ grows, the new tradeoff line becomes
flatter and approaches Theorem 5.1.

(a) Tradeoff for $P^{\mathsf{b}\mathsf{b}}_{4}(x_{1},x_{5})$

(b) Tradeoff for $P^{\mathsf{b}\mathsf{b}}_{6}(x_{1},x_{7})$

Figure 3: Space/time tradeoffs for path query of length $k=4,6$. The line in
blue (dashed) shows the tradeoff obtained from Theorem 5.1. The highlighted
portion in brown shows the improved tradeoff using BFS. The red curve is the
new tradeoff obtained using Theorem 5.4. The green portion of the original
curve is still the best possible when Theorem 5.4 is not applicable.

##  6 Lower Bounds

In this section, we study the lower bounds for adorned star and path queries.
We first present conditional lower bounds for the $k$-Set Disjointness problem
using the conditional optimality of $\ell$-Set Disjointness where $\ell<k$.
First, we review the known results from [13] starting with the conjecture for
$k$-Set Disjointness .

######  Conjecture 6.1 (due to [13]).

Any data structure for $k$-Set Disjointness problem that answers queries in
time $T$ must use space $S=\Omega(|D|^{k}/T^{k})$.

Conjecture 6.1 was shown to be conditionally optimal based on conjectured
lower bound for the $(k+1)$-Sum Indexing problem, however, it was subsequently
showed to be false [20], which implies that Conjecture 6.1 is still an open
problem. Conjecture 6.1 can be further generalized to the case when input
relations are of unequal sizes as follows.

######  Conjecture 6.2.

Any data structure for
$\varphi_{*}^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{k})=R_{1}(x,y_{1})\land\dots\land
R_{k}(x,y_{k})$ that answers queries in time $T$ must use space
$S=\Omega(\Pi_{i=1}^{k}|R_{i}|/T^{k})$.

We now state the main result for star queries.

######  Theorem 6.3.

Suppose that any data structure for
$\varphi_{*}^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{k})$ with answering
time $T$ must use space $S=\Omega(\Pi_{i=1}^{k}|R_{i}|/T^{k})$. Then, any data
structure for $Q_{*}^{\mathsf{b}\dots\mathsf{b}}(y_{1},\dots,y_{\ell})$ with
answering time $T$ must use space
$S=\Omega(\Pi_{i=1}^{\ell}|R_{i}|/T^{\ell})$, for $2\leq\ell<k$.

######  Proof 6.4.

Let $\Delta=T$ be the degree threshold for the $k$ bound variables
$y_{1},\dots y_{k}$. If any of the $k$ variables is light (i.e
$|\sigma_{y_{i}=a[y_{i}]}R_{i}(y_{i},x)|\leq\Delta$), then we can check
whether the intersection between $k$ sets is empty or not in time $O(T)$ by
indexing all relations in a linear time preprocessing phase. The remaining
case is when all $k$ variables are heavy. We now create $\ell$ views
$V_{1},\dots V_{\ell}$ by arbitrarily partitioning the $k$ relations into the
$\ell$ views followed by materializing the join of all relations in each view.
Let view $V_{i}$ contain the join of $k_{i}$ relations. Then,
$|V_{i}|=O((\Pi_{R\in J_{i}}|R|/T^{{k_{i}}-1}))$ where $J_{i}$ is the set of
all relations assigned to view $V_{i}$.

We have now reduced the $k$-star query where all $k$ variables are heavy into
an instance of $\ell$-star query where the input relations are
$V_{1},\dots,V_{\ell}$. Suppose that there exists a data structure that can
answer queries in time $T$ using space
$S=o(\Pi_{i=1}^{\ell}|V_{i}|/T^{\ell})$. Then, we can use such a data
structure for answering the original query where all variables are heavy. The
space used by this oracle is

$\displaystyle\hskip 80.00012ptS$
$\displaystyle=o(\Pi_{i=1}^{\ell}|V_{i}|/T^{\ell})=o((\Pi_{i=1}^{\ell}\Pi_{R\in
J_{i}}|R|/T^{{k_{i}}-1})\cdot(1/T^{\ell}))$
$\displaystyle=o((\Pi_{i=1}^{k}|R_{i}|/T^{k-\ell})\cdot(1/T^{\ell}))=o(\Pi_{i=1}^{k}|R_{i}|/T^{k})$

which contradicts the space lower bound for $k$-star.

Theorem 6.3 creates a hierarchy for $k$-Set Disjointness , where the
optimality of smaller set disjointness instances depends on larger set
disjointness instances. Next, we show conditional lower bounds on the space
requirement of path queries. We begin by proving a simple result for
optimality of $P^{\mathsf{b}\mathsf{b}}_{2}$ (equivalent to $2$-Set
Disjointness) assuming the optimality of $P^{\mathsf{b}\mathsf{b}}_{3}$ query.

######  Theorem 6.5.

Suppose that any data structure for $P^{\mathsf{b}\mathsf{b}}_{3}$ that
answers queries in time $T$, uses space $S$ such that $S\cdot
T=\Omega(|D|^{2})$. Then, for $P^{\mathsf{b}\mathsf{b}}_{2}$ , it must be the
case that any data structure that uses space $S=O(|D|^{2}/T^{2})$, the
answering time is $\Omega(T)$.

######  Proof 6.6.

Let $\Delta=T$ be the degree threshold for all vertices. If both bound
variables in $P^{\mathsf{b}\mathsf{b}}_{3}$ are heavy, then we can answer the
query in constant time using space $\Theta(|D|^{2}/T^{2})$ by materializing
the answers to all heavy-heavy queries. In the remaining cases, at least one
of the bound valuations is light. Without loss of generality, suppose $x_{1}$
is light. Then, we can make $\Delta$ calls to the oracle for query
$P^{\mathsf{b}\mathsf{b}}_{2}(x_{2},x_{4})=R_{2}(x_{2},x_{3}),R_{3}(x_{3},x_{4})$.

Suppose that there exists a data structure with space $O(|D|^{2}/T^{2})$ for
$P^{\mathsf{b}\mathsf{b}}_{2}(x_{2},x_{4})$ and answering time $o(T)$. Then,
we can answer $P^{\mathsf{b}\mathsf{b}}_{3}$ with light $x_{1}$ in time
$o(T^{2})$. This improves the tradeoff for $P^{\mathsf{b}\mathsf{b}}_{3}$
since the product of space usage and answering time is $o(|D|^{2})$ for any
non-constant $T$, coming to a contradiction.

Using a similar argument, it can be shown that the conditional optimality of
Theorem 5.4 for $k=4$ implies that $S\cdot T=\Omega(|D|^{2})$ tradeoff for
$P^{\mathsf{b}\mathsf{b}}_{3}$ is also optimal (but only for the range
$T\leq\sqrt{|D|}$ when the result is applicable).

##  7 Related Work

The study of fine-grained space/time tradeoffs for query answering is a
relatively recent effort in the algorithmic community. The study of distance
oracles over graphs was first initiated by [27] where lower bounds are shown
on the size of a distance oracle for sparse graphs based on a conjecture about
the best possible data structure for a set intersection problem. [10] also
considered the problem of set intersection and presented a data structure that
can answer boolean set intersection queries which is conditionally optimal
[13]. There also exist another line of work that looks at the problem of
approximate distance oracles. Agarwal et al. [4, 3] showed that for stretch-2
and stretch-3 oracles, we can achieve $S\times T=O(|D|^{2})$ and $S\times
T^{2}=O(|D|^{2})$. They also showed that for any integer $k$, a
stretch-$(1+1/k)$ oracle exhibits $S\times T^{1/k}=O(|D|^{2})$ tradeoff.
Unfortunately, no lower bounds are known for non-constant query time. [13]
used Theorem 5.1 to conjecture that the tradeoff $S\times
T^{2/(k-1)}=O(|D|^{2})$ is optimal which would also imply that
stretch-$(1+1/k)$ oracle tradeoff is also optimal. A different line of work
has considered the problem of enumerating query results of a non-boolean
query. [10] presented a data structure to enumerate the intersection of two
sets with guarantees on the total answering time. This result was generalized
to incorporate full adorned views over CQs [11]. Our work extends the results
to the setting where the join variables are projected away from the query
result (i.e. the adorned views are non-full) and makes the connection between
several different algorithmic problems that have been studied independently.
Further, we also consider boolean CQs that may contain negations. In the non-
static setting, [6] initiated the study of answering conjunctive query results
under updates. More recently, [17] presented an algorithm for counting the
number of triangles under updates. There have also been some exciting
developments in the space of enumerating query results with delay for a proper
subset of CQs known as hierarchical queries. [18] presented a tradeoff between
preprocessing time and delay for enumerating the results of any (not
necessarily full) hierarchical queries under static and dynamic settings. It
remains an interesting problem to find improved algorithms for more restricted
set of CQs such as hierarchical queries. Prior work in the space of
differential privacy [12, 22, 29, 8] also require repeated querying and may
benefit from the techniques in this paper.

##  8 Conclusion

In this paper, we investigated the tradeoffs between answering time and space
required by the data structure to answer boolean queries. Our main
contribution is a unified algorithm that recovers the best known results for
several boolean queries of practical interests. We then apply our main result
to improve upon the state-of-the-art algorithms to answer boolean queries over
the four path query which is subsequently used to improve the tradeoff for all
path queries of length greater than four and show conditional lower bounds.
There are several questions that remain open. We describe the problems that
are particularly engaging.

Unconditional lower bounds. It remains an open problem to prove unconditional
lower bounds on the space requirement for answering boolean star and path
queries in the RAM model. For instance, $2$-Set Disjointness can be answered
in constant time by materializing all answers using $\Theta(|D|^{2})$ space
but there is no lower bound to rule out if this can be achieved using sub-
quadratic space.

Improved approximate distance oracles. It would be interesting to investigate
whether our ideas can be applied to existing algorithms for constructing
distance oracles to improve their space requirement.

More general space-time bounds. The first question is to study the tradeoff
between space vs answering time (and delay guarantees) for arbitrary non-
boolean 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 better answering time guarantees.

## References

  * [1] M. Abo Khamis, P. G. Kolaitis, H. Q. Ngo, and D. Suciu.  Decision problems in information theory.  In ICALP, 2020.
  * [2] P. Afshani and J. A. S. Nielsen.  Data structure lower bounds for document indexing problems.  In ICALP, 2016.
  * [3] R. Agarwal.  The space-stretch-time tradeoff in distance oracles.  In ESA, pages 49–60. Springer, 2014.
  * [4] R. Agarwal, P. B. Godfrey, and S. Har-Peled.  Approximate distance queries and compact routing in sparse graphs.  In INFOCOM, pages 1754–1762. IEEE, 2011.
  * [5] A. Atserias, M. Grohe, and D. Marx.  Size bounds and query plans for relational joins.  SIAM Journal on Computing, 42(4):1737–1767, 2013.
  * [6] C. Berkholz, J. Keppeler, and N. 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.
  * [7] T. M. Chan and M. Lewenstein.  Clustered integer 3sum via additive combinatorics.  In STOC, pages 31–40, 2015.
  * [8] A. R. Chowdhury, T. Rekatsinas, and S. Jha.  Data-dependent differentially private parameter learning for directed graphical models.  In International Conference on Machine Learning, pages 1939–1951. PMLR, 2020.
  * [9] H. Cohen and E. Porat.  Fast set intersection and two-patterns matching.  Theoretical Computer Science, 411(40-42):3795–3800, 2010.
  * [10] H. Cohen and E. Porat.  On the hardness of distance oracle for sparse graph.  arXiv preprint arXiv:1006.1117, 2010.
  * [11] S. Deep and P. Koutris.  Compressed representations of conjunctive query results.  In PODS, pages 307–322. ACM, 2018.
  * [12] W. Dong and K. Yi.  Residual sensitivity for differentially private multi-way joins.  In Proceedings of the 2021 International Conference on Management of Data, pages 432–444, 2021.
  * [13] I. Goldstein, T. Kopelowitz, M. Lewenstein, and E. Porat.  Conditional lower bounds for space/time tradeoffs.  In WADS, pages 421–436. Springer, 2017.
  * [14] G. Gottlob, G. Greco, and F. Scarcello.  Treewidth and hypertree width.  Tractability: Practical Approaches to Hard Problems, 1, 2014.
  * [15] G. Greco and F. Scarcello.  Structural tractability of enumerating csp solutions.  Constraints, 18(1):38–74, 2013.
  * [16] J. E. Hopcroft, J. D. Ullman, and A. Aho.  The design and analysis of computer algorithms, 1975.
  * [17] A. Kara, H. Q. Ngo, M. Nikolic, D. Olteanu, and H. Zhang.  Counting triangles under updates in worst-case optimal time.  In ICDT, 2019.
  * [18] A. Kara, M. Nikolic, D. Olteanu, and H. Zhang.  Trade-offs in static and dynamic evaluation of hierarchical queries.  In PODS, pages 375–392, 2020.
  * [19] T. Kociumaka, J. Radoszewski, and W. Rytter.  Efficient indexes for jumbled pattern matching with constant-sized alphabet.  In ESA, pages 625–636. Springer, 2013.
  * [20] T. Kopelowitz and E. Porat.  The strong 3sum-indexing conjecture is false.  arXiv preprint arXiv:1907.11206, 2019.
  * [21] K. G. Larsen, J. I. Munro, J. S. Nielsen, and S. V. Thankachan.  On hardness of several string indexing problems.  Theoretical Computer Science, 582:74–82, 2015.
  * [22] C. Meehan, A. R. Chowdhury, K. Chaudhuri, and S. Jha.  A shuffling framework for local differential privacy.  arXiv preprint arXiv:2106.06603, 2021.
  * [23] A. Nash and B. Ludäscher.  Processing unions of conjunctive queries with negation under limited access patterns.  In EDBT, pages 422–440. Springer, 2004.
  * [24] H. Q. Ngo, E. Porat, C. Ré, and A. Rudra.  Worst-case optimal join algorithms.  In PODS, pages 37–48. ACM, 2012.
  * [25] H. Q. Ngo, C. Ré, and A. Rudra.  Skew strikes back: new developments in the theory of join algorithms.  SIGMOD Record, 42(4):5–16, 2013.
  * [26] D. Olteanu and M. Schleich.  Factorized databases.  ACM SIGMOD Record, 45(2):5–16, 2016.
  * [27] M. Patrascu and L. Roditty.  Distance oracles beyond the thorup-zwick bound.  In FOCS, pages 815–823. IEEE, 2010.
  * [28] N. Robertson and P. D. Seymour.  Graph minors. ii. algorithmic aspects of tree-width.  Journal of algorithms, 7(3):309–322, 1986.
  * [29] A. Roy Chowdhury, C. Wang, X. He, A. Machanavajjhala, and S. Jha.  Crypte: Crypto-assisted differential privacy on untrusted servers.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 603–619, 2020.
  * [30] J. D. Ullman.  An approach to processing queries in a logic-based query language.  In On knowledge base management systems, pages 147–164. Springer, 1986.
  * [31] F. Wei and G. Lausen.  Containment of conjunctive queries with safe negeuration.  In ICDT, pages 346–360. Springer, 2003.
  * [32] K. Xirogiannopoulos and A. 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.
  * [33] K. Xirogiannopoulos, U. Khurana, and A. Deshpande.  Graphgen: Exploring interesting graphs in relational data.  Proceedings of the VLDB Endowment, 8(12):2032–2035, 2015.
  * [34] M. Yannakakis.  Algorithms for acyclic database schemes.  In VLDB, volume 81, pages 82–94, 1981.

##  Appendix A Missing Proofs

######  Proof A.1 (Proof of Theorem 4.2).

Let $\mathcal{V}_{\mathsf{b}}=\\{x_{1},\dots,x_{k}\\}$. Recall that an access
request $\mathbf{a}=(a_{1},\dots,a_{k})$ corresponds to the query
$\varphi[a_{1}/x_{1},\dots,a_{k}/x_{k}]$; in other words, we substitute each
occurrence of a bound variable $x_{i}$ with the constant $a_{i}$. Define the
hypergraph
$\mathcal{H}_{\mathsf{b}}=(\mathcal{V}_{\mathsf{b}},\mathcal{E}_{\mathsf{b}})$,
where $\mathcal{E}_{\mathsf{b}}=\\{F\cap\mathcal{V}_{\mathsf{b}}\mid
F\in\mathcal{E}\\}$. We say that an access request $\mathbf{a}$ is valid if it
is an answer for the query $\varphi_{\mathsf{b}}$ corresponding to
$\mathcal{H}_{\mathsf{b}}$, i.e. $\mathbf{a}\in\varphi_{\mathsf{b}}(D)$. We
can construct hash indexes of linear size $O(|D|)$ during the preprocessing
phase so that we can check whether any access request is valid in constant
time $O(1)$.

For every relation $R_{F}$ in the query, let
$R_{F}(\mathbf{a})=\sigma_{x_{i}=a_{i}\mid
x_{i}\in\mathcal{V}_{\mathsf{b}}\cap F}(R_{F})$. In other words,
$R_{F}(\mathbf{a})$ is the subrelation that we obtain once we filter out the
tuples that satisfy the selection condition implied by the access request.

If $\alpha$ is the slack for the fractional edge cover $\mathbf{u}$, define
$\hat{u}_{F}=u_{F}/\alpha$ for every $F\in\mathcal{E}$. As we have discussed
earlier, $\hat{\mathbf{u}}=\\{\hat{u}_{F}\\}_{F\in\mathcal{E}}$ is a
fractional edge cover for the query $\varphi[a_{1}/x_{1},\dots,a_{k}/x_{k}]$:
indeed, it is necessary to cover only the non-bound variables, since all bound
variables are replaced by constants in the query. Hence, using a worst-case
optimal join algorithm, we can compute the access request
$\varphi[a_{1}/x_{1},\dots,a_{k}/x_{k}]$ with running time

$T(\mathbf{a})=\prod_{F\in\mathcal{E}}|R_{F}(\mathbf{a})|^{u_{F}/\alpha}.$

We can now describe the preprocessing phase and the data structure we build.
The data structure simply creates a hash index. Let $J$ be the set of valid
access requests such that $T(\mathbf{a})>T$. For every $\mathbf{a}\in J$, we
add to the hash index a key-value entry, where the key is $\mathbf{a}$ and the
value the (boolean) answer to the access request
$Q[a_{1}/x_{1},\dots,a_{k}/x_{k}]$.

We claim that the answer time using the above data structure is at most
$O(T)$. Indeed, we first check whether $\mathbf{a}$ is valid, which we can do
in constant time. If it is not valid, we simply output no. If it is valid, we
probe the hash index. If $\mathbf{a}$ exists in the hash index, we obtain the
answer in time $O(1)$ by reading the value of the corresponding entry.
Otherwise, we know that $T(\mathbf{a})<T$ and hence we can compute the answer
to the access request in time $O(T)$.

It remains to bound the size of the data structure we constructed during the
preprocessing phase. Since the size is $O(|J|)$, we will bound the size of
$J$. Indeed, we have:

$\displaystyle\hskip 70.0001ptT\cdot|J|\leq\sum_{\mathbf{a}\in
J}T(\mathbf{a})$ $\displaystyle=\sum_{\mathbf{a}\in
J}\prod_{F\in\mathcal{E}}|R_{F}(\mathbf{a})|^{u_{F}/\alpha}$
$\displaystyle=\sum_{\mathbf{a}\in
J}1^{1-1/\alpha}\cdot\left(\prod_{F\in\mathcal{E}}|R_{F}(\mathbf{a})|^{u_{F}}\right)^{1/\alpha}$
$\displaystyle\leq\left(\sum_{\mathbf{a}\in
J}1\right)^{1-1/\alpha}\cdot\left(\sum_{\mathbf{a}\in
J}\prod_{F\in\mathcal{E}}|R_{F}(\mathbf{a})|^{u_{F}}\right)^{1/\alpha}$
$\displaystyle\leq|J|^{1-1/\alpha}\cdot\prod_{F\in\mathcal{E}}|R_{F}|^{u_{F}/\alpha}$

Here, the first inequality follows directly from the definition of the set
$J$. The second inequality is Hölders inequality. The third inequality is an
application of the query decomposition lemma from [25]. By rearranging the
terms, we can now obtain the desired bound.

######  Proof A.2 (Proof of Theorem 4.8).

We introduce some new notation. Let $\mathcal{T}=(\mathscr{T},A)$ denote the
$\mathcal{V}_{\mathsf{b}}$-connex tree decomposition with $f$ as its
$\delta$-width, and $h$ as its $\delta$-height. For each node
$t\in\mathscr{T}\setminus A$, we denote by $\mathsf{anc}(t)$ the union of all
the bags for the nodes that are the ancestors of $t$,
$\mathcal{V}_{\mathsf{b}}^{t}=\mathscr{B}_{t}\cap\mathsf{anc}(t)$ and
$\mathcal{V}_{\mathsf{f}}^{t}=\mathscr{B}_{t}\setminus\mathcal{V}_{\mathsf{b}}^{t}$.
Intuitively, $\mathcal{V}_{\mathsf{b}}^{t}(\mathcal{V}_{\mathsf{f}}^{t})$ are
the bound (resp. free) variables for the bag $t$ as we traverse the tree top-
down. For example, in Figure 1(b), $A=\mathscr{B}_{t_{1}}$,
$\mathsf{anc}(t_{2})=\\{x_{1},x_{6}\\},$
$\mathcal{V}_{\mathsf{b}}^{t}=\\{x_{1},x_{6}\\}$ and
$\mathcal{V}_{\mathsf{f}}^{t}=\\{x_{1},x_{5}\\}$. For node $t_{3}$,
$\mathsf{anc}(t_{3})=\\{x_{2},x_{5},x_{1},x_{6}\\}$,
$\mathcal{V}_{\mathsf{b}}^{t}=\\{x_{2},x_{5}\\}$ and
$\mathcal{V}_{\mathsf{f}}^{t}=\\{x_{3},x_{4}\\}$

#### Data Structure Construction

We apply Theorem 4.2 to each bag (except the root bag) in $\mathscr{T}$ with
the following parameters:
$(i)\mathcal{H}^{t}=(\mathcal{V}^{t},\mathcal{E}^{t})$ where
$\mathcal{V}^{t}=\mathcal{B}_{t}$ and
$\mathcal{E}^{t}=\mathcal{E}_{\mathcal{B}_{t}}$; $(ii)$ bound variables are
$\mathcal{V}_{\mathsf{b}}^{t}=\mathsf{anc}(t)\cap\mathcal{B}_{t}$; and $(iii)$
fractional edge cover $\mathbf{u}$ corresponding to bag $\mathcal{B}_{t}$. The
space requirement for the data structure corresponding to bag
$\mathcal{B}_{t}$ is $S=O(|D|+|D|^{\rho_{t}(\delta)})\leq O(|D|+|D|^{f})$.
This follows directly from the definition of $\delta(t)$ width of bag $t$
which is assumed to be at most $f$. Recall that the data structure stores a
list of all access requests $\mathbf{a}$ defined over the schema
$\mathcal{V}_{\mathsf{b}}^{t}$ such that answering time $T>O(|D|^{f})$. Let us
call this stored list as $\mathcal{L}(t)$.

#### Query Answering

We now describe the query answering algorithm. Let $C=\\{x_{1},\dots,x_{k}\\}$
and access request $\mathbf{a}=(a_{1},\dots,a_{k})$. We first need to check
whether $\mathbf{a}$ is valid. If the request is not valid, we can simply
output no. This can be done in constant time after creating hash indexes of
size $O(|D|)$ during the preprocessing phase. If the access request is valid,
the second step is to check whether $Q(\mathbf{a})$ is true or false. Let
$\mathcal{P}$ denote the set of bags that are children of root bag. Then, for
each bag $\mathcal{B}_{t}\in\mathcal{P}$, we check whether
$\pi_{\mathcal{V}_{\mathsf{b}}^{t}}(\mathbf{a})\in\mathcal{L}(t)$. If it is
stored, it means that that running time of
$\pi_{\mathcal{V}_{\mathsf{b}}^{t}}(\mathbf{a})$ is greater than
$O(|D|^{\delta(t)})$. If the entry for
$\pi_{\mathcal{V}_{\mathsf{b}}^{t}}(\mathbf{a})$ is false in the data
structure, we can output false immediately since we know that no output tuple
can be formed by the subtree rooted at bag $\mathcal{B}_{t}$.

If there is no entry for $\pi_{\mathcal{V}_{\mathsf{b}}^{t}}(\mathbf{a})$ in
$\mathcal{L}(t)$, this means that answering time of evaluating the join at
node $t$ is $T\leq O(|D|^{\delta(t)})$. Thus, we can evaluate the join for the
bag by fixing $\mathcal{V}_{\mathsf{b}}^{t}$ as
$\pi_{\mathcal{V}_{\mathsf{b}}^{t}}(\mathbf{a})$ using any worst-case optimal
join algorithm, which guarantees that the total running time is at most
$O(|D|^{\delta(t)})$. If no output is generated, the algorithm outputs false
since no output tuple can be formed by subtree rooted at $\mathcal{B}_{t}$. If
there is output generated, then there can be at most $O(|D|^{\delta(t)})$
tuples. For each of these tuples, we recursively proceed to the children of
bag $\mathcal{B}_{t}$ and repeat the algorithm. Each fixing of variables at
bag $t$ acts as the bound variables for the children bag. In the worst case,
all bags in $\mathscr{T}$ may require join processing. Since the query size is
a constant, it implies that the number of root to leaf paths are also
constant. Thus, the answering time is dominated by the longest root to leaf
path, i.e the $\delta$-height of the decomposition. Thus, $T=O(|D|^{\sum_{t\in
P}\delta(t)})=O(|D|^{h})$.

##  Appendix B Optimizing Tree Decompositions

In this section, we discuss two key optimizations that lead to improved
tradeoffs. The first optimization relates to the space usage of the root bag.
Observe that the space requirement of Theorem 4.8 was defined as the maximum
over all bags except $A$ (which is the connected subset of tree nodes whos
union is exactly equal to $C$). Our key observation is that if the space
budget $S=O(|D|^{\max_{t\in A}\rho^{*}_{t}})$, then we can achieve an
answering time of $T=O(1)$. This is because we have materialized all possible
valid access requests (and their true/false answer) and similar to the query
answering phase, given an access request, we can check in constant time
whether the request is valid and find its boolean answer.

$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}x}$$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}y}$$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}z}$$\displaystyle
p$$\displaystyle q$$\displaystyle r$ Figure 4: Query graph with all relations
of size $|E|$. $x,y,z$ are the bound variables.

######  Example B.1.

Consider the query
$\varphi^{\mathsf{b}\mathsf{b}\mathsf{b}}(x,y,z)=R(x,y)\land S(y,z)\land
T(x,z)\land U(p,q)\land V(q,r)\land W(p,r)\land$ $D(x,p)\land E(y,p)\land
F(r,z)$ as shown in Figure 4. Applying our main result on this query gives a
tradeoff $S=O(|E|^{3}/\tau)$ and $T=O(\tau)$ by assigning an edge cover of
$1/2$ to the relations forming the two triangles. The $C$-connex decomposition
will consist of the root bag containing variables $C=\\{x,y,z\\}$ and a child
bag containing free variables $p,q,r$ and bound variables $x,y,z$. However,
note that materializing the root bag which consists of relation $R,S,T$ takes
space only $|E|^{3/2}$. Thus, the tradeoff is only useful when
$S=O(|E|^{3}/\tau)\leq|E|^{3/2}$.

Our second optimization relates to complete materialization of all tuples over
free variables in a bag. Consider a bag $t\notin A$ in the $C$-connex
decomposition. Theorem 4.8 sets space usage of $t$ as
$S=O(|D|^{\rho_{t}(\delta)})$ and answering time of $T=O(|D|^{\delta(t)})$.
The key observation is that one can achieve
$S=O(|D|^{\rho^{*}_{t}(\mathcal{V}^{t}_{\mathsf{f}})})$ and
$T=O(|D|^{\rho^{*}_{t}(\mathcal{V}^{t}_{\mathsf{f}}))}$, where
$\rho^{*}_{t}(\mathcal{V}^{t}_{\mathsf{f}})$ is the fractional edge cover
number over the free variables in $t$, by materializing the join over free
variables of bag $t$ and storing a bit that tells whether a tuple $s$
participates in some join for the bags below it in the decomposition. Thus, in
the query answering phase, we can check whether some tuple $s$ is true/false
by iterating over all materialized tuples and return the answer. We
demonstrate this with the following example.

######  Example B.2.

Consider the query
$\varphi^{\mathsf{b}\mathsf{b}\mathsf{b}\mathsf{b}}(x_{1},x_{2},x_{3},x_{4})=R(x_{1},y)\land
S(x_{2},y)\land T(y,z)\land U(x_{3},z)\land$ $V(x_{4},z)$. The $C$-connex
decomposition contains two bags: the root bag with variables
$C=\\{x_{1},x_{2},x_{3},x_{4}\\}$ and a child bag containing free variables
$y,z$ and bound variables $x_{1},x_{2},x_{3},x_{4}$. The tradeoff obtained is
$S=O(|E|^{4}/\tau^{2})$ (note that slack $\alpha=2$) and $T=O(\tau)$. However,
applying our optimization here, we observe that the fractional edge cover
number for free variables $y,z$ is $1$. Thus, during the query answering
phase, given an access request, we can iterate over all $O(|E|)$ tuples in
relation $T$ and check whether the access request and some tuple $s\in T$ join
or not, a constant time operation for each $s$. Thus, we can achieve answering
time $T=O(|E|)$ using linear space $S=O(|E|)$, which is an improvement over
the tradeoff obtained directly from Theorem 4.8.

Thus, for each bag $t\notin A$, we can set
$\rho_{t}(\delta)=\rho^{*}_{t}(\mathcal{V}^{t}_{\mathsf{f}})$ and
$\delta(t)=\rho^{*}_{t}(\mathcal{V}^{t}_{\mathsf{f}})$ to achieve the best
possible width and height for the decomposition.