1 Introduction↩︎

We focus on the problem of answering a Boolean Conjunctive Query (BCQ) \(Q\). In particular, we have a set \(\text{\sf vars}(Q)\) of variables (or attributes) and a set \(\mathsf{atoms}(Q)\) of relations where each relation \(R(\boldsymbol{X})\in\mathsf{atoms}(Q)\) is over a variable set \(\boldsymbol{X} \subseteq \text{\sf vars}(Q)\). In particular, each relation \(R(\boldsymbol{X})\) is a list of satisfying assignments to the variables \(\boldsymbol{X}\), and the query \(Q\) asks whether there exists an assignment to all variables \(\text{\sf vars}(Q)\) that simultaneously satisfies all relations in \(\mathsf{atoms}(Q)\): \[\begin{align} Q() \text{ :- }\bigwedge_{R(\boldsymbol{X}) \in \mathsf{atoms}(Q)} R(\boldsymbol{X}) \label{eq:bcq} \end{align}\tag{1}\] We assume the query to be fixed, hence its size is a constant, and we measure the runtime in terms of the total size of the input relations, denoted by \(N\), i.e., we use data complexity. For brevity, throughout the paper, we refer to a Boolean conjunctive query as just “query”.

Using only combinatorial algorithms, the best known complexity for any query \(Q\) is given by the submodular width [1]–[3]. However, when fast matrix multiplication is allowed, some isolated queries admit faster algorithms, but there is no general framework to derive such algorithms for any query. In this paper, we introduce such a framework that naturally unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. In particular, we generalize the submodular width to incorporate matrix multiplication and develop a matching algorithm. We show that our general algorithm matches or improves upon the best known custom algorithms for queries that have been studied in the literature.

A preliminary, short version of this paper appeared in [4]. That version described the algorithm only at an intuitive level. The current paper contains the full details of the algorithm, proves its runtime, and removes a polylogarithmic factor from the runtime by incorporating new techniques described in [5].

1.1 Background↩︎

1.1.1 Combinatorial Join Algorithms↩︎

We start with some background on combinatorial algorithms for queries. When restricted to the class of combinatorial algorithms, there are only three basic techniques that are sufficient to recover the best-known complexity over this class of algorithms for any query \(Q\):

• For-loops: Worst-case optimal join (WCOJ) algorithms [6], [7], like GenericJoin [8] or LeapFrog-TrieJoin [9], can be viewed as a sequence of nested for-loops, each of which iterates over possible assignments of one variable. For example, consider the Boolean triangle query: \[\begin{align} Q_\triangle() \text{ :- }R(X, Y) \wedge S(Y, Z) \wedge T(X, Z) \label{eq:intro:triangle} \end{align}\tag{2}\] One possible WCOJ algorithm consists of a for-loop over the intersection of \(X\)-values from \(R\) and \(T\), and for each such assignment, a for-loop over the intersection of \(Y\)-values from \(R\) and \(S\), and for each such assignment, a for-loop over the intersection of \(Z\)-values from \(S\) and \(T\). This simple algorithm gives a runtime of \(O(N^{3/2})\) for this query and \(O(N^{\rho^*(Q)})\) in general, where \(\rho^*(Q)\) is the fractional edge cover number of \(Q\), which is also an upper bound on the join size [10]–[12].

