5.1.4 generalize

Introduction

The generalize/3 goal is used to find the generalization of two graphs.

We have already described how a graph can be generalized. The generalize/3 goal find the largest graph which is a minimal generalization of the two input graphs. We will explain what this means below.

Signature

The signature of generalize/3 is as follows:

generalize(g1,g2,g3)

where g1,g2,g3 are graphs.

Operation

The generalize/3 goal is used for finding out what the largest minimal generalization of the two graphs g1 and g2 is. The result is returned in g3.

Thus the generalize/3 goal climbs upwards in the type-hierarchy, finding a common subgraph of g1 and g2 which has type-labels which are as low down in the type-hierarchy as possible while still being a generalization.

The result is the largest generalization possible because as much as possible of both graphs are taken into account.

The result is a minimal generalization because the algorithm only crawls as high up in the type-hierarchy as needed to find the minimum common supertype.

Example

//
// generalize/3 example
//
// Available in the AAU directory as generalize.plgCG
//
// Ulrik Petersen
// Created: September 20, 2003
// Last update: September 20, 2003
//

// type-hierarchy
Entity > Physical, Abstract.
Abstract > Property.
Property > Color, Manner.
Manner > Fast.
Physical > Process, Object.
Process > Act.
Act > Drive, Sell.
Object > Vehicle, Person.
Vehicle > Truck, Car.
Car > Porsche.
Person > Man, Woman.

// Catalog of instances
Woman = Elizabeth, Charlotte.
Man = Frank, Joe.
Color = Red, Blue.

// Graphs

// Frank drives a blue car.
graph(Frank, [Drive]-
         -AGNT->[Man: Frank],
         -PTNT->[Car],
         -CHRC->[Color: Blue]).

// Elizabeth drives a red truck fast.
graph(Elizabeth, [Drive]-
         -AGNT->[Woman: Elizabeth],
         -PTNT->[Truck],
         -MANR->[Fast],
         -CHRC->[Color: Red]).

// Joe sells a red Porsche to Charlotte.
graph(Joe, [Sell]-
        -AGNT->[Man: Joe],
        -PTNT->[Porsche],
        -CHRC->[Color: Red],
        -RCPT->[Woman: Charlotte]).

General(L1, L2, g3) :-
        graph(L1, g1),
        graph(L2, g2),
        generalize(g1, g2, g3).

Elizabeth and Joe

If we write the following query:

?-General(Elizabeth, Joe, g3).

The answer is:

{g3 = [Act] -
            -AGNT->[Person],
            -PTNT->[Vehicle],
            -CHRC->[Color : Red]}

Note how:

  • The supertype of Sell and Drive is Act.
  • The supertype of Man and Woman is Person.
  • The supertype of Truck and Porsche is Vehicle.
  • Both the truck and the porsche are red, and so this concept is left intact in the generalization.

Frank and Elizabeth

If we now write the following query:

?- General(Frank, Elizabeth, g3).

The answer is:

{g3 = [Drive] -
              -AGNT->[Person],
              -PTNT->[Vehicle],
              -CHRC->[Color]}

Note how:

  • In both graphs, the act is Drive, and so this concept has been left intact.
  • The supertype of Man and Woman is Person.
  • The supertype of Car and Truck is Vehicle.
  • Both the car and the truck have a color, and so this concept is in the generalization, but one is blue and the other is red, and so the referent has been left out.
  • Only Elizabeth's graph has a -MANR->[Fast] branch, and so this has been left out, since there is no counterpart in Frank's graph.

Frank and Joe

If we now write the following query:

?-General(Frank, Joe, g3).

The answer is:

{g3 = [Act] -
            -AGNT->[Man],
            -PTNT->[Car],
            -CHRC->[Color]}

Note how:

  • The supertype of Drive and Sell is Act, and so this is the type of the corresponding concept in the generalization.
  • Both agents are men, and so this type has been left intact.
  • One man is Frank and the other is Joe, and so the referent has been left out of the generalization.
  • The minimum common supertype of Car and Porsche is Car. Hence this is the type of the corresponding concept.
  • Both the car and the Porsche have a color, and so this concept is in the generalization, but one is blue and the other is red, and so the referent has been left out.
  • Joe's selling has a RCPT (recipient), but Frank's driving doesn't, and so this branch has been left out of the generalization.

Summary

Thus generalize/3 is used to find the largest possible minimal generalization of two graphs.


PrevLite: 5.1.3 subsume
NextLite: 5.1.5 maximalJoin

Prev: 5.1.3 subsume
Up: 5.1 CG goals
Next: 5.1.5 maximalJoin