DM: Chapter 6

Data and Information Management: Positive Datalog

• Instructor: Bas Ketsman

• Academic Year: 2025-2026

• Topic: Adding recursion to query languages via Positive Datalog.

Agenda of Today

• Introduction to Recursion: Adding recursive capabilities to standard query languages.

• Datalog Syntax: Formal structure of Datalog rules and programs.

• Model-Theoretic Semantics: Declarative logic-based interpretation of Datalog.

• Datalog as a Query Language: Definition of queries and output.

• Datalog Properties and Expressiveness: Comparison with other languages and limitations.

Datalog Syntax

• Definition of a Datalog Rule:

  • A Datalog rule over a schema $S$ is an expression of the form:     $R_0(x) :- R_1(u_1), \dots, R_n(u_n)$

  • The Head: The expression $R_0(x)$.

  • The Body: The expression $R_1(u_1), \dots, R_n(u_n)$.

  • Parameters:

    • The number of body atoms $n \ge 1$.

    • Each predicate $R_i$ is a member of the schema $S$.

    • The terms $x$ and $u_i$ (for every $i$) are tuples consisting of constants and variables.

• Safety Requirement: Every variable that appears in the head tuple $x$ must also be mentioned in at least one body atom tuple $u_i$.

• Datalog Program: A Datalog program over schema $S$ is a finite set of Datalog rules over $S$.

