THEORY OF CONCEPTUAL GRAPHS

CHAPTER 5 – HIERARCHIES AND ORDER

Basic Ideas

Much of human reasoning has to do with the classification of objects, events, states, actions, etc.. Indeed so strong is the urge to classify everything that scientists often spend a lot of time and energy arguing about the precise definition of things. The classic example is that of whether Pluto is a planet or not.

Given that we have such a strong urge to classify everything we need a means of representing our classifications, or taxonomies. So far in our investigation of conceptual graphs we have not gone into any details about this but we have provided the means of representing the taxonomic groups to which entities, situations, etc. belong. This is done by the use of type and relation labels. In this chapter we will look at how labels are related and in the next chapter we will deal with the definition of labels.

Simple Hierarchies

The title of this section, simple hierarchies, reflects the fact that we will deal with hierarchies of all kinds whereas Sowa only dealt with hierarchies of type labels in his 1984 book (but corrected this omission in his 2000 book). There are two hierarchies to be considered: the type hierarchy and the relation hierarchy. Both of these hierarchies behave in the same way so that, apart from slight differences in terminology, the treatment of one is also the treatment of the other.

Type Hierarchy

The type hierarchy deals with natural types, those types to which entities intrinsically belong for their entire existence. As such it classifies entities according to the Aristotelian principles of necessary and sufficient conditions. We will deal with this in more detail in the next chapter.

Some examples of the relationships that are captured in the type hierarchy might be:

  1. All cats are mammals

  2. All dogs are mammals

  3. All burglaries are criminal acts

  4. All nightmares are dreams

  5. All states of melancholy are moods

The types in the type hierarchy can be “concrete” types such as cat, dog or rock or they can be more abstract types such as actions or states. It is important to notice that each phrase starts with “all”. The phrases above are stating universally quantified relationships. It is impossible for any cat or dog not to be a mammal or any burglary not to be a crime. On the other hand it is quite reasonable that some mammals are not cats but dogs or anything else not yet included in the list.

We represent the relationships above more formally with the “<” or “>” operators. If we want to say that all p are q we could say either of:

p < q or q > p

With these operators we get the following:

  1. CAT < MAMMAL or MAMMAL > CAT

  2. DOG < MAMMAL or MAMMAL > DOG

  3. BURGLARY < CRIME or CRIME > BURGLARY

  4. NIGHTMARE < DREAM or DREAM > NIGHTMARE

  5. MELANCHOLIA < MOOD or MOOD > MELANCHOLIA

For p < q or q > p we say that p is a subtype of q (in normal language p is a type of or kind of q) or we say that q is a supertype of p. Therefore the examples above can be read as:

  1. CAT is a subtype of MAMMAL or MAMMAL is a supertype of CAT

  2. DOG is a subtype of MAMMAL or MAMMAL is a supertype of DOG

  3. BURGLARY is a subtype of CRIME or CRIME is a supertype of BURGLARY

  4. NIGHTMARE is a subtype of DREAM or DREAM is a supertype of NIGHTMARE

  5. MELANCHOLIA is a subtype of MOOD or MOOD s a supertype of MELANCHOLIA

In each case of p < q we can say that all p are q and that q subsumes p. This is not true the other way round as can be seen from examples 1 and 2. We can also say that where p < r and q < r then p and q have a common supertype which is r.

Relation Hierarchy

Everything said about type hierarchies applies to relation hierarchies and we adopt the same notation for relation hierarchy relations. Some simple relations might be:

  1. MOTHER < PARENT

  2. FATHER < PARENT

  3. DIRECT_OBJECT < OBJECT

  4. IMMEDIATELY_TO_LEFT_OF < NEXT_TO

  5. IMMEDIATELY_PRECEDING < PRECEDING

A hierarchy of actors can also be constructed. Maybe such a hierarchy would be part of the relation hierarchy or maybe it would be a separate entity.

Representation Of Hierarchies

In addition to the linear form notation that we have used so far it is also common to represent hierarchies in a graphical form as in the following examples of part of a hierarchy:


Fig. 5.1



Fig. 5.2

The tree structure captures the hierarchical nature of relations and types and shows how types are related to their supertypes and those to their supertypes etc.. At each level of the tree any set of types with a common supertype, such as LEMUR, TARSIER... with supertype MAMMAL, all share the properties that define MAMMAL but differ from each other in ways that distinguish each from each other. Thus the LEMUR inherits the properties of MAMMAL. It also inherits the properties of ANIMAL and LIVING_THING. This chain is called the line of inheritance.

For the line of inheritance FELINE < MAMMAL < ANIMAL < LIVING_THING we can say the following:

