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

1 INTRODUCTION

• The paper answers four questions arising from different research threads and establishes connections among those threads.The introduction frames those connections around information theory and database theory.Source: §1 · p. 1

1.1 Output-Size Bound for Full Conjunctive Qeries

• For queries with cardinality and functional-dependency constraints, the polymatroid bound can exceed the entropic bound by at least N^s for a query with output size Θ(s).This establishes that the polymatroid bound is not tight in this setting.Source: §1.1 · p. 3

1.2 Size Bound for Disjunctive Datalog Rules

• For arbitrary disjunctive datalog rules, the entropic output-size bound is asymptotically tight, but the polymatroid bound can be arbitrarily loose even with only cardinality constraints and identical cardinality upper bounds.The polymatroid bound is not tight even when every constraint is a cardinality constraint.Source: §1.2 · p. 4
• Table 1 summarizes entropic and polymatroid size bounds and their tightness for full conjunctive queries and disjunctive datalog rules under cardinality, functional-dependency, and degree constraints.The table distinguishes bounds for cardinality constraints alone, cardinality constraints with functional dependencies, and the more general degree-constraint case.Source: §1.2 · p. 5, Table 1 · p. 5

1.3 Algorithm evaluating disjunctive datalog rules

• PANDA computes any model rather than necessarily a minimal one; this permits a runtime proportional to an output-size bound even for Boolean queries with trivially bounded rule output.For non-full conjunctive queries, a model of the corresponding rule does not in general answer the query; Boolean queries illustrate why a rule-output bound alone cannot guarantee constant-time query answering.Source: §1.3 · pp. 5–6
• PANDA computes a model of a disjunctive datalog rule under degree constraints within the runtime predicted by its polymatroid bound.The algorithm derives from proof sequences that establish the bound and guide its computation.Source: §1.3 · p. 6
• Theorem 5.9 shows that Shannon-flow inequalities can be proved by sequences of four rewrite rules, while omitting decomposition leaves the proof system incomplete.Each rewrite preserves or decreases the terms for every polymatroid; prior work found an inequality that the three remaining rules plus submodularity could not prove.Source: §1.3 · pp. 6–7

1.4 Towards Optimal Algorithms for Conjunctive Qeries

• Worst-case optimal runtimes are insufficient when a query’s intrinsic cost differs from its worst-case output size, motivating output-sensitive algorithms that minimize the exponent for Boolean queries.The discussion says the Boolean-query focus extends to other conjunctive and aggregate queries.Source: §1.4 · pp. 8–9
• PANDA computes queries with runtime exponent da-subw(Q), which is bounded by da-fhtw(Q).The paper generalizes fractional hypertree width and submodular width to arbitrary degree constraints and calls the resulting measures degree-aware fractional hypertree width and degree-aware submodular width.Source: §1.4 · p. 10
• The framework and PANDA results extend to proper conjunctive queries and aggregate queries, beyond the full and Boolean cases presented for accessibility.Aggregate queries are described in the sense of FAQ-queries over one semiring.Source: §1.4 · p. 10
• PANDA interprets each proof inequality as a disjunctive datalog rule, and the resulting rules ensure every four-cycle is fully included in some tree.Taking the disjunction of the two tree results then computes the query correctly.Source: §1.4 · pp. 11–12

2 BACKGROUND AND RELATED WORK

• The paper works with non-negative monotone set functions and distinguishes modular, subadditive, submodular, and entropic functions.It uses hypergraphs to represent conjunctive queries, with input relations supported on hyperedges.Source: §2 · p. 12

2.1 Bounds for queries with cardinality constraints

• Because computing a full conjunctive query takes at least as long as producing its answer, upper bounds on answer size are of interest.The output-size discussion concerns natural joins and their worst-case output size.Source: §2.1.1 · p. 13

2.1.1 Bounds on the worst-case output size.

