Data Repair of Inconsistent DL-Programs

1 Introduction

Nonmonotonic Description Logic (DL-)programs [Eiter et al., 2008b] are a prominent approach to combine Description Logic knowledge bases (alias, ontologies) with nonmonotonic logic programming. Different from other approaches, see [Motik and Rosati, 2010] and references therein, they offer a loose coupling between the rules and the ontology through special DL-atoms which serve as query interfaces to the ontology. The possibility to add information from the rules part prior to query evaluation allows for adaptive combinations and to solve advanced reasoning problems on top of ontologies. Noticeably, the abstract design of DL-programs has been fruitfully generalized to model view-based access of external information sources from rules beyond ontologies.

Example 1. Consider the DL-program Π in Figure 1, which captures information about children of a primary school and their parents in simplistic form. It consists of an ontology O

∗This research has been supported by the Austrian Science Fund (FWF) project P20840, P20841, P24090, and by the Vienna Science and Technology Fund (WWTF) project ICT08-020.

Figure 1: DL-program Π over a family ontology

which contains a taxonomy T of concepts (i.e., classes) in (1)- (3) and factual data (i.e., assertions) A about some individuals in (4)-(6). The rules P contain some 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 ) the constraint that a child has for sure at most one father, unless it is adopted; finally (11)-(12) single out contact persons for children, which by default are the parents; for adopted children, fathers from the ontology are omitted if some other contact exists.

However, the information flow between the rules and the ontology can have unforseen effects and cause inconsistency such that no answer set, (i.e., model), of a DL-program exists. In the above example, this happens 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 yields no information and is unusable. To deal with this, [P¨uhrer et al., 2010; Fink, 2012] effected inconsistency tolerance by suppressing or weaking information leading to inconsistency in model building. However, the problem to repair the program, i.e., change formulas in it to obtain consistency (which is a natural and ubiquitous approach in data and knowledge representation), has to the best of our knowledge not been considered.

In this paper, we consider this issue, which due the interaction between the rules and the ontology is nontrivial and at least as challenging as for these parts. Ontology repair has been studied in many works, e.g., in [Lembo et al., 2010; Bienvenu, 2012] for consistent query answering; repairing nonmonotonic logic programs instead is less developed (cf. [Sakama and Inoue, 2003]). In the light of this and as the rules are on top of the ontology (such that their plausibility can be separately assessed), we take the view that the latter, and here in particular its data part might not be fully correct.

In the above example, suitable changes of the ontology facts make the DL-program consistent. For example, deleting hasParent(john, pat) from A leads to the answer set I1 = {ischildof (john, alex), boy(john)}, while the addition of Adopted(john) leads to I2 = {ischildof (john, alex ), boy(john), hasfather(john, pat), contact(john, pat)}; yet other possibilities exist. However, not all repairs might be acceptable; the question is how to find suitable repairs which, as an additional constraint, should not increase the complexity of DL-programs.

We tackle this challenge with the following contributions.

1. We formalize repairing DL-programs and introduce the notions of repair and repair answer set (Section 3). They are based on changes of the assertions in the ontology that enable answer sets. As it turns out, repair answer sets do not have higher complexity than ordinary answer sets (more precisely, weak and FLP answer sets) if queries in DL-atoms are evaluable in polynomial time; to ensure this, we concentrate on the Description Logic DL-LiteA [Calvanese et al., 2007]. We model repair preference by functions σ that select preferred ones from a set of candidates. As preference is a known source of complexity, we focus on selections σ with a benign independence property (which some practicable σ enjoy).
2. We show how an algorithm that is used for evaluating DLprograms can be gracefully extended to compute repairs resp. repair answer sets, with an optional selection σ featuring independence (Section 4). The extension involves a generalized ontology repair problem (ORP), which arises from a candidate answer set and the DL-atoms of the program. It consists of two sets D1,D2 of entailment and non-entailment queries to the ontology, with possible temporary assertions, and asks for an ABox satisfying these sets. Importantly, under independence the σ-selected ABoxes also yield, modulo a conditional check on the rules part, the σ-selected repairs of the program.

(3) Furthermore, we analyze the complexity of the ORP problem (Section 5). Unsurprisingly, it is intractable (NPcomplete) for DL-LiteA in general, but we show that NPhardness holds also in plain ontology settings, due to the temporary assertions. However, we also identify several tractable cases of σ-selections that are useful in practice.

While we focus here on DL-LiteA, our approach and basic results can be extended to DL-programs with ontologies in other Description Logics as well.

2 Preliminaries

Informally, a DL-program consists of a description logic knowledge base (or ontology) O and a set P of logic programming rules that may query O via special atoms in the rule bodies; the queries are evaluated subject to temporal updates of O with assertions given by predicate values in P .

2.1 Description Logic Knowledge Bases

We consider Description Logic (DL) knowledge bases (KBs) over a signature Σo = 〈I,C,R〉 with a set I of individuals (constants), a set C of concept names C (unary predicates), and a set R of role names R (binary predicates) as usual.

