Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins

• $\mathrm{■}$

  We introduce PCs as a generalization of DCs and provide two algorithms to determine PCs in polynomial time as well as to partition the data to witness these constraints. One is exact and runs in quadratic time, while the second runs in linear time and provides a constant factor approximation.

• $\mathrm{■}$

  We develop new bounds on the output size of a join query. These bounds use DC-based bounds as a black box and naturally extend them to incorporate PCs. We show that these bounds are asymptotically tighter than bounds that rely on DCs alone. Further, we show that if the DC-based bounds are tight, then the PC-based bounds built on top of them will be tight as well.

• $\mathrm{■}$

  Using WCOJ algorithms for DCs as a black box, we provide improved join algorithms that are worst-case-optimal relative to the tighter PC-based bound. Notably, if an algorithm were proposed that is worst-case optimal relative to a tight DC-based bound, then this would immediately result in a WCOJ algorithm relative to a tight PC-based bound.

In Section 5, we provide some basic definitions and background. We formally introduce and discuss PCs in Section 3 and compute them on common benchmark data. In Section 4, we illustrate the benefits of the PC framework by thoroughly analyzing a concrete example. The developed techniques are then extended in Section 5 and applied to arbitrary CQs. We conclude and give some outlook to future work in Section 6. Full proofs of some results are deferred to the technical report [8], and we instead focus on providing intuition in the main body.

We assume the reader is familiar with relational algebra, in particular with joins, projections, and selection, which will respectively be denoted by $\mathrm{⨝},\pi ,$ and $\sigma$. In the context of the present paper, a (conjunctive) query (CQ), denoted using relational algebra, is an expression of the form

In this expression, each $R_i({𝐙}_i)$ is a relation over the set of variables ${𝐙}_i$, and $Q(𝐙)$ is the output of the query where $𝐙={\bigcup }_i{𝐙}_i$. Thus, we only consider full conjunctive query. When clear from the context, we omit the reference to the set of variables and simply write $R_i$ and $Q$. We also use $Q$ to refer to the whole CQ. A database instance $I$ for $Q$ is comprised of a concrete instance for each $R_i$, i.e., a set of tuples (also denoted by $R_i$) where each tuple ${\text{z}}_i$ contains a value for each variable in ${𝐙}_i$. The set of values appearing in $I$ is referred to as $dom$, the domain of $I$. Furthermore, let $dom(Z)$ be the values assigned to $Z\in \text{Z}$ by some relation $R_i$ and, for $\text{Y}\subseteq \text{Z}$, $dom(\text{Y}):={\times }_{Y\in \text{Y}}dom(Y)$. For a particular database instance $I$, we denote the answers to a CQ, i.e., the join of the $R_i$, as a relation $Q^I(𝐙)$. Lastly, a join algorithm $𝒜$ is any algorithm that receives a query $Q$ and a database instance $I$ as input and outputs the relation $Q^I(𝐙)$.

In recent years, there has been a series of novel approaches to bound the size of $Q^I(𝐙)$ based on the structure of the query $Q$ and a set of statistics about the database instance $I$. For full conjunctive queries, this recent round of work began with the AGM bound [2]. This bound takes the size of each input relation as the statistics and connects the size of the result to a weighted edge covering of the hypergraph induced by $Q$. Later bounds extended this approach by considering more complex statistics about the input relations. Functional dependencies were investigated first in [14]. These were then generalized to degree constraints (DCs) in [18] and degree sequences (DSs) in [9, 10, 17]. Our work in this paper continues in this vein by generalizing degree constraints further to account for the benefits of partitioning relations. So, we begin by defining degree constraints below.

In addition to generalizing DCs, our work is able to refine any of the previous bounding methods for DCs by incorporating them into our framework. Therefore, we introduce a general notation for DC-based bounds.

Throughout this work, we will make specific reference to the combinatorics bound which we describe below. While it is impractical, this bound is computable and tight which makes it useful for theoretical analyses.

In this work, we make two minimal assumptions about bounds and statistics. First, we assume that cardinality bounds are finite by assuming that every variable in the query is covered by at least one cardinality constraint. Second, we assume that there is a bound on the growth of the bounds as our statistics increase. Formally, for a fixed query $Q$, we assume that every cardinality bound $CB$ has a function $f_Q$ such that for any $\alpha \in {ℝ}^{+}$ and degree constraints DC we have $CB(Q,\alpha \cdot \text{DC})\le f_Q(\alpha )\cdot CB(Q,\text{DC})$. Usually, cardinality bounds are expressed in terms of power products of the degree constraints [2, 14, 17]. In that case, $f_Q=O({\alpha }^c)$ for some constant $c$.

Lastly, we will also incorporate existing work on worst-case optimal join (WCOJ) algorithms. Each WCOJ algorithm is optimal relative to a particular cardinality bound, and we describe that relationship formally as follows:

