New Strategies to Resolve Inconsistencies between Models of Decoupled Tools Anne-Thérèse Körtgen Department of Software Engineering RWTH Aachen University Aachen, Germany koertgen@se-rwth.de ABSTRACT Development processes in engineering disciplines tend to be Maintaining consistency between models in development pro- highly complex. As a result, the product to be developed cesses is a challenging task. Though in software engineering needs to be modeled from multiple interdependent perspec- many case tools exist which allow the editing of models and tives and on different levels of abstraction. The results of de- include code generators for reverse or round trip engineer- velopment activities like requirements definitions, software ing, the source code is edited with specialized development architectures, or implementations in software engineering environments. The same holds for other models, such as re- are stored in models. Different models may overlap, so when quirements specifications or architectures. The editing tools they are edited independently, they may impose constraints are often decoupled from each other. Additionally, modifi- on the system to be developed which are not satisfiable any cations of the models are performed simultaneously. more. Models are then said to be inconsistent to each other [29]. The task is to maintain the inter-model consistency In this paper, we introduce strategies to resolve inconsisten- after editing. cies by so-called repair actions. The novelty of the strategies is that they specify different concurrent ways of coming to In literature consistency maintenance of models are also a consistent state, not knowing anything about the mod- called inconsistency management [8] or model synchroniza- ifications a user had applied. Concrete repair actions are tion [11] and involves the following tasks [23]: (i) consistency derived at runtime based on the consistency rules and the of dependent models must be checked, (ii) inconsistencies inconsistent parts of the models only. The maintenance tool must be categorized, and (iii) inconsistencies must be han- can maintain additional models’ consistency without devel- dled, i.e. resolved, ignored, or identified only. Reestablishing oping specialized repair actions. One new strategy proposed consistency is also called reconcilation [28]. in this paper in contrast to other approaches is to heal the violated consistency rule or try a similar one. Usually, valid statements within model overlappings are for- malized by consistency rules [23]. For example, a consis- tency rule declares that for each class definition in a UML Categories and Subject Descriptors class diagram a corresponding class definition must exist in D.2.2 [Software Engineering]: Design Tools and Tech- the source code. If a class exists in the diagram but not in niques—Computer-aided software engineering (CASE); D.2.7 the source code, then the consistency rule is violated. With [Software Engineering]: Distribution, Maintenance, and the specification of consistency rules dependencies between Enhancement—Corrections, Version control ; D.2.12 [Soft- two or more models are therefore also specified. Thus, when ware Engineering]: Interoperability—Data mapping, Dis- one model is changed and a consistency rule is violated, tributed objects; K.6.3 [Management of Computing and then consistency can be reestablished by changing depen- Information Systems]: Software Management—Software dent models analogously (propagation). Development Many approaches face the problem of inconsistencies by of- Keywords fering one integrated case tool which performs the tasks of Inconsistency Management, Model Synchronization, Incre- inconsistency management by direct propagation of changes mental Transformation, Model-driven Development to dependent models such as e.g., EclipseUML [25] or Ra- tional Software Delivery Platform [19]. But often there are 1. INTRODUCTION several reasons why changes cannot be propagated directly to depending models: (i) when different specialized hetero- geneous tools for a task are used or (ii) when developers are distributed and edit different copies in parallel, so that an integrated tool cannot observe incremental changes. Version control systems cannot be used after parallel editing of the models when dealing with graphical models [9], espe- cially if they are stored within binary data: If they are stored as text files, changes cause often an overall rearrangement 21 of the text lines. Model transformation approaches [32, 4] tures, the modeling of consistency rules, and the definition transform a source model into a target model. Mostly, these of consistency in this setting. In Section 4, the strategies transformations work batch-wise, i.e., a target model is gen- for finding and resolving category 2 inconsistencies are pre- erated completely from a source model, thus, changes on the sented. Section 5 describes shortly the implementation of target model get overridden. the maintenance tool and the resolving strategies. Related work is discussed in Section 6 and, finally, Section 7 con- Therefore, consistency maintenance should resolve an incon- cludes the paper. sistency by propagation of changes on one model to depend- ing models incrementally and bidirectionally. Incrementality 2. SCENARIO means that only local changes are made in a model to handle While the underlying concepts of the maintenance tools are one inconsistency so that other changes on the model which fairly general and domain-independent, we focus on software were done in the meantime are not overwritten. Also incon- engineering and introduce a sample scenario where UML sistency resolution should be made only on request, meaning class diagrams and source code are maintained consistent. that inconsistencies must be tolerated [23]. For example, the For designing the structure of a system, UML class diagrams user’s changes on a model create inconsistencies but the edit- are well-suited as they abstract from the implementation ing process should not be interrupted, thus, resolving has to details of the system and they are part of static structure wait until the end of the editing process. As an additional diagrams in the UML. Heterogeneous tools may be used for requirement, interaction with the user is required when res- creating UML class diagrams and source code, respectively. olution is ambiguous. In the following, we assume that the UML class diagrams are maintained by Eclipse [31] and source code is edited Triple graph grammars (TGG) [27] were developed for han- in Visual Studio [20]. We chose to use these applications dling consistency maintenance problems of two models which for our case study because they were successfully used in are modeled as graphs. The idea is to store fine-grained many software projects as modeling tool as well as integrated n : m-relationships in a correspondence graph between a software development environment and they are very widely source and a target graph and to specify analogous oper- known. ations on the three models in so-called triple rules. By applying triple rules, we may modify coupled models syn- Figure 1 illustrates how the tool assists in maintaining con- chronously, taking their mutual relationships into account. sistency when changes are made simultaneously. Three dif- But also the operations on one model can be performed inde- ferent versions of the sample UML class diagram and the pendently and based on the triple rule specification one can corresponding Visual Studio (VS) object model are shown maintain consistency by applying the corresponding opera- above and below the dashed line, respectively. The tool tions on the other model. TGG approaches basically work maintains a data structure which contains links for connect- incrementally and bidirectionally. ing the two models. These links are represented by ellipses which are located on the dashed line. Dotted lines are used A problem is that triple rules need to be monotone, i.e. to indicate the objects participating in a link1 . The connec- they only produce new nodes and edges and are not allowed tions of a link to objects in both models base on template to delete any. Thus, only inconsistencies caused by addi- specifications for corresponding object patterns, e.g. that tion of new nodes in one of the models can be resolved by UML classes correspond to code classes, UML associations transforming them into the dependent model (by applying correspond to attributes in the code owned by corresponding remaining operations of a triple rule). We would like to call classes, or UML methods correspond to code methods also inconsistencies of that kind category 1 inconsistencies. But both owned by corresponding classes. Furthermore, arrows modifications on one of the models may affect nodes which located on the right indicate the directions of change prop- are related to nodes of the other model. It can then happen agations (structural and attribute changes, respectively). that the relationship defined by the triple rule which was The figure illustrates a re-design process consisting of three applied before is not present any more. We would like to steps described in the following. call inconsistencies of that kind category 2 inconsistencies. Initially, the VS object model and the corresponding UML In this paper, we introduce strategies to resolve category class diagram are consistent to each other, thus, links al- 2 inconsistencies by so-called repair actions. The novelty ready exist between the objects (see left version in the fig- of the strategies is that they specify different concurrent ure). They each contain the classes Control and DataAcces- ways of coming to a consistent state, not knowing anything sObject and the methods getDBItem and getFileItem which about the modifications a user had applied. Concrete re- are elements of latter class. The association data is rep- pair actions are derived at runtime based on the consistency resented in the object model as attribute referencing the rules and the inconsistent parts of the models only. The corresponding class object as type. maintenance tool can maintain additional models’ consis- tency without developing specialized repair actions. One Secondly, both models are edited simultaneously (see mid- new strategy proposed in this paper in contrast to other dle version in the figure). Changes are marked with new approaches is to heal the violated consistency rule or try a or * in the figure for newly added objects or changed ob- similar one. jects, respectively. To the VS object model only the helping function helper is added. To the class diagram two further This paper is structured as follows: Section 2 presents a 1 scenario where the maintenance tool is applied. Section 3 Please note that this is a simplified notation. Some details introduces some basic concepts of the underlying data struc- of the link data structure introduced later are omitted and also not every link is shown. 22 1.) state= consistent 2.) state= inconsistent 3.) state= consistent UML Class Diagram data DataAccessObject data data DataAccessObject Control Control DataAccessObject Control +getDBItem() +getItem() +getItem() new +getFileItem() +helper() new User changes new new DBAcces FileAcces DBAcces FileAccess +getItem() +getItem() Tool changes +getItem() +getItem() * * L L L L L L L L L L L L L L L L L L L new new new new Control DataAccessObject Control DataAccessObject Control DataAccessObject :CodeClass :CodeClass :CodeClass :CodeClass :CodeClass :CodeClass User changes Type Type Type Attribute Child Attribute Child Attribute Child new data getDBItem data getDBItem data getItem :CodeAttribute :CodeFunction :CodeAttribute :CodeFunction :CodeAttribute :CodeFunction Child Child Child getFileItem getFileItem helper :CodeFunction :CodeFunction Base :CodeFunction Child Base new helpernew new DBAccess FileAccess :CodeFunction :CodeClass :CodeClass Visual Studio Object Model Child Child Propagation of Propagation of getItem * getItem * :CodeFunction :CodeFunction structure attributes Figure 1: Recovering consistency between design and implementation classes DBAccess and FileAccess are added and the meth- Also, inter-model relationships can be expressed easily with ods of their super class are distributed among these classes. nodes and edges referencing related nodes of the graphs. As Additionally, the method names are generalized to getItem. another advantage we can use the theory of graph transfor- The models are now inconsistent but the links still exist. mations to define modifications on the graphs. In the follow- We see that inconsistencies caused by newly added objects ing, the data structures, construction of consistency rules, are category 1 inconsistencies while those caused by changed and the notion of consistency in this setting are presented. objects are category 2 inconsistencies. Finally, the maintenance tool is used to synchronize the par- 3.1 Models as Triple Graphs allel work which results in the right versions of the models For using TGG in complex scenarios where two dependent in the figure. The newly added objects are added to the re- models are edited by different tools we create graphs from spective other model. The category 2 inconsistencies within these models (via tool wrappers) and denote one as source the methods correspondence relation are the non-valid at- and the other as target model. Operations on the models tribute condition, i.e. the method names are not equal, and performed by the respective tools are represented as graph the owning classes of the UML and code methods do not transformations. The data structure storing links between correspond to each other, respectively. To resolve the incon- inter-dependent models is called integration document which sistencies the name change in the UML model is propagated is also modeled as graph.The framework creates an inte- to the code model and the shift of the methods to different grated graph consisting of the three graphs to simplify spec- classes in the UML model results in rearrangement of the ref- ification of the triple rules and their application. erences between the class and method objects. What we see here is, that the basic template specification of correspond- In the following, we want to use UML object diagrams to ing methods are still valid. Please note that there might be represent typed graphs and to model triple rules as well. compile errors in the source code after the synchronization. The graph schemes, therefore, are modeled as UML class diagrams. To be able to model integration scenarios, we The example presented above demonstrates the functional- provide an extension of the UML meta-model [3] by stereo- ity of the maintenance tool, but it does not show how this types. To illustrate the graph modeling, we use the example is achieved. In the next sections, the underlying conceptual in Figure 2 which shows the graph representation of the approach is presented. The implementation is introduced in UML class diagram, the VS Object model, and the integra- Section 5. tion document from the left situation of Figure 1 with only one method object. 3. CONCEPTS OF THE APPROACH To model source and target graphs we use the stereotypes In our approach, we use typed, directed graphs to represent Increment for nodes and Incr2Incr for edges. Source and tar- the models between which relationships exist. Graphs con- get graphs have an underlying graph scheme equivalent to sisting of nodes and edges are well suited for representing the respective models’s meta-models. This means the graph complex data with manifold relationships in a natural way. schemes of UML class diagrams and source code which we 23 Association2Attribute_Triple_Rule :: LHS as UML OD <> <> <> <> <> Control : Class : ClassLink Control : Class <> <> <> <> <> : Class : ClassLink : Class <> ownedAttribute <> <> <> <> : Property ownedAttribute <> <> <> <> <> <> : Class : ClassLink : Class association <> <> <> <> <> ::= data : : AssocLink data : Property RHS as UML OD Association <> <> <> <> <> <> memberEnd : Class : ClassLink : Class <> <> <> : Property type ownedAttribute <> <> <> <> <> <> class <> : Property ownedAttribute <> <> <> <> <> <> DataAcessObj: DataAccessObj association : ClassLink Class : Class <> <> <> <> <> a : Association : AssocLink b : Property <> <> <> <> ownedOperation ownedOperation <> memberEnd a.Name == b.Name <> <> <> <> <> <> <> <> type getDBItem : getDBItem : : Property <> :MethodLink Operation Operation <> class Source Target Integration Document <> <> <> <> <> (UML Class Diagram) (Source Code) : Class : ClassLink : Class Figure 2: Triple graph as UML object diagram Source Integration Document Target (UML Class Diagram) (Source Code) Figure 3: Triple rule (synchronous) creating an asso- want to maintain consistent do not differ much from the ciation a in a UML class diagram (left) and a corre- meta-model of UML class diagrams specified by the OMG sponding attribute b with the same name in a source in [24]. This makes sense, since they both reflect the struc- code (right) ture of the system. In general, the graph schemes of the models are different. The tool wrappers realize the concrete type mapping, that is for example the concept of a Class instance in the graph representation of the UML model is As mentioned, the connections of a link to objects in both mapped to an Ecore Class and that of the VS Object Model graphs base on template specifications for corresponding is mapped to an instance of the type CodeClass. In Fig- graph patterns. These are defined in triple rules which are ure 2, we see that source and target graph contain objects also modeled as object diagrams. To give an example, the of concepts of the UML meta-model. triple rule which defines the connection pattern of the asso- ciation link from Figure 2 is shown in Figure 3. The integration document objects use the stereotype Link to mark the links. Links refer to increments in source or tar- The triple rule defines in the first place how to relate two get model via UMLLinks (instances of associations). The classes within a UML class diagram with an association increments have to be distinguished according to the graphs (source) and to simultaneously add in the source code (tar- they are contained in, either source or target graph. There- get) an attribute to the class corresponding to the associa- fore, stereotypes for UMLLinks from links to increments ap- tion’s source class whose type is of the class corresponding pear twice, one for increments of the source and one for to association’s target class. increments of the target graph. This is indicated by suf- fixes SrcIncr and TrgIncr of the stereotypes’ names. Depen- The left-hand-side (LHS) of the rule is shown above and dent on whether the increments play the role of a normal specifies that the two classes in each model already exist and or context increment, they are connected to a link via UM- are related to each other via links in the integration docu- LLinks with stereotype toSrcIncr, toTrgIncr, toConSrcIncr, or ment. The right-hand-side (RHS) shown below specifies the toConTrgIncr respectively. Increments may play the role of situation after the rule has been applied meaning that the so called context increments for a link when they define some association in the source graph, the attribute in the target kind of existent-dependency for a link, i.e. a link relates in- graph, the link in the integration document mapping both crements only if the context increments are connected to onto each other, and the edges embedding these increments these increments within the models. in the existing graphs are created. This triple rule also spec- ifies an attribute equation shown in the comment attached to The integration document also has an underlying graph the new link. It states that the increments a and b have the scheme which models the link types and how they are related same names. The RHS is the template which declaratively to classes of source and target graph schemes. In Figure 2, specifies the connection pattern for a consistent link. we see that links of type ClassLink and AssocLink are rep- resented which are used to relate classes or associations in A rule can also specify restrictions on attributes of the incre- both models. In this example, the association (source) is ments, for example the name of a class aClass could be re- mapped to a property (target). stricted by aClass == ’User’. If the restrictions or equations appear on the LHS they restrict graph pattern matching 3.2 Consistency Rules as Triple Rules allowing only those increments to be matched which fulfill 24 these constraints. If they appear on the RHS, the constraints 4. INCONSISTENCY MANAGEMENT have to be fulfilled in any case. When there is no value spec- Our tool performs the three tasks mentioned in [23]. In this ified within the rule such as in the triple rule shown above, section, we only present the check and resolving strategies a dialog is prompted to enter a value. for category 2 inconsistencies. A detailed description of the consistency check and resolution of category 1 inconsisten- Operation2Operation_Triple_Rule :: cies can be found in [2]. LHS as UML OD <> <> <> <> : Class : ClassLink <> : Class The main issues we are dealing with are that we cannot record the changes an external tool performs on a model and ::= also that we cannot assume that a rule modeler specified RHS as UML OD <> <> for each operation on a model an equivalent operation on <> <> <> : Class : ClassLink : Class a dependent model. So, instead of parsing the graph and <> <> <> <> finding out the operations which were performed on a model ownedOperation ownedOperation and to perform equivalent operations on a dependent model, <> <> <> <> <> we decided to take only the already available triple rules into a : Operation :MethodLink b : Operation account and those parts in the model which make a triple a.Name == b.Name rule inconsistent. Source Target (UML Class Diagram) Integration Document (Source Code) It is so, that a triple rule specifies declaratively in its RHS the correspondences of two patterns in source and target graph. Thus, if the rule is applied, there exist instances of Figure 4: Triple rule (synchronous) creating an op- these patterns (subgraphs) in source and target graph and a eration a in a UML class diagram (left) and a corre- link exists in the integration document referencing the nodes sponding operation b with the same name in a source of these subgraphs. An inconsistency according to a triple code (right) rule is, therefore, that the patterns do not match anymore or that attribute conditions are violated. Thus, resolution means to maintain the graphs so that a link referring to As a further example, Figure 4 shows the triple rule which is nodes in source and target graphs is valid according to an applied in the scenario for creating the methods getDBItem RHS of any triple rule, not necessarily the one which was and getFileItem in source and target graph and the links formerly applied. between them. It is important to note that a repair action is allowed to Please note: if asynchronous rules are derived from triple change only nodes and edges that were originally created by rules which have equations, attribute values are transferred the applied rule. That does not hold for context increments. into the other model. For example, the forward transforma- Therefore, a repair action never causes new inconsistencies tion of the triple rule shown above sets the attribute’s name for links referenced as context. But of course, other links to the association name (b.name := a.name), vice versa for having a repaired link in their contexts could be damaged. the backward transformation (a.name := b.name). 4.1 Inconsistency Check (Category 2) 3.3 Definition of Consistency For existing links we check if there were modifications on TGG base on Pair Graph Grammars (PGG) [26]. Pratt de- their referenced increments by doing pattern matching using fined consistency of two graphs based on pair rules: ”Two the RHS of the triple rules applied before. Each link in graphs are consistent iff both graphs can be created by syn- the integration document has an associated state. When a chronously applying corresponding graph grammar rules on link has been newly created by applying a rule, its state is corresponding nodes.” initially set to consistent. In the analysis, for each link it is checked whether increments originally referenced by the link Of course in real life scenarios a rule modeler has to model are still present in source and target graphs. If the RHS of the triple rules for two models edited by (as a general rule) the triple rule does not match any more due to modifications commercial tools and so it cannot be assumed that he spec- of source or target graphs, the state of the link is changed ifies the complete TGG covering each possible change a tool to damaged. For handling the inconsistency all reasons why can make on one of its models and relates it to changes the the link got damaged are collected during analysis. Here, all other tool should make so that the models remain consis- possibilities for a link to be damaged are listed: tent. One can assume that the tools create valid models according to the models’ meta-models so that inner-model Increments deleted Increments of the source or target consistency must not be checked. graph which take part in a link have been deleted, result- ing in dangling references of the link. As an example, an Although in practice we do not have a complete TGG we attribute of a class could have been deleted. can keep the definition of consistency of Pratt. We only regard those structures in the models which can be created Attribute values changed Attribute values of source or by one of the triple rules. Other increments are ignored; target increments of a link have been changed so that at- they also do not make the models inconsistent as there is tribute conditions do not hold any more. This would be no triple rule that would define corresponding increments in the case if the attribute of a class in the source code has the other model. been renamed resulting in an inconsistency of the Associa- 25 tion2Attribute-rule because the name of the corresponding Another option is to restore consistency by removing the association in the UML class diagram of that attribute and cause for the inconsistency. For instance, missing incre- the attribute’s name are no longer equal. ments or edges may be created. This option is desirable only in those cases where the operation causing the damage Edges deleted Edges of the source or target graph being was carried out accidentally, because it would be undone. involved in a link have been deleted, so that the patterns on For attribute values, the attribute conditions of the triple both sides are no longer valid. For example, an attribute of rule can be used to propagate the change. a class in the source code has got another type so that the edge typeRef from the attribute to the old type is deleted. 4.2.4 Define new rule This is a trivial solution to handle a damage as for the new Context damaged If a link gets damaged all links referring situation a rule is defined (induced) and attached to the link. to it as context get damaged, too. For example, a link L1 mapping an association onto an attribute refers to two links as context links, i.e. those links mapping two classes in each 4.2.5 Conserve the applied rule graph onto each other. If one of those links gets damaged, As the alternatives to repair inconsistencies presented so far L1 is damaged, too. are not very useful from the practical point of view, more specific repair types [16] based on knowledge about the origi- nal rules which created the links have to be considered. The 4.2 Resolution of Inconsistencies (Category 2) main priority when repairing links is to conserve the rule We now present what can be done in general if damaged that has been originally applied to create the link or to find links have been found and list in the following sections graph a similar one doing only small adaptations (see below). transformation strategies. We call these strategies repair types because we create concrete instances from these strate- Conserving the applied rule in general means to create a gies, repair actions, to repair a concrete damaged link with situation where the damaged link refers to increments in specific damages. Applied to a damaged link, a repair action source and target graphs so that all required conditions of brings the link back to a consistent state which means that that rule including graph pattern matching are fulfilled. As it resolves the inconsistency. there can be multiple reasons for a link to get damaged each single damage has to be healed when trying to conserve the 4.2.1 Delete all increments involved applied rule. We present in the following sub-strategies to The most primitive procedure is to delete the link and all heal a single occurrence of a damage of the same type, e.g. if the increments on both sides, which are involved in the in- an increment is missing, then a strategy/action is to replace tegration situation. It is obvious that this is suitable only in it. If multiple increments are missing, then there are actions situations where all increments of a link have been deleted for each increment to replace it. Of course all occurrences of by the user in one of the graphs or where one of the main all damage types must be healed which results in building increments has been deleted. If some increments of a link in actions of the same and different sub-strategies. one of the graphs are deleted and others still exist, the dele- tion could have been part of a restructuring activity, thus, A repair can be done by changing or not changing source deleting all increments is not the reaction the user expected. and target graphs. Not changing means that only references Still, it is a valid repair strategy, but one which should never within the integration document are adapted assuming that be executed without prompting the user before. the user established a consistent state by himself. So, con- serving the applied rule strategy exists in two variants. We explain what has to be addressed when a rule should be con- 4.2.2 Remove the link and integrate again served with and without doing any changes on the graphs. The next simple possibility is to only delete the damaged link and to leave the increments on both sides unchanged and to Conserve the applied rule (changing): make them available for other transformation rules. Most of the time this also does not lead to the desired behavior of the tool. The modifications resulting in the damaged • Create increment If an increment is deleted it can link were probably done on purpose. The link, although be recreated, thus, this (single) damage is removed, re- damaged, may contain valuable information to be used, most sulting in an undo-like operation of the user’s changes. importantly, to determine which parts of the graphs may be Note, this is not a real undo such as in the Undo affected by the modification which damaged the link. For changes repair type, because attribute values of the example, in the scenario the Operation2Operation rule from recreated increment are not reestablished as before the Figure 4 had been applied and the user rerouted the method deletion of the increment. getDBItem from the class DataAccessObject to another class DBAccess, then the rule did not match anymore. The edge • Create edge If an edge is deleted it can be recreated ownedOperation from the class DataAccessObject is missing. as above. This also is not a real undo, because an edge But instead of deleting the link and all references the desired which was deleted due to the deletion of an incident repair action is to reroute the ownedOperation reference of increment which is not part of the rule pattern is not the corresponding method in the source code from the class recreated by this repair. DataAccessObject to the class DBAccess. • Propagate attribute value If an attribute value chan- ged so that the condition of an attribute equation of 4.2.3 Undo changes of the user the applied rule does not hold, this repair type changes 26 attribute values so that the violated attribute equa- incident increments or both are replaced with alter- tions hold again. For example, in the scenario of Fig- natives which exist in the graphs if they are not used ure 1 the rule which maps two methods onto each other by another link. As for the alternative increment re- is applied two times. It states that methods a from the pair type (see above) these increments have to fulfill source and b from the target graph referred by a link all requirements of the rule. must have the same names, here getDBItem and get- FileItem. The user afterwards changed both methods’ • Include alternative context This repair type is equal names in the UML model having the role of method a to the changing version (see above) not being allowed to getItem, there are two possible actions: (i) b.name to do any change on the graphs. Thus, a valid context := a.name or (ii) a.name := b.name. The first would is included only if it is already connected as required correspond to a propagation but the system is not able to the non-context part of the link. to determine which value (that of a or b) had changed by the user, so it suggests both alternatives. 4.2.6 Apply a similar rule The following repair types do not conserve the originally • Change attribute value according to restriction applied rule but substitute it with a similar one. If an attribute value is changed so that the condition of an attribute restriction is violated, this repair changes Apply a subset rule (changing): A triple rule is a subset the attribute value so that the violated attribute re- rule of another triple rule if its RHS is a subset of the RHS striction holds again. For example, if the restriction of the other rule. If an applied rule is inconsistent, one can is aClass.name == ’User’ and aClass.name differs from try to look for a subset rule which is still consistent in the this value, then the action aClass.name := ’User’ is pro- given situation. The applicability of a subset rule is likely as posed. If the restriction is a.card < 10 and a.card is a subset rule has less conditions which may not have been greater than 10, then the action a.card := 10 - 0,1 is affected by the modifications of the user. If there exists such proposed, where it must be said that the percentage a subset rule which is not damaged, then increments which which is additionally subtracted can be configured by not appear in the subset rule but by the damaged rule are the user. Note that, for a greater than (>) relation, a deleted. The situation after the repair is as if the subset rule percentage is added up. had been applied. • Include alternative context If increments and edges of the context of a damaged link are missing, this re- Apply another rule from the same rule group (chang- pair type adapts references in the integration docu- ing): Two rules are in the same rule group if they are am- ment from the damaged link to existing increments and biguous for a pattern in a graph which means the pattern edges in source or target graph (in one step) to make can be represented in a dependent graph in two ways. If an the context valid again for the damaged link. Nev- applied rule is damaged it is likely to look for an alternative ertheless, the repair type is allowed to reassign edges rule of the same rule group which is applicable and only from the non-context increments to the new context so do little adaptations to the graph; in case that some pre- that finally changes in the graphs are made. This re- conditions for applicability of the rule are not fulfilled, their pair is applied twice in the scenario of Figure 1 where validity can be enforced with small changes on the graph. the method links first refer to the same context incre- For example, required nodes and edges for the application ment DataAccessObject in the source code and after the of a different rule can be created and nodes and edges of the repair to the alternative context increments DBAccess formerly applied rule which are not used by the alternative and FileAccess, respectively. rule can be deleted. Apply another rule from the same rule group (not Conserve the applied rule (not changing): Not doing changing): The same is possible without doing any changes any changes on the graphs but to heal each single damage is on the graphs. only possible for deleted increments and edges as they can be replaced with already existing increments and edges by Apply another rule keeping the main increments: adapting the references in the integration document. Vi- Like alternative rule repair, this repair action searches for olated attribute conditions cannot be reestablished as this another possible rule which can be applied. But instead of would mean to change at least one value in the graphs. taking the whole pattern into account, it just searches for source and target main increments, as a minimal require- ment for an alternative rule application if they still exist. • Include alternative increment A deleted increment can be replaced by an alternative increment which ex- ists in the respective graph if it is not used by another 5. IMPLEMENTATION link. This increment must fulfill all conditions stated The strategies are implemented in a framework which was in the triple rule, as for example attribute restrictions built within the IMPROVE project (1997-2009) [21] at RWTH or connections to other increments via edges. Aachen University to rapidly construct consistency mainte- nance tools [17] for specific models and editing tools. • Include alternative edge A deleted edge is only a cause for a damage if its two incident increments still The framework works tool- and model-independent on a exist. If not, then this damage is handled by alter- generic graph-based data structure; the model editing tools native increment (see above). To find an alternative are plugged in the framework by using wrappers which pro- edge for the deleted one means that either one of the vide the required graph views on the models to the frame- 27 work. Triple rules also base on the generic data structure and have to be defined for each pair of models to main- 1 List AlternativeNode(List< tain consistently. Parameterized by the rules the framework RepairAction> ras, Pattern is able to check, to categorize, and to maintain the consis- rsPattern, Pattern dmgPattern) { tency incrementally, bidirectionally, and with the work of [2, 2 List retRas = ras; 1] they operate interactively. 3 foreach (RepairAction ra in ras) 4 Pattern search = ra.GetSearchPattern(); For concrete models specific repair actions (i.e. graph trans- 5 Pattern create = ra.GetCreatePattern(); formations) for a damaged link are constructed after the 6 foreach(PatternNode patNode in damage check at runtime. The repair actions represent al- rsPattern.GetNodes()) ternatives to make the link consistent again. They can be 7 if(dmgPattern.ContainsKey(patNode) && selected and prioritized so that the framework can be em- !rsPattern.IsContext(patNode)) { ployed for various models and various phases of the develop- 8 //search alt. nodes ment process with different requirements on resolution. We 9 search.AddNode(patNode); focus on the implementation of repair actions here, how they 10 //Edges of alt. nodes are built and executed. 11 foreach (PatternEdge edge in rsPattern.GetEdges(patNode)) A repair action is a concrete instance of a repair strategy 12 if(!IntDocEdgeTypes.ContainsKey(edge for a category 2 inconsistency of a damaged link realized as .type)) graph transformation with a LHS and a RHS. The LHS and 13 //search in model RHS of a repair action are modeled with Pattern objects 14 search.AddEdge(edge); which can be then interpreted at runtime by methods for 15 else pattern search and transformation by a graph transforma- 16 //create in Int.Doc. tion engine. 17 create.AddEdge(edge); 18 } 19 return retRas; «adt» match, RepairAction search. 20 } repairActions create, -name delete, -repairType change Figure 6: Creation of the repair action for searching «adt» for alternative nodes (simplified, in C#) «adt» GraphPatternHandling::Pattern Rule -nodes -conflicts -edges When repair actions are constructed it is not known if they «adt» really are applicable, i.e. if the search pattern has a match in RepairOption create, the graph. If a match is found, then a RepairOption object repairOptions -name delete, is created which denotes a really applicable repair action. -repairType change -matching All options are offered to the user. For each match of the -conflicts search pattern found by the graph pattern search engine, the search pattern is enhanced with concrete matching node and edges ids of the graph and is now part of one RepairOption Figure 5: Data structure to store repair actions and as matching. The repair option only references create, delete, options in the integration document and change patterns of the corresponding repair action. To construct a repair action for conserving the originally ap- plied rule, the patterns are extended step-wise according to Figure 5 presents the data structure to store repair actions the sub strategies. For example, the enhancement to search in the integration document. We need store this informa- for an alternative context bases on the patterns which are tion there because of the interactivity of the tool. A user enhanced with pattern nodes and edges to search for alter- can select among multiple options and can stop the tool native nodes. Repair actions without sub strategies can be during consistency maintenance. The class Rule models the constructed independently in one step and retrieve the pat- application of a triple rule and is connected to the respective tern of the rule which is still intact, the remainder pattern. link it has created. If a rule pattern no longer matches, a set of RepairAction and RepairOption objects are created for To demonstrate how repair actions are created we present as that rule. A RepairAction contains multiple Pattern objects: examples the implementation of the alternative nodes and one is searched (search), one models the remaining match- context sub strategies. The methods describe how the differ- ing subgraph (match), one defines the subgraph which is ent pattern objects are enhanced to match alternative nodes going to create (create), one models the pattern of the sub- and an alternative context and replace the missing nodes and graph to be deleted (delete), and one specifies the pattern damaged context of a link. of the subgraph to be changed (change). We can say that the search, match, delete, and change patterns form the LHS Figure 6 shows the method which retrieves as input parame- and the the search, match, create, and change patterns form ters a list2 of already created repair actions ras, the pattern the RHS. When repair actions are created pattern nodes and 2 edges must be added to the respective Pattern objects. Please note that creation of alternative edge repair is done 28 of the rule rsPattern, and a damage pattern dmgPattern. The damage pattern contains the missing nodes and edges as well as those nodes which violate attribute conditions or restrictions. In this method, all repair actions of ras are ex- tended. Alternative nodes and edges for the missing nodes 1 List AlternativeContext_c( and their incident edges are searched, i.e. they are added to List ras, Pattern the search pattern (lines 8 to 14). When the current repair rsPattern, Pattern dmgPattern) { action is applied all edges from the integration document to 2 List retRas = ras; the alternative nodes are created, i.e. those edges are added 3 foreach (RepairAction ra in ras) { to the create pattern (line 17). 4 Pattern search = ra.GetSearchPattern(); 5 Pattern create = ra.GetCreatePattern(); Next, the repair actions are enhanced for searching for an 6 Pattern delete = ra.GetDeletePattern(); alternative context. The method shown in Figure 7 is the 7 RepairAction ra2 = new RepairAction(); changing (c) version and retrieves as input parameters the 8 retRas.Add(ra2); repair actions ras of the previous step. In this method, each 9 Pattern search2 = new Pattern(search); repair action is doubled (line 7). One version (ra) searches 10 Pattern create2 = new Pattern(create); for an alternative context group of a missing context node 11 Pattern delete2 = new Pattern(delete); only in the graph of the missing node with pattern search. 12 ra2.SetSearchPattern(search2); Nodes of the context are only added to the pattern, if the 13 ra2.SetCreatePattern(create2); graph role is equal to the graph role of the missing node 14 ra2.SetDeletePattern(delete2); (lines 21 and 22). The other version (ra2) searches for an 15 alternative context group in all three graphs with pattern 16 foreach (PatternNode patNode in search2. Nodes of the context are all added to this pattern rsPattern.GetNodes()) (line 20). The edges of the alternative context are searched 17 if(dmgPattern.ContainsKey(patNode) && in ra only if they belong to the same graph as the missing rsPattern.IsContext(patNode)) { context (line 27), ra2 searches all edges between the context 18 Pattern ctxtGroup = rsPattern. nodes (line 25). Edges from the context nodes which points GetContextGroup(patNode); to other nodes in the same graph as the missing node are 19 foreach (PatternNode ctxtNode in searched in both versions (lines 28 to 30). Those in the other ctxtGroup) { graphs are created (line 32) and edges to the former context 20 search2.Add(ctxtNode); are deleted (line 33) but only for ra2. The repair action ra 21 if(ctxtNode.graphRole.Equals(patNode only reassigns edges within the integration document (lines .graphRole)) 34 to 36). 22 search.Add(ctxtNode); 23 foreach (PatternEdge edge in To give an example, we present in Figure 8 the repair action rsPattern.GetEdges(ctxtNode)) ra2 which reassigns the operation getDBItem to the other 24 if (ctxtGroup.ContainsKey(edge. class DBAccess which plays the role of the alternative con- GetSourceNode() && ctxtGroup. text here. The search (LHS) pattern consists of the remain- ContainsKey(edge. ing graph with the current node ids. The nodes DataAcces- GetTargetNode()) { sObj in source and target graph as well as the ClassLink node 25 search2.AddEdge(edge); between them are the context group which has to be replaced 26 if (edge.graphRole.Equals(patNode. as the ownedOperation edge between DataAccessObj and get- graphRole)) DBItem in the source graph is missing. The search pattern 27 search.AddEdge(edge); } is extended by an additional context group, only edges be- 28 else if (edge.graphRole.Equals( tween that nodes are added and the ownedOperation edge patNode.graphRole)) { in the source graph where the edge is missing. The nodes 29 search.AddEdge(edge); and edges of the gluing graph K (K = LHS ∩ RHS) of the 30 search2.AddEdge(edge); } LHS and the RHS are not changed. The create pattern is 31 else { the pattern RHS\K and the delete pattern is LHS\K and in 32 create2.AddEdge(edge); this example the edges in the integration document and the 33 delete2.AddEdge(edge); target graph. 34 if(IntDocEdgeTypes.ContainsKey( edge.type)) Generating repair actions at runtime is suitable because 35 create.AddEdge(edge); they cannot be all modeled beforehand foreseeing all pos- 36 delete.AddEdge(edge);}}}} sible changes a user can make. But this approach also im- 37 return retRas; plies performance problems when at runtime a set of repair 38 } actions is generated, most of them not being applicable as required, e.g., required nodes and edges of the search pattern Figure 7: Creation of the repair action for searching are not present in the graph. for an alternative context (simplified, in C#) Therefore, we optimized the process by introducing phases before and that multiple repair actions are generated, i.e. 3e where e is the number of missing edges. 29 OperationRepair :: LHS as UML OD approach is similar to ours, but differs in some ways: the <> <> <> <> <> DataAcessObj: Class : ClassLink DataAccessObj : Class generated repair actions cannot create model elements and the modifications the user had done on one model are known <> <> <> ownedOperation and used for the generation. Thus, this generation approach <> <> <> <> <> : Class : ClassLink : Class is not immediately ready for inconsistency resolution of mod- <> ownedOperation els which are edited by external tools. <> <> <> <> <> getDBItem : getDBItem : :MethodLink Operation Operation ::= RHS as UML OD 7. CONCLUSIONS <> <> <> <> <> In this paper, novel strategies for resolving inconsistencies DataAcessObj: DataAccessObj : ClassLink Class : Class between graph-based models taking into account only con- sistency rules specified as triple rules and the damaged sub- <> <> <> <> <> graphs are presented. The operations which were performed : Class : ClassLink : Class <> <> <> ownedOperation on a model and lead to the inconsistencies are not consid- <> <> <> <> <> <> ered as it is assumed that the models are edited by external getDBItem : getDBItem : Operation :MethodLink Operation tools. Also, resolution is done on request, thus tolerating in- consistencies. A main principle in resolving inconsistencies Source (UML Class Diagram) Integration Document Target (Source Code) presented here is to conserve the applied rule or to apply a similar one and do only small adaptations. As discussed, we Figure 8: Repair action which reassigns the method think that this is a good option in practice. Not presented in to another class this paper, but nevertheless mentionable is that based on the presented strategies multiple alternative repair actions are derived for one damaged link, even multiple repair actions for the strategy to conserve the applied rule or to apply a where only repair actions for a set of predefined repair types similar one. Not all are applicable, i.e. required increments are generated and tested. Only if no valid repair action could are not available, so that only applicable repair actions are be found in one phase, repair actions of another set of repair suggested to the user. In the end, the user picks the repair types are tested in the next phase. This proved acceptable action which fits best. This should not be decided by the runtime behavior. The sets of repair types and the order of tool. their execution can be configured by the user. Additionally, a set of repair types can be specified which should be always tested. 8. REFERENCES [1] Becker, S. M. Integratoren zur Konsistenzsicherung von Dokumenten in Entwicklungsprozessen. Berichte 6. RELATED WORK aus der Informatik. Shaker Verlag, Aachen, Germany, There are many approaches handling inconsistencies with 2007. Doktorarbeit, RWTH Aachen University. graph transformations. One is, only delete and attribute [2] Becker, S. M., Herold, S., Lohmann, S., and propagations or link deletions are supported as with our ap- Westfechtel, B. A Graph-Based Algorithm for proach, e.g. in [14, 37, 13]. Another is, inconsistent situ- Consistency Maintenance in Incremental and ations are defined as graph patterns which are searched in Interactive Integration Tools. Software and Systems the host graph and graph transformations for their resolu- Modeling (SoSyM) 6, 3 (2007), 287–315. tion are specified such as in [15, 38, 10, 35, 34, 7] to name a few. This procedure is very laborious and will never cover all [3] Becker, S. M., and Westfechtel, B. UML-based cases. Additionally, [37] supports the completion of a con- Definition of Integration Models for Incremental sistency pattern which is analogous to the changing version Development Processes in Chemical Engineering. of the rule conserving strategy. Integrated Design and Process Science: Transactions of the SDPS 8:1 (2004), 49–63. Since not all kinds of inconsistencies like behavioral inconsis- [4] Czarnecki, K., and Helsen, S. Classification of tencies and resolution rules can be expressed easily as graph Model Transformation Approaches. In Proc. of the transformation rules, there are similar approaches [18, 36, Workshop on Generative Techniques in the Context of 33] which use logic-based rules to detect and resolve inconsis- Model Driven Architecture (OOPSLA 2003) (2003). tencies exemplified with UML class and sequence diagrams. [5] Egyed, A. Fixing Inconsistencies in UML Design Also in these approaches, each inconsistency and each reso- Models. In Proc. of the 29th Intl. Conf. on Software lution has to be defined in advance. Engineering (ICSE 2007) (2007), IEEE Computer Society, pp. 292–301. A similar dynamic approach is proposed by [22, 6, 5] within [6] Egyed, A., Letier, E., and Finkelstein, A. a repair framework where consistency rules are expressed Generating and Evaluating Choices for Fixing by first order logic formulae. In contrast to the other ap- Inconsistencies in UML Design Models. In ASE proaches, repairs are fully generated from these formulae. (2008), IEEE, pp. 99–108. For a violated formula a set of sets of repair actions is gen- [7] Enders, B. E., Heverhagen, T., Goedicke, M., erated, each set of repair actions representing an alternative. Tröpfner, P., and Tracht, R. Towards an A repair action adds, deletes, or changes one model to fix Integration of Different Specification Methods by the violated formula or subformula. The alternatives are Using the ViewPoint Framework. Transactions of the presented to the user who selects one for execution. This SDPS 6, 2 (2002), 1–23. 30 [8] Finkelstein, A., Spanoudakis, G., and Till, D. [22] Nentwich, C., Emmerich, W., and Finkelstein, Managing interference. In Joint Proc. of the 2nd Intl. A. Consistency Management with Repair Actions. In Software Architecture Workshop (ISAW-2) and Intl. Proc. of the 25th Intl. Conf. on Software Engineering Workshop on Multiple Perspectives in Software (ICSE 2003) (2003), IEEE Computer Society, Development (Viewpoints 1996) on SIGSOFT 1996 pp. 455–464. Workshops (1996), ACM, pp. 172–174. [23] Nuseibeh, B., Easterbrook, S., and Russo, A. [9] Förtsch, S., and Westfechtel, B. Differencing Leveraging Inconsistency in Software Development. and Merging of Software Diagrams - State of the Art Computer 33, 4 (2000), 24–29. and Challenges. In Proc. of the 2nd Intl. Conf. on [24] OMG. UML 2.0: Infrastructure, V2.1.2. online, 2007. Software and Data Technologies (ICSOFT 2007) [25] Omondo Europa. EclipseUML Studio, 2007. (Setubal, Portugal, 2007), J. Filipe, B. Shishkow, and [26] Pratt, T. W. Pair Grammars, Graph Languages and M. Helfert, Eds., INSTICC. String-to-Graph Translations. Computer and Systems [10] Hausmann, J. H., Heckel, R., and Sauer, S. Sciences 5, 6 (1971), 560–595. Extended Model Relations with Graphical Consistency [27] Schürr, A. Specification of Graph Translators with Conditions. In Jézéquel et al. [12], pp. 61–74. Triple Graph Grammars. In Proc. of the 20th Intl. [11] Hwan, C., Kim, P., and Czarnecki, K. Workshop on Graph-Theoretic Concepts in Computer Synchronizing cardinality-based feature models and Science (WG 1994) (1995), vol. 903 of LNCS, their specializations. In ECMDA-FA (2005), Springer-Verlag, pp. 151–163. A. Hartman and D. Kreische, Eds., vol. 3748 of LNCS, [28] Spanoudakis, G., and Finkelstein, A. Reconciling Springer-Verlag, pp. 331–348. Requirements: A Method for Managing Interference, [12] Jézéquel, J. M., Hußmann, H., and Cook, S., Inconsistency and Conflict. Annals of Software Eds. Proc. of the 5th Intl. Conf. on The Unified Engineering 3 (1997), 433–457. Modeling Language (UML 2002) (2002), vol. 2460 of [29] Spanoudakis, G., and Zisman, A. Inconsistency LNCS, Springer-Verlag. Management in Software Engineering: Survey and [13] Jouault, F., Allilaire, F., Bézivin, J., and Open Research Issues. In Handbook of Software Kurtev, I. Atl: A model transformation tool. Science Engineering and Knowledge Engineering, S. K. Chang, of Computer Programming 72, 1-2 (2008), 31–39. Ed., vol. 1. World Scientific Publishing Co, 2001, [14] Königs, A. Model Integration and Transformation - pp. 329–380. A Triple Graph Grammar-based QVT Implementation. [30] Stevens, P., Whittle, J., and Booch, G., Eds. PhD thesis, Technische Universität Darmstadt, Proc. of the 6th Intl. Conf. on The Unified Modeling Fachbereich Elektrotechnik und Informationstechnik, Language (UML 2003) (2003), vol. 2863 of LNCS, January 2009. Dissertation. Springer-Verlag. [15] Königs, A., and Schürr, A. Multi-Domain [31] The Eclipse Foundation, 2008. Integration with MOF and extended Triple Graph [32] Tratt, L. Model Transformations and Tool Grammars [online]. In Language Engineering for Integration. Software and Systems Modelling (SoSym) Model-Driven Software Development (Dagstuhl, 4:2 (2005), 112–122. Germany, 2005), no. 04101 in Dagstuhl Seminar Proc., [33] Van Der Straeten, R. Inconsistency Management IBFI. in Model-driven Engineering: an Approach using [16] Körtgen, A. Modellierung und Realisierung von Description Logics. PhD thesis, Vrije Universiteit Konsistenzsicherungswerkzeugen für simultane Brussel, 2005. Dokumentenentwicklung. Berichte aus der Informatik. [34] Van Der Straeten, R., and D’Hondt, M. Model Shaker Verlag, Aachen, Germany, 2009. Doktorarbeit, refactorings through rule-based inconsistency RWTH Aachen University. resolution. In Proc. of the 2006 ACM symposium on [17] Körtgen, A., Becker, S. M., and Herold, S. A Applied computing (SAC 2006) (New York, NY, USA, Graph-Based Framework for Rapid Construction of 2006), ACM, pp. 1210–1217. Document Integration Tools. In Proc. of the 11th [35] Van Der Straeten, R., and Mens, T. Incremental World Conf. on Integrated Design & Process Resolution of Model Inconsistencies. In Proc. of 18th Technology (IDPT ’07) (2007), SDPS, p. 13 pp. Intl. Workshop of Recent Trends in Algebraic [18] Liu, W., Easterbrook, S., and Mylopoulos, J. Development Techniques (WADT 2006) (2007), Rule Based Detection of Inconsistency in UML vol. 4409 of LNCS, Springer-Verlag, pp. 111–126. Models. In Jézéquel et al. [12], pp. 106–123. [36] Van Der Straeten, R., Mens, T., Simmonds, J., [19] Long, E. Transform, edit, and reverse-engineer a and Jonckers, V. Using Description Logics to UML Model into Java Source Code. Tech. rep., IBM Maintain Consistency Between UML Models. In Corporation, 2007. Stevens et al. [30], pp. 326–340. [20] Microsoft Corporation. MSDN Library - Visual [37] Wagner, R. Inkrementelle Modellsynchronisation. Studio SDK, 2008. PhD thesis, Universität Paderborn, Institut für [21] Nagl, M., and Marquardt, W., Eds. Collaborative Informatik, Fachgebiet Softwaretechnik, 2009. and Distributed Chemical Engineering Design Dissertation. Processes: Better Understanding and Substantial [38] Wagner, R., Giese, H., and Nickel, U. A Plug-In Support Results of the CRC IMRPOVE, vol. 4970 of for Flexible and Incremental Consistency LNCS. Springer-Verlag, 2008. Management. In Stevens et al. [30]. 31