Translating Canonical SQL to Imperative Code in Coq
Authors:
- Véronique BenzakenVBVéronique Benzaken
- Évelyne ContejeanÉCÉvelyne Contejean
- Mohammed Houssem HachmaouiMHMohammed Houssem Hachmaoui
- Chantal KellerCKChantal Keller
- Louis MandelLMLouis Mandel
- Avraham ShinnarASAvraham Shinnar
- Jérôme SiméonJSJérôme Siméon
Preprint
Abstract
SQL is by far the most widely used and implemented query language. Yet, on some key features, such as correlated queries and NULL value semantics, many implementations diverge or contain bugs. We leverage recent advances in the formalization of SQL and query compilers to develop DBCert, the first mechanically verified compiler from SQL queries written in a canonical form to imperative code. Building DBCert required several new contributions which are described in this paper. First, we specify and mechanize a complete translation from SQL to the Nested Relational Algebra which can be used for query optimization. Second, we define Imp, a small imperative language sufficient to express SQL and which can target several execution languages including JavaScript. Finally, we develop a mechanized translation from the nested relational algebra to Imp, using the nested relational calculus as an intermediate step.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- A formal semantics of SQL queries, its validation, and applicationsProceedings of the VLDB Endowment, 2017
- Q*cert2017
- Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler2017
- Partial Materialization for Data Integration in SQL-on-Hadoop Engines2016
- SQL-like big data environments: Case study in clinical trial analytics2015
- Validating LR(1) ParsersLecture Notes in Computer Science, 2012
- Clock-directed modular code generation for synchronous data-flow languagesACM SIGPLAN Notices, 2008
- Polymorphic type inference for the named nested relational calculusACM Transactions on Computational Logic, 2007
- SQL query optimization through nested relational algebraACM Transactions on Database Systems, 2007
- Optimization and evaluation of disjunctive queriesIEEE Transactions on Knowledge and Data Engineering, 2000