Factorised Representations of Join Queries:
Tight Bounds and a New Dichotomy

We deploy a similar “recipe” for proving both of our main results. We begin with a known characterisation of what it means for a structure $𝒜$ to have high $x$-width, for $x\in \{\text{tree, submodular}\}$. In both cases, the characterisation is of the form “there is a subset of the universe of $𝒜$ which is highly connected”. What highly connected means depends on the notion of width but the idea is that this subset is hard to disconnect, for instance by removing vertices or edges. Next we have to define some bad instance: that is some structure $ℬ$ such that there is no small $\{\cup ,\times \}$-circuit for $\mathrm{Hom}(𝒜,ℬ)$. We do this by using randomness. This is relatively straightforward for Theorem 2; we first describe this proof on a high level.

For this we use the characterisation of treewidth in terms of a highly connected set from [43, 44]. This characterisation is also used by Marx to prove a conditional lower bound in the decision setting [35]. He showed that every graph with high treewidth has high “embedding power” and can therefore efficiently simulate a $3$-SAT instance. Thus, under an assumption about how quickly $3$-SAT can be solved, Marx obtains conditional lower bounds on the decision problem which are tight up to a logarithmic factor in the exponent. As we do not need to use embeddings we obtain lower bounds in our setting which are tight up to a constant in the exponent.

Since the arity is bounded, it turns out that the main step reduces to the special case where $𝒜$ is a graph. Here we can set $ℬ$ to be a random graph where each edge is included independently with probability a half. There are two key ideas. First, the set $\mathrm{Hom}(𝒜,ℬ)$ is big; this is essential otherwise we can get a small representation with a trivial circuit which lists every homomorphism. Second, $ℬ$ contains (with high probability) no big bicliques. Intuitively, this makes it hard for a $\{\cup ,\times \}$-circuit to significantly “compress” $\mathrm{Hom}(𝒜,ℬ)$.

We deployed a similar idea in [12] to prove a lower bound where the left-hand structure is a complete graph. The reason we can in general improve the dependence on the treewidth compared with [12] is that we use a different method to lower bound the size of circuits; we deploy a framework based on tools from communication complexity that has been successfully deployed in knowledge compilation, see e.g. [6, 17, 14, 24, 47], since its introduction in [15]. Using this framework we do not directly reason about circuits – as is done in [12] – but instead about sets of combinatorial rectangles (see Section 4). This allows us to directly reason about each left-hand-side instance $𝒜$; in contrast in our previous work we only directly reason about the case where $𝒜$ is a $k$-clique and then perform a series of reductions which crucially rely on the Excluded Grid Theorem of Robertson and Seymour [45]. We show that if we partition the vertices of a high treewidth graph $𝒜$, such that the highly connected set is evenly split between the two sides of the partition, then there must be a large number of edges crossing the partition. This is the key to us proving our lower bound.

The proof of Theorem 3 follows a similar pattern but we have to be more careful about defining our “bad instances”, since we are now working with higher arity structures. In particular, we have to control the size of each relation in $ℬ$ since if they get too big compared to $|\mathrm{Hom}(𝒜,ℬ)|$ it will destroy the lower bound. To do this we exploit the existence of a highly connected set in $𝒜$ and use this explicitly in our construction of $ℬ$. Here we use the same characterisation of highly connectedness used in [37] to reason about the decision setting.

Knowledge compilation originally emerged as a sub-field of artificial intelligence concerned with the efficient representation of Boolean functions [23]. Within recent years, concepts from this area have been applied more widely, particularly within database theory (again see the survey [2]) and the related area of constraint satisfaction [12, 9, 34, 38, 3]. An advantage of this approach is that if we can represent our query answer as a (particular type of) $\{\cup ,\times \}$-circuit, then we can leverage known results to perform e.g. enumeration [42, 1], sampling [46], direct access [18] or (approximate) (weighted) counting [32, 4, 39] efficiently.⁴⁴4Note that while some of these results are only shown for circuits computing sets of Boolean functions, as is observed in the survey [2], it is straightforward to adapt them to our more general setting. These circuits (and variants) have proved useful for many other aspects of database theory: for instance for MSO queries [1], incremental view maintenance [7, 40], probabilistic databases [31] and representing query provenance [41].

