Technion – Israel Institute of Technology<EMAIL_ADDRESS>Inria, LIRMM,
Univ Montpellier, CNRS, France<EMAIL_ADDRESS>Technion – Israel
Institute of Technology<EMAIL_ADDRESS>I. Eldar, N. Carmeli, and B.
Kimelfeld <ccs2012> <concept>
<concept_id>10003752.10010070.10010111.10010113</concept_id>
<concept_desc>Theory of computation Database query languages
(principles)</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10003752.10010070.10010111.10011711</concept_id>
<concept_desc>Theory of computation Database query processing and optimization
(theory)</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Theory of computation Database query languages
(principles) [500]Theory of computation Database query processing and
optimization (theory) John Q. Open and Joan R. Access 2 42nd Conference on
Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016
Little Whinging, United Kingdom 42 23 rlemma[lemma]Lemma
rtheorem[theorem]Theorem rproposition[proposition]Proposition
rcorollary[corollary]Corollary

# Direct Access for Answers to Conjunctive Queries with Aggregation

Idan Eldar  Nofar Carmeli  Benny Kimelfeld

###### Abstract

We study the fine-grained complexity of conjunctive queries with grouping and
aggregation. For some common aggregate functions (e.g., min, max, count, sum),
such a query can be phrased as an ordinary conjunctive query over a database
annotated with a suitable commutative semiring. Specifically, we investigate
the ability to evaluate such queries by constructing in log-linear time a data
structure that provides logarithmic-time direct access to the answers ordered
by a given lexicographic order. This task is nontrivial since the number of
answers might be larger than log-linear in the size of the input, and so, the
data structure needs to provide a compact representation of the space of
answers.

In the absence of aggregation and annotation, past research provides a
sufficient tractability condition on queries and orders. For queries without
self-joins, this condition is not just sufficient, but also necessary (under
conventional lower-bound assumptions in fine-grained complexity). We show that
all past results continue to hold for annotated databases, assuming that the
annotation itself is not part of the lexicographic order. On the other hand,
we show infeasibility for the case of count-distinct that does not have any
efficient representation as a commutative semiring. We then investigate the
ability to include the aggregate and annotation outcome in the lexicographic
order. Among the hardness results, standing out as tractable is the case of a
semiring with an idempotent addition, such as those of min and max. Notably,
this case captures also count-distinct over a logarithmic-size domain.

###### keywords:

aggregate queries, conjunctive queries, provenance semirings, commutative
semirings, annotated databases, direct access, ranking function, answer
orderings, query classification

##  1 Introduction

Consider a query $Q$ that may have a large number of answers, say cubic in the
number of tuples of the input database $D$. By answering $Q$ via _direct
access_ , we avoid the materialization of the list of answers, and instead,
construct a compact data structure $S$ that supports random access: given an
index $i$, retrieve the $i$th answer. Hence, direct-access evaluation for a
query $Q$ consists of two algorithms, one for the structure construction (with
the input $D$), called _preprocessing_ , and one for fast access to the
answers (with the input $S$ and $i$). This task is nontrivial when $S$ is
considerably cheaper to construct than $Q(D)$. The typical requirement is
linear or quasi-linear time to construct $S$, and logarithmic time per access.
The structure $S$ can be viewed as a compact representation of $Q(D)$, in the
general sense of Factorized Databases [DBLP:journals/sigmod/OlteanuS16], since
its size is necessarily quasi-linear and it provides fast access.

Direct-access solutions have been devised for Conjunctive Queries (CQs), first
as a way to establish algorithms for enumerating the answers with linear
preprocessing time and constant delay [braultbaron:tel-01081392] (and FO
queries with restrictions on the database [bagan:hal-00221730]); the
preprocessing phase constructs $S$, and the enumeration phase retrieves the
answers by accessing $S$ with increasing indices $i$. Later, direct access had
a more crucial role within the task of enumerating the answers in a uniformly
random order [DBLP:journals/tods/CarmeliZBCKS22]. As a notion of query
evaluation, direct access is interesting in its own right, since we can view
$S$ itself as the “result” of the query in the case where array-like access is
sufficient for downstream processing (e.g., to produce a sample of answers, to
return answers by pages, to answer $q$-quantile queries, etc.). But then $S$
has the benefit that it is considerably smaller and faster to produce than the
materialized set of answers. Indeed, recent work has studied the complexity of
direct access independently (regardless of any enumeration context)
[DBLP:conf/pods/BringmannCM22], and specifically studied which _orders_ over
the answers allow for such evaluation [DBLP:conf/pods/CarmeliTGKR21]. In this
paper, we continue with the line of work by Carmeli et al.
[DBLP:conf/pods/CarmeliTGKR21] and investigate the ability to support query
evaluation via direct access for _aggregate queries_ , while focusing on
lexicographic orderings of answers.

For illustration, consider the following example, inspired by the FIFA World
Cup (taking place at the time of writing these lines). Suppose that we have a
database of players of teams (countries), sponsors of teams, and goals scored
in different games. Specifically, we have three relations:
$\textsc{Teams}(\textit{player},\textit{country})$,
$\textsc{Sponsors}(\textit{org},\textit{country})$, and
$\textsc{Goals}(\textit{game},\textit{player},\textit{time})$. The following
CQ finds times where sponsors got exposure due to goals of supported teams:

$Q_{1}(p,c,o,t)\mathrel{{:}{-}}\textsc{Teams}(p,c),\textsc{Sponsors}(o,c),\textsc{Goals}(g,p,t)$

Suppose also that we would like the answers to be ordered lexicographically by
$c$ (country), then by $o$ (organization). Note that $o$, $c$, $p$ and $t$ are
_free_ variables and $g$ is an _existential_ variable. Carmeli et al.
[DBLP:conf/pods/CarmeliTGKR21] studied the ability to evaluate such ordered
queries with direct access. In the case of $Q_{1}$, the results of Carmeli et
al. show that there is an efficient direct-access evaluation (since the query
is free-connex and there is no “disruptive trio”).

