What Deletion Costs in DL-Lite: Measuring Answer Loss When Ontology Updates Cannot Be Expressed

Ontology-based data access lets users query large databases through a schema of simple logical rules. The rule language usually belongs to the DL-Lite family, which is the logic behind the OWL 2 QL standard. DL-Lite deliberately leaves out logical "or", because without it every query can be rewritten into plain SQL. The cost appears when facts are deleted. Suppose the schema says every professor teaches something, and we delete "Alice teaches CS101". The minimal change to the knowledge base is then "either Alice is no longer a professor, or she teaches some other course". DL-Lite cannot write that statement down. Theory has worked this problem out in depth. Model-based semantics provably leave the language (Understanding Inexpressibility of Model-Based ABox Evolution in DL-Lite, On expansion and contraction of DL-Lite knowledge bases). Several polynomial-time repairs have also been proposed: bold and careful semantics, maximal approximations, fresh-constant "s-approximations", and type semantics. None of these repairs has ever been implemented and run on a real ontology.

We propose the first quantitative answer to the question practitioners actually face: when real update streams delete facts, how often does the "or" problem arise, and how much does each way of avoiding it cost? We measure cost in wrong or missing query answers and in runtime. The central step is to build a ground truth. On localized slices of real knowledge bases, we compute the exact minimal-change result in a logic that allows "or". Every tractable operator is then scored against that ground truth for precision and recall of query answers. The same scoring covers the ad hoc retraction that materialization systems already use in practice.

Core Claim

The existing literature proves properties of the principled operators but never measures them. Meanwhile, practical systems delete facts with no stated semantics. We hypothesize that the two sides fail in opposite directions. Sound approximations, such as maximal $(\mathcal{L},\mathcal{T})$-approximations and s-approximations, can only lose answers: their models include all models of the exact update, so their certain answers are a subset of the exact ones. Naive retraction, as done by Delete/Rederive (DRed) style maintenance, keeps facts like "Professor(Alice)" that the exact semantics no longer entails, so it can return wrong answers.

The claim to be tested has three parts. First, deletions that collide with mandatory-participation constraints, functionality, or disjointness are common enough in realistic streams to matter. Second, on those deletions, naive retraction has measurably below-perfect precision, while principled operators keep precision at 1 with a recall loss that can be quantified. Third, the fresh constants that s-approximations add carry a concrete storage and rewriting cost, which trades against their better recall.

A negative result would also be valuable. If collisions are rare, or if naive retraction almost never disagrees with exact semantics on real queries, then the practical case for this body of theory is weak, and the field should know.

Research Program

The first component is a contraction benchmark. The only existing evolution benchmarks cover additions only (Query Rewriting Under Ontology Evolution), or random 1% changes with no check on whether a constraint was triggered (Embracing Change by Abstraction Materialization Maintenance for Large ABoxes). We start from three sources and take their DL-Lite fragments:

From each source we generate two kinds of deletion stream. The first is random, which serves as the prevalence baseline. The second is adversarial: it targets assertions whose removal forces the existential, functionality, or disjointness conflicts identified as the root cause of inexpressibility. We report, per ontology, what fraction of random deletions trigger non-closure. That number alone is currently unknown.

The second component is an exact reference. Winslett-style model-based change is local: it only affects individuals connected to the changed assertion through the schema. We exploit this by extracting a bounded neighborhood around each update. On that neighborhood, we encode the exact update result, including its "or" statements, in a more expressive description logic and compute certain answers with a complete general reasoner. Whether the neighborhood bound actually preserves exactness is itself something we check. On small UOBM slices, we compare neighborhood answers against whole-knowledge-base exact computation, and we report any disagreements.

The third component is a set of implementations, done once and released:

Every one of these papers supplies an algorithm and proves it runs in polynomial time. None reports running it, and On expansion and contraction of DL-Lite knowledge bases explicitly discusses no datasets. Our contribution is the measurement layer, not new operators. We restrict ABox evolution to protected schemas, where bold semantics is deterministic. Schema evolution, where bold semantics yields many candidates, is reported separately by counting the candidates rather than choosing among them.

Baselines

The naive reference point is plain retraction. It removes the asserted fact and leaves everything else, including facts derived from it that are still derivable. This is the implicit semantics of any triple store that simply executes a DELETE. It costs essentially nothing, and it is the behavior our precision measurement is designed to expose.

