Tripel-Graph-Grammatik

Das TGG-Konzept lässt sich von Graphen auf MOF-Modelle übertragen. TGG-Regeln beschreiben dann, wie konkrete Instanz-Modelle modifiziert werden können. Zunächst wird die linke Seite der TGG-Regel per Pattern Matching in den Instanz-Modellen gesucht. Kann die linke Seite gefunden werden (d. h. die Regel ist anwendbar), so beschreibt die rechte Seite der Regel, wie die Regel angewendet wird, also wie die Instanzmodelle an dieser Fundstelle geändert werden können.

Modelle enthalten Objekte und Links, die Instanzen von Klassen und Referenzen eines Metamodells sind. Die Knoten einer TGG-Regel sind daher über die Klassen, die Kanten über die Referenzen des Metamodells typisiert. Ein Knoten kann beim Pattern Matching nur auf solche Objekte abgebildet werden, deren Klassen seinem Typ entsprechen. Genauso kann eine Kante einer TGG-Regel nur auf solche Links abgebildet werden, deren Referenzen ihrem Typ entsprechen.

Die drei Spalten einer TGG-Regel (Quell-, Korrespondenz- und Zielgraph) werden auch Domänen genannt. Eine Domäne hat typischerweise ein zugehöriges Metamodell. Die TGG-Knoten und -Kanten in dieser Domäne sind dann über dieses Metamodell typisiert.

Abb. 3: Semantik der verschiedenen TGG-Regel-Teile bei einer Vorwärtstransformation

Im Anwendungsszenario Vorwärtstransformation soll ein existierendes Quellmodell in das neu zu erzeugende Zielmodell transformiert werden. Die grundsätzliche Idee besteht darin, eine Ableitungsreihenfolge gemäß dem TGG-Regelsatzes zu finden, die in der Quelldomäne das existierende Quellmodell erzeugen würde. Gemäß dieser Abfolge von Regeln kann dann das zugehörige Korrespondenz- und Zielmodell erzeugt werden. Das Finden dieser Ableitungsreihenfolge, das sogenannte Graphparsing, kann jedoch sehr aufwändig sein: Insbesondere wenn es mehrere Regeln gibt, die an derselben Stelle im Quellmodell passen, müssen gegebenenfalls alle diese Möglichkeiten ausprobiert werden.

Für den Anwendungsfall einer Vorwärtstransformation werden üblicherweise aus den Basisregeln Übersetzungsregeln abgeleitet bzw. die Basisregeln anders interpretiert: Da das Quellmodell bereits existiert, dürfen die Produktionen der Quelldomäne nicht ausgeführt werden. Die Knoten und Kanten im produzierten Graph der Quelldomäne werden stattdessen auf bereits existierende Quellmodellelemente abgebildet. So abgedeckte Modellelemente werden auch als gebunden bezeichnet. Dabei muss sichergestellt werden, dass jedes Element des Quellmodels nur genau einmal gebunden, also von einem produzierten Knoten oder einer produzierten Kante abgedeckt wird. Kontext-Knoten und -Kanten hingegen dürfen nur auf bereits gebundene Modellelemente abgebildet werden. Abb. 3 zeigt diese Richtlinien für eine Vorwärtstransformation. So wird sichergestellt, dass als Ergebnis der Transformation nur Modell-Tripel entstehen, die auch durch simultanes Erzeugen aller drei Modelle hätten entstehen können.

Eine Transformation ist nur dann vollständig, wenn alle Elemente des Quellgraphen gebunden sind, also von der Transformation bearbeitet wurden. Falls also noch Elemente des Quellgraphen ungebunden sind, aber keine Regel mehr anwendbar ist, ist die Transformation unvollständig. Falls zuvor an einer Stelle eine andere Regel anwendbar gewesen wäre, müsste nun zu dieser Stelle zurückgegangen werden und die andere Regel benutzt werden (Backtracking).

Die Richtung der Transformation ist umkehrbar, in dem lediglich die Bedeutung von Quell- und Zielmodell getauscht wird. Aus einer TGG sind also Vorwärts- und Rückwärtstransformationen ableitbar. Es müssen nicht manuell zwei verschiedene Transformationen für die beiden Richtungen spezifiziert werden.

