Source-linked AI summary
Size Bounds for CQs Under Acyclic Constraints
Stefan Mengel, Andrei Romashchenko
TL;DR
The paper asks whether the entropic and computable polymatroid bounds remain equal for conjunctive queries with acyclic functional dependencies and projections. It constructs an acyclic example with a polynomial gap and identifies a topological-order condition under which equality is preserved.
Problem
The entropic bound is asymptotically tight but not known computable, while its computable polymatroid relaxation is generally not tight; the paper studies this trade-off under acyclic functional dependencies and projections.
Method
The paper transforms a known cyclic-gap construction into one with acyclic functional dependencies by introducing copied variables and additional dependencies, then identifies when tightness is preserved.
Results
A polynomial gap separates the polymatroid and entropic bounds for some conjunctive queries with acyclic functional dependencies and projections, while the bounds coincide when output variables form a suitable topological prefix.
Takeaways & Limitations
Projections fundamentally change the behavior of acyclic functional-dependency queries: polymatroid bounds are not generally tight, but remain tight for a natural topological class.
Takeaways & Limitations
The entropic bound is not known to be computable, and tighter bounds may require a better understanding of Shannon entropy.
Abstract
from arXiv · showhide
We study size bounds for conjunctive query (CQ) results which in recent years have played a crucial role in database theory. In particular, we compare the so-called entropic bound which is known to be asymptotically tight but not known to be computable, and its computable relaxation called the polymatroid bound, which is generally not tight. We focus here on conjunctive queries under acyclic functional dependencies. These queries are known to be well-behaved in the sense that, in the case without projections, both bounds coincide. We show that this picture changes when projections are allowed: in this case, even for acyclic functional dependencies, there is in general a polynomial gap between the two bounds. We complement this negative result by showing a special case for which the polymatroid bound is tight under acyclic functional dependencies and projections that is characterized by the position of the output variables in a topological order of the query variables.
1 Introduction
The paper examines whether entropic and polymatroid bounds coincide for conjunctive queries with acyclic functional dependencies when projections are allowed. It finds a polynomial separation in general, while identifying a topological-order condition preserving tightness.
- Motivation: Cardinality estimation bounds influence query optimization and evaluation runtimes, motivating provably correct bounds in database theory.The bounds use input statistics such as relation cardinalities, degree information, and functional dependencies.
- Existing bounds: The AGM-bound is tight under cardinality constraints, supporting worst-case optimal join algorithms whose runtime scales with the largest possible query answer.This tightness explains why algorithms proportional to the AGM-bound are worst-case optimal.
- Existing bounds: The entropic bound is asymptotically tight, but its computability is unknown because the entropic cone is not well understood.This motivates computable relaxations despite their potential looseness.
- Existing bounds: The polymatroid bound is computable through linear programming and supports the PANDA algorithm, but can exceed the entropic bound by a polynomial factor.Consequently, PANDA is generally not worst-case optimal, and no worst-case optimal algorithm is known in the relevant setting.
- Research question: Projection is common in practice, yet prior positive results for acyclic constraints concerned queries without projections, where all variables are output variables.The paper therefore asks whether the two bounds still coincide with projections.
- Contributions: A query with acyclic functional dependencies can have a polynomial gap between the polymatroid and entropic bounds, so the polymatroid bound is not generally tight.This contrasts with the setting without projections.
- Contributions: The construction starts from cyclic functional dependencies with a known gap and untangles them by adding variables and functional dependencies.The added variables take the roles of variables involved in violated cycles.
- Contributions: The two bounds coincide when output variables precede projected variables in a suitable topological order.This identifies a class of acyclic functional-dependency queries with projections for which tightness is preserved.
2 Preliminaries
The preliminaries define conjunctive queries, projections, functional dependencies, acyclicity, polymatroids, entropy, and the two query-size bounds. The entropic bound is tight but not known computable, while the polymatroid bound is a computable upper bound.
- Conjunctive queries: A conjunctive query is a conjunction of relational atoms, with output variables explicit and projected variables existentially quantified.The query result Q(D) is evaluated under set semantics, and |Q(D)| denotes its number of tuples.
- Functional dependencies: Functional dependencies have the form W → U, must be covered by an atom, and permit at most one U-extension for each assignment to W.A database is consistent with a dependency set when every dependency is satisfied.
- Functional dependencies: A dependency set is acyclic when its directed graph has variables as vertices and dependency-induced edges forming a directed acyclic graph.The example query has an acyclic dependency set under a suitable topological order.
- Polymatroids and entropy: Polymatroids are nonnegative set functions that are monotone, submodular, and zero on the empty set.The notation ΓY denotes the set of polymatroids over variable set Y.
- Polymatroids and entropy: An entropic function maps variable subsets to joint Shannon entropies, and every entropic function is a polymatroid.Thus entropic functions form a subset of the polymatroids used in the relaxation.
- Polymatroids and entropy: Conditional entropy is represented for a polymatroid by h(A | B) := h(AB) − h(B), with chain-rule and diminishing-conditional-entropy properties.These identities support the entropy calculations used later in the paper.
- Size bounds: The bound constraints require h(Xi) ≤ log(Ni) for each atom and h(V|U) = 0 for every functional dependency U → V.Here X is the output-variable set and Y is the set of all query variables.
- Size bounds: The entropic bound maximizes over entropic functions, whereas the polymatroid bound maximizes over the larger polymatroid class.The polymatroid bound is computable through linear programming and gives an upper bound on query-result size.
3 Separating the Entropic and Polymatroid Bound
The paper constructs acyclic functional dependencies with projections where the entropic bound is polynomially smaller than the polymatroid bound. It achieves this by untangling cyclic dependencies with copied variables while preserving the relevant polymatroid lower bound.
- Theorem 9 establishes a conjunctive query with acyclic functional dependencies whose entropic bound is polynomially smaller than its polymatroid bound.
- Base instance: The construction starts from the Zhang–Yeung query, whose cyclic constraints already exhibit a gap between the two bounds.
- The Entropic Bound: The entropic estimate follows by combining an information-theoretic inequality with functional-dependency, cardinality, and polymatroid constraints in a linear program.
- Untangling the functional dependencies: Algorithm 1 untangles cyclic dependencies by introducing copied variables, fresh linking atoms, and dependencies from each original variable to its copy.
- Untangling the functional dependencies: The resulting dependencies are acyclic, because newly introduced variables occur only in dependency heads and offended constraints are eliminated during processing.
4 A Tight Case
When output variables form a prefix in a topological order of acyclic functional dependencies, the polymatroid and entropic bounds coincide despite projections. The proof reduces projected queries to an unprojected query while preserving the relevant bound.
- Prefix condition: A query’s output variables form a prefix when some topological order places them before every non-output variable.This condition is defined relative to the dependency graph of the functional dependencies.
- Main result: Theorem 17 states that, under this prefix condition, the polymatroid bound is tight for conjunctive queries with cardinality constraints and functional dependencies.The result applies when projections are present, provided the output variables form a prefix with respect to the dependencies.
- Reduction: The proof constructs an output-restricted query by syntactically removing non-output variables from the query’s atoms and adapting its constraints.The transformed query retains the cardinality constraints and induces restricted functional dependencies.
- Reduction: Lemma 20 shows that the original projected query and its output-restricted version have matching polymatroid and entropic bounds when the outputs are a prefix.The construction extends functions by setting h′(A) := h(A ∩ X), while constant random variables provide the analogous entropic extension.
- Proof conclusion: Combining Lemma 20 with the known equality for unprojected queries under acyclic functional dependencies proves the tightness result.The argument uses Proposition 21 for the unprojected, acyclic case.
5 Conclusion
The paper shows that projections can separate entropic and polymatroid bounds even under acyclic functional dependencies, while output-prefix queries preserve tightness. This identifies a structural condition for when the computable polymatroid bound remains exact.
- Conclusion: With projections, entropic and polymatroid bounds do not coincide in general, even under acyclic functional dependencies.This contrasts with the case without projected variables.
- Conclusion: Queries whose output variables form a prefix of the dependency graph retain polymatroid-bound tightness under acyclic functional dependencies and projections.The prefix condition is defined through a topological order of the dependency graph.
A Appendix: computer-assisted proof of the main technical result
The appendix verifies a main technical inequality by translating entropy constraints into a large linear program and solving it computationally. The calculation yields an exact optimal value but sacrifices manual tractability and structural insight.
- Purpose: The appendix’s computer-assisted approach verifies the first inequality of Proposition 12, which implies Theorem 9.It is presented as a shortcut around the detailed proof of the main technical result.
- Limitation: The computer-assisted proof requires trusting the hardware and software and provides limited insight into the structure underlying the computation.This is identified as the approach’s main drawback.
- Linear-program formulation: The appendix represents a 9-variable entropy problem using 511 entropy quantities, corresponding to all nonempty subsets of the 9-tuple.The variables are A, B, X, Y, C, A′, B′, X′, and Y′.
- Linear-program formulation: The linear program combines functional-dependency, cardinality, polymatroid, and non-Shannon-type inequalities before maximizing the target joint entropy.The cardinality constraints include bounds such as H(XY) ≤ 3t and H(C) ≤ 2t, where t is the threshold log N.
- Implementation: The elemental Shannon inequalities can be generated mechanically, enabling the complete constraint system to be produced by a simple computer program.For 9 random variables, these inequalities imply the relevant polymatroid inequalities.
- Result: The resulting linear program has optimal value 43/11t and can be solved with standard or exact rational-arithmetic LP solvers.Modern LP solvers handle the computation easily, although the program is too large for manual solution.