Introduction to Description Logics
This introduction is neither complete nor was it meant for use
with SiteC. I will change it soon. However, it sufficiently explains
the basic concepts of description logics.
This chapter is meant to give a brief and informal introduction
into description logics (DL) and to explain how DL can be used for
natural language processing purposes. Please note that we do not
treat the formal properties of DL and that we..
The Basic Elements
Description Logic historically evolved from a combination of frame
based systems ([?]) and predicate logic [?]. Its main purpose was
to overcome some problems of the frame based systems and to provide
a clean and efficient formalism to represent knowledge.
The main idea of DL is to describe the world in terms of "properties"
or "constraints" that specific "individuals" have to satisfy. The
following basic entities were introduced:
correspond to single "objects" of the real world such as a specific
person, a table or a telephone. The main properties of an object
are that it can be distinguished from other objects and that it
can be referred to by a name. DL objects correspond to "individual
constants" in predicate logic.
can be seen as "classes of objects". Concepts have two functions:
on the one hand they describe a set of objects, on the other hand
they determine "properties" of objects. For example the class
"table" is supposed to describe the set of all table (-objects)
in this world. On the other hand it determines some properities
of a table such as having four legs, a surface and that you can
lay something on top of a table. DL concepts correspond to one-place
predicates in predicate logic and to classes in frame-based systems.
represent relationships between objects. For example the role
lays_on may determine the relationship between a book
and a table, where the book lays on the table. Roles also can
be applied to concepts. However they do not describe the relationship
between the classes (concepts), but describe the properties of
those objects that are member of that classes.
?- peter :: human and male.
Figure 1: Peter is a human and male
Concepts and Objects
Let us consider the very first example in figure 1. First we recognize
the strange ?- characters on the the left side. These characters
represent the "prompt" of the underlying Prolog system, that is used
for the implementation of our DL system. Also the full stop .
at the end of the line and the yes in the next line are part
of the Prolog syntax. We only have to know that all lines in Prolog
have to be terminated by the full stop and that the yes indicates
that the execution was successful.
Furthermore we can recognize the "double kolon" operator ::,
that has the object peter on its left side, and that has
some properties human and male on the right side. In effect
in our DL sytax the double kolon operator introduces a new object
and assigns it the properties on the right side of the operator.
As a result the DL system internally creates a new entry for the
object and somehow stores the properties of the object. One can
compare this for example with a database system, where the user
can add entries into database table and can retreive these entries
using some kind of query language. Correspondingly it is possible
to query the propertiy of our DL database using the specific DL
query operators as shown in figure 2.
?- peter ?: human.
?- peter ?: male.
?- peter ?: female.
Figure 2: Peter is a human and male
Actually we forgot to define the terms human, male
and female for our example. These terms can either be seen
as properties (the property of being a human or being male) or as
classes of objects (the class of all objects that are human or male).
In fact it doesn't matter which interpretation we adopt here because
they are equivalent.
human :< ctop.
male :< ctop.
female :< ctop.
woman := human and female.
man := human and male.
Figure 3: Humans and genders
So let's now consider example figure 3 where these terms are defined:
First we see two new operators :< and := which
are called "primitive"- and "defined" concept introduction operator
respectively. We will explain the difference later in this chapter.
Both operators take a concept name on their left side, the description
of the concept on the right side and introduce the new concept to
the interal database.
The second new element is the predefined concept ctop.
This concept refers to the top of the concept hierarchy (therefore
its name) and is used as the root of all concepts in the DL system.
Figure 2 shows a graphical representation of this little hierarchy
,that also includes the bottom element cbot.
These two elements together with some formal properties of concepts
and objects that will not be discussed in this chapter are responsible
for the fact that the concpept hierarchy can be seen as an algebra?.
This property is of great importance to the overall system design,
because it provides some kind of formal rigidity that helps to understand
the behaviour of the system and that also prooved to be helpful
for an efficient implementation.
So what is the difference between primitive and defined concepts?
To explaint this subtle difference let's get back to the definition
of a concept as a class of objects. To say it formally, the difference
is that objects can belong to defined concept by means of their
properties, while they can never belong to a primitive class without
explicitely beeing to to.
In our very first example we saw that that peter is both
a human and male. So does he belong to the class man? The
answer is yes, because the class of all men is defined by having
the two properties of being human and being male and it is a defined
concept. Thus the query in figure 4 is successful. If the class
man would have been defined as a primitive concept, the
answer would have been no.
?- peter ?< man.
Figure 4: Peter is a man
Roles and Role Constructs
So far we introduced the notion of object and concept. With these
two elements we can define large class hierarchies of objects and
we could use them im practice for example to classify relatives or
for the management and retreival of internet URLs (that is actually
not such a bad idea, as the first applications show). However we are
leacking the possibility to deal with relations between objects.
?- peter :: has_sister : mary.
Figure 5: Peter has a sister called mary
Let's consider example figure 5. The new kolon operator :<
together with its two arguments on the left and right side syntactily
just behaves like a concept name such as male. It introduces
a relationship between the object peter and his sister
mary using the role (relationship) has_sister.
The entire construct is read like "peter has a sister called mary"
and is formally captured in first order logic by a two-place predicate
such as has_sister(peter,mary). Graphically we can despict
the peter - mary relationship by a line (edge) between the two objects
such as in figure 6.
?- peter ?: has_sister : mary.
?- peter ?: some(has_sister).
?- peter ?: some(has_sister,human).
Figure 6: Queries concerning peter and his sister
So what are the conclusions that we can draw from the fact peter
has a sister? Certainly we can ask whether peter has a sister called
mary as despicted in figure 6 and certainly the system will reply
positively. However in practice we often don't know the name of
a role-filler or we are not interested in the particular role filler
but in some of its properties. For this reason the some(Role)
and some(Role,Concept) construct were introduced, that
exactly satisfy these needs. some(Role) is true, if there
is some filler at all, while some(Role,Concept) is true
if there exists a filler that is of type Concept.
But why doesn't succeed the third query in example figure 6? The
reason for this is that we do not know anything about mary
except for the fact that she is the sister of peter. But
how can we conclude that sister- and brothership is only defined
has_relative :< rtop and
range(human) and domain(human).
has_parent :< has_relative.
has_sibling :< has_relative.
has_sister :< has_sibling and range(female).
has_brother :< has_sibling and range(male).
Figure 7: Relationships between humans
Figure 7 introduces the definition of a role-hierarchy concerning
relationships between humans. We can identify the top of the role
hierarchy rtop, and two new constructs named range(Concept)
and domain(Concept). Range restricts the filler of a role
the Concept, and domain restricts the object from which the role
starts. With this role hierarchy, the third query in example figure
6 would have been positive, because the has_relative role
already restricts the range of has_sister to human.
father :< ctop.
man and some(has_child) => father.
Figure 8: Rules
The last construct that we need to build real DL systems is the "rule".
Let's consider example figure 8. In the second line we see a new operator
=> which introduces a new rule to the system, with a condition
part on the left side and the conclusion part on the right side of
the operator. The meaning of the rule can be read like "if an object
satisfies the condition on the left side, then it has the properties
of the right side". So the rule can be read like "if an object is
male and has atleast one child, then it is a father".
The Zoo of Constructs
The family of description logic system consists of many members that
in particular differ with respect to the constructs they provide.
In the last sections we introduced some elementary constructs that
will be used in the next section to provide an example from the area
of natural language processing. Below some more constructs are listed
with a brief explanation of their semantics. However not all of these
constructs will be found with all existing description logic systems.
- no(Role), no(Role,Concept)
Is true if there doesn't exist any role filler for the given role
and of the given Concept.
Is an extension of the some(Role,Concept) construct and allows
to specify the number of role-fillers.
Is the extension of the no(Role,Concept) construct corresponding
Defines the Concept1 and Concept2 to be disjoint, t.i. to disallow
objects (and concepts) to be defined as both, Concept1 and Concept2.
Concept1 and Concept2 exclude each other.
Defines all role-fillers to be of type Concept. When used in object
tells this construct forces a "propagation" of constraints from
one object to other objects, thus makeing the inference process
to be spread over entire groups of objects, which may be an undesired
Features are roles that have atmost one role filler. Features
are handled more efficiently in general then general roles.
- Term-Valued Features
TVFs are some kind of roles that do not have objects as arguments
Is true if the (one) role filler of Feature is of type Concept.
Defines a role to be the inverse of Role. Thus if peter
:: has_sister : mary then mary ?: inv(has_sister)
: peter is true.
Defines a role to be the composition of Role1 and Role2. For example
the role has_grandfather can be defined as comp(has_parent,has_father).
Defines a role by the transitive close of Role. For example the
role has_ancestor can be defined as trans(has_parent).
- Concept Disjunction (Concept1 or Concept2)
Disjunction can be defined in correspondence to conjunction. However
disjunction is difficult to treat computationally.
Defines a concept (which is a set of objects) that consists of
the objects given in ListOfObjects.
Situations are "spaces for objects" that are separated from each
other. Thus the same object (referred to by its name) in one situation
may have different (or even contadictory) properties than the
same object in another situation.
Filters are properties of concepts or roles that are not inherited
to subconcepts or -role.
What's missing in this document?
- Resolve references
- Explain subsumption