• Tree Decompositions (TDs): Sometimes, two nested loops can be (conditionally) independent of one other. For example, consider the query: \[\begin{align} \label{eq:intro:triangletriangle} Q_{\triangle\triangle}() \text{ :- }R(X, Y) \wedge S(Y, Z) \wedge T(X, Z) \wedge S'(Y, Z') \wedge T'(X, Z') \end{align}\tag{3}\] We could solve it in time \(O(N^2)\) using 4 nested for-loops over \(X\), \(Y\), \(Z\), and \(Z'\) in order. However, note that once we fix the values of \(X\) and \(Y\), the two inner loops over \(Z\) and \(Z'\) become independent, hence can be unnested. One way to capture and utilize such conditional independence is using the framework of tree decompositions, which are a form of query plans. In this example, we could break down the query using a tree decomposition, or TD for short, consisting of two “bags” (i.e. two subqueries in the query plan) where one bag corresponds to a triangle query over \(\{X, Y, Z\}\) while the other bag is a triangle query over \(\{X, Y, Z'\}\), thus leading to a runtime of \(O(N^{3/2})\). Using TDs (alongside for-loops), we can answer any query \(Q\) in time \(O(N^{\textsf{fhtw}(Q)})\) where \(\textsf{fhtw}(Q)\) is the fractional hypertree width of \(Q\) [10], [13], [14].

• Data Partitioning: For-loops and TDs alone are not sufficient to unleash the full power of combinatorial join algorithms for all queries. Consider the following 4-cycle query: \[\begin{align} Q_\square() \text{ :- }R(X, Y) \wedge S(Y, Z) \wedge T(Z, W) \wedge U(W, X) \label{eq:intro:4cycle} \end{align}\tag{4}\] \(Q_\square\) admits two TDs: one with two bags \(\{X, Y, Z\}\) and \(\{Z, W, X\}\), while the other with two bags \(\{Y, Z, W\}\) and \(\{W, X, Y\}\). However, using either TD alone, we cannot achieve a runtime better than \(O(N^2)\). On the other hand, if we partition the input relations carefully into multiple parts, and select a proper TD for each part, we could achieve a runtime of \(O(N^{3/2})\) [15]. Partitioning is done based on the “degrees” of relations where we think of a (binary) relation like \(R(X, Y)\) as a bipartite graph, and compute degrees of vertices accordingly. Taking the partitioning approach to the extreme², the \(\mathsf{PANDA}\) algorithm [2], [3] can solve any query \(Q\) in time \(O(N^{\textsf{subw}(Q)}\cdot \text{\sf polylog}(N))\) where \(\textsf{subw}(Q)\) is the submodular width of \(Q\) [1]. An improved algorithm, called \(\textsf{PANDAExpress}\) [5], removes the polylogarithmic factor, achieving a runtime of \(O(N^{\textsf{subw}(Q)}\cdot \log N)\).

The submodular width is a single definition that combines the above three techniques, and the corresponding \(\mathsf{PANDA}\) algorithm achieves (up to a polylogarithmic factor) the best-known complexity for any query \(Q\) over combinatorial algorithms. The submodular width and \(\mathsf{PANDA}\) have a deep connection to information theory. At a very high level, the submodular width of a given query \(Q\) can be thought of as aiming to capture the best complexity of answering \(Q\) using the following meta-algorithm: Think of (binary) input relations, like \(R(X, Y)\) above, as bipartite graphs, and partition each of them into (a polylogarithmic number of) parts that are almost “uniform”, i.e. where all vertices within the same part have roughly the same degree. Now each part of the data can be described by its combination of degrees, called “degree configuration”. For each degree configuration, we pick the best TD, go over its bags, and solve the corresponding subqueries, using for-loops.³ Instead of reasoning about degree configurations directly, we model them as edge-dominated polymatroids, or ED-polymatroids for short, which is an information-theoretic concept. In particular, given a degree configuration, the corresponding polymatroid is roughly the entropy of a certain probability distribution over the join of input relations having the given degree configuration. (Formal Definition will be given in Sec. 3.) Using polymatroids as a proxy to degree configurations allows us to transform a database problem into an information-theoretic problem. To sum up, the submodular width has the following skeleton (the formal definition will be given later): \[\begin{align} \textsf{subw}(Q) \quad\stackrel{\mathrm{def}}{=}\quad \underbrace{\max_{\text{ED-polymatroid \boldsymbol{h}}}}_{\substack{\text{worst part}\\\text{of the data}}} \quad \underbrace{\min_{\text{tree decomposition T}}}_{\substack{\text{best query plan}\\\text{for this part}}} \quad \underbrace{\max_{\text{bag B\in T}}}_{\substack{\text{worst subquery}\\\text{in the plan}}} \quad \underbrace{h(B)}_{\substack{\text{subquery cost}\\\text{(using for-loops)}}} \label{eq:intro:subw} \end{align}\tag{5}\]

1.1.2 Beyond Combinatorial Join Algorithms↩︎

For certain queries, there are known non-combinatorial algorithms with lower complexity than the best known combinatorial algorithms. In addition to the three techniques mentioned above, these non-combinatorial algorithms typically involve a fourth technique, which is matrix multiplication, or MM for short. For background, given two \(n\times n\) matrices, there are algebraic algorithms that can multiply them in time \(o(n^3)\). The matrix multiplication exponent \(\omega\) is the smallest exponent \(\alpha\) where this multiplication can be done in time \(O(n^{\alpha})\). It was first discovered by Strassen [16] that \(\omega < 3\), and to date, the best known upper bound for \(\omega\) is \(2.371552\) [17]. For certain queries, incorporating MM can lead to faster algorithms by first partitioning the data based on degrees, and then for each part, choosing to either perform an MM or to use a traditional combinatorial algorithm (consisting of a TD and for-loops). Which choice is better depends on the degree configuration of the part. For parts with low degrees, combinatorial algorithms are typically better, while parts with high degrees tend to benefit from MM. The complexities of such algorithms typically involve \(\omega\). For example, for the triangle query \(Q_\triangle\), there is a non-combinatorial algorithm with complexity \(O(N^{\frac{2\omega}{\omega + 1}})\) [15].⁴ However, such non-combinatorial algorithms are only known for some isolated queries; see Table 1 for a summary of known results. There is no general framework for answering any query \(Q\) using MM.

1.2 Our Contributions↩︎

In this paper, we make the following contributions: (Recall that a “query” refers to a Boolean conjunctive query.)

• We introduce a generalization of the submodular width of a query \(Q\), called the \(\omega\)-submodular width of \(Q\), and denoted by \(\textsf{\omega-subw}(Q)\), that naturally incorporates the power of matrix multiplication. The \(\omega\)-submodular width is always upper bounded by the submodular width, and becomes identical when \(\omega = 3\).

• We introduce a general framework to compute any query \(Q\) in time \(O(N^{\textsf{\omega-subw}(Q)}\cdot \log^2 N)\) for any rational⁵ value of \(\omega\). Our framework unifies known combinatorial and non-combinatorial techniques under the umbrella of information theory. (The extra \(\log^2 N\) factor is not needed for every query, e.g. \(k\)-Clique in Table1.)

• We show that for any query \(Q\), our framework recovers the best known complexity for \(Q\) over both combinatorial and non-combinatorial algorithms. See Table 1.

• We show that there are classes of queries where our framework discovers new algorithms with strictly lower complexity than the best-known ones. See highlighted cells in Table 1.

The intuition behind the connection between our framework and information theory is as follows: Information inequalities can be used to prove an upper bound on the size of every intermediate result in the query plan. At the same time, any algorithm, with a proven runtime, also leads to an upper bound on the size of all intermediate results, since these cannot be larger than the runtime of the algorithm. Hence, there is a connection between information inequalities and algorithms, namely both imply upper bounds on all intermediate results of the algorithm. What is non-obvious is how to convert the information inequalities into an algorithm: this is what the \(\mathsf{PANDA}\) algorithm did [2], [3], and what we extend in our paper to handle matrix multiplication. We give an overview of how to convert information inequalities into an algorithm in Section 2.

1.3 Paper Outline↩︎

In Section 2, we present a high-level overview of our framework and illustrate it using the triangle query \(Q_\triangle\). In Section 3, we give formal definitions for background concepts. We formally define the \(\omega\)-submodular width in Section 4. We show in Section 5 the \(\omega\)-submodular width for several classes of queries, with proofs deferred to Appendix 11. In Sections 6, we give an algorithm for computing the \(\omega\)-submodular for any query \(Q\). Section 7 is the technical core of the paper where we present our algorithm for computing the answer to any query \(Q\) in \(\omega\)-subdmodular width time. We conclude in Section 9 with some extensions and open problems.

2 Overview↩︎

We give here a simplified overview of our framework. We start with how to generalize the subdmodular width to incorporate MM, and to that end, we need to answer two basic questions:

• Q1: How can we express the complexity of MM in terms of polymatroids?

• Q2: How can we develop a notion of query plans that naturally reconciles TDs with MM?

2.1 Q1: Translating MM complexity into polymatroids↩︎

Given a query \(Q\) of the form 1 , a polymatroid is a function \(\boldsymbol{h}:2^{\text{\sf vars}(Q)}\to \mathbb{R}_+\) that satisfies the basic Shannon inequalities. By that, we mean \(\boldsymbol{h}\) is monotone (i.e. \(h(\boldsymbol{X})\leq h(\boldsymbol{Y})\) for all \(\boldsymbol{X}\subseteq \boldsymbol{Y}\subseteq \text{\sf vars}(Q)\)), submodular (i.e. \(h(\boldsymbol{X})+h(\boldsymbol{Y}) \geq h(\boldsymbol{X} \cup \boldsymbol{Y}) + h(\boldsymbol{X} \cap \boldsymbol{Y})\) for all \(\boldsymbol{X}, \boldsymbol{Y}\subseteq\text{\sf vars}(Q)\)), and satisfies \(h(\emptyset) = 0\). Given a query \(Q\), a polymatroid \(\boldsymbol{h}\) is edge-dominated if \(h(\boldsymbol{X})\leq 1\) for all \(R(\boldsymbol{X})\in\mathsf{atoms}(Q)\). The subdmodular width, given by Eq. 5 , uses edge-dominated polymatroids as a proxy for the degree configurations of different parts of the data.

Throughout the paper, we assume that \(\omega\) is a fixed constant within the range \([2, 3]\). Given two rectangular matrices of dimensions \(n^a\times n^b\) and \(n^b\times n^c\), we can multiply them by partitioning them into square blocks of dimensions \(n^d\times n^d\) where \(d \stackrel{\mathrm{def}}{=}\min(a, b, c)\) and then multiplying each pair of blocks using square matrix multiplication in time \(n^{d\cdot \omega}\). This is a folklore idea, e.g. [22]. It leads to an overall runtime of \(n^{ \omega^{\square} (a, b, c)}\) where \(\omega^{\square} (a, b, c)\) is defined below and \(\gamma \stackrel{\mathrm{def}}{=}\omega - 2\): (Proof is in Sec. 3.) \[\begin{align} \omega^{\square} (a, b, c) \stackrel{\mathrm{def}}{=}\max\{a + b + \gamma \cdot c,\quad a + \gamma \cdot b + c,\quad \gamma \cdot a + b + c\} \label{eq:rect-mat-mult} \end{align}\tag{6}\]

Now suppose we have two relations \(R(X, Y)\) and \(S(Y, Z)\), and we want to compute \(P(X, Z) \text{ :- }\) \(R(X, Y) \wedge S(Y, Z)\), by viewing \(R\) and \(S\) as two matrices of dimensions \(n^a\times n^b\) and \(n^b \times n^c\) respectively and multiplying them. In the polymatroid world, we can think of \(h(X)\), \(h(Y)\), and \(h(Z)\) as representing \(a\), \(b\), and \(c\), respectively. Motivated by this, we define the following new information measure: \[\begin{align} \mathsf{MM}(X; Y; Z) \stackrel{\mathrm{def}}{=}\max(h(X)+h(Y)+\gamma h(Z), \;\; h(X)+\gamma h(Y)+h(Z), \;\; \gamma h(X)+h(Y)+h(Z)) \label{eq:intro:mm} \end{align}\tag{7}\] And now, we can use \(\mathsf{MM}(X; Y; Z)\) to capture the complexity of the above MM, on log-scale. We also extend the \(\mathsf{MM}\) notation to allow treating multiple variables as a single dimension. For example, given the query \(Q_{\triangle\triangle}\) from Eq. 3 , we use \(\mathsf{MM}(X;Y;ZZ')\) to refer to the cost of MM where we treat \(Z\) and \(Z'\) as a single dimension. In particular, we view \(R(X, Y)\) as one matrix and \(S(Y, Z) \wedge S'(Y, Z')\) as another matrix, and multiply them to get \(P(X, Z, Z')\).

2.2 Q2: Query plans for MM↩︎

Variable Elimination [23]–[26] is a language for expressing query plans that is known to be equivalent to TDs [14] for combinatorial join algorithms. We show that variable elimination can be naturally extended to incorporate MM in its query plans. For background, given a query \(Q\), variable elimination refers to the process of picking an order \(\boldsymbol{\sigma}\) of the variables \(\text{\sf vars}(Q)\), known as variable elimination order, or VEO for short, and then going through the variables in order and “eliminating” them one-by-one. Eliminating a variable \(X\) from a query \(Q\) means transforming \(Q\) (along with the associated input data) into an equivalent query \(Q'\) (with new input data) that doesn’t contain \(X\), and this is done by removing all relations that contain \(X\) and creating a new relation with all variables that co-occurred with \(X\). (Formal Definition will be given in Sec. 3.) For example, given the 4-cycle query \(Q_\square\) from Eq. 4 , we can eliminate \(Y\) by computing a new relation \(P(X, Z) \text{ :- }R(X, Y) \wedge S(Y, Z)\) and now the remaining query becomes a triangle query: \[\begin{align} Q_\square'() \text{ :- }P(X, Z) \wedge T(Z, W) \wedge U(W, X) \end{align}\] We use \(U_Y^{\boldsymbol{\sigma}}\) to refer to the set of variables involved in the subquery that eliminates \(Y\), which is \(\{X, Y, Z\}\) in this example. Every VEO is equivalent to a TD, and vice versa [14]. In the 4-cycle example, any VEO that eliminates either \(X\) or \(Z\) first is equivalent to the TD with bags \(\{Y,Z,W\}\) and \(\{W, X, Y\}\), while any VEO that eliminates either \(Y\) or \(W\) first is equivalent to the TD with bags \(\{X, Y, Z\}\) and \(\{Z, W, X\}\).

In the presence of MM, VEOs become more expressive. For example, the triangle query \(Q_\triangle\) has only one trivial TD with a single bag \(\{X, Y, Z\}\). Now, suppose we have a VEO that eliminates \(Y\) first. There are two different ways to eliminate \(Y\):

• Either compute the full join combinatorially using for-loops, and then project \(Y\) away. This computation costs \(h(XYZ)\) on log-scale.

• Or view \(R(X, Y)\) and \(S(Y, Z)\) as matrices and multiply them to get \(P(X, Z)\). This costs \(\mathsf{MM}(X; Y; Z)\).

Alternatively, we could have eliminated either \(X\) or \(Z\) first. In this simple example, there is only a single way to eliminate a variable, say \(Y\), using MM, but in general, there could be several, and we can choose the best of them. For example, in the query \(Q_{\triangle\triangle}\) from Eq. 3 , \(Y\) occurs in three relations, and we can arrange them into two matrices in different ways. One way is to join \(S(Y,Z)\) and \(S'(Y,Z')\) into a single matrix \(S''(Y,ZZ')\) and multiply it with the matrix \(R(X,Y)\) leading to a cost of \(\mathsf{MM}(X;Y;ZZ')\). Alternatively, we could have obtained costs \(\mathsf{MM}(XZ;Y;Z')\) or \(\mathsf{MM}(XZ';Y;Z)\), and we will see later that there are even more options! ⁶ Given a VEO \(\boldsymbol{\sigma}\) and a variable \(Y\), we use \(\mathsf{EMM}_Y^{\boldsymbol{\sigma}}\) to denote the minimum cost of eliminating \(Y\) using MM. In contrast, \(h(U_Y^{\boldsymbol{\sigma}})\) is the cost of eliminating \(Y\) using for-loops. For example, in \(Q_\triangle\), \(\mathsf{EMM}_Y^{\boldsymbol{\sigma}}=\mathsf{MM}(X; Y; Z)\) and \(h(U_Y^{\boldsymbol{\sigma}}) = h(XYZ)\), whereas in \(Q_{\triangle\triangle}\), \(\mathsf{EMM}_Y^{\boldsymbol{\sigma}}=\) \(\min(\mathsf{MM}(X;Y;ZZ'),\mathsf{MM}(XZ;Y;Z'),\mathsf{MM}(XZ';Y;Z),\ldots)\) and \(h(U_Y^{\boldsymbol{\sigma}}) = h(XYZZ')\).

2.3 Defining the \(\omega\)-submodular width↩︎

Putting pieces together, we are now ready to define our notion of \(\omega\)-subdmodular width of a query \(Q\). We take the maximum over all ED-polymatroids \(\boldsymbol{h}\), and for each polymatroid, we take the minimum over all VEOs \(\boldsymbol{\sigma}\). For each \(\boldsymbol{\sigma}\), we take the maximum elimination cost over all variables \(X\), where the elimination cost of \(X\) is the minimum over all possible ways to eliminate \(X\) using either for-loops or MM: \[\begin{align} \textsf{\omega-subw}(Q) \stackrel{\mathrm{def}}{=} \underbrace{\max_{\text{ED-polymatroid \boldsymbol{h}}}}_{\substack{\text{worst part}\\\text{of the data}}} \quad \underbrace{\min_{\text{VEO \boldsymbol{\sigma}}}}_{\substack{\text{best query plan}\\\text{for this part}}} \quad \underbrace{\max_{\text{variable X}}}_{\substack{\text{worst variable}\\\text{elimination cost}}} {\color{red}\min\bigl(} \underbrace{h(U_X^{\boldsymbol{\sigma}})}_{\substack{\text{cost of eliminating}\\\text{X using for-loops}}}{\color{red}, \quad \underbrace{\mathsf{EMM}_X^{\boldsymbol{\sigma}}}_{\substack{\text{cost of eliminating}\\\text{X using MM}}} \bigr)} \label{eq:intro:osubw} \end{align}\tag{8}\] To compare the above to the submodular width, we include below an alternative definition of the submodular width that is equivalent to Eq. 5 . The equivalence follows from the equivalence of VEOs and TDs [14]: \[\begin{align} \textsf{subw}(Q) \stackrel{\mathrm{def}}{=} \underbrace{\max_{\text{ED-polymatroid \boldsymbol{h}}}}_{\substack{\text{worst part}\\\text{of the data}}} \quad \underbrace{\min_{\text{VEO \boldsymbol{\sigma}}}}_{\substack{\text{best query plan}\\\text{for this part}}} \quad \underbrace{\max_{\text{variable X}}}_{\substack{\text{worst variable}\\\text{elimination cost}}}\quad \underbrace{h(U_X^{\boldsymbol{\sigma}})}_{\substack{\text{cost of eliminating}\\\text{X using for-loops}}} \label{eq:intro:subw:ve} \end{align}\tag{9}\] The only difference between Eq. 8 and Eq. 9 is the inclusion of \(\color{red}\mathsf{EMM}_X^{\boldsymbol{\sigma}}\) in the former. This shows that \(\textsf{\omega-subw}(Q)\) is always upper bounded by \(\textsf{subw}(Q)\). We show later that they become identical when \(\omega = 3\).

For example, \(Q_\triangle\) has 6 different VEOs. For a fixed VEO, the cost of eliminating the first variable dominates the other two, thus we ignore the two. We have seen before that the cost of eliminating \(Y\) is \(\min(h(XYZ), \mathsf{MM}(X;Y;Z))\), which also happens to be the cost of eliminating either \(X\) or \(Z\).⁷ Hence, the \(\omega\)-subdmodular width becomes: \[\begin{align} \textsf{\omega-subw}(Q_\triangle) = \max_{\text{ED-polymatroid \boldsymbol{h}}} {\color{red}\min\bigl(}h(XYZ){\color{red}, \mathsf{MM}(X;Y;Z)\bigr)} \label{eq:intro:osubw:triangle} \end{align}\tag{10}\]

2.4 Computing the \(\omega\)-submodular width↩︎

Now that we have defined the \(\omega\)-submodular width, our next concern is how to compute it for a given query \(Q\). The \(\omega\)-submodular width is a deeply nested expression of min and max. (Recall that \(\mathsf{EMM}_X^{\boldsymbol{\sigma}}\) is a minimum of potentially many terms of the form \(\mathsf{MM}(X; Y; Z)\), each of which is a maximum of three terms in Eq. 7 .) To compute \(\textsf{\omega-subw}(Q)\), we first pull all \(\max\) operators outside by distributing \(\min\) over \(\max\)⁸, and then swap the order of the \(\max\) operators so that the max over \(\boldsymbol{h}\) is the inner most max. Applying this to Eq. 10 , we get: \[\begin{align} \textsf{\omega-subw}(Q_\triangle) = \max\bigl( & \max_{\text{ED-polymatroid \boldsymbol{h}}}\min(h(XYZ), h(X) + h(Y) + \gamma h(Z)),\nonumber\\ & \max_{\text{ED-polymatroid \boldsymbol{h}}}\min(h(XYZ), h(X) + \gamma h(Y) + h(Z)),\nonumber\\ & \max_{\text{ED-polymatroid \boldsymbol{h}}}\min(h(XYZ), \gamma h(X) + h(Y) + h(Z)) \bigr) \label{eq:intro:osubw:triangle:distributed} \end{align}\tag{11}\] Assume that \(\gamma\stackrel{\mathrm{def}}{=}\omega - 2\) is fixed, and consider the first term inside the outermost max above. We can turn this term into a linear program (LP) by introducing a new variable \(t\) and replacing the \(\min\) operator with a max of \(t\) subject to some upper bounds on \(t\): \[\begin{align} \max_{\substack{t \in \mathbb{R}\\ \text{ED-polymatroid \boldsymbol{h}}}} \left\{ t \quad\mid\quad t \leq h(XYZ), \quad t \leq h(X) + h(Y) + \gamma h(Z) \right\} \label{eq:intro:inner-lp:triangle} \end{align}\tag{12}\] Recall that the polymatroid \(\boldsymbol{h}\) is a function \(\boldsymbol{h}:2^{\{X,Y,Z\}}\to \mathbb{R}_+\) that satisfies the basic Shannon inequalities, or, equivalently, a vector in \(\mathbb{R}_+^{2^3}\) subject to certain linear constraints. Thus, Eq. 12 is linear program, and we will denote by \(\mathsf{opt}\) its optimal objective value. We will show that \(\mathsf{opt}= \frac{2\omega}{\omega+1}\). Since the other two LPs are similar, it follows that \(\textsf{\omega-subw}(Q_\triangle)=\frac{2\omega}{\omega+1}\).

First, we show that \(\mathsf{opt}\geq \frac{2\omega}{\omega+1}\). To that end, consider the following polymatroid (where \(h(\emptyset) = 0)\): \[\begin{align} h(X) = h(Y) = h(Z) = \frac{2}{\omega+1},\quad\quad h(XY) = h(YZ) = h(XZ) = 1,\quad\quad h(XYZ) = \frac{2\omega}{\omega+1}. \end{align}\] It can be verified that this is a valid polymatroid (for any \(\omega \in [2, 3]\)), it is edge-dominated, and forms a feasible (primal) solution to the LP (alongside \(t = \frac{2\omega}{\omega+1}\)), thus proving that \(\mathsf{opt}\geq \frac{2\omega}{\omega+1}\). In the next section, we will show a feasible dual solution that proves \(\mathsf{opt}\leq \frac{2\omega}{\omega+1}\).

2.5 Computing query answers in \(\omega\)-subdmodular width time↩︎

We now give a simplified overview of our algorithm for computing the answer to a query \(Q\) in time \(O(N^{\textsf{\omega-subw}(Q)}\cdot \log^2 N)\). The extra factor of \(\log^2 N\) does not manifest in every query, and it doesn’t manifest in the triangle query \(Q_\triangle\), which we will use as an example. It should be noted however that this simple example of \(Q_\triangle\) is not sufficient to reveal the major technical challenges of designing the general algorithm. Many of these challenges are unique to matrix multiplication, and are not encountered in the original \(\mathsf{PANDA}\) algorithm [2], [3], or its improved version [5]. We explain our general algorithm in detail in Section 7.

A Shannon inequality is an inequality that holds over all polymatroids \(\boldsymbol{h}\). The following Shannon inequality corresponds to a feasible dual solution to the LP from Eq. 12 : \[\begin{align} \omega \underbrace{h(XYZ)}_{\substack{\rotatebox{90}{\leq}\\t \\\text{\color{red}(for-loop cost)}}} + \underbrace{h(X) + h(Y) + \gamma h(Z)}_{\substack{\rotatebox{90}{\leq}\\t \\\text{\color{red}(one term of MM cost)}}} \quad\leq\quad 2 \underbrace{h(XY)}_{\substack{\rotatebox{-90}{\leq}\\1\\\color{red}(R(X, Y))}} + (\omega-1) \underbrace{h(YZ)}_{\substack{\rotatebox{-90}{\leq}\\1\\\color{red}(S(Y, Z))}} + (\omega - 1) \underbrace{h(XZ)}_{\substack{\rotatebox{-90}{\leq}\\1\\\color{red}(T(X, Z))}} \label{eq:intro:shannon:triangle} \end{align}\tag{13}\] In particular, the above is a Shannon inequality because it is a sum of the following submodularities: \[\begin{align} h(XYZ) + h(X) &\leq h(XY) + h(XZ)\\ h(XYZ) + h(Y) &\leq h(XY) + h(YZ)\\ \gamma h(XYZ) + \gamma h(Z) &\leq \gamma h(XZ) + \gamma h(YZ) \end{align}\] Since \(\boldsymbol{h}\) is edge-dominated, each term on the RHS of Eq. 13 is upper bounded by 1, hence the RHS is \(\leq 2 \omega\). On the other hand, by Eq. 12 , the LHS is at least \((\omega + 1)t\). Therefore, Inequality 13 implies \(t \leq \frac{2\omega}{\omega + 1}\), hence \(\mathsf{opt}\leq\frac{2\omega}{\omega + 1}\). Each term on the RHS of Eq. 13 corresponds to one input relation, whereas each group of terms on the LHS corresponds to the cost of solving a subquery in the plan. In particular, the group \(h(XYZ)\) corresponds to the cost of solving the query using for-loops, whereas the group \(h(X) + h(Y) + \gamma h(Z)\) corresponds to one of three terms that capture the cost of solving the query using MM.

First, the algorithm constructs a proof sequence of the Shannon inequality 13 , which is a step-by-step proof of the inequality that transforms the RHS into the LHS. Figure 1 (left) shows the proof sequence for Eq. 13 . Then, the algorithm translates each proof step into a corresponding database operation. In particular, initially each term on the RHS of Eq. 13 corresponds to an input relation. Each time we apply a proof step replacing some terms on the RHS with some other terms, we simultaneously apply a database operation replacing the corresponding relations with some new relations. Figure 1 (right) shows the corresponding database operations, which together make the algorithm for answering \(Q_\triangle\). In this example, there are only two types of proof steps:

• Decomposition Step of the form \(h(XY) \to h(X) + h(Y|X)\). Let \(R(X, Y)\) be the relation corresponding to \(h(XY)\). The corresponding database operation is to partition \(R(X, Y)\) into two parts based on the degree of \(X\), i.e. the number of matching \(Y\)-values for a given \(X\). In particular, \(X\)-values with degree \(> \Delta \stackrel{\mathrm{def}}{=}N^{\frac{\omega-1}{\omega+1}}\) go into in the “heavy” part \(R_h(X)\), whereas the remaining \(X\)-values (along with their matching \(Y\)-values) go into the “light” part \(R_\ell(X, Y)\). Note that \(|R_h|\) cannot exceed \(N/\Delta = N^{\frac{2}{\omega+1}}\).

• Submodularity Step⁹ of the form \(h(XZ) + h(Y|X) \to h(XYZ)\). The corresponding database operation is to join the two corresponding relations, \(T(X, Z)\Join R_\ell(X, Y)\). Since \(R_\ell\) is the light part, this join takes time \(N\cdot N^{\frac{\omega-1}{\omega+1}}=\) \(N^{\frac{2\omega}{\omega+1}}\), as desired. The same goes for the other submodularity steps.

The three submodularity steps compute three relations \(Q_{\ell,1}, Q_{\ell,2}, Q_{\ell,3}\) covering triangles \((X, Y, Z)\) where either \(X\), \(Y\), or \(Z\) is light, and three unary relations \(R_h(X), S_h(Y), T_h(Z)\) containing all heavy elements. We use the latter to compute the triangles where all three nodes are heavy. For that, we use \(R_h(X)\), \(S_h(Y)\), and \(R(X,Y)\) to form a dense matrix \(M_1(X,Y)\), use \(S_h(Y), T_h(Z)\), and \(S(Y,Z)\) to form a matrix \(M_2(Y, Z)\), then multiply them to get \(M(X, Z)\). Since \(|R_h|, |S_h|, |T_h| \leq N^{\frac{2}{\omega+1}}\), this multiplication takes time \(N^{\frac{2\omega}{\omega+1}}\), as desired. Finally, we join \(M(X, Z)\) with \(T(X, Z)\) to get \(Q_h(X, Z)\). There exists a triangle if and only if either one of \(Q_{\ell,1}, Q_{\ell,2}, Q_{\ell,3}\) or \(Q_h\) is non-empty. In Section 7.6.1, we explain the general principle that leads to the above simple algorithm.

3 Preliminaries↩︎

In this section, we present the formal definitions and notations for various background concepts that were introduced informally in the introduction. Given a number \(k\), we use \([k]\) to denote the set \(\{1, \ldots, k\}\).

3.1 Hypergraphs↩︎

A hypergraph \(\mathcal{H}\) is a pair \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\), where \(\mathcal{V}\) is a set of vertices, and \(\mathcal{E}\subseteq 2^{\mathcal{V}}\) is a set of hyperedges. Each hyperedge \(\boldsymbol{Z} \in \mathcal{E}\) is a subset of \(\mathcal{V}\). We typically use \(k\) to denote the number of vertices in \(\mathcal{V}\). Given a hypergraph \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) and a vertex \(X \in \mathcal{V}\), we define:

• \(\partial_\mathcal{H}(X)\) is the set of hyperedges that contain \(X\), i.e.  \(\partial_\mathcal{H}(X) \stackrel{\mathrm{def}}{=}\{{\boldsymbol{Z} \in \mathcal{E}}\mid{X \in \boldsymbol{Z}}\}\).

• \(U_\mathcal{H}(X)\) is the union of all hyperedges that contain \(X\), i.e.  \(U_\mathcal{H}(X) \stackrel{\mathrm{def}}{=}\bigcup_{\boldsymbol{Z} \in \partial_\mathcal{H}(X)} \boldsymbol{Z}\).

• \(N_\mathcal{H}(X)\) is the set of neighbors of \(X\) (excluding \(X\)), i.e.  \(N_\mathcal{H}(X) \stackrel{\mathrm{def}}{=}U_\mathcal{H}(X) \setminus \{X\}\).

When \(\mathcal{H}\) is clear from the context, we drop the subscript and simply write \(\partial(X)\), \(U(X)\), and \(N(X)\).

Given a query \(Q\) of the form 1 , the hypergraph of \(Q\) is a hypergraph \(\mathcal{H}=(\mathcal{V}, \mathcal{E})\) where \(\mathcal{V}\stackrel{\mathrm{def}}{=}\text{\sf vars}(Q)\) and \(\mathcal{E}\stackrel{\mathrm{def}}{=}\{\boldsymbol{Z} \mid R(\boldsymbol{Z})\in\mathsf{atoms}(Q)\}\). We often use a query \(Q\) and its hypergraph \(\mathcal{H}\) interchangeably, e.g. in the contexts of tree decompositions, submodular width, etc.

3.2 Tree Decompositions↩︎

Given a hypergraph \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) (or a query \(Q\) whose hypergraph is \(\mathcal{H}\)), a tree decomposition, or TD for short, is a pair \((T, \chi)\), where \(T\) is a tree, and \(\chi: \text{\sf nodes}(T) \to 2^\mathcal{V}\) is a map from the nodes of \(T\) to subsets of \(\mathcal{V}\), that satisfies the following properties:

• For every hyperedge \(\boldsymbol{Z} \in \mathcal{E}\), there is a node \(t \in \text{\sf nodes}(T)\) such that \(\boldsymbol{Z} \subseteq \chi(t)\).

• For every vertex \(X \in \mathcal{V}\), the set \(\{{t \in \text{\sf nodes}(T)}\mid{X \in \chi(t)}\}\) forms a connected sub-tree of \(T\).

Each set \(\chi(t)\) is called a bag of the tree decomposition. We use \(\mathcal{T}(\mathcal{H})\) to denote the set of all tree decompositions of \(\mathcal{H}\).

Given two sets of sets \(\mathcal{A}, \mathcal{B}\subseteq 2^\mathcal{V}\), we write \(\mathcal{A}\sqsubseteq \mathcal{B}\) if \(\forall \boldsymbol{A} \in \mathcal{A}, \exists \boldsymbol{B} \in \mathcal{B}: \boldsymbol{A} \subseteq \boldsymbol{B}\). The relation \(\sqsubseteq\) is a preorder, and we write \(\mathcal{A}\equiv \mathcal{B}\) when \(\mathcal{A}\sqsubseteq \mathcal{B}\) and \(\mathcal{B}\sqsubseteq \mathcal{A}\). We identify a tree decomposition with the set of its bags, and extend \(\sqsubseteq\) to a preorder on tree decompositions: \((T_1,\chi_1) \sqsubseteq (T_2,\chi_2)\) if \(\{{\chi_1(t)}\mid{t \in \text{\sf nodes}(T_1)}\}\sqsubseteq \{{\chi_2(t)}\mid{t \in \text{\sf nodes}(T_2)}\}\). The trivial tree decomposition, which consists of a single bag containing all vertices, is a maximal element of the preorder. A tree decomposition \((T,\chi)\) is redundant if it contains two different bags \(\chi(t_1) \subsetneq \chi(t_2)\). It is well-known that every tree decomposition is equivalent to a unique non-redundant one, obtained by removing bags that are contained in other bags.

3.3 Variable Elimination↩︎

Let \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) be a hypergraph, \(k\stackrel{\mathrm{def}}{=}|\mathcal{V}|\), and \(\pi(\mathcal{V})\) denote the set of all permutations of \(\mathcal{V}\). Given a fixed permutation \(\boldsymbol{\sigma} = (X_1, \ldots, X_k) \in \pi(\mathcal{V})\), we define a sequence of hypergraphs \(\mathcal{H}_1^{\boldsymbol{\sigma}}, \ldots, \mathcal{H}_{k+1}^{\boldsymbol{\sigma}}\), called an elimination hypergraph sequence, as follows: \(\mathcal{H}_1^{\boldsymbol{\sigma}} \stackrel{\mathrm{def}}{=}\mathcal{H}\), and for \(i = 1, ... , k\), the hypergraph \(\mathcal{H}_{i+1}^{\boldsymbol{\sigma}} = (\mathcal{V}_{i+1}^{\boldsymbol{\sigma}},\mathcal{E}_{i+1}^{\boldsymbol{\sigma}})\) is defined recursively in terms of the previous hypergraph \(\mathcal{H}_{i}^{\boldsymbol{\sigma}} = (\mathcal{V}_{i}^{\boldsymbol{\sigma}},\mathcal{E}_{i}^{\boldsymbol{\sigma}})\) using: \[\begin{align} \mathcal{V}_{i+1}^{\boldsymbol{\sigma}} \stackrel{\mathrm{def}}{=}\mathcal{V}_{i}^{\boldsymbol{\sigma}} \setminus \{X_{i}\},\quad\quad\quad \mathcal{E}_{i+1}^{\boldsymbol{\sigma}} \stackrel{\mathrm{def}}{=}\mathcal{E}_{i}^{\boldsymbol{\sigma}} \setminus \partial_{\mathcal{H}_{i}^{\boldsymbol{\sigma}}}(X_{i}) \cup \{N_{\mathcal{H}_{i}^{\boldsymbol{\sigma}}}(X_i)\}. \end{align}\] In words, \(\mathcal{H}_{i+1}^{\boldsymbol{\sigma}}\) results from \(\mathcal{H}_{i}^{\boldsymbol{\sigma}}\) by removing the vertex \(X_i\) and replacing all hyperedges that contain \(X_i\) with a single hyperedge which is their union minus \(X_i\). We refer to the permutation \(\boldsymbol{\sigma}\) as a variable elimination order, or VEO for short. For convenience, for any \(i\in[k]\), we define \(\partial^{\boldsymbol{\sigma}}_i \stackrel{\mathrm{def}}{=}\partial_{\mathcal{H}_{i}^{\boldsymbol{\sigma}}}(X_i)\) and also define \(U^{\boldsymbol{\sigma}}_i\), and \(N^{\boldsymbol{\sigma}}_i\) analogously.

