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
- 11635
- Venue
- VLDB
- Year
- 2018
- Pagerank
- 9.5479391e-05
- Overall Rank
- 2,099 | 85.40%
- 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 |
| 984 |
Natural language to SQL: Where are we today? |
2020 |
VLDB |
0.00014857465 |
| 2,596 |
WeTune: Automatic Discovery and Verification of Query Rewrite Rules |
2022 |
SIGMOD |
8.4729982e-05 |
| 3,307 |
Attacking Diophantus: Solving a Special Case of Bag Containment |
2019 |
PODS |
7.2431594e-05 |
| 3,901 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6499845e-05 |
| 4,388 |
Proving Query Equivalence Using Linear Integer Arithmetic |
2023 |
SIGMOD |
6.2303078e-05 |
| 5,243 |
QED: A Powerful Query Equivalence Decider for SQL |
2024 |
VLDB |
5.6071695e-05 |
| 5,525 |
QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting |
2023 |
VLDB |
5.4600815e-05 |
| 7,139 |
Automated Validating and Fixing of Text-to-SQL Translation with Execution Consistency |
2025 |
SIGMOD |
4.821174e-05 |
| 8,345 |
SlabCity: Whole-Query Optimization using Program Synthesis |
2023 |
VLDB |
4.5426916e-05 |
| 8,404 |
On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages |
2024 |
SIGMOD |
4.5224126e-05 |
| 8,783 |
GEqO: ML-Accelerated Semantic Equivalence Detection |
2023 |
SIGMOD |
4.452825e-05 |
| 9,151 |
The Power of Constraints in Natural Language to SQL Translation |
2025 |
VLDB |
4.3849295e-05 |
| 9,410 |
Leveraging Application Data Constraints to Optimize Database-Backed Web Applications |
2023 |
VLDB |
4.3441378e-05 |
| 9,623 |
Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries |
2024 |
SIGMOD |
4.3161663e-05 |
| 9,993 |
Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More! |
2026 |
CIDR |
4.1945683e-05 |
| 10,118 |
Test Data Generation for Complex SQL Queries |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,568 |
QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach |
2025 |
VLDB |
4.1945683e-05 |
| 10,762 |
ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation |
2025 |
VLDB |
4.1945683e-05 |
| 10,778 |
GRewriter: Practical Query Rewriting with Automatic Rule Set Expansion in GaussDB |
2025 |
VLDB |
4.1945683e-05 |
| 11,300 |
Towards Auto-Generated Data Systems |
2023 |
VLDB |
4.1945683e-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.0007857786 |
| 66 |
Spark SQL: Relational Data Processing in Spark |
2015 |
SIGMOD |
0.00061639801 |
| 106 |
Extensible/Rule Based Query Rewrite Optimization in Starburst |
1992 |
SIGMOD |
0.00048400734 |
| 109 |
Dremel: Interactive Analysis of Web-Scale Datasets |
2010 |
VLDB |
0.00048186983 |
| 130 |
Optimization of Nested SQL Queries Revisited |
1987 |
SIGMOD |
0.00044031247 |
| 335 |
Optimization of Real Conjunctive Queries |
1993 |
PODS |
0.00027036073 |
| 578 |
The GMAP: A Versatile Tool for Physical Data Independence |
1994 |
VLDB |
0.00019838707 |
| 971 |
Rewriting Aggregate Queries Using Views |
1999 |
PODS |
0.00014925576 |
| 1,057 |
Cosette: An Automated Prover for SQL |
2017 |
CIDR |
0.0001439886 |
| 1,313 |
Cost-Based Optimization for Magic: Algebra and Implementation |
1996 |
SIGMOD |
0.0001263831 |
| 1,522 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.0001153051 |
| 2,401 |
Physical Data Independence, Constraints, and Optimization with Universal Plans |
1999 |
VLDB |
8.8954126e-05 |
| 3,004 |
Benchmarking the Chase |
2017 |
PODS |
7.7314538e-05 |
| 3,377 |
Demonstration of the Myria Big Data Management Service |
2014 |
SIGMOD |
7.1624478e-05 |
| 3,432 |
Demonstration of the Cosette Automated SQL Prover |
2017 |
SIGMOD |
7.1008151e-05 |
| 3,982 |
The Myria Big Data Management and Analytics System and Cloud Service |
2017 |
CIDR |
6.5651188e-05 |
| 4,148 |
A Formal Semantics of SQL Queries, Its Validation, and Applications |
2018 |
VLDB |
6.4079361e-05 |
| 4,654 |
A Chase Too Far? |
2000 |
SIGMOD |
6.022356e-05 |
| 8,429 |
Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler |
2017 |
SIGMOD |
4.5156925e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,877 |
Semantic Query Optimization in Datalog Programs (Extended Abstract) |
1995 |
PODS |
7.9715251e-05 |
| 1,870 |
Flexible Queries over Semistructured Data |
2001 |
PODS |
0.00010263799 |
| 6,274 |
Classification of Annotation Semirings over Query Containment |
2012 |
PODS |
5.1321227e-05 |
| 2,103 |
Deciding Equivalences among Aggregate Queries |
1998 |
PODS |
9.5385023e-05 |
| 4,388 |
Proving Query Equivalence Using Linear Integer Arithmetic |
2023 |
SIGMOD |
6.2303078e-05 |
| 11,120 |
Demonstration of the VeriEQL Equivalence Checker for Complex SQL Queries |
2024 |
VLDB |
4.1945683e-05 |
| 12,297 |
Equivalence of SQL Queries In Presence of Embedded Dependencies |
2009 |
PODS |
4.1945683e-05 |
| 3,901 |
Automated Verification of Query Equivalence Using Satisfiability Modulo Theories |
2019 |
VLDB |
6.6499845e-05 |
| 5,195 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6366303e-05 |
| 4,148 |
A Formal Semantics of SQL Queries, Its Validation, and Applications |
2018 |
VLDB |
6.4079361e-05 |