Datalog is a logic language of facts and "if" rules. A rule says that a new fact holds when some facts already hold. The engine applies the rules again and again until no new fact appears. Many graph, policy and program-analysis engines run on it.
Datalog was invented in 1977, five years after C and Prolog, three years after SQL, and two years after Scheme.[1]
In Bondy, Datalog is the relation role together with its derivation rules. A rule is written with :-, and you read the relation it defines with query:
relation ReportsTo = {who: String, boss: String}
relation Manages(boss: String, who: String) :- ReportsTo(who: who, boss: boss)The facts are typed values, the same values the rest of the program uses. So a query and a function agree on what a ReportsTo is.
Two properties come with it. A derivation rule only adds facts, so a rule that follows a chain cannot loop on a cycle in the data (see transitive). And a rule may ask what is not in a relation only when that relation is computed first (see stratification). Each round of evaluation looks only at the facts the previous round added, not at every fact again.
Not to be confused with a rewrite rule over constraints, which can remove facts as well as add them. See rule.
Hervé Gallaire and Jack Minker (eds.), Logic and Data Bases. Plenum Press, 1978. The proceedings of the 1977 workshop in Toulouse where the approach was presented. The name Datalog came later, in the 1980s. ↩︎