Datalog

Datalog keeps the best part of Prolog (facts and recursive rules) and removes what makes it unpredictable: function symbols and search order. Every Datalog program terminates, and its answer does not depend on the order of rules, which lets engines optimize them like a database.

Paradigm: Logic Programming

What Makes Datalog Special

  • Rules over relations. Facts are rows in tables and rules derive new rows. reach(x, y) :- edge(x, y). is the same idea as a SQL view, with recursion built in.
  • Guaranteed termination. With no function symbols there is a finite set of possible facts, so evaluation reaches a fixed point and stops.
  • Order does not matter. Unlike Prolog, the order of rules and goals does not change the result. The engine is free to choose an efficient plan.
  • Bottom-up evaluation. Instead of searching from a goal, engines such as Soufflé derive all facts from the base facts, repeating until nothing new appears.
  • Made for big data and analysis. Datalog powers static analyzers for large codebases, security tools, graph queries and knowledge-base systems, and it scales to billions of facts.

Example: Reachability in a graph (Soufflé syntax)

.decl edge(x:number, y:number)
.decl reach(x:number, y:number)
.output reach

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

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

How It Works

  • .decl declares typed relations, which Soufflé requires. .output asks the engine to print the reach table.
  • The three edge facts form a path 1 → 2 → 3 → 4.
  • The first rule copies direct edges into reach; the second extends any reachable pair by one more edge.
  • The engine repeats the rules until no new pairs appear, and produces six rows: (1,2), (2,3), (3,4), (1,3), (2,4) and (1,4).

History and Where It Is Used

Datalog is the query language of Datomic and Cozo, the language of the Soufflé engine used in the Doop program-analysis framework (the QL language of CodeQL is Datalog-inspired too), and a common core in program verification and access-control tools. Syntax varies between engines. See also the longer Datalog lesson in the DSL roadmap.

Learn More