A DL knowledge base (or ontology) is a pair O = 〈T , A〉 of a TBox T and an ABox A, which are finite sets of formulas capturing taxonomic resp. factual knowledge, whose form depends on the underlying DL.

In DL-LiteA, concepts C, denoting sets of objects, and roles R, denoting binary relations between objects, are formed according to the following syntax, where A ∈ C is an atomic concept and P ∈ R an atomic role:

DL-LiteA TBox axioms are then of the form:

Axioms in the first column are positive inclusions (among concepts and roles, respectively), and those in the second column disjointness axioms; (func R) is a functionality axiom. An assertion is a formula A(c) or P(c, d) where A ∈ C, P ∈ R, and c, d ∈ I (called positive) or its negation, i.e., ¬A(c) resp. ¬P (c, d) (negative). 1 An example of a DL-LiteA ontology is O in Figure 1. The semantics of DL ontologies O is based on first-order interpretations I = 〈∆I , ·I 〉 of Σo with a domain ∆I and an interpretation function·I [Calvanese et al., 2007] and is captured by a modular translation τ(O) of O to first-order logic [Baader et al., 2007]; O is consistent, if τ(O) is satisfiable. Throughout the paper, we assume that ontologies are in DL-LiteA, under the unique names assumption as usual.

2.2 Description Logic Programs

DL-rules extend rules in non-monotonic logic programs with special DL-atoms. They are formed over a signature Σ = 〈C, I, P, C, R〉 where Σo = 〈I, C, R〉 is a DL signature, C ⊇ I is a set of constant symbols and P is a finite set of predicate symbols (called lp predicates) of arities ≥ 0 disjoint with C,R; for simplicity, we assume here C = I.

Syntax. A (disjunctive) DL-programΠ = 〈O, P〉 consists of a DL ontology O and a finite set P of DL-rules r of the form

a1 ∨ . . . ∨ an ← b1, . . . , bk, not bk+1, . . . , not bm , (1) where each ai, 0 ≤ i ≤ n is a first-order atom p(⃗t) with 1 ≤ i ≤ m, is either an lp-atom or a DL-atom; if n = 0, the

predicate p ∈ P (called ordinary or lp-atom) and each bi, rule is a constraint, and if n ≤ 1, it is normal.

A DL-atom a(t) is of form DL[λ; Q](⃗t), where (a) the list

λ = S1 op1 p1, . . . , Sm opm pm, m≥ 0, (2) for each i, 1 ≤ i ≤ m, Si ∈ C∪R, opi ∈ {⊎, -∪, -∩} is an update operator, and pi ∈ P is an input predicate of the same arity as Si; intuitively, opi =⊎ (resp., opi = -∪) increases Si (resp., ¬Si) by the extension of pi, while opi = -∩ constrains Si to pi; (b) Q(⃗t) is a DL-query, which has one of the forms (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; (iii) Q is an inclusion axiom and ⃗t = ϵ; (iv) Q is a disjointness axiom and ⃗t = ϵ; or (v) ¬Q′ (⃗t) where Q′ (⃗t) is from (i)-(iv). We skip (⃗t) for ⃗t = ϵ.

1 Negative assertions ¬F(⃗t) are easily compiled to positive ones using a fresh concept resp. role name F¬ and F¬(⃗t), F¬ ⊑ ¬F .

Example 2. In the Example 1 the rule (9) contains a DL-atom DL[Male ⊎ boy; Male](Y ), where we first enrich the concept Male in O by the extension of the predicate boy in P via the operator ⊎. We then query the concept Male over the

modified version of the ontology.

Semantics. The semantics of a DL-program Π = 〈O, P〉 is in terms of its grounding grd(Π) = 〈O, grd(P)〉 over C, i.e., grd(P) contains all ground instances of rules r in P over C. In the remainder, by default we assume Π is ground.

A (Herbrand) interpretation of Π is a set I ⊆ HBΠ of ground atoms, where HBΠ is the Herbrand base w.r.t. C and P (i.e. all ground atoms over C and P); I satisfies an lp- or DL-atom a, if (i) a ∈ I, if a is an lp-atom, and (ii) τ(〈T ,A∪ λI (a)〉) |= Q(c) where O = 〈T ,A〉, if a is a DL-atom of form (2), where λI (a) = ⋃mi=1 Ai(I),

• Ai(I) = {Si(⃗t) | pi(⃗t) ∈ I}, for opi = ⊎;
• Ai(I) = {¬Si(⃗t) | pi(⃗t) ∈ I}, for opi = -∪;
• Ai(I) = {¬Si(⃗t) | pi(⃗t) ∈ HBΠ \ I}, for opi = -∩.

Satisfaction of a DL-rule r resp. set P of rules by I is then 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.) with I |=O o.

Example 3. Going back to the Example 1, the interpretation I = {ischildof(john, alex), boy(john)} satisfies the DLatomo = DL[Child ⊎ boy; ¬Male](john), asO∪λI (o) |= ¬Male(john). Furthermore, I ̸|=ODL[;Adopted](john), since the input list of the respective DL-atom is empty and O ̸|= Adopted(john).

