FORM -2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See Section 10 and rule 13)
MODERN DRIVEN ENVIRONMENTS
MODERN DRIVEN ENVIRONMENTS

TATA CONSULTANCY SERVICES LTD.,
an Indian Company of Nirmal Building, 9th floor, Nariman Point, Mumbai 400 021, Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION



This invention relates to modern driven environments.
In particular this invention relates to the process of change in modern driven environments,
Model driven architecture advocates using models as first class artifacts in the life-cycle management of software systems. It recommends that all aspects of a system be modeled and all life-cycle activities be controlled from a central model repository. This leads to a more disciplined approach to systems development and better control over change management. Owing to these benefits, the model driven approach is beginning to be adopted more and more in large enterprise systems environments. However, the sheer scale and diversity of systems that exists in a large enterprise can lead to scale-up problems, if the repository and the processes around it are not architected properly. The performance of various model processing operations such as model validation, diff/merge, model transformation, code generation, etc, tends to deteriorate with increasing model sizes. This in turn affects turn¬around times for change management. Ideally, in a change management scenario these operations should only consume times that are proportional to the size of the change and remain unaffected by the total size of the model. This is a hard problem however, because in general the programs that implement these operations do not have any underlying structure that can be easily analyzed for change impact ~ they are as hard to analyze in general as any arbitrary imperative program.
2

State of the art
In the prior art, componentization is the usual solution for better change management. The model workspace is divided into a number of 'logically coherent' components, and when there are changes only the containing components are reprocessed instead of the whole workspace. However, for many small changes - especially bug fixes, etc - even a component is a rather large unit for reprocessing. Also, components grow over time.
For certain operations such as model transformations, there are special purpose languages (e.g. OMG QVT) whose structure is inherently more suitable for incremental change propagation; however, there are no published techniques for how this can actually be implemented in a model driven environment.
This invention envisages a pattern based approach that can be used for implementing incremental execution of common model driven development processes, viz. model transformation, model comparison and merging, model validation, export and code generation.
This invention further envisages a model for recording changes that can be integrated into the model repository for efficient change processing.
Thus in accordance with this invention there is provided a model for recording changes in a model repository that facilitates efficient change management which has a pattern based approach for change propagation
3

and incremental execution of affected operations in a model driven environment.
Object Management Group is an industry consortium that defines interoperability standards. Meta Object Facility (MOF) is one such standard. MOF provides a generic model that can be used for modeling other models and meta models. A meta model is a model of a model. For instance corresponding to an UML model there exists an UML metamodel that specifies the structure and behaviour of the UML model; similarly corresponding to a relational database schema there exists a meta model that describes the structure of relational schemas. MOF provides a generic model for defining such meta models. Figure 1 of the accompanying drawings shows the salient features of the MOF model.
Essentially there are classes and objects; objects are instances of classes; a class specifies the structure of its instances by means of properties and associations; an object may have values for the properties specified by its class, and links with other objects as specified by the associations of the class.
A meta model (e.g. UML meta model, relational meta model, etc) is specified as an instance of the MOF model. Figure 2 of the accompanying drawings shows a slice of the relational meta model as an instance of the MOF model. In the figure, Table and Column are instances of the MOF model element Class; dataType and length are instances of the MOF model element Property; the association between Table and Column is an instance of the MOF model element Association.
4

Pattern model
A pattern is a graph of object nodes, their properties and associations. It is specified in terms of a meta model, as shown in figure 3 of the accompanying drawings.
A pattern node maps to a meta model class; properties of interest are specified by a set of property items (PProp in the figure) that map to the corresponding meta model properties; a pattern edge maps to a meta model association. A pattern has a root node (i.e., number of 'in' edges = 0). A pattern is essentially a connected, directed acyclic subgraph of the meta model graph. Given a model that conforms to the meta model, a pattern selects a set of matching subgraphs of the model.
Suppose in a UML model we are only interested in classes and their operations. This can be specified as a pattern as shown in figure 4 of the accompanying drawings..
Pattern based specification of model processing operations
Models are well structured graphs, and many model processing operations can be formulated in terms of graphs. Another observation is that most models are processed in clusters of related elements - for instance a class, its attributes and operations are usually processed together. Each such cluster has a primary element that identifies the cluster; for instance 'Class' in the above example. Patterns can be used to specify such clusters. The root of a pattern specifies the primary element of the cluster. We discuss how various model processing operations can be specified in terms of patterns:
5

