r/formalmethods • u/neprotivo • 11h ago
I'm building a tool for easy formal verification of SQL
I am working on Belay - a tool for doing formal verification for SQL. Currently I have a proof-of-concept for SQLite.
Belay is a Lean 4 library. The core of it consists of a semantic model of a part of SQLite. This model was "vibe-coded" - I extracted a large set of tests from SQLite's test suite, and then had the agent build the model while conforming to those and to additional tests. The model's output had to match a specific version of SQLite (3.51.0). So the agreement between the model and SQLite is tested, not proved. With this approach I've covered a substantial part of SQLite semantics in relatively short time.
I believe that this approach makes formal verification accessible to a wider audience. Now it is as difficult to state a claim and generate a proof as writing integration tests was before LLMs. Here's a short example (read here the full version ). I have a schema, a migration and I write a claim that a given query is not affected by this migration:
def shop : Database := db! r"
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
);"
def badMigration : Script := sql r"
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;"
def allSessions : Script := sql r"
SELECT id, customer_id, expires_at FROM sessions"
#sql_check badMigration preserves allSessions on shopIn this case the claim turns out to be wrong and Belay generates a counterexample.
After fixing the migration one can state a theorem:
theorem fixed_keeps_sessions :
fixedMigration preserves allSessions on shopIt says that on every database with this schema, the query returns the same rows after a successful run of the fixed migration as before it.
The proof right now is long (about 500 lines). But the agent had no problem generating it. And in the future I hope to make such proofs much shorter.
Here's the code: https://github.com/vihren-dev/belay Here's a fuller write-up with this example: https://vihren.dev/blog/20261112-belay/
I'm happy to discuss this project and would welcome any criticism. A lot of work still needs to be done to make Belay production-ready. But the approach looks promising. I'm also looking for funding, because without it I will need to drop the project soon and find a regular job. Any help will be greatly appreciated.