Finally, answer sets of Π are defined using a reduct ρx that maps any set P of rules and I ⊆ HBΠ to a set ρxP I of rules: I is an x-answer set of Π, if I is a ⊆-minimal model of ρxΠI =〈O, ρxP I 〉 (called the x-reduct of Π); ASx(Π) is the set of all x-answer sets of Π. In particular, for weak (x = weak ) and FLP (x = flp) answer sets [Eiter et al., 2005]:

• The weak-reduct is ρweakP I = {wrI | r ∈ P} where wrI is void if either I |= bj, for some k < j ≤ m or I ̸|=O bi, for some DL-atom bi, 1 ≤ i ≤ k; otherwise, wrI removes all DL-atoms bi and all not bj from the rule body.
• The flp-reduct is ρflpP I = {f rI | r ∈ P} where f rI = r if the body of r is satisfied, i.e., I |=O bi, for all bi, 1 ≤ i ≤ k and I ̸|=O bj, for all k < j ≤m; otherwise, f rI is void.

For further reduct-based answer sets, see e.g. [Eiter et al., 2008b; Lukasiewicz, 2010; Wang et al., 2010; Shen, 2011].

A DL-program is inconsistent, if it has no answer set.

Example 4 (cont'd). As mentioned, Π is inconsistent; if we drop (4) fromA, then I ={ischildof (john, alex), boy(john), contact(john, pat)} is both a weak and an FLP answer set. Along with the facts (7) and (8) the flp-reduct ρflpP I contains the ground rule (11), where X and Y are substituted by john and pat respectively.

3 Repair Answer Sets

We now turn to repairing an inconsistent DL-program 〈O, P〉. In our setting, we assume that the rule part P, which is on top of the ontology O = 〈T ,A〉, is reliable and that the cause for inconsistency is in the latter. Thus when searching for a repair, modifications should only be applied to O. In principle, the TBox T and the ABox A of the ontology could be subject to change; however, as usually the TBox is well-developed and suitable TBox change is less clear in general (the more by an external user), we confine to change only the ABox.

Hence given a possibly inconsistent DL-program, our goal is to find an ABox such that replacing the ABox A by it makes the DL-program consistent. The answer sets of such a "repaired" DL-program are then referred to as repair answer sets of the program. Formally, they are defined as follows.

Definition 5. Given a DL-program Π= 〈O, P 〉, O = 〈T , A〉,

• an ABox A′ is an x-repair of Π, if (i) O′ =〈T ,A′ 〉 is consistent, and (ii) Π′ = 〈O′ , P〉 has some x-answer set; the set of all x-repairs of Π is denoted repx(Π).
• I is an x-repair answer set of Π, if I ∈ ASx(Π′ ), where Π′ = 〈O′ , P〉, O′ =〈T ,A′ 〉, and A′ ∈ repx(Π); the set of all x-repair answer sets of Π is denoted by RASx(Π).

Furthermore, we denote by repIx (Π) = {A′ ∈ repx(Π) | I ∈ ASx(Π′ ), Π′ = 〈O′ , P 〉, O′ = 〈T , A′ 〉} the set of all ABoxes A′ under which I becomes an x-answer set of Π.

Example 6. Reconsider Π in Example 1. The interpretation I1 = {ischildof (john, alex ), boy(john)} is an flp-repair answer set with flp-repair A′1 = {Male(pat ), Male(john)}.

We first briefly address the complexity of repair answer sets, but refrain from an extensive complexity study here.

Theorem 7. Given a ground DL-program Π, deciding whether RASx(Π) ̸= ∅ is (a) ΣP2 -complete for arbitrary Π and x ∈ {flp, weak}; (b) ΣP2 -complete for normal Π and x = flp; (c) NP-complete for normal Π and x = weak . Deciding ASx(Π) ̸= ∅ has in all cases the same complexity as deciding RASx(Π) ̸= ∅.

Nonsurprisingly, repair answer sets and ordinary answer sets have the same complexity in general. Indeed, a repair A′ can be jointly guessed with an answer set I, and the test whether I is a minimal model of ρxΠ′I can be done as usual; the upper bounds are then immediate from the following:

Proposition 8. Given any I ⊆ HBΠ, O in DL-LiteA, and DL-atom a, deciding I |=O a is feasible in polynomial time.

This proposition is straightforward from the definition of the DL-atom and a well-known result presented in [Calvanese et al., 2007]. The hardness is inherited from ordinary answer set programs, except for normal FLP answer sets, for which a common Σp2 -hardness proof of ordinary disjunctive logic programs can be adapted.

3.1 Selection Preference

Clearly, not all repairs are equally useful or interesting for a certain scenario. For instance, repairs that have no common assertions with the original ABox might be unwanted; repairs that introduce assertions that are not in the initial ABox; repairs that would cause non-minimal change etc.

Formally, we model preferred repairs using a selection function σ : 2AB×AB → 2AB , where AB is the set of all ABoxes, that given a set S of ABoxes and an ABox A, returns a set σ(S, A) ⊆ S of preferred (or selected) ABoxes.

This notion captures a variety of selection principles, including minimal repairs according to some preference relation, or some global selection property. We then define

Definition 9. Given Π = 〈O, P 〉, O = 〈T , A〉, and a selection σ, we call rep(σ,x)(Π) = σ(repx(Π), A) the (σ, x)-repairs of Π. An interpretation I ⊆ HBΠ is a (σ, x)-repair answer set of Π, if repI(σ,x) (Π) ̸= ∅, where repI(σ,x) (Π) = rep(σ,x)(Π)∩ repIx (Π); RAS(σ,x)(Π) is the set of all such answer sets.

In general, even polynomially computable selections σ may incur intractability, like e.g. selecting ABoxes A′ with setminimal change to A, or with smallest Dalal (Hamming) distance. We aim at selections that are useful in practice and have benign computational properties. Useful in this regard are selections of the following kind.

Definition 10. A selection σ : 2AB×AB → 2AB is independent, if σ(S, A) = σ(S′ , A) ∪σ(S \ S′ , A) whenever S′ ⊆ S.

Independence allows us to decide whether a given repair A′ ∈ S is selected by σ without looking at other repairs, and composition works easily. This makes the introduced property valuable, since independent selection functions of different kind can be conveniently combined without a major increase in the complexity. Clearly, set-minimal change and smallest Dalal distance are not independent. On the other hand, selecting all ABoxes such that A′ ⊆ A, is obviously independent. The latter, and several other independent selections that are useful in practice, will be considered in Section 5.

Independence leads to the following beneficial property.

Proposition 11. For every Π and selection σ, if σ is independent, then repI(σ,x) (Π) ⊆ rep(σ,x)(Π), for every I ⊆ HBΠ.

Proof (Sketch). By definition rep(σ,x)(Π) = σ(repx(Π),A) and repI(σ,x) (Π) = σ(repIx (Π),A). Now since repIx (Π) ⊆ repx(Π) and σ is independent, we obtain σ(repx(Π),A) = σ(repIx (Π),A) ∪ σ(repx(Π)\repIx (Π),A), from which the result follows.

Proposition 11 implies that if we can turn an interpretation I into an answer set of Π by a σ-selected repair from the repairs which achieve this for I, then I is a σ-repair answer set of Π; that is, local selection is enough for a global σ-repair answer set. This will be exploited in the next section.

4 Computation

In this section we first recall the essentials of the evaluation algorithm for DL-programs in [Eiter et al., 2012] (given there for the more general class of so-called HEX-programs). We then present the core procedure of an extension for computing (σ, x)-repair answer sets.

4.1 Evaluation of DL-programs

DL-program evaluation builds on a rewriting ˆΠ of Π, where DL-atoms a are replaced by ordinary atoms (replacement atoms) ea, together with a guess on their truth by additional 'choice' rules. Given an interpretation ˆ I over this extended language, we use ˆ I|Π to denote its restriction to the original language of Π. A crucial notion is that of compatibily:

Algorithm 1: AnsSet : Compute ASx(Π) Input: A DL-program Π, x ∈ {weak , flp} Output: ASx(Π) for ˆ I ∈ AS(ˆΠ) do (a) if CMP(ˆ I , Π) ∧ xFND( ˆ I,Π) then output ˆ I |Π end end

Definition 12. [Eiter et al., 2012] A compatible set of a DLprogram Π = 〈O, P〉 is an interpretation ˆ I, such that

(i) ˆ I is an answer set of ˆΠ, and (ii) ea ∈ ˆ I iff ˆ I|Π |=O a, for all a = DL[λ; Q](c) of Π.

Conversely, given an interpretation I of Π, we denote by Ic the interpretation of ˆΠ, such that Ic coincides with I on nonreplacement atoms, and each replacement atom ea is in Ic (i.e., true) iff I |=O a for the respective DL-atoms a.

With these concepts in place, we are ready to describe the basic algorithm AnsSet (cf. Algorithm 1) for evaluating a DL-program Π = 〈O, P 〉 adapted from [Eiter et al., 2012].

First, ˆΠ is evaluated by an ordinary ASP solver. For every answer set ˆ I, in (a), the function CMP checks for compatibility, while xFND tests for foundedness, i.e., whether ˆ I|Π is a ⊆-minimal model of the reduct ρxΠ ˆ I|Π . In case of x = weak it just returns true, otherwise (x = flp) it checks for disjointness with unfounded sets as defined in [Eiter et al., 2012]). If both tests succed, then ˆ I|Π is output as an answer set.

