This is an interpreter for Datalog, originally based on the implementation described in The Essence of Datalog by Mistral Contrastin.
The goal was to understand how Datalog accumulates facts in a knowledge base, and to get a sense of where opportunities for parallelism and other performance improvements might exist. The interpreter is extremely naive, using inappropriate data structures and having none of the standard optimizations implemented, so it’s not at all ready for production.
A simple example of defining and querying a graph using Datalog:
% Directed graphs
path(X, Y) <- edge(X, Y).
path(X, Y) <- edge(X, Z), edge(Z, Y).
edge(1, 2).
edge(2, 3).
? path(3, 1).
? path(1, 3).
? path(Start, 3).
? path(Start, End).
$ cat examples/graph.datalog | datalog
────────────────────────────────────────────────────────────────────────────────
Knowledge Base
────────────────────────────────────────────────────────────────────────────────
edge(1, 2).
edge(2, 3).
path(1, 2).
path(2, 3).
path(1, 3).
────────────────────────────────────────────────────────────────────────────────
Query Results
────────────────────────────────────────────────────────────────────────────────
? path(3, 1).
no
? path(1, 3).
yes
? path(Start, 3).
> Start := 2.
> Start := 1.
yes
? path(Start, End).
> Start := 1.
End := 2.
> Start := 2.
End := 3.
> Start := 1.
End := 3.
yes
More examples can be found in the examples directory, including a genealogy of characters from Tolkien’s legendarium.
Here’s some additional resources on Datalog that looked interesting, but I haven’t had time to go through yet:
- “Foundations of databases” by Abiteboul, Hull, and Vianu
- “Datalog - a precursor to Prolog” by Manfred von Thun from “Symbolic Processing In Pascal”
- “A relatively simple Datalog engine in Rust” by Frank McSherry
- “Codebase as Database: Turning the IDE Inside Out with Datalog” by Pete Vilter