Description Logic

From TinyCog
(Redirected from Description Logics)
Jump to: navigation, search

This is a quick start and tutorial for Description Logic in the context of TinyCog. This introduction is neither complete nor does it represent the wealth of research done in this field. The purpose is to allow students to develop simple ontologies for TinyCog domains. For a more rigorous introduction to DL please see for example this Description Logic Primer.


Basic Elements

Description Logic historically evolved as a combination of frame based systems and First Order 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 "ontologies" that are composed of "objects", "concepts" (= classes of objects) and "roles" (relationships between objects):

Object

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.

Concept

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 properties 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.

Role

Roles represent relationships between objects. For example the role "on_top" may determine the relationship between a book and a table, where the book lays on top of 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 an instance of a class.

?- peter :: human and male.
yes

Figure 1: Peter is an object of class 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 retrieval of internet URLs (that is actually not such a bad idea, as the first applications show). However we are lacking 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.

Rules

The last construct that we need to build real DL systems is the "rule". </pre> father :< ctop. man and some(has_child) => father. </pre> Figure 8: Rules

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.
  • 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.

Description Logic and Scenes

In TinyCog, Description Logic formulas are stored in Scenes. Scenes represent real-world 3D scenes or "mental scenes" from psychology.

Situation Calculus

However, in the context of DL, scenes correspond very much to situations from [Situation Calculus]. Scenes provide an inheritance mechanism, so that DL formulas held in one scene are also visible in following scenes, unless specifically overwritten.

Special Scenes

TinyCog defines a special scene:

  • tbox: This is the default scene for all DL formulas, unless otherwise specified. By using "tbox" as the base of other scenes, the DL ontology is automatically available in these scenes.

Comparison and References

  • [Brachman 1977] initially introduced Description Logics as a formalization of
  • [Minsky 1974] "frames".
  • This "TinyDL" DL implementation is based on experiences gathered during the work with the "FLEX" System ([Quantz et al. 1995]).

Implementation Status

There are currently two available for demonstrating/testing the DL subsystem:

  • DL Prim-Family] is a demo to tests the basic ("primitive") subsumption functionality of the TinyCog DL implementation. TinyCog implements these tests starting with V0.0.1.
  • Family is a demo to test the advanced ("defined concept") subsumption functionalities of TinyCog. TinyCog 0.0.1 implements some, but not all of these tests.