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

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 (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:

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:

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:

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) and the reasoning tutorial (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 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.

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.

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