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.8966017e-05
Overall Rank
1,678 | 88.76%
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
755 Natural language to SQL: Where are we today? 2020 VLDB 0.00014210408
1,888 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 9.4148912e-05
2,971 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.7851336e-05
3,294 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.4297513e-05
3,584 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.1705819e-05
4,079 QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting 2023 VLDB 6.8026178e-05
4,116 QED: A Powerful Query Equivalence Decider for SQL 2024 VLDB 6.7846764e-05
4,917 Automated Validating and Fixing of Text-to-SQL Translation with Execution Consistency 2025 SIGMOD 6.3447485e-05
5,883 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.9423067e-05
7,658 Test Data Generation for Complex SQL Queries 2026 SIGMOD 5.4565877e-05
7,941 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 5.4056478e-05
7,972 The Power of Constraints in Natural Language to SQL Translation 2025 VLDB 5.3993508e-05
8,591 On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages 2024 SIGMOD 5.2936636e-05
8,992 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.2295579e-05
9,001 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.2260584e-05
9,754 Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More! 2026 CIDR 5.115551e-05
10,170 ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation 2025 VLDB 5.0559291e-05
10,914 I-Rex: An Interactive Debugger for SQL 2026 VLDB 4.9605343e-05
11,041 Verified LLM-Based Query Rewriting for Microsoft SQL Server 2026 VLDB 4.9605343e-05
11,306 QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach 2025 VLDB 4.9605343e-05
11,434 GRewriter: Practical Query Rewriting with Automatic Rule Set Expansion in GaussDB 2025 VLDB 4.9605343e-05
11,858 Towards Auto-Generated Data Systems 2023 VLDB 4.9605343e-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.00059660827
23 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00055523999
49 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00043085722
109 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.00032702871
133 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.0003015194
312 Optimization of Real Conjunctive Queries 1993 PODS 0.00021306615
579 The GMAP: A Versatile Tool for Physical Data Independence 1994 VLDB 0.00016069665
787 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013959502
882 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013239752
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012376627
1,279 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011207548
2,241 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.7710222e-05
2,668 Benchmarking the Chase 2017 PODS 8.1323973e-05
2,804 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.96944e-05
3,194 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.5310063e-05
3,693 The Myria Big Data Management and Analytics System and Cloud Service 2017 CIDR 7.0738965e-05
3,705 A Formal Semantics of SQL Queries, Its Validation, and Applications 2018 VLDB 7.0607226e-05
4,512 A Chase Too Far? 2000 SIGMOD 6.5535364e-05
7,885 Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler 2017 SIGMOD 5.4169619e-05
Previous Page 1 / 1 Next

Semantically Similar Papers