Model transformation
OMG QVT relational language uses model patterns to specify transformation relations between models. A relation is specified as a condition that must hold between model elements that match specified model patterns over the respective models. A pattern is specified as a model graph over a meta model, with a root element. QVT's pattern model is similar to the pattern model discussed above and can be directly mapped to it. In execution terms, a QVT relation can be seen as being executed by invoking it repeatedly for each matching element of the root class of the pattern over the source model.
Diff/merge
Model comparison and merging can be specified in terms of model patterns. For example when we want to compare class models of two UML models, we want the comparison to be conducted on clusters of model elements centered around class objects; in pattern model terms we want to treat class as the primary object, with its attributes, operations and associations making up the rest of the connected elements of the cluster. In execution terms, a diff operation can be seen as being invoked repeatedly for each matching root element of the pattern from both the source and target models.
Model validation
Model validation is the process of verifying that a model satisfies all the constraints specified on its meta model. Model constraints are usually specified using OMG's OCL.
An OCL constraint has a context object and accesses other related objects starting from the context object. The context object and other related objects
6

that are relevant for the execution of a constraint can be abstracted into a model pattern (with a few enhancements to the notion of 'edge' to take care of exceptions where collections of unrelated objects are accessed), with the context object as the root of the pattern. In execution terms, model validation can be seen as repeated invocation of a constraint operation for each matching root element of the corresponding model pattern.
Model export
Model driven environments are characterized by purpose specific tool chains that process different parts of a model for different purposes such as analysis, code generation, etc. Typically the model fragments of interest are exported from the model repository and fed to the respective tool chain. Again, these tools view models in terms of well defined clusters centered on key objects, e.g. a class in a class model, a usecase in a usecase model, a state machine in a state transition model, a window in a GUI model, etc. So an export operation can be structured into subtasks that each exports a model cluster of interest ~ in other words each export subtask can be specified using a model pattern. In execution terms, an export task can be seen as being invoked repeatedly for each matching root element of the model pattern.
Tracking model changes
We present a model for recording model changes that occur in a model repository. We call this model a delta model. Figure 5 of the accompanying drawings shows the delta model.
7

A Delta is a record of a single change; it has a timestamp property that records the time of the change and an opCode property that records the operation causing the change, viz. one of ADD/MODIFY/DELETE. ObjectDelta records changes to objects; PropDelta records changes to properties; and AssocDelta records changes to associations. ObjectDelta has an association to Object to identify the object that has changed; it also stores the ID of the object (ID is required because that is the only way to identify an object that has been deleted from the repository). PropDelta has an association to Property to identify the property that has changed, and records two values - new and old (if any). AssociationDelta has an association to Association to identify the association that has changed, and two links to ObjectDelta corresponding to the two end objects. When a property or an association changes its owner object is also recorded as modified. The associations between ObjectDelta, PropDelta and AssocDelta mirror the associations between Class, Property and Association in the MOF model, and thus record the same structure. From the delta model one can retrieve all the changes that have occurred between two given timestamps, and easily figure out which specific objects have changed.
An algorithm to identify impacted model elements
This invention discloses an approach to compute the impacted root objects of a given model pattern from a given model and its delta model for the set of changes recorded in a given time period.
getlmpactedRootObjects step
Input: Model M, Delta model D, Pattern P, from-timestamp F, to-timestamp
T
8