An important link between the answer sets of Π and ˆΠ is:

Proposition 13. If I ∈ ASx(Π) then Ic ∈ ASx(ˆΠ).

While AnsSet is clearly sound, from this result its completeness follows, i.e. restricting the search to ASx(ˆΠ) does not yield any loss of answer sets.

4.2 Repair Computation

In this subsection, we first aim at a procedure for computing (σ, x)-repairs given an independent selection function σ. Then, we briefly describe how its main subroutine can be used for an extension of AnsSet that computes answer sets if they exist, and (σ, x)-repair answer sets otherwise.

A first key observation is that Proposition 13 can be generalized to repair answer sets, more precisely:

Proof (Sketch). By definition of RASx(Π), we get that I ∈ AS(Π′ ), where Π′ = 〈O′ , P〉, O′ = 〈T ,A′ 〉 and A′ ∈ repx(Π). Since by Proposition 13 Ic ∈ AS(ˆΠ′ ) and ˆΠ = ˆΠ′ , the result immediately follows.

Thus, our approach is to traverse AS(ˆΠ) and check for each answer set ˆ I whether it is a (σ, x)-repair answer set of Π. The latter proceeds in two steps, where the first step is to search for potential σ-repairs of the ontology such that Definition 12(ii) holds for ˆ I. More formally (and slightly generalized), we define an ontology repair problem as follows.

