arXiv CSopen access

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

How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons Helen Sternbach # School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel

Sara Cohen # School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel

arXiv:2609.16218v1 [cs.DB] 14 Sep 2026

Abstract Query containment and equivalence drive database query optimization and rewriting. For plain conjunctive queries, both are decided by evaluating one query over a single canonical database of the other. This classical test breaks down in two settings that pervade real queries: databases with null values under SQL’s three-valued semantics, and queries with order comparisons. In both, deciding containment is Πp2 -complete, and the known characterizations replace it by an exponential family of test databases, leaving no practical route to certifying equivalence. We ask how the family of test databases can be shrunk. For conjunctive queries over databases with nulls, we shrink the family to one that is exponential only in a special set of variables, and place containment in NP when that set has constant size. For queries with comparisons, we construct canonical values that decide containment, and then shrink the family by decomposing the test into independent components and by splitting it along the order conflicts. Finally, we combine the two features, and prove that the number of test databases is fixed-parameter tractable in three local parameters of the two queries, with the null-only and comparison-only tests as special cases. Each test evaluates the containing query over a family of databases, an operation native to any database system. 2012 ACM Subject Classification Theory of computation → Database query languages Keywords and phrases conjunctive queries, query containment, query equivalence, null values, inequalities, canonical databases Funding The authors were partially funded by the Israel Science Foundation (ISF), grant no. 359/21. H. Sternbach was partially funded by the Ariane de Rothschild Women Doctoral Program.

1

Introduction

Query containment and equivalence are among the most fundamental problems in database theory. Given queries q, q ′ , containment asks whether q(D) ⊆ q ′ (D) for every database D, and equivalence is containment in both directions. The problems drive query optimization [5, 7] and query rewriting over materialized views and integrated data sources [19, 27]. They have also found new urgency: in a recent industrial study roughly a third of over 3,100 LLM-proposed rewrites of production queries changed their results [22], and text-to-SQL benchmarks rank models by deciding equivalence to a reference query [15, 16, 32]. For the core class of conjunctive queries (CQs), Chandra and Merlin [5] characterized containment by the existence of a containment mapping, or, equivalently: q ⊆ q ′ if and only if q ′ returns the frozen head tuple over the canonical database Dq , obtained from q by freezing each variable into a constant. Such a test is attractive in practice: it amounts to evaluating q ′ over concrete databases, an operation every database system performs natively, so equivalence is certified without separate machinery for finding homomorphisms. This simple picture breaks down in two settings that pervade real queries. Databases routinely contain null values, which SQL interprets under a three-valued logic, and queries routinely contain comparisons. In both settings, deciding containment is Πp2 -complete [12, 17, 28], and a single canonical database no longer suffices. The known characterizations replace Dq by an exponential family: all null versions of Dq in the first setting, and canonical

2

Shrinking the Family of Test Databases

databases for all orderings of the variables and constants in the second. Πp2 -completeness, tested through an exponential family, leaves no practical route to certifying equivalence. Contributions. The central question of this paper is: how can we shrink the family of test databases that decides containment? For CQs over databases with nulls (Section 3), we replace the known exponential family by one that is exponential only in a special set of variables, and place containment in NP when that set has constant size. For queries with comparisons (Section 4), we give a family of canonical databases that decides containment, and then shrink it twice. The test decomposes into independent parts, and it splits along the order conflicts between the two queries. Finally, we combine the two features (Section 5). The constructions compose, because a comparison is never satisfied by a null, and the size of the combined family is fixed-parameter tractable in three local parameters of the two queries. For each result we give the idea of its proof, deferring the full proofs to Appendix B.

2

Formal Framework

Databases and Queries. A schema σ is a finite set of relation symbols, each with a fixed arity. A database D over σ assigns to each R ∈ σ of arity k a finite relation RD ⊆ (Q ∪ {⊥})k , where Q denotes the rationals and ⊥ is a distinguished null symbol representing an unknown value. A database is ordinary (or null-free) if RD ⊆ Qk for every R ∈ σ. A term is either a variable or a constant from Q. A relational atom over σ has the form R(t1 , . . . , tk ) where R ∈ σ has arity k and each ti is a term. A comparison atom has the form s ⋖ s′ where s, s′ are terms and ⋖∈ {<, ≤}. This is no restriction, since > and ≥ are the mirror images of < and ≤, and an equality s = s′ is the pair s ≤ s′ , s′ ≤ s. A query q has the form q(x̄) ← R1 (t̄1 ), . . . , Rn (t̄n ), C1 , . . . , Ck where each Ri (t̄i ) is a relational atom, each Cj is a comparison atom, and x̄ is a tuple of variables called the head. The set {R1 (t̄1 ), . . . , Rn (t̄n )} is the relational body of q, and together with the comparison atoms it forms body(q). We say q is Boolean when x̄ is empty. We write compvc (q) for the comparison atoms of q with a constant argument, and compvv (q) for those with two variables. Throughout, without loss of generality, queries are normalized: (N1) no two distinct variables are made equal by comparisons, and (N2) every argument of a relational atom is a variable, so constants occur only in comparison atoms. We use CQ for the class of conjunctive queries (CQs), which have no comparisons and are evaluated over ordinary databases, CQ⊥ for CQs with null values without comparisons evaluated over databases that may contain ⊥ and CQcmp , which allows arbitrary comparison atoms over ordinary databases and its subclass CQvc ⊆ CQcmp , in which every comparison is between a variable and a constant. Variable Classification. The variables of q, written vars(q), are all variables appearing in the query. Variables appearing in the head are the output variables, head(q). A variable v ∈ vars(q) is a join variable if it occurs at least twice in the relational atoms of q (possibly twice in a single atom), and otherwise it is a non-join variable. We write join(q) and njoin(q) for these two sets. The position set POSq (v) of v in q is the set of pairs (R, j) such that v appears in position j of some relational atom of q over the relation R. ▶ Example 2.1. For q(x) ← R(x, y), R(z, y), S(z, w), the position sets are POSq (x) = {(R, 1)}, POSq (y) = {(R, 2)}, POSq (z) = {(R, 1), (S, 1)}, and POSq (w) = {(S, 2)}. The variables y and z occur twice and are join variables, with y recurring in a single position and z across two, while x, w ∈ njoin(q). ◀

H. Sternbach and S. Cohen

Query Evaluation. A valuation for q over database D is a function µ : vars(q) → Q ∪ {⊥}, extended to terms by µ(c) = c for every constant c ∈ Q. The valuation µ satisfies a relational atom R(t1 , . . . , tk ) in D if (µ(t1 ), . . . , µ(tk )) ∈ RD , and it satisfies a comparison atom s ⋖ s′ if µ(s), µ(s′ ) ∈ Q and µ(s) ⋖ µ(s′ ) holds. If either argument is ⊥ the comparison atom is not satisfied, following SQL’s three-valued logic. We say µ is a satisfying valuation for q in D if it satisfies every atom in body(q) and maps every join variable of q to a non-⊥ value. The last requirement reflects that two occurrences of a null are never equal under SQL semantics, and is vacuous over null-free databases. The result of q(x̄) on D is q(D) := { µ(x̄) | µ is a satisfying valuation for q in D }. The output tuple µ(x̄) may itself contain nulls if a head variable is mapped to ⊥ by a relational atom. Canonical Database and Containment. The canonical database Dq of a query q is the ordinary database obtained by treating each variable as a distinct constant (“freezing” it): Dq contains the tuple ι(t̄i ) in relation Ri for each relational atom Ri (t̄i ) in body(q), where ι is the identity on variables viewed as constants. Let q and q ′ be queries of the same output arity evaluated over a class D of databases. We say q is contained in q ′ w.r.t. D, written q ⊆D q ′ , if q(D) ⊆ q ′ (D) for all D ∈ D, and the queries are equivalent, q ≡D q ′ , if containment holds in both directions. When D is all ordinary databases we write q ⊆ q ′ . When D includes databases with nulls we write q ⊆⊥ q ′ . For plain CQs, containment is characterized by containment mappings [5]: q ⊆ q ′ iff there exists a homomorphism from the relational body of q ′ to that of q mapping head(q ′ ) to head(q), or equivalently, iff q ′ returns x̄ on Dq . Both null-containment and containment for ′ CQcmp are ΠP 2 -complete [12, 17, 28] and cannot be decided by evaluating q on Dq alone.

3

Null Conjunctive Queries

Null conjunctive queries (CQ⊥ ) are conjunctive queries evaluated, under the SQL three-valued semantics of Section 2, over databases that may contain null values. ▶ Example 3.1. A genealogy stores each person’s (possibly unknown) parent and birth and death years in Person(parent, child, childBirthYr, childDeathYr). Consider the queries q(p1 , p2 ) ← Person(p1 , p2 , b2 , d2 ), Person(p2 , p3 , b3 , d3 ), q ′ (p1 , p2 ) ← Person(p1 , p2 , b2 , d2 ), Person(p1 , p3 , b3 , d3 ). So q returns grandparent–parent pairs, while q ′ pairs a parent with a child when it has another. Over complete databases every pair returned by q is also returned by q ′ , so q ⊆ q ′ . With nulls it fails: q returns (⊥, Alice) over {Person(⊥, Alice, 1920, 1980), Person(Alice, Bob, 1940, 2000)}, where Alice’s parent is unknown, while q ′ cannot return this tuple. ◀ Deciding null-containment is ΠP 2 -complete in general and NP-complete for Boolean queries [12]. We focus on characterizing containment via canonical databases, rather than homomorphisms (see Section 6 for homomorphism-based conditions). Recall Dq from Section 2. A null version of Dq replaces some of the frozen non-join variables of q by ⊥. For a set N ⊆ njoin(q), let θN be the substitution that maps the variables of N to ⊥ and fixes every other variables. We write θN Dq for the resulting database. Farré et al. showed the following result. ▶ Theorem 3.2 ([12]). Let q(x̄), q ′ (x̄) be CQ⊥ queries. Then q ⊆⊥ q ′ if and only if, for every N ⊆ njoin(q), the query q ′ returns the tuple θN x̄ over θN Dq . Since a null version may set any subset of the non-join variables to ⊥, Theorem 3.2 ranges over 2|njoin(q)| databases. We show that it suffices to toggle only a small subset of them.

3

4

Shrinking the Family of Test Databases

Throughout this section q and q ′ are fixed. Everything turns on how the non-join variables of q relate to the head of q ′ . Call a non-join variable v of q covered when it occupies the same positions as some head variable of q ′ , that is, POSq (v) = POSq′ (x′ ) for some x′ ∈ head(q ′ ), and let VC be the set of covered variables. Among these, VCJ contains the variables v whose position set also satisfies POSq (v) = POSq′ (y ′ ) for some join variable y ′ of q ′ , and VCN = VC − VCJ contains the rest. Note that since v is a non-join variable, |POSq (v)| = 1, so both equalities are equivalent to the containments POSq′ (x′ ) ⊆ POSq (v) and POSq′ (y ′ ) ⊆ POSq (v). When creating a canonical database from q, we must decide which variables to freeze and which to null. Join variables must be frozen, so that q returns a result over the canonical database. For a covered variable there is a duality: nulling it may prevent q ′ from returning a result, as join variables of q ′ cannot be mapped to nulls, but nulling it may also enable q ′ to return a result with ⊥ in the output, by mapping a head variable of q ′ to it. Given this duality, a variable of VCJ must be toggled between frozen and null. A variable of VCN can safely be frozen, as it never prevents q ′ from returning a result, and the remaining non-join, non-head variables can safely be nulled, as q ′ cannot use them to produce a result with ⊥ in the output. Formally, we freeze the variables of Vf = join(q) ∪ VCN ∪ (head(q) − VCJ ), toggle the variables of Vt = VCJ , and null the remaining variables, denoted Vn . For a subset V ⊆ Vt , let θV ∪Vn be the mapping that nulls all variables in V ∪ Vn and freezes every other variable of q. ▶ Theorem 3.3. q ⊆⊥ q ′ if and only if q ′ returns θV ∪Vn x̄ over θV ∪Vn Dq for every V ⊆ Vt . The proof recasts the test of Theorem 3.2 as the existence of a homomorphism from the relational body of q ′ to that of q that avoids the nulled variables on join variables and matches the head up to nulling. It then shows that the homomorphism witnessing the toggled database with V = N ∩ Vt also witnesses the null version of an arbitrary N ⊆ njoin(q), so the 2|Vt | toggled databases subsume all 2|njoin(q)| null versions. ▶ Corollary 3.4. If |Vt | has constant size, null containment is in NP. Furthermore, if |Vt | has constant size and q ′ admits polynomial evaluation, then null containment is in P. For example, if q and q ′ are Boolean, then Vt is empty, so Theorem 3.3 extends the previously known NP upper bound for the Boolean case to a wider class of queries. Moreover, if additionally q ′ is acyclic [30], then null containment is in P. ▶ Example 3.5. Recall Example 3.1. The query q has six non-join variables, so Theorem 3.2 considers 26 = 64 null versions of Dq . The covered variables are p1 and p3 , with VCJ = {p1 } and VCN = {p3 }, giving Vf = {p2 , p3 }, Vt = {p1 }, and Vn = {b2 , d2 , b3 , d3 }. Theorem 3.3 tests only two databases: D1 , which nulls Vn and freezes all other variables (V = ∅), and D2 , which also nulls p1 (V = {p1 }). Indeed, D2 shows non-containment. ◀

4

Conjunctive Queries with Inequalities

We now turn to conjunctive queries with comparison atoms, evaluated over null-free databases. Sections 4.1 and 4.2 develop the containment test for the variable–constant class CQvc , and Sections 4.3 and 4.4 extend it to the full class CQcmp .

4.1

Witness Sets and the Containment Criterion

Recall the classes CQcmp (queries with comparison atoms) and CQvc ⊆ CQcmp (whose comparisons are all variable–constant), and the position set POSq (v). The effective domain

H. Sternbach and S. Cohen

eDomq (v) of a variable v is the set of values in Q satisfying all comparison atoms of q involving v, written eDom(v) when q is clear. For a variable with no comparisons, eDomq (v) = Q. Since the comparison operators are < and ≤, every effective domain is an interval, possibly unbounded. We call such subsets of Q subdomains. Given q and q ′ , we seek the variables of q ′ that can correspond to those of q. We say that a variable y ∈ vars(q ′ ) matches x ∈ vars(q) if (1) POSq′ (y) ⊆ POSq (x), and (2) eDom(y) ∩ eDom(x) ̸= ∅. We write match(q ′ , q, x), or simply match(x), for the set of variables of q ′ that match x. Given a subdomain E of Q and a set of variables V ⊆ vars(q), we will say that V is incompatible with E written V ⊭ E if eDom(v) ∩ E = ∅, for all v ∈ V . Given a set of variables V ⊆ vars(q) such that some are incompatible with E, while others are not, we use incomp(E, V ) to denote the maximal subset V ′ of V such that V ′ ⊭ E. ▶ Example 4.1 (Running example). Throughout this subsection, consider a bank database with the relations Trans(acct, amount, hour, fee), Account(acct, balance, rate), and Flagged(acct), which lists the accounts flagged for review. Account numbers up to 50 are reserved for internal accounts, and first-branch accounts lie strictly between 100 and 200. Consider the Boolean CQvc queries q() ← Trans(a, m, h, e), Account(a, b, r), Flagged(a), 100 < a < 200, m ≥ 1000 q ′ () ← Trans(a′ , m′ , h′ , e′ ), Account(a′ , b′ , r′ ), Flagged(a′ ), Flagged(u), 150 ≤ a′ ≤ 400, 500 < m′ < 2000, u ≤ 50 Query q asks whether some flagged account of the first branch made a transaction of at least 1000. Query q ′ asks whether some flagged account numbered between 150 and 400 made a transaction of an amount between 500 and 2000, and some internal account is flagged. Neither query constrains the hour, fee, balance, and rate variables, so their effective domains are Q. The remaining effective domains are eDomq (a) = (100, 200) and eDomq (m) = [1000, ∞) in q, and eDomq′ (a′ ) = [150, 400], eDomq′ (m′ ) = (500, 2000), and eDomq′ (u) = (−∞, 50] in q ′ . Both POSq′ (a′ ) and POSq′ (u) are subsets of POSq (a) = {(Trans, 1), (Account, 1), (Flagged, 1)}. Since eDomq′ (a′ ) ∩ eDomq (a) = [150, 200) ̸= ∅, the variable a′ matches a. In contrast, eDomq′ (u) ∩ eDomq (a) = ∅: an internal account cannot play the role of the branch account of q, so u does not match a. Hence match(a) = {a′ }, and each other variable of q is matched exactly by its primed counterpart. For incomp, take E = [200, ∞). Only eDom(a) is disjoint from E, so incomp(E, vars(q)) = {a}. ◀
T For any set S ⊆ match(x), write Ex (S) = y∈S eDomq (x)\eDomq′ (y) for the subdomain it induces. We say that S is contradictable by x if Ex (S) ̸= ∅, and infinite-contradictable by x if Ex (S) is infinite. If S is maximal among the infinite-contradictable subsets of match(x), then S is maximally infinite-contradictable by x. Several sets may be maximally infinitecontradictable by x, as Example 4.2 shows. Let finVals(x) be the set of values of eDom(x) that lie in Ex (S) for some S ⊆ match(x) with Ex (S) finite. A finite Ex (S) may contain more than one value, for example the two endpoints of eDom(x). The witness set Wx of x collects the subdomains Ex (S) for the sets S ⊆ match(x) that are maximally infinite-contradictable by x, together with the singleton {c} for every c ∈ finVals(x). ▶ Example 4.2 (Witness sets). Over the bank schema, consider the queries q() ← Flagged(a), 100 ≤ a ≤ 200 q ′ () ← Flagged(u1 ), Flagged(u2 ), Flagged(u3 ), u1 < 150, u2 > 150, u3 ≥ 120

5

6

Shrinking the Family of Test Databases

We have match(a) = {u1 , u2 , u3 }, eDomq (a) = [100, 200], and Ea ({u1 }) = [150, 200], Ea ({u2 }) = [100, 150], and Ea ({u3 }) = [100, 120). Exactly two sets are maximally infinitecontradictable by a: the set {u1 }, since adding u2 leaves the finite set {150} and adding u3 leaves the empty set, and the set {u2 , u3 }, with witness [100, 120). The only finite Ea (S) is Ea ({u1 , u2 }) = {150}, so finVals(a) = {150} and Wa = { [150, 200], [100, 120), {150} }. ◀ A larger witness-set computation is given in Example B.1 in Appendix B.2. We now show a bound on the size of the witness set for any given variable. ▶ Proposition 4.3 (Upper bound on witness-set size). Let q and q ′ be queries, and let x be a variable in vars(q). Then, |Wx | ≤ 2 |match(x)| + 1 . The proof splits eDom(x) into maximal segments on which the set of incompatible matched variables is constant. There are at most 2|match(x)| + 1 such segments, since each variable of match(x) contributes two interval endpoints, and every witness occupies a segment of its own. To determine containment of q in q ′ , we create a set of canonical databases out of canonical values for the variables of q. For each x ∈ vars(q) and each witness E ∈ Wx , we define a constant c(x, E) as follows. If E = {c} is a singleton, then c(x, E) = c. Otherwise E is infinite, and c(x, E) is a constant chosen from E, distinct from all constants of q and q ′ , from S all values in x∈vars(q) finVals(x), and from the constants chosen for other infinite witnesses. The set of canonical values of x is c(x) = {c(x, E) : E ∈ Wx }. A canonical assignment θ maps each variable x of q to a canonical value in c(x), and Θq denotes the set of all canonical assignments. The canonical database θ(Dq ) is obtained from Dq (Section 2) by replacing each frozen variable v with the value θ(v). By construction, q outputs θ(x̄) over θ(Dq ) for every θ ∈ Θq . We write D(Θq ) for the set of all canonical databases for q. ▶ Example 4.4 (Running example, cont.). For the account variable a of Example 4.1, the only maximally infinite-contradictable set is {a′ }, with the infinite witness (100, 200) \ [150, 400] = (100, 150), so c(a) is a single value, say 120. Likewise Wm = {[2000, ∞)}, and the witness set of each of h, e, b, and r is {Q}, as no nonempty subset of its match set is contradictable. Thus, every variable in q has exactly one canonical value, yielding a single canonical database in D(Θq ), even though q has six variables and the two queries mention eight constants. In contrast, the construction of Klug [17] enumerates one canonical database for every ordering of these variables and constants. ◀ ▶ Theorem 4.5. Let q(x̄), q ′ (x̄) be CQvc queries. Then, q is contained in q ′ if and only if q(D) ⊆ q ′ (D) for all D ∈ D(Θq ). The nontrivial direction turns a valuation ν that witnesses ā ∈ q(D) into a valuation of q ′ over D. A canonical assignment θ is chosen to mimic ν: for every x ∈ vars(q), the value θ(x) avoids the effective domain of a matched variable in match(x) exactly when ν(x) does. By assumption, some valuation θ′ of q ′ produces θ(x̄) over θ(Dq ), and the composition ν ◦ θ−1 ◦ θ′ is the required valuation. The composition is well defined although θ is not injective, since variables that share a θ-value also share their ν-value, and it satisfies the comparison atoms of q ′ precisely because θ mimics ν.

