On the Complexity of Dealing with Inconsistency in Description Logic Ontologies

1 Introduction

In this paper we study the problem of dealing with inconsistency in Description Logic (DL) ontologies. This problem is becoming of increasing importance in practical applications of ontologies. In fact, the size of ontologies used by real applications is scaling up, and ontologies are increasingly merged and integrated into larger ontologies: the probability of introducing inconsistency in these activities is consequently getting higher, and dealing with inconsistency is becoming a practical issue in ontology-based systems (see e.g. [Hogan et al., 2010]).

A traditional approach (analogous to data cleaning in databases) is to manually (or semi-automatically) repair the inconsistency, by suitably modifying the ontology. This might be not be practical or feasible in many contexts, e.g., when dealing with (very) large ontologies, or integrating different ontologies. An alternative approach is to define inconsistency-tolerant semantics, which, differently from the classical FOL semantics of DLs, are able to derive meaningful conclusions from inconsistent ontologies, and can be the formal basis for an automated treatment of inconsistency.

The inconsistency-tolerant semantics for DL ontologies that we consider are based on repairing (i.e., modifying) the extensional knowledge (i.e., the ABox A) while keeping the intensional knowledge (i.e., the TBox T ) untouched. Specifically, such semantics are based on the notion of ABox repair. Intuitively, given a DL KB K = 〈T ,A〉, a repair AR for K is an ABox such that the KB 〈T ,AR〉 is satisfiable under the classical semantics, and AR "minimally" differs fromA. Notice that in general not a single but several repairs may exist, depending on the particular minimality criteria adopted.

In particular, we consider inconsistency-tolerant semantics recently proposed in [Lembo et al., 2010], called ARsemantics and CAR-semantics, for which reasoning has been studied in the context of the Description Logics of the DL-Lite family. The notion of ABox repair in the AR-semantics is a very simple and natural one: a repair is a maximal subset of the ABox that is consistent with the TBox. The CARsemantics is a variant of the AR-semantics that is based on a notion of "equivalence under consistency" of ABoxes inconsistent with respect to a given TBox.

We study the main forms of extensional reasoning in DL ontologies (instance checking and conjunctive query entailment) under the above inconsistency-tolerant semantics for a wide spectrum of DLs, ranging from tractable ones (EL) to very expressive ones (SHIQ). Our results confirm the results obtained in [Lembo et al., 2010] for DL-Lite and show that reasoning under the above semantics is inherently intractable, even for very simple DLs. So, to the aim of overcoming the high computational complexity of reasoning, we also consider sound approximations of the previous semantics. In particular, we focus on semantics (called IAR-semantics and ICAR-semantics in [Lembo et al., 2010]) that consider as a repair, in each of the previous semantics, the ABox corresponding to the intersection of all the repairs. Surprisingly, our computational analysis shows that, differently from the case of DL-Lite, reasoning under the approximated semantics is in general intractable even for tractable DLs.

Finally, we study tractable cases, i.e., suitable restrictions of such DLs that allow for tractable reasoning under inconsistency-tolerant semantics. In particular, we identify a fragment of the DL EL⊥ for which reasoning under an inconsistency-tolerant semantics (in particular, the IARsemantics) is computationally not harder than reasoning under the standard DL semantics.

2 Preliminaries

The DLs mainly considered in this paper are the following:

• EL [Baader et al., 2005], a prominent tractable DL. Here, we consider EL⊥, a slight extension of EL allowing for the empty concept ⊥ (and hence for inconsistency in KBs);
• ALC, a very well-known DL which corresponds to multimodal logic Kn [Baader et al., 2003];
• SHIQ [Glimm et al., 2008], a very expressive DL which constitutes the basis of the OWL family of DLs adopted as standard languages for ontology specification in the Semantic Web.

