How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons

1 Introduction

• Containment and equivalence support query optimization [5, 7], rewriting over views and integrated data [19, 27], and evaluation of text-to-SQL models [15, 16, 32].A cited industrial study found that roughly a third of over 3,100 LLM-proposed production-query rewrites changed their results [22].Source: §1 · p. 1
• For plain conjunctive queries, containment is decided by evaluating the containing query on the other query’s frozen canonical database.This lets database systems certify equivalence through native query evaluation rather than separate homomorphism-finding machinery.Source: §1 · p. 1
• With nulls under SQL’s three-valued semantics or with comparisons, containment is Π_2^p-complete [12, 17, 28], and the known tests use exponential families of databases.Those families leave no practical route to certifying equivalence.Source: §1 · pp. 1–2
• The paper shrinks the null test to vary only a special set of variables, reduces comparison tests through decomposition and order-conflict splitting, and combines the features with a fixed-parameter tractable test.For nulls, containment is in NP when the special variable set has constant size.Source: §1 · p. 2

2 Formal Framework

• A database assigns each schema relation a finite set of tuples over the rationals and a distinguished null symbol; it is ordinary when its tuples contain only rationals.A schema is a finite set of relation symbols with fixed arities.Source: §2 · p. 2
• Queries have relational atoms and may include < or ≤ comparisons; the framework distinguishes null queries, comparison queries, and variable–constant comparison queries.Queries are normalized so comparisons do not equate distinct variables and constants appear only in comparisons.Source: §2 · p. 2
• Under SQL semantics, a comparison is unsatisfied if either value is null, and satisfying valuations must map join variables to non-null values.The output tuple may nevertheless contain nulls when a head variable is mapped to null by a relational atom.Source: §2 · pp. 2–3
• For plain conjunctive queries, containment is characterized by a homomorphism or, equivalently, by evaluating the containing query on the canonical database; null-containment and comparison containment are Π_2^p-complete [12, 17, 28].The canonical database freezes each query variable as a distinct constant.Source: §2 · p. 3

3 Null Conjunctive Queries

• A query pair can be contained over complete databases but fail under nulls, as the genealogy example demonstrates.The null-valued grandparent–parent output cannot be returned by the comparison query in the example.Source: §3 · p. 3
• Covered non-join variables share a position set with a head variable of the containing query, and VCJ further identifies those matching one of its join variables.This classification determines which non-join variables belong in the toggled set.Source: §3 · p. 4
• The test freezes join variables, selected covered variables, and head variables outside VCJ; it toggles VCJ and nulls the remaining variables.Containment holds exactly when the containing query returns the required tuple on every resulting database.Source: §3 · p. 4
• The reduced family has 2^|Vt| databases instead of the 2^|njoin(q)| null versions considered by the earlier characterization.The proof shows a test witnessing a toggled database also witnesses the corresponding arbitrary null version.Source: §3 · pp. 3–4
• When the special toggled-variable set Vt has constant size, null containment is in NP; if the containing query also admits polynomial evaluation, containment is in P.For Boolean queries Vt is empty, and the P bound also applies when the containing query is acyclic [30].Source: §3 · p. 4
• In the genealogy example, the original test considers 64 null versions, while the reduced test uses two databases and one witnesses non-containment.The example’s six non-join variables yield Vt = {p1}.Source: §3 · p. 4

4.1 Witness Sets and the Containment Criterion

• For CQvc, containment holds exactly when the containing query’s outputs are included on every canonical database built from the contained query’s canonical assignments.Each variable’s witness set has size at most 2|match(x)| + 1; in the running example, six variables and eight query constants yield a single canonical database.Source: §4.1 · p. 6

4.2 Reducing to Independent Components

• For CQvc, legal separators and relational-graph components allow containment tests to vary each component with the separator while keeping co-matched variables together.The component-wise witnesses can be stitched into a sound and complete test even when canonical values are shared and assignments are non-injective.Source: §4.2 · p. 8
• Choosing a legal separator that minimizes the CQvc test family is NP-complete, even when every variable has exactly two canonical values.Every legal separator still gives a sound and complete test; only the family size depends on the choice.Source: §4.2 · p. 9

4.3 Extending to Variable–Variable Comparisons

