« Phase 07 · Warmup · Track Overview

Deep Dive — Mechanism & Internals

Table of Contents

• 1. Three indexes, and why
• 2. The boolean return that makes reasoning terminate
• 3. The rule set, rule by rule
• 4. Why the fixed point is reached, and in how many rounds
• 5. SHACL's evaluation order
• 6. SPARQL as a fold over bindings
• 7. The path walker
• 8. A traced entailment and query
• 9. Invariants, complexity, determinism

1. Three indexes, and why

self._spo: Dict[IRI,  Dict[IRI,  Set[Term]]]   # subject   → predicate → objects
self._pos: Dict[IRI,  Dict[Term, Set[IRI]]]    # predicate → object    → subjects
self._osp: Dict[Term, Dict[IRI,  Set[IRI]]]    # object    → subject   → predicates

Three because match() can be called with any subset of positions bound, and each index makes a different subset cheap:

The lab's match picks the most selective available index by checking subject, then predicate, then object — and then re-filters on the remaining bound positions, because the chosen index only narrows one of them.

Real stores go further. Jena's TDB2 and most others maintain six permutations (SPO, POS, OSP, SOP, PSO, OPS) so that every binding pattern has a covering index. Three is the pragmatic subset: it covers every pattern the lab's reasoner and query engine actually issue, which is worth knowing because the reasoner's inner loops are exactly match(predicate=…) and match(subject=…).

The memory cost is real — three indexes over the same data — and it is why triple stores are memory-hungry relative to the size of the source data. Add a materialized closure on top and a graph can be several times its input.

2. The boolean return that makes reasoning terminate

def add(self, subject, predicate, obj) -> bool:
    triple = Triple(subject, predicate, obj)
    if triple in self._triples:
        return False
    ...
    return True

That bool is not a convenience. It is the fixed-point signal:

added = 0
added += graph.add(...)      # bool sums as 0/1
...
if added == 0:
    break

Without it, the reasoner would need to compare the whole graph before and after each round — \( O(N) \) per round in space and time — or it would loop forever. Returning "was this new" turns termination detection into free arithmetic.

It also depends on Triple being hashable and value-comparable, which is why every term type is a frozen dataclass. Make IRI mutable and set membership breaks silently, taking termination with it.

3. The rule set, rule by rule

Nine rules, each named for the RDFS/OWL entailment rule a reviewer will recognise.

rdfs11 — subClassOf is transitive.

?a rdfs:subClassOf ?b .  ?b rdfs:subClassOf ?c .   ⟹   ?a rdfs:subClassOf ?c .

Runs first, so the class hierarchy is fully closed before rdfs9 propagates types through it. Order does not change the result (a fixed point is a fixed point) but it changes the number of rounds, and putting the hierarchy closure first is what gets the lab to 3 rounds instead of more.

rdfs9 — type propagates up.

?x rdf:type ?a .  ?a rdfs:subClassOf ?b .   ⟹   ?x rdf:type ?b .

rdfs5 — subPropertyOf is transitive. The property-hierarchy mirror of rdfs11.

rdfs7 — a sub-property's assertions are the super-property's.

?p rdfs:subPropertyOf ?q .  ?x ?p ?y .   ⟹   ?x ?q ?y .

This is half of the ownership headline: majorityOwns assertions become controls assertions.

Note the guard if not isinstance(sub.object, IRI): continue. A malformed ontology could declare rdfs:subPropertyOf with a literal object; using it as a predicate would corrupt the graph. Cheap check, real protection.

rdfs2 / rdfs3 — domain and range confer types.

?p rdfs:domain ?c .  ?x ?p ?y .   ⟹   ?x rdf:type ?c .
?p rdfs:range  ?c .  ?x ?p ?y .   ⟹   ?y rdf:type ?c .      (only if ?y is an IRI)

The range rule has the literal guard, and it is the one people get wrong. A literal is never a subject, so "Acme Trading FZE" rdf:type xsd:string is not a legal triple — the lab tests that no such triple appears.

owl:inverseOf — both directions.

?p owl:inverseOf ?q .  ?x ?p ?y .   ⟹   ?y ?q ?x .
?p owl:inverseOf ?q .  ?x ?q ?y .   ⟹   ?y ?p ?x .

Both, because inverseOf is itself symmetric in meaning and the ontology only asserts it once. Implementing only the first direction is a subtle bug: controlledBy assertions would not produce controls ones.

