"High" CG Algebra, or

CG Matching-Based Operations

 

by

Adil KABBAJ

 

               

 

 

Introduction

Amine CG Matching

CG Operations are matching-based operations

Compound CG and Coreference Matching

CG, Functional CG and CG Matching

Sets and CG Operations

New CG Operations

CGOperations API

Examples

 

 

 

Previous: We suggest to consider first CG.

 

 

Introduction

 

Graph matching (called also morphism), semantic network matching and CG matching are important topics in graph theory, knowledge representation, and CG theory respectively. Researchers in CG community have proposed several approaches to deal with CG matching, depending on the nature of the match (maximalJoin, subsumption, generalization, unification, analogy, etc.), the nature of the CG (general CG, simple CG, functional CG, headed CG, compound CGs without coreferents, compound CGs with coreferents, etc.), and the nature of the algorithm of the match (axiomatic, heuristic, algorithmic, CSP, etc.). For instance, it is possible to use the canonical formation rules proposed by John Sowa (copy, simplify, detach, join, restrict, etc.) to perform the match. With these rules, Sowa provides a theoretical definition of the match (matching operation is defined and analysed as an application of a sequence of formation rules). But their use in performing the match will generate a search space of possible matchs (at each step several formation rules can be applied and one rule can be applied in different ways). Various search strategies can be used to explore this space and backtracking can be used to manage some of these strategies. If we are interested by finding all possible matchs of two CGs, canonical rules can be used as a basis for the matching. There is even a possibility to fix some heuristics and parameters for choosing the best match. This is an open area of research.

 

Amine adopts an approach to CG matching that has been investigated for several years by Kabbaj. This approach is not interested by finding all possible matchs, but by finding an appropriate context for an algorithmic and deterministic match that produces at most one match. This approach is presented in the following sections. Of course, it can be enhanced, modified, extended, or replaced by another approach.

 

 

Amine CG Matching

Amine adopts an algorithmic approach to CG matching with an emphasis on the appropriate context for such a match. These two elements are considered in the next two sections.

 

Algorithmic approach to CG matching

Formulation of algorithmic CG matching can be concept-centered or relation-centered:

  1. concept-centered CG matching is based on an iterative application of concepts local matching. Local matching of two CGs g1 and g2 around two concepts c1 and c2 (c1 of g1 and c2 of g2) corresponds to: a) match c1 and c2, b) match income relations of c1 with income relations of c2, and c) match outcome relations of c1 with outcome relations of c2. Two concepts c1 and c2 match if their types, designators, coreferents, and descriptors match. Two relations r1 and r2 match if their types, source concepts, and target concepts match.

    Concept-centered CG matching starts with a local matching of two concepts, it is then propagated, through the matching of income and outcome relations of the two concepts being matched, to other concepts that initiate several other local matching and so on until the matching comes to closure.

    Precise description of concept-centered matching is provided in [Kabbaj, 87, 96] and in Implementation Issues.

     

  2. relation-centered CG matching focuses on relations, not on concepts: relation-centered CG matching of two CG g1 and g2 scans several times all relations of g1 looking for relations that are "partially matched" (at least one of the two concepts of the relation is already matched).

    Precise description of relation-centered CG matching is given in Kabbaj'01. The formulation of relation-centered CG matching is simpler than concept-centered CG matching but it is inefficient since several scans of all relations are needed. Indeed, we need to scan all relations of the CG to identify at each cycle which relations should be matched. However, with concept-directed CG matching we know, each time, what relations to match.

In Amine, we adopt concept-centered CG matching scheme with an emphasis on finding the appropriate context for the match.

 

 

Finding the appropriate context for the match

Two points are relevant for algorithmic CG matching since they provide the appropriate context for the match operation:

- The bootstrap step: We noted above that concept-centered CG matching of two CG g1 and g2 starts with a local matching of two concepts c1 and c2 (c1 from g1 and c2 from g2), but which ones ?; how to select c1 from g1 and c2 from g2 ? This starting step (the bootstrap step) is important since a concept c1 from g1 can be matched in general with several concepts from g2. Reducing these possibilities is relevant for the algorithmic CG matching. Section bootstrap step in Amine presents some sources of information that allow the CG matching operation to perform such a reduction.

 

- The interpretation of relations: In a "general" CG, a concept can have several income relations with the same type, and also several outcome relations with the same type. In this case, an income/outcome relation of c1 (from g1) can be matched with several income/outcome relations of c2 (from g2). These possibilities are combined in general (several concepts of g1 and g2 can be in a situation similar to c1 and c2) so that the result of the match will be, not one CG but a set of possible CGs. If match operates, in addition, on nested CGs, then the result will not be a nested CG but nested sets of CGs ! Moreover, if CG matching operations are used as primitives by a process, the output of one match operation (nested sets of CGs) will be an input of another matching operation. How to perform a match of two nested sets of CG ?, How to manage such a combinatory explosion ?, How to interpret and use these sets ?, ... All theses questions are in fact open questions and lead us to look for another approach that avoids all of them. Indeed, if conceptual relations in a CG g are interpreted as functional relations, then income relations types of each concept in g are/should be mutually different, and the same constraint should hold for outcome relations types. With functional interpretation of relations (and with a matching of relation types that is based on identity test without consideration of relation type hierarchy), relation matching is deterministic: one relation match is possible. If the bootstrap step is also deterministic (i.e. it provides a deterministic selection of the first concepts to match), then CG matching will return at most one CG (not a set of possible CGs or nested sets of CGs). First description and implementation of this approach has been provided by Kabbaj'87.

Hence, the advantage of CG with functional interpretation of relations is to allow a more deterministic CG matching. The drawback is the restriction on the generality of CG (only functional relations are allowed) !  In section CG, Functional CG, and Amine CG Matching, we discuss in more detail this important topic.

 

 

CG operations are matching based operations

In Amine, CG operations like equal, subsume, unify, maximalJoin, and generalize are defined as matching-based operations. This section presents a brief definition of the generic operation match() followed by definitions of CG operations as specializations of the match operation. See Kabbaj'87 for the first formulation of this assimilation and  Implementation Issues for details on the current implementation of these operations in Amine.

 

- match(): matchs CG g1 with CG g2. Match is a generic operation that implements concept-centred CG matching, with the bootstrap step and the functional interpretation of relations. It attempts to find a subgraph of g1 that overlays a subgraph of g2. The next steps (like the detail of concept matching) depend on the nature of the matching: equality matching, generalization matching, maximalJoin matching, subsumption matching, or unification matching. These types of matching correspond to the following CG operations:

 

- equal(): it checks if CG g1 is equal to CG g2 and corresponds to equality matching. In particular, it checks that all g1 overlays all g2 (there is an isomorphic mapping between concepts/relations of g1 and g2) modulo equality matching on matched concepts.  Equality matching of two concepts c1 and c2 checks that their types, designators, and descriptors are equal respectively. In fact, a recursive call to equal() is performed for concepts's descriptors matching. Indeed, remember that a descriptor of a concept is an Amine Object and so, it implements Matching interface that provides these matching operations (which are defined on all Amine objects, not only CG).

 