Algorithm 2: RepAns: Compute rep ˆ I |Π (σ,x) (Π) Input: Π=〈O, P〉, O=〈T ,A〉, ˆ I∈AS(ˆΠ), σ, x∈{weak, flp} Output: rep ˆ I|Π (σ,x) (Π) for A′ ∈ ORP(ˆ I, Π, σ) do if CMP( ˆ I, 〈T , A′ , P 〉) ∧ xFND( ˆ I, 〈T ,A′ , P〉) then output A′ end end

Definition 15. An ontology repair problem (ORP) is a triple P = 〈O,D1,D2〉 where O = 〈T ,A〉 is an ontology and Di = {〈U i j ,Qij 〉 | 1≤j ≤mi}, i = 1, 2, are sets of pairs where each U i j is an ABox and each Qij is a DL-query. A repair (solution) for P is any ABox A′ such that

• (i) the ontology O′ = 〈T ,A′ 〉 is consistent;
• (ii) τ(〈T ,A′ ∪U 1

j 〉) |= Q1j holds for 1 ≤ j ≤ m1; j 〉) ̸|= Q2j holds for 1 ≤ j ≤ m2.

For a selection σ, the σ-repairs of P are σ-rep(P) = σ(rep(P),A), where rep(P) is the set of all repairs of P.

Intuitively every pair 〈U i j ,Qij 〉 corresponds to some DLatom aij = DL[λij ;Qij ](⃗t) under an interpretation I, i.e., such that U i j = λI (aij ). Moreover, a1j (resp., a2j ) should evaluate to true (resp. false) such that I is a (potential) answer set of Π. We illustrate these ideas by an example, which also shows how an answer set ˆ I of ˆΠ induces a corresponding ORP instance.

Example 16. Let Π = 〈O, P〉 be a DL-program, where

Let a1 =DL[C-∪r;D](c) and a2 =DL[D⊎ p,E-∪r; ¬C](c), and consider the interpretation ˆ I = {p(c), r(c), q(c), ea1 }, i.e., a1 is guessed true and a2 false. The corresponding ORP is given by P = 〈O, D1, D2〉, where D1 = {〈{¬C(c)}; D(c)〉} and D2 = {〈{D(c), ¬E(c)}; ¬C(c)〉}.

The procedure RepAns (cf. Algorithm 2) calls the subroutine ORP ( ˆ I, Π, σ) to compute σ-repairs of the corresponding ORP. Further on, RepAns re-uses functions CMP and xFND to check whether ˆ I is an answer set of ˆΠ′ and that it is founded w.r.t. Π′ = 〈O′ , P〉, O′ =〈T ,A′ 〉. It thus computes the set of all ABoxes under which ˆ I becomes a (σ, x)-repair answer set.

Let then RepAnsSet be the algorithm that iteratively calls RepAns for every ˆ I ∈ AS(ˆΠ), and that outputs any ˆ I where the result is nonempty. We then can show:

Theorem 17. RepAns and RepAnsSet are sound and complete for rep(σ,x)(Π) and RAS(σ,x)(Π), respectively, for independent selection σ.

Proof (Sketch). Soundess. Let A′ be an output of RepAns. Towards contradiction, suppose A′ ̸∈ rep ˆ I |Π (σ,x) (Π). Then ˆ I|Π ̸∈ AS(Π′ ), where Π′ = 〈T , A′ , P〉 and A′ is σ-selected. Clearly A′ is σ-selected, since otherwise A′ ̸∈ ORP(ˆ I , Π, σ)

and A′ is not in the output. As it is given that ˆ I ∈ AS(ˆΠ), it must hold that either ˆ I is not a compatible set of Π′ or it is not x-founded. If either of these is true then the corresponding procedure CMP or xFND returns false and A′ is not in the output, which leads to contradition.

