CS Paper Radar

Time to Move on: Querying without Nulls and Bags

Molham Aref, Leonid Libkin, Wim Martens

cs.DB cs.PL ·submitted 2026-08-11 12:34 UTC · v1
position

Abstract

SQL is the database community's success story in terms of language design. The key reason for its success is its declarativeness: it gives rise to optimizability, reducing the programmer's burden significantly. However, given the evolving complexity of problems to solve with query languages, our community needs to re-think some of the fundamental early query language design decisions. Our experience in having worked on the design of Rel (a language for end-to-end relational programming) tells us that it is possible to design, implement, and successfully deploy a language based on fully normalized relations. Such relations avoid what Codd called corrupted relations and what we commonly refer to as bags, and the 'harmful' 'billion dollar mistake' that we know as nulls. In the SQL world, it is accepted that bags and nulls are tolerated as an unavoidable evil. We argue that the evil is completely avoidable: reasons offered for justifying bags and nulls evaporate at a closer examination. In addition to debunking them, we also describe opportunities offered by a null-free language with set semantics.

Closest papers

Nearest neighbours by meaning across the whole index.

Attacking Diophantus: Special Cases of Bag Containment

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

An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation

cs.DB ·2026-08-12 ·Wolfgang Gatterbauer
top venue similarity 0.62
Abstract · 7 pages, VLDB 2026 tutorial, tutorial page: https://northeastern-datalab.github.io/relational-language-tutorial/

Relational query languages have been studied and used for more than 50 years, with SQL dominant in practice. Today, queries are increasingly generated by machines and read by humans. At the same time, the landscape also includes dataframe, pipeline, logical, functional, graph, and relational programming notations. These developments invite two related questions beyond expressive power: which relational structures do languages make explicit, and how well can notation support users in reading and revising queries? This 3-hour tutorial extends an earlier SIGMOD'26 tutorial in three directions: recursive and path queries (connecting relational and graph query languages), nested relational data, and relational languages for problems beyond PTIME. Rather than beginning from formal definitions, we start from example queries and compare how different languages express the same intent. To compare recurring structure across notations, we use Abstract Relational Calculus (ARC) and Relational Diagrams as reference representations. From these examples, we develop a vocabulary for relational language design, including information need, query mapping, relational pattern structure, relational pattern denotation, and semantic conventions. Participants will leave with a framework for comparing existing and future relational languages, a precise vocabulary for articulating design trade-offs, and a concrete set of examples connecting classical database languages with alternative proposals.

0.48

SafeQL: Search-based Refinement for Safe and Efficient LLM-based Text-to-SQL

cs.DB cs.AI ·2026-08-10 ·Geonho Lee, Min-Soo Kim
top venue similarity 0.62
Abstract · VLDB 2026

Large language models (LLMs) have advanced Text-to-SQL by enabling natural language interfaces to databases without task-specific fine-tuning. However, existing LLM-based systems remain unreliable, often generating SQL queries that are invalid under the database schema, referencing non-existent tables, attributes, functions, or values. Such errors persist because interactions with the database management system (DBMS) are typically limited to error messages, leaving it in a largely passive role during query refinement. This paper proposes SafeQL, \textit{a search-based refinement paradigm that redefines the role of the DBMS as an active guide in the refinement process}. Instead of regenerating entire queries after execution failure, SafeQL interprets DBMS feedback to incrementally repair only the erroneous components. Each refinement step is formulated as a guided search within a \textit{safe query space}, where candidate queries are progressively validated through DBMS execution, thereby converging to an executable query and preventing repeated regeneration of errors. Experiments on the Bird and Spider benchmarks show that SafeQL significantly improves execution accuracy and efficiency compared to regeneration-based methods.

0.40

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

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

Post-SQLFix: Property-Guided Repair of LLM-Generated SQL with Runtime Verification

cs.SE ·2026-10-30 ·Zhihao Guo, Zonghan Wu, Yilei Shao, Haizhou Du, Nan Tang +2 more
similarity 0.60
Abstract

Large Language Models (LLMs) for Text-to-SQL frequently generate queries with syntax errors, invalid identifier references, or violations of SQL scoping and typing rules. Repairing these errors is a program correctness problem, yet existing approaches rely on Execution Feedback (EF), whose symptom-level, dialect-specific error messages force the LLM to speculate on root causes. We identify an Arbitration Paradox in this paradigm: the system relies on unverified models both to propose repairs and to make the final judgment on whether those repairs satisfy the required properties. We resolve this paradox by reformulating Text-to-SQL repair as property-guided program repair. Our framework, Post-SQLFix, canonicalizes SQL into a dialect-aware Canonical Query Structure (CQS) and validates it through a hierarchical static analyzer with three stratified property layers (Syntactic, Context-Free Structural, Context-Sensitive Semantic). The analyzer produces precise, schema-aware violation diagnostics to guide the LLM's repair proposals. A Verify-Before-Apply Temporal Monitor then accepts only repairs that reduce the violation count, do not reintroduce resolved violations, and satisfy the operator contracts. These runtime invariants are bounded by the declared rule family and operator contracts, while a finite retry budget ensures halting. On three established benchmarks (BIRD, Spider, Mini-Dev) spanning over 3,000 evaluation instances, three SQL dialects (SQLite, MySQL, PostgreSQL), and six model configurations, Post-SQLFix resolves 77.8% of the execution errors that EF leaves unrepaired, while requiring less than half as many repair iterations and 30% fewer tokens. Crucially, accepted transitions under the monitor introduce no statically detectable structural regressions in our evaluation, translating checked repair fidelity into absolute accuracy improvements of up to +11.6 percentage points.

0.20

Building SQL Equivalence Proofs from Query Rewrite Rules

cs.DB ·2026-10-21 ·Chunyu Chen, Xinyi Huang, Zhengjie Miao
benchmark similarity 0.59
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

OCTOPUS: Towards A Tag Model for Cross-Query Reuse in Semantic Query Processing

cs.DB ·2026-10-23 ·GuangXue Zhang, Nada Lahjouji, Yiming Lin, Ashwin Colaco, Sharad Mehrotra
similarity 0.59
Abstract

Large language models make it possible to pose semantic questions over diverse, multi-modal data. Recent systems give such workloads the declarative feel of a database through semantic operators: relational operators whose conditions a model judges. Most of them now run on a relational engine, yet almost none keeps what the model says past the query: every judgment is discarded on completion and paid for again the next time a query needs it. We present the tag model and tag operators, the right unit for semantic processing, and OCTOPUS, a prototype built as a middleware over DBMS. Two mechanisms are central. First, the tag: each semantic answer a model produces is written back to the relation as data, which the database engine filters, indexes, and stores as it would any other. Second, the tag operator: the unit into which common semantic operators are translated, which fixes the granularity of reuse. A model judges a tuple once, and later queries reuse that judgment as data: through relationships between predicates, a stored judgment can accept a tuple for a later predicate, eliminate one that cannot satisfy it, simplify its test, or order the search of a query that stops early. On the movie scenario of SemBench, our prototype sends the model 10 to 108x fewer rows than iPDB, ThalamusDB, Palimpzest, and LOTUS at broadly competitive quality, and three of its eight queries issue no model call at all. More broadly, a database that keeps its judgments lets its schema grow from the questions its users ask, so that each semantic answer is paid for once, stays consistent across queries, and can be audited through its provenance.

0.09