Towards a Verified Relational Database Management System

Gregory Malecha, Greg Morrisett, Avraham Shinnar, and Ryan Wisnesky.

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.

Full Paper
The full paper is available as a PDF.
Citation 

@inproceedings{ynot-rdms10,
  author =	 {Gregory Malecha and Greg Morrisett and Avraham
                  Shinnar and Ryan Wisnesky},
  title =	 {Towards a Verified Relational Database Management
                  System},
  booktitle =	 {POPL '10: Proceeding of the 37th ACM SIGACT-SIGPLAN
                  Symposium on Principles of Programming Languages},
  year =	 2010,
  location =	 {Madrid, Spain},
  publisher =	 {ACM},
  address =	 {New York, NY, USA},
}
Project Website
The accompanying source code is available from the Ynot project website.