DBScholar

Back to papers

Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries

Summary: Introduces U-semiring, a minimal-axiom extension of SQL’s semiring semantics with unbounded summation and duplicate elimination, supporting bags, sets, and integrity constraints. A Lean-oriented implementation formally verifies 68 query equivalences and rewrite rules. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
11823
Venue
VLDB
Year
2018
Pagerank
9.6671311e-05
Overall Rank
1,829 | 87.46%
DOI
10.14778/3236187.3236200

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{chu_vldb18,
        title = {{Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries}},
        author = {Chu, Shumo and Murphy, Brendan and Roesch, Jared and Cheung, Alvin and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {11},
        pages = {1482--1495},
        doi = {10.14778/3236187.3236200},
        url = {https://doi.org/10.14778/3236187.3236200},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
865 Natural language to SQL: Where are we today? 2020 VLDB 0.00013521464
1,982 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 9.3573897e-05
3,327 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.518491e-05
3,498 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.3629798e-05
3,769 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.1403543e-05
4,909 QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting 2023 VLDB 6.4486671e-05
5,353 QED: A Powerful Query Equivalence Decider for SQL 2024 VLDB 6.2519268e-05
6,267 Automated Validating and Fixing of Text-to-SQL Translation with Execution Consistency 2025 SIGMOD 5.9348282e-05
8,164 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 5.4750309e-05
8,407 On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages 2024 SIGMOD 5.4312823e-05
8,798 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.3698781e-05
8,834 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.3599176e-05
9,305 The Power of Constraints in Natural Language to SQL Translation 2025 VLDB 5.289545e-05
9,561 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.2528121e-05
9,945 ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation 2025 VLDB 5.1915905e-05
10,139 Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More! 2026 CIDR 5.093636e-05
10,406 Test Data Generation for Complex SQL Queries 2026 SIGMOD 5.093636e-05
10,834 QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach 2025 VLDB 5.093636e-05
11,007 GRewriter: Practical Query Rewriting with Automatic Rule Set Expansion in GaussDB 2025 VLDB 5.093636e-05
11,499 Towards Auto-Generated Data Systems 2023 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
17 Provenance Semirings 2007 PODS 0.00059843817
24 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00054865648
51 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.0004291425
110 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.0003309592
129 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.0003068101
309 Optimization of Real Conjunctive Queries 1993 PODS 0.00021768596
570 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00016328445
869 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013503594
910 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013285905
1,037 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012494928
1,269 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.000113935
2,189 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.9856333e-05
2,634 Benchmarking the Chase 2017 PODS 8.3210907e-05
2,804 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 8.1075524e-05
3,172 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.6679093e-05
3,618 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 7.2523695e-05
3,925 A Formal Semantics of SQL Queries, Its Validation, and Applications 2018 VLDB 7.0140857e-05
4,426 A Chase Too Far? 2000 SIGMOD 6.7098324e-05
8,712 Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler 2017 SIGMOD 5.3779634e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,883 Semantic Query Optimization in Datalog Programs (Extended Abstract) 1995 PODS
2 2,138 Flexible Queries over Semistructured Data 2001 PODS
3 6,166 Classification of Annotation Semirings over Query Containment 2012 PODS
4 2,238 Deciding Equivalences among Aggregate Queries 1998 PODS
5 3,769 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD
6 11,326 Demonstration of the VeriEQL Equivalence Checker for Complex SQL Queries 2024 VLDB
7 12,492 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS
8 3,327 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB
9 5,062 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS
10 3,925 A Formal Semantics of SQL Queries, Its Validation, and Applications 2018 VLDB