4.2

Reducing to Independent Components

The number of canonical values of each variable x is at most 2|match(x)|+1, so by Theorem 4.5 Q deciding containment amounts to evaluating q ′ over all x∈vars(q) |c(x)| canonical databases. Often, far fewer suffice. Only variables that share an atom of q or realize a common atom of q ′ interact, so recombining the values of unrelated parts of q tests nothing new. Example 4.6 shows the redundancy concretely.

H. Sternbach and S. Cohen

▶ Example 4.6 (Running example for Section 4.2). We illustrate over four relations recording the transactions on each account: Deposit(amt, acct), Withdraw(amt, acct), Fee(amt, acct), and Interest(amt, acct): q() ← Deposit(d, a), Withdraw(w, a), Fee(f, a), Interest(g, a), 0 ≤ d, w ≤ 1000, 10 ≤ f, g ≤ 50 ′

q () ← Deposit(t, c1 ), Withdraw(t, c2 ), Deposit(v1 , c1 ), Withdraw(v2 , c2 ), Fee(v3 , c3 ), Interest(v4 , c4 ), v1 , v2 > 0, v3 , v4 > 10 In q ′ , the same amount t is deposited into one account and withdrawn from another, and each account also has a transaction with a positive amount. Only the variable a of q occupies more than one position, namely the second position of every atom, and POSq′ (t) = {(Deposit, 1), (Withdraw, 1)}. Here match(d) = {v1 }, and inside eDom(d) = [0, 1000] the variable v1 induces the finite witness Ed ({v1 }) = [0, 1000] \ (0, ∞) = {0}, so Wd = {[0, 1000], {0}} and |c(d)| = 2. The same computation for w, f, g gives two canonical values each, where the finite-witness value is the boundary constant 0 for d, w and 10 for f, g. These boundary constants are shared: 0 is a canonical value of both d and w, and 10 of both f and g. The account variable a is a hub: it appears in every atom, so the amount variables meet only through it. Matched only by the unconstrained c1 , . . . , c4 , it has a single canonical value. Once a value for a is fixed, whether the Fee atom of q ′ is realized depends on the value of f alone, and likewise for the other atoms. Joint variation of d, w, f, g is therefore largely redundant, and it should suffice to vary each amount variable around the hub separately. ◀ Two subtleties make this plan delicate. First, a single variable of q ′ may be realized through several variables of q that share a value: in Example 4.6, no variable of q matches t, yet q ′ realizes t on the databases where d and w both carry the shared boundary constant 0. Second, a single relational atom of q ′ may then depend on two parts at once: realizing Deposit(t, c1 ) and Withdraw(t, c2 ) requires d and w to take the value 0 together, so these two variables cannot be varied separately after all. We first capture the sharing phenomenon by a relaxation of the matching relation, and then build it into a graph whose components can be varied safely. Recall (Section 4.1) that boundary (finite-witness) values are constants of the queries and may be shared by several variables, while infinite-witness values are fresh and distinct. For a value a, the cohort Va = {x ∈ vars(q) | a ∈ c(x)} collects the variables of q that carry a as a canonical value, and sharing is exactly the situation |Va | ≥ 2. We say that a is a witness value for y ∈ vars(q ′ ) if (1) a ∈ eDom(y), and (2) the cohort of a collectively covers S every position of y, that is, x∈Va POSq (x) ⊇ POSq′ (y). We say that y covering-matches x, written x ∈ cmatch−1 (y) (equivalently y ∈ cmatch(x)), if some witness value for y is a canonical value of x. Collective covering is exactly what a homomorphism guarantees when it sends y to a shared value. Covering-match serves only to group the variables of q in the decomposition below. The canonical values are unchanged, so Theorem 4.5 is unaffected. ▶ Example 4.7 (Running example, cont.). The value 0 is a witness value for t: it lies in eDom(t) = Q, and d and w collectively cover POSq′ (t), although neither does alone. Hence cmatch−1 (t) ⊇ V0 = {d, w}, even though t has no ordinary match. All other variables of q ′ have singleton cohorts, on which the two notions of match coincide. ◀ S k For a relational atom A = R(y1 , . . . , yk ) of q ′ , write MA = t=1 cmatch−1 (yt ) for the variables of q covering-matched by some variable of A. The relational graph RG has vertex set

7

8

Shrinking the Family of Test Databases

C1

C2

d

f

x x1

x2

≤ 0

a g

w

x3

x4

y

10

z

C3 (a) The relational graph RG.

(b) The comparison graph CG. (c) The opposite graph OG.

Figure 1 The graphs of the running examples. In (a), the red edge is a co-match edge and the separator is shaded. In (b), red edges come from comparisons induced from q ′ . In (c), unlabeled edges are labeled <, and the red edges are the Ematch(q) edges.

vars(q), an atom edge between distinct x, x′ that occur together in a relational atom of q, and a co-match edge between distinct x, x′ ∈ MA for a relational atom A of q ′ . The co-match edge is what keeps d and w of the running example together. A separator S ⊆ vars(q) is legal if no variable of q ′ covering-matches two variables of S, that is, cmatch(x) ∩ cmatch(x′ ) = ∅ for all distinct x, x′ ∈ S. Given a legal separator S, let C1 , . . . , Cm be the connected components of RG − S. A subset Ψq ⊆ Θq of the canonical assignments of Section 4.1 is S-exhaustive if, for every θ ∈ Θq and every i ∈ [m], some ψ ∈ Ψq has ψ|S∪Ci = θ|S∪Ci . Intuitively, Ψq varies each component, together with the separator, independently of the other components. ▶ Example 4.8 (Running example, cont.). The relational graph RG (Figure 1a) has an atom edge between a and each of d, w, f, g, and the single co-match edge d − w, since d, w ∈ MDeposit(t,c1 ) . Although f and g also share a boundary constant, no variable of q ′ is collectively covered by them, so no co-match edge arises. The separator S = {a} is legal, and deleting it leaves C1 = {d, w}, C2 = {f }, and C3 = {g}. Without the co-match edge, d and w would fall in different components, and the atom Deposit(t, c1 ) of q ′ would no longer be realized inside a single one. ◀ ▶ Theorem 4.9. Let q(x̄) and q ′ (x̄) be CQvc queries, let S ⊊ vars(q) be a legal separator,
and let Ψq ⊆ Θq be S-exhaustive with
respect to the components of RG. If ψ(x̄) ∈ q ′ ψ(Dq ) for all ψ ∈ Ψq , then θ(x̄) ∈ q ′ θ(Dq ) for all θ ∈ Θq . The theorem assumes nothing about the canonical values: boundary constants may be shared and canonical assignments need not be injective. The proof stitches per-component witnesses into one. For θ ∈ Θq , S-exhaustiveness supplies for each component Ci a passing assignment ψi agreeing with θ on S ∪ Ci , and hence a valuation of q ′ into ψi (Dq ). The co-match edges confine all variables covering-matched by one atom of q ′ to a single component, so every atom of q ′ is realized inside one ψi (Dq ), and legality makes the component serving a variable that matches only the separator unambiguous. Covering-match keeps the stitching sound without injectivity: whatever value a valuation places at a variable y of q ′ is a witness value for y, so its whole cohort is confined to the one component serving y. Since Θq itself is S-exhaustive, the quantity of interest is the size of the smallest Sexhaustive family, i.e., the number of canonical databases tested by the decomposition when Ψq is chosen optimally. We record it next, with the complexity of choosing an optimal S.

H. Sternbach and S. Cohen

▶ Lemma 4.10. Let q, q ′ be CQvc queries, let S ⊆ vars(q) be a separator, and let C1 , . . . , Cm be of RG − S. The smallest S-exhaustive set Ψq ⊆ Θq has size Qthe connected  components Q v∈S |c(v)| · maxi∈[m] u∈Ci |c(u)|. ▶ Example 4.11 (Running example, cont.). For the running example, the full criterion tests Q 4 while the decomposition for S = {a} tests only x |c(x)| = 2 = 16 canonical databases,
|c(a)| · max |c(d)||c(w)|, |c(f )|, |c(g)| = 4. Adding further transfer pairs off the hub scales this gap geometrically, while the separator and largest component stay fixed. ◀ By Lemma 4.10, the size of the test is governed by the separator and the largest component of RG −S, so we seek the legal separator that minimizes |Ψq |. This optimization is intractable. ▶ Theorem 4.12. Given CQvc queries q, q ′ and an integer t, deciding whether RG has a legal separator whose smallest S-exhaustive family has size at most t is NP-complete, even when every variable of q has exactly two canonical values. The hardness is by reduction from Vertex Cover, through an intermediate graph problem defined in the appendix. Intractability does not affect correctness: every legal separator yields a sound and complete containment test, and only the family size depends on the choice, so in practice one fixes a legal separator heuristically.

4.3

Extending to Variable–Variable Comparisons

We now extend our results from CQvc to CQcmp , which also allows comparisons between variables. For this class, the witness sets alone no longer determine adequate canonical values, in either direction. When q contains a comparison between two variables, the witnesses of those variables may leave no values satisfying it. When only q ′ contains one, the constraint it induces between the variables of q that can realize its sides is invisible to the witness sets, and the test passes although containment fails. Example B.5 exhibits both. To capture these additional constraints, recall from Section 2 the variable–constant comparison atoms compvc (q) and the variable–variable comparison atoms compvv (q). ▶ Example 4.13 (Running example). An online-banking system logs sessions and maintenance windows in Session(login, logout) and Maint(start, end), with hours measured from midnight. q() ← Session(x1 , x2 ), Session(x1 , x4 ), Maint(x3 , x2 ), Maint(x3 , x4 ), x1 ≤ x2 , x1 ≤ x3 , x3 < x4 , 0 < x1 , x2 < 10, 0 < x3 < 20, 10 < x4 < 20 ′

q () ← Session(y1 , y2 ), Maint(y3 , y2 ), y1 ≤ y2 , y2 > y3 , 0 < y1 , y2 < 20 Here q asks for two sessions that log in together at hour x1 , and two maintenance windows that start together at hour x3 and end at the two logout hours. Its variable–variable atoms are compvv (q) = {x1 ≤ x2 , x1 ≤ x3 , x3 < x4 }, and compvv (q ′ ) = {y1 ≤ y2 , y2 > y3 }. The effective domains in q are eDom(x1 ) = eDom(x2 ) = (0, 10), eDom(x3 ) = (0, 20), and eDom(x4 ) = (10, 20), and the match sets are match(x1 ) = {y1 }, match(x2 ) = match(x4 ) = {y2 }, and match(x3 ) = {y3 }. ◀ We now focus on pairs of variables in q whose relative order may affect containment with respect to q ′ . Some pairs arise directly from variable–variable comparison atoms in q. Others are induced by variable–variable comparison atoms in q ′ under a relaxed form of matching. A valuation of q ′ over a canonical database may send y to a value shared by several variables of q, so we say that y ∈ vars(q ′ ) partially matches x ∈ vars(q) if

9

10

Shrinking the Family of Test Databases

POSq′ (y) ∩ POSq (x) ̸= ∅ and eDom(y) ∩ eDom(x) ̸= ∅. Formally, matchComp(q, q ′ ) contains x ⋖ x′ whenever some atom y ⋖ y ′ of compvv (q ′ ) has y partially matching x and y ′ partially matching x′ , and {x ⋖ x′ } ∪ compvv (q) is satisfiable. When q and q ′ are clear from the context, we simply write matchComp. The complete set of relevant inequalities is then relComp(q, q ′ ) = compvv (q) ∪ matchComp(q, q ′ ). The comparison graph CG is the undirected graph on the vertex set vars(q) with an edge between the two variables of each inequality in relComp(q, q ′ ). We denote by Comp(CG) the set of connected components of CG. We emphasize that CG is not the relational graph RG of Section 4.2: RG groups variables whose canonical values must be varied jointly, whereas CG records the order relations among the variables, to reduce the number of orderings considered. ▶ Example 4.14 (Running example, cont.). Since compvv (q ′ ) = {y1 ≤ y2 , y2 > y3 }, the match sets above yield matchComp(q, q ′ ) = {x1 ≤ x2 , x1 ≤ x4 , x3 < x2 , x3 < x4 }, so relComp(q, q ′ ) = {x1 ≤ x2 , x1 ≤ x3 , x3 < x4 , x1 ≤ x4 , x3 < x2 }. The comparison graph CG, shown in Figure 1b, consists of a single connected component C1 = {x1 , x2 , x3 , x4 }. ◀ For every nontrivial connected component C ∈ Comp(CG), let K(C) = {k1 , . . . , kp }, where k1 < · · · < kp , be the set of all constants that appear in comparison atoms of q involving a variable of C, or in comparison atoms of q ′ involving a variable that partially matches some variable of C. These constants partition the rationals into the singleton intervals {ki } and the open intervals between consecutive constants, and we let Inter(C) = {(−∞, k1 ), {k1 }, (k1 , k2 ), {k2 }, . . . , {kp }, (kp , ∞)} denote the set of all these intervals. For every interval I ∈ Inter(C), let varsC,I = {x ∈ C | I ⊆ eDom(x)} be the set of active variables of C on I, that is, the variables that may be assigned a value anywhere in I. Note that, by construction, for every x ∈ C and every I ∈ Inter(C), the intersection eDom(x) ∩ I is either empty or equal to I. Next, we select representative values repvalsC,I for each interval I ∈ Inter(C). If I is an open interval, let ℓ = |varsC,I |. We choose values α1C,I < α2C,I < . . . < αℓC,I in I, and set repvalsC,I = {α1C,I , . . . , αℓC,I }. We choose these values to be distinct from all constants appearing in q and q ′ and from all canonical values chosen for other components, which is possible since I contains infinitely many values. If I = {k} is a singleton interval, then each variable in varsC,I can take only the value k in this interval, and we set repvalsC,I = {k}. Not every active variable may take every representative value of an open interval I. Think of the representatives α1C,I < · · · < αℓC,I as ordered positions, occupied by the active variables in increasing order of their values, where variables with equal values share a position. If q entails x ≤ y then y never lies below x, so fewer positions are open to x. Accordingly, let rmaxI (x) be ℓ minus the number of active variables y ̸= x on I for which the comparison atoms of q entail x ≤ y. Only the lowest rmaxI (x) representatives need be available to x, and we set repvalsC,I (x) = {αjC,I | 1 ≤ j ≤ rmaxI (x)}. For a singleton interval I = {k}, we set repvalsC,I (x) = {k} for every x ∈ varsC,I . We now define, for every variable x ∈ vars(q), its set of canonical values, denoted by c(x). If x is an isolated vertex, then c(x) is defined as in the construction for queries in the class CQvc , namely c(x) = {c(x, E) : E ∈ Wx }. If x belongs to a connected component C ∈ Comp(CG) with more than one vertex, then we collect, over the intervals in which x is active, the representS ative values consistent with its rank, c(x) = I∈Inter(C) repvalsC,I (x). Whenever a canonical x∈varsC,I

value is chosen arbitrarily, either from an infinite witness subdomain or as a representative of an open interval, we choose it to be distinct from all canonical values that were already fixed, in particular from all values that come from finite witness subdomains and singleton intervals. A canonical assignment θ is a mapping from the variables of q to canonical values such

H. Sternbach and S. Cohen

that θ(x) ∈ c(x) for every x ∈ vars(q), and θ satisfies all comparison atoms of q. We denote by Θq the set of all canonical assignments. For each θ ∈ Θq , let Dθ := θ(Dq ), and define D(Θq ) = {Dθ | θ ∈ Θq } to be the set of all canonical databases. ▶ Example 4.15 (Running example, cont.). Here K(C1 ) = {0, 10, 20}. The active sets are varsC1 ,(0,10) = {x1 , x2 , x3 }, varsC1 ,{10} = {x3 }, and varsC1 ,(10,20) = {x3 , x4 }, with representatives {2, 6, 8}, {10}, and {12, 17}, respectively. Rank trimming trims two variables: q entails x1 ≤ x2 and x1 ≤ x3 , so rmax(0,10) (x1 ) = 3 − 2 = 1 and x1 keeps only {2}, and the atom x3 < x4 leaves x3 only {12} in (10, 20). We have c(x1 ) = {2}, c(x2 ) = {2, 6, 8}, c(x3 ) = {2, 6, 8, 10, 12}, c(x4 ) = {12, 17}. Every canonical assignment fixes x1 7→ 2, so Θq consists of |c(x2 )| · |{(x3 , x4 ) ∈ c(x3 ) × c(x4 ) | x3 < x4 }| = 3 · 9 = 27 assignments. ◀ ▶ Theorem 4.16. Let q(x̄), q ′ (x̄) be CQcmp queries. Then q is contained in q ′ if and only if q(D) ⊆ q ′ (D) for all D ∈ D(Θq ). The proof parallels that of Theorem 4.5, with the canonical assignment chosen componentwise. What is new is the relation it must meet: within each connected component of CG, θ reproduces the order and equalities of a satisfying valuation ν and keeps every variable in the same interval, while isolated variables are treated as before. A witness for q ′ over θ(Dq ) then transports back, the variable–variable atoms holding because θ orders each component exactly as ν does. In [17], containment is checked over canonical databases for all possible orderings of the variables of q together with all constants of the two queries. Theorem 4.16 reduces this construction twice over: only the orderings within each connected component of CG are considered, and each component is ordered only against the constants relevant to it.

4.4

Splitting on Order Conflicts

The test of Theorem 4.16 still enumerates, within each connected component of CG, every ordering of the variables consistent with q. Most of them carry no information. The test only probes whether the order of q can be arranged so as to violate a comparison induced from q ′ . This section isolates the pairs on which the two queries disagree. An order that the induced comparisons do not contest may be imposed on q outright. What resists is a cyclic conflict. Splitting on the three possible orders of the pair it relates settles such a conflict, and each case pins the whole component to a single assignment. Comparison atoms may be added independently in each component of CG, so we fix one component C throughout. All the order information relevant to C fits into a single directed graph, defined as follows. The opposite graph OG = (V, Eq ∪ Ematch(q) ) has the vertex set V = vars(C) ∪ K(C). Each of its edges points upward in the order and is labeled < or ≤ by the strictness of the relation it records. The set Eq records the order that q forces. It has a constant edge between consecutive constants of K(C), an endpoint edge between each x ∈ vars(C) and each finite endpoint of eDom(x), and an atom edge for every comparison atom u ⋖ v of q. Every canonical assignment satisfies all of Eq . The set Ematch(q) records what the test is hunting for. A comparison atom y1 ⋖ y2 of q ′ with y1 partially matching x1 and y2 partially matching x2 , where x1 , x2 ∈ vars(C), induces the relation x1 ⋖ x2 . If the comparison atoms and constants of q already decide this relation, it receives the same verdict in every canonical database, and no edge is added. Otherwise we add the reverse edge x2 → x1 , labeled with the operator ⋖′ opposite in strictness to ⋖. Satisfying that edge is exactly violating the induced relation. Induced comparisons against a constant of K(C) are handled identically, with the constant as an endpoint.

11

12

Shrinking the Family of Test Databases

An order that no reverse edge contests may be imposed on q for free. Call x1 < x2 a candidate comparison if the comparison atoms of q imply no strict order between x1 and x2 , so that the pair is unordered or ordered only non-strictly. Call it addable if, in addition, OG has no path from x2 to x1 . The path condition keeps the addition from forcing further relations by transitivity. ▶ Example 4.17 (Running example). Consider the hourly events Login, Backup and Audit, and the pair q() ← Login(x), Backup(y), Audit(z), ′

′

′

0 < x, y, z < 10, x ≤ y, ′′

′′

q () ← Backup(y ), Audit(z ), Backup(y ), Audit(z ),

y ′ ≤ z ′ , z ′′ ≤ y ′′ .

