# How to Perform Datalog Evaluation with Semantica: A Complete Guide

> Learn how to perform Datalog evaluation using Semantica's native Datalog engine. This guide explains the bottom-up semi-naive fixpoint algorithm for Horn-clause rules.

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

---

**Semantica ships a native Datalog engine (`DatalogReasoner`) that evaluates Horn‑clause rules using a bottom‑up semi‑naive fixpoint algorithm.**

Semantica is an open‑source knowledge representation framework that includes a high‑performance Datalog reasoner for logical inference. The `DatalogReasoner` class in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) provides everything needed to perform **Datalog evaluation** over facts and rules, enabling recursive querying and multi‑hop reasoning within the Semantica ecosystem.

## Setting Up the DatalogReasoner

To begin Datalog evaluation, import and instantiate the reasoner:

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

r = DatalogReasoner()

```

The constructor initializes empty fact and rule indices, as well as delta structures used during fixpoint computation.

## Representing Facts and Rules

### Adding Facts with `add_fact`

Facts are represented by the immutable `DatalogFact` dataclass, which stores a predicate name and a tuple of arguments. According to lines 18‑35 of [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py), the `add_fact` method accepts two input formats:

- **String format**: `"parent(tom,bob)"`
- **Dictionary format**: `{"subject": "bob", "predicate": "parent", "object": "ann"}`

As implemented in lines 70‑84, the method parses the input, validates that all arguments are ground constants (no uppercase variables), and stores the fact in `_fact_index` for O(1) lookup:

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

```

### Defining Rules with `add_rule`

Rules follow Horn‑clause syntax with a head and body. The `add_rule` method receives strings such as `"ancestor(X,Y) :- parent(X,Y)."` and parses them using `_parse_rule_string`. According to the source (lines 47‑75), each body atom becomes a `BodyAtom` tuple within the `DatalogRule` structure:

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

```

## Semi-Naive Fixpoint Evaluation

### The `derive_all` Method

The `derive_all` method initiates bottom‑up evaluation using the **semi‑naive fixpoint algorithm**. As shown in lines 42‑60 and 62‑85 of [`datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/datalog_reasoner.py), the engine maintains two delta sets:

- **`_delta_old`**: Facts from the previous iteration
- **`_delta_new`**: Newly derived facts from the current iteration

On each iteration, the engine evaluates every rule against the delta facts (the newly derived facts from the previous round), allowing efficient incremental computation rather than re‑evaluating against the entire database. The loop continues until no new facts are generated, at which point the engine marks the program as derived and returns all facts as strings:

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

# Output includes: ancestor(tom, ann)

```

### Rule Application with `_apply_rule`

The `_apply_rule` method (lines 95‑131) implements the core semi‑naive strategy. For each rule, it selects one body atom to match against the delta index, unifies variable bindings using `_unify`, and instantiates the head atom to produce new facts. This selective delta‑matching avoids redundant work while ensuring completeness.

## Querying Derived Facts

The `query` method accepts patterns like `"ancestor(tom, ?Y)"` and returns variable bindings. As implemented in lines 44‑82, it automatically invokes `derive_all` if the knowledge base has not yet been evaluated. The method unifies the pattern against the fact index and returns a list of dictionaries mapping queried variable names to their ground bindings:

```python
answers = r.query("ancestor(tom, ?Y)")
print([a["Y"] for a in answers])

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

```

## Integrating with ContextGraph

The `load_from_graph` method bridges Semantica’s graph representation with Datalog reasoning. As defined in lines 104‑126, it traverses any object exposing `find_edges` and `find_nodes` (such as `ContextGraph`), converting each edge and node into facts via `add_fact`:

```python
class SimpleGraph:
    def __init__(self):
        self._nodes = [{"id": "microsoft", "type": "company"}]
        self._edges = [{"source": "microsoft", "target": "openai", "type": "invested_in"}]
    def find_nodes(self): return self._nodes
    def find_edges(self): return self._edges

g = SimpleGraph()
r.load_from_graph(g)  # Adds invested_in(microsoft, openai) and company(microsoft)

print(r.derive_all())

```

## Summary

- **DatalogReasoner** provides a complete Datalog engine within Semantica, located at [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py).
- **Facts** are stored as `DatalogFact` objects via `add_fact`, supporting both string and dictionary syntax with ground constant validation.
- **Rules** are parsed from Horn‑clause strings into `DatalogRule` structures containing `BodyAtom` tuples.
- **Evaluation** uses a semi‑naive fixpoint algorithm that incrementally processes `_delta_new` facts until saturation.
- **Queries** support variable binding patterns and automatically trigger derivation if the knowledge base is not yet saturated.
- **Graph integration** via `load_from_graph` enables reasoning over existing `ContextGraph` data without manual fact conversion.

## Frequently Asked Questions

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

Semantica implements a **bottom‑up semi‑naive fixpoint algorithm**. The `derive_all` method in [`semantica/reasoning/datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/datalog_reasoner.py) maintains delta sets (`_delta_old` and `_delta_new`) to incrementally evaluate rules against newly derived facts rather than the entire database, ensuring efficient computation of the least fixpoint.

### How do I add facts from a ContextGraph to the Datalog reasoner?

Use the `load_from_graph` method, which accepts any object implementing `find_nodes` and `find_edges` interfaces. As implemented in lines 104‑126, it automatically converts graph elements into ground facts and populates the reasoner’s `_fact_index`, enabling seamless Datalog reasoning over Semantica’s native graph structures.

### Can the DatalogReasoner handle recursive rules?

Yes. The semi‑naive evaluation engine fully supports recursive predicates. The test suite in [`tests/reasoning/test_datalog_reasoner.py`](https://github.com/semantica-agi/semantica/blob/main/tests/reasoning/test_datalog_reasoner.py) demonstrates multi‑hop inference through recursive rules such as transitive closure (`ancestor`), where the fixpoint loop continues until no new facts are derived.

### How does the query method handle variables?

The `query` method accepts patterns containing variables prefixed with `?` (e.g., `"ancestor(tom, ?Y)"`). According to lines 44‑82 of the source, it unifies the pattern against stored facts and returns a list of dictionaries mapping variable names (without the `?` prefix) to their ground constant bindings, handling both bound and unbound variables transparently.