The first time I saw Datalog used for program analysis, I thought the language looked too small to be useful.

No loops. No mutable maps. No work queue in sight. Just relations and rules:

path(x, y) :- edge(x, y).
path(x, z) :- path(x, y), edge(y, z).

Then the unsettling thing happens. That tiny program is a transitive-closure engine. Feed it a graph and it computes every reachable pair.

The trick is not that Datalog hides a loop from you. It hides a fixed point. The relation path starts with the known edges. The recursive rule grows it. When the rule can no longer add a pair, the meaning of the program has settled.

This is where the implementation question becomes interesting:

how do you run a recursive query without re-running the past?

The answer is semi-naive evaluation. The name is under-selling it. The idea is one of those useful little algorithmic hinges: after each round, remember only what changed.

The Meaning Is a Least Fixed Point

Datalog sits in the old and fruitful overlap between relational databases and logic programming. A relation is a set of tuples. A rule says how to derive tuples for one relation from tuples in others. For positive Datalog programs, the standard model-theoretic, proof-theoretic, and fixed-point views agree: the program denotes the least set of facts closed under its rules.1

For the reachability program, write the immediate-consequence operator as T. Given a current set of path facts, T adds:

all direct edges
all pairs (x,z) where path(x,y) and edge(y,z)

Starting from the empty relation and repeatedly applying T gives an ascending chain:

P0 = empty
P1 = T(P0)
P2 = T(P1)
P3 = T(P2)
...

Because the active domain is finite, this chain eventually stops. The stopped set is the least fixed point. Abiteboul, Hull, and Vianu build a large part of database theory around this kind of connection between logic, recursion, and query languages.2

The naive implementation follows the math directly:

path = edge
repeat
  old_size = size(path)
  for every (x,y) in path:
    for every edge(y,z):
      add path(x,z)
until size(path) == old_size

This is correct. It is also wasteful in a very specific way. If path(a,b) was known ten rounds ago, the naive loop still joins it with outgoing edges in the current round. It keeps asking old facts whether they have anything new to say.

They usually do not.

Only New Facts Can Surprise You

Let Delta_i be the facts discovered in the previous round:

Delta_i = P_i - P_{i-1}

For the one-recursive-relation reachability rule, the next frontier is:

Delta_next(x,z) :- Delta(x,y), edge(y,z), not_already_known(path(x,z)).

That last test is not logical negation in the source program. It is duplicate elimination in the engine. The declarative program is still the two-rule transitive closure above; the engine is just avoiding facts that are already in the materialized relation.

Here is the same loop with the frontier made explicit:

path = edge
delta = edge
while delta is not empty:
  next = empty
  for every (x,y) in delta:
    for every edge(y,z):
      if path(x,z) is new:
        add path(x,z) to next
  path = path union next
  delta = next

It has the same fixed point as naive evaluation. The difference is the unit of attention. Naive evaluation says: “rerun the whole recursive join.” Semi-naive evaluation says: “only the newest layer can cause the next layer.”

For this simple rule, the analogy to breadth-first search is literal. Round zero contains paths of length one. Round one discovers some length-two paths. Round two discovers longer paths, and so on. In a cyclic graph the layers are not as clean, because a short derivation can rediscover a pair already reached by another path. The frontier view still works: if no new tuple appears, the fixed point has been reached.

Why This Still Matters

Modern Datalog engines are not toy transitive-closure loops. Souffle, for example, presents Datalog as a language for recursive queries and static analysis; its tutorial starts from transitive closure and then moves into data-flow analysis over control-flow graphs.3 Recent systems work treats high-performance Datalog as a stack of techniques: semi-naive evaluation, compilation or specialization, join planning, indexing, parallel data structures, and sometimes GPUs.45

That stack matters because a realistic static analysis is just a pile of relations:

Assign(dst, src)
Load(dst, base, field)
Store(base, field, src)
Call(site, target)
PointsTo(var, object)
Reachable(block)

The recursive rules are the analysis. A points-to fact creates another points-to fact. A reachable block unlocks another reachable block. A call edge brings another function body into the reachable program. The language is small, but the fixed point can contain millions of tuples.

Semi-naive evaluation is the first bargain that makes the declarative style credible: write rules as if the whole relation is being defined, but execute rounds as if only the fresh consequences are alive.

