# «Paraconsistent Reasoning for Expressive and Tractable Description Logics Yue Ma1, Pascal Hitzler2, and Zuoquan Lin1 Department of Information ...»

– If C =≥ nR.D for D a concept and R a role, then π(C) =≥ nR.π(D);

– If C =≤ nR.D for D a concept and R a role, then π(C) =≤ nR.¬π(¬D);

– If C = ¬(≥ nR.D) for D a concept and R a role, then π(C) = nR.¬π(¬D);

– If C = ¬(≤ nR.D) for D a concept and R a role, then π(C) = nR.π(D);

Regarding both the extension of number restrictions and of nominals, the following theorem holds, which lays the theoretical foundation for the algorithm of four-valued semantics for expressive DLs.

Theorem 5 (Theorem 1 extended) For any ontology O in SHIQ, O is 4-valued unsatisﬁable if and only if π(O) is unsatisﬁable under the classical semantics of SHIQ.

4 Tractable DLs In this section, we will see that inconsistencies are also unavoidable in many tractable DLs. So we focus on discussing whether the four-valued semantics can preserve the tractability of these tractable DLs. That is, whether the reduction for computing the four-valued semantics transfers tractable DLs still into tractable DLs. If it does, then we can use the four-valued semantics to deal with inconsistency without having to worry about intractability. Our discussion is based on EL++, Horn-DLs, and DL-Lite.

**4.1 EL++**

We do not consider concrete domains. The syntax deﬁnition of EL++ knowledge bases is shown in Table 4. EL++ ontologies may also contain role inclusions (RI) of the form r1 ◦ · · · ◦ rk r, where ◦ denotes role composition.

It is easy to see that an EL++ knowledge base may be inconsistent if we consider the knowledge base {A ⊥, A(a)}. So we still hope that the 4-valued semantics can help us to handle inconsistency in EL++ knowledge bases. However, we will see that we don’t have as many choices of class inclusion as in ALC and SHIQ if we want to maintain the tractability of the 4-valued entailment relationship of EL++. The analysis is as follows.

Obviously, the concept transformation of Deﬁnition 1 performing on an EL++ concept produces an EL++ concept. For the transformation of internal inclusion, each EL++ axiom C D is transformed into π(C) π(D) where π(C) and π(D) are still EL++ concepts, so that π(C) π(D) is still an EL++ axiom. So internal class inclusion does not destroy the tractability of EL++. This property does not hold

**for material and strong class inclusions as shown by the following counterexamples:**

A A → B and A A → B. They will be transformed into ¬(A− A − ) B+ + + + − − − and {A A B,B (A A )} by Deﬁnition 2, which are not within the expressivity of EL++. This is mainly because of no negative constructor in EL++.

For role inclusions in EL++, since there is no negative role constructor which can cause inconsistency, we only need to use the classical interpretation for roles as what we do for ALC. So adaptation of 4-valued semantics does not effect the role inclusions axioms.

4.2 Horn-DLs We ground our discussion on Horn-SHOIQ◦ as deﬁned in [7]. Then we will point out that the same conclusion holds for other Horn-DLs, like Horn-SHIQ [10], which has Table 4. EL++ and Horn-SHOIQ◦. The Horn-SHOIQ◦ normal form used is due to [7].

tractable data complexity [6]. We deﬁne Horn-SHOIQ◦ by means of a normal form given in [7], which can be found in Table 4 where A, A, B are concept names.

We can see that all of the Horn-SHOIQ◦ concept constructors preserve its form under π(·) operator except ≤ 1R.B, because π(≤ 1R.B) =≤ 1R.¬B − according to Deﬁnition 4. To still maintain the concept structure of ≤ 1R.B within Horn-SHOIQ◦, we redeﬁne the π(·) operator on ≤ 1R.C as

** π(≤ 1R.C) = {≤ 1R.C = }, where C = C− ⊥.**

Then π(A ≤ 1R.C) = {A ≤ 1R.C =, C = C − ⊥} by the transformation deﬁnition of internal inclusion axiom.

