Part II: Ontology


Sowa (2000) has this to say about the word "ontology" (p. 492):

The subject of ontology is the study of the categories of things that exist or may exist in some domain. The product of such a study, called an ontology, is a catalog of the types of things that are assumed to exist in a domain of interest D from the perspective of a person who uses a language L for the purpose of talking about D.

We start with some philosophical considerations. Then we treat, at length, some core ideas pertaining to ontology. Then we look at lambda expressions, which are essential for understanding the application of ontology to conceptual graphs, which we finally look at.

Philosophical considerations


Two kinds of types are involved in conceptual graphs:

Both of these concepts are very important when trying to understand conceptual graphs. Since they are both instances of the concept of "type", it is well to treat this concept in some detail before covering concept types and relation types.

Informal definition


Informally speaking, a type is a label (or, more simply, name) which we give to a group of entities with similar traits.

The entities with similar traits can be, e.g.:

Thus, when we say "groups of entities with similar traits", we are not only referring to groups of individuals (e.g., "Peter", "Paul", "Mary"), but precisely to groups of entities. An "entity" can be anything at all, even properties and abstract entities.

Types only exist in the abstract

Types always only exist in the abstract. For example, "John" is not a type but a name for a particular individual. (Which individual we are referring to by this name is dependent on context). But types always only exist in the abstract. Since a type is a name given to a group of entities, it can only exist in the abstract.

However, the converse does not hold, that everything that is abstract is a type. For example, "2" is an abstract entity: You cannot point to a concrete thing and say "This is the thing called '2'". But even though "2" is abstract, it is not a type. Rather, it is an instance of the type "NaturalNumber".

Example and counterexample of a type

Let us give some more examples. For example, "Animal" is a type. The group of entities which are given the label "Animal" includes inviduals such as the neighbor's dog and the bird in the tree outside the window.

However, "Fido" is not a type, but a name we give to an instance of the type "Dog".

Methods of definition


It is important to understand the ways in which a type can be defined. In this section, we list four such ways and then treat each of them in some detail.

Four types of definition

Types may be defined in a number of ways. Here are four of them:

By extension

When one defines a type by extension, one provides a list of references to all of the members of the group which the type defines. This method is only practical if the group of individuals is relatively small.

For example, the type JonesFamilyMember could comprise the individuals <Marilyn, Richard, Tom, Sue> if those were the names of the four members of the Jones family. The list <Marilyn, Richard, Tom, Sue> would be an extensional definition of the type JonesFamilyMember.

By intension

When defining a type by intension, one lists the properties that define which individuals belong to the group and which do not. It can also be done by giving a general rule for finding out whether a particular individual is a member of the group. This is only practical if one can define the type by rules using some language.

For example, the type "Mammal" could be defined by intension with the rule "A Mammal is an Animal that is sexual, bears offspring by pregnancy, and breastfeeds the young".

As an example of a type defined by a general rule, consider the type "OddNumber". An odd number is a number that cannot be divided by two. If one tries to divide it by 2, there will always be 1 left over. Therefore, a rule for defining "OddNumber" by intension could be "If one divides the number by 2 and then gets 1 left over, then the number is odd. Otherwise, the number is not odd."

By axioms

The third method, by axioms, is practical if we are dealing with an abstraction, e.g., mathematical entities. If you want to know more about axioms (not required), click here.

By reference to other types with differentiae

The fourth method, when defining "by reference to other types by differentiae", is practical for many things. For example, if we have defined the type "Professor", we can define the type "FullProfessor" like this: "A FullProfessor is a Professor with the differentiae that he or she has a permanent employment contract and has been approved competent at the level of a full professor".

This method is actually the one being used when defining type hierarchies of concept types. This is done mostly by defining new types in terms of conceptual graphs. These conceptual graphs, in turn, are based on other types already defined. The relations between the concepts, as well as the referents of the concepts, show the differentiae. Therefore, when defining concept types using conceptual graphs, we are defining "by reference to other types with differentiae".

When defining by intension, one usually also employs this method. It can be difficult to define a type completely without making any reference to other types. However, for some types it can be done, and therefore "by intension" was listed apart from "by reference to other types".