• The vertex, integral edge-cover, and fractional edge-cover bounds form a hierarchy; the AGM bound is asymptotically tight and has worst-case-optimal algorithms [13].Known algorithms run in ˜O(2^ρ*(Q,(N_F)_F∈E)) time [1, 43, 44, 48].Source: §2.1.1 · p. 14
• For unbounded-arity inputs, submodular width is the best tractability parameter achievable in FPT unless the exponential time hypothesis fails.The hierarchy is strict: query classes can have bounded submodular width but unbounded fractional hypertree width.Source: §2.1.2 · pp. 14–15

2.1.3 Tree decompositions and their widths.

• Tree decompositions support dynamic programming, but fixing one decomposition can force an algorithm to incur its worst-case cost; interleaving data partitioning and decomposition motivates adaptive and submodular width.Marx showed adw(H) ≤ subw(H) ≤ fhtw(H), and subw(H) = O(adw(H)^4), and gave a Boolean-query algorithm with data-complexity time O(poly(N^subw(H))).Source: §2.1.3 · pp. 15–16
• The paper’s later framework unifies traditional, adaptive, and submodular width through information theory and extends to more general input-query constraints.Checking whether a hypergraph has fractional or generalized hypertree width at most 2 is NP-hard.Source: §2.1.3 · pp. 15–16
• The section notes an unbounded gap between subw(H) and fhtw(H) for some class, while minimal decompositions of an n-cycle correspond to the (n−1)th Catalan number.The n! estimate is described as an overestimate, even for graphs with exponentially many minimal non-redundant tree decompositions.Source: §2.1.3 · p. 16
• For a hypergraph with n vertices, there are at most n! non-dominated non-redundant tree decompositions, each with at most n bags, so their number is O(1) in data complexity.Source: §2.1.3 · p. 16

2.2 Bounds for queries with FD and degree constraints

• Degree bounds and functional dependencies arise in practice from input statistics, primary keys, built-in predicates, and user-defined predicates such as bounded edit distance.Source: §2.2 · p. 17
• A degree constraint bounds Y-extensions of X through a guarding relation; cardinality constraints and functional dependencies are special cases.Source: §2.2 · p. 17
• Prior work gives output-size bounds, and its CSMA algorithm solves Boolean queries with known degree constraints in ~O(N + poly(log N) · 2^DAPB(Q)) time.Source: §2.2 · p. 17

3.1 Basic observations

• Modularization preserves the optimum on any chosen variable set while replacing a feasible function with a modular one that still satisfies the cardinality constraints.The lemma applies to a not-necessarily full conjunctive query with hypergraph H and cardinality constraints.Source: §3.1 · pp. 17–18
• For full conjunctive queries, the AGM bound can be computed in polynomial time in query complexity, whereas computing the integral edge-cover bound is NP-hard.The text notes that the latter is a worse bound, despite using the more relaxed class of set functions.Source: §3.1 · p. 21

3.2 The polymatroid size bound is not tight!

• The separating inequality holds for entropic functions but not for some polymatroids, underpinning the gap between the two bounds.The paper identifies this as a Zhang–Yeung inequality.Source: §3.2 · pp. 21–22
• The example separates entropic and polymatroid bounds: the entropic bound gives |Q| ≤ N^(4−1/11), while a feasible polymatroid reaches N^4, a ratio of N^(1/11).The construction uses cardinality constraints and functional dependencies.Source: §3.2 · p. 22
• Taking a cross-product of 11s variable-disjoint copies of the Zhang-Yeung query amplifies the gap to N^s.Source: §3.2 · p. 22

4.1 The entropic bound for disjunctive datalog

• Lemma 4.1 states an entropic size bound for disjunctive datalog rules on database instances, with degree constraints in scope.The supplied passage fragments do not include the bound’s formula.Source: §4.1 · p. 23

4.2 The entropic bound is asymptotically tight under degree constraints

