# How DatalogReasoner Handles Recursive Ancestor Queries in Semantica

> Learn how Semantica's DatalogReasoner efficiently handles recursive ancestor queries with a bottom-up semi-naive fix-point algorithm and delta indexing for optimized computation.

- Repository: [Semantica /semantica](https://github.com/semantica-agi/semantica)
- Tags: how-to-guide
- Published: 2026-08-17

---

**Semantica's `DatalogReasoner` evaluates recursive ancestor queries using a bottom-up semi-naive fix-point algorithm that iteratively derives new facts through delta indexing until reaching closure, ensuring termination on finite graphs while avoiding redundant computations.**

The `DatalogReasoner` class in the Semantica framework provides a native Datalog engine optimized for transitive closure computations like ancestral relationships. When processing recursive ancestor queries, the implementation in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) employs a semi-naive evaluation strategy that extends classic bottom-up reasoning by ensuring each iteration considers only newly derived facts. This approach guarantees deterministic termination while efficiently materializing recursive rule applications across arbitrary graph depths.

## Semi-Naive Fix-Point Evaluation Architecture

### Rule Parsing and Initial Setup

When you invoke `add_rule()` with a recursive definition such as `ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y)`, the engine parses the string into a `DatalogRule` object via `_parse_rule_string` (lines 47-75). This method decomposes the rule into head and body atoms, establishing the logical structure required for subsequent unification operations against the fact base.

### The Derivation Loop in derive_all

The `derive_all` method (lines 60-68) implements the core fix-point computation. It initializes `_delta_new` with existing facts and enters an iterative cycle that continues until no new facts emerge. During each iteration, the engine moves `_delta_new` to `_delta_old` and rebuilds the `delta_index` to track recently derived facts. This delta-based approach distinguishes semi-naive evaluation from naïve strategies by focusing computational resources exclusively on novel derivations rather than recomputing established relationships.

### Delta Indexing and Rule Application

Within `_apply_rule` (lines 94-112), the engine evaluates whether to apply semi-naive optimization (`is_seminaive = delta_index is not None`). For recursive ancestor queries, this method generates evaluation paths where exactly one body atom matches against the delta index while others query the complete fact base (`self._fact_index`). This constraint ensures that each recursive step extends the ancestry chain by exactly one generation per iteration, preventing redundant recomputation of already-established ancestor relationships.

## Processing Recursive Ancestor Rules

Recursive ancestor resolution relies on the transitive property encoded in two complementary rules: a base case (`ancestor(X, Y) :- parent(X, Y)`) and a recursive case (`ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y)`). When `derive_all` executes, newly derived `ancestor` facts populate `_delta_new`, becoming the delta input for the subsequent iteration. This creates a cascading effect where each loop discovers grandparents, great-grandparents, and deeper lineage relationships until the graph reaches saturation.

The unification process occurs through `_unify`, which attempts to match rule patterns against concrete fact arguments. Successful bindings trigger `_instantiate_fact` to generate ground `DatalogFact` objects that join the global fact set. Because the engine operates on finite ground facts, the strictly increasing cardinality of `_all_facts` guarantees eventual termination when `_delta_new` empties, signaling fix-point achievement.

## Practical Implementation Example

The following example demonstrates the complete workflow for establishing and querying recursive ancestry:

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

# Initialize the reasoner

r = DatalogReasoner()

# Insert base parent facts

r.add_fact("parent(tom, bob)")
r.add_fact("parent(bob, ann)")

# Define recursive ancestor rules

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

# Execute semi-naive fix-point evaluation

all_facts = r.derive_all()
print(sorted(all_facts))

# Output: ['ancestor(bob, ann)', 'ancestor(tom, ann)', 'ancestor(tom, bob)', 

#          'parent(bob, ann)', 'parent(tom, bob)']

# Query for all descendants of tom

results = r.query("ancestor(tom, ?Y)")
print([row["Y"] for row in results])

# Output: ['bob', 'ann']

```

The `query` method (lines 44-52) automatically triggers `derive_all` if unevaluated rules exist, then matches patterns against `self._fact_index[pred]` to return variable bindings. This lazy evaluation ensures the fact base remains current without redundant computation. The same pattern appears in the repository's test suite ([`tests/reasoning/test_datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/tests/reasoning/test_datalog_reasoner.py)), confirming the expected transitive closure behavior.

## Summary

- **Semi-naive evaluation** in `derive_all` ensures each iteration processes only newly derived facts through delta indexing, eliminating redundant work characteristic of naïve bottom-up approaches.
- **Recursive rule application** in `_apply_rule` generates evaluation paths that require at least one body atom to match recent delta facts, guaranteeing progress toward closure while handling arbitrary recursion depths.
- **Deterministic termination** occurs when `_delta_new` empties, indicating the finite fact base has reached a fix-point with all possible ancestor relationships materialized.
- **Source implementation** resides in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py), with comprehensive test coverage in [`tests/reasoning/test_datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/tests/reasoning/test_datalog_reasoner.py) validating the engine's correctness on recursive queries.

## Frequently Asked Questions

### What algorithm does DatalogReasoner use for recursive queries?

Semantica's `DatalogReasoner` implements a bottom-up semi-naive fix-point algorithm. This approach iteratively derives new facts through delta indexing, ensuring that each round of computation only considers facts generated in the previous iteration, which prevents the redundant derivations common in naïve bottom-up evaluation while guaranteeing termination on finite domains.

### How does the engine prevent infinite loops during recursive evaluation?

The engine guarantees termination by operating strictly on finite sets of ground facts. Each iteration adds newly derived facts to `_all_facts`, and the loop in `derive_all` terminates when `_delta_new` contains no new entries. Since the input domain is finite and each iteration strictly increases fact cardinality until saturation, the algorithm must reach a fix-point where no additional ancestor relationships can be discovered.

### Can DatalogReasoner handle arbitrary recursive predicate definitions?

Yes, the implementation in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) supports arbitrary recursion through the `_apply_rule` method (lines 94-112). The evaluation path generation ensures that recursive predicates appearing in rule bodies receive proper delta indexing, allowing transitive closure computations for any stratified or linear recursive definition, including multi-hop ancestor relationships.

### What is the performance characteristic of semi-naive evaluation compared to naïve evaluation?

Semi-naive evaluation significantly reduces computational overhead by restricting each iteration to facts involving at least one newly derived tuple. While naïve evaluation recomputes all possible derivations in every round, the delta indexing strategy in `DatalogReasoner` ensures work complexity scales linearly with the number of new derivations rather than quadratically with the size of the intermediate fact base.