Automatic insertion point identification in model merging operations

Abstract

Automatic identification of an insertion point is done by comparisons defining the correspondence between elements of models. The sequence order of elements in the second model is analyzed to identify predecessor and successor elements of the element t. The comparison is used to identify a set of transferred predecessors (P trans ), comprising elements of the first model which correspond to predecessor elements (P S ) in the second model, and a set of transferred successors (S trans ) comprising elements of the first model which correspond to successor elements (S S ) in the second model. Then, positions of the elements x, y in the sequence order of the first model are compared with the positions of elements in the sets of transferred predecessors and successors (P trans , S trans ). An edge between the elements x and y is identified as an insertion point.

1 . A method for automatic identification, in a data processing system, performed on a processing device of a computer, of an insertion point in a first model stored in memory of the system for a predetermined element t of a second model, the method comprising the computer processor performing insertion point identification process steps of:
 providing in the memory a comparison of first and second models defining a correspondence between elements of the models;   analyzing a sequence order of elements in the second model to identify predecessor and successor elements of the element t in the second model;   using said comparison to identify a first model set of predecessors, comprising elements of the first model which correspond to said predecessor elements in the second model, and a set of first model successors comprising elements of the first model which correspond to said successor elements in the second model;   for pairs of adjacent elements x, y in the first model, comparing the positions of the elements x, y in the sequence order of the first model with the positions of elements in the sets of first model predecessors and successors, and determining if a position of an edge between the elements x and y relative to the first model predecessors and successors is consistent with the sequence order of the element t and the predecessor and successor elements in the second model; and   identifying the edge as an insertion point if the position of the edge is determined to be consistent with the sequence order of the element t and the predecessor and successor elements in the second model.   
     
     
         2 . A method according to  claim 1  wherein the position of the edge relative to the first model predecessors and successors is deemed not inconsistent with said sequence order in the second model if:
 (a) the element x is a successor of all first model predecessors except itself; and 
 (b) the element y is a predecessor of all first model successors except itself. 
 
     
     
         3 . A method according to  claim 2  wherein the position of the edge relative to the first model predecessors and successors is deemed consistent with said sequence order in the second model:
 in the first mode, if and only if conditions (a) and (b) are satisfied; and 
 in the second mode, if and only if either condition (c) or condition (d), wherein condition (c) requires that the element x is either a successor of, or is not ordered with respect to, all first model predecessors and condition (d) requires that the element x is a disjunctive element that does not satisfy condition (c) AND the element y is either a successor of, or is not ordered with respect to, all first model predecessors, AND either condition (e) or condition (f) is satisfied, wherein condition (e) requires that the element y is either a predecessor of, or is not ordered with respect to, all successors, and condition (f) requires that the element y is a conjunctive element that does not satisfy condition (e) AND the element x is either a predecessor of, or is not ordered with respect to, all successors. 
 
     
     
         4 . A method according to  claim 2  which is selectively operable in first and second modes, wherein the position of the edge relative to the transferred predecessors and successors is deemed not inconsistent with said sequence order in the second model
 in the first mode, if and only if conditions (a) and (b) are satisfied, and 
 in the second mode, if and only if either condition (c) or condition (d), wherein condition (c) requires that the element x is either a successor of, or is not ordered with respect to, all first model predecessors and condition (d) requires that the element x is a disjunctive element that does not satisfy condition (c) AND the element y is either a successor of, or is not ordered with respect to, all first model predecessors, AND either condition (e) or condition (f), are satisfied, wherein condition (e) requires that the element y is either a predecessor of, or is not ordered with respect to, all successors, and condition (f) requires that the element y is a conjunctive element that does not satisfy condition (e) AND the element x is either a predecessor of, or is not ordered with respect to, all successors, and 
 wherein the method includes operating in said first mode in a first pass of the insertion point identification process, and, if no insertion point is identified in the first pass, operating in said second mode in a second pass of the insertion point identification process. 
 
     
     
         5 . A method according to  claim 1  including providing in the memory a partial order of the second model indicative of the sequence order of elements in that model, and processing the partial order to identify said predecessor and successor elements of the element t. 
     
     
         6 . A method according to  claim 6  wherein the second model is stored in the memory, the method including analyzing the second model to generate said partial order. 
     
     
         7 . A method according to  claim 1  including performing said step of comparing the positions of the elements x, y in the sequence order of the first model for every pair of adjacent elements x, y in the first model. 
     
     
         8 . A method according to  claim 1  including analyzing the first model to generate a partial order indicative of the sequence order of elements in that model, and processing the partial order to compare the positions of the elements x, y in the sequence order of the first model with the positions of elements in the sets of transferred predecessors and successors. 
     
     
         9 . A method according to  claim 1  including:
 analyzing the sequence order of elements in the sets of first model predecessors and successors to identify a sequentially last transferred predecessor and the sequentially-first first model successor; and 
 performing said step of comparing by comparing the positions of the elements x, y with the positions of a sequentially last first model predecessor and a sequentially-first first model successor. 
 
     
     
         10 . A method according to  claim 1  including analyzing the first model to detect unstructured cycles, and, if an unstructured cycle is detected, applying a cycle removal operation to the model to transform the unstructured cycle to a structured cycle. 
     
     
         11 . A tangible computer-usable medium having embodied therein computer-readable program code means for causing a data processing system to perform a method for automatic identification, in a data processing system, of an insertion point in a first model stored in memory of the system for a predetermined element t of a second model, the method comprising:
 providing in the memory a comparison of the first and second models defining the correspondence between elements of the models;   analyzing the sequence order of elements in the second model to identify predecessor and successor elements of an element t in the second model;   using said comparison to identify a set of first model predecessors, comprising elements of the first model which correspond to said predecessor elements in the second model, and a set of first model successors comprising elements of the first model which correspond to said successor elements in the second model; and   for pairs of adjacent elements x, y in the first model, comparing positions of the elements x, y in the sequence order of the first model with positions of elements in the sets of first model predecessors and successors, determining if a position of an edge between elements x and y relative to the first model predecessors and successors is consistent with the sequence order of the element t and the predecessor and successor elements in the second model, and identifying the edge as an insertion point if the position of the edge between elements x and y is determined to be consistent with the sequence order of element t and the predecessor and successor elements in the second model.   
     
     
         12 . A computer system for automatic identification of an insertion point in a first model for a predetermined element t of a second model, the computer system comprising memory for storing the first model and a comparison of the first and second models which defines the correspondence between elements of the models, and processor with control logic adapted to perform an insertion point identification process by:
 analyzing a sequence order of elements in the second model to identify predecessor and successor elements of element t in the second model;   using said comparison to identify a set of first model predecessors, comprising elements of the first model which correspond to said predecessor elements in the second model, and a set of first model successors comprising elements of the first model which correspond to said successor elements in the second model; and   for pairs of adjacent elements x, y in the first model, comparing positions of the elements x, y in the sequence order of the first model with the positions of elements in the sets of first model predecessors and successors, and to identify an edge between the elements x and y as an insertion point if the position of the edge relative to the first model predecessors and successors is consistent with the sequence order of the element t and the predecessor and successor elements in the second model.   
     
     
         13 . A system according to  claim 12  wherein the control logic is adapted to determine that the position of the edge relative to the transferred predecessors and successors is not inconsistent with said sequence order in the second model if:
 (a) the element x is a successor of all first model predecessors except itself; and 
 (b) the element y is a predecessor of all first model successors except itself. 
 
     
     
         14 . A system according to  claim 12  which is selectively operable in first and second modes, wherein the control logic is adapted to determine that the position of the edge relative to the transferred predecessors and successors is not inconsistent with said sequence order in the second model:
 in the first mode, if and only if conditions (a) and (b) are satisfied, wherein condition (a) requires the element x is a successor of all first model predecessors except itself; and condition (b) requires the element y is a predecessor of all first model successors except itself; and 
 in the second mode, if and only if either condition (c) or condition (d), wherein condition (c) requires that the element x is either a successor of, or is not ordered with respect to, all first model predecessors and condition (d) requires that the element x is a disjunctive element that does not satisfy condition (c) AND the element y is either a successor of, or is not ordered with respect to, all first model predecessors, AND either condition (e) or condition (f), wherein condition (e) requires that the element y is either a predecessor of, or is not ordered with respect to, all successors, and condition (f) requires that the element y is a conjunctive element that does not satisfy condition (e) AND the element x is either a predecessor of, or is not ordered with respect to, all successors, are satisfied. 
 
     
     
         15 . A system according to  claim 12  which is selectively operable in first and second modes, wherein the control logic is adapted:
 to determine that the position of the edge relative to the transferred predecessors and successors is not inconsistent with said sequence order in the second model
 in the first mode, if and only if conditions (a) and (b) are satisfied, wherein condition (a) requires the element x is a successor of all first model predecessors except itself; and condition (b) requires the element y is a predecessor of all first model successors except itself, and 
 in the second mode, if and only if either condition (c) or condition (d), wherein condition (c) requires that the element x is either a successor of, or is not ordered with respect to, all first model predecessors and condition (d) requires that the element x is a disjunctive element that does not satisfy condition (c) AND the element y is either a successor of, or is not ordered with respect to, all first model predecessors, AND either condition (e) or condition (f) is satisfied, wherein condition (e) requires that the element y is either a predecessor of, or is not ordered with respect to, all successors, and condition (f) requires that the element y is a conjunctive element that does not satisfy condition (e) AND the element x is either a predecessor of, or is not ordered with respect to, all successors; and 
 
 to operate in said first mode in a first pass of the insertion point identification process, and, if no insertion point is identified in the first pass, to operate in said second mode in a second pass of the insertion point identification process. 
 
     
     
         16 . A system according to  claim 12  wherein the control logic is adapted to process a partial order of the second model, stored in said memory and indicative of the sequence order of elements in the second model, to identify said predecessor and successor elements of the element t. 
     
     
         17 . A system according to  claim 16  wherein the second model is stored in the memory and wherein the control logic is adapted to analyze the second model to generate said partial order. 
     
     
         18 . A system according to  claim 12  wherein the control logic is adapted to perform the step of comparing the positions of the elements x, y and elements in the sets of first model predecessors and successors for every pair of adjacent elements x, y in the first model. 
     
     
         19 . A system according to  claim 12  wherein the control logic is adapted to analyze the first model to generate a partial order indicative of the sequence order of elements in that model, and to perform the step of comparing the positions of the elements x, y and elements in the sets of first model predecessors and successors by processing the partial order of the first model. 
     
     
         20 . A system according to  claim 12  wherein the control logic is adapted to:
 analyze the sequence order of elements in the sets of first model predecessors and successors to identify the sequentially-last first model predecessor and the sequentially-first first model successor; and 
 perform the step of comparing the positions of the elements x, y and elements in the sets of first model predecessors and successors by comparing the positions of the elements x, y with the positions of the sequentially-last first model predecessor and the sequentially-first first model successor. 
 
     
     
         21 . A system according to  claim 12  wherein the control logic is adapted to analyze the first model to detect unstructured cycles, and, if an unstructured cycle is detected, to apply a cycle removal operation to the model to transform the unstructured cycle to a structured cycle.