Datalog

Origin. Datalog crystallized out of the deductive-database research that followed Gallaire and Minker's Logic and Data Bases workshops (1977 onward), the name being due to David Maier: take logic programming, delete function symbols, and what remains is a query language over a finite database. Chandra and Harel (1985) analysed the expressive power of Horn-clause queries, Bancilhon, Maier, Sagiv and Ullman (1986) gave the magic-sets transformation that makes bottom-up evaluation goal-directed, and Apt, Blair and Walker (1988) fixed the semantics of stratified negation. The language was revived in the 2000s for static program analysis, network protocols and ontology-based data access.

Models. A program is read bottom-up rather than as a search for a proof. Because no function symbols occur, the Herbrand universe is just the constants appearing in the database, the Herbrand base is finite, and the least model is reached by iterating the rules to a fixpoint in a number of rounds bounded by a polynomial in the data. Facts are split from rules: the extensional database holds the stored relations, the intensional database the derived ones. Recursion is the point of the language, and transitive closure — beyond relational algebra and beyond plain SQL before recursive common table expressions — is the standard example.

Formalism.

Syntax: H(x̄) :- B₁(ȳ₁), ..., Bₙ(ȳₙ). No function symbols; only constants and variables. Head is a single atom.

Intensional vs extensional: EDB: extensional database, the stored facts. IDB: intensional database, the predicates defined by rules. EDB predicates never appear in a head.

Safety: Every head variable occurs in a positive body literal. Ensures the answer relation is finite.

Example: ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). Transitive closure.

Bottom-up evaluation: T_P: immediate consequence operator. Iterate T_P from the EDB until nothing new is derived. Result = lfp(T_P), the least model; polynomially many rounds.

Seminaive evaluation: Each round uses only facts derived in the previous one. Avoids rederiving what is already known.

Magic sets: Rewrite the program with adornments and magic predicates. Bottom-up evaluation of the rewritten program simulates top-down goal direction.

Stratified negation: Assign each predicate a stratum. A negated body literal must come from a strictly lower stratum. No recursion through negation; evaluate stratum by stratum.

Complexity: Data complexity: P-complete. Combined complexity: ExpTime-complete.

Extensions: Datalog^¬: negation, stratified or well-founded. Datalog^±: existential quantifiers in heads, for ontological reasoning. Aggregates, and lattice-valued or provenance-annotated variants.

Symbols.

Metatheory. A Datalog program without negation is a function-free definite program, so its meaning is the least Herbrand model; the absence of function symbols confines the Herbrand universe to the constants of the database, which makes that model finite and guarantees that bottom-up iteration terminates. Data complexity is P-complete and combined complexity, counting the program as input, is ExpTime-complete. Expressive power is narrower than P-completeness suggests: every Datalog query is monotone and preserved under homomorphisms, so plain Datalog does not capture PTIME. It is least fixpoint logic with negation, over ordered structures, that captures PTIME — the Immerman–Vardi theorem (1982) — and Datalog reaches that only once stratified negation and a linear order are added. A program is equivalent to a union of conjunctive queries exactly when it is bounded, and Gaifman, Mairson, Sagiv and Vardi (1987) proved boundedness undecidable; Shmueli (1993) proved equivalence of two Datalog programs undecidable. For a stratified program the perfect model is independent of which stratification is chosen (Apt, Blair and Walker 1988).

Applies to. Deductive databases. Static program analysis (points-to, dataflow). Network routing and declarative networking. Access-control and security policies. Ontology-based data access. Graph queries.

Limitations. Datalog is monotone, so adding facts never retracts an answer and no complement, difference or negative condition is expressible; neither is counting or parity. P-completeness measures the cost of evaluation, not the reach of the language, and plain Datalog falls strictly short of the polynomial-time queries. Stratified negation restores complements but bars recursion through negation, so no predicate may be defined in terms of its own negation, and any order the program needs must be supplied by the database rather than derived. Function symbols are excluded by definition, so no term can be constructed and no infinite structure described: lists and trees must be encoded as relations. Equivalence, containment and boundedness of programs are all undecidable, so no optimizer can decide whether a recursive definition is genuinely recursive. Allowing existentials in heads breaks termination of the chase and makes entailment undecidable without further syntactic restrictions.

© 2026 Lingenic LLC