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
h7bab39deea55e152
Venue
VLDB
Year
2018
Pagerank
9.9031411e-05
Overall Rank
1,680 | 88.71%
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 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
776 Natural language to SQL: Where are we today? 2020 VLDB 0.00014063545
1,893 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 9.4126198e-05
2,961 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.8068219e-05
3,297 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.4452842e-05
3,570 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.1977783e-05
4,102 QED: A Powerful Query Equivalence Decider for SQL 2024 VLDB 6.8070264e-05
4,108 QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting 2023 VLDB 6.8020689e-05
5,544 Automated Validating and Fixing of Text-to-SQL Translation with Execution Consistency 2025 SIGMOD 6.0887243e-05
5,869 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.9648445e-05
7,638 Test Data Generation for Complex SQL Queries 2026 SIGMOD 5.4772833e-05
7,931 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 5.4238328e-05
7,952 The Power of Constraints in Natural Language to SQL Translation 2025 VLDB 5.4198293e-05
8,565 On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages 2024 SIGMOD 5.3137413e-05
8,962 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.2493925e-05
8,972 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.2458797e-05
10,129 ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation 2025 VLDB 5.0751052e-05
10,359 Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More! 2026 CIDR 4.9793485e-05
10,843 I-Rex: An Interactive Debugger for SQL 2026 VLDB 4.9793485e-05
10,971 Verified LLM-Based Query Rewriting for Microsoft SQL Server 2026 VLDB 4.9793485e-05
11,242 QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach 2025 VLDB 4.9793485e-05
11,375 GRewriter: Practical Query Rewriting with Automatic Rule Set Expansion in GaussDB 2025 VLDB 4.9793485e-05
11,808 Towards Auto-Generated Data Systems 2023 VLDB 4.9793485e-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.00059752575
23 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00055406774
49 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00043160717
109 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.0003276959
132 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.00030241193
310 Optimization of Real Conjunctive Queries 1993 PODS 0.00021374145
577 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00016118789
790 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013976438
880 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013280642
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012401489
1,275 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011242154
2,226 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.8033052e-05
2,674 Benchmarking the Chase 2017 PODS 8.1480823e-05
2,796 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.9971623e-05
3,202 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.5411821e-05
3,685 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 7.0988339e-05
3,718 A Formal Semantics of SQL Queries, Its Validation, and Applications 2018 VLDB 7.0721776e-05
4,494 A Chase Too Far? 2000 SIGMOD 6.577024e-05
7,865 Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler 2017 SIGMOD 5.4365956e-05
Previous Page 1 / 1 Next

Semantically Similar Papers