CS Paper Radar

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

Helen Sternbach, Sara Cohen

cs.DB ·submitted 2026-09-14 18:50 UTC · v1

Abstract

Query containment and equivalence drive database query optimization and rewriting. For plain conjunctive queries, both are decided by evaluating one query over a single canonical database of the other. This classical test breaks down in two settings that pervade real queries: databases with null values under SQL's three-valued semantics, and queries with order comparisons. In both, deciding containment is $Π_2^p$-complete, and the known characterizations replace it by an exponential family of test databases, leaving no practical route to certifying equivalence. We ask how the family of test databases can be shrunk. For conjunctive queries over databases with nulls, we shrink the family to one that is exponential only in a special set of variables, and place containment in NP when that set has constant size. For queries with comparisons, we construct canonical values that decide containment, and then shrink the family by decomposing the test into independent components and by splitting it along the order conflicts. Finally, we combine the two features, and prove that the number of test databases is fixed-parameter tractable in three local parameters of the two queries, with the null-only and comparison-only tests as special cases. Each test evaluates the containing query over a family of databases, an operation native to any database system.

Comment
42 pages, 4 figures. Full proofs in the appendix

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DB ·2026-09-09 ·Sara Cohen
theory similarity 0.68
Abstract · 27 pages, including 10 pages of appendices; no figures

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.

0.14

Property Testing for Recursive Query Languages

cs.DB cs.LO ·2026-09-03 ·Isolde Adler, Carsten Lutz, Quentin Manière, Marcin Przybyłko, Lukas Schulze
published similarity 0.60
Abstract

In the context of database querying, property testing provides a framework for testing query answers with high confidence while inspecting only a sublinear part of the database, through completion queries and size queries. A fundamental result of Chen and Yoshida (2019) states that non-satisfaction of a Boolean conjunctive query $q$ is testable with a constant number of such queries and one-sided error if and only if $q$ is equivalent to an $α$-acyclic query. In this article, we initiate the study of property testing for recursive query languages, focusing on two-way regular path queries (2RPQs) and monadic Datalog. One of our main results is positive: non-answers to any 2RPQ are constant query testable with one-sided error. We extend this slightly to a certain class of monadic Datalog programs in which recursion is restricted to be linear and rule bodies must be $α$-acyclic. Turning towards unrestricted monadic Datalog, we next show that if a monadic Datalog program $Π$ is not equivalent to an $α$-acyclic program, then falsity of $Π$ is not constant query testable with one-sided error. This is under the assumption that all rule-bodies are self-join free. We leave open the case of monadic Datalog programs with $α$-acyclic rule bodies that are not restricted to linear recursion, but observe as a first step that there exist $α$-acyclic programs that are mildly non-linear and constant query testable with one-sided error.

0.28

Tight Width Minimisation of Self-Join-Free Quantified Conjunctive Queries

cs.DB cs.LO ·2026-11-16 ·Hubie Chen, Fabio Mogavero, Sam M. Thompson
top venue similarity 0.58
Abstract · To appear at PODS 2027

Query minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. We study width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. For this subclass, we show that rewriting optimality coincides with semantic optimality: given a query $φ$, the minimum-width query obtainable from $φ$ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to $φ$. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.

0.27

Attacking Diophantus: Special Cases of Bag Containment

cs.DB ·2026-09-25 ·George Konstantinidis, Xinzhuo Li, Fabio Mogavero
similarity 0.58
Abstract

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

0.09

Size Bounds for CQs Under Acyclic Constraints

cs.DB cs.IT ·2026-08-27 ·Stefan Mengel, Andrei Romashchenko
similarity 0.56
Abstract

We study size bounds for conjunctive query (CQ) results which in recent years have played a crucial role in database theory. In particular, we compare the so-called entropic bound which is known to be asymptotically tight but not known to be computable, and its computable relaxation called the polymatroid bound, which is generally not tight. We focus here on conjunctive queries under acyclic functional dependencies. These queries are known to be well-behaved in the sense that, in the case without projections, both bounds coincide. We show that this picture changes when projections are allowed: in this case, even for acyclic functional dependencies, there is in general a polynomial gap between the two bounds. We complement this negative result by showing a special case for which the polymatroid bound is tight under acyclic functional dependencies and projections that is characterized by the position of the output variables in a topological order of the query variables.

0.20

Testing Implies Distance Estimation with Polynomial Loss

cs.DS math.CO ·2026-11-03 ·Gaia Carenini, Cameron Seth
similarity 0.56
Abstract

A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.

0.27

A Fine-Grained Dichotomy for Bounded-Variable Query Evaluation: The Calculus of Relations, a Boolean Modal Logic, and One-Variable Counting Logic

cs.DB cs.CCcs.LO ·2026-10-03 ·Yoshiki Nakamura, Yuya Uezato
publishedtheory similarity 0.55
Abstract · Long version of PODS'27 paper

We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.

0.29

Building SQL Equivalence Proofs from Query Rewrite Rules

cs.DB ·2026-10-21 ·Chunyu Chen, Xinyi Huang, Zhengjie Miao
benchmark similarity 0.55
Abstract · 6 pages

Query rewriting and semantic evaluation of text-to-SQL systems both depend on deciding whether two SQL queries return the same result on every database satisfying the schema constraints. Decades of equivalence-preserving optimizer rules provide a natural basis for constructive proofs: two queries are equivalent when admitted rewrites transform them to a common logical expression. Building on this observation, \sys{} organizes query-rewriting knowledge as a standalone proof-producing system. It separates rule validation from proof discovery, explicitly aligns alternative query representations, and returns the resulting rewrite derivation. Across three corpus classes, EquiTrace proves 648/1,106 expected-equivalent text-to-SQL pairs (58.6%), 229/266 curated pairs (86.1%), and 97/240 LLM-generated rewrites whose results agree under benchmark execution (40.4%). On the query rewrite corpus, EquiTrace proves 97 pairs, compared with 35 for QED and 38 for SQLSolver. An analysis of 1,242 recorded proofs shows that coverage depends on a small number of transformations, while many frequently used rules are individually substitutable. The resulting derivations make each proof replayable and expose the specific transformations on which it depends.

0.26