In every DL, concept expressions and role expressions can be constructed starting from concept and role names. Such expressions are used to define axioms. Typical axioms are concept inclusions, role inclusions, and instance assertions. A concept inclusion is an expression of the form C1 ⊑ C2, where C1 and C2 are concept expressions. Similarly, a role inclusion is an expression of the form R1 ⊑ R2, where R1 and R2 are role expressions. An instance (ABox) assertion is an expression of the form A(a) or P (a, b), where A is a concept name, P is a role name, and a, b are constant (individual) names. We do not consider complex concept and role expressions in instance assertions. A DL knowledge base (KB) is a pair 〈T , A〉, where T , called the TBox, is a set of concept and role inclusions, and A, called the ABox, is a set of instance assertions.

The syntax of EL⊥, ALC and SHIQ is summarized in Figure 1, in which the symbol A denotes a concept name and the symbol P denotes a role name (in addition to concept and role inclusions, SHIQ also allows for TBox axioms of the form Trans(R), which state transitivity of the role R).

The semantics of DLs can be given through the well-known translation ρfol of DL knowledge bases into FOL theories with counting quantifiers (see [Baader et al., 2003]). An interpretation of K is a classical FOL interpretation for ρfol (K). A model of a DL KB K = 〈T , A〉 is a FOL model of ρfol (K). We say that K is satisfiable if K has a model. We say that K entails a FOL sentence φ (and write K |= φ) if φ is satisfied in every model of K.

In the following, we are interested in particular in UCQ entailment, i.e., the problem of deciding whether a KB entails a (Boolean) union of conjunctive queries (UCQ), i.e., a FOL sentence of the form ∃⃗ y1.conj 1( ⃗ y1) ∨ · · · ∨ ∃ ⃗ yn.conj n( ⃗ yn) where ⃗ y1, . . . , ⃗ yn are terms (i.e., constants or variables), and each conj i( ⃗ yi) is a conjunction of atoms of the form A(z)

and P (z, z′ ), where A ia a concept name, P is a role name and z, z′ are terms. Instance checking (IC) is a restricted form of UCQ entailment, corresponding to the case when the UCQ is an ABox assertion (i.e., a ground atom). Notice that all the results we achieve about Boolean UCQ entailment can be easily extended in the standard way to the presence of free variables in queries (see e.g. [Glimm et al., 2008]).

In this paper, we will consider data complexity (i.e., the complexity with respect to the size of the ABox) and combined complexity (i.e., the complexity with respect to the size of the whole input) of UCQ entailment and instance checking. Besides the usual complexity classes NP, coNP, Πp2 , EXPTIME, 2-EXPTIME, we will mention the following classes:

• Δp2 [O(logn)] (resp., Δp3 [O(logn)]) is the class of problems that can be solved in polynomial time using O(logn) calls to an NP-oracle (resp., a Σp2 -oracle) (see e.g. [Gottlob, 1995]);
• DP is the class of problems corresponding to the conjunction of a problem in Σp2 and a problem in Πp2 . An example of a problem complete for this class is 3-CNFSAT+UNSAT: given two 3-CNF formulas φ1, φ2, decide whether φ1 is satisfiable and φ2 is unsatisfiable. Notice that DP = BH2(NP), i.e., DP is the second level of the Boolean hierarchy over NP;
• BH2(Σp2 ) is the class of problems corresponding to the conjunction of a problem in Σp2 and a problem in Πp2 . An example of a problem complete for this class is 2QBF-SAT+UNSAT: given two 2-QBF formulas φ1, φ2, decide whether φ1 is not valid and φ2 is valid.

Finally, the following table recalls known results on the complexity of instance checking and UCQ entailment under standard semantics in the DLs considered in this paper (all problems are complete w.r.t. the class reported).

3 Inconsistency-tolerant semantics

In this section we recall the inconsistency-tolerant semantics for DL ontologies defined in [Lembo et al., 2010]. 1 We assume that, for a knowledge base K = 〈T , A〉, T is satisfiable, whereas Amay be inconsistent with T , i.e., the set of models of K may be empty.