As with tree decompositions, we identify a VEO \(\sigma\) with the set \(\{{U^\sigma_i}\mid{i\in[k]}\}\) where \(k \stackrel{\mathrm{def}}{=}|\mathcal{V}|\), and we use the preorder \(\sqsubseteq\) to compare tree decompositions and VEOs:

3.4 The Submodular Width↩︎

Given a set \(\mathcal{V}\), a function \(\boldsymbol{h}:2^{\mathcal{V}} \to \mathbb{R}_+\) is called a polymatroid if it satisfies the following properties: \[\begin{align} h(\boldsymbol{X}) + h(\boldsymbol{Y}) &\geq h(\boldsymbol{X} \cup \boldsymbol{Y}) + h(\boldsymbol{X} \cap \boldsymbol{Y}) &\forall \boldsymbol{X}, \boldsymbol{Y} \subseteq \mathcal{V}\quad &\text{(submodularity)}\tag{15} \\ h(\boldsymbol{X}) &\leq h(\boldsymbol{Y}) &\forall \boldsymbol{X} \subset \boldsymbol{Y} \subseteq \mathcal{V}\quad &\text{(monotonicity)}\tag{16} \\ h(\emptyset) &= 0 & &\text{(strictness)}\tag{17} \end{align}\] The above properties are also known as basic Shannon inequalities. We use \(\Gamma_{\mathcal{V}}\) to denote the set of all polymatroids over \(\mathcal{V}\). When \(\mathcal{V}\) is clear from the context, we drop \(\mathcal{V}\) and simply write \(\Gamma\). Given a polymatroid \(\boldsymbol{h}\) and sets \(\boldsymbol{X}, \boldsymbol{Y} , \boldsymbol{Z}\subseteq \mathcal{V}\), we use \(\boldsymbol{X}\boldsymbol{Y}\) as a shorthand for \(\boldsymbol{X} \cup \boldsymbol{Y}\), and we define: \[\begin{align} h(\boldsymbol{Y}|\boldsymbol{X}) &\stackrel{\mathrm{def}}{=}h(\boldsymbol{X} \boldsymbol{Y}) - h(\boldsymbol{X}) \tag{18}\\ h(\boldsymbol{Y} ; \boldsymbol{Z} |\boldsymbol{X}) &\stackrel{\mathrm{def}}{=}h(\boldsymbol{X}\boldsymbol{Y}) + h(\boldsymbol{X} \boldsymbol{Z}) - h(\boldsymbol{X}) - h(\boldsymbol{X} \boldsymbol{Y}\boldsymbol{Z})\tag{19} \end{align}\] Using the above notation, we can rewrite Eq. 16 as \(h(\boldsymbol{Y}|\boldsymbol{X}) \geq 0\), and Eq. 15 as \(h(\boldsymbol{X} ; \boldsymbol{Y} |\boldsymbol{X}\cap\boldsymbol{Y}) \geq 0\). A term \(h(\boldsymbol{Y}|\boldsymbol{X})\) is called unconditional if \(\boldsymbol{X} = \emptyset\).

Given a hypergraph \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\), a function \(\boldsymbol{h}:2^{\mathcal{V}} \to \mathbb{R}_+\) is called edge-dominated if it satisfies \(h(\boldsymbol{X}) \leq 1\) for all \(\boldsymbol{X} \in \mathcal{E}\). We use \(\mathsf{ED}_\mathcal{H}\) to denote the set of all edge-dominated functions over \(\mathcal{H}\). When \(\mathcal{H}\) is clear from the context, we drop \(\mathcal{H}\) and simply write \(\mathsf{ED}\).

Given a hypergraph \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\), the submodular width [1] of \(\mathcal{H}\) is defined as follows: \[\begin{align} \textsf{subw}(\mathcal{H}) \quad\stackrel{\mathrm{def}}{=}\quad \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{(T,\chi) \in \mathcal{T}(\mathcal{H})}\quad \max_{t \in \text{\sf nodes}(T)}\quad h(\chi(t)) \label{eq:subw} \end{align}\tag{20}\] Based on Proposition 1 along with the fact that a polymatroid \(\boldsymbol{h}:2^{\mathcal{V}}\to\mathbb{R}_+\) is monotone (Eq. 16 ), we can equivalently define the submodular width using Eq. 9 , which we repeat here: \[\begin{align} \textsf{subw}(\mathcal{H}) \quad\stackrel{\mathrm{def}}{=}\quad \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{\boldsymbol{\sigma} \in \pi(\mathcal{V})}\quad \max_{i \in [k]}\quad h(U^{\boldsymbol{\sigma}}_i) \label{eq:subw:vo} \end{align}\tag{21}\] Appendix 10 summarizes how to compute the submodular width of a given hypergraph \(\mathcal{H}\).

3.5 Fast Matrix Multiplication↩︎

We show here how to multiply two rectangular matrices \(A\) and \(B\) of dimensions \(n^a\times n^b\) and \(n^b\times n^c\) in the runtime \(n^{ \omega^{\square} (a, b, c)}\), as defined by Eq. 6 . This is a folklore result; see e.g. [22]. Let \(d = \min(a, b, c)\). We partition \(A\) into \(\frac{n^a}{n^d}\times \frac{n^b}{n^d}\) blocks and \(B\) into \(\frac{n^b}{n^d}\times \frac{n^c}{n^d}\) blocks. Therefore, we have to perform \(n^{a+b+c-3d}\) block multiplications, each of which takes time \(O(n^{d\cdot\omega})\). The overall complexity, on \((\log n)\)-scale, is \(a + b + c -(3 - \omega) \min(a, b, c)\), which gives Eq. 6 . When \(\omega = 2\), this algorithm for rectangular matrix multiplication is already optimal because the complexity from Eq. 6 becomes linear in the sizes of the input and output matrices. However, when \(\omega > 2\), there could be faster algorithms that are not based on square matrix multiplication; see e.g. [27]. We define \(\overline{\omega} (a, b, c)\) as the smallest exponent for multiplying two rectangular matrices of sizes \(n^a\times n^b\) and \(n^b\times n^c\) within \(O(n^{ \overline{\omega} (a, b, c)})\) time. Based on the above discussion, we have \(\overline{\omega} (a, b, c) \leq \omega^{\square} (a, b, c)\) and this becomes an equality when \(\omega = 2\) or when \(a = b = c\).

3.6 Disjunctive Datalog Rules↩︎

In order to evaluate a BCQ \(Q\) (Eq. 1 ) in submodular width time \(O(N^{\textsf{subw}(Q)})\), the original \(\mathsf{PANDA}\) algorithm [2], [3], [5] reduces the problem of evaluating \(Q\) into evaluating a collection of Disjunctive Datalog Rules, which we review in this section. To that end, we need some preliminaries.

Let \(\mathcal{V}\) be a set of variables. An atom is an expression of the form \(R(\boldsymbol{X})\), where \(R\) is a relation symbol, and \(\boldsymbol{X} \subseteq \mathcal{V}\) is a set of variables. A schema \(\Sigma\) is a set of atoms.

Given a finite domain \(\textsf{Dom}\) and variables \(\boldsymbol{X} \subseteq \mathcal{V}\), let \(\textsf{Dom}^{\boldsymbol{X}}\) denote the set of all tuples over the variables in \(\boldsymbol{X}\) with values from \(\textsf{Dom}\). Given a tuple \(\boldsymbol{t} \in \textsf{Dom}^{\mathcal{V}}\), we use \(\boldsymbol{t}_{\boldsymbol{X}}\) to denote the projection of \(\boldsymbol{t}\) onto the variables in \(\boldsymbol{X}\). A database instance \(D\) over schema \(\Sigma\) is a mapping that assigns each atom \(R(\boldsymbol{X}) \in \Sigma\) to a finite relation \(R^{D} \subseteq \textsf{Dom}^{\boldsymbol{X}}\). Usually the database instance is clear from the context, so we simply write \(R\) instead of \(R^D\). Given a relation \(R\subseteq \textsf{Dom}^{\boldsymbol{X}}\), we use \(\text{\sf vars}(R)\) to denote the set of variables \(\boldsymbol{X}\). Given a tuple \(\boldsymbol{t}\in\textsf{Dom}^{\mathcal{V}}\) and a relation \(R(\boldsymbol{X})\) for \(\boldsymbol{X}\subseteq \mathcal{V}\), we say that \(\boldsymbol{t}\) is covered by \(R\) if \(\boldsymbol{t}_{\boldsymbol{X}} \in R\).

Given a database instance over schema \(\Sigma\), the full natural join of the instance is the set of tuples \(\boldsymbol{t} \in \textsf{Dom}^{\mathcal{V}}\) that satisfy all atoms in \(\Sigma\): \[\begin{align} \mathlarger{\mathlarger{\mathlarger{\Join}}}\Sigma & \stackrel{\mathrm{def}}{=}\{{\boldsymbol{t} \in \textsf{Dom}^{\mathcal{V}}}\mid{ \boldsymbol{t}_{\boldsymbol{X}} \in R, \text{ for all } R(\boldsymbol{X}) \in \Sigma }\} \label{eq:full:join} \end{align}\tag{22}\] In other words, \(\mathlarger{\mathlarger{\mathlarger{\Join}}}\Sigma\) is the set of tuples \(\boldsymbol{t} \in \textsf{Dom}^{\mathcal{V}}\) that are covered by all relations in \(\Sigma\).

Notice that the output instance is not unique. For example, consider the DDR: \[\begin{align} Q_1(X) \vee Q_2(Y) &\text{ :- }R(X,Y) \end{align}\] One output instance is \(Q_1 = \emptyset\), \(Q_2 = \Pi_Y(R)\) (the projection of \(R\) on \(Y\)), another instance is \(Q_1 = \Pi_X(R), Q_2 = \emptyset\). Many other instances exists: it suffices to ensure that, for every \((x,y) \in R\), at least one of \(x \in Q_1\) or \(y \in Q_2\) holds.

The size of an output instance to a DDR is the total number of tuples in all its relations: \[\begin{align} \|\Sigma_{\text{\sf out}}\| \stackrel{\mathrm{def}}{=}\sum_{Q(\boldsymbol{Z}) \in \Sigma_{\text{\sf out}}} |Q|. \label{eqn:ddr:size} \end{align}\tag{24}\] An output instance of a DDR is minimal if no proper subset of it is also an output instance. Note that a conjunctive query (CQ) is a special case of DDR where the output schema \(\Sigma_{\text{\sf out}}\) contains only one atom. The answer to a CQ is its unique minimal output instance.

3.7 Degrees in a Relation↩︎

The \(\mathsf{PANDA}\) algorithm [2], [3], [5] relies heavily on the concept of degrees in a relation, which generalizes degrees in a graph. We review the definition below.

Consider a database instance \(D\) over schema \(\Sigma\). If \(R \in \Sigma\) is a relation name, and \(\boldsymbol{Z}\) is a set of variables, then we denote by¹⁰ \(R^D_{|\boldsymbol{Z}} \stackrel{\mathrm{def}}{=}\textsf{Dom}^{\boldsymbol{Z}} \ltimes R^D\) the restriction of \(R^D\) to the variables \(\boldsymbol{Z}\). Notice that \(\boldsymbol{Z}\) is not necessarily a subset of \(\text{\sf vars}(R)\), in which case \(R^D_{|\boldsymbol{Z}}\) may be an infinite relation (assuming the domain \(\textsf{Dom}\) is infinite), but, when \(\boldsymbol{Z} \subseteq \text{\sf vars}(R)\), then \(R^D_{|\boldsymbol{Z}}=R^D\). Let \(\boldsymbol{X}, \boldsymbol{Y}\) be two disjoint subsets of variables, and \(\boldsymbol{x} \in \textsf{Dom}^{\boldsymbol{X}}\) be a data tuple. We associate three quantities: the degree \(\text{\sf deg}_{R^D}(\boldsymbol{Y} | \boldsymbol{X} = \boldsymbol{x})\) in \(R^D\) of \(\boldsymbol{x}\) w.r.t. \(\boldsymbol{Y}\), the degree \(\text{\sf deg}_{R^D}(\boldsymbol{Y}|\boldsymbol{X})\) in \(R^D\) of the pair \((\boldsymbol{Y}|\boldsymbol{X})\), and the degree \(\text{\sf deg}_{\Sigma^D}(\boldsymbol{Y}|\boldsymbol{X})\) of \((\boldsymbol{Y}|\boldsymbol{X})\) in the \(\Sigma\)-instance \(\Sigma^D\) (\(=D\)): \[\begin{align} \text{\sf deg}_{R^D}(\boldsymbol{Y} | \boldsymbol{X} = \boldsymbol{x}) &\stackrel{\mathrm{def}}{=}|\{{\boldsymbol{y} \in \textsf{Dom}^{\boldsymbol{Y}}}\mid{ (\boldsymbol{x}, \boldsymbol{y}) \in R^D_{|\boldsymbol{X} \cup \boldsymbol{Y}} }\}| \tag{25} \\ \text{\sf deg}_{R^D}(\boldsymbol{Y}|\boldsymbol{X}) &\stackrel{\mathrm{def}}{=}\max_{\boldsymbol{x} \in \textsf{Dom}^{\boldsymbol{X}}} \text{\sf deg}_{R^D}(\boldsymbol{Y}|\boldsymbol{X} = \boldsymbol{x}) \tag{26} \\ \text{\sf deg}_{\Sigma^D}(\boldsymbol{Y}|\boldsymbol{X}) &\stackrel{\mathrm{def}}{=}\min_{R \in \Sigma}\text{\sf deg}_{R^D}(\boldsymbol{Y}|\boldsymbol{X}). \tag{27} \end{align}\] As usual, we drop the superscript \(D\) when clear from the context, and write simply \(\text{\sf deg}_R(\boldsymbol{Y}|\boldsymbol{X})\), \(\text{\sf deg}_{\Sigma}(\boldsymbol{Y}|\boldsymbol{X})\).

3.8 Sub-probability measures↩︎

The original \(\mathsf{PANDA}\) algorithm [2], [3] had an extra polylog factor in the runtime, which was later removed in [5] by a more refined algorithm called \(\textsf{PANDAExpress}\). This refined algorithm relies on the concept of sub-probability measures, which we review in this section. The goal of this paper is to generalize \(\textsf{PANDAExpress}\) to incorporate fast matrix multiplication and achieve the \(\omega\)-submodular width runtime.

Let \(\Omega\) be a finite set. A function \(p : 2^\Omega \to R_+\) is called a measure on \(\Omega\) if \(p(\emptyset)=0\) and \(p(A) = \sum_{x \in A} p(x)\) for any \(A \subseteq \Omega\). In particular, to define a measure on \(\Omega\), it is sufficient to define the values of \(p(x)\) for all \(x \in \Omega\). It is called a sub-probability measure if \(p(\Omega) \leq 1\), and a probability measure if \(p(\Omega) = 1\).

Let \(p\) be a measure on \(\Omega\). If \(\Omega = \Omega_1 \times \Omega_2\) is a Cartesian product of two domains, then the measure \(p_1(x_1) \stackrel{\mathrm{def}}{=}\sum_{x_2 \in \Omega_2} p(x_1, x_2), \forall x_1 \in \Omega_1\) is called the marginal measure of \(p\) on \(\Omega_1\). Let \(A \subseteq \Omega\) with positive measure \(p(A) > 0\), then the measure \(p_{|A}(B) \stackrel{\mathrm{def}}{=}\frac{p(B \cap A)}{p(A)}\) for any \(B \subseteq \Omega\) is called the conditional measure of \(p\) on \(A\). Typically we write \(p(B|A)\) instead of \(p_{|A}(B)\). It is easy to see that, if \(p\) is a sub-probability measure then any of its marginals is also a sub-probability measure, and any of its conditional measures is a probability measure.

In this paper, we will deal with domains \(\Omega = \textsf{Dom}^{\boldsymbol{X}}\) where \(\boldsymbol{X}\) is some set of variables, and \(\textsf{Dom}\) is a finite set. A sub-probability measure \(p\) on \(\textsf{Dom}^{\boldsymbol{X}}\) will be denoted by \(p_{\boldsymbol{X}}\). The aforementioned facts are specialized as follows.

As is customary in probability theory, we write \(p_{\boldsymbol{Y} | \boldsymbol{X}}(\boldsymbol{y} | \boldsymbol{x})\) instead of \(p_{\boldsymbol{Y} | \boldsymbol{X} = \boldsymbol{x}}(\boldsymbol{y})\), with the implicit understanding that there is a measure for each \(\boldsymbol{x} \in \textsf{Dom}^{\boldsymbol{X}}\).

