PaperlayerView exact revision on arXiv

Source-linked AI summary

Attacking Diophantus: Special Cases of Bag Containment

George Konstantinidis, Xinzhuo Li, Fabio Mogavero

arXiv:2609.30956v1cs.DB

TL;DR

Bag containment for conjunctive queries remains open, motivating decision procedures for broader tractable classes. The paper reduces join-uniform containment to a constrained Diophantine problem, and establishes decidability with a 2CoNExpTime upper bound for bag-set containment into arbitrary conjunctive queries.

  • Problem

    Whether conjunctive-query containment under bag semantics is decidable remains open, despite the semantics’ relevance to relational databases.

    Source: §1 · pp. 1–2

  • Method

    The framework builds a finite unification-based characterization of multiplicities and reduces containment to a constrained monomial-polynomial Diophantine problem.

    Source: §1 · pp. 3–4

  • Results

    2CoNExpTime is an upper bound for bag-set containment of join-uniform queries into arbitrary conjunctive queries; the problems discussed are also NPTime-hard.

    Source: §1 · p. 5

  • Takeaways & Limitations

    Join-uniformity extends decidability beyond projection-free and join-on-free containees while leaving the containing query arbitrary.

    Source: §1 · p. 3

    The exact frontier beyond join-uniform queries and tighter complexity bounds remain open.

    Source: §7 · p. 60

Abstract

from arXiv · show

Query containment is a fundamental decision problem in database theory: given two queries, determine whether, over all database instances, every answer produced by the first is also produced by the second. For conjunctive queries under set semantics, the problem is understood through the classical homomorphism-based characterisation. Under bag semantics, the interpretation underlying real relational databases, containment becomes a quantitative comparison of answer multiplicities. Despite decades of work, the decidability of bag containment for conjunctive queries remains open. This frontier is fragile: for slightly more expressive classes, bag containment is undecidable, with negative results relying on reductions from variants of Hilbert's 10th problem. This work develops a unified framework for bag containment of conjunctive queries that subsumes two previously studied decidable cases: projection-free and join-on-free containee queries. The framework yields decidability for a broader class, called join-uniform queries, while leaving the containing query arbitrary. This contrasts with techniques that impose restrictions on the containing query. The approach identifies tractable classes based on the internal unification structure of the query whose multiplicities must be bounded. Specifically, it reduces containment to a controlled Diophantine problem. Starting from the containee query, one builds a canonical model generated by all its possible unifications, over which multiplicities admit a finite arithmetic characterisation. Containment is proved equivalent to the non-existence of solutions of a corresponding Diophantine inequality system. Although these problems are undecidable in general, we show that the systems arising from join-uniform containment form a decidable subclass. Thus, the standard source of undecidability for bag containment becomes the core of the decision procedure.

1. Introduction

Bag containment for conjunctive queries remains open, despite decidability results for restricted classes. This paper unifies earlier containee restrictions through join-uniform queries and reduces containment to a decidable Diophantine problem.

1. Introduction

  • Earlier Diophantine approaches established decidability for projection-free and join-on-free containees, while other techniques restrict the containing query.The information-theoretic line studies structural restrictions such as chordal and series-parallel queries; the Diophantine approach instead restricts the containee.Source: §1 · p. 3
  • Join-uniform queries subsume projection-free and join-on-free queries, allow joins on existential variables, and leave the containing query unrestricted.The paper focuses on bag-set containment; the standard copy-attribute reduction does not preserve join-uniformity, so the result does not settle bag-bag containment for this class.Source: §1 · p. 3
  • The reduction builds a finite unification closure and multicanonical instances that suffice to find counterexamples to containment.For join-uniform queries, the closure is finite and has a homomorphic order representing query shapes arising when components overlap.Source: §1 · pp. 3–4
  • Counting homomorphisms into these instances yields finite parameters whose arithmetic relations characterize the containee and containing-query multiplicities.The containee multiplicity is a monomial in total homomorphism counts; the containing-query multiplicity is expressed by a polynomial over the same variables.Source: §1 · p. 4
  • The resulting constrained monomial-polynomial inequality has Diophantine natural solutions exactly when a non-containment witness exists.Strong non-negativeness and constraints on the counting parameters support a decision procedure, although arbitrary polynomial inequalities are undecidable in general.Source: §1 · pp. 4–5
  • 2CoNExpTime is an upper bound for bag-set containment of join-uniform queries into arbitrary conjunctive queries; the problems discussed are also NPTime-hard.The framework also recovers CoNExpTime upper bounds for bag-set and bag-bag containment of join-on-free queries, and a ΠP2 upper bound for bag-bag containment of projection-free queries.Source: §1 · p. 5

