# How to Set Up Datalog Reasoning with Recursive Rules in Semantica

> Learn how to set up Datalog reasoning with recursive rules in Semantica. Use bottom-up semi-naive fix-point algorithm to define rules and derive complete closures.

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

---

**Semantica's `DatalogReasoner` implements a bottom-up semi-naive fix-point algorithm that lets you define recursive Horn-clause rules over ground facts, derive the complete closure with `derive_all()`, and query results using pattern unification.**

Semantica, an open-source reasoning framework from `semantica-agi/semantica`, ships a native **Datalog engine** designed for recursive rule evaluation without external solvers. Whether you are computing transitive closures or multi-hop ancestor graphs, the engine handles fix-point iteration automatically. This guide walks through the exact API and source-level mechanics you need to set up Datalog reasoning with recursive rules.

## How the Datalog Engine Works

Understanding the internal data structures makes it easier to reason about performance and correctness when writing recursive rules.

### Fact Storage and Indexing

In [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py), the `DatalogReasoner` class maintains two primary structures. The `_fact_index` is a `defaultdict(set)` that maps each predicate name to the set of `DatalogFact` objects for fast predicate-level lookup. The `_all_facts` attribute is a master `set` containing every fact, both user-added and derived, which prevents duplicates.

When you call `add_fact`, the engine parses either a string such as `parent(tom, bob)` or a Semantica node/edge dictionary and inserts a validated `DatalogFact` into the index. The validation logic rejects empty arguments or variables in ground facts, ensuring that only concrete terms enter the base fact set【/semantica/reasoning/datalog_reasoner.py#L70-L110】.

### Rule Parsing and Representation

Rules are supplied as Horn-clause strings. The `_parse_rule_string` method, defined around lines 47–75 of the same module, extracts the head predicate and a list of body atoms represented as `BodyAtom` objects. Each atom stores its predicate and argument tuple, which the evaluator later joins against the fact indexes【/semantica/reasoning/datalog_reasoner.py#L47-L75】.

### Semi-Naive Fix-Point Evaluation

The core reasoning loop lives in `derive_all`. The method repeatedly:

1. Copies the current fact set into `_delta_new`.
2. Shifts the delta so `_delta_old` references the previous batch while `_delta_new` is emptied.
3. Builds a temporary index for the old delta.
4. Walks every rule and calls `_apply_rule`.

Inside `_apply_rule`, the engine uses the **semi-naive** strategy: for each rule, exactly one body atom is evaluated against the delta (the newest facts), while the remaining atoms unify against the full fact index. This limits redundant work to facts that changed in the previous iteration and guarantees termination on finite graphs【/semantica/reasoning/datalog_reasoner.py#L95-L140】.

### Unification and Fact Instantiation

Variable binding is handled by `_unify`, which matches rule variables—by the Datalog convention that variables start with an uppercase letter—to concrete fact arguments and builds a binding map【/semantica/reasoning/datalog_reasoner.py#L80-L115】. Once every body atom succeeds, `_instantiate_fact` creates a concrete head fact and adds it to the evolving fact set.

After the fix-point is reached, `derive_all` returns all facts, original and derived, as strings. For querying, the `query(pattern, bindings={})` method optionally runs `derive_all` first, parses the query pattern, substitutes any pre-bound variables, and unifies the pattern against the fact index, returning a list of variable bindings【/semantica/reasoning/datalog_reasoner.py#L44-L85】.

## Setting Up Recursive Datalog Reasoning

With the mechanics in mind, the setup process is straightforward: initialize the reasoner, add ground facts, define base and recursive rules, run the derivation, and query the results.

### Initialize the Reasoner and Add Ground Facts

Start by importing `DatalogReasoner` and asserting base facts as strings or dictionaries.

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

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

```

Because `add_fact` stores each `DatalogFact` in `_fact_index` and deduplicates via `_all_facts`, duplicate insertions are safely ignored.

### Define Base and Recursive Rules

Rules follow standard Datalog syntax with a head, `:-` separator, and a body of atoms. Provide a **base case** and a **recursive case** to build transitive relations.

```python

