Knowledge graph truth maintenance: retracting conclusions

Executive Summary

Knowledge graph truth maintenance is the maintenance of conclusions supported by currently admitted assertions under a declared reasoning regime. A correct withdrawal must remove unsupported consequences while preserving conclusions with alternative grounding support. This does not certify that the admitted premises are true in the external world. Broekstra and Kampman's RDF work distinguishes asserted and derived facts and warns against circular self-justification; Doyle's foundational account emphasizes recording the reasons for program beliefs. ^{[1] [2]}

Deleting a stored triple, invalidating a provenance entity, and revising an earlier record are separate operations. SPARQL 1.1 Update, the W3C Recommendation of March 21, 2013, defines graph-store updates, while systems separately document their treatment of unsupported inferred statements. PROV-DM, recommended on April 30, 2013, defines entity invalidation. An accepted update request therefore cannot substitute for an inference acceptance test. ^{[3] [4] [5]}

This report supplies an original synthetic withdrawal fixture with independent supporting paths for Eligible and a single path for Traceable. It uses only the declared RDFS subclass instance-propagation rule, not full RDFS closure. Withdraw A: Eligible remains and Traceable disappears. Withdraw B next: neither remains. Reinstate A: both return. Reconstruct baseline: both conclusions and their earlier support paths return. The expected-output matrix and diagnostic ratios are reproducible calculations from the fixture, not field benchmarks. Provenance polynomials provide a formal precedent for representing alternative contributions to answers. ^[6]

Acceptance requires comparing observed targets with a fresh-reference result, checking surviving grounding paths, and testing historical explanations separately. Report unsupported retention and missing supported targets together; an empty output has an undefined retention ratio. Missing dependency information is unknown, not evidence of successful retraction, especially where derivation recording is optional. Query-time reasoning and materialization require different observation strategies, but the same declared answer-set oracle. Published algorithm research reports no universal winner, so correctness should be established before comparing workload-specific performance. ^{[7] [8]} (Source: docs.oxfordsemantic.tech) ^[9]

Introduction and Background

Knowledge graph maintenance becomes decision-relevant when a correction changes what a system can still justify. Removing a source assertion is straightforward to request. Establishing which conclusions remain entailed, which explanations have changed, and which earlier state can still be reproduced requires a more explicit contract. SPARQL 1.1 Update, a World Wide Web Consortium (W3C) Recommendation dated March 21, 2013, defines operations over a mutable graph store. The associated entailment specification leaves exact update behavior beyond simple entailment to system documentation. ^{[3] [10]}

The problem has a substantial intellectual history. Doyle (1979) describes a truth maintenance system as recording and maintaining reasons for program beliefs. His publication record identifies the original paper in Artificial Intelligence. Broekstra and Kampman (2003) apply dependency-sensitive maintenance to Resource Description Framework (RDF) reasoning and distinguish explicit assertions from derived statements. ^{[2] [11] [1]}

More recent research extends attention from inferred statements to explanations of query answers. Gaur, Bhattacharya and Bedathur (2020) study maintaining provenance polynomials for graph-pattern queries over changing knowledge graphs. Their scope is dynamic answer provenance; it should not be treated as a universal guarantee for every ontology language, rule engine, or historical-record system. ^[12]

This report proposes an observable acceptance test for context engineers and graph maintainers. The decision is whether an upstream withdrawal leaves the current derived graph defensible. The test evaluates output, surviving support, and historical reconstruction separately. It uses an explicitly restricted reasoning profile so that a reviewer can calculate expected answers without knowing the implementation.

The article's calculations are original, synthetic fixture calculations, not measurements of a production deployment. Product documentation is used to explain different observable contracts, not to rank implementations by speed. The test can be applied to a materializing engine, a query-time reasoner, or a surrounding application that controls which source assertions enter reasoning. Query-time inference is documented by Stardog, while RDFox documents precomputed materialization. ^[8] (Source: docs.oxfordsemantic.tech)

Definitions and the scope of truth maintenance

Knowledge graph truth maintenance means keeping accepted conclusions aligned with their currently admissible support under a declared reasoning regime. “Truth” here concerns entailment and accepted premises. The test does not establish that those premises are accurate descriptions of the external world. RDF semantics explicitly distinguishes entailment regimes, and OWL entailment concerns consequences that hold whenever the supporting statements hold. ^{[13] [14]}

