=Paper=
{{Paper
|id=Vol-327/paper-5
|storemode=property
|title=Optimizing the Crisp Representation of the Fuzzy Description Logic SROIQ
|pdfUrl=https://ceur-ws.org/Vol-327/paper5.pdf
|volume=Vol-327
|dblpUrl=https://dblp.org/rec/conf/semweb/BobilloDG07a
}}
==Optimizing the Crisp Representation of the Fuzzy Description Logic SROIQ==
https://ceur-ws.org/Vol-327/paper5.pdf
Optimizing the Crisp Representation of the
Fuzzy Description Logic SROIQ
Fernando Bobillo, Miguel Delgado, and Juan Gómez-Romero
Department of Computer Science and Artificial Intelligence, University of Granada
C. Periodista Daniel Saucedo Aranda, 18071 Granada, Spain
Phone: +34 958243194; Fax: +34 958243317
Email: fbobillo@decsai.ugr.es, mdelgado@ugr.es, jgomez@decsai.ugr.es
Abstract. 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 appropri-
ate 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ödel 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.
1 Introduction
Description Logics (DLs for short) [1] are a family of logics for representing
structured knowledge which have proved to be very useful as ontology languages.
For instance, SROIQ(D) [2] is the subjacent DL of OWL 1.1., a recent extension
of the standard language OWL1 which is its most likely immediate successor.
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 [3] for an overview).
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) expres-
sive 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 [4].
An alternative is to represent fuzzy DLs using crisp DLs and to reduce reason-
ing 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 sup-
port 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 ( [3] is a good survey), the representation of them using
crisp description logics has not received such attention. The first efforts in this
direction are due to U. Straccia, who considered fuzzy ALCH [5] and fuzzy ALC
with truth values taken from an uncertainty lattice [6]. F. Bobillo et al. extended
Straccia’s work to SHOIN , including fuzzy nominals and fuzzy General Concept
Inclusions (GCIs) with a semantics given by Kleene-Dienes (KD) implication [7].
Finally, G. Stoilos et al. extended this work to SROIQ [8]. This paper improves
the latter work providing the following contributions:
– We provide a full representation, differently from [8] which do not show
how to reduce qualified cardinality restrictions, local reflexivity concepts in
expressions of the form ρ(∃S.Self, Cγ) nor negative role assertions.
– [5, 8] force GCIs and Role Inclusion Axioms (RIAs) to be either true or
false, but we will allow them to be verified up to some degree by using Gödel
implication in the semantics.
– We improve one of their starting points (the reduction presented in [5]) by
reducing the number of new atomic elements and their corresponding axioms.
– We show how to optimize some important GCIs.
– We present DeLorean, our implementation of the reduction and the first
implemented reasoner supporting fuzzy SHOIN .
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 Fuzzy SROIQ
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 [7–9], but we will use Gödel
implication in the semantics of GCIs and RIAs.
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 in-
ductively 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 ∈ [0, 1]: C, D → A | > | ⊥ | C u D | C t
D | ¬C | ∀R.C | ∃R.C | {α1 /o1 , . . . , αm /om } | (≥ n S.C) | (≤ n S.C) | ∃S.Self .
Notice that the only difference with the crisp case is the presence of fuzzy nom-
inals [7]. Complex roles are built using the syntax rule R → RA | R− | U .
A fuzzy Knowledge Base (fKB) comprises two parts: the extensional knowl-
edge, i.e. particular knowledge about some specific situation (a fuzzy Assertional
Box or ABox KA with statements about individuals) and the intensional knowl-
edge, i.e. general knowledge about the application domain (a fuzzy Terminolog-
ical 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 γ ∈ [0, 1]. Moreover, for every operator ./ we define (i) its symmetric
operator ./− defined as ≥− =≤, >− =<, ≤− =≥, <− =>, and (ii) its negation
operator ¬ ./, defined as ¬ ≥=<, ¬ >=≤, ¬ ≤=>, ¬ <=≥.
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 = R1 R2 . . . 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 . . . Sn R
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 map-
ping (i) every individual onto an element of ∆I , (ii) every concept C onto a func-
tion C I : ∆I → [0, 1], (iii) every role R onto a function RI : ∆I × ∆I → [0, 1].
C I (resp. RI ) denotes the membership function of the fuzzy concept C (resp.
fuzzy role R) w.r.t. I. C I (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:
>I (a) = 1
⊥I (a) = 0
(C u D)I (a) = C I (a) ⊗ DI (a)
(C t D)I (a) = C I (a) ⊕ DI (a)
(¬C)I (a) = C I (a)
(∀R.C)I (a) = inf b∈∆I {RI (a, b) → C I (b)}
(∃R.C)I (a) = supb∈∆I {RI (a, b) ⊗ C I (b)}
{α1 /o1 , . . . , αm /om }I (a) = supi | a∈{oIi } αi
(≥ 0 S.C)I (a) = >I (a) = 1
(≥ m S.C)I (a) = supb1 ,...,bm ∈∆I [(⊗ni=1 {S I (a, bi ) ⊗ C I (bi )}) (⊗j 0 then S I (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 [10].
Some logical properties. It can be easily shown that f SROIQ is a sound ex-
tension of crisp SROIQ, because fuzzy interpretations coincide with crisp in-
terpretations if we restrict the membership degrees to {0, 1}.
In the fuzzy DLs literature, the notation fi DL has been proposed [11], where
i is the fuzzy implication function considered. Here in after we will concentrate
on fKD SROIQ, restricting ourselves to the Zadeh family: minimum t-norm,
maximum t-conorm, Lukasiewicz negation and KD implication, with the excep-
tion of GCIs and RIAs, where we will consider Gödel implication. This choice
comes from the fact that KD implication specifies a t-norm, a t-conorm and
a negation which make possible the reduction to a crisp KB, as we will see in
Section 3 (other fuzzy operators are not suitable for a similar reduction).
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 [7].
Another common semantics which could be considered is the one based on
Zadeh’s set inclusion (C v D = ∀x ∈ ∆I , C I (x) ≤ DI (x)) as in [10, 12], but it
forces the axioms to be either true or false. For example, under this semantics
it is not possible that concept Hotel subsumes concept Inn with degree 0.5.
Gödel 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 equiva-
lent Negation Normal Form (NNF), which is obtained by pushing in the usual
manner negation in front of atomic concepts, fuzzy nominals and local reflexiv-
ity 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 An Optimized Crisp Representation for Fuzzy SROIQ
In this section we show how to reduce a fKD SROIQ fKB into a crisp KB,
similarly as in [5, 7, 8]. The procedure preserves reasoning, so existing SROIQ
reasoners could be applied to the resulting KB. First we will describe the reduc-
tion and then we will provide an illustrating example. The basic idea is to create
some new crisp concepts and roles, representing the α-cuts of the fuzzy concepts
and relations, and to rely on them. Next, some new axioms are added to preserve
their semantics and finally every axiom in the ABox, the TBox and the RBox is
represented, independently from other axioms, using these new crisp elements.
Adding (an optimized number of ) new elements. Let Af K and Rf K be the set of
atomic concepts and atomic roles occurring in a fKB f K = hf KA , f KT , f KR i.
In [5] it is shown that the set of the degrees which must be considered for
any reasoning task is defined as N f K = X f K ∪ {1 − α | α ∈ X f K }, where
X f K = {0, 0.5, 1} ∪ {γ | hτ ./ γi ∈ f K}. This also holds in fKD SROIQ, but
note that it is not necessarily true when other fuzzy operators are considered.
Without loss of generality, it can be assumed that N f K = {γ1 , . . . , γ|N f K | } and
γi < γi+1 , 1 ≤ i ≤ |N f K | − 1. It is easy to see that γ1 = 0 and γ|N f K | = 1.
Now, for each α, β ∈ N f K with α ∈ (0, 1] and β ∈ [0, 1), for each A ∈ Af K
and for each RA ∈ Rf K , 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 [5, 7] consider A≥0 and R≥0 .
The semantics of these newly introduced atomic concepts and roles is pre-
served by some terminological and role axioms. For each 1 ≤ i ≤ |N f K | − 1, 2 ≤
j ≤ |N f K | − 1 and for each A ∈ Af K , T (N f K ) is the smallest terminology
containing these two axioms: A≥γi+1 v A>γi , A>γj v A≥γj . Similarly, for each
RA ∈ Rf K , R(N f K ) 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 f K |) [5, 7]:
A<γk v A≤γk , A≤γi v A<γi+1
A≥γk u A<γk v ⊥, A>γi u A≤γi v ⊥
> v A≥γk t A<γk , > 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 [5], although
it introduces some unnecessary axioms: C≥0 v D≥0 and C>1 v D>1 .
Summing up, a fKB f K = hf KA , f KT , f KR i is reduced into a KB K(f K) =
hσ(f KA ), T (N f K ) ∪ κ(f K, f KT ), R(N f K ) ∪ κ(f K, f KR )i.
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: X f K = {0, 0.5, 1, 0.75}, so N f K =
{0, 0.25, 0.5, 0.75, 1}.
Next, we create some new atomic concepts and roles, as well as some axioms
preserving their semantics. T (N f K ) = ∅ and R(N f K ) will contain the follow-
ing 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
isClose T o>0 .
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−
T o− −
>0.75 , isCloseT o≥1 v isCloseT o≥1 }. t
u
Optimizing GCI reductions. GCI reductions can be optimized in several cases:
– hC v > ./ γi and h⊥ v D ./ γi are tautologies, so their reductions are
unnecessary in the resulting KB.
– κ(> 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.
– κ(C v ⊥ ./ γ) = ρ(C, > 0) v ⊥. This appears when two concepts are
disjoint i.e. C and D are disjoint iff C u D v ⊥ holds with degree 1.
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 un-
necessary. This is very useful in concept definitions involving the nominal con-
structor. 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
to: {C>0 v {o1 , o2 }, C≥0.5 v {o1 }}.
Table 1. Mapping of concept and role expressions.
x y ρ(x, y)
> Bγ >
> Cγ ⊥
⊥ Bγ ⊥
⊥ Cγ >
A ≥α A≥α
A >β A>β
A ≤β ¬A>β
A <α ¬A≥α
¬A ./ γ ρ(A, ./− 1 − γ)
C uD Bγ ρ(C, Bγ) u ρ(D, Bγ)
C uD Cγ ρ(C, Cγ) t ρ(D, Cγ)
C tD Bγ ρ(C, Bγ) t ρ(D, Bγ)
C tD Cγ ρ(C, Cγ) u ρ(D, Cγ)
∃R.C Bγ ∃ρ(R, Bγ).ρ(C, Bγ)
∃R.C Cγ ∀ρ(R, ¬C γ).ρ(C, Cγ)
∀R.C ≥α ∀ρ(R, > 1 − α).ρ(C, ≥ α)
∀R.C >β ∀ρ(R, ≥ 1 − β).ρ(C, > β)
∀R.C ≤β ∃ρ(R, ≥ 1 − β).ρ(C, ≤ β)
∀R.C <α ∃ρ(R, > 1 − α).ρ(C, < α)
{α1 /o1 , . . . , αm /om } ./ γ {oi | αi ./ γ, 1 ≤ i ≤ n}
¬{α1 /o1 , . . . , αm /om } ./ γ ρ({α1 /o1 , . . . , αm /om }, ./− 1 − γ)
≥ 0 S.C ./ γ ρ(>, ./ γ)
≥ m S.C Bγ ≥ m ρ(S, Bγ).ρ(C, Bγ)
≥ m S.C Cγ ≤ m−1 ρ(S, ¬ C γ).ρ(C, ¬ C γ)
≤ n S.C ≥ α ≤ n ρ(S, > 1 − α).ρ(C, > 1 − α)
≤ n S.C > β ≤ n ρ(S, ≥ 1 − β).ρ(C, ≥ 1 − β)
≤ n S.C ≤ β ≥ n+1 ρ(S, ≥ 1 − β).ρ(C, ≥ 1 − β)
≤ n S.C < α ≥ n+1 ρ(S, > 1 − α).ρ(C, > 1 − α)
∃S.Self Bγ ∃ρ(S, Bγ).Self
∃S.Self Cγ ¬∃ρ(S, ¬ C γ).Self
RA ≥α R≥α
RA >β R>β
RA ≤β ¬R>β
RA <α ¬R≥α
R− Bγ ρ(R, Bγ)−
U ≥α U
U >β U
Table 2. Reduction of the axioms.
σ(ha : C ./ γi) a : ρ(C, ./ γ)
σ(h(a, b) : R ./ γi) (a, b) : ρ(R, ./ γ)
σ(ha 6= bi) a 6= b
σ(ha = bi) a=b
S S
κ(C v D ≥ α) γ∈N f K −{0} | γ≤α {ρ(C, ≥ γ) v ρ(D, ≥ γ)} γ∈N f K | γ<α {ρ(C, > γ) v ρ(D, > γ)}
κ(C v D > β) κ(C v D ≥ β) ∪ {ρ(C, > β) v ρ(D, > β)}
S S
κ(hR1 . . . Rn v R ≥ αi) γ∈N f K −{0} | γ≤α {ρ(R1 , ≥ γ) . . . ρ(Rn , ≥ γ) v ρ(R, ≥ γ)} γ∈N f K | γ<α
{ρ(R1 , > γ) . . . ρ(Rn , > γ) v ρ(R, > γ)}
κ(hR1 . . . Rn v R > βi) κ(hR1 . . . Rn v R ≥ βi) ∪ {ρ(R1 , > β) . . . ρ(Rn , > β) v ρ(R, > β)}
κ(dis(S1 , S2 )) dis(ρ(S1 , > 0), ρ(S2 , > 0))
κ(ref (R)) ref (ρ(R, ≥ 1))
κ(asy(S)) asy(ρ(S, > 0)
Theorem 1. A fKD SROIQ fKB f K is satisfiable iff K(f K) is satisfiable.
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 f K | is linearly bounded by |f KA | + |f KT | + |f KR |.
– |σ(f KA )| = |f KA |.
– |T (N f K )| = 2 · (|N f K | − 1) · |Af K |.
– |κ(f K, T )| ≤ 2 · (|N f K | − 1) · |T |.
– |R(N f K )| = 2 · (|N f K | − 1) · |Rf K |.
– |κ(f K, R)| ≤ 2 · (|N f K | − 1) · |R|.
The resulting KB is quadratic because it depends on the number of rele-
vant degrees |N f K |. 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.
Then, we need N f K −1 concepts of the form A≥α and another N f K −1 concepts
of the form A>β to represent it, as well as 2 · |N f K | − 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.
4 Implementation: DeLorean
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 fKD SHOIN
(OWL DL), since DIG interface does not yet support full SROIQ.
Fig. 1. Architecture of DeLorean reasoner.
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. Nev-
ertheless, 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
Table 3 shows the influence of the number of degrees on the time of the
reduction process as well as on the time (in seconds) of a classification test over
the resulting crisp ontology.
Table 3. Influence of the number of degrees in the performance of DeLorean.
Number of degrees crisp 3 5 7 9 11
Reduction time - 1.18 6.28 23.5 64.94 148.25
Reasoning time 0.56 0.98 1.343 2.88 4.28 6.47
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 Conclusions and Future Work
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ödel 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ödel implication provides better logical properties than KD,
but KD for example allows to reason with modus tolens [7]. A representation
language could allow the use of two types of GCIs and RIAs vKD y vG (with
semantics based on KD and Gödel implications respectively) similarly as [13]
which allows three types of subsumption. This way, the ontology developer would
be free to choose the better option for his own needs. [7] shows how to reduce
GCIs under KD semantics, and RIAs can be reduced similarly.
Future work could include to compare DeLorean with other fuzzy DL rea-
soners, 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 fKD SROIQ (and hence OWL 1.1) as soon as
DIG 2.0 interface is available, so it is independent of any concrete crisp reasoner.
Acknowledgements
This research has been partially supported by the project TIN2006-15041-C04-01
(Ministerio de Educación y Ciencia). Fernando Bobillo holds a FPU scholarship
from Ministerio de Educación y Ciencia. Juan Gómez-Romero holds a scholarship
from Consejerı́a de Innovación, Ciencia y Empresa (Junta de Andalucı́a).
References
1. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F.: The
Description Logic Handbook: Theory, Implementation, and Applications. Cam-
bridge University Press (2003)
2. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Pro-
ceedings of the 10th International Conference of Knowledge Representation and
Reasoning (KR-2006). (2006) 452–457
3. Lukasiewicz, T., Straccia, U.: An overview of uncertainty and vagueness in de-
scription logics for the semantic web. Technical Report INFSYS RR-1843-06-07,
Institut für Informationssysteme, Technische Universität Wien (2006)
4. Sirin, E., Cuenca-Grau, B., Parsia, B.: From wine to water: Optimizing description
logic reasoning for nominals. In: Proceedings of the 10th International Conference
of Knowledge Representation and Reasoning (KR-2006). (2006) 90–99
5. Straccia, U.: Transforming fuzzy description logics into classical description logics.
In: Proceedings of the 9th European Conference on Logics in Artificial Intelligence
(JELIA-04). Volume 3229 of Lecture Notes in Computer Science., Springer-Verlag
(2004) 385–399
6. Straccia, U.: Description logics over lattices. International Journal of Uncertainty,
Fuzziness and Knowledge-Based Systems 14(1) (2006) 1–16
7. Bobillo, F., Delgado, M., Gómez-Romero, J.: A crisp representation for fuzzy
SHOIN with fuzzy nominals and general concept inclusions. In da Costa, P.C.G.,
Laskey, K.B., Laskey, K.J., Fung, F., Pool, M., eds.: Proceedings of the 2nd ISWC
Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2006). Volume
218., CEUR Workshop Proceedings (2006)
8. Stoilos, G., Stamou, G.: Extending fuzzy description logics for the semantic web.
In: Proceedings of the 3rd International Workshop on OWL: Experiences and Di-
rections (OWLED 2007). (2007)
9. Straccia, U.: A Fuzzy Description Logic for the Semantic Web. In: Fuzzy Logic
and the Semantic Web. Volume 1 of Capturing Intelligence. Elsevier Science (2006)
73–90
10. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intel-
ligence Research 14 (2001) 137–166
11. Stoilos, G., Stamou, G., Tzouvaras, V., Pan, J.Z., Horrocks, I.: Fuzzy OWL:
Uncertainty and the semantic web. In: Proceedings of the International Workshop
on OWL: Experience and Directions (OWLED 2005). (2005)
12. Stoilos, G., Straccia, U., Stamou, G., Pan, J.Z.: General concept inclusions in fuzzy
description logics. In: Proceedings of the 17th European Conference on Artificial
Intelligence (ECAI 06). (2006) 457–461
13. Ma, Y., Hitzler, P., Lin, Z.: Algorithms for paraconsistent reasoning with OWL. In
Franconi, E., Kifer, M., May, W., eds.: Proceedings of the 4th European Semantic
Web Conference (ESWC 2007). (2007) 399–413