- generalize(): computes a new CG g3 that is a generalization of CG g1 and CG g2. This operation corresponds to generalization matching. g3 is composed of the subgraph that is common to g1 and g2 modulo generalization matching on matched concepts. Parts of g1 may not overlay parts of g2 and reciprocally. These parts that are specific to g1 and g2 are not copied in g3.  Generalization matching of two concepts c1 and c2 attempts to create a new concept with: a) a type that corresponds to the minimal common superType of c1's type and c2's type, b) a designator that is common to c1's designator and c2's designator, and c) a descriptor that results from the generalization of c1's descriptor and c2's descriptor (i.e., a recursive call to generalize()). See examples_generlize() for some examples.

 

- maximalJoin(): computes a new CG g3 that is the maximalJoin of CG g1 and CG g2. This operation corresponds to maximalJoin matching. In particular, g3 is composed of: a) the subgraph that is common to g1 and g2 modulo maximalJoin matching on matched concepts, b) a copy, in g3, of parts that are specific to g1, and c) a copy, in g3, of parts that are specific to g2. MaximalJoin matching of two concepts c1 and c2 attempts to create a new concept with : a) a type that corresponds to the maximal common subType of c1's type and c2's type, b) a designator that is a specialization of c1's designator and c2's designator, and c) a descriptor that results from the maximalJoin of c1's descriptor and c2's descriptor (i.e., a recursive call to maximalJoin()). See examples_maximalJoin() for various examples.

 

- subsume(): checks if CG g1 subsumes (i.e., is more general than) CG g2 and it corresponds to subsumption matching. In particular, it checks that all g1 overlays g2 (but the inverse may not hold: parts of g2 may not be overlayed) modulo subsumption matching on matched concepts.  Subsumption matching of two concepts c1 and c2 checks that: a) c1's type is a superType of c2's type, c1's designator is more general than c2's designator, and c1's descriptor subsumes c2's descriptor (i.e., a recursive call to subsume()). See examples_subsume() for some examples.

 

- subsumeWithResult(): checks if CG g1 subsumes CG g2 and returns the image of g1 on g2, i.e. returns a copy of the subgraph of g2 that matchs g1. See examples_subsume() for some examples.

 

- unify(): attempts to unify CG g1 with CG g2 and corresponds to unification matching. In particular, it checks that all g1 overlays g2 (but the inverse may not hold: parts of g2 may not be overlayed) modulo unification matching on matched concepts.  Unification matching of two concepts c1 and c2 checks that: a) c1's type can be unified with c2's type if one of them is a variable or the two types have a maximal common subType, c1's designator can be unified with c2's designator (if one of them is a free variable or null, or if the two value can be unified), and c1's descriptor can be unified with c2's descriptor (i.e., a recursive call to unify()). See BindingContext for examples on CG unification.

 

 

Other CG operations

Four other CG operations that are very usefull and strongly related to the above CG matching-based operations are: a) specialize() that specializes a CG by a maximalJoin of another CG, b) generalise() that generalizes a CG by a generalization with another CG, c) expand() that expands a CG g by the maximalJoin of the definition of a concept type or of a relation type, b) isCanonic() that checks if a CG g is canonic, i.e. if (specified) canons of all concepts types and of all relations types that compose g subsume g.

- specialize(): specialize a CG g1 by a maximal join with another CG g2. Contrary to maximalJoin(), specialize does not create a new CG but modifies g1. See examples specialize() for some examples.

- generalise(): generalise a CG g1 by a generalization with another CG g2. Contrary to generalize(), generalise does not create a new CG but modifies g1. See examples generalise() for some examples.

- expand(): expands a CG g by replacing the type of a concept in g by its definition, or by replacing the type of a relation in g by its definition. Such a replacement is based on the maximalJoin of g with the body of the type definition. See examples_expand() for some examples.

- isCanonic(): A CG g is canonic if (specified) canons of all concepts types and of all relations types that compose g subsume g. See examples_isCanonic() for some examples.

 

Other new CG operations are provided (since Amine 3). See  NewCGOperations.

 

Remarks:

- CG matching-based operations in Amine constitute a high CG algebra (low CG algebra concerns the canonical formation rules and other operations provided in CG's API). This algebra is provided in two ways: directly as methods of Matching interface that is implemented by CG (CG's API) and other Amine structures, and indirectly as CG operations package, by CGOperations API presented below in this document.

 

See section Examples for examples of CG operations and see Implementation Issues for details on the implementation.

 

 

Bootstrap Step in Amine

 

As reported in Kabbaj'01 (and in Kabbaj'87 , Kabbaj'96 before), three sources of information provide a deterministic bootstrap (deterministic starting step) for CG matching:

  1. Start by matching CG's heads (if CGs are headed CGs) or entry concepts which could be specified as parameters to the CG matching-based operation. Headed CG has been introduced in our discussion of CG. An entry concept is any concept from a CG that is provided as a starting point for doing a matching-based operation. Entry concepts can be provided directly by the user, or indirectly by a complex operation (such as type definition expansion which calls a maximal join operation) or by a process/task (such as a semantic analyzer which uses maximal join also). Of course, different calls to a CG-matching operation may involve different entry concepts for the same CGs. An entry concept is not a particular and fixed concept in a CG that has the specific property/role of being (for ever) an entry/head of the CG. Rather, entry concept concerns CG matching, i.e. it is a parameter of CG matching operation. It is important to make the difference between the two notions (entry concepts provided to the matching operations vs headed CG): some researchers in CG community proposed CG with head, which corresponds to fixing the entry concept in the CG. With headed CGs, a CG-matching operation will start by the matching of the CG's heads. If entry concepts are specified for the matching-based operation, then the CG matching will start by the matching of the two entry concepts. Amine allows both headed CG and the possibility to give entry concept as parameters for CG matching operations. This second possibility is provided especially by CGOperations API. Examples are presented below, but let us consider the following example. Assume that the two CG cg1 and cg2 are:

CG cg1 :
[Drive] -
    -obj->[Car],
    -agnt->[Person :{Andre, Bob}]


CG cg2 :
[Drive] -
    -manr->[Fast],
    -agnt->[Boy :{Bob, Sam, John}]

 

and we want to perform their maximal join with [Person :{Andre, Bob}] as entry concept for cg1 and [Boy :{Bob, Sam, John}] as entry concept for cg2. Here is the Java code to locate the two entry concepts in cg1 and cg2 respectively and then to call maximalJoin:

 // 1. Locate the entry concept [Person: {Bob, Andre}] in cg1
Type personType = mainLexicon.getTypeCS(Identifier.wrap("Person"));
Concept entryConcept_cg1 = cg1.findConceptWithType(personType);
// 2. Locate the entry concept [Boy : {John, Bob, Sam}] in cg2
Type boyType = mainLexicon.getTypeCS(Identifier.wrap("Boy"));
Concept entryConcept_cg2 = cg2.findConceptWithType(boyType);
// 3. Create an instance of CGOperations in order to call CG operations
CGOperations cgOperations = new CGOperations();
// 4. Call maximalJoin operation with the two entry concepts
ResMatchCG rsltMaximalJoin =        

        cgOperations.maximalJoin(entryConcept_cg1, cg1,

                                 entryConcept_cg2, cg2);

System.out.println("Print the result:\n" +
        rsltMaximalJoin.getCG().toString(mainLexicon));

 

The CG that result from the maximalJoin is:

