Generalized Covers for Conjunctive Queries

We summarize our contributions as follows:

• $\mathrm{■}$

  We generalize the notion of a cover of a query result to consider multiple tree decompositions (Section 4). We prove several interesting properties for covers, and show that given a cover of size $K$ we can spend $O(|K|)$ preprocessing time to enumerate the query output with constant delay.

• $\mathrm{■}$

  We present a simple greedy algorithm (Section 5) that, given the query output, produces an asymptotically optimal cover in time linear w.r.t. the query output. Moreover, we show an upper bound that uses not only the input size $N$ as a parameter, but any combination of degree constraints, including different cardinalities, functional dependencies, and degree bounds.

• $\mathrm{■}$

  We provide a lower bound (Section 6) that asymptotically matches our upper bound. The lower bound uses a technically interesting connection to disjunctive Datalog rules to find a worst-case instance for a cover.

• $\mathrm{■}$

  Finally, we show in Section 7 how we can use a cover to produce a semiring circuit of size linear to the cover size for the provenance polynomial of the query for any idempotent semiring. A semiring circuit can be thought as a factorization of the query output (more precisely, it is a factorization of the polynomial associated with the query output), with the additional flexibility that it can consider different tree decompositions in its internal representation.

As shown in [13], covers over a single tree decomposition are related to $d$-representations over the same tree decomposition. $d$-representations (and $f$-representations) are also lossless representations of query outputs, which allow for efficient enumeration, aggregation, and even ML model computation [18]. Query outputs can also be concisely stored using circuits [9, 1] – these circuits represent the polynomial corresponding to the join query and can be evaluated under different semiring semantics. As we will show later in the paper, analogous to the connection between covers and $d$-representations, there is also a direct connection between generalized covers and semiring circuits.

Recent work has also looked at how we can further decrease the size of a representation by trading off the enumeration delay guarantee [7, 19, 6]. Such a tradeoff allows for asymptotically smaller succinct data structures, but with an increased possible delay when outputting two consecutive outputs. Even though it would be theoretically possible to consider covers with weaker enumeration guarantees, in this work we focus only on constant delay.

Several algorithms on join computation use a two-phase framework where a preprocessing phase is followed by an output enumeration phase [3]. For instance, for any join query with fractional hypertree width $\mathrm{𝖿𝗁𝗐}$, we need $O(N^{\mathrm{𝖿𝗁𝗐}})$ preprocessing time to achieve constant delay enumeration. The intermediate data structure constructed by the preprocessing phase can be also viewed as a succinct representation of the result; however, it is critical in this case to also have an efficient algorithm to construct the data structure. Recent work has looked at preprocessing time/size and enumeration tradeoffs in this setting [11, 12]. In our paper, even though we construct a very small succinct representation, the runtime can exceed the size of the representation and thus does not lead to a better query evaluation algorithm.

A Conjunctive Query (CQ) $Q$ is an expression associated to a hypergraph $\mathscr{H}=([n],ℰ)$ where $[n]=\{1,\mathrm{\dots },n\}$ and a set $U\subseteq [n]$:

where each $R_e$ is a relation of arity $|e|$, the variables $x_1,x_2,\mathrm{\dots },x_n$ take values in some discrete domain, and ${𝐱}_e:={(x_i)}_{i\in e}$. We say that $Q$ is Boolean if $U=\{\}$ and full if $U=[n]$.

Given a tuple $t$ over $[n]$ and a subset $S\subseteq [n]$, we will use $t[S]$ to denote the projection of the tuple on the attributes in $S$.

We recall the notion of a tree decomposition.

We say that a tree decomposition is non-redundant if no bag is a subset of another; otherwise it is redundant. We let $\mathrm{𝖳𝖣}(\mathscr{H})$ be the set of all non-redundant tree decompositions of $\mathscr{H}$. This set is known to be finite; it can be shown that $|\mathrm{𝖳𝖣}(\mathscr{H})|\le n!$, where $n$ is the number of vertices of the hypergraph (Proposition 2.9 [15]).

Let $n$ be a positive integer. A function $h:2^{[n]}\to {ℝ}_{+}$ is called a set function on $[n]=\{1,2,\mathrm{\dots },n\}$. Given a discrete random variable $X$ with support in $𝒳$ and probability distribution $p:𝒳\to [0,1]$, its entropy is defined as $H(X)=-{\sum }_{x\in 𝒳}p(x)\log p(x)$. When the probability distribution is uniform in the support set, then $H(X)=\log |𝒳|$. Given a set of random variables $X_1,\mathrm{\dots },X_k$, the joint entropy $H(X_1,\mathrm{\dots },X_k)$ is defined as the entropy of the random variable $Y$ that represents the tuple $(X_1,\mathrm{\dots },X_k)$. A set function is an entropic function of order $n$ if there exist random variables $A_1,\mathrm{\dots },A_n$ such that $h(S)=H({(A_i)}_{i\in S})$ for any $S\subseteq [n]$. We denote by ${\mathrm{\Gamma }}_n^{\ast }$ the set of all entropic functions of order $n$, and ${\overline{\mathrm{\Gamma }}}_n^{\ast }$ the topological closure of ${\mathrm{\Gamma }}_n^{\ast }$.¹¹1The topological closure of a set $S$ is defined as the smallest closed set that contains $S$. The important property of ${\overline{\mathrm{\Gamma }}}_n^{\ast }$ is that it is a convex cone and hence characterized by the (infinitely many) linear inequalities it satisfies.