AR-semantics The first notion of repair that we consider, called AR-repair, is a very natural one: a repair is a maximal subset of the ABox that is consistent with the TBox. Thus, an AR-repair is obtained by throwing away from A a minimal set of assertions to make it consistent with T .

Definition 1 Let K = 〈T , A〉 be a DL KB. An AR-repair of K is a set A′ of membership assertions such that: (i)A′ ⊆ A;

1 Due to space limitations, we refer the reader to [Lembo et al., 2010] for introductory examples illustrating these semantics.

(ii) 〈T ,A′ 〉 is satisfiable; (iii) there does not exist A′′ such that A′ ⊂ A′′ ⊆ A and 〈T ,A′′ 〉 is satisfiable. The set of AR-repairs for K is denoted by AR-Rep(K). Moreover, we say that a first-order sentence φ is AR-entailed by K, written K |=AR φ, if 〈T ,A′ 〉 |= φ for every A′ ∈ AR-Rep(K).

CAR-semantics We start by formally introducing a notion of "equivalence under consistency" for inconsistent KBs.

Given a KB K, let SK denote the signature of K, i.e., the set of concept, role, and individual names occurring in K. Given a signature S, we denote with HB(S) the Herbrand Base of S, i.e. the set of ABox assertions (ground atoms) that can be built over the signature S. Then, given a KB K = 〈T ,A〉, we define the consistent logical consequences of K as the set clc(K) = {α | α ∈ HB(SK) and there exists A′ ⊆ A such that 〈T ,A′ 〉 is satisfiable and 〈T ,A′ 〉 |= α}.

Finally, we say that two KBs 〈T ,A〉 and 〈T ,A′ 〉 are consistently equivalent (C-equivalent) if clc(〈T ,A〉) = clc(〈T , A′ 〉).

We argue that the notion of C-equivalence is very reasonable in settings in which the ABox (or at least a part of it) has been "closed" with respect to the TBox, e.g., when (some or all) the ABox assertions that are entailed by the ABox and the TBox have been added to the original ABox. This may happen, for example, when the ABox is obtained by integrating different (and locally consistent) sources, since some of these sources might have been locally closed with respect to some TBox axioms.

In settings where C-equivalence makes sense, the ARsemantics is not suited to handle inconsistency. In fact, we would expect two C-equivalent ontologies to produce the same logical consequences under inconsistency-tolerant semantics. Unfortunately, the AR-semantics does not have this property. A simple example is the following: let T = {student ⊑ young, student ⊓ worker ⊑ ⊥} and let A = {student(mary), worker(mary)}, A′ = {student(mary), worker(mary), young(mary)}. It is immediate to verify that clc(K) = clc(K′ ) = A′ , thus K and K′ are C-equivalent, however K′ |=AR young(mary) while K ̸|=AR young(mary).

To overcome the above problem, the CAR-semantics has been defined in [Lembo et al., 2010], through a modification of the AR-semantics. 2

Definition 2 Let K = 〈T ,A〉 be a DL KB. A CAR-repair for K is a set A′ of membership assertions such that A′ is an AR-repair of 〈T , clc(K)〉. The set of CAR-repairs for K is denoted by CAR-Rep(T ,A). Moreover, we say that a firstorder sentence φ is CAR-entailed by K, written K |=CAR φ, if 〈T , A′ 〉 |= φ for every A′ ∈ CAR-Rep(K).

Going back to the previous example, it is immediate to see that, since K and K′ are C-equivalent, the set of CAR-repairs (and hence the set of CAR-models) of K and K′ coincide.

