This paper describes fuzzy CARIN, a knowledge representation language combining fuzzy description logics with Horn Rules. Fuzzy CARIN integrates the management of fuzzy logic into the non recursive CARIN system. It provides a sound and complete algorithm for representing and reasoning about fuzzy ALCN R extended with non recursive Horn Rules. Such an extension is most useful in realistic applications dealing with uncertainty and imprecision, such as multimedia processing and medical applications. Additionally, it provides the ability of answering to union of conjunctive queries, which is a novelty not previously addressed by fuzzy DL systems.
Over the last two decades fragments of first order logic, called
Description Logics (DLs) [
DLs main asset, their class-based knowledge representation
formalism, also sets a limit to their expressive power as they are
incapable of providing complex descriptions about role predicates.
Expressive DLs such as SHOIQ are incapable of expressing even a
simple composition between roles. For this reason, as visualized
in the Semantic Web stack diagram, there is a need for
integrating DLs with rules. A natural choice for such integration would be
classes of rule languages originating from logic programming and
non-monotonic reasoning [
In [
Though CARIN offers great expressivity in order to represent a fragment of our universe, it is incapable of encoding knowledge with some degree of uncertainty and imprecision. Uncertainty emerges from our lack of knowledge about a certain fact e.g. we assume that the black dot in the background of a picture is a lion, while imprecision refers to the intrinsic inability to strictly classify a fact or a state of an object e.g. a half-empty glass of water can neither be characterized as full, nor as empty.
Fuzzy logic is a means to represent knowledge containing
uncertainty and imprecision. Several systems, such as fuzzy fKD ¡
ALC [
A fuzzy CARIN knowledge base K is composed of three components K = hT ; H; Ai, a DL terminology component T also called a TBox, a Horn Rules component H and a ground facts component A also called an ABox. In the syntax that we propose, we consider that fuzziness exists only in the ground facts component. For example we can assert that the weather is cloudy with a degree greater or equal than 0.6: (weather : cloudy) ¸ 0:6.
Fuzzy CARIN’s primitive elements are a set of individuals I, an alphabet of concept names C, role names R and ordinary predicate names Q. Elements of I represent the objects in our universe, while C and R correspond to unary and binary fuzzy relationships between individuals in I. Elements of Q correspond to relationships, between individuals, of any arity.
Terminological component in fuzzy CARIN: The fuzzy CARIN terminological component T has the same syntax as the crisp. Complex concepts are built from concept and role names using the constructors of ALCN R as described in Equation 1 where A is a concept name, C and D are concept descriptions, R is a role definition described in Equation 2 and P1; : : : ; Pk are role names in R.
C; D ¡!
A j > j ? j C u D j C t D j :C j 8R:C j 9R:C j (¸ m R) j (· m R)
R := P1 u : : : u Pk
The TBox contains a set of concept definitions of the form A := D and concept inclusions of the form C v D
Horn Rules in fuzzy CARIN: The Horn rule component H of a fuzzy CARIN knowledge base K contains a set of Horn Rules that are logical sentences of the form:
p1(X1) ^ : : : ^ pk(Xk) ) q(Y ) where X1; ¢ ¢ ¢ ; Xk and Y are tuples of variables and individuals and p1; ¢ ¢ ¢ pk may be concept names, roles or ordinary predicates (1) (2) (3) while q is always an ordinary predicate. The antecedent of a Horn rule is called its body and the consequent is called its head.
Ground fact component: The ground fact component A of a fuzzy CARIN knowledge base contains a set of fuzzy assertions as shown in table 1:
Intuitively a fuzzy assertion of the form (weather : cloudy) > 0:5 means that the weather is cloudy with a degree at least equal to 0:5. We call assertions defined by >; > positive assertions, denoted with B, while those defined by 6; < negative assertions, denoted with C. ./ stands for any type of inequality. In fuzzy CARIN, we consider only positive role assertion, since negative assertions would imply the existence of role negation and disjunction of roles in ALCN R. According to [15] this is an undecidable problem. Similarly for ordinary predicates we use only positive assertions since negation cannot be expressed in simple Horn Rules. Finally negative concept assertions can be reduced to positive ones with the use of negation i.e. (a : C) < n can be reduced to (a : :C) ¸ 1 ¡ n.
The reasoning procedure of Fuzzy Carin is performed in two steps. In the first step a set of completion forests corresponding to the DL part of our Knowledge Base is created. The creation of each completion forest, such as presented in Figure 1, is based on the tableaux algorithm for fuzzy-ALCN R.
In the second step a graph matching algorithm populates the
ordinary predicates in the head of each Horn Rule. This procedure can
be easily done by a graph matching algorithm since in our knowledge
we have only acyclic Horn Rules. We consider that an individual a
is an instance of a concept C to some degree greater or equal than
n, if in each completion forest F we have that C(a) ¸ n0, where
n0 ¸ n. The same will apply for a pair of individuals and a Role, or
a tuple of individuals and an Ordinary Predicate, only that in the last
case we consider that the knowledge deriving from each completion
forest F is augmented according to the Horn Rules.
In this paper we have presented the fuzzy Carin algorithm which
combines fuzzy DLs with Horn Rules. The expressiveness of our
algorithm could be proved most useful especially in multimedia
applications. A more detailed description of our algorithm along with
some examples is described in [