What do Shannon-type Inequalities, Submodular Width, and
Disjunctive Datalog have to do with one another? ∗

arXiv:1612.02503v4 [cs.DB] 1 Nov 2017

Mahmoud Abo Khamis
RelationalAI, Inc.

Hung Q. Ngo
RelationalAI, Inc.

Dan Suciu
RelationalAI, Inc., &
University of Washington

Abstract
Recent works on bounding the output size of a conjunctive query with functional dependencies and
degree constraints have shown a deep connection between fundamental questions in information theory
and database theory. We prove analogous output bounds for disjunctive datalog rules, and answer several
open questions regarding the tightness and looseness of these bounds along the way. Our bounds are
intimately related to Shannon-type information inequalities. We devise the notion of a “proof sequence”
of a specific class of Shannon-type information inequalities called “Shannon flow inequalities”. We then
show how such a proof sequence can be interpreted as symbolic instructions guiding an algorithm called
PANDA, which answers disjunctive datalog rules within the time that the size bound predicted. We
show that PANDA can be used as a black-box to devise algorithms matching precisely the fractional
hypertree width and the submodular width runtimes for aggregate and conjunctive queries with functional
dependencies and degree constraints.
Our results improve upon known results in three ways. First, our bounds and algorithms are for
the much more general class of disjunctive datalog rules, of which conjunctive queries are a special
case. Second, the runtime of PANDA matches precisely the submodular width bound, while the previous
algorithm by Marx has a runtime that is polynomial in this bound. Third, our bounds and algorithms
work for queries with input cardinality bounds, functional dependencies, and degree constraints.
Overall, our results show a deep connection between three seemingly unrelated lines of research; and,
our results on proof sequences for Shannon flow inequalities might be of independent interest.

∗ This

work is partly supported by NSF grant 1535565.

1

Introduction

This paper answers four major questions that resulted from four different research threads, and establishes
new connections between those threads.

1.1

Output-Size Bound for Full Conjunctive Queries

Grohe and Marx [37], Atserias, Grohe, and Marx [12], and Gottlob, Lee, Valiant and Valiant [33] developed
a deep connection between the output size bound of a conjunctive query with (or without) functional dependencies (FD) and information theory. Our first problem is to extend this bound to degree constraints,
and to study whether the bound is tight.
def
We associate a full conjunctive query Q to a hypergraph H = ([n], E), E ⊆ 2[n] (where [n] = {1, . . . , n}).
The query’s variables are Ai , i ∈ [n]. Its atoms are RF , F ∈ E. The query is:
^
Q(A[n] ) ←
RF (AF ),
(1)
F ∈E

where AJ denotes the tuple (Aj )j∈J , for any J ⊆ [n]. Our goal is to compute an upper bound on the output
size, when the input database satisfies a set of degree constraints.
Definition 1.1 (Degree, cardinality, and FD constraints). For X ⊂ Y ⊆ F ∈ E, define
def

degF (AY |AX ) = max |ΠAY (σAX =t (RF ))|.
t

(2)

Then, a degree constraint is an assertion of the form degF (AY |AX ) ≤ NY |X , where NY |X is a natural
number. A cardinality constraint is an assertion of the form |RF | ≤ NF , for some F ∈ E; it is exactly the
def
degree constraint degF (AF |∅) ≤ NF |∅ = NF . A functional dependency AX → AY is a degree constraint
with NX∪Y |X = 1. In particular, degree constraints strictly generalize both cardinality constraints and FDs.
Handling queries with degree constraints has a strong practical motivation. For example, Armbrust et
al. [9–11] described a new approach to query evaluation, called scale-independent query processing, which
guarantees a fixed runtime even when the size of the database increases without bound; this guarantee is
provided by asking developers to write explicit degree constraints, then using heuristics to derive upper
bounds on the query output. Thus, improved upper bounds on the size of the query answer have immediate
applications to scale-independent query processing. Some complexity results on the associated decision
problem (“is the output size of the query bounded?”) were considered in [15–17].
Built in part on earlier work by Friedgut and Kahn [30] and Chung et al. [21], the first output-size upper
bound for full conjunctive queries was established in [12, 37]. Their bound, known today as the AGM-bound
(see Sec. 2), was tight, but only for queries with cardinality constraints. Extensions of the bound to handle
FDs and degree constraints were discussed in Gottlob et al. [33] and Abo Khamis et al. [3], respectively, who
left open the question of whether these bounds are tight. Our first question is whether the upper bounds
in [3, 33] for queries with FDs or degree constraints (in addition to cardinality constraints) are tight.
To set the technical context for this question, we briefly describe how the bounds were derived. Fix
an input database D and consider the joint distribution on random variables A[n] where each output tuple
t ∈ Q(D) is selected uniformly with probability 1/|Q(D)|. For any S ⊆ [n], let H(AS ) denote the marginal
entropy on the variables AS . Then,1 by uniformity H(A[n] ) = log |Q(D)|, and H(AY |AX ) ≤ log NY |X for
every degree constraint. A function h : 2A[n] → R+ is said to be entropic if there is a joint distribution
on A[n] such that h(AS ) is the marginal entropy on AS , S ⊆ [n]. We just proved the entropic bound of a
query, which states that log |Q| ≤ maxh h(A[n] ), where h ranges over all entropic functions satisfying the
given degree constraints. Recently, Gogacz and Toruńczyk [31] showed that the entropic bound is tight given
cardinality and FD constraints. However, they did not address general degree constraints.
1 All

logs are in base 2, unless otherwise stated.

2

The problem with the entropic bound is that we do not know how to compute it (except for the special
case when all degree constraints are cardinality constraints), partly because the entropic cone is characterized
by infinitely many non-Shannon-type inequalities [41, 49]. To overcome this limitation, Gottlob et al. [33]
replace entropic functions (which are difficult) by polymatroids (which are easier). A polymatroid is a set
function h : 2[n] → R+ that is non-negative, monotone, and submodular, with h(∅) = 0. Every entropic
function h is also a polymatroid, if we write h(S) for h(AS ) (see Sec. 2). Linear inequalities satisfied
by all polymatroids are called Shannon-type inequalities [49]. The polymatroid bound of a full conjunctive
query is log |Q| ≤ maxh h(A[n] ), where h ranges over all polymatroids satisfying the given constraints. The
polymatroid bound, while at least as large as the entropic bound, can be shown to be tight for cardinality
constraints, because the AGM bound is exactly the polymatroid bound for cardinality constraints (see
Prop. 3.2) and it is tight [12]. The polymatroid bound is also tight for cardinality constraints with certain
sets of FDs [3]. We ask whether it is tight in more general settings:
Question 1. Is the polymatroid bound tight for general degree constraints? Or, at least for queries with
both cardinality and FD constraints?
Example 1.2. Consider the 4-cycle query:
Q(A1 , A2 , A3 , A4 ) ← R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 ), R41 (A4 , A1 )

(3)

Assuming all input relations have size ≤ N , then (a) the AGM bound is |Q| ≤ N 2√
, (b) if we add the degree
constraints deg12 (A1 A2 |A1 ) ≤ D and deg12 (A1 A2 |A2 ) ≤ D for some integer D ≤ N then |Q| ≤ D · N 3/2 ,
and (c) if we replace the degree constraints with FDs A1 → A2 and A2 → A1 the bound reduces further to
|Q| ≤ N 3/2 . These bounds can be proven using only Shannon-type inequalities, thus they are polymatroid
bounds. They are also asymptotically tight (see Appendix A).
Answer 1. The polymatroid bound is not tight for queries with cardinality and FD constraints! By adding a
variable to a non-Shannon inequality by Zhang-Yeung [50] and constructing accordingly a database instance,
we prove in Section 3.2 the following theorem.
Theorem 1.3. For any integer s > 0, there exists a query Q of size Θ(s), with cardinality and FD constraints, such that the ratio between the polymatroid bound and the entropic bound is ≥ N s , where N is the
size of the database.

1.2

Size Bound for Disjunctive Datalog Rules

Disjunctive datalog [8, 26] is a powerful extension of datalog. In this paper we are interested in a single
disjunctive-datalog rule:
_
^
P :
TB (AB ) ←
RF (AF )
(4)
F ∈E

B∈B

The body is similar to that of a conjunctive query, while the head is a disjunction of output relations TB ,
which we call targets. Given a database instance D, a model of P is a tuple T = (TB )B∈B of relations, one
for each target, such that the logical implication indicated by the rule holds. More precisely, for any tuple
t, if ΠF (t) ∈ RF for every input relation RF , then there exists a target TB ∈ T such that ΠB (t) ∈ TB . We
write T |= P to denote the fact that T is a model. Define the size of a model to be maxB |TB |, and define
the output size of P to be the minimum size over all models:
def

|P (D)| =

min max |TB |

T:T|=P B∈B

(5)

Our second question is to find an output size upper bound for a disjunctive datalog rule whose input
database D satisfies given degree constraints. If the rule has a single target then it becomes a conjunctive
query: a model is any superset of the answer, and the output size is the standard size of the query’s answer.
We thus expect the upper bound to come in two flavors, entropic and polymatroid, as is the case for full
conjunctive queries.
3

Question 2. Find the entropic and polymatroid output size bounds of a disjunctive datalog rule, under
general degree constraints. Determine if it is tight.
Example 1.4. Consider the disjunctive datalog rule, where input relations have sizes ≤ N :
P :

T123 (A1 , A2 , A3 ) ∨ T234 (A2 , A3 , A4 ) ← R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 ).

Intuitively, for every tuple t = (a1 , a2 , a3 , a4 ) in R12 ✶ R23 ✶ R34 we want to have either (a1 , a2 , a3 ) in T123
or (a2 , a3 , a4 ) in T234 or both. A model of size N 3 can be obtained trivially by populating the target T123
with all triples obtained from the active domain, but we show below that |P (D)| ≤ N 3/2 , for all D whose
relation sizes are ≤ N .
Answer 2. To describe the answer to the second question, we recall some standard notations [49]. We
n
identify set-functions h : 2[n] → R+ with vectors in R2+ , and we use both h(AS ) and h(S) to denote
hS , where A1 , A2 , . . . are (random) variables. (We will use h(S) and h(AS ) interchangeably in this paper,
depending on context. The reason is that, h(AS ) is more apt for marginal entropies, and h(S) is more apt
n
∗
for polymatroids.) The sets Γ∗n ⊂ Γn ⊂ Γn ⊂ R2+ denote the set of entropic functions, its topological closure,
and the set of polymatroids. We encode degree constraints by a set DC of triples (X, Y, NY |X ), specifying
degF (AY |AX ) ≤ NY |X . Define




^
def
h(Y |X) ≤ log NY |X
(6)
HDC = h : 2[n] → R+ |


(X,Y,NY |X )∈DC

def

to be the collection of set functions h satisfying the constraints DC, where h(Y |X) = h(Y ) − h(X).2 Fix
n
a closed subset F ⊆ R2+ . Define the log-size-bound with respect to F of a disjunctive datalog rule P to be
the quantity:
def
LogSizeBoundF (P ) = max min h(B).
(7)
h∈F B∈B

The following is our second result, whose proof can be found in Section 4.
Theorem 1.5. Let P be any disjunctive datalog rule (4), and DC be given degree constraints.
(i) For any database instance D satisfying all constraints in DC, the following holds:
log |P (D)| ≤

LogSizeBoundΓ∗ ∩HDC (P )
|
{z n
}

(8)

entropic bound

≤

LogSizeBoundΓn ∩HDC (P )
|
{z
}

(9)

polymatroid bound

(ii) The entropic bound above is asymptotically tight.

(iii) The polymatroid bound is not tight, even if the constraints are all cardinality constraints, and even if all
cardinality upperbounds are identical. Furthermore, the gap between the two bounds can be arbitrarily
large.
Inequalities (8) and (9) generalize the entropic and polymatroid bounds from full conjunctive queries
(Prop. 3.2) to arbitrary disjunctive datalog rules. The tightness result (ii) generalizes the main result
in [31], which states that the entropic bound is asymptotically tight for full conjunctive queries under FDs.
Note that the non-tightness result (iii) is incomparable to the non-tightness result in Theorem 1.3.
2 If

h was entropic, then h(Y |X) = h(Y ) − h(X) is the conditional entropy. Recall also X ⊆ Y whenever (X, Y, NY |X ) ∈ DC.

4

Example 1.6. From (9), the bound |P (D)| ≤ N 3/2 in Example 1.4 follows by applying twice the submodularity law for polymatroids:
3 log N ≥ h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 )

(cardinality constraints)

≥ 2 min(h(A1 A2 A3 ), h(A2 A3 A4 ))
≥ 2 log |P |.

(From (9))

≥ h(A1 A2 A3 ) + h(A2 ) + h(A3 A4 )
≥ h(A1 A2 A3 ) + h(A2 A3 A4 )

(submodularity)
(submodularity)

Table 1 summarizes size bounds for full conjunctive queries and disjunctive datalog rules and states their
tightness properties.

Disjunctive Datalog
Rule P

Full Conjunctive
Query Q

Bound
Definition
Cardinality
Constraints (CC)
CC and FD
Degree
Constraints (DC)
Definition
Cardinality
Constraints (CC)
CC and FD
Degree
Constraints (DC)

Entropic Bound
log |Q| ≤

max
∗

h([n])

h∈Γn ∩HDC

(See [3, 33])
AGM bound [12, 37]
(Tight [12])
Entropic Bound for FD [33]
(Tight [31])
Entropic Bound for DC [3]
(Tight [Thm. 1.5, (ii)])
log |P (D)| ≤

max
∗

min h(B)

h∈Γn ∩HDC B∈B

([Thm. 1.5, (i)])
Entropic Bound for
Disjunctive Datalog with CC
(Tight [Thm. 1.5, (ii)])
(same as below)
Entropic Bound for
Disjunctive Datalog with DC
(Tight [Thm. 1.5, (ii)])

Polymatroid Bound
log |Q| ≤

max

h∈Γn ∩HDC

h([n])

(See [3, 33])

AGM bound [12, 37]
(Tight [12])
Polymatroid Bound for FD [33]
(Not tight [Thm. 1.3])
Polymatroid Bound for DC [3]
(Not tight [Thm. 1.3])
log |P (D)| ≤

max

min h(B)

h∈Γn ∩HDC B∈B

([Thm. 1.5, (i)])

Polymatroid Bound for
Disjunctive Datalog with CC
(Not tight [Thm. 1.5, (iii)])
(same as below)
Polymatroid Bound for
Disjunctive Datalog with DC
(Not tight [Thm. 1.5, (iii)
or Thm. 1.3])

Table 1: Summary of entropic and polymatroid size bounds for full conjunctive queries and for disjunctive
datalog rules along with their tightness properties. The top half of the table depicts bounds for full conjunctive queries while the bottom half depicts bounds for disjunctive datalog rules. The “Definition” row
shows definitions of both the entropic and polymatroid bounds. The “Cardinality Constraints (CC)” row
shows the special cases of those definitions when only cardinality constraints are given. The “CC and FD”
row shows the cases when both cardinality constraints and functional dependencies are given. The “Degree
Constraints (DC)” row shows the most general cases. New results due to this work are marked in bald.

1.3

Algorithm evaluating disjunctive datalog rules

A worst-case optimal algorithm is an algorithm for computing a query in time within a poly-log factor of a
tight worst-case output size bound. Such algorithms are known for full conjunctive queries under cardinality
constraints [1, 42, 43, 47] and FDs [3]. Our next problem is finding a (worst-case optimal?) algorithm for a
disjunctive datalog rule P , under degree constraints. More precisely, given an input database D satisfying
5

given degree constraints, compute a model T in time no larger than the worst-case bound for |P (D)| under
those constraints.
Notice that we allow the algorithm to compute any model, and not necessarily a minimal model. This is
unavoidable in order to guarantee the runtime proportional to a good upperbound on |P (D)|, as we explain
next. A conjunctive query Q is a single-target disjunctive datalog rule PQ . If Q is full, then from any model
T of PQ we can answer Q by semijoin-reducing T with each input relation. Thus, any algorithm evaluating
disjunctive datalog rules can also be used to answer (i.e. compute a minimal model for) a full conjunctive
query. However, this does not hold for non-full conjunctive queries. For example, if Q is Boolean, then PQ
has a single target T∅ (), and its size is trivially bounded by |P (D)| ≤ 1; for trivial information theoretic
reasons, we simply cannot answer an arbitrary Boolean conjunctive query in O(1)-time. By allowing the
algorithm to compute any model, we can answer a Boolean query trivially by returning T∅ = {()}, since this
is always a model. Our third problem is:
Question 3. Design an algorithm to compute a model for a given disjunctive datalog rule, under given
degree constraints, with runtime matching the polymatroid bound (9) above.
Answer 3. Details are presented in Sections 5 and 6. We summarize the ideas here. We present an algorithm
called PANDA (Proof-Assisted eNtropic Degree-Aware), which computes a model of a disjunctive datalog
rule P within the runtime predicted by the bound (9). PANDA is derived using a novel principle that we
introduced in [3]. First, one has to provide “evidence”, called proof sequence, that the polymatroid bound
is correct. Second, each step in the sequence is interpreted as a relational operator (one of: join, horizontal
partition, union), leading to a model of P .
We elaborate a bit more on how a proof sequence arises from the polymatroid bound (9). This bound
seems difficult to handle at first glance: while the feasible region Γn ∩ HDC is polyhedral, the objective
of (7) is non-linear. We start by proving in Lemma 5.2 that it is equivalent to a linear program: there exist
constants λB ≥ 0, for B ∈ B, for which:
X
λB h(B)
(10)
max min h(B) = max
h∈Γn ∩HDC B∈B

h∈Γn ∩HDC

B∈B

The right hand side of (10) is simpler to deal with. In particular, from linear programming duality and
Farkas’s lemma we show in Prop. 5.4 that one can compute non-negative coefficients δY |X for which the
following hold:
X
X
δY |X · log NY |X , and
(11)
λB h(B) =
max
h∈Γn ∩HDC

B∈B

X

B∈B

λB · h(B) ≤

(X,Y,NY |X )∈DC

X

(X,Y,NY |X )∈DC

δY |X · h(Y |X), ∀h ∈ Γn .

(12)

Inequality (12), which holds for any polymatroid h ∈ Γn , is called a Shannon-flow
inequality; it is a (vast)
P
generalization of Shearer’s lemma [21]. Note that (12) implies log |P | ≤
δY |X log NY |X . Thus, the first
task is to prove (i.e. provide evidence for) the inequality (12).
A key technical result in the paper is Theorem 5.9 which, stated informally, says that inequality (12) can
be proved using a sequence of rules of one of the following four types, where X ⊆ Y :
h(Y |X) → h(Y ∪ Z|X ∪ Z),

Submodularity

h(Y ) → h(X),
h(X) + h(Y |X) → h(Y ),

Monotonicity
Composition

h(Y ) → h(X) + h(Y |X).

Decomposition

(13)
(14)
(15)
(16)

To explain the theorem, assume for the sake of discussion that all coefficients in (12) are natural numbers.
Then both sides can be seen as bags of terms, and the theorem says that there exists a sequence of rewritings
6

using the four rules above, transforming the term bag on the RHS to the term bag on the LHS. Obviously,
if such a sequence exists, then inequality (12) holds, because each rewriting replaces a term (or sum of two
terms) with a smaller or equal term (or sum of two terms). The converse statement is non-obvious. For
example in our prior work [3] we found that, without the decomposition rule (16), the remaining three rules
along with the additional submodularity rule h(A) + h(B) → h(A ∪ B) + h(A ∩ B) are not a complete proof
system: there exists a Shannon-flow inequality without a proof sequence consisting only of those rules.
Finally, PANDA consists of interpreting each step in the proof sequence as a relational operation, leading
to:
Theorem 1.7. PANDA computes a model of a disjunctive datalog rule P under degree constraints DC in
time 3


Y
δ |X
,
NYY|X
Õ N + poly(log N ) ·
(X,Y,NY |X )∈DC

where

X

δY |X log NY |X = LogSizeBoundΓn ∩HDC (P ).

(X,Y,NY |X )∈DC

We now illustrate how the inequality in Example 1.6 can be proved using the above set of complete rules,
and then use the proof to compute the query P from Example 1.4 in time O(N 3/2 ).
Example 1.8. Consider the disjunctive rule P in Example 1.4, which we repeat here:
P :

T123 (A1 , A2 , A3 ) ∨ T234 (A2 , A3 , A4 ) ← R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 ).

Assume all input relations have cardinality ≤ N . We illustrate PANDA by showing how to compute this
rule in time O(N 3/2 ). To do this, the first step for us is to provide a proof sequence, showing that the
output size of P satisfies |P | ≤ N 3/2 . While we have done this already in Example 1.6, we provide here an
alternative proof sequence, using only the proof steps (13). . . (16). As before we start by noticing log |P | ≤
min(h(A1 A2 A3 ), h(A2 A3 A4 )) ≤ 12 (h(A1 A2 A3 ) + h(A2 A3 A4 )), then we prove the Shannon-flow inequality:
 1

1
h(A1 A2 A3 ) + h(A2 A3 A4 ) ≤ h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 )
2
2

using a proof sequence consisting of steps (13). . . (16):

h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 )
h(A1 A2 |A3 ) + h(A2 A3 ) + h(A3 A4 )
[h(A1 A2 |A3 ) + h(A3 )] + [h(A2 A3 ) + h(A4 |A3 )]
[h(A1 A2 |A3 ) + h(A3 )] + [h(A2 A3 ) + h(A4 |A2 A3 )]

h(A1 A2 A3 ) + h(A2 A3 A4 )

(1)

→

(2)

→

(3)

→

(4)

→

(And since each one of the terms h(A1 A2 ), h(A2 A3 ) and h(A3 A4 ) is bounded by log N , this proves that
log |P | ≤ 3/2 log N .) PANDA associates each term in the above proof sequence to some relation, and
interprets each proof step as a relational operator on the relations associated to the terms in that proof step.
(See Figure 1.) Initially, the terms h(A1 A2 ), h(A2 A3 ) and h(A3 A4 ) are associated with the input relations
R12 , R23 and R34 respectively. Step (1) is a submodularity step: PANDA does nothing but keeps track that
the new term h(A1 A2 |A3 ) is associated with the relation R12 . Step (2) is a decomposition step: PANDA
′
′
partitions R34 (A3 , A4 ) horizontally into R3′ (A3 ) and
√ R34 (A3 , ′A4 ), where R3 contains all values a3 that are
“heavy hitters”, meaning that |σA3 =a3 (R34 )| ≥ N , and R34 consists of all pairs (a3 , a4 ) with a3 being
3 In this paper, the big-O notation is in data-complexity, hiding a factor that is query-dependent and data-independent. The
big-Õ additionally hides a single log-factor in data-complexity.

7

′
“light hitters”. R3′ becomes associated with the term h(A3 ) while R34
becomes associated with h(A4 |A3 ).
′
Step (3) is another submodularity where PANDA associates the new term h(A4 |A2 A3 ) with the relation R34
.
Step (4) are two compositions, interpreted as joins. PANDA computes the first target T123 (A1 , A2 , A3 ) =
′
R12 (A1 , A2 ) ✶ R3′ (A3 ), and the second target
T234
√
√ (A2 , A3 , A4 ) = R23 (A2 , A3 )√✶ R34 (A3 , A4 ). Both joins
3/2
′
take time O(N ), because |R3 | ≤ |R34 |/ N ≤ N and degR′34 (A3 A4 |A3 ) < N . (Note that without the
horizontal partitioning into heavy and light hitters in step (3), both |R3′ | and degR′34 (A3 A4 |A3 ) could have
been as large as N , hence both joins could have taken up to N 2 time, which would have exceeded our budget
of N 3/2 .)

h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 )

R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 )

submodularity

no OP

h(A1 A2 |A3 ) + h(A2 A3 ) + h(A3 A4 )

R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 )
data
partitioning

decomposition
h(A1 A2 |A3 ) + h(A3 )
composition
h(A1 A2 A3 )

R12 (A1 , A2 ), R3′ (A3 )

h(A2 A3 ) + h(A4 |A3 )
submodularity

′
R23 (A2 , A3 ), R34
(A3 , A4 )

✶

h(A2 A3 ) + h(A4 |A2 A3 )

no OP

T123 (A1 , A2 , A3 )

′
R23 (A2 , A3 ), R34
(A3 , A4 )

composition

✶

h(A2 A3 A4 )

T234 (A2 , A3 , A4 )

Proof steps

Algorithmic steps

Figure 1: Illustration of the proof sequence and the corresponding PANDA algorithm from Example 1.8.
Example 1.8 has the nice property that the two terms h(A4 |A3 ) and h(A3 ) resulting from the decomposition step (2) diverged, i.e. were used in different targets. This allowed PANDA to place each tuple from R34
′
in either R3′ or R34
: no need to place in both, since these relations are not joined later. However, we could
neither prove nor disprove the divergence property in general. Instead, PANDA in general conservatively
places each tuple in both relations, yet it must ensure |R3′ (A3 )| · degR′34 (A3 A4 |A3 ) ≤ |R34 |. For that it creates
log N bins, with tuples whose degree is in [2i , 2i+1 ), for i = 0, . . . , ⌊log N ⌋, and processes each bin separately.
This needs to be repeated at each non-divergent decomposition step, hence the additional poly(log N ) factor
in the runtime.

1.4

Towards Optimal Algorithms for Conjunctive Queries

