  Deciding the equivalence of SQL queries is a fundamental problem in data
management. As prior work has mainly focused on studying the theoretical
limitations of the problem, very few implementations for checking such
equivalences exist. In this paper, we present a new formalism and
implementation for reasoning about the equivalences of SQL queries. Our
formalism, U-semiring, extends SQL's semiring semantics with unbounded
summation and duplicate elimination. U-semiring is defined using only very few
axioms and can thus be easily implemented using proof assistants such as Coq
for automated query reasoning. Yet, they are sufficient enough to enable us
reason about sophisticated SQL queries that are evaluated over bags and sets,
along with various integrity constraints. To evaluate the effectiveness of
U-semiring, we have used it to formally verify 39 query rewrite rules from both
classical data management research papers and real-world SQL engines, where
many of them have never been proven correct before.