• For CQcmp, relevant inequalities from both queries define a comparison graph that groups variables whose relative order can affect containment.The method uses partial matching to identify inequalities induced by q′, alongside q’s own variable comparisons; representative values are selected within intervals partitioned by relevant constants and constrained by variable order.Source: §4.3 · p. 10
• Containment holds exactly when the containing query holds on every canonical database from componentwise canonical assignments; this considers only component orderings against relevant constants, unlike the earlier construction [17].Assignments preserve the order and equalities of a satisfying valuation within each connected component and keep variables in their intervals.Source: §4.3 · p. 11

4.4 Splitting on Order Conflicts

• For each component, the opposite graph records orders forced by q and reverse edges for comparisons induced by q′; comparisons not blocked by a reverse path can be added to q without changing containment.An addable comparison has no strict order implied by q, and the graph has no path from its second variable to its first.Source: §4.4 · pp. 11–12
• Splitting each cycle reverse edge into <, =, or > preserves containment, and each resulting query needs at most one local assignment per component.A component contributes at most 3^|Ecycle| local assignments across the trichotomy cases, with fewer when cases are unsatisfiable.Source: §4.4 · p. 12
• When the opposite graph has no non-strict cycle, containment is equivalent to containment for every minimal match-feedback-edge-set query, generated with polynomial delay.Each such query is tested together with its local assignment.Source: §4.4 · pp. 12–13
• The no-non-strict-cycle condition is necessary: with a non-strict cycle, feedback queries can miss a failing equality assignment, while trichotomy still detects it.In the example, containment fails exactly when the two variables are equal; the trichotomy case assigning = to both cycle edges captures that database.Source: §4.4 · p. 13

5 Combining Nulls and Comparisons

• Nulling and ordering act on disjoint variables because a comparison with a null argument is unsatisfied.Using nonnull variables in place of join variables aligns the two constructions: compared variables are frozen on one side and force covered variables to be toggled on the other.Source: §5 · pp. 13–14
• Containment holds exactly when the containing query's outputs are contained on every database in the combined canonical family.Each combined assignment supplies a canonical test database; it assigns variables canonical values, null, or either, subject to the query's comparisons.Source: §5 · p. 13
• The test decomposes using legal separators, while splitting along cyclic order conflicts forces each nontrivial component to a local assignment.The combined construction adds graph constraints for nontrivial components and variable–variable comparisons; nulling can only shrink the cycle-conflict case split.Source: §5 · p. 14
• The combined test-family size is fixed-parameter tractable in Δ, w, and |Ecycle(q)|; on CQvc,⊥ it is fixed-parameter tractable in Δ and w.Containment is in NP when these parameters are constant, and in P when q′ admits polynomial evaluation.Source: §5 · p. 14
• The three parameters are local: Δ measures match-set size, w separator structure, and |Ecycle(q)| cyclic conflicts between induced comparisons and q's order.None grows with query size alone; in the absence of comparisons or nulls, the bound specializes to the corresponding single-feature result.Source: §5 · p. 14
• Over null-free databases, the feedback queries and their local assignments are generated with polynomial delay.A worked example computes the parameters and resulting family.Source: §5 · p. 15

6 Related Work

• Earlier CQ containment work extended the characterization to union and difference [3, 24], while tractable fragments include acyclic queries [30], restricted fanout [25, 23], and bounded treewidth [8].Source: §6 · p. 15
• For inequalities, Klug [17] gave an upper bound using canonical databases for all variable orderings, and Van der Meyden [28] established the matching lower bound.Other work identifies arithmetic-comparison classes where homomorphism-based tests remain complete [1], while the present paper counts canonical databases rather than mapping disjunctions [2].Source: §6 · p. 15
• Existing SQL equivalence tools either certify only restricted fragments, find bounded counterexamples, or guarantee test coverage; this paper instead identifies database families whose passing certifies containment.Source: §6 · p. 15

7 Conclusion

• For nulls, the test family has size 2|Vt| rather than 2|njoin(q)|; for comparisons, witness-set canonical values support shrinking by decomposition and cyclic-conflict splitting.Source: §7 · p. 15
• Combining the features makes the number of test databases fixed-parameter tractable in three local parameters, and small for many query pairs.Source: §7 · p. 15
• The constructions do not cover disequality, richer semantics, aggregation, unions, or negation, and their families are generated in no particular order.Disequality would require handling effective domains that are unions of intervals; generating a distinguishing database early remains a goal for refutation-oriented checkers.Source: §7 · p. 15

A Use of Artificial Intelligence