What is an optimal runtime to compute a given conjunctive query? A common belief is that its cost is of
the form Õ(N d + |output|), where N is the size of the input database, N d represents the “intrinsic” cost
of the query, and |output| is the unavoidable cost of reporting the output. Worst-case optimal algorithms
are not optimal in this sense. They are only good for inputs whose intrinsic cost is about the same as the
worst-case output size. As described below, there are algorithms whose runtimes are more output-sensitive.
If the query is Boolean, then the output size is always 1, and the cost is totally dominated by the intrinsic
cost of the query; for simplicity we discuss here only Boolean queries, but our discussion extends to other
conjunctive and aggregate queries [2] (see Sec. 8). Thus, an optimal algorithm should compute a Boolean
query in time Õ(N d ), with an exponent d as small as possible. Generalizing to degree constraints, it should
Q δ |X
), where NY |X are the degree bounds, and the product is minimized.
compute the query in time Õ( NYY|X
8

T123 (A1 , A2 , A3 ) ← R12 (A1 , A2 ), R23 (A2 , A3 )

T234 (A2 , A3 , A4 ) ← R23 (A2 , A3 ), R34 (A3 , A4 )

T341 (A3 , A4 , A1 ) ← R34 (A3 , A4 ), R41 (A4 , A1 )

T412 (A4 , A1 , A2 ) ← R41 (A4 , A1 ), R12 (A1 , A2 )

Tree Decomposition 1

Tree Decomposition 2

Figure 2: Two tree decompositions for the query in Example 1.2. Normally, each tree node is labeled with
a set of variables, e.g. χ(t) = {A1 , A2 , A3 }; for convenience we also show the atoms contained in those
variables, i.e. R12 (A1 , A2 ), R23 (A2 , A3 ), and also give a name to the associated full conjunctive query, e.g.
T123 (A1 , A2 , A3 ).
In search of a yardstick for optimality, we borrow from the long history of research on fixed-parameter
tractability. To a recursively enumerable class C of Boolean conjunctive queries (equivalently, hypergraphs
of CSP problems) we associate the following decision problem, denoted by BCQ(C): given a query Q ∈ C
and an instance D, check if the query is true on the instance. BCQ(C) is polynomial-time solvable if there
exists an algorithm that runs in polynomial time in |Q|, |D| (combined complexity [46]). The problem is
fixed-parameter tractable (FPT, with parameter |Q|, the query’s size) if there is an algorithm solving every
C-instance in time f (|Q|) · |D|d for some fixed constant d, where f is any computable function. It was
known very early on that if C is the class of bounded tree-width then BCQ(C) is in PTIME [29], and this was
extended to query width [20], then (generalized) hypertree width [34], and fractional hypertree width [37]:
boundedness of any of these parameters implies BCQ(C) is in PTIME.
Grohe’s now classic result [35] states that, assuming W[1] 6= FPT, if the arity of the relations are bounded,
then the converse also holds: BCQ(C) ∈ FPT, BCQ(C) ∈ PTIME, and queries in C having bounded width
are three equivalent statements, for any width notion above. In a beautiful paper, Marx [40] extended this
result to unbounded arity case, showing that BCQ(C) is FPT iff every Q ∈ C has bounded submodular
width, denoted by subw(Q). His results suggest to us using the submodular width, as a yardstick for
optimality. In order to prove that bounded submodular width implies FPT-membership, Marx described a
query evaluation algorithm that runs in time O(poly(N subw(Q) )).4 We define an algorithm to be optimal if
its runtime is Õ(N subw(Q) ). While no lower bounds are known to date to rule out faster algorithms for a
specific query, Marx’s dichotomy theorem ruled out faster algorithms for any recursively enumerable class of
queries (see [40] and Section 2). Our fourth problem is:
Question 4. Design an algorithm evaluating a Boolean conjunctive query Q in Õ(N subw(Q) )-time. Extend
the notion of submodular width, and the algorithm, to handle arbitrary degree constraints, to arbitrary
conjunctive and aggregate queries.
We briefly review the notion of submodular width, and its relationship to other width parameters. Note
that all known width parameters considered only cardinality constraints. A polymatroid h is edge-dominated
if h(F ) ≤ 1, ∀F ∈ E. Edge domination is a normalized version of cardinality constraints. The submodular
def

width is defined to be subw(Q) = maxh min(T,χ) maxt∈V (T ) h(χ(t)), where h ranges over edge-dominated
polymatroids, and (T, χ) over tree decompositions of Q (see Definition 2.5). Prior width parameters such as
tree-width [29], generalized- [34] and fractional- hypertree width [37] are defined by first defining the width
of a tree decomposition, then choosing the decomposition that minimizes this width (see [32] for a nice
survey). Thus, there is always a best tree decomposition (T, χ), and a query evaluation algorithm running
def

on that (T, χ); e.g., the fractional hypertree width is fhtw(Q) = min(T,χ) maxt∈V (T ) ρ∗ (χ(t)), where ρ∗ is
the fractional edge cover number of the set χ(t). In the submodular width, we are allowed to choose the tree
decomposition (T, χ) after we see the polymatroid h. Marx showed that subw(Q) ≤ fhtw(Q), for all Q, and
there are classes of queries for which the gap is unbounded (see also Example 7.4).
4 It is not clear what the exact runtime of Marx’s algorithm is. His theorem states that it is O(poly(N subw(Q) )). Our best
interpretation of Lemma 4.3 and Lemma 4.5 of [40] is that Marx’s algorithm runs in time at least O(N 2·subw(Q) ).

9

Answer 4. Our answer is presented in Section 7. Briefly, we generalize the notions of fractional hypertree width fhtw(Q) and submodular width subw(Q) to account for arbitrary degree constraints, and call
them degree-aware fractional hypertree width / submodular width, denoted by da-fhtw(Q) and da-subw(Q),
respectively. In fact, we describe a very general framework that captures virtually all previously defined
width-parameters, and extends them to degree constraints. We then show how to use PANDA to compute
a query in time whose exponent is da-subw(Q) (which is bounded by da-fhtw(Q)), using the same earlier
principle: from a proof of the bound of da-subw(Q), we derive an algorithm that computes Q in that bound.
Theorem 1.9. PANDA computes any full or Boolean conjunctive query Q in time Õ(N + poly(log N ) ·
2da-subw(Q) + |output|).
We have chosen to present only results on the full and Boolean conjunctive query cases in order to keep
the paper more accessible and focused. Our results extend straightforwardly to proper conjunctive queries
and to aggregate queries (in the sense of FAQ-queries over one semiring [2, 5]) as well. Section 8 briefly
describes how these more general queries are handled with PANDA.
Example 1.10. Consider the Boolean variant of the 4-cycle query Q in Example 1.2. More precisely we
ask the question: does there exists a cycle of length 4?; Alon, Yuster, and Zwick [7] described an algorithm
solving this problem in time O(N 3/2 ), where N is the number of edges. However, every traditional treedecomposition-based evaluation algorithm takes time N 2 . Indeed, the query has only two non-trivial tree
decompositions, shown in Fig. 2 and, for each tree, there exists a worst-case input on which the intermediate
tables for that tree have size N 2 . For example, given the instance R12 = R34 = [N ] × [1], R23 = R41 =
[1] × [N ], both intermediate tables of the tree on the left have size N 2 , and a similar worst-case instance
exists for the tree on the right. In fact, the fractional hypertree width of Q is fhtw(Q) = 2, because both
trees have fhtw = 2.
In contrast to the fractional hypertree width, the submodular width is adaptive: it chooses the tree based
on h. More precisely, subw(Q) is the maximum over edge-dominated polymatroids h of the quantity

min max(h(A1 A2 A3 ), h(A3 A4 A1 )), max(h(A2 A3 A4 ), h(A4 A1 A2 ))
(17)

(where “edge-dominated” in this example means h(A1 A2 ), h(A2 A3 ), h(A3 A4 ), and h(A4 A1 ) are all ≤ 1).
Intuitively, max(h(A1 A2 A3 ), h(A3 A4 A1 )) is the complexity of the tree on the left, and the other max is the
complexity of the tree on the right. PANDA starts by proving subw(Q) ≤ 3/2. To do that, it applies the
distributivity law of min over max on (17):
Eq. (17) = max min(h(A1 A2 A3 ), h(A2 A3 A4 )), min(h(A1 A2 A3 ), h(A4 A1 A2 )),

min(h(A3 A4 A1 ), h(A2 A3 A4 )), min(h(A3 A4 A1 ), h(A4 A1 A2 ))

(18)

then it proves one inequality for each term under max:
min(h(A1 A2 A3 ), h(A2 A3 A4 )) ≤

min(h(A1 A2 A3 ), h(A4 A1 A2 )) ≤

min(h(A3 A4 A1 ), h(A2 A3 A4 )) ≤

min(h(A3 A4 A1 ), h(A4 A1 A2 )) ≤


1/2 h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 ) ,

1/2 h(A4 A1 ) + h(A1 A2 ) + h(A2 A3 ) ,

1/2 h(A2 A3 ) + h(A3 A4 ) + h(A4 A1 ) ,

1/2 h(A3 A4 ) + h(A4 A1 ) + h(A1 A2 ) .

(19)
(20)
(21)
(22)

Example 1.6 showed the first inequality, the other three are similar. Since h is edge-dominated, every RHS
is ≤ 3/2, implying that Eq. (17) is ≤ 3/2, which proves the claim that subw(Q) ≤ 3/2. PANDA computes
the query in time Õ(N subw(Q) ) as follows. First, it interprets each inequality above as the output size bound
of a disjunctive datalog rule:
P1 :
P2 :
P3 :
P4 :

T123 (A1 , A2 , A3 ) ∨ T234 (A2 , A3 , A4 ) ← R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 ).

T123 (A1 , A2 , A3 ) ∨ T412 (A4 , A1 , A2 ) ← R41 (A4 , A1 ), R12 (A1 , A2 ), R23 (A2 , A3 ).
T341 (A3 , A4 , A1 ) ∨ T234 (A2 , A3 , A4 ) ← R23 (A2 , A3 ), R34 (A3 , A4 ), R41 (A4 , A1 ).

T341 (A3 , A4 , A1 ) ∨ T412 (A4 , A1 , A2 ) ← R34 (A3 , A4 ), R41 (A4 , A1 ), R12 (A1 , A2 ).
10

Next, PANDA evaluates each rule using the algorithm mentioned earlier in Section 1.3; the first rule above
was shown in Example 1.4 and the corresponding algorithm with runtime N 3/2 was explained in Example 1.8.
Each one of the rules P1 and P2 computes a different table T123 , and the union of both is taken as a single
intermediate table T123 . Similarly, the four rules result in the intermediate tables T341 , T234 , T412 , which
-along with T123 - correspond to all tree nodes in Fig. 2. The runtime so far is N 3/2 . Now, PANDA semi-join
reduces each one of those intermediate tables with all input relations, i.e. it semi-join reduces T123 (A1 , A2 , A3 )
with R12 (A1 , A2 ) and with R23 (A2 , A3 ), and so on: This step is needed to remove spurious tuples. Finally,
PANDA computes separately each one of the two trees from Fig. 2 (viewed as an acyclic Boolean query and
3/2
using Yannakakis algorithm [48]),
(since each one of the intermediate tables has size at most
W in time N
3/2
N ), then returns the logical of the two results.
One way to get the intuition behind the four rules above is to combine them into a single rule, where the
head is the conjunction of the four heads, then apply the (reverse) distributivity law to the head
(T123 ∨ T234 ) ∧ (T123 ∨ T412 ) ∧ (T341 ∨ T234 ) ∧ (T341 ∨ T412 ) =


T123 (A1 , A2 , A3 ) ∧ T341 (A3 , A4 , A1 ) ∨ T234 (A2 , A3 , A4 ) ∧ T412 (A4 , A1 , A2 ) ←

R12 (A1 , A2 ), R23 (A2 , A3 ), R34 (A3 , A4 ), R41 (A4 , A1 ). (23)

This captures the intuition of the fact that PANDA places each four-cycle (a1 , a2 , a3 , a4 ) either in both
intermediate tables of the first tree T123 (A1 , A2 , A3 ) ∧ T341 (A3 , A4 , A1 ), or in both intermediate tables of the
second tree T234 (A2 , A3 , A4 ) ∧ T412 (A4 , A1 , A2 ).
As we explained, no single tree is sufficient to compute Q in time O(N 3/2 ). Instead, each of the four
rules P1 , . . . , P4 directs tuples to either one tree or the other. For example, on the worst-case instance above
(where R12 = R34 = [N ] × [1], R23 = R41 = [1] × [N ]), at most N 3/2 of the N 2 four-cycles are inserted by
P1 into T123 (in the left tree), the others are spilled over to T234 (in the right tree). However, we prove that
the two trees together are sufficient to compute Q, by showing
that every four-cycle a = (a1 , a2 , a3 , a4 ) is
W
inserted in both nodes of either tree, thus, by taking the
of the two trees, PANDA computes the query
correctly. Indeed, suppose otherwise: Since a is missing from the left tree, assume w.l.o.g. that (a1 , a2 , a3 )
is missing from node T123 ; similarly, since a is missing from the right tree, assume that (a2 , a3 , a4 ) is missing
from T234 . But that implies that T123 ∨ T234 is not a model of the disjunctive datalog rule P1 above, which
is a contradiction. Thus, each tuple a is fully included in some tree.

2

Background and Related Work

Throughout the paper, we use the following convention. The non-negative reals, rationals, and integers are
denoted by R+ , Q+ , and N respectively. For a positive integer n, [n] denotes the set {1, . . . , n}.
Functions log without a base specified are base-2, i.e. log = log2 . Uppercase Ai denotes a variable/attribute, and lowercase ai denotes a value in Q
the discrete domain Dom(Ai ) of the variable. For any
subset S ⊆ [n], define AS = (Ai )i∈S , aS = (ai )i∈S ∈ i∈S Dom(Ai ). In particular, AS is a tuple of variables
and aS is a tuple of specific values with support S. Occasionally we use tS to denote a tuple with support
S. For any two finite sets S and T , let S T denote the collection of all maps f : T → S. Such a map f is
also viewed as a vector whose coordinates are indexed by members of T and whose coordinate values are
members of S.5
[n]
Definition 2.1. Let n be a positive integer. A function
P f : 2 → R+ is called a (non-negative) set function
on [n]. A set function f on [n] is modular if f (S) = v∈S f ({v}) for all S ⊆ [n], is monotone if f (X) ≤ f (Y )
whenever X ⊆ Y , is subadditive if f (X ∪ Y ) ≤ f (X) + f (Y ) for all X, Y ⊆ [n], and is submodular if
f (X ∪ Y ) + f (X ∩ Y ) ≤ f (X) + f (Y ) for all X, Y ⊆ [n]. A function h : 2A[n] → R+ is said to be entropic if
there is a joint distribution on A[n] such that h(AS ) is the marginal entropy on AS , S ⊆ [n]. We also write
h(S) for h(AS ), and thus entropic functions are also set functions.
5 This

is standard combinatorics notation. There are |S||T | of those maps.

11

h : 2[n] → R+ , non-negative, monotone, h(∅) = 0
h(X) ≤ h(Y ) if X ⊆ Y
SAn = {h | h is subadditive (& non-negative, monotone)}
h(X ∪ Y ) ≤ h(X) + h(Y )
Γn = {h | h is submodular (& non-negative, monotone)}
h(X ∪ Y ) + h(X ∩ Y ) ≤ h(X) + h(Y )
∗

Γn : topological closure of Γ∗n
Γ∗n = {h | h is entropic}
Mn = {h | h is modular}
P
h(X) = x∈X h(x)

Figure 3: Hierarchy of set functions
Unless specified otherwise, we will only consider non-negative and monotone set functions f for which
f (∅) = 0; this assumption will be implicit in the entire paper.
Definition 2.2. Let Mn , SAn , and Γn denote the set of all (non-negative and monotone) modular, subadditive, and submodular set functions on [n], respectively. Let Γ∗n denote the set of all entropic functions on
∗
n variables, and Γn denote its topological closure. 6
The following chain of inclusion is either known [49], or straightforward to show (see also Fig. 3):
Proposition 2.3. For any positive integer n, we have
∗

Mn ⊆ Γ∗n ⊆ Γn ⊆ Γn ⊆ SAn .

(24)

∗