[Drive] -
    -obj->[Car],
    -agnt->[Boy :{John, Sam, Bob, Andre}],
    -manr->[Fast]

 

  1. Start by matching concepts from CGs g1 and g2 that have specific and identical designators: the designator is specific if it is either an Individual or a set of Individuals (not a variable). Only one concept should represent a specific individual in a CG (a description); this rule is a consequence of the unicity principle adopted in Amine. The result of a CG matching should respect the unicity principle and by consequence, concepts from g1 and g2 that have specific and identical designators should be matched to produce one representative of the identical designator in the output CG. Let us consider the following example, a maximalJoin of CGs cg1 and cg2:

CG cg1 :

    [Person:imad]-ageOf->[Age = 40]

 

CG cg2 :

[Person]<-agnt-[Hit]-

                  -obj->[Man:imad],

                  -instr->[Book]-poss->[Person]

 

with the following statement for calling maximalJoin operation:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Hit] -
    -obj->[Man :imad]-ageOf->[Age = 40],
    -instr->[Book]-poss->[Human],
    -agnt->[Human]

 

There is only one solution since maximalJoin started with a deterministic bootstrap: the join of the concept [Person :imad] of cg1 with the concept [Man :imad] of cg2.

  1. Start by matching concepts with partially matched coreferences. Matching-based operations on compound CGs can benefit from the presence of coreferences which can be interpreted as sources for automatic identification of entry concepts for nested CGs. Indeed, matching two compound CGs is a recursive operation and while entry concepts can be specified as parameters for the first call of the matching operation, no entry concepts can be specified directly for the recursive calls. However, coreferences allow the identification of entry concepts for the match of nested CGs. To see why, recall first that a coreference is a special relation; a relation over nested contexts (Figure 1): coreference is a link of identity that relates a concept c1 in a CG g1 with another concept c11 in a CG g11 that is nested in g1; g11 is a descriptor of a concept in g1 (Figure 1). Concepts c1 and c11 refeer to the same entity (that is why a coreference link is called also a link of identity). Let us consider also another CG g2 with a nested CG g21 and assume that the concept c2 in g2 is in coreference with a concept c21 in g21 (Figure 1). Assume also that during the match of g1 with g2, the two concepts c1 and c2 have been matched (Figure 1). As a result, the coreference   c1--crf1--c11 in g1 is now (partially) matched with the coreference c2--crf2--c21 in g2. If the match of g1 with g2 involves also the match of g11 with g21, then the (partial) match of the two coreferences crf1 and crf2 creates a constraint on the match of g11 with g22: concept c11 in g11 should match with c21 in g21 in order to complete the matching of the two coreferences crf1 and crf2 (indeed, the match of c1 with c2 involved the match of crf1 with crf2 which involves in turn the match of c11 with c21; the other two extremities of the two coreferences crf1 and crf2).

                   

Figure 1: Matching compound CG with coreferences

 

This important point, matching compound CG with coreference, is discussed in more detail in section Compound CG Matching and Coreference. But let us consider now the following example: Assume the two CGs cg1 and cg2:

        CG cg1 :

     [Man *x]<-agnt-[Think]-obj->[Proposition =

                                       [Person ?x]-ageOf->[Age = 40]]

 

        CG cg2 :

     [Person *y]<-agnt-[Action]-obj->

         [Proposition = [Person]<-agnt-[Hit]-

                                          -obj->[Man ?y],

                                          -instr->[Book]-poss->[Person]

                      ]

 

        And the following statement:

        CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

        The result of the code is:

[Think] -
    -obj->[Proposition = [Hit] -
                            -obj->[Man ?y]-ageOf->[Age = 40],
                            -instr->[Book]-poss->[Human],
                            -agnt->[Human]
                        ],
    -agnt->[Man *y]

 

The join of [Man *x] of cg1 with [Person *y] of cg2 leads to the join of their coreferences    --x-- and --y-- which involved in turn a deterministic bootstrap at the level of the two nested CGs: their maximalJoin started with [Person ?x] and [Man ?y]. To see the impact of coreferences on the above operation, let us consider the same example but without the coreference in cg2:

CG cg1 :

    [Man *x]<-agnt-[Think]-obj->[Proposition =

                                    [Person ?x]-ageOf->[Age = 40]]

CG cg2 (note that the coreference --y-- is eliminated) :

  [Person]<-agnt-[Action]-obj->

      [Proposition = [Person]<-agnt-[Hit]-

                                       -obj->[Man],

                                       -instr->[Book]-poss->[Person]

                    ]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Think] -
    -obj->[Proposition = [Hit] -
                            -obj->[Man],
                            -instr->[Book]-poss->[Human],
                            -agnt->[Human ?x]-ageOf->[Age = 40]
                        ],
    -agnt->[Man *x]

 

The result is different from the one given in the previous example: the absence of matched coreferences for the nested CGs involves a non-deterministic maximalJoin in this case. The non-deterministic maximalJoin is performed and Amine provides one result (the first successfull one). Indeed, the concept [Person ?x] in the nested CG in cg1 could be joined with [Person], [Man], or [Person] of the nested CG in cg2, producing differents results. Only one of the three possibilities has been choosen.

Another source of information for a deterministic bootstrap have been adopted in Amine:

  1. If no one of the three sources above is available and if the CG operation is a projection based operation (like equal, subsume and unify: all parts of the first CG g1 should overlay with the second CG g2 but the inverse may not hold: parts of g2 may not be overlayed), and if there is a relation type in g1 that occurs only once in g1 and in g2, then the two relations must match and so, their income/outcome concepts must match also. Thus, these concepts will play the role of entry concepts for starting a deterministic CG matching.

If even point 4 is not applied, then a non-deterministic bootstrap is performed: takes one relation r1 from CG g1 and looks for a relation r2 in CG g2 with the same type as r1, then starts the match of the two CGs by matching the two relations. If the match of the two CG fails, backtracks to the first step and selects another relation r2' from CG g2 with the same type as r1 and try again. If the CG operation is a projection-based operation, then any relation r1 from g1 should be matched with a relation from g2, otherwise the match operation fails. Thus, for projection-based operation, if one relation from g1 cannot be matched with a relation from g2, then the match should stop and return fail. If the operation is not projection-based, then the match should try again with another relation from g1.

 

An algorithmic and detailed formulation of the bootstrap step in CG matching is provided in Implementation Issues.

 

To summarize: 1) heads in the case of headed CGs, 2) entry concepts, 3) identity of individuals (a single individual or a set of individuals), 4) matched coreferences, or 5) one occurrence of a relation in both g1 and g2 when the CG operation is a projection-based operation, are sources for deterministic bootstrap, i.e. the two concepts (or relations) identified by the bootstep must be matched, otherwise the match abort. If in addition, the two CGs to match are functional CGs, then the matching operation is deterministic. If none of the four sources above is available, then the match will start with a non-deterministic bootstrap, i.e. two relations r1 and r2 are selected (from g1 and g2) for the match, but it is not mandatory that the two relations match: if this bootstrap leads to a failure (especially with functional CGs), another couple of relations (for instance, r1 with another relation from g2) is selected. Of course, the matching will be more deterministic if the two CGs to match are functional CGs ; in this case the indeterministic choice is reduced to the bootstrap step only.

 

Remark: Actually, when the bootstrap is non-deterministic, the first successfull match is returned, other possible matchs are not considered. A better approach is to compute all possible matchs and select the best one. One heuristic to determine the best match is the number of matched relations, i.e. the match with the high number of matched relations (the maximum overlay between the two CGs) is the "best" match. This possibility may be integrated in the next version of Amine.

 

 

Compound CG and Coreference Matching

 