Let $\mathrm{𝖣𝖢}$ be a set of triples $(X,Y,N_{Y|X})$ for some $X\subset Y\subseteq [n]$ and $N_{Y|X}\in \mathbb{N}$ that encodes a set of degree constraints. A database instance $I$ over the relational schema ${\{R_e\}}_{e\in ℰ}$ satisfies the constraints if for every relation $R_e$ in $I$ with $X\subseteq Y\subseteq e$ and every tuple $t$ defined over schema $X$, we have $|{\pi }_Y(R_e⋉t)|\le N_{Y|X}$. A constraint of the form $(\mathrm{\varnothing },e,N_e)$ is simply a cardinality constraint that says that relation $R_e$ has size at most $N_e$. The degree constraints on an instance can be translated as constraints on entropic functions as follows:

where $h(Y|X):=h(Y)-h(X)$. For a given set of degree constraints $\mathrm{𝖧𝖣𝖢}$, we define the “scaled-up” degree constraints $\mathrm{𝖧𝖣𝖢}\times k$ as the same set of constraints but with all the degree bounds multiplied by $k$. It will be also helpful to define the entropic constraints in the case we are only given a uniform cardinality constraint (input size):

We now define the entropic width (defined in [9]) and degree-aware entropic width (defined in [15] as eda-subw) w.r.t. a set of tree decompositions $𝕋$ respectively:

When $𝕋=\mathrm{𝖳𝖣}(\mathscr{H})$, we obtain the standard notions of (degree-aware) entropic width.

We use the uniform-cost RAM model where data values as well as pointers to databases are of constant size. Our runtime analysis will consider data complexity (where the query is considered fixed) unless otherwise stated.

This follows immediately from the fact that for every tree decomposition $(𝒯,\chi )$ and relational instance $K$, we have $K\subseteq {⨝}_{t\in V(𝒯)}({\pi }_{\chi (t)}K)$. $◀$

We say that a cover $K$ is minimal w.r.t. $𝕋$ if there is no strict subset $K^{\prime }⊊K$ that is also a cover w.r.t. $𝕋$ ²²2We should note here that in [13] a cover always refers to a minimal cover. In this paper, however, we will also consider covers that may not be minimal.. A cover is minimum w.r.t. $𝕋$ if it has the smallest possible size across all covers w.r.t. $𝕋$.

We will construct the sets ${\overline{K}}_{\beta }$ following the construction of $\overline{K}$ in algorithm 1. Initially, all ${\overline{K}}_{\beta }$ are empty. Consider the point where a new tuple $t$ is added in $\overline{K}$ in line 4. Then, for every decomposition $(𝒯,\chi )\in 𝕋$ there must exist some bag $v\in V(𝒯)$ such that $t[\chi (v)]\notin {\pi }_{\chi (v)}(\overline{K})$ (if there is more than one such bag, we choose one arbitrarily). Consider the bag selector $\beta$ such that its image is exactly this set of bags, and add $t$ to ${\overline{K}}_{\beta }$. It is easy to see that, for every tuple $t^{\prime }\in {\overline{K}}_{\beta }$ and $B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$, we have $t^{\prime }[B]\in {\pi }_B(\overline{K})$ and thus it must be that $t[B]\ne t^{\prime }[B]$. $◀$

Equipped with the above two lemmas, we can now prove an upper bound on the size of the cover constructed via algorithm 1.

From Lemma 13, we have that ${\sum }_{\beta \in {ℳ}_{𝕋}}|{\overline{K}}_{\beta }|=|\overline{K}|$. Hence, there exists a set ${\overline{K}}_{\beta }$ with size $|{\overline{K}}_{\beta }|\ge |\overline{K}|/|{ℳ}_{𝕋}|$ such that for any two tuples $t,t^{\prime }\in {\overline{K}}_{\beta }$ it holds that $t[B]\ne t^{\prime }[B]$ for every $B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$. The set ${\overline{K}}_{\beta }\subseteq Q(D)$ satisfies all degree constraints, since it is a subset of $Q(D)$ which also satisfies all degree constraints. Now, take a probability distribution over $[n]$ that is uniformly random for ${\overline{K}}_{\beta }$, that is, each tuple in ${\overline{K}}_{\beta }$ is chosen independently with the same probability. Let $\overline{h}$ denote the entropy of this distribution. Note that by construction, $\overline{h}\in {\overline{\mathrm{\Gamma }}}_n^{\ast }\cap \mathrm{𝖧𝖣𝖢}$. Moreover, because the projections of the tuples on the bags of $B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$ are disjoint, $\log |{\overline{K}}_{\beta }|=\overline{h}(B)$.

