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:

  • Objects
    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.
  • Concepts
    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.
  • Roles
    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.
yes
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.
yes

?- peter ?: male.
yes

?- peter ?: female.
no
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.
yes
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.
yes
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.
yes

?- peter ?: some(has_sister).
yes

?- peter ?: some(has_sister,human).
no
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 between humans? 

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

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.

Other Constructs

  • no(Role), no(Role,Concept)
    Is true if there doesn't exist any role filler for the given role and of the given Concept.
  • atleast(N,Role,Concept)
    Is an extension of the some(Role,Concept) construct and allows to specify the number of role-fillers.
  • atmost(N,Role,Concept)
    Is the extension of the no(Role,Concept) construct corresponding to atleast.
  • disjoint(Concept1,Concept2)
    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.
  • all(Role,Concept)
    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 property.

Extensions

  • Features
    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 but concepts.
  • the(Feature,Concept)
    Is true if the (one) role filler of Feature is of type Concept.
  • inv(Role)
    Defines a role to be the inverse of Role. Thus if peter :: has_sister : mary then mary ?: inv(has_sister) : peter is true.
  • comp(Role1,Role2)
    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).
  • trans(Role)
    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.
  • oneof(ListOfObjects)
    Defines a concept (which is a set of objects) that consists of the objects given in ListOfObjects.
  • Situations
    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
    Filters are properties of concepts or roles that are not inherited to subconcepts or -role.

ToDo

What's missing in this document?
  • Resolve references
  • Explain subsumption
Generated 11.2.2004 by Frank Bergmann