Completeness. Let rep ˆ I |Π (σ,x) (Π) be the set of all σ-selected repairs for Π that turn ˆ I|Π into an x-repair answer set. Towards contradiction assume that there exists some A′ ∈ rep ˆ I |Π (σ,x) (Π), which is not an output of the algorithm RepAns. Then either (1) A′ ̸∈ ORP(ˆ I,Π, σ); (2) CMP(ˆ I, 〈T ,A′ , P〉) = false or (3) xFND(ˆ I, 〈T ,A′ , P〉) = false. If (1) holds, then A′ is not a solution of the ORP problem. Thus either 〈T ,A′ 〉 is unsatisfiable (contradiction to A′ ∈ rep ˆ I |Π (σ,x) (Π) by the definition of the repair) or the actual values of the DL-atoms do not coincide with the replacement atoms in ˆΠ (contradiction due to the failure of the compatibility check). Finally, if either (2) or (3) holds then we obtain contradiction, since A′ ∈ rep ˆ I |Π (σ,x) (Π) implies ˆ I|Π should be compatible and x-founded.

Using argument above and Proposition 14 soundness and completeness of RepAnsSet is easily established.

Similarly, RepAns could be intertwined with AnsSet for an extension that computes answer sets if they exist, and repair answer sets otherwise: while iterating over ˆ I ∈ AS(ˆΠ) and checking for compatibility and foundedness, also RepAns is called for every ˆ I, as long as no answer set is found. The results of these calls are stored and can, in case, eventually be used to output all (σ, x)-repair answer sets.

Note also that, for illustration, we kept the algorithms simple and several optimizations apply. For instance, to compute some (σ, x)-repair answer set, we can replace RepAns by a version that just computes a first witnessing ABox A′ . Moreover, caching ABoxes A′ and/or all answer sets of the respective Π′ (which can be straight output as (σ, x)-repair answer sets of Π) further reduces the search space.

A natural question is whether computing repair answer sets via compatible sets ˆ I of Πmakes repair answer set checking for ˆ I|Π easier than for abritrary interpretations I. Unfortunately, this is not the case.

Theorem 18. For ground Π= 〈O, P 〉 and I ⊆HBΠ, deciding whether I∈RASx(Π) is NP-complete for x=weak and Σp2 - complete for x=flp; hardness holds even if I = ˆ I|Π for a compatible set ˆ I of Π.

Proof (Sketch). For space issues the exposition is necessarily superficial and covers only the Σp2 -hardness result. The latter holds by a reduction from the problem of validity of a QBF formula

where E = χ1 ∨ . . . ∨ χr is a DNF formula, and each χk = lk1 ∧ lk2 ∧ lk3 is a conjunction of literals over atoms x1, . . . , xn, y1, . . . , ym. Given φ, we construct Π = 〈∅, A, P 〉 with A = {X1(a), . . . , Xn(a)} and P as follows:

Set I = {w(a), y1(a), . . . , ym(a)}, and note that I = ˆ I|Π for some compatible set ˆ I of Π and f ΠI = {(5), (6)}. Intuitively, due to (1)-(3) a repair A′ must be a maximal consistent subset of {Xi(a), ¬Xi(a) | 1≤i≤n}. Now I ∈RASflp(Π) implies the existence of some A′ s.t. by minimality of I, for each I ′ ⊆I\{w(a)} exists some k, where all f(lk1 ), f(lk2 ), f(lk3 ) are true, hence χk is true; thus φ is true. Conversely, every assignment to the xi witnessing that φ is true induces some A′ ∈ repIflp (Π).

This also yields a lower bound for (σ, x)-repair answer sets. Informally, the reason is that ORPs are a source of complexity that is orthogonal to minimality checking of models.

An interesting and practically relevant quest is for tractable cases, and a natural choice is to consider restricted programs and ORPs (see next section), such that compatibility checking is polynomial. While this yields tractability for weak-repair answer sets, checking foundedness for flp-repair answer sets remains intractable (although the complexity drops to NP).

5 Ontology Repair

The Ontology Repair Problem from above is an important subtask in the algorithm for computing repair answer sets. Nonsurprisingly, this problem is intractable in general; however, this holds already in simple settings.

Theorem 19. Deciding if an ORP P=〈O,D1,D2〉 has some repair is NP-complete, and NP-hard even if T =A=∅.

Proof (Sketch). A guess for a repair A′ is verifiable in polynomial time, as deciding each 〈T ,A′ ∪ U i j 〉 |= Qij is polynomial. NP-hardness holds by a reduction from SAT. Given φ=χ1∧ · · · ∧χm on atoms x1, . . . , xn, we construct P = 〈〈∅, ∅〉,D1,D2〉, with concepts Xj, ¯Xj for the xj and A, s.t. · D1 = {〈Ui, A(d)〉, 〈Vj , A(d)〉 | 1 ≤ i ≤ m}, where Ui = { ¯Xj(d), Xj ′(d) | xj∈χi, ¬xj ′∈χi}, Vj = {Xj(d), ¯Xj(d)}, · D2 = {〈∅, A(d)〉}.

