KNOWLEDGE ENGINEERING, PART A: Knowledge Representation

index

Lecture 4. Conceptual Graphs

4.1. Individuals and Names
4.2. Canonical Graphs

4.1. Individuals and Names

Concepts defined so far are generic concepts: they are like variables that represent an unspecified individual of a given type.
In database systems, Todd et. al (1976) introduced unique identifier or surrogates to identify particular individuals.
In relational database theory, Codd (1979) adopted surrogates as internal representatives of external entities.
Beside surrogates for specific individuals, a database also contain null values, which are place holders for individuals whose identities are unknown.
In conceptual graphs, surrogates are represented by individual markers, which are serial numbers like #80972, and null values are represented by asterisks.
The concept box is divided into two fields separated by colon, as in [PERSON:#80972]. The field to the left of the colon contains the type label PERSON, the field to the right of the colon contains the referent #80972, which designates a particular person.
If the referent is just an asterisk, as in [PERSON:*], the concept is called a generic concept, which may be read as a person or some person.
3.3.1 Assumption. There is a set I ={#1, #2, #3, ....} whose elements are called individual markers. The function referent may be applied to any concept c:

referent(c) is either an individual marker in I or the generic marker *.
When referent(c) is in I, then c is said to be an individual concept.
When referent(c) is *, then c is aid to be a generic concept.

Each generic concept is bounded by an implicit existential quantifier.
3.3.2 Assumption. The operator f maps conceptual graphs into formulas in the first-order predicate calculus. If u is any conceptual graphs, then fu is a formula determined by the following construction:

If u contains k generic concepts, assign a distinct variable symbol x₁, x₂, x₃, ....., x_k to each one.
For each concept c of u, let identifier(c) be the variable assigned to c if c is generic or referent(c) is c is individual.
Represent each concept c as monadic predicate whose name is the same as type(c) and whose argument is identifier(c).
Represent each n-adic conceptual relation r of u as an n-adic predicate whose name is the same as type(r). For each i from 1 to n, let the ith argument of the predicate be the identifier of the concept linked to the ith arc of r.
Then fu has a quantifier prefix $x₁ $x₂ $x₃ .... $x_k and a body consisting of the conjunction of all the predicates for the concepts and conceptual relations of u.

Example:

If graph u is: [CAT:#98077]->(STAT)->[SIT]->(LOC)->[MAT]

then

y(CAT(#98077)^STAT(#98077,x)^SIT(x)^LOC(x,y)^MAT(Y))

3.3.3 Assumption. The conformity relation :: relates type label to individual markers: if t::i is true, then i is said to conform to type t. The conformity relation obeys the following conditions:

The referent of a concept must conform to its type label:

if c is a concept, type(c) :: referent(c).

If an individual marker conforms to type s, it must also conform to all supertypes of s:

if s

£t

s::i

t::i.

If an individual marker conforms to types s and t, it must also conform to their maximal common subtype:

s::i

t::i

t)::i.

Every individual marker conforms to the universal type T; no individual marker conforms to the absurd type ^:

for all i in I, T::i, but not

^::i.

The generic marker * conforms to all type labels:

t, t::*.

Some abbreviations:

3.3.4 Assumption. NAME is a type label for a dyadic conceptual relation, and ENTITY and WORD are type labels for concepts. Let a and b be any concepts linked to arc #1 and #2 of the conceptual relation of type NAME: a ->(NAME)->b. Then the following conditions must hold:

type(a) is a subtype of ENTITY: type(a) <= ENTITY.
type(b) is a proper subtype of WORD: type(b) < WORD.

type(b)

referent(a).

A graph can be abbreviated by name contraction to form a simple graphs, as follows:

[PERSON:#3074]->(NAME)->["Judy"]

[PERSON:Judy]

Measures can be treated in the same way as names. Given the graph:

[BAR]->(CHRC)->[LENGTH]->(MEAS)->[MEASURE]->(NAME)->["25.4cm"]

By name contraction, it may be simplified to:

[BAR]->(CHRC)->[LENGTH]->(MEAS)->[MEASURE: 25.4cm].

Since unit of measure occur so frequently, they may be abbreviated further by measure contraction:

[BAR]->(CHRC)->[LENGTH: @ 25.4cm]

where the symbol @ shows that the following string is not a name, but a measure.

4.2. Canonical Graphs

Not all conceptual graphs make sense. For example:

[SLEEP]->(AGNT)->[IDEA]-(COLR)->[GREEN]

To distinguish the meaningful graphs that represent real or possible situations in the external world, certain graphs are declared to be canonical.
Through experience, each person develops a world view represented in canonical graphs.
3.4.1 Assumption. Certain conceptual graphs are canonical. New graphs may become canonical or be canonized by any of the following three processes:

Perception: Any conceptual graph constructed by the assembler in matching a sensory icon is canonical.
Formation rules: New canonical graph may be derived from other canonical graphs by the rules copy, restrict, join and simplify.
Insight: Arbitrary conceptual graphs may be assumed as canonical.

3.4.3 Assumption. There are four canonical formation rules for deriving a conceptual graph w from conceptual graphs u and v (where u and v may be the same graphs):

Copy. w is an exact copy of u.
Restrict. For any concept c in u, type(c) may be replaced by a subtype; if c is generic, its referent may be changed to an individual marker. These changes are permitted only if referent(c) conforms to type(c) before and after change.
Join. If a concept c in u is identical to a concept d in v, then let w be the graph obtained by deleting d and linking to c all arcs of conceptual relations that had been linked to d.
Simplify. If conceptual relations r and s in the graph u are duplicates, then one of them may be deleted from u together with all its arcs.

By the copy rule, an exact copy of a canonical graph is also canonical.
The restrict rule replaces the type label of a concept with the label of a subtype, as in deriving [GIRL] from [PERSON]. It may also convert a generic concept like [DOG] to an individual concept [DOG:Snoopy].
The join rule merges identical concepts. Two graphs may be joined by overlaying one graph on top of the other so that the two identical concepts merge into a single concept. As a result, all conceptual relations that had ben linked to either concept are linked to the single merged concept.
When two concepts are joined, some relations in the resulting graph may become redundant. One of each pair of duplicates can be deleted by the rule of simplification: when two relations of the same type are linked to the same concepts in the same order, they assert the same information; one of them may therefore be erased.

The formation rules are a kind of graph grammar for canonical graphs, Besides defining syntax, they also enforce certain semantic constraints.
The formation rules enforce selectional constrains by preventing certain combinations from being derived.
Canonical formation rules are NOT rules of inference !!!!

E.g.: If some girl is eating fast, and Sue is eating pie, it does not follow

that Sue is the one who is eating pie fast.

Canonical Formation Rules enforce selectional constraints, but they make no guarantee of truth or falsity.
Levels of meaningfulness:

Gibberish:

Ozderst vwxo ahlazza.

English words, but in an ungrammatical sequence:

A am I number prime.

Grammatical sequence, but violating selectional constraints:

I am a prime number.

Obeying selectional constraints, but violating rules of logic, meaning postulates, or word intensions:

I am the prime minister of the U.K., and so is Margaret.

Logically consistent, but possibly false:

I am the prime minister of the U.K.

Empirically true:

I am writing about canonical formation rules in this

section.

3.4.4 Definition. Let A be any set of conceptual graphs. A graph w is said to be canonically derivable from A if either of the following conditions is true:

w is a member of A.
w may be derived by applying a canonical formation rule to graphs u and v that are themselves canonically derivable from A.

3.4.5 Assumption. The canon contains the information necessary for deriving a set of canonical graphs. It has four components:

A type hierarchy T,
A set of individual markers I,
A conformity relation :: that relates labels in T to markers in I,
A finite set of conceptual graphs B, called a canonical basis, with all type labels in T and all referents either * or markers in I.

The canonical graphs are the closure of B under the canonical formation rules.
If a new graph is canonized that cannot be canonically derived from B, then it must be added to B.

Dickson Lukose &

Rob Kremer . KNOWLEDGE ENGINEERING, PART A: Knowledge Representation. July 1996.

index