The atoms of q ′ induce y ≤ z and z ≤ y, neither decided by q, so CG has the single nontrivial component C = {x, y, z}, with K(C) = {0, 10}. Each induced comparison contributes a reverse edge, labeled < (Figure 1c), and the two form the only directed cycle of OG. The pair x < z is a candidate comparison, since q implies no order between x and z, and it is addable: OG has no path from z to x. ◀ ▶ Theorem 4.18. Let x1 < x2 be an addable comparison, where x1 , x2 ∈ vars(C), and let q ∗ be obtained from q by adding it to the body of q. Then, q ⊆ q ′ ⇐⇒ q ∗ ⊆ q ′ . The nontrivial direction reorders a canonical database witnessing q ̸⊆ q ′ along a topological order of OG, so that it witnesses q ∗ ̸⊆ q ′ as well. Only the absence of a reverse path is used, so the theorem also covers variable–constant candidate comparisons, with the constant fixed. Applied repeatedly, the theorem orders more and more pairs. What it cannot order is a pair on a directed cycle of OG. In either direction, the cycle supplies the forbidden reverse path. A cycle inside Eq merely reflects an equality that q already forces. The genuine obstruction is a cycle through a reverse edge, where a comparison induced from q ′ conflicts cyclically with the order constraints of q. We call the reverse edges lying on a directed cycle of OG the cycle reverse edges, and write Ecycle ⊆ Ematch(q) for their set. We split q on them. Each cycle reverse edge e = (u → v) admits three cases, namely u < v, u = v and v < u. A choice σ ∈ {<, =, >}Ecycle picks one case for every e ∈ Ecycle , and the trichotomy query qσ adds the picked cases to q. It thereby fixes the full order relation between the endpoints of every cycle reverse edge. We call the restrictions to vars(C) of the canonical assignments of q the local assignments of C, and write Θq ↾C for their set. The test of Theorem 4.16 enumerates these inside C. ▶ Theorem 4.19. q ⊆ q ′ if and only if qσ ⊆ q ′ for every trichotomy query qσ . Moreover, each qσ is tested over at most one local assignment. The case split holds because every satisfying valuation of q realizes exactly one of the three cases of each cycle reverse edge. For the single-assignment claim, merging the variables that qσ equates leaves an opposite graph with no reverse edge on a cycle, so the theorem above strictly orders every pair, and rank trimming then leaves each variable a single representative. So C contributes at most 3|Ecycle | local assignments, and fewer when some qσ is unsatisfiable. The trichotomy family fixes the order of every cycle reverse edge separately, although breaking each cycle once already removes the obstruction. Call a directed cycle of OG non-strict when every edge on it is labeled ≤, and suppose OG has none. Then the minimal sets of reverse edges that break all cycles suffice. A set E ⊆ Ecycle is a match feedback edge set (MFES) if the graph (V, Eq ∪ (Ematch(q) \ E)) is acyclic, and a minimal MFES if no proper subset of E is one. For each minimal MFES Ei of OG, the feedback query qi adds to q the relation u ⋖ v asserted by ⋖ every cycle reverse edge u → v outside Ei , and the negation v ⋖′ u of every such edge in Ei .

H. Sternbach and S. Cohen

▶ Example 4.20 (Running example, cont.). Both reverse edges of Example 4.17 lie on its directed cycle, so Ecycle = {y → z, z → y} and the minimal MFESs are E1 = {y → z} and E2 = {z → y}. For E1 , the kept edge z → y contributes z < y and the removed edge its negation z ≤ y, so q1 is equivalent to q ∧ z < y. Symmetrically, q2 is equivalent to q ∧ y < z. With the representatives {2, 6, 8}, the test of Theorem 4.16 runs over the 15 local assignments of Θq↾C , the trichotomy split over 32 = 9 cases, and each feedback query over a single one. Since C holds every variable of q, two canonical databases decide the containment. ◀ ▶ Theorem 4.21. Assume that OG has no non-strict cycle. Then q ⊆ q ′ if and only if qi ⊆ q ′ for every minimal MFES Ei of OG. Moreover, these feedback queries, each together with its local assignment, can be generated with polynomial delay in the sizes of q and q ′ . The forward direction is immediate. For the converse, the cycle reverse edges violated by a witnessing assignment contain a minimal MFES Ei , and rebuilding along a topological order of the rest, as in Theorem 4.18, witnesses qi ̸⊆ q ′ . The opposite graph of each pair (qi , q ′ ) is acyclic, so saturation pins one local assignment, and the minimal MFESs are exactly the minimal feedback vertex sets of a digraph on Ecycle , enumerable with polynomial delay [26]. The assumption cannot be dropped. Take q() ← R(x, y), R(y, x) and q ′ () ← R(u, v), R(u′ , v ′ ), u < v, v ′ < u′ , whose opposite graph is the non-strict cycle x → y → x. Containment fails exactly on the canonical databases with θ(x) = θ(y), so the two feedback queries, q ∧ y < x and q ∧ x < y, both miss it and are contained in q ′ . The trichotomy split still decides the pair, through the case sending both cycle edges to =.

5

Combining Nulls and Comparisons

A query in CQcmp,⊥ has comparison atoms and is evaluated under the three-valued semantics of Section 2, over databases that may contain ⊥. Its subclass CQvc,⊥ allows only variable– constant comparisons. The two features meet in exactly one place. A comparison with a ⊥ argument is unsatisfied, so a variable occurring in a comparison atom is never nulled. Nulling and ordering therefore act on disjoint variables, and the constructions of Sections 3 and 4 compose instead of interfering. For a query q, let compVars(q) be the variables of its comparison atoms, and let nonnull(q) = join(q) ∪ compVars(q) be its variables that cannot take the value ⊥. Let VCJ consist of the covered variables v of Section 3 with POSq (v) = POSq′ (w′ ) for some w′ ∈ nonnull(q ′ ), and set
Vt = VCJ \nonnull(q), Vn = vars(q)\ nonnull(q)∪VC ∪head(q) , Vf = vars(q)\(Vt ∪Vn ). This is the partition of Section 3 with nonnull in place of join, in both queries. A compared variable is non-null for the same reason a join variable is, so it plays the same role on each side. On the side of q ′ it forces a covered variable of q to be toggled, and on the side of q it is frozen. A combined assignment θ sends each x to a value in c(x) if x ∈ Vf , to ⊥ if x ∈ Vn , and to either if x ∈ Vt . Its non-⊥ part satisfies the comparison atoms of q. The set of variables that θ sends to ⊥ is its null pattern, and the combined canonical family is Dcomb (q, q ′ ) = {θ(Dq ) | θ combined}. ▶ Theorem 5.1 (Combined characterization). For q, q ′ ∈ CQcmp,⊥ , q ⊆⊥ q ′ if and only if q(D) ⊆ q ′ (D) for every D ∈ Dcomb (q, q ′ ). The proof follows those of Theorems 3.3 and 4.16. A combined assignment mimics a satisfying valuation of q in both features at once, and a witness for q ′ then transports back.

13

14

Shrinking the Family of Test Databases

What is new is that the two halves must agree on which variables may be nulled, and nonnull(q ′ ) in place of join(q ′ ) is what makes them agree. A variable of nonnull(q ′ ) landing on a covered variable that is frozen rather than toggled would place it in VCJ , contradicting its membership in VCN , and this one argument settles join and compared variables alike. Let the value count val(u) be the number of values a combined assignment may give u, namely 1, |c(u)|, or |c(u)| + 1 according as u ∈ Vn , u ∈ Vf , or u ∈ Vt . For the trivial components of CG these choices are independent, so they contribute the product of the counts. Inside a nontrivial component they are not. Its variables draw their values from the representatives of Section 4.3 and must realize a common ordering, so the component contributes its orderings rather than a product. The trichotomy split of Section 4.4 removes the exception. For every nontrivial component C we build its opposite graph on the vertices S outside Vn , write Ecycle (C) for its cycle reverse edges, and let Ecycle (q) = C Ecycle (C). Nulling a vertex removes every cycle through it, so a null pattern can only shrink the case split, and each case still forces C to a single local assignment. Within a case a variable of a nontrivial component therefore has a single value, or two if it lies in Vt , and we use these counts for such variables and the counts above for all others. Two points remain about the decomposition of Section 4.2. First, we treat ⊥ as a canonical value of every variable of Vn ∪ Vt , so that the covering-matches account for it, and we read RG accordingly. Second, RG is now too coarse. A component of CG is pinned as a whole, so its variables can no longer be varied independently, and a variable–variable comparison atom of q ′ constrains the values realized for its two sides together. We therefore obtain RG + from RG by adding a clique on every nontrivial component of CG and, for each variable–variable comparison atom y ⋖ y ′ of q ′ , a clique on cmatch−1 (y) ∪ cmatch−1 (y ′ ). Deleting a legal separator of RG + leaves each of these sets inside a single piece, as the stitching of Theorem 4.9 requires. On CQvc,⊥ every component of CG is trivial, so Ecycle (q) = ∅ and RG + = RG. Write ∆ = maxx |match(x)| for the largest match set. The width of RG + is w = minS (|S| + maxi |Ci |), over its legal separators S. ▶ Theorem 5.2 (Combined multiplicity). Let q, q ′ ∈ CQcmp,⊥ . For a legal separator S of RG + with components C1 , . . . , Cm of RG + − S, containment q ⊆⊥ q ′ is decided by Y  Y 3 |Ecycle (q)| · val(v) · max val(u) ≤ 3 |Ecycle (q)| (2∆ + 2) |S|+maxi |Ci | v∈S

i∈[m]

u∈Ci

canonical databases. The size of the family is therefore fixed-parameter tractable in (∆, w, |Ecycle (q)|), and on CQvc,⊥ in (∆, w). Replacing a component by its forced local assignment leaves the null pattern untouched, so the covering-match decomposition applies with the value counts above. The numeric bound holds because val(u) ≤ 2|match(u)| + 2 ≤ 2∆ + 2 by Proposition 4.3. ▶ Corollary 5.3. If ∆, w and |Ecycle (q)| are constant, containment is in NP, and in P when q ′ admits polynomial evaluation. If no opposite graph has a non-strict cycle, then 3 |Ecycle (q)| Q improves to C ℓC , where ℓC is the number of minimal MFESs of the opposite graph of C. All three parameters are local. The largest match set ∆ measures how many variables of q compete for a single variable of q, the width w measures the separator structure of RG + , and |Ecycle (q)| counts the comparisons induced from q ′ that conflict cyclically with the order of q. None of them grows with the size of the queries on its own. Finding a legal separator that minimizes w is NP-complete even for RG (Theorem 4.12), and Ecycle (q) is empty whenever the induced comparisons create no cyclic conflict. The bound accordingly specializes to that of Lemma 4.10 in the absence of nulls and of variable–variable comparisons, and to the bound 2|Vt | of Theorem 3.3 in the absence of comparisons. Over null-free databases ′

H. Sternbach and S. Cohen

the feedback queries and their local assignments are moreover generated with polynomial delay (Theorem 4.21). A worked example, computing the three parameters and the resulting family, is given in Example B.16.

6

Related Work

Containment and equivalence of conjunctive queries were characterized by Chandra and Merlin [5] through containment mappings, and the theory was extended to relational expressions with union and difference by Aho, Sagiv, and Ullman [3] and by Sagiv and Yannakakis [24]. Containment of CQs is NP-complete, with tractable fragments including acyclic queries [30], restricted fanout [25, 23] and bounded treewidth [8], and Barceló et al. [4] study when tractability of evaluation transfers to containment. Klug [17] showed that the homomorphism criterion does not extend to conjunctive queries with inequalities, although it remains complete for semi-interval queries, and gave a Πp2 upper bound for containment through the canonical databases of all orderings of the variables. Van der Meyden [28] established the matching lower bound. Kolaitis, Martin, and Thakur [18] located the boundary between the NP-complete and Πp2 -complete cases of inequality predicates. Afrati, Li, and Mitra [1] identify further classes of queries with arithmetic comparisons for which homomorphism-based tests remain complete. Afrati and Damigos [2] chart the semi-interval case, separating the classes in which a single containment mapping certifies containment from those that remain Πp2 -complete, and bounding the number of mappings required. Their axis is the size of the mapping disjunction. Ours is orthogonal, counting canonical databases, of which the homomorphism-complete cases are the single-database endpoint. Farré et al. [12] showed that null-containment is ΠP 2 -complete in general and NP-complete for Boolean queries, and characterized it through the null versions of the canonical database (Theorem 3.2). They also give a sufficient but not necessary condition, a homomorphism mapping every join variable to a join variable or a constant, which is itself NP-complete to decide. On the practical side, SQL equivalence checkers are one-sided. Symbolic provers certify equivalence on restricted syntactic fragments and return no counterexamples [34, 33, 11, 29]. Bounded checkers search for a counterexample database up to a size bound and certify nothing beyond it [10, 13, 31, 16], and test-generation tools guarantee only coverage of a criterion or a mutation space [6, 9, 21]. We instead delimit families of databases whose passing certifies containment outright.

7

Conclusion

This paper asked how few test databases suffice to decide containment, for two classes in which one database does not: CQs over databases with nulls, and CQs with order comparisons. For nulls, only the toggled variables need vary, giving 2|Vt | test databases in place of 2|njoin(q)| . For comparisons, canonical values from witness sets decide containment, and the family shrinks by decomposition and by splitting along the cyclic order conflicts. Combined, the number of test databases is fixed-parameter tractable in three local parameters, small for many query pairs. Several directions remain open. The nearest is to admit disequality atoms (s = ̸ s′ ), whose effective domains are unions of intervals rather than intervals. Further out lie other semantics and richer languages. Under bag semantics two CQs are equivalent exactly when they are isomorphic, while containment remains open, and slight extensions already make it undecidable [7, 14, 20], so it is not clear what a canonical-database test should even be. Aggregation, unions and negation are beyond our constructions as well. Finally, our families are generated in no particular order, while a checker hoping to refute [13, 31] wants a distinguishing database early.

15

16

Shrinking the Family of Test Databases

References 1

2

3 4

5

6

7

8 9

10

11

12

13

14

15

16

17

Foto Afrati, Chen Li, and Prasenjit Mitra. On containment of conjunctive queries with arithmetic comparisons. In International Conference on Extending Database Technology, pages 459–476. Springer, 2004. Foto N. Afrati and Matthew Damigos. Semi-interval comparison constraints in query containment and their impact on certain answer computation. arXiv preprint arXiv:2509.10138, 2025. Alfred V. Aho, Yehoshua Sagiv, and Jeffrey D. Ullman. Equivalences among relational expressions. SIAM Journal on Computing, 8(2):218–246, 1979. Pablo Barceló, Miguel Romero, and Moshe Y Vardi. Does query evaluation tractability help query containment? In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 188–199, 2014. URL: https://dl.acm.org/doi/pdf/ 10.1145/2594538.2594553. Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 77–90, 1977. URL: https://dl.acm.org/doi/abs/10.1145/800105.803397. Bikash Chandra, Bhupesh Chawda, Biplab Kar, K. V. Maheshwara Reddy, Shetal Shah, and S. Sudarshan. Data generation for testing and grading SQL queries. The VLDB Journal, 24(6):731–755, 2015. Surajit Chaudhuri and Moshe Y Vardi. Optimization of real conjunctive queries. In Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 59–70, 1993. URL: https://dl.acm.org/doi/pdf/10.1145/153850.153856. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211–229, 2000. Chunyu Chen, Zhengjie Miao, Yong Zhang, and Jiannan Wang. Parseval: Plan-aware test database generation for SQL equivalence evaluation. Proceedings of the VLDB Endowment, 18(11):4750–4762, 2025. doi:10.14778/3749646.3749727. Shumo Chu, Konstantin Weitz, Alvin Cheung, and Dan Suciu. Cosette: An automated prover for SQL. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), 2017. Haoran Ding, Zhaoguo Wang, Yicun Yang, Dexin Zhang, Zhenglin Xu, Haibo Chen, Ruzica Piskac, and Jinyang Li. Proving query equivalence using linear integer arithmetic. Proceedings of the ACM on Management of Data, 1(4):227:1–227:26, 2023. doi:10.1145/3626768. Carles Farré, Werner Nutt, Ernest Teniente, and Toni Urpí. Containment of conjunctive queries over databases with null values. In International Conference on Database Theory, pages 389–403. Springer, 2007. URL: https://link.springer.com/chapter/10.1007/11965893_27. Yang He, Pinhan Zhao, Xinyu Wang, and Yuepeng Wang. Verieql: Bounded equivalence verification for complex SQL queries with integrity constraints. Proceedings of the ACM on Programming Languages, 8(OOPSLA1):1071–1099, 2024. doi:10.1145/3649849. T. S. Jayram, Phokion G. Kolaitis, and Erik Vee. The containment problem for REAL conjunctive queries with inequalities. In Proceedings of the twenty-fifth ACM SIGMODSIGACT-SIGART symposium on Principles of database systems, pages 80–89, 2006. URL: https://dl.acm.org/doi/abs/10.1145/1142351.1142363. Heegyu Kim, Jeon Taeyang, SeungHwan Choi, Seungtaek Choi, and Hyunsouk Cho. FLEX: Expert-level false-less EXecution metric for text-to-SQL benchmark. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics, NAACL 2025, 2025. Rocky Klopfenstein, Yang He, Andrew Tremante, Yuepeng Wang, Nina Narodytska, and Haoze Wu. Spotit: Evaluating text-to-SQL evaluation with formal verification. In The Fourteenth International Conference on Learning Representations, ICLR 2026, 2026. arXiv:2510.26840. Anthony Klug. On conjunctive queries containing inequalities. Journal of the ACM (JACM), 35(1):146–160, 1988. URL: https://dl.acm.org/doi/pdf/10.1145/42267.42273.

H. Sternbach and S. Cohen

18

19 20

21

22

23

24 25 26 27

28

29

30

31

32

33

34

Phokion G Kolaitis, David L Martin, and Madhukar N Thakur. On the complexity of the containment problem for conjunctive queries with built-in predicates. In Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 197–204, 1998. URL: https://dl.acm.org/doi/pdf/10.1145/275487.275510. Alon Y Levy and Yehoshua Sagiv. Queries independent of updates. In VLDB, volume 93, pages 171–181, 1993. URL: https://www.vldb.org/conf/1993/P171.PDF. Jerzy Marcinkowski and Mateusz Orda. Bag semantics conjunctive query containment: Four small steps towards undecidability. Proceedings of the ACM on Management of Data, 2(2):103:1–103:24, 2024. URL: https://dl.acm.org/doi/10.1145/3651604. Zhengjie Miao, Sudeepa Roy, and Jun Yang. Explaining wrong queries using small examples. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD 2019, pages 503–520, 2019. doi:10.1145/3299869.3319866. Vivek R. Narasayya and Surajit Chaudhuri. Leveraging query optimizers to verify the soundness of LLM-based query rewrites for real-world workloads, and more. In 16th Conference on Innovative Data Systems Research, CIDR 2026, 2026. Yehoshua Sagiv and Yatin Saraiya. Minimizing restricted-fanout queries. Discrete Applied Mathematics, 40(2):245–264, 1992. URL: https://www.researchgate.net/publication/ 220569961_Minimizing_Restricted-Fanout_Queries. Yehoshua Sagiv and Mihalis Yannakakis. Equivalences among relational expressions with the union and difference operators. Journal of the ACM, 27(4):633–655, 1980. Yatin P Saraiya. Subtree-elimination algorithms in deductive databases. Stanford University, 1991. URL: https://apps.dtic.mil/sti/pdfs/ADA323806.pdf. Benno Schwikowski and Ewald Speckenmeyer. On enumerating all minimal solutions of feedback problems. Discrete Applied Mathematics, 117(1–3):253–265, 2002. Jeffrey D Ullman. Information integration using logical views. In International Conference on Database Theory, pages 19–40. Springer, 1997. URL: https://www.sciencedirect.com/ science/article/pii/S0304397599002194. Ron Van Der Meyden. The complexity of querying indefinite data about linearly ordered domains. In Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 331–345, 1992. URL: https://dl.acm.org/doi/pdf/10. 1145/137097.137902. Shuxian Wang, Sicheng Pan, and Alvin Cheung. QED: A powerful query equivalence decider for SQL. Proceedings of the VLDB Endowment, 17(11):3602–3614, 2024. doi:10.14778/ 3681954.3682024. Mihalis Yannakakis. Algorithms for acyclic database schemes. In Proceedings of the seventh international conference on Very large data bases, pages 82–94. VLDB Endowment, 1981. URL: https://dl.acm.org/doi/abs/10.5555/645919.672836. Pinhan Zhao, Yuepeng Wang, and Xinyu Wang. Polygon: Symbolic reasoning for SQL using conflict-driven under-approximation search. Proceedings of the ACM on Programming Languages, 9(PLDI):1315–1340, 2025. doi:10.1145/3729303. Ruiqi Zhong, Tao Yu, and Dan Klein. Semantic evaluation for text-to-SQL with distilled test suites. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, 2020. Qi Zhou, Joy Arulraj, Shamkant B. Navathe, William Harris, and Jinpeng Wu. SPES: A symbolic approach to proving query equivalence under bag semantics. In 38th IEEE International Conference on Data Engineering, ICDE 2022, 2022. Qi Zhou, Joy Arulraj, Shamkant B. Navathe, William Harris, and Dong Xu. Automated verification of query equivalence using satisfiability modulo theories. Proceedings of the VLDB Endowment, 12(11):1276–1288, 2019. doi:10.14778/3342263.3342267.

17

18

Shrinking the Family of Test Databases

A

Use of Artificial Intelligence