Axioms (optional)

This is optional material

The material on this page is optional and is provided for those who might be interested.


An axiom is a statement which says something which does not need to be proved. Or rather, something which we decide does not need to be proved. Something which we will assume to be true. We will then try to derive everything else from our axioms.

Example: Peano's axioms

Axioms are most useful in mathematics where we are dealing with abstractions. For example, the following five axioms (Peano's axioms) define the members of the set of natural numbers. Therefore, the type NaturalNumber can be defined by the following five axioms:

  1. 0 is a natural number.
  2. If a is a natural number then so is a+1.
  3. If you can prove something about a and that implies that you can prove it for a+1, and if you can prove the very same thing for 0, then will this hold for all natural numbers.
  4. If a+1=b+1 then a=b.
  5. You can not add 1 to a natural number to get 0.

Everything that does not satisfy these five axioms is not a natural number. Conversely, everything that satisfies these five axioms is a natural number. Thus these five axioms define the type NaturalNumber by axioms.

Core ontological ideas

In this chapter, we explore the core ideas in the realm of ontology.

A central notion is "type". Types are central to ontology, and ontology is crucial to conceptual graphs. In addition, treating types in their generality means that we only need to say a few specifics when we treat types in the context of conceptual graphs.

The chapter has the following subsections:

Type hierarchies

Types can be organized in type hierarchies. Type hierarchies are networks of types (called 'lattices') where the types are ordered by a partial order. This partial order is called the "subtype relation", and is symbolized by "≤". For example, "A ≤ B" means that the type A is a subtype of the type B. For example, "Bird ≤ Animal" means "Bird is a subtype of Animal".

Example in graphical form

An example of a type hierarchy could be as follows:

"Example of type-hierarchy"

The lattice-notation is to be read as follows:

Example in linear form (Prolog+CG form)

As already noted, in Module II of this course, we will be studying a system called Prolog+CG. This system has a mechanism for specifying a type hierarchy in linear form. The above could be written as follows in Prolog+CG:

Entity > Living, NonLiving.
Living > Person, Animal.
Person > god, HumanBeing.
Animal > Bird, Fish, Mammal.
Mammal > Elephant.

Subtype relation


To explain what the subtype relation means, let us offer this definition:

If A ≤ B (read as "A is a subtype of B"), then either:

For example, the type "Bird" is a subtype of the type "Animal". This is because "Bird" is a specialization of "Animal".


A specialization A ("Bird") of another type B ("Animal") includes all of the properties of the original type B ("Animal"), but adds some more restrictions. For example, a Bird not only has all of the characteristics of "Animal", it also has specialized characteristics such as

Thus, "Bird" is a specialization of "Animal", since it has all of the properties of "Animal", but adds further restrictions.


But A can also be identical to B. For example,

   Animal ≤ Animal


Proper subtype

If A is not B, but A ≤ B, then we are entitled to write

   A < B

, which means "A is a proper subtype of B". This is a way of saying that while A is not B; instead, A is a specialization of B.


The converse of the '≤' relation is the '≥' relation, called the "supertype relation". The two formulas

   A ≤ B    and     B ≥ A

are equivalent.

Proper supertype

If A is a supertype of B, i.e., A ≥ B, and A is not B, then we are entitled to write

   A > B

, which means "A is a proper supertype of B". The two formulas

   A < B     and     B > A

are equivalent.


It is also true that since

   SeaGull ≤ Bird    and    Bird ≤ Animal

, then it follows that

   SeaGull ≤ Animal

. (Note to the interested: This is because ≤ is a partial order and partial orders are transitive.)

Immediate subtype

An immediate subtype A of another type B is a subtype that has no other types in between A and B.

Because of the transitivity of the subtype relation, if A ≤ B, it does not follow that A is an immediate subtype of B: There may be other subtypes in between. It is useful to be able to speak about immediate subtypes, however, even if we have no notation to use for it.


Next, we discuss two special types, the universal type and the absurd type.

Entity and Absurdity


In every type hierarchy, the following two types always exist:

Universal type

The universal type is the type that is a supertype of every other type in the type hierarchy. Therefore, it says nothing about anything. Thus the label "Entity" can be used to refer to anything at all in the type hierarchy, since "Entity" is a supertype of everything else.

Absurd type

The absurd type is the type that is a subtype of every other type in the type hierarchy. Nothing is lower than "Absurdity" in the type hierarchy, and nothing exists which is an instance of "Absurdity".

Relationships among types

Everything is a subtype of Entity. In particular, Absurdity is a proper subtype of Entity:

   Entity > Absurdity

. Also, if "Bird" were in our type hierarchy, then it would be true that

   Absurdity < Bird

and also that

   Bird < Entity


Usefulness of the universal type

Especially the type Entity is useful, in that it can be used to represent any entity. For example the following graph,

   relation Poss(*x,*y) is
     [Animate: ?x]->(Has)->[Entity: ?y]

could be used to define the relation "Poss" or "possession". It says that "An animate thing has an entity", without specifying which kind of entity. The symbols '?x' and '?y' are place-holders for whatever is in the concepts that belong to the Poss relation. In fact, we have just seen an instance of a lambda expression, which will be defined later on.

Reason for the Absurdity type

The reason why there has to be an Absurdity element is that it makes for certain theoretical conveniences, which are deeply rooted in lattice theory and in partial order theory. We do not need to concern ourselves with the details in this course. We just accept that it is common practice to have an Absurdity element.

If you want to know a little bit more about partial orders (not required), click here.


An important concept related to the subtype relation ≤ is that of inheritance. We discuss this concept next.


Inheritance refers to properties. For example, if we have

   A ≤ B

then A has all the properties of B. A is said to inherit the properties of B. Thus, whatever can be said of B can also be said of A.

For example, since

   Mammal ≤ Animal

Mammal is said to inherit all the properties of Animal. Whatever is true of any instance of Animal is also true of any instance of Mammal. For example, all animals reproduce; therefore, a Mammal reproduces.

However, the converse does not hold. Not everything that can be said about a Mammal can be said about an Animal. For example, while it can be said that a Mammal breastfeeds its young, this cannot be said of every Animal.


The concept of inheritance can also be used to talk about types that are defined in terms of more than one supertype. We discuss this next.

Multiple inheritance

Introduction by example

A type may inherit from more than one type. For example, if we have the types "Cat" and "Cuddly", then we can form the type "CuddlyCat" by letting "CuddlyCat" be a subtype of both "Cat" and "Cuddly".

This can be visualized as in this lattice:

Another example

Here is another example:


Next, we give some examples of types, so that all of this may become less abstract and easier to understand.


Consider the following definitions:

   Entity > Animal, Person.
   Animal > Bird, Mammal.
   Mammal > Dog, Cat, Mouse.
   Person > Student, Employee.
   Employee > Professor, TeachingAssistant.
   Professor > FullProfessor, AssistantProfessor.

This tells us, among other things, that Animal is a subtype of Entity; that Bird and Mammal are both subtypes of Animal; that Dog, Cat, and Mouse are all subtypes of Mammal; and that FullProfessor and AssistantProfessor are subtypes of Professor.

This may be drawn as in the following type hierarchy:

Notice that although Animal and Person are both subtypes of Entity, this does not mean that there can be no definitions in between. For example, both could be included in the common supertype Animate. We just haven't specified this in the above example.

Partial orders (optional)

This is optional material

This page is optional material, provided for those who might be interested in fuller details. Feel free to skip ahead.

Introduction and example

A partial order is a relation between elements of a set. You already know an instance of a partial order, namely ≤ on numbers. For example:

The three axioms defining partial orders

In the following, think of a, b, and c as natural numbers. Then think of the following three axioms in terms of natural numbers:

  1. A partial order operator is reflexive:

    For all a: a ≤ a. (Reflexivity)

    For example, 2 ≤ 2.

  2. A partial order operator is transitive:

    For all a,b,c: If a ≤ b and b ≤ c, then a ≤ c. (Transitivity)

    For example, since 1 ≤ 2 and 2 ≤ 4, it is also true that 1 ≤ 4.

  3. A partial order operator is antisymmetric:

    For all a,b: If a ≤ b and a ≥ b, then a = b. (Antisymmetry)

    For example, since 2 ≤ 2 and 2 ≥ 2, it is also true that 2 = 2.

Application to subtype relation

All of these axioms are satisfied by every partial order. Since the subtype relation on a type hierarchy is a partial order, these axioms are also satisfied by the subtype relation.

For example, "Animate ≥ Bird", since Bird is a subtype of Animate. The three axioms above apply as follows:

  1. Reflexivity: "Bird ≤ Bird".
  2. Transitivity: Since "Penguin ≤ Bird" and "Bird ≤ Animal", it follows that "Penguin ≤ Animal".
  3. Antisymmetry: Since "Bird ≤ Bird" and "Bird ≥ Bird", it follows that "Bird = Bird".

Lambda expressions

Introduction to this chapter

This chapter gives a brief introduction to lambda expressions. After that, there will be a quiz. Then lambda expressions will be treated in their full generality in an optional section.

Table of contents for this chapter

The basics


You don't need to learn a whole lot about lambda expressions, even though much could be said. Therefore, we will just give some examples and a little explanation.

Where to get advanced information

If you want to know more, you are encouraged to read through this series of pages.

Introduction by means of an example

A lambda expression could look like this:

   [Person: ?x]<-(Agnt)<-[Sing]
   "A person, x, is singing"

Note the occurrence of '?x' in the space of the referent of the "Person" concept. This syntactic construct, '?x', is a placeholder for something else. We can fill this slot with the referent of another concept, as we shall see shortly.

Why is it called a 'lambda-expression'?

The reason this is called a lambda expression is that traditionally, such placeholders are written using the Greek letter lambda, or . Thus the above graph could be written:

   [Person: ]<-(Agnt)<-[Sing]
   "A person, , is singing"

We will mostly stick to the other notation, where we use ?x, ?y, ?z, ?a, ?b, etc. instead of , 1, 2, 3, 4, etc.

Monadic, dyadic, triadic, n-adic

A lambda expression can be monadic, as in the example above, where there is only one formal parameter. A lambda expression can also be dyadic or triadic, having two or three formal parameters respectively. In general, a lambda expressions can have n formal parameters and be n-adic.

Lambda expressions in use

Usage of lambda expressions

For defining relations

We use lambda expressions to stand for other things. Lambda expressions can be used to define new relations and concept types. For example:

   relation Singing(*x) is
     [Animate: ?x]<-(Agnt)<-[Sing]

Here, '*x' is the formal parameter of the relation. The formal parameter is the placeholder for what will be substituted into ?x's place when the relation is used. For example, the above relation might be used like this:

   [Person: John]<-(Singing)
   "John is singing"

When the relation is expanded to its defining lambda expression, the graph will look like this:

   [Person: John]<-([Animate: ?x]<-(Agnt)<-[Sing])
   "John is the formal parameter to the lambda expression 'An animate
    entity, ?x, is singing'"

This can then be unified to:

   [Person: John]<-(Agnt)<-[Sing]
   "John is singing"

For defining concept types

We can also define concept types using lambda expressions:

   type StarcrossedLover(*x) is
      [Lover: ?x]->(Attr)->[StarCrossed]

This concept type can then be used like this:

   [StarcrossedLover: {Romeo,Juliet}@2]<-(Agnt)<-[Take]-
      ->(Thme)->[Life: #their]
   "A pair of star-cross'd lovers take their life..."

The notation "{Romeo, Juliet}@2" will be explained later in the course, here and here. The notation "#their" will be explained here.


We see, then, that lambda expressions are used when defining relation types and concept types. Lambda expressions fill out the definition of relations and concept types, while allowing parts of the lambda expression to be filled with input from the outside.

Lambda expressions (optional)

This is optional material

This section is optional, and can be skipped. Use the navigation bar on the left to skip this section.


Introduction by means of an example

An example of a lambda expression could be:

   [Person: ?x]<-(Agnt)<-[Sing]
   "A person, x, is singing"

The symbol '?x' is a placeholder for something else that must come from outside of the lambda expression. This lambda expression could be used to define the concept "SingingPerson". For example, the following two would be equivalent:

   [SingingPerson: John]


   [ [Person: ?x]<-(Agnt)<-[Sing] : John ]

Notice how we can replace the concept type "SingingPerson" with the lambda expression and get exactly the same meaning.

The two main usages of lambda expressions

Lambda expressions are used in two situations:

  1. When defining new concept types, and
  2. When defining new relation types.

Since lambda expressions are the chief method of defining new concept types and new relation types in knowledge bases based on conceptual graphs, they are quite important. Next, we give some definitions.

Definition of lambda expressions

In the context of conceptual graph-theory, a lamda expression is a conceptual graph where zero or more of the referents in the concepts in the graph have been replaced with the Greek letter , pronounced "lambda".

If more than one referent has been replaced by a , the lambdas can be numbered such that no name-clash occurs, e.g., 1, 2, 3, etc.

In practice, we will often use other symbols, such as '?x', '?y', '?z', '?a', etc, since they are easier to write on a computer keyboard.


Example in graphical notation

As an example, the following is a conceptual graph for "some particular person is going to a particular city":

Example in linear notation

When writing this in linear notation, the symbols ?x, ?y, ?a, ?b, etc. can be used instead of 1, 2, etc. Thus the above graph could be written like this:

   [Person: ?x]<-(Agnt)<-[Go]->(Dest)->[City: ?y]
   "Someone, ?x, is going to a City, ?y"

Formal parameters


A lambda expression has an associated integer, n, called its valence, which counts the number of referents that have been replaced with lambdas. The number n may be 0 or higher. A lambda expression with n replacements is called an n-adic lambda expression. Again, the adjectives "monadic", "dyadic", and "triadic" are used to described 1-adic, 2-adic, and 3-adic lambda expressions.

Formal parameters

An n-adic lambda expression has n formal parameters numbered 1, 2, ..., n. The formal parameters of a lambda expression are the placeholders in the expression, referred to by s or expressions like ?x, ?y, ?z, etc.

Each formal parameter is a concept with a type and a referent. The type of the formal parameter is the type of the concept whose referent has been replaced with a .


For example, the following lambda expression can be used to define a relation, GoingToAalborg:

   relation GoingToAalborg(*x) is
      [Person: ?x]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]

Defining label, bound label

This definition has two parts:

  1. The name-part ("relation GoingToAalborg(*x) is"),
  2. The definition-part (the conceptual graph).

Note that in the name-part, the formal parameter is denoted by '*x', while in the definition-part, the formal parameter is denoted by '?x'. The label '*x' is called the defining label, while '?x' is called the bound label.

This notation is also used with coreference links.


One might use this relation as follows:

   [Professor: Alfred]<-(GoingToAalborg)
   "Alfred the professor is going to Aalborg"

Here, the concept

   [Professor: Alfred]

is the actual parameter to the lambda expression.

The relation GoingToAalborg can be expanded to its defining lambda expression:

   [Professor: Alfred]<-([Person: ?x]<-(Agnt)<-[Go]->(Dest)-
         ->[City: Aalborg])
   "Alfred the professor is going to Aalborg"

The formal parameter ("[Professor: Alfred]") can then be substituted for the lambda to which it refers:

   [Professor: Alfred]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]
   "Alfred is going to Aalborg"

