How to Perform Datalog Evaluation with Semantica: A Complete Guide

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

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

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:

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

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:

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:

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

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