2. Preliminaries

The preliminaries establish the paper’s query and homomorphism notation, then introduce finite-poset tools for relating numerical counts to underlying contributions.

2. Preliminaries

  • The preliminaries distinguish constants, variables, and values, treating non-variable values like labelled nulls that homomorphisms may map to other terms.A homomorphism fixes constants and maps the source atom set into the target atom set.Source: §2.1 · p. 6

2.1. Queries & Homomorphisms.

  • Queries are represented by atoms with distinguished and existential variables; Boolean queries have no distinguished variables, and answers arise through homomorphisms.Components connect atoms sharing existential variables; unification and disjoint most general unification describe how query atoms or components can overlap.Source: §2.1 · pp. 6–7

2.2. Posets & Convolutions.

  • A poset supplies the order used to organize comparable elements, while convolution combines values across that order and can be inverted when its diagonal entries are nonzero.The paper uses this relation to recover underlying counts from total counts; integrality and non-negativity require divisibility and lower-bound conditions.Source: §2.2 · pp. 7–8

3. Special Cases of Bag Containment

The section formalizes bag-set and bag-bag containment, revisits projection-free and join-on-free containees, and introduces join-uniform queries as a broader class. Join-uniform queries subsume both earlier classes while allowing existential joins under a uniform-sharing condition.

3.1. The Bag-Set and Bag-Bag Containment Problems.

  • Bag-bag containment compares answer multiplicities over every instance and fact-multiplicity assignment, whereas bag-set containment uses unit multiplicities.Bag-bag containment implies bag-set containment, which implies set containment.Source: §3.1 · p. 9
  • The framework restricts the containee query, leaves the containing query unrestricted, and reduces containment to a Diophantine inequality system.The authors describe this as an exponential reduction.Source: §3.1 · p. 9

3.2. A Tale of Three Queries.

  • Projection-free and join-on-free queries are earlier tractable containee classes; the former have no existential variables, while the latter forbid joins on them.The section presents join-uniform queries as a generalization of these two classes.Source: §3.2 · pp. 10–11
  • Join-uniform queries subsume projection-free and join-on-free queries, allowing existential joins when atoms sharing an existential join share all existential variables.The condition extends the containee classes while leaving the containing query unrestricted in the paper’s framework.Source: §3.1 · p. 9, §3.2 · p. 11
  • The standard reduction from bag-bag to bag-set containment does not yield a bag-set problem whose containee is necessarily join-uniform.Consequently, solving bag-set containment for join-uniform queries does not necessarily settle their bag-bag containment problem.Source: §3.2 · p. 12

4. Computing Multiplicities

Section 4 develops finite closure and multicanonical-instance methods to characterize query multiplicities through homomorphism counts and weighted closure-poset inversion, including a component-wise product calculation for BJUQs whose components share only constants. It uses these characterizations to express bag non-containment as a constrained Diophantine inequality.

4. Computing Multiplicities

  • For a BJUQ, multiplicity is the product of the homomorphism counts of its components.The component-wise calculation applies when the only terms shared across components are constants.Source: §4.1 · p. 12

