Korrespondenzberechnung auf Klassendiagrammen

Titelangaben

Uhrig, Sabrina:
Korrespondenzberechnung auf Klassendiagrammen.
Bayreuth , 2011
( Dissertation, 2011 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

	Format: PDF Name: Dissertation_Uhrig.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
	Download (93MB)

Abstract

Für die modellgetriebene Softwareentwicklung werden Werkzeuge benötigt, die das Arbeiten mit Modellen unterstützen. Ein besondere Stellung nehmen Vergleichswerkzeuge ein, die dem Entwickler nicht nur veranschaulichen, was sich zwischen zwei Versionen eines Modells geändert hat, sondern auch Differenzen liefern, auf deren Grundlage zwei Versionen miteinander zu einem Dokument verschmolzen werden können. Vergleichsverfahren arbeiten üblicherweise in zwei Schritten. Zunächst werden die korrespondierenden Modellelemente bestimmt, bevor dann im zweiten Schritt die Unterschiede auf Basis der Korrespondenzen ermittelt werden. Die vorliegende Arbeit beschäftigt sich mit dem ersten, schwierigeren Schritt, der Korrespondenzberechnung, mit einem Schwerpunkt auf Klassendiagrammen, die das Kernstück der objektorientierten Modellierung darstellen. In diesem Rahmen wurden zwei Korrespondenzberechnungsverfahren für den Vergleich von Ecore-Klassendiagrammen entwickelt, die strukturbasiert arbeiten und keine eindeutigen Objektbezeichner verwenden. Während die bisher bekannten Vergleichsverfahren für Klassendiagramme, die keine eindeutigen Objektbezeichner verwenden, die Korrespondenzen über Ähnlichkeitsheuristiken bestimmen, wurde für das erste Verfahren ein neuartiger Ansatz verfolgt. Analog zu der Definition eines Edierabstandes für Bäume oder Graphen wurde ein Edierkostenmodell in Verbindung mit einer Menge zulässiger Änderungsoperationen auf Klassendiagrammen entworfen. Auf diese Weise kann die Berechnung der Korrespondenzen zwischen zwei Klassendiagrammen als Optimierungsproblem dargestellt werden, eine Zuordnung mit minimalen Edierkosten zu bestimmen. Aufgrund der kontextabhängigen Kosten für die Edieroperationen auf Assoziationen und Vererbungskanten würde eine Bestimmung der optimalen Lösung die Bewertung aller O(n!) verschiedenen Kombinationsmöglichkeiten der Klassenpaare erfordern. Daher wird in dem vorgestellten Verfahren stattdessen ein relaxiertes Optimierungsproblem gelöst. Mit Hilfe der Abschätzung der Kosten für Assoziationen und Vererbungsbeziehungen durch eine untere Schranke lässt sich das Optimierungsproblem auf ein Netzwerkflussproblem reduzieren, das mit Hilfe eines Verfahrens aus der Graphentheorie mit polynomiellem Aufwand gelöst werden kann. In einem Teil der Fälle lässt sich über ein leicht überprüfbares hinreichendes Optimalitätskriterium nachweisen, dass die so berechnete Lösung für das relaxierte Optimierungsproblem auch für das ursprüngliche Optimierungsproblem optimal ist. Entsprechend den Ergebnissen einer durchgeführten Evaluation weichen die berechneten Edierkosten nur wenig von den optimalen Edierkosten ab. Das Verfahren unterscheidet sich von allen heuristischen Verfahren dadurch, dass ein objektives Kriterium, die Edierkosten der berechneten Zuordnung, existiert, mit dem beurteilt werden kann, inwieweit das Verfahren die vorgegebenen Ziele erreicht hat. Als zweites Verfahren zum Vergleich wurde ein ähnlichkeitsbasiertes, heuristisches Verfahren entwickelt, das für die möglichen Korrespondenzpaare Ähnlichkeitswerte berechnet und mit Hilfe eines heuristischen Auswahlverfahrens die korrespondierenden Elemente über die Maximierung der Gesamtähnlichkeit bestimmt. Beide Verfahren wurden in einem Plugin für Eclipse implementiert, das zusammen mit Komponenten des Eclipse Modeling Frameworks ein Rahmenwerk zum Modellieren und Vergleichen von Ecore-Klassendiagrammen bildet. Dabei wurde der Vergleich von Klassendiagrammen mit Paketen in zwei Stufen unterteilt. Über einen Vergleich aller Klassenpaare unabhängig von deren Lage in der Pakethierarchie werden zunächst die Korrespondenzen auf Klassenebene gebildet. Darauf aufsetzend werden die korrespondierenden Pakete unter der Vorgabe der Klassenkorrespondenzen bestimmt. Das Rahmenwerk bietet eine Auswahlsicht, in der verschiedene Klassen- und Paketebenenverfahren kombiniert werden können. Die Vergleichsergebnisse des edierkostenbasierten und des ähnlichkeitsbasierten Verfahrens wurden in einer Evaluation einander gegenübergestellt. Die vorliegende Arbeit erweitert den Stand der Technik in diesem Gebiet somit nicht nur um Korrespondenzberechnungsverfahren, sondern liefert auch Erkenntnisse über die Eignung des Edierabstandes zwischen Modellen als Kriterium für die Bewertung von Modelldifferenzen und darüber, wie sich ein edierkostenbasiertes Verfahren im Vergleich zu einem ähnlichkeitsbasierten Verfahren verhält.

Abstract in weiterer Sprache

In the field of model-driven software development tools are needed which supply the work on models, especially the comparison of models. With such a tool a developer can visualize the changes between two versions of a model and use the differences to merge the two versions. Usually the comparison of models consists of two steps, the identification of the corresponding model elements and the interpretation of the differences based on the computed correspondences. The present study deals with the computation of the correspondences - which is the more difficult step of both - and focuses on class diagrams since class diagrams are the most relevant type of diagram in object-oriented modeling. In this context, two algorithms for the computation of correspondences between Ecore class diagrams have been developed. Both are structure-based and do not make use of unique object identifiers. While all known differencing algorithms for class diagrams which do not rely on unique object identifiers use heuristic similarity values, the approach of our first algorithm is new. On the analogy of edit distance for trees or graphs, a set of edit costs and feasible edit operations have been defined for class diagrams. This way the computation of corresponding elements is treated as an optimization problem to find correspondences associated with minimal edit costs. As the costs for edit operations on association edges and inheritance edges of classes depend on how the other classes are matched, a computation of the optimal solution requires the evaluation of all O(n!) possibilities to combine the class correspondences. Therefore the presented edit costs-based algorithm solves a relaxation of the original optimization problem instead. An estimation of the costs for association and inheritance edges with a lower bound enables the reduction of the problem on a network flow problem solvable with a graph algorithm in polynomial time. In some cases a sufficient optimality criterion - which can be easily verified - proves that the optimal solution for the relaxed problem holds for the original problem too. According to the results of our evaluation there is a small deviation of the computed edit costs from the optimal edit costs. This algorithm differs from all existing heuristic approaches in that there exists an objective criterion - the edit costs - to check the resulting correspondences for optimality. A second similarity-based algorithm has been developed, in order to compare the two different approaches. The algorithm computes similarity values for all possible correspondences and finally selects the corresponding elements with the largest total similarity using a heuristic greedy strategy. Both algorithms have been implemented as an Eclipse plug-in, which - together with several plug-ins of the Eclipse Modeling Framework - form a framework for modeling and differencing Ecore class diagrams. The comparison of class diagrams which also contain packages is divided in two parts. First all classes of all packages are compared and the correspondences on the class level are determined. Based on these correspondences the correspondences on the package level are computed. The framework offers a view to select different matching algorithms for the class and the package level. The results of the two differencing algorithms have been compared in an evaluation. Thus the contribution of the present study consists not only in two differencing algorithms for class diagrams but also in insights on the suitability of edit distance for the comparison of models and on how an edit cost-based algorithm behaves compared to a similarity-based algorithm.