However, not all of the axiom transformations in Deﬁnition 2 preserve the structures of Horn-DL axioms. As the analysis in last paragraph, internal inclusion preserves Horn-ness. As counterexamples for material inclusion and strong inclusion, just consider again the counterexample used in EL++ case. The transformed forms ¬(A− A −) B + and {A+ A + B+, B− (A− A − )} are not within the expressivity of Horn-SHOIQ◦. Since A A B is allowed in other Horn-DLs, the same conclusion as for Horn-SHOIQ◦ holds. This means that when we want ro preserve the structure of tractable Horn-DLs, we have to choose internal inclusion as the only inclusion form to perform paraconsistent reasoning.

4.3 DL-Lite DL-Lite family includes DL-Litecore, DL-LiteF, and DL-LiteR. The logics of DL-Lite family are the maximal DLs supporting efﬁcient query answering over large amounts of instances. In [3], the usual DL reasoning tasks on DL-Lite family are shown to be polynomial in the size of the TBox, and query answering is LOGSPACE in the size of the ABox. Moreover, DL-Lite family allows for separation between TBox and ABox reasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the part of the process requiring to the ABox can be carried out by an SQL engine [3].

**Concepts and roles of DL-Lite family are formed by the following syntax [3]:**

It is also easy to construct an inconsistent knowledge base even for DL-Litecore. For instance, KB = {B ¬A, B(a), A(a)}. Moreover, conﬂictions about roles possibly occur on DL-LiteR, such as {P P, P ¬P, P (a, b)}.

In order to still adopt 4-valued semantics for DL-Lite family, we deﬁne the fourvalued semantics extension for roles. Just as the four-valued semantics for concepts, a pair RP, RN (RP, RN ⊆ (∆I )2 ) denotes the four-valued semantics of a role R under interpretation I, where RP stands for the set of pairs of individuals which are related via R and RN explicitly represents the set of pairs of individuals which are not related via R. Table 6 gives the formal deﬁnition.

necessary to hold under four-valued semantics. This also the key point why our fourvalued semantics can tolerant conﬂicts caused by role assertions, by allowing a, b both positively related and negatively related via R under a four-valued interpretation I. We give the following example to illustrate the four-valued semantics of ∃R.

Example 2 Note that the ontology O = {∃hasStud(Green), ¬∃hasStud(Green)} is inconsistent.

**Consider the following 4-interpretation I = (∆I, ·I ), where ∆I = {a, b, Green}:**

hasStudI = {(Green, a)}, {(Green, a), (Green, b), (Green, Green)} which says that we know that Green has a student a, and that Green doesn’t relate any of the individuals via the relation hasStudent. By checking the following formulae

**we know that I is a 4-model of O:**

Intuitively, this 4-model reﬂects the contradictory status of the ontology about whether Green has a student.

Now we turn to deﬁne the concept transformations for DL-Lite.

Deﬁnition 5 The concept and role transformations for DL-Lite concepts are dened on structure induction as follows.

– For E = R, then π(E) = R;

– For E = ¬R, then π(E) = R, where R is a new role;

– If C = ∃R, then π(C) = ∃R;

If C = ¬∃R, then π(C) = ¬∃R=, where R= is a new role name and R= – ¬R.

Consider the internal inclusion transformation, we have all the GCIs B C of DL-Lite will be transferred into form B C with at most an additional role inclu¬∃R=, R= sion because π(B ¬∃R) = {B ¬R }. For material inclusion and strong inclusion, because the negative concept is not allowed to occur on the left of a GCI, they do not preserve the DL-Lite structure. So only internal inclusion works under the reduction from four-valued semantics to classical semantics of DL-Lite family to keep tractability. We can see that the four-valued semantics of DL-Lites family can be reduced to the reasoning of classical DL-LiteR. The following theorem shows this.

Theorem 6 For any DL-Lite ontology O, O is 4-valued unsatisﬁable if and only if π(O) is unsatisﬁable under the classical semantics of DL-LiteR.