• During exploratory research, Claude Code searched for potential counterexamples to tentative hypotheses and performed preliminary sanity checks.Source: A Use of Artificial Intelligence · p. 18
• The authors developed the proof strategies, constructions, mathematical arguments, and case analyses; Claude Code drafted appendix portions from detailed author-prepared outlines.The authors reviewed and revised the prose and independently checked the final mathematical statements, proofs, and citations.Source: A Use of Artificial Intelligence · p. 18

B.1 Proofs for Section 3

• A valuation of q′ over θM Dq yields a homomorphism from q′’s relational body to q, with conditions preserving non-null join values and the head tuple.Conversely, such a homomorphism produces a valuation over θN Dq for any N satisfying the same conditions.Source: §B.1 · p. 18
• Containment follows by testing null versions that null V ∪ Vn, then extending the result to every N ⊆ njoin(q).The proof uses the containment characterization over all null versions and the definitions of Vf, Vt, and Vn.Source: §B.1 · pp. 18–19
• The same matching homomorphism works for N after transferring the head condition and ruling out nullified values for join variables.The proof uses position-set inclusion and coverage: a covered head variable cannot map to an uncovered non-join variable, and a join-variable image in N would contradict the matching conditions.Source: §B.1 · p. 19

B.2 Proofs for Section 4.1

• In the running example, four maximally infinite-contradictable sets yield witness intervals [0, 2), (3, 5), (6, 8), and (11, 13].The example also notes that all comparisons are non-strict and finVals(x1) is empty.Source: §B.2 · p. 20
• At most 2|match(x)| + 1 cells partition an effective domain, and singleton and infinite witnesses occupy distinct point and interval cells.Cells group points with an unchanged set of incompatible variables; each witness identifies its own cell.Source: §B.2 · pp. 20–21
• For each variable, the proof chooses singleton or infinite witnesses to select canonical values, then forms a canonical database where q′ returns q’s head tuple.The chosen witness stays within the subdomain induced by variables incompatible with the original valuation.Source: §B.2 · p. 21
• The canonical-database valuation lifts to the original database by mapping each q′ value through a q-variable preimage, with well-definedness ensured by singleton or distinct infinite-witness values.The proof checks relational atoms and comparison atoms before showing the original head tuple is preserved.Source: §B.2 · pp. 21–22

B.3 Proofs for Section 4.2

• Atom locality confines each relational atom’s covering matches to at most one component after removing the separator, enabling a valuation assembled from component-wise tests.The proof handles relational atoms, constant comparisons, and head variables to show the assembled valuation witnesses q′ on the canonical database.Source: §B.3 · pp. 23–24
• The smallest S-exhaustive family has size |A(S)| · maxi |A(Ci)|, combining assignments on the separator with the largest component assignment space.The proof gives matching lower and upper bounds by showing every separator–largest-component assignment must occur and constructing an exhaustive family of that size.Source: §B.3 · p. 24
• Containment-test size can be checked in polynomial time for a guessed legal separator, using witness sets and a sweep over effective-domain endpoints.The proof states NP membership for the decision problem.Source: §B.3 · pp. 24–25
• With two canonical values per variable, minimizing the separator-size plus largest-component-size criterion is NP-hard via a reduction from Vertex Cover.The proof realizes the graph instance as a query pair with two canonical values per variable and legal separators.Source: §B.3 · pp. 25–26

• Witness sets alone can miss noncontainment: despite no feasible witness-set values for x1 > x2, {R(21), S(11)} satisfies q but not q′.Source: §B.4 · p. 26
• A second example shows that even a single assignment determined by witness sets can miss noncontainment when q′ adds the comparison y1 < y4.Source: §B.4 · p. 26
• Every satisfying valuation has a canonical assignment preserving component order and equalities, interval membership, and isolated-variable forbidden-set inclusion.Source: §B.4 · p. 27
• For nontrivial components, the construction assigns singleton interval values or ordered representatives to equality classes; isolated variables use finite witnesses or infinite witnesses that preserve forbidden sets.Source: §B.4 · p. 27
• Theorem 4.16 proves sufficiency by transporting a q′ witness from a canonical database back to an arbitrary database, establishing containment there.Source: §B.4 · pp. 28–29
• Every containment failure has a canonical-assignment witness: a tuple returned by q on its canonical database but not by q′.Source: §B.4 · p. 29

Lemma B.8 and Theorem 4.18

• A canonical counterexample assignment can be reordered to satisfy an added comparison while preserving the failure of q′; the argument also applies when an endpoint is a constant of K(C).The reordering fixes constants and preserves validity of q’s comparisons.Source: §B.5 · pp. 30, 32

Lemma B.9