Now, suppose that we would like to count the goals per sponsorship and player.
In standard CQ notation (e.g., Cohen et al. [10.1145/1219092.1219093]), we can
phrase this query as follows.

$Q_{2}(p,c,o,\mathsf{Count}())\mathrel{{:}{-}}\textsc{Teams}(p,c),\textsc{Sponsors}(o,c),\textsc{Goals}(g,p,t)$

Here, the variables $p$, $c$, and $o$ are treated as the _grouping variables_
(rather than free variables), where each combination of values defines a group
of tuples over $(p,c,o,g,t)$ and $\mathsf{Count}()$ simply counts the tuples
in the group. Again, we would like to answer this query via direct access.
This introduces two challenges. The first challenge is _aggregate
construction_ : when we access a tuple using $S$, the aggregate value should
be quickly produced as well. The second challenge is _ordering by aggregation_
: how can we incorporate the aggregation in the lexicographic order of the
answers, if so desired by the query? As an example, we may wish to order the
answers first by $c$, then by $\mathsf{Count}()$, and then by $o$.

As previously done in the context of algorithms for aggregate queries
[DBLP:journals/vldb/ReS09, DBLP:journals/tods/KhamisCMNNOS20], we also study a
semiring alternative to the above formalism of aggregate queries.
Specifically, we can adopt the well-known framework of _provenance semiring_
[10.1145/1265530.1265535] and phrase the query as an ordinary CQ with the
annotation carrying the aggregate value (number of goals in our example). To
design random-access evaluation, we found it more elegant, general, and
insightful to support annotation rather than SQL-like aggregate functions. For
illustration, we can phrase $Q_{2}$ as the following query.

$Q_{3}(p,c,o)\mathrel{{:}{-}}\textsc{Teams}(p,c),\textsc{Sponsors}(o,c),\textsc{Goals}(g,p,t)$

Yet, now, the database is annotated using a commutative semiring. In a
nutshell (the formal definition is in Section 2), the idea is that each tuple
is annotated with an element of the semiring, the annotation of each tuple in
the group is the product of the participating tuple annotations, and the
annotation of the whole group is the sum of all tuple annotations in the
group’s tuples. In the case of our example with $Q_{3}$, we use the numeric
semiring $(\mathbb{Z},+,\cdot,0,1)$ and each tuple is annotated simply with
the number $1$. We can use different semirings and annotations to compute
different aggregate functions like sum, min, and max. Here again, we have
challenges analogous to the aggregate case: _annotation construction_ and
_ordering by annotation_ (where the previous example becomes ordering by $c$,
then by the annotation, and then by $o$).

In this paper, we study queries in both formalisms—CQs enhanced with aggregate
functions and ordinary CQs over annotated databases. We usually devise
algorithms and upper bounds on general commutative semirings (possibly with
additional conditions), as positive results carry over to the aggregate
formalism, and we prove cases of specific intractable queries with specific
aggregate functions over ordinary (non-annotated) databases.

Our analysis is done in two parts. In Section 4, we study the case where the
annotation or aggregation is _not_ a part of the lexicographic order; we show
that under reasonable assumptions about the complexity of the semiring
operations, all results for ordinary databases [DBLP:conf/pods/CarmeliTGKR21]
continue to hold in the presence of annotation (that is, we can solve
annotation construction). We conclude the analogous tractability for the
common aggregate functions (count, sum, min, max, average), with the exception
of count-distinct which cannot be expressed efficiently as a semiring
annotation. In Section LABEL:sec:inside, we study the ability to include the
annotation or aggregation in nontrivial positions within the lexicographic
order; we show that the picture is more involved there since we hit hardness
very quickly, and we need to carefully state the conditions that allow for
efficient direct access for important cases.

The remainder of the paper is organized as follows. After preliminary concepts
and notation in Section 2, Section 3 defines the challenge of direct access
with an underlying order and recalls the state of affairs for ordinary CQs
over ordinary databases. We present our analysis in Sections 4 and
LABEL:sec:inside (as explained in the previous paragraph), and conclude in
Section LABEL:sec:conclusions. For space considerations, the proofs are in the
Appendix.

##  2 Preliminaries

We begin with preliminary notation and terminology that we use throughout the
paper.

#### Databases and conjunctive queries.

A _schema_ $\mathord{\mathbf{S}}$ is a finite set $\\{R_{1},\dots,R_{k}\\}$ of
relation symbols. Each relation symbol $R$ is associated with an arity
$\texttt{ar}(R)$, which is a natural number. We assume a countably infinite
set $\mathsf{Const}$ of _constants_ that appear as values of databases. A
_database_ $D$ over a schema $\mathord{\mathbf{S}}$ maps every relation symbol
$R$ of $\mathord{\mathbf{S}}$ to a finite relation
$R^{D}\subseteq\mathsf{Const}^{\texttt{ar}(R)}$. If $(c_{1},\dots,c_{k})$ is a
tuple of $R^{D}$ (where $k=\texttt{ar}(R)$), then we call the expression
$R(c_{1},\dots,c_{k})$ a _fact_ of $D$.