4.1. Multicanonical Instances.

  • A minimal unification closure starts from query components and adds queries formed by intra-query factorisation and inter-query merging.The closure is designed to capture possible image structures; it separates ground from non-ground queries.Source: §4.1 · pp. 12–13
  • For every BJUQ, its minimal unification closure is a finite poset, and its ordering coincides with bag-set containment among closure queries.Every non-ground closure query is also connected and join-uniform.Source: §4.1 · p. 14
  • If image elements of two closure queries overlap, their union is an image element of a closure query below both in the ordering.This supplies a closure query that represents overlapping images, even when the original queries are incomparable.Source: §4.1 · p. 16
  • Net images partition query images into disjoint, atom-preserving layers, enabling homomorphism counts to be summed over lower closure queries.For a query r, the count sums, over s ≼ r, the number of homomorphisms from r to s times the number of net-image elements for s.Source: §4.1 · p. 17

4.1. Multicanonical Instances

  • A net-image counting records each closure query’s number of net-images; every instance induces one, and ground queries assigned 1 form a ground selection.A ground query can have at most one net-image, and the selected ground queries are the minimal elements among closure queries constructible from their atoms.Source: §4.1 · pp. 19–20
  • Conversely, each net-image counting can be realized by a multicanonical instance with exactly the prescribed number of net-images for every closure query.The construction uses fresh, mutually disjoint copies for non-ground queries and selected ground copies; these copies are precisely the resulting net-images.Source: §4.1 · p. 21
  • For every instance I, q has a multicanonical instance I* preserving |Hom(q, I)| while not increasing |Hom(p, I)| for BCQs p with cn(p) ⊆ cn(q).This canonisation enables restriction of containment counterexample searches to multicanonical instances.Source: §4.1 · pp. 21–23
  • Bag non-containment of a BJUQ q and BCQ p holds exactly when a multicanonical instance for q witnesses it.The witness has |Hom(q, I)| > |Hom(p, I)|.Source: §4.1 · pp. 23–24

4.1. Multicanonical Instances.

  • A multicanonical expansion consists of renamed copies of all non-ground closure elements, optionally augmented with the ground atoms from a chosen ground selection.Different ground selections share the non-ground expansion and differ only in their ground facts.Source: §4.2 · p. 24

4.2. Counting Homomorphisms.

  • Lenses partition Hom(p, I), and each lens size is a product of net-image counts for the closure elements reached by its non-ground h-components.Thus counting homomorphisms into I amounts to summing these lens products.Source: §4.2 · p. 26
  • For a BJUQ q and BCQ p, multiplicity on a multicanonical instance is computed by evaluating N_p^q on its ground selection and net-image counting.The counting formula sums the sizes of lenses for homomorphisms into the multicanonical expansion.Source: §4.2 · pp. 27–28

4.3. Poset Characterisation.

  • The weight m(s, r) = |Hom(r, s)| records each closure copy’s contribution; weights are monotone, convolution-invertible, and yield integer-scaled inverse values.Total homomorphism counts combine net-image counts with these weights, and convolution inversion recovers the net-image counts uniquely.Source: §4.3 · pp. 28–30
  • Convolution by the multiplicity weight converts net-image counts into homomorphism counts, and inversion recovers the exact net-image counts.Lemma 4.28 establishes this equivalence for every BCQ in the closure.Source: §4.3 · p. 30
  • Non-containment holds exactly when some non-trivial homomorphism counting g for q satisfies Mq(g) > Pp.The equivalent condition searches over counts on the finite weighted closure poset.Source: §4.3 · p. 31

