Deterministic Reasoning Engines in Semantica: Forward Chaining, Rete, Datalog, and Temporal Logic

Semantica ships with five pure-Python deterministic reasoning engines—Reasoner (forward/backward chaining), ReteEngine, SPARQLReasoner, DatalogReasoner, and TemporalReasoningEngine—that guarantee identical outputs for identical inputs by avoiding stochastic LLM calls and relying on fixed algorithmic evaluation.

The semantica-agi/semantica repository implements a modular knowledge-graph framework where reproducible inference is foundational. These deterministic engines reside under semantica/reasoning and implement stable, rule-based logic ranging from classic production systems to Allen-interval temporal algebra, ensuring auditability and consistent behavior across runs.

Core Deterministic Engines in semantica.reasoning

All deterministic engines share a common trait: they operate on immutable facts and explicit rule priorities, producing the same inference trace every time. Below are the five engines guaranteed to behave deterministically according to the source code.

1. Reasoner (Forward and Backward Chaining)

The Reasoner class in semantica/reasoning/reasoner.py provides general-purpose IF/THEN rule evaluation with fix-point convergence. It supports both forward chaining (data-driven inference) and backward chaining (goal-driven proof search), iterating until no new facts are derived.

from semantica.reasoning import Reasoner, Rule, RuleType

r = Reasoner()
r.add_fact("Manager(Alice)")
r.add_fact("Employee(Alice)")

r.add_rule(
    Rule(
        rule_id="r001",
        name="manager_authority",
        conditions=["Manager(?x)", "Employee(?x)"],
        conclusion="HasAuthority(?x)",
        rule_type=RuleType.IMPLICATION,
        confidence=1.0,
    )
)

# Forward chaining – deterministic fix-point

for inf in r.forward_chain():
    print(inf.conclusion)   # → HasAuthority(Alice)

# Backward chaining – deterministic proof search

proved = r.backward_chain("HasAuthority(Alice)")
print(proved.conclusion if proved else "Not provable")

Rule evaluation order is stabilized by an explicit priority attribute (higher values execute first), eliminating non-determinism from hash-order variations.

2. ReteEngine (High-Throughput Pattern Matching)

Located in semantica/reasoning/rete_engine.py, the ReteEngine implements the Rete algorithm for efficient matching of large fact bases against complex rule patterns. It builds a discrimination network that shares nodes across rules, ensuring deterministic, high-performance inference.

from semantica.reasoning import ReteEngine, Fact

engine = ReteEngine()
engine.build_network([
    # rule definitions in the Rete DSL (or use Rule objects)

])
engine.add_fact(Fact(fact_id="f1", predicate="PortScan", arguments=["10.0.0.5"]))
matches = engine.match_patterns()
results = engine.execute_matches(matches)
print(results)

The Rete network topology is constructed deterministically from the rule set, guaranteeing that the same fact insertions always trigger the same agenda of rule firings.

3. SPARQLReasoner (RDF/OWL Rule Inference)

The SPARQLReasoner class in semantica/reasoning/sparql_reasoner.py enables deterministic rule expansion on RDF/OWL graphs using SPARQL CONSTRUCT queries. It treats SPARQL patterns as Horn-clause bodies and constructs new triples as heads, iterating to a fix-point.

from semantica.reasoning import SPARQLReasoner

sparql = SPARQLReasoner()
sparql.add_fact({
    "subject": "ex:Alice",
    "predicate": "rdf:type",
    "object": "ex:Manager"
})

# Add a SPARQL rule (as a CONSTRUCT query)

sparql.add_rule("""CONSTRUCT { ?x ex:hasAuthority true } WHERE { ?x a ex:Manager }""")
inferred = sparql.infer_results()
print(inferred)

Because SPARQL evaluation against a static graph is deterministic, the inferred triples are fully reproducible across executions.

4. DatalogReasoner (Horn-Clause Logic)

Implemented in semantica/reasoning/datalog_reasoner.py, the DatalogReasoner evaluates recursive Horn-clause rules using a semi-naïve fix-point algorithm. It guarantees termination for stratified negation and delivers deterministic query results for recursive ancestry, transitive closure, and aggregation tasks.

from semantica.reasoning import DatalogReasoner

