Reasoning is easy when you're only adding data. The hard part comes when you delete something.
Consider this scenario:
# Ontology :Dog rdfs:subClassOf :Animal . # Data :rex a :Dog . # Inferred (by reasoner) :rex a :Animal .
Now you delete the triple :rex a :Dog. What happens to the inferred triple :rex a :Animal?
:rex a :Dog
:rex a :Animal
This is the retraction problem — knowing which inferences to retract when their supporting evidence is removed. Each triplestore handles it differently, and it's one of the most important architectural decisions in reasoning systems.
How it works: Delete ALL inferred triples, then re-run the entire reasoning process from scratch.
Before deletion: Base triples: 1,000,000 Inferred triples: 3,000,000 Total: 4,000,000 After deleting 1 triple: 1. Delete all 3,000,000 inferred triples 2. Re-run forward-chaining on 999,999 base triples 3. Materialize ~2,999,997 inferred triples 4. Total time: Same as initial reasoning
Pros:
Cons:
Used by: GraphDB (all versions)
How it works: Track dependencies between triples. When a base triple is deleted, only recompute the affected inferences.
The DRed (Delete/Rederive) algorithm (Gupta, Mumick, Subrahmanian, 1993) has three phases:
Phase 1: OVER-DELETE Identify all inferences that used the deleted triple Pessimistically delete them all (some may be over-deleted) Phase 2: REDERIVE For each deleted inference, check if it can be re-derived from remaining base triples via alternative reasoning paths If yes → restore it Phase 3: NET RESULT Only truly unsupported inferences remain deleted
Example:
# Ontology :Dog rdfs:subClassOf :Animal . :Pet rdfs:subClassOf :Animal . # Data :rex a :Dog . :rex a :Pet . # Inferred :rex a :Animal . (supported by BOTH :Dog→:Animal AND :Pet→:Animal)
When you delete :rex a :Dog:
:rex a :Pet
:Pet rdfs:subClassOf :Animal
Used by: RDFox (Oxford Semantic Technologies)
How it works: Don't materialize inferences at all. Instead, rewrite SPARQL queries at execution time to account for reasoning rules.
-- User writes: SELECT ?x WHERE { ?x a :Animal } -- Stardog internally rewrites to: SELECT ?x WHERE { { ?x a :Animal } UNION { ?x a :Dog } -- because :Dog rdfs:subClassOf :Animal UNION { ?x a :Cat } -- because :Cat rdfs:subClassOf :Animal UNION { ?x a :Pet } -- because :Pet rdfs:subClassOf :Animal -- ... for all known subclasses }
:rex
:Dog
Used by: Stardog
RDF Studio currently uses the same strategy as GraphDB — re-reason from scratch:
# When ontology is edited: 1. Load the full ontology graph (TBox) 2. Run owlrl over the entire graph 3. Compute diff: new inferences = (reasoned graph) - (original graph) 4. Display inferred triples in the UI
This is perfectly appropriate because:
When RDF Studio adds instance data reasoning (ABox), full recomputation may become too slow:
For Phase 2, a Rust-based DRed implementation would:
This matches the approach used by the Oxigraph reasoner fork (see "The Oxigraph Reasoner Fork" topic) and RDFox.
For those who want to understand the internals:
Dependency Graph: inferred_triple → Set[Set[base_triple]] Each inferred triple has one or more "support sets" Each support set is a minimal set of base triples that justify the inference An inferred triple is valid if ANY of its support sets is complete
function delete(triple): remove triple from base_triples // Phase 1: Over-delete affected = { t ∈ inferred | triple ∈ any_support_set(t) } for each t in affected: remove t from inferred_triples // Cascade: t may support other inferences affected += { u ∈ inferred | t ∈ any_support_set(u) } // Phase 2: Rederive for each t in affected (in dependency order): if can_derive(t, base_triples ∪ inferred_triples): restore t to inferred_triples update support_sets(t)
Consider:
A → B (rule 1) A → C (rule 2) B ∧ C → D (rule 3)
If A is deleted:
But what if B was also supported by another base fact E?
Without the over-delete phase, you might miss cascading effects and leave stale inferences behind.