CVSM Bibliography, Entry [ Uh2011Diss ]


Uhrig, Sabrina: Korrespondenzberechnung auf Klassendiagrammen; Dissertation, Universität Bayreuth, urn:nbn:de:bvb:703-opus-9050; 2011
Download: Volltext (91 MB!)
Deskriptoren: CVSM

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.