arXiv CSopen access

Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics

Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics Sara Cohen # School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel

arXiv:2609.09978v1 [cs.DB] 9 Sep 2026

Abstract Bounded SQL equivalence checkers search for a counter-example database of bounded size, and a search that comes back empty proves nothing. We supply missing theory: computable bounds B such that agreement on all databases with at most B tuples per relation implies equivalence. We work in the combined-semantics framework, which captures SQL’s mix of duplicate-eliminating (DISTINCT) and duplicate-preserving computation over set-valued relations. For conjunctive queries we prove a bound linear in the query size for fixed multiset width: inequivalent queries already disagree on a database with at most 2w |Q| tuples, where the width w counts only the columns the queries actually read, independently of the total number of multiset variables. Declared keys shrink the bound to 2kw |Q| for the smaller key-width kw, acyclic foreign keys leave it unchanged, and the result extends to several classes of queries with comparisons, for which equivalence had not previously been characterized. For these fragments, bounded search becomes a terminating, complete decision procedure. 2012 ACM Subject Classification Theory of computation → Database query languages (principles); Theory of computation → Complexity theory and logic; Information systems → Query optimization Keywords and phrases query equivalence, combined semantics, bounded equivalence, counterexample bounds, conjunctive queries, integrity constraints Funding The authors were partially supported by the ISF (Israel Science Foundation, Grant 359/21).

1

Introduction

Query equivalence is a central problem of database theory. Two queries are equivalent if they return the same result on every database. Five decades of research on the problem have powered query optimization, rewriting over materialized views, and data integration [3, 4]; it has recently gained new urgency. Large language models now rewrite SQL at scale, and err at scale: in a recent industrial study, roughly a third of over 3,100 LLM-proposed rewrites of production queries returned results different from the original [17], and text-to-SQL benchmarks’ equivalence verdicts determine published model rankings [14]. This renewed demand has produced a wave of practical SQL equivalence checkers, split into two one-sided families. Symbolic provers [22, 12, 20] certify equivalence, but each only on a restricted syntactic fragment, and none certifies a refutation. Bounded refuters [8, 13, 21, 14] embrace the most expressive queries by testing bounded equivalence: a solver searches for a counter-example—a database on which the two queries disagree—among all databases with at most n tuples per relation, growing n until timeout or fixing it in advance. A counter-example refutes equivalence; an exhausted search proves nothing, yet its verdicts are trusted. A fifth of the pairs one suite of VeriEQL’s evaluation reports as “checked” are in fact inequivalent, two needing counter-examples of over a thousand tuples [13], and SpotIt publishes what survives its n=5-capped search as benchmark accuracy [14]. What is missing is a completeness threshold: a computable bound B such that any two inequivalent queries already disagree on some database with at most B tuples per relation. With such a bound the search stops at B and reports equivalent with certainty—and a per-relation version caps each relation separately, shrinking the search space further. This paper establishes such bounds for the conjunctive core of the problem.

2

Equivalence of Queries Mixing Set and Bag Semantics

We work in the framework of combined semantics [9, 10], which captures a core aspect of how real SQL queries evaluate. SQL mixes two modes of computation. A DISTINCT block or an EXISTS subquery is a set computation, blind to duplicates, while projection without DISTINCT preserves multiplicities. Combined semantics expresses this mix in one language by declaring, per variable, whether different values contribute new copies to the answer (multiset variables) or not (set variables). Following common practice, we take stored relations to be sets, as is the case whenever every table declares a key. For the two pure extremes, small counter-examples have long been known. Inequivalent set queries (pure DISTINCT) disagree on a database with at most one tuple per query atom [3], and the same holds for pure bag-set queries [4]. In both cases the bound is the self-join size: the maximum number of atoms sharing a predicate. For queries that genuinely mix the two modes, the property fails, and it fails already for the simplest possible queries. ▶ Example 1. The following queries return the names of vip customers. The first returns each name once. The second returns each name once per distinct customer bearing it. QA: SELECT DISTINCT name FROM Customer WHERE type=’vip’ QB: SELECT name FROM (SELECT DISTINCT cid, name FROM Customer WHERE type=’vip’) D

Each query uses the Customer table once, so the classical bounds promise a one-tuple counter-example. None exists: the queries agree on every one-tuple database, and differ only once two vip customers share a name—which takes two tuples. The classical bound is wrong for mixed queries, and how far it must grow is precisely the question. ♢ The example is benign, but the general phenomenon is not: it is not even clear that a computable bound on counter-example size exists at all. Our main result is that it does, and it is linear in the query size. Contributions. Section 3 proves the central result, a counter-example bound for relational combined-semantics queries that is linear in the query: inequivalent queries disagree on a database with at most 2w |Q| tuples, where |Q| is the number of atoms and the multiset width w counts only the multiset columns the queries actually read. Section 4 admits integrity constraints. The bound refines per relation, drops to 2kw |Q| for the smaller key-width kw under declared keys, covering in particular queries whose joins follow keys acyclically, and is unchanged under acyclic foreign keys. The same argument characterizes equivalence there, as multiset-homomorphism of the key-chased reducts, and so places the problem in NP. These are the first results on equivalence of multiset and combined queries in the presence of integrity constraints. Section 5 extends the bound to several classes of queries with comparisons against constants, for which no equivalence characterization, and hence no decision procedure, was previously known. Taken together, the results turn heuristic bounded search into a terminating, complete decision procedure for the conjunctive fragment studied here, with a threshold that is small whenever self-joins are few and the multiset columns are narrow. All proofs, and some constructions, are deferred to the appendix.

2

Preliminaries

We recall the framework of combined semantics introduced in [9, 10], specialized to databases whose relations are sets. Combined semantics uniformly captures both set semantics (the DISTINCT behaviour of SQL, and the existential behaviour of subqueries) and bag-set semantics (the multiplicities produced by projection without DISTINCT) within a single query language.

S. Cohen

Databases. Predicate symbols are denoted p, q, r. A database D over a set of predicate symbols P is a set of ground atoms with predicates from P. Every relation is thus a set: multiplicities in query answers arise from the bag-set behaviour of projection, not from duplicate stored tuples. The active domain adom(D) is the set of constants occurring in D. Keys and Foreign Keys. Real schemas constrain their data. A schema assigns every predicate p of arity rp a key key(p) ⊆ {1, . . . , rp }, and declares a set of foreign keys. A foreign key is a triple (p, ı̄, q), where ı̄ is a tuple of positions of p with |ı̄| = |key(q)|. A database D is legal if it satisfies every declared constraint. A key requires that no two distinct p-atoms agree on all positions in key(p). A foreign key (p, ı̄, q) requies for every p(s̄) ∈ D some q(t̄) ∈ D with s̄|ı̄ = t̄|key(q) . The foreign keys are acyclic if the relation “p references q” on predicates has no cycle. When every key is the whole tuple, i.e., key(p) = {1, . . . , rp } for all p, and no foreign keys are declared, every database is legal. We call such a schema unconstrained. ▶ Example 2 (Running Example). Our examples use a small retail schema with four relations, key attributes underlined: Customer(cid, name, email, phone, city, state, cc, signup, type), Order(oid, cid, date, via, status, shipcity, total), Item(oid, sku, qty, price, discount), and Product(sku, title, category, brand, list, color). An order is placed by a customer, and its items reference products by their sku, so the schema declares acyclic foreign keys, from Order.cid to Customer, from Item.oid to Order, and from Item.sku to Product. A customer or a product may recur across many rows—one shopper places many orders, and a popular product appears in many of them. ♢ Syntax of Queries. We denote constants by c, d and variables (ranging over constants) by x, y, z. A term s, t is either a variable or a constant. We use x̄ and s̄ to denote a sequence of variables and terms, respectively. Queries can contain two types of atoms: relational atoms, denoted p(s̄), order atoms or comparisons, denoted s1 ρ s2 where ρ ∈ {<, ≤, >, ≥, =, ̸=}. A condition L is a conjunction of relational and order atoms. Variables in a query are either distinguished, appearing in the head, or nondistinguished, appearing only in the body. The nondistinguished variables are of two types, set variables and multiset variables: intuitively, assignments differing on multiset variables contribute to the multiplicity of the query result, while those differing on set variables do not. We specify the set of multiset variables to the right of the condition, and we call a column holding a multiset variable a multiset column. A conjunctive query is an expression of the form Q(x̄) ← L, M where L is a conjunction of atoms and M is the set of multiset variables. We require M to contain only nondistinguished variables. We assume queries are safe [18], i.e., every variable in the query occurs in some relational atom. For a query Q, we write |Q| for the number of relational atoms of Q and, when convenient, treat the body as this set, writing p(s̄) ∈ Q for a relational atom of Q. We define several classes of queries. Query Q is a set query if M = ∅, a multiset query if M is precisely the set of all nondistinguished variables, and a combined query otherwise. A query is relational if it has no order atoms. Set queries correspond to SQL queries that eliminate duplicates (via DISTINCT), while multiset queries correspond to SQL queries without DISTINCT and with no existential subqueries. Set and multiset variables also meet through existential subqueries: a multiset query that probes a multiset column with an EXISTS, IN, or ANY subquery equates the multiset variable with a set variable of the inner block. The value is then counted once, however many rows of the inner block witness the subquery. Real SQL queries may combine both set and multiset computations, as demonstrated in the following example.

3

4

Equivalence of Queries Mixing Set and Bag Semantics

▶ Example 3 (Query syntax). Recall the relations of Example 2. The queries below report the customers who ordered an electronics product, differing only in how they treat duplicates: Q1: SELECT D.cid FROM (SELECT DISTINCT O.cid, I.sku FROM Order O, Item I, Product P WHERE O.oid = I.oid AND I.sku = P.sku AND P.category = ’electronics’) D Q2: SELECT DISTINCT O.cid FROM Order O, Item I, Product P WHERE O.oid = I.oid AND I.sku = P.sku AND P.category = ’electronics’

Query Q1 deduplicates on (cid, sku) before projecting onto cid. Query Q2 deduplicates fully. Query Q3, defined as Q2 without DISTINCT, returns one row per electronics line item. To render these in our notation, we write _ for an anonymous variable (one used nowhere else, distinct at each appearance) and . . . for a run of them, and let L be the body Order(o, x, . . . ) ∧ Item(o, k, . . . ) ∧ Product(k, _, electronics, . . . ), finding a customer x who placed an order o containing an electronics product k. Writing V for the set of all nondistinguished variables of L (o, k, and every _), the three queries are Q1 (x) ← L, {k}, Q2 (x) ← L, ∅, and Q3 (x) ← L, V . Thus Q1 is combined, counting a customer once per distinct product, Q2 is a set query, and Q3 is a multiset query. ♢ Semantics of Queries. Let D be a database and Q(x̄) ← L, M be a query. A satisfying assignment γ maps the terms of Q to constants such that γ is the identity on constants, for every relational atom p(s̄) in L, we have p(γs̄) ∈ D, for every order atom s1 ρ s2 in L, we have γs1 ρ γs2 . Let Γ(Q, D) denote the set of satisfying assignments of Q. If Y is a set of variables of Q, we write ΓY (Q, D) for the projection of Γ(Q, D) onto Y , i.e., the set of all assignments to Y that extend to a satisfying assignment in Γ(Q, D). Let X be the set of distinguished variables of Q. The result of applying Q to D, denoted Q(D), is the multiset  γ(x̄) | γ ∈ ΓX∪M (Q, D) . Thus each assignment to the distinguished and multiset variables that extends to a satisfying assignment contributes one tuple to the answer, whereas the choices for the set variables are collapsed. When Q is a set query this coincides with set semantics, as M = ∅ and every answer tuple appears exactly once. When Q is a multiset query it coincides with bag-set semantics. The answer multiplicities are exactly what SQL’s COUNT reports, COUNT(*) for a bag block and COUNT(DISTINCT ...) over the multiset columns, and adding such an aggregate preserves equivalence. Combined-semantics equivalence is thus precisely the equivalence of SQL counting queries. Query Containment and Equivalence. Fix a schema. Query Q is contained in query Q′ , denoted Q ⊆ Q′ , if Q(D) is a subbag of Q′ (D) for every legal database D. Queries Q and Q′ are equivalent, written Q ≡ Q′ , if containment holds in both directions. Over an unconstrained schema these are the classical notions, quantifying over all set databases. Over unconstrained schemas, containment of set queries and equivalence of multiset queries are classically characterized by homomorphisms and isomorphisms respectively [3, 15, 19, 4, 11] (see Section 6). For queries combining set and multiset variables, equivalence is