The vocabulary for evaluation should be fixed before an update:

• Asserted triple: A subject, predicate, object statement admitted as input. An assertion can have a source-specific occurrence even when its RDF content duplicates another occurrence.
• Inferred triple: A statement obtained through the declared reasoning rules, rather than solely through direct input.
• Derivation: A rule application with its premises, potentially linked to other applications until it reaches admitted assertions.
• Alternative support: Another admissible derivation sufficient to establish the same conclusion after the first derivation disappears.
• Invalidation: An event affecting a provenance entity's availability for use, with the scope of that entity identified.
• As-of state: The assertions, rules, admissibility decisions, outputs, and explanations associated with a specified historical boundary.

The asserted/derived distinction follows Broekstra and Kampman's terminology. A triple can require more than a single status flag when both direct assertion and inference support it. The fixture below avoids that overlap initially and proposes an extension to test it separately. ^[1]

PROV-DM, the W3C provenance data model, defines invalidation as the start of an entity's destruction, cessation, or expiry. It describes derivation more broadly than a logical proof, including transformations and updates producing new entities. PROV expressly does not specify the conditions under which derivations exist. Consequently, a provenance link can identify lineage without proving that a conclusion still follows. ^[5]

Belief revision addresses a different question when the desired change concerns a conclusion rather than an input occurrence. Alchourrón, Gärdenfors and Makinson (1985) study contraction that eliminates a proposition and revision that introduces one. Their partial-meet account considers maximal subsets that fail to imply the proposition being contracted. Deleting one selected premise is not equivalent to requiring a conclusion to become underivable. ^[15]

Classical truth maintenance also admits different representations of reasons and assumptions. Reiter and de Kleer's foundational analysis relates traditional truth maintenance systems to restricted clause management systems. The present acceptance test deliberately does not require that representation: it requires reproducible observations and sufficient evidence for the support claims being accepted. ^[16]

Absence must be interpreted with the same care. Under the open-world assumption described in the Web Ontology Language (OWL) primer, a missing fact can still be true. After withdrawal, “not derivable from this admitted graph” therefore does not mean “false in reality.” Report the former unless an explicit negative assertion or a separately declared closed-world rule establishes the latter. ^[14]

What a withdrawal changes

Delete a stored assertion

A DELETE DATA request operates on specified graph contents. SPARQL Update says deletion applies when those graphs contain the supplied triples. These are storage-operation semantics. They do not, by themselves, establish an application's treatment of derived answers or source eligibility. ^[3]

Attempting to delete an entailed statement is especially ambiguous. The recommendation notes that a delete operation may try to remove entailed statements without actual effects. RDFox similarly documents deletion of explicit input triples and distinguishes removal of derived triples as a belief-revision or view-update problem. A successful request is therefore insufficient evidence that an inferred conclusion has disappeared. ^[3] (Source: docs.oxfordsemantic.tech)

The update scope must match the inference scope. A query service and an update service need not expose identical graph sets under SPARQL Update. An evaluator should record exactly which named graphs were changed and which graphs the reasoning query reads. A graph-name mismatch can invalidate the test setup before any retraction algorithm is evaluated. ^[3]

Withdraw a source occurrence or invalidate an entity

A source correction concerns the admissibility of particular evidence. RDF4J documents using contexts to record which files statements originated from and to replace statements when a file changes. Named graphs can group provenance-associated triples, as discussed in TripleProv. Neither mechanism, alone, specifies which query answers depend on which members of that group. ^{[17] [18]}

For the proposed test, withdrawing source A means removing A's admitted assertion occurrence from the reasoning input. It does not mean deleting every occurrence of the same RDF triple throughout the system. If a distinct source B still contributes that content, the content-level assertion may remain admitted. This occurrence-level distinction is a declared test policy, not an additional RDF entailment rule.

PROV invalidation has its own entity-relative meaning: the affected entity is no longer available for use. A retained document version, the live document it describes, and an assertion occurrence extracted from it should be distinguished in the test packet. Invalidating one does not automatically explain the intended treatment of the others.

