Fuzzy Description Logics are a family of logics which allow the representation of (and the reasoning within) structured knowledge affected by uncertainty and vagueness. They were born to overcome the limitations of classical Description Logics when dealing with such kind of knowledge, but they bring out some new challenges, requiring an appropriate fuzzy language to be agreed and needing practical and highly optimized implementations of the reasoning algorithms. In the current paper we face these problems by presenting a reasoning preserving procedure to obtain a crisp representation for a fuzzy extension of SHOIN , which makes possible to reuse a crisp representation language as well as currently available reasoners, which have demonstrated a very good performance in practice. As an additional contribution, we define the syntax and semantics of a novel fuzzy version of the nominal construct and allow to reason within fuzzy general concept inclusions.
Ontologies [
Nowadays, the World Wide Web Consortium (W3C) standard for ontology
representation is OWL Web Ontology Language1, a language comprising three
sublanguages of increasing expressive power: OWL Lite, OWL DL and OWL Full
(being OWL DL the most used level and nearly equivalent to SHOIN (D) [
An alternative way to obtain fuzzy ontologies facing these two problems is
i) to represent fuzzy DLs using crisp DLs and ii) to reduce reasoning within
fuzzy DLs to reasoning within crisp DLs. This way it would be possible to
translate them automatically into a crisp ontology language (e.g. OWL) and
to use currently available reasoners (e.g. Pellet [
On the other hand, current fuzzy DLs still present some limitations which
we think that should be overcome. Some works on fuzzy DLs deal with nominals
(named individuals) but they choose not to fuzzify the nominal construct arguing
that a fuzzy singleton set does not represent any real concept world [
Our work provides the following contributions. Firstly, we propose a
different definition of f SHOIN , including a fuzzy nominal construct and fuzzy GCIs.
Secondly, we reduce reasoning in fKDSHOIN to reasoning in SHOIN ,
extending [
Fuzzy S HOI N
In this section we define f SHOIN , which extends SHOIN to the fuzzy case
by letting (i) concepts denote fuzzy sets of individuals and (ii) roles denote fuzzy
binary relations between individuals. Our logic is similar to [
A | (atomic concept) > | (top concept) ⊥ | (bottom concept) C u D | (concept conjunction) C t D | (concept disjunction)
¬C | (concept negation) ∀R.C | (universal quantification) ∃R.C | (full existential quantification) {(o1, α1), . . . , (om, αm)} | (nominals) (≥ n S) | (at-least unqualified number restriction) (≤ n S) (at-most unqualified number restriction) If RA is an atomic role, complex roles are built using this syntax rule:
R → RA | R−
A fuzzy Knowledge Base (fKB) comprises two parts: 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), and the extensional
knowledge, i.e. particular knowledge about some specific situation (a fuzzy
Assertional Box or ABox KA with statements about individuals). A fuzzy ABox
f KA consists of a finite set of fuzzy assertions, which can be individual assertions
or constraints on the truth value of a concept or role assertion. An individual
assertion is either an inequality of individuals ha 6= bi or an equality of individuals
ha = bi (they are necessary since we do not impose unique name assumption). A
constraint on the truth value of a concept or role assertion is an expression of the
form hΨ ≥ αi, hΨ > βi, hΦ ≤ βi, hΦ < αi, where Ψ is an assertion of the form
a : C or (a, b) : R, Φ is an assertion of the form a : C, α ∈ (0, 1] and β ∈ [0, 1)).
3 A simple role is a non transitive role not having transitive sub-roles i.e. R is a sub-role
of R0 if R v∗R0, where v∗ is the transitive-reflexive closure of v
Note that fuzzy assertions of the form h(a, b) : R ≤ βi, h(a, b) : R < αi are not
allowed since they relate to negated roles, which are not part of SHOIN . A
fuzzy TBox f KT consists of a finite set of fuzzy terminological axioms. A fuzzy
terminological axiom is either a fuzzy GCI or a concept definition. A fuzzy GCI
constrains the truth value of a GCI i.e. it is an expression of the form hΩ ≥ αi,
hΩ > βi, hΩ ≤ βi or hΩ < αi, where Ω is a GCI of the form C v, α ∈ (0, 1] and
β ∈ [0, 1). We think that concept definitions should not be fuzzified, so C ≡ D
is an abbreviation of the pair of axioms hC v D ≥ 1i and hD v C ≥ 1i. A fuzzy
RBox f KR consists of a finite set of fuzzy role axioms. A fuzzy role axiom is
either a fuzzy role inclusion R v R0, a fuzzy role definition R ≡ R0 (a short hand
for both R v R0 and R0 v R) or a transitive role axiom trans(R).
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 every individual onto an element of ΔI , every concept C onto a function
CI : ΔI → [
(¬C)I (a) = ¬CI (a) (∀R.C)I (a) = infb∈ΔI {RI (a, b) → CI (b)} (∃R.C)I (a) = supb∈ΔI {RI (a, b) ∧ CI (b)} {(o1, α1), . . . , (om, αm)}I (a) = supi | a∈{oiI} αi (≥ 0)I (a) = >I (a) = 1 (≥ m)I (a) = supb1,...,bm∈ΔI [∧im=1SI (a, bi) V ∧i<j {bi 6= bj }] (≤ n S)I (a) = ¬(≥ n+1 S)I (a) (R−)I (a, b) = RI (b, a)
We will shortly justify our decision of fuzzifying the nominal construct by showing an example. Suppose we want to represent the concept of country where German is a widely spoken language as C ≡ {germany, austria, switzerland}. The classical semantics for the nominal construct is: {oi}I (a) = 1 if a ∈ {oiI } or 0 otherwise. This semantics forces switzerland to fully belong to the concept or not, despite of German-speaking community of Switzerland represents only about two thirds of the total population of the country. On the contrary, our proposal allows to define {(germany, 1), (austria, 1), (switzerland, 0.67)}, which does represent a real-life concept. It is easy to see that our definition generalizes the previous definition for the nominal construct, as {o1, . . . , om} is equivalent to {(o1, 1), . . . , (om, 1)}.
A fuzzy interpretation I satisfies (is a model of): – A fuzzy assertion ha : C ≥ αi iff CI (aI ) ≥ α. Similar definitions can be given for > β, ≤ β and < α. – A fuzzy assertion h(a, b) : R ≥ αi iff RI (aI , bI ) ≥ α. Similar definitions can be given for > β, ≤ β and < α. – An assertion ha 6= bi iff aI 6= bI (resp. ha = bi iff aI = bI ). Note that we consider individuals assertions to be crisp. – A fuzzy GCI hC v D ≥ αi iff infa∈ΔI {CI (a) → DI (a)} ≥ α. Similar definitions can be given for > β, ≤ β and < α. – A concept definition C ≡ D iff CI = DI . – A role inclusion axiom R v R0 iff RI ⊆ R0I . – A role definition axiom R ≡ R0 iff RI = R0I . – An axiom trans(R) iff ∀a, b ∈ ΔI , RI (a, b) ≥ supc∈ΔI RI (a, c) ∧ RI (c, b). – A fKB hf KA, f KT , f KRi iff it satisfies each element in KA, KT and KR.
The definition of fuzzy GCIs allows concept subsumption to hold to a certain
degree in [
The following lemma shows that our definition of f SHOIN is a sound
extension of crisp SHOIN :
Lemma 1. Fuzzy interpretations coincide with crisp interpretations if we
restrict to the membership degrees of 0 and 1 [
Some properties. Here in after we will concentrate on fKDSHOIN ,
restricting ourselves to the minimum t-norm a ∧ b = min{a, b}, maximum t-conorm
a ∨ b = max{a, b}, Lukasiewicz negation ¬a = 1 − a and the Kleene-Dienes
implication a → b = max{1 − a, b}. For instance, in the semantics of the at-least
unqualified number restriction, ∧i<j {bi 6= bj } means that there must exist n
distinct elements of the domain. The choice of the t-norm and the t-conorm will
be justified in Sect. 3. On the other hand, in fuzzy DLs it is very common to use
the Kleene-Dienes implication in the semantics of universal quantification, so for
the sake of coherence we have chosen to use it in the semantics of fuzzy GCIs as
well. Similarly as in [
Unfortunately, the use of Kleene-Dienes implication in the semantics of fuzzy
GCIs brings about two counter-intuitive effects. Firstly, a concept does not fully
subsume itself i.e. C v C ⇒ infa∈ΔI max{1 − CI (a), CI (a)} = 0.5. Secondly,
crisp concept subsumption forces fuzzy concepts to be crisp i.e. hC v D ≥ 1i ⇒
infa∈ΔI max{1 − CI (a), DI (a)} ≥ 1 which is true iff for each element of the
domain DI (a) = 1 or 1 − CI (a) ≥ 1 ⇒ CI (a) = 0. These problems point
out the need of further investigation involving alternative fuzzy operators. For
example, using a residuum based implications (see [
A Crisp Representation for Fuzzy S HOI N
In this section we show how to reduce a fKDSHOIN fKB into a crisp
Knowledge Base (KB). The procedure preserves reasoning, so existing SHOIN
reasoners could be applied to the resulting KB. [
New Elements. Let AfK and RfK be the set of atomic concepts and atomic
roles occurring in a fKB f K = hf KA, f KT , f KRi. In [
This also holds in fKDSHOIN , but note that it is no longer true when other
fuzzy operators are considered. In that case, the process may calculate all
possible degrees in [
Now, for each α, β ∈ N fK , α ∈ (0, 1], β ∈ [0, 1), for each relation in {≥, > , ≤, <}, for each A ∈ AfK and for each R ∈ RfK , four new atomic concepts A≥α, A>β , 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. Neither A<0, A>1, R>1 are considered (they are always empty sets) nor A≤1, A≥0, R≥0 (they are always equivalent to the top concept).
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, for each 2 ≤ j ≤ |N fK |, for each A ∈ AfK and for each R ∈ RfK , T (N fK ) is the smallest terminology containing the following axioms:
A≥γi+1 v A>γi
A<γj v A≤γj A≥γj u A<γj v ⊥ > v A≥γj t A<γj
A>γi v A≥γi
A≤γi v A<γi+1 A>γi u A≤γi v ⊥ > v A>γi t A≤γi Similarly, R(N fK ) is the smallest terminology containing these two axioms: R≥γi+1 v R>γi
R>γi v R≥γi
It is easy to see that allowing expressions of the type h(a, b) : R ≤ βi, h(a, b) : R < αi would need additional role constructs (role conjunction, role disjunction, bottom role and top role).
Mapping the ABox. Fuzzy assertions are mapped into SHOIN assertions using a mapping σ. Let γ ∈ N fK , ./ ∈ {≥, <, ≤, >}, σ(f KA) = {σ(Φ)|Φ ∈ f KA}, where σ(Φ) is defined as in the following table (where ρ is inductively defined on the structure of concepts and roles as in Table 1):
σ(ha : C ./ γ i) = a : ρ(C, ./ γ ) σ(h(a, b) : R ./ γ i) = (a, b) : ρ(R, ./ γ ) σ(ha 6= bi) = a 6= b σ(ha = bi) = a = b Mapping the TBox. f SHOIN fuzzy terminological axioms to either terminological axioms (for ≥ or >) or assertions (for ≤ and <). In the former case, we redefine k(f K, f KT ) as k(f K, f KT ) = SΩ∈fKT k(Ω), where Ω = hC v D{≥, > }γi and k(Ω) is defined as: k(hC v D ≥ γi) = ρ(C, > 1 − γ) v ρ(D, ≥ γ) k(hC v D > γi) = ρ(C, ≥ 1 − γ) v ρ(D, > γ)
In the latter case, new assertions are necessary since negated terminological axioms are nor part of crisp SHOIN . A new function A(f KT ) adds these new assertions to the ABox. A(f KT ) = SΞ∈fKT A(Ξ), where Ξ = hC v D{≤, <}γi and A(Ξ) is defined as:
A(hC v D ≤ γi) = x : ρ(C, ≥ 1 − γ) u ρ(D, ≤ γ)
A(hC v D < γi) = x : ρ(C, > 1 − γ) u ρ(D, < γ)
Note that how to modify the reduction process when alternative implication functions are used remains an open question.
x A A A A R R
y ≥ γ > γ ≤ γ < γ ≥ γ > γ ≥ γ > γ ≤ γ < γ ≥ γ > γ ≤ γ < γ Mapping the RBox. Role axioms are reduced using a function k(fK, fKR) = SΩ∈fKR k(Ω), where k(Ω) is defined as:
k(R v R0) = S k(trans(R)) = Sγ∈NfK,./ ∈{≥,>} ρ(R, ./ γ ) v ρ(R0, ./ γ ) γ∈NfK,./ ∈{≥,>} trans(ρ(R, ./ γ )) Discussion. A fKB fK = hfKA, fKT , fKRi is reduced into a KB K(fK) = hσ(fKA) ∪ A(fKT ), T (NfK) ∪ k(fK, fKT ), R(NfK) ∪ k(fK, fKR)i. The comρ(x, y) A≥γ if γ 6= 0, > otherwise A>γ, if γ 6= 1, ⊥ otherwise A≤γ if γ 6= 0, > otherwise A<γ, if γ 6= 1, ⊥ otherwise R≥γ if γ 6= 0, > otherwise
R>γ, if γ 6= 1, ⊥ otherwise > > > > if γ 6= 1, ⊥ otherwise > > if γ = 1, ⊥ otherwise > ⊥ ⊥ > if γ = 0, ⊥ otherwise ⊥ ⊥ ⊥ > ⊥ > if γ 6= 0, ⊥ otherwise C u D {≥, >} γ ρ(C, {≥, >} γ) u ρ(D, {≥, >} γ) C u D {≤, <} γ ρ(C, {≤, <} γ) t ρ(D, {≤, <} γ) C t D {≥, >} γ ρ(C, {≥, >} γ) t ρ(D, {≥, >} γ) C t D {≤, <} γ ρ(C, {≤, <} γ u ρ(D, {≤, <} γ) ¬C {≥, >} γ ρ(C, {≤, <} 1 − γ) ¬C {≤, <} γ ρ(C, {≥, >} 1 − γ) ∃R.C {≥, >} γ ∃ρ(R, {≥, >} γ).ρ(C, {≥, >} γ) ∃R.C {≤, <} γ ∀ρ(R, {>, ≥} γ).ρ(C, {≤, <} γ) ∀R.C {≥, >} γ ∀ρ(R, {>, ≥} 1 − γ).ρ(C, {≥, >} γ) ∀R.C {≤, <} γ ∃ρ(R, {≥, >} 1 − γ).ρ(C, {≤, <} γ) {(o1, α1), . . . , (om, αm)} ./ γ {oi | αi ./ γ, 1 ≤ i ≤ n}./γ ≥ 0 S ./ γ ρ(>, ./ γ ) ≥ m S {≥, >} γ ≥ m ρ(S, {≥, >} γ) ≥ m S {≤, <} γ ≤ m−1 ρ(S, {>, ≥} γ) ≤ n S {≥, >} γ ≤ n ρ(S, {>, ≥} 1 − γ) ≤ n S {≤, <} γ ≥ n+1 ρ(S, {≥, >} 1 − γ)
R− ./ γ ρ(R, ./ γ )−
plexity of our procedure is quadratic: the ABox is linear while the TBox and
the RBox are quadratic. It is interesting to note that, while [
Unfortunately, we cannot show the proof due to space limitations. Firstly, it has to be proved that the translation preserves the satisfiability of every single statement of the fKB. It can be shown that, if there exists a fuzzy interpretation satisfying a statement, then a crisp interpretation satisfying the result of its translation can be built. Secondly, it has to be proved that the translation preserves the satisfiability of the whole fKB. Then, it has be shown that the translation preserves the clashes. For example, the clash produced by the pair of conjugated axioms ha : A ≥ γi and ha : A < γi is preserved, since the axiom A≥γ u A<γ v ⊥ prevents any individual from belonging to A with degree ≥ γ and degree < γ. 4
Conclusions and Future Work
This paper has presented an alternative approach to achieve fuzzy ontologies,
reusing currently existing crisp ontology languages and reasoners. In
particular, after having presented a sound fuzzy extension of SHOIN including fuzzy
nominals (enabling to define fuzzy sets extensively) and fuzzy GCIs (allowing
to constrain the truth value of a GCI), we have presented a reasoning
preserving procedure (quadratic in complexity) to reduce a fKDSHOIN fKB into a
crisp one. The semantics of fuzzy GCIs reduces the size of the resulting TBox
w.r.t. [
The main direction for future work is to perform an empirical evaluation
in order to validate the theoretical results. From a theoretical point view, we
are considering different fuzzy operators to avoid the counter-intuitive effects of
the Kleene-Dienes implication. We also plan to include a crisp representation
for fuzzy datatypes. Since OWL does not currently allow to define customised
datatypes, it seems interesting to consider OWL Eu [