# How Semantica's Datalog Reasoner Handles Recursive Rule Evaluation: A Bottom-Up Fixpoint Deep Dive

> Learn how Semantica's Datalog reasoner handles recursive rule evaluation with its bottom-up semi-naive fixpoint algorithm, optimizing computation by using only new facts per iteration.

- Repository: [Semantica /semantica](https://github.com/semantica-agi/semantica)
- Tags: deep-dive
- Published: 2026-08-20

---

**Semantica's Datalog engine evaluates recursive Horn-clause rules using a bottom-up semi-naive fixpoint algorithm that minimizes redundant computation by processing only newly derived facts each iteration.**

The `semantica-agi/semantica` repository provides a native Datalog reasoner designed for efficient inference over knowledge graphs. Understanding how this system handles recursive rule evaluation is essential for building performant semantic applications. This article examines the implementation in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py), breaking down the data structures, algorithmic optimizations, and termination guarantees that enable scalable recursive reasoning.

## Core Data Structures for Datalog Evaluation

The Datalog reasoner operates on two fundamental abstractions defined in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) lines 18-35:

- **`DatalogFact`** – Represents grounded atomic statements (e.g., `parent(alice, bob)`)
- **`DatalogRule`** – Encodes Horn clauses with a head atom and a body list of `BodyAtom` objects

Facts are indexed by predicate in `_fact_index`, enabling efficient lookups during rule application. Rules maintain their body as an ordered list, which the engine exploits during semi-naive evaluation to identify which position corresponds to the "delta" relation in each iteration.

## Semi-Naive Fixpoint Algorithm Implementation

The `derive_all()` method (lines 59-86) implements the core recursive evaluation strategy. This approach avoids the quadratic blow-up of naive evaluation by tracking only incremental changes between iterations.

### Delta Set Management

The algorithm maintains two critical delta sets:

- **`_delta_old`** – Facts derived in the previous iteration
- **`_delta_new`** – Facts discovered in the current iteration

Each iteration performs three operations (lines 69-72):
1. Shift `_delta_new` → `_delta_old`
2. Clear `_delta_new` for fresh accumulation
3. Build `delta_index` from `_delta_old` for indexed access

### Rule Application with Selective Scanning

The `_apply_rule()` method (lines 110-124) implements the semi-naive optimization. For each rule body atom:

- **One delta-position atom** scans only `_delta_old` facts (the incremental input)
- **All other atoms** scan the full `_fact_index` (the accumulated knowledge base)

This selective scanning ensures recursive rules like `ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z)` only evaluate the recursive `ancestor` atom against newly discovered ancestors from the previous round, not the entire transitive closure.

### Unification and Instantiation

Variable bindings flow through two helper methods:
- **`_unify()`** – matches body atoms against facts, producing substitution maps
- **`_instantiate()`** – applies substitutions to head atoms, generating concrete `DatalogFact` instances

Newly instantiated facts are deduplicated against `_all_facts` before insertion into `_delta_new` and the global fact set.

## Handling Recursive Rules Naturally

Recursive rule evaluation emerges automatically from the fixpoint structure. Consider transitive closure:

```python
from semantica.reasoning.datalog_reasoner import DatalogReasoner

# Initialize the engine

datalog = DatalogReasoner()

# Add base facts

datalog.add_fact("parent(alice, bob)")
datalog.add_fact("parent(bob, charlie)")

# Add recursive rules for ancestry

datalog.add_rule("ancestor(X, Y) :- parent(X, Y).")
datalog.add_rule("ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).")

# Derive the closure (semi-naive fixpoint)

all_facts = datalog.derive_all()
print(all_facts)

# → ['parent(alice, bob)', 'parent(bob, charlie)', 

#    'ancestor(alice, bob)', 'ancestor(bob, charlie)',

#    'ancestor(alice, charlie)']

```

In the first iteration, only `ancestor(alice, bob)` and `ancestor(bob, charlie)` derive from the non-recursive rule. The second iteration discovers `ancestor(alice, charlie)` by combining `parent(alice, bob)` with the newly derived `ancestor(bob, charlie)` from `_delta_old`. The third iteration yields no new facts, triggering termination.

## Termination Guarantees

The algorithm guarantees termination on finite knowledge graphs (lines 85-86). Two properties ensure this:

- **Finite fact space** – The underlying graph contains finitely many constants and predicates
- **Monotonic growth with deduplication** – Each iteration adds only previously unseen facts to `_all_facts`

When `_delta_new` empties, the loop exits. The maximum iteration count is bounded by the number of derivable ground facts, which is finite for stratified Datalog.

## Query Integration

The `query()` method (lines 44-51) provides pattern-based retrieval with automatic derivation. If rules exist but `derive_all()` hasn't been called, `query()` triggers the fixpoint computation lazily:

```python

# Query after derivation (or rely on automatic triggering)

results = datalog.query("ancestor(alice, ?descendant)")
print(results)

# → [{'descendant': 'bob'}, {'descendant': 'charlie'}]

```

Query patterns support variable placeholders (e.g., `?descendant`) that unify against the derived fact set.

## Summary

- **Bottom-up semi-naive evaluation** processes recursive rules efficiently by tracking delta sets between iterations in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py)
- **Selective scanning** in `_apply_rule()` restricts one body atom per rule to delta facts only, avoiding redundant inferences
- **Automatic termination** occurs when no new facts are derived, guaranteed for finite knowledge graphs
- **Lazy query execution** triggers `derive_all()` automatically when needed, simplifying the API

## Frequently Asked Questions

### What is semi-naive evaluation in Datalog?

**Semi-naive evaluation is an optimization that avoids re-deriving facts across iterations by processing only the "delta" (newly derived) facts from the previous round.** In Semantica's implementation, this means each rule body has exactly one atom scanned against `_delta_old` while others scan the full fact index. This reduces complexity from quadratic to linear in the number of derivable facts for many common recursive patterns.

### How does Semantica handle left-recursive rules?

**Left-recursive rules (where the recursive predicate appears first in the body) are handled identically to right-recursive rules due to the semi-naive delta rotation.** The engine determines which body position receives delta treatment based on iteration state, not rule syntax. For `ancestor(X, Z) :- ancestor(X, Y), parent(Y, Z)`, the first `ancestor` atom would be delta-scanned in appropriate iterations, with correct results achieved regardless of body ordering.

### Can the reasoner handle mutually recursive predicates?

**Yes, mutual recursion (e.g., `a` depends on `b` and `b` depends on `a`) resolves naturally through the global delta set mechanism.** All predicates share `_delta_old` and `_delta_new` across iterations. When `a` derives new facts, they enter the delta for the next round where `b` can consume them, and vice versa. The fixpoint captures the simultaneous least fixed point of both predicates.

### What happens if I add facts after calling derive_all()?

**Adding facts invalidates the previous fixpoint; you must call `derive_all()` again to derive new consequences.** The current implementation does not incrementally maintain derived facts—`derive_all()` performs complete recomputation from the current `_all_facts` base. For production use cases requiring frequent updates, consider batching fact additions or implementing custom incremental maintenance atop the core engine.