Tractability of the Crisp Representations of Tractable Fuzzy Description Logics

Abstract

An important line of research within the eld of fuzzy DLs is the computation of an equivalent crisp representation of a fuzzy ontology. In this short paper, we discuss the relation between tractable fuzzy DLs and tractable crisp representations. This relation heavily depends on the family of fuzzy operators considered. Introduction. Despite the undisputed success of ontologies, classical ontology languages are not appropriate to deal with vagueness or imprecision in the knowledge, which is inherent to most of the real world application domains. As a solution, several fuzzy extensions of Description Logics (DLs) have been proposed in the literature. For a good survey we refer the reader to [1]. An important line of research within the eld of fuzzy DLs is the computation of an equivalent crisp representation of a fuzzy ontology. This way, it is possible to reason with the obtained crisp ontology, making it possible to reuse classical ontology languages (e.g., OWL 2), DL reasoners, and other resources. It is possible to reason with very expressive fuzzy DLs, and with di erent families of fuzzy operators (also called fuzzy logics ), namely Zadeh [2], Godel [3], and Lukasiewicz [4]. To be precise, in Godel and Lukasiewicz it is necessary to restrict to the nite case, i.e., where the set of degrees of truth is nite and xed. In the last years, there is a growing interest in the study of tractable DLs. In these logics, the expressive power is compromised for the e ciency of reasoning. In OWL 2, the current standard language for ontology representation, three fragments (called pro les) have been identi ed, namely OWL 2 EL, OWL 2 QL, and OWL 2 RL [5]. Table 1 shows the relation of some OWL 2 constructors and its fragments. In OWL 2 EL and OWL 2 RL, the basic reasoning tasks can be performed in a time which is polynomial with respect to the size of the ontology. In OWL 2 QL, conjunctive query answering can be performed in LogSpace with respect to the size of the assertions. Sometimes, the crisp representation of a fuzzy KB enjoys the following property: given a fuzzy ontology O in a fuzzy DL language X , the crisp representation of O is in the (crisp) DL X . The objective of this paper is to determine in a precise way when this property is veri ed, focusing on the case of tractable fuzzy DLs, which is a very interesting case in real-world applications. De nition 1. A fuzzy DL language X is closed under reduction i the crisp representation of a fuzzy ontology in X is in the (crisp) DL language X .

-