5 Conclusions In this paper, we further studied the four-valued semantics for description logics, specially for expressive DLs and tractable DLs. We formally deﬁned their four-valued semantics and proper reductions to classical semantics, such that all the beneﬁts from existing reasoners on these DLs can also be achieved by invoking classical reasoners after employing these reduction algorithms in a preprocessing manner. And the size of obtained ontology is linear as the size of original ontology. Unlike the four-valued semantics for ALC and SHIQ, we showed that in order to preserve the tractability of tractable DLs, only internal class inclusion among the three class inclusion forms is suitable to model class inclusion. Intuitively, this is because that the semantics of material and strong class inclusions needs the ability to represent negation in some complex form, which is not within the expressivity of tractable DLs. In the future, we will implement these extensions on our existing prototype ParOWL1 to support paraconsistent inconsistency handling on these DLs.

References

1. N. D. Belnap. How a computer should think. Comtemporary Aspects of Philosophy: Proceedings of the Oxford International Symposium, pages 30–56, 1977.

2. N. D. Belnap. A useful four-valued logic. Modern uses of multiple-valued logics, pages 7–73, 1977.

3. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efﬁcient query answering in description logics: The l-lite family. J. Autom. Reasoning, 39(3):385–429, 2007.

4. Peter Haase, Frank van Harmelen, Zhisheng Huang, Heiner Stuckenschmidt, and York Sure.

A framework for handling inconsistency in changing ontologies. In Yolanda Gil, Enrico Motta, V. Richard Benjamins, and Mark A. Musen, editors, International Semantic Web Conference, volume 3729 of Lecture Notes in Computer Science, pages 353–367. Springer, 2005.

5. Zhisheng Huang, Frank van Harmelen, and Annette ten Teije. Reasoning with inconsistent ontologies. In Leslie Pack Kaelbling and Alessandro Safﬁotti, editors, IJCAI, pages 454–

459. Professional Book Center, 2005.

6. Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data Complexity of Reasoning in Very Expressive Description Logics. In Proc. of the 19th Int. Joint Conference on Artiﬁcial Intelligence (IJCAI 2005), pages 466–471, Edinburgh, UK, July 30 – August 5 2005. Morgan Kaufmann Publishers.

7. Markus Kr¨ tzsch, Sebastian Rudolph, and Pascal Hitzler. Complexity boundaries for Horn o description logics. In AAAI, pages 452–457. AAAI Press, 2007.

8. Yue Ma, Pascal Hitzler, and Zuoquan Lin. Algorithms for paraconsistent reasoning with owl. In Enrico Franconi, Michael Kifer, and Wolfgang May, editors, ESWC, volume 4519 of Lecture Notes in Computer Science, pages 399–413. Springer, 2007.

9. Yue Ma, Guilin Qi, Pascal Hitzler, and Zuoquan Lin. Measuring inconsistency for description logics based on paraconsistent semantics. In Khaled Mellouli, editor, ECSQARU, volume 4724 of Lecture Notes in Computer Science, pages 30–41. Springer, 2007.

10. Boris Motik. Reasoning in description logics using resolution and deductive databases. PhD theis, University Karlsruhe, Germany, 2006.

11. Peter F. Patel-Schneider. A four-valued semantics for terminological logics. Artiﬁcial Intelligence, 38:319–351, 1989.

12. Peter F. Patel-Schneider and Horrocks Ian. OWL web ontology language semantics and

**Abstract**

syntax. W3C Recommendation, 10 February, 2004.

13. Peter F. Patel-Schneider and Horrocks Ian. OWL 1.1 web ontology language overview. W3C Member Submssion, 19 December, 2006.

14. Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In Georg Gottlob and Toby Walsh, editors, IJCAI, pages 355–362. Morgan Kaufmann, 2003.

15. Umberto Straccia. A sequent calculus for reasoning in four-valued description logics. In Didier Galmiche, editor, TABLEAUX, volume 1227 of Lecture Notes in Computer Science, pages 343–357. Springer, 1997.