From Imprecise N-Way Model Matching to Precise N-Way Model Merging

By: Dennis Reuling, Malte Lochau, Udo Kelter

Abstract

N-way model merging is a key technique for managing software variabil- ity, by integrating N concurrent model variants/versions into one. Most merging techniques are based on three operators: (1) compare, (2) match and (3) merge. As finding optimal solutions for (2) in terms of matching precision is NP-hard, many proposals for scalable yet sufficiently precise matching heuristics exist. However, most approaches are either generic which obstructs precision if applied to realistic modeling languages, or they require excessive computational upfront investment already in step (1) to ensure sufficient precision. We propose an alternative approach for auto- mated construction of precise model merges by focusing on step (3): given an arbitrarily imprecise matching, we incrementally apply default model- refactoring operators, as available for most mature modeling languages, to identify and unify further similarities among initially unmatched model elements. For those model-refactoring operators to produce correct results if applied to merged models, we utilize variability encoding as known from product-line engineering. Our tool implementation supports any EMF- compliant modeling language and is instantiated for UML class diagrams to demonstrate our methodology. Our evaluation results show that our technique (a) preserves the precision of near optimal matchings and (b) remarkably improves the precision of arbitrarily imprecise matchings while requiring acceptable computational effort.

Keywords

Model Merging, Model Transformation, Software Variability

Cite as:

Dennis Reuling, Malte Lochau, Udo Kelter, “From Imprecise N-Way Model Matching to Precise N-Way Model Merging”, Journal of Object Technology, Volume 18, no. 2 (July 2019), pp. 8:1-20, doi:10.5381/jot.2019.18.2.a8.