Note that "Professor", which is the type of the concept of the actual parameter, is a subtype of "Person", which is the type of the concept which the actual parameter replaces. We see then, that the type of the actual parameter has to be a subtype of the type of the formal parameter. It need not be a proper subtype, as in this usage, but it must be a subtype.


Setting the stage for the definition

A lambda expression is, as we have seen, a conceptual graph where zero or more concepts have had their referents replaced by lambdas. Let us assume that we are dealing with a particular lambda expression e. Let us further assume that e has n concepts whose referents have been replaced by lambdas. Finally, let us call these concepts c1, c2, ..., cn.

Definition of signature

n-adic lambda expressions


  1. the type of c1 is t1,
  2. the type of c2 is t2,
  3. ...,
  4. and the type of cn is tn,

then the signature of e is:

   <t1,t2, ..., tn>

. This is simply a list of the types of the formal parameters.

Special case: 0-adic lambda expressions

Since a 0-adic lambda expression has no formal parameters, it has an empty signature, denoted by:




We have seen two examples of lambda expressions. Both can be used to define new relation types:

   relation GoingTo(*x,*y) is
     [Person: ?x]<-(Agnt)<-[Go]->(Dest)->[City: ?y]
   relation GoingToAalborg(*x) is
     [Person: ?x]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]

