How to Set Up Datalog Reasoning with Recursive Rules in Semantica

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, 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.

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.

# 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.

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

The output includes every original and inferred fact:

# ['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.

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】.

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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}