Furthermore, when n ≥ 4, all inclusions are strict: Mn ( Γ∗n ( Γn ( Γn ( SAn .
Throughout the paper, we will work on multi-hypergraphs H = ([n], E) (i.e. a hyperedge may occur
multiple times in E).
Definition 2.4. Given a hypergraph H = ([n], E), define the following two set functions:
def

ED =

def

VD =

{h | h : 2[n] → R+ , h(F ) ≤ 1, ∀F ∈ E}

{h | h : 2[n] → R+ , h({v}) ≤ 1, ∀v ∈ [n]}

(25)
(26)

ED stands for edge-dominated and VD stands for vertex-dominated.
Given a set function h and a scalar s, we will use s · h to denote h scaled by s. If C is a class of set
def
functions, then s · C = {s · h | h ∈ C}. Specifically, we will be interested in log N · ED and log N
V · VD.
To each hypergraph H we associate a full conjunctive query, or natural join query, Q(A[n] ) ← F ∈E RF (AF ),
as discussed in Section 1, where for each hyperedge F ∈ E there is an input relation RF with attributes AF ;
6 Note

∗

that any non-negative modular function is monotone. The notations Γn , Γ∗n , Γn are standard in information theory [49].

12

the set F is called the support of relation RF . The hypergraph is a multi-hypergraph because for the same
hyperedge F there can
the Boolean
V
V be multiple relations RF with the same support F . Similarly, we associate
query, Q() ← ∃A[n] F ∈E RF (AF ), and drop the existential quantifiers, writing Q() ← F ∈E RF (AF ).
def

For each F ∈ E, let NF = |RF |, where NF ∈ N ∪ {∞}. We set NF = ∞ if RF is not a materialized
relation, a negation of a relation, or if its size is not known. Throughout this paper, let
N=

2.1
2.1.1

max

F ∈E,|RF |<∞

NF .

(27)

Bounds for queries with cardinality constraints
Bounds on the worst-case output size

In the case of a full conjunctive query, the runtime is as least at large as the size of its answer, hence there is
interest in finding upper bounds on the query answers. Bounding the worst-case output size |Q| of a natural
join query Q is a well-studied problem. There is a hierarchy of such bounds: the vertex bound, integral edge
cover bound, and the fractional edge cover bound (also called the AGM-bound).
def

|Q| ≤ VB(Q) = N n

|Q| ≤ 2

ρ(Q,(NF )F ∈E )

def

∗

|Q| ≤ AGM(Q, (NF )F ∈E ) = 2ρ

(Q,(NF )F ∈E )

Vertex bound

(28)

Integral edge cover bound

(29)

Fractional edge cover bound

(30)

(also called AGM bound)

The vertex bound is trivial. The quantities ρ(Q, (NF )F ∈E ) and ρ∗ (Q, (NF )F ∈E ) are defined via the edge
cover polytope:






X
def
E
ECP = λ | λ ∈ R+ ,
λF ≥ 1, ∀v ∈ [n]
(edge-cover polytope).
(31)




F ∈E
v∈F

A vector λ ∈ ECP is called a fractional edge cover of the hypergraph, while a vector λ ∈ ECP ∩ NE is called
an integral edge cover, or just an edge cover of H. Then,
)
(
!
Y
def
λF
(32)
ρ(Q, (NF )F ∈E ) = min log
NF
| λ ∈ ECP ∩ NE
F ∈E

∗

def

(

Y

ρ (Q, (NF )F ∈E ) = min log

F ∈E

NFλF

!

)

| λ ∈ ECP

(33)

The edge cover bounds are dependent on the input relations’ sizes. Often, to state a bound that is
independent of the input size, researchers use cruder approximations of the bound:
1
· ρ(Q, (NF = N )F ∈E )
log N
1
def
ρ∗ (Q) =
· ρ∗ (Q, (NF = N )F ∈E )
log N
def

ρ(Q) =

the integral edge cover number of H,

(34)

the fractional edge cover number of H,

(35)

(assuming N > 1.) In particular, note that 2ρ(Q,(NF =N )F ∈E ) = N ρ(Q) , and similarly for the ρ∗ case. The
AGM-bound by Atserias, Grohe, and Marx [12] built on earlier works [6,21,30,36]. One remarkable property
of the AGM-bound is that it is asymptotically tight. In addition, there are known algorithms [1, 42, 43, 47]
∗
with runtime Õ(2ρ (Q,(NF )F ∈E ) ): they are worst-case optimal. (Recall that in this paper, the big-O notation
is in data-complexity, hiding a factor that is query-dependent and data-independent. The big-Õ additionally
hides a single log-factor in data-complexity.)
13

not FPT
Bounded

FPT

submodular width
Bounded fractional

PTIME

hypertree width

Bounded
fractional
edge cover number

Bounded
(generalized)
Hypertree Width

Bounded
Treewidth

Figure 4: Islands of tractability for conjunctive queries and constraint satisfaction problems.
2.1.2

Islands of tractability for Boolean conjunctive queries (and CSP problems)

We have briefly discussed various width parameters of a Boolean conjunctive query in Section 1.4. In
particular, bounded widths often imply tractability. For unbounded-arity inputs, Marx [40] showed that
the submodular width is the best one can hope for in terms of being in FPT, unless the exponential time
hypothesis fails. Figure 4 explains the important classes of widths known thus far.7 The hierarchy is strict in
the sense that there are (infinite) classes of queries which have bounded submodular width but unbounded
fractional hypertree width, bounded fractional hypertree width but unbounded (generalized) hypertree width,
and so forth.
2.1.3

Tree decompositions and their widths

This section defines more precisely commonly used width parameters, which are parameters of the tree
decompositions of the input query. Tree decompositions capture conditional independence among variables
in a query, facilitating dynamic-programming. We refer the reader to the recent survey by Gottlob et al. [32]
for more details on historical contexts, technical descriptions, and open problems thereof.
Definition 2.5. A tree decomposition of a hypergraph H = ([n], E) is a pair (T, χ), where T is a tree and
χ : V (T ) → 2[n] maps each node t of the tree to a subset χ(t) of vertices such that (1) Every hyperedge
F ∈ E is a subset of some χ(t), t ∈ V (T ), (2) For every vertex v ∈ [n], the set {t | v ∈ χ(t)} is a nonempty (connected) sub-tree of T . Somewhat confusingly, the sets χ(t) are often called the bags of the tree
decomposition.
A compact method of defining width parameters is the framework introduced by Adler [4].
Definition 2.6. Let H = ([n], E) be a hypergraph, and g : 2[n] → R+ be a set function. The g-width of
a tree decomposition (T, χ) is maxt∈V (T ) g(χ(t)). The g-width of H is the minimum g-width over all tree
decompositions of H. Note that the g-width of a hypergraph is a minimax function.
Definition 2.7. For any subset of vertices B ⊆ [n], denote by HB = (B, {F ∩ B | F ∈ E}) the hypergraph
restricted to B. Define s(B) = |B| − 1, ρ(B) = ρ(HB ) the integral edge cover number of HB , and ρ∗ (B) =
ρ∗ (HB ), its fractional edge cover number. Then, the treewidth of H, denoted by tw(H), is the s-width of H.
The generalized hypertree width of H, denoted by ghtw(H) is the ρ-width of H. And, the fractional hypertree
width of H, denoted by fhtw(H), is the ρ∗ -width of H.
7 Redrawn

from Marx’s slides at http://www.cs.bme.hu/~ dmarx/papers/marx-weizmann-hypergraph.pdf

14

Very recently, Fischl et al. [27] showed that, checking whether a given hypergraph has a fractional
hypertree width or a generalized hypertree width at most 2 is NP-hard, settling two important open questions.
The common approach to compute a Boolean query Q using the tree decomposition is to compute
the full conjunctive query associated to the hypergraph Hχ(t) at each tree node t, then run Yannakakis’
algorithm [48] on the acyclic conjunctive query consisting of their results. It is known [2, 5, 14, 23, 38] that a
vast number of problems in graphical model inference, database query computation, constraint satisfaction,
and logic can be solved using this strategy. However, this tree-decomposition-first strategy has a drawback
that once we stick with a tree decomposition we are forced to suffer the worst-case instance for that tree
decomposition. Marx [39, 40] had a wonderful observation: if we partition the data first, and then use a
different tree decomposition for each part of the data, then we can in some cases significantly improve the
runtime. This idea leads to the notions of adaptive width and submodular width of a query, where in essence
data partitioning and query decomposition are used interleavingly.
Definition 2.8. The adaptive width adw(H) of H and the submodular width subw(H) of H are defined by
adw(H)
subw(H)

def

=

def

=

max

min max h(χ(t)),

(36)

max

min max h(χ(t)),

(37)

h∈ED∩Mn (T,χ) t∈V (T )

h∈ED∩Γn (T,χ) t∈V (T )

where ED is the set of edge-dominated functions (Definition 2.4).
Marx [40] proved that adw(H) ≤ subw(H) ≤ fhtw(H), and that subw(H) = O(adw4 (H)), for any H.
There are classes of queries for which subw(H) is bounded by a constant while fhtw(H) grows with the query
size (see also Example 7.4). Marx also designed an algorithm showing that Boolean conjunctive queries can
be solved in data-complexity time O(poly(N subw(H) )).
The definitions of the traditional width parameters and the adaptive and submodular width parameters
are somewhat disconnected from one another. In Section 7, we will explain how all these width parameters
can be unified using the same information-theoretic framework which can deal with much more general
constraints on the input queries. We will also present a simple example showing the unbounded gap between
subw(H) and fhtw(H) for some class of graphs.
A tree decomposition is non-redundant if no bag is a subset of another. A tree decomposition (T1 , χ1 ) is
dominated by another tree decomposition (T2 , χ2 ) if every bag of (T1 , χ1 ) is a subset of some bag of (T2 , χ2 ).
Let TD(H) denote the set of all non-redundant tree decompositions of H such that no tree decomposition
in TD(H) is dominated by another tree decomposition in TD(H). We will also use TD(Q) to denote TD(H)
where H is Q’s hypergraph. In many cases, we drop the qualifier Q or H for brevity. We shall use the
following crude estimate in Section 7.
Proposition 2.9. (Bounding the number of tree decompositions and the size of each tree decomposition)
Given a hypergraph with n vertices, |TD| ≤ n! and the number of bags of a non-redundant tree decomposition
is at most n. In particular, |TD| = O(1) in data complexity.
Proof. Every non-dominated non-redundant tree decomposition can be constructed from a variable ordering [2], and there are n! variable orderings. When we run GYO-elimination on such a tree decomposition
with an arbitrary root-bag, every bag contains a variable that does not belong to the parent bag.
The above bound is certainly an over-estimate even for graphs with an exponential number of minimal
non-redundant tree decompositions. For example, if the graph is an n-cycle, then every minimal nonredundant tree decomposition
precisely to a triangularization of an n-gon, which is the (n − 1)th
 corresponds
2n−1
1
n
Catalan number n−1
n−1 = o(4 ).

2.2

Bounds for queries with FD and degree constraints

The series of bounds and width parameters from Section 2.1 were based on a single class of statistics on the
input relations: their sizes. In practice we very often encounter queries with degree bounds, or functional
15

dependencies (FD) which can be seen as special cases of degree bounds equal to 1. The FDs come from two
main sources: primary keys and builtin predicates (such as A1 + A2 = A3 ). The degree constraints come
from more refined statistics of the input (materialized) relations, or from some user-defined predicates, for
example the relation edit-distance(A1 , A2 ) ≤ 2 has a bounded degree that depends on the maximum length
of the strings A1 , A2 .
Definition 2.10 (Degree constraints and their guards). A degree constraint is a triple (X, Y, NY |X ) where
X ⊂ Y ⊆ [n] and NY |X ∈ N ∪ {∞}. A relation/predicate RF is said to guard the degree constraint
(X, Y, NY |X ) if X ⊂ Y ⊆ F and for every tuple tX we have
def

degRF (Y |tX ) = |ΠY (σAX =tX (RF ))| ≤ NY |X .

(38)

The quantity on the left-hand side is called the degree of tX with respect to Y in relation RF . Note that a
relation may guard multiple degree constraints.
def
To avoid writing log2 in many places, define nY |X = log2 NY |X . We use DC to denote a set of degree
constraints. A cardinality constraint is a degree constraint of the form (∅, F, NF ). We use CC to denote a
set of cardinality constraints. An FD X → Y is a degree constraint of the form (X, Y, 1). Thus, degree
constraints strictly generalize both cardinality constraints and FDs. Similar to HDC defined by (6), we use
HCC (and HFD) to denote the collections of set functions h satisfying cardinality constraints CC (and FDs
respectively).
As an example on guards of degree constraints, consider an input relation R(A1 , A2 , A3 ) satisfying the
following conditions: for every value a1 in the active domain of A1 , there are at most D different values
a2 ∈ Dom(A2 ) such that (a1 , a2 ) ∈ ΠA1 A2 (R). Then, R guards the degree constraint ({A1 }, {A1 , A2 }, D).
As explained earlier, and as shown in [3], the output size of Q(A[n] ) can be bounded by
log2 |Q| ≤

max h([n]) ≤ max h([n])
h∈HDC∩Γn
{z
}
{z
} |

h∈HDC∩Γ̄∗
n

|

DAEB(Q)

(39)

DAPB(Q)

DAEB and DAPB stand for “degree-aware” entropic and polymatroid bounds, respectively. Note that (39) is
a special case of (8) and (9). The CSMA algorithm from [3] can solve a Boolean query Q with known degree
constraints in time Õ(N + poly(log N ) · 2DAPB(Q) ). We shall use the quantities DAEB(Q) and DAPB(Q) in
Fig. 9.

3
3.1

Size bounds for full conjunctive queries
Basic observations

We revisit known output size bounds for conjunctive queries without FDs nor degree constraints, and reformulate them from the perspective of the information theoretic framework. We first prove a simple lemma,
which shows that, sometimes we can “modularize” an optimal submodular function under cardinality constraints. Recall that CC denotes a set of cardinality constraints and HCC denotes the collections of set
functions h satisfying the cardinality constraints.
Lemma 3.1 (Modularization Lemma). Given a (not-necessarily full) conjunctive query Q with hypergraph
H = ([n], E) and degree constraints CC, let B ⊆ [n] be arbitrary. Then, we have
max{h(B) | h ∈ Mn ∩ HCC} = max{h(B) | h ∈ Γn ∩ HCC}.

16

(40)

Proof. Up to renumbering, we can assume B = [k] for some positive integer k. SetP[0] = ∅ by convention. Let
h∗ = argmax{h(B) | h ∈ Γn ∩ HCC}. Define a set function h̄ as follows: h̄(F ) = i∈F (h∗ ([i]) − h∗ ([i − 1])),
for any ∅ 6= F ⊆ [n], and h̄(∅) = 0. Clearly h̄ ∈ Mn and h̄(B) = h∗ (B). Next, we prove h̄ ∈ HCC by proving
h̄(F ) ≤ h∗ (F ) for all F ⊆ [n], by induction on |F |. The base case when |F | = 0 is trivial. For the inductive
step, let j be the maximum integer in F , then by noting that |F ∩ [j − 1]| < |F |, we have
X
(h∗ ([i]) − h∗ ([i − 1]))
h̄(F ) = h∗ ([j]) − h∗ ([j − 1]) +
i∈F −{j}

∗

(induction hypothesis)
(submodularity of h∗ )

∗

= h ([j]) − h ([j − 1]) + h̄(F ∩ [j − 1])
= h∗ (F ∪ [j − 1]) − h∗ ([j − 1]) + h̄(F ∩ [j − 1])

≤ h∗ (F ∪ [j − 1]) − h∗ ([j − 1]) + h∗ (F ∩ [j − 1])

≤ h∗ (F ).

Consequently, h̄ ∈ Mn ∩ HCC and thus max{h(B) | h ∈ Mn ∩ HCC} ≥ max{h(B) | h ∈ Γn ∩ HCC}. The
reverse inequality is trivial because Mn ⊆ Γn .
Recall that a full conjunctive query is a special case of a disjunctive datalog rule: It is a disjunctive
datalog rule with only one target B = [n]. Hence for a full conjunctive query Q, the log-size-bound defined
by (7) simplifies to
def

LogSizeBoundF (Q) = max h([n]).

(41)

h∈F

The following simple proposition recaps major known bounds under one umbrella. Since the proposition
is restricted to full conjunctive queries rather than the more general disjunctive datalog rules, it makes
stronger claims about size bounds: In particular, some bounds for full conjunctive queries collapse part of
∗
the hierarchy of function classes: Mn ⊆ Γn ⊆ Γn ⊆ SAn . In the following, we use notations defined in
Section 2.
Proposition 3.2. Let Q be a full conjunctive query with no FDs whose hypergraph is H = ([n], E). Then
the followings hold:
log VB(Q) = LogSizeBoundF ∩(log N ·VD) (Q),
ρ(Q, (NF )F ∈E ) = LogSizeBoundSAn ∩HCC (Q)

∗

∀F ∈ {Mn , Γn , Γn , SAn }

∗

∀F ∈

log AGM(Q) = LogSizeBoundF ∩HCC (Q),

∀F ∈

ρ (Q) · log N = LogSizeBoundF ∩(log N ·ED) (Q),

∗
{Mn , Γn , Γn }
∗
{Mn , Γn , Γn }

(42)
(43)
(44)
(45)

Proof. We prove (45) first, which implies (44). By strong duality of linear programming, we have log AGM(Q) =
LogSizeBoundMn ∩HCC (Q). Lemma 3.1 implies LogSizeBoundMn ∩HCC (Q) = LogSizeBoundΓn ∩HCC (Q).
To prove (42), note that log VB(Q) = LogSizeBoundMn ∩(log N ·VD) (Q) is trivial. Since Mn ⊆ SAn it is
sufficient to show that LogSizeBoundSAn ∩(log N ·VD) (Q)P≤ n log N = log
P VB(Q). Let h ∈ SAn ∩ (log N · VD) be
arbitrary, then from sub-additivity we have h([n]) ≤ v∈[n] h(v) ≤ v∈[n] log N = n log N , which completes
the proof.
Lastly, we prove equality (43) which is the only non-trivial statement in this proposition. Recall the
definition of ρ(Q, (NF )F ∈E ) from (32). Let (λF )F ∈E ∈ ECP ∩ NE be any integral edge cover of H, and
h ∈ SAn ∩ HCC be arbitrary. Let {F1 , . . . , Fk } be the collection of all hyperedges in E with λFi = 1, ∀i ∈ [k].

17

Then,
h([n]) ≤
≤
=



k
X

h Fi \

i=1

k
X

j=1



Fj 

(sub-additivity)

h (Fi )

(monotonicity)

i=1

X

F ∈E

≤

i−1
[

X

λF · h(F )
λF log NF

(cardinality constraints)

F ∈E

= log

Y

NFλF

F ∈E

!

.

This proves LogSizeBoundSAn ∩HCC (Q) ≤ ρ(Q, (NF )F ∈E ). Conversely, suppose h∗ is an optimal solution to
the linear program max {h([n]) | h ∈ SAn ∩ HCC}, which is explicitly written as
max h([n])
s.t. h(I ∪ J) − h(I) − h(J) ≤ 0,

(46)
I⊥J

h(F ) ≤ log NF ,
h(X) − h(Y ) ≤ 0,

F ∈E
X ⊂ Y ⊆ [n]

h(Z) ≥ 0

(i.e. I 6⊆ J and J 6⊆ I)

∅ 6= Z ⊆ [n].

We are done if we can prove the following claim:
P
Claim 1: there is an integral edge cover (λF )F ∈E such that F ∈E λF log NF ≤ h∗ ([n]).
To prove this claim, we need the dual of the LP (46). Associate a dual variable δF to each cardinality
constraint h(F ) ≤ log NF , a dual variable σI,J to each sub-additivity constraint h(I ∪ J) − h(I) − h(J) ≤ 0,
def

and a dual variable µX,Y to each monotonicity constraint h(X) − h(Y ) ≤ 0. For convenience, let δZ = 0 for
any Z ∈ 2[n] \ E. For any Z ⊆ [n], define flow(Z) to be
X
X
X
X
def
flow(Z) = δZ +
σI,J −
σZ,J −
µX,Z +
µZ,Y .
(47)
I⊥J:I∪J=Z

X:X⊂Z

J:J⊥Z

Y :Z⊂Y

Then, the dual LP is
min
s.t.

P

F ∈E (log NF )

flow(Z)
flow([n])

· δF

(48)
≥ 0, ∅ 6= Z ⊆ [n]
≥1

≥ 0.

(δ, σ, µ)

We need the following auxiliary claim.
Claim 2: given a rational feasible dual solution (δ, σ, µ), let D be a common denominator for all entries
(i)
in (δ, σ, µ). Then, there exist D integral edge covers λ(i) = (λF )F ∈E , i ∈ [D], such that for any F ∈ E,
PD (i)
i=1 λF ≤ D · δF .
Assuming
we prove Claim 1. Let (δ ∗ , σ ∗ , µ∗ ) be a rational optimal dual solution, then
P Claim 2 holds,
∗
∗
h ([n]) = F ∈E (log NF ) · δF by strong duality. Applying Claim 2 on (δ ∗ , σ ∗ , µ∗ ), we get
h∗ ([n]) ≥

X X λ(i)
X (i)
1 X X (i)
F
log NF =
λF log NF ≥ min
λF log NF .
D
D
i∈[D]

F ∈E i∈[D]

i∈[D] F ∈E

18

F ∈E

This proves Claim 1.
Proof of Claim 2: Note the following: if flow(B) > δB for some B 6= ∅, then from (47) and the fact that
(δ, σ, µ) is feasible to the dual LP, there must be either (1) I ⊥ J with I ∪ J = B and σI,J > 0, or (2)
def

Y ⊃ B with µB,Y > 0. Let w = 1/D. Initially, let B = {[n]}. While there is B ∈ B with flow(B) > δB , we
do the following:
• If Case (1) holds, then we reduce σI,J by w, remove B from B, and add both I and J to B.
• If Case (2) holds, then we reduce µB,Y by w, remove B from B, and add Y to B.
Either way, we are maintaining the following invariants (which initially hold):
• flow(B) > 0 for any B ∈ B.
• flow(Z) ≥ 0 for any ∅ 6= Z ⊆ [n].
• For any v ∈ [n], there is some B ∈ B such that v ∈ B.
The above process terminates because at each iteration we are reducing kσk1 + kµk1 by w. When it does
(1)
terminate, we have δB ≥ flow(B) > 0 for all B ∈ B. Note that δZ = 0 for all Z ∈ 2[n] − E. Hence, (λF )F ∈E
is an integral edge cover where
(
1 if F ∈ B,
(1) def
λF =
0 otherwise.

This way, we have constructed the first integral edge cover λ(1) out of the promised D integral edge covers.
Now for every B ∈ B, we reduce δB (hence flow(B)) by w and remove B from B. Notice that except for
the initial [n] in B, the following was always maintained. Before we added any B to B we increased flow(B)
by w, and before we removed any B ′ from B we decreased flow(B ′ ) by w. Therefore, at the end flow(Z)
is unchanged for all Z ⊂ [n], and flow([n]) is reduced by w. If the final flow([n]) = 0, then we are done.
1
· (δ, σ, µ) is a feasible dual solution with (D − 1) as a common denominator, and we can
Otherwise, 1−w
repeat the process to construct the next integral edge cover.
The top part of Figure 9 (which we shall elaborate more on later) depicts all the bounds in Proposition 3.2.
Regarding the AGM-bound, the fact that the size bound on Γn is equal to the size bound on Mn allows us to
compute the bound efficiently (polynomial time in query complexity). By contrast, computing the integral
edge cover bound is NP-hard in query complexity, despite being the worse bound, i.e. the bound over the
∗
more relaxed function class SAn . From the above proposition and the chain of inclusion Mn ⊆ Γn ⊆ Γn ⊆ SAn
and HCC ⊆ VD · log N , we have VB(Q) ≥ 2ρ(Q,(NF )F ∈E ) ≥ AGM(Q) for any Q.

3.2

The polymatroid size bound is not tight!

Next, we prove Theorem 1.3, which states that the polymatroid bound is not tight for queries with cardinality
and FD constraints.
Proof of Theorem 1.3. Consider the following which we shall call the Zhang-Yeung query:
Q(A, B, X, Y, C) ← K(A, B, X, Y, C), R(X, Y ), S(A, X), T (A, Y ), U (B, X), V (B, Y ), W (C)

(49)

with given cardinality constraints |R|, |S|, |T |, |U |, |V | ≤ N 3 , |W | ≤ N 2 (none on K, or |K| ≤ N c for large
constant c), and the following keys in K: AB, AXY , BXY , AC, XC, Y C. We prove two claims.
Claim 1: the following inequality holds for all entropic functions h ∈ Γ∗5 :
11h(ABXY C) ≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) + 5h(C)

+ (h(ABXY C|AB) + 4h(ABXY C|AXY ) + h(ABXY C|BXY ))
+ (h(ABXY C|AC) + 2h(ABXY C|XC) + 2h(ABXY C|Y C)).
19

(50)

4 ABXY C

3 AX

3 BX

3 XY

3 AY

3 BY
2 C

2 X

2 A

2 B

2 Y

0 ∅
Figure 5: A polymatroid h (shown in green).
Claim 2: there exists a polymatroid h satisfying all cardinality and FD constraints such that h(ABXY C) =
4 log N .
1
The first claim implies 11 log |Q| ≤ 11 log N 3 + 5 log N 2 = 43 log N , or |Q| ≤ N 4− 11 , while the second
1
claim shows that the polymatroid bound is ≥ N 4 . In other words, the two claims show a ratio of N 11 between
s
the two bounds. To construct a query with an amplified gap of N between the two bounds, consider a
query which is a cross-product of 11s variable-disjoint copies of the basic Zhang-Yeung query.
Proof of Claim 1. Let I(X; Y|Z) := h(XZ) + h(YZ) − h(XYZ) − h(Z) denote the conditional mutual
information between random variables X and Y conditioned on random variables Z. In a breakthrough
∗
paper in information theory, Zhang and Yeung [50] proved that Γ4 ( Γ4 by proving that the following
inequality is a non-Shannon-type inequality (see [49, Th.15.7]), i.e. an inequality satisfied by all entropic
functions and not satisfied by some polymatroid:
2I(X; Y ) ≤ I(A; B) + I(A; XY ) + 3I(X; Y |A) + I(X; Y |B),
or equivalently
h(AB) + 4h(AXY ) + h(BXY ) ≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY )
− h(A) − 2h(X) − 2h(Y ).

(51)

Let h be any entropic function on 5 variables A, B, X, Y, C, then it still satisfies inequality (51), because
the restriction of h on the 4 variables A, B, X, Y is the marginal entropy. Now, add h(ABXY C|AB) +
4h(ABXY C|AXY ) + h(ABXY C|BXY ) to both sides:
6h(ABXY C) ≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) − (h(A) + 2h(X) + 2h(Y ))
+ (h(ABXY C|AB) + 4h(ABXY C|AXY ) + h(ABXY C|BXY ))

(52)

From these three Shannon-type inequalities h(A) + h(C) ≥ h(AC), h(X) + h(C) ≥ h(XC), and h(Y ) +
h(C) ≥ h(Y C) we derive the following:
5h(ABXY C) ≤ h(A) + 2h(X) + 2h(Y ) + 5h(C)
+ (h(ABXY C|AC) + 2h(ABXY C|XC) + 2h(ABXY C|Y C))

(53)

By adding Eq.(52) and (53) we obtain (50).
Proof of Claim 2. The proof is shown in Fig. 5. The figure shows a polymatroid h on the five variables
def
A, B, X, Y, C. For each missing set of variables Z, h(Z) = h(Z+ ), where Z+ is the smallest set shown in the
20

figure that contains Z: in other words, the figure shows the closed sets of a closure on {A, B, X, Y, C}. For
def

def

example, h(AB) = h(AB + ) = h(ABXY C) = 4, etc. One can check that ĥ = log N · h is a polymatroid
satisfying all cardinality constraints and functional dependencies: for example ĥ(XY ) = 3 log N , ĥ(AX) =
3 log N , and ĥ(AB) = ĥ(ABXY C) satisfies the FD AB → XY C.

4
4.1

Size bounds for disjunctive datalog rules
The entropic bound for disjunctive datalog

Lemma 4.1 (Part (i) of Theorem 1.5). For any disjunctive datalog rule P of the form (4), and any database
instance D, the following holds:
log |P (D)| ≤ LogSizeBoundΓ∗n ∩HDC (P ) ≤ LogSizeBoundΓn ∩HDC (P ).
∗

Proof. Since Γn ⊆ Γn , the second inequality is trivial. To show the first inequality, let T denote the set of
all tuples t satisfying the body of P ; construct a set T of tuples as follows. We scan though tuples t ∈ T
one at a time, and either add t to T or ignore t. To decide whether to add t to T , we also keep a collection
of tables T = (T B )B∈B . These tables shall form a model of the disjunctive datalog rule P . Initially T and
all the T B are empty. Consider the next tuple t taken from T . If ΠB (t) ∈ T B for any target B ∈ B, then
we ignore t. Otherwise, we add ΠB (t) to T B for every B ∈ B, and add t to T . In the end, obviously the
collection (T B )B∈B is a model of the disjunctive datalog rule. Furthermore, by construction the tuples t ∈ T
satisfy the property that: for every two different tuples t, t′ ∈ T , every B ∈ B, we have ΠB (t) 6= ΠB (t′ ) and
both ΠB (t) and ΠB (t′ ) are in T B .
Now, construct a joint probability distribution on n variables by picking uniformly a tuple from T . Let
h denote the entropy function of this distribution, then, from the above property
log2 |T | = h([n]) = h(B), ∀B ∈ B.

(54)

∗

Furthermore, h ∈ Γn by definition, and h ∈ HDC because T ⊆ T and T was the join of input relations
satisfying all degree constraints. Consequently,
log |P (D)| =

min

max log2 |TB | ≤

max log2 |T B |

(due to (54)) =

max h(B)

(due to (54)) =

min h(B)

(TB )B∈B |=P B∈B

(because h̄ ∈

∗
Γn

∩ HDC) ≤
=

4.2

B∈B

B∈B

B∈B

max
∗

min h(B)

h∈Γn ∩HDC B∈B

LogSizeBoundΓ∗ ∩HDC (P ).
n

The entropic bound is asymptotically tight under degree constraints

Recall that HDC, HCC and HFD denote the collection of set functions h satisfying the degree constraints, cardinality constraints and functional dependencies respectively. Recently, Gogacz and Toruńczyk [31] showed
that LogSizeBoundΓ∗ ∩HCC∩HFD (Q) is an asymptotically tight upper bound for full conjunctive queries Q
n
with FDs. This section proves a generalization of their result in two different directions: We show that
LogSizeBoundΓ∗ ∩HDC (P ) is asymptotically tight for disjunctive datalog rules P with given degree constraints
n
HDC.
The proof is based on the same observation made in [31]: one can take the group characterizable entropy
function from Chan and Yeung [19] and turn it into a database instance.
21

Three technical issues we need to nail down to push the proof through are the following. First, we need to
make sure that the database instance so constructed satisfies the given degree constraints (which include FD
and cardinality constraints). Second, it takes a bit more care to define what we meant by “asymptotically
tight” in the case of queries with degree bounds. When the input query has only input relation cardinality
bounds and functional dependencies, one can set all input relations to be of the same cardinality N and let
N go to infinity. The tightness of the bound is in the exponent α (if the bound was N α ). This was the
result from Gogacz and Toruńczyk. When the input query has degree bounds, it does not make sense to
set all degree bounds (and cardinality bounds) to be N : we want a finer level of control over their relative
magnitudes. Third, and most importantly, unlike in the full conjunctive query case where there is only one
output; in the disjunctive datalog rule case there are multiple models and we have to show that any model
to the rule must have size asymptotically no smaller than the worst-case entropic bound.
We start with the construction from Chan and Yeung [19].
Definition 4.2 (Database instance from group system). Let G be a finite group and G1 , . . . , Gn be n
subgroups of G. A database instance associated with this group system (G, G1 , . . . , Gn ) is constructed as
follows. There are n attributes A1 , . . . , An . The domain of attribute Ai is the left coset space G/Gi , i.e. the
collection of all left cosets {gGi | g ∈ G} of the subgroup Gi . For every F ⊆ [n], define a relation RF by
def

RF = {(gGi )i∈F | g ∈ G}.

(55)

In other words, RF is the set of tuples aF = (ai )i∈F on attributes AF , where ai = gGi for some g ∈ G. The
group element g is said to define the tuple aF .
def T
Given a group system (G, G1 , . . . , Gn ), for any ∅ 6= F ⊆ [n], define GF = i∈F Gi ; and, define G∅ = G.
Note that GZ is a subgroup of GY for all ∅ ⊆ Y ⊆ Z ⊆ [n]. Recall the notion of degree defined in (38). We
prove the following lemma, which is a slight generalization of Proposition 4 from Chan [18].
Lemma 4.3. Let D be a database instance associated with the group system (G, G1 , . . . , Gn ). Let ∅ ⊆ Z ⊂
Y ⊆ [n] be two sets of attributes (Z can be empty). Then, for any tuple aZ ∈ RZ :
degRY (Y |aZ ) =

|GZ |
.
|GY |

In particular, Z → Y is an FD satisfied by the database instance iff GZ is a subgroup of

(56)
T

i∈Y −Z

Gi .

Proof. For any F ⊆ [n],
T two group elements b, c ∈ G define the same tuple aF in RF , i.e. cGi = bGi , ∀i ∈ F ,
if and only if b−1 c ∈ i∈F Gi = GF , which is equivalent to b = cg for some g ∈ GF .
Now suppose aZ ∈ RZ was defined by an element b ∈ G, i.e. aZ = (ai )i∈Z = (bGi )i∈Z . Consider any
two group elements c1 , c2 ∈ G which define the same aZ tuple but different aY tuples. First, c1 , c2 ∈ G
define the same aZ iff there are two elements g1 , g2 ∈ GZ such that c1 = bg1 and c2 = bg2 . Second, c1 and
c2 define different aY tuples iff c−1
/ GY , which is equivalent to g1−1 b−1 bg2 = g1−1 g2 ∈
/ GY , which in turn
1 c2 ∈
is equivalent to g1 GY 6= g2 GY . Thus, the degree of aZ in RY is precisely the index of the subgroup GY in
the group GZ , which is equal to |GZ |/|GY |.
If Z → Y is a functional dependency, then from the fact that
T GY is a subgroup of GZ and the inequality
|GZ |/|GY | ≤ 1, we conclude that GZ has to be a subgroup of i∈Y −Z Gi . The converse holds trivially.

For a given set of degree constraints HDC, let HDC × k denote the same set of constraints but with all the
degree bounds are multiplied by k. The constraints HDC × k are called the “scaled up” degree constraints.

Lemma 4.4 (Part (ii) of Theorem 1.5). Let P be the disjunctive datalog rule (4) with degree constraints
HDC, where LogSizeBoundΓ∗ ∩HDC (P ) ≥ 1. For any ǫ > 0, there exists a scale factor k and a database instance
n
D satisfying the scaled-up degree constraints HDC × k for which the following holds:
log |P (D)| ≥ (1 − ǫ) · LogSizeBoundΓ∗n ∩HDC×k (P ).

22

∗

Proof. Let H = argmaxh∈Γ∗ ∩HDC minB∈B h(B). Note that, Γn is a convex cone, and thus kH is an optimal
n
solution to the problem maxh∈Γ∗ ∩HDC×k minB∈B h(B). Following Chan and Yeung [19] without loss of
n
generality we assume that there is a distribution on n random variables A1 , . . . , An such that all their
domains Dom(Ai ) are discrete and finite, and that H is the joint entropy all of whose marginal entropies are
rational numbers. (In general, just as in Chan and Yeung [19], if H is not rational, or is not an entropy over
discrete random variables of finite domains, we construct a sequence of distributions over discrete and finite
domains whose entropies Q
tend to H.)
For any tuple aF ∈ i∈F Dom(Ai ), we use p(aF ) to denote Pr[AF = aF ], i.e. p is the probability
mass function. Let d denote the minimum common denominator of all probabilities p(a[n] ), over all tuples
2δ
a[n] for which p(a[n] ) > 0. Set δ such that ǫ = 1+δ
, and let r be a multiple of d sufficiently large so that
Qn
d
2
d log2 e + 2 log2 d ≤ δr and log2 r ≥ d log2 (e ). Construct a matrix Mr whose columns are in i=1 Dom(Ai )
where column a[n] appears precisely r · p(a[n] ) times.
The following construction of a group system is from Chan and Yeung [19]. Let Gr denote the group of
permutations of columns of Mr . This group acts on the rows of Mr . For i ∈ [n], let Gri be the subgroup of
r
r
Gr that fixes the ith
Q row of Mr , i.e G is the stabilizer subgroup of G with respect to the ith row of Mr .
r
Note that |GF | = aF (r · p(aF ))!, where the product is over all vectors aF which have positive probability
mass. Consider the database instance Dr associated with the group system (Gr , Gr1 , . . . , Grn ). We claim that
this database instance satisfies all degree constraints HDC × k for scale factor k = r(1 + δ).
First, we verify that Dr satisfies all the functional dependency constraints (i.e. the degree upperbounds
of 0). Let Z → Y be an FD. Then, H[AY |AZ ] = 0, which means for every tuple aZ with positive probability
mass, the tuple aY −X is completely determined. In particular, there cannot be two vectors aY 6= a′Y with
positive probability mass for which ΠX (aY ) = ΠX (a′Y ). Thus, if a permutation fixes all the
T rows in Z, then
it also fixes all the rows in Y − Z of the matrix Mr . This means GZ is a subgroup of i∈Y −Z Gi . From
Lemma 4.3, the associated database instance satisfies the FD.
Second, we verify the higher-order degree constraints (with degree bounds nY |Z = log2 NY |Z ≥ 1). From
definition of probability mass, entropy, and the monotonicity of the log2 function, we know the obvious facts
that
X
p(aF ) = 1,
aF

−

X

p(aF ) log2 p(aF ) =

H[AF ],

aF

X
aF

X
aF

log2 (c · p(aF ))
log2



1
p(aF )



In the above and henceforth in this section,
Stirling approximation8 we have
Y
log2 |GrF | = log2 (r · p(aF ))!

≤

d · log2

≤

d · log2 d.

P

aF

X
aF

!

c · p(aF )

= d · log2 c.

denotes the sum over all positive-mass vectors aF . From

aF

≤
=


X
1
log2 (e) + r · p(aF ) log2 (r · p(aF )) + log2 (r · p(aF )) − r · p(aF ) log2 e
2
aF


X
1
log2 e + log2 (r · p(aF ))
r log2 (r/e) − rH[AF ] +
2
a
F

8

√
log2 ( 2π) + n log2 n +

1
2

log2 n − n log2 e ≤ log2 n! ≤ log2 (e) + n log2 n +

23

1
2

log2 n − n log2 e

√

P
Similarly, log2 |GrF | ≥ r log2 (r/e) − rH[AF ] + aF log2 2π + 12 log2 (r · p(aF )) . We now use Stirling approximation as above and Lemma 4.3 to bound


Q
|GrZ |
aZ (r · Pr AZ = aZ )!


log2 r
= log2 Q
|GY |
aY (r · Pr AY = aY )!
"
#
X
1
log2 e + log2 (r · p(aZ ))
≤
r log2 (r/e) − rH[AZ ] +
2
aZ
"
#
X
√
1
log2 2π + log2 (r · p(aY ))
− r log2 (r/e) − rH[AY ] +
2
aY



X
X
√
1
1
log2 e + log2 (r · p(aZ )) −
log2 2π + log2 (r · p(aY ))
= rH[AY |AZ ] +
2
2
aZ
aY
X
1
1
log2
≤ rH[AY |AZ ] + d log2 e +
2 a
p(aY )
Y

≤
≤

≤
≤

=

d
rH[AY |AZ ] + d log2 e + log2 d
2
rH[AY |AZ ] + δr
rnY |Z + δr
r(1 + δ)nY |Z
k · nY |Z .

Third, let T = (TB )B∈B be any model of the rule P on the database instance D satisfying the scaled degree
constraints HDC × k. We are to show that
max log2 |TB | ≥ (1 − ǫ) · LogSizeBoundΓ∗ ∩HDC×k (P ) = (1 − ǫ) · k · min H[AB ].
B∈B

B∈B

n

(57)

Let Q denote the set of tuples satisfying the body of the rule (i.e. Q is the join of all atoms in the body).
To bound maxB∈B |TB |, we reason as follows. First, without loss of generality, we can assume TB ⊆ RB , for
all B ∈ B, because tuples in TB \ RB can be removed while keeping T a model of P . Second, for any B ∈ B,
we say that tB ∈ RB “covers” a tuple a ∈ Q whenever ΠB (a) = tB . From Lemma 4.3, for every B ∈ B, and
|Gr |
|Gr |
every tuple tB ∈ RB , there are precisely |GrB | tuples a ∈ Q covered by tB . The size of RB is exactly |Gr∅ |
B

[n]

and the size of Q (i.e. R[n] ) is exactly
let B̄ = argmaxB∈B

|GrB |
|Gr[n] | .

|Gr∅ |
|Gr[n] | .

Hence, no two tuples in RB cover the same tuple in Q. Third,

Then,
|Gr∅ |
|Gr[n] |

(every tuple in Q has to be covered)

= |Q|
|GrB |
|Gr[n] |
B∈B
!


X |Gr |
B
≤
max |TB | ·
B∈B
|Gr[n] |
B∈B
!


|GrB |
≤
max |TB | · |B| · max r
B∈B
B∈B |G |
[n]
!


r
|GB̄ |
.
= |B| max |TB | ·
B∈B
|Gr[n] |

≤

24

X

|TB | ·

Hence,
max |TB | ≥
B∈B

1 |Gr∅ |
1
=
|R |.
|B| |GrB̄ |
|B| B̄

To complete the proof of (57), we are left to show that
log2

|RB̄ |
≥ (1 − ǫ) · k · min H[AB ],
B∈B
|B|

which would follow immediately from showing that
log2 |RB̄ | − log2 |B| ≥ (1 − ǫ) · k · H[AB̄ ].
Recall that we assumed LogSizeBoundΓ∗n ∩HDC (P ) ≥ 1 which means H[AB̄ ] ≥ 1, and thus
1
d log2 r + log2 |B| ≤ δrH[AB̄ ]
2

(58)

for sufficiently large r. We have,
log2 |RB̄ | − log2 |B| = log2

r!
− log2 |B|
|GrB̄ |


√
1
≥
r log2 (r/e) + log2 r + log2 2π
2



X
1
− r log2 (r/e) − rH[AB̄ ] +
log2 e + log2 (r · p(aB̄ ))  − log2 |B|
2
a


B̄

√
1
1X
log2 (re2 p(aB̄ )) − log2 |B|
= rH[AB̄ ] + log2 2π + log2 r −
2
2 a
B̄

≥
=
≥
(due to (58))

≥
=
=

4.3

1
1
rH[AB̄ ] + log2 r − d log2 (re2 ) − log2 |B|
2
2
1
1
r(1 + δ)H[AB̄ ] − δrH[AB̄ ] − d log2 (r) + (log2 r − d log2 (e2 )) − log2 |B|
2
2
1
r(1 + δ)H[AB̄ ] − δrH[AB̄ ] − d log2 (r) − log2 |B|
2
r(1 + δ)H[AB̄ ] − 2δrH[AB̄ ]


2δ
1−
r(1 + δ)H[AB̄ ].
1+δ
(1 − ǫ) · k · H[AB̄ ].

The polymatroid bound for disjunctive datalog is not tight

Lemma 4.5 (Part (iii) of Theorem 1.5). The polymatroid bound for a disjunctive datalog rule is not tight,
even if the input constraints are only cardinality constraints, and all cardinality upperbounds are identical.
Proof. We first give a short proof for the case when the upperbounds vary, to illustrate the main idea. The
non-Shannon inequality (51) along with the following three submodularity inequalities
h(AC) ≤ h(A) + h(C)

h(XC) ≤ h(X) + h(C)

25

h(Y C) ≤ h(Y ) + h(C)

imply that the following hold for all entropic functions h on five variables X, Y, A, B, C,
h(AB) + 4h(AXY ) + h(BXY )
≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) − h(A) − 2h(X) − 2h(Y )

≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) − h(AC) − 2h(XC) − 2h(Y C) + 5h(C).

Moving all negative terms to the left hand side, we have equivalently
h(AB) + 4h(AXY ) + h(BXY ) + h(AC) + 2h(XC) + 2h(Y C)
≤ 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) + 5h(C). (59)
Now, consider the disjunctive datalog rule
P : T1 (AB) ∨ T2 (AXY ) ∨ T3 (BXY ) ∨ T4 (AC) ∨ T5 (XC) ∨ T6 (Y C)
← R1 (XY ) ∧ R2 (AX) ∧ R3 (AY ) ∧ R4 (BX) ∧ R5 (BY ) ∧ R6 (C),
with the following cardinality bounds: |R1 |, |R2 |, |R3 |, |R4 |, |R5 | ≤ N 3 and |R6 | ≤ N 2 . From (59), the
entropic bound for the disjunctive datalog rule P above is upper-bounded by
LogSizeBoundΓ∗ ∩HCC (P ) =
5

max
∗

min{h(AB), h(AXY ), h(BXY ), h(AC), h(XC), h(Y C)}

h∈Γ5 ∩HCC


1
h(AB) + 4h(AXY ) + h(BXY ) + h(AC) + 2h(XC) + 2h(Y C)
h∈Γ5 ∩HCC 11

1
3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY ) + 5h(C)
≤ max
∗
h∈Γ5 ∩HCC 11