A _Conjunctive Query (CQ)_ over the schema $\mathord{\mathbf{S}}$ has the form
$Q(\vec{x}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$
where $\vec{x}$ and $\vec{y}$ are disjoint sequences of variables, and each
$\varphi_{i}(\vec{x},\vec{y})$ is an _atomic query_ $R(z_{1},\dots,z_{k})$
such that $R\in\mathord{\mathbf{S}}$ with $\texttt{ar}(R)=k$ and each $z_{i}$
is a variable in $\vec{x}$ or $\vec{y}$. Each $\varphi_{i}(\vec{x},\vec{y})$
is an _atom_ of $Q$, and we denote by $\mathrm{atoms}(Q)$ the set of atoms of
$Q$. We call $Q(\vec{x})$ the _head_ of the query and
$\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$ the
_body_ of the query. The variables of $\vec{x}$ are the _free_ variables of
$Q$, and those of $\vec{y}$ are the _existential_ variables of $Q$, and every
variable occurs at least once in the body. We use $\mathrm{vars}(Q)$ and
$\mathrm{free}(Q)$ to denote the set of all variables and all free variables
of $Q$, respectively. If $\varphi\in\mathrm{atoms}(Q)$, then
$\mathrm{vars}(\varphi)$ is the set of variables in $\varphi$. We say that $Q$
is _full_ if it has no existential variables, that is
$\mathrm{vars}(Q)=\mathrm{free}(Q)$.

We refer to a database $D$ over the schema $\mathord{\mathbf{S}}$ of the CQ
$Q$ simply as a _database over $Q$_. A _homomorphism_ from a CQ $Q$ to a
database $D$ (both over the same schema $\mathord{\mathbf{S}}$) is a mapping
$h$ from the variables and constants of $Q$ into values of $D$ such that _(a)_
for every constant $c\in\mathsf{Const}$ we have that $h(c)=c$ (i.e., constants
are mapped to themselves); _and (b)_ for each atom
$R(\kappa_{1},\dots,\kappa_{k})$ of $Q$ it holds that
$R(h(\kappa_{1}),\dots,h(\kappa_{k}))$ is a fact of $D$. We denote by
$\mathsf{Hom}(Q,D)$ the set of all homomorphisms from $Q$ to $D$. If
$h\in\mathsf{Hom}(Q,D)$ then we denote by $h(\vec{x})$ the tuple obtained by
replacing every variable $x$ with the constant $h(x)$, and we denote by
$h(\varphi_{i}(\vec{x},\vec{y}))$ the fact that is obtained from the atom
$\varphi_{i}(\vec{x},\vec{y})$ by replacing every term $\kappa$ with the
constant $h(\kappa)$. An _answer_ to $Q$ over $D$ is a tuple of the form
$h(\vec{x})$ where $h\in\mathsf{Hom}(Q,D)$. The _result_ of $Q$ over $D$,
denoted $Q(D)$, is $Q(D)\vcentcolon=\\{h(\vec{x})\mid
h\in\mathsf{Hom}(Q,D)\\}$.

Consider a CQ
$Q(\vec{x}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$.
We may refer to $Q$ as $Q(\vec{x})$ to specify the sequence of free variables
in the head. In this work, the _order_ of the sequence $\vec{x}$ has a crucial
role, since it determines the desired order of answers. Specifically, we will
assume that the desired order of answers is _lexicographic_ in the left-to-
right order of $\vec{x}$. For example, the CQ
$Q(x_{1},x_{2}){\,:\\!\\!-\,}R(x_{1},x_{2}),S(x_{2},y)$ differs from the CQ
$Q^{\prime}(x_{2},x_{1}){\,:\\!\\!-\,}R(x_{1},x_{2}),S(x_{2},y)$ not only in
the order of values within each answer tuple, but also in the order over the
answers. For $Q(x_{1},x_{2})$ we order the answers first by $x_{1}$ and then
by $x_{2}$, and for $Q^{\prime}(x_{2},x_{1})$ we order first by $x_{2}$ and
then by $x_{1}$,

As usual, we associate a CQ $Q$ with the hypergraph $H(Q)=(V_{Q},E_{Q})$ where
$V_{Q}=\mathrm{vars}(Q)$ and
$E_{Q}=\\{\mathrm{vars}(\varphi)|\varphi\in\mathrm{atoms}(Q)\\}$. We say that
$Q$ is _acyclic_ if $H(Q)$ is an ($\alpha$-)acyclic hypergraph. Recall that a
hypergraph $H=(V,E)$ is acyclic if there is a tree $T=(E,E_{T})$, called a
_join tree_ of $H$, with the running intersection property: for each vertex
$v\in V$, the set of hyperedges that contain $v$ induces a connected subtree
of $T$. If $H$ is acyclic and $S\subseteq V$, then we say that $H$ is _$S$
-connex_ if $H$ remains acyclic even if we add $S$ to the set of hyperedges
[braultbaron:tel-01081392]. An acyclic CQ $Q$ is _free-connex_ if $H(Q)$ is
acyclic and $\mathrm{free}(Q)$-connex.

A hypergraph $H^{\prime}=(V,E^{\prime})$ is an _inclusive extension_ of an
hypergraph $H=(V,E)$ if $E\subseteq E^{\prime}$ and for every edge
$e^{\prime}\in E^{\prime}$ there is an edge $e\in E$ such that
$e^{\prime}\subseteq e$. It is known that $H$ is acyclic $S$-connex if and
only if $H$ has an inclusive extension with a join tree $T$ such that $S$ is
precisely the set of all variables contained in the vertices of some subtree
of $T$ [10.1007/978-3-540-74915-8_18]. We call such a tree ext-$S$-connex
tree. When $S$ is the set of free variables of the CQ, and the CQ is clear
from the context, we call such a tree _ext-free-connex_.

The notion of a _disruptive trio_ has been introduced previously in the
context of direct access to the answers of CQs [DBLP:conf/pods/CarmeliTGKR21].
A disruptive trio of a CQ $Q(\vec{x})$ is a set of three distinct free
variables $x_{1}$, $x_{2}$, and $x_{3}$ such that $x_{1}$ and $x_{2}$ neighbor
$x_{3}$ but not each other, and $x_{3}$ succeeds both $x_{1}$ and $x_{2}$ in
$\vec{x}$. By saying that $x$ and $y$ are _neighbors_ we mean that they occur
jointly in at least one of the atoms.

#### Aggregate queries.

By an _aggregate function_ we refer to a function that takes as input a bag of
tuples over $\mathsf{Const}$ and returns a single value in $\mathsf{Const}$.
We adopt the notation of Cohen et al. [10.1145/1219092.1219093] to our
setting, as follows. An _aggregate query_ here is an expression of the form

$Q(\vec{x},\alpha(\vec{w}),\vec{z}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y},\vec{z}),\dots,\varphi_{\ell}(\vec{x},\vec{y},\vec{z})$

such that
$Q^{\prime}(\vec{x},\vec{z}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y},\vec{z}),\dots,\varphi_{\ell}(\vec{x},\vec{y},\vec{z})$
is a CQ, $\alpha$ an aggregate function, and $\vec{w}$ a sequence of variables
from $\vec{y}$. An example is
$Q(x_{1},x_{2},\mathsf{Sum}(y_{2}),z){\,:\\!\\!-\,}R(x_{1},x_{2},y_{1}),S(y_{1},y_{2},z)$.
We refer to such a query as an _Aggregate CQ_ or _ACQ_ for short. Given a
database $D$ over $Q^{\prime}$, the result $Q(D)$ is defined by
$Q(D)\vcentcolon=\\{(\vec{a},\alpha(B(\vec{a},\vec{b})),\vec{b})\mid(\vec{a},\vec{b})\in
Q^{\prime}(D)\\}$ where $B(\vec{a},\vec{b})$ is the bag that is obtained by
collecting the tuples $h(\vec{w})$ from every $h\in\mathsf{Hom}(Q^{\prime},D)$
with $h(\vec{x})=\vec{a}$ and $h(\vec{z})=\vec{b}$.

