POPL 2019 (series) / CPP 2019 (series) / CPP 2019 - The 8th ACM SIGPLAN International Conference on Certified Programs and Proofs, January 14-15 2019 /
A Coq Mechanised Formal Semantics for Realistic SQL Queries - Formally Reconciling SQL and Bag Relational Algebra
Tue 15 Jan 2019 14:30 - 15:00 at Sala XII - Research Papers: Program Verification Chair(s): Nicolas Tabareau
In this article, we provide a Coq mechanised, executable, formal semantics for a realistic fragment of SQL consisting of select [distinct] from where group by having queries with NULL values, functions, aggregates, quantifiers and nested potentially correlated sub-queries. Relying on the Coq extraction mechanism to Ocaml, we produce a Coq certified semantic analyser for a SQL compiler. We then relate this fragment to a Coq formalised (extended) relational algebra that enjoys a bag semantics hence recovering all well-known algebraic equivalences upon which are based most of compilation optimisations. By doing so, we provide the first formally mechanised proof of the equivalence of SQL and extended relational algebra.
Tue 15 JanDisplayed time zone: Belfast change
Tue 15 Jan
Displayed time zone: Belfast change
14:00 - 15:30 | |||
14:00 30mResearch paper | A Verified Protocol Buffer Compiler CPP DOI | ||
14:30 30mResearch paper | A Coq Mechanised Formal Semantics for Realistic SQL Queries - Formally Reconciling SQL and Bag Relational Algebra CPP DOI | ||
15:00 30mResearch paper | Dynamic Class Initialization Semantics: a Jinja Extension CPP DOI |