• The section proves that LogSizeBound is asymptotically tight for disjunctive datalog rules with degree constraints HDC.The proof adapts a group-characterizable entropy function into a database instance.Source: §4.2 · p. 23
• Lemma 4.5 considers every 0 < ε < 1 and guarantees a scale factor k and database instance satisfying the scaled-up constraints HDC × k.The lemma’s stated setup requires the supremum over HDC to be at least 1.Source: §4.2 · p. 25
• For the degree-constraint tightness argument, the proof bounds max_B |T_B| by restricting T_B to R_B and tracking which tuples each relation tuple covers.It uses the fact that no two tuples in R_B cover the same tuple in Q.Source: §4.2 · p. 27

4.3 The polymatroid bound for disjunctive datalog is not tight

• The polymatroid bound for disjunctive datalog is not tight, even when input constraints are only cardinality bounds and all upper bounds are identical.The examples use polymatroids satisfying the input constraints to establish lower bounds of 4 log N on the polymatroid bound.Source: §4.3 · pp. 29, 31

5 SHANNON FLOW INEQUALITIES

• Shannon flow inequalities are inequalities that hold for every polymatroid, with their target sets specified as part of the definition.For disjunctive datalog rules, degree constraints can serve as the conditional terms in these inequalities.Source: §5 · p. 31, §5.1 · p. 32

5.1 Motivations

• Farkas’s lemma characterizes a Shannon flow inequality by whether its coefficients can be extended to a feasible solution of the dual LP.When the degree-constraint coefficients are optimal, the inequality yields the output upper bound equal to the primal and dual optimal objective value.Source: §5.1 · p. 34

5.2 Proof sequences

• The revised definition enables a simpler PANDA algorithm than CSMA and constructs proof sequences for general Shannon flow inequalities, beyond the output-inequality special case in.Source: §5.2 · p. 34
• The refined proof-sequence system is complete, and its sequences can be bounded polynomially in the size of LP (81), rather than doubly exponentially as in.Source: §5.2 · p. 34
• A proof sequence has length at most D(3||σ||₁ + ||δ||₁ + ||μ||₁), where D is the minimum common denominator of the inequality and witness entries.Source: §5.2 · p. 36
• The construction inductively reduces an integer measure of the inequality and witness, then prefixes one or two proof steps to the shorter sequence.Source: §5.2 · p. 36
• The entire proof sequence can be constructed in time polynomial in the initial measure ℓ(λ, δ, σ, μ).Source: §5.2 · p. 37

Appendix B.2 presents an alternative construction of a proof sequence with an even smaller length bound.

• Any witness can be made tight by increasing μ_∅,Z by inflow(Z) − λ_Z wherever inflow(Z) exceeds λ_Z.This adjustment makes inflow(Z) = λ_Z for every Z.Source: Appendix B.2 · p. 37
• Given a Shannon flow inequality with ||λ||1 > 0 and δ_Y|∅ > 0, the truncation lemma constructs modified witness vectors using step size 1/D, where D is a common denominator.The lemma requires D to be a common denominator of the entries in the original vectors (λ, δ, σ, μ).Source: Appendix B.2 · p. 37
• Starting from a tight witness, the construction begins with inflow'(Z) − λ'_Z = 0 at every point, then moves the deficit from Y to new points.At each move, the new point is the only point with a deficit; the process continues unless that point is ∅.Source: Appendix B.2 · pp. 37–38
• The procedure terminates because each move reduces 2||σ'||1 + ||δ'||1 + ||μ'||1 by w, and the resulting witness establishes a Shannon flow inequality.The construction also never increases entries of λ' or δ', and it strictly reduces ||δ'||1.Source: Appendix B.2 · p. 38

6 THE PANDA ALGORITHM

• PANDA computes a model of a disjunctive datalog rule in time predicted by its polymatroid bound.The section identifies Theorem 1.7 as its main result.Source: §6 · p. 38

6.1 The algorithm

