Compositional Datalog on SQL: Relational Algebra of the Environment

Summary

I spent some time before making Datalogs that translated into SQL. https://www.philipzucker.com/tiny-sqlite-datalog/ There are advantages. SQL engines are very well engineered and commonly available. SQLite and DuckDB are a pretty great one-two punch. A new twist on how to do this occurred to me that seems very clean compared to my previous methods. Basically, the relational algebra style of SQL actually meshes with manipulating the Datalog body environments (sets of named variables bindings) better then it meshes with the base Datalog relations themselves (edge, path, etc). As a cheeky bonus as the end, you can do semi-naive by using the dual number https://en.wikipedia.org/wiki/Dual_number trick from forward mode automatic differentiation over these environment relations. You can tinker on this post yourself on colab here https://colab.research.google.com/github/philzook58/philzook58.github.io/blob/master/pynb/2025-08-26-compose_datalog.ipynb The Environment As a Relation The core bits of SELECT-FROM-WHERE SQL, select-project-join relational algebra expressions, and datalog bodies are all expressing roughly the same thing: conjunctive queries. I rather like the syntax of a Datalog. It presents as both operational and logical. It is also pretty close to a SQL query, but it takes a jussst a little work because of incompatibilities In SQL: columns names are properties of the tables like myrow.name rows can be locally named in FROM mytable as myrow In Datalog: The columns are referred to positionally entries of rows are bound to variables edge(1,X) If you write a Datalog interpreter, like most interpreters, you’ll thread through a environment mapping variables names to values type Env = dict[Var, Value]. Datalog interpreters are branching in the sense that to bind a variable there are many choices (which row in the table to use). Roughly, an interpreter of a query has the signature interp : expr -> database -> env -> set[env]. It is a basic trick that I vaguely associ...