In the Semantic Web information would be retrieved, processed, combined, shared and reused in the maximum automatic way possible. Obviously, such procedures involve a high degree of uncertainty and imprecision. For example ontology alignment or information retrieval are rarely true or false procedures but usually involve confidence degrees or provide rankings. Furthermore, it is often the case that information itself is imprecise and vague like the concept of a “tall” person, a “hot” place and many more. In order to be able to represent and reason with such type of information in the Semantic Web (SW), as well as, enhance SW applications we present an extension of the Description Logic SHIN with fuzzy set theory. We present the semantics as well as detailed reasoning algorithms for the extended language.
Uncertainty, like imprecision and vagueness, is a factor that can cause the
degradation of the performance of a system. To this end, many applications and
domains have incorporated mathematical frameworks that deal with such type of
information, resulting in the improvement of their effectiveness. Applications like
robotics [
Knowledge in the SW is usually structured in the form of ontologies [10]. This has led to considerable efforts to develop a suitable ontology language, culminating in the design of the OWL Web Ontology Language [11], which is now a W3C recommendation. The OWL recommendation actually consists of three languages of increasing expressive power, namely OWL Lite, OWL DL and OWL Full. OWL Lite and OWL DL are, basically very expressive description logics; they are almost3 equivalent to the SHIF (D+) and SHOIN (D+) DLs. OWL Full is clearly undecidable because it does not impose restrictions on the use of transitive properties. Although the above DL languages are very expressive, they feature expressive limitations regarding their ability to represent vague and imprecise knowledge. As obvious, in order to make applications that use DLs able to cope with vague and uncertain information we have to extend them with a theory capable of representing this kind of information. One such important theory is fuzzy set theory.
In the current paper we extend the results obtained in [9] for fuzzy SI (f-SI) to the language SHIN , thus creating f-SHIN . SHIN extends SI [12] with number restrictions and role hierarchies [13]. Number restrictions give us the ability to restrict the number of objects that a certain object is related to by a specific relation. For example we can state that a car has exactly four wheels, writing Car ≡ Vehicle u ≥ 4hasWheel u ≤ 4hasWheel. But though this definition is correct, it faces many limitations, for example, in the context of image processing where several wheels of a car in an image might be hidden. Hence a detected object can belong to a concept like, ≥ 4hasWheel, only to a certain degree. On the other hand role hierarchies allow us to state sub-role/super-role relations, as for example the relation that holds between the hasChild and hasOffspring roles. Regarding expressive power, SHIN is more expressive than OWL-Lite, ignoring data-types. In the following we will introduce the syntax of f-SHIN and present a detailed procedure to reason with the extended language. 2
In this section we introduce the DL f-SHIN . As pointed out in the fuzzy DL literature [9,14], fuzzy extensions of DLs involve only the assertion of individuals to concepts and the semantics of the new language. Hence, as usual we have an alphabet of distinct concept names (C), role names (R) and individual names (I). f-SHIN -roles and f-SHIN -concepts are defined as follows: Definition 1. Let RN ∈ R be a role name, R an f-SHIN -role, C, D f-SHIN concepts. Valid f-SHIN -roles are defined by the abstract syntax: R ::= RN | R−. The inverse relation of roles is symmetric, and to avoid considering roles such as R−−, we define a function Inv, which returns the inverse of a role, more precisely Inv(R) := RN − if R = RN and Inv(R) := RN if R = RN −.
The set of f-SHIN concepts is the smallest set such that:
2. if C and D are f-SHIN -concepts, R is an f-SHIN -role, S a simple fSHIN -role [15] and p ∈ N, then (C t D), (C u D), (¬C), (∀R.C), (∃R.C), (≥ pS) and (≤ pS) are also f-SHIN concepts. 3 They also provide annotation properties, which Description Logics don’t.
A fuzzy T Box is a finite set of fuzzy concept axioms. Let A be a concept name, C a f-SHIN -concept. Fuzzy concept axioms of the form A v C are called fuzzy inclusion introductions; fuzzy concept axioms of the form A ≡ C are called fuzzy equivalence introductions. Note that how to deal with general fuzzy concept inclusions [12] still remains an open problem in fuzzy concept languages. A fuzzy RBox is a finite set of fuzzy role axioms. Fuzzy role axioms of the form Trans(RN ), where RN is a role name, are called fuzzy transitive role axioms; fuzzy role axioms of the form R v S are called fuzzy role inclusion axioms. We use the notation v* to denote the transitive-reflexive closure of v. A role R is called sub-role (super-role) of a role S if R v* S (S v* R). A fuzzy ABox is a finite set of fuzzy assertions. A fuzzy assertion [14] is of the form . ha : C./n i, h(a, b) : R./n i, where ./ stands for ≥, >, ≤ or < or a 6= b, for a, b ∈ I. Intuitively, a fuzzy assertion of the form ha : C ≥ ni means that the membership degree of a to the concept C is at least equal to n. We call assertions defined by ≥, > positive assertions, while those defined by ≤, < negative assertions [9]. A fuzzy knowledge base Σ is a triple hT , R, Ai, where T is a fuzzy T Box, R is a fuzzy RBox and A is a fuzzy ABox. A pair of assertions are called conjugated if they impose contradicting restrictions. For example, the pair of assertions hφ ≥ ni and hφ < mi, with n ≥ m contradict to each other. In the presence of role hierarchies one should also take into consideration possible subor super-roles when checking for such contradictions. For example the assertions h(a, b) : R ≥ 0.7i and h(a, b) : P ≤ 0.4i, with P v* R are conjugated. For a detailed description of the possible conjugated pairs the reader is referred to [14].
The semantics of fuzzy DLs are provided by a fuzzy interpretation [9, 14]. A
fuzzy interpretation is a pair I = hΔI , ·I i where the domain ΔI is a non-empty
set of objects and ·I is a fuzzy interpretation function, which maps an
individual name a to elements of aI ∈ ΔI and a concept name A (role name R) to
a membership function AI : ΔI → [
An fKD-SHIN -concept C is satisfiable iff there exists some fuzzy
interpretation I for which there is some a ∈ ΔI such that CI (a) = n, and n ∈ (0, 1].
A fuzzy interpretation I satisfies a fuzzy T Box T iff ∀a ∈ ΔI , AI (a) ≤ CI (a)
for each A v C in T and AI (a) = CI (a) for each A ≡ C in T . The
semantics of fuzzy inclusion axioms is the usual one found in fuzzy set theory [
Since a fuzzy ABox A might contain many positive assertions for the same individual (pair of individuals), without forming a contradiction, it is in our interest to compute what is the best lower and upper truth-value bounds of a fuzzy assertion. In [14] the concept of greatest lower bound of a fuzzy assertion w.r.t. Σ was defined as glb(Σ, φ) = sup{n : Σ |= hφ ≥ ni}, and that of a least upper bound as, lub(Σ, φ) = inf{n : Σ |= hφ ≤ ni}, where φ represents a crisp assertion of the form a : C or (a, b) : R. Observe that sup ∅ = 0 and inf ∅ = 1. A procedure to solve the best truth-value bound was provided in [14]. Such a procedure can also be used in our framework. 3
ABoxes Most of the inference services of fuzzy DLs, can be reduced to the problem of consistency checking for ABoxes [14]. Consistency is usually checked with tableaux algorithms that try to construct a fuzzy tableau for a fuzzy ABox A [9], which is an abstraction of a model of A [13]. The tableau has a forest-like structure with nodes representing the individuals that appear in A, and edges between nodes, which represent the relations that hold between two individuals. Each node is labelled with a set of triples of the form hD, ./, n i, which denote the concept, the type of inequality and the membership degree that the individual of the node has been asserted to belong to D. We call such triples membership triples. For triples of a single node, the concepts of conjugated, positive and negative triples can be defined in the obvious way. Since the expansion rules decompose the initial concept, the concepts that appear in triples are sub-concepts of the initial concept. Sub-concepts of a concept D are denoted by sub(D). The set of all sub-concepts that appear within an ABox is denoted by sub(A).
Since the De’Morgan laws are satisfied by the operations we use in the current
paper [
For all s, t ∈ S, C, E ∈ sub(A), and R ∈ RA, T satisfies: 1. If h¬C, ./, n i ∈ L(s), then hC, ./ −, 1 − ni ∈ L(s), 2. If hC u E, B, ni ∈ L(s), then hC, B, ni ∈ L(s) and hE, B, ni ∈ L(s), 3. If hC t E, C, ni ∈ L(s), then hC, C, ni ∈ L(s) and hE, C, ni ∈ L(s), 4. If hC t E, B, ni ∈ L(s), then hC, B, ni ∈ L(s) or hE, B, ni ∈ L(s), 5. If hC u E, C, ni ∈ L(s), then hC, C, ni ∈ L(s) or hE, C, ni ∈ L(s), 6. If h∀R.C, B, ni ∈ L(s) and hhs, ti, B0, n1i ∈ E(R) is conjugated with hhs, ti, B−, 1 − ni, then hC, B, ni ∈ L(t), 7. If h∃R.C, C, ni ∈ L(s) and hhs, ti, B, n1i ∈ E(R) is conjugated with hhs, ti, C, ni, then hC, C, ni ∈ L(t), 8. If h∃R.C, B, ni ∈ L(s), then there exists t ∈ S such that hhs, ti, B, ni ∈ E(R) and hC, B, ni ∈ L(t), 9. If h∀R.C, C, ni ∈ L(s), then there exists t ∈ S such that hhs, ti, C−, 1 − ni ∈ E(R) and hC, C, ni ∈ L(t), 10. If h∃S.C, C, ni ∈ L(s), and hhs, ti, B, n1i ∈ E(R) is conjugated with hhs, ti, C, ni, for some R v* S with Trans(R), then h∃R.C, C, ni ∈ L(t), 13. If hhs, ti, B, ni ∈ E(R) and R v* S then, hhs, ti, B, ni ∈ E(S), 14. If h≥ pR, B, ni ∈ L(x), then |{t ∈ S | hhs, ti, B, ni ∈ E(R)}| ≥ p, 15. If h≤ pR, C, ni ∈ L(x), then |{t ∈ S | hhs, ti, C−, 1 − ni ∈ E(R)}| ≥ p + 1, 16. If h≥ pR, C, ni ∈ L(x), then |{t ∈ S | hhs, ti, B, nii ∈ E(R)}| ≤ p − 1, conjugated with hhs, ti, C, ni, 17. If h≤ pR, B, ni ∈ L(x), then |{t ∈ S | hhs, ti, B0, nii ∈ E(R)}| ≤ p conjugated with hhs, ti, B−, 1 − ni, 18. There do not exist two conjugated triples in any label of any individual x ∈ S, 19. If ha : C./n i ∈ A, then hC, ./, n i ∈ L(V(a)), 20. If h(a, b) : R./n i ∈ A, then hhV(a), V(b)i, ./, n i ∈ E(R),
. 21. If a 6= b ∈ A, then V(a) 6= V(b) Properties 10 and 11 are a consequence of the fact that the supremum and infimum restrictions have to be preserved, when relations that have transitive sub-roles participate in negative existential and positive value restrictions. The membership degrees that the concepts are being propagated, in Properties 10 and 11, is the same as in the nodes that cause propagation. The proof of this property is quite technical and omitted here. Properties 14-17 are a direct consequence of the semantics of fuzzy number restrictions and the fact that from the De’ Morgan laws we can establish equivalences between negative and positive triples. Lemma 1. An fKD-SHIN -ABox A is consistent w.r.t. R iff there exists a fuzzy tableau for A w.r.t. R. 3.1
The Tableaux Algorithm In order to decide ABox consistency a procedure that constructs a fuzzy tableau for an fKD-SHIN ABox has to be determined. In the current section we will provide the technical details for constructing a correct tableaux algorithm. As pointed out in [13] algorithms that decide consistency of an ABox work on completion-forests rather than on completion-trees. This is because an ABox might contain several individuals with arbitrary roles connecting them. Such a forest is a collection of trees that correspond to the individuals in the ABox.
Nodes in the completion-forest are labelled with a set of triples L(x) (node
triples), which contain membership triples. More precisely we define L(x){hC, ./, n i},
where C ∈ sub(A) and n ∈ [
If nodes x and y are connected by an edge hx, yi, then y is called a successor of x and x is called a predecessor of y, ancestor is the transitive closure of predecessor. A node x is called an S − neighbour of a node x if for some R with if 1. h∃R.C, C, ni ∈ L(x), x is not indirectly blocked and 2. there is some P , with Trans(P ), and P v* R, x has a P -neighbour y with, h∃P.C, C, ni 6∈ L(y), and 3. h∗, C, ni is conjugated with the positive triple that connects x and y then L(y) → L(y) ∪ {h∃P.C, C, ni}, if 1. h≥ pR, B, ni ∈ L(x), x is not blocked, 2. there are no p R-neighbours y1, ..., yp connected to x with a triple hP ∗, B, ni, P v* R, 3. and yi 6= yj for 1 ≤ i < j ≤ p then create p new nodes y1, ..., yp, with L(hx, yii) = {hR, B, ni} and yi 6= yj for 1 ≤ i < j ≤ p if 1. h≤ pR, C, ni ∈ L(x), x is not blocked, then apply (≥B)-rule for the triple h≥ (p + 1)R, C−, 1 − ni if 1. h≤ pR, B, ni ∈ L(x), x is not indirectly blocked, 2. there are p + 1 R-neighbours y1, ..., yp+1 connected to x with a triple hP ∗, B0, nii, P v* R, 3. which is conjugated with hP ∗, B−, 1 − ni, and there are two of them y, z, with no y 6 =. z and 4. y is neither a root node nor an ancestor of z then 1. L(z) → L(z) ∪ L(y) and 2. if z is an ancestor of x then L(hz, xi) −→ L(hz, xi) ∪ Inv(L(hx, yi)) else L(hx, zi) −→ L(hx, zi) ∪ L(hx, yi) 3. L(hx, yi) −→ ∅ 4. Set u 6 =. z for all u with u 6 =. y if 1. h≥ pR, C, ni ∈ L(x), x is not indirectly blocked, then apply (≤B)-rule for the triple h≤ (p − 1)R, C−, 1 − ni if 1. h≤ pR, B, ni ∈ L(x), 2. there are p + 1 R-neighbours y1, ..., yp+1 connected to x with a triple hP ∗, B0, nii, P v* R, 3. conjugated with hP ∗, B−, 1 − ni, and there are two of them y, z, both root nodes, with no y 6 =. z then 1. L(z) → L(z) ∪ L(y) and 2. For all edges hy, wi: i. if the edge hz, wi does not exist, create it with L(hz, wi) = ∅ ii. L(hz, wi) −→ L(hz, wi) ∪ L(hy, wi) 3. For all edges hw, yi: i. if the edge hw, zi does not exist, create it with L(hw, zi) = ∅ ii. L(hw, zi) −→ L(hw, zi) ∪ L(hw, yi) 45.. SSeett uL (6=y.)z=fo∅r aanlldurewmitohveua6 =.ll yedagneds tsoet/fyro=m.zy (≥rC ) if 1. h≥ pR, C, ni ∈ L(x), then apply (≤rB )-rule for the triple h≤ (p − 1)R, C−, 1 − ni R v* S either y is a successor of x and L(hx, yi) = hR, ./, n i or y is a predecessor of x and L(hy, xi) = hInv(R), ./, n i. We then say that the edge triple connects x and y to a degree of n.
A node x is blocked iff it is not a root node and it is either directly or indirectly blocked. A node x is directly blocked iff none of its ancestors is blocked, and it has ancestors x0, y and y0 such that: (i) y is not a root node, (ii) x is a successor of x0 and y a successor of y0, (iii) L(x) = L(y) and L(x0) = L(y0) and, (iv) L(hx0, xi) = L(hy0, yi). In this case we say that y blocks x. A node y is indirectly blocked iff none of its ancestors is blocked, or it is a successor of a node x and L(hx, yi) = ∅.
The algorithm initializes a forest FA to contain a root node xi0, for each individual ai ∈ IA occurring in the ABox A and additionally {hCi, ./, n i}∪L(xi0), for each assertion of the form hai : Ci./n i in A, and an edge hx0, xj0i if A contains i an assertion h(ai, aj ) : Ri./n i, with {hRi, ./, n i}∪L(hxi0, xj0i) for each assertion of tahi e6=.foarjm∈hA(aia,nadj )t:hReri.e/lnatiioinn A=. .tAotbleasetmwpetyi.nFitAialiiszethtehne erxeplaatniodne d6=. baysrxepi0 e6=.atxedj0liyf applying the rules from Table 2. We use the notation R∗ to denote either the role R or the role returned by Inv(R), and the notation h∗, ./, n i, to denote any role that participates in such a triple.
For a node x, L(x) is said to contain a clash if it contains one of the following: (a) two conjugated pairs of triples, (b) one of the triples h⊥, ≥, ni, h>, ≤, ni, with n > 0, n < 1, h⊥, >, ni, h>, <, ni hC, <, 0i or hC, >, 1i, (c) some triple h≤ pR, B, ni ∈ L(x) and x has p + 1 R-neighbours y0, ..., yp, connected to x with a triple hP ∗, B0, nii, P v* R, which is conjugated with hP ∗, B−, 1 − ni, and yi 6= yj , for all 0 ≤ i < j ≤ p, or (d) some triple h≥ pR, C, ni ∈ L(x) and x has p R-neighbours y0, ..., yp−1, connected to x with a triple hP ∗, B, nii, P v* R, which is conjugated with hP ∗, C, ni, and yi 6= yj , for all 0 ≤ i < j ≤ p. A completionforest is clash-free if none of its nodes contains a clash, and it is complete if none of the expansion rules is applicable.
Lemma 2. Let A be an fKD-SHIN ABox and R a fuzzy RBox. Then
4
Much work has been carried out towards combining fuzzy logic and description logics during the last decade. The initial idea was presented by Yen in [19], where a structural subsumption algorithm was provided in order to perform reasoning. The DL language used was a sub-language of the basic DL ALC. Reasoning in fuzzy ALC was latter presented in [14], as well as in other approaches [20, 21], where an additional concept constructor, called membership manipulator was included in the extended language. In all these approaches tableaux decision procedures were presented for performing reasoning services. The operations used to interpret the concept constructors in all these approaches were the same ones as in our context. Approaches towards more expressive DLs, are presented in [16], where the DL is ALCQ, and in [17], where the language is SHOIN (D+). The former one also included fuzzy quantifiers, which is a new novel idea for fuzzy DLs. Unfortunately, in both these approaches only the semantics of the extended languages were provided and no reasoning algorithms. As far as we know the most expressive fuzzy DL presented till now, which also covers reasoning, is fKD-SI, appeared in [9]. The present work provides an extension of the latter one to an even more expressive DL, namely SHIN . 5
The importance and role that uncertainty, like vagueness (fuzziness) and
imprecision, plays in the Semantic web context, as well as to many applications
that use DLs to capture, represent and perform reasoning with domain
knowledge has been stressed many times in the literature [
This work is supported by the FP6 Network of Excellence EU project Knowledge Web (IST-2004-507482). 6. Kifer, M.: Requirements for an expressive rule language on the semantic web, W3C
Workshop on Rule Languages for Interoperability (2005) 7. Zhang, L., Yu, Y., Zhou, J., Lin, C., Yang, Y.: An enhanced model for searching in semantic portals. In: Int. WWW Conference Committee. (2005) 8. Bechhofer, S., Goble, C.: Description Logics and Multimedia - Applying Lessons Learnt from the GALEN Project. In: KRIMS 96 Workshop on Knowledge Representation for Interactive Multimedia Systems, ECAI 96, Budapest (1996) 9. Stoilos, G., Stamou, G., Tzouvaras, V., Pan, J., Horrocks, I.: A fuzzy description logic for multimedia knowledge representation, Proc. of the International Workshop on Multimedia and the Semantic Web (2005) 10. Lassila, O., R.Swick, R.: Resource Description Framework (RDF) Model and Syntax Specification – W3C Recommendation 22 February 1999. Technical report, World Wide Web Consortium (1999) 11. Bechhofer, S., van Harmelen, F., Hendler, J., Horrocks, I., McGuinness, D.L., Patel
Schneider, P.F., eds., L.A.S.: OWL Web Ontology Language Reference (2004) 12. Horrocks, I., Sattler, U.: A description logic with transitive and inverse roles and role hierarchies. Journal of Logic and Computation 9 (1999) 385–410 13. Horrocks, I., Sattler, U., Tobies, S.: Reasoning with Individuals for the Description Logic SHIQ. In MacAllester, D., ed.: CADE-2000. Number 1831 in LNAI, Springer-Verlag (2000) 482–496 14. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intelligence and Research 14 (2001) 137–166 15. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Proceedings of the 6th International Conference on Logic for Programming and Automated Reasoning (LPAR’99). Number 1705 in LNAI, SpringerVerlag (1999) 161–180 16. S´anchez, D., Tettamanzi, G.: Generalizing quantification in fuzzy description logic.
In: Proceedings 8th Fuzzy Days in Dortmund. (2004) 17. Straccia, U.: Towards a fuzzy description logic for the semantic web. In: Proceedings of the 2nd European Semantic Web Conference. (2005) 18. Hollunder, B., Nutt, W., Schmidt-Schaus, M.: Subsumption algorithms for concept description languages. In: European Conference on Artificial Intelligence. (1990) 348–353 19. Yen, J.: Generalising term subsumption languages to fuzzy logic. In: In Proc of the 12th Int. Joint Conf on Artificial Intelligence (IJCAI-91). (1991) 20. Tresp, C., Molitor, R.: A description logic for vague knowledge. In: In proc of the 13th European Conf. on Artificial Intelligence (ECAI-98). (1998) 21. H¨olldobler, S., Khang, T.D., St¨orr, H.P.: A fuzzy description logic with hedges as concept modifiers. In: Proceedings InTech/VJFuzzy’2002. (2002) 25–34 22. Horrocks, I., Sattler, U.: Ontology reasoning in the SHOQ(D) description logic.
In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. (2001) 23. Pan, J.Z.: Web Ontology Reasoning in the SHOQ(Dn) Description Logic. In: Carlos Areces and Maartin de Rijke, editors,Proceedings of the Methods for Modalities 2 (M4M-2). (2001) ILLC, University of Amsterdam.