# How to Perform Recursive Queries (Transitive Closure) with Semantica’s DatalogReasoner

> Learn to perform recursive queries like transitive closure using Semantica's DatalogReasoner. Add facts and rules, then compute results with a bottom-up semi-naive fix-point algorithm.

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

---

**Use the `DatalogReasoner` class from `semantica.reasoning` to add base facts and recursive Horn-clause rules, then call `derive_all()` to compute the transitive closure via a bottom-up semi-naive fix-point algorithm.**

Semantica provides a native Datalog engine that enables recursive inference over knowledge graphs and relational data. The `DatalogReasoner` implements a bottom-up semi-naive evaluation strategy to efficiently compute transitive closure and other recursive queries by iteratively applying rules until no new facts are derived. This guide explains the engine's architecture and demonstrates how to implement recursive rules using the actual source code from the `semantica-agi/semantica` repository.

## How the Semi-Naive Fix-Point Engine Works

### Fact Storage and Indexing

The engine stores ground facts in `_fact_index`, a predicate-indexed structure that enables O(1) lookup during rule evaluation. According to the implementation in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) (lines 52-54), this indexing maintains both the master fact set (`_all_facts`) and separate delta sets for incremental evaluation. This separation allows the algorithm to distinguish between previously derived facts and newly discovered facts in each iteration.

### Rule Representation and Delta Processing

Rules are represented as `DatalogRule` objects containing a head predicate, head arguments, and a list of `BodyAtom` instances (lines 30-35). The `derive_all()` method implements the semi-naive algorithm by maintaining two delta sets: `_delta_new` (recently derived facts) and `_delta_old` (previously processed facts). Each iteration shifts the delta and builds a temporary index to avoid redundant computation (lines 42-58 and 60-68). The loop terminates when `_delta_new` is empty, guaranteeing convergence on finite graphs.

### Rule Application and Unification

The `_apply_rule()` method (lines 95-112) handles the actual inference. When `is_seminaive` is enabled, the engine uses the delta index for exactly one body atom position (the "delta position"), ensuring O(1) delta lookup rather than re-scanning the entire fact database. The `_unify()` method (lines 84-115) implements standard Datalog unification where variables start with uppercase letters, while `_instantiate_fact()` (lines 131-138) converts variable bindings into concrete ground facts.

## Writing Recursive Rules for Transitive Closure

To compute transitive closure, define recursive Horn-clause rules where the head predicate appears in the body. The engine evaluates these bottom-up: starting with base facts, it repeatedly applies rules to derive new facts until reaching a fix-point. Because the algorithm is **semi-naive**, it only considers combinations involving at least one newly derived fact in each iteration, significantly improving performance over naive evaluation.

## Practical Examples for Recursive Queries

### Ancestor Hierarchy (Classic Transitive Closure)

This example implements the canonical recursive pattern for hierarchical relationships:

```python
from semantica.reasoning import DatalogReasoner

dl = DatalogReasoner()

# Base facts

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

# Recursive rules

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

# Derive everything

derived = dl.derive_all()
print("Derived facts:", derived)

# → includes: ancestor(tom, bob), ancestor(bob, ann), ancestor(tom, ann)

# Query the closure

print(dl.query("ancestor(tom, ?Y)"))

# → [{'Y': 'bob'}, {'Y': 'ann'}]

```

The recursive rule is handled by the semi-naive loop in `derive_all()` (lines 62-69), which automatically chains the `parent` relationships to derive `ancestor` facts across arbitrary depths.

### Multi-Hop Graph Reachability

For arbitrary directed graphs, use edge facts with a recursive `reachable` predicate:

```python
from semantica.reasoning import DatalogReasoner

dl = DatalogReasoner()
edges = ["edge(1,2)", "edge(2,3)", "edge(3,4)"]
for e in edges:
    dl.add_fact(e)

dl.add_rule("reachable(X, Y) :- edge(X, Y).")
dl.add_rule("reachable(X, Y) :- edge(X, Z), reachable(Z, Y).")

print(dl.derive_all())

# → reachable(1,4) appears as part of the transitive closure

```

The engine automatically computes all reachable node pairs by repeatedly applying the recursive rule until the transitive closure stabilizes.

### Loading Facts from a ContextGraph

You can also populate the reasoner from an existing knowledge graph:

```python
from semantica.reasoning import DatalogReasoner

# Assuming a ContextGraph instance named 'my_graph'

dl = DatalogReasoner()
dl.load_from_graph(my_graph)  # Converts graph edges to Datalog facts

dl.add_rule("invested_transitive(X, Y) :- invested_in(X, Y).")
dl.add_rule("invested_transitive(X, Y) :- invested_in(X, Z), invested_transitive(Z, Y).")

print(dl.derive_all())

# → Computes transitive closure of investment relationships

```

The `load_from_graph()` method converts `ContextGraph` structures into ground facts, enabling recursive reasoning over existing knowledge bases without manual fact entry. This integration is documented in both the reference guide ([`docs/reference/reasoning.md`](https://github.com/semantica-agi/semantica/blob/main/docs/reference/reasoning.md)) and the reasoning tutorial ([`docs/guides/reasoning.md`](https://github.com/semantica-agi/semantica/blob/main/docs/guides/reasoning.md)).

## Summary

- Use `DatalogReasoner` from `semantica.reasoning` to perform recursive queries via bottom-up evaluation
- The engine employs a **semi-naive fix-point algorithm** that iteratively applies rules using delta indexing for O(1) lookup performance
- Define recursive rules by including the head predicate in the rule body (e.g., `ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y)`)
- Call `derive_all()` to compute the transitive closure, then use `query()` to retrieve specific variable bindings
- Source implementation resides in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) with core logic in `derive_all()` (lines 42-68) and `_apply_rule()` (lines 95-112)

## Frequently Asked Questions

### What algorithm does Semantica's DatalogReasoner use for recursive queries?

The engine implements a **bottom-up semi-naive fix-point algorithm** as defined in `derive_all()` (lines 42-68). This approach maintains delta sets (`_delta_new` and `_delta_old`) to track recently derived facts, applying rules incrementally until no new facts are produced. The semi-naive strategy avoids redundant computation by indexing deltas separately and only considering new bindings in each iteration, as opposed to recomputing all possible inferences from scratch.

### How do I query the results after computing transitive closure?

Invoke the `query()` method with a pattern containing variables (prefixed with `?` or uppercase letters). For example, `dl.query("ancestor(tom, ?Y)")` returns a list of binding dictionaries like `[{'Y': 'bob'}, {'Y': 'ann'}]`. This method reuses the same unification logic as the rule engine (lines 44-71) to match patterns against the derived fact set stored in `_fact_index`.

### Can I load existing graph data into the DatalogReasoner?

Yes, use the `load_from_graph()` method to import facts from a `ContextGraph` instance. This method automatically converts graph nodes and edges into ground Datalog facts, allowing you to apply recursive rules like transitive closure without manual fact insertion. The functionality is demonstrated in the test suite at [`tests/reasoning/test_datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/tests/reasoning/test_datalog_reasoner.py).

### What is the time complexity of recursive evaluation in Semantica?

The semi-naive evaluation achieves **O(1) delta lookup** per rule application by using the delta index for exactly one body atom position in `_apply_rule()` (lines 95-112). While the overall complexity depends on the number of derived facts and rule arity, the algorithm guarantees termination on finite graphs and avoids the quadratic redundancy of naive evaluation by only processing newly derived facts in each iteration of the `while self._delta_new:` loop.