Now, consider any tree decomposition $(𝒯,\chi )\in 𝕋$; then, there exists a bag $v\in V(𝒯)$ such that $B=\chi (v)\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$:

Taking the $\min$ over all tree decompositions in $𝕋$, we can write:

The bound in the statement follows from the fact that $|{\overline{K}}_{\beta }|\ge |\overline{K}|/|{ℳ}_{𝕋}|$. $◀$

Combining the above corollary with Theorem 8, we obtain that we can construct a data structure of size only $O({|D|}^{\text{entw}})$ such that we can provide a constant-delay enumeration guarantee of the output $Q(D)$. Note that the best-known such data structure has size $O({|D|}^{\text{subw}})$, where subw is the submodular width of the query. However, it holds that $\text{entw}\le \text{subw}$ [14].³³3It is not known whether there is some query where there is a gap between the two width measures. Of course, we do not know whether we can construct this data structure in time $O({|D|}^{\text{entw}})$, since our algorithm needs time linear w.r.t. the output size, which can be asymptotically larger. However, as the next proposition shows, we can construct a (potentially larger) cover in time and size $O({|D|}^{\text{subw}})$ using the PANDA algorithm as a blackbox.

We will construct a model of $P_{\beta }$ from the cover $K$ by taking $T_B:={\pi }_B(K)$ for every $B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$. Clearly, $|P_{\beta }|={\max }_B|T_B|\le |K|$. To show that ${\{T_B\}}_{B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )}$ is a model for $P_{\beta }$, consider any tuple $t\in Q(D)$. Then, since $K$ is a cover, there exists a tree decomposition $(𝒯,\chi )$ such that $t\in {⨝}_{v\in V(𝒯)}{\pi }_{\chi (v)}(K)$. Since $\beta$ is a bag selector, there exists $B\in \mathrm{𝗂𝗆𝖺𝗀𝖾}(\beta )$ for which $\beta (𝒯,\chi )=B$, and for this bag, $t[B]\in {\pi }_B(K)=T_B$. $◀$

We will use the lower bound construction for an output of a disjunctive rule [15] and follow the proof of Theorem 3.7 in [9]. Let ${𝐁}_{𝕋}$ be the collection of images of all $\beta \in {ℳ}_{𝕋}$. Then, we can bound ${\text{da-entw}}_{𝕋}(\mathscr{H},\mathrm{𝖧𝖣𝖢}\times k)$ as follows:

For a bag selector $\beta$, consider the disjunctive rule $P_{\beta }$ as constructed in 19. We know from Lemma 4.4 in [15] that for any $ϵ>0$ there exists an integer $k_{\beta }>0$ and an instance $I_{\beta }$ such that

Consider now the $k_0$ that maximizes $k_{\beta }$ over all bag selectors in ${ℳ}_{𝕋}$, and let ${\beta }_0$ the bag selector that maximizes the right-hand side of the first inequality. Then,

To conclude the proof, observe that from Lemma 19 we have that for a cover $K$, it holds that $\log |K|\ge \log |P(I_{{\beta }_0})|$. $◀$

This lower bound matches (asymptotically) the upper bound in the previous section. When the degree constraints correspond to a uniform cardinality constraint $N$ on each relation and $𝕋$ is the set of all non-redundant tree decompositions, then we obtain from Theorem 21 that there exists an instance where any cover has size $\mathrm{\Omega }(N^{\text{entw}})$.

For a decomposition $T=(𝒯,\chi )\in 𝕋$, we will first augment it with a mapping ${\mu }_T:ℰ\to V(𝒯)$; this mapping assigns each hyperedge of $\mathscr{H}$ to a node $v$ in the tree decomposition. For a node $v\in V(𝒯)$ and a tuple $t$, we can now define a new variable

In other words, the new variable corresponds to taking the semiring product of the input tuples for the hyperedges we have assigned to the bag $v$. If there is no hyperedge assigned to $v$, then $y_t^v:=\mathrm{𝟏}$. Any variable $y_t^v$ can be always encoded via a constant-size subcircuit that computes a constant-size semiring product.

Using the definition of a cover, we can now write:

At this point, we can see that it suffices to build a subcircuit for each tree decomposition $(𝒯,\chi )\in 𝕋$ and then sum their output gates to obtain the final output. Since $|𝕋|$ is data-independent, the number of these sum-gates is a constant. Hence, our problem reduces to constructing a circuit for the polynomial

This corresponds to constructing a circuit for the polynomial of an acyclic query with body ${\bigwedge }_{v\in V(𝒯)}{S}_{\chi (v)}({𝐱}_{\chi (v)})$, where each input relation $S_{\chi (v)}$ is constructed by computing the projection on the cover ${\pi }_{\chi (v)}K$. Any such projection can be computed in linear time $O(|K|)$. Additionally, from [9] (Theorem 4.1), we know how to construct this circuit in time linear w.r.t. the size of the input, which is $O(|K|)$. Moreover, the size of the circuit is bounded by the input size, and thus is also $O(|K|)$. $◀$