Proving Query Equivalence Using Linear Integer Arithmetic
Open Access
- 8 December 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (4) , 1-26
Abstract
Proving the equivalence between SQL queries is a fundamental problem in database research. Existing solvers model queries using algebraic representations and convert such representations into first-order logic formulas so that query equivalence can be verified by solving a satisfiability problem. The main challenge lies in "unbounded summations", which appear commonly in a query's algebraic representation in order to model common SQL features, such as projection and aggregate functions. Unfortunately, existing solvers handle unbounded summations in an ad-hoc manner based on heuristics or syntax comparison, which severely limits the set of queries that can be supported. This paper develops a new SQL equivalence prover called SQLSolver, which can handle unbounded summations in a principled way. Our key insight is to use the theory of LIA^*, which extends linear integer arithmetic formulas with unbounded sums and provides algorithms to translate a LIA^* formula to a LIA formula that can be decided using existing SMT solvers. We augment the basic LIA^* theory to handle several complex scenarios (such as nested unbounded summations) that arise from modeling real-world queries. We evaluate SQLSolver with 359 equivalent query pairs derived from the SQL rewrite rules in Calcite and Spark SQL. SQLSolver successfully proves 346 pairs of them, which significantly outperforms existing provers.Keywords
Funding Information
- National Natural Science Foundation of China (62272304,62132014)
- Fundamental Research Funds for the Central Universities
- National Science Foundation (FMitF-2220407,CCF-2131476)
This publication has 24 references indexed in Scilit:
- Decision Procedures for Multisets with Cardinality Constraints2008
- Z3: An Efficient SMT Solver2008
- Deciding equivalences among conjunctive aggregate queriesJournal of the ACM, 2007
- Deciding Boolean Algebra with Presburger ArithmeticJournal of Automated Reasoning, 2006
- An Algorithm for Deciding BAPA: Boolean Algebra with Presburger ArithmeticLecture Notes in Computer Science, 2005
- Rewriting aggregate queries using views1999
- Containment of conjunctive queriesACM Transactions on Database Systems, 1995
- Optimization of nested SQL queries revisitedACM SIGMOD Record, 1987
- Equivalences Among Relational Expressions with the Union and Difference OperatorsJournal of the ACM, 1980
- Optimal implementation of conjunctive queries in relational data bases1977