An immediate subtype T2 of a type T1 will be distinguished from T1 by the acquisition of a single characteristic. Other subtypes of T1 will be distinguished from T2 by having different values of the distinguishing characteristic.

As one moves up the tree each type label is more general than those lower down. Therefore the higher up labels represent bigger sets of individuals. The set of individuals that a type label represents is called its denotation, δ. δMAMMAL is not {LEMUR, TARSIER,...} but is {#234, #3456, #4567,....} where each member of this set is a marker for a particular MAMMAL.

Kinds Of Hierarchy

The type hierarchy above has as its top node LIVING_THING. There is no reason to stop here because LIVING_THING is itself a subtype of PHYSICAL_OBJECT which is a subtype of ENTITY etc.. Taken to its extreme we finally reach the most general type of all, the supertype of every other type, which is called the universal type or top and is given the symbol T. The relation hierarchy also has a top symbol or universal relation which can also be given the symbol T but we also use the symbol R to distinguish it from the top of the type hierarchy.

Trees

Tree structures show how types are related to their supertypes and subtypes but the hierarchy above does not include all the subtypes of mammal that it could do. It does not show subtypes such as CARNIVOROUS_MAMMAL or HERBIVOROUS_MAMMAL. Therefore the hierarchy is wrongly constructed. What is needed may be something like the following:

Fig. 5.3

This certainly separates the carnivorous mammals from the herbivorous and we could have included the omnivorous as well. However, when we come to classify the reptiles, fish or amphibians we would have to make exactly the same distinctions. We may even want to classify mammals as placental mammals or monotremes before splitting them into carnivores and herbivores, giving us carnivorous placentals, herbivorous placentals, carnivorous monotremes and herbivorous monotremes in a tree such as:

Fig. 5.4

This is unnecessary duplication (especially since each type in the hierarchy also needs a definition, to be dealt with later) and we need a way of placing carnivores and herbivores into the type hierarchy in such a way that any carnivore, whether fish or mammal, can be shown as a subtype of both carnivore and mammal.

It seems that trees are not the way to capture type hierarchies and we need something more versatile.

Lattices

The following diagram illustrates how the hierarchical representation can be enhanced to solve the problems brought up in the previous section:


Fig. 5.5


This diagram shows that the types CARNIVORE and MAMMAL have common subtypes. Also the types HERBIVORE and MAMMAL have common subtypes. Any other type such as FISH or REPTILE could also have subtypes linked to CARNIVORE and HERBIVORE and in this way the duplication of these latter types and their definitions can be avoided. Any type that is a subtype of several types has multiple inheritance. In other words it is on several lines of inheritance. This is the way we would like it to be because when we learn that something is carnivorous we want to reuse our understanding of the word and not have to redefine it for every situation in which it might be used.

The idea of multiple inheritance can be taken to the extreme in a type hierarchy of the form known as a lattice. A general lattice may have a structure such as the following, taken from Sowa's 2000 book:

Fig 5.6 – A generalised type lattice.


T is the universal type and has immediate subtypes T1, T2 , T3 and T4. These in turn have immediate subtypes T5, T6, T7 and T8. Finally we reach the bottom with a node that we have called “A”. “A” is the absurd type and is the subtype of all types. We next need to look at a concrete example of such a lattice, again taken from Sowa's 2000 book:

Fig 5.7 – Type lattice of the elements.


This is a real type lattice that shows the relationships between the four elements and their supertypes. Matter has four subtypes, cold, dry, wet and hot matter. From these it is possible to construct the four elements by linking them in pairs to give the main properties of each type of matter, thus Earth is cold and dry, Fire is hot and dry, Water is cold and wet while air is hot and wet. New types can be created by combinations of two types to produce a common subtype.

There comes a point when the creation of a new subtype of two types produces a contradiction in the meaning of the new type. For instance a common subtype of Earth and Fire will be a subtype of cold and dry (Earth) and hot and dry (Fire). In other words such a type would be both cold and hot at the same time. This is clearly a contradiction and is “absurd”, hence the common subtype of Earth and Fire is the absurd type. Similarly for each other pair of elements any common subtype is the absurd type.

A Hidden Subtlety

The lattice in fig 5.7 contains a hidden problem. It is contrived so that, apart from the absurd type, all the common subtypes (the elements) are not absurd. The common subtypes that are included are all and only those that work. From a purely syntactic point of view, and as far as a machine is concerned, there is no reason why there should not be subtypes of HOT and COLD or DRY and WET.

In other words the subtypes of MATTER are of two kinds and a subtype of one kind can combine with either subtype of the other kind without producing a contradiction, but two subtypes of such a kind cannot have a common subtype. The diagram above, and the usual diagrams seen in the literature, do not show this. There is no information in the links as shown that COLD and HOT cannot share a subtype by COLD and DRY can.

There is therefore a need to find a way of showing that nonsensical subtypes cannot be formed. We will propose that where types are mutually exclusive that they are placed in a single tree separate from the rest of the hierarchy and that the types in such a tree cannot form common subtypes. For common subtypes to be allowed the types involved must come from different trees. The tops of each of these trees will be immediate subtypes of the universal type. With this we get the following lattice for the elements:

Fig. 5.8 - Alternative type lattice for the elements.


In this scheme, since MATTER_TEMPERATURE and MATTER_CONSISTENCY are immediately below the universal type, which has no properties, they must be fundamental types with just a single defining attribute or characteristic. Therefore they can form subtypes with other such types but the trees which emanate from them cannot form common subtypes because the placing of types on different branches from their common supertype is equivalent to saying that one type has a property and another does not.

Additional Terminology

We have dealt with some of the terminology surrounding hierarchies and now we will add some more common terms.

Given two types T1 and T2 which share a common supertype T, if T is the type at which the lines of inheritance of T1 and T2 meet then T is the least common supertype or supremum of T1 and T2. An example from fig. 5.8 is COLD is the supremum of EARTH and WATER.

Given two types T1 and T2 which share a common subtype T, if T is the type at which lines of inheritance diverge to T1 and T2 the T is the greatest common subtype or infimum of T1 and T2. An example from fig. 5.8 is AIR is the infimum of WET and HOT.

Order

So far all our examples and discussions about types have been about types of real-world entity such as things, states or situations. These are all things that exist in the universe. Such entities are first order entities and the logic of first order entities is first order logic, or FOL. It is possible to consider types themselves as entities and in this case their type labels become the referents of concepts. Such entities are second order entities and their types are second order types. Consider the two hierarchies below:


Fig. 5.9


The first hierarchy is a first order lattice which shows the types to which the particular elephant called Clyde belongs whilst the second hierarchy is a second order lattice which shows the type to which the type ELEPHANT belongs. There is no theoretical reason why there should not be third or higher order hierarchies but it becomes increasingly difficult to imagine them.

When dealing with types of different orders it is important to avoid certain paradoxes. The classic one is ”Clyde is an elephant, elephant is a species, therefore Clyde is a species”. Clyde can only conform to types that are supertypes in the hierarchy of the same order as Clyde's natural type.

Relations between concepts of different orders will themselves be of the appropriate order. More is said about this later.

Complex Hierarchies

The question arises about what is the universal type of hierarchies of different orders. Do the hierarchies of different orders share a common universal type or are their hierarchies completely separate entities? Even within the same order do different kinds of entity share the universal type of that order? One possible solution might be a hierarchy such as:


fig. 5.10

Here we have arranged for the immediate subtypes of T to be the universal types T0 – Tn-1 of n orders of types. We can say that, within any order, for any type t with supertype T that t < T We can also say that for any type tn+1 in the hierarchy of order n+1 there are types tn in the hierarchy of order n where tn :: tn+1. Thus we can say that Clyde is an ELEPHANT because Clyde :: ELEPHANT and we can say that ELEPHANT is a SPECIES because ELEPHANT :: SPECIES but we cannot say that Clyde therefore is a SPECIES because the conformity relation is not transitive. We can however say that Clyde being an ELEPHANT and ELEPHANT being an ENTITY that Clyde is an ENTITY.

Relation And Actor Hierarchy

Everything that we have said about the type hierarchy applies equally to the relation and actor hierarchy. Since actors are just a special case of relations we will include them in the discussion of relations. They have exactly the same kinds of structure and the terminology of type hierarchies applies to relation hierarchies as well.

Relations may be of different orders however in many cases it may be that the same relation can be used between concepts of different orders. This is best illustrated by way of examples:


Fig. 5.11

It is often said that orders cannot be mixed but the last example in fig 5.11 suggests that this is not necessarily the case. Nevertheless it is important that incorrect mixing of orders is avoided otherwise paradoxes can result. The following diagram shows how the top of the relation hierarchy might be organised:


Fig. 5.12

At the first level we have relations of orders 0, 1, 2..., shown by their universal relations R0, R1, R2... Below these, for each arity we have arities 0, 1, 2... shown by their universal relations R0,0, R0,1, R0,2.... Next are some examples of some of the kinds of relation. Notice that the PARENT relation is shown as both monadic and diadic. This is because many relations can be used in an incomplete form to specify a role without specifying all the entities that the individual is playing the role with respect to. It would probably be the case that missing attachments would be completed by a real system.



Return To Main Index

Previous Chapter

Next Chapter


Updated 14th December, 2006