Correct the present without rewriting the past

Historical evaluation needs explicit clocks. IBM's temporal-data guidance distinguishes system time, also called transaction time, from business time, also called valid time; bitemporal tables combine both. These definitions support asking separately what the system recorded and when the described information applied. The cited guidance supplies terminology, not a claim about current implementation features. ^[19]

A present withdrawal can coexist with a reproducible earlier accepted state. An as-of query must declare whether it asks for the record as previously known or a retrospective account using today's corrections. Those answers can differ. Standard belief-revision models do not themselves supply an explicit representation of time, so historical reproducibility should be tested as an additional property. ^[20]

The withdrawal manifest should specify:

• Affected occurrence: The exact source contribution being removed.
• Affected entity: The provenance entity, if an invalidation event is also recorded.
• Current admissibility: Whether the source content remains available for present reasoning.
• Historical boundary: Which committed or recorded state an as-of request selects.
• Correction meaning: Whether the correction changes recorded knowledge, described validity, or both.
• Reader view: The endpoint, graph selection, and permissions used to observe the outcome.

A reproducible withdrawal fixture (Hypothetical Example)

Declare the reasoning profile

The fixture uses RDF triples but applies only subclass instance propagation, corresponding to the RDFS entailment pattern commonly labeled rdfs9. Given x rdf:type C and C rdfs:subClassOf D, it derives x rdf:type D. W3C semantics states that a subclass extension is a subset of its superclass extension. ^[13]

This is a restricted positive rule profile, not full RDF Schema (RDFS) closure. Full RDFS reasoning includes other patterns and axiomatic consequences. The test deliberately projects onto the named target conclusions below and excludes other entailment rules, negation, equality reasoning, and anonymous existential consequences. An implementation running a broader regime must isolate this profile or provide a corresponding broader oracle. ^[13]

The frozen schema and admitted input are:

@prefix : <https://example.org/tm-test/> .
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

:schema {
  :Checked rdfs:subClassOf :Eligible .
  :Registered rdfs:subClassOf :Eligible .
  :Checked rdfs:subClassOf :Traceable .
}

:sourceA { :item rdf:type :Checked . }
:sourceB { :item rdf:type :Registered . }

The example is original test data. The declared reasoning input is the union of the schema and the currently admitted source graphs. Named graph membership records source contribution; it does not itself authorize a different rule. The only target derived statements are :item rdf:type :Eligible and :item rdf:type :Traceable.

Eligible has independent supporting paths through Checked and Registered. Traceable has only the Checked path. The retained schema is part of each derivation. Independence here means that the premise sets survive different source withdrawals within the fixture. It does not claim that two real documents have independent authorship or independent factual origins.

Identify the support structure

Let a denote the source-A input occurrence and b the source-B occurrence. With the schema fixed, the support expressions are Eligible = a + b and Traceable = a. This is an illustrative use of alternative-support notation. Green, Karvounarakis and Tannen's provenance semirings formalize polynomial annotations, including sums over derivation trees and products of input annotations. ^[6]

The authors' presentation explains provenance propagation through polynomials. The fixture uses the simpler Boolean interpretation: plus means an alternative sufficient path, and a path succeeds only when all its premises remain admitted. It does not require that the tested product internally store polynomials. ^[21]

For manual inspection, the expected proof paths are:

• Eligible through A: A's Checked assertion and Checked subclass Eligible.
• Eligible through B: B's Registered assertion and Registered subclass Eligible.
• Traceable through A: A's Checked assertion and Checked subclass Traceable.
• After A withdrawal: Only the B path remains sufficient for Eligible.
• After B withdrawal: Neither target has an admitted supporting path.
• After A reinstatement: Both target statements follow through A again.

Execute the update sequence

At baseline, admit both sources. Withdraw A, then withdraw B from that resulting state. Reinstate A while leaving B withdrawn. Finally reconstruct the baseline as-of state. These steps deliberately distinguish a changed current graph from historical replay.

For a store exposing the fixture graphs directly, the first request can be represented as:

PREFIX : <https://example.org/tm-test/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
DELETE DATA {
  GRAPH :sourceA { :item rdf:type :Checked . }
}