The strongest existing practical method is ARDRed, from Embracing Change by Abstraction Materialization Maintenance for Large ABoxes. It combines ABox abstraction with Delete/Rederive: facts derived from a deleted fact are over-deleted, then re-derived where possible. It is the only evolution method in the file that has been benchmarked at scale with deletions. That paper reports 281.48 seconds for remove-only updates on UOBM100, against 3191.51 seconds for plain DRed. ARDRed targets Horn $\mathcal{ALCHI}$ materialization, a different language from DL-Lite. For a fair comparison, we run it and our DL-Lite operators on the same DL-Lite fragment of UOBM100, with the same 100 change sets, the same hardware and the same timeout. On runtime, we treat ARDRed's number on its own setup as the reference to approach. On correctness, no reported result was found on Lacuna for ARDRed or any evolution operator. A principled operator "beats" ARDRed if it matches its answer precision of 1 on non-trigger deletions, exceeds it on trigger deletions, and stays within a small constant factor of its runtime.

The information-discarding baseline is WIDTIO, which keeps only what is common to all maximal consistent subsets. Evolution of DL-Lite Knowledge Bases argues on toy examples that it throws away too much. We measure how much, as recall against the exact reference.

For query cost, the reference is recomputation from scratch using a rewriting engine such as Graal on the DBpedia suite. A DBpedia-based Benchmark for Ontology-mediated Query Answering reports Graal at 80.3 seconds on 10M triples and failing the 10-minute limit at 20M triples.

The key ablation compares s-approximation with and without its fresh auxiliary constants, the latter falling back to AtAlg-style maximal approximation. This isolates whether the recall gain claimed in Trust-Sensitive Evolution of DL-Lite Knowledge Bases is worth the growth in stored facts and the extra joins in rewritten queries.

Why not just…?

Why not just delete whatever conflicts, syntactically? Syntactic deletion is WIDTIO-like or plain base revision. Instance-Driven Ontology Evolution in DL-Lite shows it discards unrelated valid rules, which it calls the "drowning effect". Its evidence is a single NCI toy example, however. Our recall measurements settle the question empirically. If syntactic deletion loses little recall on real queries, that is a legitimate finding against the heavier operators, and we will report it as such.

Why not just use DRed or ARDRed, which already scale? They scale, but they have no minimal-change semantics. On a deletion like Alice's, they keep "Professor(Alice)", which the exact update does not entail. This is a genuine threat to the relevance of the whole proposal, because if such cases are rare, DRed wins by default. The prevalence measurement and the per-trigger precision measurement decide it directly.

Why not just move to an expressive logic that has "or"? This option gives up translation of queries into SQL and polynomial data complexity. The DBpedia benchmark already shows rewriting engines collapsing within tractable rule languages: Drewer fails at 181 rules. Still, we use exactly this approach as our ground truth on neighborhoods. We will report whether exact expressive reasoning is fast enough on localized updates to be used directly. If it is, that would undercut the approximations, and we would say so.

Why not just benchmark runtime and stop? Every operator is already proven polynomial. Runtime alone would mostly confirm known bounds. The open question is semantic: how many answers each operator gets wrong or misses. Only the exact reference can measure that.

Proposed Experiments

Experiment one measures prevalence. It reports the fraction of random deletions on NPD, UOBM and DBpedia that trigger inexpressibility, broken down by constraint type.

Experiment two measures correctness. It uses the DBpedia queries and UOBM's queries, restricted to those touching updated individuals. For each operator it reports answer precision and recall against the exact neighborhood reference, separately for trigger and non-trigger deletions. It also splits the results by instance queries versus conjunctive queries with joins, because approximations are proven only for instance checking.

Experiment three measures cost. It records update time and memory on UOBM10 through UOBM100, the number of added facts from s-approximation's fresh constants, and rewriting time and size on the DBpedia suite at 5M and 10M triples.

The decisive checks are these. If naive retraction shows precision below 1 on a non-trivial share of real queries, the formal semantics matter in practice. If maximal approximation's recall on join queries falls well below its instance-query recall, the unproven gap is real. If the s-approximation ablation shows recall gains that do not survive the added rewriting cost at 10M triples, that trade-off decides which operator to deploy.