Note how the second one can be defined in terms of the first:

   relation GoingToAalborg(*x) is
     [Person: ?x]->(GoingTo)->[City: Aalborg]

The first lambda expression is a dyadic lambda expression with the signature <Person, City>. The second lambda expression is a monadic lambda expression with the signature <Person>.

Exercise: Can you explain why the arrows in this last definition of GoingToAalborg point the way they do?


Finally, we have a short quiz on the main points in this chapter.

Ontology in conceptual graphs


All of what has been said so far in this part has been preparing the ground for this chapter. We are now able to say with quite few words all that needs to be said about ontology in conceptual graphs. We start with concepts.

Concept types

What is a type hierarchy of concept types?

A type hierarchy T of concept types is a type hierarchy as defined in the section above. It only uses two methods of definition, detailed below.

Significance of type hierarchies

Every knowledge base must have a type hierarchy T, and every conceptual graph must have an associated type hierarchy T. Thus type hierarchies are quite important.

Two kinds of type labels

A type hierarchy T is a lattice (or 'network') of type labels. A type label in T can be one of two kinds:

A primitive type label is just a name in T that is placed somewhere in the type hierarchy using the subtype operator ("≤").

A defined type label is defined in terms of a monadic lambda expression.

Entity and absurdity

Every type hierarchy contains two primitive type labels, Entity and Absurdity. These have been explained above.

