Datalog

Datalog is a declarative logic programming language that grew out of database theory and the logic programming community.

In the CS294-260 material, it is presented from a very operational perspective: think of Datalog as rules over relations, repeatedly applied until nothing new can be derived.

What makes Datalog unusually effective in systems and programming-languages work is that many analyses and graph problems are fundamentally mutually recursive relations. Instead of writing complicated iterative algorithms, you write the recursive specification directly and let the engine compute its closure.

Relations, rules, and recursive joins

A Datalog program defines relations (sets of tuples) using:

Facts — tuples you start with

edge(1,2).
edge(2,3).
edge(3,4).

Rules — how to derive new tuples

path(X,Y) :- edge(X,Y).
path(X,Z) :- edge(X,Y), path(Y,Z).

• edge is the input relation
• path is the derived relation
• the second rule expresses transitive closure

Rules can be read logically:

path(X,Z) holds if there exists Y such that edge(X,Y) and path(Y,Z) hold.

Operationally, the rule body behaves like a join:

So Datalog evaluation is essentially recursive relational joins over growing relations.

Fixed point

Datalog evaluation repeatedly applies rules and accumulates new tuples until no rule can add anything. The final saturated set of tuples is the least fixed point and defines the program’s meaning.

Formally, starting from input facts:

Iterate rule application:

Stop when nothing changes:

Intuitively: keep closing relations under the rules until closure is reached.

For reachability:

Iteration 0: path = ∅
Iteration 1: {(1,2),(2,3),(3,4)}
Iteration 2: {(1,3),(2,4)}
Iteration 3: {(1,4)}
Iteration 4: no change → fixpoint

The result is exactly the graph’s transitive closure.

This bottom-up fixpoint model is equivalent to logical entailment: the final relation contains precisely the facts implied by the rules and inputs.

Semi-naive algorithm

In bottom-up Datalog evaluation, rules are applied repeatedly as relations grow. A naive implementation would recompute every join over the entire relations at each iteration. But most of that work is redundant: tuples derived in earlier steps have already been combined once.

The key observation is simple:

A join can produce new tuples only if at least one input relation has changed.

Consider the recursive rule:

path(X,Z) :- edge(X,Y), path(Y,Z).

The edge relation never changes. So once all existing edge tuples have been joined with all existing path tuples, repeating the same join cannot produce anything new — unless path itself has grown.

So after each iteration, the only possible source of new path tuples is the newly added part of path from the previous step.

For each relation (R), engines conceptually maintain:

• (R) — all known tuples (old + new)
• (\Delta R) — tuples added in the last iteration

If we join two relations (R) and (S), the next iteration’s new results come from:

We do not recompute:

because that was already done in a previous iteration.

So joins are decomposed into:

• old × new
• new × old
• new × new

but never old × old.

Most Datalog engines maintain two physical tables per relation:

• R_old — accumulated tuples
• R_new — tuples from last iteration

Each recursive rule is rewritten into joins over these parts:

join(R_old, S_new)
union
join(R_new, S_old)
union
join(R_new, S_new)

After each iteration:

R_old ← R_old ∪ R_new
R_new ← newly derived tuples

This transformation preserves semantics and eliminates redundant work, which is why semi-naive evaluation is the standard execution strategy in essentially all Datalog systems.

Magic sets

Standard bottom-up Datalog evaluation derives all tuples implied by the rules, regardless of which ones are actually needed to answer a query. For recursive relations, this can be extremely wasteful.

For example, the reachability program computes the entire transitive closure of path, even if we only ask:

path(42,X)

Only nodes reachable from 42 matter, but naive bottom-up evaluation still computes reachability for every source node.

Magic-set rewriting solves this by transforming the program so evaluation is restricted to tuples that are relevant to the query bindings, while still running as a bottom-up fixpoint computation.

The key insight is that a rule instance can only contribute to the query result if its arguments are consistent with the query’s bindings. So instead of computing all path(X,Y), we propagate the constraint X = 42 through the recursion and compute only reachable tuples from that seed.