Given a sub-probability measure \(p_{\boldsymbol{Y}|\boldsymbol{X}}\) and a tuple \(\boldsymbol{t} \in \textsf{Dom}^{\mathcal{V}}\) where \(\boldsymbol{X}\cup\boldsymbol{Y}\subseteq \mathcal{V}\), we define \[\begin{align} p_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{t}) \stackrel{\mathrm{def}}{=}p_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{t}_{\boldsymbol{Y}}|\boldsymbol{t}_{\boldsymbol{X}}) \end{align}\]

4 The \(\omega\)-Submodular Width: Formal Definition↩︎

While Eq. 8 gives a high-level sketch of our definition of the \(\omega\)-submodular width, we aim here to provide the full formal definition. To that end, we start with some auxiliary definitions.

4.1 Generalizing variable elimination orders↩︎

In the traditional submodular width (Eq. 9 or 21 ), it was sufficient to consider variable elimination orders that eliminate only one variable at a time. However, once we allow using MM to eliminate variables, there could be situations where eliminating multiple variables at once using a single MM might be cheaper than eliminating the same set of variables one at a time using multiple MMs. For example, suppose we want to compute the query: \[Q(X, Z) \text{ :- }R(X, Y_1, Y_2) \wedge S(Y_1, Y_2, Z)\] There are at least two options to evaluate this query using MM:

• Option 1: For each value \(y_1\) of \(Y_1\), treat \(\sigma_{Y_1 = y_1}R\) and \(\sigma_{Y_1 = y_1}S\) as two matrices and multiply them. Finally, put together the resulting matrices for all \(y_1\) and project \(Y_1\) away.

• Option 2: Combine \(Y_1\) and \(Y_2\) into a single attribute \((Y_1Y_2)\), view \(R\) and \(S\) as two matrices with dimensions \(X \times (Y_1Y_2)\) and \((Y_1Y_2) \times Z\) respectively, and multiply them.

Depending on the relations \(R\) and \(S\), either option could be cheaper. Motivated by this observation, our first task is to generalize the notion of a VEO and an elimination hypergraph sequence to allow eliminating multiple variables at once.

First, we lift the definitions of \(\partial_\mathcal{H}(X)\), \(U_\mathcal{H}(X)\), and \(N_\mathcal{H}(X)\) from a single variable \(X\) to a set of variables \(\boldsymbol{X}\). Given a hypergraph \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) and a non-empty set of variables \(\boldsymbol{X}\subseteq\mathcal{V}\), we define \(\partial_\mathcal{H}(\boldsymbol{X})\) as the set of hyperedges in \(\mathcal{H}\) that overlap with \(\boldsymbol{X}\): \[\begin{align} \partial_\mathcal{H}(\boldsymbol{X}) \stackrel{\mathrm{def}}{=}\{{\boldsymbol{Z} \in \mathcal{E}}\mid{\boldsymbol{X} \cap \boldsymbol{Z} \neq \emptyset}\},\quad\quad U_\mathcal{H}(\boldsymbol{X}) \stackrel{\mathrm{def}}{=}\bigcup_{\boldsymbol{Z} \in \partial_\mathcal{H}(\boldsymbol{X})} \boldsymbol{Z},\quad\quad N_\mathcal{H}(\boldsymbol{X}) \stackrel{\mathrm{def}}{=}U_\mathcal{H}(\boldsymbol{X}) \setminus \boldsymbol{X}. \end{align}\]

4.2 Expressing MM runtime using polymatroids↩︎

We now give the formal definition of the MM expression that generalizes the special case \(\mathsf{MM}(X; Y; Z)\) that was given earlier in Eq. 7 . Recall that \(\omega\) is a constant in the range \([2, 3]\) and \(\gamma \stackrel{\mathrm{def}}{=}\omega - 2\).

The following proposition intuitively says that the MM runtime is at least linear in the sizes of the two input matrices and the output matrix.

4.3 Variable elimination via matrix multiplication↩︎

Here we present the formal definition of the quantity \(\mathsf{EMM}\) introduced earlier in Section 2.2, which captures the cost of eliminating a variable (or set of variables) using matrix multiplication. Given a hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) and a set of vertices \(\boldsymbol{X} \subseteq \mathcal{V}\), in order to eliminate \(\boldsymbol{X}\) using a multiplication of two matrices, we take the neighboring hyperedges \(\partial_\mathcal{H}(\boldsymbol{X})\) of \(\boldsymbol{X}\) and assign them to two (potentially overlapping) sets of hyperedges \(\mathcal{A}\) and \(\mathcal{B}\), each of which will form a matrix. Since every neighboring hyperedge needs to participate in this multiplication, we need \(\mathcal{A}\) and \(\mathcal{B}\) to cover \(\partial_\mathcal{H}(\boldsymbol{X})\), i.e. \(\mathcal{A}\cup\mathcal{B}= \partial_\mathcal{H}(\boldsymbol{X})\). Let \(\boldsymbol{A}\) and \(\boldsymbol{B}\) be the sets of vertices in \(\mathcal{A}\) and \(\mathcal{B}\) respectively, i.e. \(\boldsymbol{A} = \cup \mathcal{A}\) and \(\boldsymbol{B} = \cup\mathcal{B}\). In order to eliminate \(\boldsymbol{X}\) using matrix multiplication, we require that \(\boldsymbol{X}\) is a subset of \(\boldsymbol{A} \cap \boldsymbol{B}\). Additionally, we are allowed to choose a set \(\boldsymbol{G} \subseteq \boldsymbol{A} \cup \boldsymbol{B}\) of “group-by variables”: These are variables that do not participate in the matrix multiplication. Instead, for every assignment \(\boldsymbol{g} \in \textsf{Dom}^{\boldsymbol{G}}\) of \(\boldsymbol{G}\), we perform a matrix multiplication over the remaining variables (hence the name “group-by variables”). Given \(\boldsymbol{G}\), denote by \(\boldsymbol{A}^{\boldsymbol{G}} \stackrel{\mathrm{def}}{=}\boldsymbol{A} \setminus \boldsymbol{G}\), \(\boldsymbol{B}^{\boldsymbol{G}} \stackrel{\mathrm{def}}{=}\boldsymbol{B}\setminus \boldsymbol{G}\); for the choice of \(\boldsymbol{G}\) to be meaningful we require that \(\boldsymbol{X} = \boldsymbol{A}^{\boldsymbol{G}} \cap \boldsymbol{B}^{\boldsymbol{G}}\). Then, for every assignment of the variables in \(\boldsymbol{G}\), we perform a multiplication of a matrix with dimensions \((\boldsymbol{A}^{\boldsymbol{G}} \setminus \boldsymbol{X}) \times \boldsymbol{X}\) with a matrix with dimensions \(\boldsymbol{X} \times (\boldsymbol{B}^{\boldsymbol{G}} \setminus \boldsymbol{X})\). The cost of this multiplication is given by \(\mathsf{MM}(\boldsymbol{A}^G\setminus \boldsymbol{X}, \boldsymbol{B}^G\setminus \boldsymbol{X}, \boldsymbol{X} \mid \boldsymbol{G})\); see Figure 2. Finally, \(\mathsf{EMM}_\mathcal{H}(\boldsymbol{X})\) is the minimum cost over all valid assignments of \(\mathcal{A}\), \(\mathcal{B}\), and \(\boldsymbol{G}\).

We can simplify the above expression further by excluding trivial combinations where either one of the two sets \(\boldsymbol{A}^{\boldsymbol{G}}\setminus \boldsymbol{X}\), or \(\boldsymbol{B}^{\boldsymbol{G}}\setminus \boldsymbol{X}\) is empty.

Let \(\overline{\boldsymbol{\sigma}}=(\boldsymbol{X}_1, \ldots, \boldsymbol{X}_{|\overline{\boldsymbol{\sigma}}|})\) be a generalized variable elimination order and \(\mathcal{H}^{\overline{\boldsymbol{\sigma}}}_1, \ldots, \mathcal{H}^{\overline{\boldsymbol{\sigma}}}_{|\overline{\boldsymbol{\sigma}}|+1}\) be the corresponding generalized hypergraph sequence (Definition 3). For any \(i \in [|\overline{\boldsymbol{\sigma}}|]\), we use \(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_i\) to denote \(\mathsf{EMM}_{\mathcal{H}^{\overline{\boldsymbol{\sigma}}}_i}(\boldsymbol{X}_i)\).

4.4 Putting pieces together↩︎

We now have all the components in place to formally define the \(\omega\)-submodular width.

To compare the \(\omega\)-submodular width with the traditional submodular width, we include below a definition of the submodular width that is equivalent to Eq. 21 , except that it uses GVEOs:

Proposition 7 holds by comparing Eq. 32 to ?? . Proposition 8 holds because Proposition 5 implies that when \(\omega = 3\), \(h(U^{\overline{\boldsymbol{\sigma}}}_i) \leq \mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_i\).

For the purpose of computing the \(\omega\)-submodular width, we propose an equivalent form of Eq. 32 that is easier to compute.

The only difference between Eq. ?? and Eq. 32 is that \(\max_{i \in [|\overline{\boldsymbol{\sigma}}|]}\) is more restricted in Eq. ?? . In particular, we only need to consider \(i\) where \(U_i^{\overline{\boldsymbol{\sigma}}}\) is not contained in any previous \(U_j^{\overline{\boldsymbol{\sigma}}}\). For example, given the hypergraph of the triangle query \(Q_\triangle\) from Eq. 2 , Eq. ?? allows us to only consider the first variable elimination step, thus simplifying the \(\omega\)-submodular width to become Eq. 10 .

5 The \(\omega\)-Submodular Width for Example Queries.↩︎

We show in Table 2 the \(\omega\)-submodular width for several classes of queries and compare it with the submodular width for each of them. Proofs can be found in Appendix 11. They use a variety of techniques to obtain both upper and lower bounds on the \(\omega\)-submodular width. Below are the hypergraphs for these query classes: \[\begin{align} \text{k-Clique:}\quad &\mathcal{H}= \left(\{X_1,X_2,\cdots,X_k\},\;\{\{X_i,X_j\}: i,j \in [k], i \neq j\}\right)\tag{34}\\ \text{k-Cycle:}\quad &\mathcal{H}= \left(\{X_1,X_2,\cdots,X_k\},\;\{\{X_i,X_{i+1}\}: i \in [k-1]\}\cup\{\{X_k, X_1\}\}\right)\tag{35}\\ \text{k-Pyramid:}\quad &\mathcal{H}= \left(\{Y, X_1, X_2,\cdots, X_k\}, \;\{\{Y,X_1,\}, \{Y,X_2\}, \cdots, \{Y, X_k\}, \{X_1,X_2,\cdots,X_k\}\}\right)\tag{36} \end{align}\] Our main result, Theorem [thm:panda:osubw], says that any query \(Q\) can be evaluated in time \(O(N^{\textsf{\omega-subw}(Q)}\cdot \log^2 N)\). Combined with Table 2, this implies the results in Table 1 for the corresponding queries.

6 Algorithm for Computing the \(\omega\)-Submodular Width↩︎

We present in this section an algorithm for computing the value of the \(\omega\)-submodular width for any given hypergraph. This algorithm is a crucial component in our algorithm for computing the answer to a query \(Q\) in \(\omega\)-submodular width time, as we will see in Section 7. The algorithm in this section can also be viewed as a generalization of the algorithm for computing the submodular width of a hypergraph, which is summarized in Appendix 10.

Using Eq. ?? alone, it is not immediately clear how to compute the \(\omega\)-submodular width of a hypergraph \(\mathcal{H}\) because the outer \(\max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\) ranges over an infinite set. Nevertheless, every other \(\max\) and \(\min\) in Eq. ?? ranges over a finite set whose cardinality only depends on \(\mathcal{H}\). Note that by Eq. 29 , \(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_i\) is a minimum of a collection of terms, each of which has the form \(\mathsf{MM}(\boldsymbol{X}; \boldsymbol{Y}; \boldsymbol{Z} | \boldsymbol{G})\). Note also that each term \(\mathsf{MM}(\boldsymbol{X}; \boldsymbol{Y}; \boldsymbol{Z} | \boldsymbol{G})\) is by itself a maximum of 3 terms, as described by Eq. 28 .

In order to compute the \(\omega\)-submodular width, the first step is to distribute every \(\min\) over \(\max\) in Eq. ?? , thus pulling all \(\max\) operators to the top level. To formally describe this distribution, we need some notation. Given an expression \(e\) which is either a minimum or a maximum of a collection of terms, we use \(\mathsf{args}(e)\) to denote the collection of terms over which the minimum or maximum is taken. Let \(k\) be the number of vertices in \(\mathcal{H}\). Let \(f:\overline{\pi}(\mathcal{V})\to [k]\) be a function that maps every generalized variable elimination order \(\overline{\boldsymbol{\sigma}}\in\overline{\pi}(\mathcal{V})\) to a number \(i\) between 1 and \(|\overline{\boldsymbol{\sigma}}|\) that satisfies \(U^{\overline{\boldsymbol{\sigma}}}_i \not\subseteq U^{\overline{\boldsymbol{\sigma}}}_j\) for all \(j \in [i-1]\). (Note that \(|\overline{\boldsymbol{\sigma}}|\leq k\) for every \(\overline{\boldsymbol{\sigma}}\).) Let \(\mathcal{F}\) be the set of all such functions \(f\). For a fixed function \(f \in\mathcal{F}\), let \(g_f\) be a function that maps every pair \((\overline{\boldsymbol{\sigma}}, \mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}))\) where \(\overline{\boldsymbol{\sigma}}\in\overline{\pi}(\mathcal{V})\) and \(\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G})\) is a term in \(\mathsf{args}(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})})\) to one of the three terms in \(\mathsf{args}(\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}))\) from Eq. 28 . Let \(\mathcal{G}_f\) be the set of all such functions \(g_f\) for a fixed \(f\). Then, by distributing the min over the max in Eq. ?? , we get: \[\begin{align} &{\textsf{\omega-subw}}(\mathcal{H}) \quad\nonumber\\ &\stackrel{\mathrm{def}}{=} \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})}\quad \max_{\substack{i \in [|\overline{\boldsymbol{\sigma}}|]\\ {\forall j < i, U_i^{\overline{\boldsymbol{\sigma}}} \not\subseteq U_j^{\overline{\boldsymbol{\sigma}}}}}}\quad \min(h(U^{\overline{\boldsymbol{\sigma}}}_i), \mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_i) \nonumber\\&= \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \max_{f \in \mathcal{F}}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})}\quad \min\left(h(U^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}), \mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}\right) \nonumber\\&= \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \max_{f \in \mathcal{F}}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})}\quad \min\left( h(U^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}), \min_{\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}) \in \mathsf{args}\left(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}\right)} \mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}) \right) \nonumber\\&= \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \max_{f \in \mathcal{F}}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})}\quad \min\left( h(U^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}), \min_{\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}) \in \mathsf{args}\left(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}\right)} \quad \max_{e \in \mathsf{args}(\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}))} e \right) \nonumber\\&= \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \max_{f \in \mathcal{F}}\quad \max_{g_f \in \mathcal{G}_f}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})} \min\left( h(U^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}), \min_{\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}) \in \mathsf{args}\left(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}\right)} g_f(\overline{\boldsymbol{\sigma}}, \mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G})) \right) \nonumber\\&= \max_{f \in \mathcal{F}}\quad \max_{g_f \in \mathcal{G}_f}\quad\nonumber\\ &\quad\quad\underbrace{\max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})}\quad \min\left( h(U^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}), \min_{\mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G}) \in \mathsf{args}\left(\mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_{f(\overline{\boldsymbol{\sigma}})}\right)} g_f(\overline{\boldsymbol{\sigma}}, \mathsf{MM}(\boldsymbol{X};\boldsymbol{Y};\boldsymbol{Z}|\boldsymbol{G})) \right)}_{\text{Equivalent to an LP}} \label{eq:osubw:distributed:swapped:raw} \end{align}\tag{37}\] The above expression can be rewritten into the following form: \[\begin{align} &\textsf{\omega-subw}(\mathcal{H}) = \max_{i \in [\mathcal{I}]}\nonumber\\ &\quad\quad\quad\underbrace{ \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min\bigl( \min_{\ell \in [L_i]} h(\boldsymbol{U}_{i \ell}),\quad \min_{j \in [J_i]} h(\boldsymbol{X}_{ij}|\boldsymbol{G}_{ij}) + h(\boldsymbol{Y}_{ij}|\boldsymbol{G}_{ij}) + \gamma h(\boldsymbol{Z}_{ij}|\boldsymbol{G}_{ij}) + h(\boldsymbol{G}_{ij}) \bigr) }_{\text{Equivalent to LP~\eqref{eq:osubw:inner-lp} {\em assuming} \gamma is fixed}} \label{eq:osubw:distributed:swapped} \end{align}\tag{38}\] In the above expression, \(\mathcal{I}\) is the number of \(\max\) terms at the top level. For every \(i \in [\mathcal{I}]\), the \(i\)-th term is a maximum over \(\boldsymbol{h} \in \Gamma\cap\mathsf{ED}\) of a minimum of \(L_i + J_i\) terms that are divided into two sets:

• \(L_i\) terms of the form \(h(\boldsymbol{U})\) corresponding to \(h(U_i^{\overline{\boldsymbol{\sigma}}})\) from Eq. ?? .

• \(J_i\) terms of the form \(h(\boldsymbol{X} | \boldsymbol{G}) + h(\boldsymbol{Y} | \boldsymbol{G}) + \gamma h(\boldsymbol{Z} | \boldsymbol{G}) + h(\boldsymbol{G})\) corresponding to terms in Eq. 28 .

Suppose that \(\omega\) (and by extension \(\gamma\)) is a fixed constant. For a fixed \(i \in [\mathcal{I}]\), the inner expression in Eq. 38 is equivalent to an LP, as we now show. The condition \(\boldsymbol{h} \in \Gamma\cap\mathsf{ED}\) is a finite collection of linear constraints. The objective function is a minimum of \(L_i+J_i\) linear functions of \(\boldsymbol{h}\). To convert it to a linear objective function, we introduce a fresh variable \(t\) that is lower bounded by each of these \(L_i+J_i\) linear functions, and we set the objective to maximize \(t\) as follows:

Hence, computing the \(\omega\)-submodular width of a hypergraph \(\mathcal{H}\) reduces to solving \(\mathcal{I}\) linear programs of the form in Eq. 39 , and taking the maximum of their optimal values.¹¹ Section 2.4 exemplifies the above using the hypergraph of the triangle query \(Q_\triangle\) (Eq. 2 ).

7 Algorithm for Answering Queries in \(\omega\)-Submodular Width Time↩︎

We show below our main result about evaluating a BCQ of the form 1 in \(\omega\)-submodular width time. The runtime is measured in terms of \(N\), which is the size of the input database instance, i.e., \(N\stackrel{\mathrm{def}}{=}\sum_{R(\boldsymbol{Z})\in\mathsf{atoms}(Q)} |R|\).

We will see later that the extra \(\log^2 N\) factor in the runtime of \(\omega\)-BCQSolver comes from Lemma 2, which will be described in Section 7.5. We note, however, that this extra \(\log^2 N\) factor does not manifest in every query. See Table 1 for examples of some queries, e.g. \(k\)-Clique, where the runtime of \(\omega\)-BCQSolver becomes tighter.