We disclose the following uses of Anthropic’s Claude Code. During the exploratory stages of the research, we used the tool to search for potential counterexamples to tentative hypotheses and to perform preliminary sanity checks. All proof strategies, constructions, mathematical arguments, and case analyses presented in the paper were developed by the authors. We additionally used Claude Code to draft portions of the appendices from detailed author-prepared outlines. The resulting prose was thoroughly reviewed and revised by the authors, and all mathematical statements, proofs, and citations in the final paper were independently checked and validated. The authors bear full responsibility for the content of the paper.

B

Full Proofs

B.1

Proofs for Section 3

Proof of Theorem 3.3. Recall that CQ⊥ queries contain only relational atoms, so a satisfying valuation of q ′ over a database D is a map h : vars(q ′ ) → adom(D), where adom(D) is the set of values occurring in the tuples of D, that places every relational atom of q ′ into D and sends every join variable of q ′ to a non-⊥ value. We use two elementary facts about position sets. First, every non-join variable of q has a single occurrence, hence a singleton position set. Second, being covered, and lying in VCJ or VCN , depends only on a variable’s position set: if v, v ′ ∈ njoin(q) satisfy POSq (v) = POSq (v ′ ), then v is covered (respectively, in VCJ , in VCN ) iff v ′ is, since each of these conditions is phrased entirely in terms of the position set. The matching homomorphism. Let M ⊆ njoin(q), and suppose q ′ returns θM x̄ over θM Dq , witnessed by a valuation h. Every value of adom(θM Dq ) is either ⊥ or a frozen variable u ∈ /M (identified with its constant), and every tuple of θM Dq is the θM -image of a relational atom of q. Hence for each atom R(ȳ) of q ′ we may fix an atom R(ū) of q with h(ȳ) = θM (ū). Reading off, for each occurrence of a variable y of q ′ at a position p, the variable of the matched q-atom at position p, defines a map ϕ : vars(q ′ ) → vars(q). This is well defined. A non-join variable of q ′ has a single occurrence. If y is a join variable then h(y) ̸=⊥ is a frozen variable w∈ / M , so θM maps the matched variable at every occurrence of y to the constant w, forcing that variable to be w. Thus ϕ(y) = w ∈ / M for join y, independently of the occurrence chosen. By construction ϕ maps each atom R(ȳ) of q ′ to the atom R(ϕ(ȳ)) of q, i.e. it is a homomorphism from the relational body of q ′ to that of q, and it satisfies (h1) ϕ(u) ∈ / M for every join variable u of q ′ ;
(h2) θM ϕ(x′i ) = θM (xi ) for every head position i, where (h2) restates h(x̄′ ) = θM x̄ via θM ◦ ϕ = h. Conversely, for any N ⊆ njoin(q), a homomorphism ϕ from the relational body of q ′ to that of q satisfying (h1) and (h2) with M := N gives the valuation θN ◦ϕ, which witnesses that q ′ returns θN x̄ over θN Dq : relational atoms are satisfied because ϕ is a homomorphism, each join variable u has θN (ϕ(u)) ̸=⊥ by (h1), and the output is θN x̄ by (h2). We use this criterion in both directions. For the forward direction, if q ⊆⊥ q ′ , then by Theorem 3.2, q ′ returns the head of q over every null version of Dq . Since each member of the family is a null version θV ∪Vn Dq with V ∪ Vn ⊆ njoin(q), q ′ returns the head of q over every member of the family. For the converse, assume that q ′ returns θV ∪Vn x̄ over θV ∪Vn Dq for every V ⊆ Vt . By Theorem 3.2, it suffices to fix an arbitrary N ⊆ njoin(q) and show that q ′ returns θN x̄

H. Sternbach and S. Cohen

over θN Dq . We will use the identity Vn = vars(q) \ join(q) ∪ VC ∪ head(q) , which follows immediately from Vf ∪ Vt = join(q) ∪ VC ∪ head(q) and the definitions of Vf , Vt , and Vn . We first observe that POSq′ (x′i ) ⊆ POSq (xi ) for every head position i. Indeed, take V = ∅, so the corresponding member of the family is θVn Dq . Since head(q) ∩ Vn = ∅, every head variable is frozen. Let ψ be a matching homomorphism witnessing that q ′ returns over this database. By (h2), θVn (ψ(x′i )) = θVn (xi ) = xi , hence ψ(x′i ) = xi . Since ψ is a homomorphism, every position of x′i in q ′ is therefore a position of xi in q. Now set V := Vt ∩ N and M := V ∪ Vn . By hypothesis, q ′ returns θM x̄ over θM Dq . Let ϕ be a matching homomorphism witnessing this, so ϕ satisfies (h1) and (h2) for M . We show that the same ϕ satisfies both conditions for N . Condition (h2). Fix a head position i. Since xi ∈ head(q), we have xi ∈ / Vn , and hence xi ∈ M iff xi ∈ V . If xi ∈ / V , then xi ∈ / M , so θM (xi ) = xi . By (h2) for M , ϕ(x′i ) = xi , and therefore ′ θN (ϕ(xi )) = θN (xi ). If xi ∈ V = Vt ∩ N , then θM (xi ) =⊥, so (h2) for M gives ϕ(x′i ) ∈ M . We claim that ϕ(x′i ) ∈ N . Since M = V ∪ Vn and V ⊆ N , it remains only to rule out ϕ(x′i ) ∈ Vn . Suppose e := ϕ(x′i ) ∈ Vn . Then e ∈ njoin(q), so POSq (e) is a singleton, and since ϕ is a homomorphism, POSq′ (x′i ) ⊆ POSq (e). We also have POSq′ (x′i ) ⊆ POSq (xi ) by the observation above, while POSq (xi ) is a singleton because xi ∈ N ⊆ njoin(q). Since POSq′ (x′i ) is nonempty, POSq (e) = POSq′ (x′i ) = POSq (xi ). But xi ∈ Vt ⊆ VC is covered, so e is covered as well, contradicting e ∈ Vn . Thus ϕ(x′i ) ∈ V ⊆ N , and hence θN (ϕ(x′i )) =⊥= θN (xi ). Condition (h1). Let u be a join variable of q ′ . By (h1) for M , ϕ(u) ∈ / M = V ∪ Vn . Suppose towards a contradiction that ϕ(u) ∈ N . Since N ⊆ njoin(q), POSq (ϕ(u)) is a singleton, say {(R, c)}. As ϕ is a homomorphism and u occurs in q ′ , POSq′ (u) ⊆ POSq (ϕ(u)) = {(R, c)}, and hence POSq′ (u) = POSq (ϕ(u)). If ϕ(u) is covered, then POSq (ϕ(u)) = POSq′ (x′′ ) for some x′′ ∈ head(q ′ ). Since u is a join variable and POSq′ (u) = POSq (ϕ(u)), the variable ϕ(u) satisfies the defining condition of VCJ . Thus ϕ(u) ∈ VCJ = Vt , and therefore ϕ(u) ∈ Vt ∩ N = V ⊆ M , a contradiction. If ϕ(u) is not covered, then ϕ(u) ∈ / VC . Moreover, ϕ(u) ∈ / join(q) because ϕ(u) ∈ N ⊆ / Vn because ϕ(u) ∈ / M . By the identity above, ϕ(u) ∈ head(q), so we njoin(q), and ϕ(u) ∈ write ϕ(u) = xi . The observation above then gives POSq′ (x′i ) ⊆ POSq (xi ) = {(R, c)}. Since x′i occurs in q ′ , equality follows. Hence xi is covered by the head variable x′i of q ′ , contradicting the assumption that ϕ(u) = xi is not covered. Thus ϕ(u) ∈ / N , so (h1) also holds for N . Therefore (h1) and (h2) hold for N , so θN ◦ ϕ witnesses that q ′ returns θN x̄ over θN Dq . As N ⊆ njoin(q) was arbitrary, Theorem 3.2 yields q ⊆⊥ q ′ . ◀

B.2

Proofs for Section 4.1

The following example, referenced in Section 4.1, illustrates the witness-set construction on a larger instance, where the maximally infinite-contradictable sets can be read directly from the diagram of the effective domains in Figure 2. ▶ Example B.1. Consider the queries q and q ′ over Q: q() ← R(x1 ), x1 ≥ 0, x1 ≤ 13 q ′ () ← R(y1 ), R(y2 ), R(y3 ), R(y4 ), R(y5 ), y1 ≤ 3, y2 ≥ 8, y3 ≤ 9, y3 ≥ 2, y4 ≤ 6, y5 ≤ 11, y5 ≥ 5

19

20

Shrinking the Family of Test Databases

y5 y4 y3 y1 0

2 {y2 , y3 , y5 }

3

{y2 , y5 } −y3

y2 5

{y1 , y2 , y5 }

+y1

6

{y1 , y2 } −y5

+y4

8 {y1 , y2 , y4 }

9

{y1 , y4 } −y2

+y3

11 {y1 , y3 , y4 }

13

{y1 , y3 , y4 , y5 } +y5

Figure 2 Contradictable sets.

We compute the witness set Wx1 . The effective domain of x1 is eDomq (x1 ) = [0, 13]. For each yi ∈ match(x1 ), the incompatibility set Ei = eDomq (x1 ) \ eDomq′ (yi ) is as follows: E1 = (3, 13],

E2 = [0, 8),

E3 = [0, 2) ∪ (9, 13],

E4 = (6, 13],

E5 = [0, 5) ∪ (11, 13]

Figure 2 illustrates the interaction between these domains. This illustration shows how the set of incompatible variables changes along the effective domain of x1 as we cross the endpoints of each eDomq′ (yi ). The labels −yi and +yi show when a variable’s interval starts or ends within the domain of x1 . Specifically, −yi marks the point where yi ’s interval begins, meaning it is no longer incompatible with x1. Conversely, +yi marks where yi ’s interval ends, making it incompatible from that point. From Figure 2, we can see that there are four maximally infinite-contradictable sets of variables. These sets, highlighted in red boxes, define the following witnesses in Wx1 : 1. S1 = {y2 , y3 , y5 } giving the witness E1 = [0, 2). 2. S2 = {y1 , y2 , y5 } giving the witness E2 = (3, 5). 3. S3 = {y1 , y2 , y4 } giving the witness E3 = (6, 8). 4. S4 = {y1 , y3 , y4 , y5 } giving the witness E4 = (11, 13]. Here all comparisons are non-strict, so no finite witness arises and finVals(x1 ) = ∅. As a result, Wx1 = {[0, 2), (3, 5), (6, 8), (11, 13]}. Note that each witness represents a region where no single yi from the corresponding maximal set can satisfy the query q. ◀ Proof of Proposition 4.3. Since the comparison operators are < and ≤, the effective domain eDom(x) and every eDomq′ (y) with y ∈ match(x) are intervals. For a point p ∈ eDom(x), let incomp(p) = {y ∈ match(x) | p ∈ / eDomq′ (y)} be the set of variables in match(x) whose effective domain does not contain p. Grouping the points of eDom(x) by the set incomp(p) splits eDom(x) into maximal segments, on which incomp(p) does not change. We call each such segment a cell. Each cell is an interval or a single point. We first bound the number of cells, and then show that every witness in Wx picks out a cell of its own. There are at most 2|match(x)| + 1 cells. As p moves through eDom(x), the set incomp(p) can change only when p crosses an endpoint of some eDomq′ (y). Each y ∈ match(x) has just two endpoints and can therefore change incomp at most twice, once when p enters eDomq′ (y) and once when it leaves. This gives at most 2|match(x)| changes in total. The cells are the maximal segments on which incomp(p) does not change, so their number is one more than the number of changes, that is, at most 2|match(x)| + 1.

H. Sternbach and S. Cohen

21

Singleton witnesses use point cells. Let {c} be a witness with c ∈ finVals(x), so c ∈ Ex (S) for some S with Ex (S) finite. Then S ⊆ incomp(c), so Ex (incomp(c)) ⊆ Ex (S) is finite and still contains c. The cell of c lies inside the finite set Ex (incomp(c)), which forces it to be the single point {c}. Therefore, distinct values c occupy distinct point cells. Infinite witnesses use interval cells. Let Ex (S) be a witness with S maximally infinitecontradictable. As Ex (S) is infinite, it contains a nondegenerate interval, and hence an interval cell C, on which incomp(p) is the same set T ⊇ S. Were T strictly larger than S, the inclusion C ⊆ Ex (T ) would make T infinite-contradictable and larger than S, contradicting maximality. So incomp equals S on C, and distinct sets S pick out distinct interval cells. Point cells and interval cells are never the same cell, so the singleton and infinite witnesses are matched to disjoint families of cells. Therefore |Wx | ≤ #cells ≤ 2|match(x)| + 1.

◀

Proof of Theorem 4.5. Clearly, if q is contained in q ′ , then q(D) ⊆ q ′ (D) for all D ∈ D(Θq ). We prove the other direction. Assume that q(D) ⊆ q ′ (D) for all D ∈ D(Θq ). Let D be any database instance. We assume that q(D) ̸= ∅, as otherwise containment is trivial. Therefore, there is a valuation ν : vars(q) → adom(D) and a tuple ā ∈ q(D) such that ν(x̄) = ā and D |= ν(body(q)). We construct a valuation ν ′ for q ′ that also produces ā over D. To find this valuation, we first identify a canonical database that maps the variables in q to constants in a way that is similar to (and only more restrictive than) the valuation of q over D. For each x ∈ vars(q), consider the set incomp(ν(x)) of variables in match(x) whose effective domains do not contain ν(x), and the subdomain Ex (incomp(ν(x))) induced by this set. Note that this subdomain is non-empty, since ν(x) ∈ eDom(x). We now choose, for each x ∈ vars(q), a witness Fx ∈ Wx , and use it to define a canonical assignment θ ∈ Θq . Recall ν(x) ∈ Ex (incomp(ν(x))). If Ex (incomp(ν(x))) is finite: since ν(x) ∈ Ex (incomp(ν(x))), the definition of finVals(x) gives ν(x) ∈ finVals(x), so {ν(x)} ∈ Wx . We set Fx := {ν(x)} and θ(x) := ν(x), which is a canonical value since c(x, {ν(x)}) = {ν(x)}. If Ex (incomp(ν(x))) is infinite: then incomp(ν(x)) is infinite-contradictable, so we may extend it to a maximally infinite-contradictable set Sx ⊇ incomp(ν(x)). We set Fx := Ex (Sx ), which is an infinite witness in Wx , and θ(x) := c(x, Fx ), the constant chosen for Fx . In both cases θ(x) ∈ Fx , and Fx ⊆ Ex (incomp(ν(x))) (in the infinite case because incomp(ν(x)) ⊆ Sx ). Hence θ(x) ∈ Ex (incomp(ν(x))). Now, consider the canonical database Dθ = θ(Dq ). Since θ ∈ Θq , the assignment θ satisfies all atoms of q over Dθ , so θ(x̄) ∈ q(Dθ ), and by assumption θ(x̄) ∈ q ′ (Dθ ). Therefore, there exists a valuation θ′ : vars(q ′ ) → adom(Dθ ) such that θ′ (x̄) = θ(x̄) and Dθ |= θ′ (body(q ′ )). Observe that we have a mapping θ′ from q ′ to Dθ , a mapping θ from q to Dθ and a mapping ν from q to D (see Figure 3). If θ was invertible, composing these mapping would immediately yield a mapping from q ′ to D as is required. Unfortunately, θ is not invertible, as multiple variables in q may be mapped to the same constant by θ. However, as we show next, we can overcome this problem as all such variables in q will also be mapped to the same value in D. We define the mapping ν ′ : vars(q ′ ) → adom(D) as follows. For each y ∈ vars(q ′ ), choose some x ∈ vars(q) with θ′ (y) = θ(x), and set ν ′ (y) := ν(x). Such an x exists because q is in normalized form, so every value occurring in Dθ is the θ-image of a variable of q. We check that ν ′ is well-defined, i.e., independent of the chosen x. Suppose θ(x1 ) = θ(x2 ). If this common value was chosen from an infinite witness, then by construction it is distinct

22

Shrinking the Family of Test Databases

from all other canonical values, so x1 = x2 . Otherwise it is a singleton value, and then θ(xi ) = ν(xi ) for i = 1, 2, so ν(x1 ) = θ(x1 ) = θ(x2 ) = ν(x2 ). In either case the value ν ′ (y) does not depend on the chosen preimage. Now, it remains to show that D |= ν ′ (body(q ′ )). First, consider a relational atom R(ȳ) in the body of q ′ . We must show that this atom is satisfied by ν ′ in D. Since θ′ satisfies q ′ in Dθ , we have R(θ′ (ȳ)) ∈ Dθ . By the construction of Dθ , there exists an atom R(z̄) in the body of q such that θ(z̄) = θ′ (ȳ). Moreover, since D |= ν(body(q)), we get R(ν(z̄)) ∈ D. By the definition of ν ′ and well-definedness, we have ν ′ (ȳ) = ν(z̄), and therefore R(ν ′ (ȳ)) ∈ D. Hence, the relational atoms of q ′ are satisfied in D under ν ′ . It remains to show that ν ′ satisfies all comparison atoms of q ′ . Let y ∈ vars(q ′ ), and let x be the variable used in defining ν ′ (y), so θ′ (y) = θ(x) and ν ′ (y) = ν(x). We show that ν ′ (y) ∈ eDomq′ (y). If Fx = {ν(x)}, then ν ′ (y) = ν(x) = θ(x) = θ′ (y). Since θ′ satisfies the comparison atoms of q ′ , we have θ′ (y) ∈ eDomq′ (y), and hence ν ′ (y) ∈ eDomq′ (y). Now suppose Fx is infinite, so θ(x) is the constant chosen for Fx . We first show that y ∈ match(x). Since θ′ (y) = θ(x) ∈ eDomq′ (y) (as θ′ is a valuation) and θ(x) ∈ Fx ⊆ eDom(x), we have eDom(x) ∩ eDomq′ (y) ̸= ∅. For the positional condition, let (R, j) ∈ POSq′ (y). Then y occurs in position j of some atom R(ȳ) of q ′ , so R(θ′ (ȳ)) ∈ Dθ , and the value in position j is θ′ (y) = θ(x). Since θ(x) is the canonical constant assigned to the infinite witness Fx , it is distinct from every other canonical value. Thus, this tuple can only have been produced from an atom of q in which x occurs in position j. Hence (R, j) ∈ POSq (x). Assume, towards a contradiction, that ν ′ (y) = ν(x) ∈ / eDomq′ (y). Since y ∈ match(x), the definition of incomp(ν(x)) gives y ∈ incomp(ν(x)), whence Ex (incomp(ν(x))) ⊆ eDom(x) \ eDomq′ (y). As Fx ⊆ Ex (incomp(ν(x))), it follows that Fx ∩ eDomq′ (y) = ∅. But θ(x) ∈ Fx and θ(x) = θ′ (y) ∈ eDomq′ (y), a contradiction. Hence ν ′ (y) ∈ eDomq′ (y). Therefore D |= ν ′ (body(q ′ )). Finally, θ′ (x̄) = θ(x̄) gives ν ′ (x̄) = ν(x̄) = ā, so ā ∈ q ′ (D). Since D and ā ∈ q(D) were arbitrary, q ⊆ q ′ , as required. ◀ vars(q ′ ) ν′ adom(D)

θ′ θ′ (y) = θ(x) =⇒ ν ′ (y) = ν(x)

ν

adom(Dθ ) θ vars(q)

Figure 3 The mappings in the proof of Theorem 4.5. Given a valuation θ′ of q ′ over the canonical database Dθ , we use θ and ν to build a valuation ν ′ of q ′ over the original database D.

B.3

Proofs for Section 4.2

The proof of Theorem 4.9 rests on two localization lemmas. We will use the following observation, immediate from the definition of witness values: a witness value pulls in its whole cohort. ▶ Observation B.2. If a is a witness value for y, then Va ⊆ cmatch−1 (y). Throughout, recall that legality means |cmatch−1 (y) ∩ S| ≤ 1 for every y ∈ vars(q ′ ). For y ∈ vars(q ′ ) set I(y) = {i ∈ [m] | cmatch−1 (y) ∩ Ci ̸= ∅} and, for a relational atom S A of q ′ , IA = y∈A I(y). Thus I(y) records the components from which y may take its value, and a match lying only in the separator contributes no index. When IA is a single

H. Sternbach and S. Cohen