Recent work [33, 25, 26, 13] studies the algebraic circuit size for sum-product polynomials over some semiring. While algebraic circuits are generally incomparable to $\{\cup ,\times \}$-circuits, it turns out that multilinear circuits over the Boolean semiring considered in [25, 26] can be translated to $\{\cup ,\times \}$-circuits with only a polynomial blow-up, but not vice versa. In this sense, our lower bounds hold in a strictly more general model and also imply lower bounds for these algebraic circuits, see the full version.

As observed by Feder and Vardi [27] the problem of deciding if there is a homomorphism between two relational structures $𝒜$ and $ℬ$ is a generalisation of the constraint satisfaction problem. Given the generality of this problem it is unsurprisingly NP-complete. Therefore, research has focused on finding tractable restrictions, where we demand $𝒜\in 𝖠$ and $ℬ\in 𝖡$ for classes of structures $𝖠,𝖡$; we denote this problem by $\mathrm{𝖧𝖮𝖬}(𝖠,𝖡)$. If we set $𝖠$ to be the class of all structures _ then we have a complete (conditional) understanding of when we have polynomial time tractability for $\mathrm{𝖧𝖮𝖬}(\text{\_},𝖡)$ [16, 48].

However, for left-hand-side restrictions, where we set $𝖡=\text{\_}$ and ask for what $𝖠$ we have polynomial time solvability, no dichotomy is known. Still, a lot of work has been done on such restrictions. If $𝖠$ has bounded arity we know that $\mathrm{𝖧𝖮𝖬}(𝖠,\text{\_})$ is in polynomial time iff there is a constant bounding the treewidth of the homomorphic core of every structure in $𝖠$ [28, 35]. Moreover, for the counting variant the criterion is that $𝖠$ has bounded treewidth [20]. In the general case, we do have a conditional dichotomy in the parametrised setting: there the correct criterion is that $𝖠$ has bounded submodular width [37]. Our main results imply comparable dichotomy results for the problem of representing $\mathrm{Hom}(𝒜,ℬ)$ by a $\{\cup ,\times \}$-circuit; see Section 3.1 for more details.

For $n\in \mathbb{N}$, we write $[n]:=\{1,\mathrm{\dots },n\}$. Given a set $S$ we write $𝒫(S)$ to denote the power set of $S$. Whenever writing $\overline{a}$ to denote a $k$-tuple, we write $a_i$ to denote its $i$-th component; i.e., $\overline{a}=(a_1,\mathrm{\dots },a_k)$. Moreover, we write $\tilde{a}$ to denote the set $\{a_1,\mathrm{\dots },a_k\}$. For a function $f:X\to Y$ and $X^{\prime }\subset X$ we write $f{\upharpoonright }_{X^{\prime }}$ to denote the restriction of $f$ to $X^{\prime }$, i.e. $f{\upharpoonright }_{X^{\prime }}:X^{\prime }\to Y$ is defined by $x\mapsto f(x)$ for all $x\in X^{\prime }$. We extend this operation to a set of such functions $F$ by setting $F{\upharpoonright }_{X^{\prime }}:=\{f{\upharpoonright }_{X^{\prime }}\mid f\in F\}$. Given disjoint sets $X,X^{\prime }$ and two functions $f:X\to Y,g:X^{\prime }\to Y^{\prime }$ we define $f\times g:X\cup X^{\prime }\to Y\cup Y^{\prime }$ by:

We will often combine two sets of functions pairwise in this way. Formally, for a set $S$ of functions with domain $X$ and a set $T$ of functions with domain $X^{\prime }$ we define $S\times T:=\{f\times g\mid f\in S,g\in T\}$. We also use $\times$ to denote Cartesian product in the normal sense; we can overcome this seeming mismatch by viewing a function $f:X\to D$ as a tuple with coordinates in bijection with $X$ such that the $x$-th coordinate is $f(x)$.