As the above example shows, there are sentences entailed by a KB under CAR-semantics that are not entailed under AR-semantics. Conversely, it is shown in [Lembo et al.,

2 The definition provided here of the CAR-semantics is a slight simplification of the one appearing in [Lembo et al., 2010]: this modification, however, does not affect any of the computational results presented in [Lembo et al., 2010].

2010] that the AR-semantics is a sound approximation of the CAR-semantics, i.e., for every KB K and every FOL sentence φ, K |=AR φ implies K |=CAR φ.

IAR-semantics and ICAR-semantics We then recall the sound approximations of the AR-semantics and the CARsemantics, called IAR-semantics and ICAR-semantics, respectively [Lembo et al., 2010].

Definition 3 Let K = 〈T ,A〉 be a DL KB. The IARrepair (respectively, ICAR-repair) for K, denoted by IAR-Rep(K) (respectively, ICAR-Rep(K)) is defined as IAR-Rep(K) = ⋂A′∈AR-Rep(K) A′ (respectively, ICAR-Rep(K) = ⋂A′∈CAR-Rep(K) A′ ). Moreover, we say that a first-order sentence φ is IAR-entailed (resp., ICARentailed) by K, and we write K |=IAR φ (resp., K |=ICAR φ), if 〈T , IAR-Rep(K)〉 |= φ (resp., 〈T , ICAR-Rep(K)〉 |= φ).

It is immediate to see [Lembo et al., 2010] that the IARsemantics is a sound approximation of the AR-semantics, and that the ICAR-semantics is a sound approximation of the CAR-semantics, while the converse in general does not hold.

4 Lower bounds

We start by considering data complexity. First, we provide lower bounds for instance checking in EL⊥. 3

Theorem 1 Let K be an EL⊥ KB and let α be an ABox assertion. Then: (i) deciding whether K |=AR α is coNPhard w.r.t. data complexity; (ii) deciding whether K |=IAR α is coNP-hard w.r.t. data complexity; (iii) deciding whether K |=CAR α is DP-hard w.r.t. data complexity.

Then, we consider UCQ entailment, still in EL⊥.

Theorem 2 Let K be an EL⊥ KB and let Q be a UCQ. Then: (i) deciding whether K |=CAR Q is Δp2 [O(logn)]- hard w.r.t. data complexity; (ii) deciding whether K |=ICAR Q is Δp2 [O(log n)]-hard w.r.t. data complexity.

We then provide a lower bound for instance checking in ALC.

Theorem 3 Let K be an ALC KB and let α be an ABox assertion. Then: (i) deciding whether K |=AR α is Πp2 - hard w.r.t. data complexity; (ii) deciding whether K |=IAR α is Πp2 -hard w.r.t. data complexity; (iii) deciding whether K |=CAR α is BH2(Σp2 )-hard w.r.t. data complexity.

We now turn our attention to UCQ entailment in ALC.

Theorem 4 Let K be an ALC KB and let Q be a UCQ. Then: (i) deciding whether K |=CAR Q is Δp3 [O(logn)]- hard w.r.t. data complexity; (ii) deciding whether K |=ICAR Q is Δp3 [O(log n)]-hard w.r.t. data complexity.

Finally, we consider combined complexity and provide lower bounds for UCQ entailment in EL⊥.

Theorem 5 Let K be an EL⊥ KB and let Q be a UCQ. Then: (i) deciding whether K |=IAR Q is Δp2 [O(log n)]-hard w.r.t. combined complexity; (ii) deciding whether K |=AR Q is Πp2 -hard w.r.t. combined complexity; (iii) deciding whether K |=CAR Q is Πp2 -hard w.r.t. combined complexity.

3 Due to lack of space, in the present version of the paper we omit the proofs of lower bounds.

5 Upper bounds

We start by providing upper bounds for the combined complexity of instance checking in EL⊥.

Theorem 6 Let K be an EL⊥ KB and let α be an ABox assertion. Then: (i) deciding whether K |=AR α is in coNP w.r.t. combined complexity; (ii) deciding whether K |=IAR α is in coNP w.r.t. combined complexity; (iii) deciding whether K |=CAR α is in DP w.r.t. combined complexity.

