Efficient Deletion in Materialized Knowledge Bases

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 122 papers51 conceptsfrozen 2026-10-04

In large-scale reasoning systems, "materialization" is a common strategy for performance: instead of calculating logical consequences every time a user asks a question, the system pre-computes all possible facts and stores them in a database. This makes querying nearly instantaneous.

However, this speed comes at a cost when the underlying data changes. While adding a new fact is relatively straightforward (you simply derive and store its consequences), deleting a fact is notoriously difficult. If you remove a base fact, you must also remove every inferred fact that relied on it—but only if that inferred fact doesn't have an alternative proof from other data.

The Over-deletion Problem

The traditional approach to this problem is known as Delete-and-Rederive (DRed). As the name suggests, the algorithm is pessimistic: when a fact is deleted, it identifies every consequence that might be affected and deletes them all in a massive cascade. Afterward, it performs a "re-derivation" phase to see if any of those deleted facts can be proven again using the remaining data.

As Pan Hu, Boris Motik, and Ian Horrocks explain in Optimised Maintenance of Datalog Materialisations, this leads to a massive amount of redundant work. In highly connected datasets, a single fact might be supported by dozens of different logical paths. DRed will delete that fact and its entire downstream tree, only to spend significant CPU cycles re-calculating and re-inserting the exact same information.

The High Cost of Backward Verification

A natural question is: why not just check for an alternative proof before deleting? This is known as backward evaluation.

The problem, as noted by Pan Hu and colleagues, is that backward evaluation is often an order of magnitude more expensive than the original forward derivation. In a forward pass, the system simply follows rules to new conclusions. In a backward pass, the system must search through the entire database to prove a specific "goal," which often transforms simple linear operations into complex quadratic searches. This makes "checking before deleting" a major performance bottleneck.

Solution 1: Derivation Counting

To avoid both the over-deletion of DRed and the expensive searches of backward chaining, researchers have turned to Derivation Counting.

The intuition is simple: for every inferred fact, the system maintains a counter of how many distinct proofs support it.

  • When a new proof for a fact is found, the counter increments.
  • When a supporting fact is deleted, the counter decrements.
  • The fact is only physically removed from the database when the counter hits zero.

Jacopo Urbani and the DynamiTE team demonstrated that this "reference counting" allows for near-instant updates even on datasets with billions of triples. Similarly, James P. McGlothlin and Latifur Khan showed in Materializing and Persisting Inferred and Uncertain Knowledge in RDF Datasets that this mechanism ensures "knowledge derived from multiple sources remains intact if only one source is removed."

Solution 2: The Backward/Forward (B/F) Algorithm

While counting is efficient, it requires extra memory to store the counters. An alternative approach, introduced by Boris Motik and Yavor Nenov in Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm, is the B/F algorithm.

B/F tries to find a "middle ground." When a fact is slated for deletion, the algorithm performs a limited backward search to find just one alternative proof. If it finds one, it stops immediately and keeps the fact. If it can't find one quickly, it proceeds with the deletion. By interleaving these checks, the system minimizes the "deletion cascade" without the memory overhead of full derivation counting.

Modern Applications and Formalisms

This research direction has moved from theoretical database logic to massive real-world deployments. For instance, the RDFox engine—developed by Ian Horrocks and others—uses these optimized incremental algorithms to power on-device AI for millions of users in the Samsung Galaxy S25.

Recent work has also sought to provide a more rigorous mathematical foundation for these updates. Mario Alvarez-Picallo and Luke Ong have framed incremental maintenance as a problem of calculating derivatives of fixpoints. By treating changes to a database as mathematical derivatives, they provide a modular way to propagate updates through complex recursive programs, ensuring that even the most sophisticated AI systems can stay up-to-date without starting from scratch.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_efficient_deletion_in_materialized_knowl_e1ce4cdb,
  title = {Efficient Deletion in Materialized Knowledge Bases},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-deletion-in-materialized-knowledge-bases/rdr_e1ce4cdb7c76497fb25ac52b97e92794},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_efficient_deletion_in_materialized_knowl_e1ce4cdb_v1,
  title = {Efficient Deletion in Materialized Knowledge Bases},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-deletion-in-materialized-knowledge-bases/rdr_e1ce4cdb7c76497fb25ac52b97e92794/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}