A hypergraph $\mathscr{H}=(V_{\mathscr{H}},E_{\mathscr{H}})$ is a pair, consisting of a finite set of vertices $V_{\mathscr{H}}$ and a finite set of edges $E_{\mathscr{H}}\subseteq 2^{V_{\mathscr{H}}}$. If $|e|=2$, for every $e\in E_{\mathscr{H}}$, we say that $\mathscr{H}$ is a graph. Via this definition we are implicitly assuming that all graphs are undirected and simple, i.e., that they do not contain self-loops. We write ${𝒦}_k$ for the complete graph on $k$ vertices, which we also call the $k$-clique. Given a hypergraph $\mathscr{H}=(V_{\mathscr{H}},E_{\mathscr{H}})$ and a subset $X\subseteq V_{\mathscr{H}}$, an edge cover of $X$ is a set $S\subseteq E_{\mathscr{H}}$ such that for all $v\in X$ there is some $e\in S$ with $v\in e$. A fractional edge cover of $X$ is the natural fractional relaxation, i.e. a function $s:E_{\mathscr{H}}\to [0,1]$, such that for every $v\in X$, we have that ${\sum }_{e\ni v}s(e)\ge 1$. We write $\mathrm{𝗐𝖾𝗂𝗀𝗁𝗍}(s):={\sum }_{e\in E_{\mathscr{H}}}s(e)$. Then ${\rho }^{\ast }(X)$ – the fractional edge cover number of $X$ – is defined to be the minimum of $\mathrm{𝗐𝖾𝗂𝗀𝗁𝗍}(s)$ over all fractional edge covers of $X$.

We extend functions $f:V_{\mathscr{H}}\to {ℝ}^{\ge 0}$ to subsets of $X\subseteq V_{\mathscr{H}}$ in the natural way, i.e.​ by setting $f(X)={\sum }_{v\in X}f(v)$. A fractional independent set of $\mathscr{H}$ is a map $\mu :V_{\mathscr{H}}\to [0,1]$, such that for every $e\in E_{\mathscr{H}}$, ${\sum }_{v\in e}\mu (v)\le 1$; or equivalently $\mu (e)\le 1$ for every $e\in E_{\mathscr{H}}$. Note that by LP duality the weight $\mu (V_{\mathscr{H}})$ of a maximal fractional independent set $\mu$ agrees with the weight of a minimal fractional edge cover. Now let $𝐒(\mathscr{H})$ be the set of all functions $f:𝒫(V_{\mathscr{H}})\to {ℝ}^{\ge 0}$ with $f(\mathrm{\varnothing })=0$ that satisfy the following properties:

1. 1.

   Monotonicity: $f(S)\le f(T)$ for all $S\subseteq T\subseteq V_{\mathscr{H}}$,

2. 2.

   Edge dominatedness: $f(e)\le 1$ for every $e\in E_{\mathscr{H}}$, and

3. 3.

   Submodularity: $f(S)+f(T)\ge f(S\cap T)+f(S\cup T)$ for every $S,T\subseteq V_{\mathscr{H}}$.

Observe that for every fractional independent set $\mu$ of $\mathscr{H}$ we have $\mu \in 𝐒(\mathscr{H})$.

A tree decomposition of a hypergraph $\mathscr{H}$ is a pair $(𝒯,\beta )$ where $𝒯$ is a tree and $\beta :V_{𝒯}\to 𝒫(V_{\mathscr{H}})$ associates to every node $t\in V_{𝒯}$ a bag $\beta (t)$ such that:

1. 1.

   for every $v\in V_{\mathscr{H}}$ the set $\{t\in V_{𝒯}\mid v\in \beta (t)\}$ is a non-empty connected subset of $V_{𝒯}$ and

2. 2.

   for every $e\in E_{\mathscr{H}}$ there is some $t\in V_{𝒯}$ such that $e\subseteq \beta (t)$.

We write $𝖳(\mathscr{H})$ for the set of all tree decompositions of $\mathscr{H}$. The width of a tree decomposition is ${\max }_{t\in V_{𝒯}}|\beta (t)|-1$ and the treewidth of $\mathscr{H}$ is the minimum width of all $(𝒯,\beta )\in 𝖳(\mathscr{H})$. Note that the $-1$ in the definition of treewidth is there to ensure that trees have treewidth one.

From an algorithmic point of view, the idea of treewidth is that we can perform various bottom-up computations on the tree decomposition. Since we only consider one bag at a time, if the bags are small this can allow for efficient algorithms on small treewidth hypergraphs for problems which are in general intractable. For this, and other reasons, treewidth has become an incredibly influential concept and has inspired many more sophisticated notions of width, see [30] for a survey.

Two such measures are relevant in this paper: fractional hypertree width and submodular width. The fractional hypertree width of a tree decomposition $(𝒯,\beta )$ is defined to be the maximum value of ${\rho }^{\ast }(\beta (t))$ over all $t\in V_{𝒯}$. The fractional hypertree width of a hypergraph $\mathscr{H}$ is the minimum fractional hypertree width over all tree decomposition of $\mathscr{H}$, in symbols

