General Concept Inclusion (GCIs) absorption algorithms have shown to play an important role in classical Description Logics (DLs) reasoners, as they allow to transform GCIs into simpler forms to which apply specialised inference rules, resulting in an important performance gain. In this work, we develop a rst absorption algorithm for fuzzy DLs, and evaluate it over some ontologies.
We recap here some basic de nitions we rely on. We refer the reader to e.g., [
Although fuzzy sets have a far greater expressive power than classical crisp sets, its usefulness depends critically on the capability to construct appropriate membership functions for various given concepts in di erent contexts. The problem of constructing meaningful membership functions is a di cult one and we refer the interested reader to, e.g., [13, Chapter 10]. However, one easy and typically satisfactory method to de ne the membership functions is to uniformly partition the range of, e.g., salary values (bounded by a minimum and maximum value), into 5 or 7 fuzzy sets using either trapezoidal functions (e.g., as illustrated on the left in Figure 2), or using triangular functions (as illustrated on the right in Figure 2). The latter is the more used one, as it has less parameters.
In Mathematical Fuzzy Logic [
A fuzzy interpretation I maps each atomic statement pi into [0; 1] and is then extended inductively to all statements: I( ^ ) = I( ) I( ), I( _ ) = I( ) I( ), I( ! ) = I( ) ) I( ), I(: ) = I( ), I(9x: (x)) = supy2 I I( (y)), I(8x: (x)) = infy2 I I( (y)), where I is the domain of I, and , , ), and are so-called t-norms, t-conorms, implication functions, and negation functions, respectively, which extend the Boolean conjunction, disjunction, implication, and negation, respectively, to the fuzzy case.
One usually distinguishes three di erent logics, namely Lukasiewicz, Godel,
and Product logics [
Lukasiewicz logic max( + 1; 0)
min( + ; 1) min(1
+ ; 1) 1
Godel logic min( ; ) max( ; ) (1 if
otherwise (1 if = 0 0 otherwise
Product logic Zadeh logic
min( ; ) + max( ; ) min(1; = ) max(1
; ) (1 if = 0 0 otherwise 1
We will also use an optional subscript X 2 fl; g; pg to identify the logic they refer to (e.g., g refers to Godel conjunction). Note that the operators for Zadeh logic, namely = min( ; ), = max( ; ), = 1 and ) = max(1 ; ), can be expressed in Lukasiewicz logic. More precisely, min( ; ) = l ( )l ); max( ; ) = 1 min(1 ; 1 ). Furthermore, the implication )kd = max(1 ; b) is called Kleene-Dienes implication (denoted )kd), while Zadeh implication (denoted )z) is the implication )z = 1 if ; 0 otherwise.
An r-implication is an implication function obtained as the residuum of a continuous t-norm i.e., ) = maxf j g. Note that Lukasiewicz, Godel and Product implications are r-implications, while Kleene-Dienes implication is not. Note also, that given an r-implication )r, we may also de ne its related negation r by means of )r 0 for every 2 [0; 1].
Some additional properties of truth combination functions are the following: Property = 0 = 1 = = =
) ( ( )) == ( ) ) = ( ) = ( ) = ) = ( ) = ( ) ( ) ( ) )
Lukasiewicz logic Godel Product Zadeh [23]
The notions of satis ability and logical consequence are de ned in the standard way, where a fuzzy interpretation I satis es a fuzzy statement h ; i or I is a model of h ; i, denoted as I j= h ; i, i I( ) .
Fuzzy ALC(D) basics. We recap here the fuzzy variant of the DL ALC(D) [
A fuzzy concrete domain or fuzzy datatype theory D = h D; Di consists of a datatype domain D and a mapping D that assigns to each data value an element of D, and to every n-ary datatype predicate d an n-ary fuzzy relation over D. We will restrict to unary datatypes as usual in fuzzy DLs. Therefore, D maps indeed each datatype predicate into a function from D to [0; 1]. Typical examples of datatype predicates d are the well known membership functions 4 The main reason is that any other t-norm can be obtained as a combination of them. d := ls(a; b) j rs(a; b) j tri(a; b; c) j trz(a; b; c; d) j where e.g., ls(a; b) is the left-shoulder membership function and v corresponds to the crisp set of data values that are greater or equal than the value v.
Now, let A be a set of concept names (also called atomic concepts), R be a set of role names. Each role is either an object property or a datatype property. The set of concepts are built from concept names A using connectives and quanti cation constructs over object properties R and datatype properties T , as described by the following syntactic rules: C ! > j ? j A j C1 u C2 j C1 t C2 j :C j C1 ! C2 j 9R:C j 8R:C j 9T:d j 8T:d : Each of the connectives u and t may also have a subscript X 2 fg; l; pg, ! may have a subscript X 2 fkd; g; l; p; zg and, : may have a subscript Y 2 fg; lg. The subscript indicates the fuzzy logic the connectives refers to (see Section 2). For instance, C u (D !l 8R::gE) is a concept (if a subscript is missing, then we assume that a a priori selected fuzzy logic X 2 fg; l; p; zg has been selected).
An ABox A consists of a nite set of assertions of the forms ha:C; i (meaning that a is an instance of C to degree at least ), or h(a; b):R; i (meaning that a and b are related via R with degree degree at least ), where a; b are individual names, C is a concept, R is a role name and 2 (0; 1] is a truth value.
A Terminological Box or TBox T is a nite set of GCIs and constraints. A General Concept Inclusion (GCI) axiom is of the form hC1 v C2; i (C1 is a sub-concept of C2 to degree at least ), where Ci is a concept and 2 (0; 1]. A primitive GCI is one of the form hA v C; i, where A is a concept name and C is a concept. In both cases above, v may also have a subscript X 2 fg; l; p; zg. Note that vkd is not allowed. A de nitional GCI is one of the form A = C. A is called the head of a primitive/de nitional axiom, and C is the body. A synonym GCI is of the form A = B, where both A and B are concept names. A generalised de nitional GCI is of the form C = D, where both C and D are concepts.
A constraint axiom has one of the following form (R is an object property): (i) domain(R; C), called domain restriction, that restricts the domain of role R to be concept C; (ii) range(R; C), called range restriction, that restricts the range of role R to be concept C; and (iii) disjoint(A; B), called disjoint restriction, that restricts the concept names A and B to be disjoint.
We may omit the truth degree of an axiom; in this case = 1 is assumed. A knowledge base is a pair K = hA; T i, where A is an ABox and T is a TBox.
Let T be a TBox consisting of de nitional GCIs only. Concept name A directly uses concept name B w.r.t. T , if A is the head of some axiom 2 T such that B occurs in the body of . Let uses be the transitive closure of the relation directly uses. T is acyclic if no concept name A is the head of more than one de nitional axiom in T and there is no concept name A such that A uses A.
Concerning the semantics, let us x a fuzzy logic X 2 fl; g; p; zg. Unlike classical DLs in which an interpretation I maps e.g., a concept C into a set of individuals CI I , i.e., I maps C into a function CI : I ! f0; 1g (either an individual belongs to the extension of C or does not belong to it), in fuzzy DLs, I maps C into a function CI : I ! [0; 1] and, thus, an individual belongs to the extension of C to some degree in [0; 1], i.e., CI is a fuzzy set. Speci cally, a fuzzy interpretation is a pair I = ( I ; I ) consisting of a nonempty (crisp) set
I (the domain) and of a fuzzy interpretation function I that assigns: (i) to each atomic concept A a function AI : I ! [0; 1]; (ii) to each object property R a function RI : I I ! [0; 1]; (iii) to each data type property T a function T I : I D ! [0; 1]; (iv) to each individual a an element aI 2 I ; and (v) to each concrete value v an element vI 2 D.
Now, a fuzzy interpretation function is extended to concepts as speci ed below (where x; y 2 I are elements of the domain), so for every concept C we get a function CI : I ! [0; 1]: ?I(x) = 0; >I(x) = 1; (C u D)I(x) = CI(x) DI(x); (C uX D)I(x) = CI(x) X DI(x); (C t D)I(x) = CI(x) DI(x); (C tX D)I(x) = CI(x) X DI(x); (:C)I(x) = CI(x); (:X C)I(x) = X CI(x); (C ! D)I(x) = CI(x) ) DI(x); (C !X D)I(x) = CI(x) )X DI(x); (8R:C)I(x) = infy2 I fRI(x; y) ) CI(y)g; (9R:C)I(x) = supy2 I fRI(x; y) (8T:d)I(x) = infy2 I fT I(x; y) ) dD(y)g; (9T:d)I(x) = supy2 I fT I(x; y) CI(y)g; dD(y)g : The satis ability of axioms is then de ned by the following conditions: (i) I satis es an axiom ha:C; i if CI (aI ) ; (ii) I satis es an axiom h(a; b):R; i if RI (aI ; bI ) ; (iii) I satis es an axiom hC v D; i if (C v D)I where5 (C v D)I = infx2 I fCI (x) ) DI (x)g; (iv) I satis es an axiom hC vX D; i if (C vX D)I where (C vX D)I = infx2 I fCI (x) )X DI (x)g; (v) I satis es an axiom domain(R; C) if I satis es 9R:> v C; (vi) I satis es an axiom range(R; C) if I satis es > v 8R:C; and (vii) I satis es an axiom disjoint(A; B) if I satis es A u B v?.
I is a model of a K = hA; T i i I satis es each axiom in K. We say that K entails and axiom , denoted K j= , if any model of K satis es . Two TBoxes T ; T 0 are equivalent (denoted T T 0) i they entail the same set of axioms. Example 1. We have built a fuzzy wine ontology6, according the FuzzyOWL 2 proposal7. One of the GCIs in there is of the form SparklingW ineu(9hasSugar: tri(32; 41; 50)) v DemiSecSparklingW ine where hasSugar is a datatype property whose values are measured in g=L.
Example 2. fuzzyDL-Learner 8 is a system that illustrates how one may learn graded GCIs. For instance, consider the case of hotel nding in a possible tourism application, where an ontology is used to describe the meaningful entities of the domain. Now, one may x a city, say Pisa, extract the characteristic of the hotels from Web sites and the graded hotel judgements of the users, e.g., from Trip 5 However, note that under Zadeh logic v is interpreted as )z and not as )kd. 6 http://www.straccia.info/software/FuzzyOWL/ontologies/FuzzyWine.1.0.owl 7 http://www.straccia.info/software/FuzzyOWL 8 http://straccia.info/software/FuzzyDL-Learner Advisor9 and asks about what characterises good hotels. Then one may learn that, e.g., h9hasP rice:High v GoodHotel; 0:569i where hasP rice is a datatype property whose values are measured in euros and the price concrete domain has been automatically fuzzi ed as illustrated below.
Now, it can be veri ed that for hotel verdi, whose room price is 105 euro, i.e., we have the assertion verdi:9hasP rice: =105 in the KB, we infer under Product logic that K j= hverdi:GoodHotel; 0:18i (note that 0:18 = 0:318 0:569, where 0:318 = tri(90; 112; 136)(105)). 3
The aim of our GCI absorption algorithm is to build from a TBox T an equivalent TBox T 0, which is the union of two disjoint sets of axioms Tg and Tu, where: 1. Tg is a set of GCIs of the form h> v C; i, 2. Tu = Tdef [ Tinc [ Tdr [ Tdisj [ Tsyn is the disjoint union of (a) Tdef , which is acyclic and contains de nitional GCIs only; (b) Tinc, which contains primitive GCIs only; (c) Tdr, which contains domain and range restrictions only; (d) Tdisj , which contains disjoint restrictions only; (e) Tsyn, which contains synonym GCIs only; and 3. there cannot be a concept name A that is a head of axioms in Tdef and Tinc. This partitioning makes it possible to apply lazy unfolding rules to axioms in Tu only. Now, we explain now how to compute it: Sections 3.1{3.4 present some auxiliary steps and then Section 3.5 describes the partitioning algorithm.
The transformations, if left unspeci ed, hold always, i.e., for connectives taken from the same logic; for the other cases, the semantics under which they hold is speci ed explicitly. The transformations are semantics preserving in the sense that they transform a TBox T into an equivalent TBox T 0. 3.1
The procedure Simplif y(C) performs the following concept simpli cations, replacing the left-hand part with the right-hand part. The simpli cations are applied recursively considering that u; t are n-ary, commutative and associative: 9 http://www.tripadvisor.com 3.2
The following axioms can safely be removed, since they are trivially satis ed: 1. h? v C; i, hC v >; i and C = C 2. hC v C; i, for any r-implication and Zadeh implication
n 3. hui=1Ci v A; li, if some Ci is A and v is an r-implication or Zadeh implication.
n 4. hA v ti=1Ci; li, if some Ci is A and v is an r-implication or Zadeh implication. 3.3
Basic Role Absorption. As in the classical case, > v 8R:C and 9R:> v C
are equivalent to range(R; C) and domain(R; C), respectively, so we have the
following rules [
Lukasiewicz and Zadeh logics. !G :D), for 3.4
In the following, C; Ci are concepts, A; Aj are atomic concepts.
Classical Case. For classical DLs we have the following de nitions: GCI transformation rules.
n (CT1) Replace C v ui=1Ci with C v Ci, for i
n (CT2) Replace ti=1Ci v C with Ci v C, for i n; n.
Primitive concept absorption. (CA0) A v C is a possible absorbable GCI, A is the de ned atom and A v C is its rewriting; (CA1) C v :A is a possible absorbable GCI, A is the de ned atom and A v :C; is its rewriting (CA2) If some Cj is a negated atomic concept :A, then C v tin=1Ci is a possible n absorbable GCI, A is the de ned atom and A v :C t ti=1;i6=j Ci is its rewriting; n (CA3) If some Cj is an atomic concept A, then ui=1Ci v C is a possible absorbable n
GCI, A is the de ned atom and A v C t ti=1;i6=j :Ci is its rewriting. Fuzzy Case. For fuzzy DLs we have the following de nitions instead: GCI transformation rules. (FT1) Replace hC v C1 uG : : : uG Cn; i with hC v Ci; i, for i (FT2) Replace hC1 tG : : : tG Cn v C; i with hCi v C; i, for i n; n.
Primitive concept absorption. (FA0) hA v C; i is a possible absorbable GCI, A is the de ned atom and hA v C; i is its rewriting; (FA1) C v :lA is a possible absorbable GCI, A is the de ned atom and A v :lC is its rewriting; (FA2.1) If some Cj is an atomic concept :A, then hC v tin=1Ci; i is a possible abn sorbable GCI, A is the de ned atom and hA v :C t ti=1;i6=j Ci; i is its rewriting (for Lukasiewicz or Zadeh implication and Lukasiewicz t-conorm); (FA2.2) hC v A ! D; i is a possible absorbable GCI, A is the de ned atom and hA v C ! D; i is its rewriting (if v and ! are interpreted as the same r-implication); n (FA3) If some Cj is an atomic concept A, then hui=1Ci v C; i is a possible absorbable GCI, A is the de ned atom and hA v (uin=1;i6=j Ci) ! C; i is its rewriting (for v and ! interpreted as the residuum of u, or for the triple hvz; ug; !gi, or hu; !i is the pair hug; !gi, = 1 and v is any r-implication or Zadeh implication). n (FA4) If some Cj is an atomic concept A, then hti=1Ci v C; i is a possible absorbable GCI, A is the de ned atom and hA v (uin=1;i6=j :Ci) ! C; i is its rewriting (for Lukasiewicz logic). 1. Simplify the GCIs in T using the concept simpli cations in Section 3.1 2. Remove redundant GCIs (Section 3.2) 3. Initialise Tg = Tdef = Tinc = Tdr = Tdisj = Tsyn = ; 4. Remove any range and domain axiom in T and add it to Tdr 5. Remove any disjointness axiom in T and add it to Tdisj 6. Remove any synonym axiom in T and add it to Tsyn 7. For any axiom 2 T do (a) if is of the form hC v D; i then add to Tg (b) if is of the form C = D then add C v D and D v C to Tg Phase B: Apply iteratively the following steps to axioms 2 Tg, in the order speci ed below, until none of these steps can be applied to any axiom in Tg. As soon as one step is applied once, we restart Phase B.
Redundant GCIs removal. Remove redundant GCIs (Section 3.2). GCI transformations. If a GCI transformation rule can be applied to an axiom 2 Tg, remove from Tg and add the obtained GCIs to Tg (see Section 3.4). Synonym absorption. If for 2 Tg there is 0 2 Tg [ Tinc such that f ; 0g is fA v B; B v Ag with A; B atomic, then remove ; 0 from the sets they are in and add A = B to Tsyn.
Primitive concept absorption. If there is a possible absorbable GCI 2 Tg, with de ned atom A, A not de ned in Tdef , then remove from Tg and add the rewriting of to Tinc (see Section 3.4).
De nition absorption. If for some 2 Tg there is 0 2 Tg [Tinc such that f ; 0g is fA v C; C v Ag with A atomic, C non-atomic, A not de ned in Tdef or Tinc n f 0g, and Tdef [ fA = Cg acyclic, then remove ; 0 from the sets they are in and add A = C to Tdef .
Role absorption. If for some 2 Tg a role absorption rule can be applied (Section 3.3), then remove from Tg and move the obtained restriction to Tdr. Phase C: Once none of the above steps in Phase B can be applied anymore, replace any axiom hC v D; i 2 Tg with an equivalent axiom h> v E; i where E is the simpli cation of C ! D using the rules in Section 3.1, and return the TBox partitioning hTu; Tgi, where Tu = Tdef [ Tinc [ Tdr [ Tdisj [ Tsyn.
Example 3. Consider the TBox T = fA = B t C; A v Dg. Then, it can be veri ed that under classical and Zadeh logic, the absorbed TBox is given by Tinc = fC v A; B v A; A v D; A v B t Cg and Tg = Tdef = Tdisj = Tsyn = Tdr = ;, while under Lukasiewicz logic the absorbed TBox is given by Tinc = fA v D; A v B t C; B v (:C u A)g and Tg = Tdef = Tdisj = Tsyn = Tdr = ;. Note that Example 3 also illustrates the usefulness of giving less priority to the \de nition absorption" step. Usually, this step has highest priority. In that case Example 3 will not be absorbed completely. Also, the example shows that a non acyclic KB may be transformed into an acyclic one and, thus, avoiding the undecidability problem mentioned in the introduction.
We have implemented the fuzzy GCI absorption algorithm in our fuzzyDL reasoner, under Zadeh, Lukasiewicz, and classical logics.
To evaluate our algorithm, we have selected 7 well-known classical ontologies: Economy, LUBM, FBbt XP, GALEN doctored (or GALEN-d), NCI, process and Transportation. We also have considered the fuzzy wine ontology, FuzzyWine.
Table 1 shows some information for each ontology:the expressivity (column
expressivity) and the number of classes (classes), primitive GCIs (subsCls),
de nitional GCIs (equivCls), domain restrictions (domain), range restrictions
(range), disjoint restrictions, (disjoint) and general concept inclusions (GCIs).
These ontologies were loaded in fuzzyDL using a parser translating from OWL 2
into fuzzyDL syntax [
Table 2 shows the same values after running the absorption algorithm for each of the three fuzzy logics considered. We include the semantics of the reasoner (column semantics with values z for Zadeh, l for Lukasiewicz and c for classical), the number of classes (classes), the sizes of Tinc; Tdef ; Tsyn; Tdr; Tdisj ; Tg and the running time (in seconds) of the absorption algorithm. The tests run under Mac OS X, 10.7.5, Mac Pro 2 x 3 GHz Dual-Core Intel Xeon, 9GB Ram.
Note that that the number of disjoint constraints is constant, as our absorption algorithm does not create new restrictions of these type. yet
The results are similar for the 3 semantics. In terms of running time, the algorithm behaves similarly in the 3 cases. In terms of number of absorbed axioms, the semantics is not signi cant in Economy, NCI and Transportation, there are small di erences in FBbt XP, GALEN-d, LUBM, FuzzyWine and process.
In all the considered ontologies Tg is empty, which is important from a reasoning e ectiveness point of view. For instance, the reasoner gets out of memory when solving a simple query in some ontologies such as GALEN-d, but using the absorbed one our preliminary subsumption tests perform in a fraction of second. We have worked out a rst absorption algorithm for fuzzy DLs. We implemented it into the fuzzyDL reasoner and evaluated it over some ontologies, and our preliminary results seem to be very encouraging.
There are several directions for future research related to optimised fuzzy DL reasoning that need to be addressed: Absorption. We plan to investigate and evaluate more deeply our absorption algorithm considering more ontologies and several heuristics (e.g., which atom to select for absorption and concept name unfolding) such as those reported in the literature [1, 11, 12, 18{20, 24].
Classi cation. While we already have implemented in fuzzyDL all fuzzy lazy
unfolding rules related to absorbed TBoxes and preliminary subsumption
tests perform in a fraction of second, a non trivial optimised fuzzy classi
cation algorithm in the style of e.g., [
Instance retrieval. Other important tasks to optimise are instance
checking, i.e., determining the best entailment degree bed(K; a:C) = supf j
K j= ha:C; ig, and instance retrieval, i.e., determining the set ans(K; C) =
fha; i j = bed(K; a:C)g [