Datalog’s Resurgence Inside Modern Tooling: Where It Really Lives and Where It Only Rhymes
How a restricted logic language became the engine behind static analysis, and why your incremental build system is only a cousin
Every few years, an old idea returns wearing new clothes. Datalog is a good example. It spent the 1990s fading out of fashion, then quietly came back inside tools that most developers use without knowing it. Its comeback is real, but the popular story around it contains two mistakes worth fixing first.
Two Myths Worth Clearing Up
The first myth says Datalog is older than Prolog. It is not. Alain Colmerauer developed Prolog in 1972, according to the historical notes in Artificial Intelligence: A Modern Approach. Logic and databases only became a field of its own at a 1977 workshop in Toulouse, as Jack Minker recounts. Datalog is a syntactic subset of logic programs, and David Maier is credited with coining the name, as the Taylor & Francis overview notes. The ideas underneath are older, but the language itself is Prolog’s younger, stricter cousin.
The second myth says Bazel is built on Datalog. It is not. Bazel’s incrementality comes from Skyframe, which the official documentation calls its incremental evaluation framework. Skyframe is a memoized dependency graph written in Java, not a logic engine. As we will see, though, the two share a surprisingly similar instinct.
What Datalog Actually Is
Datalog works bottom-up. It starts with known facts, applies rules to derive new facts, and repeats until nothing new appears. Prolog, in contrast, usually works top-down, starting from a goal and searching backward. Because Datalog forbids things like lists and term constructors, termination is guaranteed, as these lecture notes on deductive databases explain.
Why the Restriction Is the Feature
That sounds like a weakness, yet it is the whole point. A program that always terminates and has no hidden control flow can be optimized like a database query. Consequently, engineers can write what must be true and let the engine decide how to compute it. David Warren’s survey chapter traces both the decline of the language in the 1990s and its later resurgence in several application areas.
Home Turf: Static Analysis
Static analysis is where the resurgence is most solid. Programs are naturally relational: methods call methods, variables point to objects, and those facts chain together recursively. That is exactly what Datalog does well.
The Doop framework made the case early. It specifies Java points-to analyses declaratively in Datalog, and its abstract reports it was more than 15 times faster than the older Paddle framework on a 1-call-site sensitive analysis of the DaCapo benchmarks (see the bibliographic record). Later, Soufflé arrived as an engine that compiles Datalog into C++ and uses semi-naive evaluation, as this paper on its architecture describes.
Meanwhile, the idea reached mainstream security tooling. The CodeQL documentation states that QL looks like SQL but has semantics based on Datalog, including its recursive predicates. Even the Rust borrow checker has been formulated this way: the Polonius version serves as a benchmark workload in a recent Datalog engine paper.
The Build-System Cousin
Now to the build side. Skyframe models every computation as a node identified by a key. A function computes the node’s value and requests the other nodes it needs, so the graph of dependencies is discovered while it runs. Afterward, Bazel invalidates only what depends on a changed input, which the docs describe as bottom-up invalidation. A community guide adds that evaluation stops early when a rebuilt node produces an unchanged value.
Here is the key difference. Skyframe functions are ordinary code, so they must obey a rule: read data only through the framework. Otherwise the dependency goes unregistered and, as the docs warn, incremental builds can become incorrect. Datalog avoids that trap by construction, since the rules already state what depends on what. For example, Differential Datalog lets programmers write ordinary non-incremental rules while the runtime handles streams of input changes. In my reading, that is the same instinct as Skyframe, moved from a framework discipline into a language guarantee.
| Tool | What it is | Relation to Datalog |
|---|---|---|
| Doop | Java points-to framework | Analyses written as Datalog rules |
| Soufflé | Datalog engine | Compiles rules to C++, semi-naive evaluation |
| CodeQL | Code query platform | QL semantics based on Datalog |
| DDlog | Incremental language | Datalog dialect, only recomputes what changed |
| Bazel Skyframe | Incremental build evaluator | Not Datalog; memoized graph with bottom-up invalidation |
Measuring the Idea
To see why this matters, I ran a small experiment of my own. I computed reachability (the classic recursive Datalog program) on random acyclic graphs of 100 to 800 nodes. I counted join lookups, which is a machine-independent measure of work, instead of seconds.
First, I compared naive evaluation, which re-joins every known fact each round, with semi-naive evaluation, which joins only the newly found facts.

The gap widens with size. At 800 nodes, semi-naive did about 46 times less work than naive. Next, I added one new edge to an already computed result and compared a full recompute with an incremental update that propagates only the new facts.

At 800 nodes, absorbing one new edge took about 211 lookups on average, against about 28,850 for a full recompute, roughly 137 times less. This is the same economics that make an incremental build feel instant after a one-line change. However, treat these as toy numbers: one graph family, small sizes, and counts rather than timings.
Where the Resurgence Stops
Several limits deserve honesty. First, deletions are harder than insertions; a preprint on a differential Datalog interpreter contrasts semi-naive evaluation for additions with delete-and-rederive for removals. Second, debugging is painful: a paper on Datalog provenance notes that analyses with hundreds of recursive rules are notoriously hard to debug. Finally, DDlog’s repository now sits under vmware-archive, so check maintenance before adopting it.
Checklist before you reach for Datalog
- Is your problem a set of recursive relations, such as calls, reachability, or ownership?
- Do you need results that stay correct when inputs change a little?
- Can your team debug rules without a stack trace?
- Will your data fit in memory? DDlog, for one, requires it on a single machine.
- If you only need cached build steps, a graph evaluator like Skyframe may be enough.
What We Have Learned
Datalog is not older than Prolog; it is a younger, stricter cousin whose restrictions guarantee termination and make optimization possible. That is why it thrives in static analysis, through Doop, Soufflé, and CodeQL, where recursive relations are the natural shape of the problem. Bazel, however, runs on Skyframe, a hand-built memoized graph that shares Datalog’s incremental instinct without sharing its language. Our own measurements showed why the instinct matters: semi-naive evaluation did about 46 times less work than naive at 800 nodes, and an incremental update did about 137 times less than recomputing. Therefore, the lesson is less about one language and more about declaring dependencies so that machines, not people, keep them honest.


