Classical ontologies are not suitable to represent imprecise nor uncertain pieces of information. Fuzzy Description Logics were born to represent the former type of knowledge, but they require an appropriate fuzzy language to be agreed and an important number of available resources to be adapted. This paper faces these problems by presenting a reasoning preserving procedure to obtain a crisp representation for a fuzzy extension of the logic SROIQ which uses G¨odel implication in the semantics of fuzzy concept and role subsumption. This reduction allows to reuse a crisp representation language as well as currently available reasoners. Our procedure is optimized with respect to the related work, reducing the size of the resulting knowledge base, and is implemented in DeLorean, the first reasoner supporting fuzzy OWL DL.
Description Logics (DLs for short) [
Nevertheless, it has been widely pointed out that classical ontologies are not
appropriate to deal with imprecise and vague knowledge, which is inherent to
several real-world domains. Since fuzzy logic is a suitable formalism to handle
these types of knowledge, several fuzzy extensions of DLs can be found in the
literature (see [
Defining a fuzzy DL brings about that crisp standard languages are no longer
appropriate, new fuzzy languages need to be used, and hence the large number
of resources available need to be adapted to the new framework, requiring an
important effort. An additional problem is that reasoning within (crisp)
expressive DLs has a very high worst-case complexity (e.g. NExpTime in SHOIN )
and, consequently, there exists a significant gap between the design of a decision
procedure and the achievement of a practical implementation [
An alternative is to represent fuzzy DLs using crisp DLs and to reduce reasoning within fuzzy DLs to reasoning within crisp ones. This has several advantages: 1 http://www.w3.org/TR/owl-features – There would be no need to agree a new standard fuzzy language, but every developer could use its own language expressing fuzzy SROIQ, as long as he implements the reduction that we describe. – We will continue using standard languages with a lot of resources available, so the need (and cost) of adapting them to the new fuzzy language is avoided. – We will continue using the existing crisp reasoners. We do not claim that reasoning will be more efficient, but it supposes an easy alternative to support early reasoning in future fuzzy languages. In fact, nowadays there is no reasoner fully supporting a fuzzy extension of OWL DL.
Under this approach an immediate practical application of fuzzy ontologies is feasible, because of its tight relation with already existing languages and tools which have proved their validity.
Although there has been a relatively significant amount of works in extending
DLs with fuzzy set theory ( [
The remainder is organized as follows. Section 2 describes a fuzzy extension of SROIQ and discusses some logical properties. Section 3 depicts a reduction into crisp SROIQ, whereas Section 4 presents our implementation of the procedure. Finally, in Section 5 we set out some conclusions and ideas for future work. 2
In this section we define f SROIQ, which extend SROIQ to the fuzzy case
by letting (i) concepts denote fuzzy sets of individuals and (ii) roles denote fuzzy
binary relations. Axioms are also extended to the fuzzy case and some of them
hold to a degree. The following definition combines [
Syntax. f SROIQ assumes three alphabets of symbols, for concepts, roles and
individuals. The concepts of the language (denoted C or D) can be built
inductively from atomic concepts (A), atomic roles (R), top concept >, bottom
concept ⊥, named individuals (oi), universal role (U ) and simple roles (S, which
will be defined below) according to the following syntax rule, where n, m are
natural numbers (n ≥ 0, m > 0) and αi ∈ [
A fuzzy Knowledge Base (fKB) comprises two parts: the extensional knowledge, i.e. particular knowledge about some specific situation (a fuzzy Assertional Box or ABox KA with statements about individuals) and the intensional knowledge, i.e. general knowledge about the application domain (a fuzzy Terminological Box or TBox KT and a fuzzy Role Box or RBox KR).
In the rest of the paper we will assume ./ ∈ {≥, <, ≤, >}, α ∈ (0, 1], β ∈
[0, 1) and γ ∈ [
A fuzzy ABox consists of a finite set of fuzzy assertions. A fuzzy assertion can be an inequality assertion ha 6= bi, an equality assertion ha = bi or a constraint on the truth value of a concept or role assertion, i.e. an expression of the form hΨ ./ α i, where Ψ is an assertion of the form a : C or (a, b) : R.
A fuzzy TBox consists of fuzzy GCIs, which constrain the truth value of a GCI i.e. they are expressions of the form hΩ ≥ αi or hΩ > βi, where Ω = C v D.
A fuzzy RBox consists of a finite set of role axioms, which can be fuzzy RIAs hw v R ≥ αi or hw v R > βi for a role chain w = R1R2 . . . Rn, or any other of the role axioms from the crisp case: transitive trans(R), disjoint dis(S1, S2), reflexive ref (R), irreflexive irr(S), symmetric sym(R) or asymmetric asy(S). As in the crisp case, role axioms cannot contain U and every RIA should be ≺regular for a regular order ≺. A RIA hw v R B γi is ≺-regular if R = RA and (i) w = RR, or (ii) w = R−, or (iii) w = S1 . . . Sn and Si ≺ R for all i = 1, . . . , n, or (iv) w = RS1 . . . Sn and Si ≺ R for all i = 1, . . . , n, or (v) w = S1 . . . SnR and Si ≺ R for all i = 1, . . . , n.
Simple roles are inductively defined: (i) RA is simple if does not occur on the right side of a RIA, (ii) R− is simple if R is, (iii) if R occurs on the right side of a RIA, R is simple if, for each hw v R B γi, w = S for a simple role S.
A fuzzy axiom τ is positive (denoted hτ B αi) if it is of the form hτ ≥ αi or hτ > βi, and negative (denoted hτ C αi) if it is of the form hτ ≤ βi or hτ < αi. hτ = αi is equivalent to the pair of axioms hτ ≥ αi and hτ ≤ αi.
Notice that negative GCIs or RIAs are not allowed, because they correspond
to negated GCIs and RIAs respectively, which are not part of crisp SROIQ.
Semantics. A fuzzy interpretation I is a pair (ΔI , ·I ) consisting of a non empty
set ΔI (the interpretation domain) and a fuzzy interpretation function ·I
mapping (i) every individual onto an element of ΔI , (ii) every concept C onto a
function CI : ΔI → [
CI (resp. RI ) denotes the membership function of the fuzzy concept C (resp. fuzzy role R) w.r.t. I. CI (a) (resp. RI (a, b)) gives us the degree of being the individual a an element of the fuzzy concept C (resp. the degree of being (a, b) an element of the fuzzy role R) under the fuzzy interpretation I. We do not impose unique name assumption, i.e. two nominals might refer to the same individual. For a t-norm ⊗, a t-conorm ⊕, a negation function and an implication function →, the fuzzy interpretation function is extended to complex concepts and roles as follows:
A fuzzy interpretation I satisfies (is a model of): – (i) ha : C ≥ αi iff CI (aI ) ≥ α, – (ii) h(a, b) : R ≥ αi iff RI (aI , bI ) ≥ α, – (iii) ha 6= bi iff aI 6= bI , – (iv) ha = bi iff aI = bI , – (v) hC v D ≥ αi iff infa∈ΔI {CI (a) → DI (a)} ≥ α, – (vi) hR1 . . . Rn v R ≥ αi iff supb1...bn+1∈ΔI N[R1I (b1, b2), . . . , RnI(bn, bn+1)] →
RI (b1, bn+1) ≥ α, – (vii) trans(R) iff ∀a, b ∈ ΔI , RI (a, b) ≥ supc∈ΔI RI (a, c) ⊗ RI (c, b), – (viii) dis(S1, S2) iff ∀a, b ∈ ΔI , S1I (a, b) ⊗ S2I (a, b) = 0, – (ix) ref (R) iff ∀a ∈ ΔI , RI (a, a) = 1, – (x) irr(S) iff ∀a ∈ ΔI , SI (a, a) = 0, – (xi) sym(R) iff ∀a, b ∈ ΔI , RI (a, b) = RI (b, a), – (xii) asy(S) iff ∀a, b ∈ ΔI , if SI (a, b) > 0 then SI (b, a) = 0, – (xii) a fKB iff it satisfies each element in f KA, f KT and f KR.
In cases (i), (ii) similar definitions can be given for > β, ≤ β and < α, whereas in cases (v), (vi) a similar definition can be given for > β.
Notice that individual assertions are considered to be crisp
In the rest of the paper we will only consider fKB satisfiability, since (as in
the crisp case) most inference problems can be reduced to it [
In the fuzzy DLs literature, the notation fiDL has been proposed [
However, the use of KD implication in the semantics of GCIs and RIAs
brings about two counter-intuitive effects: (i) in general concepts (and roles) do
not fully subsume themselves and (ii) crisp subsumption (holding to degree 1)
forces some fuzzy concepts and roles to be interpreted as crisp [
Another common semantics which could be considered is the one based on
Zadeh’s set inclusion (C v D = ∀x ∈ ΔI , CI (x) ≤ DI (x)) as in [
G¨odel implication solves the afore-mentioned problems and is suitable for a classical representation as we will see in Section 3. Moreover, for GCIs of the form hC v D ≥ 1i, the semantics is equivalent to that of Zadeh’s set inclusion.
It is possible to transform concept expressions into a semantically equivalent Negation Normal Form (NNF), which is obtained by pushing in the usual manner negation in front of atomic concepts, fuzzy nominals and local reflexivity concepts. In the case of ¬(≥ 0 S), it could be replaced by ⊥ since it is an inconsistent concept. In the following, we will assume that concepts are in NNF.
Irreflexive, transitive and symmetric role axioms are syntactic sugar for every R-implication (and consequently it can be assumed that they do not appear in fKBs) due to the following equivalences: – irr(S) ≡ h> v ¬∃S.Self ≥ 1i, – trans(R) ≡ hRR v R ≥ 1i, – sym(R) ≡ hR v R− ≥ 1i. 3
In this section we show how to reduce a fKDSROIQ fKB into a crisp KB,
similarly as in [
Now, for each α, β ∈ N fK with α ∈ (0, 1] and β ∈ [0, 1), for each A ∈ AfK
and for each RA ∈ RfK , two new atomic concepts A≥α, A>β and two new
atomic roles R≥α, R>β are introduced. A≥α represents the crisp set of individuals
which are instance of A with degree higher or equal than α i.e the α-cut of
A. The other new elements are defined in a similar way. The atomic elements
A>1, R>1, A≥0 and R≥0 are not considered because they are not necessary, due
to the restrictions on the allowed degree of the axioms in the fKB (e.g. we do
not allow GCIs of the form C v D ≥ 0). Note that [
The semantics of these newly introduced atomic concepts and roles is preserved by some terminological and role axioms. For each 1 ≤ i ≤ |N fK | − 1, 2 ≤ j ≤ |N fK | − 1 and for each A ∈ AfK , T (N fK ) is the smallest terminology containing these two axioms: A≥γi+1 v A>γi , A>γj v A≥γj . Similarly, for each RA ∈ RfK , R(N fK ) is the smallest terminology containing R≥γi+1 v R>γi and R>γi v R≥γi .
In contrast to previous works, which use two more atomic concepts A≤β , A<α
and some additional axioms (2 ≤ k ≤ |N fK |) [
A<γk v A≤γk , A≥γk u A<γk v ⊥, > v A≥γk t A<γk ,
A≤γi v A<γi+1 A>γi u A≤γi v ⊥ > v A>γi t A≤γi we use ¬A>γk rather than A≤γk and ¬A≥γk instead of A<γk , since the six axioms above follow immediately from the semantics of the crisp concepts as Proposition 1 shows: Proposition 1. If A≥γi+1 v A>γi and A>γk v A≥γk hold, then the followings axioms are verified: (1) ¬A≥γk v ¬A>γk (2) ¬A>γi v ¬A≥γi+1 (3) A≥γk u ¬A≥γk v ⊥ (4) A>γi u ¬A>γi v ⊥ (5) > v A≥γk t ¬A≥γk (6) > v A>γi t ¬A>γi (1) and (2) derive from the fact that in crisp DLs A v B ≡ ¬B v ¬A. (3) and (4) come from the law of contradiction A u ¬A v ⊥, while (5) and (6) derive from the law of excluded middle > v A t ¬A. Moreover, we do not introduce the axiom A>0 v A≥0; since A≥0 is equivalent to > the axiom trivially holds. Mapping fuzzy concepts, roles and axioms. Concept and role expressions are reduced using mapping ρ, as shown in Table 1. Axioms are reduced as in Table 2, where σ maps fuzzy axioms into crisp assertions and κ maps fuzzy TBox (resp. RBox) axioms into crisp TBox (resp. RBox) axioms.
Notice that ρ(R, Cγ) can only appear in a (crisp) negated role assertion. Notice also that expressions of the form ρ(A, ≥ 0), ρ(A, > 1), ρ(A, ≤ 1), ρ(A, < 0) cannot appear, because there exist some restrictions on the degree of the axioms in the fKB. The same also holds for >
, ⊥ and RA. Besides, expressions of the form ρ(U, Cγ) cannot appear either. Observe that the reduction preserves simplicity of the roles and regularity of the RIAs.
Our reduction of a fuzzy GCI hC v D ≥ 1i is equivalent to the reduction of a
GCI under a semantics based on Zadeh’s set inclusion proposed in [
Summing up, a fKB f K = hf KA, f KT , f KRi is reduced into a KB K(f K) = Example 1. Let us consider the following fKB: {hsym(isCloseT o)i, h(h1, h2) : isCloseT o ≤ 0.75i}. Firstly, hsym(isCloseT o)i is represented as the fuzzy RIA hisCloseT o v isCloseT o−
≥ 1i. Now, we have to compute the number of truth values which have to be considered: XfK = {0, 0.5, 1, 0.75}, so N fK = isClose T o>0.
Next, we create some new atomic concepts and roles, as well as some axioms preserving their semantics. T (N fK ) = ∅ and R(N fK ) will contain the following axioms: isCloseT o≥1 v isCloseT o>0.75, isCloseT o>0.75 v isCloseT o≥0.75, isCloseT o≥0.75 v isCloseT o>0.5, isCloseT o>0.5 v isCloseT o≥0.5, isCloseT o≥0.5 v isCloseT o>0.25, isCloseT o>0.25 v isCloseT o≥0.25 and isCloseT o≥0.25 v T o−>0.75, isCloseT o≥1 v isCloseT o−≥1}.
Finally, we map axioms in the ABox, TBox and RBox. Firstly, σ(h(h1, h2) : isCloseT o ≤ 0.75i) = (h1, h2) : ¬isCloseT o>0.75. Then, κ(hisCloseT o v isCloseT o− ≥ 1i) = {isCloseT o>0 v isCloseT o−>0, isCloseT o≥0.25 v isCloseT o−≥0.25, isClo− seT o>0.25 v isCloseT o−>0.25, isCloseT o≥0.5 v isCloseT o−≥0.5, isCloseT o>0.5 v isCloseT o−>0.5, isCloseT o≥0.75 v isCloseT o−≥0.75, isCloseT o>0.75 v isClose− tu Optimizing GCI reductions. GCI reductions can be optimized in several cases: unnecessary in the resulting KB. – hC v > ./ γ i and h⊥ v D ./ γ i are tautologies, so their reductions are – κ(C
v ⊥ ./ γ ) = ρ(C, > 0) v ⊥ – κ(> v D ./ γ ) = > v ρ(D, ./ γ ). Note that this kind of axiom appears in role range axioms i.e. C is the range of R iff > v ∀R.C holds with degree 1.
. This appears when two concepts are disjoint i.e. C and D are disjoint iff C u D v ⊥ holds with degree 1. to: {C>0 v {o1, o2}, C≥0.5 v {o1}}.
Another optimization involving GCIs follows from the following observation. If the resulting TBox contains A v B, A v C and B v C, then A v C is unnecessary. This is very useful in concept definitions involving the nominal constructor. For example, the reduction of the definition κ(C v {1/o1, 0.5/o2}) = {C>0 v {o1, o2}, C≥0.5 v {o1, o2}, C>0.5 v {o1}, C≥1 v {o1}} can be optimized ≥ α > β ≤ β < α Bγ ≥ α > β
R≥α R>β ¬R>β ¬R≥α ρ(R, Bγ)−
U
U Complexity. |K(f K)| is O(|f K|2) i.e. the resulting knowledge base is quadratic. The ABox is actually linear while the TBox and the RBox are both quadratic: – |N fK | is linearly bounded by |f KA| + |f KT | + |f KR|. – |σ(f KA)| = |f KA|. – |T (N fK )| = 2 · (|N fK | − 1) · |AfK |. – |κ(f K, T )| ≤ 2 · (|N fK | − 1) · |T |. – |R(N fK )| = 2 · (|N fK | − 1) · |RfK |. – |κ(f K, R)| ≤ 2 · (|N fK | − 1) · |R|.
The resulting KB is quadratic because it depends on the number of relevant degrees |N fK |. An immediate solution to obtain a KB which is linear in complexity is to fix the number of degrees which can appear in the knowledge base. From a practical point of view, in most of the applications it is sufficient to consider a small number of degrees, e.g. {0, 0.25, 0.5, 0.75, 1}.
It is easy to see that the complexity of the crisp representation is caused by fuzzy concepts and roles. Fortunately, in real applications not all concepts and roles will be fuzzy. Another optimization would be allowing to specify that a concept (resp. a role) is crisp. For instance, suppose that A is a fuzzy concept. oTfhtehne, fwoermneAed>NβtfoKr−ep1recsoennctepitt,saosf wtheell faosrm2 · A|N≥αfKand another N fK − 1 concepts | − 3 axioms to preserve their semantics. On the other hand, if A is declared to be crisp, we just need one concept to represent it and no new axioms. The case for crisp roles is similar.
An interesting property of the procedure is that the reduction of an ontology can be reused when adding new axioms. In fact, for every new axiom τ , the reduction procedure generates only one new axiom or a (linear in size) set of axioms if τ does not introduce new atomic concepts nor new atomic roles and, in case τ is a fuzzy axiom, if it does not introduce a new degree of truth.
Our prototype implementation of the reduction process is called DeLorean (DEscription LOgic REasoner with vAgueNess). It has been developed in Java with Jena API2, the parser generator JavaCC3, and using DIG 1.1 interface4 to communicate with crisp DL reasoners. Currently the logic supported is fKDSHOIN (OWL DL), since DIG interface does not yet support full SROIQ.
Figure 1 illustrates the architecture of the system. The Parser reads an input file with a fuzzy ontology and translates it into an internal representation. As we have remarked in the Introduction, we could use any language to encode the fuzzy ontology, as long as the Parser can understand the representation and the reduction is properly implemented; consequently we will not get into details of our particular choice. In the next step, the Reduction module implements the procedure described in Section 3, building a Jena model from which an OWL file with an equivalent crisp ontology is created. Finally, the Inference module tests this ontology for consistency, using any crisp reasoner through the DIG interface. The User interface allows the user to introduce the inputs and shows the result of the reasoning and the elapsed time.
We have carried out some experiments in order to evaluate our approach in terms of reasoning, that is, in order to check that the results of the reasoning tasks over the crisp ontology were the expected. The aim of this section is not to perform a full benchmark, which could be the topic of a forthcoming work. Nevertheless, we will show some performance examples to show that our approach is feasible and the increment of time for small ontologies when using a limited number of degrees of truth is acceptable. In any case, optimizations are crucial.
We considered the Koala ontology5, a sample ALCON (D) ontology with 20 named classes, 15 anonymous classes, 4 object properties, 1 datatype property (which we have omitted) and 6 individuals. We extended its axioms with random (lower bound) degrees and we used Pellet reasoner through the DIG interface. 2 http://jena.sourceforge.net/ 3 https://javacc.dev.java.net 4 http://dl.kr.org/dig/ 5 http://http://protege.cim3.net/file/pub/ontologies/koala/koala.owl
It can be observed that the reduction time is quite large with respect to the reasoning time. We recall that DeLorean is currently just a prototype, so the implementation of the reduction process should be optimized. Moreover, as already discussed in the previous section, the reduction can be reused and hence needs to be computed just once. Regarding the reasoning time, the increment of complexity when the fuzzy ontology contains 3 or 5 degrees can be assumed. 5
In this paper we have shown how to reduce a fuzzy extension of SROIQ with fuzzy GCIs and RIAs (under a novel semantics using G¨odel implication) into SROIQ. We have enhanced previous works by reducing the number of new elements and axioms. We have also presented DeLorean, our implementation of this reduction procedure which is, to the very best of our knowledge, the first reasoner supporting fuzzy SHOIN (and hence and eventually fuzzy OWL DL). The very preliminary experimentation shows that our approach is feasible in practice when the number of truth degrees is small, even for our non-optimized prototype. This work means an important step towards the possibility of dealing with imprecise and vague knowledge in DLs, since it relies on existing languages and tools.
In general, G¨odel implication provides better logical properties than KD,
but KD for example allows to reason with modus tolens [
Future work could include to compare DeLorean with other fuzzy DL reasoners, although they support different languages and features and, as far as we know, there does not exist any significant fuzzy knowledge base. We will also allow the definition of crisp concepts and roles in the fuzzy language. Finally, the reasoner will be extended to fKDSROIQ (and hence OWL 1.1) as soon as DIG 2.0 interface is available, so it is independent of any concrete crisp reasoner. This research has been partially supported by the project TIN2006-15041-C04-01 (Ministerio de Educaci´on y Ciencia). Fernando Bobillo holds a FPU scholarship from Ministerio de Educacio´n y Ciencia. Juan G´omez-Romero holds a scholarship from Consejer´ıa de Innovaci´on, Ciencia y Empresa (Junta de Andaluc´ıa).