Formal verification for database migrations
An agent writes a migration in ten seconds, and then a person spends an hour making sure that it loses no data. With Belay, a formal proof gives that assurance instead. Belay is a proof of concept, and it works on SQLite today.
Databases are scary, frustrating and expensive.
You press Enter, and the answer is not “4 rows affected”. It is 1,647. Your stomach drops before you finish reading the number.
Or you need one column. You file the ticket. Weeks later you are still waiting, because someone, once, had that first moment.
Or your agent writes the migration in ten seconds. Then you spend the next hour reading it, because someone has to answer for what it does.
You pay for all of it: the failures, the waiting, the reading, and the changes nobody dares to make.
Formal verification can take away much of this. You state what must stay true. A proof shows that your migration or your query keeps it true, on every database with your schema and not only on the ones you tested. A small program checks the proof, so nobody has to trust its author.
Until now, proofs took experts to write, so few used this method: research labs, and the teams that build chips and compilers. Belay is a Lean 4 library that demonstrates how agents can change that. You decide which claims a migration must satisfy, and you check that their expression in Lean says what you mean. The claims are usually short and plain to read, as the example below shows. The agent then writes the proof, or fixes the migration when the claim does not hold, and Lean’s proof checker verifies the proof. All of this works on SQLite today.
In the rest of this post I follow one example to show how Belay works and what it gives you. I then name what it cannot do yet, and I end with a request, because the project needs funding to continue.
The migration, and why it looks right
The migration of this example rebuilds a table in SQLite. It passes its tests on an empty database, and every statement reports success. On a database with data, it deletes every session of every customer.
The schema has two tables. Each session belongs to a customer.
CREATE TABLE customers (
id INTEGER PRIMARY KEY,
name TEXT,
email TEXT NOT NULL
);
CREATE TABLE sessions (
id INTEGER PRIMARY KEY,
customer_id INTEGER NOT NULL
REFERENCES customers(id) ON DELETE CASCADE,
expires_at INTEGER NOT NULL
);
The team wants customers to be a STRICT table, so that SQLite enforces the
column types. SQLite cannot do that in place. The migration has to create a new
table, copy the rows, drop the old table and rename the new one.
The author saw a danger. With foreign keys on, dropping customers deletes every
session. So the migration turns foreign keys off for the rebuild.
PRAGMA foreign_keys = ON;
BEGIN;
PRAGMA foreign_keys = OFF;
CREATE TABLE customers_new (
id INTEGER PRIMARY KEY,
name TEXT,
email TEXT NOT NULL
) STRICT;
INSERT INTO customers_new SELECT id, name, email FROM customers;
DROP TABLE customers;
ALTER TABLE customers_new RENAME TO customers;
COMMIT;
But PRAGMA foreign_keys does nothing inside a transaction, and SQLite reports no
error, so foreign keys stay on. When DROP TABLE customers then deletes the
customers row by row, ON DELETE CASCADE deletes their sessions with them. The
transaction still commits, and every statement reports success. The same mistake
deleted a table of a real Rails application.
On an empty database the migration passes its test, because there is nothing to
lose. To catch the problem, a test would need rows in both tables and a check that
the sessions are still there afterwards. Such a test has to be written for this
one migration, and nobody writes it unless they already suspect that sessions is
at risk.
The claim
A claim needs no such suspicion. The claim used here has a simple form: a
migration preserves a query, which means that the query returns the same rows
after a successful run of the migration as before it. The author only has to choose the query. The
data to protect is in sessions, so the query is this one:
SELECT id, customer_id, expires_at FROM sessions
The claim is then one sentence: on a database with this schema, the bad migration preserves this query.
Nothing in this claim is special to this migration. The same claim, with the queries of the application, can be checked for every migration, so the author does not have to foresee where the danger is.
The Lean excerpt below checks the claim. It searches for a database that breaks it, and it also does an automated search for simple proofs of the claim. In Lean, the schema, the migration and the query each get a name, and the last line states the claim almost word for word.
def shop : Database := db! r"…the schema above…"
def badMigration : Script := sql r"…the migration above…"
def allSessions : Script :=
sql r"SELECT id, customer_id, expires_at FROM sessions"
#sql_check badMigration preserves allSessions on shop
What the check answers
SQL check: false.
Database:
customers:
id | name | email
1 | NULL | ''
sessions:
id | customer_id | expires_at
1 | 1 | 0
allSessions: rows [[1, 1, 0]]
The check found a counterexample: a database on which the query returns different
rows after the migration than before it. This one has one customer and one
session, and the session is gone afterwards, although every statement of the
migration reported success. The output ends with a script that replays the loss in
the sqlite3 shell, so the result does not depend on trust in Belay.
No special test was needed for this. The check is as generic as a lint rule, and it answers in about ten seconds, so an agent that works on a migration can run it before it attempts a proof. A bug that destroys data is then caught at the earliest point there is, while the migration is still being written.
The fix, and what is proved
The fix is to move PRAGMA foreign_keys = OFF before BEGIN, where it takes
effect. Here is the fixed migration:
PRAGMA foreign_keys = OFF;
BEGIN;
CREATE TABLE customers_new (
id INTEGER PRIMARY KEY,
name TEXT,
email TEXT NOT NULL
) STRICT;
INSERT INTO customers_new SELECT id, name, email FROM customers;
DROP TABLE customers;
ALTER TABLE customers_new RENAME TO customers;
PRAGMA foreign_key_check;
COMMIT;
PRAGMA foreign_keys = ON;
On this migration the same check answers unknown: it found no database that
breaks the claim, and none of the proofs that the library tries by itself went
through. That is not yet a guarantee, because the search stops after a few
seconds. To know that the migration is good on every database, the claim has to
be stated as a theorem and proved. In practice an agent writes the proof and
the Lean proof checker verifies it, so the only part that a person has to read and
understand is the statement of the theorem.
The theorem states the claim in the same words as the check:
def fixedMigration : Script := sql r"…the fixed migration above…"
theorem fixed_keeps_sessions :
fixedMigration preserves allSessions on shop
It says that on every database with this schema, whatever rows it holds,
allSessions returns the same rows after a successful run of the fixed migration
as before it. No test can say that, because a test covers only the databases that
someone thought of.
The words “a successful run” matter, though, because a migration that always fails also preserves every query. So the author needs a second claim – that the migration succeeds – and the check has an answer to it at once:
#sql_check fixedMigration succeeds on shop
SQL check: false.
Database:
customers:
id | name | email
1 | NULL | X''
The old table is not STRICT, so nothing stopped an application from storing a blob as an email. The new table refuses that row, and the copy fails. Nobody had asked about the types of the existing rows, and the claim made the question visible before the migration ran anywhere.
The claim that can be proved therefore has a condition: the migration succeeds on every database in which the existing customers fit the new types. The repository has that theorem and its proof. Together, the two theorems say what the team can rely on: if the rows fit, the migration runs to the end, and no session is lost.
The big picture
What does all of this mean? The example shows that formal verification can be an accessible way to protect a database. It moves the attention from what a migration does to what must stay true when it runs. Such a property can be as general or as specific as the author wishes: that a table keeps its rows, as above, or a rule of the business, such as that no order is left without a customer.
The first thing this changes is speed. The reviews, the tickets and the waiting around a database all exist because a person has to stand between a change and the data. A change that arrives with a proof does not need that person for this question, so it does not have to wait for them. The properties are written once, and every later change is verified against them while it is still being written. The gate that used to be a ticket and a wait becomes a check in the editor.
The same holds for agents, and there the gain is larger. An agent writes a migration in seconds, and today a person must still read every line of it, because a rule in a prompt can be ignored. A proof cannot be talked around, since a program – the Lean proof checker in this case – verifies it and not the agent. Once the properties stand, an agent can be left to write the migrations, and what a person has to read is the properties and not every statement.
Chip makers have worked this way for decades. In 1994 a fault in the division of the Pentium cost Intel about 475 million dollars, and the company has verified its floating-point hardware formally since then, because it is far cheaper to verify a design than to manufacture the chip and find the fault by testing it. A proof took experts months, though, so the method paid mostly where one fault costs that much. Agents have brought the cost of a proof down, and that is why the same idea now fits database operations.
Belay shows this on SQLite, as a proof of concept. The rest of this post says how it works and what it does not cover, and it ends with what the project needs to go further.
How it works, and why to trust it
Belay is a library for Lean, a language in which programs and mathematical proofs are written together. Its core is a model of a part of SQLite: something like a second SQLite, written in Lean, in which every statement is a function that takes a database and gives the next one. Because the model is ordinary Lean, a claim about a migration is a mathematical statement about such functions, and a proof of it can be checked by Lean’s proof checker. The model is the heart of Belay, and the check, the proofs and the notation of the claims are all ways to use it.
A model is worth exactly as much as its agreement with the real database,
because a proof is a proof about the model. It says something about SQLite as
far as the model behaves like SQLite, and this condition stands under every
result above. The agreement is hard to reach, since SQLite’s behaviour is full of
rules like the two of the example: a pragma that silently does nothing inside a
transaction, and a DROP TABLE that deletes the rows of another table. The model
has to get each such rule right, or the check would have passed the bad
migration. Belay does not prove the agreement, because that would take a proof
about SQLite’s C code itself, which is far outside this project. It tests it
instead. 5,525 cases, taken from SQLite’s own test suite and from the project’s
corpora, run on the real SQLite 3.51.0 and on the model, and the results must
match in every case. SQL that the model does not cover is refused with a message
and never approximated.
Agents wrote most of the model and of its proofs, and no person has yet read all of the model’s rules. The tests above are the reason to trust it today. If the project gets enough funding to continue, all of those rules will also go through a review by a human expert.
What a proof does not cover
A claim says what a statement does to the data stored in the database, and what output it produces, when the database operates normally. It says nothing about:
- Run time. How long the statement runs, and which plan SQLite chooses for it.
- Locks. Which locks the statement holds, and for how long.
- Concurrency. What happens when several connections work at the same time.
- Storage. The file format, a crash in the middle of a write, or a failing disk.
- Faults in SQLite outside its semantics. For example, a bug that crashes SQLite or corrupts the file.
Try it
The code is public, and the example of this post is
in the repository. The shortest way to try it is to point a coding agent at the
repository and tell it to set up Belay with the
skill
that the repository has. The agent sets up a project and runs the check of the
bad migration, so you see the same false as above, and from there you can
change the migration or the claim and watch the answer change. If you prefer to
do it by hand, the
README has the steps. The first
build takes a while, because it compiles the model once.
Questions are welcome in the discussions. The most useful thing to report is a case in which the model and SQLite disagree, as an issue.
What the project needs
Belay is a proof of concept. It shows that the method works on a part of SQLite, and the same method fits the databases where the heavy processes live, such as PostgreSQL. To get there the project needs funding, and without it the work stops here. So if you want it to continue and you can fund it, or you know someone who can, write to me at [email protected].