1
11 log N 3 + 5 log N 2
≤
11
43
=
log N.
(60)
11

≤

max
∗

On the other hand, consider the polymatroid ĥ = log N · h, where h is the polymatroid shown in Fig. 5.
(This is the same ĥ as in the proof of Theorem 1.3.) It is easy to check that ĥ satisfies all the cardinality constraints, and ĥ(AB) = ĥ(AXY ) = ĥ(BXY ) = ĥ(AC) = ĥ(XC) = ĥ(Y C) = 4 log N. Hence,
LogSizeBoundΓ5 ∩HCC (P ) ≥ 4 log N > 43
11 log N .
Next, we prove the stronger statement by using the fact that inequality (59) holds for any entropic function
h on 5 variables {A, B, X, Y, C}. Now, consider an entropic function h on 8 variables A′ , B ′ , X ′ , Y ′ , A, B, X, Y ;
then the restriction of h on the 5-variable sets {A′ , B ′ , X ′ , Y ′ , A}, {A′ , B ′ , X ′ , Y ′ , X}, and {A′ , B ′ , X ′ , Y ′ , Y }
all satisfy (59). In particular, we have the following inequalities:
h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ A) + 2h(X ′ A) + 2h(Y ′ A)
≤

3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ) + 5h(A),
h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ X) + 2h(X ′ X) + 2h(Y ′ X)

(61)

≤

3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ) + 5h(X),
h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ Y ) + 2h(X ′ Y ) + 2h(Y ′ Y )

(62)

≤

3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ) + 5h(Y ).

(63)

Add 5× inequality (51) with 1× inequality (61), 2× inequality (62), and 2× inequality (63), we obtain the

26

following non-Shannon inequality:


5 h(AB) + 4h(AXY ) + h(BXY )


+ h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ A) + 2h(X ′ A) + 2h(Y ′ A)


+ 2 h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ X) + 2h(X ′ X) + 2h(Y ′ X)


+ 2 h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ ) + h(A′ Y ) + 2h(X ′ Y ) + 2h(Y ′ Y )


≤ 5 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY )


+ 3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ))


+ 2 3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ )


+ 2 3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ) .
The inequality simplifies to


5 h(AB) + 4h(AXY ) + h(BXY ) + h(A′ B ′ ) + 4h(A′ X ′ Y ′ ) + h(B ′ X ′ Y ′ )
+ h(A′ A) + 2h(X ′ A) + 2h(Y ′ A)
+ 2h(A′ X) + 4h(X ′ X) + 4h(Y ′ X)
+ 2h(A′ Y ) + 4h(X ′ Y ) + 4h(Y ′ Y )


≤ 5 3h(XY ) + 3h(AX) + 3h(AY ) + h(BX) + h(BY )+


3h(X ′ Y ′ ) + 3h(A′ X ′ ) + 3h(A′ Y ′ ) + h(B ′ X ′ ) + h(B ′ Y ′ ) (64)

Now, consider the disjunctive datalog rule P :

T1 (AB) ∨ T2 (AXY ) ∨ T3 (BXY ) ∨ T4 (A′ B ′ ) ∨ T5 (A′ X ′ Y ′ ) ∨ T6 (B ′ X ′ Y ′ )
∨ T7 (A′ A) ∨ T8 (X ′ A) ∨ T9 (Y ′ A)
∨ T10 (A′ X) ∨ T11 (X ′ X) ∨ T12 (Y ′ X)

∨ T13 (A′ Y ) ∨ T14 (X ′ Y ) ∨ T15 (Y ′ Y )
← R1 (XY ) ∧ R2 (AX) ∧ R3 (AY ) ∧ R4 (BX) ∧ R5 (BY )

∧ R6 (X ′ Y ′ ) ∧ R7 (A′ X ′ ) ∧ R8 (A′ Y ′ ) ∧ R9 (B ′ X ′ ) ∧ R10 (B ′ Y ′ ), (65)

with a uniform cardinality bound |Ri | ≤ N 3 for all i ∈ [10]. Using the same averaging trick we used in (60),
from inequality (64) we get:

330
110
log N 3 =
log N < 4 log N.
85
85
On the other hand, consider the function h shown in Figure 6. This is a set function on 8 variables
{A, B, X, Y, A′ , B ′ , X ′ , Y ′ }, where for any set whose (green) value is not shown, h takes on the same value as
the smallest set in the figure containing it. It is easy to check that this is a polymatroid, and the polymatroid
ĥ = log N · h satisfies all input cardinality constraints; furthermore, ĥ(AB) = ĥ(AXY ) = · · · = ĥ(Y ′ Y ) =
4 log N . Hence, LogSizeBoundΓ8 ∩HCC (P ) ≥ 4 log N .
LogSizeBoundΓ∗ ∩HCC (P ) ≤
8

5

Shannon flow inequalities

The PANDA algorithm is built on the notion of a “proof sequence” for a class of Shannon-type inequalities
called the Shannon flow inequalities.
Definition 5.1. Let B ⊆ 2[n] denote a collection of subsets of [n]. Let C ⊆ 2[n] × 2[n] denote a collection of
C
pairs (X, Y ) such that ∅ 6= X ⊂ Y ⊆ [n]. Let λB = (λF )F ∈B ∈ QB
+ and δ C = (δY |X )(X,Y )∈C ∈ Q+ denote two
9
vectors of non-negative rationals. For any polymatroid h, let h(Y |X) denote h(Y ) − h(X). If the following
9 The

quantity h(Y |X) is the polymatroid-analog of the conditional entropy H[Y |X] = H[Y ] − H[X].

27

4 ABXY A′ B ′ X ′ Y ′

3 AX

2X

3 BX

3 XY

2A

3 AY

2B

3 A′ X ′

3 BY

3 B′X ′

2 X′

2Y

3 X ′Y ′

2 A′

3 A′ Y ′

2 B′

3 B′Y ′

2Y′

0∅
Figure 6: Another polymatroid h (shown in green).
inequality

X

B∈B

λB · h(B) ≤

X

(X,Y )∈C

def

δY |X · h(Y |X) =

X

(X,Y )∈C

δY |X · (h(Y ) − h(X))

(66)

holds for all h ∈ Γn (i.e. for all polymatroids), then it is called a Shannon flow inequality. The set B is called
the set of targets of the flow inequality.
For a simple illustration, the following shows a Shannon-flow inequality that we proved in Example 1.6:
h(A1 A2 A3 ) + h(A2 A3 A4 ) ≤ h(A1 A2 ) + h(A2 A3 ) + h(A3 A4 )
Section 5.1 motivates the study of these inequalities. Section 5.2 explains why they are called “flow” inequalities.

5.1

Motivations

Fix a disjunctive datalog rule P of the form (4) with degree constraints DC. Abusing notations, we write
(X, Y ) ∈ DC whenever (X, Y, NY |X ) ∈ DC. In particular the set DC can play the role of the generic set C
in the definition of Shannon flow inequality. To explain where the Shannon flow inequalities come from, we
study the (log) polymatroid bound (9) for P , which was defined by (7) with F chosen to be Γn ∩ HDC. The
bound LogSizeBoundΓn ∩HDC (P ) is the optimal objective value of the following optimization problem:
max
such that

min h(B)

(67)

B∈B

h(Y ) − h(X) ≤ nY |X ,
h(I ∪ J|J) − h(I|I ∩ J) ≤ 0,
h(X) − h(Y ) ≤ 0,
h(Z) ≥ 0,
def

(X, Y, NY |X ) ∈ DC
I⊥J
∅=
6 X ⊂ Y ⊆ [n]
∅=
6 Z ⊆ [n].

(Recall that implicitly we have h(∅) = 0, and that nY |X = log2 NY |X .) Here, I ⊥ J means I 6⊆ J and J 6⊆ I.
The optimization problem above is not easy to handle. Lemma 5.2 below shows that we can reformulate the
above maximin optimization problem into a linear program:

28

Lemma 5.2. There exists a non-negative vector λ = (λB )B∈B , with kλk1 = 1, such that
X
λB · h(B).
LogSizeBoundΓn ∩HDC (P ) = max
h∈Γn ∩HDC

(68)

B∈B

Instead of proving 5.2 directly, we prove a slightly more general lemma:
be a matrix with
Lemma 5.3 (A generalization of Lemma 5.2). Let A ∈ Qℓ×m , b ∈ Rℓ , and C ∈ Qm×p
+
columns c1 , . . . , cp . Consider the following maximin optimization problem:
max{min c⊤
k x | Ax ≤ b, x ≥ 0}

(69)

k∈[p]

If problem (69)’s objective value is positive and bounded, then there exists a vector λ ∈ Qp+ satisfying the
following conditions:
(a) kλk1 = 1.
(b) The problem (69) has the same optimal objective value as the following linear program:
max{(Cλ)⊤ x | Ax ≤ b, x ≥ 0}

(70)

Proof. Let 1p ∈ Rp be the all-1 vector. We first reformulate problem (69) with an equivalent LP:
max{w | Ax ≤ b, 1p w − C⊤ x ≤ 0,
The dual of (71) is
∗

∗

∗

∗

min{b⊤ y | A⊤ y ≥ Cz, 1⊤
p z ≥ 1,

x ≥ 0, w ≥ 0}

(71)

y ≥ 0, z ≥ 0}

(72)

Let (w , x ) and (z , y ) be a pair of primal-optimal and dual-optimal solutions to (71) and (72) respectively.
∗
∗
⊤ ∗ ⊤ ∗
Due to complementary slackness of the (71) and (72) pair, w∗ > 0 implies 1⊤
p z = 1 and (1p w −C x ) z =
∗
∗
0. We know w > 0 because problem (69) has a positive optimal value. If follows that kz k1 = 1, and
w∗ = (C⊤ x∗ )⊤ z∗ .
Next, we show λ = z∗ satisfies (a) and (b). Condition (a) follows from kz∗ k1 = 1. To show (b), note that
∗
x is a feasible solution to (70) with objective value (Cλ)⊤ x∗ = (Cz∗ )⊤ x∗ = (C⊤ x∗ )⊤ z∗ = w∗ . Furthermore,
for any x feasible to (70), we have (Cλ)⊤ x = (Cz∗ )⊤ x ≤ (A⊤ y∗ )⊤ x = (Ax)⊤ y∗ ≤ b⊤ y∗ = w∗ .
Along with Farkas lemma, the linear program (LP) on the right hand side of (68) gives rise to Shannon
flow inequalities. We first need the dual LP of (68). Associate a dual variable δY |X to each degree constraint,
a variable σI,J to each submodularity constraint, and a variable µX,Y to each monotonicity constraint. The
dual of the RHS of (68) is
X
nY |X · δY |X
(73)
min
(X,Y )∈DC

inflow(B) ≥ λB ,
inflow(Z) ≥ 0,

such that

∀B ∈ B
∅=
6 Z ⊆ [n].

(δ, σ, µ) ≥ 0.

def

(recall that nY |X = log2 NY |X ), where for any ∅ 6= Z ∈ 2[n] , inflow(Z) is defined by
def

inflow(Z) =

X

X:(X,Z)∈DC

δZ|X −

X

X

δY |Z +

σI,J

I⊥J
I∩J=Z

Y :(Z,Y )∈DC

+

X

I⊥J
I∪J=Z

σI,J −

29

X

J:J⊥Z

σZ,J −

X

X:X⊂Z

µX,Z +

X

Y :Z⊂Y

µZ,Y . (74)

I ∪J

Y

Y
Z ∪J

I
+µZ,Y

−δY |Z

+σI,J
J

I ∩ J = I′ ∪ J′ = Z

X ⊂Z ⊂Y

Z

Z

−σZ,J

J

J′
+σI ′ ,J ′

+δZ|X

−µX,Z

I′
I′ ∩ J′

X

Z ∩J

X

Figure 7: Contributions of coefficients to inflow(Z)
Again, recall that I ⊥ J means I 6⊆ J and J 6⊆ I. Note that the function inflow : 2[n] → Q+ is also a
function of the dual variables (δ, σ, µ). However, we do not explicitly write down this dependency to avoid
heavy-loading notations. Figure 7 illustrates the contributions of various coefficients to inflow(Z) for a given
set Z. It is helpful in the rest of the paper to keep this picture in mind when we reason about balancing the
inflow (in)equalities.
Let h∗ = P
(h∗Z )Z⊆[n] denote anP
optimal solution to (68), and let (δ ∗ , σ ∗ , µ∗ ) denote an optimal solution
∗
to (73), then B∈B λB · h (B) = (X,Y )∈DC δY∗ |X · nY |X , by strong duality. In particular, instead of solving
for the primal optimal solution h∗ , we can look for the dual optimal solution (δ ∗ , σ ∗ , µ∗ ). One way to
characterize any dual feasible solution (δ, σ, µ), is to use Farkas’ lemma [44], which in our context takes the
following form.
Proposition 5.4. Given non-negative vectors λB and δ DC , the inequality
X
X
δY |X · h(Y |X)
λB · h(B) ≤
B∈B

(75)

(X,Y )∈DC

is a Shannon flow inequality if and only if there exist σ and µ such that (δ, σ, µ) is feasible to the dual
LP (73).
Proof. There are many variants of Farkas’ lemma [44]. We use a version whose proof we also reproduce here
because the proof is very short.
Let A ∈ Rm×n be a matrix and c ∈ Rn be a vector. Let P = {x | Ax ≤ 0, x ≥ 0} be a polyhedron and
D = {y | A⊤ y ≥ c, y ≥ 0} be the dual polyhedron. Then, a variant of Farkas’ lemma states that D is nonempty if and only if there is no x ∈ P such that c⊤ x > 0. To see this, note that the system {c⊤ x > 0, x ∈ P }
is infeasible iff max{c⊤ x | x ∈ P } = 0, which by strong duality is equivalent to min{0⊤ y | y ∈ D} is feasible,
which is the same as D is non-empty.
Now, to see why the above variant of Farkas’ lemma implies Proposition 5.4, we note that (75) holds for
all polymatroids iff {(λB − δ DC )⊤ h > 0 | h ∈ Γn } is infeasible; now we are in the exact setting of the above
variant of Farkas’ lemma and the rest follows trivially.
Note that inequality (75) holds when δ = δ ∗ , in which case the Shannon flow inequality implies the upper
bound
X
X
δY∗ |X · nY |X ,
λB · h(B) ≤
B∈B

(X,Y )∈DC

where the right-hand side is the optimal objective value of both the primal and the dual.

30

5.2

Proof sequences

