DM: Chapter 7

Datalog with Equality: Syntax and Semantics

• Definition of Syntax Extensions: Datalog is extended by allowing equality atoms within the rule bodies. These atoms can take two forms:

  • Expressions of the form $x = y$, where both $x$ and $y$ are variables.

  • Expressions of the form $x = c$, where $x$ is a variable and $c$ is a constant.

• Safety Requirement: To ensure safety, all variables present in the equality atoms must also occur in the non-equality body atoms of the rule.

• Example of Datalog with Equality: Finding nodes in a graph that are part of both a directed triangle and a directed rectangle:

  • $\text{InTriangle}(x) \leftarrow \text{Edge}(x, y), \text{Edge}(y, z), \text{Edge}(z, x)$.

  • $\text{InRectangle}(x) \leftarrow \text{Edge}(x, y), \text{Edge}(y, z), \text{Edge}(z, w), \text{Edge}(w, x)$.

  • $\text{InBoth}(x) \leftarrow \text{InTriangle}(x), \text{InRectangle}(y), x = y$.

• Semantics and Least Fixpoint (LFP): The standard LFP semantics can be reused with a slight extension to the definition of rule satisfaction by a mapping.

  • Consistent Mappings: A mapping or homomorphism $\mu$ satisfies a rule only if it is consistent with the equalities. Specifically, $\mu(x) = \mu(y)$ must hold if $x = y$ is an atom in the rule body.

  • Existence of LFP: The LFP semantics is always defined. Repeatedly applying the immediate-consequence operator ($T_P$) will always lead to a fixpoint, using the same logic as Datalog without equalities.

• Expressive Power comparison:

  • Proposition: Every query expressible in standard Datalog is expressible in Datalog with equalities (trivial proof).

  • Equivalence: Every query expressible in Datalog with equalities is also expressible in standard Datalog.

  • Proof Strategy for Eliminating Equalities:

    1. If a query is unsatisfiable, replace it with a non-satisfiable program without equalities.

    2. For $x = c$, substitute all occurrences of variable $x$ in the rule with constant $c$.

    3. For $x = y$, substitute all occurrences of variable $x$ in the rule with variable $y$.

    4. If an equality results in $c = d$ (two different constants), remove the entire rule.

    5. Equalities of the form $c = c$ are redundant and can be removed.

  • Corollary: Datalog and Datalog with equalities possess identical expressive power.

Datalog with Non-Equality

• Definition: Datalog can be extended with non-equality atoms in the rule bodies.

  • Expressions of the form $x \neq y$ (variables $x, y$).

  • Expressions of the form $x \neq c$ (variable $x$, constant $c$).

• Safety: As with equalities, all variables in non-equality atoms must appear in regular body atoms.

• Example: Find nodes in a directed triangle where all three nodes are distinct:

  • $\text{Answer}(x) \leftarrow \text{Edge}(x, y), \text{Edge}(y, z), \text{Edge}(z, x), x \neq y, y \neq z, x \neq z$.

• Semantics: The mapping $\mu$ must satisfy $\mu(x) \neq \mu(y)$ if $x \neq y$ is a body atom. The LFP semantics remains defined as the immediate-consequence operator is still inflationary.

• Expressivity Gap: Datalog with non-equalities is strictly more expressive than Datalog.

  • Proof: Datalog queries are preserved under homomorphisms. However, queries with non-equalities are not necessarily preserved.

  • Counter-example instance: Let graph $D = \{E(a, b), E(b, c), E(c, a)\}$ and $D' = \{E(a, a)\}$. There is a homomorphism $h : (D, a) \rightarrow (D', a)$. In $D$, node $a$ is in a triangle of distinct nodes, so $(a) \in q(D)$. In $D'$, node $a$ is only in a self-loop, so $(a) \notin q(D')$. Since the result is not preserved, the query cannot be expressed in standard Datalog.

Datalog with Negation (Datalog ⁻)

• Definition: Allows the use of the negation operator ($\neg$) over atoms in rule bodies.

• Safety Requirement: Every variable appearing in a negated atom must also appear in at least one non-negated (positive) atom in the same rule body.