S. Cohen

characterized only for relational queries over unconstrained schemas, by multiset homomorphisms [9, 10]. Almost no characterization is known with comparisons (except for the join queries of [9]), and no prior work addresses combined equivalence under integrity constraints. Unlike work that directly characterizes equivalence, we reduce equivalence to bounded equivalence. Formally, let D be a database over predicates P. The size of a predicate p in D, denoted size(p, D), is the number of p-facts in D. We say that D is n-bound if size(p, D) ≤ n for all p ∈ P. We write Q ⊆n Q′ if Q(D) ⊆ Q′ (D) for all legal n-bound databases D, and Q ≡n Q′ if this holds in both directions. Clearly, if Q ⊆ Q′ then Q ⊆n Q′ for every n. This paper studies the converse: Given a class of queries, is there a computable bound n such that n-bounded equivalence implies equivalence? Under both set and bag-set semantics, over unconstrained schemas, the equivalence problem enjoys the small counter-example property: if two queries are inequivalent, a witnessing database exists whose size is bounded by the number of atoms in the queries [3, 4, 11, 10]. To be precise, the self-join size sj(Q) of Q is the maximum number of occurrences of any single predicate in Q. Write k = sj(Q) and k ′ = sj(Q′ ). For set queries, Q ⊆ Q′ if and only if Q ⊆k Q′ , since the frozen body of Q—a database with one atom per subgoal—already witnesses any failure of a containment mapping [3]. For multiset queries, Q ≡ Q′ if and only if Q ≡max(k,k′ ) Q′ , by the characterization of bag-set equivalence as isomorphism of the queries [4], which a database built from the bodies likewise detects. For combined queries, bounded equivalence up to the self-join size no longer implies equivalence, even for very simple queries, as demonstrated by Example 1. This paper extends these bounds to queries that mix set and multiset variables. Since such queries cannot be equivalent unless their bodies are equivalent as set queries, we assume throughout that the queries are set-equivalent over the legal databases of the schema at hand, and that each is satisfiable, nonempty on some legal database. We focus on whether their multiplicities coincide. Set-equivalence is itself decided within thresholds below every bound we prove [3, 1].

3

Unconstrained Schemas

This section proves the counter-example bound for relational queries over an unconstrained schema (Theorem 7), where every database is legal. Constrained schemas follow in Section 4. Recall the standing assumption that Q, Q′ are set-equivalent (Section 2), so their answers can differ only in multiplicity. Throughout this section queries are relational (no order atoms), the setting of the [9, 10] characterization. Let Q(x̄) ← L, M and Q′ (x̄′ ) ← L′ , M ′ be relational conjunctive queries. A multiset-homomorphism from Q′ to Q is a mapping µ from the terms of Q′ to the terms of Q satisfying: 1. µ(x̄′ ) = x̄, 2. µ maps each constant to itself, 3. every atom of µ(L′ ) occurs in L, and 4. µ maps M ′ injectively into M : µ(M ′ ) ⊆ M and µy ̸= µy ′ for distinct y, y ′ ∈ M ′ . Conditions (1)–(3) state that µ is an ordinary containment mapping from Q′ to Q, which witnesses the set-containment Q ⊆ Q′ . We say that Q and Q′ are multiset-homomorphic if there is a multiset-homomorphism from Q′ to Q and one from Q to Q′ . Since each direction injects one set of multiset variables into the other, multiset-homomorphic queries necessarily satisfy |M | = |M ′ |. Multiset-homomorphisms characterize equivalence of relational queries.

5

6

Equivalence of Queries Mixing Set and Bag Semantics

▶ Theorem 4 ([9, 10]). Let Q and Q′ be relational conjunctive queries. Then Q ≡ Q′ if and only if Q and Q′ are multiset-homomorphic. Sufficiency is immediate: a multiset-homomorphism from Q′ to Q shows that Q′ returns each tuple at least as often as Q on every database, so maps in both directions give equality. Necessity is proved by a database construction that we now outline, as the same construction yields our counter-example bound. The canonical family and the characteristic monomial. Let m = |M | be the number of multiset variables of Q. The canonical family of Q is parameterized by a vector ⃗ = (N1 , . . . , Nm ) ∈ Nm N ⃗ [Q], the j+ , one parameter per multiset variable. In the database DN th multiset variable ranges over a fresh domain of exactly Nj constants, while the distinguished and set variables receive fixed fresh values, shared across all assignments. For each of the Qm resulting j=1 Nj assignments, one ground atom is inserted per subgoal of Q, and identical ⃗. atoms are merged. Using c̄ for the fixed image of the head, we have c̄ ∈ Q(DN⃗ [Q]) for every N (R) ⃗ For any query R, let F (N ) be the multiplicity of c̄ in the bag R(D ⃗ [Q]). The function N

F (R) is a polynomial in N1 , . . . , Nm with non-negative integer coefficients, of total degree at most the number of multiset variables of R, since each multiset variable of R contributes at most one parameter factor. One monomial of F (Q) is special, the characteristic monomial (Q) P∗ = N1 N2 · · · Nm : the unique monomial of total degree m that is squarefree, using every parameter exactly once. It always appears in F (Q) with a positive coefficient, realized by the generic assignment that places each multiset variable in its own fresh domain. Crucially, ′ (Q) P∗ appears in F (Q ) if and only if there is a multiset-homomorphism from Q′ to Q [10]. ′ Theorem 4 follows. If Q ≡ Q′ then F (Q) = F (Q ) , so the characteristic monomial— ′ present in F (Q) —also appears in F (Q ) , yielding a multiset-homomorphism from Q′ to Q, and symmetrically over the family of Q′ . The same correspondence separates inequivalent queries on the family itself, and the rest of this section turns that separation into an explicit small witness. Separation at a Boolean corner. Throughout, for a query R with multiset variables MR , we write mR := |MR |, so m = mQ . The engine of the bound is the next proposition: it separates the two multiplicity functions on the canonical family itself, not merely on some unspecified database. Its proof rests on three facts restated from [10]: polynomiality with a per-query degree bound, positivity of the characteristic monomial in F (Q) , and the ′ multiset-homomorphism criterion for its appearance in F (Q ) . ▶ Proposition 5 (Characteristic monomial separation). Let Q′ be a relational query with no (Q) multiset-homomorphism from Q′ to Q. Then the characteristic monomial P∗ does not ′ ′ appear in F (Q ) , so P := F (Q) − F (Q ) is a nonzero polynomial on the family {DN⃗ [Q]} (its characteristic monomial coefficient is positive). If moreover mQ′ ≤ m, then P has total degree at most m. This says more than that P is a nonzero polynomial of degree at most m. The monomial responsible is the multilinear N1 · · · Nm , and by Alon’s Combinatorial Nullstellensatz [2], a Q nonzero top-degree coefficient on i Niti forces a nonzero point on any grid A1 × · · · × Am with |Ai | > ti . Here every ti is 1, so we may take every Ai = {1, 2}. Hence, when no multiset-homomorphism Q′ → Q exists and mQ′ ≤ m, the queries already disagree on a corner database D⃗a [Q] with ⃗a ∈ {1, 2}m . The second requirement is free, as the queries can always be named to meet it: when their counts differ, take the one with fewer multiset ′ (Q) variables as Q′ , and no monomial of F (Q ) then reaches the degree m of P∗ , so that direction fails outright. Note that a generic degree-m polynomial would force only the grid

S. Cohen

7

{1, . . . , m + 1}m and a witness of size |Q|(m + 1)m . The multilinearity of the characteristic monomial pins the witness to the corner. It remains to bound the size of the corner databases. The size of a corner database. We measure database size per relation, as in the n-bound notion of Section 2: size(p, D) is the number of p-facts. Recall that |Q| is the number of Q relational atoms of Q. The construction inserts, for each of the i Ni blow-up assignments, Q at most one atom per subgoal, so, before merging, a relation could carry a factor i Ni . At a Boolean corner ⃗a ∈ {1, 2}m , however, the merging of identical atoms is dramatic. Each subgoal produces only a bounded number of distinct atoms, no matter how many multiset variables are set to two. The relevant parameter is not the arity but the number of multiset variables an atom carries. For an atom p(s̄), let #M (p(s̄)) be the number of distinct multiset variables occurring in s̄. Distinguished and set variables, being fixed in the canonical family, do not count. For a predicate p, the width of p in Q is w(Q, p) := max{#M (p(s̄)) : p(s̄) ∈ Q}, the largest such count among atoms with predicate p. The multiset width of Q is the maximum over predicates, w(Q) := maxp w(Q, p). Thus w(Q, p) ≤ w(Q) for every p, and w(Q) is at most the maximum arity, often much smaller. Recall the self-join size sj(Q), the maximum number of occurrences of any single predicate in Q. We refine it per predicate: sj(Q, p) is the number of subgoals of Q with predicate p, so sj(Q) = maxp sj(Q, p). When Q is clear from context we drop it, writing w, w(p), sj, and sj(p). ▶ Lemma 6 (Distinct atoms at a corner). For every ⃗a ∈ {1, 2}m and predicate p, X
size p, D⃗a [Q] ≤ 2w(p) sj(p), hence |D⃗a [Q]| ≤ 2 #M (p(s̄)) ≤ 2w |Q|. p(s̄)∈Q

The reason is that a subgoal’s atoms vary only through its multiset variables, each of which takes at most two values at a corner. Neither bound mentions the corner ⃗a or the number m of multiset variables, so both are uniform over the corner and independent of m. Combining the separation with the size count gives the main theorem. ▶ Theorem 7 (Counter-example bound for inequivalence). Let Q and Q′ be relational queries with Q ̸≡ Q′ . Write wp := max(w(Q, p), w(Q′ , p)) and w := maxp wp = max(w(Q), w(Q′ )) for the per-predicate and the overall width of the pair. Then there is a database D with Q(D) ̸= Q′ (D),

