University of Toronto Department of Computer Science A Relationship-Driven Framework for Model Merging Mehrdad Sabetzadeh, Shiva Nejati, Steve Easterbrook, Marsha Chechik Department of Computer Science University of Toronto http://www.cs.toronto.edu/~mehrdad May 19, 2007 Workshop on Modeling in Software Engineering (MiSE07) Mehrdad Sabetzadeh, 2007 University of Toronto Department of Computer Science Terminology A tentative classification for fusion tasks: Model Fusion Compliance Checking Merging Unificatio n of overlaps Composition Weaving Sequential or parallel Incorporation of execution w.r.t. cross-cutting
given interfaces concerns Enforcement of modelmetamodel or model-model constraints This talk focuses on Merging Mehrdad Sabetzadeh, 2007 2 University of Toronto Department of Computer Science Motivation Background: Merging conceptual models [Sabetzadeh&Easterbrook RE05] Requirements, Early Design Merging behavioural models [Uchitel&Chechik FSE04, Nejati et al ICSE07] Design, Implementation These differ in various details: [RE05] [FSE04, ICSE07] Model semantics
tacit, semi-formal formal Main concerns preservation of structure preservation of behaviour Motivating Applications elicitation, negotiation, inconsistency management synthesis, variability analysis, maintenance Underlying math categorical colimits behavioural refinement Can we have a unified tool despite these differences? Mehrdad Sabetzadeh, 2007 3 University of Toronto Department of Computer Science Characteristics of Merge 1. Completeness Merge should not lose information
2. Non-Redundancy Merge should not have redundant copies of shared objects 3. Coherence Merge should deal with information missing from source models 4. Property Preservation Merge should preserve the intended meaning of source models For structural models: preservation of structure For behavioural models: preservation of behaviour All these require a notion of how models are related! Mehrdad Sabetzadeh, 2007 4 University of Toronto Department of Computer Science Specification of Relationships Implicit vs. Explicit Relationships Implicit: Rely on name or id equality to give the correspondences correspondin g not corresponding a b a c M2 M1
Explicit: No two objects correspond unless explicitly mapped a not corresponding b c M1 Mehrdad Sabetzadeh, 2007 a M2 correspondin g 5 University of Toronto Department of Computer Science Implicit Relationships Rationale Existence of a common ancestor A A+ 1 A+ 2
M1 M2 Merge=A+ 1 + Problematic because: 2 Not suitable for independently-developed models No common ancestor Not bullet-proof for models with common ancestors either 1 and 2 may be overlapping! Can be addressed by explicit relationships Mehrdad Sabetzadeh, 2007 6 University of Toronto Department of Computer Science Explicit Relationships Overlaps described by explicit mappings In our work: For merging conceptual models: Goal: Unification of shared structures A transitive notion of equality between objects a b Collapse a and b in the merge
will see how this generalizes to more complex relationships For merging (LTS-based) behavioural models: Goal: Unification of shared behaviours A non-transitive notion of behavioural similarity between states a b Create a common refinement of a and b in the merge Mehrdad Sabetzadeh, 2007 7 University of Toronto Department of Computer Science Conceptual Model Merging: Example Models: Graphs Mappings: Homomorphisms C M1 p1 s M2 p2 s1
Merge t1 a b s2 s3 Mehrdad Sabetzadeh, 2007 d t2 p1 c t3 a s2 s c p2 t3 8 University of Toronto Department of Computer Science
More Complex Relationships Example: Relating objects through generalization H s1 t1 M1 M2 c1 s1 t1 Similar techniques used in [Medvidovic et al SEKE01] and [Madhavan et al AAAI02] for bridging conceptual gaps between models M1 Retrenchment Evolution M1 s1 Mehrdad Sabetzadeh, 2007 s1 a b a b
s2 s3 s2 s3 9 University of Toronto Department of Computer Science Behavioural Model Merging: Example Models: State machines Mappings: Binary relation over states M1 M2 s1 Merge t1 a b s2 s3
b t2 c t3 a[M1] s2 s1.t1 b c[M2] s3.t2 t3 Preserves temporal properties of the source models Universal properties preserved by the unguarded fragment Existential properties preserved by either the guarded or unguarded fragments Mehrdad Sabetzadeh, 2007 10 University of Toronto Department of Computer Science One-To-Many Mappings M1 c s2 s1 a
b s3 s4 M2 t2 t1 a t3 b Behavioural Merge s1.t1 c[M1] a b[M1] t4 s2 s3.t3 Refactoring s1 c[M1] s2 Nave Structural Merge c s2 s1.t1.t2 a
b s3.t3 s4.t4 Mehrdad Sabetzadeh, 2007 s1.t2 c[M1] a[M1] b t1 a b[M1] a[M1] s3.t3 s4.t4 t2 b s4.t4 Doesnt preserve negative behaviours! 11 University of Toronto Department of Computer Science A Unified Tool for Merge What we saw so far:
1. 2. 3. 4. There may be more than one way of relating models There may be more than one meaningful merge between models Different merges pose different requirements on relationships Need explicit description of relationships between models Constructing models and relationships Models built using a rich graph editing interface Mappings defined visually through functions/relations between model pairs Proposed architecture for the tool: A unified GUI for building models and relationships Merge algorithms implemented as plugins Appropriate plugin chosen based on the intended relationships hence, relationship-driven Mehrdad Sabetzadeh, 2007 12 University of Toronto Department of Computer Science Overall Framework Sourc e Model s Build Relationships Select Models and
Mappings Merge! Merged Model Mehrdad Sabetzadeh, 2007 13 University of Toronto Department of Computer Science Implementation TReMer (Tool for Relationship-Driven Model Merging) Prototype tool implementing the [RE05] and [ICSE07] approaches TReMer+ (TReMer + Traceability + Relational Property Checking) Checking inter-model properties of distributed models via checking intra-model properties of their merge [RE07, upcoming] Ask us for a demo! Tool and examples available at: http://www.cs.toronto.edu/~ mehrdad/tremer Mehrdad Sabetzadeh, 2007 14 University of Toronto Department of Computer Science Current Work HCI Aspects Layout, model navigation, tool aesthetics Have direct impact on the quality of resulting artifacts
Major source of confounding factors in empirical evaluation of Model Management activities Interactions between Merge and other MM operators such as Match, Diff, Slice, etc. A step toward a standard algebra for Model Management See [Easterbrook et al GaMMa06] for some early results Tool for Model Management Based on Eclipse Large ongoing effort: M. Chechik, Z. Diskin, S. Easterbrook, P. McCormick, S. Nejati, N. Niu, M. Sabetzadeh, R. Salay, M. Sassolas, S. Uchitel, P. Viriyakattiyaporn, P. Zave Mehrdad Sabetzadeh, 2007 15 University of Toronto Department of Computer Science Thank You! Questions? Mehrdad Sabetzadeh, 2007 16
