Towards Practical Deletion Repair of Inconsistent DL-programs? Thomas Eiter, Michael Fink, and Daria Stepanova Institute of Information Systems Vienna University of Technology Favoritenstraße 9-11, A-1040 Vienna, Austria {eiter,fink,dasha}@kr.tuwien.ac.at Abstract. Nonmonotonic Description Logic (DL-) programs couple nonmono- tonic 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 an- swer 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-Lite A ontology queries to con- straint matching. This leads to significant performance gains towards inconsistency management in practice. 1 Introduction 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 (1)-(3) and a set A of assertions (ABox), i.e. facts, about individuals in (4)-(6). The rules P contain further facts (7), (8) and proper rules: (9) determines fathers from the ontology, upon feeding information to it; (10) checks, informally, against them for local parent information (ischildof ) that a child has surely not two fathers, unless it is adopted; finally (11)-(12) single out contact persons for children (by default, the parents); for adopted children, fathers in O are omitted if some other contact exists. Inconsistency arises as john, who is not provably adopted, has pat as father by the ontology, and by the local information possibly also alex . 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 Fig. 1. DL-program Π over a family ontology   (1) Child v ∃hasParent (2) Adopted v Child (3) Female v ¬Male O= (4) Male(pat) (5) Male(john) (6) hasParent(john, pat)     (7) ischildof (john, alex ); (8) boy(john);   (9) hasfather (X, Y ) ← DL[Male ] boy; Male](Y ), DL[; hasParent](X, Y );           (10) ⊥ ← not DL[; Adopted ](X), Y1 6= Y2 , hasfather (X, Y1 ), ischildof (X, Y2 ),   P=   not DL[Child ] boy; ¬Male](Y2 );         (11) contact(X, Y ) ← DL[; hasParent](X, Y ), not omit(X, Y );     (12) omit(X, Y ) ← DL[; Adopted ](X), Z 6= Y, hasfather (X, Y ), contact(X, Z)   recently [7]. They give rise to so-called repair answer sets under the supposition of suitable changes to the ABox (data) of the ontology. As for repair computation, however, a natural realization of corresponding algorithms turns out to be too naive and does not scale for practical applications due to large number of ABoxes to be checked in general. 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 non- ground 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-Lite A 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: (1) We formally establish support sets as sound and complete structures for DL-atom evaluation avoiding ontology access. Moreover, this characterization is faithfully lifted to the nonground level, enabling scalability of exploitation. (2) Nonground support sets for DL-atoms over DL-Lite A ontologies can not only be efficiently computed, but also turn out to be small. We utilize this fact to devise an algorithm for the effective computation of deletion repairs of DL-programs under so-called flp semantics and discuss potential generalizations. (3) We report experimental results obtained implementing our approach and evalu- ating its scalability on a set of benchmark scenarios; they provide evidence for the effectiveness of the method. 2 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-Lite A 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 ∈ C is an atomic concept and U ∈ R is an atomic role: C → A | ∃R B → C | ¬C R → U | U − S → R | ¬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 , (1) where each ai , 0 ≤ i ≤ n, is an lp-atom and each bi 1 ≤ i ≤ m, is either an lp-atom or a DL-atom; here • 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 op 1 p1 , . . . , Sm op m pm , m ≥ 0, (2) is such that, for 1 ≤ i ≤ m, Si ∈ C ∪ R, op i ∈ {], ∪} − is an update operator, and pi ∈ P is an input predicate of the same arity as Si —intuitively, op i = ] (resp., op i = ∪) − 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 (9) of Example 1 first enriches the concept M ale in O by the extension of the predicate boy in P via ], and then queries the concept Male over the modified ontology. Semantics. The semantics of a DL-program Π = hO, Pi is defined in terms of its grounding gr(Π) = hO, gr(P)i over C, i.e., gr(P) contains all ground instances of rules r in P over C. In the remainder, by default we assume that Π is ground. 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 ∈ I and a DL-atom a of the form (2) if O ∪ τ I (a) |= Q(c) (3) I Sm where τ (a) = i=1 Ai (I), and • Ai (I) = {Si (t) | pi (t) ∈ I}, for op i = ]; • Ai (I) = {¬Si (t) | pi (t) ∈ I}, for op i = ∪. − 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 ∈ P. We denote that I satisfies (is a model of) an object o (atom, rule, etc.) by I |=O o. 1 We disregard here for simplicity the less used constraints-operator ∩ − and subsumption queries. Example 3 (cont’d). In Example 1, I = {ischildof (john, alex ), boy(john)} satis- fies a = DL[Male ] boy; Male](john), since O ∪ λI (a) |= Male(john), while I 6|=O DL[; Adopted ](john), as the input list is empty and O 6|= Adopted (john). An (flp-)answer set of Π = hT ∪ A, Pi is any interpretation I that is a ⊆-minimal I model of the flp-reduct ΠFLP , which maps any set P of rules and I ⊆ HB Π to the rule I I I set PFLP = {rFLP | r ∈ gr(P)}, where rFLP = r if the body of r is satisfied, i.e., I |=O bi , for all bi , 1 ≤ i ≤ k and I 6|=O bj , for all k < j ≤ m; otherwise, rFLP I is void. A DL-program Π is inconsistent, if it has no answer set. An interpretation I is an (flp-)deletion repair answer set of Π = hT ∪ A, Pi, if it is an flp-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 (4) from A, then I = {boy(john), ischildof (john, alex ), contact(john, pat)} is an answer set. Along I with the facts (7) and (8) the flp-reduct PFLP contains the ground rule (11), where X and Y are substituted by john and pat respectively. The interpretation I1 = {boy(john), ischildof (john, alex )} is a deletion repair answer set with a deletion repair A01 = {Male(pat), Male(john)}. In DL-Lite A ontologies, inconsistency arises by few assertions. Proposition 1 (cf. [3]). In DL-Lite A given a TBox T every ⊆-minimal ABox A such that T ∪ A is inconsistent fulfills |A| ≤ 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 I 0 ⊆ I of an interpretation I and a set A0 ⊆ A of ABox assertions from the ontology, we can conclude that I |=O Q(t). The evaluation of d w.r.t. I reduces then to test whether some support set S = I 0 ∪ A0 exists; to this end, a sufficient collection of such sets S can be precomputed and stored. Fortunately, for DL-Lite A this is efficiently possible. To simplify matters and avoid dealing with I 0 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 ∈ λ, ◦ ∈ {], ∪} − and c ∈ 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 ∪ {Pp v P | P ] p ∈ λ} ∪ {Pp v ¬P | P ∪p − ∈ λ}, and for an interpretation I, let OdI = Td ∪A∪{Pp (t) ∈ Ad | p(t) ∈ I}. Then we have: Proposition 2. For every O = T ∪ A, DL-atom d = DL[λ; Q](t) and interpretation I, I I |=O d iff I |=Od DL[; Q](t) iff OdI |= Q(t). Unlike (3), in OdI there is a clear distinction between native assertions and input assertions of d w.r.t. I (via facts Pp and axioms Pp v (¬)P ), mirroring the lp-input of d. 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 = {P (c)} and Td ∪ S |= Q(t), or (ii) S = {P (c), P 0 (d)} such that Td ∪ S is inconsistent, where c ∪ d has at most three distinct constants; by Supp O (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) ∈ S it holds that p(c) ∈ I. Example 5 (cont’d). The set {hasParent(john, pat)} is a support set for the DL-atom DL[; hasParent](john, pat) w.r.t. O, and so is {Male(pat)} for the DL-atom a = DL[Male ] boy; Male](pat). Moreover, {Male boy (pat)} is in Supp O (a) but incoher- ent 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 |=O d iff some S ∈ Supp O (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 interpreta- tion I such that I |=O d iff Supp O (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 DL- atom 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 = {X, Y, Z} be distinct variables such that X ⊆ V and let C = {a, b, c}. A nonground support set for d w.r.t. T is a set S = {P (Y )} resp. S = {P (Y ), P 0 (Y 0 )} such that (i) Y , Y 0 ⊆ V and (ii) for each substitution θ : V → C, the instance Sθ = {P (Y θ)} (resp. Sθ = {P (Y θ), P 0 (Y 0 θ)}) 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 Supp O (d) ⊆ Supp O0 (d)); three variables suffice as at most three different constants are involved. Example 6 (cont’d). Certainly {hasParent(X, Y )} is a nonground support set for the DL-atom DL[; hasParent](X, Y ), and so are {Male(X)} and {Male boy (X)} for the DL-atom a(X) = DL[Male ] boy; Male](X). But also, {Male boy (X), Female(X)} 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., {A(X), R(X, Y )} by {A(X)}) 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 ∈ Supp O (d(Xθ)), some S 0 ∈ S exists s.t. S = S 0 θ0 , for some extension θ0 of θ to V . TBox classification is well studied in Description Logics [1]. For example, [9] discusses it for EL 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, ¬∃R, ¬∃R− ) with positive replacements C (R, ∃R, ∃R− ). 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ˆ ∈ AS(Π̂) do ˆ Dp ← {a | ea ∈ I}; ˆ Dn ∈ {a | nea ∈ I}; ˆ SIgr ← Gr(S, I,ˆ A); ˆ I ˆ I (c) if Sgr (a) 6= ∅ for a ∈ Dp and every S ∈ Sgr (a) for a ∈ Dn fulfills S ∩ A 6= ∅ then (d) for all a ∈ Dp do ˆ (e) if some S ∈ SIgr (a) exists s.t. S ∩ A = ∅ then pick next a ˆ ˆ else remove each S from SIgr (a) s.t. S ∩ A ∩ a0 ∈Dn SIgr (a0 ) 6= ∅ S ˆ (f) if SIgr (a) = ∅ then pick next Iˆ end ˆ A0 ← A \ a0 ∈Dn SIgr (a0 ); S (g) (h) ˆ hT ∪ A0 , Pi) then output I| if flpFND(I, ˆΠ end end Example 7 (cont’d). Consider the DL-atom a = DL[Male ] boy; Male](X) in our run- ning example. For computing a complete family S of nonground support sets for a w.r.t. O, we may refer to Ta = T ∪ {Male boy v Male} and its classification Clf (Ta ). Hence, S1 = {Male(X)} and S2 = {Male boy (X)} are the only unary nonground support sets of a. Further nonground support sets are obtained by computing minimal conflict sets, yielding {P (X), ¬P (X)} for each P ∈ C ∪ R, as well as {Male boy (X), ¬Male(X)}, {Male(X), Female(X)}, and {Male boy (X), Female(X)}. However, since we are in- terested 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 = {S1 , S2 } 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 ˆ Π to denote their restriction to the original language of Π. use I| 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 corre- sponding 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 ˆ 0I| ˆ I| check (subset minimality of I| ˆ Π w.r.t. Π Π = hT ∪ A0 , P Π i) establishes repair FLP FLP 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 ˆ Next, for all ground DL-atoms in Dp ∪ Dn , the function guessed true (resp. false) in I. ˆ 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 α ∈ A that also supports some atom a0 ∈ 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 ∈ 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 {ea , neb } ⊆ Iˆ for a = DL[; hasParent](john, pat) and ˆ b = DL[Male ] boy; Male](pat). Then, SIgr (a)= {{hasParent(john, pat)}} we get ˆ ˆ to the else part of Step (e) where nothing is removed from SIgr (a), since SIgr (b) = ˆ ˆ {{Male(pat)}} and SIgr (a) ∩ SIgr (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| ˆΠ ˆ 0 is an answer set of Π = hT ∪ A, Pi. If I is a compatible set for Π = hT ∪ A , Pi 0 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. 5 Implementation and Experiments We implemented Algorithm SupRAnsSet within the DLVHEX evaluation framework2 , which allows us to effectively compute deletion repair answer sets for DL-Lite A . 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 real- ize 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 subsump- tions 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: S̄A ← r(S), nea ; supa ← r(S), ea , not S̄A ; ← 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)). Fur- thermore, pP , npP , and supa are fresh predicates not in P, and S̄A 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 ˆ resp. encodes deletion repair candidates, according to SupRAnsSet. prunes candidates I, 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 (11) and (12), not involved in conflicts, have been dropped from P. Instances are varied in terms of facts over I included in P by increasing the probability p/100 (p ranges from 5 to 35): for every child c, one additional fact isChildOf (c, p) is added with probability p/100 for a random male adult non-parent; as well boy(c) is included with probability p/100. 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: A50 A1000 Pconn Pguess p p AS rep AS rep AS rep AS rep 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) Table 1. Family and Network benchmark results O = {∃forbid v Block , Broken v Block , Block v ¬Avail }. We consider two DL-programs, Pguess and Pconn , over O that are randomly gener- ated as follows. Pguess contains for any node n the fact node(n) with probability p/100, and the following rules: (1) go(X, Y ) ← open(X), open(Y ), DL[; edge](X, Y ). (2) route(X, Z) ← route(X, Y ), route(Y, Z). (3) route(X, Y ) ← go(X, Y ), not DL[Block ] block ; forbid ](X, Y ). (4) open(X) ∨ block (Y ) ← node(X), not DL[; ¬Avail ](X). (5) negIs(X) ← node(X), route(X, Y ), X 6= Y. (6) ⊥ ← node(X), not negIs(X). Intuitively, (1), (2) and (3) recursively determine routes over non-blocked (open) nodes; where (3) expresses that by default a route is recommended unless it is known to be forbidden. Rule (4) amounts to guessing for each node not known to be unavailable, whether it is blocked or not, i.e. it contains nondeterminism, which makes rule processing challenging. Rules (5) and (6) encode the requirement that no input node is isolated w.r.t. the resulting routes. 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 (1) and (2) above, and variants of (3), (4) and (6): (30 ) route(X, Y ) ← go(X, Y ), not DL[; forbid ](X, Y ). (40 ) open(X) ← node(X), not DL[; ¬Avail ](X). (60 ) ⊥ ← in(X), out(Y ), not route(X, Y ). Intuitively, rather than guessing, (40 ) expresses that each node is open by default unless known to be unavailable, and by (60 ) the program checks whether each in-node is connected to all out-nodes (thus ensuring they are available, i.e. not blocked). Results. The results that we obtained for these settings are given in Table 1. Instances are grouped by the probability (the value p) used for generating them. For each p, 25 instances were generated and their average running time (in seconds) to compute a first answer set and deletion repair answer set is reported. The naive approach [7] has not been implemented (but expectedly would time out for even the smallest problem instances). 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 (4). Employing a default in Pconn rather than guessing scales linearly, however. For Pconn we also considered different splits (rather than p = 1/2) between in and out, although without significant change. Additionally, our approach has been evaluated on inconsistent programs over the LUBM3 ontology; more precisely, over a DL-Lite A 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-Lite A ontologies to constraint matching, providing a base for effective deletion repair answer set computation under flp- semantics. 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 re- pairs, 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 fundamen- tally: (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 EL. While no small complete support families exist for EL 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 EL reasoner. 3 http://swat.cse.lehigh.edu/projects/lubm/ 4 http://code.google.com/p/combo-obda/ References 1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.: The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, New York, NY, 2nd edn. (2007) 2. Borgida, A., Calvanese, D., Rodriguez-Muro, M.: Explanation in DL-Lite. In: Baader, F., Lutz, C., Motik, B. (eds.) Description Logics. CEUR Workshop Proc., vol. 353. CEUR- WS.org (2008) 3. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning 39(3), 385–429 (2007) 4. Calvanese, D., Ortiz, M., Simkus, M., Stefanoni, G.: The complexity of explaining negative query answers in DL-Lite. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Principles of Knowledge Representation and Reasoning: Proc. of 13th International Conference, KR 2012, pp. 583–587. AAAI Press (2012) 5. Eiter, T., Fink, M., Krennwallner, T., Redl, C.: Liberal safety for answer set programs with external sources. In: desJardins, M., Littman, M.L. (eds.) Proc. of 27th Conf. on Artificial Intelligence (AAAI ’13), pp. 267–275. AAAI Press (2013) 6. Eiter, T., Fink, M., Redl, C., Stepanova, D.: Exploiting support sets for answer set programs with external evaluations. In: Brodley, C., Stone, P. (eds.) Proc. 28th Conf. on Artificial Intelligence (AAAI ’14), AAAI Press (2014), To appear. 7. Eiter, T., Fink, M., Stepanova, D.: Data repair of inconsistent dl-programs. In: Rossi, F. (ed.) Proc. 23rd International Joint Conf. on Artificial Intelligence (IJCAI-13), pp. 869–876. AAAI Press/IJCAI (2013) 8. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the Semantic Web. J. Artificial Intelligence 172(12- 13), 1495–1539 (2008) 9. Kazakov, Y., Krötzsch, M., Simancik, F.: The incredible ELK - from polynomial procedures to efficient reasoning with EL ontologies. J. Autom. Reasoning 53(1), 1–61 (2014) 10. Lembo, D., Santarelli, V., Savo, D.F.: A graph-based approach for classifying OWL 2 QL ontologies. In: Eiter, T., Glimm, B., Kazakov, Y., Krötzsch, M. (eds.) Description Logics. CEUR Workshop Proc., vol. 1014, pp. 747–759. CEUR-WS.org (2013) 11. Masotti, G., Rosati, R., Ruzzi, M.: Practical ABox cleaning in DL-Lite (progress report). In: Rosati, R., Rudolph, S., Zakharyaschev, M. (eds.) Description Logics. CEUR Workshop Proce., vol. 745. CEUR-WS.org (2011) 12. Motik, B., Rosati, R.: Reconciling Description Logics and Rules. Journal of the ACM 57(5), 1–62 (2010) 13. Rosati, R., Ruzzi, M., Graziosi, M., Masotti, G.: Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies. In: Cudré-Mauroux, et al. (eds.) International Semantic Web Conference (2). Lecture Notes in Computer Science, vol. 7650, pp. 337–349. Springer (2012)