Back to papers
Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries
Summary: Presents U-semiring, an extension of SQL semantics with unbounded summation and duplicate elimination for query equivalence. Lean-based implementation verifies 68 equivalences and rewrite rules over bags/sets and constraints, yielding unproved correctness results.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 11636
- Venue
- VLDB
- Year
- 2018
- Pagerank
- 9.5439744e-05
- Overall Rank
- 2,097 | 85.43%
- DOI
-
10.14778/3236187.3236200
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 20 of 20 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 973 |
Natural language to SQL: Where are we today? |
2020 |
VLDB |
0.0001488435 |
| 2,595 |
WeTune: Automatic Discovery and Verification of Query Rewrite Rules |
2022 |
SIGMOD |
8.4725961e-05 |
| 3,311 |
Attacking Diophantus: Solving a Special Case of Bag Containment |
2019 |
PODS |
7.2361776e-05 |
| 3,903 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6439695e-05 |
| 4,385 |
Proving Query Equivalence Using Linear Integer Arithmetic |
2023 |
SIGMOD |
6.2247394e-05 |
| 5,245 |
QED: A Powerful Query Equivalence Decider for SQL |
2024 |
VLDB |
5.6017846e-05 |
| 5,533 |
QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting |
2023 |
VLDB |
5.4555519e-05 |
| 7,137 |
Automated Validating and Fixing of Text-to-SQL Translation with Execution Consistency |
2025 |
SIGMOD |
4.8165495e-05 |
| 8,339 |
SlabCity: Whole-Query Optimization using Program Synthesis |
2023 |
VLDB |
4.5383933e-05 |
| 8,400 |
On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages |
2024 |
SIGMOD |
4.5180771e-05 |
| 8,780 |
GEqO: ML-Accelerated Semantic Equivalence Detection |
2023 |
SIGMOD |
4.4485568e-05 |
| 9,151 |
The Power of Constraints in Natural Language to SQL Translation |
2025 |
VLDB |
4.380727e-05 |
| 9,416 |
Leveraging Application Data Constraints to Optimize Database-Backed Web Applications |
2023 |
VLDB |
4.3399748e-05 |
| 9,623 |
Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries |
2024 |
SIGMOD |
4.3120302e-05 |
| 9,992 |
Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More! |
2026 |
CIDR |
4.1905499e-05 |
| 10,118 |
Test Data Generation for Complex SQL Queries |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,577 |
QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach |
2025 |
VLDB |
4.1905499e-05 |
| 10,768 |
ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation |
2025 |
VLDB |
4.1905499e-05 |
| 10,784 |
GRewriter: Practical Query Rewriting with Automatic Rule Set Expansion in GaussDB |
2025 |
VLDB |
4.1905499e-05 |
| 11,302 |
Towards Auto-Generated Data Systems |
2023 |
VLDB |
4.1905499e-05 |
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 |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.00078516827 |
| 66 |
Spark SQL: Relational Data Processing in Spark |
2015 |
SIGMOD |
0.00061707583 |
| 107 |
Extensible/Rule Based Query Rewrite Optimization in Starburst |
1992 |
SIGMOD |
0.00048363446 |
| 109 |
Dremel: Interactive Analysis of Web-Scale Datasets |
2010 |
VLDB |
0.00048217028 |
| 130 |
Optimization of Nested SQL Queries Revisited |
1987 |
SIGMOD |
0.00044001626 |
| 335 |
Optimization of Real Conjunctive Queries |
1993 |
PODS |
0.00027012705 |
| 578 |
The GMAP: A Versatile Tool for Physical Data Independence |
1994 |
VLDB |
0.00019825485 |
| 971 |
Rewriting Aggregate Queries Using Views |
1999 |
PODS |
0.00014915911 |
| 1,056 |
Cosette: An Automated Prover for SQL |
2017 |
CIDR |
0.00014391317 |
| 1,313 |
Cost-Based Optimization for Magic: Algebra and Implementation |
1996 |
SIGMOD |
0.00012629432 |
| 1,520 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.00011524911 |
| 2,398 |
Physical Data Independence, Constraints, and Optimization with Universal Plans |
1999 |
VLDB |
8.8871067e-05 |
| 3,007 |
Benchmarking the Chase |
2017 |
PODS |
7.7243073e-05 |
| 3,371 |
Demonstration of the Myria Big Data Management Service |
2014 |
SIGMOD |
7.1634294e-05 |
| 3,430 |
Demonstration of the Cosette Automated SQL Prover |
2017 |
SIGMOD |
7.0985442e-05 |
| 3,983 |
The Myria Big Data Management and Analytics System and Cloud Service |
2017 |
CIDR |
6.5588011e-05 |
| 4,150 |
A Formal Semantics of SQL Queries, Its Validation, and Applications |
2018 |
VLDB |
6.4022639e-05 |
| 4,650 |
A Chase Too Far? |
2000 |
SIGMOD |
6.0169723e-05 |
| 8,420 |
Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler |
2017 |
SIGMOD |
4.5116638e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,887 |
Semantic Query Optimization in Datalog Programs (Extended Abstract) |
1995 |
PODS |
7.9640219e-05 |
| 1,873 |
Flexible Queries over Semistructured Data |
2001 |
PODS |
0.00010255165 |
| 6,272 |
Classification of Annotation Semirings over Query Containment |
2012 |
PODS |
5.1271971e-05 |
| 2,105 |
Deciding Equivalences among Aggregate Queries |
1998 |
PODS |
9.5309231e-05 |
| 4,385 |
Proving Query Equivalence Using Linear Integer Arithmetic |
2023 |
SIGMOD |
6.2247394e-05 |
| 11,123 |
Demonstration of the VeriEQL Equivalence Checker for Complex SQL Queries |
2024 |
VLDB |
4.1905499e-05 |
| 12,305 |
Equivalence of SQL Queries In Presence of Embedded Dependencies |
2009 |
PODS |
4.1905499e-05 |
| 3,903 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6439695e-05 |
| 5,196 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6311982e-05 |
| 4,150 |
A Formal Semantics of SQL Queries, Its Validation, and Applications |
2018 |
VLDB |
6.4022639e-05 |