A key observation from our prior work [3] was that we can turn a proof of a special case of inequality (75)
into an algorithm. The proof has to be performed in a sequential manner; and this brings us to the concept
of a proof sequence. In this paper, we refine the proof sequence notion from [3] in four significant ways. First,
the definition of the proof sequence is different, allowing for a simpler algorithm (PANDA) than CSMA in [3].
Second, in [3] we left open whether proof sequences are a complete proof system, even for special Shannonflow inequalities; the CSMA algorithm used a specific workaround to achieve optimality even without proving
completeness of proof sequences. Our most important contribution here is to prove completeness of our new
proof sequence. Third, we are able to bound the length of the proof sequence to be polynomial in the size of
the linear program (73), as opposed to the doubly exponential length in [3]. Fourth, new technical ideas are
introduced so that we can construct proof sequences for the much more general Shannon flow inequality (75)
(as opposed to the special case of “output inequality” in [3], whose form is given in (101)).
Definition 5.5 (Conditional polymatroids). Let P ⊆ 2[n] × 2[n] denote the set of all pairs (X, Y ) such
that ∅ ⊆ X ⊂ Y ⊆ [n]. A vector f ∈ RP
+ has coordinates indexed by pairs (X, Y ) ∈ P. We denote the
corresponding coordinate value of f by f (Y |X). The vector f is called a conditional polymatroid iff there
exists a polymatroid h such that f (Y |X) = h(Y ) − h(X); and, we say h defines the conditional polymatroid
f . Abusing notation somewhat, the conditional polymatroid defined by the polymatroid h is denoted by
h. In particular, h = (h(Y |X))(X,Y )∈P . If h is a polymatroid then h(∅) = 0, in which case we write h(Y )
instead of h(Y |∅).
To formally define the notion of a proof sequence, we rewrite the Shannon flow inequality (66) as an
B
C
inequality on conditional polymatroids in the QP
+ space. We extend the vectors λB ∈ Q+ and δ C ∈ Q+ to
P
become vectors λ, δ in the Q+ space in the obvious way:
(
λB (B) when Y = B, X = ∅
def
λ(Y |X) =
0
otherwise.
(
δC (Y |X) when (X, Y ) ∈ C
def
δ(Y |X) =
0
otherwise.
Then, inequality (66) can be written simply as hλ, hi ≤ hδ, hi. Note the crucial fact that, even though
λ ∈ QP
+ , for it to be part of a Shannon flow inequality only the entries λB|∅ can be positive. We will often
write λB instead of λB|∅ . These assumptions are implicit henceforth. Proposition 5.4 can now be written
simply as:
Proposition 5.6. Given any λ, δ ∈ QP
+ , where λY |X > 0 implies X = ∅, the inequality hλ, hi ≤ hδ, hi is a
Shannon flow inequality if and only if there exist σ and µ such that (δ, σ, µ) satisfy the constraints
inflow(Z) ≥ λZ , ∀∅ =
6 Z ⊆ [n] and (δ, σ, µ) ≥ 0
Note that the following set is a polyhedron and it is independent of the values nY |X :

(δ, σ, µ) | inflow(Z) ≥ λZ , ∀∅ 6= Z ⊆ [n] and (δ, σ, µ) ≥ 0 .
The conditional polymatroids satisfy four basic linear inequalities:

h(I ∪ J|J) − h(I|I ∩ J) ≤ 0, I ⊥ J (submodularity)

−h(Y |∅) + h(X|∅) ≤ 0, X ⊂ Y (monotonicity)
h(Y |∅) − h(Y |X) − h(X|∅) ≤ 0, X ⊂ Y (composition)

−h(Y |∅) + h(Y |X) + h(X|∅) ≤ 0, X ⊂ Y (decomposition)
31

(76)

P
For every I ⊥ J, define a vector sI,J ∈ QP
+ , and for every X ⊂ Y , define three vectors mX,Y , cX,Y , dY,X ∈ Q+
such that the linear inequalities above can be written correspondingly in dot-product form:

hsI,J , hi ≤
hmX,Y , hi ≤

hcX,Y , hi ≤
hdY,X , hi ≤

0, I ⊥ J (submodularity)
0, X ⊂ Y (monotonicity)

0, X ⊂ Y (composition)
0, X ⊂ Y (decomposition)

(77)
(78)
(79)
(80)

Definition 5.7 (Proof sequence). A proof sequence of a Shannon flow inequality hλ, hi ≤ hδ, hi, is a sequence
(w1 f1 , . . . , wℓ fℓ ) satisfying the following:
(1) fi ∈ { sI,J , mX,Y , cX,Y , dY,X } for all i ∈ [ℓ]. The fi are called proof steps.
(2) wi ∈ R+ , i ∈ [ℓ] are the corresponding weights of the proof steps.
def

(3) All the vectors δ 0 = δ, δ 1 , . . . , δ ℓ defined by δ i = δ i−1 + wi · fi , i ∈ [ℓ] are non-negative.
(4) Furthermore, δ ℓ ≥ λ (component-wise comparisons).
Due to the linear inequalities (77)–(80) above, if (w1 f1 , · · · , wℓ fℓ ) is a proof sequence for the Shannon
flow inequality hλ, hi ≤ hδ, hi, then
hδ, hi = hδ 0 , hi ≥ hδ 1 , hi ≥ · · · hδ ℓ , hi ≥ hλ, hi.
The proof step sI,J is called a submodularity step, mX,Y a monotonicity step, dY,X a decomposition step,
and cX,Y a composition step.
Definition 5.8 (Witness). Let hλ, hi ≤ hδ, hi be a Shannon flow inequality. From Prop. 5.4 there exists
(σ, µ) such that (δ, σ, µ) belongs to the polyhedron (76). We call (σ, µ) a witness for the Shannon flow
inequality.
We next show one way to construct a proof sequence for any given Shannon flow inequality. (See
Appendix B for more advanced constructions of shorter proof sequences.)
Theorem 5.9 (Constructing a proof sequence). Let hλ, hi ≤ hδ, hi be a Shannon flow inequality with witness
(σ, µ). There exists a proof sequence for the inequality hλ, hi ≤ hδ, hi with length at most D(3kσk1 + kδk1 +
kµk1 ), where D is the minimum common denominator of all entries in (λ, δ, σ, µ).
Proof. We induct on the quantity
def

ℓ(λ, δ, σ, µ) = D (kλk1 + 2kσk1 + kδk1 + kµk1 ) ,
which is an integer. The base case is when kλk1 = 0, which is trivial because the inequality has a proof
sequence of length 0. In the inductive step, assume kλk1 > 0, meaning there must be some B ⊆ [n] for
which λB > 0. We will produce a Shannon flow inequality hλ′ , hi ≤ hδ ′ , hi witnessed by (σ ′ , µ′ ) such that
ℓ(λ′ , δ ′ , σ′ , µ′ ) < ℓ(λ, δ, σ, µ), and D is a common denominator of the entries in (λ′ , δ ′ , σ ′ , µ′ ). From the
induction hypothesis we obtain a proof sequence ProofSeq′ for hλ′ , hi ≤ hδ ′ , hi. Finally the proof sequence
ProofSeq for hλ, hi ≤ hδ, hi is constructed from ProofSeq′ by appending to the beginning one or two proof
steps.
P
From Prop. 5.6, we know ∅6=W ⊆[n] inflow(W ) ≥ λB > 0. Consequently, there must exist Z 6= ∅ for
which δZ|∅ > 0, because all the variables δY |X with X 6= ∅, σI,J , and µX,Y contribute a non-positive amount
P
def
to the sum ∅6=W ⊆[n] inflow(W ). Let w = 1/D, and fix an arbitrary Z 6= ∅ where δZ|∅ > 0. We initially set
′
′
(λ , δ , σ ′ , µ′ ) = (λ, δ, σ, µ); then we modify (λ′ , δ ′ , σ′ , µ′ ) slightly depending on the cases below.
′
Case (a): λZ > 0. Reduce both λ′Z and δZ|∅
by w. From Prop. 5.6, we can verify that hλ′ , hi ≤ hδ ′ , hi
is a Shannon flow inequality witnessed by (σ ′ , µ′ ) = (σ, µ). By induction hypothesis, hλ′ , hi ≤ hδ ′ , hi has a
32

proof sequence ProofSeq′ of length at most D(3kσk1 + kδ ′ k1 + kµk1 ). Furthermore, the ProofSeq′ is also a
proof sequence for hλ, hi ≤ hδ, hi.
′
Case (b): λZ = 0 and inflow(Z) > 0. Reduce δZ|∅
by w. Then, from Prop. 5.6, we can verify that
′
hλ, hi ≤ hδ , hi is a Shannon flow inequality witnessed by (σ, µ). The inductive step is now identical to that
of Case (a).
Case (c): λZ = 0 and inflow(Z) = 0. Since δZ|∅ > 0, there must be some dual variable that is contributing
a negative amount to inflow(Z) (See Figure 7 [right]). In particular, one of the following three cases must
hold:
(1) There is some X ⊂ Z such that µX,Z ≥ w. Define δ ′ = δ + w · mX,Z and reduce µ′X,Z by w.
Note that kδ ′ k1 = kδk1 , kµ′ k1 = kµk1 − w, and hλ, hi ≤ hδ ′ , hi is a Shannon flow inequality. witnessed
by (σ, µ′ ). By induction hypothesis, hλ, hi ≤ hδ ′ , hi has a proof sequence ProofSeq′ of length at most
D(3kσk1 + kδ ′ k1 + kµ′ k1 ). It follows that ProofSeq = (w · mX,Z , ProofSeq′ ) is a proof sequence for hλ, hi ≤
hδ, hi of length at most D(3kσk1 + kδk1 + kµk1 ).
(2) There is some Y ⊃ Z such that δY |Z ≥ w. Define δ ′ = δ + w · cZ,Y . Note that kδ ′ k1 = kδk1 − w
and hλ, hi ≤ hδ ′ , hi is a Shannon flow inequality witnessed by (σ, µ). From the proof sequence ProofSeq′
for hλ, hi ≤ hδ ′ , hi we obtain the proof sequence ProofSeq = (w · cZ,Y , ProofSeq′ ) for hλ, hi ≤ hδ, hi of the
desired length.
′
(3) There is some J ⊥ Z such that σZ,J ≥ w. Define δ ′ = δ + w · dZ,Z∩J + w · sZ,J , and reduce σZ,J
′
′
′
by w. In this case, kδ k1 = kδk1 + w, kσ k1 = kσk1 − w, and hλ, hi ≤ hδ , hi is a Shannon flow inequality
witnessed by (σ ′ , µ). By induction hypothesis, hλ, hi ≤ hδ ′ , hi has a proof sequence ProofSeq′ of length
at most D(3kσ′ k1 + kδ ′ k1 + kµk1 ). It follows that ProofSeq = (w · dZ,Z∩J , w · sZ,J , ProofSeq′ ) is a proof
sequence for hλ, hi ≤ hδ, hi of length at most D(3kσk1 + kδk1 + kµk1 ).
Appendix B.1 presents bounds on kσk1 , kδk1 and kµk1 . By plugging those bounds into Theorem 5.9,
we can bound the length of the constructed proof sequence by D(3kσk1 + kδk1 + kµk1 ) ≤ D · ( 32 n3 + n).
(See Corollaries B.6 and B.7.) Appendix B.2 present an alternative construction of a proof sequence with
an even smaller length bound.
The PANDA algorithm needs another technical lemma, which we state below along with some prerequisite
concepts.
Definition 5.10 (Tight witness). A witness is said to be tight if inflow(Z) = λZ for all Z.
We remark that, if inflow(Z) > λZ , we can always increase µ∅,Z by the amount inflow(Z) − λZ so that
inflow(Z) = λZ . In particular, it is easy to turn any witness into a tight witness. The proof of Lemma 5.11
below follows the same strategy as in the proof of Theorem 5.9, but with some subtle differences.
Lemma 5.11 (Truncating a Shannon flow inequality). Let hλ, hi ≤ hδ, hi be a Shannon flow inequality
def
with witness (σ, µ). Let D be a common denominator of all entries in (λ, δ, σ, µ), and w = 1/D. Suppose
kλk1 > 0 and δY |∅ > 0. Then, there are vectors (λ′ , δ ′ , σ ′ , µ′ ) satisfying the following conditions:
(a) hλ′ , hi ≤ hδ ′ , hi is a Shannon flow inequality (with witness (σ ′ , µ′ )).
(b) λ′ ≤ λ and δ ′ ≤ δ (component-wise comparisons).
(c) kλ′ k1 ≥ kλk1 − w and δY′ |∅ ≤ δY |∅ − w.
(d) D is a common denominator of all entries in the vector (λ′ , δ ′ , σ ′ , µ′ ).
(e) D(3kσ′ k1 + kδ ′ k1 + kµ′ k1 ) ≤ D(3kσk1 + kδk1 + kµk1 ) − 1.
Proof. W.L.O.G. we can assume that (σ, µ) is a tight witness. Construct (λ′ , δ ′ , σ ′ , µ′ ) from (λ, δ, σ, µ) as
follows. Initially set (λ′ , δ ′ , σ′ , µ′ ) = (λ, δ, σ, µ). Let inflow′ (Z) denote the quantity inflow(Z) measured on
the vector (λ′ , δ ′ , σ ′ , µ′ ). Due to tightness of the witness, at this point inflow′ (Z) − λ′Z = 0 for every Z.
33

′
′
Now, we start disturbing the flow balance equations starting from Z = Y by setting δZ|∅
= δZ|∅
−w
′
′
′
which means inflow (Z) was reduced by w. Note that Z is the only point for which inflow (Z) − λZ 6= 0 (it
is negative). If λ′Z > 0, then we simply reduce λ′Z by w and terminate. If λ′Z = 0, then either (1) there is
some X ⊂ Z such that µ′X,Z ≥ w, (2) there is some Y ⊃ Z such that δY′ |Z ≥ w, or (3) there is some J ⊥ Z
′
such that σZ,J
≥ w. Cases (1) and (2) are handled in a similar way to the proof of Theorem 5.9 while case
(3) is handled differently. In particular, if (1) holds, then we reduce µ′X,Z by w and set Z = X. If (2) holds,
′
then we reduce δY′ |Z by w and set Z = Y . If (3) holds, then we reduce σZ,J
by w, increase µ′Z∩J,J by w,
and set Z = Z ∪ J. In all three cases, (the new) Z is the only point where inflow′ (Z) − λ′Z has a deficit, and
the process continues if the new Z is not ∅.
The above process terminates because every time we move Z to a new deficit point, the quantity 2kσ′ k1 +
kδ ′ k1 + kµ′ k1 is reduced by w. When the process terminates, all quantities inflow′ (Z) − λ′Z = 0 and thus
hλ′ , hi ≤ hδ ′ , hi is a Shannon flow inequality witnessed by (σ ′ , µ′ ) by Proposition 5.6. Property (b) holds
because we never increase the λ′ and δ ′ entries. Property (c) holds because we started the process by
reducing δY′ |∅ and the process terminates as soon as some λ′Z is reduced by w. Property (d) hold trivially.
Property (e) holds because kδ ′ k1 < kδk1 and the quantity 3kσ′ k1 + kµ′ k1 never increases in the above
process.

6

The PANDA algorithm

This section presents an algorithm called PANDA that computes a model of a disjunctive datalog rule P in
time predicted by its polymatroid bound (9):
Õ(N + poly(log N ) · 2LogSizeBoundΓn ∩HDC (P ) ).
(Recall N was defined in (27).) The principle in PANDA is the following: start by providing a proof sequence
for a Shannon flow inequality, then interpret each step of the proof sequence as a relational operation on the
query’s input relations. The main result of this section is Theorem 1.7, whose proof is in Section 6.2.

6.1

The algorithm

A simple demonstration of the algorithm was given in Example 1.8. The algorithm sketch is shown in the
box Algorithm 1. In general, PANDA takes as input the collection of input relations R, the degree constraints
DC, a Shannon flow inequality and its proof sequence. The Shannon flow inequality is constructed by solving
the optimization problem (7) with F = Γn ∩ HDC:
def

LogSizeBoundΓn ∩HDC (P ) =

max

min h(B).

h∈Γn ∩HDC B∈B

(81)

From Lemma 5.2, we can find a vector λB with kλk1 = 1 such that the problem has the same optimal
objective value as the linear program maxh∈Γn ∩HDC hλ, hi. (Recall from Section 5.2 that, when we extend
λB to the (conditional polymatroid) space λ ∈ QP
+ , only the entries λB|∅ for B ∈ B can be positive.) Let
(δ, σ, µ) denote an optimal dual solution to this LP, then by strong duality
X
nY |X · δY |X = LogSizeBoundΓn ∩HDC (P )
(82)
(X,Y )∈DC

Moreover, from Proposition 5.6 we know hλ, hi ≤ hδ, hi is a Shannon flow inequality. From Theorem 5.9,
we obtain a proof sequence for the Shannon flow inequality.
For brevity, let the constant OBJ denote our budget of LogSizeBoundΓn ∩HDC (P ):
def

OBJ = LogSizeBoundΓn ∩HDC (P ).

34

(83)

Algorithm 1 PANDA(R, DC, (λ, δ), ProofSeq)
Input:
Input:
Input:
Input:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

hλ, hi ≤ hδ, hi is a Shannon flow inequality with proof sequence ProofSeq, 0 < kλk1 ≤ 1
DC are input degree constraints guarded by input relations R
The degree-support invariant (invariant (1)) is satisfied
Invariant (4) is satisfied

If an input relation R ∈ R has attribute set AB , with B ∈ B then
Return TB = R
⊲ Only one table in the output
′
Let ProofSeq = (w · f , ProofSeq )
⊲ f is the first proof step, with weight w
δ′ ← δ + w · f
⊲ Advance the proof step
If f = sI,J then
⊲ Case 1. δI|I∩J ≥ w > 0 must hold
Return PANDA(R, DC, (λ, δ ′ ), ProofSeq′ )
else If f = mX,Y then
⊲ Case 2. δY |∅ ≥ w > 0 must hold
Let R be a guard for (∅, Y, NY |∅ ) ∈ DC, which supports δY |∅
R′ = R ∪ {ΠX (R)}
def

DC′ = DC ∪ {(∅, X, NX|∅ = |ΠX (R)|)}
Return PANDA(R′ , DC′ , (λ, δ ′ ), ProofSeq′ )
else If f = dY,X then
Let R ∈ R be a guard for (∅, Y, NY |∅ ) ∈ DC
Partition R = R(1) ∪ · · · ∪ R(k) as in (86)
For j ← 1 to k do
R(j) ← R ∪ {R(j) }

(j)
(j)
DC(j) = DC ∪ (∅, X, NX|∅ ), (X, Y, NY |X )

⊲ Case 3. δY |∅ ≥ w > 0 must hold
⊲ k=O(log2 |R|) branches

(j)

(TB )B∈B ← PANDA(R(j) , DC(j) , (λ, δ ′ ), ProofSeq′ )
def Sk
(j)
Return TB = j=1 TB
B∈B

⊲ Union of results from branches

else If f = cX,Y then
⊲ Case 4. δX|∅ ≥ w > 0 and δY |X ≥ w > 0
Let R be a guard of (∅, X, NX|∅ ) ∈ DC, which supports δX|∅
Let S be a guard of (Z, W, NW |Z ) ∈ DC, which supports δY |X
If NX|∅ · NW |Z ≤ 2OBJ then
⊲ Case 4a. OBJ defined in (83)
Compute T (AY ) ← ΠX (R) ✶ ΠW (S)
⊲ Within runtime Õ(2OBJ )
′
R = R ∪ {T }
def

DC′ = DC ∪ {(∅, Y, NY |∅ = |T |)}
Return PANDA(R′ , DC′ , (λ, δ ′ ), ProofSeq′ )
else
⊲ Case 4b.
Let hλ′ , hi ≤ hδ ′ , hi be the truncated Shannon flow inequality stated in Lemma 5.11
Recompute a fresh ProofSeq′ for hλ′ , hi ≤ hδ ′ , hi
Return PANDA(R, DC, (λ′ , δ ′ ), ProofSeq′ )

Throughout the algorithm, the collection of input relations R, the degree constraints DC, the Shannon
flow inequality hλ, hi ≤ hδ, hi, and the associated proof sequence will all be updated. However for inductive
purposes, the following invariants will always be maintained:
1. Degree-support invariant: For every δY |X > 0, there exist Z ⊆ X, W ⊆ Y such that W − Z = Y − X
and (Z, W, NW |Z ) ∈ DC. (Note that, if X = ∅ then W = Y and Z = ∅.) The degree constraint
(Z, W, NW |Z ) is said to support the positive δY |X . See Fig. 8 (a). (If there are multiple constraints
(Z, W, NW |Z ) supporting δY |X , then the one with the minimum NW |Z is said to be the constraint that
supports δY |X , where ties can be broken arbitrarily.)

35

I ∪J
′
δI∪J|J
>0

Y

I

J

δY |X > 0

X

I ∩J

W

W

(Z, W, NW |Z ) ∈ DC

(Z, W, NW |Z ) ∈ DC
Z

Z

(a) Degree-support invariant

(b) Case 1 of PANDA

Figure 8: Degree-support invariant and its usage
2. λ satisfies
0 < kλk1 ≤ 1.

(84)

3. The Shannon flow inequality along with the supporting degree constraints satisfy the following:
X
n(δY |X ) ≤ kλk1 · OBJ,
(85)
(X,Y )

where
def

n(δY |X ) =
def



δY |X · nW |Z



0

if δY |X > 0 and
(Z, W, NW |Z ) supports it
if δY |X = 0.

(Recall that nW |Z = log2 NW |Z .) We call the quantity

P

(X,Y )

n(δY |X ) the potential.

4. For every δY |∅ > 0, the supporting degree constraint (∅, Y, NY |∅ ) satisfies nY |∅ ≤ OBJ.
At the very beginning, invariants (1), (2) and (3) above are satisfied obviously. Less obviously, invariant
(4) is also satisfied at the beginning: We will assume so for now and prove later why this is the case.
A very high-level description of the algorithm is as follows. Recall from Definition 5.7 that a proof
sequence ProofSeq is a series of proof steps, which are used by PANDA as “symbolic instructions”. For each
instruction, PANDA does some computation, spawns a number of subproblem(s) all of which are disjunctive
datalog rules, and creates new (intermediate) relations to become input of the subproblems if necessary.
(i)
The output of the ith subproblem is a set of tables TB for B ∈ B. The overall output is the set of tables
S (i)
TB = i TB , B ∈ B; namely for each B ∈ B we take the union of the corresponding tables from the
subproblems’s outputs. The number of subproblems will be shown to be polylogarithmic in the input size.
We now walk the reader step-by-step through the algorithm. We will keep every step of the algorithm
to run within Õ(2OBJ ). Specifically, we will keep every intermediate relation the algorithm computes of size
≤ 2OBJ . In the base case, the algorithm stops as soon as there is a relation R ∈ R with attribute set AB where
B ∈ B, in which case R is a target relation. Otherwise, the algorithm takes steps which are modeled after
the proof steps. Let f be the first proof step (instruction) with weight w, i.e. ProofSeq = (w · f , ProofSeq′ )
where ProofSeq′ contains the rest of the instructions.
Case 1: f = sI,J is a submodularity step. By definition of proof sequence, δ + w · sI,J ≥ 0, and thus
δI|I∩J ≥ w > 0. Let (Z, W, NW |Z ) ∈ DC be the degree constraint supporting δI|I∩J ; then Z ⊆ I ∩ J, W ⊆ I,
36

′
and W − Z = I − I ∩ J. The algorithm proceeds by setting δ ′ = δ + w · sI,J . Note that δI∪J|J
is now positive,
and so it needs a supporting degree constraint. From the fact that W −Z = I −I ∩J = I ∪J −J, (Z, W, NW |Z )
′
can support δI∪J|J
(see Fig. 8 (b)). Since f was the next step in the proof sequence, hλ, hi ≤ hδ ′ , hi is a
P
Shannon flow inequality with proof sequence ProofSeq′ . Moreover, the potential (X,Y ) n(δY |X ) remains
unchanged because δI|I∩J was reduced by w, δI∪J|J was increased by w, and they have the same support.
Hence, invariant (85) remains satisfied.
Case 2: f = mX,Y is a monotonicity step. By definition of proof sequence, δ + w · mX,Y ≥ 0, and thus
δY |∅ ≥ w > 0. Let (∅, Y, NY |∅ ) ∈ DC be the degree constraint supporting δY |∅ , and R ∈ R be a guard for
this degree constraint (which implies |ΠY (R)| ≤ NY |∅ ; recall Definition 2.10). By invariant (4) above, we
′
have NY |∅ ≤ 2OBJ . We proceed by setting δ ′ = δ + w · mX,Y . Note that δX|∅
is positive, and so it needs
a supporting degree constraint, which is the newly added degree constraint (∅, X, NX|∅ ), guarded by R,
def

where NX|∅ = |ΠX (R)| ≤ |ΠY (R)| ≤ NY |∅ . Invariant (85) remains satisfied because we subtracted w · nY |∅
from the potential and added w · nX|∅ ≤ w · nY |∅ instead. Moreover invariant (4) remains satisfied because
NX|∅ ≤ NY |∅ ≤ 2OBJ .
Case 3: f = dY,X is a decomposition step with weight w. From δ + w · dY,X ≥ 0, it follows that
δY |∅ ≥ w > 0. From the guarantee that δY |∅ has a supporting degree constraint, it follows that there is a
relation R ∈ R guarding (∅, Y, NY |∅ ), which means |ΠY (R)| ≤ NY |∅ . By invariant (4), NY |∅ ≤ 2OBJ . We will
need the following lemma.
Lemma 6.1. Let X ⊂ Y ⊆ [n]. Let T (AY ) be a table with |T | ≤ NY |∅ . Then, T can be partitioned into at
(j)

(j)

most k = 2 log |T | sub-tables T (1) , . . . , T (k) such that NX|∅ · NY |X ≤ NY |∅ , for all j ∈ [k], where
NX|∅

def

(j)

def

(j)

NY |X

=

=

|ΠX (T (j) )|,
max

tX ∈ΠX (T (j) )

degT (j) (Y |tX ),

(where degT (j) (Y |tX ) was defined by (38) in Definition 2.10.)
Proof. To obtain the sub-tables T (j) , observe that the number of tuples tX ∈ ΠX (T ) with log-degree in the
interval [j, j + 1) is at most |T |/2j ≤ 2nY |∅ −j . Hence, if we partition T based on which of the buckets [j, j + 1)
(j)
(j)
the log-degree falls into, we would almost have the required inequality: nX|∅ + nY |X ≤ (nY |∅ − j) + (j + 1) =

nY |∅ + 1. To resolve the situation, we partition each T (j) into two tables whose projections onto X are
equal-sized. Overall, we need k = 2 log |T |.
def

By applying the above lemma on T (AY ) = ΠY (R), we show that R can be partitioned into at most
(j)
(j)
(k = 2 log2 |R| ≤ 2 · OBJ) sub-tables R(1) , . . . , R(k) such that NX|∅ · NY |X ≤ NY |∅ , for all j ∈ [k], where
NX|∅

def

(j)
NY |X

def

(j)

=

=

|ΠX (R(j) )|,
max

tX ∈ΠX (R(j) )

(86)
degR(j) (Y |tX ).

For each of these sub-tables R(j) of R, we create a subproblem with the same input tables but with R
replaced by R(j) . The jth subproblem has degree constraints DC(j) where

(j)
(j)
DC(j) = DC ∪ (∅, X, NX|∅), (X, Y, NY |X ) .

The table R(j) guards both of the new degree constraints. Set δ ′ = δ +w·dY,X . The jth subproblem is on the
Shannon flow inequality hλ, hi ≤ hδ ′ , hi with proof sequence ProofSeq′ . Moreover, invariant (85) still holds in
(j)
(j)
the jth subproblem because we subtracted w ·nY |∅ from the potential, and added w ·(nX|∅ + nY |X ) ≤ w ·nY |∅
(j)

to the potential. Invariant (4) holds because NX|∅ ≤ NY |∅ ≤ 2OBJ .
37

Case 4: f = cX,Y is a composition step with weight w. By definition of proof sequence, δ + w · cX,Y ≥ 0,
and thus δX|∅ ≥ w > 0 and δY |X ≥ w > 0. Because δX|∅ has a support, there must be an input relation R
for which |ΠX (R)| ≤ NX|∅ ; and because δY |X has a support, there must be two sets Z ⊆ X and W ⊆ Y
for which W − Z = Y − X and (Z, W, NW |Z ) ∈ DC which is guarded by an input relation S. Note that
X ∪ (W − Z) = X ∪ (Y − X) = Y . We consider two cases:
def
(Case 4a) If NX|∅ · NW |Z ≤ 2OBJ , then we can compute the table T (AY ) = ΠX (R) ✶ ΠW (S) by going
over all tuples in ΠX (R) and expanding them using matching tuples in ΠW (S). The runtime of the join is
Õ(NX|∅ · NW |Z ) = Õ(2OBJ ), and the size of T is ≤ NX|∅ · NW |Z ≤ 2OBJ . The Shannon flow inequality is
modified by setting δ ′ = δ + w · cX,Y , with the proof sequence ProofSeq′ , and the set of degree constraints
def

is extended by adding the constraint (∅, Y, NY |∅ = |T |), guarded by T . Moreover, invariant (85) still holds
because we subtracted w · (nX|∅ + nW |Z ) and added at most the same amount to the potential. Invariant
(4) holds because |T | ≤ 2OBJ .
(Case 4b) If NX|∅ · NW |Z > 2OBJ , then we will not perform this join. Instead, we restart the subproblem
with a fresh inequality. In particular, set δ = δ + w · cX,Y . Now we have δY |∅ ≥ w. We restart the problem
with the inequality hλ′ , hi ≤ hδ ′ , hi satisfying the conditions stated in Lemma 5.11. Since δ ′ ≤ δ and
δY′ |∅ ≤ δY |∅ − w, the potential is reduced by at least w · (nX|∅ + nW |Z ) > w · OBJ. Since kλ′ k1 ≥ kλk1 − w,
the
side of (85) was reduced by at most w · OBJ, hence invariant (85) still holds. Moreover, let
P right-hand
′
n(δ
)
(X,Y )
Y |X be the new potential. Now we have
X
X
n(δY |X ) − w · OBJ ≤ (kλk1 − w) · OBJ ≤ kλ′ k1 · OBJ.
n(δY′ |X ) <
0≤
(X,Y )

(X,Y )

This proves kλ′ k1 > 0. And because λ′ ≤ λ, we have kλ′ k1 ≤ kλk1 ≤ 1. Hence, invariant (84) holds.
Invariant (4) holds because δ ′ ≤ δ.
Finally, we get back to our earlier assumption that invariant (4) was initially satisfied.
Proposition 6.2. Invariant (4) is satisfied at the beginning of the PANDA algorithm.
Proof. If initially there was some δY |∅ with nY |∅ > OBJ, then we could have replaced the original Shannonflow inequality and witness with the inequality hλ′ , hi ≤ hδ ′ , hi along with the witness (σ ′P
, µ′ ) satisfying the
′
conditions of Lemma 5.11. Similar to Case 4b above, we conclude that kλ k1 > 0 and (X,Y ) n(δY′ |X ) <
kλ′ k1 · OBJ. But this is a contradiction, because
OBJ =
≤

max

min h(B)

h∈Γn ∩HDC B∈B

X λ′
B
h(B)
′
h∈Γn ∩HDC
kλ
k1
B∈B
max

1
kλ′ k1
1
≤
kλ′ k1
1
=
kλ′ k1

=

max

hλ′ , hi

max

hδ ′ , hi

h∈Γn ∩HDC

h∈Γn ∩HDC

max

h∈Γn ∩HDC

≤

1
kλ′ k1

(X,Y )∈DC

=

1
kλ′ k1

X

< OBJ.

X

X

(X,Y )∈DC

δY′ |X nY |X
n(δY′ |X )

(X,Y )∈DC

38

δY′ |X h(Y |X)

6.2

Analysis

Proof of Theorem 1.7. Consider an input proof sequence of length ℓ ≤ D(3kσk1 + kδk1 + kµk1 ), thanks to
Theorem 5.9. If we do not hit Case 4b, then there will be at most ℓ steps in the algorithm, where each
step either takes Õ(2OBJ ) time or spawns O(OBJ) subproblems, for a total of Õ(poly(OBJ) · 2OBJ )-time. A
subproblem will terminate at producing a relation T (AB ) for some B ∈ B because the proof sequence will,
by definition, reach a point where δB|∅ ≥ w > 0 for some B ∈ B.
The worst case is obtained when the algorithm branches as far as possible only to have to restart at
Case 4b with a slightly shorter proof sequence of length at most D(3kσk1 + kδk1 + kµk1 ) − 1, thanks to
Lemma 5.11. Thus, overall the exponent of OBJ (in poly(OBJ)) will be ≤ 21 D2 (3kσk1 + kδk1 + kµk1 )2 .
(Note that this constant is data-independent because the optimal dual solution (δ, σ, µ) can be taken to be
an extreme point of the dual polyhedron (76), whose constraints are only dependent on the input query.)
Since OBJ equals the polymatroid bound LogSizeBoundΓn ∩HDC (P ), which is bounded by the vertex bound
log(N n ), and n is a constant in data complexity, we have OBJ = O(log N ), and the runtime is Õ(poly(log N )·
2LogSizeBoundΓn ∩HDC (P ) ), as desired.

7

Degree-Aware width parameters and algorithms

This section explains how PANDA can be used to evaluate queries within the analogs of fractional hypertree
width and submodular width under general degree constraints. In particular, we shall present a proof
of Theorem 1.9. Towards this goal, we need to generalize traditional width parameters to handle degree
constraints. The typical definitions of these width parameters (Definition 2.7) do not generalize in any obvious
way to handle functional dependencies, let alone degree constraints. Hence, our first task in Section 7.1 is
to reformulate known width parameters under the information theoretic view. Our reformulation leads
naturally to generalizations, described in Section 7.2 with degree constraints taken into account. Section 7.3
demonstrates the utility of our formulation by summarizing all major known bounds and widths under the
same umbrella. Finally, Section 7.4 shows how PANDA is used to achieve a runtime predicted by these new
degree-aware widths.

7.1

Minimax and maximin widths

We slightly reformulate existing width parameters under a common framework. Recall from Section 2
that there are two classes of width parameters: the first class captures algorithms seeking the best tree
decomposition with the worst bag runtime, while the second class captures algorithms adapting the tree
decomposition to the instance at hand. In the definitions below, the maximin width notion is from Marx [39,
40].
Definition 7.1. Let F denote a topologically closed class of non-negative set functions on [n]. The F minimax width and F -maximin width of a query Q are defined by
MinimaxwidthF (Q)

def

MaximinwidthF (Q)

def

=

min max max h(χ(t)),

(87)

max min max h(χ(t)).

(88)

(T,χ) t∈V (T ) h∈F

=

h∈F (T,χ) t∈V (T )

The following observation is straightforward:
Lemma 7.2. If G ⊆ F are two topologically closed classes of functions, then
MinimaxwidthG (H) ≤
MaximinwidthG (H) ≤

MinimaxwidthF (H)
MaximinwidthF (H).

For a fixed class F of functions, we have MaximinwidthF (H) ≤ MinimaxwidthF (H).
39

Proof. We prove the only non-trivial inequality that MaximinwidthF (H) ≤ MinimaxwidthF (H). From definition:
MaximinwidthF (H) =

max min max h(χ(t))
h∈F (T,χ) t∈V (T )

≤

min max max h(χ(t))

(T,χ) h∈F t∈V (T )

=

min max max h(χ(t))

(T,χ) t∈V (T ) h∈F

=

MinimaxwidthF (H).

These width notions are used by specializing F to capture two aspects of the input. The first aspect
∗
uses either the class of entropic functions or its relaxation, coming from the chain of inclusion Mn ⊂ Γn ⊂
Γn ⊂ SAn (See Fig. 3). The second aspect models the granularity level of statistics we know from the input
database instance, with the following inclusion chain
HDC ⊂ HCC ⊂ ED · log N ⊂ VD · log N.

(89)

(Recall notation from Section 2.) Note that the bounds in the constraints HDC are not normalized as in the
sets ED or VD in the traditional width parameters. This is because normalizing degree constraints makes
them less general than they can be, and it does not make practical sense to assume that all degree bounds
to be the same! (For example, the FD-based degree bounds are always 0, while the relation-size-based
degree bounds are log2 NF .) Consequently, we used the log2 N scaled up versions of the traditional width
parameters to compare with our new width parameters.
From these specializations, the minimax and maximin widths capture all width parameters we discussed
in Section 2, summarized in the following proposition.
Proposition 7.3. Let Q be a conjunctive query with only cardinality constraints (no FDs nor proper degree
constraints) whose hypergraph is H = ([n], E). Then the followings hold (Recall notation from Section 2):
1 + tw(H) = MinimaxwidthF ∩VD (Q)
∗

∀F ∈ {Mn , Γn , Γn , SAn }

= MaximinwidthF ∩VD (Q)
ghtw(H) = MinimaxwidthSAn ∩ED (Q)
= MaximinwidthSAn ∩ED (Q)

(90)
(91)

∀F ∈

fhtw(H) = MinimaxwidthF ∩ED (Q)
subw(H) = MaximinwidthΓn ∩ED (Q)

∗
{Mn , Γn , Γn }

adw(H) = MaximinwidthMn ∩ED (Q).

(92)
(93)
(94)

Proof.
To prove (90), note that for h ∈ SAn and any set F ⊆ [n], from subadditivity we have h(F ) ≤
P
v∈F h(v) ≤ |F |. Hence, recalling the definition of tree-width from Section 2.1, we have
MinimaxwidthSAn ∩VD (Q) = min max

max

(T,χ) t∈V (T ) h∈SAn ∩VD

h(χ(t)) ≤ min max |χ(t)| = tw(H) + 1.
(T,χ) t∈V (T )

To show the reverse, define the function h̄(F ) = |F | for all F ⊆ [n]. This function is modular and vertexdominated, and thus
tw(H) + 1 ≥
≥
≥

=

MinimaxwidthSAn ∩VD (Q)
MinimaxwidthMn ∩VD (Q)
MaximinwidthMn ∩VD (Q)
max

min max h(χ(t))

h∈Mn ∩VD (T,χ) t∈V (T )

≥

(T,χ) t∈V (T )

=

tw(H) + 1.

min max h̄(χ(t))

40

Thus the bound hierarchy collapses for the VD constraints.
The first equality in (91) is proved similarly to that of identity (43). To prove the second equality in (91),
define the function h̄(B) = ρ(B) for all B ⊆ [n]. This function is in SAn and is also edge-dominated. Then
MaximinwidthSAn ∩ED (Q) =
≥

max

min max h(χ(t))

h∈SAn ∩ED (T,χ) t∈χ(t)

min max h̄(χ(t))

(T,χ) t∈χ(t)

= ghtw(H)
= MinimaxwidthSAn ∩ED (Q).
Identity (92) follows immediately from Lemma 3.1, picking B to be the bag with the worst-case bound
for any tree decomposition. Identities (93) and (94) are just their definitions.
Note from (91) the interesting fact that the set SAn is so large that switching to the Maximinwidth
does not help reduce the objective. While SAn yields too large of an upperbound, and Mn only yields a
lowerbound, depending on the constraints we want to impose, some parts of the hierarchy collapse.
To further illustrate the strength of the minimax/maximin characterization, Example 7.4 below uses the
above characterization to bound the subw of a cycle query, and to show that the gap between fhtw and
subw is unbounded. (Marx [39, 40] already constructed a hypergraph where subw is bounded and fhtw is
unbounded, which is a stronger result; on the other hand, his example is much more involved.)
Example 7.4 (Unbounded gap between fhtw and subw). Consider a query whose graph H = (V, E) and is
defined as follows. The vertex set V = I1 ∪ I2 ∪ · · · ∪ I2k is a disjoint union of 2k sets of vertices. Each set Ij
has m vertices in it. There is no edge between any two vertices within the set Ij for every j ∈ [2k], namely Ij
is an independent set. The edge set E of the hypergraph is the union of 2k complete bipartite graphs Km,m :
def

E = I1 × I2 ∪ I2 × I3 ∪ · · · ∪ I2k−1 × I2k ∪ I2k × I1 .
To each edge in E there corresponds an input relation.
We first bound the fhtw of this graph. Consider any non-redundant tree decomposition (T, χ) of H with
fractional hypertree width equal to fhtw(H). Let t ∈ V (T ) be a leaf node of the tree T and t′ be the (only)
neighbor of t. Due to non-redundancy, there must be a vertex v ∈ χ(t) such that v ∈
/ χ(t′ ). It follows that
χ(t) is the only bag in the tree decomposition containing (v, u), for any u for which (v, u) ∈ E. This means
χ(t) contains the entire neighborhood of v in the graph H. The neighborhood of every vertex contains 2m+ 1
vertices: the vertex and its neighboring two independent sets for a total of 2m independent vertices. Since
no edge can cover two vertices of an independent set, the best fractional cover bound for χ(t) is at least 2m,
namely fhtw(H) ≥ 2m.
Next, we bound H’s submodular width. Let h be any submodular function.
• Case 1: h(Ii ) ≤ θ for some i ∈ [2k]. WLOG assume h(I1 ) ≤ θ. Consider the tree decomposition
I1 ∪ I2 ∪ I3
For bag B = I1 ∪ Ii ∪ Ii+1 ,

I1 ∪ I2k−1 ∪ I2k

I1 ∪ I3 ∪ I4

h(B) ≤ h(I1 ) + h(Ii ∪ Ii+1 ) ≤ θ + m.

• Case 2: h(Ii ) > θ for all i ∈ [2k]. Consider the tree decomposition
I1 ∪ I2 ∪ · · · ∪ Ik+1

Ik+1 ∪ Ik+2 ∪ · · · ∪ I2k ∪ I1

Bag B1

Bag B2

41

From submodularity, it is easy to see that
h(B1 ) ≤
h(B2 ) ≤

k+1
X

h(I1 ∪ I2 ) +
h(I2k ∪ I1 ) +

i=3

h(Ii ∪ Ii−1 |Ii−1 )

2k−1
X

i=k+1

≤ km − (k − 1)θ

h(Ii ∪ Ii+1 |Ii+1 ) ≤ km − (k − 1)θ

Thus, by setting θ = (1 − 1/k)m we have just proved that subw(H) ≤ m(2 − 1/k). By increasing m,
the gap between m(2 − 1/k) and 2m is infinite for a fixed k ≥ 2.
Corollary 7.5. Let Q be a conjunctive query (with no FDs nor degree constraints) whose hypergraph is H,
then 1 + tw(H) ≥ ghtw(H) ≥ fhtw(H) ≥ subw(H) ≥ adw(H). Moreover, the gap between any two consecutive
entries in the above series is unbounded.

7.2

New width parameters

Using the maximin and minimax formalism, we easily extend the traditional width parameters to handle
general degree constraints. As shown by Theorem 1.3 we know that there is a gap between the polymatroid
∗
bound and the entropic bound; and hence it is natural to use Γn itself instead of some approximation of it.
Definition 7.6. We define the following width parameters for queries Q with degree constraints DC. The
first two parameters are generalizations of fhtw and subw under degree constraints, and the last two are their
entropic versions:
da-fhtw(Q)
da-subw(Q)
eda-fhtw(Q)
eda-subw(Q)

def

=

MinimaxwidthΓn ∩HDC (Q)

(95)

def

=

MaximinwidthΓn ∩HDC (Q)

(96)

def

=

MinimaxwidthΓ∗ ∩HDC (Q)

(97)

def

MaximinwidthΓ∗ ∩HDC (Q).

(98)

=

n

n

(da stands for “degree-aware”, and eda for “entropic degree-aware”.) The following relationships hold
between these four quantities.
Proposition 7.7. For any query Q with degree constraints

≤

da-fhtw(Q).

da-subw(Q)

≤

eda-fhtw(Q)

≤

eda-subw(Q) ≤

The quantities eda-fhtw(Q) and da-subw(Q) are not comparable. The gap between the two sides of any of the
above four inequalities can be made arbitrarily large by some input.
Proof. We prove that eda-fhtw(Q) and da-subw(Q) are incomparable. Let ZY denote the Zhang-Yeung query
defined in the proof of Theorem 1.3. Add one additional relation R[n] to the query, with very large relation
size bound N[n] . Call the resulting query ZY+ . Then, for this query eda-subw(ZY+ ) = eda-fhtw(ZY+ ) <
da-subw(ZY+ ) = da-fhtw(ZY+ ). In fact, with the gap amplification trick we showed in the proof of Theorem 1.3, we can show that there are queries for which the gap is as large as one wants.
On the other hand, for the 4-cycle query C4 , we show in Example 7.8 that 2 log N = eda-fhtw(C4 ) >
3/2 log N = da-subw(C4 ).

42

Example 7.8 (Computing da-fhtw, da-subw, eda-fhtw, and eda-subw for a 4-cycle). Consider the 4-cycle query
C4 shown in equation (3), which has no proper degree bounds (only input size bounds). Let N be the common
upperbound on all input relations’ sizes, we will show that da-subw(C4 ) = eda-subw(C4 ) = 3/2 log N and
da-fhtw = eda-fhtw(C4 ) = 2 log N . Since there is no degree bound, da-fhtw(C4 ) = fhtw(C4 ) · log N = 2 log N ,
and da-subw(C4 ) = subw(C4 ) · log N ≤ 3/2 log N (see Example 7.4). To show da-subw(C4 ) ≥ 3/2 log N ,
consider the function h̄(F ) = |F2 | log N , for all F ⊆ [4]. This function is in Γ∗4 ; and, for any bag B of
the two tree decompositions shown in Figure 2, h(B) = 3/2 log N . Hence, 3/2 log N ≤ eda-subw(C4 ) ≤
da-subw(C4 ) ≤ 3/2 log N . The fact that eda-fhtw(C4 ) = 2 log N can be shown similarly.
Another somewhat interesting observation which follows from the above is the following. Due to the fact
that every non-negative modular set function is entropic, we have

Corollary 7.9. When Q has only edge domination constraints ED (i.e. no FD nor proper degree bounds),
we have adw(Q) ≤ eda-subw(Q).
Following Marx [39, 40], for these queries with only ED constraints, we have da-subw(Q) = subw(Q) =
O(adw4 (Q)) = O(eda-subw4 (Q)). Thus, when there is only ED constraints, if a class of queries has bounded
eda-subw, then it has bounded da-subw.

7.3

Summary of known bounds and width parameters

We have mentioned quite a few known and proved new bounds in this paper. The bounds can be summarized
systematically as follows. Each bound is identified by coordinates (X, Y, Z). The X-axis represents the
∗
entropy approximation that is being used: one starts from the desired target Γn , then relaxes it to Γn and
∗
SAn . The inclusion chain is Γn ⊂ Γn ⊂ SAn . The Y -axis represents the constraints we can extract from the
input database instance, where we can go from bounding domain sizes, relation sizes, to incorporating more
refined degree bounds and functional dependencies. One chain of inclusion was given by (89). The Z-axis
represents the level of sophistication of the query plan that is being considered in this bound. The simplest
query plan just joins everything together without computing any tree decomposition – or, equivalently,
this is the plan that uses the trivial tree decomposition with one bag containing all attributes. (Recall
the bounds DAEB(Q) and DAPB(Q) from (39).) Then, one can get more sophisticated by computing a
tree decomposition then computing its bags. And, lastly the query plan can also be adaptive to the input
instance, yielding the submodular-width style of complexity. The bounds are summarized in Figure 9. If
bound A has coordinates (XA , YA , ZA ) that are less than the corresponding coordinates (XB , YB , ZB ) of
bound B (i.e. if XA ≤ XB ∧ YA ≤ YB ∧ ZA ≤ ZB ), then bound A ≤ bound B.

7.4

Achieving degree-aware width parameters

With increasing levels of complexity, the corollaries below explain how PANDA can be used to evaluate
a (full or Boolean) conjunctive query achieving the degree-aware polymatroid size bound defined in (39),
the degree-aware version of the fractional hypertree width defined in (95), and the degree-aware version of
the submodular width defined in (96). (In Section 8, we briefly show how to use PANDA to solve other
conjunctive queries as well as aggregate queries.)
A basic fact that we employ in this section is the following: given an α-acyclic query (with no FD nor
degree constraints), the query can be computed in time Õ(|input| + |output|) [28,48]. In particular, let (T, χ)
be some tree decomposition, and suppose we have a query for which every bag B of the tree decomposition
corresponds uniquely to an input relation RB ; then, the query is α-acyclic (the tree decomposition is the
join tree of the query), and it can be computed in linear time in the input plus output sizes (modulo a log
factor).
7.4.1

Conjunctive query with degree constraints

Consider a full conjunctive query Q with degree constraints HDC. Since a full conjunctive query is just the
disjunctive datalog rule (4) with B = {[n]}, we have an immediate corollary. However, we spell out more
43

Z

HDC

∗

Γn

HCC

DAEB(Q)
Γn
DAPB(Q)

log AGM(Q
)

SAn

ED · log N

log AGM(Q
)

ρ(Q, (N )
F F ∈E )

ρ ∗(Q) · log

ρ ∗(Q) · log

N

N

ρ(Q) · log N

VD · log N
log VB(Q)

)

∩Y

)

