Datalog is one of those ideas that looks niche until you try it. Once you have a working datalog engine, queries that would be a nightmare in SQL become ten-line programs. The catch has always been that most datalog implementations are heavyweight and tied to a specific runtime.
According to philipzucker, the cleanest workaround is to encode datalog directly on top of SQLite. SQLite bindings exist in nearly every programming language, so this trick lets you embed a usable datalog in whatever stack you already have.
The short version:
- Datalog is a declarative logic programming language suited to recursive queries.
- SQLite bindings exist in nearly every language, which makes it a portable datalog backend.
- Two crucial features must survive the encoding: recursion and set semantics.
- Set semantics are handled by declaring all columns as primary keys.
- Less crucial differences, like nonlinear patterns, can be transformed away.
- The encoding is small enough to fit in a blog post.
What must survive the encoding
Two features are non-negotiable. The first is recursion, which is the entire point of datalog. SQL supports recursion through recursive common table expressions, but they are clunky and limited. To stay usable, the encoding must skip redundant work iteration after iteration, the standard trick called the semi-naive optimisation.
The second is set versus bag semantics. Datalog assumes sets: the same fact twice is one fact. SQL is bag-based by default: the same row twice is two rows. The clean fix in SQLite is to declare every table with all columns as primary keys and use INSERT OR IGNORE. Duplicate inserts are silently dropped and you have set semantics.
Less crucial features can be transformed away. Datalog allows nonlinear patterns, where the same variable appears twice in a rule body to act as an implicit equality constraint. SQL cannot express that directly. The fix is to linearise: rewrite the rule so each variable is bound once, and use explicit equality for the shared variable. As an example, a path rule written with a shared variable y is converted to the linear normal form by introducing a fresh variable y1, writing the rewritten path body as path(y1,z), and replacing the duplicated binding with the constraint y = y1.
Worked example: transitivity
The classic datalog example is transitive closure, which expresses reachability in a graph. In Souffle syntax the program declares an edge relation, declares a path relation, lists four edges forming a chain, then defines path as the transitive closure.
After linearising and switching to record-binding style, the same rules map cleanly to a SQLite-backed loop. The engine walks each rule body, applies the equality constraints as filters, and inserts the resulting rows. The semi-naive optimisation is implemented by tracking which rules added new rows on the previous iteration. That is a few extra lines of glue on top of the basic encoding.
Our analysis: who this is actually for
This encoding is for the reader who has a logic-programming-shaped problem and does not want to ship a heavyweight runtime. Recursive queries on graphs, program analysis, configuration validation and certain kinds of business rules are good fits. Bulk data processing is not. SQL engines are tuned for that workload and you will lose to them.
The interesting bet is portability. Because SQLite is essentially universal, the same datalog encoding runs in Python, Rust, Go, Node, Java, and probably whatever language you happen to use. The cost is performance: you are giving up a real datalog engine's tuned indexing and fixed-point iteration. For small to medium datasets that cost is fine.
The other lesson is how much of datalog is actually load-bearing. Strip out nonlinear patterns, linearise the variables, and you are left with a small, regular loop over SQL. That is the entire encoding.
Worked example: Say you have a small config graph
You have a set of services and you want to know which ones depend on which, transitively. Write edge rules for the direct dependencies. Add a path rule with the linearised pattern. Run the encoding against an in-memory SQLite database. The result is the full dependency graph, no recursion keywords required.
If you want to expose the result to a web UI, the same SQLite database that powers the datalog is also what the UI queries. One engine, two roles.
What to watch next
The blog post ends on a cliffhanger, with the next step being a "Stan" library that packages the encoding into something reusable. Watch for that, and for any community ports to other databases. Postgres has recursive CTEs that could support a similar trick with less glue.
Key takeaways
- Linearising datalog patterns makes them easy to translate to SQL.
- Set semantics are one extra SQLite declaration away.
- Recursion and the semi-naive optimisation are the parts that need real care.
Frequently asked questions
Why SQLite?
Because SQLite bindings exist in nearly every programming language, so the same datalog encoding works everywhere.
Does this support full Souffle-style syntax?
Not directly. The encoding handles the load-bearing features; less crucial syntax is rewritten before translation.
Is this fast enough for production?
For small to medium datasets, yes. For bulk workloads, a real datalog engine is still the better choice.
What about PostgreSQL?
Recursive CTEs in Postgres could support a similar encoding with less glue, since Postgres already has native recursion.