So if $\mathscr{H}$ has low fractional hypertree width then there is a tree decomposition where every bag has small fractional edge cover number.

The definition of submodular width is slightly more involved: if $\mathscr{H}$ has low submodular width then for every $f\in 𝐒(\mathscr{H})$ there is a tree decomposition where every bag evaluates to a small number under $f$. To be precise, the submodular width of $\mathscr{H}$ is defined to be

From the definitions, one can see that $\mathrm{𝗍𝗐}(\mathscr{H})+1\ge \mathrm{𝖿𝗁𝗍𝗐}(\mathscr{H})$. Moreover, Marx proved that $\mathrm{𝖿𝗁𝗍𝗐}(\mathscr{H})\ge \mathrm{𝗌𝗎𝖻𝗐}(\mathscr{H})$ [37, Proposition 3.7.].

A (relational) signature $\sigma$ is a set of relation symbols $R$, each equipped with an arity $r=r(R)$. We assume all signatures are finite. A (finite, relational) $\sigma$-structure $𝒜$ consists of a finite set $A$ (the universe of $𝒜$) and relations $R^{𝒜}\subseteq A^r$ for every $r$-ary relation symbol $R\in \sigma$. The size of $𝒜$ is defined to be $\Vert 𝒜\Vert :={\sum }_{R\in \sigma }|R^{𝒜}|$ and the arity of $𝒜$ is the maximum arity of all relations in $\sigma$.

The Gaifman graph of $𝒜$ is the graph with vertex set $A$ and edges $\{u,v\}$ for any distinct $u,v$ that occur together in a tuple of a relation in $𝒜$. We say $𝒜$ is connected if its Gaifman graph is connected and we will henceforth assume that all structures are connected. All of our results can be easily extended to disconnected structures. The hypergraph of a $\sigma$-structure $𝒜$ is a hypergraph with vertex set $A$ such that $e\subseteq A$ is an edge iff there is a tuple $\overline{e}\in R^{𝒜}$ for some $R\in \sigma$, such that $\tilde{e}=e$.

For $x\in \{\text{tree, fractional hypertree, submodular}\}$, the $x$-width of a structure is the $x$-width of its hypergraph. For a class of structures $𝖠$, we write $\mathrm{𝗍𝗐}(𝖠):={sup}_{𝒜\in 𝖠}\mathrm{𝗍𝗐}(𝒜)$, which may be infinite. If $\mathrm{𝗍𝗐}(𝖠)$ is finite we say that $𝖠$ has bounded treewidth, otherwise we say it has unbounded treewidth. We define the analogous notions for fractional hypertree and submodular width. It is known that there are classes of structures with bounded fractional hypertree width but unbounded treewidth [29] and a class of structures with bounded submodular width but unbounded fractional hypertree width [36]. If there is some integer $r$ such that every structure in $𝖠$ has arity at most $r$, we say that $𝖠$ has bounded arity. In this case, $𝖠$ has bounded treewidth iff $𝖠$ has bounded fractional hypertree width iff $𝖠$ has bounded submodular width.

Finally, a homomorphism from $𝒜$ to $ℬ$ is a function $h:A\to B$ that preserves all relations, i.e., for every $r$-ary $R\in \sigma$ and $\overline{a}=(a_1,\mathrm{\dots },a_r)\in R^{𝒜}$ it holds that $h(\overline{a}):=(h(a_1),\mathrm{\dots },h(a_r))\in R^{ℬ}$. We write $\mathrm{Hom}(𝒜,ℬ)$ for the set of all homomorphisms from $𝒜$ to $ℬ$.

Since $(X,Y)$ is $W$-balanced we may assume w.l.o.g.​ that

Further suppose, for a contradiction, that there exists a set $S^{\prime }\subseteq V_{𝒢}$ of size $\lfloor 2k/3\rfloor$ such that removing $S^{\prime }$ from $𝒢$ disconnects $X$ from $Y$. Then pick arbitrarily a set $T$ of $\lceil k/3\rceil$ elements of $(Y\cap W)\setminus S^{\prime }$ and add these to $S^{\prime }$ to form a set $S$. Then $|S|=k$. We claim that $S$ is a balanced separator with respect to $W$.

To see this, let $C$ be a connected component of $𝒢\setminus S$. Then either $C\subseteq X$ or $C\subseteq Y\setminus T$, by the assumption on $S^{\prime }$. If $C\subseteq X$ then $|C\cap W|\le |X\cap W|\le k$. On the other hand if $C\subseteq Y\setminus T$ then