4.4. Polynomial Characterisation.

  • Profiles uniquely partition homomorphisms to the expansion; grouping by profile lets the polynomial sum count each class with its shared product.The class size is the multiplier for the product contributed by homomorphisms with that profile.Source: §4.4 · p. 33
  • For a BJUQ q, BCQ p, and ground selection G for q, for every profile i in Prof_p(q(G)), the cardinality |H_p(q(G), i)| is divisible by Q.Source: §4.4 · p. 34
  • For q6 and p1, the example gives Mq(u) = 480 > 25 = Pp; for q7, the strict inequality cannot hold for natural u.For q7, Pq7 q (G, u) = uC Mq(u), and uC is a factor of Mq(u).Source: §4.4 · p. 35
  • Non-containment is equivalent to a non-trivial ground selection and a Diophantine solution satisfying the constrained monomial–polynomial inequality.This polynomial characterisation restates the poset criterion for all BJUQs q and BCQs p.Source: §4.4 · p. 35
  • Extending ξ with the prescribed ground values and applying m−1 ⋆ yields n, whose natural-number values on non-ground elements ensure it is a net-image counting for G.This makes the extension a homomorphism counting with Gg = G.Source: §4.4 · p. 36
  • The construction preserves the multiplicity expression because Mq depends only on non-ground elements, enabling the polynomial inequality to transfer between ξ and the corresponding homomorphism counting.The proof uses the corresponding equality for Pp to transfer the inequality in both directions.Source: §4.4 · p. 36
  • Non-containment holds exactly when a non-trivial G and vector ξ satisfy the constraints and Mq(ξ) > Pp_q(G, ξ).The proof establishes both directions by converting between such a vector and a homomorphism counting that witnesses non-containment.Source: §4.4 · p. 36

5. A Diophantine Problem

This section analyzes constrained Diophantine systems arising in bag-containment characterisation, relating positive linear feasibility to increasing, admissible, and natural solutions under weighted-poset constraints. It characterizes natural solutions for n-MPIs and uses these results to develop a decision procedure.

5. A Diophantine Problem

  • Bag non-containment reduces to a monomial-polynomial inequality whose unknowns obey naturality constraints induced by weighted convolution and a fixed offset.Arbitrary polynomial-inequality solvability is undecidable, so the section seeks sufficient conditions for decidability of this constrained problem.Source: §5 · p. 37
  • Multiplicity posets encode integral convolution structure, while natural valuations require the offset-subtracted inverse contribution to be a natural number.Strong non-negativity requires the polynomial to remain non-negative on Diophantine natural valuations even after removing one positive monomial, enabling degree-based reasoning despite negative coefficients.Source: §5 · p. 38

5.1. Solutions of 1-GMPIs.

  • For a 1-GMPI with positive coefficients, a solution at least 1 requires the left monomial’s degree to exceed the polynomial’s degree; exceeding its positive degree ensures all sufficiently large values solve it.Negative-coefficient monomials cannot obstruct eventual domination by the left-hand monomial.Source: §5.1 · p. 39
  • For a finite poset on parameter unknowns, each n-exppar 1-GMPI yields a homogeneous linear system requiring left-monomial degree to exceed each positive right monomial, valuation to increase along the poset, and minimal coordinates to be nonnegative.For an n-exppar 1-MPI, its +‑system admits a solution iff it admits a (6ϕn3)-bit-bounded Diophantine positive solution, where ϕ is its facet complexity.Source: §5.1 · pp. 40, 42
  • A feasible positive system for an exponent-parameterised 1-MPI yields an increasing integer exponent vector, and every sufficiently large base then solves that inequality.The result supplies a threshold ℓ such that every base ζ > ℓ works.Source: §5.1 · p. 43

5.3. Increasing Solution of n-MPIs.

  • For polynomials with coefficients in R≥1, an increasing real solution, positive-system feasibility, and arbitrarily large Diophantine increasing solutions are equivalent.The theorem’s equivalence links real solutions to an arithmetic certificate and to solutions that can dominate any prescribed vector.Source: §5.3 · pp. 44–45