Proof. For case (i), we define the following AlgorithmAR1: ALGORITHMAR1 (decides 〈T ,A〉 |=AR Qwith QUCQ)

if there exists A′ ⊆ A such that 1) 〈T ,A′ 〉 satisfiable and 2) A′ is maximal T -consistent subset of A and 3) 〈T ,A′ 〉 ̸|= Q

then return false else return true

It is easy to verify that the above algorithm is correct for every DL, i.e., it returns true iff 〈T ,A〉 |=AR Q, and that, in the case of EL⊥ and when Q is an ABox assertion, the algorithm runs in coNP.

For case (ii), we define the following Algorithm IAR1:

ALGORITHM IAR1 (decides 〈T ,A〉 |=IAR Qwith QUCQ) if there exist A′ ⊆ A (let A-A′ = {α1, . . . , αn}), A1 ⊆ A, . . . , An ⊆ A such that 1) 〈T , A′ 〉 ̸|= Q and 2) for each i such that 1 ≤ i ≤ n, αi ∈ Ai and Ai is a minimal T -inconsistent subset of A then return false else return true

It is easy to verify that the above algorithm is correct for every DL, i.e., it returns true iff 〈T ,A〉 |=IAR Q, and that, in the case of EL⊥ and when Q is an ABox assertion, the algorithm runs in coNP.

For case (iii), we define the following algorithm ICAR1:

ALGORITHM ICAR1 (decides 〈T ,A〉 |=ICAR α) if (a) for each A′ ⊆ A, either 〈T ,A′ 〉 unsatisfiable or 〈T ,A′ 〉 ̸|= α or (b) there exist A′′ = {α1, . . . , αn} ⊆ HB(T , A), A1 ⊆ A, . . . , An ⊆ A such that 1) α ∈ A′′ and 2) 〈T , A′′ 〉 unsatisfiable and 3) for every i s.t. 1 ≤ i ≤ n 3.1) 〈T ,A′′ - {αi}〉 satisfiable and 3.2) 〈T ,Ai〉 satisfiable and 3.3) 〈T ,Ai〉 |= αi

then return false else return true

It is easy to verify that the above algorithm is correct for every DL, i.e., it returns true iff 〈T ,A〉 |=ICAR α, and that, in the case of EL⊥, the algorithm runs in DP.

We now turn our attention to both data and combined complexity of UCQ entailment in EL⊥.

Theorem 7 Let K be an EL⊥ KB and let Q be a UCQ. Then: (i) deciding whether K |=AR Q is in coNP w.r.t. data complexity; (ii) deciding whether K |=IAR Q is in coNP w.r.t. data complexity; (iii) deciding whether K |=CAR Q is in Δp2 [O(log n)] w.r.t. data complexity.

Proof. Case (i) follows from the correctness of Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from the correctness of Algorithm IAR1 defined in the proof of Theorem 6. Finally, case (iii) follows from the correctness (for every DL) of the following Algorithm CAR1:

ALGORITHMCAR1 (decides 〈T ,A〉 |=CAR Qwith QUCQ) A′ = ∅; for each α ∈ HB(T , A) do if there exists A′′ ⊆ A such that 〈T ,A′′ 〉 satisfiable and 〈T ,A′′ 〉 |= α then A′ = A′ ∪ {α}; if 〈T , A′ 〉 |=AR Q then return true else return false

When the input KB is in EL⊥, the above algorithm can be reduced to an NP tree [Gottlob, 1995], which proves the Δp2 [O(log n)] upper bound.

Theorem 8 Let K be an EL⊥ KB and let Q be a UCQ. Then: (i) deciding whether K |=AR Q is in Πp2 w.r.t. combined complexity; (ii) deciding whether K |=CAR Q is in Πp2 w.r.t. combined complexity; (iii) deciding whether K |=IAR Q is in Δp2 [O(logn)] w.r.t. combined complexity; (iv) deciding whether K |=ICAR Q is in Δp2 [O(logn)] w.r.t. combined complexity.

