CS Paper Radar

Building SQL Equivalence Proofs from Query Rewrite Rules

Chunyu Chen, Xinyi Huang, Zhengjie Miao

cs.DB ·submitted 2026-10-21 17:47 UTC · v1
benchmark

Abstract

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.

Comment
6 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Dialect-Agnostic SQL Equivalence Refutation

cs.DB ·2026-10-15 ·Junwen An, Manuel Rigger
publishedbenchmark similarity 0.68
Abstract

Identifying semantically inequivalent SQL queries is useful for many applications, such as evaluating Text-to-SQL and dialect translation systems. However, existing approaches often struggle with the diversity of SQL features and dialects, requiring significant manual effort and expertise to extend query feature support across Database Management Systems (DBMSs). To address these limitations, we present SQLWitness, an efficient, DBMS-agnostic query equivalence refutation engine. Our core idea is leveraging the DBMS execution engine to determine whether generated instances constitute counterexamples, thereby faithfully capturing the semantics of the SQL dialect and preventing false counterexamples. To efficiently generate test data, our approach explores a constrained data-generation space and uses an integrity-constraint-aware generation strategy. Furthermore, to guide time-efficient termination of this test-data generation process, we pair predicate-coverage signals with a statistical estimator. We extensively evaluated SQLWitness on six benchmark suites across four SQL dialects. SQLWitness refuted 5.34% to 88.4% more pairs than state-of-the-art baselines, and processed query pairs in 0.12 seconds on average, achieving a speedup from 2.1x to 16.4x over the baselines. Furthermore, in a case study, SQLWitness found 8.4% inconsistent translations within a dialect translation benchmark. We believe SQLWitness could be broadly adopted for many use cases.

0.35

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.66
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

Structure-Aware Equivalence for Evaluating Autoformalized Statements

cs.PL ·2026-10-18 ·Yi Yu, Yu-Hsuan Wu, Guang Lin, Yuhui Zhang, Yuxiang Peng
benchmarkhot direction similarity 0.65
Abstract

Evaluating autoformalized mathematical statements requires determining whether a candidate preserves the mathematical claim intended by a trusted reference. Existing methods approach this problem from complementary directions: reference-free learned evaluators estimate semantic agreement but are not constrained to a formal equivalence relation, while reference-based proof methods typically employ whole-statement logical equivalence to provide formal certificates, which is too coarse for translation fidelity and may identify mathematically unrelated statements. We introduce Structure-Aware Equivalence (SAE), a role-preserving formal equivalence relation between syntactic and whole-statement logical equivalence that allows formally justified reformulations while preserving translation-relevant mathematical structure. We operationalize SAE in the Autoformalization Correctness Evaluator (ACE), which provides certified equivalence or inequivalence judgments and reports Inconclusive otherwise. On ProofNetVerif, a benchmark introduced with BEq+, ACE retains substantial equivalent-case coverage while remaining highly conservative in certifying disputed or inequivalent pairs. On targeted diagnostics, BEq+ accepts 94-96% of unrelated but whole-statement logically equivalent pairs, while Mathesis LeanScorer accepts 42% of localized meaning-changing perturbations; ACE accepts none of either set as equivalent.

0.23

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

cs.DB ·2026-09-09 ·Sara Cohen
theory similarity 0.63
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

SQLMorph: Query Mutation and Fine-Grained Metrics for Text-to-SQL Evaluation

cs.DB cs.AI ·2026-09-08 ·Mohammadhossein Malekpour, Mohamed Riahi, Maxime Lamothe, Amine Mhedhbi
top venue similarity 0.63
Abstract

Text-to-SQL systems translate natural language queries into executable SQL, democratizing access to structured data. Despite recent advances driven by large language models (LLMs), evaluation remains a major bottleneck: public benchmarks fail to capture the complexity of enterprise schema, while building private evaluation sets is costly and nondeterministic, making evaluation results difficult to reproduce. To address this issue, we present SQLMorph, a framework for Text-to-SQL evaluation via query mutation. SQLMorph introduces two techniques to automatically generate and expand evaluation sets: Join Query Expansion (JQE), which systematically increases structural complexity through valid join additions, and Textual Query Augmentation (TQA), which generates controlled natural language perturbations to assess robustness to linguistic variation. JQE and TQA create targeted choke points to challenge specific system components. When applied to state-of-the-art systems, JQE increases query coverage and reveals accuracy degradation as the number of joins grows. Meanwhile, TQA shows that linguistic brittleness induced by heavy abbreviation can reduce accuracy by up to 17%. Beyond evaluation sets, SQLMorph introduces a family of execution-level metrics that address the limitations of current binary measures, such as Execution Accuracy. We define Execution Precision (EXP) and Execution Recall (EXR) to quantify the fraction of correct and recovered results, respectively, and combine them via F1 for unified scoring. Our experiments show that these relaxed metrics enable fine-grained analysis of over- and under-prediction, revealing differences across systems that binary metrics obscure. Together, SQLMorph's query mutation and fine-grained metrics support debugging and better align Text-to-SQL evaluation practices with real-world deployments.