• Proof sequences for Shannon flow inequalities guide PANDA as symbolic instructions, with each step prompting computation and, when needed, disjunctive datalog subproblems and intermediate relations.Source: §6.1 · p. 40
• PANDA keeps each intermediate relation within ˜O(2^OBJ) size, and the number of subproblems is polylogarithmic in the input size.Source: §6.1 · pp. 40–41
• When N_X|∅ · N_W|Z ≤ 2^OBJ, PANDA computes the join table in Õ(2^OBJ) time and size; above that threshold, it skips the join and restarts.The join branch extends the degree constraints with the table’s size; the restart branch updates the inequality and reduces the potential.Source: §6.1 · p. 42
• Invariant (I4) holds at the beginning of PANDA.Source: §6.1 · p. 43

6.2 Analysis

• Without Case 4b, PANDA takes at most ℓ steps, each costing Õ(2^OBJ) or spawning O(OBJ) subproblems, for total time Õ(poly(OBJ) · 2^OBJ).When Case 4b occurs, the restarted subproblem has a shorter proof sequence, reducing its length by at least one.Source: §6.2 · p. 43
• In data complexity, OBJ is O(log N), since it equals the polymatroid bound, which is bounded by the vertex bound log(N^n) for constant n.Source: §6.2 · p. 43

7 DEGREE-AWARE WIDTH PARAMETERS AND ALGORITHMS

• PANDA evaluates queries under general degree constraints within the runtime predicted by the new degree-aware widths.The section develops this use of PANDA to prove Theorem 1.9.Source: §7 · p. 44

7.1 Minimax and maximin widths

• The minimax/maximin framework captures traditional widths; without FDs or degree constraints, 1 + tw(H) ≥ ghtw(H) ≥ fhtw(H) ≥ subw(H) ≥ adw(H), with every consecutive gap unbounded.Source: §7.1 · pp. 45, 47

7.2 New width parameters

• Degree-aware parameters generalize fhtw and subw and have entropic counterparts; eda-fhtw and da-subw are incomparable, and each stated inequality can have arbitrarily large gaps.Source: §7.2 · pp. 47–48
• 3/2 log N is both da-subw(C4) and eda-subw(C4), while 2 log N is both da-fhtw(C4) and eda-fhtw(C4), with only input-size bounds.Source: §7.2 · p. 48
• With only edgedomination constraints, da-subw(Q) = subw(Q) = O(adw4(Q)) = O(eda-subw4(Q)).The passage also states that bounded eda-subw implies a further property, but the statement is truncated in the supplied text.Source: §7.2 · p. 48

7.3 Summary of known bounds and width parameters

• The bounds are organized by entropy approximation, input constraints, and query-plan sophistication, with coordinate-wise smaller bounds no greater than larger ones.The query-plan axis ranges from joining everything in one bag, through computing a tree decomposition, to adapting the plan to the input instance.Source: §7.3 · p. 49

7.4 Achieving degree-aware width parameters

• PANDA can evaluate full or Boolean conjunctive queries using the degree-aware polymatroid size bound, degree-aware fractional hypertree width, or degree-aware submodular width.The section introduces these increasingly complex applications of PANDA; it also notes that Section 8 treats other conjunctive and aggregate queries.Source: §7.4 · p. 49

7.4.1 Conjunctive query with degree constraints.

• A full or Boolean conjunctive query with degree constraints can be solved using PANDA in time ˜O(N + poly(log N) · 2^DAPB(Q)).PANDA’s bound is obtained from a Shannon flow inequality for an optimal dual solution; the output is then semijoin-reduced against the input relations.Source: §7.4.1 · p. 51

7.4.2 Achieving the degree-aware fractional hypertree width.

• A full or Boolean conjunctive query with degree constraints can be solved using PANDA in time ˜O(N + poly(log N) · 2^da-fhtw(Q) + |output|).The algorithm uses a tree decomposition attaining da-fhtw, applies PANDA to compute a superset for each bag, and joins the semijoin-reduced tables.Source: §7.4.2 · p. 52

7.4.3 Achieving the degree-aware submodular width.

• A full or Boolean conjunctive query with degree constraints DC can be solved using PANDA in time ˜O(N + poly(log N) · 2^da-subw(Q) + |output|).The proof introduces an auxiliary minimax-style lemma to reformulate the degree-aware submodular-width bound.Source: §7.4.3 · pp. 52–53