Our \(\textsf{\omega-BCQSolver}\) algorithm is given in Algorithm 3. We give a high-level overview of the algorithm here, and then we spend the rest of this section zooming in on one technical component at a time.

Our algorithm is a huge generalization of the original \(\mathsf{PANDA}\) algorithm [2], [3], [5], where we have to deal with many technical challenges that are not encountered in the original \(\mathsf{PANDA}\). Nevertheless, there are still some similarities between the structures of the two algorithms in hind sight. The original \(\mathsf{PANDA}\) algorithm [2], [3], [5] evaluates a BCQ \(Q\) in two phases:

• In the first phase, we construct and solve a collection of Disjunctive Datalog Rules, or DRRs (Section 3.6). In particular, there is one DDR for every “bag selector”, where a bag selector is a collection of bags that is obtained by picking one bag from each tree decomposition of \(Q\).

• In the second phase, we take the outputs of these DDRs, and we use them to construct a collection of acyclic queries. We then use the Yannakakis algorithm [28] to evaluate each one of these queries, and return the union of the answers.

In contrast, our \(\textsf{\omega-BCQSolver}\) algorithm also has two phases:

• In the first phase (the loop in line [alg:omega-panda-express:outer:loop1] of Algorithm 3), we construct a collection of \(\omega\)-Disjunctive Datalog Rules, or \(\omega\)-DDRs. These are generalizations of DDRs that are specifically tailored to deal with fast matrix multiplication. The formal definition will be given in Section 7.5. In particular, mirroring the formulation of \(\textsf{\omega-subw}(Q)\) from Eq. 37 , where there is an LP 39 for every \(f\in\mathcal{F}\) and \(g\in\mathcal{G}_f\), we construct an \(\omega\)-DDR for every such pair \((f,g)\). We will see shortly how to evaluate these \(\omega\)-DDRs.

• In the second phase (the loop in line [alg:omega-panda-express:outer:loop2] of Algorithm 3), assuming we already evaluated the \(\omega\)-DDRs, we take their outputs and use them to construct the inputs to a collection of \(\omega\)-query plans, which generalize tree decompositions. In particular, an \(\omega\)-query plan is a generalized variable elimination order (Definition 3) that is also amended with a specification of how each variable elimination step is executed, i.e., whether it is executed using a join or a fast matrix multiplication, and if so, specifically which matrix multiplication to use (Definition 13). We execute these \(\omega\)-query plans one by one, and return the union of the answers. This process is explained in detail in Section 7.7.

We now explain at high level how we evaluate an \(\omega\)-DDR in the first phase of our \(\textsf{\omega-BCQSolver}\) algorithm. To that end, we first go back to the original \(\mathsf{PANDA}\) algorithm [2], [3], [5] and recap how it evaluates a DDR within the desired runtime bound. The original \(\mathsf{PANDA}\) algorithm starts from a Shannon-flow inequality [2], [3], [5], which is a Shannon inequality of the following form: \[\begin{align} \sum_{\ell \in [L]} \lambda_\ell h(\boldsymbol{U}_{\ell}) \quad\leq\quad \sum_{i \in [I]} w_i h(\boldsymbol{Y}_i |\boldsymbol{X}_i), \label{eq:shannon-flow} \end{align}\tag{40}\] where the coefficients \(\lambda_\ell\) and \(w_i\) are non-negative. \(\mathsf{PANDA}\) then constructs a proof sequence for inequality 40 , which is a sequence of steps that proves the inequality by transforming the RHS into the LHS. Finally, \(\mathsf{PANDA}\) translates each proof step into an algorithmic operation. Mirroring this process, in order to evaluate an \(\omega\)-DDR in our \(\textsf{\omega-BCQSolver}\) algorithm, we use the following steps:

• We construct an \(\omega\)-Shannon-flow inequality, which is a generalization of inequality 40 that we will formally define in Section 7.2. This \(\omega\)-Shannon-flow inequality is constructed from an optimal dual solution to the LP 39 , as we will see in Section 7.7.

• We construct a proof sequence for this \(\omega\)-Shannon-flow inequality, as we will describe in Section 7.4.

• We evaluate the \(\omega\)-DDR by translating each step of the proof sequence into an algorithmic operation. This translation is described in Section 7.6. Some operations might exceed our time budget, in which case, we will have to skip them, and modify the inequality and the proof sequence accordingly, in order to obtain a new inequality/sequence without the expensive operation. This is achieved by what we call the reset lemma, which will be described in Section 7.3.

Section Overview

This section is organized as follows. Section 7.1 introduces some upper bounds on the matrix multiplication expression, which are needed to define the class of \(\omega\)-Shannon-flow inequalities in Section 7.2. Sections 7.3 and 7.4 present, respectively, the reset lemma and the proof sequence construction for \(\omega\)-Shannon-flow inequalities. In Section 7.5, we introduce \(\omega\)-DDRs, and we explain how to evaluate them in Section 7.6. Finally, in Section 7.7, we explain how to evaluate a BCQ \(Q\) in \(\textsf{\omega-subw}(Q)\) time, thus proving Theorem [thm:panda:osubw]. While most of the section uses the triangle query \(Q_\triangle\) from Eq. 2 as a running example, Section 7.8 presents a more advanced example of the 4-cycle query \(Q_\square\) from Eq. 4 .

7.1 Upper Bounds on the Matrix Multiplication Expression↩︎

We start by introducing some upper bounds on the matrix multiplication expression from Definition 4. We will use these upper bounds in Section 7.2 to define our \(\omega\)-Shannon-flow inequalities.

As a warmup example, note that the following upper bound on \(\mathsf{MM}(X; Y; Z)\) always holds: \[\begin{align} \mathsf{MM}(X; Y; Z) \quad\leq\quad \omega \cdot\max(h(X), h(Y), h(Z)) \label{eq:mm:upper-bound:example} \end{align}\tag{41}\] In particular, to prove the above inequality, assume WLOG that \(h(X) \geq h(Y) \geq h(Z)\). Then, \(\mathsf{MM}(X; Y; Z) = h(X) + h(Y) + \gamma h(Z)\), but the latter is upper bounded by \(\omega h(X)\). Inequality 41 is just one example of an upper bound on \(\mathsf{MM}(X; Y; Z)\). Here is another example that can be proved analogously: \[\begin{align} \mathsf{MM}(X; Y; Z) \quad\leq\quad \frac{\omega}{2}\cdot\max( h(X) + h(Y), h(Y) + h(Z), h(X) + h(Z)) \end{align}\] We introduce below a general way to derive such upper bounds.

7.2 \(\omega\)-Shannon-flow Inequalities↩︎

As explained earlier, our query evaluation algorithm relies on the idea of deriving a Shannon inequality of a certain form, called \(\omega\)-Shannon-flow inequality, constructing a proof sequence of this inequality, and then translating each proof step into an algorithmic operation. In this section, we formally define the class of \(\omega\)-Shannon-flow inequalities.

Note that \(\omega\)-Shannon-flow inequalities generalize Shannon-flow inequalities [2], [3], [5], which were given in Eq. 40 .

Following [3], the following proposition follows immediately from Farkas’ Lemma. Recall the notation for \(h(\boldsymbol{Y}; \boldsymbol{Z}|\boldsymbol{X})\) from Eq. 19 .

We use the standard notation \(\|\boldsymbol{\lambda}\|_1\) to denote \(\sum_{\ell \in [L]} |\lambda_\ell|\).

The \(\omega\)-Shannon-flow inequality in Eq. 13 is an example of an integral \(\omega\)-Shannon-flow inequality.

7.3 The Reset Lemma↩︎

Our query evaluation algorithm relies on translating a proof sequence of an \(\omega\)-Shannon-flow inequality into a sequence of algorithmic operations, as exemplified in Figure 1. However, some operations might be too expensive to fit within our time budget, e.g., performing the join \(T(X, Z)\Join R(X, Y)\) over heavy values \(X\), which takes time \(O(N^2)\) exceeding our budget of \(O(N^{3/2})\) in this example. Whenever we encounter such an expensive operation, we have to give up on performing it while guaranteeing that the skipped tuples will still be produced later by some future operation, e.g., by the matrix multiplication \(M_1(X, Y)\times M_2(Y, Z)\) in Figure 1. In the language of \(\omega\)-Shannon-flow inequalities, this “giving up” corresponds to dropping some terms \(h(XZ) + h(Y|X)\) on the RHS of the inequality corresponding to the expensive operation \(T(X, Z)\Join R(X, Y)\). However, when we drop those terms from the RHS, we have to fix the inequality without losing too many terms on the LHS, in order to guarantee that the skipped tuples will still be produced later by some future operation. This idea of dropping terms and repairing the resulting Shannon-flow inequality goes back to what was known as the reset lemma in the original \(\mathsf{PANDA}\) algorithm [2], [3].

We present here a highly non-trivial generalization of the reset lemma from Shannon-flow inequalities 40 to \(\omega\)-Shannon-flow inequalities 45 . In particular, given an integral \(\omega\)-Shannon-flow inequality 45 , this lemma allows us to sacrifice any unconditional term \(h(\boldsymbol{Y}_i|\emptyset)\) on the RHS while losing at most one unit from the quantity \(\|\boldsymbol{\lambda}\|_1 + \|\boldsymbol{\kappa}\|_1\) on the LHS. Unlike the original Reset Lemma [2], [3] which was restricted to Shannon-flow inequalities 40 , our new lemma has to support proper conditionals \(h(\boldsymbol{X}_j|\boldsymbol{G}_j)\) on the LHS of the \(\omega\)-Shannon-flow inequality. Moreover, this lemma has to maintain the \(\omega\)-dominance property of the triples \(\left(\frac{\alpha_j}{\kappa_j}, \frac{\beta_j}{\kappa_j}, \frac{\zeta_j}{\kappa_j}\right)\), which will be crucial for our query evaluation algorithm.

Before proving the lemma, we give some examples.

7.4 The Proof Sequence Construction↩︎

The original \(\mathsf{PANDA}\) algorithm is based on constructing a proof sequence for a given Shannon-flow inequality (Eq. 40 ). We present here a highly non-trivial generalization of the proof sequence construction that works for \(\omega\)-Shannon-flow inequalities (Eq. 45 ). Out of the box, the original proof sequence construction does not work for \(\omega\)-Shannon-flow inequalities because, unlike Shannon-flow inequalities, the \(\omega\)-Shannon-flow ones can have proper conditionals, i.e., terms \(h(\boldsymbol{X}_j|\boldsymbol{G}_j)\) where \(\boldsymbol{G}_j\neq\emptyset\), on the LHS. The other challenge here is maintaining the \(\omega\)-dominance property of the triples \(\left(\frac{\alpha_j}{\kappa_j}, \frac{\beta_j}{\kappa_j}, \frac{\zeta_j}{\kappa_j}\right)\), which is needed later to get a corresponding evaluation algorithm that uses matrix multiplication.

Note that by Shannon inequalities, each one of the above steps replaces one or two terms with smaller terms. In particular, \[\begin{align} h(\boldsymbol{X} \boldsymbol{Y}) &= h(\boldsymbol{X}) + h(\boldsymbol{Y}|\boldsymbol{X}) &\text{(by Eq.~\eqref{eq:conditional})}\\ h(\boldsymbol{X}\boldsymbol{Y}) &\geq h(\boldsymbol{X}) &\text{(by Eq.~\eqref{eq:monotone})}\\ h(\boldsymbol{Y}|\boldsymbol{X}) &\geq h(\boldsymbol{Y}|\boldsymbol{X}\boldsymbol{Z}) &\text{(by Eq.~\eqref{eq:submod})}\\ \end{align}\]

7.4.1 Example of Theorem 13↩︎

\[\small \begin{array}{|l|l|} \hline \rowcolor{lightgray}\text{\bf Identity~\eqref{eq:omega-shannon:identity}} & \text{\bf Proof Steps}\\\hline \begin{aligned}[c] &\omega h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= 2\positiveterm{h(XY)} + (\omega-1) h(YZ) + (\omega-1)h(XZ)\nonumber\\ &-[\negativeterm{h(XY)} + h(XZ) - h(X) - h(XYZ)]\nonumber\\ &-[h(XY) + h(YZ) - h(Y) - h(XYZ)]\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \positiveterm{h(XY)} &\to h(X) + h(Y|X)\\ h(Y|X) &\to h(Y|XZ) \end{aligned}\\\hline \begin{aligned}[c] &\omega h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(XY) + h(X) + \negativeterm{h(Y|XZ)} + (\omega-1) h(YZ) + (\omega-1)\positiveterm{h(XZ)}\nonumber\\ &-[h(XY) + h(YZ) - h(Y) - h(XYZ)]\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \positiveterm{h(XZ)} + \negativeterm{h(Y|XZ)} &\to h(XYZ) \end{aligned}\\\hline \begin{aligned}[c] &\omega \negativeterm{h(XYZ)} + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(XY) + h(X) + \positiveterm{h(XYZ)} + (\omega-1) h(YZ) + (\omega-2)h(XZ)\nonumber\\ &-[h(XY) + h(YZ) - h(Y) - h(XYZ)]\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \text{Cancel $h(XYZ)$ on both sides} \end{aligned}\\\hline \begin{aligned}[c] &(\omega-1) h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(XY) + h(X) + (\omega-1) \positiveterm{h(YZ)} + (\omega-2)h(XZ)\nonumber\\ &-[h(XY) + \negativeterm{h(YZ)} - h(Y) - h(XYZ)]\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \positiveterm{h(YZ)} &\to h(Y) + h(Z|Y)\\ h(Z|Y) &\to h(Z|XY) \end{aligned}\\\hline \begin{aligned}[c] &(\omega-1) h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= \positiveterm{h(XY)} + h(X) + (\omega-2) h(YZ) + h(Y) + \negativeterm{h(Z|XY)}+ (\omega-2)h(XZ)\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \positiveterm{h(XY)} + \negativeterm{h(Z|XY)} &\to h(XYZ) \end{aligned}\\\hline \begin{aligned}[c] &(\omega-1) \negativeterm{h(XYZ)} + h(X) + h(Y) + (\omega-2)h(Z) \\ &= \positiveterm{h(XYZ)} + h(X) + (\omega-2) h(YZ) + h(Y)+ (\omega-2)h(XZ)\nonumber\\ &-(\omega-2)[h(XZ) + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \text{Cancel $h(XYZ)$ on both sides} \end{aligned}\\\hline \begin{aligned}[c] &(\omega-2) h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(X) + (\omega-2) h(YZ) + h(Y)+ (\omega-2)\positiveterm{h(XZ)}\nonumber\\ &-(\omega-2)[\negativeterm{h(XZ)} + h(YZ) - h(Z) - h(XYZ)] \end{aligned}& \begin{aligned}[c] \gamma\positiveterm{h(XZ)} &\to \gamma h(Z) + \gamma h(X|Z)\\ \gamma h(X|Z) &\to \gamma h(X|YZ) \end{aligned}\\\hline \begin{aligned}[c] &(\omega-2) h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(X) + \positiveterm{(\omega-2) h(YZ)} + h(Y)+ (\omega-2)h(Z) + \negativeterm{(\omega-2)h(X|YZ)} \end{aligned}& \begin{aligned}[c] \positiveterm{\gamma h(YZ)} + \negativeterm{\gamma h(X|YZ)} &\to \gamma h(XYZ) \end{aligned}\\\hline \begin{aligned}[c] &\negativeterm{(\omega-2) h(XYZ)} + h(X) + h(Y) + (\omega-2)h(Z) \\ &= h(X) + \positiveterm{(\omega-2) h(XYZ)} + h(Y)+ (\omega-2)h(Z) \end{aligned}& \begin{aligned}[c] \text{Cancel $(\omega-2)h(XYZ)$ on both sides} \end{aligned}\\\hline \begin{aligned}[c] &\negativeterm{h(X) + h(Y) + (\omega-2)h(Z)}\\ &= \positiveterm{h(X) + h(Y)+ (\omega-2)h(Z)} \end{aligned}& \begin{aligned}[c] &\text{Cancel $h(X) + h(Y)+ (\omega-2)h(Z)$}\\ &\text{on both sides} \end{aligned}\\\hline \begin{aligned}[c] 0=0 \end{aligned}& \begin{aligned}[c] \end{aligned}\\\hline \end{array}\]

Before proving the theorem, we give an example. Figure 1 shows a compact form of the proof sequence for the \(\omega\)-Shannon-flow inequality in Eq. 13 . In particular, the proof sequence in Figure 1 combines two steps \(h(Y|X) \to h(Y|XZ)\) and \(h(XZ) + h(Y|XZ)\to h(XYZ)\) into a single step \(h(XZ) + h(Y|X) \to h(XYZ)\). Table ¿tbl:table:ps? shows the detailed proof steps for the same \(\omega\)-Shannon-flow inequality, as well as how we come up with these steps in the first place. In particular, Proposition 12 tells us that as long as \(\|\boldsymbol{\lambda}\|_1 + \|\boldsymbol{\kappa}\|_1 > 0\), there must exist some unconditional term \(h(\boldsymbol{Y}_i|\emptyset)\) on the RHS of the \(\omega\)-Shannon-flow inequality. We repeatedly rely on the existence of such unconditional term on the RHS. In particular, we start from the identity form 48 of the \(\omega\)-Shannon-flow inequality in Eq. 13 . We pick such unconditional term on the RHS, say \(h(XY)\). Since 48 is an identity and \(h(XY)\) does not appear on the LHS, it must be getting canceled with some other term on the RHS. In this case, it is being canceled by \(-h(XY)\) coming from \(-h(Y;Z|X)\). We apply the two proof steps \(h(XY) \to h(X) + h(Y|X)\) and \(h(Y|X) \to h(Y|XZ)\) to the RHS of the identity 48 and we also drop \(-h(Y;Z|X)\) from the RHS, thus resulting in a new identity. This new identity is depicted in the second row of Table ¿tbl:table:ps?. We repeat the same process until we end up with the trivial identity \(0=0\).

7.4.2 Proof of Theorem 13↩︎

For the purpose of proving the Theorem 13 in general, we will represent an \(\omega\)-Shannon-flow inequality slightly differently from Eq. 45 . In particular, some terms on the LHS of Eq. 45 might already occur on the RHS, therefore we could decompose the RHS into two parts: One part which is a subset of terms on the LHS, and another part containing the remaining RHS terms. Formally, we can represent an \(\omega\)-Shannon-flow inequality as follows: \[\begin{align} \sum_{\ell \in [L]} \lambda_\ell h(\boldsymbol{U}_{\ell}) +& \sum_{j \in [J]} \left(\alpha_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \beta_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \zeta_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \kappa_j h(\boldsymbol{G}_j)\right) \quad\leq\quad\nonumber\\ &\sum_{j \in [J]} \left(\hat{\alpha}_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \hat{\beta}_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \hat{\zeta}_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \hat{\kappa}_j h(\boldsymbol{G}_j)\right) +\sum_{i \in [I]} \hat{w}_i h(\boldsymbol{Y}_i |\boldsymbol{X}_i) \label{eq:omega-shannon-ps} \end{align}\tag{55}\] where in addition to the conditions from Definition 8, we also require that

• For all \(j \in [J]\), we have \(0\leq\hat{\alpha}_j \leq \alpha_j\), \(0\leq\hat{\beta}_j \leq \beta_j\), \(0\leq\hat{\zeta}_j \leq \zeta_j\), and \(0\leq\hat{\kappa}_j \leq \kappa_j\).

• For all \(i \in [I]\), we have \(0\leq \hat{w}_i \leq w_i\).

• Finally, we assume, for all \(j \in [J]\), \[\begin{align} \kappa_j - \hat{\kappa}_j = 0 \quad\quad\Rightarrow\quad\quad \alpha_j - \hat{\alpha}_j= \beta_j - \hat{\beta}_j= \zeta_j - \hat{\zeta}_j = 0 \label{eq:cond:well-behaved} \end{align}\tag{56}\]

By Proposition 11, for every inequality of the form 55 , there exist non-negative vectors \(\boldsymbol{m} \stackrel{\mathrm{def}}{=}(m_p)_{p \in [P]}\) and \(\boldsymbol{s} \stackrel{\mathrm{def}}{=}(s_q)_{q \in [Q]}\) such that the following identity holds over symbolic variables \(h(\boldsymbol{X})\) for \(\boldsymbol{X} \subseteq \mathcal{V}\) where \(h(\emptyset) = 0\):

\[\begin{align} \sum_{\ell \in [L]} \lambda_\ell h(\boldsymbol{U}_{\ell}) +& \sum_{j \in [J]} \left(\alpha_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \beta_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \zeta_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \kappa_j h(\boldsymbol{G}_j)\right) \quad=\quad\nonumber\\ &\sum_{j \in [J]} \left(\hat{\alpha}_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \hat{\beta}_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \hat{\zeta}_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \hat{\kappa}_j h(\boldsymbol{G}_j)\right) +\sum_{i \in [I]} \hat{w}_i h(\boldsymbol{Y}_i |\boldsymbol{X}_i)\nonumber\\ - &\sum_{p \in [P]} m_p h(\boldsymbol{Y}_p |\boldsymbol{X}_p) - \sum_{q \in [Q]} s_q h(\boldsymbol{Y}_q;\boldsymbol{Z}_q |\boldsymbol{X}_q) \label{eq:omega-shannon-ps:identity} \end{align}\tag{57}\]

7.5 \(\omega\)-Disjunctive Datalog Rules↩︎

The original \(\mathsf{PANDA}\) algorithm from [2], [3], [5] evaluates a BCQ in submodular width time by reducing the problem to evaluating a collection of Disjunctive Datalog rules (DDRs), which were reviewed in Section 3.6. For the purpose of designing a general algorithm for evaluating a BCQ in \(\omega\)-submodular width time, we will need to generalize the concept of DDRs. In this section, we present our generalization of DDRs, called \(\omega\)-DDRs. In Section 7.6, we present an algorithm for evaluating \(\omega\)-DDRs. Finally, in Section 7.7, we show how to evaluate a BCQ \(Q\) in \(\omega\)-submodular width time by reducing the problem to evaluating a collection of \(\omega\)-DDRs, each of which is evaluated using the algorithm from Section 7.6.

7.5.1 A new notion of model for an \(\omega\)-DDR↩︎

For the purpose of evaluating an \(\omega\)-DDR in our target runtime bounds, we need a different notion of a model for an \(\omega\)-DDR, where the model is described through sub-probability measures rather than relations. This follows the \(\textsf{PANDAExpress}\) approach [5] in order to avoid unnecessary \(\text{\sf polylog}\)-factors in the runtime. See Section 3.8 for some background on sub-probability measures.

Recall from Section 3.8 that we use \(p_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{t})\) as a shorthand for \(p_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{t}_{\boldsymbol{Y}}|\boldsymbol{t}_{\boldsymbol{X}})\).