owl:TransitiveProperty — the composition rule.

?p rdf:type owl:TransitiveProperty .  ?x ?p ?y .  ?y ?p ?z .   ⟹   ?x ?p ?z .

This is the other half of the headline, and note that it only fires after rdfs7 has produced the controls triples — which is why the fixed point needs more than one round.

owl:SymmetricProperty. Straightforward, with the same IRI guard.

4. Why the fixed point is reached, and in how many rounds

Termination. Every rule only adds triples, and every added triple is built from terms already in the graph. The reachable vocabulary is finite, so the set of derivable triples is finite, and a monotonically growing subset of a finite set converges. The max_rounds guard is a backstop against a rule bug, not the termination argument.

Round count. Each round applies every rule once over the whole graph, so a derivation needing \( k \) dependent steps completes in at most \( k \) rounds. In the lab:

The lab reports 3 rounds and 22 derived triples, and the third round exists only to prove there is nothing left. That is why test_materialization_reaches_a_fixed_point asserts the second call adds zero in one round: the first call already reached the fixed point, so the second detects it immediately.

Semi-naive evaluation is the standard optimization: only consider triples derived in the previous round, since a rule firing on old triples produced its output already. The lab is naive (it re-scans everything each round) because the naive version is legible and the graphs are small. At scale the difference is large, and knowing the name is the point.

5. SHACL's evaluation order

for shape in shapes:
    for focus in graph.subjects(RDF_TYPE, target_class):
        for prop in shape.properties:
            values = graph.objects(focus, path)
            # 1. cardinality
            # 2. per value: node kind → datatype → pattern → in

Target selection reads rdf:type from the graph, which after materialization includes entailed types. That is the interaction between the two halves of the phase, and reversing the order (validate then materialize) silently skips every node whose type was inferred. The lab tests it directly: the same graph and shape conform before materialization and fail after.

Cardinality before value checks, because a minCount failure is about the absence of values and the per-value loop has nothing to iterate.

continue after a node-kind or datatype failure. A value that is a literal where an IRI was required should produce one error, not also a pattern-match failure on a value whose type is already wrong. Same reasoning as the JSON-Schema validator in Phase 02 — error lists are read by humans and by repair loops, and noise lowers the success rate of both.

Severity is applied at report level, not at check level. Every constraint produces a result; conforms is not any(severity is VIOLATION). That separation is what lets you ship a shape as a Warning, measure how much of the corpus fails it, and promote it to Violation once the data is clean — an operationally important pattern, because a new shape that blocks ingestion on day one gets disabled rather than fixed.

Closed shapes compare each of the node's predicates against the declared paths plus ignored_properties plus rdf:type. rdf:type is always allowed because forbidding it would make every closed shape unsatisfiable — the shape targets a class, which requires a type triple.

6. SPARQL as a fold over bindings

bindings = [{}]                       # one empty solution
for element in query.where:
    if isinstance(element, Pattern):   bindings = _join(graph, bindings, element)
    elif isinstance(element, Optional_): bindings = _left_join(...)
    elif isinstance(element, Filter):  bindings = [b for b in bindings if element.fn(b)]

The whole engine is a left fold over the WHERE clause, carrying a list of partial solutions. Three observations:

The initial [{}] is load-bearing. Starting with an empty list would make every query return nothing, because there is nothing to extend. Starting with a list containing one empty binding means the first pattern is unconstrained and generates all its matches.

Shared variable names are the join condition. In _join, _resolve looks up each term in the current binding: if ?owner is already bound, the pattern is matched with that value fixed; if it is free, every match extends the binding. There is no join clause because variable identity is the condition — which is the thing to understand about SPARQL, and once seen the rest is syntax.

This is a nested-loop join with no reordering, and the order of patterns in the WHERE clause determines cost. Putting the most selective pattern first can change a query from milliseconds to minutes. A real engine has a planner that reorders using cardinality estimates; the lab does not, which is why PRINCIPAL-DEEP-DIVE treats query planning as the thing a production engine actually sells you.

_left_join runs the OPTIONAL block's patterns as an inner join starting from each binding, and keeps the original binding when the block produces nothing:

out.extend(extended if extended else [binding])

That one line is the entire semantics of OPTIONAL, and getting it wrong — returning extended unconditionally — turns a left join into an inner join and silently deletes rows.