7.4.3 Achieving the degree-aware submodular width

• For each valid B, solving a linear program yields a dual Shannon flow inequality that guides PANDA to construct tables covering every output tuple through some B-projection.The maximum solution over the collection of linear programs computes da-subw(Q).Source: §7.4.3 · p. 53
• For each tuple of selected sets (B1, . . . , BM), a tree decomposition exists whose bags are among those sets, enabling computation through an associated join query.The procedure is repeated for each such tuple, a query-complexity quantity.Source: §7.4.3 · p. 54
• Semijoin-reducing each table with every input relation before joining yields runtime ˜O(2^da-subw(Q) + |J(B1, . . . , BM) ∩ Q|).Without semijoin reduction, the stated runtime instead depends on the size of the full join.Source: §7.4.3 · p. 54

8 DISCUSSIONS

• Whether algorithms can match the entropic output-size bound for queries with functional dependencies or degree constraints remains an open question.The discussion also asks whether the class of queries with functional dependencies for which the bound can be met can be extended beyond prior results.Source: §8 · p. 54
• PANDA already achieves eda-subw and eda-fhtw on an example, while designing algorithms for disjunctive datalog rules that match entropic bounds remains a direction for future work.The discussion names the example as the 4-cycle query.Source: §8 · p. 54
• The discussion raises open algorithmic questions about meeting bounds that involve both HDC and other constraints.It also identifies removing PANDA’s polylog factor as an open problem.Source: §8 · p. 55
• For queries with only cardinality constraints, da-subw is O(eda-subw^4), so bounded entropic submodular width and bounded submodular width are equivalent.Whether this relationship holds with functional dependencies or degree bounds remains open.Source: §8 · p. 55
• The formally stated algorithmic results apply to full and Boolean conjunctive queries, while the discussion considers extensions to proper conjunctive and aggregate queries.For general conjunctive queries, it proposes restricting width computations to free-connex tree decompositions, where non-free variables are eliminated first.Source: §8 · p. 55
• The free-connex adaptation yields the da-fhtw runtime for FAQ-SS queries, but achieving da-subw for general FAQ-SS queries remains open.The paper does not present this broader treatment, concentrating instead on Boolean and full conjunctive queries.Source: §8 · p. 55

A MISSING DETAILS FROM THE INTRODUCTION

• The section proves correctness for the three bounds before establishing tightness for each.It introduces the correctness argument and then separately introduces the tightness proofs.Source: A MISSING DETAILS FROM THE INTRODUCTION · p. 57
• |Q| ≤ N^2 is tight on an instance with R12 = R34 = [N] × and R23 = R41 = [1] × [N].The section presents this as the tightness instance for bound (a).Source: A MISSING DETAILS FROM THE INTRODUCTION · p. 57
• Bound (c), obtained from bound (b) by setting D = 1, is asymptotically tight on an instance whose output is {(i,i,j,k) | i,j,k ∈ [K]}.The cited instance uses R12 = {(i,i) | i ∈ [K]} and R23 = R34 = R41 = [K] × [K].Source: A MISSING DETAILS FROM THE INTRODUCTION · p. 57
• |Q| ≤ N^3/2 · D is tight on an instance generalized from the preceding one to 1 ≤ D ≤ K.This is the tightness instance for bound (b).Source: A MISSING DETAILS FROM THE INTRODUCTION · p. 57

B MORE ON SHANNON-FLOW INEQUALITIES AND PROOF SEQUENCES

• The section presents additional results on Shannon-flow inequalities and proof sequences.The excerpt does not specify the additional results.Source: B MORE ON SHANNON-FLOW INEQUALITIES… · p. 57