Defined type labels and their lambda expressions

A defined type label (defined in terms of a monadic lambda expression) is interchangeable with its definition. Thus, wherever you can write the type label of a defined type, you can substitute its lambda expression, and vice versa.

Concept types need not be type labels

Here is an important definition:

All concepts have a concept type. For any concept, its concept type is either a type label in T or a monadic lambda expression.

What we just said was a bit subtle. Notice that a concept type need not be a type label. It can also be a lambda expression which is not placed in the type hierarchy.

For example, the following conceptual graph is a concept whose type is not a type label:

  [ [PartyLight: ?x]->(Attr)->[Blue] : Blinky ]
  "Blinky, the blue partylight"

This means that we need not define all of our types in a type hierarchy: We can make ad-hoc types if necessary by inventing a monadic lambda expression.

However, giving a name to the monadic lambda expression and placing it in the type hiearchy can be a help if we are going to use the type more than once.

Why can't concept types be blank?

Notice also that now we have the explanation for what we said earlier, that while the referent of a concept can be blank, its type cannot be blank. For example, the following is not a well-formed concept:

   [ : John]

A concept type cannot be blank because a concept type must be either:

  1. a type label in T (in which case it is not blank), or
  2. a monadic lambda expression (in which case it cannot be blank because the blank conceptual graph is not a monadic lambda expression).