• Comparison Note: While Datalog has a similar flavor to Prolog, it is not the same (e.g., Datalog is purely declarative and does not use Prolog\'s search strategy).

Example: Reachability in Graphs

• Scenario: Given a directed graph represented by an $Edge$ relation, collect all nodes reachable from a specific source node $'s'$.

• Rule 1 (Base Case): $Reachable(x) :- Edge('s', x).$

• Rule 2 (Recursive Step): $Reachable(x) :- Reachable(y), Edge(y, x).$

Extensional vs. Intensional Relations

• Intensional Database Predicates (IDB):

  • A relation name is intensional if it occurs in the head of at least one rule.

  • These predicates are computed through definitions within the program.

  • Example: $Reachable$ in the reachability program.

• Extensional Database Predicates (EDB):

  • A relation name is extensional if it does not occur in any rule head.

  • These predicates are defined through explicit enumeration within the database.

  • Example: $Edge$ in the reachability program.

• Schema Assumption: Similar to conjunctive queries (CQs), schemas are often not explicitly provided; it is assumed that databases $D$ consist of the extensional relations of the program $P$.

Example: Points-To Analysis

• Context: Based on the work of Smaragdakis and Balatsouras (2015).

• EDB Conversion of C Instructions:

  • Instruction a = &b becomes $AddressOf(a, b)$.

  • Instruction a = b becomes $Assign(a, b)$.

  • Instruction a = *b becomes $Load(a, b)$.

  • Instruction *a = b becomes $Store(a, b)$.

• IDB Relation: $PointsTo(x, y)$ stores pairs of variables where $x$ may point to $y$.

• Rules for Analysis:

  1. $PointsTo(x, y) :- AddressOf(x, y).$

  2. $PointsTo(x, y) :- Assign(x, z), PointsTo(z, y).$

  3. $PointsTo(x, w) :- Load(x, z), PointsTo(z, y), PointsTo(y, w).$

  4. $PointsTo(x, y) :- Store(z, w), PointsTo(z, x), PointsTo(w, y).$

Datalog Semantics Overview

• Datalog utilizes coinciding declarative and operational semantics:

  • Model-Theoretic Semantics: Declarative approach based on First-Order (FO) logic formulas.

  • Fixpoint Semantics: Operational approach based on the repeated application of a fixpoint operator.

  • Proof-Tree Semantics: Note that this is mentioned as out of scope for the current course.

Model-Theoretic Datalog Semantics

• Interpretation: A Datalog rule $\rho$ of the form $R_0(x) :- R_1(u_1), \dots, R_n(u_n)$ is interpreted as a First-Order sentence $\phi_{\rho}$:     $\forall x_1 \dots \forall x_m (R_1(u_1) \land \dots \land R_n(u_n) \rightarrow R_0(x))$

• FO Theory: A Datalog program $P$ defines a set of constraints called an FO theory: ${ \phi_{\rho} \mid \rho \in P }$

• Model Definition: A database over the extensional schema of $P$ ($edb(P)$) is a model for $P$ if it satisfies all sentences in the FO theory.

• Program Output: Given a Datalog program $P$ and database $D$ of $edb(P)$, the output $P(D)$ is defined as the minimal model (with respect to set inclusion $\subseteq$) of $P$ that contains $D$.

• Validity Proof Hint:

  • A model of $P$ containing $D$ always exists (specifically, the database containing all possible facts over the Domain $Dom(P, D)$).

  • The intersection of all valid models is itself a model and is the unique minimal model.

Fixpoint Semantics: Immediate Consequences

• Immediate Consequences of P over D:

  1. Include all facts currently in $D$.

  2. Include facts $R(a)$ for which there exists a rule $\rho \in P$ and a valuation mapping all body atoms into existing facts in $D$, results in the head mapping to $R(a)$.

  • Operational Note: This computes the rule similarly to a Conjunctive Query (CQ).

• Immediate Consequence Operator ($T_P$):

  • A function mapping databases $D$ over $edb(P) \cup idb(P)$ to their immediate consequences.

  • $T_P^1(D) = T_P(D)$.

  • $T_P^i(D) = T_P(T_P^{i-1}(D))$.

• Fixpoint Definition: A database $D$ is a fixpoint for $T_P$ if $T_P(D) = D$.

• Least Fixpoint ($T_P^{\infty}(D)$): The first/least database that establishes a fixpoint for $T_P$ and $D$.

• Definition of Output: The output $P(D)$ is defined as $T_P^{\infty}(D)$.

Equivalence of Semantics

• Proposition: For any Datalog program $P$ and database $D$ over $edb(P)$, the Fixpoint and Model-Theoretic semantics are equivalent because:

  • $T_P$ is monotone.

  • There exists an integer $k$ such that the fixpoint is reached at $T_P^k(D)$.

  • Every fixpoint of $T_P$ containing $D$ is a model for $P$ and $D$.

  • Every model for $P$ and $D$ contains the set produced by $T_P(D)$.

Datalog as a Query Language

• Definition: A Datalog query $q$ over schema $S$ is a pair $q = (P, R)$.

  • $P$ is a Datalog program over schema $S \cup S'$.

  • $R \in idb(P)$.

  • $edb(P) \subseteq S$.

  • $idb(P) \subseteq S'$.

• Query Output ($q(D)$): The set of tuples present in relation $R$ within the resulting database instance $P(D)$.

Properties and Expressiveness

• Preservation Properties: Datalog queries are preserved under homomorphisms and are monotone.

• Expressive Limitations: Because of these properties, Datalog cannot express:

  • Inequalities.

  • Negative relational atoms.

  • Set difference.

• Complexity: Naive evaluation of Datalog takes polynomial many steps relative to the size of the database.

Naive Datalog Evaluation Example

• Database $D$: $Edge = \{ (a, b), (b, c), (c, d), (d, e) \}$, $R = \emptyset$.

• Program Rules:

  • $R(x, y) :- Edge(x, y).$

  • $R(x, y) :- R(x, z), R(z, y).$

• Rounds of Evaluation:

  • Round 1: $D_1 = T_P^1(D) = D \cup \{ (a, b), (b, c), (c, d), (d, e) \}$.

  • Round 2: $D_2 = T_P^2(D) = D_1 \cup \{ (a, c), (b, d), (c, e) \}$.

  • Round 3: $D_3 = T_P^3(D) = D_2 \cup \{ (a, d), (b, e), (a, e) \}$.

  • Round 4: $D_4 = T_P^4(D) = D_3$. (Fixpoint reached).

• Critique: Already discovered facts are derived repeatedly in every round, which is inefficient.

Semi-Naive Datalog Evaluation

• Logic: Avoid redundant work by focusing on "new" facts found in the previous step.

• Variables:

  • $R(i)$: Facts found after step $i$.

  • $\Delta R(i) = R(i) - R(i-1)$.

• Rule Expansion (Example $R(x, y) :- R(x, z), R(z, y)$):

  • Let the rule be a function $f(R, R)$.

  • $R(i+1) = f(R(i-1) \cup \Delta R(i), R(i-1) \cup \Delta R(i))$

  • Expanded: $f(R(i-1), R(i-1)) \cup f(R(i-1), \Delta R(i)) \cup f(\Delta R(i), R(i-1)) \cup f(\Delta R(i), \Delta R(i))$

  • $\Delta R(i+1) = f(R(i-1), \Delta R(i)) \cup f(\Delta R(i), R(i-1)) \cup f(\Delta R(i), \Delta R(i))$

• Procedure:

  1. Maintain two copies for each IDB relation $R$: the relation itself and its delta $\Delta R$.

  2. Apply the immediate consequence operator using the split formula to isolate new derivations.

  3. Update relations and deltas after each application until the delta is empty.

Linear Datalog Programs

• Definition: A rule is linear if it contains at most one IDB relation name in its body.

• Linear Program: A program consisting exclusively of linear rules.

• Efficiency: Linear programs are significantly more efficient to compute than non-linear programs.

• Linear Delta Derivation:

  • $\Delta R(i+1) = f(\Delta R(i), E(0))$

  • This removes the need to cross-join multiple IDB relations or deltas from different steps.

Undecidability and Satisfiability

• Undecidable Properties:

  • Determining if there is a bound on the number of applications of the immediate consequence operator needed for a fixpoint.

  • Determining query containment ($q \subseteq q'$) between two Datalog queries.

• Satisfiability Question: The transcript asks if every Datalog query $(P, R)$ is satisfiable.

Questions & Discussion

• Discussion on Minimal Models:

  • Question: Which databases are minimal models for $P$ and $D$ in the reachability example?

  • Answer Logic: The unique minimal model is the one generated by the fixpoint iteration, containing only nodes with a path from 's'.

• Discussion on Immediate Consequences:

  • Question: What are the immediate consequences of the reachability program on a graph with nodes $(s \rightarrow a)$, $(a \rightarrow b)$, $(a \rightarrow c)$?

  • Answer: In the first step, we derive $Reachable(a)$. In subsequent steps, we derive $Reachable(b)$ and $Reachable(c)$.

• Discussion on Performance:

  • Question: Why use Semi-Naive evaluation?

  • Answer: To avoid the overhead of re-deriving facts that were already established in previous rounds.