Note that some algorithms fulfill a slightly looser definition of worst-case optimal by allowing additional poly-logarithmic factors [19]. These algorithms can still be incorporated into this framework, but we choose the stricter definition to emphasize that we do not induce additional factors of this sort.

Much of the recent work on WCOJ algorithms can be categorized as variable-at-a-time (VAAT) algorithms. Intuitively, a VAAT computes the answers to a join query by answering the query for an increasingly large number of variables. This idea is at the heart of Generic Join [22], Leapfrog Triejoin [24], and NPRR [21]. We define this category formally as follows. For an arbitrary query $Q(\text{Z})\leftarrow R_1\mathrm{⨝}\mathrm{\dots }\mathrm{⨝}{R}_k$, let $Q_i$ denote the sub-query

for an ordering $Z_1,\mathrm{\dots },Z_r=\text{Z}$.

It suffices to provide a collection of databases $ℐ$ such that $I\models \text{DC}$ and $|Q_{\mathrm{⬡}}^I|=\mathrm{\Omega }(n^{\frac{4}{3}})$ for $I\in ℐ$. To accomplish this, we introduce a new relation $R_{X,Y,Z}(X,Y,Z)$ with $|dom(X)|=|dom(Z)|=n^{\frac{2}{3}}$ and $|dom(Y)|=n^{\frac{1}{3}}$. Intuitively, think of $R_{X,Y,Z}$ as a bipartite graph from the domain of $X$ to the domain of $Z$ where $Y$ identifies the edge for a given $x\in dom(X)$ or $z\in dom(Z)$. Thus, every $x\in dom(X)$ is connected to $n^{\frac{1}{3}}$ neighbors in $dom(Z)$ and, due to symmetry, also the other way around.

Therefore, the constraints $DC(XY,XYZ,1)$, $DC(YZ,XYZ,1)$, and $CC(n)$ are satisfied over $R_{X,Y,Z}$. Thus, we can use a relation of this type for $R_1,R_2,R_3$. Concretely, we use this relation in the following way: $R_1=R_{A,W,B},R_2=R_{B,U,C},R_3=R_{C,V,A}.$ Thus, for each ($n^{\frac{2}{3}}$ many) $a\in dom(A)$ there are $n^{\frac{1}{3}}$ many matching $b\in dom(B)$ and possibly up to $n^{\frac{1}{3}}$ many matching $c\in dom(C)$. Thus, in total, there may be up to $n^{\frac{4}{3}}$ answers to $R_1\mathrm{⨝}{R}_2\mathrm{⨝}{R}_3$. To accomplish this also for $Q_{\mathrm{⬡}}$, we only have to make sure that the variables $U,V,W$ also join in $R_4$. For that, we simply set $R_4=dom(U)\times dom(V)\times dom(W)$. This relation then satisfies its cardinality constraint. (Note that it does not satisfy its PC.) $◀$

We now provide an algorithm (Algorithm 1) that enumerates $Q_{\mathrm{⬡}}$ in linear time for databases with the PC on $R_4$. This proves that the output size is linear, simultaneously completing our proof of claim 1 and claim 2. Algorithm 1 first decomposes $R_4$ into three parts with one DC on each part. For this, we apply a linear time greedy partitioning algorithm (for more details see Algorithm 2) and show that it results in partitions whose constraints are within a factor of 3 from the optimal PC. Then, for each part, a variable order is selected to take advantage of all DCs. As an example, for the part $R_4^W(U,V,W)$, there are at most 3 matching $(u,v)\in dom(U,V)$ pair for each value of $w\in dom(W)$. Thus, starting with a tuple $(a,w,b)$ of $R_1$, we can use this fact to determine these values for $u,v$ and then combine this with $D{C}_{R_2}(BU,BUC,1)$ to determine the unique value for $c$. By this reasoning, all of the inner for-loops iterate over a single element or 3 pairs of elements. Thus, the nested loops are linear in their total runtime. We defer the formal proof to the technical report [8].

Lemma 11 and Lemma 12 together prove the first two claims of Theorem 10. This shows that PCs have an asymptotic effect on query bounds and that we can take advantage of PCs to design new WCOJ algorithms to meet these bounds. Nevertheless, one might wonder whether the variable elimination idea of established WCOJ algorithms can already meet the improved bound and, in fact, achieve optimal runtimes. Proving the third claim in Theorem 10, we show that they cannot and, thus, the new techniques have to be employed. Specifically, we show that VAAT algorithms (Definition 5) require time $\mathrm{\Omega }(n^{1.5})$ to compute $Q_{\mathrm{⬡}}$ on database instances satisfying the PCs.