Since $|C\cap W|$ is an integer it follows that $|C\cap W|\le k$. Therefore, $S$ is indeed a balanced $k$-separator, a contradiction. So there is no such set $S^{\prime }$.

To construct $ℳ$ we first choose any edge between $X$ and $Y$ and delete the two endpoints. We then choose an edge between $X$ and $Y$ in this new graph and repeat until $X$ and $Y$ become disconnected. By the above this leads to an $(X,Y)$-matching of size at least $\lfloor k/3\rfloor$. $◀$ By exploiting this matching it is now not too hard to show that every $W$-balanced rectangle is small; the key is that one endpoint of every edge in the matching must have small image.

Let $(X,Y)$ be the underlying partition of $ℛ$. By Lemma 20, there is an $(X,Y)$-matching $ℳ$ of size $\lfloor k/3\rfloor$. Let $\{x,y\}\in ℳ$ with $x\in X,y\in Y$. Further define,

Then for every $u\in P_x$ and $v\in P_y$, there is an edge in $\mathscr{H}$ between $u$ and $v$. To see this, let $h,g\in ℛ$ with $h(x)=u$ and $g(y)=v$. Hence $h{\upharpoonright }_X\times g{\upharpoonright }_Y\in ℛ\subseteq \mathrm{Hom}(𝒢,\mathscr{H})$, since $ℛ$ is an $(X,Y)$-rectangle. Therefore, since $\{x,y\}\in E_{𝒢}$, we have that $\{h(x),g(y)\}=\{u,v\}\in E_{\mathscr{H}}$. It follows that either $|P_x|\le 3\log (n)$ or $|P_y|\le 3\log (n)$, since $\mathscr{H}$ contains no ${𝒦}_{3\log (n),3\log (n)}$ subgraph by Lemma 19(2). Moreover, by definition $|P_x|=|ℛ{\upharpoonright }_{\{x\}}|$ and $|P_y|=|ℛ{\upharpoonright }_{\{y\}}|$.

Since the above holds for every $\{x,y\}\in ℳ$, there are at least $\lfloor k/3\rfloor$ vertices $v\in V_{𝒢}$ such that $|ℛ{\upharpoonright }_{\{v\}}|\le 3\log (n)$. The result follows by Observation 15. $◀$ To infer Theorem 16, first observe that by Lemma 19(3), $|\mathrm{Hom}(𝒢,\mathscr{H})|=\mathrm{\Omega }(n^t)$. Here we use the fact that any mapping $h:V_{𝒢}\to V_{\mathscr{H}}$ whose image is a clique is a homomorphism. Therefore, by Lemmas 14 and 21 the result follows; see the full version for details.

We next lift this to relational structures. We could do this similarly to the above. However, it is convenient to instead use the following reduction result from [12].

Let $𝒢$ be the Gaifman graph of $𝒜$ and let $N^{\prime }$ be an integer. Then since the treewidth of $𝒢$ is the same as the treewidth of $𝒜$ we may apply Theorem 16, to obtain a graph $\mathscr{H}$ with $n\ge N^{\prime }$ vertices and at least $n^2/8$ many edges such that any $\{\cup ,\times \}$-circuit computing $\mathrm{Hom}(𝒢,\mathscr{H})$ has size $\mathrm{\Omega }(n^{\frac{w}{9}-2})={\Vert \mathscr{H}\Vert }^{\mathrm{\Omega }(w)}$. Therefore, by Lemma 22, there is a $\sigma$-structure $ℬ$ with $\Vert ℬ\Vert \ge \Vert \mathscr{H}\Vert \ge N^{\prime }$ such that any $\{\cup ,\times \}$-circuit for $\mathrm{Hom}(𝒜,ℬ)$ has size ${\Vert ℬ\Vert }^{\mathrm{\Omega }(w)}$, since $r$ is a constant and by choosing $n$ (and hence $\Vert ℬ\Vert$) to be sufficiently big. $◀$ Note that some form of dependence on the arity is necessary since there are classes of structures $𝖠$ of unbounded treewidth such that solving $\{\cup ,\times \}$-$\mathrm{Hom}(𝖠)$ is in polynomial time, e.g. classes of unbounded treewidth but bounded fractional hypertree width. Such classes must have unbounded arity; we next turn to this setting.