|D| ≤ 2w max |Q|, |Q′ | and size(p, D) ≤ 2wp max sj(Q, p), sj(Q′ , p) for every p. In particular, Q ≡b Q′ implies Q ≡ Q′ for b = maxp 2wp max(sj(Q, p), sj(Q′ , p)). By Theorem 4, some direction, say Q′ → Q, admits no multiset-homomorphism, named as above. The separation then produces a corner database of Q on which the queries disagree, and Lemma 6 bounds its size. Two tightness questions must be kept apart: whether every multiset variable must be doubled, and whether the 2w |Q| atoms the bound then permits are ever needed. The first is settled by one pair of queries, which leaves the second untouched. The exact threshold is open (Section 7). ▶ Example 8 (The full corner can be necessary). Let L be the directed 4-cycle p(x0 , x1 ) ∧ p(x1 , x2 ) ∧ p(x2 , x3 ) ∧ p(x3 , x0 ) and take the Boolean queries Q ← L, {x0 , x1 } and Q′ ← ′ L, {x0 , x2 }, differing only in their multiset variables. On the canonical family F (Q) − F (Q ) = (N1 + 1)(N2 + 1) − 2(N1 + N2 ) = (N1 − 1)(N2 − 1), which vanishes whenever N1 = 1 or

8

Equivalence of Queries Mixing Set and Bag Semantics

N2 = 1. Only the all-twos corner separates, so no multiset variable escapes doubling. The size bound is loose on the same pair. Theorem 7 permits 16 atoms, the witness D(2,2) [Q] uses nine, and {p(0, 0), p(0, 1), p(1, 0)} already separates. ♢ Collapsing unobserved attributes. The width w can come close to the arity when a wide table’s columns each carry their own multiset variable. Yet a query typically inspects only a handful of those columns, and the width that governs the bound ought to count only them. Call the i-th attribute of a relation r unobserved (for the pair Q, Q′ ) if in neither query does any atom of r place, in position i, a distinguished variable, a join variable—one occurring in two or more positions of the body—or a variable occurring in a comparison. A multiset variable in an unobserved attribute feeds the multiplicity but is otherwise inert. The collapse of the pair Q, Q′ merges each relation’s unobserved attributes into one fresh attribute, rewriting queries and databases alike. It yields queries Q↓ , Q′↓ over a shared schema with w(Q↓ ) ≤ w(Q), |Q↓ | = |Q|, and sj(Q↓ ) = sj(Q), and it preserves every relation’s size. ▶ Lemma 9 (Collapse preserves equivalence). Q ≡ Q′ if and only if Q↓ ≡ Q′↓ . The merged attribute carries a fresh multiset variable exactly when a merged column did, and that variable ranges over the product of the merged domains, so it reproduces exactly the multiplicity factor the merged variables contributed. Because the collapse preserves sizes, witnesses for Q ̸≡ Q′ and for Q↓ ̸≡ Q′↓ correspond with identical per-relation sizes. Theorem 7 holds for any relational queries, so we may apply it to the collapse Q↓ , Q′↓ and lift the witness
back by Lemma 9, replacing the width w by the collapsed width max w(Q↓ ), w(Q′↓ ) ≤ w. ▶ Example 10 (Collapsing a wide pair). Collapse the pair (Q1 , Q3 ) of Example 3. In their shared body the only joins are o and k, with head x, so every other column holds an anonymous variable occurring once, hence unobserved. The collapse merges each relation’s unobserved columns into one fresh attribute, giving the body Order↓ (o, x, z1 ) ∧ Item↓ (o, k, z2 ) ∧ Product↓ (k, electronics, z3 ). In Q↓3 the new variables z1 , z2 , z3 are multiset and the width drops from 6 to 3. In Q↓1 they are set placeholders and the width stays 1. The canonical witness thus shrinks from 26 |Q3 | to 23 |Q3 | atoms: collapsing first saves exponentially in the columns the queries ignore. ♢

4

Constrained Schemas

We now let the schema constrain its data, first by declared keys and then, at the end of the section, by acyclic foreign keys as well (Section 4). Legality means satisfying the declared constraints. A key need not remove any counter-example, as is the case with the two-customer witness of Example 1 which respects the key of Customer. It can, however, remove all of them: under key(p) = {1}, the 4-cycle pair of Example 8 becomes equivalent, as the key makes p a partial function f and both queries count the points with f 4 (x0 ) = x0 . For an atom p(s̄) of Q, let kw(p(s̄)) be the number of distinct multiset variables of Q occurring at a key position of the atom, i.e., at a position in key(p). The key-width of a predicate p in Q is kw(Q, p) := max{kw(p(s̄)) : p(s̄) ∈ Q}, and the key-width of Q is kw(Q) := maxp kw(Q, p). As with the multiset width, we drop Q when it is clear from context. Only key positions are counted, so kw(Q) ≤ w(Q), with equality when every key is the whole tuple. In the case where multiset variables never occupy a key position, kw(Q) = 0. Key-width governs the bound under keys because a multiset variable off the key carries no multiplicity. Each atom p(s̄) of Q reads its key as a functional dependency on the variables of Q: the variables at the key positions of the atom determine those at its remaining positions.

S. Cohen

9

For a set T of variables, T + is the closure of T under these dependencies, and a variable v is T -determined if v ∈ T + : on any legal database its value is fixed once the variables of T are. ▶ Lemma 11 (Demotion). Let X be the distinguished variables of Q and let v ∈ M be (X ∪ (M \ {v}))-determined. Let Q−v be Q with v moved from M to the set variables. Then Q ≡ Q−v and kw(Q−v ) ≤ kw(Q). On a legal database the forgotten variable is determined by the rest, so forgetting it bijects the assignment sets and no multiplicity changes. Demote an (X ∪ (M \ {v}))determined multiset variable, repeat until none remains, and call the result a key-reduct Q♭ . By Lemma 11, Q♭ ≡ Q and kw(Q♭ ) ≤ kw(Q). Its surviving multiset variables are key-free: none is determined by the remaining distinguished and multiset variables. Demotion also explains why keys force the combined setting on us. A multiset query need not stay one over legal databases, its key-reduct having genuine set variables, so bag-set semantics alone does not survive the declaration of a key. Demotion is non-deterministic: different orders demote different mutually-determined variables, and the surviving sets can differ even in size and key-width. But every key-reduct satisfies Q♭ ≡ Q and kw(Q♭ ) ≤ kw(Q), which is all the bound requires, and whether the reduct is key-anchored, defined below, is order-independent (Proposition B.3). Anchoring and legality. Key-freeness alone does not make the canonical family of Section 3 legal: the demotion that frees one variable can fix another that serves as a key elsewhere. The obstruction is a cyclic key dependency. ▶ Example 12 (Key-freeness is not enough). Let R have body p(y0 , y1 ) ∧ p(y1 , y0 ), with key(p) = {1} and M = {y0 , y1 }. The key makes p a partial function, so the two variables move as a pair. Demotion frees y0 by freezing y1 , and the canonical family then varies y0 alone, which the key forbids. Legal witnesses of the same multiplicity still exist, so only the rigid family fails. ♢ What the construction needs is anchoring. Call a query R key-anchored if every multiset variable of R occurs, in every atom of R containing it, at a key position of that atom. The key-chase of R repeatedly unifies the terms of two atoms of a predicate that agree on their key, and merges duplicates. It terminates and preserves equivalence over legal databases, and the canonical family of a key-chased key-anchored query is legal at every corner (Lemma B.1). Call Q key-anchorable if its key-reducts are key-anchored. The condition is decidable and order-independent, being equivalent to M ⊆ (X ∪A)+ , where A collects the multiset variables occurring only at key positions (Proposition B.3). Finally, in a legal database distinct atoms of a predicate differ on their key, so a legal corner database has at most 2kw(p) atoms per subgoal (Lemma B.2). The bound follows for key-anchorable queries. ▶ Theorem 13 (Equivalence and counter-examples under declared keys). Let Q, Q′ be keyanchorable relational queries over a schema with declared keys and no foreign keys, and write Q♮ for the key-chase of the key-reduct of Q. Put kw := max(kw(Q♮ ), kw(Q′♮ )) and kw(p) := max(kw(Q♮ , p), kw(Q′♮ , p)), both at most the same quantities for Q and Q′ . Then 1. Q ≡ Q′ over legal databases if and only if Q♮ and Q′♮ are multiset-homomorphic, and 2. if Q ̸≡ Q′ , there is a legal database D with Q(D) ̸= Q′ (D), |D| ≤ 2kw max(|Q♮ |, |Q′♮ |)

and

size(p, D) ≤ 2kw(p) max(sj(Q♮ , p), sj(Q′♮ , p))

for every predicate p. In particular Q ≡b Q′ implies Q ≡ Q′ for b = maxp 2kw(p) max(sj(Q♮ , p), sj(Q′♮ , p)).

10

Equivalence of Queries Mixing Set and Bag Semantics