In the following, we will assume that X is not more expressive than SROIQ(D). Fuzzy DLs. We assume the reader to be familiar with fuzzy DLs [ 1 ]. We note that the many existing proposals usually di er in syntax, semantics, and logical properties. In this paper, we consider fuzzy DLs with the following features: { Concepts and roles are syntactically the same as in the crisp case. { Axioms are syntactically the same as in the crisp case, with the exception of concept assertions, role assertions, general concept inclusions (GCIs), and role hierarchies, where a crisp axiom is extended with a lower bound as h B i, with B 2 f ; >g, and 2 [0; 1]. For instance, ha : C u D 0:6i means that the concept assertion a : C u D is true with degree at least 0:6. { The semantics of classes, properties and axioms depends on some fuzzy logical operators, namely a t-norm, a t-conorm, a negation, and an implication. For instance, the semantics of the conjunction is given by a t-norm. Fuzzy DLs with di erent fuzzy operators have many di erent logical properties. Crisp representations of fuzzy DLs. The basic idea of the crisp representation is to use some basic crisp concepts and roles, representing the -cuts of the fuzzy concepts and roles. To keep the semantics of the -cuts, some axioms must be introduced, namely GCIs and role hierarchies. Finally, every axiom of the fuzzy ontology is represented, independently from other axioms, using these basic crisp elements. An important property of these crisp representations is that, although the number of axioms in the TBox and the RBox increase, the number of axioms in the ABox is constant. Let us illustrate this with an example. Example 1. Assume that a fuzzy ontology K includes the set of axioms fha : 9R:C 0:6i; ha : :9R:C > 0:8ig. The crisp representation of the ontology must consider the crisp concepts C 0:6; C 0:8, and the crisp roles R 0:6; R 0:8, which produce the GCI C 0:8 v C 0:6 and the role hierarchy R 0:8 v R 0:6. Assuming that the t-norm is the minimum and the negation is the standard (Lukasiewicz), the crisp representation of the axioms is fa : 9R 0:6:C 0:6; a : 8R 0:8:(:C 0:8)g. The case of Zadeh fuzzy logic. The full details of the crisp representation in Zadeh SROIQ(D) can be found in [ 2 ]. Zadeh logic makes it possible to obtain smaller crisp representations than with Godel and Lukasiewicz logics. For instance, in Zadeh logic, from ha : C uD 0:6i we can deduce both ha : C 0:6i and ha : D 0:6i. However, in Lukasiewicz logic, this is not possible, and we have to build a disjunction over all the possibilities. In Godel implication, we have a similar problem. In the case of Zadeh logic, we have the following property: Property 1. In Zadeh fuzzy logic, a fuzzy DL language X is closed under reduction i it includes GCIs and role hierarchies. tu

The proof of this property is trivial from the crisp representation [ 2 ]. This result applies, for instance, to logics more expressive than ALCH, such as SROIQ(D). Furthermore, it also applies to the DLs that are equivalent to the pro les OWL 2 EL, OWL 2 QL, and OWL 2 RL (see Table 1).

Example 2. Consider again the fuzzy ontology K from Example 1, and assume that the language of K is ALC. Since ALC does not contain role hierarchies, the second condition of Property 1 fails, and hence fuzzy ALC is not closed under reduction. This is intuitive, because the crisp representation contains role hierarchies (R 0:8 v R 0:6). tu The case of Godel fuzzy logic. The full details of the crisp representation in Godel SROIQ(D) can be found in [ 3 ]. This case is very similar to the previous one. In fact, using a similar reasoning, it can be seen that the following property is veri ed by the three OWL 2 pro les.

Property 2. In Godel fuzzy logic, a fuzzy DL language X is closed under reduction i it veri es each of the following conditions: { X includes GCIs. { X includes role hierarchies. { If X includes universal (all) restrictions, then it also include conjunction. tu The case of Lukasiewicz fuzzy logic. The full details of the crisp representation in Lukasiewicz ALCHOI can be found in [ 4 ].

Property 3. In Lukasiewicz fuzzy logic, a fuzzy DL language X is not closed under reduction if it veri es some of the following conditions: { X does not include GCIs. { X does not include role hierarchies. { X includes one and only one of the constructors disjunction and conjunction. { X includes existential (some) restrictions, but it does not include disjunction. { X includes universal (all) restrictions, but it does not include conjunction.

Again, the proof of this property is trivial from the crisp representation [ 4 ]. The three OWL 2 pro les verify this property. OWL 2 EL and OWL 2 QL support conjunction but not disjunction (see Table 1); and OWL 2 RL allows intersection as a superclass expression, but does not allow disjunction there [ 5 ].

Note that this property is formulated in a di erent way. The reason is that a crisp representation for a fuzzy DL more expressive than ALCHOI is still unknown. Hence, rather than a general result, we only have a partial one. Size of the crisp representations. In Zadeh and Godel OWL 2 QL we obtain a crisp ontology where the ABox has the same number of axioms as the original fuzzy ABox. Hence, tractability is preserved, since the complexity of reasoning depends on the number of assertions.

In Zadeh and Godel OWL 2 EL and OWL 2 RL, we obtain a crisp ontology in a tractable language. However, the TBox and the RBox are larger than in the original fuzzy ontology. This increase in the size is an issue to consider when dealing with tractable fuzzy DLs from a practical point of view, as reasoning depends on the size of the ontology.

In Godel OWL 2 QL, a fuzzy universal restriction is mapped into a (crisp) conjunction of universal restrictions. Hence, the resulting ontology is bigger than in the Zadeh case. This does not happen in OWL 2 EL nor in OWL 2 QL, as they do not allow universal restrictions (see Table 1).

In tractable fuzzy DLs, it is specially important to use optimized crisp representations. For instance, domain and range restrictions can be treated as GCIs, but their crisp representation are more e cient if treated as special cases [ 2 ]. Acknowledgement. The authors have been partially supported by the Spanish Ministry of Science and Technology (project TIN2009-14538-C02-01).

References

1. Lukasiewicz , T. , Straccia , U. : Managing uncertainty and vagueness in description logics for the semantic web . Journal of Web Semantics 6 ( 4 ) ( 2008 ) 291 { 308

2. Bobillo , F. , Delgado , M. , Gomez-Romero , J. : Crisp representations and reasoning for fuzzy ontologies . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 17(4) ( 2009 ) 501 { 530

3. Bobillo , F. , Delgado , M. , Gomez-Romero , J. , Straccia , U. : Fuzzy description logics under Godel semantics . Int. J. of Approximate Reasoning 50 ( 3 ) ( 2009 ) 494 { 514

4. Bobillo , F. , Straccia , U. : Towards a crisp representation of fuzzy description logics under Lukasiewicz semantics . In Proceedings of ISMIS 2008. Volume 4994 of Lecture Notes in Computer Science , Springer-Verlag ( 2008 ) 309 { 318

5. OWL 2 Web Ontology Language Pro les . http://www.w3.org/TR/owl2-profiles.