As defined in CG, Amine CG can be simple (i.e. a CG that contains no context) or compound CG (CG that contains contexts: concepts with CGs as descriptors), producing nested CGs. Few CG researchers worked on compound CG matching. The first attempt to extend CG operations (like maximalJoin, generalize, and subsume) to compound CG with coreferences has been done by Kabbaj in Kabbaj'87 and then extended in Kabbaj'96. Compound CG matching is an important topic since descriptions of real-world situations require very often the use of compound CGs with coreferences, and hence, the necessity to define matching-based operations on compound CG with coreferences. Beside the necessity and the importance to defining CG operations on compound CGs, we made great emphasis (in Kabbaj'87, Kabbaj'96, and Kabbaj'01) on the relevance of coreferences in finding the appropriate context for an algorithmic and deterministic CG matching. In particular, two aspects of the relation between the matching operation and coreferences are relevant:

  1. Matching-based CG operations can use coreferences to determine entry concepts for matching nested CGs. This aspect has been introduced in the previous section and concerns the bootstrap step in the matching operation,

  2. A full exploitation of coreferences involves a specific design of the matching algorithm. This aspect is treated in this section.

 

Note first that compound CG is in fact a tree of simple CGs. Hence, compound CG matching is a matching of two trees of simples CGs. Compound CG matching can be done following either a depth-first or a breadth-first traversal of the two trees:

  1. Compound CG matching with depth-first traversal of the two trees: when the matching operation determines that two concepts (from CGs g1 and g2) should match, the match is done immediately. This choice applies to both simple concepts (a concept with a descriptor that is not a CG) and contexts (concept with CG as descriptor). Of course, matching two contexts, i.e. two concepts with CGs as descriptors, involves a recursive call to the matching operation, producing depth-first matching.

  2. Compound CG matching with breadth-first traversal of the two trees: in this case and contrary to depth-first compound CG matching, the match of two contexts is done in two steps: contexts types and designators are matched immediately but the match of contexts descriptors is delayed until all concepts and relations of the two current CGs are matched.

Which kind of traversal to choose for the match of two compound CGs ? To have a full exploitation of coreferences, breadth-first traversal should be adopted. Indeed, the problem with "depth-first matching" is that coreferences may not be fully used in order to generate entry concepts for the match of nested CGs. Consider for instance the example in Figure 1: assume that the matching of g1 and g2 starts with the match of concept ca from g1 with concept cb from g2. The second match may concern contexts g11 and g21 (if relations between ca-r->g11 and cb-r->g21 are considered first). According to depth-first matching, the two contexts g11 and g21 will be matched immediately. At this time, the two coreferences have not been considered (see Figure 1) and so, their potential use as source for determining entry concepts for g11 and g22 is not exploited. Depth-first compound CG matching has been adopted by Kabbaj in Kabbaj'87. However, with "breadth-first matching" all coreferences in the current CGs are considered before applying recursive matching on the nested CGs. In this way, the potential use of coreferences as source for determining entry concepts for the match of nested CGs is fully exploited. Breadth-first compound CG matching has been adopted by Kabbaj in Kabbaj'96. Breadth-first compound CG matching is adopted also in Amine.

 

 

CG, Functional CG and CG Matching

 

We noted in section finding the appropriate context for CG matching that the advantage of CG with functional interpretation of relations is to allow a more deterministic and efficient CG matching. The drawback is an "à priori" restriction on the generality of CG (only functional relations are allowed). Concerning this compromise (efficiency vs generality), we take the side of efficiency. This section is concerned by an ontological question: is functional interpretation really a (bad) restriction and generality of relation type a (good) feature ? Our answer to this question is based on the assumption that functional interpretation of relation is a semantic or ontological principle (or convention). It is an answer to an ontological question: what relation types to use for the formulation of knowledge in CG ? CG theory provides a formal algebra and a formal logical basis for CG theory, it is not concerned by this semantic/ontological aspect. But a knowledge engineer who is willing to use CG in a particular application has to adopt some ontology/semantic principles for his formulation of knowledge in term of CGs. It is well known that the same knowledge can be expressed with different terms depending on the underlying ontology. Consider for instance the three CGs below that express the same information:

  General CG:                                    Functional CG (a):                       Functional CG (b):

 [Person]-                       [Person]-                    [Person]-

   -attr->[Color],                 -colorOf->[Color],            -Color->[Color],

   -attr->[Weight],                -weightOf->[Weight],          -Weight->[Weight],

   -attr->[Sex]                    -sexOf->[Sex]                 -Sex->[Sex]

 

The three formulations are equivalent and some mapping rules can be defined to allow a translation from one formulation to another. How to express knowledge (in general CG or in functional CG) is a convention, the important point is that the convention should be known and respected by all users and interpreters of the implied expressions. Note that in Functional CG (b), we use Type in the role of RelationType (Amine 3 provides this possibility. See below for more detail).

It is very important to be aware that: a) the compromise "functional-specific vs general" relation types is in fact an ontological choice, and b) that the two possibilities are equivalent.  We insist on the fact that functional interpretation of relation type is a semantic principle or convention: it is not a restriction that comes from CG formalism, but a convention that comes from the ontological level and that has an impact on CG (as a structure).

It is now clear why Amine CG operations adopt functional interpretation of relation types: functional CG is equivalent to general CG (any knowledge that is expressed in general CG can be expressed also in functional CG) and it allows the definition of a more efficient CG matching-based operations. What is the implication of this decision on a knowledge engineer who is willing to use Amine CG operations ? He has to model his knowledge in terms of functional relation types instead of general relation types. Let us consider for instance an extension of the previous example:

  General CG:                                    Functional CG (a):                       Functional CG (b):

 [Person]-                       [Person]-                    [Person]-

   -attr->[Color],                 -colorOf->[Color],            -Color->[Color],

   -attr->[Weight],                -weightOf->[Weight],          -Weight->[Weight],

   -attr->[Sex],                   -sexOf->[Sex],                -Sex->[Sex],

   -part->[Hand],                  -handOf->[Hand],              -Hand->[Hand],

   -part->[Head],                  -headOf->[Head],              -Head->[Head],

   -part->[Foot],                  -footOf->[Foot],              -Foot->[Foot],

    <-agnt-[Drink]-obj->[Water]             <-agnt-[Drink]-obj->[Water]          <-agnt-[Drink]-obj->[Water]

 

In the general CG, generic relation types (like attr and part) are used. In the functional CG, specific relation types are used and relations are interpreted as roles: [Color] is the colorOf [Person], [Hand] is the handOf [Person], [Water] is the objectOf [Drink], etc. In many situations, relations represent roles (like roles of an Action: agent, obj, instr, loc, dest, etc.). Generic relations like "attr" and "part" relates attributes and components to an object respectively. In this case, the relation type has not an "effective role"; it can be formed automatically by taking the name of the attribute and adding "Of" (of course, addition of "Of" is not mandatory !). Another possibility, provided by Amine 3, is the use of Type in the place of RelationType, as illustrated by Functional CG (b) above. With this possibility, the user avoids the creation and use of "artificial relation identifier" (like colorOf, weightOf, etc.): Color, for instance, plays the role of slot and filler.

 

Knowledge engineer can be general in his formulation of concepts but he should be specific in the formulation of relations.

