This course is about a technology called 'conceptual graphs'. This technology can be used to represent knowledge and meaning in a computer. The technology consists of a "formal language" in which we can express knowledge and meaning. In this course, we will be learning about that language, but not much about any particular implementation. We will be drawing graphs with pencil and paper where necessary, and we will learn to read conceptual graphs.
A simple conceptual graph could look like this:
It represents the phrase "Conceptual graphs". This is a very simple example, but conceptual graphs can scale to almost any size to express almost anything which we want to say.
A knowledge base, so far as conceptual graph-theory is concerned, consists of a number of things:
Knowledge bases are the means to representing knowledge and meaning. We will not be making reference to any particular knowledge base in this course. Instead, we will simply assume that all the graphs we draw are part of some larger knowledge-base which has the elements listed above.
Conceptual graphs as such are only a part of the overall theory of conceptual graphs: Other parts include:
We will get back to all of these in due course. For now, it is important to bear this goal in mind: That we will be able to represent knowledge and meaning in a computer.
Next, we note some practical points before going on to the main material.
Noting a number of practical points will help you navigate through the pages of this course.
Firstly, at the bottom of each page, you will find a number of links to help you navigate the document-structure. For example, some pages will have links to "Prev"(ious), "Up", and "Next".
The "Prev" and "Next" links take you to the previous and following pages in the document flow respectively. The "Up" link takes you to the page once upwards in the hierarchy of pages.
For example, following the "Up" link from this page will take you to the table of contents. You will always be able to get to the table of contents if you follow "Up"-links far enough.
Secondly, at a number of points through the course material, there will be optional parts. You can read these parts if you want to, or skip them if you like; they are not required reading. If you do decide to follow the links to the optional parts, there will be a "Back" link at the bottom of the page which will take you back to where you left the main flow of the material.
A number of reference materials are available in Part VI. They are:
The page with sample conceptual relations contains a list of some of the most commonly used relations (such as "Agnt" (Agent)). You will need to refer to this page often, so one suggestion would be to bookmark it. There will also be links to this page from the graphs that have relations defined on this page.
This course is quite liberally interlinked with hyperlinks. One particular kind of hyperlink is to the glossary. You will be able to identify the glossary-hyperlinks by hovering the mouse over the link, then looking at the status line of the browser. If it says "Glossary", you know it is a link to the glossary. You can then decide whether you want to follow the link or not.
The glossary of symbols defines some of the symbols used in the course, with links to the relevant parts of the material.
Another kind of hyperlink is to other parts of the course. You can identify these in the same way as for the glossary-definitions, except that the URL in the status-line will say "Module_I/XXXX.php", where "XXXX" is a four- or five-digit number.
At the end of most chapters, there will be a short quiz to help you reflect on the main points of the chapter. The quizzes will be quite easy, and sometimes you may even think that the questions are insulting your intelligence. If this is the case, please be forgiving.
The quizzes will be multiple-choice. You will be given a question, and then you have to choose from a number of answers. Only one answer will be correct. When you have selected the right answer to all questions, simply press the "Check answers" button at the bottom of the page. This will take you to a new page that tells you how many you got right, as well as the answer to, and an explanation for, any question which you got wrong.
The answers given in the quizzes will be logged. However, no-one will be able to trace the link between you and the answers. Thus, even though the answers are logged, the answers given are anonymous.
But now, let us get going. We start by looking at conceptual graphs, the most central aspect of the overall theory of conceptual graphs.
A conceptual graph is a graph or network of two kinds of nodes:
The nodes have arcs between them. The arcs are always directed, i.e., they have a direction. This is indicated by an arrow head.
Now we will see some examples.
An example of a conceptual graph could be:
This is a graph representing the phrase "Conceptual graphs". The notation used is called the "linear notation" because it is drawn using linear text. There is another way to draw conceptual graphs, namely the graphical notation:
In the graphical notation, concepts are drawn as rectangles while relations are drawn as circles (or ovals). In the linear notation, concepts have [square brackets] around them, while relations have (parentheses).
A conceptual graph is a bipartite graph. This simply means that there are no arcs between a concept and another concept, and no arcs between a relation and another relation. All arcs either go from a concept to a relation or from a relation to a concept.
The term "bipartite" means "partitioned in two". The nodes of a bipartite graph can be divided into two nonempty sets A and B, with two different kinds of nodes. All arcs of a bipartite graph then connect exactly one node from A and one node from B. Therefore, all arcs cross the boundary between the two sets of the two kinds of nodes.
Conceptual graphs are bipartite in that it has two kinds of nodes, concepts and relations, and every arc "crosses the border" between the two sets of the two kinds of nodes. That is, any arc connects a concept with a relation.
An arc is said to belong to a relation but to be attached to a concept. This is useful terminology, and will be used throughout the remainder of these notes.
For example, in the graph
[Say]->(Thme)->[Phrase: "Nightie-night"] "Say 'Nightie-night'"the two arcs belong to the relation "(Thme)", while they are attached to the two concepts "[Say]" and "[Phrase: "Nightie-night"]".
A conceptual graph may have concepts that are not linked to any relation. Thus concepts can stand alone without being linked to any relation.
For example, the following conceptual graph is well-formed:
This conceptual graph means "There is a God". Of course, this may or may not be true.
While it is possible for concepts not to have any arcs attached to themselves, this is not possible for relations. A relation must have at least one arc that belongs to it.
For example, the following is not a well-formed conceptual graph:
(On) Ill-formed conceptual graph
However, the following is a well-formed conceptual graph, since the relation (In) has at least one arc that belongs to it (in fact, it has two):
[Bird]->(In)->[SycamoreTree] Well-formed conceptual graph
It means "There is a bird in a sycamore tree".
Three kinds of conceptual graph are given distinguished names:
A blankThe blank conceptual graph is the graph that says nothing about anything, and which therefore is true about everything.
[God] A singleton
[Bird]->(In)->[SycamoreTree] "A bird is in a sycamore tree"
[Cat]->(On)->[Mat] "A cat is on a mat"
The following two graphs are equivalent:
[A]->(R)->[B] and [B]<-(R)<-[A]
Thus the direction of the arrows on the page is determined by the position of the concept types within the signature, and is otherwise immaterial.
There is also special standard language associated with the direction of an arrow. This language can be divided into two groups:
For each group, it also matters whether we are reading an arrow that points towards or away from a relation.
This can be shown as in the following two tables. The first is when reading from left to right and the second is when reading from right to left:
[concept]<-(relation) "is a"
[concept]->(relation) "has a"
(relation)->[Concept] "which is"
[Fat]<-(Attr)<-[Cat]Fat "is an" attribute "of" Cat
[Cat]->(Attr)->[Fat]Cat "has an" attribute "which is" Fat.
[concept]<-(relation) "which is"
(relation)<-[Concept] "has a"
(relation)->[Concept] "is a"
[Fat]<-(Attr)<-[Cat]Cat "has an" attribute "which is" Fat.
[Cat]->(Attr)->[Fat]Fat "is an" attribute "of" Cat.
Now we need examples. Try to follow these examples in the two tables above. The following graph can be read in two ways:
[Bird]<-(Agnt)<-[Sing] "A bird is singing"
can be read:
It is important that you learn to read arrows. Thus it is recommended that you go back and try to match each arrow with each of the four expressions in the two ways of reading the graph.
[Person: John]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg] "John is going to Aalborg"
This technique does not work very well with relations which are prepositions, such as On and In. In this case, it is better simply to say the preposition, preceded by a form of the verb 'to be', as in:
[Book]->(On)->[Table] "A book is on a table"
This concludes our discussion of how to read arrows. It is important that you practice reading arrows until you master the technique.
If you wish, you can print out this page and have it lying beside you as a reference.
On this page, we define what a concept is.
A concept is always made up of two entities:
The concept is drawn like this:
where the type and the referent are separated by a colon. For example:
[Person: John] "There exists a person whose name is John"
Here, "Person" is the concept type, and "John" is the referent.
[Bus] "There exists a bus"
The type can never be blank.
We now discuss concept types in a little more detail.
The concept type of a concept says what kind of concept we are dealing with. For example, these could all be types in our ontology:
Entity > Bus, Person, Tree, Location, Act, Animal. Person > Student, Employee. Employee > Professor. Tree > SycamoreTree. Location > City. Act > Go, Leave, Eat, Catch. Animal > Cat, Dog, Bird, Mouse.
A type is a label or name we give to a group of entities with similar traits. If we can categorize a number of individuals (e.g., "John", "Alfred", "Mary") in the same group (e.g., "Person"), then we can call the name of the group, together with the definition of the group, a "type".
A type can be a subtype of another type. For example, in the above ontology, "Cat" is a subtype of "Animal", while "Student" is a subtype of "Person". In the list of examples above, subtypes are listed after their supertype and a '>'.
The concepts "subtype" and "supertype" will become clearer if we look at the above examples of types in a diagram such as this:
"Some of the above types, drawn in a lattice"
Here, we see that the "subtypes" are below their "supertypes". The Entity and Absurdity types will be explained later.
Look at the lattice of types from the previous page:
"Types in a lattice"
An individual from any of the groups that these types define can be the referent of a concept. For example:
This concept says that "There exists a person whose name is John". "Person" is the type, while "John" is the referent. In other words, "John" is the particular individual (or referent) which we are referring to, and he is an instance of the type "Person".
These are also examples of types and referents:
[Cat: Felix] [Mouse: Eeek] [Cat: Garfield] [Dog: Odie] [Animal: Odie] [Employee: Jon] [Professor: Alfred]
For example, in the concept:
"Professor" is the type and "Alfred" is the referent.
In Module II of this series of courses on conceptual graphs, we will learn about a system called Prolog+CG. Later on in this course, we will learn what an ontology is. In Prolog+CG, the above individuals could be specified, as part of an ontology, like this:
Cat = Felix, Garfield. Mouse = Eeek. Dog = Odie. Employee = Jon. Professor = Alfred.
The referent may be left blank, as in the following conceptual graph:
Here, the concept "[Bus]" has no referent. The concept simply means "A bus" or "There is a bus".
Anytime the referent is left blank, it means "There is an X" or simply "An X", where "X" is the concept type.
The whole conceptual graph means"There is a bus which has a destination (Dest) which is a City, the referent of which is Aalborg."
It will be remembered that a conceptual graph is a bipartite graph with two different kinds of nodes:
We have already discussed concept nodes. Now we discuss the other kind, relation nodes.
If concepts can be likened to bricks in a wall, then relations can be likened to the mortar that bonds the bricks together. Relations relate concepts to each other in all of the different ways that concepts can be related.
For example, in the following graph,
[Cat]->(On)->[Mat] "A cat is on a mat"
the concepts "Cat" and "Mat" are related by the relation node "On". The concepts "Cat" and "Mat" are the "bricks" of the graph, while "On" is the "mortar" that binds the concepts together.
With this informal introduction in mind, we now gives some definitions that are useful when thinking and talking about relations.
This page merely gives an overview of the three kinds of ideas associated with relations, namely:
In later sections, we treat each idea more fully.
All relations have a relation type. This tells us the kind of relation we are dealing with. While concepts have both a type and a referent, relations only have a type.
The valence of a relation is the number of arcs that belong to it. This number, or the valence of a relation, is always greater than or equal to 1.
A relation type also has a signature. The signature of a relation is a list of the concept types involved in the relation.
In the following, we discuss relation type first, then valence, and then signatures.
A relation type is simply a name which we give to the relation. It tells us what kind of relation we are dealing with. The type also determines the valence of the relation and its signature. That is, the type of the relation determines the number of arcs that belong to it, and the types of the concepts that are attached to those arcs.
For example, all of these are relation types:
A very important relation is "Agnt" or "agent". It is used again and again when we draw conceptual graphs. It relates an act (such as "Sing") and an animate being (such as "Bird") which performs the act. We will use this relation in the next example.
Consider this conceptual graph:
This conceptual graph says:"There is a bird which is the agent of Sing. This same bird is in a sycamore tree".
Or, put into better English:"A bird is singing in a sycamore tree".
This graph has two relations, "Agnt" (agent) and "In" (in). The relation type of "Agnt" is "Agnt". Its valence is 2, and it relates an act with an animate being. The relation type of "In" is "In". Its valence is 2, and it relates two physical entities in a spatial relationship.
There are techniques for specifying both tense and aspect, but we will not be looking at them in this course. The only exception is that we will note that to specify past, we can use the "Past" relation:
(Past)->[Situation: [Sing]->(Agnt)->[Bird]->(In)->[SycamoreTree] ]
This graph has a sub-graph that is embedded in a concept (the graph that is the referent of the concept "Situation"). This structure will be explained later.
To summarize: A relation is defined by its relation type. The relation type not only gives a name to the relation, it also determines the other two ideas associated with relations, valence and signature. We discuss valence next.
The valence n of a relation is the number of arcs that belong to it. For any relation type t, the valence n is always constant. That is, the number of arcs that belong to a relation is always the same.
For example, the number of arcs that belong to the relation "Dest" (destination) is always two, and the number of arcs that belong to the relation "Agnt" (agent) is also always two. This is because the valence of "Dest" is 2, and the valence of "Agnt" is also 2:
[Person: John]<-(Agnt)<-[Go]->(Dest)->[City: Aalborg]
This conceptual graph can be paraphrased as:"A Person, John, is the agent of 'Go', and the destination of Go is a City, which is Aalborg".
In better English:"John is going to Aalborg".
A relation with valence n is said to be n-adic. For example, a relation with valence 5 is said to be 5-adic. The first three valences have special names:
Examples of monadic expressions include "Past" (past tense) and "Psbl" (possibility):
(Past)->[Situation: [Bird]<-(Agnt)<-[Sing] ] "In the past, there was this situation: A bird was singing."
(Psbl)->[Situation: [Bird]<-(Agnt)<-[Sing] ] "It is possible that a bird is singing."
We have already seen numerous example of dyadic relations. For example, "Agnt" (agent), "Dest" (destination), and "On".
An example of a triadic relation could be "Betw" or 'between'.
[Person: Julia]<-(Betw)- <-1-[Person: Tom] <-2-[Person: Brad] "Julia is between Tom and Brad" Example of a triadic relation.
Note the special multi-line notation. We will discuss this in detail later.
To summarize: the valence of a relation is determined by the relation type, is always constant, and signifies the number of arcs that belong to the relation.
An n-adic conceptual relation r is said to have a signature of n concept types. The signature is written as <t1, t2, ..., tn>, where t1, t2, t3, etc. are the types of the concepts that are attached to each of the arcs that belong to r.
For example, the relation type
is said to have the signature
This is because the first arc that belongs to Agnt must be attached to a concept whose concept type is either Act or a subtype of Act. The second arc must be attached to a concept whose concept type is either Animate or a subtype of Animate:
Here, "Sing" is a subtype of "Act", which is the first concept in the signature. "Bird" is a subtype of "Animate", which is the second concept in the signature.
The order of the concept types in the signature of a relation is significant and is always constant. This is important for the direction of the arrows on the arcs, as we shall see next.
There is a convention for the direction of the arrows that go to and from a conceptual relation. In fact, this convention is part of the definition of a conceptual relation. The convention is this: For a conceptual relation with n arcs, the first n-1 arcs point towards the relation, while the last, or n-th, arc points away.
How do we know which is the last arc? In other words, how do we know which arc should point away from the relation while all the rest should point towards the relation?
The answer is simple: We know from the signature of the relation. For example, the signature for the "Agnt" relation is:
Therefore, the arc that points away must be the one that points to the concept denoting the animate entity:
Thus when we say "first arc", "second arc", "third arc", etc., we are referring to their position within the signature.
It follows from the definition that in the special case where there is only one arc (a monadic relation), the arc must point away from the relation. In the case of two arcs, the first points towards the relation while the second points away. For example:
(Past)->[Situation: [Sing]->(Agnt)->[Bird] ] "A bird sang"
Notice how for the monadic relation (Past), the arc points away, while for the dyadic relation (Agnt), the first points towards the relation while the other points away.
Relations may have more than two arcs (have valence greater than 2). The next section discusses notation for dealing with this.
In the linear notation, if a relation has more than two arcs, the arcs may be represented as in this example:
[Person: Julia]<-(Betw)- <-1-[Person: Tom] <-2-[Person: Brad] "Julia is between Tom and Brad"
If this were a Hollywood movie, we might imagine Julia Roberts walking gracefully between Tom Cruise and Brad Pitt.
The hyphen after the relation indicates that its arcs are continued on subsequent lines. Here is the example again, in a different form:
[Person: Tom]-1->(Betw)- <-2-[Person: Brad] ->[Person: Julia]
Notice the hyphen after "(Betw)".
In the graphical notation, the arcs are simply labelled with numbers:
Notice how the arc that has no number is the arc that points away from the relation. Recall that all of the arcs except the last one must point towards the relation, while the last one must point away. Thus the last arc could be labelled with a "3" in this case, but we often simply leave it unlabelled, since it is uniquely identified by its pointing away from the relation.