• Example Program:

  • $\text{Reachable}(x) \leftarrow \neg\text{Edge}("s", x), N(x)$.

  • $\text{Reachable}(x) \leftarrow \text{Reachable}(y), \neg\text{Edge}(y, x), N(x), N(y)$.

• Fixpoint Semantics ($T_P$): The operator $T_P$ over database $D$ produces:

  1. All facts originally in $D$.

  2. Facts $R(a)$ produced by a rule where a valuation maps positive atoms to facts in $D$ and negated atoms to facts not in $D$.

• Termination: The process always terminates on a finite database because $T_P$ is inflationary (the set of facts only grows) and no new constants are introduced (the domain is limited to $\text{Dom}(D, P)$).

Semi-Positive Datalog⁻

• Definition: A Datalog⁻ program is semi-positive if negation is applied only to EDB (Extensional Database) atoms (i.e., predicates that only appear in the input and never in the head of a rule).

• Examples:

  • "Reachability over complement graph" is semi-positive.

  • "Non-reachability" (negation of an IDB) is not semi-positive.

• Properties:

  • Semi-positive programs have a unique minimal model, and the fixpoint operator correctly identifies it.

  • Expressivity: Strictly more expressive than Datalog. While Datalog is monotone, semi-positive Datalog is not (e.g., adding an edge to a complement graph might remove a result).

• Construction to Positive Datalog: Any semi-positive program $P$ and database $D$ over schema $S$ can be converted to an equivalent positive Datalog program $P'$ and database $D'$:

  1. Create a copy $R^-$ for every relation $R$ in $S$.

  2. Replace $\neg R(x)$ in $P$ with $R^-(x)$.

  3. Populate $D(R^-)$ with all tuples in the domain $\text{Dom}(D)^k$ that are not in $D(R)$.

  4. Result: $P(D) = P'(D')$.

• Semi-Monotonicity: A query $q$ is semi-monotone if $q(I) \subseteq q(I \cup J)$ provided that the new facts in $J$ involve at least one constant not in the original domain $\text{Dom}(P, D)$.

  • Intuition: In a graph, a monotone query result remains if we add edges. A semi-monotone result remains if we add edges, as long as we don't add edges between nodes that already existed in the original graph.

Stratified Datalog

• Definition: A stratification is a sequence of programs $P_1, \dots, P_n$ that partitions program $P$.

• Rules for Stratification (Given mapping $\sigma$ from IDB predicates to strata indices $[1, n]$):

  1. All rules defining an IDB predicate $R$ must belong to the same stratum $P_{\sigma(R)}$.

  2. If IDB $R$ depends on a positive atom $S$, then $\sigma(S) \le \sigma(R)$.

  3. If IDB $R$ depends on a negated atom $S$, then $\sigma(S) < \sigma(R)$.

• Semantics: Stratified Datalog evaluates each stratum sequentially using fixpoint semantics. The results of lower strata ($P_{i}$) are treated as EDB facts for higher strata ($P_{i+1}$).

• Key Proposition: A program may have multiple valid stratifications, but they all yield the same final semantic result.

• Logic of Stratification Example (Non-Reachability):

  • Stratum 1: Compute $\text{Reachable}(x)$ (positive recursion).

  • Stratum 2: Compute $\text{NotReachable}(x) \leftarrow \neg\text{Reachable}(x), N(x)$ (negation of result from Stratum 1).

Comparison of Model-Theoretic and LFP Semantics

• Discrepancy: Unlike standard Datalog, for Datalog with negation, the LFP and model-theoretic semantics do not coincide.

• Counter-example: Let database $D = \{Q(0)\}$ and program $P$:

  • $R(0) \leftarrow Q(0), \neg R(1)$.

  • $R(1) \leftarrow Q(0), \neg R(0)$.

• Evaluation:

  • LFP result ($T_P(D)$): $\text{Includes } \{Q(0), R(0), R(1)\}$.

  • Minimal Models: $\text{Model}_1 = \{Q(0), R(0)\}$ and $\text{Model}_2 = \{Q(0), R(1)\}$.

  • Since $T_P(D)$ contains both $R(0)$ and $R(1)$, it is not a minimal model. The model-theoretic semantics is ambiguous (multiple minimal models), whereas LFP is deterministic but not minimal.