Data Management

Toward a Verified Relational Database Management System

Free registration required

Executive Summary

This paper reports on the 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. The contributions include a complete specification of the relational algebra in Coq; An efficient realization of that model (B+ trees) implemented with the Ynot extension to Coq; and a set of simple query optimizations proven to respect both semantics and run-time cost.

  • Format: PDF
  • Size: 260.2 KB