Errors in Description Logic (DL) ontologies are often detected when reasoning yields unintuitive consequences. Consider we have data represented in an ABox using role and concept assertions, such as has_parent(SOUTH, KIM) and Famous(KIM), which say that South has the famous parent Kim. Additionally, assume there is background information represented in a TBox using concept inclusions such as ∃has_parent.Famous ⊑ Rich saying that children of famous parents are rich. Suppose that the user realizes that Kim actually is not a parent of South, i.e., the consequence has_parent(SOUTH, KIM) is incorrect, and requests that it has to be removed. The classical approach for satisfying the repair request is to construct a maximal subset of the ABox that has none of the unwanted consequences w.r.t. the given TBox. In our example, has_parent(SOUTH, KIM) must be removed from the ABox, but this also removes consequences ∃ has_parent. Famous(SOUTH) and Rich(SOUTH) that are not problematic for the user. It might be that the user knows that South has a famous parent, but made an error when naming this parent. Thus, they want to get rid of the erroneous role assertion, but not of the concept instance relationships for South that the ABox entails. From the above concern, we are interested in repairing the ontology in an optimal way such that the unwanted consequences are removed, but instead of preserving a maximal subset of the input ABox, we intend to keep a maximal set of the unobjected consequences. The problem of computing such optimal repairs was already addressed in our previous work [1, 2, 3, 4]. In particular, in [2] we consider a setting, where the TBoxes are static and formulated in ℰℒ, while the ABoxes are generalized into so-called quantified ABoxes (qABoxes) , which may contain anonymous individuals represented as existentially quantified variables. Moreover, the setting also considers instance repair requests that consist of ℰℒ concept assertions and the optimality of the repairs is defined w.r.t. IQ-entailment, where qABoxes are compared w.r.t. which ℰℒ
instance relationships they imply. It is shown in [
As the first contribution of our SAC ’23 paper [
For the ABox repair request, one first applies this approach to the subset consisting of
its role assertions, and continue with the approach of [
Error-Tolerant Reasoning
In general, a given repair problem may have exponentially many optimal repairs, both in
the classical and in the optimal sense, and thus it is often hard to decide which one to use.
Error-tolerant reasoning does not commit to a single repair, but rather reasons w.r.t. all repairs
(within the classical or the optimal setting). Brave entailment asks if a given query is entailed by
some repair, whereas cautious entailment asks if the query is entailed by all repairs. This was
originally considered for classical TBox repairs [
In our RuleML+RR ’22 paper [11], we look into error-tolerant reasoning w.r.t. optimal
IQrepairs for instance repair requests, and in our SAC ’23 paper [
Dealing with cautious reasoning is more involved since we need to check what is entailed
by all optimal repairs, each of which can have exponential size [12]. To this end, we need to
look closer at how optimal repairs are constructed. Since the optimal IQ- and IRQ-repairs can
be obtained from the set of canonical IQ-repairs and each canonical IQ-repair is induced by a
seed function of polynomial size [
To make this solution feasible, we first showed that the instance problem w.r.t. canonical repairs can be solved in polynomial time in the size of the seed function. Secondly, since not all canonical repairs are optimal, we must be able to decide if a given seed function induces an optimal repair. We were able to show that this problem can also be solved in polynomial time. This yields a coNP-procedure for deciding cautious reasoning: to show that a set of assertions is not a cautious consequence, we guess a seed function and check whether it is minimal and the induced canonical repair does not entail one of the given assertions. If we consider empty TBox and instance queries, then we were able to show that cautious entailment w.r.t. optimal IQ-repairs for instance repair requests can be decided in polynomial time [11].
There is no matching lower bound yet for cautious entailment in both settings. However, if we consider classical repairs [13, 14, 15] rather than the optimal ones, then we can show that cautious reasoning is coNP hard and brave reasoning becomes NP-hard. The NP-hardness of cautious non-entailment is obtained by a reduction from the NP-complete path via a node problem [16, 17], while the NP-hardness of the brave entailment via a reduction from the NP-complete monotone 1-in-3-SAT problem [18].
Our approach for checking brave entailment can be used to support computing an optimal
repair that retains the consequences that are wanted. By viewing the set of such consequences as
a brave consequence, if this set is a repair, then, as shown in [11], we can compute in polynomial
time a seed function that induces an optimal repair that entails the given wanted consequences.
On the other hand, as argued in [
The full paper of [11] is published in the proceedings of the 6th International Joint Conference
on Rules and Reasoning (RuleML+RR 2022), while the full paper of [