component, the atom A is realized within it, and when IA has several, A straddles them and only the separator links its images. ▶ Lemma B.3 (Atom locality). For every relational atom A of q ′ , |IA | ≤ 1. In particular |I(y)| ≤ 1 for every y ∈ vars(q ′ ), and cmatch−1 (y) \ S is contained in a single component. Sk Proof. Fix a relational atom A = R(y1 , . . . , yk ) of q ′ , and recall that MA = t=1 cmatch−1 (yt ) is the set of all variables of q that are covering-matched by some variable occurring in A. By the co-match edges, every two distinct variables of MA are adjacent in RG, so MA is a clique. Forming RG − S deletes exactly the separator vertices, so the vertices removed from this clique are those in MA ∩ S. Any two surviving variables of MA \ S are still joined by their co-match edge, because deleting a vertex removes only the edges incident to it. Hence MA \ S remains a clique and lies in a single connected component of RG − S. S Since y∈A (cmatch−1 (y) \ S) = MA \ S sits in that one component, the variables of A reach at most one component, so |IA | ≤ 1. Applying this to any atom A that contains a fixed y ∈ vars(q ′ ) gives cmatch−1 (y) ⊆ MA , so cmatch−1 (y) \ S lies in a single component and |I(y)| ≤ 1. Note that I(y) = ∅ if every variable covering-matched by y lies in S. ◀ ▶ Lemma B.4 (Realizer localization). Let θ ∈ Θq and let ν be a valuation with θ(Dq ) |= ν(body(q ′ )). Let A = R(y1 , . . . , yk ) be a relational atom of q ′ and let R(z1 , . . . , zk ) be any relational atom of q with θ(zt ) = ν(yt ) for all t (one exists because R(ν(ȳ)) ∈ θ(Dq )). Then the value at := ν(yt ) is a witness value for yt and zt ∈ Vat ⊆ cmatch−1 (yt ) for every t. Consequently, if IA = {i} then z1 , . . . , zk ∈ S ∪ Ci , and if IA = ∅ then z1 , . . . , zk ∈ S. Proof. Fix t and write a = ν(yt ) = θ(zt ). As a = θ(zt ) is a canonical value of zt , we have zt ∈ Va . We check that a is a witness value for yt . First, a = ν(yt ) ∈ eDom(yt ), because ν satisfies the comparison atoms of yt . Second, let (R′ , p′ ) ∈ POSq′ (yt ) be arbitrary, say yt occurs at position p′ in an atom ′ A = R′ (. . . ) of q ′ . Since ν satisfies A′ , the tuple R′ (ν(. . . )) lies in θ(Dq ), so there is an atom R′ (w1 , . . . ) of q with θ(wp′ ) = ν(yt ) = a. Hence wp′ ∈ Va and (R′ , p′ ) ∈ POSq (wp′ ). S As (R′ , p′ ) was arbitrary, x∈Va POSq (x) ⊇ POSq′ (yt ). Thus a is a witness value for yt , and by Observation B.2 Va ⊆ cmatch−1 (yt ), in particular zt ∈ cmatch−1 (yt ). Finally, by Lemma B.3 we have cmatch−1 (yt ) \ S ⊆ Ci when IA = {i} (and cmatch−1 (yt ) ⊆ S when IA = ∅, since then cmatch−1 (yt ) meets no component). Hence zt ∈ S ∪ Ci (resp. zt ∈ S). The argument uses no injectivity: the realizer zt is localized directly through the witness value a, regardless of how many variables of q also carry a. ◀ Proof of Theorem 4.9. Let θ ∈ Θq be arbitrary. We construct a valuation witnessing θ(x̄) ∈ q ′ (θ(Dq )). Let C1 , . . . , Cm be the components of RG − S. Since Ψq is S-exhaustive, for each i ∈ [m] pick ψi ∈ Ψq with ψi |S∪Ci = θ|S∪Ci . By hypothesis each ψi admits a valuation µi : vars(q ′ ) → adom(ψi (Dq )) with ψi (Dq ) |= µi (body(q ′ )) and µi (x̄) = ψi (x̄). Lemma B.4 applies to each pair (ψi , µi ). The plan is to build µ from the µi , taking the value of each y ∈ vars(q ′ ) from the index i in I(y). Step 1: variables with I(y) = ∅ get the same value from every µi . Let y ∈ vars(q ′ ) with I(y) = ∅, and let A be a relational atom of q ′ containing y. By Lemma B.3, cmatch−1 (y) ⊆ S. The set cmatch−1 (y) is not empty, since Lemma B.4 applied to (ψ1 , µ1 ) and A places a variable of cmatch−1 (y) at the position of y. Since S is a legal separator, |cmatch−1 (y) ∩ S| ≤ 1. Hence cmatch−1 (y) = {s} for a single s ∈ S. Now fix any i. Lemma B.4 applied to (ψi , µi ) and A places a variable z ∈ cmatch−1 (y) = {s} at the position of y, so µi (y) = ψi (s) = θ(s), as ψi and θ agree on S. This value does not depend on i.

23

24

Shrinking the Family of Test Databases

Step 2: the assembled valuation. By Lemma B.3, |I(y)| ≤ 1 for every y ∈ vars(q ′ ). Define µ(y) := µi (y), where i is the unique index with I(y) = {i}, and where i is arbitrary if I(y) = ∅. By Step 1 the choice of i does not matter in the second case. In both cases, µ(y) = µi (y) for every i with I(y) ⊆ {i}. We use this property in the remaining steps. Step 3: relational atoms. Let A = R(y1 , . . . , yk ) be a relational atom of q ′ . By Lemma B.3, IA ⊆ {i} for some i. Every yt satisfies I(yt ) ⊆ IA ⊆ {i}, so µ(yt ) = µi (yt ) by Step 2. Hence R(µ(ȳ)) = R(µi (ȳ)) ∈ ψi (Dq ), so there is an atom R(z1 , . . . , zk ) of q with ψi (zt ) = µi (yt ) for all t. By Lemma B.4, every zt lies in S ∪ Ci , where ψi agrees with θ. Therefore µ(yt ) = ψi (zt ) = θ(zt ) for all t, and R(µ(ȳ)) = R(θ(z̄)) ∈ θ(Dq ). Step 4: comparison atoms. Since q ′ ∈ CQvc , every comparison atom of q ′ has the form y ⋖ c with c a constant. By Step 2, µ(y) = µi (y) for some i, and µi satisfies y ⋖ c. Hence µ(y) ⋖ c holds. This is the only place where q ′ ∈ CQvc is used: a comparison between two variables could involve two different indices i. Step 5: head. Let xj be a head variable, which occurs in both q and q ′ . Choose i with I(xj ) ⊆ {i}. By Step 2 and head preservation, µ(xj ) = µi (xj ) = ψi (xj ). It remains to show that the variable xj of q lies in S ∪ Ci , since then ψi (xj ) = θ(xj ). Let a = ψi (xj ). Then a ∈ c(xj ), so xj ∈ Va . Lemma B.4 applied to (ψi , µi ) and an atom of q ′ containing xj shows that a = µi (xj ) is a witness value for xj . By Observation B.2, Va ⊆ cmatch−1 (xj ), so xj ∈ cmatch−1 (xj ). By Lemma B.3 and I(xj ) ⊆ {i}, cmatch−1 (xj ) ⊆ S ∪ Ci . Hence xj ∈ S ∪ Ci and µ(xj ) = θ(xj ). By Steps 3 to 5, µ satisfies body(q ′ ) over θ(Dq ) and µ(x̄) = θ(x̄). Thus µ witnesses θ(x̄) ∈ q ′ (θ(Dq )), as required. ◀ Proof of Lemma 4.10. Recall that a canonical assignment chooses one canonical value for Q each variable. For a set of variables W ⊆ vars(q), write A(W ) = u∈W c(u) for the set of Q all assignments of canonical values to W , so |A(W )| = u∈W |c(u)| and Θq = A(vars(q)). Since S, C1 , . . . , Cm partition vars(q), an assignment θ ∈ Θq is the same as the tuple of its restrictions (θ|S , θ|C1 , . . . , θ|Cm ) ∈ A(S) × A(C1 ) × · · · × A(Cm ), and every such tuple arises from exactly one θ. Let ni = |A(Ci )| and N = maxi∈[m] ni , and fix i∗ with ni∗ = N . The claimed size is |A(S)| · N . We show that every S-exhaustive set has at least this size, and then construct one that has at most this size. Lower bound. Let Ψ ⊆ Θq be S-exhaustive. Applying the definition with i = i∗ , for every θ ∈ Θq some ψ ∈ Ψ has ψ|S∪Ci∗ = θ|S∪Ci∗ . As θ ranges over Θq , the restriction θ|S∪Ci∗ ranges over all of A(S ∪ Ci∗ ). Hence the map ψ 7→ ψ|S∪Ci∗ from Ψ to A(S ∪ Ci∗ ) is surjective, and |Ψ| ≥ |A(S ∪ Ci∗ )| = |A(S)| · ni∗ = |A(S)| · N . Construction. For each i ∈ [m], since ni ≤ N , we can list the elements of A(Ci ) as a sequence γi1 , . . . , γiN of length N in which every element of A(Ci ) appears at least once. For σ ∈ A(S) and t ∈ [N ], let ψσ,t ∈ Θq be the assignment with ψσ,t |S = σ and ψσ,t |Ci = γit for every i ∈ [m], and let Ψq = {ψσ,t | σ ∈ A(S), t ∈ [N ]}. There are |A(S)| · N pairs (σ, t), so |Ψq | ≤ |A(S)| · N . It remains to check that Ψq is S-exhaustive. Let θ ∈ Θq and i ∈ [m]. Let σ = θ|S , and choose t ∈ [N ] with γit = θ|Ci , which exists because every element of A(Ci ) appears in the sequence. Then ψσ,t agrees with θ on S and on Ci , that is, on S ∪ Ci . By the lower bound, |Ψq | ≥ |A(S)| · N as well, so |Ψq | = |A(S)| is the size
· N and this Q Q of the smallest S-exhaustive set. Since |A(S)| · N = |c(v)| · max i∈[m] v∈S u∈Ci |c(u)|, the lemma follows. ◀ Proof of Theorem 4.12. Membership in NP. Guess S ⊆ vars(q), check that it is legal, and

H. Sternbach and S. Cohen

compare the size given by Lemma 4.10 with t. This is polynomial, since the witness sets, and with them the counts |c(v)| and the covering-match relation, can be computed by a sweep over the endpoints of the effective domains. Reduction to a graph problem. When |c(v)| = 2 for every variable v, the size in Lemma 4.10 is 2|S| · 2maxi |Ci | = 2|S|+maxi |Ci | . So if every separator of RG is legal, asking for a legal separator with |Ψq | ≤ 2t is the same as asking for a set S with |S| + maxi |Ci | ≤ t. This is the following problem. Min-Separator: given an undirected graph G = (V, E) and an integer t, is there S ⊆ V with |S| + maxi |Ci (G − S)| ≤ t, where C1 , . . . , Cm are the connected components of G − S? We show that Min-Separator is NP-hard, and then that every graph is the relational graph of a query pair in which every variable has two canonical values and every separator is legal. Min-Separator is NP-hard. We reduce from Vertex Cover. Let (G0 = (V0 , E0 ), k) be an instance with n = |V0 |. We may assume k ≥ 1, since for k = 0 the answer is yes if and only if G0 has no edges. We may assume k < n, since otherwise V0 itself is a cover of size at most k. Adding isolated vertices to G0 changes neither its vertex covers nor their sizes, so we may also assume n ≥ 2k + 1. Let G be G0 with k new leaf vertices attached to each v ∈ V0 , each adjacent only to v, and let t = 2k + 1. We claim that G0 has a vertex cover of size at most k if and only if G has a set S with |S| + maxi |Ci (G − S)| ≤ t. (⇒) Let X be a vertex cover of G0 with |X| ≤ k, and let S = X. Since X covers every edge of G0 , no two original vertices outside S are adjacent. So every original vertex v ∈ /S forms a component together with its k leaves, of size k + 1, and every leaf of a vertex in S is a component by itself. As |X| ≤ k < n, some original vertex lies outside S, so maxi |Ci | = k + 1 and |S| + maxi |Ci | ≤ k + (k + 1) = t. (⇐) Let S satisfy |S|+maxi |Ci (G−S)| ≤ t. We may assume S ⊆ V0 : removing a leaf from S lowers |S| by one, and the leaf either joins a component, raising its size by one, or forms a new component of size one, so the maximum rises by at most one and the sum does not increase. We may also assume S ̸= V0 , since for S = V0 the graph G−S consists of the nk ≥ 1 isolated leaves and |S|+maxi |Ci | = n+1 ≥ 2k+2 > t. Now S is a vertex cover of G0 : if some edge (u, v) ∈ E0 had both endpoints outside S, then u, v and their 2k leaves would lie in one component of size at least 2k + 2 > t. Hence every original vertex outside S forms a component of size exactly k+1, so maxi |Ci | = k+1 and |S| ≤ t−(k+1) = k. Thus G0 has a vertex cover of size at most k. The construction of G is polynomial, so Min-Separator is NP-hard. Every graph is a relational graph. Let G = (V, E) be a graph. Let q have a variable xv for each v ∈ V and no comparison atoms, so eDom(xv ) = Q. For each edge (u, v) ∈ E, add to q the atom Ruv (xu , xv ) over a fresh relation symbol Ruv . For each v ∈ V , add to q the atom Uv (xv ) over a fresh unary symbol Uv , and add to q ′ two variables yv , yv′ with the atoms Uv (yv ), Uv (yv′ ) and the comparisons yv < 0 and yv′ ≥ 0. Each of yv , yv′ occurs only in the position (Uv , 1), which in q is occupied by xv alone, so match(xv ) = {yv , yv′ }. The sets {yv } and {yv′ } are infinite-contradictable by xv , with Exv ({yv }) = [0, ∞) and Exv ({yv′ }) = (−∞, 0), while Exv ({yv , yv′ }) = ∅. So these are the two maximally infinite-contradictable sets, no finite witness arises, and |c(xv )| = 2. Both canonical values of xv are constants chosen for infinite witnesses, so by the choice of canonical constants they differ from the constant 0 and from every canonical value of every other variable of q. We now show RG = G. The atoms Ruv produce exactly the atom edges of G. Let a be a witness value for yv . Its cohort Va must cover the only position (Uv , 1) of yv , which xv alone occupies, so xv ∈ Va and a ∈ c(xv ). By the previous paragraph no other variable of q carries a, so Va = {xv }. Hence cmatch−1 (yv ) = {xv }, and likewise cmatch−1 (yv′ ) = {xv }. Thus no variable of q ′ covering-matches two distinct variables of q, so every separator is legal. Each relational

25

26

Shrinking the Family of Test Databases

atom of q ′ contains a single variable, whose covering-matches form a singleton, so no atom of q ′ covering-matches two distinct variables and there are no co-match edges. Therefore RG = G. Combining the two reductions, deciding whether some legal separator achieves |Ψq | ≤ 2t is NP-hard, which completes the proof. ◀

B.4

Proofs for Section 4.3

The following example, referenced in Section 4.3, shows that for CQcmp queries the witness sets alone are insufficient, in either direction. In the first pair below the query q contains a variable–variable comparison. In the second pair, only q ′ does. ▶ Example B.5. q carries the comparison. Let q ∈ CQcmp and q ′ ∈ CQvc be the Boolean queries q() ←R(x1 ), S(x2 ), 10 < x1 ≤ 25, 10 ≤ x2 < 25, x1 > x2 q ′ () ←R(y1 ), R(y2 ), R(y3 ), S(y4 ), S(y5 ), 10 ≤ y1 ≤ 25, 10 ≤ y2 ≤ 15, 20 ≤ y3 ≤ 25, 10 ≤ y4 ≤ 25, 10 ≤ y5 ≤ 20 For x1 , the subsets induced by y1 , y2 , y3 are E1 = ∅, E2 = (15, 25] and E3 = (10, 20), so {y2 , y3 } is the only maximally infinite-contradictable set and no finite witness arises. Symmetrically, only {y5 } is maximally infinite-contradictable by x2 . Hence Wx1 = {(15, 20)} and Wx2 = {(20, 25)}, so canonical values taken from the witness sets cannot satisfy x1 > x2 . Yet this does not mean that q ⊆ q ′ , as D = {R(21), S(11)} gives q(D) = true and q ′ (D) = false.

y2

y5

y3 y1

10

15 {y3 }

{y2 , y3 } −y2

x1

20

25 {y2 }

y4 10

x2

20 {y5 }

∅

+y3

25

−y5

Figure 4 Witness set that does not yield feasible canonical values.

q ′ carries the comparison. Let now q̂ ∈ CQvc be q̂() ←R(x1 ), R(x3 ), R(x4 ), S(x2 ), S(x5 ), T (x1 ), T (x2 ), 10 < x1 ≤ 25, 10 ≤ x2 < 25, 10 ≤ x3 ≤ 15, 20 ≤ x4 ≤ 25, 10 ≤ x5 ≤ 20 and let q̂ ′ ∈ CQcmp be obtained from q ′ by adding the atoms T (y1 ), T (y4 ) and the comparison y1 < y4 . The variables x3 , x4 , x5 have no contradictable sets, so the witness set of each is its effective domain alone and each has a single canonical value, while x1 and x2 have the same witness sets as above, as illustrated in Figure 4. The witness sets thus determine a single canonical assignment θ, and q̂(Dθ ) ⊆ q̂ ′ (Dθ ). Still, q̂ ̸⊆ q̂ ′ : since y1 can be matched only to x1 and y4 can be matched only to x2 , one can choose values satisfying all atoms of q̂ whose images violate the comparison y1 < y4 . ◀ The proof of Theorem 4.16 rests on the componentwise-relaxation machinery, which we now define formally. For an assignment µ : vars(q) → Q and an isolated variable x ∈ vars(q), define forbiddenµ (x) = {y ∈ match(x) | µ(x) ∈ / eDomq′ (y)}. Intuitively, forbiddenµ (x) contains

H. Sternbach and S. Cohen

the variables of q ′ that can match x at the relational level, but cannot be assigned the value µ(x) because this value violates their effective domains. Let µ1 , µ2 : vars(q) → Q be two assignments. We say that µ1 is a componentwise relaxation of µ2 and write µ1 ≺ µ2 , if the following conditions hold. 1. The assignments agree on the ordering within each connected component: for every component C of CG and every pair z1 , z2 ∈ C, both µ1 (z1 ) < µ1 (z2 ) ⇐⇒ µ2 (z1 ) < µ2 (z2 ) and µ1 (z1 ) = µ1 (z2 ) ⇐⇒ µ2 (z1 ) = µ2 (z2 ). 2. The assignments agree on the intervals: for every nontrivial component C of CG, variable z ∈ C, and interval I ∈ Inter(C), we have µ1 (z) ∈ I ⇐⇒ µ2 (z) ∈ I. 3. For every isolated variable x ∈ vars(q), every variable of q ′ forbidden under µ1 is also forbidden under µ2 , that is, forbiddenµ1 (x) ⊆ forbiddenµ2 (x). The relation ≺ captures exactly the information about a valuation that the containment test must preserve: the internal order and equalities within each component, the interval of each component variable, and the forbidden sets of the isolated variables. The next lemma shows that this information can always be preserved by a canonical assignment. ▶ Lemma B.6. For every database instance D and every satisfying valuation µ of q over D, there exists a canonical assignment θ ∈ Θq such that µ ≺ θ. Proof of Lemma B.6. Let D be a database instance, and let µ be a satisfying valuation of q over D. We construct a canonical assignment θ ∈ Θq as follows. First, we handle isolated variables as in the proof of Theorem 4.5. Let x be an isolated variable, and recall that incomp(µ(x)) is the set of variables in match(x) whose effective domains do not contain µ(x), so that forbiddenµ (x) = incomp(µ(x)). Recall also that, for any
T set S ⊆ match(x), Ex (S) = y∈S eDomq (x) \ eDomq′ (y) . Since µ(x) ∈ eDomq (x) (as µ satisfies q) and µ(x) ∈ / eDomq′ (y) for every y ∈ incomp(µ(x)), we have µ(x) ∈ Ex (incomp(µ(x))). Hence incomp(µ(x)) is contradictable by x. If Ex (incomp(µ(x))) is finite, then µ(x) ∈ finVals(x), so {µ(x)} ∈ Wx . We set θ(x) = µ(x), which is a canonical value since c(x, {µ(x)}) = {µ(x)}, and then forbiddenθ (x) = forbiddenµ (x). If Ex (incomp(µ(x))) is infinite, then incomp(µ(x)) is infinite-contradictable, so we extend it to a maximally infinite-contradictable set Sx ⊇ incomp(µ(x)) and set θ(x) = c(x, Ex (Sx )), the constant chosen for the infinite witness Ex (Sx ). Since θ(x) ∈ Ex (Sx ) ⊆ eDomq (x) \ eDomq′ (y) for every y ∈ Sx , we have Sx ⊆ forbiddenθ (x), and therefore forbiddenµ (x) = incomp(µ(x)) ⊆ forbiddenθ (x). In either case, forbiddenµ (x) ⊆ forbiddenθ (x). For every nontrivial connected component C ∈ Comp(CG) and every interval I ∈ Inter(C), define XC,I = {x ∈ varsC,I | µ(x) ∈ I}.Since the intervals in Inter(C) are pairwise disjoint, for every variable x there is at most one interval I ∈ Inter(C) such that x ∈ XC,I . We define θ separately on each set XC,I . If I = {k} is a singleton interval, set θ(x) = k for every x ∈ XC,I . If I is an open interval, let B1 , . . . , Bt be the equivalence classes of XC,I under equality of µ-values, ordered so that i < j implies µ(x) < µ(y) for every x ∈ Bi and y ∈ Bj . Since t ≤ |XC,I | ≤ |varsC,I |, and repvalsC,I = {α1C,I , . . . , αℓC,I } where ℓ = |varsC,I |, we define θ(x) = αiC,I for every x ∈ Bi . Repeating this construction for every nontrivial connected component C and every interval I ∈ Inter(C) defines θ on all non-isolated variables of q. Together with the construction above for isolated variables, this defines θ on all variables of q. We check that θ(x) ∈ c(x) for every non-isolated x. Suppose θ(x) = αiC,I , so x ∈ Bi and i is the number of equality-classes of XC,I up to and including that of x. The classes B1 , . . . , Bi−1