Output: Set of object IDs of the impacted root objects of pattern P Begin
Let h be the height of P (i.e. the length of the max path from the root to any
node in P).
Let Nk (0 <= k <= h) be the set of nodes that are at length k from the root
node.
Since P is a DAG, there can be nodes that have multiple paths from the root,
and so at multiple lengths from the root. Such nodes are included in multiple
Nk (0 <= k <= h).
Let Ok (0 <= k <= h) stand for the set of IDs of objects corresponding to the
class nodes in Nk that have been identified as impacted due to changes
recorded in the delta model D.
Initialize Ok (0 <= k <= h) to NULL (i.e. empty set).
Main body:
for (i = h; i >= 0; i«)
{
for each n € Nt
{
CO = getChangedObjects(n, D, F, T);
Oi — Oi U CO; // set union will remove duplicates if any
}
if (i > 0)
{
for each o ε 0,
9

C = node in Nt corresponding to the class of object o\ II C may belong to multiple Nk (0 <= k <= h) due to

for eachy ε[0..h] such that CεNj
{
A = the set of associations of edges from nodes in

For each a ε A
{
AO = getAssociatedObjects(o, a, M, D, F,
T);
Oj = Oj U AO; // set union removes
duplicates
} } }
Free O1 //i.e. release the storage, because O1 is not needed after this step;
} }
// At this point O0 will have all the impacted root objects
return O0
End.
10

getChangedObjects step
Input: Pattern node n, Delta model D, from-timestamp F, to-timestamp T Output: Set of IDs of changed objects corresponding to node n. Begin
OS = select the set of object deltas whose timestamp falls between F and T; PS = set of property items specified with the pattern node n; if (PS is empty)
return OS.objectID; //i.e. the set of IDs extracted from each object delta in OS
DS = o Ε OS whose opCode is DELETE; //i.e. DS is the set of deleted
objects
RS = OS-DS;
CS = set of objects oεRS that have, for at least one property P Ε PS, at least one property delta falling between F and T;
FS = CSUDS;
return FS.objectID; //i.e. the set of IDs extracted from each object delta in
FS
End.
getAssociatedObjects step
Input: Object ID o, Association a, Model M, Delta model D, from-timestamp F, to-timestamp T.
11

Output: Set of IDs of objects that had (before the change) or currently have
association a with object o.
Begin
if o has a delta object between F and T with opCode = DELETE //i.e. o is a deleted object
{
// o's associations if any must have been deleted and recorded in AssocDelta
AS = set of association deltas corresponding to association 'a' that
have one end as o and opCode as DELETE;
AO = object deltas that are at the other end of the association deltas in
AS;
return AO.objectID; //i.e. the set of IDs extracted from each object
delta in AO
}
// Get the objects that currently have associations with o in model M. CO = set of objects in model M that have association a with object oII Get the objects that previously (before the current time frame) had
associations with o.
AS = set of association deltas corresponding to association 'a' that have one
end as o and opCode as DELETE;
PO = object deltas that are at the other end of the association deltas in AS;
FS = CO U PO;
12

return FS.objectID; //i.e. the set of IDs extracted from each object delta in
FS
End.
Ch ange propagation
Many of the common model processing operations can be specified in terms of model patterns along the lines discussed in this invention. These operations can be designed to record the results of their initial execution. These results can then be incrementally updated in subsequent change propagation cycles by executing the affected operations on affected model elements. A change propagation cycle has a start time and an end time, and the end-time of one cycle becomes the start-time of the next cycle. For an operation of interest, we take the corresponding model pattern and use the method given herein above to identify the impacted root objects and invoke the relevant tasks on these root objects.
Advantages of the method in accordance with this invention
The proposed approach provides a scaleable solution that greatly improves the performance of various model processing operations. These operations can be performed in times that are proportional to the change size rather than the absolute model size, greatly reducing turn-around times for change management.
The proposed delta model can also be used in efficient version store implementations. Only the delta model needs to be stored between two
13

consecutive versions. The delta model facilitates efficient implementation of version comparison and merging operations.
Thus in accordance with this invention there is provided a model for recording changes in a model repository that facilitates efficient change management which has a pattern based approach for change propagation and incremental execution of affected operations in a model driven environment.
Although the invention has been described in terms of particular embodiments and applications, one of ordinary skill in the art, in light of this teaching, can generate additional embodiments and modifications without departing from the spirit of or exceeding the scope of the chained invention. Accordingly, it is to be understood that the drawings and descriptions herein are offered by way of example to facilitate comprehension of the invention and should not be construed to limit the scope thereof.
Dated this 25thday of September 2008.

14