# Base case

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

# Recursive case

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

```

The parser converts each string into a structured `DatalogRule` with a head predicate and a list of `BodyAtom` instances, preparing them for semi-naive evaluation.

### Run the Fix-Point Derivation

Call `derive_all` to evaluate all rules against the delta indexes until no new facts are produced.

```python
derived = r.derive_all()
print("Derived facts:", derived)

```

The output includes every original and inferred fact:

```python

# ['parent(tom, bob)', 'parent(bob, ann)', 'ancestor(tom, bob)',

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

```

### Query the Derived Facts

After derivation, use `query` with variables to retrieve specific bindings. Variable names in the query must start with an uppercase letter or use the `?` prefix.

```python
results = r.query("ancestor(tom, ?Y)")
print([row["Y"] for row in results])   # → ['bob', 'ann']

```

The query engine parses the pattern, substitutes any pre-bound entries from the optional `bindings` argument, and unifies against `_fact_index`, returning a list of matching substitution maps.

### Load Facts from a Semantica Graph

If your data already lives in a Semantica `ContextGraph` or any object exposing `find_edges` and `find_nodes`, use `load_from_graph` to bulk-import facts without manual string construction【/semantica/reasoning/datalog_reasoner.py#L104-L130】.

```python
class SimpleGraph:
    def __init__(self):
        self._edges = [
            {"source": "alice", "target": "bob", "type": "manages"},
            {"source": "bob", "target": "carol", "type": "manages"}
        ]

    def find_edges(self):
        return self._edges

    def find_nodes(self):
        return []

g = SimpleGraph()
r.load_from_graph(g)

r.add_rule("transitive_manages(X, Y) :- manages(X, Y).")
r.add_rule("transitive_manages(X, Y) :- manages(X, Z), transitive_manages(Z, Y).")

print(r.derive_all())

# → includes 'transitive_manages(alice, carol)'

```

Because `load_from_graph` converts each edge and node into ground `DatalogFact` objects, the transition from graph representation to recursive Datalog reasoning is seamless.

## Summary

- **`DatalogReasoner`** in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) provides a pure-Python Datalog engine with no external dependencies.
- Facts are indexed in **`_fact_index`** and deduplicated via **`_all_facts`**, while `add_fact` validates ground terms and rejects variables or empty arguments.
- Rules are parsed by **`_parse_rule_string`** into head predicates and `BodyAtom` lists; recursive rules are fully supported.
- **`derive_all`** executes a **semi-naive** fix-point loop through `_apply_rule`, evaluating one delta body atom per iteration to avoid redundant work.
- **`query`** supports pattern unification with optional pre-bound variables against the full derived fact set.
- **`load_from_graph`** bridges Semantica `ContextGraph` structures and the Datalog fact base for transitive-closure and reachability tasks.

## Frequently Asked Questions

### What algorithm does Semantica use for Datalog evaluation?

Semantica uses a **bottom-up semi-naive fix-point algorithm**. The `derive_all` method iteratively applies every rule to newly derived facts until the global fact set stabilizes, at which point the engine has reached a fix-point.

### How does the semi-naive strategy improve performance?

In `_apply_rule`, the engine selects exactly one body atom to evaluate against the delta index while the remaining atoms match the full fact index. This restriction ensures that only facts produced in the previous iteration drive new derivations, which dramatically reduces redundant unification on large fact sets.

### Can I load facts directly from a Semantica graph?

Yes. The `load_from_graph` method accepts any object implementing `find_edges` and `find_nodes`, such as a Semantica `ContextGraph`. It walks the structure and converts each edge and node into a ground `DatalogFact`, enabling you to run recursive rules like transitive closure directly on graph data.

### What happens if I add a duplicate fact or an invalid rule?

The `add_fact` method silently ignores duplicates because the master `_all_facts` set tracks every inserted fact. It also validates inputs and rejects strings that contain variables or empty arguments, since ground facts must consist entirely of concrete terms before rule evaluation begins.