Nonmonotonic Description Logic (DL-) programs couple nonmonotonic logic programs with DL-ontologies through queries in a loose way which may lead to inconsistency, i.e., lack of an answer set. Recently defined repair answer sets remedy this but a straightforward computation method lacks practicality. We present a novel evaluation algorithm for deletion repair answer sets based on support sets, which reduces evaluation of DL-LiteA ontology queries to constraint matching. This leads to significant performance gains towards inconsistency management in practice.
The need for combining rules with ontologies has led to different approaches (see [12]
and references therein). Among them Nonmonotonic Description Logic (DL-) programs
[8] embody a loose coupling of rules and a DL-knowledge base (i.e., ontology) which
the rules can query through special DL-atoms. As the ontology may be enriched before
query evaluation, a bidirectional flow of information enables one to solve advanced
reasoning tasks on top of ontologies. On the other hand, the information flow may lead
to inconsistency, that is, cause a DL-program to lack answer sets (i.e., models).
Example 1. Consider the DL-program in Figure 1, which represents information
about children of a primary school and their parents in simplistic form [7]. It has an
ontology O consisting of a concept taxonomy (TBox) T in (
An inconsistent program may be unusable since it yields no answer set. To cope with this, notions of DL-program repair (under different semantics) have been formalized ? Supported by the Austrian Science Fund (FWF) project P24090
over a family ontology
O =
(
We thus propose an alternative approach for repair answer set computation which is based on the notion of support sets. Intuitively, a support set for a ground DL-atom a = DL[ ; Q](t) is a set of assertions which together with the original TBox is sufficient for the given DL-query Q(t) to be derived.
Our basic method is to precompute small support sets for each DL-atom on a nonground level. Then during the DL-program evaluation, for each candidate interpretation the ground instantiations of the support sets are effectively obtained. These help to prune the answer set search space and they are also used for the ABox repair construction.
This approach is particularly attractive for DL-LiteA ontologies, for which it scales much better then the naive approach [7], as the number of necessary support sets is small and they are easy to compute.
Our contributions on DL-program repair computation are:
(
Preliminaries We start with briefly recalling DL-programs and repair answer sets; see [8; 7] for details. Syntax. A DL-program is a pair = hO; Pi of a finite ontology O and a finite set of rules P defined as follows.
O is a DL-knowledge base (or ontology) over a signature o = hI; C; Ri with a set I of individuals, a set C of concept names and a set R of role names. We assume here throughout that O = T [ A is a consistent DL-LiteA KB [3] with a TBox T and ABox A, which are sets of axioms capturing taxonomic resp. factual knowledge. Concepts C and roles R obey the following syntax, where A 2 C is an atomic concept and U 2 R is an atomic role:
C ! A j 9R B ! C j :C R ! U j U S ! R j :R
TBox axioms are of the form C v B and R v S (inclusion axiom), or (func R) (functionality axiom). ABox contains positive and negative fact assertions.
When the distinction between concepts and roles is immaterial, P denotes a possibly negated predicate from C [ R and P is the opposite of P , i.e. P = :P and :P = P .
The logic program part P of = hO; Pi consists of the rules r of the form
a1 _ : : : _ an
b1; : : : ; bk; not bk+1; : : : ; not bm ;
(
an lp-atom is a first-order atom p(t) with predicate p from a set P of predicate names disjoint with C and R, and constants from the set C = I; a DL-atom a(t) is of form DL[ ; Q](t), where = S1 op1 p1; : : : ; Sm opm pm; m 0; is such that, for 1 i m, Si 2 C [ R, opi 2 f]; [g is an update operator, and pi 2 P is an input predicate of the same arity as Si—intuitively, opi = ] (resp., opi = [) increases Si (resp., :Si) by the extension of pi; Q(t) is a DL-query, which is either of the form (i) C(t), where C is a concept and t is a term; (ii) R(t1; t2), where R is a role and t1; t2 are terms; or (iii) :Q0(t) where Q0(t) is from (i)-(ii). We skip (t) for t = 1 . If n = 0, the rule is a constraint.
Example 2 (cont’d). A DL-atom DL[Male ] boy ; Male](Y ) contained in the rule (
A (Herbrand) interpretation of is a set I HB of ground atoms, where HB is
the usual Herbrand base w.r.t. C and P; I satisfies an lp-atom a, if a 2 I and a DL-atom
a of the form (
O [
I (a) j= Q(c) where I (a) = Sim=1 Ai(I), and
Ai(I) = fSi(t) j pi(t) 2 Ig, for opi = ]; Ai(I) = f:Si(t) j pi(t) 2 Ig, for opi = [.
Satisfaction of a DL-rule r resp. set P of rules by I is then defined as usual, where I satisfies not bj if I does not satisfy bj ; I satisfies , if it satisfies each r 2 P. We denote that I satisfies (is a model of) an object o (atom, rule, etc.) by I j=Oo. 1 We disregard here for simplicity the less used constraints-operator \ and subsumption queries. Example 3 (cont’d). In Example 1, I = fischildof (john; alex ), boy (john)g satisfies a = DL[Male ] boy ; Male](john), since O [ I (a) j= Male(john), while I 6j=ODL[; Adopted ](john), as the input list is empty and O 6j= Adopted (john).
An ( p-)answer set of = hT [ A; Pi is any interpretation I that is a -minimal model of the p-reduct FILP , which maps any set P of rules and I HB to the rule set PFLP = frFLP j r 2 gr(P)g, where rFILP = r if the body of r is satisfied, i.e.,
I I I j=O bi, for all bi, 1 i k and I 6j=O bj , for all k < j m; otherwise, rFILP is void.
A DL-program is inconsistent, if it has no answer set. An interpretation I is an
( p-)deletion repair answer set of = hT [ A; Pi, if it is an p-answer set of some
0 = hT [ A0; Pi where A0 A; any such A0 is called a deletion repair of .
Example 4 (cont’d). As mentioned, is inconsistent; if we drop (
In DL-LiteA ontologies, inconsistency arises by few assertions.
Proposition 1 (cf. [3]). In DL-LiteA given a TBox T every -minimal ABox A such that T [ A is inconsistent fulfills jAj 2.
From this result it is not hard to establish that 3 distinct constants occur in such an A. 3
Support Sets In this section, we introduce support sets for DL-atoms. Intuitively, a support set for a DL-atom d = DL[ ; Q](t) is a portion of its input that, together with ABox assertions, is sufficient to conclude that the query Q(t) will evaluate to true, i.e, that given a subset I0 I of an interpretation I and a set A0 A of ABox assertions from the ontology, we can conclude that I j=O Q(t). The evaluation of d w.r.t. I reduces then to test whether some support set S = I0 [ A0 exists; to this end, a sufficient collection of such sets S can be precomputed and stored. Fortunately, for DL-LiteA this is efficiently possible.
To simplify matters and avoid dealing with I0 separately, it is convenient to introduce input assertions as follows.
Definition 1. Given a DL-atom d = DL[ ; Q](t), we call Pp(c) an input assertion for d, if P p 2 , 2 f]; [g and c 2 C, where Pp is a fresh ontology predicate; Ad is the set of all such assertions.
For a TBox T and DL-atom d, let then Td = T [ fPp v P j P ] p 2 g [ fPp v :P j P [p 2 g, and for an interpretation I, let OdI = Td [A[fPp(t) 2 Ad j p(t) 2 Ig. Then we have: I j=O d iff I j=OdI DL[ ; Q](t) iff OdI j= Q(t).
Proposition 2. For every O = T [ A, DL-atom d = DL[ ; Q](t) and interpretation I,
Unlike (
Now, in view of the property that in DL-LiteA a single assertion is sufficient to derive a query [3] from a consistent ontology, we obtain support sets as follows. Definition 2 (Ground Support Sets). Given a ground DL-atom d = DL[ ; Q](t), a set S of assertions from A [ Ad is a support set for d w.r.t. an ontology O = T [ A, if either (i) S = fP (c)g and Td [ S j= Q(t), or (ii) S = fP (c); P 0(d)g such that Td [ S is inconsistent, where c [ d has at most three distinct constants; by SuppO(d) we denote the set of all such S.
Support sets are linked to interpretations by the following notion.
Definition 3. A support set S of a DL-atom d is coherent with an interpretation I, if for each Pp(c) 2 S it holds that p(c) 2 I.
Example 5 (cont’d). The set fhasParent (john; pat )g is a support set for the DL-atom DL[; hasParent ](john; pat ) w.r.t. O, and so is fMale(pat )g for the DL-atom a = DL[Male ] boy ; Male](pat ). Moreover, fMaleboy (pat )g is in SuppO(a) but incoherent with minimal models of .
The evaluation of d w.r.t. I then reduces to the search for coherent support sets. Proposition 3. Let d be a ground DL-atom, let O = T [ A be an ontology, and let I be an interpretation. Then, I j=O d iff some S 2 SuppO(d) exists s.t. S is coherent with I.
As a simple consequence, we get: Corollary 1. Given a ground DL-atom d and an ontology O, there exists an interpretation I such that I j=O d iff SuppO(d) 6= ;. 3.1
Nonground Support Sets Using support sets, we can completely eliminate the ontology access for the evaluation of DL-atoms. In a naive approach, one precomputes all support sets for all ground DL-atoms with respect to relevant ABoxes, and then uses them during the repair answer set computation. This does not scale in practice, since support sets may be computed that are incoherent with all candidate repair answer sets.
An alternative is to fully interleave the support set computation with the search for repair answer sets. Here we construct coherent ground support sets for each DLatom and interpretation on the fly. As the input to a DL-atom may change in different interpretations, its support sets must be recomputed, however, since reuse may not be possible; effective optimizations are not immediate.
A better solution is to precompute support sets on a nonground level, that is, schematic support sets, prior to repair computation. Furthermore, in that we may leave the concrete ABox open; the support sets for a DL-atom instance are then easily obtained by syntactic matching. This leads to the following definition.
Definition 4 (Support Set for Nonground DL-atom). Let d(X) = DL[ ; Q](X) be a DL-atom and T be a TBox. Let V = fX; Y; Zg be distinct variables such that X V and let C = fa; b; cg. A nonground support set for d w.r.t. T is a set S = fP (Y )g resp. S = fP (Y ); P 0(Y 0)g such that (i) Y ; Y 0 V and (ii) for each substitution : V ! C, the instance S = fP (Y )g (resp. S = fP (Y ); P 0(Y 0 )g) is a support set for d(X ) w.r.t. OC = T [ AC, where AC is the set of all possible assertions over C.
Here AC takes care of any possible ABox, by considering the maximal ABox (as O O0 implies SuppO(d) SuppO0 (d)); three variables suffice as at most three different constants are involved.
Example 6 (cont’d). Certainly fhasParent (X; Y )g is a nonground support set for the DL-atom DL[; hasParent ](X; Y ), and so are fMale(X)g and fMaleboy (X)g for the DL-atom a(X) = DL[Male ] boy ; Male](X). But also, fMaleboy (X); Female(X)g is a nonground support set for a(X).
Nonground support sets S are sound, i.e. each instance S that matches with A [ Ad is a support set of the ground DL-atom d w.r.t. O = T [ A; they are also complete, i.e., every support set S of a ground DL-atom d w.r.t. O = T [ A results as such an instance, and thus can be determined by syntactic matching. Clearly, support sets as defined above may be subsumed by other support sets (e.g., fA(X); R(X; Y )g by fA(X)g) and removed; for space reasons, we omit further discussion here. In the next section, we discuss how to compute a sufficient set of nonground support sets. 3.2
Determining Nonground Support Sets Our technique for computing the nonground support sets is based on TBox classification, which is one of the main ontology reasoning tasks. This reasoning service computes complete information about the TBox constraints specified at the conceptual level.
More formally, given a TBox T over a signature o, the TBox classification Clf (T ) determines all subsumption relations P v (:)P 0 between concepts and roles P; P 0 in o that are entailed by T . This can be exploited for our goal to compute nonground support sets, more precisely a complete family S of such sets. Here completeness of S for a (non-ground) DL-atom d(X) w.r.t. O means that for every : X ! I and S 2 SuppO(d(X )), some S0 2 S exists s.t. S = S0 0, for some extension 0 of to V .
TBox classification is well studied in Description Logics [1]. For example, [9] discusses it for E L w.r.t. concept hierarchy, and [10] studies it for the OWL 2 QL profile.
Respective algorithms are thus suitable and also easily adapted for the computation of (a complete family of) nonground support sets for a DL-atom d(X) w.r.t. O. In principle, one can exploit Proposition 2 and resort to Td, i.e., compute the classification Clf (Td), and determine nonground support sets of d(X) proceeding similar as for computing minimal conflict sets [10]. To determine inconsistent support sets, perfect rewriting [3] can be done over Pos(T ), i.e., the TBox obtained from T by substituting all negated concepts (roles) :C (:R, :9R, :9R ) with positive replacements C (R, 9R, 9R ).
In practice (and as in our implementation), it nonetheless can be worthwhile to compute Clf (T ) first, as it is reusable for all DL-atoms. The additional axioms in Td, i.e., those of form Pp v (:)P (according to the update operators), are handled when determining the nonground support sets for a particular DL-atom from Clf (T ).
Algorithm 1: SupRAnsSet : all deletion repair answer sets
Input: =hT [ A; Pi
Output: f lpRAS( ) (a) compute a complete set S of nongr. supp. sets for the DL-atoms in (b) for I^ 2 AS( ^ ) do (c) (d) (e) (f) (g) (h) end end
if SIg^r(a) = ; then pick next I^ end A0 A n Sa02Dn SIg^r(a0); if pFND (I^; hT [ A0; Pi) then output I^j Dp fa j ea 2 I^g; Dn 2 fa j nea 2 I^g; SIg^r Gr(S; I^; A);
^ ^ if SIgr(a) 6= ; for a 2 Dp and every S 2 SIgr(a) for a 2 Dn fulfills S \ A 6= ; then for all a 2 Dp do if some S 2 SIg^r(a) exists s.t. S \ A = ; then pick next a else remove each S from SIg^r(a) s.t. S \ A \ Sa02Dn SIg^r(a0) 6= ; Example 7 (cont’d). Consider the DL-atom a = DL[Male ] boy ; Male](X) in our running example. For computing a complete family S of nonground support sets for a w.r.t. O, we may refer to Ta = T [ fMaleboy v Maleg and its classification Clf (Ta). Hence, S1 = fMale(X)g and S2 = fMaleboy (X)g are the only unary nonground support sets of a. Further nonground support sets are obtained by computing minimal conflict sets, yielding fP (X); :P (X)g for each P 2 C [ R, as well as fMaleboy (X); :Male(X)g, fMale(X); Female(X)g, and fMaleboy (X); Female(X)g. However, since we are interested in completeness w.r.t. O and O is consistent, pairs not involving input assertions can be dropped (as they will not have a match in A). The remaining two sets are supersets of S2, therefore S = fS1; S2g is a complete family of support sets for a w.r.t. O. 4
Repair Answer Set Computation We are now ready to describe our algorithm for computing deletion repair answer sets with the use of support sets. DL-programs are evaluated usually (as in DLVHEX) by means of a rewriting ^ of gr( ), where DL-atoms a are replaced by ordinary atoms ea (replacement atoms), together with a guess on their truth by additional ‘choice’ rules ea _ nea, where nea stands for negation of ea. We denote interpretations of ^ by I^, and use I^j to denote their restriction to the original language of .
A basic algorithm for computing repair answer sets was given in [7]. It checks whether candidates I^ (i.e., answer sets of ^ ) yield repair answer sets by solving a corresponding ontology repair problem (ORP). Intuitively, solutions to an ORP correspond to (potentially) modified ABoxes A0 (not necessarily obtained by deletion, i.e. subsets of A) such that all DL-atoms evaluate as guessed in I^ (formally I^ is a compatible set of hT [ A0; Pi, cf. [7]); they are computed through multiple calls to the external ontology via a query interface to evaluate DL-atoms under varying ABoxes. A final foundedness check (subset minimality of I^j w.r.t. answer sets.
Our new algorithm SupRAnsSet (see Algorithm 1), avoids instead multiple interface calls and merely needs to access the ontology once. Given a (ground) DL-program for input, SupRAnsSet proceeds as follows. We start (a) by computing a complete family S of nonground support sets for each DL-atom. Afterwards the replacement program ^ is created and its answer sets are computed one by one. Once an answer set I^ of ^ is found (b), we first determine the sets of DL-atoms Dp (resp. Dn) that are guessed true (resp. false) in I^. Next, for all ground DL-atoms in Dp [ Dn, the function Gr(S; I^; A) instantiates S to relevant ground support sets, i.e., that are coherent with I^ and match with A [ Aa. We then check in (c) for atoms in Dp (resp. Dn) without support (resp. input only support). If either is the case, we skip to (b), the next model candidate, since no repair exists for the current one. Otherwise, in a loop (d) over atoms in Dp—except for those supported input only (e)—we remove support sets S that are conflicting w.r.t. Dn. Intuitively, this is the case if S hinges on an assertion 2 A that also supports some atom a0 2 Dn (hence needs to be deleted; note that due to consistency of A, even inconsistent support of a0 leaves no choice). If this operation leaves the atom from Dp under consideration without support (check at (f)), then no repair exists and the next model candidate is considered. Otherwise (exiting the loop at (g)), a potential deletion repair A0 is obtained from A by removing assertions that occur in any support set for some atom a0 2 Dn. An eventual check (h) for foundedness (minimality) w.r.t. A0 determines whether a deletion repair answer set has been found. Example 8 (cont’d). Suppose fea; nebg I^ for a = DL[; hasParent ](john; pat ) and b = DL[Male ] boy ; Male](pat ). Then, SIg^r(a)= ffhasParent (john; pat )gg we get to the else part of Step (e) where nothing is removed from SIg^r(a), since SIg^r(b) = ffMale(pat )gg and SIg^r(a) \ SIg^r(b) = ;. Hence, at Step (g) we must drop Male(pat ) from A to make I^ a deletion repair answer set.
As can be shown, algorithm SupRAnsSet correctly computes the deletion repair answer sets of the input DL-program. For the completeness part, i.e., that all deletion repair answer sets are indeed produced, the following proposition is crucial.
Proposition 4. Given a DL-program , let I^ be an answer set of ^ such that I = I^j is an answer set of = hT [ A; Pi. If I^ is a compatible set for 0 = hT [ A0; Pi where A0 A, then I is an answer set for 0 = hT [ A0; Pi.
Armed with this result, we establish the correctness result.
Theorem 1 SupRAnsSet is sound and complete w.r.t. deletion repair answer sets.
We implemented Algorithm SupRAnsSet within the DLVHEX evaluation framework2, which allows us to effectively compute deletion repair answer sets for DL-LiteA. In 2 http://www.kr.tuwien.ac.at/research/systems/dlvhex order to profit from existing DLVHEX data structures (e.g. for parsing) and optimization methods (such as nogood learning, etc.), we pursued a declarative ASP approach to realize SupRAnsSet . This applies to (a) computing complete nonground support families and to (b) searching candidate deletion repair answer sets and deletion repairs.
As for (a), we use a (stratified) logic program that intuitively mimics perfect rewriting to compute classifications relevant for support set computation on top. The logic program reifies concepts (roles, etc.), as well as positive replacements. Facts express subsumptions in Pos(T ), their contra-positives, and the duality of concepts (roles, etc.) and positive replacements of their negation. A simple rule transitively closes the subsumption relation; support sets are naturally expressed (and thus computed), using unary and binary predicates to represent respective support for a DL-atom, the query and relevant concepts (roles) as from the input signature.
Concerning (b), non-ground rules (see below) are added to ^ for the purpose of filtering candidate deletion repair answer sets as done by SupRAnsSet . Therefore, the language of ^ is extended to include support set information. For any nonground support set S that covers a ground DL-atom a, the additional rules are of the form: SA r(S); nea; supa r(S); ea; not SA; ea; not supa ; where r(S) is a suitable representation of S, i.e., using predicates p(X) for input assertions Pp(X), resp. pP (X) (npP (X)) for ABox assertions P (X) (:P (X)). Furthermore, pP , npP , and supa are fresh predicates not in P, and SA refers to npP (X) (resp. pP (X)) if S \ A 6= ; and the assertion is positive (resp. negative), otherwise it is void. With further constraints pP (X); npP (X), the resulting program intuitively prunes candidates I^, resp. encodes deletion repair candidates, according to SupRAnsSet . Experimental Setup. We have evaluated the approach by comparing it with ordinary answer set computation on two scenarios. They were run on a Linux server with two 12-core AMD 6176 SE CPUs/128GB RAM using DLVHEX 2.3.0; a timeout of 120 secs was set for each run.
Family Benchmark. The first benchmark is derived from our running example. We fixed
two ABoxes with A50 and A1000, of different size, where A50 contains 50 children (7
adopted), 20 female and 32 male adults; and twenty times that many for A1000. Every
child has at most two parents of different sex and the number of children per parent varies
from 1 to 3. Rules (
Network Benchmark. In the second scenario a network is described by a fixed ontology O using a relation edge. Some nodes might be broken or blocked. There are overall 70 nodes, (among them 23 broken and rest available). There are 68 edges (among them 5 forbidden). The TBox encodes that if an edge is forbidden, then its endpoint must be blocked, and if a node is known to be broken, then it is automatically blocked, moreover blocked nodes are not available:
p AS A50 rep ASA1000 rep p ASPconnrep ASPguessrep
5 (25) 0.12 (0) 0.19 (0) 63.93 (0) 36.70 (0) 10 (25) 0.19 (0) 0.13 (0) 0.48 (0) 0.16 (0)
10 (25) 0.12 (0) 0.19 (0) 63.77 (0) 37.59 (0) 20 (25) 0.19 (0) 0.44 (0) 0.48 (0) 0.37 (0)
15 (25) 0.12 (0) 0.20 (0) 63.98 (0) 38.29 (0) 30 (25) 0.19 (0) 1.28 (0) 0.51 (0) 0.86 (0)
20 (25) 0.12 (0) 0.20 (0) 63.90 (0) 39.17 (0) 40 (25) 0.19 (0) 2.36 (0) 0.53 (0) 1.31 (0)
25 (25) 0.12 (0) 0.20 (0) 63.82 (0) 39.97 (0) 50 (25) 0.19 (0) 5.60 (0) 0.57 (0) 3.00 (0)
30 (25) 0.12 (0) 0.21 (0) 63.97 (0) 40.77 (0) 60 (25) 0.19 (0) 8.83 (0) 0.60 (0) 5.03 (0)
35 (25) 0.12 (0) 0.21 (0) 63.18 (0) 41.41 (0) 70 (25) 0.19 (0) 15.92 (0) 0.64 (0) 7.27 (0)
80 (25) 0.20 (0) 25.89 (0) 0.69 (0) 11.45 (0)
time in seconds for first ordinary and 90 (25) 0.20 (0) 37.33 (0) 0.75 (0) 16.95 (0)
deletion repair answer set 100 (25) 0.20 (0) 55.43 (0) 0.87 (0) 16.38 (0)
(
The program Pconn contains the same random node facts as Pguess and facts in(n)
and out (n), either for each node n with equal probability (i.e., in with p = 1=2, out ,
otherwise). It contains the rules (
Despite a small overhead for computation of deletion repair answer sets compared to ordinary ones the results for the family problem with A50 scale well. For A1000 the first repair answer set is found quicker then the inconsistency is identified during ordinary answer set computation. Liberal safety [5] exploited in the experiments improves greatly the running time both for repair and ordinary answer set computation modes.
In the Network domain, as expected, running times grow exponentially with the
instance size for Pguess due to the guessing rule (
Additionally, our approach has been evaluated on inconsistent programs over the LUBM3 ontology; more precisely, over a DL-LiteA version together with a fixed, generated4 ABox (1 university with over 500 students, 50 courses and 29 teaching assistants). Rules encode default reasoning under constraints: teaching assistants (TAs) are normally students, and TAs must not take the exam of a course they teach. Facts takesExam(c1; c2) have been randomly added to the program with a probability between 0:05 to 0:2. A first repair answer set is found for all instances within 4 seconds, while detecting inconsistency with ordinary answer set computation takes about 1 minute.
These results indicate the effectiveness of our approach for practical settings. 6
Conclusion Support sets reduce the evaluation of DL-atoms over DL-LiteA ontologies to constraint matching, providing a base for effective deletion repair answer set computation under psemantics. Our results, and in particular algorithm SupRAnsSet , easily extend to other semantics, e.g., weak repair answer sets [7], and to other notions of repairs. Furthermore, support sets are used in a companion work to compute answer sets of HEX-programs [6]. As external atoms lack an explicit data part (ABox), support sets ought to be more abstract, which makes direct efficient usage less clear; repair is an open issue.
Note that algorithm SupRAnsSet constructs in its search all maximal deletion repairs, i.e., -maximal repairs A0 A that admit an answer set (however, it also may construct non-maximal repairs). In this regard it is similar to work on ABox cleaning [11; 13]. There, an inconsistent ontology (with consistent TBox) is repaired by identifying and eliminating minimal conflict sets causing, i.e., explaining, the inconsistency, thus resulting in maximal deletion repairs. However, our setting and work differ fundamentally: (i) the ontology is consistent and inconsistency arises only through the interface of DL-atoms, and (ii) several DL-atom queries have to be considered (entailment or non-entailment) under different potential ABox updates.
More remotely related to our work are approaches for explaining positive and negative answers to conjunctive queries in DL-Lite [4; 2], as they apply the perfect reformulation algorithm [3] and then extract explanations in a nontrivial way.
In ongoing work, we consider restricted repairs [7] and an extension of our approach to other DLs like E L. While no small complete support families exist for E L in general, this might still apply for practically relevant fragments. Furthermore incomplete support families can be used for optimization (caching) to reduce access to an E L reasoner. 3 http://swat.cse.lehigh.edu/projects/lubm/ 4 http://code.google.com/p/combo-obda/