0.67

SemReuse: Certified Reuse of Cached Natural-Language Views for Semantic Operators

cs.DB ·2026-10-12 ·Phat T. Tran-Truong, Tung Kieu, Xuan-Bach Le, Son X. Ha, Duc Kieu +2 more
similarity 0.62
Abstract

Semantic operators allow users to filter unstructured data using conditions expressed in natural language, but existing systems typically invoke an LLM for every input tuple. Analytical workloads often contain repeated or related filters whose results could be reused. Such reuse is risky because it requires inferring whether filter conditions are equivalent, whether one implies another, or whether they are mutually exclusive. An incorrect judgment can omit qualifying tuples or include nonqualifying ones. We introduce SemReuse, a system for safely reusing previous semantic-filter results. SemReuse stores each result as a materialized view and compares new filters with existing views to identify tuples that can provisionally be accepted or skipped without another LLM call. Because these decisions rely on a fallible language reasoner, SemReuse audits every rewritten result. Its pooled stratified audit uses exact finite-population bounds to provide jointly valid per-query recall and precision guarantees. If the requested guarantees cannot be established, SemReuse evaluates additional tuples and progressively approaches full evaluation. Thus, incorrect relation judgments affect efficiency rather than the validity of the reported guarantees. Experiments on large labeled corpora and real LLM executions show reductions of up to 15.4x. They also identify cross-filter inconsistency as the main source of repair cost.

0.07

Revision-Bound Evidence Cuts: Authenticated Queries and Contextual Witness Capacity

cs.CR cs.DB ·2026-10-27 ·Faruk Alpay, Taylan Alpay
similarity 0.62
Abstract · 54 pages, 10 figures

Authentic records can support unauthorized narratives when their qualifications, query scope, or counterevidence are silently dropped. We present revision-bound evidence cuts, a framework for authenticating both supporting and opposing inference obligations across changing source versions. Signed complete-update frontiers permit transport of unaffected certificates, alternative-cut recovery, and an exact certified-reuse radius given by a frontier-hypergraph transversal number. Their source obligations induce an integral model of context-bound authorization. To secure database-derived claims, we introduce an authenticated relational query contract that binds original source records, complete selected bags, counting units, parameters, and aggregates independently of execution strategy. A full-source verifier checks 16,824 Chogha Mish records across SQLite scans, indexes, and materialized views; three valid strategies agree and eight contract/view mutations are rejected. A separate 340-row NISP cohort shows that changing the admitted weighting rule can reverse a comparison while preserving every source record. A frozen English text-to-frame compiler produces qualified evidence receipts, with linguistic accuracy evaluated separately from cryptographic integrity. We also separate logical-source from transport commitments so lossless re-encoding need not invalidate unchanged scientific evidence. The SCENE prototype evaluates signed revisions, authenticated queries, scoped disclosures, and adversarial mutations at scales reaching one million source records. These guarantees rely on declared policies and independently pinned trust roots; they authenticate specified computations and obligations, not historical truth, complete counterevidence, or institutional endorsement.

0.27

Recipe-Matching, Not Equivalence

cs.IR cs.CLcs.LG ·2026-09-25 ·Ali Habibullah, Mohammad Alshiekh, Yazan Alshoibi, Salman Khan, Naeemullah Khan
benchmarkhot direction similarity 0.62
Abstract

MathNet-Retrieve asks a retriever to find, for a math problem, a document stating the same problem. An LLM under one fixed prompt writes each gold document and its near-miss distractors; LLM judges filter them. We call this procedure the "recipe", training on pairs built the same way "recipe-matching", and ask how much score it buys beyond the ability the benchmark claims to test. Two models from one base, matched in rows and settings, differ only in the training file: pairs written under the benchmark's published prompt by another vendor's LLM and judge, or computer-algebra-verified pairs with no LLM anywhere. The first leads by 45 R@1 points on the easy tier. By a non-LLM paraphrase control, half to two thirds of that gap comes from the pairs being LLM-written at all: LLM rewrites under two unrelated prompts, with the verified model's negatives, recover 30 and 22 of the 45 points; back-translations with the same negatives recover almost none. The remaining 15 to 25 points appear only under the benchmark's own prompt and vanish on real duplicates no generator wrote, the same problem in two languages. The hard tier rewards the recipe's pair structure, a deep rewrite against a minimal-edit near-miss: LLM rewrites alone score zero on it, attaching negatives unlocks it, and every negative that does so costs cross-language points; the sets scoring highest on it separate near-misses no LLM wrote worse than LLM rewrites with verified negatives. MELD also moves when a model trains on pairs built its way, without losing retention; on SABER-Math the registered attack fails, and the one gain, from its LLM-written summaries, is small but holds at a matched budget. Only on MathNet-Retrieve could we pin an inversion, benchmark score up and real retention down, to one edit of a training file. We release the generator-free duplicate evaluations, the near-miss test and three trained models.

0.37