Examples of type labels

Example defining a new type label

An example of a type label that is defined in terms of a monadic lambda expression could be:

   type AAUStudent(*x) is
       [Student: ?x]<-(Agnt)<-[Attend]->(Thme)->[University: AAU]

This defines a new type in the type hierarchy. It can be used as a concept type like this:

   [AAUStudent: Romeo]
   "Romeo is an AAUStudent"

When expanding the lamda expression, the referent of the concept, Romeo, is put into the lambda expression in place of ?x. Thus, the above concept is equivalent to:

   [Student: Romeo]<-(Agnt)<-[Attend]->(Thme)->[University: AAU]
   "Romeo is a student who attends the university AAU"

Example not defining a new type label

Another example, which does not involve defining a new type label, is the following:

   [[Donkey: ?x]->(Agnt)->[Graze]: Benjamin]
   "Some donkey, ?x, is the agent of Graze.  ?x is Benjamin."

This is equivalent to:

   [Donkey: Benjamin]->(Agnt)->[Graze]
   "A donkey, Benjamin, is grazing."

A wonder for the interested

The very astute reader will have noticed that there is a conundrum here: If the formal parameter to the monadic lambda expression (in this example, "[Donkey: ?x]") has both a type and a referent, and if the actual parameter is "Benjamin", where does the actual parameter get its type from? It seems that the actual parameter only has a referent (or is a referent), an individual. So where does the type of the actual parameter come from?