7.5.2 Performing matrix multiplication over models of \(\omega\)-DDRs↩︎

In order to evaluate a BCQ \(Q\) in \(\omega\)-submodular width time, we will describe in Section 7.7 a reduction from evaluating \(Q\) to evaluating a collection of \(\omega\)-DDRs. After we evaluate these \(\omega\)-DDRs, we will need to perform some fast matrix multiplication operations on the outputs (models) of these \(\omega\)-DDRs. We describe below how to do that efficiently. The extra \(\log^2\) factor in our main theorem, Theorem [thm:panda:osubw], is inherited from the following lemma.

7.6 Evaluating \(\omega\)-Disjunctive Datalog Rules↩︎

In the previous section, we introduced a generalization of DDRs, called \(\omega\)-DDRs. We now present an algorithm for evaluating these \(\omega\)-DDRs. This algorithm will be used as a building block for our final algorithm for evaluating a BCQ \(Q\) in \(\omega\)-submodular width time in Section 7.7.

7.6.1 Example of the \(\textsf{\omega-PANDAExpress}\) algorithm↩︎

\[\small \begin{array}{|l|l|} \hline \rowcolor{lightgray}\text{\bf $\omega$-Shannon-flow Inequality and Steps} & \text{\bf Probabilistic Inequality and Steps}\\\hline \rowcolor{lightergray} \begin{aligned}[t] &\omega h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &\leq{\color{blue}2h(XY) + (\omega-1) h(YZ) + (\omega-1)h(XZ)}\\ & {\color{blue}\leq 2\omega} \end{aligned}& \begin{aligned}[t] {\color{red}p_{XY}(xy)^2\cdot p_{YZ}(yz)^{\omega-1} \cdot p_{XZ}(xz)^{\omega-1} \geq \frac{1}{N^{2\omega}}} = \frac{1}{B^{\omega+1}}\\ p_{XY}(xy) \defeq \frac{1}{N},\quad p_{YZ}(yz) \defeq \frac{1}{N},\quad p_{XZ}(xz) \defeq \frac{1}{N} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(XY) \to h(X) + h(Y|X) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{XY}(xy) \to p_X(x) \cdot p_{Y|X}(y|x)}\\ &p_X(x) \defeq \sum_{y} p_{XY}(xy) = \frac{\deg_R(Y|X=x)}{N}\\ &p_{Y|X}(y|x) \defeq \frac{p_{XY}(xy)}{p_X(x)} = \frac{1}{\deg_R(Y|X=x)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(Y|X) \to h(Y|XZ) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{Y|X}(y|x) \to p_{Y|XZ}(y|xz)}\\ &p_{Y|XZ}(y|xz) \defeq p_{Y|X}(y|x) = \frac{1}{\deg_R(Y|X=x)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(XZ) + h(Y|XZ) \to h(XYZ) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{XZ}(xz) \cdot p_{Y|XZ}(y|xz) \to p'_{XYZ}(xyz)}\\ &p'_{XYZ}(xyz) \defeq p_{XZ}(xz) \cdot p_{Y|XZ}(y|xz) = \frac{1}{N\cdot\deg_R(Y|X=x)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(YZ) \to h(Y) + h(Z|Y) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{YZ}(yz) \to p_Y(y) \cdot p_{Z|Y}(z|y)}\\ &p_Y(y) \defeq \sum_{z} p_{YZ}(yz) = \frac{\deg_S(Z|Y=y)}{N}\\ &p_{Z|Y}(z|y) \defeq \frac{p_{YZ}(yz)}{p_Y(y)} = \frac{1}{\deg_S(Z|Y=y)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(Z|Y) \to h(Z|XY) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{Z|Y}(z|y) \to p_{Z|XY}(z|xy)}\\ &p_{Z|XY}(z|xy) \defeq p_{Z|Y}(z|y) = \frac{1}{\deg_S(Z|Y=y)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}h(XY) + h(Z|XY) \to h(XYZ) \end{aligned}& \begin{aligned}[t] &{\color{red} p_{XY}(xy) \cdot p_{Z|XY}(z|xy) \to p''_{XYZ}(xyz)}\\ &p''_{XYZ}(xyz) \defeq p_{XY}(xy) \cdot p_{Z|XY}(z|xy) = \frac{1}{N\cdot\deg_S(Z|Y=y)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}\gamma h(XZ) \to \gamma h(Z) + \gamma h(X|Z) \end{aligned}& \begin{aligned}[t] &{\color{red}p_{XZ}(xz)^\gamma \to p_Z(z)^\gamma \cdot p_{X|Z}(x|z)^\gamma}\\ &p_Z(z) \defeq \sum_{x} p_{XZ}(xz) = \frac{\deg_T(X|Z=z)}{N}\\ &p_{X|Z}(x|z) \defeq \frac{p_{XZ}(xz)}{p_Z(z)} = \frac{1}{\deg_T(X|Z=z)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}\gamma h(X|Z) \to \gamma h(X|YZ) \end{aligned}& \begin{aligned}[t] &{\color{red}p_{X|Z}(x|z)^\gamma \to p_{X|YZ}(x|yz)^\gamma}\\ &p_{X|YZ}(x|yz) \defeq p_{X|Z}(x|z) = \frac{1}{\deg_T(X|Z=z)} \end{aligned}\\\hline \begin{aligned}[t] &\color{blue}\gamma h(YZ) + \gamma h(X|YZ) \to \gamma h(XYZ) \end{aligned}& \begin{aligned}[t] &{\color{red}p_{YZ}(yz)^\gamma \cdot p_{X|YZ}(x|yz)^\gamma \to p'''_{XYZ}(xyz)^\gamma}\\ &p'''_{XYZ}(xyz) \defeq p_{YZ}(yz) \cdot p_{X|YZ}(x|yz) = \frac{1}{N\cdot\deg_T(X|Z=z)} \end{aligned}\\\hline \rowcolor{lightergray} \begin{aligned}[t] &\omega h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z) \\ &\leq{\color{blue}h(XYZ) + h(X) + h(Y) + (\omega-2)h(Z)} \\ & {\color{blue}\leq 2\omega} \end{aligned}& \begin{aligned}[t] &\color{red}p'_{XYZ}(xyz) \cdot p''_{XYZ}(xyz) \cdot p'''_{XYZ}(xyz)^{\omega-2}\cdot p_X(x) \cdot p_Y(y) \cdot p_Z(z)^{\omega-2} \\ & {\color{red}\geq \frac{1}{N^{2\omega}}} = \frac{1}{B^{\omega+1}} \end{aligned}\\\hline \end{array}\]

Before describing the general \(\textsf{\omega-PANDAExpress}\) algorithm and proving the associated Theorem 15, we start in this section with an example that illustrates the main ideas behind the algorithm and its analysis. Consider the following \(\omega\)-DDR, whose body is the same as \(Q_\triangle\) from Eq. 2 , and whose head consists of one join target and one MM target: \[\begin{align} P_1(X, Y, Z) \vee (S_1(X) \wedge T_1(Y) \wedge W_1(Z)) \quad\text{ :- }\quad R(X, Y) \wedge S(Y, Z) \wedge T(X, Z) \label{eq:pandaexpress:ddr} \end{align}\tag{70}\] Suppose that \(|R| = |S| = |T| = N\). Consider the \(\omega\)-Shannon-flow inequality 13 (or equivalently 46 ). The quantity \(B\) from Eq. 69 becomes: \[\begin{align} B \stackrel{\mathrm{def}}{=}N^{\frac{2\omega}{\omega+1}} \end{align}\] Note that \(\frac{2\omega}{\omega+1}\) is the optimal objective value of the LP 12 , which gave us the \(\omega\)-Shannon-flow inequality 13 in the first place. This is not a coincidence, as we will see later (Lemma 3). We explain here how we can utilize the \(\omega\)-Shannon-flow inequality 13 in order to compute a \(B\)-probabilistic model to the \(\omega\)-DDR 70 in time \(O(B)\). (The extra \(\log N\) is not needed in this example.)

The RHS of inequality 13 is as follows: \[\begin{align} 2h(XY) + (\omega-1) h(YZ) + (\omega-1)h(XZ) \quad\leq\quad 2\omega \label{eq:opnadaexpress:shannon:ineq} \end{align}\tag{71}\] We initialize three probability distribution \(p_{XY}(xy)\), \(p_{YZ}(yz)\), and \(p_{XZ}(xz)\) to be uniform, i.e., equal to \(1/N\) over the relations \(R\), \(S\), and \(T\), respectively. Now, we have the following probabilistic inequality, which we think of as the probabilistic interpretation of inequality 71 : \[\begin{align} p_{XY}(xy)^2\cdot p_{YZ}(yz)^{\omega-1} \cdot p_{XZ}(xz)^{\omega-1} \quad\geq\quad \frac{1}{N^{2\omega}} = \frac{1}{B^{\omega+1}} \label{eq:opnadaexpress:prob:ineq} \end{align}\tag{72}\] The proof sequence given earlier in Table ¿tbl:table:ps? transforms the RHS of the \(\omega\)-Shannon-flow inequality 13 into the LHS. Every time we apply a proof step, we mirror it in the probabilistic world by applying a corresponding transformation on inequality 72 . The process is illustrated in Table ¿tbl:table:opandaexpress?. For example, to mirror the step \(h(XY) \to h(X) + h(Y|X)\), we replace the term \(p_{XY}(xy)\) in inequality 72 with the product \(p_X(x) \cdot p_{Y|X}(y|x)\), where \(p_X(x)\) and \(p_{Y|X}(y|x)\) are the marginal and conditional measures from Eq. ?? and Eq. ?? , respectively. By Eq. ?? and ?? , this replacement preserves inequality 72 .

At the end of the above process, we would have constructed distributions \(p'_{XYZ}\), \(p''_{XYZ}\), \(p'''_{XYZ}\), \(p_X\), \(p_Y\), and \(p_Z\) that satisfy inequality 72 which now takes the following form: \[\begin{align} p'_{XYZ}(xyz) \cdot p''_{XYZ}(xyz) \cdot p'''_{XYZ}(xyz)^{\omega-2}\cdot p_X(x) \cdot p_Y(y) \cdot p_Z(z)^{\omega-2} \geq \frac{1}{N^{2\omega}} = \frac{1}{B^{\omega+1}} \label{eq:opnadaexpress:prob:ineq:final} \end{align}\tag{73}\] The \(\textsf{\omega-PANDAExpress}\) algorithm works by going through the sequence of probability distributions defined in Table ¿tbl:table:opandaexpress? and actually computing them one by one (by materializing their supports along with the associated probabilities). But there is a catch: For the distributions \(p'_{XYZ}\), \(p''_{XYZ}\), and \(p'''_{XYZ}\), we cannot afford to materialize their full supports, since their sizes could exceed \(B\). Instead, we truncate them by keeping only the tuples that have probability at least \(1/B\). This guarantees that, after truncation, each one of these distributions will have support size of at most \(B\). But what about tuples that were truncated away in the above process? This is were inequality 73 comes to the rescue. These tuples \(xyz\) that were truncated away must have \(p'_{XYZ}(xyz)\), \(p''_{XYZ}(xyz)\), \(p'''_{XYZ}(xyz) < 1/B\). Substituting this into inequality 73 , we get \[\begin{align} p_X(x)\cdot p_Y(y) \cdot p_Z(z)^{\omega-2} \quad\geq\quad \frac{B^\omega}{B^{\omega+1}} = \frac{1}{B} \end{align}\] Therefore, we can report the distributions \((p_X, p_Y, p_Z)\) along with the \(\omega\)-dominant triple \((1, 1, \gamma)\) as a probabilistic interpretation of the MM target \((\{S_1(X), T_1(Y)\}, W_1(Z))\) of the \(\omega\)-DDR 70 . By Eq. 61 , the \(B\)-support covers all tuples \(xyz\) that were truncated away. Therefore, if we return a \(B\)-probabilistic model that contains this probabilistic interpretation of the MM target, along with the (geometric mean of the) truncated distributions \(p'_{XYZ}\), \(p''_{XYZ}\), and \(p'''_{XYZ}\) as the probabilistic interpretation of the join target \(P_1(X, Y, Z)\), then this is indeed a valid \(B\)-probabilistic model of the \(\omega\)-DDR 70 (Definition 12).

