=Paper=
{{Paper
|id=None
|storemode=property
|title=Tractability of the Crisp Representations of Tractable Fuzzy Description Logics
|pdfUrl=https://ceur-ws.org/Vol-654/pospaper4.pdf
|volume=Vol-654
|dblpUrl=https://dblp.org/rec/conf/semweb/BobilloD10
}}
==Tractability of the Crisp Representations of Tractable Fuzzy Description Logics==
https://ceur-ws.org/Vol-654/pospaper4.pdf
Tractability of the Crisp Representations of
Tractable Fuzzy Description Logics
Fernando Bobillo1 and Miguel Delgado2
1
Dpt. of Computer Science and Systems Engineering, University of Zaragoza, Spain
2
Dpt. of Computer Science and Artificial Intelligence, University of Granada, Spain
Email: fbobillo@unizar.es, mdelgado@ugr.es
Abstract. An important line of research within the field 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 ontol-
ogy 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 field of fuzzy DLs is the compu-
tation 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 different fam-
ilies of fuzzy operators (also called fuzzy logics), namely Zadeh [2], Gödel [3],
and Lukasiewicz [4]. To be precise, in Gödel and Lukasiewicz it is necessary to
restrict to the finite case, i.e., where the set of degrees of truth is finite and fixed.
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 efficiency of reasoning.
In OWL 2, the current standard language for ontology representation, three
fragments (called profiles) have been identified, 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 prop-
erty: 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 verified, focusing on the case of tractable fuzzy
DLs, which is a very interesting case in real-world applications.
Definition 1. A fuzzy DL language X is closed under reduction iff the crisp
representation of a fuzzy ontology in X is in the (crisp) DL language X .
Table 1. Summary of the relation among OWL 2 and its three profiles.
OWL 2 OWL 2 EL OWL 2 QL OWL 2 RL
Class X X X
ObjectIntersectionOf X restricted X
ObjectUnionOf restricted
ObjectComplementOf restricted restricted
ObjectAllValuesFrom restricted
ObjectSomeValuesFrom X restricted restricted
DataAllValuesFrom restricted
DataSomeValuesFrom X X restricted
...
ObjectProperty X X X
DatatypeProperty X X X
...
ClassAssertion X X X
ObjectPropertyAssertion X X X
SubClassOf X X X
SubObjectPropertyOf X X X
SubDataPropertyOf X X 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 differ 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 ∈ {≥, >}, and α ∈ [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 logi-
cal 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 different fuzzy operators have many different logical properties.
Crisp representations of fuzzy DLs. The basic idea of the crisp represen-
tation 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 {ha :
∃R.C ≥ 0.6i, ha : ¬∃R.C > 0.8i}. 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 {a : ∃R≥0.6 .C≥0.6 , a : ∀R≥0.8 .(¬C≥0.8 )}.
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 Gödel 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 Gödel 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 reduc-
tion iff it includes GCIs and role hierarchies. t
u
The proof of this property is trivial from the crisp representation [2]. This re-
sult 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 profiles 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 ). t
u
The case of Gödel fuzzy logic. The full details of the crisp representation in
Gödel 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 verified by the three OWL 2 profiles.
Property 2. In Gödel fuzzy logic, a fuzzy DL language X is closed under reduc-
tion iff it verifies each of the following conditions:
– X includes GCIs.
– X includes role hierarchies.
– If X includes universal (all) restrictions, then it also include conjunction. t
u
The case of Lukasiewicz fuzzy logic. The full details of the crisp represen-
tation 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 verifies 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.
t
u
Again, the proof of this property is trivial from the crisp representation [4].
The three OWL 2 profiles 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 different 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 Gödel 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 Gödel 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 Gödel 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 repre-
sentations. For instance, domain and range restrictions can be treated as GCIs,
but their crisp representation are more efficient 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., Gómez-Romero, J.: Crisp representations and reason-
ing for fuzzy ontologies. International Journal of Uncertainty, Fuzziness and
Knowledge-Based Systems 17(4) (2009) 501–530
3. Bobillo, F., Delgado, M., Gómez-Romero, J., Straccia, U.: Fuzzy description logics
under Gödel semantics. Int. J. of Approximate Reasoning 50(3) (2009) 494–514
4. Bobillo, F., Straccia, U.: Towards a crisp representation of fuzzy description log-
ics 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 Profiles. http://www.w3.org/TR/owl2-profiles.