We say that $Q$ is _acyclic_ if $Q^{\prime}$ is acyclic. Similarly, $Q$ is
_free-connex_ if $Q^{\prime}$ is free-connex. A _disruptive trio_ of $Q$ is a
disruptive trio of $Q^{\prime}$; in other words, the definition of a
disruptive trio remains unchanged when introducing aggregates, while we
consider only the grouping variables and not the aggregate function.

######  Remark 2.1.

We remark on two aspects in our definition of ACQs. First, the reason for
using both $\vec{x}$ and $\vec{z}$ as sequences of free variables is to
determine a position for aggregate value $\alpha(\vec{w})$ and, consequently,
define its position in the lexicographic order over the answers. Second, the
reader should note that, in our notation, an ACQ has a single aggregate
function. While this is important for some of our results, other results can
be easily extended to multiple aggregate functions $\alpha(\vec{w_{1}})$, …,
$\alpha(\vec{w_{k}})$. We will mention this extension when relevant.∎

In this work, we restrict the discussion to the common aggregate functions
$\mathsf{Count}$, $\mathsf{CountD}$ (count distinct), $\mathsf{Sum}$,
$\mathsf{Avg}$ (average), $\mathsf{Min}$ and $\mathsf{Max}$. All aggregate
functions take a single column as input (i.e., $\vec{y_{i}}$ is of length one)
except for $\mathsf{Count}$ that counts the tuples in the group and takes no
argument. For instance, the query $Q_{2}$ in the Introduction uses
$\mathsf{Count}()$ and it could also use $\mathsf{CountD}(g)$ for counting the
distinct games with scored goals.

#### Commutative semirings.

A _commutative monoid_ is an algebraic structure
$(\mathbb{K},\square,\varnothing)$ over a domain $\mathbb{K}$, with a binary
operation $\square$ and a distinguished element $\varnothing\in\mathbb{K}$ the
satisfy: _associativity_ : $(a\square b)\square c=a\square(b\square c)$ for
any $a,b,c\in\mathbb{K}$, _commutativity_ : $a\square b=b\square a$ for any
$a,b\in\mathbb{K}$, and _neutrality_ : $a\square\varnothing=a$ for any
$a\in\mathbb{K}$. A _commutative semiring_ is an algebric structure
$(\mathbb{K},\oplus,\otimes,\mathord{\bar{0}},\mathord{\bar{1}})$ over a
domain $\mathbb{K}$, with two binary operations $\oplus$ and $\otimes$ and two
distinguished elements $\mathord{\bar{0}}$ and $\mathord{\bar{1}}$ in
$\mathbb{K}$ that satisfy the following conditions: _(a)_
$(\mathbb{K},\oplus,\mathord{\bar{0}})$ is a commutative monoid; _(b)_
$(\mathbb{K},\times,\mathord{\bar{1}})$ is a commutative monoid; _(c)_
$a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c)$ for all
$a,b,c\in\mathbb{K}$; _and (d)_ $a\otimes\mathord{\bar{0}}=\mathord{\bar{0}}$
for all $a\in\mathbb{K}$.

We refer to $\oplus$ as the _addition_ operation, $\otimes$ as the
_multiplication_ operation, $\mathord{\bar{0}}$ as the _additive identity_ and
$\mathord{\bar{1}}$ as the _multiplicative identity_. We give examples of
commutative semirings at the end of this section.

#### Annotated databases and query answers.

Let $\mathord{\mathbf{S}}$ be a schema and
$(\mathbb{K},\oplus,\otimes,\mathord{\bar{0}},\mathord{\bar{1}})$ a
commutative semiring. A _$\mathbb{K}$ -database_ (_over
$\mathord{\mathbf{S}}$_) is a pair $(D,\tau)$ where $D$ is a database over
$\mathord{\mathbf{S}}$ and $\tau:D\rightarrow\mathbb{K}$ is function that maps
every fact $f$ of $D$ to an element $\tau(f)$ of $\mathbb{K}$, called the
_annotation_ of $f$.

The annotation of a database propagates to the query answers by associating a
semiring operation with each algebraic operation [10.1145/1265530.1265535]. In
the case of CQs, the relevant operations are _joins_ and _projection_. For
join, the annotation of the result is the product of the annotation of the
operands. For projection, the annotation is the sum of the annotations of the
tuples that give rise to the result. In our terminology, we have the
following.

