Quality-Optimised Differencing Algorithms for Models

• Applicant: Professor Dr. Udo Kelter
• Subject Area: Software Engineering and Programming Languages
• Term: from 2010 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 186192750

In modern model-based development processes, models are part of the operating software. They assume the role of source code and they are, like source code, versioned frequently. Consequently, powerful tools for comparing, merging, and patching models are required. Such tools are based on algorithms which calculate the difference between models. Differencing algorithms for models must take the structure of each model type and the characteristics of typical edit operations into account. They should explain the difference between models as understandably as possible, in other words, produce differences of high quality. However, improving the quality of differences deteriorates the already high response times, so one has to compromise between quality and cost. Systematic approaches to defining the quality of differences are currently missing. This project thus aims at defining notions and measures for the quality of model differences and at optimizing differencing algorithms both in terms of runtime as well as the achieved quality of the differences. In the first period of funding, the project has developed methods and tools for creating benchmarks which can be used to evaluate differencing algorithms. A substantial set of test data, mainly class diagrams, was created and various variants of algorithms have been evaluated using these test models. In the meantime, new differencing algorithms became available which enhance the quality of differences by using refactorings and other complex operations to report changes. On the basis of the preliminary results the third project year is planned to develop a new conceptual framework which distinguishes variants of the quality of differences depending on the requirements of various classes of differencing tools. It is planned to re-evaluate differencing algorithms for class diagrams and to evaluate for the first time algorithms for differencing algorithms for BPMN models, which show significantly different characteristics and for which many refactorings have been proposed.

• DFG Programme: Research Grants