Intuitively, by D2 a repair A′ must not contain A(d), and by D1 adding either (i) Ui or (ii) Vj to A′ causes inconsistency. By (i) A′ must contain some Xj(d) (resp. ¯Xj(d)) such that xj ∈ χi (¬xj ∈ χi), and by (ii) {Xj(d), ¯Xj(d)} ̸⊆ A′ ; thus A′ encodes a consistent choice of literals that satisfies φ.

We note that ORP has two sources of NP-hardness, viz. the data part (as in the proof above), and the taxonomy, which under σ-repairs may derive further assertions. Furthermore, each ORP can be encountered in the algorithm above, for some answer set ˆ I of a program ˆΠ; we show this on an example.

,

Example 20. Let P=〈O,D1,D2〉 where D1 ={δ1}, D2 = {δ2} with δ1 =〈{C(c), ¬D(c)}, ¬E(c)〉, and δ2 = 〈{D(d), ¬S(d)},C(d)〉. We introduce predicates pδ1 C , pδ1 D for δ1 and pδ2 D , pδ2 S for δ2 and construct Π = 〈O, PI ∪ PDL〉, where

Then, ˆΠ has a single answer set ˆ I, and it gives rise to P; (1) effects the pair δ1 in D1 and (2) the pair δ2 in D2.

5.1 Tractable Cases

To gain tractability for ORP, we consider restrictions on repairs and the ontology, as the pairs D1 and D2 are hard to control in practice. We present four tractable cases of σ-repairs with independent selection function σ, which are arguably useful in practice. In what follows, let P=〈O,D1,D2〉, O=〈T ,A〉.

1. Bounded δ±-change. A natural restriction is to bound the distance from the original ABox, i.e., use σδ±,k(S, A) = {A′ | |A′△A| ≤ k}, for some constant k. As the number m of possible ABox assertions is polynomial in the size of T and A, traversing all O((mk )) possible A′ and checking the repair condition is possible in polynomial time.
2. Deletion repair. Another important restriction is to allow only to delete assertions from the original ABox, i.e., use σdel(S,A) = {A′ | A′ ⊆ A}.

Example 21. In Example 1, eachA′ ⊂Aexcept {Male(pat), hasParent(john, pat)} is a deletion repair.

To achieve tractability, we exclude non-containment (̸⊑) DL-queries, i.e., of the form ¬Q where Q is an inclusion or disjointness axiom, fromP; let us call such ORPs ̸⊑-free.

Theorem 22. Deciding if a ̸⊑-free ORP P=〈O,D1,D2〉 with consistent O has a σdel-repair is polynomial.

For inconsistent O, or if non-containment DL-queries occur in P, the problem is NP-hard. The proof of Proposition 22 exploits the following property of the remaining DL-queries.

Lemma 23. If 〈T ,A〉 is consistent, then τ(〈T ,A∪U i j 〉) |= Qij iff τ(〈T ,A0 ∪U i j 〉) |= Qij for some A0 ⊆Awith |A0|≤1.

That is, at most one assertion α from A is sufficient to derive the query. This follows from a respective result for empty U i j and instance queries Qij in [Calvanese et al., 2007].

Now if τ(〈T , U i j 〉) |=Qij , we can drop 〈U i j ,Qij 〉 fromP if i=1, and stop if i=2 as no repair exists. Otherwise we let the support set Supp ij of Qij contain all assertions α such that τ(〈T , {α}∪U i j 〉) |=Qij . Then, any repair A′ must fulfill A′∩Supp 1j ̸=∅ for each j (i.e., be a hitting set), and must be disjoint with each Supp 2j ′ . Let then Sj := (Supp 1j ∩ A) \ ⋃j ′ Supp 2j ′ . A σdel-repair A′ exists iff each Sj is nonempty; the hitting sets of the Sj are all the σdel-repairs. The construction of the Sj and the check can be done in polynomial time, thus the overall problem is tractable. Furthermore, the (possibly exponentially many) σdel-repairs can be output in total polynomial time. This method can be extended to allow in addition also a constant number of new assertions in repairs.

1. Deletion δ+. This selection combines deletion and small change in a prioritized way. First one deletes assertions from A (assumed to be consistent) according to some polynomial method µ (using domain knowledge etc.) until some A0 = µ(O) ⊆ A results that satisfies Definition 15 (iii). If A0 is a repair, it is the result; otherwise, one looks for a close repair with bounded δ± change. That is σdel,δ+(S, A) = {µ(O)} if µ(O) ∈ S and σdel,δ+(S, A) = σδ+(S, µ(O)) otherwise.

