Datalog

Origin. 1980s database research. Function-free logic programming. Polynomial evaluation. Bottom-up. Foundation for deductive databases.

Models. Horn clauses without function symbols. Finite Herbrand universe. Fixed-point semantics. Safe rules. Stratified negation.

Formalism.

Syntax: H(x̄) :- B₁(ȳ₁), ..., Bₙ(ȳₙ). No function symbols. Only constants and variables.

Intensional vs extensional: EDB: extensional database (facts). IDB: intensional database (rules).

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

Bottom-up evaluation: Apply rules iteratively. T_P: immediate consequence. Fixed point reached in polynomial rounds.

Seminaive: Only use new facts. Avoid redundant derivations. Efficient iteration.

Safety: All head variables in positive body literal. Ensures finite answers.

Stratified negation: Negated predicates computed in prior stratum. No recursion through negation. Well-founded semantics.

Complexity: Data complexity: PTIME. Combined: EXPTIME. Captures PTIME queries.

Extensions: Datalog^ω: with aggregates. Datalog^¬: with negation. Datalog^∃: with existentials (ontology).

Symbols.

Symbol	Unicode	Name	Meaning
:-	—	Rule	If-then
EDB	—	Base	Facts
IDB	—	Derived	Rules
T_P	—	Immediate	Consequence

Metatheory. PTIME data complexity. Least model unique. Terminates. Captures PTIME.

Applies to. Databases. Program analysis. Network routing. Security policies. Ontologies.

Limitations. No functions. Limited recursion patterns. Negation requires care. Not Turing complete.