27

28

Shrinking the Family of Test Databases

consist of variables of XC,I that are strictly smaller than x under µ. No variable y with q |= x ≤ y lies in them, since µ satisfies q and hence µ(x) ≤ µ(y). Thus the i − 1 classes below x are formed from variables in varsC,I \ ({x} ∪ {y | q |= x ≤ y}), so i − 1 ≤ |varsC,I | − 1 − |{y ∈ varsC,I \ {x} | q |= x ≤ y}|, that is, i ≤ rmaxI (x). Hence αiC,I ∈ repvalsC,I (x) ⊆ c(x). (For a singleton interval the claim is immediate, as repvalsC,I (x) = {k}.) By construction, θ(x) ∈ c(x) for every x ∈ vars(q). Moreover, every non-isolated variable is mapped to a value in the same interval of Inter(C) as under µ, and within each interval both equality and strict order are preserved. Hence θ satisfies all comparison atoms of q, and therefore θ ∈ Θq . It remains to prove that µ ≺ θ. First, let C be a nontrivial connected component of CG, and let z1 , z2 ∈ C. If µ(z1 ) and µ(z2 ) lie in the same interval of Inter(C), then by construction µ(z1 ) = µ(z2 ) ⇐⇒ θ(z1 ) = θ(z2 ) and µ(z1 ) < µ(z2 ) ⇐⇒ θ(z1 ) < θ(z2 ). If µ(z1 ) and µ(z2 ) lie in two distinct intervals of Inter(C), then, by the interval-membership property proved above, θ(z1 ) and θ(z2 ) lie in the same two intervals, respectively. Since Inter(C) is an ordered partition of Q, the relative order between the two values is the same under both µ and θ, and since the intervals are disjoint, equality is impossible under both assignments. Finally, let x be an isolated variable. By the construction for isolated variables, we have forbiddenµ (x) ⊆ forbiddenθ (x). Therefore, all three conditions in the definition of ≺ hold, and hence µ ≺ θ. ◀ Proof of Theorem 4.16. As before, the ‘only if’ direction is immediate, so it remains to prove the ‘if’ direction. Assume that q(D̂) ⊆ q ′ (D̂) for all canonical databases D̂ ∈ D(Θq ), and let D be an arbitrary database instance. As before, we assume that q(D) ̸= ∅, and fix a tuple ā ∈ q(D) together with a valuation ν : vars(q) → adom(D) such that ν(x̄) = ā and D |= ν(body(q)). By Lemma B.6, there exists a canonical assignment θ ∈ Θq such that ν ≺ θ. We choose such a θ as constructed in the proof of the lemma. Let Dθ = θ(Dq ). Since θ(x̄) ∈ q(Dθ ) and, by assumption, q(Dθ ) ⊆ q ′ (Dθ ), there exists a valuation θ′ : vars(q ′ ) → adom(Dθ ) such that Dθ |= θ′ (body(q ′ )) and θ′ (x̄) = θ(x̄). We define the mapping ν ′ : vars(q ′ ) → D as follows. For y ∈ vars(q ′ ), we set ν ′ (y) = ν(x) for some variable x such that θ′ (y) = θ(x). There may be several variables x that θ maps to the same value c = θ′ (y). We check that they all have the same value ν(x), so that ν ′ (y) is well defined. If c comes from a finite witness or is a singleton-interval value, then by construction θ(x) = ν(x) = c for every such x. If c = αiC,I is a representative of an open interval, then every variable x with θ(x) = c lies in the same equality class Bi of the construction in the proof of Lemma B.6, and the variables of Bi share a common ν-value, so ν(x) is the same for all of them. Finally, a constant chosen for an infinite witness is, by construction, distinct from all other canonical values, so it is taken by a unique variable. In every case all possible choices of x give the same value ν(x), so ν ′ (y) is well defined. It remains to show that D |= ν ′ (body(q ′ )). First consider a relational atom R(ȳ) of q ′ . Since Dθ |= θ′ (R(ȳ)), we have R(θ′ (ȳ)) ∈ Dθ . By the definition of Dθ , there exists a relational atom R(x̄) in the body of q such that θ(x̄) = θ′ (ȳ). Moreover, since D |= ν(body(q)), we get R(ν(x̄)) ∈ D. By the definition of ν ′ , we have ν ′ (ȳ) = ν(x̄), and therefore R(ν ′ (ȳ)) ∈ D. Hence all relational atoms of q ′ are satisfied in D under ν ′ . For the comparison atoms we use the following observation: for every y ∈ vars(q ′ ) we may take the variable x chosen for ν ′ (y) to be partially matched by y. Indeed, y occurs in some relational atom R(ȳ) of q ′ , and as above there is an atom R(x̄) of q with θ(x̄) = θ′ (ȳ). The variable x of x̄ at the position of y occupies a position of y and satisfies θ(x) = θ′ (y). Since θ′ satisfies the comparison atoms of q ′ and θ ∈ Θq , this common value

H. Sternbach and S. Cohen

lies in eDomq′ (y) ∩ eDomq (x), so y partially matches x. By the well-definedness shown above, ν ′ (y) = ν(x) for this x as well, so we assume from now on that y partially matches the chosen x. Consider first a variable y with an atom in compvc (q ′ ), and let x be the variable chosen for it, so that θ(x) = θ′ (y) ∈ eDomq′ (y) and ν ′ (y) = ν(x). If x belongs to a nontrivial connected component C, then, since y partially matches x and x ∈ C, the constants bounding eDomq′ (y) belong to K(C) and hence are among those inducing Inter(C). Let Ix ∈ Inter(C) be the unique interval such that ν(x) ∈ Ix . Since ν ≺ θ, we also have θ(x) ∈ Ix , and the interval Ix is either contained in eDomq′ (y) or disjoint from it. As θ(x) ∈ Ix ∩ eDomq′ (y), it follows that Ix ⊆ eDomq′ (y), and therefore ν ′ (y) = ν(x) ∈ eDomq′ (y). If x is isolated, then θ(x) was chosen in the proof of Lemma B.6 either as the constant of an infinite witness or as a finite-witness value. In the second case θ(x) = ν(x) by construction, so ν ′ (y) = θ′ (y) ∈ eDomq′ (y). In the first case θ(x) is taken by no other variable of q, so, exactly as in the proof of Theorem 4.5, every position of y is a position of x and y ∈ match(x). Then θ(x) ∈ eDomq′ (y) gives y ∈ / forbiddenθ (x). Since ν ≺ θ, we have forbiddenν (x) ⊆ forbiddenθ (x). Hence y ∈ / forbiddenν (x), and therefore ν ′ (y) = ν(x) ∈ eDomq′ (y). Now let y ⋖ y ′ ∈ compvv (q ′ ), and let x, x′ ∈ vars(q) be the variables chosen in the definition of ν ′ for y and y ′ , so that θ′ (y) = θ(x), θ′ (y ′ ) = θ(x′ ), ν ′ (y) = ν(x) and ν ′ (y ′ ) = ν(x′ ). Since y partially matches x, y ′ partially matches x′ , and y ⋖ y ′ ∈ compvv (q ′ ), we show that x and x′ lie in the same connected component of CG (if x = x′ there is nothing to show). If the induced inequality x ⋖ x′ is consistent with compvv (q), then it belongs to matchComp(q, q ′ ) and hence to relComp(q, q ′ ), giving an edge {x, x′ }. Otherwise it contradicts compvv (q), so compvv (q) itself constrains the order of x and x′ , and they are connected through edges of compvv (q). In either case x and x′ belong to the same nontrivial connected component C. Since θ′ satisfies q ′ , θ(x) ⋖ θ(x′ ) holds, and condition (1) of ν ≺ θ on the component C transfers it to ν(x) ⋖ ν(x′ ), that is, ν ′ (y) ⋖ ν ′ (y ′ ). We have shown that D |= ν ′ (body(q ′ )). Moreover, since θ′ (x̄) = θ(x̄), the definition of ′ ν gives ν ′ (x̄) = ν(x̄) = ā. Thus ā ∈ q ′ (D). Since both D and ā ∈ q(D) were arbitrary, q(D) ⊆ q ′ (D) for every database instance D. Therefore, q ⊆ q ′ . ◀ The proof of Theorem 4.16 yields the following stronger fact, used by the proofs of Section 4.4: when containment fails, it fails on a tuple produced by a canonical assignment itself. ▶ Corollary B.7. Let q(x̄), q ′ (x̄) be CQcmp queries. If q ̸⊆ q ′ , then there exists a canonical assignment θ ∈ Θq such that θ(x̄) ∈ q(Dθ ) and θ(x̄) ∈ / q ′ (Dθ ), where Dθ = θ(Dq ). Proof of Corollary B.7. Assume q ̸⊆ q ′ , and fix a database D and a tuple ā ∈ q(D) \ q ′ (D), together with a valuation ν such that ν(x̄) = ā and D |= ν(body(q)). Let θ ∈ Θq be the canonical assignment with ν ≺ θ constructed in the proof of Theorem 4.16, and suppose that θ(x̄) ∈ q ′ (Dθ ). Then the argument in that proof transports a witnessing valuation for q ′ over Dθ back to D and yields ā ∈ q ′ (D), contradicting the choice of ā. Hence θ(x̄) ∈ / q ′ (Dθ ), while θ(x̄) ∈ q(Dθ ) holds by the definition of Dθ . ◀

B.5

Proofs for Section 4.4

Throughout this subsection we fix a nontrivial component C of CG and write V = vars(C) ∪ ⋖ K(C). Assignments are extended to K(C) by θ(k) = k. An edge u → v is satisfied by an assignment θ if θ(u) ⋖ θ(v), and is violated otherwise. Thus a reverse edge is violated exactly when the induced comparison whose violation it encodes is satisfied. Every canonical assignment of q satisfies every edge of Eq .

29

30

Shrinking the Family of Test Databases

A produced query is obtained from q by adding zero or more comparison atoms whose sides lie in V , possibly after merging variables of C that the atoms entail equal. A merged vertex stands for its members. Every produced query p is read with the component C, the constants K(C), the intervals Inter(C), and the representative values of (q, q ′ ). When only t merged variables of p are active on an open interval that has ℓ ≥ t representatives, p uses the lowest t of them. The opposite graph OG p = (V, Ep ∪ Ematch(p) ) of p is defined as for q. This convention is sound. The proofs of Lemma B.6 and Theorem 4.16 use the component data only through three facts, and each remains true for p. (F1) No comparison atom of p joins variables of two different components of CG, since the added atoms have both sides in V . (F2) Every constant that bounds the effective domain of a variable of C lies in K(C), since no new constant is introduced. (F3) If a variable of q ′ partially matches a vertex of p, then it partially matches a member of that vertex in (q, q ′ ), since adding atoms and merging only shrink effective domains. The proof of Lemma B.6 needs only t ordered representatives on an interval with t active variables, and the proof of Theorem 4.16 places the two realizers of a variable–variable atom of q ′ in one component using only that they are partially matched in (q, q ′ ), which (F3) provides. Hence Theorem 4.16 and Corollary B.7 hold for every produced query, as do all subsequent results in this subsection that rely on them. To prove Theorem 4.18, a canonical assignment witnessing q ̸⊆ q ′ must be reordered so that it also satisfies the added comparison. The next lemma performs the reordering along any graph extending Eq and shows that the failure of q ′ survives it. ▶ Lemma B.8 (Reordering and transport). Let θ ∈ Θq , and let G = (V, E) be a labeled directed graph with Eq ⊆ E. Assume no directed cycle of G contains a strict edge and that θ is constant on every strongly connected component of G. Then some assignment ρ satisfies: 1. (Locality) ρ = θ outside vars(C) and ρ(k) = k for every k ∈ K(C), 2. (Order) ρ satisfies every edge of G, and satisfies it strictly whenever its endpoints lie in distinct strongly connected components of G, 3. (Validity) ρ satisfies the comparison atoms of q, and 4. (Inj) for all u, v ∈ vars(q), ρ(u) = ρ(v) =⇒ θ(u) = θ(v). If, in addition, every edge of Ematch(q) satisfied by θ belongs to E, then θ(x̄) ∈ / q ′ (θ(Dq )) =⇒ ′ ρ(x̄) ∈ / q (ρ(Dq )). (Tr) Proof. We contract the strongly connected components of G. The resulting condensation is a DAG. We choose a topological order o of its vertices. Since Eq contains the constant edges, the components containing constants appear in o in increasing numerical order. No component contains two distinct constants, since the strict constant edges between them would then lie on a directed cycle. We now construct ρ. Outside vars(C), set ρ = θ. For a component S containing a constant k, set ρ(x) = k for every x ∈ S. Since θ is constant on S and θ(k) = k, we also have θ(x) = k for every x ∈ S. In particular, ρ(k) = k for every k ∈ K(C). This proves (Locality). Now let S contain variables but no constant. Let k and k ′ be, respectively, the closest constant components before and after S in o, with an infinite endpoint when one does not exist. Then IS = (k, k ′ ) ∈ Inter(C). The endpoint edges of Eq imply IS ⊆ eDom(x) for every x ∈ S. For all variable components with the same interval IS , choose distinct rational values inside IS in the order given by o. Choose these values also to be distinct from the finitely many values taken by θ outside C. This is possible because every open interval of Q is infinite. We next verify (Order). The resulting values strictly increase between distinct components in o. Indeed, two variable components with no constant component between them in o have the

H. Sternbach and S. Cohen

same closest constants and hence the same interval, where we chose the values in the order o. If two components have different intervals, some constant component lies between them. Values before that constant are smaller than it, unless the component is the constant itself, and values after it are larger. Distinct constant components appear in their numerical order. Hence every edge of G is satisfied, with strict inequality between distinct components. This proves (Order). We now verify (Validity). By (Order), all comparison-atom edges of q are satisfied, and the endpoint edges ensure that every variable remains in its effective domain. Thus ρ satisfies the comparison atoms of q. This proves (Validity). It remains to verify (Inj). Two variables of C receive the same value only when they lie in the same strongly connected component, where θ is constant. A value shared by a variable of C and a variable outside C can only be a constant k, in which case both variables also receive k under θ. Thus ρ(u) = ρ(v) =⇒ θ(u) = θ(v), which proves (Inj). It remains to prove (Tr). Suppose toward a contradiction that some valuation h satisfies q ′ over ρ(Dq ) and h(x̄′ ) = ρ(x̄). For every y ∈ vars(q ′ ), choose a relational atom of q ′ containing y. Since its image under h belongs to ρ(Dq ), it is the ρ-image of a relational atom of q. Let zy be the variable of that atom at the position of y. Then h(y) = ρ(zy ), and y partially matches zy , so the common value belongs to both relevant effective domains. Define h0 (y) = θ(zy ). If another variable zy′ is chosen, then ρ(zy ) = ρ(zy′ ), so (Inj) gives θ(zy ) = θ(zy′ ). Hence h0 is well defined. The same argument applies to relational atoms, position by position. Indeed, for a relational atom R(ȳ) of q ′ , the tuple h(ȳ) is the ρ-image of some atom R(z̄) of q. At each position, the globally chosen realizer of the corresponding variable of q ′ has the same ρ-value as the variable of z̄ at that position, hence the same θ-value by (Inj). Therefore h0 (ȳ) = θ(z̄) and R(h0 (ȳ)) ∈ θ(Dq ). Similarly, from h(x′i ) = ρ(xi ) and (Inj) we obtain h0 (x′i ) = θ(xi ) for every head position, so h0 (x̄′ ) = θ(x̄). Since θ(x̄) ∈ / q ′ (θ(Dq )), some comparison atom of q ′ must fail under h0 . Write this atom as u1 ⋖ u2 , and replace each variable uj by its chosen variable wj = zuj , while a constant stands for itself. Thus the induced comparison w1 ⋖ w2 fails under θ. Since h(uj ) = ρ(wj ) for each j (with constants fixed by ρ(k) = k), it suffices to show that the induced comparison fails under ρ. Then the original comparison atom also fails under h. If both sides are constants, the comparison has the same fixed truth value under every assignment, so we may assume that at least one of w1 , w2 is a variable. If some variable among w1 , w2 lies outside C, the induced comparison has the same truth value under θ and ρ. Constants are fixed, and for a variable–variable comparison the two corresponding variables lie in the same component of CG, as shown in the proof of Theorem 4.16. Hence if one lies outside C, so does the other. We may therefore assume that every variable among w1 , w2 lies in C. Any constant among them then belongs to K(C). If the comparison atoms of q, together with the order of the constants, imply w1 ⋖ w2 , then it cannot fail under θ. If they imply the negation of w1 ⋖ w2 , then w1 ⋖ w2 also fails under ρ, since (Validity) says that ρ satisfies the comparison atoms of q. Otherwise the induced comparison is undecided by q. By the definition of the opposite graph, the reverse edge encoding the negation of w1 ⋖ w2 lies in Ematch(q) . Since the induced comparison fails under θ, that reverse edge is satisfied by θ, and hence belongs to E by hypothesis. By (Order), it is therefore satisfied by ρ, so the induced comparison fails under ρ as well. Thus some comparison atom of q ′ fails under h, contradicting the assumption that h satisfies q ′ , which proves (Tr). ◀ Proof of Theorem 4.18. Since q ∗ is obtained from q by adding x1 < x2 , we have q ∗ ⊆ q. Thus q ⊆ q ′ implies q ∗ ⊆ q ′ .

31

32

Shrinking the Family of Test Databases

For the converse, we prove the contrapositive. Suppose q ̸⊆ q ′ . By Corollary B.7 there is a canonical assignment θ ∈ Θq such that θ(x̄) ∈ q(D) \ q ′ (D) for D = θ(Dq ). < Let F = {e ∈ Ematch(q) : θ satisfies e} and let G = (V, Eq ∪ F ∪ {x1 → x2 }). Every edge of Eq ∪ F is satisfied by θ. Hence, no directed cycle in this subgraph contains a strict edge, and θ is constant on each of its strongly connected components. Since x1 < x2 is addable, OG contains no path from x2 to x1 . In particular none exists in Eq ∪ F , so the new strict edge creates no directed cycle and the strongly connected components are unchanged. Apply Lemma B.8. By (Order), it gives an assignment ρ that satisfies G, and hence ρ(x1 ) < ρ(x2 ). By (Validity), ρ satisfies all comparison atoms of q, and by (Tr), it preserves the failure of q ′ . Therefore, ρ(x̄) ∈ q ∗ (ρ(Dq )) \ q ′ (ρ(Dq )), so q ∗ ̸⊆ q ′ . This proves the equivalence. The proof used only the absence of a directed path from x2 to x1 and kept constants fixed. Therefore, the same argument applies when one endpoint is a constant of K(C). ◀ In order to prove Theorem 4.19 we use three lemmas. Lemma B.9 characterizes the relations entailed by a produced query in terms of paths in its opposite graph. Lemma B.10 shows that once every cycle reverse edge is decided and the variables that are entailed to be equal are merged, the only directed cycles left in the opposite graph pin a variable to a constant, so no reverse edge lies on a cycle any more and every remaining pair can be ordered by an addable comparison. Lemma B.11 then uses these two lemmas to add such comparisons to a trichotomy query until only one local assignment remains. ▶ Lemma B.9 (Path characterization). Let r be a produced query with satisfiable comparison atoms, and let s, t be vertices of its opposite graph OG r = (V, Er ∪ Ematch(r) ). The comparison atoms of r entail s ≤ t if and only if Er contains a directed path from s to t, and entail s < t if and only if at least one such path contains a strict edge. Proof. First let Er contain a directed path from s to t. Every edge of Er records a relation that follows from the comparison atoms of r or from the numerical order of the constants. An atom edge is given by an atom of r, an endpoint edge records the tightest bound that the atoms of r place on its variable, and a constant edge is a true inequality between two constants. Composing these relations along a path from s to t gives s ≤ t, and gives s < t when at least one edge on the path is strict. For the other direction, suppose that Er has no path from s to t, or that no path of Er from s to t contains a strict edge. We build a satisfying valuation of r with t < s in the first case and with t ≤ s in the second. Add to Er the edge t → s, labeled < in the first case and ≤ in the second. A directed cycle through the new edge closes a path of Er from s to t. Thus, in the first case there is no such cycle, and in the second case every such cycle consists only of non-strict edges. A directed cycle of Er that contains a strict edge would give u < u for any vertex u on it, by the direction just proved. This is impossible, since the comparison atoms of r are satisfiable. Hence the extended graph has no directed cycle containing a strict edge. As in the proof of Lemma B.8, contract the strongly connected components of the extended graph and fix a topological order of the resulting DAG. Since the constant edges are strict and belong to Er , no component contains two distinct constants, and the components containing constants occur in numerical order. Assign to each such component its constant, and to each remaining component a value in the open interval between the nearest constant components before and after it, choosing these values increasing along the order. The resulting assignment ρ fixes every constant and satisfies every edge of the extended graph, strictly between distinct components. In particular ρ satisfies every atom edge of Er , and hence every comparison atom of r whose variables lie in C. No comparison atom of r joins a variable of C to a