Earlier in Section 2.5, we have seen a simpler algorithm, depicted in Figure 1, where there was no mentioning of probability distributions. Instead, we just performed a join, say \(T(X,Z) \Join R_\ell(X, Y)\), over all \(X\)-values that are light, i.e., have degree \(\leq \Delta \stackrel{\mathrm{def}}{=}N^{\frac{\omega-1}{\omega+1}}\). But how are the two algorithms related? The answer is that they are one and the same! In particular, in the above \(\textsf{\omega-PANDAExpress}\) algorithm, the truncation condition \(p'_{XYZ}(xyz) \geq 1/B\) corresponds to: \[\begin{align} \frac{1}{N\cdot\deg_R(Y|X=x)} \geq \frac{1}{B} = \frac{1}{N^{\frac{2\omega}{\omega+1}}} \end{align}\] which is equivalent to \(\deg_R(Y|X=x) \leq N^{\frac{\omega-1}{\omega+1}} = \Delta\). In general, the \(\textsf{\omega-PANDAExpress}\) algorithm is a generic way to come up with the right partitioning strategies based on degrees, in order to achieve the desired runtime bounds.

7.6.2 Description of the \(\textsf{\omega-PANDAExpress}\) algorithm↩︎

Now that we have seen an example of the \(\textsf{\omega-PANDAExpress}\) algorithm for a specific \(\omega\)-DDR, we are ready to describe the general algorithm for any \(\omega\)-DDR. The \(\omega\)-PANDAExpress algorithm generalizes the \(\textsf{PANDAExpress}\) algorithm from [5], and it is given in Algorithm 4. We describe it here in detail. It is a recursive algorithm that takes two input arguments:

• An integral \(\omega\)-Shannon-flow inequality \(\mathcal{I}\) of the form 45 .

• A collection, \(\mathcal{P}\), of sub-probability measures: one measure \(p_{\boldsymbol{Y}_i|\boldsymbol{X}_i}\) for each term \(w_i h(\boldsymbol{Y}_i|\boldsymbol{X}_i)\) on the RHS of inequality \(\mathcal{I}\).

For the outer-most call to \(\textsf{\omega-PANDAExpress}\), the inequality \(\mathcal{I}\) is set to be the integral \(\omega\)-Shannon-flow inequality from the statement of Theorem 15. Also, for this outer-most call, the collection \(\mathcal{P}\) is initialized from the input database instance \(D\) with schema \(\Sigma_\text{\sf in}\) from Theorem 15 as follows: For each term \(w_i h(\boldsymbol{Y}_i|\boldsymbol{X}_i)\) on the RHS of inequality 45 , let \(R_i\in\Sigma_\text{\sf in}\) be a relation that minimizes the degree \(\deg_{R_i}(\boldsymbol{Y}_i|\boldsymbol{X}_i)\), i.e., where \(\deg_{R_i}(\boldsymbol{Y}_i|\boldsymbol{X}_i) = \deg_{\Sigma_\text{\sf in}}(\boldsymbol{Y}_i|\boldsymbol{X}_i)\). Then, the associated sub-probability measure \(p_{\boldsymbol{Y}_i|\boldsymbol{X}_i} \in \mathcal{P}\) is initialized as follows: (Recall the notation \({R}_{|\boldsymbol{X}\cup\boldsymbol{Y}}\) from Section 3.7.) \[\begin{align} p_{\boldsymbol{Y}_i|\boldsymbol{X}_i}(\boldsymbol{y}_i | \boldsymbol{x}_i) \stackrel{\mathrm{def}}{=} \begin{cases} \frac{1}{\deg_{R_i}(\boldsymbol{Y}_i|\boldsymbol{X}_i=\boldsymbol{x}_i)} & \text{if }(\boldsymbol{x}_i, \boldsymbol{y}_i) \in {R_i}_{|\boldsymbol{X}_i\cup\boldsymbol{Y}_i} \\ 0 & \text{otherwise} \end{cases} \label{eq:initial:measure} \end{align}\tag{74}\]

The algorithm proceed as follows:

• If there is no term left on the LHS of the inequality \(\mathcal{I}\), i.e., if we end up with \(\|\boldsymbol{\lambda}\|_1 + \|\boldsymbol{\kappa}\|_1 = 0\) (line [line:opanda-express:no-targets] of Algorithm 4), then we return immediately with an empty \(B\)-probabilistic model to the \(\omega\)-DDR.

• If there is one term \(h(\boldsymbol{U}_\ell)\) on the LHS of \(\mathcal{I}\) that also appears on the RHS as a term \(h(\boldsymbol{Y}_i|\boldsymbol{X}_i)\) (which means \(\boldsymbol{X}_i = \emptyset\) and \(\boldsymbol{Y}_i=\boldsymbol{U}_\ell\)), then we return a \(B\)-probabilistic model containing only the corresponding sub-probability measure \(p_{\boldsymbol{U}_\ell}\). This measure \(p_{\boldsymbol{U}_\ell}\) serves as a probabilistic interpretation of the join target \(P_\ell(\boldsymbol{U}_\ell)\) of the \(\omega\)-DDR 60 .

• If there is a sum \(\alpha_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \beta_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \zeta_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \kappa_j h(\boldsymbol{G}_j)\) on the LHS of \(\mathcal{I}\) that appears in full on the RHS, then we construct a \(B\)-probabilistic model \(\Sigma_\text{\sf out}^l\) containing only the tuple \(((p_{\boldsymbol{G}_j}, p_{\boldsymbol{X}_j|\boldsymbol{G}_j}, p_{\boldsymbol{Y}_j|\boldsymbol{G}_j}, p_{\boldsymbol{Z}_j|\boldsymbol{G}_j}), (\alpha_j/\kappa_j, \beta_j/\kappa_j, \zeta_j/\kappa_j))\). This tuple serves as a probabilistic interpretation of the MM target \((\{S_j(\boldsymbol{X}_j \boldsymbol{G}_j), T_j(\boldsymbol{Y}_j \boldsymbol{G}_j)\}, W_j(\boldsymbol{Z}_j\boldsymbol{G}_j))\) of the \(\omega\)-DDR 60 . We do not immediately return \(\Sigma_\text{\sf out}^l\) in this case. Instead, we also drop \(\alpha_j h(\boldsymbol{X}_j|\boldsymbol{G}_j) + \beta_j h(\boldsymbol{Y}_j|\boldsymbol{G}_j) + \zeta_j h(\boldsymbol{Z}_j|\boldsymbol{G}_j) + \kappa_j h(\boldsymbol{G}_j)\) from both sides of \(\mathcal{I}\), and recursively call the algorithm on the resulting \(\mathcal{I}\) to compute another \(B\)-probabilistic model \(\Sigma_\text{\sf out}^h\). We return the union of the two models.

• Otherwise, we proceed very similarly to the original \(\textsf{PANDAExpress}\) algorithm from [5]. In particular, by Theorem 13, \(\mathcal{I}\) must have a proof sequence. Let \(s\) be the first step in the sequence. We use a sub-routine called \(\textsf{apply-step}\) from [5] (reviewed below) to apply the proof step \(s\) to update the RHS of the inequality \(\mathcal{I}\) and also mirror these changes into \(\mathcal{P}\). (Recall that each term on the RHS of \(\mathcal{I}\) is associated with a sub-probability measure in \(\mathcal{P}\), hence when we update the first, we have to update the second.) Let \(\mathcal{I}^l\) and \(\mathcal{P}^l\) be the new \(\mathcal{I}\) and \(\mathcal{P}\) after \(\textsf{apply-step}\), respectively. We call the algorithm recursively on \(\mathcal{I}^l\) and \(\mathcal{P}^l\) to compute a \(B\)-probabilistic model \(\Sigma_\text{\sf out}^l\). Now we recognize two cases:

  • If the proof step \(s\) is not a composition step, then we return \(\Sigma_\text{\sf out}^l\).

  • Otherwise, i.e., if \(s\) has the form \(h(\boldsymbol{X}) + h(\boldsymbol{Y}|\boldsymbol{X})\to h(\boldsymbol{X}\boldsymbol{Y})\), then applying this step to the RHS of \(\mathcal{I}\) must have resulted in an inequality \(\mathcal{I}^l\) whose RHS contains \(h(\boldsymbol{X}\boldsymbol{Y})\). We use the reset lemma (Lemma 1) to drop this term \(h(\boldsymbol{X}\boldsymbol{Y})\) from the RHS of \(\mathcal{I}^l\) and also drop the corresponding sub-probability measure from \(\mathcal{P}^l\), resulting in \(\mathcal{I}^h\) and \(\mathcal{P}^h\) respectively. Now, we recursively call the algorithm on \(\mathcal{I}^h\) and \(\mathcal{P}^h\) to compute another \(B\)-probabilistic model \(\Sigma_\text{\sf out}^h\), and we return the union of \(\Sigma_\text{\sf out}^h\) and the previously computed \(\Sigma_\text{\sf out}^l\).

For sake of completeness, we describe here the \(\textsf{apply-step}\) sub-routine, which goes back to the original \(\textsf{PANDAExpress}\) algorithm [5]:

• If \(s\) is a decomposition step \(h(\boldsymbol{X} \boldsymbol{Y}) \to h(\boldsymbol{X}) + h(\boldsymbol{Y} | \boldsymbol{X})\), then let \(p_{\boldsymbol{X}}\) be the marginal measure ?? of \(p_{\boldsymbol{X} \boldsymbol{Y}}\) on \(\boldsymbol{X}\) and \(p_{\boldsymbol{Y} | \boldsymbol{X}}\) be the conditional measure ?? of \(p_{\boldsymbol{X} \boldsymbol{Y}}\) on \(\boldsymbol{Y}\) given \(\boldsymbol{X}\). The new inequality \(\mathcal{I}^\ell\) results from \(\mathcal{I}\) by replacing the term \(h(\boldsymbol{X} \boldsymbol{Y})\) on the RHS of \(\mathcal{I}\) with the two terms \(h(\boldsymbol{X})\) and \(h(\boldsymbol{Y} | \boldsymbol{X})\). The new set of sub-probability measures \(\mathcal{P}^\ell\) results from \(\mathcal{P}\) by replacing \(p_{\boldsymbol{X}\boldsymbol{Y}}\) with the two measures \(p_{\boldsymbol{X}}\) and \(p_{\boldsymbol{Y} | \boldsymbol{X}}\).

• If \(s\) is a submodularity step \(h(\boldsymbol{Y} | \boldsymbol{X}) \to h(\boldsymbol{Y} | \boldsymbol{X} \boldsymbol{Z})\), then define \(p_{\boldsymbol{Y} | \boldsymbol{X} \boldsymbol{Z}} \stackrel{\mathrm{def}}{=}p_{\boldsymbol{Y} | \boldsymbol{X}}\). The new \(\mathcal{I}^\ell\) results from \(\mathcal{I}\) by replacing \(h(\boldsymbol{Y} | \boldsymbol{X})\) with \(h(\boldsymbol{Y} | \boldsymbol{X} \boldsymbol{Z})\) on the RHS, whereas the new \(\mathcal{P}^\ell\) results from \(\mathcal{P}\) by replacing \(p_{\boldsymbol{Y} | \boldsymbol{X}}\) with \(p_{\boldsymbol{Y} | \boldsymbol{X} \boldsymbol{Z}}\).

• If \(s\) is a monotonicity step \(h(\boldsymbol{X} \boldsymbol{Y}) \to h(\boldsymbol{X})\), then define \(p_{\boldsymbol{X}}\) as the marginal measure ?? of \(p_{\boldsymbol{X} \boldsymbol{Y}}\) on \(\boldsymbol{X}\). The new \(\mathcal{I}^\ell\) results from \(\mathcal{I}\) by replacing \(h(\boldsymbol{X} \boldsymbol{Y})\) with \(h(\boldsymbol{X})\) on the RHS, whereas the new \(\mathcal{P}^\ell\) results from \(\mathcal{P}\) by replacing \(p_{\boldsymbol{X}\boldsymbol{Y}}\) with \(p_{\boldsymbol{X}}\).

• If \(s\) is a composition step \(h(\boldsymbol{X}) + h(\boldsymbol{Y} | \boldsymbol{X}) \to h(\boldsymbol{X} \boldsymbol{Y})\), then let \(p_{\boldsymbol{X}\boldsymbol{Y}}\) be the truncated product measure: \[\begin{align} p_{\boldsymbol{X} \boldsymbol{Y}}(\boldsymbol{x}, \boldsymbol{y}) \stackrel{\mathrm{def}}{=} \begin{cases} p_{\boldsymbol{X}}(\boldsymbol{x}) \cdot p_{\boldsymbol{Y} | \boldsymbol{X}}(\boldsymbol{y} | \boldsymbol{x}), & \text{if } p_{\boldsymbol{X}}(\boldsymbol{x}) \cdot p_{\boldsymbol{Y} | \boldsymbol{X}}(\boldsymbol{y} | \boldsymbol{x}) \geq 1/B \\ 0, & \text{otherwise} \end{cases} \label{eqn:truncated:product} \end{align}\tag{75}\] The new \(\mathcal{I}^\ell\) results from \(\mathcal{I}\) by replacing the two terms \(h(\boldsymbol{X})\) and \(h(\boldsymbol{Y} | \boldsymbol{X})\) on the RHS of \(\mathcal{I}\) with the single term \(h(\boldsymbol{X} \boldsymbol{Y})\), whereas the new \(\mathcal{P}^\ell\) results from \(\mathcal{P}\) by replacing the two measures \(p_{\boldsymbol{X}}\) and \(p_{\boldsymbol{Y} | \boldsymbol{X}}\) with the truncated product measure \(p_{\boldsymbol{X}\boldsymbol{Y}}\).

7.6.3 Correctness and runtime analysis of \(\textsf{\omega-PANDAExpress}\)↩︎

We now prove Theorem 15 by proving both correctness and the runtime bound of \(\textsf{\omega-PANDAExpress}\).

7.7 Evaluating a BCQ \(Q\) in \(\omega\)-submodular width time↩︎

We are now ready to prove Theorem [thm:panda:osubw] about answering Boolean conjunctive queries in \(\omega\)-submodular width time.

In order to prove Theorem [thm:panda:osubw], we will need some further preliminaries. The following lemma is very similar to a lemma in [2], [3]. Its proof relies on the observation that every feasible dual solution to the linear program 39 corresponds to an \(\omega\)-Shannon-flow inequality 45 of a certain structure. By strong duality, if we pick an optimal dual solution, we can match the optimal objective value of the (primal) LP 39 .

Given a hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) and a generalized variable elimination order \(\overline{\boldsymbol{\sigma}} =\) \((\boldsymbol{X}_1, \boldsymbol{X}_2, \ldots, \boldsymbol{X}_{|\overline{\boldsymbol{\sigma}}|})\) \(\in\overline{\pi}(\mathcal{V})\), each set of vertices \(\boldsymbol{X}_i\) can be eliminated by either a join algorithm or some matrix multiplication. The concept of an \(\omega\)-query plan, that we define below, amends a generalized variable elimination order with a mapping that specifies how to eliminate each variable.

Note that, for a given hypergraph \(\mathcal{H}\), the number of \(\omega\)-query plans is finite.

7.8 A more advanced example: The 4-cycle query↩︎

None

None

Consider the 4-cycle BCQ \(Q_\square\) from Eq. 4 . As explained earlier in Table 2, the \(\omega\)-submodular width of \(Q_\square\) is exactly \(2 - \frac{3}{2\cdot \min\{\omega,\frac{5}{2}\}+1}\). See Lemma 8 in the Appendix for a proof. When \(\omega \leq 5/2\), this expression simplifies to \(\frac{4\omega-1}{2\omega+1}\), thus matching the exponent in the runtime \(O\left(N^{\frac{4\omega-1}{2\omega+1}}\right)\) from prior work [18], [21], as shown in Table 1. In contrast, when \(\omega \geq 5/2\), the expression simplifies to \(3/2\), thus matching the exponent in the well-known runtime \(O\left(N^{3/2}\right)\) from [5], [15].

The hypergraph of \(Q_\square\) is as follows: \[\begin{align} \mathcal{H}_{\square}= (\{X,Y,Z,W\},\quad \{\{X,Y\}, \{Y,Z\}, \{Z,W\}, \{W,X\}\}) \label{eq:4cycle:H} \end{align}\tag{98}\] The corresponding \(\omega\)-submodular width expression from Eq. ?? is: \[\begin{align} \textsf{\omega-subw}(\mathcal{H}_{\square}) = \max_{h \in \Gamma \cap \mathsf{ED}} \min \bigl(& \max(\min(h(XYZ), \mathsf{MM}(X; Y; Z)), \min(h(ZWX), \mathsf{MM}(Z; W; X))),\nonumber\\ &\max(\min(h(YZW), \mathsf{MM}(Y; Z; W)), \min(h(WXY), \mathsf{MM}(W; X; Y))) \bigr)& \label{eq:osubw:4cycle} \end{align}\tag{99}\] In particular, Eq. 99 suggests that the 4-cycle query \(Q_{\square}\) admits basically two kinds of \(\omega\)-query plans:

• \(\omega\)-query plans that start by eliminating either \(Y\) or \(W\):

  • Eliminating \(Y\) involves the variables \(X, Y, Z\) and can be done by either a join or an MM.

  • Eliminating \(W\) involves the variables \(Z, W, X\) and can also be done by either a join or an MM.

• \(\omega\)-query plans that start by eliminating either \(X\) or \(Z\):

  • Eliminating \(Z\) involves the variables \(Y, Z, W\) and can be done by either a join or an MM.

  • Eliminating \(X\) involves the variables \(W, X, Y\) and can also be done by either a join or an MM.

By distributing every \(\min\) over inner \(\max\) in Eq. 99 following Eq. 37 , we get the expression for \(\textsf{\omega-subw}(\mathcal{H}_{\square})\) given in Figure 5, which has 36 terms of the form \(\max_{h \in \Gamma \cap \mathsf{ED}}\cdots\). Each one of these 36 terms is upper bounded by \(\textsf{\omega-subw}(\mathcal{H}_{\square})\). Moreover, each one of these terms corresponds to an \(\omega\)-DDR of the form 91 . The 36 \(\omega\)-DDRs are depicted in Figure 6. Each \(\omega\)-DDR has four targets: two join targets and two MM targets. Recall that in an MM target, e.g., \((S_1(X) \wedge T_1(Y) \wedge W_1(Z))\), the relations \(S_1\) and \(T_1\) are interchangeable whereas \(W_1\) plays a distinct role in the definition of a \(B\)-probabilistic model for this MM target (Definition 12). A target selector \(\mathcal{T}\) picks one target from each of the 36 \(\omega\)-DDRs, hence the total number of target selectors is \(4^{36}\). Proposition 21 guarantees that if we pick any of those target selectors, then at least one of the above \(\omega\)-query plans will be supported. For example, consider the highlighted target selector in Figure 6. This target selector is chosen carefully to avoid supporting any \(\omega\)-query plan that starts with eliminating \(Y\) or \(W\). However, while constructing such a target selector, eventually we run out of options and we end up being cornered into supporting some other \(\omega\)-query plan. In this particular case, we end up supporting the \(\omega\)-query plan that starts with eliminating \(Z\) by a join \(h(YZW)\) and eliminating \(X\) by an MM \(\mathsf{MM}(W; X; Y)\). This is the only supported \(\omega\)-query plan for this target selector.

Suppose for now that we already evaluated the \(\omega\)-DDRs from Figure 6; we will come back shortly to explain how to evaluate them. In order to evaluate the original BCQ \(Q_{\square}\), the algorithm is to go over the target selectors, and for each one, to use the supported \(\omega\)-query plan to evaluate \(Q_{\square}\) filtered by the targets in this \(\omega\)-query plan, which are a subset of the targets in the target selector. Completeness follows from Proposition 23, which guarantees that if we compute a \(\overline{B}\)-probabilistic model for each of the 36 \(\omega\)-DDRs, then every tuple \(\boldsymbol{t} \in \mathlarger{\mathlarger{\mathlarger{\Join}}}\Sigma_\text{\sf in}\) is accounted for by some target selector.

We now explain briefly how to evaluate the \(\omega\)-DDRs from Figure 6. Let’s pick the eighth \(\omega\)-DDR as an example: \[\begin{gather} P_{8}(XYZ) \quad\vee\quad (S_{8}(X) \wedge T_{8}(Z) \wedge W_{8}(Y)) \quad\vee\quad P'_{8}(YZW) \quad\vee\quad (S'_{8}(Y) \wedge T'_{8}(W) \wedge W'_{8}(Z)) \text{ :- }\\ R(X, Y) \wedge S(Y, Z) \wedge T(Z, W) \wedge U(W, X) \label{eq:omega-ddr:4cycle:example} \end{gather}\tag{100}\] The corresponding term from Figure 5 is \(\text{highlighted}\). We repeat it below: \[\begin{align} \max_{h \in \Gamma \cap \mathsf{ED}}\quad\min(h(XYZ),\quad h(X) + \gamma h(Y) + h(Z),\quad h(YZW),\quad h(Y) + \gamma h(Z) + h(W)) \label{eq:osubw:4cycle:example} \end{align}\tag{101}\] By the equation from Figure 5, we know that the quantity in Eq. 101 is upper bounded by \(\textsf{\omega-subw}(\mathcal{H}_{\square})\), which is \(\frac{4\omega-1}{2\omega+1}\) assuming \(\omega \leq 5/2\). In this particular case, the quantity from Eq. 101 is exactly the \(\omega\)-submodular width. This quantity is equivalent to the optimal objective value of the following linear program of the form 39 : \[\begin{align} \max_{t, \boldsymbol{h} \in \Gamma \cap \mathsf{ED}} \bigl\{ t \quad\mid\quad &t \leq h(XYZ),\nonumber\\ &t \leq h(X) + \gamma h(Y) + h(Z),\nonumber\\ &t \leq h(YZW),\nonumber\\ &t \leq h(Y) + \gamma h(Z) + h(W) \bigr\} \label{eq:osubw:4cycle:lp} \end{align}\tag{102}\] Lemma 3 suggests that the optimal dual solution to the above LP corresponds to the following \(\omega\)-Shannon-flow inequality: \[\begin{gather} (\omega-1) h(XYZ) + \omega h(YZW) + (h(X) + \gamma h(Y) + h(Z)) + (h(Y) + \gamma h(Z) + h(W)) \leq\\ \omega h(XY) + (2\omega-2) h(YZ) + \omega h(ZW) + h(WX) \label{eq:osubw:4cycle:shannon-flow} \end{gather}\tag{103}\] Note that the RHS of the above inequality is upper bounded by \(4\omega-1\) because \(\boldsymbol{h}\in\mathsf{ED}\). Moreover, the LHS is lower bounded by \((2\omega+1)t\). Hence, this inequality proves that \(t\) is upper bounded by \(\frac{4\omega-1}{2\omega+1}\), which is the optimal objective value of the LP from 102 . Inequality 103 is a Shannon inequality specifically because it is a sum of the following basic Shannon inequalities: \[\begin{align} &h(XY) + h(WX) - h(X) - h(XYW) \geq 0\\ &h(XYW) - h(YW) \geq 0\\ &h(YW) + h(ZW) - h(W) - h(YZW) \geq 0\\ &(\omega-1)h(XY) + (\omega-1)h(YZ) - (\omega-1)h(Y) - (\omega-1)h(XYZ) \geq 0\\ &(\omega-1)h(YZ) + (\omega-1)h(ZW) - (\omega-1)h(Z) - (\omega-1)h(YZW) \geq 0 \end{align}\] By Theorem 15, the \(\textsf{\omega-PANDAExpress}\) algorithm (Algorithm 4) takes inequality 103 along with the collection \(\mathcal{P}\) of sub-probability measures from Eq. 74 which correspond to the RHS of 103 , and computes a \(B\)-probabilistic model for the \(\omega\)-DDR from Eq. 100 , where \(B = N^{\frac{4\omega-1}{2\omega+1}}=N^{\textsf{\omega-subw}(Q_{\square})}\), in time \(O(B \cdot \log N)\). The other \(\omega\)-DDRs from Figure 6 are evaluated similarly.

