Computable limits show when sql queries are truly equivalent
Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics
Databases
Summary
Figuring out if two database queries always give the same result is tricky when queries mix counting duplicates and ignoring them. The authors found exact size limits for small example databases you need to check to be sure two queries behave identically. These limits depend on how many columns the queries look at and some database rules called keys. This finding means that testing query equivalence can be automated and will always finish for important types of queries.
What this means in practice
- •For database system developers: Enable automated tools to decide when SQL queries mixing duplicates are equivalent by checking only small example databases.
- •For query optimization engineers: Use guaranteed finite tests to confirm query rewriting correctness that involves duplicates and keys, improving compiler reliability.
A theory result. No direct application yet.
Authors
Sara Cohen
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 $2^w |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 $2^{kw} |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.