Concretely, magic sets introduce a new predicate representing demand for a relation. For the query path(42,X):

magic_path(42).

This predicate means: we only care about path facts whose first argument is reachable from 42.

We then guard the original rules:

path(X,Y) :- magic_path(X), edge(X,Y).
path(X,Z) :- magic_path(X), edge(X,Y), path(Y,Z).

And propagate demand along recursion:

magic_path(Y) :- magic_path(X), edge(X,Y).

Now bottom-up evaluation explores only the subgraph reachable from 42. No unrelated tuples are ever generated.

This transformation preserves semantics because every derivation that could contribute to the query remains possible; it only removes derivations that cannot affect the query result. Operationally, it converts “compute everything then filter” into “propagate constraints first, then compute.”

Importantly, magic sets do not change the evaluation model: execution remains bottom-up, joins remain relational, and semi-naive evaluation still applies. What changes is the search space. Recursion becomes restricted to the region reachable from the query bindings, giving goal-directed behavior without switching to top-down execution.

Beyond boolean relations

Classic Datalog treats relations as sets: a tuple is either present or absent. But you can view a relation as a function:

If (v\in{\text{true,false}}), you recover sets.

If (v) is numeric or algebraic, recursion computes values instead of membership.

Examples:

• min-plus semiring → shortest paths
• counting semiring → number of paths
• provenance semiring → derivation traces

The recursive structure stays the same; only the algebra changes.

Negation and stratification

Basic Datalog rules are positive: they only derive new facts from existing ones. Adding negation allows rules to depend on the absence of facts:

disconnected(X,Y) :- not path(X,Y).

This says: two nodes are disconnected if no path exists between them.

The difficulty is that negation interacts with recursion. If a rule uses not R(...), we must know whether R is already complete — otherwise we might derive facts that later become false.

Stratified negation

To keep semantics well-defined, Datalog systems usually require stratification.

A program is stratified if relations can be assigned to numbered layers (strata) such that:

• If a rule uses S positively, then stratum(head) ≥ stratum(S)
• If a rule uses not S, then stratum(head) > stratum(S)

Evaluation then proceeds in increasing stratum order.

Example:

path(X,Y) :- edge(X,Y).
path(X,Z) :- edge(X,Y), path(Y,Z).

disconnected(X,Y) :- not path(X,Y).

Dependencies:

edge → path → disconnected

Valid numbering:

edge         : 1
path         : 2
disconnected : 3

Evaluation:

1. Compute all edge
2. Compute fixpoint of path
3. Compute disconnected using final path

Because path is complete before negation is evaluated, results are stable.

Why cyclic negation breaks semantics

Consider:

p(X) :- not q(X).
q(X) :- not p(X).

Dependencies:

p depends on not q
q depends on not p

Stratification would require:

stratum(p) > stratum(q)
stratum(q) > stratum(p)

which is impossible. No ordering exists.

Semantically, this creates contradictory possibilities:

• assume p(a) → q(a) must be false
• assume q(a) → p(a) must be false

There is no unique minimal model and no well-defined fixpoint. Therefore such programs are disallowed in stratified Datalog.

How to compute strata

To stratify a program:

1. Build a dependency graph between relations

   • edge R → S if R depends on S
   • mark edge positive or negative

2. Collapse strongly connected components (mutual recursion shares a stratum)

3. Ensure no SCC contains a negative edge (otherwise impossible)

4. Topologically order SCCs so:

   • positive edges: same or later stratum
   • negative edges: strictly later stratum

5. Assign increasing integers as strata

Example:

a(X) :- b(X).
b(X) :- c(X).
d(X) :- not b(X).

Dependencies:

a → b
b → c
d -not→ b

Strata:

c : 1
b : 2
a : 2
d : 3

Reference

• [1] Declarative Program Analysis and Optimization, CS294-260, Spring 2024