8 Related Work↩︎

Fast matrix multiplication has recently attracted a lot of attention in the database community for processing join-project queries. Let \(\textsf{OUT}\) be the number of query results. Note that for Boolean conjunctive queries that we study in this paper, the output is a Boolean value, hence \(\textsf{OUT}= 1\). Let \(\overline{\omega} (a,b,c)\) be the smallest exponent for multiplying two rectangular matrices of dimensions \(n^a \times n^b\) and \(n^b \times n^c\) within \(O\left(n^{ \overline{\omega} (a,b,c)}\right)\) time. For the purpose of analyzing the complexity of rectangular matrix multiplication, several constants have been defined, namely, \(\alpha \le 1\) defined as the largest constant such that \(\overline{\omega} (1,\alpha,1)=2\), and \(\mu\) defined as the (unique) solution to the equation \(\overline{\omega} (\mu, 1, 1) = 2\mu + 1\). Note that \(\alpha = 1\) if and only if \(\omega=2\), and the current best bounds on \(\alpha\) are \({0.321334 <} \alpha \le 1\) [29]. Moreover, \(\mu = \frac{1}{2}\) if \(\omega=2\), and the current best bounds on \(\mu\) are \(\frac{1}{2} \le \mu {< 0.527661}\) [29]. Amossen and Pagh [30] first proposed an algorithm for the Boolean matrix multiplication by using fast matrix multiplication techniques, which runs in \(\tilde{O}\left(N^{\frac{2}{3}}\cdot \textsf{OUT}^{\frac{2}{3}} + N^{\frac{(2-\alpha)\omega -2}{(1+\omega)(1-\alpha)}} \cdot \textsf{OUT}^{\frac{2-\alpha \omega}{(1+\omega)(1-\alpha)}} +\textsf{OUT}\right)\) time when \(\textsf{OUT}\ge N\), and \(\tilde{O}\left(N \cdot \textsf{OUT}^{\frac{\omega-1}{\omega+1}}\right)\) time when \(\textsf{OUT}< N\), where \(\tilde{O}\) hides a factor of \(O(N^{o(1)})\). If \(\omega = 2\), this result degenerates to \(\tilde{O}\left(N^{\frac{2}{3}}\cdot \textsf{OUT}^{\frac{2}{3}} + N\cdot \textsf{OUT}^{\frac{1}{3}}\right)\). Very recently, Abboud et al. [31] have completely improved this to \(O\left(N \cdot \textsf{OUT}^{\frac{\mu}{1+\mu}} + \textsf{OUT}+ N^{\frac{(2+\alpha)\mu}{1+\mu}} \cdot \textsf{OUT}^{\frac{1-\alpha \mu}{1+\mu}}\right)\). If \(\omega = 2\), this complexity can be simplified to \(O\left(N \cdot \textsf{OUT}^{\frac{1}{3}} + \textsf{OUT}\right)\). On the other hand, improving this result for any value of \(\textsf{OUT}\) is rather difficult, assuming the hardness of the all-edge-triangle problem [31]. Many algorithms have been proposed for Boolean matrix multiplication, whose complexity is also measured by the domain size of attributes; we refer readers to [31] for details. Deep et al. [32] and Huang et al. [33] also investigated the efficient implementation of these algorithms on sparse matrix multiplication in practice. Very recently, Hu [34] first applied fast matrix multiplication to speed up acyclic join-project queries and showed a large polynomial improvement over the combinatorial Yannakakis algorithm [28]. As an independent line of research, fast matrix multiplication has been extensively used in the algorithm community to speed up detecting, counting, and listing subgraph patterns, such as cliques [15], [19], [35] and cycles [36]. In addition, this technique has been used to approximately count triangles [37] and cycles [38], k-centering in graphs [39], etc.

9 Conclusion↩︎

We proposed a general framework for evaluating Boolean conjunctive queries that naturally subsumes both combinatorial and non-combinatorial techniques under the umbrella of information theory. Our framework generalizes the notion of submodular width by incorporating matrix multiplication, and provides a matching algorithm for evaluating queries in the corresponding time complexity. Using this framework, we show how to recover the best known complexity for various classes of queries as well as improve the complexity for some of them.

Our framework can be straightforwardly extended from Boolean conjunctive queries to count and sum queries, albeit without free variables. In particular, in the combinatorial world, the transition from Boolean to count/sum queries (and more generally to aggregate queries over any semiring) is done by adapting the submodular width to become the Sharp-submodular width [40]. The latter is a variant of the submodular width that is obtained by relaxing the notion of polymatroids. In the presence of matrix multiplication, a similar transition from Boolean to count/sum queries is possible by adapting the \(\omega\)-submodular width to become the Sharp-\(\omega\)-submodular width. Nevertheless, this transition only applies to count/sum queries, i.e., aggregate queries over the semiring of real numbers \((\mathbb{R}, +, \times)\), and does not extend to aggregate queries over other semirings like the tropical semiring \((\mathbb{R}_+, \min, +)\), since fast matrix multiplication does not apply in the latter.

It is not clear how to extend our framework to full conjunctive queries due to the use of fast matrix multiplication. For example, consider the full version of the triangle query from Eq. 2 where we replace the head \(Q_\triangle()\) with \(Q_\triangle(X, Y, Z)\). While we could use matrix multiplication between \(S\) and \(T\) to compute the number of triangles containing every edge \((X, Y)\) in \(R\), the multiplication result cannot help us recover a list of those triangles. Nevertheless, we could still use this multiplication result to answer the version of the query where the head is \(Q_\triangle(X, Y)\). Prior results from Table 1 are not known to apply to the corresponding full conjunctive queries with an additional \(+O(\textsf{OUT})\) factor in the runtime where \(\textsf{OUT}\) is the output size. We leave characterizing (non-full) conjunctive queries that can benefit from fast matrix multiplication as an open problem.

10 Computing the Submodular Width↩︎

We summarize here how to compute the submodular width of a given hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), as defined in Eq. 20 . To that end, we need to apply a couple of tricks. Let \(\mathcal{T}(\mathcal{H}) =\) \(\{(T_1, \chi_1), (T_2, \chi_2), \ldots,\) \((T_K, \chi_K)\}\) be the list of all tree decompositions of \(\mathcal{H}\). Let \(\boldsymbol{t} = (t_1, t_2, \ldots, t_K) \in \text{\sf nodes}(T_1)\times\ldots\times \text{\sf nodes}(T_K)\) denote a tuple of nodes, one from each tree decomposition. (Note that \(t_1, \ldots, t_K\) are not nodes from the same tree decomposition.) By distributing¹⁶ the min over the max in Eq. 20 , we can equivalently write (where \([K]\) denotes \(\{1, \ldots, K\}\)): \[\begin{align} \textsf{subw}(\mathcal{H}) &\quad\stackrel{\mathrm{def}}{=}\quad \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{(T,\chi) \in \mathcal{T}(\mathcal{H})}\quad \max_{t \in \text{\sf nodes}(T)}\quad h(\chi(t))\nonumber\\ &\quad=\quad \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \max_{\substack{(t_1, \ldots, t_K)\in\\\text{\sf nodes}(T_1)\times\ldots\times\text{\sf nodes}(T_K)}}\quad \min_{i \in [K]}\quad h(\chi_i(t_i))\tag{104}\\ &\quad=\quad \max_{\substack{(t_1, \ldots, t_K)\in\\\text{\sf nodes}(T_1)\times\ldots\times\text{\sf nodes}(T_K)}}\quad \underbrace{\max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{i \in [K]}\quad h(\chi_i(t_i))}_{\text{Equivalent to LP~\eqref{eq:subw:lp}}}\tag{105} \end{align}\] Eq. 105 follows by swapping the two max operators in Eq. 104 . Now for a fixed tuple \((t_1, \ldots, t_K)\), consider the inner optimization problem: \[\begin{align} \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad \min_{i \in [K]}\quad h(\chi_i(t_i)) \label{eq:subw:pre-lp} \end{align}\tag{106}\] Although the constraints \(\boldsymbol{h} \in \Gamma \cap \mathsf{ED}\) are linear, Eq. 106 is still not a linear program (LP) because the objective is a minimum of linear functions. However, we can convert 106 into an LP by introducing a new variable \(w\) that is upper bounded by each term in the minimum: \[\begin{align} \max_{w, \boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\{ w\mid w \leq h(\chi_1(t_1)), \ldots, w \leq h(\chi_K(t_K)) \} \label{eq:subw:lp} \end{align}\tag{107}\] As a result, computing the submodular width can be reduced to taking the maximum solution of a finite number of LPs, one for each tuple \((t_1, \ldots, t_K) \in \text{\sf nodes}(T_1)\times\ldots\times\text{\sf nodes}(T_K)\).

11 Missing details from Section 5↩︎

We show here how to compute the \(\omega\)-submodular width for the classes of queries that are given by Table 2 in Section 5. We start with some preliminaries:

11.1 Clique Hypergraphs↩︎

From Proposition 28 and Definition 6, we can simplify \(\textsf{\omega-subw}\) for clique hypergraphs \(\mathcal{H}\) as below: \[\begin{align} {\textsf{\omega-subw}}(\mathcal{H}) \quad = \quad \max_{\boldsymbol{h} \in \Gamma \cap \mathsf{ED}}\quad {\min\left(h(\mathcal{V}), \min_{\overline{\boldsymbol{\sigma}} \in \overline{\pi}(\mathcal{V})} \mathsf{EMM}^{\overline{\boldsymbol{\sigma}}}_1\right)} \label{eq:osubw:trimmed:clique} \end{align}\tag{108}\]

11.2 Cycle Hypergraphs↩︎

[18] defines an exponent \(\overline{c} _k\) for detecting a \(k\)-cycle in a graph, and the definition is based on rectangular matrix multiplication. We define below an upper bound, \(c^{\square} _k\), on \(\overline{c} _k\) that uses only square matrix multiplication and show that \(\textsf{\omega-subw}(\mathcal{H}) \le c^{\square} _k\) for any \(k\)-cycle graph \(\mathcal{H}\). In particular, \(\overline{c} _k \leq c^{\square} _k\) and this becomes an equality when \(\omega = 2\). Moreover, [18] shows that \(\overline{c} _k = c^{\square} _k\) when \(k\) is odd as well as \(k=4\) or \(6\). More details can be found in [18].

First, we recall the definition of \(\overline{c} _k\) from [18]. Recall from Table 1 that \(\overline{\omega} (a,b,c)\) is the smallest exponent for multiplying two rectangular matrices of sizes \(n^a \cdot n^b\) and \(n^b \cdot n^c\) within \(O\left(n^{ \overline{\omega} (a,b,c)}\right)\) time, whereas \(\omega^{\square} (a,b,c)\) is the smallest upper bound on \(\overline{\omega} (a,b,c)\) that is obtained through square matrix multiplication, i.e.  \(\omega^{\square} (a, b, c) \stackrel{\mathrm{def}}{=}\max\{a + b+(\omega-2)c, a+(\omega-2)b + c, (\omega-2)a + b + c\}\). In particular, \(\overline{\omega} (a,b,c) \leq \omega^{\square} (a, b, c)\), and this becomes an equality when \(\omega = 2\) or when \(a=b=c\). Given a graph of size \(N\), let \(\mathbf{D} = \{0,\log_N 2, 2\log_N 2, \cdots, 1\}^{2k}\). For each vector \(\vec{d}\), [18] defines a function \(\overline{P} ^{\vec{d}}_{i,j}\) (for \(i < j\)) in a recursive way as follows: \[\label{eq:rect-ck-pij} \overline{P} ^{\vec{d}}_{i,j} = \min\left\{ \overline{P} ^{\vec{d}}_{i,j-1} + d^+_{j-1}, \overline{P} ^{\vec{d}}_{i+1,j} + d^{-}_{i+1}, \min_{i<r < j}\left\{ \overline{P} ^{\vec{d}}_{i,r}, \overline{P} ^{\vec{d}}_{r,j}, \overline{\omega} (1-d_i, 1-d_r, 1-d_j)\right\}\right\}\tag{111}\] with \(\overline{P} ^{\vec{d}}_{i,i+1} = 1\). Finally, [18] defines \(\overline{c} _k\) as follow: \[\label{eq:rect-ck} \overline{c} _k = \max_{\vec{d} =\left(d^-_1, d^+_1, d^-_2, d^+_2, \cdots, d^-_k, d^+_k\right) \in \mathbf{D}}\min\left\{\min_{i \in [k]} 2 - d_i, \min_{i,j \in [k]: i<j} \max\left\{ \overline{P} ^{\vec{d}}_{i,j}, \overline{P} ^{\vec{d}}_{j,i}\right\}\right\}\tag{112}\]

In contrast, by replacing \(\overline{\omega} (1-d_i, 1-d_r, 1-d_j)\) with \(\omega^{\square} (1-d_i, 1-d_r, 1-d_j)\) in Eq. 111 , we obtain our variants \(P^{\vec{d}}_{i,j}\) and \(c^{\square} _k\) defined below (with \(P^{\vec{d}}_{i,i+1} = 1\)):

\[\label{eq:square-ck-pij} P^{\vec{d}}_{i,j} = \min\left\{P^{\vec{d}}_{i,j-1} + d^+_{j-1}, P^{\vec{d}}_{i+1,j} + d^{-}_{i+1}, \min_{i<r < j}\left\{P^{\vec{d}}_{i,r}, P^{\vec{d}}_{r,j}, \omega^{\square} (1-d_i, 1-d_r, 1-d_j)\right\}\right\}\tag{113}\] \[\label{eq:square-ck} c^{\square} _k = \max_{\vec{d} =\left(d^-_1, d^+_1, d^-_2, d^+_2, \cdots, d^-_k, d^+_k\right) \in \mathbf{D}}\min\left\{\min_{i \in [k]} 2 - d_i, \min_{i,j \in [k]: i<j} \max\left\{P^{\vec{d}}_{i,j}, P^{\vec{d}}_{j,i}\right\}\right\}\tag{114}\]

11.3 Clustered Hypergraphs↩︎

11.3.0.1 Remark.

For the hypergraph \(\mathcal{H}\) in Lemma 13, \(\textsf{subw}(\mathcal{H}) = \frac{9}{5}\). If \(\omega =3\), \(\textsf{\omega-subw}(\mathcal{H}) \le 2 - \frac{1}{2 \omega -1} = \textsf{subw}(\mathcal{H}) = \frac{9}{5}\). If \(\omega < 3\), \(\textsf{\omega-subw}(\mathcal{H}) < \textsf{subw}(\mathcal{H})\).

References↩︎

---

1. This work was partially supported by NSF-BSF 2109922, NSF-IIS 2314527, NSF-SHF 2312195, and by the Natural Sciences and Engineering Research Council of Canada – Discovery Grant, and was initiated while the authors participated in the Fall 2023 Simons Program on Logic and Algorithms in Databases and AI.↩︎

2. By that, we mean partitioning not just the input relations but also intermediate relations that result from the join of (input or intermediate) relations. This “multi-level” partitioning can indeed lower the complexity further than one-level partitioning, for some classes of queries.↩︎

3. Note that this algorithm uses the three techniques mentioned above in reverse order.↩︎

4. Note that for \(\omega = 3\), this complexity collapses back to \(O(N^{3/2})\) which is the same as the combinatorial algorithm.↩︎

5. If \(\omega\) is irrational, we can use any rational upper bound on \(\omega\) instead.↩︎

6. In particular, later we will extend the notion of \(\mathsf{MM}\) to allow for group-by variables, and we will also generalize the concept of VEOs to allow eliminating multiple variables at once.↩︎

7. Note that \(\mathsf{MM}(X;Y;Z)\) is symmetric.↩︎

8. Note that \(\min(a, \max(b, c)) = \max(\min(a, b), \min(a, c))\)↩︎

9. Note that \(h(XZ) + h(Y|X) \geq h(XYZ)\) is just another form of the submodularity \(h(XZ) + h(XY) \geq h(X) + h(XYZ)\), hence the name.↩︎

10. \(S \ltimes T\) denotes the semi-join reduce operator defined by \(S \ltimes T \stackrel{\mathrm{def}}{=}\pi_{\text{\sf vars}(S)}(S \Join T)\).↩︎

11. If \(\omega\) is not fixed, then Eq. 39 is not an LP because the coefficient \(\gamma\) depends on \(\omega\). Hence, we end up having constraints that are quadratic in terms of \(\omega\) and \(\boldsymbol{h}\).↩︎

12. If \(\omega\) is irrational, we can use any rational upper bound on \(\omega\) instead.↩︎

13. Recall the notion of “covered” from Section 3.6.↩︎

14. The constant \(C\) can be assumed to be independent of the specific values of the \(\omega\)-dominant triples \((\alpha_i, \beta_i, \zeta_i)\). This is because every \(\omega\)-dominant triple \((\alpha_i, \beta_i, \zeta_i)\) can be replaced with another \((\alpha_i', \beta_i', \zeta_i') \leq (\alpha_i, \beta_i, \zeta_i)\) where inequality 44 is tight, i.e., where \(\alpha_i' + \beta_i' + \zeta_i' = \omega\). Such replacement can only expand the \(B\)-support of the probabilistic interpretation of the MM target, and thus it can only expand the set \(E\).↩︎

15. Recall what “covered” means from Section 3.6.↩︎

16. Note that \((\mathbb{R}, \max, \min)\) is a commutative semiring.↩︎