Both clauses come from one argument. The proof passes to the key-reducts, which are equivalent to the original queries by Lemma 11. Their corner databases are legal by Lemma B.1, so the separation of Theorem 7 applies to them verbatim and delivers a legal witness, which Lemma B.2 counts. Multiset-homomorphic reducts are equivalent over all databases by Theorem 4, hence over the legal ones, which gives clause (1) with the separation as its converse. One consequence: if every multiset variable is X-determined the reducts are set queries, which the standing assumption already equates, so the question bites only when some multiset variable is not forced by the head. Finally, the collapse of Lemma 9 carries over to keyed schemas, replacing kw in Theorem 13 by its collapsed counterpart. The anchoring requirement is not incidental. Call an atom of Q a counting atom if all its variables are distinguished or multiset, and call Q well-formed if every multiset variable occurs in some counting atom. Real SQL queries whose counting arises from a FROM clause over base tables are well-formed, every column of such a table being either returned or a contributor to the multiplicity. Say that a counting atom b references a counting atom b′ if some multiset variable at a key position of b′ occurs at a non-key position of b. ▶ Proposition 14 (Well-formed queries with acyclic key references). Let Q be a well-formed query, over a schema with declared keys, such that 1. every occurrence of a multiset variable at a non-key position lies in a counting atom, and 2. the references among the counting atoms of Q are acyclic. Then M ⊆ (X ∪ A)+ , that is, Q is key-anchorable. Two such queries meet the requirements of Theorem 13. In SQL terms, the two conditions say that multiset columns are compared, inside subqueries, only against key columns, and that the join conditions of the counting block do not cycle through keys. Joins that follow foreign keys, as in star and snowflake schemas, always satisfy both. Neither condition is free: the query of Example 12 is well-formed, both its atoms being counting atoms, yet its two atoms reference each other and it is not key-anchorable. Foreign keys. We now admit the full schemas of Section 2: declared keys together with acyclic foreign keys. Foreign keys are inclusion dependencies, handled by a chase. Because they point key-into-key, the foreign-key chase is deterministic: for each unmatched reference it adds the referenced atom, copying the key values and filling the remaining positions with b for the chased query. For acyclic foreign keys fresh set variables (Lemma B.4). We write Q the chase terminates, adds no multiset variable, so M , w, and kw are unchanged, and its b return the same answers. As added subgoals are redundant on legal databases, so Q and Q with demotion, the chase moves a multiset query out of its class: the atoms it adds carry set b is combined even when Q was not. variables, so Q ▶ Theorem 15 (Counter-example bound under keys and acyclic foreign keys). Let Q, Q′ be b Q c′ are relational queries over a schema with keys and acyclic foreign keys, such that Q, ′ b Q c : equivalence over legal key-anchorable. Then both clauses of Theorem 13 hold for Q, ♮ ♮ ′ b c databases is multiset-homomorphism of Q and Q , and inequivalent Q, Q′ are separated by b |Q c′ |) atoms. The query size |Q| b is at most |Q| a legal database with at most 2kw max(|Q|, times the reference depth of the schema. The chase makes every referenced atom explicit, so the witness of Theorem 13 for the chased queries is already closed under the foreign keys. The chase also preserves the requirements of Proposition 14, since every atom it adds places existing variables only at key positions.

S. Cohen

Clause (1) also settles the complexity, which the bounds leave open: their witnesses are exponential, whereas a multiset-homomorphism is a mapping between queries of polynomial size. ▶ Corollary 16 (Complexity of equivalence under constraints). Deciding Q ≡ Q′ over a schema with declared keys and acyclic foreign keys is NP-complete for queries whose foreign-key chases are key-anchorable. Membership guesses the two multiset-homomorphisms of clause (1), checked by inspection of the atoms, over queries computed in polynomial time: the foreign-key chase is bounded by the reference depth, the key-reduct is a closure under the key dependencies, and the key-chase is a union-find on the terms. Hardness is classical, already for M = M ′ = ∅ [3]. Enumeration is thus needed only to exhibit a counter-example, never to decide. The residual open case. Outside key-anchorability the separation is driven by a multiset variable that demotion has stranded off a key, so the rigid canonical family is illegal although legal witnesses exist (Example 12). The regime is not exotic: counting the customers that placed some order joins the counted cid to a non-key position of an existential atom. What is missing is realizability, assigning the set variables as functions of the multiset ones so as to meet the keys while preserving the separating multiplicity. Whether a computable bound exists here remains open.

5

Queries with Comparisons

Throughout, Q ← L, M and Q′ ← L′ , M ′ are combined-semantics queries with order atoms. Until Section 5.3 the schema is unconstrained and every order atom is var-const: y ρ c with ρ ∈ {<, ≤, >, ≥, =, = ̸ }, y a variable and c a constant. Variable-versus-variable comparisons are set aside until Section 5.3, which readmits those pinned by keys. Renaming nondistinguished variables apart, we assume Q, Q′ share no variables. Values are drawn from a dense linear order without endpoints, taken to be Q. Density is the only property we use: it lets us drop a fresh value into any open interval. Write RQ for the relational part of Q (delete the order atoms). Following the standing assumption, Q and Q′ are set-equivalent, so the sole question is whether their multiplicities agree. The whole section turns on one idea. The constants of the two queries cut the domain into finitely many intervals, a comparison reads a value only through the interval it lies in, and once each value is fixed to an interval, what remains is the relational counting of Section 3. The comparisons decide only which values appear, not how many atoms, so the witness never grows beyond the comparison-free bound 2w |Q|. What varies is what fixes the interval of a compared value in the witness. Section 5.1 builds the machinery, and Section 5.2 proves the bound whenever every position-group of the pair carries one of three certificates: comparisons pointing one way, values retained in the answer, or a private column whose interval set-equivalence pins. Section 5.3 adds a fourth, values determined by keys. The one configuration with no certificate—a two-sided comparison on a projected-away value entangled with counted ones—is the case we leave open (Remark 22).

5.1

Slots, placements, and homomorphisms

Let C = {c1 < · · · < ck } collect the constants of both Q and Q′ . The constants cut Q into the slots: the k singleton sets {ci } and the k + 1 open intervals between consecutive constants, from (−∞, c1 ) to (ck , ∞). We write S for the set of slots.

11

12

Equivalence of Queries Mixing Set and Bag Semantics

An order atom y ρ c holds or fails for a value depending only on which slot the value lies in, since its threshold c is a slot boundary. The region Ry ⊆ S collects the slots on which every order atom on y holds, with Ry = S when y is unconstrained. Throughout, we assume that no region Ry is the single slot {c} of a constant, as an equality y = c forces. Such a y takes the value c in every satisfying assignment, so replacing y by c, and dropping it from M when it is there, preserves every answer. Every region then contains at least one open slot. Call y simple if Ry is a single open half-line (one strict comparison) or all of S (unconstrained), and composite otherwise. For a simple y with an upper bound, we write ub(y) = min{c : (y < c) ∈ Q}, dually lb(y), and call the slot just below ub(y), or just above lb(y), the tight slot of y. Placed canonical family. Fix a placement π assigning each variable a slot π(y) ∈ Ry , ⃗ = (N1 , . . . , Nm ) ∈ Nm , one per multiset variable (m = |M |). The placed and block sizes N + π family DN⃗ [Q] repeats the blow-up of Section 3, drawing every fresh value from the slot π dictates: the distinguished and set variables receive fixed fresh values inside their slots, and the j-th multiset variable a block of Nj fresh values inside the open interval π(Yj ), all values pairwise distinct and avoiding C. (A variable placed in a singleton slot {c} takes the value c ⃗ , and multQ (D, ā) denotes and carries no block.) The head image ā is the same for every N the multiplicity of ā in Q(D), abbreviated multQ (D) when the answer is that head image. Two observations drive everything below. Order-invariance: as a relational structure, π DN ⃗ [RQ ] of Section 3, since the two differ only in the numeric ⃗ [Q] is the canonical family DN values of the fresh constants, which a relational query cannot see. All-or-none: every threshold of Q′ lies in C, a slot boundary, so it never falls inside a block. Each block therefore lies entirely inside or entirely outside any region Ry′ , and likewise each fixed value. So on π ′ ′ DN ⃗ [Q] the multiplicity of Q equals that of its relational part RQ restricted to assignments sending each variable into a block or value whose slot lies in that variable’s Q′ -region, and π ⃗ multQ′ (DN ⃗ [Q]) is an integer polynomial in N . ′ A multiset-homomorphism µ : Q → Q respects regions when Rµ(y′ ) ⊆ Ry′ for every y ′ sent to a variable, and {c} ∈ Ry′ for every y ′ sent to a constant c. ▶ Lemma 17 (Soundness). If there are region-respecting multiset-homomorphisms Q′ → Q and Q → Q′ , then Q ≡ Q′ . Soundness needs no restriction on regions or variables: composing assignments with a region-respecting homomorphism preserves the comparisons, so each direction bounds one multiplicity by the other. The converse is the subject of the next subsection.

5.2

The Certified Bound

Comparisons on columns that never meet cannot interfere. To make this precise, form the position graph on the variables of Q and Q′ together, joining two variables with an edge whenever they occupy a common position, the same argument slot of the same predicate, in a relational atom of either query. Its connected components are the position-groups. Homomorphisms respect groups, since a containment map sends each p-atom to a p-atom position-wise, so each variable goes to a constant or to a variable of its own group. Say a position-group is directed if every comparison on its variables is strict and all point the same way, all upper or all lower. Different groups may point differently. Call a variable retained if it is distinguished or multiset, and a group retained if all its variables are. Call a group isolated if it is {y, y ′ } with y from Q and y ′ from Q′ , and no constant occurs at a position they occupy. Being a group of two already keeps every other variable out of those

S. Cohen

positions, and excluding constants leaves a homomorphism in either direction no image for y ′ but y, and none for y but y ′ , whether the variables are multiset or existential. Finally, call a constant c boundary-free if it occurs in Q, Q′ only in weak comparisons on existential variables, never in a strict comparison, never constraining an (X ∪ M )-variable, never inside a relational atom. ▶ Theorem 18 (Certified comparison bound). Let Q, Q′ be queries with var-const comparisons such that, after replacing the weak comparisons at boundary-free constants by their strict forms, every position-group of the pair is directed, retained, or isolated. If Q ̸≡ Q′ , they differ on an ordered database of at most 2w |Q| atoms. The proof handles each group by its certificate. We present the three mechanisms in turn, each with a small example that calls for it. Directed groups. A single one-directional comparison has a tight slot, and blocks want to sit in it. For y < 5 against y ′ < 3, a block just below 5 lands in (3, 5), which the lower threshold cannot follow. In general, place every variable of a directed group in its tight slot. By all-or-none and Proposition 5, the coefficient of the characteristic monomial in π ′ multQ′ (DN ⃗ [Q]) then counts exactly the region-respecting homomorphisms Q → Q, since a tight slot lands inside a region of the same direction precisely when the regions are contained. Comparing this count with the same count for Q itself yields a characterization. Say Q, Q′ are simple if every position-group of the pair is directed. ▶ Corollary 19 (Criterion for simple pairs). Let Q, Q′ be simple. Then Q ≡ Q′ if and only if there are region-respecting multiset-homomorphisms Q′ → Q and Q → Q′ . Retained groups. A two-sided comparison has no tight slot. For 2 < y < 8 against 2 < y ′ < 5, a counted value may sit in (2, 5), which Q′ can follow, or in (5, 8), which it cannot, so no placement suffices. We split the range at its interior constant 5 and treat each slot on its own. The split counts correctly only when the compared value is retained, its slot then determined by the answer, so answers from different slots are never merged. For a query P , standing for either of Q and Q′ , a resolution σ picks one slot σ(y) ∈ Ry for every variable y of every retained group that is not directed. The reduct Pσ confines each such y to σ(y): when σ(y) is an open slot, by the two comparisons cutting it out, and when σ(y) = {c}, by replacing y with c outright, so that no variable is frozen at a constant. A satisfying assignment of P places each resolved variable in exactly one slot, and the resolved variables are retained, so an assignment’s (X ∪ M )-image contributes to exactly one P reduct. Hence multP (D, ā) = σ multPσ (D, ā) for every D and ā. Every group of a reduct is directed or pinned to a single open slot, and the exact-placement count extends to the pinned groups. The proof of Theorem 18 orders the reducts of both queries by the existence of region-respecting homomorphisms and reads a maximal class off its own placed family. Weak comparisons are the smallest instance: y ≤ c resolves into the strict y < c and the boundary y = c, so the single-atom database {r(0, 5)} separates the counted z ≤ 5 from the counted y < 5 over r(x, ·). When every group is directed or retained, Q ≡ Q′ holds exactly when Q and Q′ carry the same multiset of reducts, up to equivalence. That criterion is no short certificate, the resolutions numbering the product of the region sizes, so no counterpart of Corollary 16 accompanies Theorem 18. Isolated groups. When the compared value is projected away, splitting over-counts: the value is not part of the answer. Yet a range on such a column can still be harmless. Consider SELECT D.x FROM (SELECT DISTINCT r.x, r.z FROM r WHERE r.y > 2

13

14

Equivalence of Queries Mixing Set and Bag Semantics

AND r.y < 8) D. The column r.y is existential and its comparison is two-sided, so neither mechanism above applies. But r.y occurs nowhere else: if a second query filtered it by a different range, a row with a value in the gap between the ranges would break set-equivalence, which thus pins the range even though r.y is projected away. ▶ Lemma 20 (Region pinning). Let y be isolated, paired with y ′ , confined to Ry and Ry′ . Under the standing set-equivalence assumption Ry = Ry′ . The proof freezes Q with y placed in a slot of Ry \ Ry′ and derives a contradiction with set-equivalence. Once the regions match, the comparisons are inert. Place both variables of an isolated group in an open slot of the common region. By all-or-none, every comparison accepts the placed block or value as a whole, and a homomorphism maps the pair to each other, the only images available. An isolated group therefore never disturbs the count. When every comparison sits on an isolated variable, the comparisons drop out of the criterion altogether. ▶ Corollary 21 (Criterion for isolated pairs). Suppose every comparison of Q, Q′ is a var-const atom on an isolated variable, of either kind and of any shape. Then Q ≡ Q′ if and only if their relational parts are multiset-homomorphic. Boundary-free constants. Last, the strictification in the theorem. Suppose a query filters an existential column by z ≤ 9, and the constant 9 appears nowhere else in either query. No answer changes when every occurrence of the value 9 in a database is lowered slightly, so counter-examples may avoid the value 9, and on such databases z ≤ 9 acts as the strict z < 9. Weak comparisons at boundary-free constants may therefore be made strict before the certificates are checked. ▶ Remark 22 (The frontier). What is left is a position-group with no certificate: a composite comparison on an existential variable that is neither isolated nor at a boundary-free constant. Then splitting over-counts and set-equivalence no longer pins the region. For instance, take Q(x) ← r(x, y), r(x, u), 0 < y < 1, 0 < u < 2, {y} and Q′ (x) ← r(x, y ′ ), r(x, u′ ), 0 < y ′ < 2, 0 < u′ < 1, {y ′ }, with u, u′ existential. The queries are set-equivalent. Each states that some r(x, ·) value lies in (0, 1). Yet the regions of the multiset variables differ, (0, 1) ̸= (0, 2), and the queries are inequivalent: on {r(0, 12 ), r(0, 32 )} they return multiplicities 1 and 2. The counter-example is small, but none of our arguments delivers it. This case, together with variable-versus-variable comparisons on variables that keys do not pin, where a block can be split from inside and all-or-none fails outright, is left to future work.

5.3

Comparisons on key-determined variables

The results so far leave two cases out of reach: a composite comparison on a variable that both blows up and shares its group (Remark 22), and any comparison between two variables. Both become free when the compared variables are pinned by keys, so their values are determined by the answer and cannot blow up. This is the ubiquitous SQL pattern of filtering on attributes fixed by keys, as in selecting the line items sold below list price: I.price < P.list relates two values fixed by the keys of the output row and only decides which rows appear. We work over a schema with declared keys and, following the standing set-equivalence assumption, take Q, Q′ set-equivalent over legal databases. Call a variable key-anchored if it is X-determined, lying in the closure X + of the distinguished variables under the key dependencies of Q (Section 4), and a comparison atom, var-const or var-var, pinned if every variable it mentions is key-anchored. Write Q0 for

S. Cohen

Q with all comparison atoms deleted. Without declared keys X + = X, so pinned means on distinguished variables. A declared key enlarges X + to any attribute reached from the output through key lookups. Two facts make pinned comparisons free. First, a pinned comparison is a support gate: on a legal ordered database, any two satisfying assignments of Q0 producing the answer ā agree on every key-anchored variable, so multQ (D, ā) equals multQ0 (D, ā) when the values forced by ā satisfy every comparison, and 0 otherwise. Second, a comparison-free query is order-blind: an injection σ of values fixing the constants of P has multP (σD, σā) = multP (D, ā), and σD is legal whenever D is. ▶ Theorem 23 (Pinned comparison bound). Let Q, Q′ be set-equivalent over legal databases, with every comparison atom, var-const or var-var, pinned, and let their comparison-free bodies Q0 , Q′0 , obtained by deleting all comparison atoms, be key-anchorable. If Q ̸≡ Q′ , they differ on a legal ordered database of at most 2kw |Q| atoms. The proof uses the support gate to reduce inequivalence to the comparison-free bodies, applies Theorem 13 to them, and reorders the witness’s values by an injection so that the pinned comparisons hold, which order-blindness allows.

6

Related Work

Equivalence characterizations. Equivalence of conjunctive queries under set semantics is characterized by containment mappings [3], under bag and bag-set semantics by isomorphism of the queries [4], and with comparisons via linearizations [15, 19, 11]. Cohen introduced combined semantics, subsuming set, bag, and bag-set semantics, and characterized equivalence for several classes—including relational queries—by multiset-homomorphisms [9, 10], the characterization our bound rests on (Theorem 4). Chirkova extended the study to copy-sensitive queries over bag-valued relations, characterized by covering mappings on an explicit-wave subclass with piecewise-polynomial multiplicity functions [5, 7, 6]. Bag-containment remains an open problem [16]. Equivalence under integrity constraints is classically handled by chasing the constraints into the queries [1], as our foreign-key analysis does. Practical equivalence checkers. Recent systems check SQL equivalence with solvers, in the two one-sided families of Section 1. Cosette pairs counter-example search with a proof-assistant backend [8]. EQUITAS translates queries to first-order formulas discharged by an SMT solver [22]. SQLSolver reduces the unbounded summations of bag semantics to linear integer arithmetic [12]. QED decides a substantial fragment via Q-expressions [20]. Each certifies equivalence on its own fragment. Only Cosette emits counter-examples. On the refuting side, VeriEQL encodes all databases with at most n tuples per relation as an SMT formula, escalating n, and leads the field in integrity-constraint support [13]. Polygon fixes n and searches under-approximations of operator behaviour exhaustively, so an empty-handed search is definitive relative to the bound [21]. SpotIt turns the machinery into a correctness oracle for text-to-SQL benchmarks [14]. No completeness threshold was known for any of them. Ours supply it for the fragment covered here.

7

Conclusion

We proved computable counter-example bounds for the equivalence of conjunctive queries under combined semantics: 2w |Q| over unconstrained set databases, 2kw |Q| under declared keys, unchanged under acyclic foreign keys, and 2w |Q| again for several comparison classes

15

16

Equivalence of Queries Mixing Set and Bag Semantics

previously lacking any equivalence characterization. Up to these thresholds, bounded search becomes a terminating, complete proof method. Three problems remain open. First, the keyed bound requires key-anchorability, leaving open the queries in which demotion strands a multiset variable off every key. Second, the comparison frontier: a two-sided comparison on a projected-away value neither isolated nor key-determined, and var-var comparisons not pinned by keys. Third, tightness: the corner {1, 2}m cannot be relaxed, yet on the pair forcing it the size bound is loose. We know no family forcing size 2Ω(w) , and whether the true threshold is polynomial in the query is open. Beyond these, extending the bounds to bag-valued stored relations [5, 7] and to further query classes, aggregation foremost, is a natural next step. References 1 2 3

4

5

6

7

8

9

10

11 12

Alfred V. Aho, Yehoshua Sagiv, and Jeffrey D. Ullman. Equivalences among relational expressions. SIAM Journal on Computing, 8(2):218–246, 1979. doi:10.1137/0208017. Noga Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing, 8(1– 2):7–29, 1999. doi:10.1017/S0963548398003411. 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, STOC ’77, page 77–90, New York, NY, USA, 1977. Association for Computing Machinery. doi:10.1145/800105.803397. 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, PODS ’93, page 59–70, New York, NY, USA, 1993. Association for Computing Machinery. doi:10.1145/153850.153856. Rada Chirkova. Equivalence and minimization of conjunctive queries under combined semantics. In Proceedings of the 15th International Conference on Database Theory, ICDT ’12, page 262–273, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145/ 2274576.2274604. Rada Chirkova. Combined-semantics equivalence and minimization of conjunctive queries. Comput. J., 57(5):775–795, 2014. URL: https://doi.org/10.1093/comjnl/bxt032, doi: 10.1093/COMJNL/BXT032. Rada Chirkova. Combined-semantics equivalence of conjunctive queries: Decidability and tractability results. Journal of Computer and System Sciences, 82(3):395–465, 2016. URL: https://www.sciencedirect.com/science/article/pii/S0022000015001129, doi:10.1016/j.jcss.2015.11.001. Shumo Chu, Chenglong Wang, Konstantin Weitz, and Alvin Cheung. Cosette: An automated prover for SQL. In 8th Biennial Conference on Innovative Data Systems Research (CIDR), 2017. Sara Cohen. Equivalence of queries combining set and bag-set semantics. In Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’06, pages 70–79, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1142351.1142362. Sara Cohen. Equivalence of queries that are sensitive to multiplicities. VLDB J., 18(3):765–785, 2009. URL: https://doi.org/10.1007/s00778-008-0122-1, doi:10.1007/ S00778-008-0122-1. Sara Cohen, Werner Nutt, and Yehoshua Sagiv. Deciding equivalences among conjunctive aggregate queries. J. ACM, 54(2):5–es, April 2007. doi:10.1145/1219092.1219093. 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.

S. Cohen

13

14

15 16

17

18 19

20 21

22

Yang He, Pinhan Zhao, Xinyu Wang, and Yuepeng Wang. VeriEQL: Bounded equivalence verification for complex SQL queries with integrity constraints. Proc. ACM Program. Lang., 8(OOPSLA1):132:1–132:29, 2024. doi:10.1145/3649849. 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, 35(1):146– 160, 1988. doi:10.1145/42267.42273. Jerzy Marcinkowski and Piotr Ostropolski-Nalewaja. Bag semantics query containment: The CQ vs. UCQ case and other stories. Proceedings of the ACM on Management of Data, 3(5):275:1–275:24, 2025. doi:10.1145/3767711. 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. Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press, 1988. Ron van der Meyden. The complexity of querying indefinite data about linearly ordered domains. Journal of Computer and System Sciences, 54(1):113–135, 1997. doi:10.1006/jcss. 1997.1455. Shuxian Wang, Sicheng Pan, and Alvin Cheung. QED: A powerful query equivalence decider for SQL. Proc. VLDB Endow., 17(11):3602–3614, 2024. doi:10.14778/3681954.3682024. 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. Qi Zhou, Joy Arulraj, Shamkant B. Navathe, William Harris, and Dong Xu. Automated verification of query equivalence using satisfiability modulo theories. Proc. VLDB Endow., 12(11):1276–1288, 2019. doi:10.14778/3342263.3342267.

17

18

Equivalence of Queries Mixing Set and Bag Semantics

Use of AI Tools We disclose our use of AI tools, following the ACM Policy on Authorship. A general-purpose AI coding assistant, Anthropic’s Claude Code, was used throughout the preparation of this work. Its use went beyond assistance with the writing, so we describe it here in full. The assistant was used in three ways that bear on the results. First, it wrote Python scripts that search for small counter-examples and evaluate candidate queries. We used those scripts to probe conjectures before attempting to prove them, and to look for refutations of statements we suspected were false. No claim in this paper rests on them. The paper reports no experiments, and every statement we kept was proved afterwards. Second, it expanded human-written proof sketches into the full proofs given in the appendices. The proof strategy, the constructions, and the case analyses are ours. Third, it pointed out connections between our setting and existing mathematical tools. At least one such connection is used in the paper, and the result it rests on is cited where it is applied. The authors read and checked every definition, statement, proof, and reference in this paper, and take full responsibility for all of them. AI tools are not authors and made no decision about what this paper claims.

A

Formalization of the Canonical Construction

This appendix makes Sections 3 and 4 self-contained by repeating the key constructions and proofs from [10]. A reader can verify the size, degree, and separation claims on which the counter-example bound rests. Throughout, Q ← L, M is a relational query with m = |M | multiset variables. We assume m ≥ 1. The case M = ∅ is the classical containment-mapping theorem [3] and needs no construction. We name the variables of Q as follows: X1 , . . . , Xl are the head variables, Xl+1 , . . . , Xl+u the nonhead set variables, and Y1 , . . . , Ym the multiset variables. ▶ Definition A.1 (The canonical database family DN⃗ [Q], [10]). Let ν0 be an injection assigning a value to each head variable, each set variable, and each constant of Q, fixed once and for all. It maps each constant to itself, and all other values are fresh, pairwise distinct, and distinct from every constant occurring in Q or Q′ . Write c̄ := ν0 (x̄) for the image of the head, the ⃗ = (N1 , . . . , Nm ) ∈ Nm , distinguished tuple. It is the same in every database below. Given N + construct DN⃗ [Q] as follows. 1. For each j ∈ {1, . . . , m} pick a set Dj of Nj fresh constants, with the Dj pairwise disjoint, disjoint from the range of ν0 , and disjoint from every constant occurring in Q or Q′ . Let D := D1 × · · · × Dm (a single empty tuple if m = 0). 2. For each d¯ = (d1 , . . . , dm ) ∈ D, let νd¯ be the assignment agreeing with ν0 on the head and set variables and on constants, and sending each Yj 7→ dj . 3. Main loop. For each d¯ ∈ D and each subgoal p(s̄) ∈ Q, add the ground atom p(νd¯(s̄)). The database DN⃗ [Q] consists of exactly these atoms (identical atoms merged, so the result is a set). Each tuple d¯ ∈ D gives a satisfying assignment of Q into DN⃗ [Q] taking the head to c̄, so ⃗ . The main loop iterates over the Qm Ni tuples of D and adds c̄ ∈ Q(DN⃗ [Q]) for every N i=1 at most |Q| atoms per tuple. The size of each relation after merging is bounded in Lemma 6. ▶ Example A.2. Take Q(x) ← r(x, y) ∧ s(y, z), {y}, with y the single multiset variable and z a set variable, so m = 1 and |Q| = 2. The fixed values send x 7→ x̂ and z 7→ ẑ (fresh and

S. Cohen

distinct), giving c̄ = (x̂). For a parameter N1 , blow up y over D1 = {a1 , . . . , aN1 }. The main loop then inserts, for each ai , the atoms r(x̂, ai ) and s(ai , ẑ), so D(N1 ) [Q] = { r(x̂, ai ) : 1 ≤ i ≤ N1 } ∪ { s(ai , ẑ) : 1 ≤ i ≤ N1 }, with r and s each of size N1 (2N1 atoms in all). Each ai gives one satisfying assignment with head x̂, taking z = ẑ, and these are all of them. So c̄ has multiplicity N1 , exactly the (Q) characteristic monomial P∗ = N1 . ♢ Fix a relational query R. The construction expresses the multiplicity of c̄ in R(DN⃗ [Q]) ⃗ : write F (R) (N ⃗ ) for the multiplicity of c̄ in the bag R(D ⃗ [Q]), that is, the as a function of N N number of assignments in ΓXR ∪MR (R, DN⃗ [Q]) whose head image is c̄. To describe F (R) , [10] classifies the c̄-producing assignments of R. Each ground atom of DN⃗ [Q] has a unique subgoal of Q as its template, namely its νQ -image. An association records, for one such assignment, the template of each subgoal of R. It also records a signature: for each multiset variable of R, which multiset variable Yi of Q, or which fixed value of ν0 , its image lies under. Now group the c̄-producing assignments by association. Suppose an association’s signature sends the multiset variables of R into domains Di1 , . . . , Dik , with repetition. It is realized by Q exactly j Nij assignments, a monomial. Its total degree is the number of multiset variables of R mapped into blown-up domains, hence at most mR . Distinct associations contribute additively. Thus F (R) is the sum of these monomials. (Q) Among the monomials of F (Q) one is distinguished: the characteristic monomial P∗ = N1 N2 · · · Nm of Q. It has total degree m and contains every parameter N1 , . . . , Nm . The three facts below, the black boxes used in Section 3, summarize what we need of these multiplicity functions. ▶ Proposition A.3 (Multiplicity polynomials and the characteristic monomial; [10], Lemma 5.2 and Thm. 5.3). Let Q, Q′ be relational queries and R any relational query, with the family DN⃗ [Q] built from Q. 1. F (R) is an integer polynomial in N1 , . . . , Nm , and every monomial of it has total degree at most mR = |MR |. (Q) 2. The characteristic monomial P∗ occurs in F (Q) with a positive coefficient. (Q) (Q′ ) 3. P∗ occurs in F if and only if there is a multiset-homomorphism from Q′ to Q. Proof sketch. (1) Each multiset variable of R contributes at most one parameter factor, so every monomial above has total degree at most mR ; integrality and the polynomial form follow from the additive count over associations. (2) The identity assignment of Q places each Yj in its own domain Dj , giving an association with signature (Y1 , . . . , Ym ) that contributes N1 · · · Nm . It is the unique association of degree m using every domain exactly once, so ′ nothing cancels it and its coefficient is positive. (3) A monomial N1 · · · Nm in F (Q ) comes from an association of a special form. Its signature is a bijection from the multiset variables of Q′ onto Y1 , . . . , Ym , and its templates send every subgoal of Q′ to a subgoal of Q. Read as a map on terms, such an association is a multiset-homomorphism from Q′ to Q: it fixes the head and constants, maps atoms to atoms, and is injective on the multiset variables. Conversely, such a homomorphism induces the association, hence the monomial. See [10]. ◀ These facts are what the separation Proposition 5 invokes. With them, the separation argument and the size accounting of Lemma 6 give the bound theorems of Sections 3 and 4 entirely by the (new) reasoning presented there.

19

20

Equivalence of Queries Mixing Set and Bag Semantics

B

Omitted Proofs

B.1

Unconstrained Schemas

▶ Proposition 5 (Characteristic monomial separation). Let Q′ be a relational query with no (Q) multiset-homomorphism from Q′ to Q. Then the characteristic monomial P∗ does not (Q′ ) (Q) (Q′ ) appear in F , so P := F −F is a nonzero polynomial on the family {DN⃗ [Q]} (its characteristic monomial coefficient is positive). If moreover mQ′ ≤ m, then P has total degree at most m. (Q)

′

Proof. By Proposition A.3, P∗ is absent from F (Q ) , as no multiset-homomorphism from Q′ to Q exists, yet present in F (Q) with positive coefficient. Its coefficient in P is therefore ′ positive, so P = ̸ 0. For the degree, F (Q) has total degree m and F (Q ) at most mQ′ ≤ m. ◀ ▶ Lemma 6 (Distinct atoms at a corner). For every ⃗a ∈ {1, 2}m and predicate p, X
size p, D⃗a [Q] ≤ 2w(p) sj(p), hence |D⃗a [Q]| ≤ 2 #M (p(s̄)) ≤ 2w |Q|. p(s̄)∈Q

Proof. The atoms a subgoal p(s̄) contributes depend on the blow-up assignment only through the multiset variables occurring in s̄, the other positions being fixed. Each such variable ranges over ai ≤ 2 values, so the subgoal yields at most 2 #M (p(s̄)) ≤ 2w(p) distinct atoms. Summing over the sj(p) subgoals with predicate p bounds size(p, D⃗a [Q]), and summing over P all subgoals, using p sj(p) = |Q|, bounds the total by 2w |Q|. ◀ ▶ Theorem 7 (Counter-example bound for inequivalence). Let Q and Q′ be relational queries with Q ̸≡ Q′ . Write wp := max(w(Q, p), w(Q′ , p)) and w := maxp wp = max(w(Q), w(Q′ )) for the per-predicate and the overall width of the pair. Then there is a database D with Q(D) ̸= Q′ (D),
|D| ≤ 2w max |Q|, |Q′ |

and

size(p, D) ≤ 2wp max sj(Q, p), sj(Q′ , p) for every p.

In particular, Q ≡b Q′ implies Q ≡ Q′ for b = maxp 2wp max(sj(Q, p), sj(Q′ , p)). Proof. By Theorem 4, some direction admits no multiset-homomorphism. The conclusion is symmetric in Q and Q′ , so we may assume mQ′ ≤ mQ and that no multiset-homomorphism Q′ → Q exists. Indeed, when mQ ̸= mQ′ , put the query with fewer multiset variables as Q′ : the characteristic monomial of Q then has degree mQ , exceeding the degree of every ′ monomial of F (Q ) (Proposition A.3(1)), so no multiset-homomorphism Q′ → Q exists by the criterion (Proposition A.3(3)). When mQ = mQ′ , name the failing direction Q′ → Q. ′ Write m := mQ and P := F (Q) − F (Q ) . The Combinatorial Nullstellensatz [2] states Q P that if P has a nonzero coefficient on a monomial i Niti with i ti = deg P , then for any sets A1 , . . . , Am with |Ai | > ti there is a point ⃗a ∈ A1 × · · · × Am with P (⃗a) ̸= 0. By Proposition 5, the coefficient of N1 · · · Nm in P is nonzero and deg P = m, so this monomial is a top-degree term with every ti = 1. Taking each Ai = {1, 2} yields ⃗a ∈ {1, 2}m with P (⃗a) ̸= 0, so the multiplicity of c̄ differs between Q and Q′ on D := D⃗a [Q]. The size bounds are Lemma 6 at ⃗a, weakened from w(Q, p), sj(Q, p) to the pair-maxima in the statement. The final claim is the contrapositive, as the witness is b-bound. ◀ A variable sitting in an unobserved attribute occurs exactly once, not in the head and in no order atom. An unobserved multiset variable feeds the multiplicity but is otherwise inert, and several in one atom can be merged: k unobserved multiset variables ranging over

S. Cohen

domains D1 , . . . , Dk contribute exactly the multiplicity of a single multiset variable over D1 × · · · × Dk . (For the relational queries of Section 3 the clause about compared variables is vacuous. It is stated so that the notion remains correct once comparisons are present.) The collapse of the pair Q, Q′ rewrites each relation r according to its unobserved attributes. If some atom of r, in Q or Q′ , places a multiset variable in an unobserved position, append one fresh attribute at the end of r and delete the unobserved ones. An atom r(s̄) then becomes r↓ (s̄|obs , z), whose new last position holds a fresh multiset variable z when s̄ had a multiset variable in an unobserved position, and a fresh set variable otherwise. If no atom of r places a multiset variable in an unobserved position, r is left unchanged. The unobserved attributes are common to Q and Q′ , so the same rewriting applies to both, yielding Q↓ and Q′↓ over a shared schema. A collapsed atom carries only the join multiset variables of the original, plus at most one new multiset variable, so w(Q↓ ) ≤ w(Q), and clearly |Q↓ | = |Q| and sj(Q↓ ) = sj(Q). The collapse acts on databases by the same merging: D becomes D↓ by sending each ground atom r(c̄) of a rewritten relation to r↓ (c̄|obs , ⟨c̄|unobs ⟩), the new attribute recording the whole tuple of merged values. This map is a bijection on databases and preserves every relation’s size. ▶ Lemma 9 (Collapse preserves equivalence). Q ≡ Q′ if and only if Q↓ ≡ Q′↓ . Proof. The collapse preserves every answer multiplicity. A multiset variable in an unobserved position contributed a factor equal to its domain size, and the new variable z, ranging over the product of those domains, reproduces exactly that factor, while set variables there contribute nothing. So Q(D) = Q↓ (D↓ ) for every D, and likewise for Q′ , which with the bijection D 7→ D↓ gives the claim. (An unobserved attribute holding a constant is simply retained. It contributes nothing to the width.) ◀ Under declared keys the collapse requires one adjustment: the schema surgery must merge a relation’s unobserved key attributes separately from its unobserved non-key attributes, so that the key is preserved and the bijection maps legal databases to legal databases. Merging unobserved key attributes then lowers the key-width, replacing kw in Theorem 13 by its collapsed counterpart.

B.2

Constrained Schemas

The surviving multiset variables of a run of demotions form a basis of M under the closure T 7→ (X ∪ T )+ , and because functional-dependency closures need not obey the matroid exchange axiom, bases are not unique and may differ in size. One might hope that the dependencies induced by primary keys are better behaved than general functional dependencies. They are not. Take the atoms p(a, b), q(a, c) of key {1} and r(b, c, a) of key {1, 2}, with M = {a, b, c} and X = ∅. The induced dependencies are purely key-driven, a → b, a → c, and {b, c} → a, and the last two make a and {b, c} two candidate keys for the same information: a determines {b, c} and {b, c} determines a. Demoting b then c leaves the basis {a}, whereas demoting a leaves {b, c}—bases of different size, and even of different key-width (1 versus 2). One might expect order-irrelevance once every dependency is a key. It fails, and the culprit is precisely the cyclic mutual determination a ↔ {b, c}, the same cyclic-key phenomenon as in Example 12. With acyclic key dependencies the basis is unique. The order affects how tight the witness is, as a smaller basis lowers the effective exponent. It never affects whether the reduct is key-anchored: the statically anchored variables are never demotable and survive every run, so by Proposition B.3 anchoredness is the order-independent condition M ⊆ (X ∪ A)+ , and when it holds every order reaches the same anchored reduct A.

21

22

Equivalence of Queries Mixing Set and Bag Semantics

▶ Lemma 11 (Demotion). Let X be the distinguished variables of Q and let v ∈ M be (X ∪ (M \ {v}))-determined. Let Q−v be Q with v moved from M to the set variables. Then Q ≡ Q−v and kw(Q−v ) ≤ kw(Q). Proof. On a legal database D the key dependencies hold, so in every satisfying assignment γ the value γ(v) is determined by the restriction of γ to X ∪ (M \ {v}). Hence the map ΓX∪M (Q, D) → ΓX∪(M \{v}) (Q, D) that forgets v is a bijection, and the answer multisets coincide on every legal D. Moving v out of M cannot raise the number of multiset variables in any key position. ◀ Recall that a query R is key-anchored if every multiset variable of R occurs, in every atom of R containing it, at a key position of that atom. The key-chase of R repeatedly unifies the terms of two atoms p(s̄), p(t̄) of the same predicate that agree on key(p) (an equality-generating chase under the key dependencies) and merges duplicates. It terminates, preserves ≡, and leaves distinct atoms of each predicate with distinct key-term tuples. ▶ Lemma B.1 (Legality of the canonical family, anchored case). If R is key-chased and key-anchored, then D⃗a [R] is legal for every corner ⃗a ∈ {1, 2}m . Proof of Lemma B.1. Let p(ū), p(v̄) ∈ D⃗a [R] agree on key(p). They arise from subgoals p(s̄), p(s̄′ ) and assignments νt , νt′ (t, t′ ∈ S), with ū = νt (s̄) and v̄ = νt′ (s̄′ ). Recall from Appendix A that ν0 is injective on the set/distinguished variables and constants, and the multiset domains Sj are pairwise disjoint and disjoint from range(ν0 ). Hence two terms receive equal values under the ν’s iff they are the same variable or the same constant. Same subgoal (s̄ = s̄′ ). For each i ∈ key(p), νt (si ) = νt′ (si ). At a fixed term this is automatic, and at a multiset variable y it forces t, t′ to agree on the coordinate of y. By key-anchoredness every multiset variable of s̄ occurs at some key position, so t, t′ agree on all multiset variables of s̄. The other terms being fixed, νt (s̄) = νt′ (s̄), i.e. ū = v̄. Different subgoals (s̄ = ̸ s̄′ ). After the key-chase the key-term tuples s̄|key(p) and s̄′ |key(p) are distinct, hence differ at some key position i where si , s′i are different variables, different constants, or a variable and a constant. In every case νt (si ) ̸= νt′ (s′i ) by the disjointness above, so ū, v̄ disagree on key(p), a contradiction. Thus atoms agreeing on the key are equal, and D⃗a [R] is legal. ◀ ▶ Lemma B.2 (Distinct legal atoms at a corner). Let D be any legal database all of whose atoms arise, as in D⃗a [·], by assigning each multiset variable one of at most two values. Then for every predicate p, size(p, D) ≤ 2kw(p) sj(p),

hence

|D| ≤ 2kw |Q|.

Proof of Lemma B.2. By legality, distinct atoms of p differ on key(p). A key position holds either a fixed term or a multiset variable with at most two values, so a subgoal with predicate p admits at most 2kw(p) distinct key projections, hence at most that many distinct atoms. Summing over subgoals as in Lemma 6 gives both bounds. ◀ ▶ Proposition B.3 (When an anchored reduct exists). Let A be the set of multiset variables of Q that occur only at key positions (the statically anchored variables). Every variable in A belongs to every key-reduct of Q, and the following are equivalent: 1. some key-reduct of Q is key-anchored, 2. every key-reduct of Q is key-anchored, 3. every multiset variable of Q is (X ∪ A)-determined, that is M ⊆ (X ∪ A)+ .

S. Cohen

23

When these hold, A is the unique key-reduct, reached by every demotion order. The condition holds in particular when no multiset variable occurs off a key (then A = M ), but it is strictly weaker: it asks only that the anchored variables determine the rest. Proof of Proposition B.3. A statically anchored v never occupies a non-key position, so it appears in a key dependency only within the left-hand (key) side. Hence v ∈ (X ∪ T )+ implies v ∈ X ∪ T , so v is never demotable and lies in every reduct. (3) ⇒ (2): assume M ⊆ (X ∪ A)+ and let F be any reduct and u ∈ / A a non-anchored multiset variable. As A ⊆ F for the reason just given, A ⊆ F \ {u}, whence u ∈ M ⊆ (X ∪ A)+ ⊆ (X ∪ (F \ {u}))+ . In a reduct no surviving multiset variable is determined by the others, so u ∈ / F . Hence no non-anchored variable survives, F = A, and A is key-anchored. (2) ⇒ (1) is immediate. (1) ⇒ (3): a reduct F generates M , i.e. M ⊆ (X ∪ F )+ . If F is key-anchored then F ⊆ A, so M ⊆ (X ∪ A)+ . ◀ ▶ Proposition 14 (Well-formed queries with acyclic key references). Let Q be a well-formed query, over a schema with declared keys, such that 1. every occurrence of a multiset variable at a non-key position lies in a counting atom, and 2. the references among the counting atoms of Q are acyclic. Then M ⊆ (X ∪ A)+ , that is, Q is key-anchorable. Proof. Let G be the digraph on the counting atoms of Q whose edges c → b are the references: some multiset variable at a key position of b occurs at a non-key position of c. By assumption G is acyclic. For a counting atom b, let h(b) be the length of the longest directed path in G ending at b. We show by induction on h(b) that every variable at a key position of b lies in (X ∪A)+ . Let v be such a variable. A counting atom has no set variables, and constants and distinguished variables are immediate, so assume v ∈ M . If no occurrence of v in Q sits at a non-key position, then v ∈ A. Otherwise some occurrence of v sits at a non-key position, and by the first requirement it sits in a counting atom c. Then c → b is an edge of G, so h(c) < h(b). In particular this case cannot occur when h(b) = 0. By induction every key variable of c lies in (X ∪ A)+ , and the key of c determines its remaining positions, so v ∈ (X ∪ A)+ . Now let x ∈ M . By well-formedness x occurs in some counting atom b. Every key variable of b lies in (X ∪ A)+ , and the key of b determines all its positions, so x ∈ (X ∪ A)+ . Hence M ⊆ (X ∪ A)+ , and Proposition B.3 makes every key-reduct of Q key-anchored. ◀ ▶ Theorem 13 (Equivalence and counter-examples under declared keys). Let Q, Q′ be keyanchorable relational queries over a schema with declared keys and no foreign keys, and write Q♮ for the key-chase of the key-reduct of Q. Put kw := max(kw(Q♮ ), kw(Q′♮ )) and kw(p) := max(kw(Q♮ , p), kw(Q′♮ , p)), both at most the same quantities for Q and Q′ . Then 1. Q ≡ Q′ over legal databases if and only if Q♮ and Q′♮ are multiset-homomorphic, and 2. if Q ̸≡ Q′ , there is a legal database D with Q(D) ̸= Q′ (D), |D| ≤ 2kw max(|Q♮ |, |Q′♮ |)

and

size(p, D) ≤ 2kw(p) max(sj(Q♮ , p), sj(Q′♮ , p))

for every predicate p. In particular Q ≡b Q′ implies Q ≡ Q′ for b = maxp 2kw(p) max(sj(Q♮ , p), sj(Q′♮ , p)). Proof. Write Q♮ for the key-chase of the key-reduct Q♭ , and likewise for Q′ . By Lemma 11 and the key-chase, Q ≡ Q♮ and Q′ ≡ Q′♮ over legal databases. Chasing after demoting is sound: the key-chase unifies only terms at non-key positions, since the two atoms already agree on the key, while under key-anchorability the surviving multiset variables are those of

24

Equivalence of Queries Mixing Set and Bag Semantics

A, which occupy key positions only (Proposition B.3). So Q♮ is key-chased and key-anchored, and no merge raises kw. Clause (1), sufficiency. If Q♮ and Q′♮ are multiset-homomorphic they are equivalent over all databases by Theorem 4, hence over the legal ones, and Q ≡ Q′ follows. Clause (1), necessity, and clause (2). Suppose no multiset-homomorphism exists in some direction. As in the proof of Theorem 7 the queries may be named so that the failing direction is Q′♮ → Q♮ with mQ′♮ ≤ mQ♮ . By Proposition 5 and the Boolean-corner extraction of Theorem 7 the two multiplicity functions differ at some corner ⃗a ∈ {1, 2}m of D⃗a [Q♮ ], which is legal by Lemma B.1. Hence Q ̸≡ Q′ over legal databases, which is the contrapositive of necessity, and the separating database is legal. Its size obeys Lemma B.2, with the relevant key-width for predicate p at most kw(p), giving clause (2). ◀ Foreign keys. Formally, the foreign-key chase chase fk (Q) repeatedly picks a foreign key (p, ı̄, q) and an atom p(s̄) ∈ Q with no atom q(t̄) ∈ Q satisfying s̄|ı̄ = t̄|key(q) , and adds a fresh atom q(t̄) whose key positions copy s̄|ı̄ and whose remaining positions are pairwise fresh set variables. ▶ Lemma B.4 (Foreign-key chase). For acyclic foreign keys, chase fk (Q) terminates and 1. every atom it adds has fresh set variables in all non-key positions, so M is unchanged and w(chase fk (Q)) = w(Q), kw(chase fk (Q)) = kw(Q). 2. for every database D satisfying the keys and foreign keys, Q(D) = chase fk (Q)(D). Proof sketch. Termination is the standard acyclic-inclusion-dependency argument: each added atom belongs to a target relation strictly lower in the (acyclic) reference order, so no chain of additions is longer than the schema’s reference depth. The added positions are fresh existential variables, hence set variables, so no multiset variable and no key occurrence is created, giving (1). For (2), on a database satisfying the foreign keys the witness atom required by each added subgoal already exists, so the added subgoals are redundant and the satisfying assignments—hence the answer multisets—coincide. ◀ ▶ Theorem 15 (Counter-example bound under keys and acyclic foreign keys). Let Q, Q′ be b Q c′ are relational queries over a schema with keys and acyclic foreign keys, such that Q, ′ b Q c : equivalence over legal key-anchorable. Then both clauses of Theorem 13 hold for Q, ♮ ♮ ′ b c databases is multiset-homomorphism of Q and Q , and inequivalent Q, Q′ are separated by b |Q c′ |) atoms. The query size |Q| b is at most |Q| a legal database with at most 2kw max(|Q|, times the reference depth of the schema. b Q c′ over Proof. By Lemma B.4(2), inequivalence over legal databases is inequivalence of Q, the databases satisfying the keys alone, to which Theorem 13 applies. The witness it returns satisfies the keys, and—because the chase made every referenced atom explicit—is closed under the foreign keys without new multiset structure, keeping the size bound. The key-width and the anchoring requirement are preserved by Lemma B.4(1), whose added atoms place only fresh set variables in non-key positions. ◀ ▶ Corollary 16 (Complexity of equivalence under constraints). Deciding Q ≡ Q′ over a schema with declared keys and acyclic foreign keys is NP-complete for queries whose foreign-key chases are key-anchorable. ♮

b ♮ and Q c′ in both directions Proof. Membership. Guess mappings between the terms of Q and check conditions (1)–(4) of Section 3, all by inspection of the atoms. By clause (1) of Theorem 13, applied to the chased queries as in Theorem 15, such mappings exist exactly

S. Cohen

when Q ≡ Q′ . The certificate is polynomial, and so is its subject: the foreign-key chase adds at most one atom per atom and per declared foreign key, and terminates within the reference depth of the schema (Lemma B.4); the key-reduct is the set A of statically anchored variables, a closure under the key dependencies (Proposition B.3); and the key-chase merges two classes of terms per step, so at most |Q| times the maximum arity steps occur. Hardness. Let Q, Q′ have M = M ′ = ∅ over the schema whose every key is the whole tuple, where every database is legal and every query is key-anchorable. Exactly one assignment of X ∪ M produces each answer, so Q(D) is the set that Q returns under set semantics, and Q ≡ Q′ is equivalence of conjunctive queries, which is NP-hard [3]. ◀

B.3

Queries with Comparisons

▶ Lemma 17 (Soundness). If there are region-respecting multiset-homomorphisms Q′ → Q and Q → Q′ , then Q ≡ Q′ . Proof. Suppose µ : Q′ → Q respects regions. As in Section 3, µ injects the Q-assignments producing ā into the Q′ -assignments producing ā through γ 7→ γ ◦ µ, and respecting regions makes this preserve the comparisons: a satisfying γ of Q puts γ(µy ′ ) in Rµ(y′ ) ⊆ Ry′ when µ(y ′ ) is a variable, and on a constant of Ry′ otherwise. Hence multQ ≤ multQ′ pointwise, and maps in both directions give equality. ◀ ▶ Lemma 20 (Region pinning). Let y be isolated, paired with y ′ , confined to Ry and Ry′ . Under the standing set-equivalence assumption Ry = Ry′ . Proof. Suppose not, say some slot lies in Ry \ Ry′ , and pick a value v in it, off C. Let D be the canonical database of RQ , freezing the variables of Q to distinct fresh values off C, each inside its own region, with y 7→ v. This is possible by density, the regions being nonempty. Then D has at most |Q| atoms, and the freezing satisfies Q, so its head ā lies in Q(D). By set-equivalence ā ∈ Q′ (D), witnessed by an assignment δ of Q′ into D that meets every var-const atom of Q′ . As the freezing is injective and the atoms of D are its images of the atoms of RQ , δ factors as (freezing) ◦ h for a containment map h : Q′ → Q. Because homomorphisms respect groups, h(y ′ ) is a constant or a variable of y ′ ’s group. That group is {y, y ′ }, whose sole Q-variable is y, and the shared position holds no constant. So h(y ′ ) = y and δ(y ′ ) = v, forcing v ∈ Ry′ against the choice of v. Hence Ry ⊆ Ry′ , and by symmetry Ry = Ry′ . ◀ ▶ Theorem 18 (Certified comparison bound). Let Q, Q′ be queries with var-const comparisons such that, after replacing the weak comparisons at boundary-free constants by their strict forms, every position-group of the pair is directed, retained, or isolated. If Q ̸≡ Q′ , they differ on an ordered database of at most 2w |Q| atoms. Proof. Strictification. Let c be boundary-free and D any ordered database. Choose a fresh value c− strictly between c and the next lower constant of C \ {c}, off adom(D), and let D− rename every occurrence of the value c to c− . Queries compare values only to constants, and c− lies in the same gap of C \ {c} as c, so the renaming preserves every value’s order relation to every constant the queries mention, and preserves z ≤ c, now met by c− < c. As c neither is a relational constant nor constrains an (X ∪ M )-variable, it enters an (X ∪ M )-image only through the renaming, applied identically to Q and Q′ . Hence multQ (D) = multQ (D− ), and likewise for Q′ . So counter-examples may avoid the boundary-free values, and on databases avoiding them each weak comparison at such a constant holds iff its strict form does. Every

25

26

Equivalence of Queries Mixing Set and Bag Semantics

database below is built from fresh values off C and avoids these values, so we may assume every position-group of the pair is directed, retained, or isolated. Pinning. For every isolated group {y, y ′ }, Ry = Ry′ by Lemma 20, whose frozen database uses fresh values off C. Resolution. Resolve every retained group that is not directed, as in Section 5.2. The decomposition displayed there gives, for every (D, ā), X X multQ (D, ā) − multQ′ (D, ā) = multQσ (D, ā) − multQ′ ′ (D, ā), σ

σ

σ′

a signed sum over a pool of reducts in which every group is directed, pinned to a single open slot, or isolated with matched regions, and no variable is frozen at a constant. If Q ̸≡ Q′ , the sum is not the zero function. The placement and the count. For reducts P, P ′ of the pool, place P as follows: each variable of a directed group in its tight slot, an unconstrained variable of an upper group above all constants and dually for a lower group; each pinned variable in its slot; each isolated variable in an open slot of the common region, which exists because regions are not single constants (Section 5.1). By order-invariance and all-or-none, the coefficient of (P ) π ′ P∗ in multP ′ (DN ⃗ [P ]) counts the multiset-homomorphisms P → P whose images meet ′ the comparisons of P under this placement (Proposition 5). We claim these are exactly the region-respecting ones. On a directed group, say upper, a variable z sits just below ub(z), so its block or value lies in Ry′ = (−∞, ub(y ′ )) exactly when ub(z) ≤ ub(y ′ ), that is, when Rz ⊆ Ry′ . The uniform direction rules out a spurious match, and a constant image c lies in Ry′ iff {c} ∈ Ry′ . On a pinned group the placed slot is the region of the reduct, so placement-respect and region-respect coincide, and the exclusion of existential variables from pinned groups keeps a pinned slot from matching an image elsewhere. On an isolated group the map is forced, and the placed block or value lies in the counterpart’s region because the regions match, so the group imposes no constraint. The classes. For reducts P, P ′ of the pool write P ⪯ P ′ when there is a region-respecting multiset-homomorphism P → P ′ . It is reflexive and transitive, and P ⪯ P ′ ⪯ P implies P ≡ P ′ by Lemma 17, so ⪯ descends to a partial order on equivalence classes. Collecting reducts by class, write a[P ] ∈ Z for the number of Q-reducts in [P ] minus the number of P Q′ -reducts. The difference above is [P ] a[P ] multP , and as it is not zero, some a[P ] = ̸ 0. Let m be the greatest number of multiset variables among classes with a[P ] ̸= 0, and pick such a class [P ] of degree m that is ⪯-minimal among them. Since equivalent queries (P ) π have equal multiplicity functions, the coefficient of P∗ in multP ′ (DN ⃗ [P ]) is the same for ′ every member P of a class. By the count, it is nonzero only for P ′ with mP ′ ≥ m and P ′ ⪯ P , hence mP ′ = m, so by minimality only [P ] itself contributes, a[P ] times the positive self-homomorphism count. (P ) Extraction. As [P ] has maximal degree, P∗ is a top-degree multilinear monomial of the combination with a nonzero coefficient. By the Boolean-corner extraction of Theorem 7 the ⃗ ∈ {1, 2}m , where multQ ̸= multQ′ . The reduct P has at combination is nonzero at some N most |Q| atoms and width at most w, so its placed family at the corner has at most 2w |Q| atoms. Its values are fresh and off C, so the witness also separates the original, unstrictified pair. ◀ ▶ Corollary 19 (Criterion for simple pairs). Let Q, Q′ be simple. Then Q ≡ Q′ if and only if there are region-respecting multiset-homomorphisms Q′ → Q and Q → Q′ . Proof. If both homomorphisms exist, Q ≡ Q′ by Lemma 17. Conversely let Q ≡ Q′ , so the multiplicity functions agree on the placed family of Q under the tight placement. All

S. Cohen

groups being directed, the count in the proof of Theorem 18 applies with no resolved and (Q) no isolated groups: the coefficient of P∗ in multQ is the number of region-respecting homomorphisms Q → Q, positive by the identity, and in multQ′ it is the number of regionrespecting homomorphisms Q′ → Q. Equality makes the latter positive, so a homomorphism Q′ → Q exists. The symmetric argument on the family of Q′ gives one from Q to Q′ . ◀ ▶ Corollary 21 (Criterion for isolated pairs). Suppose every comparison of Q, Q′ is a var-const atom on an isolated variable, of either kind and of any shape. Then Q ≡ Q′ if and only if their relational parts are multiset-homomorphic. Proof. Suppose the relational parts are multiset-homomorphic. Every comparison sits on an isolated variable, whose image under either homomorphism is its counterpart, with equal regions by Lemma 20, and every other variable is unconstrained. Both homomorphisms therefore respect regions, and Q ≡ Q′ by Lemma 17. Conversely let Q ≡ Q′ , and place each isolated variable in an open slot of the common region. By all-or-none, every comparison of either query accepts each placed block or value whole, so for R ∈ {Q, Q′ } the coefficient of (Q) π P∗ in multR (DN ⃗ [Q]) counts all multiset-homomorphisms of the relational parts RR → RQ . As in the previous proof, equality of the multiplicity functions turns the positive self-count into a multiset-homomorphism RQ′ → RQ , and the symmetric argument on the family of Q′ completes the claim. ◀ ▶ Theorem 23 (Pinned comparison bound). Let Q, Q′ be set-equivalent over legal databases, with every comparison atom, var-const or var-var, pinned, and let their comparison-free bodies Q0 , Q′0 , obtained by deleting all comparison atoms, be key-anchorable. If Q ̸≡ Q′ , they differ on a legal ordered database of at most 2kw |Q| atoms. Proof. By the support gate, multQ = β multQ0 and multQ′ = β ′ multQ′0 , with β, β ′ ∈ {0, 1}. Since Q ̸≡ Q′ , some legal (D0 , ā0 ) has multQ = ̸ multQ′ . Were one zero and the other positive, that answer would lie in one support but not the other, contradicting set-equivalence. So both are positive, whence β = β ′ = 1, multQ0 (ā0 ) ̸= multQ′0 (ā0 ), and the pinned variables’ forced values satisfy every comparison. Identify the pinned variables of Q0 , Q′0 exactly as they coincide at (D0 , ā0 ). The resulting comparison-free bodies still differ, and remain key-anchorable, since adding equalities only enlarges the closures. By the comparison-free bound over legal databases (Theorem 13) they differ on a legal database D1 of at most 2kw |Q| atoms. Its canonical answer assigns distinct variables distinct values, so the pinned values on D1 carry exactly the coincidences we imposed and no others. Some ordering of those values, the one at (D0 , ā0 ), satisfies every comparison, including the atoms relating two pinned variables. So by order-blindness an injection σ fixing the constants reorders the values of D1 to satisfy every comparison atom, changing neither body’s multiplicity nor legality. On σD1 the pinned comparisons hold, so the support gate makes the multiplicities equal to those of the bodies, which differ. This is the required counter-example. ◀

27

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