H. Sternbach and S. Cohen

variable outside C, because such an atom of q is an edge of CG and every added atom has both sides in V . Extending ρ outside C by any satisfying valuation of r, which exists by satisfiability, therefore yields a satisfying valuation of r. It satisfies the added edge, so it has t < s in the first case and t ≤ s in the second, as required. ◀ ▶ Lemma B.10 (Pinned pairs). Let p be obtained from q by adding for every cycle reverse edge ⋖ e = (u → v) ∈ Ecycle , comparison atoms between u and v that decide the induced comparison encoded by e, assume that the comparison atoms of p are satisfiable, and let pe be obtained from p by merging every maximal class of variables of C that its atoms entail to be equal. Call a variable x pinned to a constant k if pe entails x ≤ k and k ≤ x. Then: 1. if the comparison atoms of pe entail s ≤ t for vertices s and t, then OG contains a directed path from every member of s to every member of t, and 2. every strongly connected component of OG e is a singleton or a pinned variable–constant p pair. Proof. Call a directed path in OG from a member of a to a member of b an expansion of an edge a → b of Ep or OG e , where a merged vertex stands for its members. We claim that p every such edge has an expansion. For edges inherited from q, this is immediate: every atom, endpoint, or constant edge is already an edge of OG between the corresponding members. Now consider an edge introduced by an added comparison between u and v, where e = (u → v) ∈ Ecycle . If the added edge has the direction of e, then e itself is an expansion. If it has the opposite direction, the rest of a directed cycle of OG containing e gives the required path. If an added variable–constant comparison tightens an endpoint edge, the tightened edge is simply the edge of that added atom. It remains to consider reverse edges of OG e . Such an edge has a member-level counterpart p in Ematch(q) \ Ecycle . Indeed, partial matching can only shrink when passing to pe, so the corresponding induced comparison already exists for (q, q ′ ). Since this comparison is not decided by pe, it is not decided by q, and its reverse edge therefore belongs to Ematch(q) . It cannot belong to Ecycle , because p decides the comparison encoded by every edge in Ecycle . Expansions of consecutive edges of Ep can be concatenated directly, since p has no merged vertices. For OG e , two consecutive expansions may meet at different members of the same p merged vertex. Let x and y be such members. Since they were merged, p entails both x ≤ y and y ≤ x. By Lemma B.9, Ep therefore contains paths from x to y and from y to x. Expanding these paths gives directed paths in OG in both directions. Thus we can connect any two expansions that meet at the same merged vertex. It follows that the expansions of all edges on a path in OG e from s to t can be concatenated p into a directed path in OG, and by the same connections it can start at any member of s and end at any member of t. Claim (1) now follows from Lemma B.9 applied to pe. No reverse edge of OG e can lie on a directed cycle. Suppose that a reverse edge a → b p did lie on such a cycle. Then the rest of the cycle gives a directed path from b back to a. By the previous argument, this path expands to a directed path in OG from a member of b to a member of a. The reverse edge itself has a member-level counterpart in Ematch(q) \ Ecycle , so together they form a directed cycle in OG containing that counterpart. This is impossible, since any such edge lying on a directed cycle would belong to Ecycle . For claim (2), suppose that a strongly connected component of OG e contains two distinct p vertices s and t. There are directed paths from s to t and from t to s. Every edge on these paths lies on a directed cycle, so by the previous paragraph none of them is a reverse edge. Thus all of them are atom, endpoint, or constant edges, and therefore record relations entailed by pe or by the order of the constants.

33

34

Shrinking the Family of Test Databases

Neither path can contain a strict edge. Otherwise, one path would imply s < t while the other implies t ≤ s, or vice versa, contradicting satisfiability. Hence pe entails both s ≤ t and t ≤ s, so s and t are entailed equal. By construction of pe, two distinct merged variables cannot be entailed equal, and neither can two distinct constants. Therefore a non-singleton strongly connected component contains exactly one variable x and one constant k. Since they are entailed equal, pe entails both x ≤ k and k ≤ x, so x is pinned to k. ◀ ▶ Lemma B.11 (Completion after the cycle decisions). Let p, pe be as in Lemma B.10. One can, in polynomial time, add O(|V |2 ) comparison atoms on V to pe and obtain pb with: 1. p ⊆ q ′ if and only if pb ⊆ q ′ , 2. the canonical assignments of pb induce a single local assignment on C, and 3. this local assignment satisfies every edge of Ematch(q) \ Ecycle . Proof. Merging identifies only variables that p entails to be equal, so p ⊆ q ′ if and only if pe ⊆ q ′ . Throughout the construction, the current query is produced and satisfies (F1)–(F3). Hence Theorem 4.18 applies at every stage, and by Lemma B.9, every entailed relation is witnessed by a path. ⋖ Protection. Let e = (u → v) ∈ Ematch(q) \ Ecycle . If the current atoms already imply u ⋖ v, no modification is needed. They cannot imply its negation, since the corresponding reverse path would expand, as in Lemma B.10, to a path from v to u in OG, placing e on a directed cycle. Thus, whenever u and v are not yet strictly ordered in the direction of e, the comparison u < v is a candidate. It is addable for the same reason: a reverse path in the current opposite graph would expand to one in OG. We therefore add such comparisons for all edges in Ematch(q) \ Ecycle . Since added edges are parallel to the corresponding protected edges and reverse edges can only disappear, the argument remains valid throughout. Afterwards, every valuation of the current query satisfies every edge of Ematch(q) \ Ecycle . Completion. We maintain the invariant that every strongly connected component of the current opposite graph is either a singleton or a pinned variable–constant pair. This holds initially by Lemma B.10(2) and is preserved by protection, since addable edges create no directed cycle. We repeatedly apply the following two operations. First (materialization), if an entailed variable–constant bound is not yet an atom, we add it. By Lemma B.9, the new edge is parallel to an existing path, so any cycle created by it stays within an existing pinned component. Second (saturation), if two vertices are neither strictly ordered nor entailed to be equal, at least one strict orientation between them is addable. Otherwise, they would lie in the same strongly connected component and hence be entailed to be equal. We add such an orientation and repeat. These operations preserve the invariant and satisfiability. They also introduce no new equality. Any new equality using an added strict edge would create a strict directed cycle. Each operation adds a new atom, so after O(|V |2 ) additions the process terminates with a query pb. By Theorem 4.18, containment equivalence with q ′ is preserved at every strict addition, while materialization adds only entailed atoms. Hence p ⊆ q ′ ⇐⇒ pb ⊆ q ′ , which proves (1). All required tests are reachability tests in graphs of polynomial size, so pb is computable in polynomial time. One local assignment. In pb, every two vertices are either strictly ordered or entailed to be equal, and every entailed variable–constant bound is an atom. Thus every pinned variable is fixed to its constant, while every unpinned variable lies in a unique interval I ∈ Inter(C). The merged variables active on I form a strict total order x1 < · · · < xt .

H. Sternbach and S. Cohen

For xj , exactly xj+1 , . . . , xt are forced above it, so its rank bound is j. Hence its canonical set is {α1C,I , . . . , αjC,I }, and strict increase forces xj 7→ αjC,I by induction on j. It remains only to check that these values are canonical for q. Let ℓ = |varsC,I |, and let x belong to the class of xj . No lower class contains a variable y with q |= x ≤ y, since pb is satisfiable and extends q, and every lower class remains active on I for q. Choosing one member from each lower class gives j − 1 ≤ ℓ − 1 − |{y ∈ varsC,I \ {x} : q |= x ≤ y}|, so j ≤ rmaxI (x) and αjC,I ∈ repvalsC,I (x). Pinned variables similarly take the canonical value of their singleton interval. Hence pb induces a single local assignment on C, proving (2). Finally, (3) follows from the protection step: every valuation of pb satisfies every edge of Ematch(q) \ Ecycle . ◀ Proof of Theorem 4.19. Every trichotomy query qσ is obtained from q by adding comparison atoms, so qσ ⊆ q. Hence q ⊆ q ′ implies qσ ⊆ q ′ for every σ. Conversely, suppose q ̸⊆ q ′ . Choose a database D, a tuple ā ∈ q(D) \ q ′ (D), and a satisfying valuation ν of q with ν(x̄) = ā, extended to constants by ν(k) = k. For every e = (u → v) ∈ Ecycle , exactly one of ν(u) < ν(v), ν(u) = ν(v), or ν(v) < ν(u) holds. Let σ record these relations. Then ν satisfies every atom added to qσ , and therefore ā ∈ qσ (D)\q ′ (D). Thus qσ ̸⊆ q ′ , proving q ⊆ q ′ if and only if qσ ⊆ q ′ for every trichotomy query qσ . For the local-assignment claim, fix σ. If qσ is unsatisfiable, its canonical test is vacuous. Otherwise qσ decides the induced comparison encoded by every edge of Ecycle , so Lemma B.11 applies. It yields a completed query qbσ with qσ ⊆ q ′ ⇐⇒ qbσ ⊆ q ′ , whose canonical assignments induce one local assignment on C. Thus each trichotomy case is tested over at most one local assignment, and the component contributes at most 3|Ecycle | local assignments. ◀ Proof of Theorem 4.21. Assume OG has no non-strict cycle. Every feedback query qi adds comparisons to q, so qi ⊆ q. Hence q ⊆ q ′ implies qi ⊆ q ′ for every minimal MFES Ei . For the converse, suppose q ̸⊆ q ′ . By Corollary B.7 there is a canonical assignment θ ∈ Θq such that θ(x̄) ∈ q(θ(Dq )) \ q ′ (θ(Dq )). Let U = {e ∈ Ecycle : θ violates e}. We claim that U is an MFES. Otherwise (V, Eq ∪ (Ematch(q) \ U )) contains a directed cycle γ. Every reverse edge on γ lies on a directed cycle of the original OG, and hence belongs to Ecycle \ U . It is therefore satisfied by θ. The edges of Eq are satisfied as well. Thus θ is nondecreasing around γ, which forces all vertices of γ to receive the same value. However, by the assumption of the theorem, γ contains a strict edge, a contradiction. Choose a minimal MFES E ⊆ U , and set H = (V, Eq ∪ (Ematch(q) \ E)). Then H is a DAG. Every reverse edge satisfied by θ belongs to H. Indeed, a satisfied cycle reverse edge is not in U and hence not in E, while a reverse edge outside Ecycle is never removed. Apply Lemma B.8 to H. Since H is acyclic, the resulting assignment ρ is strictly increasing along every edge of H by (Order), and ρ(x̄) ∈ / q ′ (ρ(Dq )) by (Tr). Let qE be the feedback query associated with E. Its original comparison atoms hold under ⋖ ρ. If e = (u → v) ∈ Ecycle \ E, then e ∈ H, so ρ satisfies the comparison u ⋖ v asserted by qE . ⋖ If e = (u → v) ∈ E, the minimality of E implies that adding e back to H creates a directed cycle. Hence H contains a directed path from v to u. Since ρ is strict along H, ρ(v) < ρ(u), and therefore ρ satisfies the negation v ⋖′ u added by qE . Thus ρ(x̄) ∈ qE (ρ(Dq )). Together with ρ(x̄) ∈ / q ′ (ρ(Dq )), this gives qE ̸⊆ q ′ . This proves the characterization. One local assignment. If the comparison atoms of q are unsatisfiable, which can be checked in polynomial time, then q and every qE are contained in q ′ and have no canonical assignment, so the claims hold trivially. Assume therefore that they are satisfiable. Then every feedback query qE is satisfiable. Fix any θ ∈ Θq , which exists by Lemma B.6. For

35

36

Shrinking the Family of Test Databases

a minimal MFES E, the graph H above is a DAG, so θ is trivially constant on each of its strongly connected components. Lemma B.8 (Order) therefore realizes every edge of H strictly, and the reverse path supplied by minimality satisfies the negation added for every edge of E. The query qE decides the induced comparison encoded by every edge of Ecycle , so Lemma B.11 applies and yields one local canonical assignment on C. Polynomial-delay generation. We may assume that Eq is acyclic, since otherwise every directed cycle of Eq contains a strict edge by the assumption of the theorem, and no MFES exists. Define a digraph T whose vertices are the edges of Ecycle . Put an edge e → f whenever the head of e reaches the tail of f by a path consisting only of Eq -edges, where the path may be empty when the two vertices coincide. For E ⊆ Ecycle , write OG E = (V, Eq ∪ (Ematch(q) \ E)). We show that E is an MFES of OG if and only if E is a feedback vertex set of T . If OG E has a directed cycle, every reverse edge on that cycle belongs to Ecycle \ E, and because Eq is acyclic the cycle contains at least one such edge. These reverse edges are pairwise distinct, and reading them in cyclic order, the Eq -paths between consecutive ones witness the edges of a directed cycle of T − E, a self-loop when there is only one. Conversely, let e1 → e2 → · · · → em → e1 be a directed cycle in T − E. For each i, follow the reverse edge ei and then the Eq -path witnessing the edge from ei to ei+1 (indices modulo m). Following these pieces in order leads from the head of e1 back to the tail of e1 , so OG E contains a directed path between them. Together with e1 it forms a directed cycle. This proves the equivalence. The correspondence preserves inclusion, so the minimal MFESs are exactly the minimal feedback vertex sets of T . The graph T is computable in polynomial time by reachability in Eq . A vertex of T carrying a self-loop belongs to every feedback vertex set. Remove all such vertices and enumerate the minimal feedback vertex sets of the remaining loop-free digraph with polynomial delay using the algorithm of Schwikowski and Speckenmeyer [26]. Adding the forced loop vertices back gives exactly the minimal MFESs, once each. For each output E, the feedback query qE can be constructed in polynomial time. By the satisfiability argument above, Lemma B.11 computes its unique local assignment in polynomial time. Indeed, each materialization or saturation step requires only a reachability computation in a graph of polynomial size, and at most O(|V |2 ) comparison atoms are added. Hence the feedback queries, together with their local assignments, are generated with polynomial delay. ◀

B.6

Proofs for Section 5

A value is private under a combined assignment θ if exactly one variable of q is assigned that value. ▶ Observation B.12. Let θ be a combined assignment, let h be a satisfying valuation of q ′ over θ(Dq ), and let y ∈ vars(q ′ ) satisfy h(y) = θ(z), where θ(z) is private. Then POSq′ (y) ⊆ POSq (z). Proof. Let (R, j) ∈ POSq′ (y). Choose an R-atom of q ′ in which y occurs at position j. Since h satisfies q ′ over θ(Dq ), the image of this atom under h belongs to θ(Dq ), and hence is the θ-image of some R-atom of q. The variable occurring at position j in that atom is mapped by θ to h(y) = θ(z). Since θ(z) is private, that variable must be z. Thus (R, j) ∈ POSq (z), which proves the claim. ◀ Proof of Theorem 5.1. Every D ∈ Dcomb (q, q ′ ) is a database, so the only-if direction is

H. Sternbach and S. Cohen

immediate. For the converse, assume that q(D) ⊆ q ′ (D) for every D ∈ Dcomb (q, q ′ ). Let D0 be a database, let ν satisfy q over D0 , and set ā = ν(x̄). We show that ā ∈ q ′ (D0 ). Head positions. Let xi be a head variable in no comparison atom. We claim that POSq′ (x′i ) ⊆ POSq (xi ). We choose a combined assignment θ1 that assigns a private value to xi . If xi is isolated, assign it the fresh constant from an infinite witness in Wxi , which exists since eDom(xi ) = Q. If xi lies in a nontrivial component C, then by normalization the comparison atoms of q admit a satisfying assignment that is injective on C and places xi in an open interval. The construction of Lemma B.6 turns it into a canonical assignment that is still injective on C, and we null Vn . Since xi is a head variable, xi ∈ / Vn , so its value is a private open-interval representative of C. Since θ1 (x̄) ∈ q(θ1 (Dq )), the assumption gives a satisfying valuation h1 of q ′ over θ1 (Dq ) with h1 (x′i ) = θ1 (xi ), and Observation B.12 gives the claim. The assignment θ. Let θ(x) = ⊥ for x ∈ Vn and for x ∈ Vt with ν(x) = ⊥. Every other x receives a canonical value as follows. (a) If ν(x) ̸= ⊥, take the value that mimics ν(x) in the proof of Theorem 4.5 when x is isolated. If x lies in a nontrivial component, use the representative produced by Lemma B.6 from the non-null part of ν. (b) If ν(x) = ⊥, then x ∈ Vf and x is uncompared. If x is isolated, choose the fresh constant of an infinite witness in Wx . If x lies in a nontrivial component C, then x is active on every interval and every representative is canonical for x. On each open interval I, rule (a) uses one representative for each ν-equality class whose value lies in I. Hence enough representatives remain to assign the variables of rule (b) in C distinct unused representatives. Compared variables lie in nonnull(q), so they are non-null under ν and fall under rule (a). Hence ν ≺ θ on the variables that both assignments leave non-null, so θ satisfies the variable– variable comparison atoms of q, and θ(x) ∈ eDom(x) gives the variable–constant ones. Thus θ is a combined assignment. Moreover, a value chosen by rule (b) is taken by no other variable, so it is private. The valuation ν ′ . Since θ(x̄) ∈ q(θ(Dq )), the assumption gives a satisfying valuation h of q ′ over θ(Dq ) with h(x̄′ ) = θ(x̄). For each relational atom A = R(ȳ) of q ′ , fix an atom R(z̄A ) of q with θ(z̄A ) = h(ȳ). We define ν ′ by two rules: (1) If h(y) ̸= ⊥, set ν ′ (y) = ν(z) for any z with θ(z) = h(y). (2) If h(y) = ⊥, then y ∈ / nonnull(q ′ ) occurs once, in some atom ′ A, and we set ν (y) = ν(z) for the variable z of z̄A at the position of y. Rule (1) is well defined. If θ(z1 ) = θ(z2 ) ̸= ⊥, then the value is private and z1 = z2 , or it is an open-interval representative of rule (a) and z1 , z2 share their ν-value, or it is a finite-witness or singleton-interval value and θ(zj ) = ν(zj ) for both j. Hence ν(z1 ) = ν(z2 ) in all cases. Relational atoms. For A = R(ȳ), rules (1) and (2) give ν ′ (ȳ) = ν(z̄A ), and R(ν(z̄A )) ∈ D0 because ν satisfies q. Non-null variables of q ′ . Let w ∈ nonnull(q ′ ), so h(w) ̸= ⊥ and ν ′ (w) = ν(z) for some z with θ(z) = h(w). Suppose that ν(z) = ⊥. Then z falls under rule (b), so θ(z) is private and Observation B.12 gives POSq′ (w) ⊆ POSq (z). As z is uncompared and non-join, z ∈ Vf \ nonnull(q) = VCN ∪ (head(q) \ VCJ ) and POSq (z) is a singleton, so POSq′ (w) = POSq (z). Now z is covered. This is immediate for z ∈ VCN , and for z = xi ∈ head(q) it follows from the head-position claim, which gives POSq′ (x′i ) = POSq (z). Hence w puts z into VCJ , contradicting z ∈ / VCJ . So ν ′ (w) ̸= ⊥. Comparison atoms. For a compared variable y of q ′ , pick an atom A containing y and let zy be the variable of z̄A at the position of y. Then θ(zy ) = h(y) lies in both effective

37

38

Shrinking the Family of Test Databases