Let
$Q(\vec{x}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$
be a CQ and $(D,\tau)$ an annotated database. For a homomorphism $h$ from $Q$
to $D$, we denote by $\otimes h$ the product of the annotations of the facts
in the range of $h$, that is $\otimes
h\vcentcolon=\tau(h(\varphi_{1}(\vec{x},\vec{y})))\otimes\dots\otimes\tau(h(\varphi_{\ell}(\vec{x},\vec{y})))$.
An _answer_ to $Q$ over $(D,\tau)$ is a pair $(\vec{c},a)$ such that
$\vec{c}\in Q(D)$ and

$a=\oplus\\{\otimes h\mid h\in\mathsf{Hom}(Q,D)\land h(\vec{x})=\vec{c}\\}$

where, for $A=\\{a_{1},\dots,a_{n}\\}\subseteq\mathbb{K}$, we define $\oplus
A=a_{1}\oplus\dots\oplus a_{n}$. As before, the _result_ of $Q$ over
$(D,\tau)$, denoted $Q(D,\tau)$, is the set of answers $(\vec{c},a)$ to $Q$
over $(D,\tau)$. We will make use of the fact that over commutative semirings,
projections and joins are commutative [10.1145/1265530.1265535].

In this work, we study the ability to incorporate the annotation in the order
over the answers. More precisely, we will investigate the complexity of
involving the annotation in the lexicographic order over the answers, as if it
were another value in the tuple. So, when we consider a CQ $Q(\vec{x})$, we
need to specify where the annotation goes inside $\vec{x}$. Similarly to the
ACQ notation, we do so by replacing $\vec{x}$ with a sequence
$(\vec{x},\star,\vec{z})$ where $\star$ represents the annotation value. We
refer to a CQ of this form as a CQ⋆. An example of a CQ⋆ is
$Q(x_{1},x_{2},\star,z){\,:\\!\\!-\,}R(x_{1},x_{2},y_{1}),S(y_{1},y_{2},z)$
where the lexicographic order is by $x_{1}$, then by $x_{2}$, then by the
annotation, and then by $z$.

Let $Q$ be a CQ⋆, and let $Q^{\prime}$ be the CQ obtained from $Q$ by removing
$\star$ from the head. As in the case of ACQs, $Q$ is _acyclic_ if
$Q^{\prime}$ is acyclic, $Q$ is _free-connex_ if $Q^{\prime}$ is free-connex,
and a _disruptive trio_ of $Q$ is a disruptive trio of $Q^{\prime}$.

Aggregate functions can often be captured by annotations of answers in
annotated databases, where each aggregate function might require a different
commutative semiring:

  * •

$\mathsf{Sum}$: the numeric semiring $(\mathbb{Q},+,\cdot,0,1)$.

  * •

$\mathsf{Count}$: the counting semiring $(\mathbb{N},+,\cdot,0,1)$.

  * •

$\mathsf{Max}$: the max tropical semiring
$(\mathbb{Q}\cup\\{-\infty\\},\mathsf{max},+,-\infty,0)$.

  * •

$\mathsf{Min}$: the min tropical semiring
$(\mathbb{Q}\cup\\{\infty\\},\mathsf{min},+,\infty,0)$.

The translation is straightforward (and known, e.g.,
[DBLP:journals/vldb/ReS09, DBLP:journals/tods/KhamisCMNNOS20]), as we
illustrate in Figure 1: the aggregated value becomes the annotation on one of
the relations, the annotation outside of this relation is the multiplicative
identity (as we later term “locally annotated”), and the addition operation
captures the aggregate function.

$\mathsf{Avg}$ can be computed using $\mathsf{Sum}$ and $\mathsf{Count}$.
$\mathsf{CountD}$ (count distinct) cannot be captured by a semiring, as the
result of $\oplus$ cannot be computed from two intermediary annotations in the
domain. We can, however, capture a semantically similar concept with the set
semiring $({\mathcal{P}}(\Omega),\cup,\cap,\varnothing,\Omega)$ by annotating
each fact with the actual set of distinct elements. However, in such cases, we
will need our complexity analysis to be aware of the cost of the operations.

Teams
---
$p$ | $c$
1 | 5
2 | 5
3 | 6
4 | 7
5 | 8

Goals
---
$g$ | $p$ | $t$
1 | 1 | 31
1 | 3 | 50
1 | 3 | 75
2 | 4 | 90
2 | 4 | 9

Replays
---
$g$ | $t$
1 | 1
1 | 31
1 | 50
2 | 5
1 | 90

$\Rightarrow$ Team $p$ $c$ $\tau_{+}$ 1 5 1 2 5 1 3 6 1 4 7 1 5 8 1 Goals $g$
$p$ $t$ $\tau_{+}$ 1 1 31 1 1 3 50 1 1 3 75 1 2 4 90 1 2 4 9 1 Replays $g$ $t$
$\tau_{+}$ 1 1 1 1 31 31 1 50 50 2 5 5 1 90 90

Figure 1: An example of a $\mathbb{Q}$-database over the numerical semiring
constructed to evaluate the ACQ
$Q(c,\mathsf{Sum}(t)){\,:\\!\\!-\,}\textsc{Teams}(p,c),\textsc{Goals}(g,p,t),\textsc{Replays}(g,t)$.

##  3 The Direct-Access Problem

In this paper, we study CQs with lexicographic orders over the answers. As
said earlier, the lexicographic order for the CQ $Q(\vec{x})$ is left to right
according to $\vec{x}$. We will also investigate lexicographic orders that
involve the annotation or aggregation, when the query is a CQ⋆
$Q(\vec{x},\star,\vec{z})$ or an ACQ $Q(\vec{x},\alpha(\vec{u}),\vec{z})$,
respectively. We refer uniformly to the annotation of an answer (over an
annotated database) and to the aggregate value of the answer’s group (over an
ordinary database) as the _computed value_.

Let $Q$ be a CQ, CQ⋆, or an ACQ. A _direct access_ solution for $Q$ consists
of two algorithms: one for _preprocessing_ and one for _access_.

  * •

The preprocessing algorithm takes as input a database $D$ over $Q$ and
constructs a data structure $S_{D}$.

  * •

The access algorithm takes as input $S_{D}$ and an index $i$, and returns the
$i$th answer of $Q(D)$ in the lexicographic order. Note that this answer
includes the computed value, when it exists. If $i>|Q(D)|$ then the algorithm
should return _null_.

To define the complexity requirements of _efficient_ direct access, we first
describe the complexity model that we adopt. We use _data complexity_ as a
yardstick of tractability. Hence, complexity is measured in terms of the size
of the database, while the size of the query is fixed (and every query is a
separate computational problem). Assuming the input is of size $n$, we use the
RAM model of computation with $O(\log n)$-bit words and uniform-cost
operations. Notably, this model allows us to assume perfect hash tables can be
constructed in linear time, and they provide access in constant time [louis-
model].

Let $T_{p}$ and $T_{a}$ be numeric functions. A direct-access algorithm is
said to be _in $\mathord{\langle T_{p},T_{a}\rangle}$_ if the preprocessing
phase takes $O(T_{p}(|D|))$ time and each access takes $O(T_{a}(|D|))$ time.
For example, $\mathord{\langle\mathrm{loglinear},\log\rangle}$ states that
preprocessing constructs in $O(|D|\log|D|)$ time a data structure that
provides $O(\log|D|)$-time access. In this work, a query $Q$ has _efficient_
direct access (and $Q$ is deemed tractable) if it has a direct access
algorithm in $\mathord{\langle\mathrm{loglinear},\log\rangle}$.

Carmeli et al. [DBLP:conf/pods/CarmeliTGKR21] established a dichotomy in the
tractability of the CQs and lexicographic orders. This dichotomy relies on the
following hypotheses.

  * •

######  Theorem 3.1 ([DBLP:conf/pods/CarmeliTGKR21]).

Let $Q$ be a CQ.

  1. 1.

If $Q$ is free-connex with no disruptive trio, then direct access for $Q$ is
in $\mathord{\langle\mathrm{loglinear},\log\rangle}$.

  2. 2.

Otherwise, if $Q$ is also self-join-free, then direct access for $Q$ is not in
$\mathord{\langle\mathrm{loglinear},\log\rangle}$, assuming the

##  4 Incorporating Annotation and Aggregation in the Answers

In this section, we discuss the existence of efficient direct access in the
case where the order _does not_ involve the computed value, that is, the
annotation (for CQ⋆s) or the aggregate values (for ACQs). Equivalently, these
are queries where the computed value is last in order, that is, the vector
$\vec{z}$ in the head is empty. Hence, we focus on CQ⋆s of the form
$Q(\vec{x},\star)$ and ACQs of the form $Q(\vec{x},\alpha(\vec{w}))$. In other
words, the problem is similar to the CQ case, except that the access algorithm
should also retrieve the aggregated value from the data structure. In Section
4.1, we will use annotated databases to identify the cases where this can be
done efficiently for min, max, count, sum, and average. By contrast, in
Section 4.2 we will show that we cannot do the same for count-distinct, even
in the case of an extremely simple query, unless the domain of the elements we
count is small (logarithmic-size).

But first, we need to be clear about the complexity of the semiring
operations. The RAM model allows us to assume that the numeric, counting, min
tropical, and max tropical semirings use constant space for representing
values and constant time for the operations $\oplus$ and $\otimes$. In fact,
it suffices for our results to assume that the operations take logarithmic
time, and later we will make use of this relaxed assumption (within a special
case of $\mathsf{CountD}$). We refer to a semiring with this property as a
_logarithmic-time (commutative) semiring_.

In our proofs, we will use the following definition of when two facts $f$ and
$f^{\prime}$ agree in the context of two queries.

######  Definition 4.1.

Let $Q$ and $Q^{\prime}$ be CQs over the schemas $\mathord{\mathbf{S}}$ and
$\mathord{\mathbf{S}}^{\prime}$, respectively. Let $\varphi$ and
$\varphi^{\prime}$ be atoms of $Q$ and $Q^{\prime}$ over the relation symbols
$R$ and $R^{\prime}$, respectively. Let $f$ and $f^{\prime}$ be facts over $R$
and $R^{\prime}$, respectively. We say that $f$ and $f^{\prime}$ _agree_
(w.r.t. $\varphi$ and $\varphi^{\prime}$) if there exists a homomorphism
$h:\mathrm{vars}(\phi)\cup\mathrm{vars}(\phi^{\prime})\rightarrow\mathsf{Const}$
such that $f$ and $f^{\prime}$ are obtained from $\varphi$ and
$\varphi^{\prime}$, respectively, by replacing each variable $x$ with the
constant $h(x)$.

###  4.1 Generalized Dichotomies

We now show that Theorem 3.1 extends to databases with annotations, and so,
also to queries with aggregate functions that can be efficiently simulated by
annotations. The first step is to eliminate the existential variables from the
CQ⋆. It is folklore that free-connex CQs (over non-annotated databases) can be
transformed into _full_ acyclic CQs in linear time [10.1145/3035918.3064027,
10.1145/2656335]. The following lemma states that the same holds for free-
connex CQ⋆s over annotated databases.

Let $(\mathbb{K},\oplus,\otimes,\mathord{\bar{0}},\mathord{\bar{1}})$ be a
logarithmic-time commutative semiring, and let $Q(\vec{x},\star,\vec{z})$ be a
free-connex CQ⋆. There exists a full acyclic CQ⋆
$Q^{\prime}(\vec{x},\star,\vec{z})$, without self-joins, and an
$O(|D|\log|D|)$-time algorithm that maps $\mathbb{K}$-databases $(D,\tau)$ of
$Q$ to $\mathbb{K}$-databases $(D^{\prime},\tau^{\prime})$ of $Q^{\prime}$
such that _(a)_ $Q^{\prime}(D^{\prime},\tau^{\prime})=Q(D,\tau)$, _and (b)_
$Q$ has a disruptive trio if and only if $Q^{\prime}$ has a disruptive trio.

######  Proof 4.2.

Since $Q$ is free-connex, it has an ext-free-connex join tree $T$. First, we
make it so that each node of the tree has a unique associated atom in the
query and a unique associated relation in the database. We eliminate self-
joins by assigning the atoms with unique relation names and duplicating the
relations accordingly. For every node of the tree that does not correspond to
a relation, we take the relation of a node that contains it (without the
annotations), project it accordingly, and annotate the facts with
$\mathord{\bar{1}}$. The query answers are unchanged by the addition of these
annotated relations as they contain projections of existing relations
annotated with the multiplicative identity.

Since $T$ is an ext-free-connex tree, it has a subtree $T^{\prime}$ which
contains precisely the free variables of $Q$. We denote the vertices of
$T^{\prime}$ as the free vertices. We now claim that as long as $T$ has nodes
that are not in the set of free vertices, we can remove such a node from $T$
and remove its associated atom from the query while adapting the database so
that the query results remain unchanged. At the end of this process, we are
left with a full conjunctive query and a matching join tree. Thus, the query
remains acyclic.

As long as $T$ has a node not in the set of free vertices, eliminate such a
leaf node as follows:

  1. 1.

In the relation associated with the node, project out every variable not
shared between the node and its neighbor while summing ($\oplus$) annotations.

  2. 2.

Join the obtained relation into the relation of the neighbor node while
multiplying ($\otimes$) annotations.

  3. 3.

Remove the leaf from the tree, its associated atom from the query, and its
associated relation from the database.

More specifically, denote by $S$ the variables shared between the treated leaf
node $v$ and its neighbor. During step (1), we initialize a lookup table where
for each unique assignment of $S$ matching a fact in the relation of $v$, we
set the semiring value $\mathord{\bar{0}}$. Then, we iterate over each fact of
the relation of $v$ and add its annotation (using the semiring $\oplus$) to
the entry matching its assignment to $S$. Next, during step (2), we iterate
over every fact in the relation matching the neighbor of $v$ and multiply its
existing annotation (using the semiring $\otimes$) with the value stored for
its assignment to $S$. Once we are done, each fact in the relation matching
the neighbor of $v$ had its annotation multiplied by the sum of the
annotations of the facts that agree with it in the relation of $v$.

Consider the variables that appear in $v$ and not its neighbor. Since $v$ was
chosen to be a leaf, the running intersection property guarantees that such
variables only appear in $v$. This means that they do not appear in the free
vertices, so they are existential and must be projected out. As joins and
projections are commutative over annotated databases
[10.1145/1265530.1265535], we can do the projection first. As these variables
appear only in $v$, the projection can be done locally. Thus, the results of
the modified query over the modified database remain unchanged.

In terms of complexity, we perform the elimination of a single node in
quasilinear time. Since the number of elimination steps is bounded by the size
of the query, the entire elimination takes quasilinear time.

Lastly, we prove that $Q$ has a disruptive trio if and only if $Q^{\prime}$
has a disruptive trio. Since the existence of a disruptive trio relies solely
on which variables are neighbors in the query, it is sufficient to prove that
two variables are neighbors in $Q$ if and only if they are neighbors in
$Q^{\prime}$.

The atoms of $Q^{\prime}$ are also atoms of $Q$; hence, if $x_{1}$ and $x_{2}$
be neighbors in $Q^{\prime}$, then they are also neighbors in $Q$. Conversely,
suppose that $x_{1}$ and $x_{2}$ are neighbors in $Q$. Consider the subtree
$T^{\prime}$ of the ext-free-connex join tree $T$ of $Q$ that contains
precisely the free variables. Note that $T^{\prime}$ is the join tree of
$Q^{\prime}$. Hence, it suffices to show that $T^{\prime}$ contains a vertex
that includes both $x_{1}$ and $x_{2}$. Suppose that $x_{1}$ and $x_{2}$ are
neighbors in node $v$ of $T$, and suppose that $v$ is not in $T^{\prime}$
(otherwise, we are done). Let $v^{\prime}$ be a vertex in $T^{\prime}$ that is
closest to $v$ in $T$. Since $T^{\prime}$ contains both $x_{1}$ and $x_{2}$
(as they are both free variables), the running intersection property implies
that $v^{\prime}$ must contain both $x_{1}$ and $x_{2}$.

We note that in the case where the semiring operations require only constant
time, the algorithm of Section 4.1 runs in linear time instead of loglinear
time. With this lemma, we can now prove the following generalization of
Theorem 3.1 to annotated databases.

Let $(\mathbb{K},\oplus,\otimes,\mathord{\bar{0}},\mathord{\bar{1}})$ be a
logarithmic-time commutative semiring, and let $Q(\vec{x},\star)$ be a CQ⋆.

  1. 1.

If $Q$ is free-connex and with no disruptive trio, then direct access for $Q$
is in $\mathord{\langle\mathrm{loglinear},\log\rangle}$ on
$\mathbb{K}$-databases.

  2. 2.

Otherwise, if $Q$ is also self-join-free, then direct access for $Q$ is not in
$\mathord{\langle\mathrm{loglinear},\log\rangle}$, assuming the

######  Proof 4.3.

We prove each part separately.

#### Part 1 (tractability).

We can use Section 4.1 to focus on full CQ⋆s without self-joins. We build on
the algorithm that Carmeli et al. [DBLP:conf/pods/CarmeliTGKR21] presented for
proving what we gave here as Theorem 3.1. This algorithm uses the concept of a
_layered join tree_ , defined for a conjunctive query $Q$ and variable order.
It can be seen as a particular kind of join tree of a query $Q_{\texttt{lay}}$
to $Q$. That is, the variables of every atom of $Q$ are contained in an atom
of $Q_{\texttt{lay}}$ and vice versa. They showed how to find such a tree when
there is no disruptive trio. They also showed how, given a database $D$ over
$Q$, to construct a database $D_{\texttt{lay}}$ over $Q_{\texttt{lay}}$ such
that $Q(D)=Q_{\texttt{lay}}(D_{\texttt{lay}})$ in $O(|D|\log|D|)$ time. Then,
they show how to use the special structure of the layered join tree to perform
access calls in logarithmic time. In an access call, a fact is selected from
each relation of $D_{\texttt{lay}}$, and these facts are joined to form the
answer.

We use the same construction, and incorporate the annotations as follows. We
construct $Q_{\texttt{lay}}$ and $(D_{\texttt{lay}},\tau_{\texttt{lay}})$ from
$Q$ and $(D,\tau)$, respectively. For $Q_{\texttt{lay}}$ and
$D_{\texttt{lay}}$, we use the same construction as that of Carmeli et al.
[DBLP:conf/pods/CarmeliTGKR21], and we apply it by ignoring the annotation.
Next, we annotate each fact $f$ of $D_{\texttt{lay}}$ with the initial value
$\tau^{\prime}(f)=\mathord{\bar{1}}$, and then apply the following operation.

1: for all atoms $\varphi$ of $Q$ do

2: Select an atom $\varphi_{\texttt{lay}}$ of $Q_{\texttt{lay}}$ such that
$\mathrm{vars}(\varphi)\subseteq\mathrm{vars}(\varphi_{\texttt{lay}})$

3: Let $R$ and $R_{\texttt{lay}}$ be the relation symbols of $\varphi$ and
$\varphi_{\texttt{lay}}$, respectively

4: for all facts $f_{\texttt{lay}}$ of $R_{\texttt{lay}}$ do

5: Find a fact $f$ of $R$ such that $f$ and $f_{\texttt{lay}}$ agree w.r.t.
$\varphi$ and $\varphi_{\texttt{lay}}$ (see Definition 4.1)

6:
$\tau_{\texttt{lay}}(f_{\texttt{lay}})\leftarrow\tau_{\texttt{lay}}(f_{\texttt{lay}})\cdot\tau(f)$

Note that in line 5, at most one corresponding $f$ exists for every
$f_{\texttt{lay}}$, since
$\mathrm{vars}(\varphi)\subseteq\mathrm{vars}(\varphi_{\texttt{lay}})$.
Moreover, from the construction of Carmeli et al.
[DBLP:conf/pods/CarmeliTGKR21] it follows that such an $f$ necessarily exists
(Since they apply the full reduction of the Yannakakis
[10.5555/1286831.1286840] algorithm). Finding each $f$ can be done in constant
time by constructing a hash table where each key is a tuple of values assigned
to $\mathrm{vars}(\phi)$ by $f$. Then, for each $f_{\texttt{lay}}$, we project
out other variables and search the hash table. In total, this procedure
requires additional $O(|D|\log|D|)$ time during construction.

The access algorithm extends naturally from before: a fact is selected from
each relation of $D_{\texttt{lay}}$, and those are combined to form an answer.
The annotation of the answer is the product of the annotation of the selected
facts. Retrieving the answer takes logarithmic time, and then we compute the
annotation in logarithmic time using a constant number of semiring
multiplications. The returned answer is annotated correctly: the annotation is
indeed the product of the annotations of the fact of $D$ that form the answer
and those were multiplied to form the annotation in $D_{\texttt{lay}}$.

#### Part 2 (hardness).

For the negative side of the dichotomy, we simply use the negative side of
Theorem 3.1, since each answer to a CQ⋆ contains the ordinary (non-annotated)
answer to the CQ obtained by removing $\star$, and moreover, the answers have
the same order. This concludes the proof.

From the positive side of Section 4.1, we conclude efficient direct access for
ACQs $Q$, as long as we can efficiently formulate the aggregate function as an
annotation over some logarithmic-time commutative semiring. This is stated in
the following Corollary of Section 4.1. The negative side of the corollary is
a straightforward consequence of Theorem 3.1. In the case of $\mathsf{Avg}$,
we compute $\mathsf{Sum}$ and $\mathsf{Count}$ separately and divide the
results.

Consider an ACQ
$Q(\vec{x},\alpha(\vec{w})){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$
where $\alpha$ is one of $\mathsf{Min}$, $\mathsf{Max}$, $\mathsf{Count}$,
$\mathsf{Sum}$, and $\mathsf{Avg}$.

  1. 1.

If the CQ
$Q^{\prime}(\vec{x}){\,:\\!\\!-\,}\varphi_{1}(\vec{x},\vec{y}),\dots,\varphi_{\ell}(\vec{x},\vec{y})$
is free-connex with no disruptive trio, then direct access for $Q$ is in
$\mathord{\langle\mathrm{loglinear},\log\rangle}$.

  2. 2.

Otherwise, if $Q$ is also self-join-free, then direct access for $Q$ is not in
$\mathord{\langle\mathrm{loglinear},\log\rangle}$, assuming the

######  Proof 4.4.

For the positive side, we simply apply Section 4.1 with the corresponding
semiring. In the case where $\alpha$ is $\mathsf{Avg}$, we compute
$\mathsf{Sum}$ and $\mathsf{Count}$ separately and divide the results. The
negative side carries over from Theorem 3.1, since a direct access solution
for $Q$ in $\mathord{\langle\mathrm{loglinear},\log\rangle}$ is also a direct
access solution for $Q^{\prime}$ in
$\mathord{\langle\mathrm{loglinear},\log\rangle}$ if we ignore the aggregated
values.

######  Remark 4.5.

Section 4.1 can be easily extended to support multiple aggregate functions
$\alpha_{1}(\vec{w}_{1})$, …, $\alpha_{k}(\vec{w}_{k})$. For that, we can
simply solve the problem for each $\alpha_{i}(\vec{w}_{i})$ separately, and
extract the aggregate values of an answer from the $k$ data structures that we
construct in the preprocessing phase. (Moreover, a practical implementation
can handle all aggregate values in the same structure.) ∎

###  4.2 Hardness of Count Distinct

Can we generalize Section 4.1 beyond the stated aggregate functions? The most
notable missing aggregate function is $\mathsf{CountD}$ (count distinct).
Next, we show that we _cannot_ have similar tractability for count distinct,
even in the case of a very simple query, under the _small-universe Hitting Set
Conjecture (_

######  _Hypothesis 9_.

HSC)

[vassilevska2015hardness]. In

######  Hypothesis 10.

HSC, we are given two sets $\mathcal{U}$ and $\mathcal{V}$ of size $N$, each
containing sets over the universe $\\{1,2,\ldots,d\\}$, and the goal is to
determine whether $\mathcal{U}$ contains a set that shares an element with
(hits) every set in $\mathcal{V}$.