Projection shortens IRIs, stringifies literals and maps unbound variables to "". The empty string rather than None keeps the output shape uniform for a caller, and the lab's OPTIONAL test asserts on exactly that.

7. The path walker

def _walk(graph, step, subject, obj) -> List[Tuple[Term, Term]]

Returns every (start, end) pair reachable by the step, so _join can bind either or both ends.

Unbound starts. With no bound subject, the starts are every subject of the predicate — or every object, when the step is inverse. Getting that branch wrong makes ^p with a free subject return nothing, which looks like missing data.

+ and * are breadth-first with a visited set:

ends = []
if step.modifier == "*":
    ends.append(start)                     # zero-length path
frontier, seen = [start], ({start} if step.modifier == "*" else set())
while frontier:
    current = frontier.pop(0)
    for nxt in one_hop(current):
        if nxt in seen: continue
        seen.add(nxt); ends.append(nxt); frontier.append(nxt)

Two subtleties:

The seen set is initialized differently for * and +. For *, the start is already in ends and must be in seen so it is not added twice. For +, the start is not in ends, and must not be in seen — otherwise a cycle back to the start would be suppressed, and A controls+ A in a two-node cycle would be wrong. The lab tests exactly this: in a cycle, A is reachable from A by controls+.

Without the visited set, a cycle does not terminate. Circular shareholdings are legitimate corporate structures, not pathological data, so this is a correctness requirement rather than a defensive nicety.

Cost. _walk is \( O(V + E) \) per start via BFS, and with an unbound subject it runs once per possible start — \( O(V(V+E)) \). For a transitive path over a large graph that is the expensive operation in the engine, which is why real stores either materialize transitivity (as the lab's OWL reasoner does) or index the closure.

8. A traced entailment and query

Asserted (the relevant subset):

Opaque    majorityOwns  Sanctioned
Meridian  controlledBy  Sanctioned          ← note: the inverse direction
Meridian  majorityOwns  Northgate
Northgate majorityOwns  Acme
majorityOwns rdfs:subPropertyOf controls
controls  rdf:type      owl:TransitiveProperty
controls  owl:inverseOf controlledBy

Round 1:

Round 2: transitivity composes over round-1 output — Sanctioned controls Acme, Opaque controls Northgate, Opaque controls Acme.

Round 3: nothing new. Fixed point at 22 derived triples.

The chain Opaque → Acme is four hops and required three distinct mechanisms: a sub-property rule, an inverse rule, and transitivity — composing across two rounds. That is the argument for an ontology in one example: application code doing this by hand would be a recursive traversal with three special cases, and it would be wrong.

Then the query:

SELECT ?owner WHERE {
  ?owner bank:controls+ ent:Acme .
  ?owner bank:onSanctionsList true .
}

Note that the second pattern is a filter in effect, because its subject is already bound. Putting it first would be far cheaper — one match, then a single-start walk. The lab's engine does not reorder, and that is precisely the gap a real query planner fills.

9. Invariants, complexity, determinism

Invariants (each tested):

1. Adding a duplicate triple returns False and changes nothing.
2. A second materialize adds zero triples in one round.
3. Entailment is monotone: an unrelated addition never removes a prior conclusion.
4. A literal never receives a type from rdfs:range.
5. Materialization terminates on a cycle, and A controls+ A holds there.
6. Opaque controls Acme is entailed across four hops and three rule kinds.
7. A Warning violation leaves conforms true.
8. A node typed only by entailment is validated.
9. OPTIONAL retains a row whose optional variable is unbound; the required form drops it.
10. p* includes the start; p (exact) does not transit.
11. A full IRI is not parsed as a CURIE.
12. Every query and every report is deterministic across runs.

Complexity:

The two that do not scale are the naive reasoner (semi-naive evaluation is the fix) and the unplanned join order (a cost-based planner is the fix). Both are deliberate: they are exactly what a production triple store sells you, and building the naive version is how you understand what it is selling.

Determinism. Every accessor sorts — triples(), match(), objects(), subjects(), _walk() — and execute sorts its projected rows by order_by (defaulting to the select list). Validation results sort by (focus_node, path, message). No clock, no RNG, no set-iteration order leaking into output. Two runs, or two machines, produce byte-identical results, which is what makes the tests equality assertions.