The paper presents recent findings on the fine-grained complexity of conjunctive queries with aggregation. For common aggregate functions (e.g., min, max, sum), such a query can be phrased as an ordinary conjunctive query over a database annotated with a suitable commutative semiring. We investigate the ability to evaluate queries by constructing in log-linear time a data structure that provides logarithmictime direct access to the answers, ordered by a lexicographic order of choice. Importantly, these complexity guarantees hold even if the result of the query is asymptotically larger than log-linear in the size of the input.
CQ finds times where sponsors got exposure due to goals of supported teams: 1(, , , ) ∶−
Teams(, ), Sponsors(, ), Goals(, , ) Suppose also that we would like the answers to be ordered lexicographically by their order in the head: first by country, then by organization, and so on. Note tha,t , and arefree variables and is anexistential variable. Carmeli et al4.][studied the ability to evaluate such ordered queries with direct access. In the case of1, they show that there is an eficient direct-access evaluation, since the query ifsree-connex and there is nodisruptive trio. We explain these terms next. (For more precise definition, we refer the reader to Carmeli et a4]l.)[
In general, a CQ has the for(m)⃗∶− 1(,⃗)⃗, … , ℓ(,⃗)⃗ where ⃗ and ⃗ are disjoint sequences of variables, and eac h (,⃗)⃗ is anatomic query. A CQ is free-connex if it is acyclic and remains acyclic even if the head is viewed as an atom. Also recall thdaitsrauptive trio of a CQ()⃗ is a set of three distinct free variable1s, 2, and 3 such that 1 and 2 neighbor 3 but not each other, and 3 appears after both 1 and 2 in ⃗. Two variables are considered neighbors if they appear together in some query atom.
In this work, we continue with the line of work of Carmeli et a4]l.a[nd investigate the ability to support query evaluation via direct access for queries over annotated databases. To illustrate, suppose that we would like to count the goals per sponsorship and player. We can phrase this query as follows.
2(, Count(), , ) ∶−
Teams(, ), Sponsors(, ), Goals(, , ) Here, we order the answers first b y, then by Count(), and then by and . Semantically, , , and are treated as thegrouping variables (rather than free variables), where each combination of values defines a group of tuples over(, , , , ) andCount() counts the tuples in the group.
CQs with some common aggregate functions can be translated into ordinary CQs over
annotated databases5[
3(, ⋆, , ) ∶−
Teams(, ), Sponsors(, ), Goals(, , ) Ignoring the⋆ symbol, this is an ordinary CQ applied when the database is annotated by elements from the domain of a commutative semiring(, ⊕, ⊗, 0̄, 1̄). In a nutshell, 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. We can use diferent semirings and annotations to compute diferent aggregate functions like sum, min, and max. In the case of 3, for instance, the semiring is(ℤ, +, ⋅, 0, 1) and each tuple is annotated simply with the number 1. Moreover, we order by, then by the annotation, and then b yand . Notationally, we specify the annotation position by the symbo⋆l and refer to the query as a C⋆Q,which is defined similarly to a CQ but with⋆ added to the head. More precisely, we write a C⋆ Qas (,⃗⋆, )⃗ to denote that⋆ is between the (possibly empty) sequence s⃗ and ⃗ of head variables.
We now describe our results on direct access for⋆Cs.QAs conventionally done in fine-grained analysis of queries, we use the RAM model8][. We assume logarithmic space for representing each element of the semiring, and constant time for the operatio⊕nsand ⊗. We also assume that the semiring domain is ordered, and comparison is in constant time.
We begin with the case where the ordedroes not involve the annotation. Equivalently, we discuss CQ⋆s of the form(,⃗⋆) . The following theorem states that, in this case, the results of Carmeli et al.4[] continue to hold for annotated databases. The theorem refers toHtYhPeERCLIQUE and SparseBMM hypotheses, which are common assumptions of lower bounds in ifne-grained complexity. (We refer the reader to Carmeli et a4l]. f[or details.) Theorem 1. Let (, ⊕, ⊗, 0̄, 1̄) be a commutative semiring and (,⃗⋆) a CQ⋆. 1. If is free-connex and with no disruptive trio, then direct access for is in ⟨loglinear, log⟩ on -databases. 2. Otherwise, if is also self-join-free, then direct access for is not in ⟨loglinear, log⟩, assuming the HYPERCLIQUE hypothesis (in case is cyclic) and the SparseBMM hypothesis (in case is acyclic).
The following theorem states a lower bound in an extremely simple query (Cartesian product)
for the semirings used to compute the aggregates count, sum, min, and max, assuming the
3SUM conjecture [
Theorem 2. Let (, ⊕, ⊗, 0̄, 1̄) be one of the counting, numerical, max tropical, or min tropical semirings. Direct access for the CQ⋆ (⋆, , ) ∶− (), ( ) is not in ⟨loglinear, log⟩ over databases, assuming the 3SUM conjecture.
Theorem2 implies that, to obtain evaluation algorithms⟨ilnoglinear, log⟩ while incorporating the annotation in the order, we need to restrict the class o⋆fsCoQr make assumptions on the annotated database. In the following theorem, we restrict the structure of th⋆e. CWQe also make the mild assumption that the semiring is⊗-monotone, that is, the function is monotone for every ∈ , where ∶ → is defined by ( ) = ⊗ .
Theorem 3. Let (, ⊕, ⊗, 0̄, 1̄) be a ⊗-monotone commutative semiring, and (,⃗⋆, )⃗ a freeconnex CQ⋆ with no disruptive trio. If every atom of contains either all variables of ⃗ or none of them, then direct access for is in ⟨loglinear, log⟩.
As an example, the CQ⋆ ( , , ⋆, , ) ∶− ( , ), (, , ), ( , ) databases annotated with the numerical semiring. is in ⟨loglinear, log⟩ over
The final result that we explain in this section holds under two assumptions that we explain next. For the first assumption, consider the aggregate query
( Max( ), , ) ∶− (, ), ( ) When translating into a CQ⋆, we obtain(⋆, , ) ∶− (), ( ) overℚ-databases annotated by the max tropical semiring(ℚ∪{−∞}, max, +, −∞, 0). Hence, according to Theorem2, we translate the problem into an intractable one. Nevertheless, direct access fboyr(⋆, , ) is, in fact, in ⟨loglinear, log⟩. This discrepancy stems from the fact that the hardness in Theore2mrelies on the annotation of tuples from bot h and . Yet, in our translation, al-lfacts are annotated b1y. The resulting -database is such that every fact is annotated b1̄y(the multiplicative identity), with the exception of one relation. We call such a-database -annotated.
The second assumption is that the operatio⊕n is idempotent, that is, for ever y in the domain we have that ⊕ = . This is the case when we start with the aggregate functions min and max, for example.
The following theorem states that, under the above assumptions, we can efectively classify every CQ⋆ without self-joins into two categories:
2. CQ⋆s where direct access is not in⟨loglinear, log⟩ under standard complexity assumptions and under the assumption that the domai n contains the domain of natural numbers. (In fact, it sufices that we can generate an infinite increasing sequence of elements in .) This is done by converting the C Q⋆ into an ordinary C Q0, so that direct access for the two is computationally equivalent. We can then use previous resu4l]tsto[ determine the feasibility of eficient direct access.
Theorem 4. Let (, ⊕, ⊗, 0̄, 1̄) be a ⊕-idempotent commutative semiring. There exists a polynomialtime algorithm that takes as input a free-connex CQ⋆ without self-joins and a relation symbol of , and produces a full acyclic CQ 0 without self-joins, so that the following hold. 1. If 0 has no disruptive trio, then direct access for over -annotated -databases is in ⟨loglinear, log⟩. 2. Otherwise, in the case where ℕ ⊆ , direct access for over -annotated -databases is not in ⟨loglinear, log⟩, assuming the SparseBMM hypothesis.
(⋆, 1, 2, 3) ∶− ( 1, 3, 3), ( 2, 3), ( 3, 1), ( 1, 2) The translation of theore4mreduces direct access for on -annotated -databases to direct access for the following CQ:
0( , 1, 2, 3) ∶− ′( 1, 3, ), ′( 2, 3, ), ′( 3, ) Since 0 does not have a disruptive trio, direct access for0 is in ⟨loglinear, log⟩, and therefore, so is direct access fo r on -annotated -databases.
See the full version of this paper11[] for more details about the results described here. The work of Idan Eldar and Benny Kimelfeld was supported by the Israel Science Foundation (ISF), Grant 768/19, and the German Research Foundation (DFG) Project 412400621 (DIP program).