CS Paper Radar

Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance

Jingyu Ke, Jingyang Li, Guoqiang Li

cs.DB ·submitted 2026-08-16 12:25 UTC · v1

Abstract

SQL rewrite verification must account for duplicate rows, observable row order, and typed value semantics. Existing verifiers have yet to combine proofs over database instances of arbitrary finite cardinality with an ordered-list semantics for nested, tie-sensitive top-k. Unbounded systems reason primarily over bags or handle ordering through syntax-directed restrictions, whereas bounded systems either support only restricted top-k forms or impose a deterministic ordering rather than retain all legal tie-induced outcomes. Support for typed expression and aggregate semantics, observable runtime errors, and integrity constraints also remains partial. In Rocq, we mechanize a compositional logical semantics for a typed SQL core with order-sensitive operators, capturing all possible ordered lists and observable SQL failures in the supported fragment. To our knowledge, this is the first mechanized SQL semantics to combine nested, tie-sensitive top-k with a closure-based lifting from bag equivalence to ordered-list equivalence, enabling sound reuse of bag-theoretic reasoning while preserving compositionality across order-sensitive and correlated contexts. The formalization further provides executable semantics for PostgreSQL-oriented scalar and aggregate evaluation and an explicit account of integrity constraints. Building on this semantics, we present Logos, an LLM-guided Rocq verifier for unbounded SQL rewrite equivalence. Its agent uses a verified SQL-specific lemma library to construct query-specific Rocq proofs. Our evaluation covers 389 query pairs from Apache Calcite optimizer tests, TPC-H and TPC-DS rewrites, and WeTune's real-application workloads. Logos solves 86.9% of them, compared with 64.0% for SQLSolver, the strongest baseline.

Comment
13 pages, 4 figures, and 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Whiel: A Neurosymbolic Platform for Certified Relational Program Verification

cs.DB cs.AIcs.LO ·2026-11-03 ·Jesse Comer, Fangzhu Shen, Shuo Zhang, Mayur Naik, Sudeepa Roy +1 more
benchmarktheory similarity 0.65
Abstract

We present the Whiel (a contraction of Whi(le-R)el) system for Lean-certified reasoning about imperative relational programs. The system can encode containment and equivalence problems for Datalog, its extensions with negation, and the core fragment of graph query languages. It can also represent optimized or incremental evaluation algorithms that are not expressible in the original query language, as well as first-order specifications of integrity constraints, schema mappings, and views arising in data integration, exchange, and sharing. Whiel's program states are database instances, and its imperative structure enables compositional Hoare-style reasoning with first-order relational specifications, using prophecy variables and leveled invariants to support inductive arguments. Whiel supports neurosymbolic discovery of loop invariants whose verification conditions can be checked using the Vampire first-order theorem prover. Counterexamples are fed back into the neurosymbolic pipeline, while proposed solutions are translated into Lean proof certificates. To validate the Whiel system, we evaluate its performance on a curated benchmark suite. In summary, we envision the Whiel system as a tool for tackling mathematically demanding, typically undecidable problems involving complex query and constraint languages, with a high degree of trust in its output.

0.24

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.62
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation

cs.PL cs.AIcs.CL ·2026-09-28 ·Paul Kronlund-Drouault
similarity 0.62
Abstract

Constrained decoding can enforce regular or context-free output formats, but many program-generation failures are semantic: scope, typing, and declaration effects depend on context. We present semantic grammar specifications, a declarative formalism that attaches such constraints to a context-free surface and executes them during Earley descent. Our implementation enforces \emph{safe pruning}: it rejects only prefixes whose semantic contradictions cannot be repaired by any continuation. A separate, grammar-dependent, \emph{dead-end freedom} property guarantees the existence of a realizable witness for each remaining branch. We give simple sufficient conditions based on surface productivity, type coverage, and left-to-right constraint flow. Our finite-lambda, core ML, and C-like fragments satisfy them, while the STLC instance used in our experiments does not: plain STLC can violate type coverage, and we show how restricting its type universe recovers it. A tokenizer-lifting lemma carries character-level witnesses to token sequences under an explicit vocabulary-coverage hypothesis. We validate the implementation differentially against production compilers (\texttt{ocamlc}, \texttt{cc}). Across every prefix of 65 compiler-valid programs we observe zero false prunes. The semantic oracle localizes 25/30 invalid programs mid-stream, against 0/30 for a syntax-only oracle, and agrees on 42/42 recursion probes. A twelve-model generation study, including a matched semantic-versus-syntactic ablation for nine models, finds nonnegative observed semantic-minus-syntactic point estimates for every model-language pair, with maxima of $+15.2$ points on STLC task correctness and $+14.3$ points on ML validity.

0.32

Towards a Deductive Verification Infrastructure for Weighted Programming