Proof. Case (i) follows from the correctness of Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from the correctness (for every DL) of the following Algorithm CAR2:

ALGORITHMCAR2 (decides 〈T ,A〉 |=CAR Qwith QUCQ) if there exists A′ ⊂ HB(T , A) such that 1) for each α ∈ A′ α ∈ clc(T , A) and 2) for each α ∈ HB(T , A) - A′ α ̸∈ clc(T , A) or 〈T , A′ ∪ {α}〉 unsatisfiable and 3) 〈T ,A′ 〉 ̸|= Q

then return false else return true

and from the fact that deciding α ∈ clc(T , A) (with α ABox assertion) can be decided in NP. Case (iii) follows from the correcness (for every DL) of the following Algorithm IAR2:

ALGORITHM IAR2 (decides 〈T ,A〉 |=IAR Qwith QUCQ)

for each α ∈ A do

if α does not belong to any minimal T -inconsistent subset of A then A′ = A′ ∪ {α};

if 〈T , A′ 〉 |= Q then return true else return false

Finally, Case (iv) follows from the correctness (for every DL) of the following Algorithm ICAR2:

ALGORITHM ICAR2 (decides 〈T ,A〉 |=ICAR Qwith QUCQ) A′ = ∅;

for each α ∈ HB(T , A) do if there exists A′′ ⊆ A such that 〈T ,A′′ 〉 satisfiable and 〈T ,A′′ 〉 |= α then A′ = A′ ∪ {α}; if 〈T , A′ 〉 |=IAR Q then return true else return false

and from the fact that, when the input KB is in EL⊥, the above algorithm can be reduced to an NP tree [Gottlob, 1995], which proves the Δp2 [O(log n)] upper bound.

We then consider the combined complexity of UCQ entailment in ALC.

Theorem 9 Let K be an ALC KB and let Q be a UCQ. Then: (i) deciding whether K |=AR Q is in EXPTIME w.r.t. combined complexity; (ii) deciding whether K |=CAR Q is in EXPTIME w.r.t. combined complexity; (iii) deciding whether K |=IAR Q is in EXPTIME w.r.t. combined complexity; (iv) deciding whether K |=ICAR Q is in EXPTIME w.r.t. combined complexity.

Proof. Case (i) follows from the correctness of Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from the correctness of Algorithm CAR1 defined in the proof of Theorem 7. Case (iii) follows from the correctness of Algorithm IAR2 defined in the proof of Theorem 8. Finally, case (iv) follows from the correctness of Algorithm ICAR2 defined in the proof of Theorem 8.

Then, we provide upper bounds for the data complexity of both instance checking and UCQ entailment in SHIQ.

Theorem 10 Let K be an SHIQ KB and let α be an ABox assertion. Then, deciding whether K |=CAR α is in BH2(Σp2 ) w.r.t. data complexity.

Proof. The proof follows from the correctness of Algorithm ICAR1 defined in the proof of Theorem 6.

Theorem 11 Let K be a SHIQ KB and let Q be a UCQ. Then: (i) deciding whether K |=AR Q is in Πp2 w.r.t. data complexity; (ii) deciding whether K |=IAR Q is in Πp2 w.r.t. data complexity; (iii) deciding whether K |=CAR Q is in Δp3 [O(logn)] w.r.t. data complexity; (iv) deciding whether K |=ICAR Q is in Δp3 [O(log n)] w.r.t. data complexity.