• The construction replaces an inequality and witness with a “just as good” version having lower ∥σ∥1, ∥δ∥1, and ∥μ∥1.Source: §B.1 · p. 57
• Bounding ∥μ∥1 also bounds ∥δ∥1 and ∥σ∥1, motivating minimization of these quantities because PANDA’s runtime depends on proof-sequence length.Source: §B.1 · pp. 57–58
• The total nonempty-X monotonicity weight is at most ∥λ∥1, while the total δY|∅ weight is at most n·∥λ∥1.Source: §B.1 · p. 59
• A tight replacement witness can have ∥μ∥1 ≤ n·∥λ∥1, with its δ′ dominated by δ and the replacement rationally compatible with the original.Source: §B.1 · p. 61

• The proof first uses Lemma B.5 to bound δY|∅, then Corollary B.4 to obtain a tight witness for a further replacement inequality.Source: In particular · p. 61
• 2∥σ∥1 + ∥δ∥1 ≤ n^3·∥λ∥1 for a replacement inequality with a tight witness and dominated δ′.The replacement is rationally compatible with the original inequality and witness.Source: In particular · p. 62
• For disjoint I and J, the set-cardinality inequality is at least 2, yielding Tσ′′ ≥ 2∥σ∥1; the delta terms are bounded using |Y|² − |X|² ≥ 1.Source: In particular · p. 63

• The proof-sequence length is the target for minimization because PANDA’s runtime depends on it.Source: §B.2 · p. 63
• The target is a proof sequence polynomial in the linear-program size, specifically with length poly(2^n).Section 5.1 relates the inequality to a feasible solution of a linear program of size O(2^(2n)).Source: §B.2 · p. 63
• The construction introduces a connection to flow networks and uses the Edmond-Karp maximum flow algorithm together with bounds developed earlier.Source: §B.2 · p. 63

B.2.1 Introduction: Connection to flow networks

• Algorithm 2 constructs a proof sequence of length at most 2nD(||λ||_1 + ||σ||_1) for a Shannon flow inequality with witness (σ, μ).Each iteration reduces ||λ||_1 + ||σ||_1 by 1/D and adds at most 2n steps.Source: §B.2.1 · pp. 63, 65

B.2.2 Final construction of a poly-sized proof sequence

• Algorithm 3 uses Edmond-Karp [23, 26] as a black box in constructing the poly-sized proof sequence.The algorithm applies it to the extended flow network.Source: §B.2.2 · pp. 65–67
• The extended flow network in Definition B.9 has maximum flow at least ||λ||_1.The proof uses the min-cut max-flow theorem to establish the lower bound.Source: §B.2.2 · p. 65
• Lemma B.11 removes the domination assumption by constructing a proof sequence for the target inequality from one for a dominated vector.The construction adjusts the domination function as it translates proof steps.Source: §B.2.2 · p. 66
• For any Shannon flow inequality ⟨λ, h⟩ ≤ ⟨δ, h⟩ with witness (σ, μ) and ||λ||1 = 1, Algorithm 3 produces a proof sequence of length O(log D·poly(2^n)).D is the common denominator of all entries in (λ, δ, σ, μ).Source: §B.2.2 · p. 66

B.2.1 Introduction: Connection to flow networks.

• The constructed flow network has a maximum flow at least ∥λ∥₁ ≥ Δ, and its vertex and arc sets each have size O(2^{2n}).The loop’s reductions preserve the quantities inflow′(Z) − λ_Z for every nonempty Z ⊆ [n].Source: §B.2.2 · p. 67
• Each iteration reduces ∥σ′∥₁ + ∥λ∥₁ by at least Δ, and the proof sequence gains O(2^{6n} · 3^n) steps across the bounded iterations and scaling phases.There are at most n^3 + 1 iterations before ∥λ∥₁ falls below Δ, and at most O(log D) such drops; each phase extends the proof by O(2^{6n} · 3^n) steps.Source: §B.2.2 · pp. 67–68
• For a positive bounded objective in optimization problem (75), there exists a Shannon flow inequality whose proof sequence has length O(n^4 · 2^{7n} · 3^n) = O(poly(2^n)).The inequality also satisfies the corollary’s stated bound on the sum of its δ-weighted degree terms.Source: §B.2.2 · p. 68