dl = DatalogReasoner()
dl.add_fact("parent(john, mary)")
dl.add_fact("parent(mary, susan)")

# Recursive rule for ancestry

dl.add_rule("""
    ancestor(X, Y) :- parent(X, Y).
    ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).
""")
answers = dl.query("ancestor(john, X)")
print(list(answers))   # → ['mary', 'susan']

The engine stores derived facts in deterministic insertion order and prevents infinite loops via duplicate suppression, ensuring consistent output ordering.

5. TemporalReasoningEngine (Allen Interval Algebra)

The TemporalReasoningEngine in semantica/reasoning/temporal_reasoning.py implements the full set of 13 Allen interval algebra relations (before, meets, overlaps, finishes, etc.) for time-aware deterministic inference. It normalizes timestamps to specified granularities and computes relations through direct interval comparison.

from semantica.reasoning import TemporalReasoningEngine
from datetime import datetime

engine = TemporalReasoningEngine()
a = engine.normalize_interval(
    "2024-01-01T00:00:00Z", "2024-06-01T00:00:00Z", granularity="month"
)
b = engine.normalize_interval(
    "2024-03-01T00:00:00Z", "2024-09-01T00:00:00Z", granularity="month"
)

print(engine.relation(a, b))          # → "overlaps"

print(engine.contains(b, a))          # → False

print(engine.active_at(a, datetime(2024, 4, 15)))  # → True

All temporal calculations are pure Python math on datetime objects, eliminating any source of randomness in interval relations.

Architectural Guarantees of Determinism

Semantica enforces deterministic behavior across all reasoning engines through three implementation strategies visible in the source:

• Content-Addressed Fact Storage – Facts are hashed using MD5 digests (see semantica/context/entity_linker.py), ensuring that identical fact content receives identical internal identifiers.
• Explicit Rule Prioritization – Rules are sorted by a numeric priority field before evaluation, preventing arbitrary execution order.
• Fix-Point Termination – Engines iterate until a global "no new facts" condition is met, detected via deterministic set comparisons rather than timeouts or random sampling.

Contrast with Non-Deterministic GraphReasoner

For completeness, Semantica also provides GraphReasoner in semantica/reasoning/graph_reasoner.py. This engine forwards queries to an external LLM for natural-language reasoning over the knowledge graph. Because LLM outputs are stochastic and temperature-dependent, GraphReasoner is explicitly non-deterministic and is excluded from the deterministic suite.

Summary

• Reasoner – General forward/backward chaining with priority-ordered rules in semantica/reasoning/reasoner.py.
• ReteEngine – High-performance pattern matching via the Rete algorithm in semantica/reasoning/rete_engine.py.
• SPARQLReasoner – Deterministic RDF/OWL inference through SPARQL CONSTRUCT in semantica/reasoning/sparql_reasoner.py.
• DatalogReasoner – Semi-naïve evaluation of recursive Horn clauses in semantica/reasoning/datalog_reasoner.py.
• TemporalReasoningEngine – Allen-interval temporal logic in semantica/reasoning/temporal_reasoning.py.

All five engines guarantee repeatable inference traces suitable for regulatory auditing, unit testing, and reproducible research.

Frequently Asked Questions

What distinguishes the Reasoner from the ReteEngine?

The Reasoner evaluates rules sequentially and is optimized for clarity and backward chaining, while the ReteEngine builds a shared discrimination network to process large rule bases efficiently. Both are deterministic, but Rete offers better performance when thousands of rules and facts intersect.

Can DatalogReasoner handle recursive queries safely?

Yes. The DatalogReasoner uses a semi-naïve fix-point algorithm that evaluates recursive Horn clauses (e.g., transitive closure) until no new facts are derived. This guarantees termination for stratified programs and produces deterministic results identical across runs.

Why is GraphReasoner considered non-deterministic?

GraphReasoner delegates inference to an external large language model (LLM). Because LLM outputs vary with temperature settings and model state, the same query may return different conclusions on successive invocations, violating the deterministic contract required by the other engines.

How does TemporalReasoningEngine manage interval granularity?

The engine normalizes all timestamps to a user-specified granularity (e.g., "month", "day") before applying Allen algebra relations. This normalization occurs in semantica/reasoning/temporal_reasoning.py and ensures that interval comparisons are deterministic regardless of input precision.

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