It is not the whole bargain. The 2024 Formulog work by Bembenek, Greenberg, and Chong is especially useful here because it warns against treating semi-naive evaluation as magic. For SMT-heavy Datalog variants, they found that changing the order of inference could beat the conventional semi-naive schedule on their benchmarks.4 In other words, semi-naive is a default engine shape, not a law of nature.

The deeper lesson survives the caveat: recursive query performance is often about controlling the frontier.

A Browser-Sized Fixed Point

The lab below computes the transitive closure of a generated directed graph in three independent ways:

  • a plain BFS from every source node;
  • naive bottom-up evaluation of the recursive Datalog rule;
  • semi-naive bottom-up evaluation that joins only the delta frontier.

The default graph has 34 nodes and 120 edge facts. All three methods derive 561 reachable pairs. The JavaScript audit then repeats the comparison over 48 graph settings:

default graph shape       chain + skips
edge facts                120
reachable path facts      561
naive join probes         5,462
semi-naive join probes    1,477
work saved                72.96%
fixed-point audit grid    48 / 48 passed

The work counter is intentionally humble: it counts adjacency probes in this one join shape. A production Datalog engine would care about indexes, join order, memory layout, parallel scheduling, and relation representation. Still, the core duplication is visible enough in a browser. Drag the graph toward cycles or add edge noise and watch the frontier thicken; the fixed point is the same object, but the path to it changes.

The executable artifact is assets/js/seminaive-datalog-lab.js. It checks both fixed-point evaluators against an independent BFS closure.

What the Delta Buys

The most important invariant in the lab is not “semi-naive is faster on this graph.” It is:

naive_path == semi_naive_path == bfs_closure

The optimization is allowed only because it preserves the least fixed point. Every derived fact still has a proof. The engine merely observes that a proof whose recursive premise was already present in the previous round would have already had its chance to fire.

For a rule with several recursive inputs, the rewrite has several delta cases. If a rule uses A and B, and both are recursive relations, the next round has to consider the ways one side or the other changed. Real engines also group relations into strongly connected components, choose join orders, select indexes, and schedule work across threads. Subotic, Jordan, Chang, Fekete, and Scholz make automatic index selection one of the core engineering problems for large-scale Datalog computation.6

So the tiny reachability lab is not a replacement for a Datalog engine. It is the part of the engine I like to keep in my head:

the fixed point grows by differences

Once you see that, a lot of systems start rhyming. Incremental view maintenance. Differential dataflow. Data-flow analysis. Build systems. Even human debugging, on a good day: stop rereading the whole world; ask what just changed.

That is the small useful idea hiding behind the dry name. A recursive query does not have to forget its past. It can keep the old facts still and let only the new ones move.

  1. Stefano Ceri, Georg Gottlob, and Letizia Tanca, “What you always wanted to know about Datalog (and never dared to ask),” IEEE Transactions on Knowledge and Data Engineering, 1989. DOI: 10.1109/69.43410. ↩

  2. Serge Abiteboul, Richard Hull, and Victor Vianu, Foundations of Databases, Addison-Wesley, 1995. The authors host the book online at webdam.inria.fr/Alice. ↩

  3. The Souffle tutorial describes Datalog as a recursive query language and gives transitive closure and data-flow analysis examples. See Souffle: Tutorial. ↩

  4. Aaron Bembenek, Michael Greenberg, and Stephen Chong, “Making Formulog Fast: An Argument for Unconventional Datalog Evaluation,” OOPSLA 2024. The paper is useful both for the conventional high-performance recipe around semi-naive evaluation and for the caveat that some SMT-heavy workloads prefer a different inference order. See arXiv:2408.14017. ↩ ↩2

  5. Yihao Sun, Ahmedur Rahman Shovon, Thomas Gilray, Kristopher Micinski, and Sidharth Kumar, “Optimizing Datalog for the GPU,” arXiv:2311.02206, revised 2024. The abstract names query planning, semi-naive evaluation, and parallelization as the engine work hidden behind declarative Datalog queries. See arXiv:2311.02206. ↩

  6. Pavle Subotic, Herbert Jordan, Lijun Chang, Alan Fekete, and Bernhard Scholz, “Automatic Index Selection for Large-scale Datalog Computation,” Proceedings of the VLDB Endowment, 2018. ↩