This request identifies the stored assertion to remove; the expected consequences come from the declared rule and remaining input, not from the request syntax alone. Official RDF4J documentation supplies a concrete example in which removal of a supporting input causes the inference layer to remove an inferred statement. That documented example is narrower than the acceptance sequence proposed here. ^[17]

Table 1 gives the original fixture's expected-output matrix. Counts describe target statements only. They exclude asserted input, schema triples, and consequences outside the declared projection.

The first row detects over-retraction and under-retraction simultaneously: Eligible must remain, and Traceable must disappear. The second row checks final loss of support. The third checks recovery. The last checks historical state selection, including explanations, rather than merely observing that reinstatement happens to produce the same target set.

Implementation guidance and the acceptance packet

Use a fresh reference calculation

The strongest oracle for this fixture is a fresh rebuild from the frozen schema and remaining admitted assertions. Compare its target set with the updated system's target set after each visible update boundary. This establishes output agreement without depending on the implementation's own dependency metadata.

Incremental maintenance has several documented strategies. Gupta, Mumick and Subrahmanian (1993) describe counting alternative derivations and a Delete and Rederive (DRed) algorithm that initially deletes a superset of affected tuples. Rederivation restores tuples that remain supported. Their counting description stores counts rather than complete derivations, which separates efficient maintenance information from a reviewer-readable explanation. ^[22]

Claims about counting must be qualified by the specific algorithm. Hu, Motik and Horrocks discuss conventional counting limited to nonrecursive rules and hybrid approaches supporting arbitrary Datalog programs. Motik and colleagues subsequently describe a counting algorithm handling recursive rules and an optimized DRed variant. “Counting cannot handle recursion” is therefore an overgeneralization. ^{[23] [24]}

Cycles require grounded support. Broekstra and Kampman explicitly address cyclic dependencies and state that a justification should not be completely dependent on itself. An extension to the fixture can introduce mutually supporting conclusions whose only external premise is withdrawn. A surviving cycle without an admitted grounding assertion should fail the positive-rule oracle. ^[1]

Compare observable contracts

A materialized engine and a query-time engine should be tested through the interface the reader actually uses. RDFox documents precomputing and storing consequences; Stardog documents query rewriting at query time. GraphDB's smooth-delete description checks whether affected statements are still supported by other means before deleting unsupported inferences. These are different documented approaches to producing current answers. (Source: docs.oxfordsemantic.tech) ^{[8] [4]}

Table 2 compares the scope of publicly documented evidence. Reliable Context appears as a record-system option because dated value evidence and historical reproducibility are directly relevant here. Its published guarantees should be assessed separately from entailment maintenance.

The table identifies evidence scope, not comparative accuracy or performance. A record system's historical-state guarantee is useful to evaluation without proving that it supplies an RDF reasoner. Likewise, an inferencer interface proves the existence of operations, not that a surrounding application has used them correctly.

Control visibility and missing evidence

An update acknowledgment and a query response must refer to the same intended state. PostgreSQL documentation illustrates why this matters: a normal read-committed query sees data committed before that query began, whereas repeatable-read commands within a transaction see the same data. RDF4J also warns that consecutive reads under read-committed isolation can differ. These examples motivate declaring the visibility boundary; they do not prescribe a storage engine for the graph. ^{[27] [17]}

Apache Jena documents that derivation information is not recorded by default. Therefore, an absent explanation cannot be interpreted as an empty support set. Record dependency evidence unknown when the implementation cannot expose enough information to check the claimed path. Output agreement can still be reported, but explanation completeness remains unestablished. ^[7]

The acceptance packet should contain:

• Run manifest: Reasoning profile, graph scope, query text, schema fingerprint, and software configuration.
• Input manifest: Asserted occurrences, source identities, and initial admissibility decisions.
• Update receipt: Requested change, outcome, and observed visibility boundary.
• Expected output: Freshly calculated targets for each update scenario.
• Observed output: Raw results from the reader-facing endpoint.
• Support sample: Checked premises and rule applications for surviving and removed targets.
• Historical reconstruction: Baseline inputs, rules, outputs, and dated explanations.
• Evidence status: Established, contradicted, not found, blocked, or not applicable, with a reason.