Proof. Case (i) follows from the correctness of Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from the correctness of Algorithm IAR2 defined in the proof of Theorem 8. Case (iii) follows from the correctness of Algorithm CAR1 defined in the proof of Theorem 7. It can be proved that, when the input KB is in SHIQ, Algorithm CAR1 can be reduced to a Σp2 tree, which proves the Δp3 [O(logn)] upper bound. Analogously, case (iv) follows from the correctness of Algorithm ICAR2 defined in Theorem 8: when the input KB is in SHIQ, Algorithm ICAR2 can be reduced to a Σp2 tree, which proves the Δp3 [O(logn)] upper bound.

Finally, we provide upper bounds for the combined complexity of instance checking and UCQ entailment in SHIQ.

Theorem 12 Let K be a SHIQ KB and let α be an ABox assertion. Then: (i) deciding whether K |=AR α is in EXPTIME w.r.t. combined complexity; (ii) deciding whether K |=CAR α is in EXPTIME w.r.t. combined complexity; (iii) deciding whether K |=IAR α is in EXPTIME w.r.t. combined complexity; (iv) deciding whether K |=ICAR α is in EXPTIME w.r.t. combined complexity.

Proof. Case (i) follows from the correctness of Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from the correctness of Algorithm CAR1 defined in the proof of Theorem 7. Case (iii) follows from the correctness of Algorithm IAR2 defined in the proof of Theorem 8. Finally, case (iv) follows from the correctness of Algorithm ICAR2 defined in the proof of Theorem 8.

Theorem 13 Let K be a SHIQ KB and let Q be a UCQ. Then: (i) deciding whether K |=AR Q is in 2-EXPTIME w.r.t. combined complexity; (ii) deciding whether K |=CAR Q is in 2-EXPTIME w.r.t. combined complexity; (iii) deciding whether K |=IAR Q is in 2-EXPTIME w.r.t. combined complexity; (iv) deciding whether K |=ICAR Q is in 2-EXPTIME w.r.t. combined complexity.

Proof. Case (i) follows from Algorithm AR1 defined in the proof of Theorem 6. Case (ii) follows from Algorithm CAR1 defined in the proof of Theorem 7. Case (iii) follows from Algorithm IAR2 defined in the proof of Theorem 8. Finally, case (iv) follows from Algorithm ICAR2 defined in the proof of Theorem 8.

The theorems presented in the last two sections provide a complete picture of the complexity of reasoning in the DLs considered in this paper under the four inconsistency-tolerant semantics. A summary of the complexity results obtained is reported in Figure 2. All the results displayed are completeness results: all the lower bounds are implied by theorems 15 and by the lower bounds for reasoning under standard DL semantics reported in the preliminaries, while all the upper bounds are implied by theorems 6-13.

6 Tractable cases

We now consider a language restriction of EL⊥ whose aim is to allow for tractable reasoning under inconsistency-tolerant semantics, in particular, under the IAR-semantics. The condition is on the form of empty concept assertions, i.e., concept inclusions whose right-hand side is the empty concept ⊥. Formally, an empty concept assertion in EL⊥ is an inclusion of the form C1 ⊓ . . . ⊓ Cn ⊑ ⊥.

Given an EL⊥ TBox T , we say that a concept name N is relevant for empty concepts in T if there exists an empty concept assertion δ such that N occurs in δ and T |= δ and T ̸|= δ[⊤/N ], where δ[⊤/N ] is the empty concept assertion obtained from δ by replacing every occurrence of N with ⊤. Intuitively, concept names relevant for empty concepts in a TBox T are those involved in the empty concept assertions entailed by T . The above definition filters out "redundant" (i.e., non-minimal) empty concept assertions.

Then, we introduce the notion of (non)-recursive concept name in T . A concept name N is recursive in T if T entails an inclusion of the form C ⊑ N, where C contains at least an occurrence of N nested into an existentially quantified concept expression, and there exists no concept C′ such that T entails C ′ ⊑ N and C ′ is more specific than C in T (i.e., T entails C ′ ⊑ C but not vice versa). Otherwise, we say that N is non-recursive in T . We call EL⊥nr (EL⊥ with nonrecursive empty concepts) KB every EL⊥ KB K = 〈T ,A〉 such that every concept name that is relevant for empty concepts in T is non-recursive in T . It is easy to see that deciding whether an EL⊥ KB is an EL⊥nr KB can be done in time polynomial w.r.t. the size of the TBox.