9
X
nd . (3
u
q
o
E

log VB(Q)

B
ze .2 &
Si
g
.3
Lo rop

log VB(Q)

eda-fhtw(Q
)

P

fhtw(Q) · lo
g

da-fhtw(Q
)

fhtw(Q) · lo
g
ghtw(Q) ·
log

N

N

N

(tw(Q) + 1)

(tw(Q) + 1)

(tw(Q) + 1)

log N

log N
∩Y

(Q

)
6

.
th X fn. 7
id
e

log N

w
D
ax
m 7.3 &
i
in p.
M
o
Pr

eda-subw(Q
)
da-subw(Q
)

(tw(Q) + 1)
subw(Q) ·
log

X

(Q

ghtw(Q) ·
log

N

N

(tw(Q) + 1)

(tw(Q) + 1)

log N
∩Y

log N

log N

M

ax

im

(Q

)

Y
6

7.
hX
dt efn.
i
w
D
in
&

Pr

.7
op

.3

Figure 9: A hierarchy of bounds: Each bound corresponds to an entry in a three-dimensional space. On
the Z-axis, we have three levels: The top level (in red) depicts LogSizeBoundX∩Y (Q) (where X and Y are
the X- and Y - coordinates), the middle level (in green) depicts MinimaxwidthX∩Y (Q), and the lowest level
(in blue) depicts MaximinwidthX∩Y (Q). On the X-axis, we have three different coordinates: SAn , Γn , and
∗
∗
Γn , and they are ordered: SAn ⊃ Γn ⊃ Γn . On the Y -axis, we have four different ordered coordinates:
VD · log N ⊃ ED · log N ⊃ HCC ⊃ HDC. Notations are defined in Section 2. For example, on the top
level of the Z-axis (the red level), the bound whose X-coordinate is Γn and whose Y -coordinate is HCC
should be LogSizeBoundΓn ∩HCC (Q), which by Proposition 3.2 corresponds to log AGM(Q). Similarly on the
lowest level of the Z-axis (the blue level), the bound whose X-coordinate is Γn and whose Y -coordinate is
ED · log N should be MaximinwidthΓn ∩(ED log N ) (Q), which by Proposition 7.3 corresponds to subw(Q) · log N .
This diagram satisfies the following property: Given a bound A whose coordinates are (XA , YA , ZA ) and a
bound B whose coordinates are (XB , YB , ZB ), if XA ≤ XB , YA ≤ YB and ZA ≤ ZB , then bound A ≤ bound
B. For example, if bound A has coordinates (XA , YA , ZA ) = (Γn , HDC, Maximinwidth) and bound B has
coordinates (XB , YB , ZB ) = (Γn , ED · log N, Minimaxwidth), then we can infer that bound A ≤ bound B.
This is true because bound A corresponds to da-subw(Q) and bound B corresponds to fhtw(Q) · log N . From
the same property, we can also infer that the bound eda-subw(Q) is ≤ any other bound in the diagram since
∗
it has the smallest coordinates (Γn , HDC, Maximinwidth) on all three axes. For more details and insights
about this diagram, see Section 7.3.

44

details than necessary here for the reader to get a sense of how the Shannon flow inequality looks in this
simple case. In this case, LogSizeBoundΓn ∩HDC (Q) specializes to DAPB(Q) whose LP (39) can be written
more concretely as
max
s.t.

h([n])
h(Y ) − h(X) ≤ nY |X

(99)
(X, Y, NY |X ) ∈ DC

h(X) − h(Y ) ≤ 0,
h(Z) ≥ 0,

∅ 6= X ⊂ Y ⊆ [n]
∅ 6= Z ⊆ [n].

h(I ∪ J|J) − h(I|I ∩ J) ≤ 0,

(degree constraints)

I⊥J

(submodularity)
(monotonicity)
(non-negativity)

The dual of (99) is
min
s.t.

P

(X,Y )∈DC

nY |X · δY |X

inflow([n])

(100)
≥1

≥ 0, ∅ 6= Z ⊂ [n].
≥ 0.

inflow(Z)
(δ, σ, µ)

Let h∗ denote an optimal solution to (99), and (δ ∗ , σ ∗ , µ∗ ) a dual-optimal solution, then h∗ ([n]) =
nY |X . The DAPB(Q) bound can also be written as
DAPB(Q) = 2h

∗

([n])

=

Y

∗

2nY |X δY |X =

Y

P

∗
(X,Y )∈DC δY |X ·

δ∗

|X
NYY|X
.

(X,Y )∈DC

(X,Y )∈DC

This was in the same form as the more familiar AGM(Q) bound for queries with no degree constraints. (See
also Proposition 3.2). In this case, Proposition 5.4 states the following. Given δ ∈ QDC
+ , the inequality
h([n]) ≤

X

(X,Y )∈DC

δY |X · h(Y |X)

(101)

is a Shannon flow inequality if and only if there exist σ and µ such that (δ, σ, µ) is feasible to the dual
LP (100). (In particular, the inequality holds when δ = δ ∗ .) Note that inequality (101) implies the
upperbound on h([n]) we wanted because h(Y |X) ≤ nY |X . Note also that inequality (101) has only one
target [n].
Let B ⊆ [n] be any fixed set. Let eB = (e(Y |X))(X,Y )∈P ∈ QP
+ denote the unit vector where e(B|∅) = 1
[n]
and e(Y |X) = 0 otherwise. Then, inequality (101) is he , hi ≤ hδ, hi.
Corollary 7.10. A full or Boolean conjunctive query Q with degree constraints can be solved by PANDA in
time Õ(N + poly(log N ) · 2DAPB(Q) ).
Proof. Let (δ ∗ , σ ∗ , µ∗ ) denote an optimal solution to the dual (100). Then, from Proposition 5.4 he[n] , hi ≤
hδ ∗ , hi is a Shannon flow inequality. When feeding this Shannon flow inequality to PANDA, the quantity
OBJ defined in (83) is exactly DAPB(Q) due to strong duality. The output of PANDA is a single table T[n]
which is a superset of Q. To compute Q exactly, we semijoin-reduce T[n] with every input relation RF ,
F ∈ E; namely we set T[n] = T[n] ⋉ R(F ) for all F ∈ E.
7.4.2

Achieving the degree-aware fractional hypertree width

Next let us consider the degree-aware version of the fractional hypertree width defined in (95), whose full
definition is
def
da-fhtw(Q) = min max
max h(χ(t)).
(T,χ) t∈V (T ) h∈Γn ∩HDC

45

Suppose we want to compute da-fhtw, a bruteforce algorithm is to go over all tree decompositions (T, χ) of
H10 ; for each (T, χ) we take a bag B = χ(t) and solve the inner most optimization problem: 11
max{h(B) | h ∈ Γn ∩ HDC}

(102)

Thanks to Lemma 3.1, we know max{h(B) | h ∈ Γn ∩ HDC} = max{h(B) | h ∈ Mn ∩ HDC} when all
constraints are cardinality constraints, in which case this LP can be reduced to the LP (99) by restricting
all functions down to the universe B. However, this does not hold when we add FDs to the query, and it is
certainly not true when we add arbitrary degree constraints. The dual of (102) is the following LP:
P
(103)
min
(X,Y )∈DC nY |X · δY |X
s.t.

≥1
≥ 0, ∅ 6= Z ⊆ [n].

inflow(B)
inflow(Z)

≥ 0.

(δ, σ, µ)

Proposition 5.4 states the following: given δ ∈ QDC
+ , the inequality
X
δY |X · h(Y |X)
h(B) ≤

(104)

(X,Y )∈DC

is a Shannon flow inequality if and only if there exist σ and µ such that the vector (δ, σ, µ) is feasible to
the dual LP (103). More compactly, inequality (104) can be written as heB , hi ≤ hδ, hi.
Corollary 7.11. A full or Boolean conjunctive query Q with degree constraints can be solved by PANDA in
time
Õ(N + poly(log N ) · 2da-fhtw(Q) + |output|).
Proof. As discussed, a tree decomposition (T, χ) of Q for which maxt∈V (T ) maxh∈Γn ∩HDC h(χ(t)) = da-fhtw(Q)
can be computed bruteforcely by going through at most n! tree decompositions and solving a total of ≤ 2n
distinct linear programs, each of which is data independent (except for a log-factor in the data to compute
the degree bounds in advance).
Now suppose we have already fixed an optimal tree decomposition (T, χ). For every bag B of this
tree decomposition, we use PANDA to compute a relation TB for which ΠB (Q) ⊆ TB . After that we set
TB = TB ⋉ RF for every F ∈ E. (By definition of a tree decomposition, for every input relation RF , there
must be a bag B ⊇ F .) Finally, Q is the join of all these tables TB , which is now an α-acyclic query solvable
in linear time (in input plus output size) by Yannakakis’s algorithm [28, 48].
For a fixed bag B of the optimal tree decomposition, let OPT be the optimal objective value of the
LP (102). Let (δ ∗ , σ ∗ , µ∗ ) denote a dual-optimal solution. Then, from Proposition 5.4 we know heB , hi ≤
hδ ∗ , hi is a Shannon flow inequality. When feeding this Shannon flow inequality to PANDA, the quantity
OBJ defined in (83) is exactly OPT due to strong duality.
7.4.3

Achieving the degree-aware submodular width

The third corollary is on achieving the the degree-aware submodular width. Unlike the first two corollaries,
proving this requires a couple of new ideas. In order to compute da-subw, even in a bruteforce manner, we
need an auxiliary lemma, which is somewhat related to Neumann’s minimax theorem [24].
Lemma 7.12. Let A and B be two finite sets, and f : A × B → R be any function. Let B A denote the set
of all maps from A to B. Then, the following holds:
min max f (a, b) = max min f (a, β(a)).
a∈A b∈B

β∈B A a∈A

10 There

are at most n! non-redundant tree decompositions, each of which has at most n bags (Proposition 2.9).
11 The total number of distinct optimization problems that we have to solve for all n! tree decompositions is ≤ 2n , since we
have one problem for each distinct choice of B ⊆ [n].

46

def

Proof. For any a ∈ A, define β ∗ (a) = argmaxb∈B f (a, b).
min max f (a, b) = min f (a, β ∗ (a)) ≤ max min f (a, β(a)).
a∈A b∈B

a∈A

β∈B A a∈A

Conversely,
max min f (a, β(a)) ≤ max min f (a, β ∗ (a)) = min f (a, β ∗ (a)) = min max f (a, b).

β∈B A a∈A

β∈B A a∈A

a∈A

a∈A b∈B

Intuitively, on the LHS we select for each a ∈ A a neighbor b for which f (a, b) is maximized; call such
neighbor a’s “representative”. Then, we select the a with the least-weight representative. On the RHS, we
have a “representative selector” β; we pick the a-value with the least-weight selected representative, and
then maximize over all selectors.
Corollary 7.13 (Restatement of Theorem 1.9). A full or Boolean conjunctive query Q with degree constraints
DC can be solved by PANDA in time
Õ(N + poly(log N ) · 2da-subw(Q) + |output|).
Proof. We first apply Lemma 7.12 to reformulate (96). To this end, we need a few notations. (Recall from
Section 2.1 that TD denotes the set of all non-redundant tree decompositions of Q.) Let M be the set of all
maps β : TD → 2[n] , such that β(T, χ) = χ(t) for some t ∈ V (T ). In English, β is a “bag selector” map that
picks out a bag from each tree decomposition (T, χ). Let B be the collection of images of all β ∈ M, i.e.
B = {B | B = image(β) for some β ∈ M}.

(105)

Using Lemma 7.12, we can rewrite (96) as follows.
da-subw(H)

=

(Lemma 7.12)

=
=
=

max

min

max h(χ(t))

h∈Γn ∩HDC (T,χ)∈TD t∈V (T )

max

max min h(β(T, χ))

max

max

h∈Γn ∩HDC β∈M (T,χ)

min

h(B)

min

h(B)

h∈Γn ∩HDC β∈M B∈image(β)

max

max

= max

max

= max

max

β∈M h∈Γn ∩HDC B∈image(β)

min h(B)
(
)
X
λB h(B)

B∈B h∈Γn ∩HDC B∈B

(Lemma 5.2)

B∈B h∈Γn ∩HDC

|

(106)

B∈B

{z

Linear program (68)

}

In (106), for a fixed B ∈ B the inner max is exactly the LP on the right-hand side of (68) whose dual
is (73). In particular, to compute the da-subw(Q), we can solve a collection of linear programs and take the
maximum solution among them. Since there is a different linear program for each valid choice of B (and B
n
is a set of subsets of [n]), the total number of linear programs is ≤ 22 .
In order to compute Q in the desired time, we mimic this strategy in the algorithm. For each B ∈ B, we
solve the LP (68). Let (δ ∗ , σ ∗ , µ∗ ) denote a dual optimal solution. From Proposition 5.4, hλ, hi ≤ hδ ∗ , hi is
a Shannon flow inequality. On this input PANDA computes a tuple TB = (TB )B∈B of tables such that, for
every a ∈ Q there exists a B ∈ B for which ΠB (a) ∈ TB .
Let M = |B| and suppose B = {B1 , . . . , BM }. We prove the following claims:
47

QM
Claim 1: for every (B1 , . . . , BM ) ∈ i=1 Bi , there is a tree decomposition (T, χ) ∈ TD(Q) such that,
for every tree node t ∈ V (T ), χ(t) = Bj for some j ∈ [M ]. Breaking ties arbitrarily, we call this tree
decomposition the tree decomposition (of Q) associated with the tuple (B1 , . . . , BM ).
QM
Claim 2: for any tuple (B1 , . . . , BM ) ∈ i=1 Bi with associated tree decomposition (T, χ), define
def

J(B1 , . . . , BM ) = ✶t∈V (T ) Tχ(t) .

Then,



Q⊆

[

(B1 ,...,BM )∈

QM

i=1 Bi





⊆
✶M
j=1 TBj

[

(B1 ,...,BM )∈

QM

i=1 Bi



J(B1 , . . . , BM ) .

(107)

QM
Assuming the claims, the query can be computed by taking each tuple (B1 , . . . , BM ) ∈ i=1 Bi and running
Yannakakis algorithm to compute the output of the associated join query J(B1 , . . . , BM ) within a runtime of
Õ(2da-subw(Q) +|J(B1 , . . . , BM )∩Q|). If we apply Yannakakis algorithm straight up on the join J(B1 , . . . , BM ),
then we can attain the runtime Õ(2da-subw(Q) + |J(B1 , . . . , BM )|), because every table TBj has size bounded
by 2da-subw(Q) . To reduce the runtime down to Õ(2da-subw(Q) + |J(B1 , . . . , BM ) ∩ Q|), we semijoin-reduce every
table Tχ(t) in the join J(B1 , . . . , BM ) with every input relation before we join the tables Tχ(t) together. The
QM
QM
above process has to be repeated for every tuple (B1 , . . . , BM ) ∈ i=1 Bi . There are i=1 |Bi | such tuples,
which is a query-complexity quantity.
QM
We next prove Claim 1. Fix a tuple (B1 , . . . , BM ) ∈ i=1 Bi . Suppose to the contrary that for every
tree decomposition (T, χ) there is a tree node t ∈ V (T ) such that χ(t) ∈
/ {B1 , . . . , BM }. Call the bag χ(t)
a missed bag of the tree decomposition (T, χ). Consider a bag selector β̄ : TD(Q) → 2[n] where β̄(T, χ) is
exactly the missed bag of the tree decomposition (T, χ). Note that by definition of B we have image(β̄) = Bk
for some k ∈ [M ]. This is a contradiction because Bk ∈ Bk must then be the missed bag of some tree
decomposition, but it is not missed anymore (since it belongs to {B1 , . . . , BM }).
Finally, we prove Claim 2. Consider an output tuple a ∈ Q. For each j ∈ [M ], let Bj denote the target
in Bj for which ΠBj (a) ∈ TBj . Then, obviously a ∈✶M
j=1 TBj . This proves the first inclusion in (107). The
second inclusion is obvious because the join J(B1 , . . . , BM ) drops some tables from the join ✶M
j=1 TBj .
For a simple example on the algorithm from the proof of Corollary 7.13, see Example 1.10.

8

Discussions

Our negative answer to Question 1 from Section 1 leads to a natural question: can we design an algorithm
whose runtime matches the entropic bound under the presence of FDs or degree constraints? Worst-case
optimal join algorithms [1,42,43,47] were able to achieve this when there are no FDs (nor degree constraints).
And, as shown in [3] there are classes of queries with FDs for which the answer is positive (using the chain
algorithm). A natural direction is to extend the class of queries with FDs where the entropic bound can be
met, beyond what was shown in [3].
Along the same line, the next natural open question is to design algorithms to evaluate disjunctive
datalog rules matching the entropic bound LogSizeBoundΓ∗ ∩HDC (P ). From there, the possibility of achieving
n
eda-subw and/or eda-fhtw is within reach. We already have an example where PANDA was able to achieve
eda-subw and eda-fhtw: the 4-cycle query. In general, the inner-most column of Figure 9 (i.e. the column
∗
with X-coordinate of Γn and Y -coordinate of HDC) contains open algorithmic questions: we do not know of
∗
algorithms meeting bounds involving both Γn and HDC. Another big open question is to remove the polylog
factor from the runtime of PANDA.
As was mentioned right after Corollary 7.9, for queries with only cardinality constraints, da-subw(Q) =
O(eda-subw(Q)4 ) and hence bounded entropic submodular width implies bounded submodular width and
vice versa. It is open whether or not the same relationship holds when Q has FDs and/or degree bounds.

48

The algorithmic results we formally stated in the paper apply only to full and to Boolean conjunctive
queries (Theorem 1.9). This begs a natural question: “what happens to proper conjunctive queries and
to aggregate queries (such as FAQ-queries over a single semiring, called the SumProd or FAQ-SS queries [2,
5])?” Our technique and results easily extend to the case of general conjunctive queries Q (i.e. queries
whose set of free variables isn’t necessarily empty nor equal to [n]). To deal with these queries, the first
minor change is to generalize the notions of Maximinwidth and Minimaxwidth defined in Definition 7.1:
In particular, the min(T,χ) should now range only over “free-connex“ tree decompositions (T, χ) instead of
ranging over all tree decompositions. A “free-connex” tree decomposition is a tree decomposition constructed
from a GYO variable elimination ordering in which non-free variables are eliminated before the free variables
(see [2] for how one obtains a tree decomposition from a variable ordering). Alternatively, a free-connex tree
decomposition can be defined as a tree decomposition whose bags form a free-connex acyclic query [13, 45].
Achieving the Minimaxwidth can be done in the exact same way as before. Achieving the Maximinwidth
requires a second minor change: we need a collection of auxiliary disjunctive datalog rules. These rules are
obtained using the distributivity law in exactly the same way it was applied in (23), except that the head
conjunction is now only over free-connex tree decompositions. In other words, the “bag selector map” β in
the proof of Corollary 7.13 selects bags only from “free-connex” tree decompositions. In the case of FAQ-SS
queries, we can easily achieve the da-fhtw-runtime from Corollary 7.11, with da-fhtw replaced by the width
over free-connex tree decompositions as above. However, achieving the da-subw for general FAQ-SS queries
remains an open problem. To keep the paper accessible, we have decided against presenting the more general
treatment outlined in this paragraph, concentrating only on Boolean and full conjunctive queries.

References
[1] Abo Khamis, M., Ngo, H. Q., Ré, C., and Rudra, A. Joins via geometric resolutions: Worst-case
and beyond. In PODS 2015 (New York, NY, USA, 2015), ACM, pp. 213–228.
[2] Abo Khamis, M., Ngo, H. Q., and Rudra, A. FAQ: questions asked frequently. In PODS 2016
(2016), pp. 13–28.
[3] Abo Khamis, M., Ngo, H. Q., and Suciu, D. Computing join queries with functional dependencies.
In PODS 2016 (2016), pp. 327–342.
[4] Adler, I. Width functions for hypertree decompositions. University of Freiburg, 2006. Ph.D. Dissertation, Albert-Ludwigs-Universität Freiburg. 2006.
[5] Aji, S. M., and McEliece, R. J. The generalized distributive law. IEEE Transactions on Information
Theory 46, 2 (2000), 325–343.
[6] Alon, N. On the number of subgraphs of prescribed type of graphs with a given number of edges.
Israel J. Math. 38, 1-2 (1981), 116–130.
[7] Alon, N., Yuster, R., and Zwick, U. Finding and counting given length cycles. Algorithmica 17,
3 (1997), 209–223.
[8] Alviano, M., Faber, W., Leone, N., Perri, S., Pfeifer, G., and Terracina, G. The disjunctive
datalog system DLV. In Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK,
March 16-19, 2010. Revised Selected Papers (2010), O. de Moor, G. Gottlob, T. Furche, and A. J.
Sellers, Eds., vol. 6702 of Lecture Notes in Computer Science, Springer, pp. 282–301.
[9] Armbrust, M., Curtis, K., Kraska, T., Fox, A., Franklin, M. J., and Patterson, D. A.
PIQL: success-tolerant query processing in the cloud. PVLDB 5, 3 (2011), 181–192.
[10] Armbrust, M., Fox, A., Patterson, D. A., Lanham, N., Trushkowsky, B., Trutna, J., and
Oh, H. SCADS: scale-independent storage for social computing applications. In CIDR 2009, Fourth
49

Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2009,
Online Proceedings (2009).
[11] Armbrust, M., Liang, E., Kraska, T., Fox, A., Franklin, M. J., and Patterson, D. A. Generalized scale independence through incremental precomputation. In SIGMOD 2013 (2013), pp. 625–
636.
[12] Atserias, A., Grohe, M., and Marx, D. Size bounds and query plans for relational joins. In FOCS
(2008), IEEE Computer Society, pp. 739–748.
[13] Bagan, G., Durand, A., and Grandjean, E. On Acyclic Conjunctive Queries and Constant Delay
Enumeration. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 208–222.
[14] Bakibayev, N., Kociský, T., Olteanu, D., and Zavodny, J. Aggregation and ordering in factorised databases. PVLDB 6, 14 (2013), 1990–2001.
[15] Benedikt, M., Leblay, J., and Tsamoura, E. Querying with access patterns and integrity constraints. PVLDB 8, 6 (2015), 690–701.
[16] Benedikt, M., ten Cate, B., and Tsamoura, E. Generating plans from proofs. ACM Trans.
Database Syst. 40, 4 (2016), 22.
[17] Cao, Y., Fan, W., Wo, T., and Yu, W. Bounded conjunctive queries. PVLDB 7, 12 (2014),
1231–1242.
[18] Chan, T. H. Group characterizable entropy functions. CoRR abs/cs/0702064 (2007).
[19] Chan, T. H., and Yeung, R. W. On a relation between information inequalities and group theory.
IEEE Transactions on Information Theory 48, 7 (2002), 1992–1995.
[20] Chekuri, C., and Rajaraman, A. Conjunctive query containment revisited. Theor. Comput. Sci.
239, 2 (2000), 211–229.
[21] Chung, F. R. K., Graham, R. L., Frankl, P., and Shearer, J. B. Some intersection theorems
for ordered sets and graphs. J. Combin. Theory Ser. A 43, 1 (1986), 23–37.
[22] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, Third
Edition, 3rd ed. The MIT Press, 2009.
[23] Dechter, R. Bucket elimination: A unifying framework for reasoning. Artif. Intell. 113, 1-2 (1999),
41–85.
[24] Du, D., and Pardalos, P. Minimax and Applications. Nonconvex Optimization and Its Applications.
Springer US, 1995.
[25] Edmonds, J., and Karp, R. M. Theoretical improvements in algorithmic efficiency for network flow
problems. J. ACM 19, 2 (1972), 248–264.
[26] Eiter, T., Gottlob, G., and Mannila, H. Disjunctive datalog. ACM Trans. Database Syst. 22, 3
(1997), 364–418.
[27] Fischl, W., Gottlob, G., and Pichler, R. General and Fractional Hypertree Decompositions:
Hard and Easy Cases. ArXiv e-prints (Nov. 2016).
[28] Flum, J., Frick, M., and Grohe, M. Query evaluation via tree-decompositions. J. ACM 49, 6
(2002), 716–752.

50

[29] Freuder, E. C. Complexity of k-tree structured constraint satisfaction problems. In Proceedings of
the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, July 29 - August 3, 1990,
2 Volumes. (1990), H. E. Shrobe, T. G. Dietterich, and W. R. Swartout, Eds., AAAI Press / The MIT
Press, pp. 4–9.
[30] Friedgut, E., and Kahn, J. On the number of copies of one hypergraph in another. Israel J. Math.
105 (1998), 251–256.
[31] Gogacz, T., and Toruńczyk, S. Entropy bounds for conjunctive queries with functional dependencies. In Proc. 20th International Conference on Database Theory (ICDT) (2017).
[32] Gottlob, G., Greco, G., Leone, N., and Scarcello, F. Hypertree decompositions: Questions
and answers. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016 (2016), pp. 57–74.
[33] Gottlob, G., Lee, S. T., Valiant, G., and Valiant, P. Size and treewidth bounds for conjunctive
queries. J. ACM 59, 3 (2012), 16.
[34] Gottlob, G., Leone, N., and Scarcello, F. Hypertree decompositions and tractable queries. J.
Comput. Syst. Sci. 64, 3 (2002), 579–627.
[35] Grohe, M. The complexity of homomorphism and constraint satisfaction problems seen from the
other side. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003,
Cambridge, MA, USA, Proceedings (2003), IEEE Computer Society, pp. 552–561.
[36] Grohe, M., and Marx, D. Constraint solving via fractional edge covers. In SODA (2006), ACM
Press, pp. 289–298.
[37] Grohe, M., and Marx, D. Constraint solving via fractional edge covers. ACM Transactions on
Algorithms 11, 1 (2014), 4.
[38] Kohlas, J., and Wilson, N. Semiring induced valuation algebras: Exact and approximate local
computation algorithms. Artif. Intell. 172, 11 (2008), 1360–1399.
[39] Marx, D. Tractable structures for constraint satisfaction with truth tables. Theory Comput. Syst. 48,
3 (2011), 444–464.
[40] Marx, D. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM
60, 6 (2013), Art. 42, 51.
[41] Matus, F. Infinitely many information inequalities. In 2007 IEEE International Symposium on Information Theory (2007), IEEE, pp. 41–44.
[42] Ngo, H. Q., Porat, E., Ré, C., and Rudra, A. Worst-case optimal join algorithms: [extended
abstract]. In PODS (2012), pp. 37–48.
[43] Ngo, H. Q., Ré, C., and Rudra, A. Skew strikes back: new developments in the theory of join
algorithms. SIGMOD Record 42, 4 (2013), 5–16.
[44] Schrijver, A. Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Ltd., Chichester, 1986. A Wiley-Interscience Publication.
[45] Segoufin, L. Enumerating with constant delay the answers to a query. In Intl. Conf. on Database
Theory (2013), ICDT’13.
[46] Vardi, M. Y. The complexity of relational query languages (extended abstract). In STOC (1982),
pp. 137–146.

51

[47] Veldhuizen, T. L. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International
Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014. (2014), N. Schweikardt,
V. Christophides, and V. Leroy, Eds., OpenProceedings.org, pp. 96–106.
[48] Yannakakis, M. Algorithms for acyclic database schemes. In VLDB (1981), pp. 82–94.
[49] Yeung, R. W. Information Theory and Network Coding, 1 ed. Springer Publishing Company, Incorporated, 2008.
[50] Zhang, Z., and Yeung, R. W. On characterization of entropy function via information inequalities.
IEEE Transactions on Information Theory 44, 4 (1998), 1440–1452.

A

Missing details from the introduction

First, we prove the correctness of three bounds for the query from Example 1.2.
• Bound (a) follows from:
log |Q| = h(A1 A2 A3 A4 )

≤ h(A1 A2 ) + h(A3 A4 ) ≤ 2 log N,

which implies |Q| ≤ N 2 .
• Bound (b) follows from:
3 log N + 2 log D

≥
≥

h(A2 A3 ) + h(A3 A4 ) + h(A4 A1 ) + h(A2 |A1 ) + h(A1 |A2 )
h(A3 ) + h(A2 A3 A4 ) + h(A4 A1 ) + h(A2 |A1 ) + h(A1 |A2 )

=
=

2h(A1 A2 A3 A4 )
2 log |Q|,

≥
≥

h(A3 A4 A1 ) + h(A2 A3 A4 ) + h(A2 |A1 ) + h(A1 |A2 )
h(A3 A4 A1 ) + h(A2 A3 A4 ) + h(A2 |A3 A4 A1 ) + h(A1 |A2 A3 A4 )

which implies |Q| ≤ N 3/2 · D.
• Bound (c) follows from (b) by setting D = 1.
Now, we prove the tightness of the three bounds:
• Bound (a) is tight on the following database instance: R12 = R34 = [N ] × [1], R23 = R41 = [1] × [N ].
The output is Q(A1 , A2 , A3 , A4 ) = [N ] × [1] × [N ] × [1].
j
k
def √
N . Bound (c) is asymptotically tight on the instance R12 = {(i, i) | i ∈ [K]}, R23 =
• Let K =
R34 = R41 = [K] × [K]. The output is Q(A1 , A2 , A3 , A4 ) = {(i, i, j, k) | i, j, k ∈ [K]} .
• Bound (b) is tight on the following instance (which is a generalization of the previous one to 1 ≤ D ≤
K.)
R23 = R34 = R41 = [K] × [K],
R12 = {(i, j) | i, j ∈ [K], (j − i) mod K < D} .

B

More on Shannon-flow inequalities and proof sequences

This section presents extra results on Shannon flow inequalities and their proof sequences that go beyond
the results of Section 5.
52

B.1

Bounding kδk1 , kµk1 , and kσk1 (w.r.t kλk1 )

Given a Shannon flow inequality hλ, hi ≤ hδ, hi with a witness (σ, µ), there are various ways to construct
a proof sequence for hλ, hi ≤ hδ, hi. (Theorem 5.9 showed one possible construction, and we will see more
efficient constructions in Section B.2.) What those various constructions have in common is that the length
of the resulting proof sequence depends on kσk1 , kδk1 and/or kµk1 . In turn, the runtime of the PANDA
algorithm depends on the length of the proof sequence, which provides a motivation for minimizing kσk1 ,
kδk1 and kµk1 as much as possible, which is our target in this section. In particular, we want to replace the
original inequality (and its witness) with a new inequality that is “just as good” but has lower kσk1 , kδk1
and kµk1 .
This section is outlined as follows. We start Section B.1.1 with some definitions that formalize what
we meant by an inequality being “just as good” as another, then we proceed to bounding the total of
monotonicity terms of the form µX,Y for X 6= ∅. In Section B.1.2, we bound the total of terms of the form
δY |∅ . Section B.1.3 shows that this is equivalent to bounding monotonicity terms µ∅,Y , hence we now have
a bound on all monotonicity terms kµk1 . Finally, Section B.1.4 shows that bounding kµk1 imposes a bound
on both kδk1 and kσk1 .
B.1.1

Bounding the total of µX,Y for X 6= ∅

′
Definition B.1 (δ ′ dominated by δ). Given two vectors δ, δ ′ ∈ QP
+ , we say that δ is dominated by δ if
there exists a function f : P × P → Q+ that satisfies the following conditions.

• If f ((X, Y ), (X ′ , Y ′ )) 6= 0, then Y ′ \ X ′ ⊆ Y \ X and X ′ ⊇ X.
P
′
′
• ∀(X, Y ) ∈ P,
(X ′ ,Y ′ )∈P f ((X, Y ), (X , Y )) ≤ δY |X .
P
′
′
′
• ∀(X ′ , Y ′ ) ∈ P,
(X,Y )∈P f ((X, Y ), (X , Y )) ≥ δY ′ |X ′ .

The function f is called the domination function for (δ, δ ′ ).

′

Definition B.2 (Rational compatibility). Given two vectors of rational numbers q ∈ Ql+ , q′ ∈ Ql+ (for some
integers l, l′ ), we say that q′ is rationally-compatible with q if the minimum common denominator of all
entries in q is a common denominator (not-necessarily minimum) for all entries in q′ .
Lemma B.3. For any Shannon flow inequality hλ, hi ≤ hδ, hi with a witness (σ, µ), there exists a Shannon
flow inequality hλ′ , hi ≤ hδ ′ , hi with a tight12 witness (σ ′ , µ′ ) such that δ ′ is dominated by δ and λ′ dominates
λ and µ′X,Y = 0 for all ∅ 6= X ⊂ Y ⊆ [n]. Moreover, (λ′ , δ ′ , σ ′ , µ′ ) is rationally-compatible with (λ, δ, σ, µ).
Proof. W.L.O.G we can assume the witness (σ, µ) to be tight. We start by choosing δ ′ = δ, λ′ = λ,
(σ ′ , µ′ ) = (σ, µ). Moreover, we initially choose the domination function f for (δ, δ ′ ) to be
(
δY |X if X ′ = X and Y ′ = Y
′
′
f ((X, Y ), (X , Y )) =
0
otherwise.
Similarly, the domination function g for (λ′ , λ) is chosen to be
(
λY |X if X ′ = X and Y ′ = Y
g((X ′ , Y ′ ), (X, Y )) =
0
otherwise.
Let D be the common dominator of (λ′ , δ ′ , σ ′ , µ′ ), and w be 1/D. While there are ∅ =
6 X ⊂ Y ⊆ [n] where
µ′X,Y > 0 we apply the following. If λ′X > 0, then we reduce both λ′X and µ′X,Y by w and increase λ′Y by w.
Moreover, we choose an arbitrary Z (if any) where g((∅, X), (∅, Z)) > 0, and we reduce g((∅, X), (∅, Z)) by
12 See

Definition 5.10.

53

w and increase g((∅, Y ), (∅, Z)) by w. Otherwise (if λ′X = 0), since the witness (σ ′ , µ′ ) is tight and µ′X,Y is
increasing inflow(X), there must be some dual variable that is reducing inflow(X) back to 0. In particular,
we recognize the following three cases, which are depicted in Figure 10:
1. If there is W ⊂ X such that µ′W,X > 0, then we reduce both µ′W,X and µ′X,Y by w and increase µ′W,Y
by w.
2. If there is some Y ′ ⊃ X such that δY′ ′ |X > 0, then we reduce both µ′X,Y and δY′ ′ |X by w and increase
both δY′ ∪Y ′ |Y and µ′Y ′ ,Y ∪Y ′ by w. Moreover, we choose an arbitrary W ⊂ Z ⊆ [n] (if any) where
f ((W, Z), (X, Y ′ )) > 0, and we reduce f ((W, Z), (X, Y ′ )) by w and increase f ((W, Z), (Y, Y ∪ Y ′ )) by
w.
′
′
′
3. If there is some X ′ ⊥ X such that σX,X
′ > 0, then we reduce both µX,Y and σX,X ′ by w and increase
′
′
′
each one of σY,X ′ , µX∪X ′ ,Y ∪X ′ , µX∩X ′ ,Y ∩X ′ by w.

In all cases, we are maintaining (σ ′ , µ′ ) as a valid and tight witness. We are also maintaining that δ ′ is
dominated by δ and λ′ dominates λ. To prove that the above process terminates, consider the following
non-negative, bounded, integral function.
"
#
X
X
X
′ ′
′ def
′
′
′
φ(λ , δ , σ ) = D ·
λB (n − |B|) +
δY |X (|Y | − |X|)(n − |X|) +
σI,J (2n − |I| − |J|) .
B

X⊂Y

I⊥J

In all cases except (1), φ(λ′ , δ ′ , σ ′ ) decreases by 1. Case (1) reduces the quantity D · kµ′ k1 by 1. Initially,
we have kµ′ k1 = kµk1 . However, kµ′ k1 increases in case (3). Hence, initially case (1) can maximally be
repeated D · kµk1 consecutive times. Later on, every time we increase some µ′X,Y in cases (2) and (3), we
can immediately check whether there is some W ⊂ X where µ′W,X > 0 and if so apply case (1). By doing
so, we can amortize the cost of case (1) over cases (2) and (3).
Corollary B.4 (The total of µX,Y for X 6= ∅ is ≤ kλk1 ). For any Shannon flow inequality hλ, hi ≤ hδ, hi
with a witness (σ, µ), there exists a Shannon flow inequality hλ, hi ≤ hδ ′ , hi with a tight witness (σ ′ , µ′ )
such that δ ′ is dominated by δ and
X
∀∅ =
6 X ⊆ [n],
µ′X,Y ≤ λX .
Y ⊃X

Hence

X

∅6=X⊂Y ⊆[n]

µ′X,Y ≤ kλk1 .

(108)

Moreover, (λ, δ ′ , σ ′ , µ′ ) is rationally-compatible with (λ, δ, σ, µ).
B.1.2

Bounding the total of δY |∅

Lemma B.5 (The total of δY |∅ is ≤ n · kλk1 ). For any Shannon flow inequality hλ, hi ≤ hδ, hi with a
witness (σ, µ), there exists a Shannon flow inequality hλ, hi ≤ hδ ′ , hi with a witness (σ ′ , µ′ ) such that δ ′ is
dominated by δ and
X
∀v ∈ [n],
δY′ |∅ ≤ kλk1 .
Y ∋v

Hence

X

Y ⊆[n]

δY′ |∅ ≤ n · kλk1 .

Moreover, (λ, δ ′ , σ ′ , µ′ ) is rationally-compatible with (λ, δ, σ, µ).

54

(109)

Case (1)

Case (2)

Case (3)

Y
X ∪ X′

µ′X,Y
Y′

Y
X

δY′ ′ |X

µ′X,Y
µ′W,X

Y ∩Y

W

Y

Y
µ′X,Y
X

X ∩ X′

Y ∪Y′

Y ∪ X′
µ′X∪X ′ ,Y ∪X ′

µ′Y ′ ,Y ∪Y ′
Y′

Y

Y

′
X µW,Y

X
Y ∩Y

X′

′

X

δY′ ∪Y ′ |Y

W

′
σX,X
′

′

X ∪ X′
′
σY,X
′
Y ∩ X′

X′

µ′X∩X ′ ,Y ∩X ′
X ∩ X′

X

Figure 10: Illustration of the proof of Lemma B.3.
P
P
Proof. Fix an arbitrary variable v ∈ [n] such that Y ∋v δY |∅ > kλk1 . Define a function F : QP
+ → Q+ such
′
P
that for any vector t ∈ QP
,
F
(t)
is
a
vector
t
∈
Q
defined
as
+
+
(
tY |X + tY |X−{v} + tY −{v}|X−{v} if v ∈ X (hence v ∈ Y )
def
t′Y |X =
0
otherwise (i.e. if v ∈
/ Y or v ∈
/ X)
Note that t′ is dominated by t where the domination function f is defined as
f ((X, Y ), (X ∪ {v}, Y ∪ {v})) = tY |X ,
f ((X, Y ), (X ′ , Y ′ ))

= 0

otherwise.

Claim 1: The inequality hF (λ), hi ≤ hF (δ), hi holds for all conditional polymatroids h.
(Notice that the inequality hF (λ), hi ≤ hF (δ), hi does not necessarily have the form (66) of a Shannon
flow inequality, because it can have λ′B∪{v}|{v} > 0.) We will prove Claim 1 based on the following claim.
Claim 2: For any f ∈ {sI,J , mX,Y , cX,Y , dY,X } and any conditional polymatroid h, the following inequality holds
hF (f ), hi ≤ 0.

55

Claim 2 holds because the following inequalities hold for all conditional polymatroids.
h(I ∪ J ∪ {v}|J ∪ {v}) − h(I ∪ {v}|(I ∩ J) ∪ {v}) ≤
−h(Y ∪ {v}|{v}) + h(X ∪ {v}|{v}) ≤

0, I ⊥ J
0, X ⊂ Y

−h(Y ∪ {v}|{v}) + h(Y ∪ {v}|X ∪ {v}) + h(X ∪ {v}|{v}) ≤

0, X ⊂ Y

h(Y ∪ {v}|{v}) − h(Y ∪ {v}|X ∪ {v}) − h(X ∪ {v}|{v}) ≤

0, X ⊂ Y

To prove Claim 1, we construct a proof sequence for the original inequality hλ, hi ≤ hδ, hi, which is
possible thanks to Theorem 5.9. Consider the corresponding inequality sequence δ = δ 0 , δ 1 , . . . , δ ℓ ≥ λ such
that, for every i ∈ [ℓ], δ i = δ i−1 + wi · fi for some wi > 0 and fi ∈ {sI,J , mX,Y , cX,Y , dY,X }.
hF (fi ), hi
hF (1/wi (δ i − δ i−1 )), hi

≤ 0
≤ 0

h1/wi (F (δ i ) − F (δ i−1 )), hi
hF (δ i ), hi

(Claim 2)

≤ 0
(by linearity of F )
≤ hF (δ i−1 ), hi

which proves Claim 1.
Finally, let δ ′ = F (δ), λ′ = F (λ), f be the domination
of (δ, δ ′ ), D be the common denominator
P function
′
′
′
of (δ, δ , λ, λ ), and w = 1/D. Initially, we have
Y ∋v δY |∅ = 0. While there is B ⊆ [n] such that
′
λB∪{v}|{v} > 0, finds Y ∋ v such that f ((∅, Y ), ({v}, Y )) > 0, and reduce λ′B∪{v}|{v} , f ((∅, Y ), ({v}, Y )), and
δY′ |{v} by w, and increase λ′B∪{v}|∅ , f ((∅, Y ), (∅, Y )), and δY′ |∅ by w. Note that this update maintains that
′
′
hλ′ , hi ≤ hδ ′ , hi holds
P for′ all polymatroids h and that δ is dominated by δ. At the end, λ will dominate λ
and we will have Y ∋v δY |∅ ≤ kλk1 .
B.1.3

Bounding kµk1

Corollary B.6 (kµk1 ≤ n · kλk1 ). For any Shannon flow inequality hλ, hi ≤ hδ, hi with a witness (σ, µ),
there exists a Shannon flow inequality hλ, hi ≤ hδ ′′ , hi with a tight witness (σ ′′ , µ′′ ) such that δ ′′ is dominated
by δ and
kµ′′ k1 ≤ n · kλk1 .
(110)
In particular

∀∅ =
6 X ⊆ [n],
and

X

Y ⊃X

µ′′X,Y ≤ λX ,
X

Y ⊆[n]

X

hence

∅6=X⊂Y ⊆[n]

µ′′X,Y ≤ kλk1

µ′′∅,Y ≤ (n − 1) · kλk1 .

(111)

(112)

Moreover, (λ, δ ′′ , σ ′′ , µ′′ ) is rationally-compatible with (λ, δ, σ, µ).
Proof. First,
apply Lemma B.5 to get a Shannon flow inequality hλ, hi ≤ hδ ′ , hi where δ ′ is dominated
P we will
′
by δ and Y ⊆[n] δY |∅ ≤ n · kλk1 . Then, we apply Corollary B.4 on hλ, hi ≤ hδ ′ , hi to get another Shannon
flow inequality hλ, hi ≤ hδ ′′ , hi with a tight witness (σ ′′ , µ′′ ) such that δ ′′ is dominated by δ ′ and (111)
holds. Because δ ′′ is dominated by δ ′ , we have
X
X
δY′ |∅ ≤ n · kλk1 .
δY′′ |∅ ≤
Y ⊆[n]

Y ⊆[n]

Let inflow′′ (Z) denote the quantity inflow(Z) measured on the vector (δ ′′ , σ ′′ , µ′′ ).
X
inflow′′ (Z) = kλk1
∅6=Z⊆[n]

X

Z6=∅

′′
δZ|∅

−

X

Z6=∅

µ′′∅,Z −

X

I⊥J
I∩J=∅

56

′′
σI,J

= kλk1

X

Z6=∅

µ′′∅,Z ≤

kµ′′ k1

B.1.4

X

Z6=∅

′′
− kλk1 ≤ n · kλk1 − kλk1 .
δZ|∅

X

=

X

µ′′∅,Z +

∅6=X⊂Y ⊆[n]

Z6=∅

µ′′X,Y ≤ n · kλk1 .

Bounding kσk1 and kδk1

Corollary B.7 (2kσk1 + kδk1 ≤ n3 · kλk1 ). For any Shannon flow inequality hλ, hi ≤ hδ, hi with a witness
(σ, µ), there exists a Shannon flow inequality hλ, hi ≤ hδ ′′ , hi with a tight witness (σ ′′ , µ′′ ) such that δ ′′ is
dominated by δ and
2kσ′′ k1 + kδ ′′ k1
′′

kµ k1

n3 · kλk1 ,

≤

≤

(113)

n · kλk1 .

(114)

Moreover, (λ, δ ′′ , σ ′′ , µ′′ ) is rationally-compatible with (λ, δ, σ, µ).
Proof. We apply Corollary B.6 and obtain (δ ′′ , σ ′′ , µ′′ ). Let inflow′′ (Z) denote the quantity inflow(Z) measured on the vector (δ ′′ , σ ′′ , µ′′ ).
X
X
λB · |B|2
(115)
inflow′′ (Z) · |Z|2 ≤
B6=∅

Z⊆[n]

Define the following quantities.
Tσ′′

def

Tδ′′

def

Tµ′′

def

X

=

I⊥J

′′
σI,J
(|I ∪ J|2 + |I ∩ J|2 − |I|2 − |J|2 )

X

=

X⊂Y

X

=

X⊂Y

δY′′ |X (|Y |2 − |X|2 )
µ′′X,Y (|X|2 − |Y |2 )

Now (115) becomes
Tσ′′ + Tδ′′ + Tµ′′ ≤
Tσ′′ + Tδ′′ −

Tσ′′ + Tδ′′

≤

≤

X

µ′′∅,Y · |Y |2 +

X

µ′′∅,Y

Y 6=∅

Y 6=∅

2



n · 
|

X

∅6=X⊂Y

2

· |Y | +

X

µ′′∅,Y

Y 6=∅

{z

X

B6=∅

n3 · kλk1

B6=∅

λB · |B|2

µ′′X,Y (|X|2 − |Y |2 ) ≤

X

B6=∅

λB · |B|2



X
X
′′
′′
µB,Y +
|B| λB −
µX,B
2

Y ⊃B



 +n2 ·
}

bounded by (112)

≤

X

|

≥ 0 by (111)

X

B6=∅

|

{z

λB −

X

∅6=X⊂B

}

µ′′B,Y

∅6=X⊂B

{z

=kλk1

Claim 1: For any I ⊥ J, we have |I ∪ J|2 + |I ∩ J|2 − |I|2 − |J|2 ≥ 2.
57

+

Y ⊃B

X

µ′′X,B


}

From Claim 1, Tσ′′ ≥ 2kσk1 . Moreover, for any X ⊂ Y , |Y |2 − |X|2 ≥ 1. Therefore, Tδ′′ ≥ kδ ′′ k1 , which
proves (113).
def
def
To prove Claim 1, let a = |I \ J|, b = |J \ I|, and c = |I ∩ J|. Because I ⊥ J, we have a ≥ 1 and b ≥ 1.
|I ∪ J|2 + |I ∩ J|2 − |I|2 − |J|2 = (a + b + c)2 + c2 − (a + c)2 − (b + c)2 = 2ab ≥ 2.

B.2

Construction of a poly-sized proof sequence

Given a fixed Shannon flow inequality hλ, hi ≤ hδ, hi, Section 6 shows that the runtime of PANDA algorithm
depends on the length of the proof sequence that is being used for that inequality, thus motivating the need
to minimize that length as much as possible. Section 5.1 shows that the inequality hλ, hi ≤ hδ, hi basically
corresponds to a feasible solution to the linear program (73), whose size is O(22n ). Our aim in this section
is to construct a proof sequence for hλ, hi ≤ hδ, hi whose length is polynomial in the size of that linear
program. Hence, we are looking for a proof sequence whose length is poly(2n ).
We start by introducing a connection to flow networks in Section B.2.1, and then we present the actual
construction of a poly-sized proof sequence in Section B.2.2. The construction relies on many technical tools
among which is Edmond-Karp maximum flow algorithm [25]. It also relies on the bounds developed earlier
in Section B.1.
B.2.1

Introduction: Connection to flow networks

We will make use of the following definition. Given a Shannon flow inequality hλ, hi ≤ hδ, hi, define
n
o
def
filter(λ) = F | ∃B ∈ 2[n] where λB > 0 and B ⊆ F .
(116)

Theorem B.8 (Construction of a proof sequence using a flow network). Let hλ, hi ≤ hδ, hi be a Shannon
flow inequality with witness (σ, µ). Algorithm 2 produces a proof sequence for the inequality hλ, hi ≤ hδ, hi
with length at most 2n D(kλk1 + kσk1 ), where D is the minimum common denominator of all entries in
(λ, δ, σ).
Proof. Given (λ, δ, σ, µ), define a flow network G(λ, δ, σ, µ) = (2[n] , A) as follows. There is an arc (i.e.
directed edge) (X, Y ) ∈ A for every pair (X, Y ) for which X ⊂ Y and δY |X > 0; the capacity of (X, Y )
is δY |X . These are called up arcs. There is an arc (Y, X) for every pair (X, Y ) such that X ⊂ Y ; The
capacity of this arc is +∞. These are called down arcs. Let K denote the set of vertices Z reachable from ∅
in G(λ, δ, σ, µ). A pair (I, J) ∈ 2[n] × 2[n] is good for K if I ∈ K, J ∈ K, I ∪ J ∈
/ K, and σI,J > 0.
def P
[n]
For any set K ⊂ 2 such that filter(λ) ∩ K = ∅, define outflow(K) =
Z ∈K
/ inflow(Z). We claim that
the algorithm maintains the following two invariants:

• Invariant 1: all the quantities inflow(Z) − λZ are unchanged from one iteration to the next iteration
of the algorithm.
• Invariant 2: for every K where K ∩ filter(λ) = ∅, at the beginning of each iteration we have
X
λB ≤ outflow(K).
B∈filter(λ)

The first invariant is simple to verify: we specifically modified all the entries (λ, δ, σ, µ) to keep the flows
unchanged, except for the very last element B in line 8, where the value inflow(B) for that element B is
reduced by w. However, λB is also reduced by w at line 14, keeping inflow(B) − λB constant. The second
invariant is satisfied at the beginning of the very first iteration, and hence it is satisfied the the beginning of
every later iteration due to the first invariant.
58

Algorithm 2 Constructing a proof sequence for hλ, hi ≤ hδ, hi
Input: Inequality hλ, hi ≤ hδ, hi with witness (σ, µ)
1: ProofSeq← ()
2: For each B ∈ 2[n] do
3:
t ← min{λB , δB|∅ }; λB ← λB − t; δB|∅ ← δB|∅ − t
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

w ← 1/D
While filter(λ) 6= ∅ do
K ← {Z | Z is reachable from ∅ in G(λ, δ, σ, µ)}
If (filter(λ) ∩ K 6= ∅) then
⊲ Case 1
Find a shortest path ∅ = X0 , X1 , . . . , Xℓ = B in G(λ, δ, σ, µ) from ∅ to some B where λB > 0
For (j ← 1 to ℓ) do
⊲ Push w-flow to F
If ((Xj−1 , Xj ) is an up arc) then
Append w · cXj−1 ,Xj to ProofSeq; δXj |Xj−1 ← δXj |Xj−1 − w
else
⊲ (Xj−1 , Xj ) is a down arc
Append w · dXj−1 ,Xj to ProofSeq; δXj−1 |Xj ← δXj−1 |Xj + w
λB ← λB − w;
else If (There exists a good pair (I, J) for K) then
⊲ Case 2
Find a shortest path ∅ = X0 , X1 , . . . , Xℓ = I
For (j ← 1 to ℓ) do
⊲ Push w-flow to I
If ((Xj−1 , Xj ) is an up arc) then
Append w · cXj−1 ,Xj to ProofSeq; δXj |Xj−1 ← δXj |Xj−1 − w
else
⊲ (Xj−1 , Xj ) is a down arc
Append w · dXj−1 ,Xj to ProofSeq; δXj−1 |Xj ← δXj−1 |Xj + w

14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

Append w · dI,I∩J , then w · sI,J to ProofSeq
σI,J ← σI,J − w; δI∪J|J ← δI∪J|J + w; δI∩J|∅ ← δI∩J|∅ + w.

Return ProofSeq

We now show that the algorithm produces a valid proof sequence. At the beginning of every iteration,
the inequality hλ, hi ≤ hδ, hi is a Shannon flow inequality witnessed by (σ, µ), due to invariant 1 and
Proposition 5.4. (Note that we modify λ and the witness inside each iteration.) Hence, if we can show that
the algorithm does terminate, then the proof sequence it produces is valid. To show termination, we show
that as long as there exists a B ∈ filter(λ) for which λB > 0, then either Case 1 or Case 2 applies in the
algorithm.
Assume that at the beginning of some iteration, we have filter(λ) ∩ K =
6 ∅. Then from (116), there is some
B ⊆ F where λB > 0 and F ∈ K, and thanks to the down arc (F, B), we have B ∈ K. Now, assume that at
the beginning of some iteration (where λB > 0 for some B), we have filter(λ) ∩ K = ∅, yet there is no good
pair (I, J) for K. Then, outflow(K) ≥ λB > 0 due to Invariant 2. However, all variables δY |X , µX,Y , σI,J
contribute a non-positive amount to outflow(K), which is a contradiction.
Next, we bound the proof sequence’s length. When any one of the two cases applies, kλk1 + kσk1 was
reduced by w = 1/D, and at most 2n steps are added to the proof sequence. Hence the overall length of the
proof sequence is at most 2n D(kλk1 + kσk1 ).
B.2.2

Final construction of a poly-sized proof sequence

We start by extending the flow network that we constructed earlier in Theorem B.8. Then, we prove a lower
bound on the maximum flow of the extended network in Lemma B.10. Theorem B.12 presents an advanced
construction of a proof sequence that is “almost” polynomial. Among other technical tools, the construction
uses Edmond-Karp maximum flow Algorithm as a black-box [25]. Finally, Corollary B.14 makes the final
step and bounds the length of the proof sequence to be truly polynomial in 2n .

59

Definition B.9 (Extended flow network). Given (λ, δ, σ, µ), we define a flow network Ḡ(λ, δ, σ, µ) (which
is an extended version of the network G(λ, δ, σ, µ) defined in the proof of Theorem B.8) as follows. The set
def
of vertices of the network Ḡ is V̄ = 2[n] ∪ T ∪ {T̄ }, where T is a set that contains a new vertex TI,J for
every pair I, J ⊆ [n] such that I ⊥ J, i.e.
def

T = {TI,J | I, J ⊆ [n] ∧ I ⊥ J} ,
and T̄ is yet another vertex that represents the sink of the network. The source of the network Ḡ is ∅. The
set of arcs Ā of Ḡ consists of the following subsets:
• There is an arc (X, Y ) for every pair (X, Y ) for which X ⊂ Y ⊆ [n] and δY |X > 0; the capacity of
(X, Y ) is δY |X . These are called up arcs (as in the network G from Theorem B.8).
• There is an arc (Y, X) for every pair (X, Y ) such that X ⊂ Y ⊆ [n]; The capacity of this arc is +∞.
These are called down arcs (as in the network G).
• For ever pair I, J ⊆ [n] where I ⊥ J, σI,J > 0, there are two arcs (I, TI,J ) and (J, TI,J ) each of which
has an infinite capacity (+∞), and there is a third arc (TI,J , T̄ ) whose capacity is σI,J .
• For every ∅ 6= B ⊆ [n] where λB > 0, there is an arc (B, T̄ ) whose capacity is λB .
Lemma B.10 (Maximum flow is ≥ kλk1 ). For any (λ, δ, σ, µ), the maximum flow of the network Ḡ(λ, δ, σ, µ)
given by Definition B.9 is ≥ kλk1 .
Proof. We will use the min-cut max-flow theorem, and show that every cut has a capacity ≥ kλk1 (where
the capacity of a cut is the total capacity of arcs crossing that cut). In particular, for any C ⊂ V̄ such that
def

∅ ∈ C, T̄ ∈
/ C, and C ′ = V̄ \ C, we will show that the capacity of the C-C ′ cut is ≥ kλk1 .

• If there are X ⊂ Y ⊆ [n] where Y ∈ C and X ∈
/ C, then the down arc (Y, X) crosses the cut, hence the
cut capacity is +∞.
• Otherwise (i.e. if for any X ⊂ Y ⊆ [n] where Y ∈ C, we have X ∈ C), if there is a pair I, J ⊆ [n] where
I ⊥ J, σI,J > 0, I ∈ C and TI,J 6∈ C, then the cut capacity is also +∞.
def

def

• Otherwise, let K = C ∩ 2[n] , K′ = 2[n] \ K.

X

Z∈K′

X

X

σI,J +

I,J∈K
I⊥J, I∪J∈K′

inflow(Z) ≥

X∈K, Y ∈K
X⊂Y

δY |X
′

≥

X

λB

B∈K′

X

λB

B∈K′

However, we have 3 types of arcs crossing the cut: (TI,J , T̄ ) where I ∈ K, up arcs (X, Y ) where
X ∈ K, Y ∈ K′ , and (B, T̄ ) where B ∈ K. Hence the cut capacity is at least
X
X
X
σI,J +
δY |X +
λB ≥ kλk1 .
I∈K
I⊥J

X∈K, Y ∈K′
X⊂Y

B∈K

Lemma B.11 (Getting rid of the domination assumption). Let hδ ′ℓ′ , hi ≤ hδ ′0 , hi be an equality that has a
proof sequence ProofSeq′ of length ℓ′ , and let δ 0 be a vector that dominates δ ′0 . Then, there exists a vector
δ ℓ that dominates δ ′ℓ′ and an inequality hδ ℓ , hi ≤ hδ 0 , hi that has a proof sequence ProofSeq of length ℓ that
satisfies
ℓ = O(3n · ℓ′ ).

60

Proof. Let f be the domination function of (δ 0 , δ ′0 ). Let w′ · f ′ = δ ′1 − δ ′0 be the first proof step in ProofSeq′ ,
where w′ > 0 and f ′ ∈ {sI,J , mX,Y , cX,Y , dY,X }. Initially, let δ 1 be identical to δ 0 .
P
• If f ′ = sI,J for some I ⊥ J, then (I ∩ J, I) is dominated by a total of w′ (i.e.
(X,Y ) f ((X, Y ), (I ∩
J, I)) ≥ w′ ). We keep looking for pairs (X, Y ) ∈ P that dominate (I ∩J, I) (i.e. such that f ((X, Y ), (I ∩
J, I)) > 0), and we make those pairs (X, Y ) dominate (J, I ∪ J) instead (i.e. we reduce f ((X, Y ), (I ∩
J, I)) and increase f ((X, Y ), (J, I ∪ J)) by the same amount). We keep doing so until (J, I ∪ J) is
dominated by a total of w′ . Now, f is a domination function for (δ 1 , δ ′1 ).
• If f ′ = mX ′ ,Y ′ for some X ′ ⊂ Y ′ , then we look for (∅, Y ) that dominate (∅, Y ′ ) and we make them
dominate (∅, X ′ ) instead until (∅, X ′ ) is dominated by a total of w′ . Now, f is a domination function
for (δ 1 , δ ′1 ).
• If f ′ = dY ′ ,X ′ for some X ′ ⊂ Y ′ , then we look for (∅, Y ) that dominate (∅, Y ′ ), and we append w·mY ′ ,Y
to ProofSeq (if Y ′ 6= Y ), and reduce f ((∅, Y ), (∅, Y ′ )) by the same amount w. We keep doing so until
the total of w is equal to w′ . Now, we append w′ · dY ′ ,X ′ to ProofSeq, and increase f ((∅, X ′ ), (∅, X ′ ))
and f ((X ′ , Y ′ ), (X ′ , Y ′ )) by w′ .
• If f ′ = cX ′ ,Y ′ for some X ′ ⊂ Y ′ , then we look for (∅, X) that dominate (∅, X ′ ), and we append w·mX ′ ,X
to ProofSeq, and reduce f ((∅, X), (∅, X ′)) by the same amount w, until the total of w is equal to w′ .
def
Now, we look for (X, Y ) that dominates (X ′ , Y ′ ) 13 , and append w2 · mA,X ′ (where A = X ′ \ (Y \ X)),
w2 ·sY,A , w2 ·cA,Y ∪A , w2 ·mY ′ ,Y ∪A to ProofSeq, and we reduce f ((X, Y ), (X ′ , Y ′ )) by the same amount
w2 . We keep doing so until the total of w2 is equal to w′ . Finally, we increase f ((∅, Y ′ ), (∅, Y ′ )) by w′ .
The total number of pairs (X, Y ) where X ⊂ Y ⊆ [n] is ≤ 3n .

Theorem B.12 (Construction of a poly-sized proof sequence, modulo log D). For any Shannon flow inequality hλ, hi ≤ hδ, hi with witness (σ, µ) where kλk1 = 1, Algorithm 3 produces a proof sequence whose
length is O(log D · n3 · 26n · 3n ) = O(log D · poly(2n )), where D is the common denominator of all entries in
(λ, δ, σ, µ).
Proof. Given a flow network G with vertex set V and arc set A, Edmond-Karp algorithm [22, 25] finds the
maximum flow in time O(|V| · |A|2 ). Edmond-Karp is based on augmenting paths. In particular, it finds
O(|V| · |A|) such paths, each of which has length ≤ |V| and can be found in time O(|A|). Each path also has
a capacity c, which is the minimum capacity among arcs of that path. The total capacity of all augmenting
paths is equal to the maximum flow.
The flow network Ḡ(λ, δ ′ , σ ′ , µ′ ) constructed in Line 8 of Algorithm 3 has a vertex set V of size |V̄| =
O(22n ) and an arc set A of size |Ā| = O(22n ). By Lemma B.10, it has a maximum flow ≥ kλk1 ≥ ∆ . The
loop in Line 11 maintains the quantities inflow′ (Z) − λZ for all ∅ =
6 Z ⊆ [n] unchanged (where inflow′ (Z) is
′
′
′
the quantity inflow(Z) measured on the vector (δ , σ , µ ).). For each augmenting path in the loop, we either
′
(in Line 29). After we are done with all paths in the loop, the quantity
reduce some λB (in Line 14) or σI,J
′
kσ k1 + kλk1 is reduced by at least ∆, and a total of O(26n ) proof steps where appended to ProofSeq′0 . By
Lemma B.11, the original proof sequence ProofSeq is extended by O(26n · 3n ) proof steps.
Before the loop in line 7, we had ∆ ≤ kλk1 < 2∆ and kσ ′ k1 < n3 ∆, which both continue to hold and ∆
remains fixed as long as kλk1 remains ≥ ∆ in line 32. The maximum number of iterations the loop in line 7
can make before kλk1 drops below ∆ can be bounded as follows. At each iteration, the quantity kσ′ k1 +kλk1
is reduced by at least ∆. However, kλk1 cannot be reduced by more than ∆ in total (since ∆ ≤ kλk1 < 2∆).
Also, kσ ′ k1 cannot be reduced by more than n3 ∆ in total. Therefore the maximum number of iterations
before kλk1 drops below ∆ is bounded by n3 + 1.
Every time kλk1 drops below ∆, ∆ gets divided by 2 (or a higher power of 2). The initial ∆ in line 6
was ≤ D. Therefore, the maximum number of times kλk1 can drop below ∆ is O(log D).
13 From

Definition B.1, if f ((X, Y ), (X ′ , Y ′ )) > 0, then Y ′ \ X ′ ⊆ Y \ X and X ′ ⊇ X.

61

Algorithm 3 Constructing a poly-sized proof sequence for hλ, hi ≤ hδ, hi

Input: Inequality hλ, hi ≤ hδ, hi with witness (σ, µ), where kλk1 = 1
1: ProofSeq← ()
2: D ← least-common-denominator((λ, δ, σ, µ)) ⊲ D is the least common denominator of all entries
3: λ ← D · λ; δ ← D · δ; σ ← D · σ; µ ← D · µ
⊲ Now, all entries are integers
′
′
4: Find hλ, hi ≤ hδ , hi with witness (σ ′ , µ′ ) where δ is dominated by δ and kσ ′ k1 ≤ 21 n3 kλk1
5:
⊲ Corollary B.7

6: ∆ ← max 2i | 2i ≤ kλk1 and i ∈ N
⊲ Now, we have ∆ ≤ kλk1 < 2∆ and kσ ′ k1 < n3 ∆
7: While kλk1 > 0 do
8:
Construct Ḡ(λ, δ ′ , σ ′ , µ′ )
⊲ Definition B.9
9:
P ←Edmond-Karp(Ḡ(λ, δ ′ , σ ′ , µ′ )).
⊲ Apply Edmond-Karp algorithm for maximum flow
10:
⊲ P is a collection of augmenting paths
11:
For each augmenting path ∅ = X0 , X1 , . . . , Xℓ = T̄ with capacity w′ in P do
12:
For j ← 1 to ℓ do
13:
If (Xj−1 , Xj ) = (B, T̄ ) for some ∅ 6= B ⊆ [n], λB > 0 then
′
′
14:
λB ← λB − w′ ; δB|∅
← δB|∅
− w′
′
15:
t←w
16:
While t > 0 do
17:
Find Y ⊇ B such that δY |∅ > 0
⊲ Possible because δ dominates δ ′
18:
w ← min{t, δY |∅ }; t ← t − w; δY |∅ ← δY |∅ − w
19:
If Y ⊃ B then
20:
Append w · dY,B to ProofSeq; δY |B ← δY |B + w
21:
22:

23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

else
δ ′0 ← δ ′ ; ProofSeq′0 ← (); δ 0 ← δ
If (Xj−1 , Xj ) is an up arc then
Append w′ · cXj−1 ,Xj to ProofSeq′0 ; δ ′ ← δ ′ + w′ · cXj−1 ,Xj
else If (Xj−1 , Xj ) is a down arc then
Append w′ · dXj−1 ,Xj to ProofSeq′0 ; δ ′ ← δ ′ + w′ · dXj−1 ,Xj
else If (Xj−1 , Xj ) = (I, TI,J ) for some I, J ⊆ [n], I ⊥ J, σI,J > 0 then
Append w′ · dI,I∩J , then w′ · sI,J to ProofSeq′0 ;
δ ′ ← δ ′ + w′ · dI,I∩J + w′ · sI,J
′
′
′
σI,J ← σI,J − w
⊲ Now, ProofSeq′0 is a proof sequence for hδ ′ , hi ≤ hδ ′0 , hi, and δ 0 dominates δ ′0
Find δ dominating δ ′ and a proof sequence ProofSeq0 for hδ, hi ≤ hδ 0 , hi ⊲ Lemma B.11
Append ProofSeq0 to ProofSeq
If kλk1 < ∆ then
Find hλ, hi ≤ hδ ′ , hi with witness (σ ′ , µ′ ) where
δ ′ is dominated
by δ and kσ′ k1 ≤ 21 n3 kλk1
⊲ Corollary B.7
 i i
∆ ← max 2 | 2 ≤ kλk1 and i ∈ N
⊲ Now, we have ∆ ≤ kλk1 < 2∆ and kσ ′ k1 < n3 ∆

Return ProofSeq

Proposition B.13 (log D is polynomial). Given an optimization problem of the form (67), if the objective
value is positive and bounded, then there exists a vector λ = (λB )B∈B satisfying the following conditions:
(a) kλk1 = 1.
(b) The optimization problem (67) has the same optimal objective value as the linear program (68) (using
this λ).
(c) The linear program (68) has an optimal dual solution (δ ∗ , σ ∗ , µ∗ ) such that the common denominator

62

D of all entries in (λ, δ ∗ , σ ∗ , µ∗ ) satisfies
D ≤ (2n )!
Proof. This proposition is a minor extension to Lemma 5.3, specialized to the optimization problem (67).
In particular, when we pick an optimal dual solution (z∗ , y∗ ) to (72), we choose (z∗ , y∗ ) to be an extreme
point of the following polyhedron
{(z, y) | AT y ≥ Cz, 1Tp z ≥ 1, (z, y) ≥ 0}.
In (67), all entries of A and C are in {1, 0, −1}. By Cramer’s rule, the common denominator D∗ of all entries
in (z∗ , y∗ ) is (the absolute value of) the determinant of an m × m matrix whose entries are all in {1, 0, −1}.
Hence, D ≤ m!.
Corollary B.14 (Construction of a poly-sized proof sequence). Given any optimization problem of the form
(67) where the optimal objective value OBJ is positive and bounded, there exists a Shannon flow inequality
hλ, hi ≤ hδ, hi satisfying the following conditions:
P
•
(X,Y ) δY |X nY |X ≤ OBJ.
• λY |X = 0 for all (X, Y ) ∈ P where X 6= ∅ or Y ∈
/ B.

• hλ, hi ≤ hδ, hi has a proof sequence of length O(n4 · 27n · 3n ) = O(poly(2n )).

63

