Software Development

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.

ToolWhat it isRelation to Datalog
DoopJava points-to frameworkAnalyses written as Datalog rules
SouffléDatalog engineCompiles rules to C++, semi-naive evaluation
CodeQLCode query platformQL semantics based on Datalog
DDlogIncremental languageDatalog dialect, only recomputes what changed
Bazel SkyframeIncremental build evaluatorNot 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.

Chart 1. Join lookups to compute full reachability (log scale). Random acyclic graphs with 1.25 edges per node and short hops, fixed seed. Both methods produced identical results.

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.

Chart 2. Mean join lookups after inserting one edge, over 100 random insertions per size (log scale). Every incremental result was checked equal to a full recompute. Assumes a maintained reverse index and insert-only changes.

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.

Eleftheria Drosopoulou

Eleftheria is an Experienced Business Analyst with a robust background in the computer software industry. Proficient in Computer Software Training, Digital Marketing, HTML Scripting, and Microsoft Office, they bring a wealth of technical skills to the table. Additionally, she has a love for writing articles on various tech subjects, showcasing a talent for translating complex concepts into accessible content.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Back to top button