Ein Beispiel für eine Modelltransformation im Kontext der Softwareentwicklung ist die objektrelationale Abbildung, bei der Objekte in einer relationalen Datenbank persistent abgelegt werden. Dazu werden für die Klassen, deren Objekte persistiert werden sollen, entsprechende Tabellen in der Datenbank angelegt.

Eine mögliche Abbildung von Klassen auf Tabellen ist, pro Vererbungshierarchie eine Tabelle anzulegen. Eine Basisklasse wird also in eine Tabelle übersetzt, alle von ihr abgeleiteten Klassen verwenden ebenfalls diese Tabelle der Basisklasse. Die in Abb. 2 gezeigte TGG-Regel stammt aus einem Regelsatz, der eine solche Abbildung definiert. Diese Regel beschreibt, dass jeder Basisklasse in der Domäne Klassen eine Tabelle in der Domäne Datenbank entspricht.

Abb. 4: Vorwärtstransformation von Klassen in ein Datenbankschema (animiert)

Abb. 4 zeigt links den gesamten TGG-Regelsatz für diese Abbildung. An oberster Stelle befindet sich das Axiom, das einem Paket ein Datenbankschema zuordnet. Die nächste Regel ordnet einer Basisklasse eine Tabelle zu. Die negative Anwendungsbedingung verhindert, dass diese Regel auch für abgeleitete Klassen angewendet wird. Die dritte Regel ordnet dann abgeleitete Klassen der Tabelle ihrer Basisklasse zu. Dies funktioniert auch für mehrstufige Vererbung, da der Kontext der Regel auch von dem produzierten Teil derselben Regel gebildet werden kann. Die letzte Regel übersetzt schließlich Attribute einer Klasse in Spalten in der entsprechenden Tabelle der Klasse.

Rechts sieht man, wie in einer Vorwärtstransformation Schritt für Schritt durch Anwendung der verschiedenen TGG-Regeln das Zielmodell aus dem Quellmodell erstellt wird. In der Ausgangssituation sind dabei bereits die Wurzelelemente der drei Modelle (die Objekte :Package, :PackageToSchema, :Schema) durch das Axiom gebunden. Nun wird versucht, die verschiedenen TGG-Regeln anzuwenden. Jede TGG-Regel wird dabei in drei Schritten bearbeitet:

1. Zunächst wird versucht, per Pattern Matching zum Kontextgraphen der Regel passende Teile in Quell-, Ziel- und Korrespondenzmodell zu finden.

2. Wurde in Schritt 1 ein zum Kontextgraphen passender Teil gefunden, so wird anschließend ein zum produzierten Quellgraphen passender Teil im Quellmodell gesucht.

Wird ein passender Teil im Quellmodell gefunden, werden die entsprechenden Elemente als gebunden markiert und mit Schritt 3 fortgefahren. Kann kein Teil gefunden werden, so wird zu Schritt 1 zurückgegangen und ein anderes Pattern Matching für den Kontextgraphen gesucht.

3. Wurde in Schritt 2 ein Matching für den Kontext- und produzierten Quell-Teil der Regel gefunden, darf die Regel angewendet werden.

Dabei werden für den produzierten Korrespondenz- und Ziel-Teil der Regel Modellelemente erzeugt und gleichzeitig als gebunden markiert. Abschließend werden noch eventuell notwendige Attributwertzuweisungen durchgeführt.

Abb. 5: Pattern-Matching-Ablauf und Anwendung einer Regel (animiert)

Abb. 5 zeigt beispielhaft, wie das Pattern Matching und die Anwendung einer TGG-Regel zur Übersetzung von Attributen abläuft.

Mithilfe von Tripel-Graph-Grammatiken können nicht nur einmalige Modelltransformationen (Batch-Transformationen) durchgeführt werden. Durch den Korrespondenzgraph werden zusammengehörige Modellteile markiert, so dass auch nachträgliche Änderungen an einem der Modelle in das andere Modell übertragen werden können, ohne diese vollständig neu zu erzeugen („inkrementelle Transformation“).

Wird beispielsweise ein neues Modellelement hinzugefügt, braucht lediglich geprüft werden, ob durch diese Einfügung weitere Regeln anwendbar sind, um diese dann ausführen. Neben einer verbesserten Laufzeit hat dies den Vorteil, dass möglicherweise zwischenzeitlich ins Zielmodell eingefügte modellspezifische Informationen (also Informationen ohne Relevanz für die Modelltransformation) nicht verloren gehen.[1]