Those who are familiar with the use of generic relation types will find functional CGs unfamiliar, unnatural and quite restrictive. But once the functional interpretation is adopted and the user gains practice (and familiarity), he/she will find functional CG familiar and quite natural (recall that it is more a convention and a habit than a necessity) !!

 

In Amine, matching-based CG operations are defined on functional CG but the other operations of CG's API are defined on general CG (being functional or not). If an application or a process makes use of matching-based CG operations, it is strongly recommanded to use functional CGs instead of general CGs.

 

Next sections present some flexibilities that Amine provides, concerning CG and CG matching: a) the first section shows how the possibility to have a set of Individuals as designator of a concept is exploited during CG matching, b) the second section presents the possiblity to force, during a CG matching, an automatic coercion of Individual designators to sets of Individuals, and c) the third section presents the possibility to force conformity between the concept type and its designator.

 

Sets and CG Operations

The designator of a concept (in a CG) can be a set of individuals. Hence, CG operations should take into account the case of set matching. Consider for instance the maximal join of the following two CGs:

CG1: [Man: {Karl, John}]<-agnt-[Walk]

CG2: [Man: {Karim, John}]<-agnt-[Walk]

It seems that maximal join of the two sets {Karl, John} and {Karim, John} should be their union: {Karl, John, Karim}, since maximal join of two CG can be viewed as "an union" of two CG (taking into account the connectivity of the graphs). At the level of the graph, maximal join can be viewed as the union of the two graphs (union of their relations). But at the level of the graph nodes (concepts), maximal join looks for the most specific of the two joined concepts. In particular, the maximal join of two concepts [Type1:Designator1] and [Type2:Designator2] looks for the most specific of Type1 and Type2, and the most specific of Designator1 and Designator2. The most specific of two types corresponds to the maximal common subtype of the two types. For instance, the maximal common subtype of "FamiliarVehicle" and "SportVehicle" is "FamiliarSportVehicle". If we consider the set interpretation of types, the set of "FamiliarSportVehicle" is the intersection (not the union) of the sets of "FamiliarVehicle" and "SportVehicle". For the most specific of two designators that correspond to two sets we adopt the same interpretation: the most specific of two sets corresponds to their intersection (and not to their union).

 

Thus, maximal join of the above two CG should be:

[Man: {John}]<-agnt-[Walk] or [Man: John]<-agnt-[Walk]

 

In the same way, generalization of two CG can be viewed, at the level of graph, as "the intersection" of two graphs (intersection of their relations, taking into account the connectivity of the graph). But at the level of nodes/concepts, generalization corresponds to the minimal common supertype for concept types (using the set interpretation, this corresponds to the union) and to union of the two sets when concept designators are sets.

For subsumption, at the level of graph, a CG g1 subsumes (i.e. is more general than) a CG g2 if g1 is a subgraph of g2; the set of relations of g1 is a subset of the set of relations of g2 (taking into account the connectivity of the two graphs). But at the level of nodes/concepts, a concept [Type1:Designator1] is more general than a concept [Type2:Designator2] if Type1 is more general than Type2. If we adopt a set interpretation of types, this corresponds to state that the set of instances of Type2 is a subset of the set of instances of Type1. This same interpretation is adopted for subsumption of sets as designators. For instance:

The CG [Man: {Karl, John, Hicham}]<-agnt-[Walk] subsumes the CG  [Man: {John, Hicham}]<-agnt-[Walk].

 

Coercion of Individuals to sets enhances the flexibility of CG Matching

As illustrated in the previous section, if we have to match a designator that is an individual with another which is a set of Individuals, then an automatic coercion is done (the individual is converted to a set composed of this individual). But if the two designators are two different individuals, then no coercion is done. Note that in some cases, it is desirable to perform such a coercion and in other cases it is not. That is why Amine associates to the class CGOperations presented below, a static boolean attribute, coerceDesignator: if this attribute is true, automatic coercion is done, otherwise no coercion is done.

 

Example:

Assume for instance that we have to apply a maximal join of these two CGs:

g1 = [Drive]-
         -obj->[Car],
         -agnt->[Woman : {Mary, Sue}]

 

g2 = [Drive]-
         -manr->[Fast],
         -agnt->[Woman : Sue]

 

Assume also the following statements where the attribute coerceDesignator is set to false:

  CGOperations.setCoerceDesignator(false);

  CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code above is:

**** maximal join failed

 

Since the attribute coerceDesignator is set to false with the method setCoerceDesignator(false), automatic coercion of individuals to sets of individuals is not done and the maximalJoin fails to join the designator {Mary, Sue}  with the designator Sue. However, if the attribute coerceDesignator is set to true, as in the following code:

  CGOperations.setCoerceDesignator(true);

  CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code will be:

[Drive] -
    -obj->[Car],
    -agnt->[Woman :Sue],
    -manr->[Fast]

 

New CG Operations

Other new CG operations are provided (since Amine 3). See  NewCGOperations.

 

 

CGOperations API

 

CGOperations class contains the implementation of CG operations: match() operation, matching-based operations as well as other operations like specialize(), generalise(), expand(), and isCanonic(). Note that these operations are provided also as methods in CG's API.

CGOperations API provides additional variants for most of matching-based CG operations; variants that allow the specification of entry concepts. Here is for instance, specification of some of these variants:

- Match two CGs G1 and G2, according to the matchOperation (maximalJoin, generalize, etc.) specified in the first argument, starting with entry concept E1 for G1 and entry concept E2 for G2, and bindInf1/bindInf2 which specify binding information for G1 and G2 respectively (if variables binding and their resolution are considered).

 

public ResMatchCG match(byte matchOperation,

              CG G1, Concept E1, Object bindInf1,
              CG G2, Concept E2, Object bindInf2);

 

- In this variant of match() operation, binding information is ignored:

 

public ResMatchCG match(byte matchOperation,

                        CG G1, Concept E1,

                        CG G2, Concept E2);

 

- Perform a maximalJoin of two CGs G1 and G2 starting with entry concept E1 for G1 and entry concept E2 for G2:

 

public ResMatchCG maximalJoin(CG G1, Concept E1, 

                              CG G2, Concept E2);

 

- In this variant of maximalJoin() operation, entry concepts are not provided:

public CG maximalJoin(CG G1, CG G2);

 

Similar variants are offered for the other CG operations (equal(), subsume(), subsumeWithResult(), generalize(), and unify()).

 

Note also that the two parameters coerceDesignator and relaxType, are defined as two static boolean attribute of CGOperations. Getters and setters for these attributes are provided by CGOperations API.

 

see APIs Specification for the detailed specification of CGOperations API and Implementation Issues for detail on its implementation. The next section presents examples of CG operations.

 

 

 

 

 

 

Examples

Here is excerpts from the Java class CGTest that concern CG operations. Also, reader who is not interested by using Java classes, can "see" these examples "in execution" by proceeding as described in CGOperations GUI (which is a GUI that allows a user to activate CG operations directly). See BindingContext for examples on CG unification.

 

- maximalJoin():

 

-> Example 1: simple maximal join with sets

Assume these two CGs:

CG cg1 :
  [Drive]-
       -obj->[Car],
       -agnt->[Human :{Bob, Andre}]


CG cg2 :
  [Drive]-
      -manr->[Fast],
      -agnt->[Boy :{Bob, John, Sam}]

 

And the following statement:
CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of maximalJoin is (note the union of the two sets of individuals):

  [Drive]-
        -obj->[Car],
        -agnt->[Boy :Bob],
        -manr->[Fast]

 