• For a produced query, its comparison atoms entail s ≤ t exactly when the opposite graph has a path from s to t, and entail s < t when such a path contains a strict edge.The converse is shown by constructing a satisfying valuation that reverses the relation when no suitable path exists.Source: §B.5 · p. 32

Lemma B.10

• After cycle reverse edges are decided and entailed-equal variables merged, each opposite-graph strongly connected component is a singleton or a variable pinned to a constant.Entailed relations are witnessed by paths between every member of the corresponding merged vertices.Source: §B.5 · p. 33

Lemma B.11

• In polynomial time, completion adds O(|V|^2) comparisons while preserving containment with q′, yielding one local assignment that satisfies every non-cycle reverse edge.The completed query has canonical assignments inducing a single local assignment on C.Source: §B.5 · pp. 34–35

Proof of Theorem 4.19

• q ⊆ q′ holds exactly when every trichotomy query qσ is contained in q′, and each trichotomy case tests at most one local assignment on component C.The proof also states that the component contributes at most 3|Ecycle| local assignments.Source: §B.5 · p. 35

B.5 Proofs for Section 4.4

• For the converse, a canonical counterexample assignment identifies a set of violated cycle-reverse edges containing an MFES, whose minimal subset yields a feedback-query counterexample.Removing that subset makes the graph acyclic; an assignment strictly increasing along its edges satisfies the feedback query while still falsifying q′.Source: §B.5 · p. 35
• Under the no-non-strict-cycle assumption, q ⊆ q′ exactly when every feedback query for a minimal MFES is contained in q′.If q is not contained in q′, the proof constructs a minimal MFES whose feedback query has a counterexample assignment.Source: §B.5 · p. 35
• Minimal MFESs correspond exactly to minimal feedback vertex sets of a polynomial-time constructible digraph whose vertices are cycle-reverse edges.Its edges encode reachability between reverse-edge endpoints using only Eq-edges.Source: §B.5 · p. 36
• Minimal MFESs, their feedback queries, and unique local assignments can be generated with polynomial delay using minimal feedback-vertex-set enumeration [26].Self-loop vertices are forced into every feedback vertex set; query construction and local-assignment computation take polynomial time.Source: §B.5 · p. 36

Theorem 5.1

• Theorem 5.1 proves that passing the combined-assignment tests implies containment on every database, by transporting an arbitrary satisfying valuation of q into one of q′.The proof constructs a combined assignment and uses a satisfying valuation of q′ over its canonical test database to build the required valuation over the original database.Source: §B.6 · pp. 37–38

Corollary B.13

• A failure of containment is witnessed by a combined assignment θ at its own output tuple θ(¯x), which lies outside q′(θ(Dq)).Thus checking these tuples suffices to detect non-containment.Source: §B.6 · p. 38

Theorem 5.2

• Component pinning reduces the tests to local assignments fixed by null patterns and cycle-edge trichotomies, with at most 3^|Ecycle(q)| cases.Within each case, a legal separator supports stitching independent choices while preserving a violating assignment; each case contributes at most the product of the variables’ choice counts.Source: §B.6 · pp. 38–40

Corollary 5.3

• Under the no-non-strict-cycle condition, feedback pinning replaces the cycle-trichotomy factor with a product of minimal-feedback-edge-set counts ℓC across nontrivial components.For each null pattern, only surviving minimal feedback edge sets that remain minimal in the restricted opposite graph contribute local assignments.Source: §B.6 · pp. 40, 42
• When ∆, w, and |Ecycle(q)| are constant, the family has constantly many polynomial-size databases, placing containment in NP, or in P if q′ admits polynomial evaluation.Each case contributes at most (2∆ + 2)^w assignments.Source: §B.6 · pp. 41–42

B.6 Proofs for Section 5

• The comparison graph separates into two cliques, making the empty separator legal and yielding width w = 5.One clique contains {p1, p2, p3, b2, b3}; the other contains the comparison component C.Source: §B.6 · p. 42
• The example reduces 512 combined databases to 18 canonical tests, or 4 with the feedback improvement.Theorem 5.2 gives 3|Ecycle(q)| · max{2, 1} = 18; Corollary 5.3 gives ℓC · 2 = 4. The example has 256 local assignments before the two toggles; its parameters include ∆ = 3, |Ecycle(q)| = 2, ℓC = 2, and width w = 5.Source: §B.6 · p. 42
• Adding maintenance events lengthens the induced chain while leaving |Ecycle(q)| and the value counts unchanged.Source: §B.6 · p. 42