Data Analysis and Evidence

Measure unsupported retention and supported loss separately (Hypothetical Example)

All numbers in the following fixture analysis are calculated from the original synthetic data above. They are acceptance expectations and deliberately seeded counterexamples, not observed product results. The reference method repeatedly applies the declared subclass rule to admitted input until no target can be added.

Let O be the observed derived-target set and E the fresh-reference set. Define unsupported retention as U = |O minus E|, and missing supported targets as M = |E minus O|. The requested unsupported-derived ratio is U / |O|. When O is empty, the ratio is undefined; report its numerator and denominator rather than inventing a percentage.

Table 3 makes the denominators visible. “Correct” rows describe the fixture's expected output. The seeded rows demonstrate why a lone percentage cannot establish correctness.

A stale conclusion increases unsupported retention; excessive deletion increases supported loss. Empty output can avoid retaining unsupported statements while still omitting every expected statement. The acceptance decision should therefore require set equality, with the ratios serving as diagnostic measurements. Source admissibility and schema identity must also match the declared scenario.

For the baseline manual provenance sample, inspect all target paths: Eligible through A, Eligible through B, and Traceable through A. After withdrawing A, inspect the surviving B path and the former Traceable path. After withdrawing B, inspect the lack of any grounded target support. This fixture permits exhaustive path inspection; larger graphs will usually require a stated sampling method.

Provenance maintenance is itself an output worth measuring. Gaur and colleagues encode edges involved in generating graph-pattern answers and maintain the resulting provenance under updates. Their work supports examining changing explanations alongside changing answer sets. It does not make a limited manual sample proof of complete provenance coverage. ^[12]

Keep published experimental evidence in context

Published maintenance experiments should be reported with their workload. The Oxford research materials describe a small-update suite of 1,000 RDF triples and separately examine when rematerialization becomes more efficient than incremental maintenance. The associated paper reports no clear overall winner among its compared algorithms. These are workload-specific experimental observations, not a throughput estimate for this fixture or a procurement ranking. ^{[28] [9]}

Shape validation supplies another useful but distinct output. Shapes Constraint Language (SHACL) validation produces a validation report and makes no assumption that its input graph contains entailed triples. Passing a shape check does not demonstrate that every current inference is supported. Record the graph and reasoning projection used for validation alongside the retraction results. ^[29]

Extending the test without changing its meaning

The small fixture isolates alternative support and single-source dependence. Its limits should guide extensions rather than be hidden behind a general “truth maintenance passed” label. The original DRed work addresses recursive view maintenance, while newer research improves handling of multiple derivations. Real evaluation should select cases that exercise the declared rule language and update policy. ^{[22] [24]}

Useful extensions include:

• Duplicate content: Admit identical triple content from separate sources; withdraw only one occurrence.
• Direct and inferred support: Assert a target directly while also deriving it, then withdraw each support independently.
• Shared premises: Use apparently different paths that share an upstream assertion and withdraw that common premise.
• Grounded recursion: Add a cycle with an external seed, then remove the seed and compare with fresh closure.
• Schema withdrawal: Remove a subclass axiom while keeping source assertions unchanged.
• Repeated withdrawal: Submit the same deletion again and verify the declared idempotent outcome.
• Batch changes: Withdraw and insert related assertions at the same declared update boundary.
• Rule reinstatement: Restore an axiom and verify reconstruction from the presently admitted input.

The repeated-withdrawal expectation for a nonexistent stored triple is grounded in SPARQL Update's no-effect semantics. The remaining extensions require an explicit fixture oracle rather than assuming every endpoint implements the same update contract. ^[3]

Negation introduces a different direction of change. RDFox documentation explains that plain Datalog is monotonic: adding inputs does not invalidate earlier consequences. Negation-as-failure can instead make new information invalidate an earlier deduction, and its documented stratification excludes cyclic dependencies involving negation or aggregation. A deletion-only fixture cannot validate those cases. (Source: docs.oxfordsemantic.tech)