-> Example 5: maximalJoin() from CGOperations with entry concepts

Assume that the two CG cg1 and cg2 are:

CG cg1 :
[Drive] -
    -obj->[Car],
    -agnt->[Person :{Andre, Bob}]


CG cg2 :
[Drive] -
    -manr->[Fast],
    -agnt->[Boy :{Bob, Sam, John}]

 

and we want to perform their maximal join with [Person :{Andre, Bob}] as entry concept for cg1 and [Boy :{Bob, Sam, John}] as entry concept for cg2. Here is the code to locate the two entry concepts in cg1 and cg2 respectively and then to call maximalJoin:

 // 1. Locate the entry concept [Person: {Bob, Andre}] in cg1
Type personType = mainLexicon.getTypeCS(Identifier.wrap("Person"));
Concept entryConcept_cg1 = cg1.findConceptWithType(personType);
// 2. Locate the entry concept [Boy : {John, Bob, Sam}] in cg2
Type boyType = mainLexicon.getTypeCS(Identifier.wrap("Boy"));
Concept entryConcept_cg2 = cg2.findConceptWithType(boyType);
// 3. Create an instance of CGOperations in order to call CG operations
CGOperations cgOperations = new CGOperations();
// 4. Call maximalJoin operation with the two entry concepts
ResMatchCG rsltMaximalJoin =        

        cgOperations.maximalJoin(cg1, entryConcept_cg1,

                                 cg2, entryConcept_cg2);

System.out.println("Print the result:\n" +
        rsltMaximalJoin.getCG().toString(mainLexicon));

 

The CG that result from the maximalJoin is:

[Drive] -
    -obj->[Car],
    -agnt->[Boy :Bob],
    -manr->[Fast]

 

-> Example 6: maximalJoin() with bootstrap fixed by the presence of identical designators

Assume that the two CGs are:

CG cg1 :

    [Person:imad]-ageOf->[Age = 40]

 

CG cg2 :

[Person]<-agnt-[Hit]-

                  -obj->[Man:imad],

                  -instr->[Book]-poss->[Person]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Hit] -
    -obj->[Man :imad]-ageOf->[Age = 40],
    -instr->[Book]-poss->[Human],
    -agnt->[Human]

 

The maximalJoin here starts with a deterministic bootstrap: the join of the concept [Person :imad] in cg1 with the concept [Man :imad] in cg2. If the unicity principle was not considered and hence the constraint to join the two concepts with specific and identical individuals is not considered, then the maximalJoin will be non-deterministic since the concept [Person :imad] in cg1 can be joined with [Person], [Man :imad], or [Person] of cg2.

 

-> Example 7: maximalJoin() on nested CGs

Assume now the two CG:

CG cg1 :

[Begin]-
    -obj->[Session],
    -srce->[Proposition = [Press]-
                                -obj->[Key :enter]-partOf->[Keyboard],
                                -agnt->[Human :John]
                          ],
    -agnt->[Human :John]


CG cg2 :
[Begin]-
    -obj->[Session],
    -srce->[Proposition = [Press]-
                               -manr->[Fast],
                               -obj->[Key],
                               -agnt->[Man]
                          ],
    -agnt->[Man]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Begin]-
     -obj->[Session],
     -srce->[Proposition = [Press]-
                                -obj->[Key :enter]-partOf->[Keyboard],
                                -agnt->[Man :John],
                                -manr->[Fast]
                            ],
     -agnt->[Man :John]

 

-> Example 8: maximalJoin() on nested CGs (continue)

Assume now the two CG:

CG cg1 :

[Begin]-
    -obj->[Session],
    -srce->[Proposition = [Press]-
                                -obj->[Key :enter]-partOf->[Keyboard],
                                -agnt->[Human :John]
                          ],
    -agnt->[Human :John]

 

CG cg1:

[Begin]-
    -srce->[Proposition = [Look]-
                            -dest->[Person],
                            -pat->[Person]    ],
    -agnt->[Man]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                                -obj->[Key :enter]-partOf->[Keyboard],
                                -agnt->[Human #0]<-dest-[Look]-pat->[Human]
                         ],
    -agnt->[Man]

 

-> Example 9: maximalJoin() on nested CGs with coreferences

Assume now the two CG:

CG cg1 :

[Begin]-
    -obj->[Session],
    -srce->[Proposition = [Press]-
                                -obj->[Key :enter]-partOf->[Keyboard],
                                -agnt->[Person ?x]
                          ],
    -agnt->[Person *x]

 

CG cg1:

[Begin]-
    -srce->[Proposition = [Look]-
                            -dest->[Person],
                            -pat->[Person]    ],
    -agnt->[Man]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                              -obj->[Key :enter]-partOf->[Keyboard],
                              -agnt->[Human #0 ?x]<-dest-[Look]-pat->[Human]
                         ],
    -agnt->[Man *x]

 

-> Example 10: maximalJoin() of nested CGs with bootstrap fixed by coreferences

Assume that the two CGs are:

CG cg1 :

    [Man *x]<-agnt-[Think]-obj->[Proposition =

                                    [Person ?x]-ageOf->[Age = 40]]

 

CG cg2 :

    [Person *y]<-agnt-[Action]-obj->

        [Proposition = [Person]<-agnt-[Hit]-

                                          -obj->[Man ?y],

                                          -instr->[Book]-poss->[Person]

                      ]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Think] -
    -obj->[Proposition = [Hit] -
                            -obj->[Man ?y]-ageOf->[Age = 40],
                            -instr->[Book]-poss->[Human],
                            -agnt->[Human]
                        ],
    -agnt->[Man *y]

 

The join of [Man *x] of cg1 with [Person *y] of cg2 leads to the join of their coreferences --x-- and --y-- which involves in turn a deterministic bootstrap at the level of the two nested CGs: their maximalJoin started with [Person ?x] and [Man ?y]. To see the impact of coreferences on the above operation, let us consider the same example but without the coreference in cg2:

CG cg1 :

    [Man *x]<-agnt-[Think]-obj->[Proposition =

                                    [Person ?x]-ageOf->[Age = 40]]

 

CG cg2 :

    [Person]<-agnt-[Action]-obj->

        [Proposition = [Person]<-agnt-[Hit]-

                                          -obj->[Man],

                                          -instr->[Book]-poss->[Person]

                      ]

 

And the following statement:

    CG maximalJoinResult = (CG) cg1.maximalJoin(cg2);

 

The result of the code is:

[Think] -
    -obj->[Proposition = [Hit] -
                            -obj->[Man],
                            -instr->[Book]-poss->[Human],
                            -agnt->[Human ?x]-ageOf->[Age = 40]
                        ],
    -agnt->[Man *x]

 

Note that the result is different from the one given in the previous example: the absence of matched coreferences for the nested CGs involves a non-deterministic maximalJoin in this case. The non-deterministic maximalJoin is performed and Amine provides one result (the first successfull one). Indeed, the concept [Person ?x] in the nested CG in cg1 could be joined with [Person], [Man], or [Person] of the nested CG in cg2, producing differents results. Only one of the three possibilities has been choosen.

 

- specialize()

-> Example 11: specialize a CG cg1 by a maximalJoin with cg2

Assume these two CGs:

CG cg1 :
  [Drive]-
       -obj->[Car],
       -agnt->[Person :{Bob, Andre}]