The answer is that "Benjamin" is an individual in our catalog of individuals that is carried along in the implicit knowledge-base of which this conceptual graph is a part. In this catalog of individuals, "Benjamin" has been given a type. Thus the type of the actual parameter is implicit in the name (or locator) "Benjamin".

Relation types

What is a relation hierarchy

A relation hierarchy is a type hierarchy as defined above, with a number of restrictions, given below.

Two kinds of relation labels

The elements of a relation hierarchy R are called relation labels. Each relation label is either:


For every relation label in R, there is a positive integer n (greater than or equal to 1) called its valence. A relation label of valence n is said to be n-adic. Again, we give the names "monadic", "dyadic" and "triadic" to 1-adic, 2-adic, and 3-adic relation labels.

For example, "In" is a dyadic relation label:

   [Person: Romeo]->(In)->[City: Manchua]
   "Romeo is in Manchua"

The valence of a relation label is the number of arrows going to and from the relation.


A relation label has a signature, which is an ordered list


Each type in the signature corresponds to the concept type of a concept connected to the relation. The last arc, as you may recall, points away from the relation, and corresponds to the last type in the signature. All the other arcs point towards the relation.

For example, the signature of the Agnt (Agent) relation is


This means that the arc going from the relation (corresponding to the last type, "Animate") must point to a concept whose type is either Animate or a subtype of Animate.

Likewise, the arc pointing towards the relation (corresponding to the type "Act") must point to a concept whose type is either Act or a subtype of Act.

This can be seen in the following graph:

  [Sing]->(Agnt)->[Person: MarilynMonroe]
  "Sing has an agent, which is a person, who is Marilyn Monroe"
  "Marilyn Monroe sings"

Here, Person is a subtype of Animate, and Sing is a subtype of Act. Note how this matches the signature, and how the directions of the arcs are as they are because of the signature.

Primitive relation labels

A primitive relation label is a relation label that has no definition, but has been placed in the relation hierarchy by means of the "≤" subtype relation. However, a primitive relation label still has a signature, which must be specified as part of the definition of the primitive type label.

Thus a primitive type label is both defined and not defined. Its signature, and therefore its valence, must be defined, but its content or meaning need not be defined. Also, its position in the type hierarchy is fixed by means of the subtype-relation.

Defined relation labels

An n-adic defined relation label is the combination of:

  1. its name, and
  2. an n-adic lambda expression called its definition.

A defined relation label and its definition are interchangeable: Where one could be used, the other could be substituted.

For example, the relation "GoingTo" could be defined like this:

   relation GoingTo(*x,*y) is
      [Person: ?x]<-(Agnt)<-[Go]->(Dest)->[City: ?y]

and could be used like this:

   [Person: John]->(GoingTo)->[City: Aalborg]

Relations need not be relation labels

A relation need not be a relation label. It can also be a lambda expression with the same valence as the relation itself.

For example, instead of using the monadic relation label "IsBlue", we can use a lambda expression:

  [Person: John]<-([Object: ?x]->(Attr)->[Blue])

Relation labels with different valences are not subtypes of each other (optional)

This section is advanced material and is optional. Feel free to skip it.

The last constraint on a relation hierarchy R is the following: If:

  1. a is an n-adic relation label in R,
  2. b is an m-adic relation label in R, and
  3. n is not equal to m,

Then none of the following is true:

What this says is that only an n-adic relation label a can only be a subtype of an n-adic relation label b. That is, for a relation label a to be a subtype of relation label b, both must have the same valence.