5.4. General Solutions of n-MPIs.

  • The general-solution argument works directly over arbitrary finite posets and does not require a meet-semilattice restriction.Source: §5.4 · p. 46
  • An admissible solution can be approximated by admissible increasing solutions while preserving the strict inequality.For sufficiently small positive ε, perturbing the solution yields the required family.Source: §5.4 · pp. 46–47
  • From a Diophantine natural solution and strong non-negativeness, the construction obtains an admissible increasing solution satisfying an inequality against a scaled positive part of the polynomial.Continuity preserves the finitely many strict monomial inequalities near the natural solution; sufficiently large common powers amplify them while eventually preserving admissibility.Source: §5.4 · pp. 46–47
  • A sufficiently scaled positive part allows sufficiently large Diophantine increasing solutions to recover Diophantine natural increasing solutions under weighted convolution.The construction chooses α so that solutions of M(u⊤) > αP+(u⊤) above a specified coordinatewise bound yield solutions of the original inequality.Source: §5.4 · p. 48
  • For strongly non-negative n-MPIs with unknowns bounded below by 1, natural solvability, positive-linear-system feasibility, and arbitrarily large natural increasing solutions are equivalent.This is the positive-solution characterization of Theorem 5.17.Source: §5.4 · p. 50
  • The reduction retains unknowns forced positive by the monomial or offsets, enabling the positive-solution characterization to apply without a meet-semilattice constraint.The retained set is upward closed; solutions of the reduced problem extend to the original by assigning zero to deleted unknowns.Source: §5.4 · p. 51
  • With zeros allowed, the original n-MPI has a natural solution iff its reduced MPI admits a natural increasing solution above any bound λ.The reduced MPI uses an upward-closed subset of unknowns and a polynomial formed by setting the deleted unknowns to zero.Source: §5.4 · p. 52

5.5. Decision Procedure for n-MPIs.

  • Prob. 3 is decidable in ∃∀-alternating polynomial time, with polynomial existential-guess space and logarithmic universal-guess space in max(n,m).The procedure guesses a bounded solution to the induced homogeneous linear system, then universally checks degree and strictness constraints.Source: §5.5 · p. 53

6. Decidability & Complexity

The section turns non-containment for the studied containee classes into Diophantine decision problems and derives upper bounds while leaving the containing query unrestricted. Join-uniform queries have a 2CoNExpTime upper bound; the earlier join-on-free and projection-free cases retain sharper bounds, and all four problems are NPTime-hard.

6. Decidability & Complexity

  • Non-containment for a BJUQ and arbitrary BCQ is equivalent to a natural solution of an associated n-MPI for some non-trivial ground selection.The multiplicity poset encodes the closure order, homomorphism weights, and ground-selection offset.Source: §6 · p. 54
  • The finite closure and Diophantine procedure decide JUQ non-containment by enumerating ground selections and testing their induced instances.Containment follows by complementation.Source: §6 · pp. 56–58
  • 2CoNExpTime, CoNExpTime, and ΠP2 upper bounds hold, respectively, for bag-set JUQs, bag-set and bag-bag JoFQs, and bag-bag PFQs into arbitrary CQs.All four problems are also NPTime-hard.Source: §6 · pp. 57–59
  • For JoFQs, atom-level closure representatives avoid the JUQ powerset blow-up, yielding exponential-size instances and CoNExpTime containment bounds.The same bound applies to bag-set and bag-bag semantics.Source: §6 · p. 58
  • For bag-bag PFQs, the closure has at most |q| representatives, enabling a polynomial-size existential certificate despite exponentially many monomials.The complement problem lies in the second existential level of the polynomial hierarchy.Source: §6 · p. 58
  • All four bag-set and bag-bag containment problems are NPTime-hard, with the lower bound already holding for Boolean restrictions.The hardness argument reduces from 3-colourability.Source: §6 · pp. 58–59

7. Discussion

The framework uses the containee query’s unification structure to cover projection-free and join-on-free cases and extend decidability to join-uniform queries, while leaving the containing query unrestricted. Its results leave open both tighter complexity bounds and the exact boundary beyond join-uniformity.

7. Discussion

  • The framework covers projection-free and join-on-free queries and extends to join-uniform queries, leaving the containing query unrestricted.It allows genuine joins on existential variables.Source: §7 · p. 59
  • A finite arithmetic representation of multiplicities over the minimal unification closure reduces containment to monomial-polynomial inequalities with controlled order structure.The approach constrains, rather than avoids, the usual Diophantine source of undecidability.Source: §7 · p. 59
  • Tighter complexity bounds remain open, and it is unclear whether the finiteness and order requirements that make join-uniformity sufficient can be weakened.The authors also identify integration with methods restricting the containing query as a direction toward resolving the general problem.Source: §7 · p. 60
Loading 2609.30956v1…