cs.PL ·2026-08-19 ·Emma Ahrens, Samuel Rode, Philipp Schröer, Joost-Pieter Katoen
theory similarity 0.61
Abstract

Weighted programs extend guarded commands with trace weights drawn from a semiring, or more generally a monoid-module. Varying this algebra gives one programmatic syntax for a variety of quantitative and symbolic models. Weakest-preweighting semantics provides a compositional basis for reasoning about those programs. We present a deductive verification framework based on a weighted assertion language and an intermediate verification language. Its weight domains are ordered structures with implication and coimplication, which let verification conditions express lower- and upper-bound obligations internally. We prove sound translations of core commands and reusable encodings for various proof rules applying to procedure calls and loops. To facilitate automation, we prove soundness of a quantifier elimination procedure for our assertion language. A prototype in the Caesar verifier checks case studies for probabilistic queueing costs, recursive database provenance with cyclic dependencies, clearance bounds for networks of arbitrary size, and formal-language reasoning about lock-freedom of a compare-and-swap counter.

0.24

Attacking Diophantus: Special Cases of Bag Containment

cs.DB ·2026-09-25 ·George Konstantinidis, Xinzhuo Li, Fabio Mogavero
similarity 0.61
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

When the Application Layer Is Disposable: Putting Integrity Constraints Back in the Database

cs.DB ·2026-10-26 ·Hasara Kalumin, Amol Deshpande
similarity 0.61
Abstract

Integrity constraints have been central to the relational model since its inception. However, beyond keys, single-row CHECKs, and referential integrity, most constraints are enforced by application layers today. SQL ASSERTIONs, standardized in SQL-92, remain poorly supported by major RDBMSs. This has become increasingly unacceptable due to two developments. First, LLM-driven applications and agents increasingly issue queries and updates directly against databases, bypassing application layers where invariants reside. Such code may be generated on demand and discarded afterwards, making the database the only durable component that can encode and enforce these invariants. Second, natural constraints in higher-level conceptual models, such as E/R and property graphs, become fragmented across relations under mappings chosen for performance. The resulting multi-relation constraints lack direct database support, and only some can be efficiently enforced using existing mechanisms such as triggers. These developments motivate an overhaul of how constraints are defined, mined, managed, and enforced in data management systems. As a first concrete step, we introduce constraint indexes, which represent constraints spanning multiple relations as transactional access paths, and implement a proof of concept as a PostgreSQL extension. Constraint indexes enforce constraints arising from distributed inheritance hierarchies, folded relationships, and folded weak entities, as well as cardinality bounds and functional dependencies, at low overhead relative to no enforcement. Across these workloads, they outperform the better of the correctness-preserving baselines by up to 2.41 times. We also show that LLM-driven writers frequently violate unenforced constraints and behave erratically when provided with a list of constraints to enforce. We close by discussing a few research challenges raised by this agenda.

0.53

Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_{<:}^{\top}$

cs.PL ·2026-10-14 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.60
Abstract · 44 pages, 8 figures, 2 tables. Includes appendices

System $F_{<:}^{\top}$ has decidable subtyping but lacks minimum types. We prove that typechecking is decidable for arbitrary explicitly annotated terms with unrestricted subsumption. The difficulty is that type abstraction uses a variable's declared bound to type its body, while quantified subtyping forgets that bound. We construct finite covers that preserve all required subtype comparisons across this change of context. These covers yield a compositional finite typing basis and a decision procedure. We then derive a backward checker that propagates acceptable targets without constructing the complete typing basis. Rectangularity of typing families gives a uniform elimination domain while retaining every result type, even when the canonical type is not least. Finite inverse families transport targets through type substitution. The same inverse specification recovers bound forgetting and yields finite type-avoidance families. Both typechecking procedures are total Rocq functions proved equivalent to the original typing judgment. For a separate symbolic word-RAM realization, we prove a quartic worst-case work bound. We measure family representation sizes and comparison storage in independent OCaml prototypes on synthetic checking judgments.

0.25

Dependently Typed Model Composition for Matching Logic

cs.LO ·2026-09-28 ·Ádám Kurucz, Péter Bereczky, Dániel Horpácsi
published similarity 0.60
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

This paper investigates model composition—often referred to as "gluing"—within the framework of matching logic. Specifically, we examine the systematic combination of existing signatures, variable valuations, theories, and their corresponding models. Our primary objective is to ensure that this composition preserves satisfaction proofs; that is, any theory validated by the individual constituent models is also validated by the resulting composite model. Our definitions are based on a polyadic, sorted variant of matching logic, which has also been expressed in the Rocq proof assistant. Therefore, we outline our definitions with dependent types for this work to serve as a direct blueprint for the mechanization in the short-term future.

0.29