Does Datalog need recursion?

No. Nonrecursive rules are valid, but recursion is an important source of its usefulness.

It is a language and reasoning approach; implementations may read database relations, maintain facts or integrate with other storage systems.

Can two rules derive the same fact?

Yes. Under classic set semantics, that fact is still represented once in the resulting relation, though provenance-aware extensions can track multiple derivations.

AI Glossary / Graphs and symbolic AI / Intermediate

Datalog

Definition

Datalog is a declarative logic-programming language for expressing facts and rules over relations. Its classic form uses function-free rules to derive additional facts, often including recursive relationships such as reachability in a graph.

What it means

A Datalog program describes what relationships should hold rather than spelling out a sequence of loops for finding them. A fact might state that one warehouse supplies another. A rule might state that an indirect supply route exists whenever two shorter routes connect appropriately.

The language is useful when the answer involves repeated application of relational rules. It appears in program analysis, graph reasoning and other tasks where new conclusions can be derived from existing facts.

“Datalog” also names a family of implementations and extensions. Features such as arithmetic, aggregates and negation vary. Claims about the classic finite, positive language should not automatically be applied to an unrestricted extension that can generate new values indefinitely.

How it works

Relations contain tuples of values. A rule has a head, describing the fact to derive, and a body, describing the conditions that must hold. A common notation writes Head :- Body, meaning that a matching body supports the head.

Variables connect the body conditions. Reusing the same variable means those positions must agree; it does not refer to a mutable storage box as in many imperative languages. Standard safety restrictions ensure that variables used in the result are appropriately grounded by the body.

For positive Datalog, a bottom-up evaluation starts with the input facts and repeatedly applies rules to add consequences. It stops at a fixed point: another round produces no new facts. Under the usual finite-domain, function-free assumptions, only finitely many ground facts can be formed, so this process terminates.

Efficient implementations avoid needlessly repeating all earlier work. Semi-naive evaluation uses newly derived facts to focus subsequent rounds. The intended least-fixed-point result is distinct from the particular order or optimization used to compute it. Negation requires additional semantic rules, such as stratification in systems that support that approach.

Three practical examples

A program-analysis tool derives which procedures can reach others through chains of calls.
A graph application computes indirect connections from a relation of direct links.
An access-review prototype derives inherited memberships from an explicitly modeled hierarchy, with separate rules governing the meaning of those memberships.

Think of it this way

Think of repeatedly adding justified entries to a shared fact board. Whenever existing entries satisfy a rule, another entry can be added. Eventually the rules have nothing new to contribute.

The analogy assumes positive rules over a bounded set of possible facts. Removing facts, introducing negation or generating unlimited new values changes the behavior and requires more careful semantics.

Worked example

Deriving indirect routes

Suppose the input facts are Edge(A,B), Edge(B,C) and Edge(C,D). Define two rules:

Reach(x,y) :- Edge(x,y).
Reach(x,z) :- Reach(x,y), Edge(y,z).

The first rule derives Reach(A,B), Reach(B,C) and Reach(C,D). Using those facts, the second rule derives Reach(A,C) and Reach(B,D). A further application derives Reach(A,D). No other distinct Reach facts follow, so the result contains six ordered pairs.

Notice that Reach(A,A) is not derived. These rules describe paths with at least one edge; they do not automatically include zero-length self-reachability. A separate rule or convention would be needed for reflexive reachability.

If Edge(D,A) is added, directed cycles allow self-reachability through nonempty paths. Repeated derivations still do not create endlessly many duplicate facts in classic set semantics. There are only 4×4=16 possible ordered Reach pairs over the four objects.

Illustrative case study

A fictional software-audit team, Cedar Code, uses Datalog rules to inspect procedure-call relationships. Its first report treats a procedure as indirectly calling itself only when an actual cycle exists in the input graph.

A reviewer expects every procedure to count as reachable from itself, even with no calls. The disagreement is about the relation's intended definition, not an engine defect. The team labels the original relation as nonempty-path reachability and adds a separate reflexive version where needed.

It also records which call relationships were extracted statically and which may be missing. Correct rule evaluation over incomplete facts cannot establish that the analyzed program has no other runtime behavior.

Common misconceptions and mistakes

Datalog rules run once in the order written. Recursive consequences may require repeated evaluation, and declarative meaning is not ordinary line-by-line execution.
Every Datalog extension necessarily terminates. Value-generating arithmetic or other extensions can alter classic guarantees.
A fact not derived is universally false. That interpretation depends on the chosen semantics and completeness assumptions about the data.
Datalog is simply unrestricted Prolog with different punctuation. Their classic restrictions and common evaluation strategies differ.

Business use

Datalog can make recurring relational reasoning compact and reviewable. It is particularly useful when requirements naturally involve dependencies, reachability or rule-derived classifications.

Before adopting a rule system, agree on relation meanings, input completeness, duplicate handling and treatment of negation. Test rules against small cases whose answers can be checked manually, including cycles and empty inputs. Performance depends on relation sizes, joins and recursion; short rule text does not guarantee cheap computation. Document implementation extensions so that portability and termination expectations remain clear.

Check your understanding

With only Edge(A,B) and the two Reach rules shown, must Reach(A,A) follow?

Answer: No. The rules derive Reach(A,B). There is no nonempty path returning to A, and no separate rule adds zero-length paths.

Related terms

Relation
Fixed point
Horn clause
Logic programming
recursive query
semi-naive evaluation
stratified negation

Learn next

Apply the two reachability rules to a three-node chain, then add an edge closing a cycle. List distinct derived pairs after each round. Finally, write down whether your application needs nonempty-path reachability or a reflexive relation that also includes every node itself.

Relation

Sources

Soufflé's official tutorial explains Datalog facts, rules, recursion, evaluation and implementation extensions: https://souffle-lang.github.io/tutorial

Inria VALDA discusses Datalog in the context of recursive database queries: https://radar.inria.fr/report/2018/valda/uid13.html

The reachability calculation and Cedar Code case are original examples.

Previous: Datafication Next: Dataset shift