# How to Implement Recursive Datalog Queries in Semantica: A Complete Guide

> Learn to implement recursive Datalog queries in Semantica using the DatalogReasoner and bottom-up semi-naive fixpoint evaluation for deep graph analysis.

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

---

**Use `DatalogReasoner` with bottom-up semi-naive fixpoint evaluation to execute recursive Horn-clause rules on arbitrarily deep graph structures.**

The Semantica library provides a native Datalog engine that handles recursive queries—such as transitive closure and reachability—without requiring manual recursion management. This article explains how to implement recursive Datalog queries in Semantica using the [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) implementation, covering data structures, rule syntax, and the semi-naive evaluation algorithm that guarantees termination.

## Core Architecture of Semantica's Datalog Engine

Semantica's `DatalogReasoner` implements recursive Horn-clause evaluation through three interconnected components: fact storage, rule processing, and fixpoint iteration.

### Data Structures

Facts and rules use distinct internal representations:

- **`DatalogFact`** — Stores a predicate name plus a tuple of constant arguments (e.g., `parent("alice", "bob")`)
- **`DatalogRule`** — Contains a head predicate/arguments and a list of `BodyAtom` objects representing the rule body
- **`_all_facts`** — The complete set of derived facts
- **`_fact_index`** — Predicate-indexed structure for O(1) lookup of facts by predicate name

These structures enable efficient unification during recursive evaluation.

### Adding Facts and Rules

The engine accepts multiple input formats through `add_fact` and `add_rule`:

```python
from semantica.reasoning import DatalogReasoner

dl = DatalogReasoner()

# String form (simplest for literals)

dl.add_fact("parent(alice, bob)")

# Alternative: dictionary or DatalogFact objects

dl.add_fact({"predicate": "parent", "args": ["bob", "charlie"]})

# Recursive Horn-clause rules

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

```

The second rule demonstrates left-recursion—the engine handles this automatically through fixpoint computation.

## Semi-Naive Fixpoint Evaluation

The `derive_all` method implements **bottom-up semi-naive evaluation**, the standard algorithm for terminating recursive Datalog execution.

### How the Algorithm Works

1. **Initialization** — `_delta_new` copies the current fact set
2. **Iteration** — On each round:
   - `_delta_new` moves to `_delta_old`
   - New facts are computed **only from the delta** of the previous iteration (via `delta_index`)
   - `_apply_rule` unifies body atoms against facts from either the full index or the delta
3. **Termination** — When an iteration produces no new facts, the fixpoint is reached

This semi-naive approach avoids redundant work: facts derived in iteration *n* cannot contribute to new derivations until iteration *n+1*, and only the delta (not all historical facts) is scanned.

### Key Implementation Details

In [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py):

- `_apply_rule` generates candidate variable bindings through unification
- New derived facts are added to `_all_facts` and become the next `_delta_new`
- The process **guarantees termination** on finite graphs—no infinite loops

```python

# Execute recursive derivation

all_facts = dl.derive_all()
print(f"Total facts derived: {len(all_facts)}")

```

## Querying Recursive Predicates

After `derive_all` completes, use `query` with variable patterns:

```python

# Variable syntax: ?prefix or uppercase letters

results = dl.query("ancestor(alice, ?Z)")
print(results)

# → [{'Z': 'bob'}, {'Z': 'charlie'}, {'Z': 'dave'}]

# Multiple variables

results = dl.query("ancestor(?X, ?Y)")

```

The `query` method **lazily invokes `derive_all`** if derivation hasn't run, ensuring results are always complete.

## Complete Implementation Example

```python
from semantica.reasoning import DatalogReasoner

# -------------------------------------------------

# 1. Initialize the reasoner

# -------------------------------------------------

dl = DatalogReasoner()

# -------------------------------------------------

# 2. Add base facts

# -------------------------------------------------

dl.add_fact("parent(alice, bob)")
dl.add_fact("parent(bob, charlie)")
dl.add_fact("parent(charlie, dave)")

# -------------------------------------------------

# 3. Define recursive rules

# -------------------------------------------------

dl.add_rule("ancestor(X, Y) :- parent(X, Y).")          # Base case

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

# -------------------------------------------------

# 4. Execute semi-naive fixpoint evaluation

# -------------------------------------------------

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

# Output includes all ancestor relationships at arbitrary depth:

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

# ancestor(bob, charlie), ancestor(bob, dave), ancestor(charlie, dave)

# -------------------------------------------------

# 5. Query the recursive predicate

# -------------------------------------------------

descendants = dl.query("ancestor(alice, ?Z)")
print("Alice's descendants:", [r["Z"] for r in descendants])

# → ['bob', 'charlie', 'dave']

# -------------------------------------------------

# 6. Reset and restart (optional)

# -------------------------------------------------

dl.clear()  # Removes all facts and rules

```

## Loading from ContextGraph

Integrate with Semantica's knowledge graph workflow:

```python
from semantica.graph import ContextGraph
from semantica.reasoning import DatalogReasoner

graph = ContextGraph.load_from_file("my_graph.json")

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

# Define reachability via recursion

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

dl.derive_all()
paths = dl.query("connected(start_node, ?dest)")

```

## Common Recursive Query Patterns

| Pattern | Rule Structure | Use Case |
|---------|---------------|----------|
| **Transitive closure** | `R(X,Z) :- R(X,Y), R(Y,Z).` | Reachability in graphs |
| **Same-generation** | `sg(X,Y) :- par(X,XP), par(Y,YP), sg(XP,YP).` | Finding cousins in family trees |
| **Predecessor chains** | `before(X,Z) :- before(X,Y), before(Y,Z).` | Temporal ordering |

All patterns execute correctly under semi-naive evaluation without risking non-termination.

## Summary

- **`DatalogReasoner`** in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) provides native recursive Datalog support
- **Semi-naive fixpoint evaluation** ensures efficient, terminating execution on finite data
- **Horn-clause syntax** supports both base cases and recursive rule definitions
- **Multiple input formats** (strings, dicts, objects) simplify fact and rule ingestion
- **Lazy derivation** via `query` automates fixpoint computation when needed

## Frequently Asked Questions

### What makes Semantica's Datalog engine suitable for recursive queries?

The `DatalogReasoner` implements **bottom-up semi-naive fixpoint evaluation**, which is the academically proven method for handling recursion in Datalog. According to the [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) source, this approach evaluates rules iteratively using only the "delta" of newly derived facts from each round, avoiding redundant computation while guaranteeing termination on finite graphs.

### How do I prevent infinite loops with recursive rules?

You don't need manual safeguards. The semi-naive algorithm in `derive_all` automatically terminates when no new facts are produced in an iteration. Because the fact set is finite and monotonically growing, the fixpoint is always reached. The `_delta_new` and `_delta_old` mechanism ensures progress: each iteration must contribute new facts or stop.

### Can I use variables without the `?` prefix in queries?

Yes. The `query` method accepts two variable conventions: `?Z` (explicit prefix) or uppercase identifiers like `X` or `Dest` (Datalog convention). Both `dl.query("ancestor(alice, ?Z)")` and `dl.query("ancestor(alice, Z)")` return identical results. The parser detects variables by case and prefix in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py).

### Where is the recursive query functionality tested?

The test suite in [`tests/reasoning/test_datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/tests/reasoning/test_datalog_reasoner.py) validates recursive inference correctness, including transitive closure scenarios and multi-level derivations. These tests confirm that the semi-naive implementation matches expected theoretical behavior for recursive Horn-clause programs.