CG cg2 :
  [Drive]-
      -manr->[Fast],
      -agnt->[Boy :{Bob, John, Sam}]

 

And the following statement (specialize cg1 by a maximalJoin with cg2):
cg1.specialize(cg2);

 

The result of specialization is (note that the result is a modification of cg1 itself):

cg1 = [Drive]-
         -obj->[Car],
         -agnt->[Boy :Bob],
         -manr->[Fast]

 

- generalize()

-> Example 12: Generalization of two simple CGs

Assume that the two CGs to generalize are:

CG cg1 :
[Drive] -
    -obj->[Car]-chrc->[Color :red],
    -agnt->[Boy :John]


CG cg2 :
[Drive] -
    -obj->[Truck],
    -manr->[Fast],
    -agnt->[Girl :Sue]

 

And the following statement:

     CG generalizeResult = (CG) cg1.generalize(cg2);


The result of the statement above is:
[Drive] -
    -agnt->[Human: {John, Sue}],
    -obj->[Vehicle]

 

-> Example 13: Generalization of two simple CGs with sets as designators

CG cg1 :
[Drive] -
    -obj->[Car]-chrc->[Color :red],
    -agnt->[Human :{Sam, John, Mary, Sue}]


CG cg2 :
[Drive] -
    -obj->[Truck],
    -manr->[Fast],
    -agnt->[Girl :{Mary, Sue}]

 

And the following statement:

     CG generalizeResult = (CG) cg1.generalize(cg2);


The result of the statement above is:
[Drive] -
    -agnt->[Human :{Sam, John, Mary, Sue}],
    -obj->[Vehicle]

 

-> Example 14: Generalization of two simple CGs with automatic coercion

CG cg1 :
[Drive] -
    -obj->[Car]-chrc->[Color :red],
    -agnt->[Human :{Sam, John, Mary, Sue}]


CG cg2 :
[Drive] -
    -obj->[Truck],
    -manr->[Fast],
    -agnt->[Girl :Sue]

 

And the following statement:

     CG generalizeResult = (CG) cg1.generalize(cg2);


The result of the statement above is:
[Drive] -
    -obj->[Vehicle],
    -agnt->[Human :{Sam, John, Mary, Sue}]

 

Note that the designator Sue of the concept [Girl :Sue] in cg2 is coerced first to the set {Sue}, then the generalization operation of [Girl :{Sue}] and [Human :{Sam, John, Mary, Sue}] is done, producing the concept [Human :{Sam, John, Mary, Sue}].

 

-> Example 15: Generalization of two compound CGs with coreference

CG cg1 :
[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                            -obj->[Key :enter]-partOf->[Keyboard],
                            -agnt->[Human ?x]
                        ],
    -agnt->[Human *x]


CG cg2 :
[Begin] -
    -srce->[Proposition = [Action] -
                                -dest->[Human],
                                -agnt->[Boy]
                           ],
    -agnt->[Man]

 

And the following statement:

     CG generalizeResult = (CG) cg1.generalize(cg2);


The result of the statement above is:
[Begin] -
    -srce->[Proposition = [Human]<-agnt-[Action]
                          ],
    -agnt->[Human]
 

Note that the CG that results from the generalization does not contain a coreference link between [Human] and [Human], because concepts [Man] and [Boy] in cg2 (that matched with [Human *x] and [Human ?x] from cg1) are not in coreference and so, the coreference link is not common to the matched concepts. Consider however the next example:

 

-> Example 16: Generalization of two compound CGs with coreference (continue)

CG cg1 :
[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                            -obj->[Key :enter]-partOf->[Keyboard],
                            -agnt->[Human ?x]
                        ],
    -agnt->[Human *x]


CG cg2 :
[Begin] -
    -srce->[Proposition = [Action] -
                                -dest->[Human],
                                -agnt->[Boy ?y]
                           ],
    -agnt->[Man *y]

 

And the following statement:

     CG generalizeResult = (CG) cg1.generalize(cg2);


The result of the statement above is:
[Begin] -
    -srce->[Proposition = [Human ?y]<-agnt-[Action]
                          ],
    -agnt->[Human *y]

 

Since the matched concepts have common coreference links, the two concepts that result from their generalization are also in coreference.

 

- generalise()

-> Example 17: Generalize a CG cg1 by a generalization with a CG cg2

Assume these two CGs:

CG cg1 :
[Drive] -
    -obj->[Car]-chrc->[Color :red],
    -agnt->[Boy :John]


CG cg2 :
[Drive] -
    -obj->[Truck],
    -manr->[Fast],
    -agnt->[Girl :Sue]

 

And the following statement (generalize cg1 by a generalization with cg2):

  CG generalizeResult = (CG) cg1.generalise(cg2);

 

The result of the statement above is (note that the result is a modification of cg1 itself):

[Drive] -
    -agnt->[Human: {John, Sue}],
    -obj->[Vehicle]

 

- subsume() and subsumeWithResult()

-> Example 18: Subsumption of simple CG

Assume the following two CGs:

CG cg1 :
    [Human]-childOf->[Human]


CG cg2 :
    [Boy :Bob] -
        <-agnt-[Love]-obj->[Girl :Mary],
        <-childOf-[Man :John]

 

And the following statements:

    boolean isSubsume = cg1.subsume(cg2);

    CG subsumeResult = (CG) cg1.subsumeWithResult(cg2);

 

The result of the two statements above is:
The result of subsume: true


The result of subsumeWithResult :
    [Man :John]-childOf->[Boy :Bob]

 

-> Example 19: Subsumption of simple CG with sets as designators

Assume the following two CGs:

CG cg1 :
    [Human]-childOf->[Human :{Karl, Sam, Bob, Andre}]


CG cg2 :
  [Boy :{Sam, Karl}] -
                    <-agnt-[Love]-obj->[Girl :Mary],
                    <-childOf-[Man :John]

 

And the following statements:

    boolean isSubsume = cg1.subsume(cg2);

    CG subsumeResult = (CG) cg1.subsumeWithResult(cg2);

 

The result of the two statements above is:
The result of subsume: true
 

The result of subsumeWithResult :
  [Man :John]-childOf->[Boy :{Sam, Karl}]

 

-> Example 20: Subsumption of simple CG with sets as designators (continue)

Assume the following two CGs:

CG cg1 :
[Human]-childOf->[Human :{Andre, Bob, John}]

 
CG cg2 :
[Boy :{Sam, John}] -
        <-agnt-[Love]-obj->[Girl :Mary],
        <-childOf-[Man :Karl]

 

And the following statements:

    boolean isSubsume = cg1.subsume(cg2);

    CG subsumeResult = (CG) cg1.subsumeWithResult(cg2);

 

The result of the two statements above is:
The result of subsume: false
 

The result of subsumeWithResult :
**** subsumeWithResult failed

 

CG cg1 does not subsume cg2 because {Sam, John} is not a subset of {Andre, Bob, John}.

 

-> Example 21: Subsumption of compound CG

Assume the following two CGs:

CG cg1 :
[Begin] -
    -srce->[Proposition = [Action] -
                                -obj->[Object],
                                -agnt->[Human]
                        ],
    -agnt->[Human]


CG cg2 :
[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                              -obj->[Key :enter]-partOf->[Keyboard],
                              -agnt->[Boy]
                          ],
    -agnt->[Man]


 

And the following statements:

    boolean isSubsume = cg1.subsume(cg2);

    CG subsumeResult = (CG) cg1.subsumeWithResult(cg2);

 

