Vi rapporterar om vår erfarenhet av att implementera ett lättviktigt, fullständigt verifierat relationsdatabashanteringssystem (RDBMS). Den funktionella specifikationen av RDBMS beteende, RDBMS genomförande, och bevis för att genomförandet uppfyller specifikationen är alla skrivna och verifieras i Coq. Våra bidrag inkluderar: (1) en fullständig specifikation av relational algebra i Coq; (2) ett effektivt förverkligande av den modellen (B+ träd) genomförs med Ynot förlängning till Coq; och (3) en uppsättning enkla frågeoptimeringar som visat sig respektera både semantik och run-time kostnad. Förutom att beskriva designen och genomförandet av dessa artefakter, lyfter vi fram de utmaningar vi stött på formalisera dem, inklusive valet av representation för finita relationer av typade tuples och utmaningarna med resonemang om datastrukturer med komplex delning. Vår erfarenhet visar att även om många utmaningar kvarstår, är det inom räckhåll att bygga fullt verifierade systemprogram i Coq.  Relationella databashanteringssystem (RDBMS) har blivit allmänt förekommande komponenter i modern applikationsprogramvara. Till exempel, SQLite, en lättviktig RDBMS, fartyg som en komponent i Firefox, Skype, SymbianOS, och McAfee Antivirus, bland annat. I många av dessa tillämpningar används RDBMS för att lagra data vars integritet och sekretess måste upprätthållas strikt (t.ex. finansiella register eller säkerhetsuppgifter). I en idealisk värld skulle en applikation utvecklare förses med en hög nivå specifikation för beteendet hos datahanteraren, lämplig för formella (dvs. mekaniska) resonemang om applikationsnivå säkerhet och korrekthet egenskaper. Dessutom har implementeringen av data man- * Denna forskning stöddes delvis av National Science Foundation bidrag 0910660 (Combining Foundational and Lightweight Formal Methods to Build Certify Reliable Software), NSF bidrag 0702345 (Integrating Types and Verification) och en NSF Graduate Research Fellowship. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. agrar skulle bevisas vara korrekt med avseende på denna specifikation för att säkerställa att ett fel inte kan leda till oavsiktlig korruption eller avslöjande. Det är av dessa skäl som vi ser verifierade RDBMS som en övertygande utmaning för de programmeringsspråk och programverifieringsgemenskaper som rör sig bortom de nu framgångsrika domänerna av verifierade kompilatorer och teoremtestare. Som ett steg mot detta mål har vi konstruerat en verifierad, lätt, in-minne RDBMS med hjälp av Coq proof assistent [2]. För närvarande stöder vår RDBMS frågor, skrivna i en stiliserad delmängd av SQL, över en in-minne relationell butik som kan [de]serialized till disk. Som sådan, ger det mycket av den funktionalitet som behövs för enkeltrådade klientapplikationer, men saknar de "ACID" egenskaper (Atomicity, konsekvens, Isolation, Hållbarhet) som krävs i en samtidig, ihållande lagringssystem. Den relationella butiken är modellerad med ändliga uppsättningar av typade tuples, och frågesemantik uttrycks i termer av denna modell. Före utförandet, en fråga omvandlas av en enkel och bevisligen semantik-bevarande optimizer. Den resulterande optimerade frågan kartläggs sedan till en sekvens av låg nivå operationer över B+ träd. Vi implementerar B+ träd med Ynot [15], en axiomatic förlängning till Coq som ger möjligheter till skrivande och resonemang om imperativ, pekarbaserad kod. Utformningen och genomförandet är i hög grad modulariserade för att stödja vidareutnyttjande av kod (och bevis) och för att möjliggöra alternativa implementationer. Till exempel fungerar frågeutförandemotorn i termer av ett generiskt ändligt kartgränssnitt som kan realiseras med hashtabeller eller andra datastrukturer förutom B+ träd. Som ett annat exempel kan frågeoptimatorn utökas med semantiska optimeringar som utnyttjar en förkunskaper om relationer, så länge som lämpliga (semantiska) intyg om denna kunskap kan presenteras för den. Målet med denna uppsats är att beskriva våra verifierade, lätta RDBMS och diskutera de utmaningar vi stod inför med hjälp av en säker utvecklingsmiljö som Coq för att bygga systemet. De flesta av dessa var: • Välja en lämplig kodning av relationsmodellen. Informellt är en relation helt enkelt en ändlig uppsättning tuples över vissa grundläggande värdetyper. I Coq finns det många sätt att representera sådana förbindelser, var och en med olika kompromisser. Till exempel, tidigare arbetskodning relationell algebra i Agda tyder på att scheman bör representeras som funktioner från en ändlig uppsättning kolumnnamn till grundläggande typer [9], men i praktiken fann vi att en betongkodning med hjälp av en lista av typnamn ger en mer fungerande representation. • Ett annat val var hur man skulle representera finita uppsättningar. Finita uppsättningar är en gemensam abstraktion och Coq ger dem bekvämt som ett standardbibliotek. Tyvärr är biblioteket för närvarande kodad som en kompilerings-tid, ML-stil functor parameteriserad av en fast elementtyp. Detta är alltför restriktivt för våra RDBMS, som måste bestämma typparametern vid körning. • Slutligen fann vi formaliserande korrekturbevis för komplicerade, pekarbaserade datastrukturer särskilt svåra trots tidigare arbete på detta område [3, 23]. B+ träd, som är gener-237
I synnerhet finns det en del tidigt arbete mot att bygga en verifierad relationsdatabas ledningssystem REF.
Toward a verified relational database management system
{'venue': "POPL '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}