A DAFSA-backed Datalog engine that never forgets itself.

Load facts into an on-disk minimal-acyclic-DAFSA store, compile Datalog rules to a small VM, materialize derived relations, and serve reads from an mmap’d snapshot. Every publish is an immutable, versioned point-in-time — so time travel is a first-class feature, not an afterthought.

The headline: time travel

// dl_publish_snapshot · dl_snapshot_versions · dl_query_version

Every dl_publish_snapshot writes an immutable, versioned snapshot and keeps the full history by default. The database is content-addressed by construction — the timeline is its complete history. Read it as it was at any version with an as-of query, diff or replay the evolution of a derived relation, and roll back — without ever losing the record of what happened.

$ ./dl -d db versions v042 2026-08-18 09:12 · published · ok v041 2026-08-17 22:04 · published · ok v040 2026-08-17 18:55 · rolled-forward to v042 ... $ ./dl -d db search 'gpu rental' --top 10 --version 39 # as-of a past snapshot $ ./dl -d db versions # the full history

Immutable snapshots — later writes never disturb a published version.
As-of queries — dl_query_version, dl_search_version, and dl_vector_search_version read the exact past state.
Opt-in retention — keep N snapshots, prune the rest, done.

The time-travel & as-of guide →

What else stands out

A database that shares its suffixes — genuinely compact

Every relation is stored as a minimized acyclic DAFSA: common suffix paths between facts merge into a single shared state, not duplicated. Reads are mmap’d zero-copy — the DAFSA is the index, so there’s 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 →

Typed projects — schema, validated data, typechecked rules

The dlp tool defines the schema in Dhall (schema.dhall), validates and coerces CSV/JSON data against it, and typechecks every rule before compilation. Mixed-type rules are rejected with file:line:col diagnostics — type errors surface early instead of mis-evaluating.

The typed project workflow →

Search — full-text and semantic, both versioned

dl search is AND-intersect full-text over a postings index. The vector tier adds semantic retrieval (dl vsearch / dl vhybrid): bge-small embeddings via the dl-embed tool, MIH-over-ITQ candidate retrieval, and in-store int8 re-rank — all stored in-relation and snapshot-versioned like everything else.

The vector-search tier →

Order statistics — rank, select, range, count

The big-endian encoding means the extreme prefix is the extreme key, so rank/select/range_count/count fall out of the DAFSA naturally — with bound + permutation-index variants, a pull-iterator + merge-join, and a lazy range generator. Median, percentiles, and ordered scans are native primitives, not table scans.

The order-statistics guide →

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>.

# 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 + prefix enumeration.
$ ./dl -d /tmp/db lookup edge 1 2
found
$ ./dl -d /tmp/db prefix edge 2
2 3
2 4

# Transitive closure via a Datalog rule.
$ ./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 — an immutable point-in-time.
$ ./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), qmagic (magic-sets), search, vsearch, vhybrid, and versions. See the CLI reference.

Feature summary

Area	Capabilities	Details
Time travel	Immutable versioned snapshots, as-of queries (`dl_query_version`, `dl_search_version`, `dl_vector_search_version`), opt-in retention	Time Travel
DAFSA storage	Fixed-width u32BE key encoding; one DAFSA + WAL per relation; symbol interner; WAL + compaction; mmap zero-copy reads	Architecture
Datalog syntax	Facts, rules, recursion, negation, aggregates (count/sum/min/max), equality, comparisons, arithmetic, strings, lists, range, regex	Language Reference
Evaluation	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
Durability	Per-relation WAL + fsync, single-writer lock, atomic snapshot publish, mmap read path	Architecture § durability
Search	Full-text `dl search` + semantic `dl vsearch`/`dl vhybrid` (bge-small via `dl-embed`, MIH-over-ITQ, in-store int8 re-rank), all versioned	Vector Search

Reference pages

Language Reference — the complete rule language.
CLI Reference — the dl subcommands.
C API Reference — the full dl.h surface.
Architecture — storage thesis, lifecycle, join & evaluation strategies.
Time Travel — versioned snapshots and as-of queries.
Vector Search — semantic dl vsearch/dl vhybrid, bge-small via dl-embed.
Order Statistics — rank / select / range / count and the sorted iterator.
Typed Projects — schema.dhall + validated data + typechecked rules.