The result of the code above is:

The result of subsume: false
 

The result of subsumeWithResult :
[Begin] -
    -srce->[Proposition = [Press] -
                                -agnt->[Boy],
                                -obj->[Key :enter]
                          ],
    -agnt->[Man]

 

-> Example 22: Subsumption of compound CG with coreference

Assume the following two CGs:

CG cg1 :
[Begin] -
    -srce->[Proposition = [Action] -
                                -obj->[Object],
                                -agnt->[Human ?x]
                        ],
    -agnt->[Human *x]


CG cg2 :
[Begin] -
    -obj->[Session],
    -srce->[Proposition = [Press] -
                              -obj->[Key :enter]-partOf->[Keyboard],
                              -agnt->[Boy]
                          ],
    -agnt->[Man]


 

And the following statements:

    boolean isSubsume = cg1.subsume(cg2);

    CG subsumeResult = (CG) cg1.subsumeWithResult(cg2);

 

The result of the code above is:

The result of subsume: false
 

The result of subsumeWithResult :

**** subsumeWithResult failed

 

CG cg1 does not subsume CG cg2 because the coreference between [Human *x] and [Human ?x] in cg1 has no corresponding coreference in cg2.

 

- equal()

-> Example 23:

Assume these two CGs:

CG cg1 :
  [Drive]-
       -obj->[Car],
       -agnt->[Human :{Bob, Andre}]


CG cg2 :
  [Person :{Andre, Bob}]<-agnt-[Drive]-obj->[Car :x]

 

And the following statement:
boolean rslt = (CG) cg1.equal(cg2);

 

The result of equal() is:

 true

 

Note the "syntactic differences": LF of the two CGs are not identical, concepts [Car] and [Car:x] are not identical (in the first there is no designator and in the second a designator), concepts [Human :{Bob, Andre}] and [Person :{Andre, Bob}] are not identical: in the first, the type identifier is Human, and in the second we have a different type identifier. There is also syntactic difference between the two sets. But all these differences are syntactical only, the two CGs are equal in content. However, if instead of the concept [Car] in cg1 we have [Vehicle], the result will be false. Also, if instead of [Human :{Bob, Andre}] in cg1 we have [Human], the result will be false.

 

- isCanonic()

-> Example 24:

Assume that the concept type Work has the following canon:

[Work] -
    -obj->[Job],
    -agnt->[Human]

 

And we want to check the canonicity of the following CG:
CG cg1 : [Work] -
            -obj->[Finger],
            -manr->[Hard],
            -agnt->[Man]

 

The statement for checking canonicity:

    boolean isCanonic = cg1.isCanonic();

 

The result of the above statement:

false

 

CG cg1 is not canonic because the canon of the concept type Work does not subsume cg1.

 

-> Example 25:

Assume that CG cg1 is:

[Work] -
     -obj->[Job],
     -manr->[Book],
     -agnt->[Man]

 

The statement for checking canonicity:

    boolean isCanonic = cg1.isCanonic();

 

The result of the above statement:

false

 

In this example, the canon for Work subsumes the CG cg1 but the canon for the relation manr does not subsume cg1, hence cg1 is not canonic.

 

-> Example 26:

Assume that CG cg1 is:

[Work] -
     -obj->[Job],
     -manr->[Hard],
     -agnt->[Man]

 

The statement for checking canonicity:

    boolean isCanonic = cg1.isCanonic();

 

The result of the above statement:

true

 

Now, CG cg1 is canonic since all (specified) canons of concept types and relations types that are used in cg1 subsume cg1.

 

- expand()

-> Example 27: Concept type expansion. A simple example

Assume that the definition of the concept type Man is:

[Human :super]-sexOf->[Sex = male]

 

And assume that CG cg1 is:

[Work] -
     -obj->[Job],
     -manr->[Hard],
     -agnt->[Man :imad]

 

And we want to expand the concept [Man]. Here is the code for doing such an expansion:

  // First step: get the Type CS for the identifier named "Man"

  manType = mainLexicon.getTypeCS(Identifier.wrap("Man"));

  // Second step: find in CG cg1 the concept with the Type CS manType
  Concept concMan = cg1.findConceptWithType(manType);

  // Third step: do the expansion
  CG cgRslt = cg1.
expand(concMan);

 

The result of the code above:

cgRslt:

[Work] -
    -obj->[Job],
    -manr->[Hard],
    -agnt->[Human :imad]-sexOf->[Sex = male]

 

-> Example 28: Concept type expansion. A more complex example

Assume that the definition of the concept type Intelligent_System is:

[Intelligent:super]<-intelligenceOf-[System:super]<-obj-[Build]

                                                        -agnt->[AIScientist]

 

And assume that the CG cg1 to expand is:

[Action] -
    -obj->[Intelligent_System]-chrc->[Hard],
    -agnt->[Man]

 

And we want to expand the concept [Intelligent_System]. If a concept type is defined in terms of more than one genus (like type Intelligent_System) and we want to expand a CG with such a definition, there is the problem to determine which genus to consider. Our solution to this problem is to loop on all genus in the definition, looking for the one that allows for a successfull maximalJoin and that provides a result that is canonic.

 

Hence, the result of the expansion of CG cg1 is:

[System] -
    -intelligenceOf->[Intelligent :super],
    -chrc->[Hard],
    <-obj-[Build]-agnt->[AIScientist]

 

Note that the selected genus in the above expansion is [System :super]. If the concept [intelligent :super] is selected as genus, it will lead to a violation of canonicity:

[Intelligent #0] -
        -chrc->[Hard],
        <-intelligenceOf-[System :super]<-obj-[Build]-agnt->[AIScientist],
        <-obj-[Action]-agnt->[Man]

 

The canon of the relation type obj is violated: the target of obj should be an Object and Intelligent is not an Object.

 

-> Example 29: Relation type expansion.

Assume that the definition of the relation type workOf is:

[Person:x_source]<-agnt-[Work]-obj->[Job:y_target]

 

And assume that CG cg1 is:

    [Man]-workOf->[TaxiDriver]-ageOf->[Age = 50]

 

And we want to expand the relation -workOf->. Here is the code for doing such an expansion:

// First step: get the RelationType CS for the identifier named "workOf"
RelationType workOfType =        

                mainLexicon.getRelationTypeCS(Identifier.wrap("workOf"));

// Second step: find in cg1 the (first) relation with the Type CS workOfType
Relation relWorkOf = (Relation) cg1.findRelations(workOfType).nextElement();
// Third step: do the expansion
cgRslt = cg1.expand(relWorkOf);

 

The result of the code above is:

[TaxiDriver] -
        -ageOf->[Age = 50],
        <-obj-[Work]-agnt->[Man]

 

 

Other new CG operations are provided (with Amine 3). See  NewCGOperations.

 

References

 

Kabbaj A., SMCG : un système de manipulation des graphes conceptuels, M. Sc. Thesis, Univ. Laval, Canada, 1987.

 

Kabbaj A., Un système multi-paradigme pour la manipulation des connaissances utilisant la théorie des graphes conceptuels, Ph.D Thesis, DIRO, U. de Montréal, Juin, 1996.

 

A. Kabbaj and B. Moulin, An algorithmic definition of CG operations based on a bootstrap step, in 9th Int. Conf. on Conceptual Structures, ICCS'2001, Springer-Verlag, 2001.