Repairs of Knowledge Bases. Even though logic-based systems produce logically correct and explainable inferences, faulty conclusions might be drawn if the knowledge base (KB) itself contains errors. Of course, the KB should then be appropriately repaired. The classical method is to pinpoint the statements in the KB from which the incorrect conclusion was drawn, and then either delete a minimal number of them such that the observed error vanishes or present these statements to knowledge engineers and domain experts for rectification. However, often only parts of statements are erroneous and thus deletion of whole statements would erase too much. On the other hand, it might be dificult for the experts to correct the statements since they first need to understand how the faulty consequence is inferred from them. In order to surmount both practicability issues of the classical method, we propose an interactive repair method which employs the optimal repair framework. Errors are not resolved by deleting a minimal number of statements but instead by modifying the KB such that only minimally many consequences are removed (including the observed faulty ones). Unlike the classical method, the experts do not need to consult, in a bottom-up manner, proofs of the unwanted consequence to appropriately correct the KB. Instead, they start with the reported errors and proceed towards logical causes of identified faulty statements. Through this interactive top-down manner, the experts' workload is significantly lowered. Optimal Repairs in General. The general setting is as follows, which covers both unwanted consequences as well as missing consequences (whereas previous definitions in the literature considered only unwanted consequences). A repair request is an assertion set := + ⊎ − partitioned into an addition part + and a removal part − . Of a consistent KB := ⊎ , an ABox repair for is an ABox ℬ such that the KB ℬ ∪ is consistent, entails all assertions in +, and does not entail any assertion in − . That is, we treat the ABox as refutable and the ontology as static - a reasonable assumption since ABoxes often contain vast amounts of collected observations whereas ontologies are usually more carefully maintained. Repairs as defined above have no connection to the input ABox, but the following order relation ≥ between repairs takes it into account. We write ℬ ≥ and say that ℬ is at least as good as another repair if ℬ ∪ entails all retained knowledge in (i.e. ℬ ∪ |= for each ∈ with |= ) and ∪ entails all additional knowledge in ℬ (i.e. ∪ |= for each ∈ ℬ with ̸|= ). Moreover, we write ℬ > and say that ℬ is better than if ℬ ≥ but ̸≥ ℬ , i.e. either less knowledge is added or less knowledge is removed. In order to emphasize that these two relations depend on the input KB to be repaired, the symbols ≥ and > could be used instead. A repair ℬ is optimal if there is no repair better than ℬ. Figure 1 illustrates an optimal repair: between the optimal repair and the input KB no further repair exists. Previous Work. There is no general approach to computing optimal repairs, and previous research focused on repair requests without an addition part. It seems that abduction methods [3-5] could be used to treat the addition part but it is still unclear how optimality could be achieved. Instead, we * This is an extended abstract of an article [1] published in the proceedings of the 40th ACM/SIGAPP Symposium On Applied
< < < < · · · <
just assume that the addition part + is already entailed by the input KB (which could be achieved by simply adding all statements in + to the KB), and so + is only to be preserved by every repair.
Interestingly enough, optimal repairs need not exist even if the input KB can be repaired [
Disputable Consequences. In order to comply with the repair request, optimal repairs preserve as much as possible knowledge entailed by the input KB while containing as little as possible new knowledge — yet not every assertion entailed by should be preserved in the concrete application. The reason is that such an entailed assertion might only make sense in the application domain as long as it is substantiated. For instance, if we repair for an assertion stating that Bob has a particular disease, then we would not want to keep the consequence that Bob is ill, unless there is knowledge that he has another disease. In contrast, if it should be repaired that Alice is a celebrity, then we would still want to retain the consequence that Alice is a human. In order to formulate this precisely, we use substantiations. In the literature, justifications of a statement have been defined as subsets of the refutable part that together with the static part entail . In order to eliminate dependence on the syntax, our following definition instead defines substantiations as KBs entailed by the refutable part. (We chose another denotation to avoid confusion.) We further take the provided information in the repair request into account by treating its addition part like the ABox of the input KB, since both are the “positive knowledge” before the repair process. That is, a substantiation of is an ABox such that ∪ + |= and ∪ |= .
With that, we call a consequence of disputable if a repair entails it while another not (i.e. it could
be included in a repair or not), but none of its substantiations can be found in any repair (i.e. it is
not justified anymore). More formally: given a consistent KB and a repair request , a disputable
Computing (SAC 2025) and of its extended version [
DL 2025: 38th International Workshop on Description Logics, September 3–6, 2025, Opole, Poland $ francesco.kriegel@tu-dresden.de ( Francesco Kriegel) https://tu-dresden.de/inf/lat/francesco-kriegel ( Francesco Kriegel) 0000-0003-0219-0330 ( Francesco Kriegel)
© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). consequence is an assertion such that ∪ + |= , there is a repair that entails , there is another repair that does not entail , and for each repair ℬ, the KB ℬ ∪ does not entail any substantiation of . In order to obtain an optimal repair that makes sense in the application domain, we recommend to initially decide all disputable consequences and accordingly refine the repair request, i.e. add all accepted ones to + and all rejected ones to − .
Deterministic Repair Requests. Even if repair requests are optimally coverable in the considered setting, they might be under-specified in the sense that there is no unique optimal repair. From a practical perspective, it then makes no sense to compute a random optimal repair. To see this, consider the KB consisting of the ABox {charlie : Horse, charlie : Male} and the TBox {Horse ⊓ Male ⊑ Stallion}. For the repair request with removal part {charlie : Stallion}, there are two optimal ABox repairs: {charlie : Horse} and {charlie : Male}. Now, if in real world Charlie is a horse, then the second, formally optimal repair does not make sense.
If the repair request is non-deterministic, then it should be further refined to eventually identify an optimal repair appropriate for the application. Formally, we say that is deterministic w.r.t. if is optimally coverable w.r.t. and there is exactly one optimal repair of w.r.t. up to equivalence w.r.t. .
refine = →−0− −
refine →−1− −
refine →−2− −. . .
refine
→−− −
deterministic
Apart from computing disputable consequences, the question addressed in the conference article [
We show that deciding disputable consequences in this setting is co NP-complete w.r.t. combined complexity — nevertheless, they can be computed rather eficiently for real-world KBs. W.r.t. data complexity, Lemma 4.11 implies that it can be decided in polynomial time only whether an assertion is a disputable consequence. We further present an interaction strategy with which a deterministic refinement can be identified in polynomially many steps, i.e. the number of questions that need to be answered by the users/experts is polynomial. Every (theoretically) optimal repair can be found with the strategy, and it runs in two phases: • Phase 1 is devoted to identifying the causes of the initially reported errors in . • Phase 2 first computes all disputable consequences that are concept assertions built from the subconcepts in the input or role assertions, and then proceeds with these as Phase 1. In both phases, the questions are not fixed but evolve according to the answers received. If a question inherits its answer already by logical reasoning from previous answers, then it is not presented to the users/experts.
An implementation of the underlying repair construction as well as the interaction strategy is available.L1 It comes in form of a plug-in for the KB editor Protégé.L2 Since it is implemented in the programming language Scala,L3 it can be used on any operating system for which a Java virtual machine (JVM) is available. It is recommended to use a modern JVM like GraalVML4 since it ofers faster code execution (often twice as fast as a standard JVM). Furthermore, the implementation employs the currently fastest ℰℒ reasoner: ELK.L5 On MacOS, the easiest way to try out the implementation is to use the installer script.L6 For other operating systems this script can be easily adapted. More details are explained on the start page of the GitHub repository.L1
Even though co NP-hardness of disputable consequences seems to indicate that Phase 2 would be intractable, the implementation works suficiently fast even with large TBoxes such as (the ℰℒ fragment of) SNOMED CT,L7 which contains more than 360,000 concept names. Interactively identifying a repair of an ABox representing data on a patient having a common cold and then computing this repair completes within about four to five minutes. More specifically, in this experiment we used an ABox containing a single assertion stating that a particular person has a common cold; the user interaction then amounted to about 30 questions only (as the interaction process is local to the statements to be repaired for). This computation time can surely be further improved with optimizations or faster programming languages such as C++.
Future Work. As future work, we want to extend the strategy to optimal repairs in more expressive
DLs such as Horn-ℒℛℐ [
This work has been supported by Deutsche Forschungsgemeinschaft (DFG) in Project 389792660 (TRR 248: Foundations of Perspicuous Software Systems) and in Project 558917076 (Construction and Repair of Description-logic Knowledge Bases) as well as by the Saxon State Ministry for Science, Culture, and Tourism (SMWK) by funding the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI).
The author has not employed any Generative AI tools.
L1 https://github.com/francesco-kriegel/interactive-optimal-repairs L2 https://protege.stanford.edu L3 https://www.scala-lang.org L4 https://www.graalvm.org L5 https://github.com/liveontologies/elk-reasoner L6 https://raw.githubusercontent.com/francesco-kriegel/interactive-optimal-repairs/main/install-macos.
sh L7 https://www.snomed.org/