It suffices to provide a collection of databases $ℐ$ such that $I\models \text{PC}$ and ${\max }_i|Q_{\mathrm{⬡}i}^I|=\mathrm{\Omega }(n^{1.5})$ for databases $I\in ℐ$ and arbitrary ordering of the variables. To that end, we introduce two relations, a relation $C_{X,Y,Z}(X,Y,Z)$ and a set of disjoint paths $P_{X,Y,Z}(X,Y,Z)$. For $P_{X,Y,Z}(X,Y,Z)$, the domains of $X,Y,Z$ are of size $\mathrm{\Theta }(n)$ and $P_{X,Y,Z}$ simply matches $X$ to $Y$ and $Z$ such that each $d\in dom(X)\cup dom(Y)\cup dom(Z)$ appears in exactly one tuple of $P_{X,Y,Z}$. On the other hand, think of $C_{X,Y,Z}$ as a complete bipartite graph from the domain of $X$ to the domain of $Y$ and $Z$ uniquely identifies the edges. Thus, $|dom(X)|=|dom(Y)|=\mathrm{\Theta }(\sqrt{n})$ while $|dom(Z)|=\mathrm{\Theta }(n)$. Notice that for both relations, $DC(XY,XYZ,1),DC(Z,XYZ,1)$ hold. I.e., any pair of variables determine the last variable and there is a variable that determines the whole tuple on its own.

Consequently, the disjoint union of relations $C$ and $P$ multiple times (with permutated versions of $C$), e.g.,

satisfies $P{C}_R(\{X,Y,Z\},XYZ,1)$ and $DC(S_1{S}_2,XYZ,1)$ for any $S_1{S}_2\subseteq XYZ$.

Thus, we can set $R_1,R_2,R_3,R_4$ to be the disjoint union of $P$ and all permutations of the relation $C$. Now, let $X_1,\mathrm{\dots },X_6$ be an arbitrary variable order for $Q_{\mathrm{⬡}}$. Then, a VAAT algorithm based on this variable order at least needs to compute the sets:

Let us consider the set ${\mathrm{⨝}}_i{\pi }_{X_1\mathrm{\cdots }{X}_4}{R}_i$. There are two cases:

Case 1:

$X_5$ and $X_6$ appear conjointly in a relation. Due to the symmetry of the query and the database, we can assume w.l.o.g, $X_5{X}_6=UV$ and ${\mathrm{⨝}}_i{\pi }_{X_1\mathrm{\cdots }{X}_4}{R}_i={\mathrm{⨝}}_i{\pi }_{ABCW}{R}_i.$ Furthermore, ${\pi }_{ABW}{C}_{A,B,W}\subseteq {\pi }_{ABW}{R}_1$, ${\pi }_{BC}{C}_{B,C,U}\subseteq {\pi }_{BC}{R}_2$, ${\pi }_{AC}{C}_{A,C,V}\subseteq {\pi }_{AC}{R}_3,{\pi }_W{P}_{U,V,W}\subseteq {\pi }_W{R}_4$. Thus, intuitively, for at least $\mathrm{\Omega }(\sqrt{n})$ elements $a\in dom(A)$ there are $\mathrm{\Omega }(\sqrt{n})$ elements $b\in dom(B)$ and $\mathrm{\Omega }(\sqrt{n})$ elements $c\in dom(C)$ that all join, and for each pair $a,b$ there is an element $w\in dom(W)$ that fits. In total, $|{\mathrm{⨝}}_i{\pi }_{ABCW}{R}_i|=\mathrm{\Omega }(n^{1.5})$.

Case 2:

$X_5$ and $X_6$ do not appear conjointly in a relation. Due to the symmetry of the query and the database, we can assume w.l.o.g, $X_5{X}_6=AU$ and ${\mathrm{⨝}}_i{\pi }_{X_1\mathrm{\cdots }{X}_4}{R}_i$ $={\mathrm{⨝}}_i{\pi }_{BCVW}{R}_i.$ Furthermore, ${\pi }_{BW}{C}_{B,W,A}\subseteq {\pi }_{BW}{R}_1$, ${\pi }_{BC}{C}_{B,C,U}\subseteq {\pi }_{BC}{R}_2$, ${\pi }_{CV}{C}_{C,V,A}\subseteq {\pi }_{CV}{R}_3,{\pi }_{VW}{C}_{V,W,U}\subseteq {\pi }_{VW}{R}_4$. Thus, intuitively, for at least $\mathrm{\Omega }(\sqrt{n})$ elements $b\in dom(B)$ there are $\mathrm{\Omega }(\sqrt{n})$ elements $w\in dom(W)$, $\mathrm{\Omega }(\sqrt{n})$ elements $v\in dom(V)$ and, $\mathrm{\Omega }(\sqrt{n})$ elements $c\in dom(C)$ that all join. In total, $|{\mathrm{⨝}}_i{\pi }_{BCVW}{R}_i|=\mathrm{\Omega }(n^2)$.

$◀$