Toward a verified relational database management system
Authors:
Open Access
- 2 January 2010
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 45 (1) , 237-248
Abstract
We report on our experience implementing a lightweight, fully verified relational database management system (RDBMS). The functional specification of RDBMS behavior, RDBMS implementation, and proof that the implementation meets the specification are all written and verified in Coq. Our contributions include: (1) a complete specification of the relational algebra in Coq; (2) an efficient realization of that model (B+ trees) implemented with the Ynot extension to Coq; and (3) a set of simple query optimizations proven to respect both semantics and run-time cost. In addition to describing the design and implementation of these artifacts, we highlight the challenges we encountered formalizing them, including the choice of representation for finite relations of typed tuples and the challenges of reasoning about data structures with complex sharing. Our experience shows that though many challenges remain, building fully-verified systems software in Coq is within reach.Keywords
This publication has 12 references indexed in Scilit:
- Effective interactive proofs for higher-order imperative programs2009
- Towards type-theoretic semantics for transactional concurrency2009
- Reasoning about B+ Trees with Operational Semantics and Separation LogicElectronic Notes in Theoretical Computer Science, 2008
- The power of Pi2008
- First-Class Type Classes2008
- Program-ing finger trees in C oq2007
- Resources, concurrency, and local reasoningTheoretical Computer Science, 2007
- A semantics for concurrent separation logicTheoretical Computer Science, 2007
- Polymorphism and separation in hoare type theory2006
- The view from the leftJournal of Functional Programming, 2004