Example 24 (cont'd). If µ(O) drops unreliable information about the sex of certain persons (e.g. pat), A0={Male(john), hasParent(john, pat)} is a deletion repair. If the constraint

(the sex of parents must be known) were in P , one would have to add Female(pat) to A0 to obtain a deletion-δ+ repair.

1. Addition under bounded opposite polarity. Repairs by unbounded additions become tractable, if few of them are positive resp. negative, i.e., the number of assertions with opposite polarity is bounded (which by Proposition 19 is necessary). That is, if A+ (resp., A-) is the positive (negative) part of an ABox A, then σbop(S,A) = {A′ ⊇ µ(O) | |A′+\A|≤k or |A′-\O|≤ k} where µ(O) is a starting ABox as above and k is a constant. The following result is instrumental.

Theorem 25. For a ̸⊑-free ORP P = 〈O,D1,D2〉, O = 〈T , A〉, where T has no disjointness axioms 2 and µ(O) = A, deciding whether some σbop-repair exists is polynomial.

This can be shown by an extension of the method for deletion repairs; like for the latter, the problem is NP-hard in presence of ̸⊑ DL-queries. Assuming that 〈T ,A〉 is consistent (otherwise no σbop-repair exists), we proceed as follows:

1. Like for deletion repairs, we compute the support sets Supp ij and simplify P resp. quit if no repair can exist, checking also whether Supp ij ∩ A ̸= ∅ (as then Qij is entailed).
2. We then let Sj = Supp 1j \ (A ∪ ⋃j ′ Supp 2j ′ ). Similar as above, the σbop repairs are then of the formA′ = A∪H where H is a hitting set of the Sj, but we must ensure that 〈T , A′ 〉 is consistent as H consists of new assertions.
3. We choose a set H- ⊆ ⋃j Sj of at most k negative assertions, which is a partial hitting set, and check that 〈T , A∪ H-〉 is consistent. If yes, we remove Sj if it intersects with H- and remove otherwise from Sj each positive assertion α s.t. ¬α is entailed by 〈T , A∪H-〉, and all negative assertions.
4. Then, for every hitting set H+ of the remaining updated Sj, the ABox A′ = A ∪ H- ∪ H+ is a σbop-repair. On the other hand, some σbop-repair with few negative additions exists only if some choice for H- succeeds.

The crucial point for the correctness of this method is that, if T has no disjointness axioms, by adding to A∪H- positive assertions H+ we can not infer new negative assertions, unless inconsistency emerges; this is exploited in Step 3, which limits the candidate space for positive hitting sets a priori. The case of few positive additions is completely symmetric.

2 Disregarding axioms F¬ ⊑ ¬F to compile negative assertions.

5. Applicability of results. Like for relational databases, our tractable cases fit real applications, e.g. in case of deletion repairs (observing that non-subsumption queries are insignificant for practical DL-programs) and scenarios akin to key-constraint violations in databases.

Composability of independent selections adds to their applicability. Moreover, they may be combined with DB-style factorization and localization techniques (see [Bertossi, 2011] and references therein) and with local search (see Conclusions) to compute closest repairs.

Bounding the number of changes, especially additions, is also compliant with practice, where too many potential repairs suggest human intervention (cf. database repair).

Finally, one may increase the bound in iterative deepening (assuming that not many changes are needed).

6 RelatedWork and Conclusions

Managing inconsistent DL-programs has focused so far on inconsistency tolerance, rather than on repair as we considered. P¨uhrer et al. [2010] avoid unintuitive answer sets caused by inconsistency in DL-atoms, and dynamically deactivate rules to discard spoiled information; they pointed ontology repair out as an issue, but left it open. Fink [2012] presented a paraconsistent semantics, based on the logic of here-and-there.

Repairing ontologies was considered in many works, often to deal with inconsistency. In particular, [Lembo et al., 2010; Bienvenu, 2012] studied consistent query answering over DLLite ontologies based on the repair technique (see [Bertossi, 2011]), using minimal deletion repairs (which amount to nonindependent σ-selections). Calvanese et al. [2012] studied query answers to DL-LiteA ontologies that miss expected tuples, and defined abductive explanations corresponding to repairs. They analyzed the complexity of explanation existence for various preferences that amount to non-independent σ-selections. While their problem can be viewed as a special ORP for atomic queries, we deal-also in comparison to the aforementioned works-with a more general problem, where mixed entailment and non-entailment of queries must be satisfied, and moreover under ABox updates. Repairing inconsistent nonmonotonic logic programs is less developed; [Sakama and Inoue, 2003] used extended abduction to delete minimal sets of rules (but also adding rules can remove inconsistency).

Future Work. There are several issues for ongoing and future work. One is extending this work to other classes of Description Logics, like the tractable DLs EL++ and RL, but also to more expressive DLs like Horn-SHIQ, SHIQ, or SROIQ. Related to this is also to consider DL-programs with richer queries, e.g., with (unions of) conjunctive queries (cf. [Eiter et al., 2008a]), or more generally to consider logic programs that access multiple and perhaps also heterogenous ontologies. Orthogonal to this are further σ-selections for repairs, both independent and non-independent ones. The latter may cause intractability in very simple settings, as they open an exponential search space (e.g., subset-minimal or Dalal distance). However, neighborhood search on top of σ allows to compute locally optimal σ-repairs without loss of tractability (by using a slight adaption of our algorithm). Finally, optimization and implementation remain to be done.