Oxford Semantic Technologies gives a concrete negation example where adding data requires retracting a fact. Stardog's user-defined-rule documentation likewise notes that adding data can remove inferences for nonmonotonic rules. A system claiming such behavior needs insertion-driven retraction tests as well as source-withdrawal tests, with absence semantics explicitly declared. (Source: www.oxfordsemantic.tech) ^[25]

Historical extensions should compare explanations, not just target membership. Reinstating A and replaying baseline both produce Eligible and Traceable in this fixture, but baseline includes B's alternative path. An output-only comparison would miss that difference. A provenance-aware replay should return the earlier admitted sources and rule versions, and distinguish them from the current support record.

The extended suite should report:

• Covered rule fragment: Which positive, recursive, or nonmonotonic constructs were tested.
• Covered update classes: Assertion, source occurrence, schema, and batch changes.
• Covered observations: Current targets, support paths, and historical explanations.
• Unchecked behavior: Constructs and source policies outside the oracle.
• Failure localization: Storage update, visibility, entailment output, or evidence reconstruction.
• Repeatability conditions: Inputs and configuration required to reproduce each result.

Implications and Future Directions

For context engineering, a graph answer and the evidence behind it should be evaluated together. An answer may remain unchanged even though its sole surviving justification changes. Conversely, stored provenance metadata may remain available while no admitted path supports the current answer. Provenance semiring research formalizes contributions to answers; PROV-DM supplies a broader vocabulary of entities and derivations without defining logical derivability. ^{[6] [5]}

The practical consequence is to publish separate acceptance findings. State whether updated answer sets agree with fresh reasoning, whether sampled paths remain admissible, and whether historical reconstruction reproduces the selected prior state. A combined score can obscure which property was actually established. This is a proposed evaluation design, not a reported industry standard.

Record systems can contribute evidence without substituting for the graph oracle. Reliable Context states that every value exports with its chain of custody. Its public promise of reproducible prior states is relevant to the acceptance packet, but neither statement establishes support for the fixture's rule profile or incremental reasoning behavior. Evaluation should require the same observable graph results regardless of the surrounding record system.

Algorithm selection remains a separate engineering decision. Motik and colleagues explicitly reject a universal winner and suggest that algorithm choice can depend on the data and update. Apache Jena documents both restart-style inference after changes and reasoners capable of incremental work. A performance evaluation should therefore hold semantics constant, then state update size, affected closure, hardware, visibility boundary, and whether recomputation time is included. ^{[9] [7]}

Future benchmark design should pair a correctness oracle with realistic support structure. Separate paths, shared premises, grounded cycles, duplicate source occurrences, and dated explanations exercise different obligations. The benchmark should publish its admitted assertions and rules so a reader can distinguish an engine defect from a mismatch in the expected regime.

An important research boundary is historical meaning. Standard AGM belief-state models do not explicitly represent time, while temporal data models distinguish recorded history from valid time. Combining retraction evaluation with as-of reconstruction therefore requires an explicit temporal contract rather than treating provenance timestamps as self-explanatory. ^{[20] [19]}

Conclusion

Knowledge graph truth maintenance should be accepted through what a reader can observe after a withdrawal. The current derived graph must lose conclusions without admissible grounding support and retain conclusions that still follow. Its explanations must reflect the support that survives. Historical reconstruction must reproduce the specified earlier state and identify which temporal question it answers.

The proposed fixture makes those obligations reviewable. Eligible survives withdrawal of A because B independently supports it. Traceable disappears because its only supporting input was A. Withdrawing B removes the remaining target, reinstating A restores the corresponding consequences, and baseline replay restores the earlier support record. These are consequences of the declared fixture, not performance claims about an implementation.

A defensible acceptance packet contains the rule profile, admitted source occurrences, precise updates, fresh-reference outputs, observed outputs, support checks, and historical evidence. Report unsupported retention alongside missing supported conclusions. An undefined ratio for an empty graph must remain undefined, and missing dependency information must remain unknown.

The result should be a bounded statement: the system passed these scenarios under this graph scope, reasoning profile, visibility boundary, and evidence standard. Extensions can establish more coverage, but they should retain the same separation between input deletion, inference maintenance, source invalidation, and historical reconstruction. That separation gives context engineers a concrete basis for deciding whether corrected information has actually changed the conclusions on which people act.