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.  Relational database management systems (RDBMSs) have become ubiquitous components of modern application software. For example, SQLite, a lightweight RDBMS, ships as a component of Firefox, Skype, SymbianOS, and McAfee Antivirus, among others. In many of these applications, the RDBMS is used to store data whose integrity and confidentiality must be strictly maintained (e.g., financial records or security credentials). In an ideal world, an application developer would be provided with a high-level specification for the behavior of the data manager, suitable for formal (i.e., mechanical) reasoning about application-level security and correctness properties. Furthermore, the implementation of the data man- * This research was supported in part by National Science Foundation grant 0910660 (Combining Foundational and Lightweight Formal Methods to Build Certifiably Dependable Software), NSF grant 0702345 (Integrating Types and Verification), and a NSF Graduate Research Fellowship. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ager would be proven correct with respect to this specification to ensure that a bug cannot lead to accidental corruption or disclosure. It is for these reasons that we see verified RDBMSs as a compelling challenge to the programming languages and software verification communities that moves beyond the now successful domains of verified compilers and theorem provers. As a step towards this goal, we have constructed a verified, lightweight, in-memory RDBMS using the Coq proof assistant [2] . Currently, our RDBMS supports queries, written in a stylized subset of SQL, over an in-memory relational store that can be [de]serialized to disk. As such, it provides much of the functionality needed for single-threaded client applications, but lacks the "ACID" properties (Atomicity, Consistency, Isolation, Durability) necessary in a concurrent, persistent storage system. The relational store is modeled using finite sets of typed tuples, and query semantics are expressed in terms of this model. Before execution, a query is transformed by a simple and provably semantics-preserving optimizer. The resulting optimized query is then mapped to a sequence of low-level operations over B+ trees. We implement B+ trees using Ynot [15] , an axiomatic extension to Coq that provides facilities for writing and reasoning about imperative, pointer-based code. The design and implementation are highly modularized to support code (and proof) re-use, and to enable alternative implementations. For example, the query execution engine works in terms of a generic finite map interface that can be realized with hash tables or other data structures besides B+ trees. As another example, the query optimizer can be extended with semantic optimizations that exploit a priori knowledge about relations, as long as appropriate (semantic) certificates of that knowledge can be presented to it. The goal of this paper is to describe our verified, lightweight RDBMS and discuss the challenges we faced using a proof development environment such as Coq to build the system. Foremost among these were: • Choosing an appropriate encoding of the relational model. Informally, a relation is simply a finite set of tuples over some basic value types. In Coq, there are many ways to represent such relations, each with different tradeoffs. For example, previous work encoding relational algebra in Agda suggests that schemas should be represented as functions from a finite set of column names to basic types [9] , but in practice, we found that a concrete encoding using a list of type names yields a more workable representation. • Another choice was how to represent finite sets. Finite sets are a common abstraction and Coq conveniently provides them as a standard library. Unfortunately, the library is currently coded as a compile-time, ML-style functor parameterized by a fixed element type. This is too restrictive for our RDBMS, which must determine the type parameter at run-time. • Finally, we found formalizing correctness proofs for complicated, pointer-based data structures particularly difficult despite previous work in this area [3, 23] . B+ trees, which are gener-237
A more recent formalization is found in Malecha et al., REF which addresses the problem of designing a fully verified, lightweight implementation of a relational database system.
Toward a verified relational database management system
POPL '10
Computer Science