The language restriction imposed in EL⊥nr KBs allows us to prove the following property, which is crucial for lowering the complexity of reasoning under the IAR-semantics.

Lemma 1 Let 〈T ,A〉 be an EL⊥nr KB. The maximum cardinality of a minimal T -inconsistent subset of A is bounded by the number of concept expressions occurring in T .

We are now ready to state the complexity of reasoning in EL⊥nr under IAR-semantics.

Theorem 14 Let K be an EL⊥nr KB, let α be an ABox assertion, and let Q be a UCQ. Then: (i) deciding whether K |=IAR α is PTIME-complete w.r.t. data complexity; (ii)

deciding whether K |=IAR α is PTIME-complete w.r.t. combined complexity; (iii) deciding whether K |=IAR Q is PTIME-complete w.r.t. data complexity; (iv) deciding whether K |=IAR Q is NP-complete w.r.t. combined complexity.

Proof. For all the four cases, the upper bounds are an immediate consequence of Lemma 1 and of the correctness of Algorithm IAR2 in the proof of Theorem 8 (observe that Lemma 1 implies that there are only polynomially many potential minimal T -inconsistent subsets w.r.t. the size of the ABox), while the lower bounds are immediately implied by the complexity of reasoning under standard DL semantics in EL (notice that EL is a sublogic of EL⊥nr ).

The above theorem shows the nice computational behaviour of reasoning under IAR semantics in EL⊥nr , which is not harder than reasoning under standard DL semantics. This case seems very important not only from the theoretical viewpoint, but also for practical applications, since it identifies a DL allowing for tractable automated treatment of inconsistency. Conversely, it can be shown that reasoning under the ICAR semantics is still intractable in EL⊥nr . Informally, the reason is that the restriction imposed by EL⊥nr only affects the cardinality of minimal T -inconsistent subsets of A, while it leaves unbounded the cardinality of the minimal subsets of A entailing an ABox assertion. Therefore, it is still NP-hard to decide whether an ABox assertion belongs to clc(T , A).

7 Related work and conclusions

Inconsistency-tolerance has been studied in various forms in several areas of Artificial Intelligence and databases. While several recent papers have dealt with different forms of inconsistency in DL ontologies (focusing especially on the TBox, see e.g. [Qi and Du, 2009]), the approach considered in this paper (based on instance-level repair only) is novel for DLs, and is actually inspired by the work on consistent query answering (CQA) in databases (see [Chomicki, 2007] for a survey). Moreover, the form of inconsistency-tolerance considered in this paper corresponds to a form of belief revision [Eiter and Gottlob, 1992]: more precisely, with respect to the knowledge base revision framework, the ABox corresponds to the initial knowledge, while the TBox represents the new information. Based on such a correspondence, the semantic studies on belief revision are indeed very relevant for the present setting (e.g., the IAR-semantics and ICARsemantics are deeply connected to the well-known WIDTIO semantics of belief revision [Eiter and Gottlob, 1992]): however, the kind of theories and formulas considered in the DL

setting have a very special form, which has never been considered in the research in belief revision and update. Therefore, (to the best of our knowledge) there are no available results about reasoning in the present setting.

The present work can be continued along several lines. For instance, it would be very interesting to see whether the present approach can be extended to handle more general forms of ABoxes (e.g., ABoxes with variables and/or non-atomic concept expressions). Also, it would be very important for practical purposes to identify further DL sublanguages allowing for tractable reasoning under the IAR and the ICAR semantics.

Acknowledgments This research has been partially supported by the EU funded Project ACSI (Artifact-Centric Service Interoperation).