datalog-dafsa

datalog-dafsa

A DAFSA-backed Datalog engine written in C. You load facts into an on-disk minimal-acyclic-DAFSA fact store, compile Datalog rules to a small VM, materialize derived relations, and serve reads from an mmap’d snapshot.

Try it right here — the real engine, compiled to WebAssembly, runs in your browser. No setup, no server.
Open the Playground →

Two things that stand out

A database that shares its suffixes — so it’s genuinely compact

Every relation is stored as a minimized acyclic DAFSA: common suffix paths between facts are merged into a single shared state, not duplicated. A store that keeps thousands of edge(1,…) prefixes over the same tail columns is dramatically smaller than a row store, because the shared tails exist once. Reads are mmap’d zero-copy — the DAFSA is the index, so there is no separate index file and no deserialization on the read path. Exact lookup and prefix enumeration are the two most common join access patterns, and both are native DAFSA primitives.

Why the DAFSA makes the store small →

Every publish is a point-in-time — time-travel as a first-class feature

Every dl_publish_snapshot writes an immutable, versioned snapshot and keeps the full history by default. That makes as-of queries a native capability: read the database as it was at version n — audit, replay, or diff the evolution of a derived relation — without touching live routing. Old snapshots are immutable; later writes never disturb them. Opt-in retention bounds disk growth.

Time-travel & as-of queries →

Typed projects — schema, validated data, and typechecked rules

The dlp tool defines the database schema in Dhall (schema.dhall), validates and coerces CSV/JSON data against it, and typechecks every rule before compilation. A variable can’t silently be Natural in one atom and Text in another — mixed-type rules are rejected with file:line:col diagnostics. Closed-world and typed, so type errors surface early instead of mis-evaluating.

The typed project workflow →

Quickstart

make                 # build libdatalog.so, dl CLI, test binaries
make test            # run the full test suite
make bench           # run the demonstration benchmark

The dl CLI loads facts and answers queries. The database directory defaults to dl-test-db and can be overridden with -d <dir>. 

$ cat edges.csv
1,2
1,3
2,3
2,4
3,5

# Load a headerless CSV (arity 1-8) into a relation.
$ ./dl -d /tmp/db load edges.csv --rel edge
Loaded 5 facts into edge

# Exact lookup.
$ ./dl -d /tmp/db lookup edge 1 2
found

# Prefix enumeration (bind leading columns).
$ ./dl -d /tmp/db prefix edge 2
2 3
2 4

# Run a Datalog rule (compile + publish + query in one step):
# transitive closure of edge.
$ ./dl -d /tmp/db query 'tc(X,Y) :- edge(X,Y). tc(X,Y) :- edge(X,Z), tc(Z,Y).' tc
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 5

# Publish a snapshot for read-only serving.
$ ./dl -d /tmp/db publish
Snapshot published.

CSV values that parse as integers are stored raw as u32; anything else is interned to a symbol id. Other commands include bound, pattern (regex), and qmagic (magic-sets). See the CLI reference.

Feature summary

AreaCapabilitiesDetails
DAFSA storage Fixed-width u32BE key encoding; one DAFSA + WAL per relation; symbol interner; WAL + compaction Architecture
Datalog syntax Facts, rules, recursion, negation, aggregates (count/sum/min/max), equality, comparisons, arithmetic, strings, lists, range, regex Language Reference
Evaluation strategies Semi-naive fixpoint, stratified negation, bushy joins, permutation-index selection + hash-join, magic-sets / QSQ top-down, incremental view maintenance Architecture § strategies
Order statistics rank / select / range_count / count, bound + perm variants, pull-iterator + merge-join, lazy range generator Order Statistics
Time-travel Versioned snapshots, as-of queries, opt-in retention Time Travel
Durability Per-relation WAL + fsync, single-writer lock, atomic snapshot publish, mmap read path Architecture § durability

Reference pages