Datalog

Datalog is a declarative language, meaning programmers specify what to compute (the logical rules and facts) rather than how to compute it (the procedural steps). The system's inference engine determines the evaluation strategy. This separates business logic from execution details, making programs easier to write, understand, and maintain.

• Key Principle: Programs consist of Horn clauses (rules of the form head :- body).
• Example: A rule ancestor(X, Y) :- parent(X, Y). declares the logical relationship for ancestry.
• Contrast: Unlike imperative languages (e.g., Python, Java), there are no explicit loops or assignment statements; computation arises from logical deduction.

Datalog is typically evaluated using a bottom-up (forward-chaining) strategy. The engine starts with all known base facts and iteratively applies rules to derive all possible new facts until no more can be inferred (a fixpoint is reached). This results in the complete materialization of all entailed knowledge.

• Process: 1. Start with base facts (EDB - Extensional Database). 2. Apply rules to generate new facts (IDB - Intensional Database). 3. Add new facts to the set and repeat until no changes.
• Advantage: Guarantees finding all solutions to a query. Efficient for complex queries over large datasets as it leverages database-style set-at-a-time processing rather than tuple-at-a-time.
• Use Case: Ideal for computing transitive closures (e.g., all paths in a graph) and other recursive queries.

Datalog natively and efficiently supports recursive rules, where a predicate is defined in terms of itself. This is fundamental for querying graph-like structures and computing transitive relationships.

• Classic Example: Defining ancestry or reachability in a graph.

  prologCopy
  path(X, Y) :- edge(X, Y).
  path(X, Z) :- edge(X, Y), path(Y, Z).

• Capability: The second rule is recursive; it defines path using itself. A Datalog engine can compute the full transitive closure of the edge relation.
• Significance: This feature is notoriously difficult and inefficient to express in standard SQL (requiring recursive CTEs) but is a natural and optimized primitive in Datalog.

Datalog imposes a safety condition on rules to ensure that queries are finite and evaluation terminates. A rule is considered safe if every variable that appears in the head (conclusion) or in a negative literal in the body (premise) also appears in a positive, non-built-in literal in the body.

• Purpose: Prevents rules from generating an infinite number of facts. For example, a rule like bigNumber(X) :- NOT smallNumber(X). is unsafe because X is unbound, potentially referring to an infinite universe.
• Result: This restriction, combined with the lack of function symbols (like Prolog's s(X)), guarantees that the Herbrand universe is finite and evaluation will halt.
• Engineering Benefit: Provides developers with strong termination guarantees, crucial for predictable system performance in production reasoning engines.

Datalog supports negation through Negation as Failure (NAF), expressed with NOT or !. A literal NOT p(X) is considered true if p(X) cannot be proven from the current facts and rules. Its use requires careful semantics due to non-monotonicity.

• Stratified Negation: To ensure clear and consistent semantics, most Datalog dialects require stratification. The program is partitioned into strata where a predicate that uses negation cannot depend on its own negation, either directly or indirectly.
• Example: Finding people without a manager: managerless(X) :- employee(X), NOT hasManager(X).
• Importance: Allows for expressing closed-world queries (e.g., "find all items not in the catalog") and is essential for practical business logic.

Datalog serves as a powerful query language for deductive databases and knowledge graphs. It seamlessly blends stored data (facts in tables or triples) with derived knowledge (inference rules).

• Deductive Database: Combines a traditional relational database (storing Extensional Data - EDB) with a Datalog inference engine to compute Intensional Data (IDB) on demand or via materialization.
• Knowledge Graph Querying: Datalog is a foundational language for semantic reasoning. Systems like OWL 2 RL can be mapped to Datalog rules, enabling ontology reasoning (classification, consistency checking) over RDF triplestores.
• Modern Systems: Used in industrial logic engines (e.g., Datomic, LogicBlox, Soufflé) and academic systems for program analysis, network verification, and data integration.

Stratified Datalog is a syntactic subset of Datalog that guarantees a unique, unambiguous meaning for programs using negation. It restricts rule dependencies to avoid circular reasoning through negation.

• Stratification: A program is stratified if its predicates can be partitioned into strata (layers) such that for every rule, the stratum of the head predicate is greater than or equal to the stratum of all positive body predicates, and strictly greater than the stratum of any negated body predicate.
• Evaluation: Programs are evaluated stratum-by-stratum, computing the fixpoint for one stratum before moving to the next, which gives negation a well-defined semantics.
• Importance: Provides a decidable and efficient form of negation, making Datalog programs with negation tractable and predictable.

Datalog± is a family of extensions to Datalog designed to achieve a favorable trade-off between expressive power and computational complexity. The '±' denotes controlled additions (+) and restrictions (-) to the language.

• Goal: Extend Datalog with features essential for ontology querying (like existential quantification in rule heads) while preserving tractability and decidability.
• Key Extensions: Includes tuple-generating dependencies (TGDs) for expressing ontological constraints and equality-generating dependencies (EGDs) for key constraints.
• Use Case: Serves as a formal foundation for ontology-based data access (OBDA) and querying knowledge graphs with lightweight ontological reasoning.

Bottom-up evaluation is the standard computational strategy for Datalog and deductive databases. It starts from known facts (the extensional database) and repeatedly applies rules to derive all possible new facts until no more can be inferred (a fixpoint is reached).

• Process: 1. Initialize with base facts. 2. Apply all rules to current facts to generate new facts. 3. Add new facts to the set. 4. Repeat steps 2-3 until no new facts are produced.
• Algorithms: The naïve evaluation algorithm reapplies all rules in each iteration. The semi-naïve evaluation is an optimization that only considers rules that could be fired by facts derived in the previous iteration.
• Contrast: Differs from top-down evaluation (used in Prolog), which starts from a query and works backward through rules to find supporting facts.

A recursive query is a query that references its own output, either directly or indirectly, allowing it to traverse hierarchical or graph-structured data. This is a defining feature of Datalog.

• Datalog Syntax: Expressed using rules where a predicate appears in both the head and the body.
• Classic Example: Computing transitive closure (e.g., finding all ancestors in a parent-child relationship).

prologCopy
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

• Significance: Enables expression of complex graph traversals and inductive definitions that are cumbersome or impossible in standard SQL without procedural extensions.