domains, so y partially matches zy , and ν ′ (y) = ν(zy ) by rule (1). By the previous paragraph ν(zy ) ̸= ⊥, so zy falls under rule (a). Let y ⋖ k be an atom of q ′ . If zy is isolated, either θ(zy ) = ν(zy ), so ν ′ (y) = h(y) ∈ eDomq′ (y), or θ(zy ) is the private constant of an infinite witness. Then Observation B.12 gives y ∈ match(zy ). Since θ(zy ) ∈ eDomq′ (y), we have y ∈ / forbiddenθ (zy ) ⊇ forbiddenν (zy ), and hence ν(zy ) ∈ eDomq′ (y). If zy lies in a nontrivial component C, then the bounds of eDomq′ (y) lie in K(C), while ν(zy ) and θ(zy ) lie in the same interval of Inter(C). This interval is either contained in or disjoint from eDomq′ (y). Since θ(zy ) ∈ eDomq′ (y), also ν(zy ) ∈ eDomq′ (y). Let y ⋖ y ′ be an atom of q ′ . As in the proof of Theorem 4.16, zy and zy′ lie in one nontrivial component, and ν ≺ θ on them transfers θ(zy ) ⋖ θ(zy′ ) to ν(zy ) ⋖ ν(zy′ ). Head. Let i be a head position, so h(x′i ) = θ(xi ). If θ(xi ) ̸= ⊥, then h(x′i ) ̸= ⊥, and rule (1) with z = xi gives ν ′ (x′i ) = ν(xi ). Otherwise xi ∈ Vt with ν(xi ) = ⊥, so xi is uncompared, and h nulls x′i , so ν ′ (x′i ) = ν(z) for the variable z at the position of x′i in the fixed atom, where θ(z) = ⊥. If ν(z) ̸= ⊥, then z ∈ Vn , so z is non-join and POSq (z) is that single position. By the head-position claim, and since xi ∈ Vt ⊆ VC is non-join, POSq (z) = POSq′ (x′i ) = POSq (xi ). Coveredness depends only on the position set and xi is covered, so z is covered, contradicting z ∈ Vn . Hence ν(z) = ⊥ = ν(xi ). Thus ν ′ satisfies q ′ over D0 with ν ′ (x̄′ ) = ā, so ā ∈ q ′ (D0 ). Since D0 and ν were arbitrary, q ⊆⊥ q ′ . ◀ As in Corollary B.7, the proof of Theorem 5.1 yields the following stronger fact: when containment fails, it fails at the tuple of a combined assignment itself. ▶ Corollary B.13. Let q, q ′ ∈ CQcmp,⊥ . If q ̸⊆⊥ q ′ , then θ(x̄) ∈ / q ′ (θ(Dq )) for some combined assignment θ. Proof. The converse direction of Theorem 5.1 uses its hypothesis only at tuples θ(x̄). Hence, if θ(x̄) ∈ q ′ (θ(Dq )) for every combined assignment θ, that proof turns an arbitrary satisfying valuation of q over an arbitrary database into a satisfying valuation of q ′ with the same output. Thus q ⊆⊥ q ′ . ◀ ▶ Lemma B.14 (Component pinning under nulls). Let q, q ′ ∈ CQcmp,⊥ , let C be a nontrivial component of CG, and let P be a set with Vn ⊆ P ⊆ Vn ∪ Vt , that is, a possible null pattern of a combined assignment. Let OG P be the opposite graph of C restricted to the vertices outside P , let Ecycle P (C) be its cycle reverse edges, and let σ : Ecycle P (C) → {<, =, >} be a choice whose trichotomy query qσ is satisfiable. Then there is a single local assignment θP,σ of the variables of C outside P with the following property. Let θ be a combined assignment with null pattern P that gives the endpoints of every edge of Ecycle P (C) the relation recorded by σ, and let θ∗ be obtained from θ by replacing its values on the variables of C outside P with those of θP,σ . If θ(x̄) ∈ / q ′ (θ(Dq )), then θ∗ (x̄) ∈ / q ′ (θ∗ (Dq )). Proof. A nulled variable is uncompared, so it has effective domain Q and carries only reverse edges. Hence OG P keeps the forced edges Eq of C on the surviving vertices, with the original constants, intervals, and representatives, and the atoms of qσ relate surviving vertices and decide the comparison encoded by every edge of Ecycle P (C). Lemmas B.10 and B.11 therefore apply to qσ read on OG P . Merging the variables that qσ entails equal and completing the order yields a single local assignment θP,σ on the surviving variables, which depends only on C, P ∩ vars(C), and σ. Its values are canonical values of q: the rank check in the proof of Lemma B.11 counts ℓ = |varsC,I | for q itself and uses only that no lower class contains a variable y with q |= x ≤ y, which holds here as well, and a variable pinned to a constant

H. Sternbach and S. Cohen

k takes k ∈ eDom(x). By Lemma B.11(3) and the atoms of qσ , the assignment θP,σ satisfies every reverse edge of OG P that lies on no directed cycle and realizes σ on Ecycle P (C). (P) Now let θ be as stated. Its non-null part on C satisfies the comparison atoms of q and realizes σ, so it satisfies every atom of qσ . Suppose that a satisfying valuation h of q ′ over θ∗ (Dq ) has h(x̄′ ) = θ∗ (x̄). Set h′ (y) = ⊥ if h(y) = ⊥, and otherwise h′ (y) = θ(z) for any z with θ∗ (z) = h(y). This is well defined. Suppose that θ∗ (z1 ) = θ∗ (z2 ) ̸= ⊥. If neither zj is a surviving variable of C, then θ and θ∗ agree on both. If both are, they lie in one merged class, since θP,σ separates distinct classes, so qσ entails z1 = z2 and θ equates them. If exactly one is, the shared value is a constant k to which that variable is pinned, because representatives of C are taken by no variable outside C, and then θ gives it k as well. Thus θ(z1 ) = θ(z2 ) in every case. Consequently h′ sends every relational atom of q ′ into θ(Dq ), position by position. It nulls exactly the variables that h nulls, hence no variable of nonnull(q ′ ), and h′ (x̄′ ) = θ(x̄): at a head position with h(x′i ) ̸= ⊥ we have θ∗ (z) = θ∗ (xi ) for the chosen z, so θ(z) = θ(xi ), and otherwise both assignments null xi . Let α be a comparison atom of q ′ , satisfied by h. Choose its realizers positionally as in the proof of Lemma B.8, and write the induced condition as w1 ⋖ w2 , a constant standing for itself. Realizers are non-null, so a realizer in C survives, and for a variable–variable atom both realizers lie in one component, as in the proof of Theorem 4.16. If no realizer lies in C, then θ and θ∗ agree on w1 , w2 . Otherwise w1 , w2 are vertices of OG P , and there are three cases. If the comparison atoms of q and the order of the constants decide w1 ⋖ w2 , its truth value is the same under θ and θ∗ . If its reverse edge lies in Ecycle P (C), the same holds, since σ records the relation under θ and θP,σ realizes σ. Otherwise its reverse edge lies on no directed cycle of OG P , so by (P) it is satisfied by θ∗ , and w1 ⋖ w2 fails under θ∗ , contradicting that h satisfies α. Hence w1 ⋖ w2 holds under θ, and h′ satisfies α. Thus h′ witnesses θ(x̄) ∈ q ′ (θ(Dq )), contradicting the assumption on θ. ◀ Proof of Theorem 5.2. By Theorem 5.1 containment is decided by the combined canonical family, and by Corollary B.13 a failure appears at the tuple θ(x̄) of some combined assignment. Fix a null pattern P and apply Lemma B.14 to the nontrivial components one at a time. A violating assignment is thereby replaced by one that agrees with θP,σ on every nontrivial component and still violates, so only such assignments are needed. Since Ecycle P (C) ⊆ Ecycle (C) for every P , indexing the cases by maps on the original cycle-edge sets leaves at most 3|Ecycle (q)| cases. Within a fixed case of the trichotomy, a variable in a nontrivial component takes the value assigned by θP,σ , unless it is mapped to ⊥. Thus, a variable in Vt has two possible choices, while every other variable in such a component has only one. Variables outside nontrivial components retain the choices defined in Section 5. Now consider a legal separator S. Since RG + contains a clique on every nontrivial component, each such component is contained in S ∪ Ci for some component Ci of RG + − S. The choices made for the variables of a nontrivial component must be considered together, since they determine a single assignment for that component. In particular, if the component meets both S and Ci , the choices on its two parts are not independent. We therefore use one choice per variable and apply the construction of Lemma 4.10 with these choices in place of the canonical values. This construction pairs every choice vector on S with a choice vector on each Ci . Not every such pair need be realizable in the fixed case. Indeed, if a nontrivial component meets both S and some Cj , the combined choices may make its trichotomy query unsatisfiable. Whenever a member is unrealizable on some Cj , we replace the choices on Cj by those of

39

40

Shrinking the Family of Test Databases

any realizable assignment that agrees with the given choices on S. If no such assignment exists, we simply omit that member. For the pair (θ, i) used to establish S-exhaustiveness in Lemma 4.10, the member is never omitted, since θ itself is a realizable assignment with the same choices on S, and this replacement can affect only components outside S ∪ Ci . It therefore does not change the required agreement on S ∪ Ci . Hence resulting family is still S-exhaustive, and its size
the Q Q remains bounded by val(v) · max i v∈S u∈Ci val(u). The stitching of Theorem 4.9 applies to this subfamily with two additions. First, coveringmatches are read with ⊥ as a canonical value of every variable of Vn ∪ Vt . The cohort of ⊥ is V⊥ = Vn ∪ Vt , and ⊥ is a witness value for y whenever this cohort covers POSq′ (y). The effective-domain condition is vacuous because a satisfying valuation nulls only variables of q ′ occurring in no comparison atom. Lemmas B.3 and B.4 are unaffected, since they use only that the value placed at a variable of q ′ is a witness value for it. The head step is unaffected for the same reason: a head variable sent to ⊥ lies in V⊥ . Second, the stitching step that in Section 4.2 was restricted to variable–constant atoms of q ′ is repaired by the cohort edges of RG + . For a variable–variable atom y ⋖ y ′ of q ′ , these edges place cmatch−1 (y) ∪ cmatch−1 (y ′ ) outside the separator in one component Ci . Hence the stitched valuation takes both values from the witness µi of that component: directly when a variable is served from Ci , through agreement of the witnesses on S when one is served from the separator, and from any witness when both cohorts lie in S. Since µi satisfies the comparison, so does the stitched valuation. Containment therefore holds if and only if every member of every case passes the test ψ(x̄) ∈ q ′ (ψ(Dq )). A violating member witnesses the failure of containment directly, and a failure of containment yields a violating combined assignment, then a violating assignment of some case, a violating member of that case. Each case contributes Qand then, by  the stitching, Q |Ecycle (q)| at most cases this gives v∈S val(v) · maxi u∈Ci val(u) databases. With at most 3 the stated bound. The numeric estimate follows from val(u) ≤ 2|match(u)| + 2 ≤ 2∆ + 2 outside nontrivial components, by Proposition 4.3, and from val(u) ≤ 2 inside them. ◀ ▶ Lemma B.15 (Feedback pinning under nulls). Let q, q ′ ∈ CQcmp,⊥ , let C be a nontrivial component of CG, and assume that the opposite graph of C has no non-strict cycle. Let P be a set with Vn ⊆ P ⊆ Vn ∪ Vt , that is, a possible null pattern of a combined assignment, let OG P be as in Lemma B.14, and let θ be a combined assignment with null pattern P such that θ(x̄) ∈ / q ′ (θ(Dq )). Then: 1. The set U of cycle reverse edges of OG P violated by θ is an MFES of OG P . 2. Every minimal MFES of OG P is the set of surviving edges of a minimal MFES of the opposite graph of C. In particular, if ℓC is the number of minimal MFESs of the original opposite graph, then OG P has at most ℓC minimal MFESs. 3. For every minimal MFES E of OG P there is a single local assignment θP,E of the variables of C outside P such that, if E ⊆ U , the combined assignment θ∗ that agrees with θP,E on the variables of C outside P and with θ everywhere else satisfies θ∗ (x̄) ∈ / q ′ (θ∗ (Dq )). Proof. Every directed cycle of OG P is a directed cycle of the opposite graph of C and therefore P contains a strict edge. Write V P for the vertices of OG P and Ematch(q) for its reverse edges, and call an edge of the opposite graph of C surviving if both its endpoints lie outside P . P Part (1). Suppose that (V P , Eq ∪ (Ematch(q) \ U )) has a directed cycle γ. Every reverse edge on γ lies on a directed cycle of OG P and is not in U , so θ satisfies it, and θ satisfies every edge of Eq . Hence θ is nondecreasing around γ and constant on it, contradicting the strict edge of γ. So U is an MFES of OG P , and it contains a minimal one.

H. Sternbach and S. Cohen

Part (2). Let E be a minimal MFES of OG P , and let F be the set of cycle reverse edges of the opposite graph of C with an endpoint in P . A vertex in P carries only reverse edges, so every directed cycle through such a vertex uses an edge of F , and every other directed cycle lies in OG P and uses an edge of E. Hence E ∪ F is an MFES of the opposite graph of C and contains a minimal one, say E ′′ . The surviving edges of E ′′ form a subset of E that still breaks every cycle of OG P , since a cycle of OG P avoiding them avoids all of E ′′ . By minimality of E this subset is E itself. Thus E is the surviving part of E ′′ , and distinct E have distinct E ′′ , so OG P has at most ℓC minimal MFESs. Part (3), the assignment. Let E be a minimal MFES of OG P and let H = (V P , Eq ∪ P (Ematch(q) \ E)), a DAG. The feedback query qE adds the relation asserted by every cycle reverse edge of OG P outside E and the negation of every edge of E. Its atoms are satisfiable: Lemma B.8 applied to H gives an assignment that is strict along every edge of H, and the ⋖ path from v to u that H contains for each e = (u → v) ∈ E, by minimality of E, makes it satisfy the added negation v ⋖′ u. The opposite graph of qE , read on OG P , is acyclic, because each of its edges is realized by a directed path of H. An edge of Eq or a kept cycle reverse edge is an edge of H. The negation added for e ∈ E is realized by the path from v to u just mentioned. A tightened endpoint edge coincides with the added variable–constant atom. A reverse edge of qE comes from a reverse edge of OG P that qE leaves undecided, since adding atoms only shrinks partial matches, so it lies outside Ecycle P (C) and belongs to H. A directed cycle would therefore expand to a directed cycle of the DAG H. Lemma B.11 applied to qE on OG P now yields a single local assignment θP,E of the surviving variables, with values canonical for q by the rank argument in the proof of Lemma B.14. By Lemma B.11(3) and the atoms of qE , it satisfies every edge of H and violates every edge of E. Since the opposite graph of qE is acyclic, no two surviving variables are entailed equal and no variable is pinned to a constant, so all values of θP,E are open-interval representatives, distinct for distinct variables and taken by no variable outside C. Part (3), the transport. Assume E ⊆ U and let θ∗ be as stated. Suppose that a satisfying valuation h of q ′ over θ∗ (Dq ) has h(x̄′ ) = θ∗ (x̄), and define h′ from h as in the proof of Lemma B.14. Well-definedness follows from the injectivity just noted, and relational atoms, the null pattern, and the head transport as there. Let α be a comparison atom of q ′ satisfied by h, with realizers chosen positionally and induced condition w1 ⋖ w2 . If no realizer lies in C, then θ and θ∗ agree on w1 , w2 . Otherwise w1 , w2 are vertices of OG P and there are three cases. If the atoms of q and the order of the constants decide the condition, its truth value is the same under θ and θ∗ . If its reverse edge lies in E, then E ⊆ U says that θ violates it, and θP,E violates it too, so the condition holds under both assignments. Otherwise its reverse edge lies in H and is satisfied by θ∗ , so the condition fails under θ∗ , contradicting that h satisfies α. Hence h′ satisfies every comparison atom of q ′ and witnesses θ(x̄) ∈ q ′ (θ(Dq )), a contradiction. ◀ Proof of the complexity claims of Corollary 5.3. By Corollary B.13 and the proof of Theorem 5.2, containment holds if and only if ψ(x̄) ∈ q ′ (ψ(Dq )) for every combined assignment ψ in the families of the at most 3|Ecycle (q)| cases. Assume that ∆, w, and |Ecycle (q)| are constant. Some legal separator S of RG + has |S| + maxi |Ci | ≤ w, and in particular |S| ≤ w, so such a separator is found by enumerating the polynomially many subsets of size at most w and checking legality and width directly. The witness sets, the canonical values, the graph RG + , and the local assignments of Lemma B.11 are all computable in polynomial time, and each case contributes at most (2∆ + 2)w assignments, so the whole family consists of constantly many databases, each of size polynomial in the queries. Testing ψ(x̄) ∈ q ′ (ψ(Dq )) amounts to guessing a valuation of q ′ and verifying its atoms, so the conjunction of constantly many

41

42

Shrinking the Family of Test Databases

such tests lies in NP. When q ′ admits polynomial evaluation, each test runs in polynomial time, and containment is in P. ◀ Proof of the feedback claim of Corollary 5.3. Replace Lemma B.14 by Lemma B.15 in the proof of Theorem 5.2. On each nontrivial component, a violating assignment with null pattern P violates a set of cycle reverse edges that is an MFES of OG P and contains a minimal one. Forcing the components one at a time preserves the violation. A case is now a minimal MFES of the original opposite graph of C, and under P it contributes the local assignment of its surviving part exactly when that surviving part is a minimal MFES of OG P , and nothing otherwise. By part (2) of Lemma B.15, every local assignment that is needed arises this way. Thus a component contributes at most ℓC cases, and the count within a case Q is unchanged. The factor 3|Ecycle (q)| is therefore replaced by C ℓC . ◀ ▶ Example B.16 (The combined test, worked). A genealogy records each child’s birth year in Person(parent, child, birthYr), where the parent may be unknown, and maintenance events are timestamped by the hour in Backup, Audit, Archive, and Purge. Consider q(p1 , p2 ) ← Person(p1 , p2 , b2 ), Person(p2 , p3 , b3 ), Backup(x1 ), Audit(x2 ), Archive(x3 ), Purge(x4 ),

0 < x1 , x2 , x3 , x4 < 10,

′

q (u1 , u2 ) ← Person(u1 , u2 , c2 ), Person(u1 , u3 , c3 ), Backup(s1 ), Audit(t1 ), Archive(g1 ), Purge(h1 ), Backup(s2 ), Audit(t2 ), s1 ≤ t1 , t1 ≤ g1 , g1 ≤ h1 , t2 ≤ s2 . Query q asks for a grandparent–parent pair and four events in the first ten hours. Query q ′ asks for a parent with two children, and for events in which a backup precedes an audit, an audit an archive, and an archive a purge, while a second audit follows a second backup. The join variables are join(q) = {p2 } and join(q ′ ) = {u1 }, and the compared variables are compVars(q) = {x1 , . . . , x4 } and compVars(q ′ ) = {s1 , s2 , t1 , t2 , g1 , h1 }. The non-join variables p1 , p3 are covered, by u1 and u2 , and only p1 shares its position set with a variable of nonnull(q ′ ), namely u1 . Hence Vt = {p1 }, Vn = {b2 , b3 }, and Vf holds the other six variables. The birth years are nulled outright, and only the unknown grandparent is toggled. We compute the three parameters of Theorem 5.2. The match sets are match(p1 ) = {u1 }, match(p2 ) = {u1 , u2 , u3 }, match(p3 ) = {u2 , u3 }, match(b2 ) = match(b3 ) = {c2 , c3 }, match(x1 ) = {s1 , s2 }, match(x2 ) = {t1 , t2 }, match(x3 ) = {g1 }, and match(x4 ) = {h1 }, so ∆ = 3. The variable–variable atoms of q ′ induce x1 ≤ x2 , x2 ≤ x3 , x3 ≤ x4 , and x2 ≤ x1 , none decided by q, so CG has the single nontrivial component C = {x1 , . . . , x4 }, with K(C) = {0, 10}. These comparisons contribute the strict reverse edges x2 → x1 , x3 → x2 , x4 → x3 , and x1 → x2 , whose only directed cycle is x1 → x2 → x1 . Hence |Ecycle (q)| = 2, and the two singleton edge sets are the minimal MFESs, so ℓC = 2. For the width, note that each isolated variable has one canonical value, because the variables of q ′ matching it carry no comparison. Hence val(p1 ) = 2, as p1 may also be nulled, while val(p2 ) = val(p3 ) = val(b2 ) = val(b3 ) = 1, and val(xi ) = 1 because a case pins C to one value and xi ∈ Vf . Moreover, RG + is the disjoint union of a clique on {p1 , p2 , p3 , b2 , b3 }, from the two Person atoms and their covering-matches, and a clique on C. So the empty separator is legal and w = 5. All four variables of C are active on (0, 10) and q entails no order among them, so each keeps all four representatives and C has 44 = 256 local assignments, which the two toggles of p1 double to |Dcomb (q, q ′ )| = 512. Theorem 5.2 tests instead 3|Ecycle (q)| · max{2, 1} = 18 canonical databases, and the feedback improvement of Corollary 5.3 only ℓC · 2 = 4. Adding further maintenance events lengthens the induced chain while leaving Ecycle (q) and the value counts unchanged. ◀

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181