Innerhalb der letzten Jahre wurde eine Vielzahl von Methoden zur Analyse von
verteilten Gescha¨ftsprozessen der Sprache Web Services Business Process
Execution Language (WS-BPEL) [
Ein Prozessfragment dass nicht fehlerfrei analysiert werden kann, falls
Datenabha¨ngigkeiten ignoriert werden, ist in Abbildung 1 dargestellt. Die
abgebildete Aktivita¨t OrderingSequence ist mo¨glicherweise Bestandteil eines gro¨ßeren
Gescha¨ftsprozesses zur Realisierung eines Online-Shop. Darin kann ein Kunde
mehrere Bestellungen aufgeben (Nachricht Order), und so die
Auftragsabwicklung (Aktivita¨t OrderProcessing) zu jeder Bestellung einleiten. Nachdem der
Kunde alle Bestellungen u¨bertragen hat, kann er den Bestellvorgang beenden
(Nachricht Complete). Zur Umsetzung entha¨lt die Aktivita¨t OrderingSequence
eine Schleife (While), deren Ausfu¨hrung durch die boolesche Variable doOrder
gesteuert wird. Anfangs wird die Variable mit dem Wert true belegt und die
Schleife daher durchlaufen. Die Pick-Aktivita¨t innerhalb der Schleife fu¨hrt dann
entweder die Sequenz OrderProcessing aus, falls Nachricht Order empfangen
wird, oder die Sequenz Termination, falls der Kunde die Nachricht Complete
u¨bermittelt. Im letzten Fall wird der Wert von doOrder auf false gesetzt und so
die Schleife beendet. Der Schleifenabbruch wird demzufolge durch Empfang der
Nachricht Complete ausgelo¨st, entsprechend nennen wir das verallgemeinernde
Muster auch nachrichtengesteuerter Schleifenabbruch. Da im Sprachumfang von
WS-BPEL derzeit kein Gegenstu¨ck zur break-Anweisung aus Sprachen wie Java
enthalten ist [
Die in der Arbeit [
Reply Confirmation
OrderingSequence $doOrder = true() $index = 0 While($doOrder)
Pick
OnMessage Complete
Termination $doOrder = false() Reply OrderList ng inkLShipment ip r p e ihS tra n P
Order k inConfirmation L trrean irregndPOOrCdoemrLpilsetitneg
pLoop tLoopExit
While tLoopEnter
Pick ... ...
Order
OrderingSequence betrachtet werden, der genau eine Bestellung aufgibt. Die
Kommunikation besteht dann aus den aufeinanderfolgenden Nachrichten Order,
Confirmation, Complete und OrderList. Offensichtlich sind die beiden
Fragmente kompatibel [
Zusammenfassend ist die Kompatibilita¨tsanalyse in [
Um eine verlustfreie Repra¨sentation von Gescha¨ftsprozessen der Sprache
WSBPEL zu ermo¨glichen, verwenden wir eine Erweiterung von Workflow-Graphen.
Workflow-Graphen [
In Abbildung 2 ist der so erweiterte Workflow-Graph fu¨r das oben beschriebene Prozessfragment OrderingSequence dargestellt. Darin modellieren Knoten die Aktivita¨ten und Kanten verbinden die Knoten gema¨ß dem Kontrollfluss. Elementare Aktivita¨ten (beispielsweise Reply Confirmation) werden unter Verwendung eines einzelnen Knotens abgebildet. Sequenzen elementarer Aktivita¨ten sind dann durch mehrere sukzessive verbundener Knoten repra¨sentiert. Im Fall der Verzweigung Pick werden spezielle Knoten genutzt, um die Aufspaltung (P ick) und Vereinigung (M erge) des Kontrollflusses darstellen zu ko¨nnen. Dies gilt auch fu¨r die enthaltene Schleife While, fu¨r die der Knoten zum Aufspalten des Kontrollflusses (Branch) die Schleifenbedingung entha¨lt und der Knoten zur Vereinigung (Header) des Kontrollflusses als Schleifenkopf bezeichnet wird.
Grundlegende Eigenschaft der CSSA-Form ist, dass Variablen (statisch) nur einmal definiert werden du¨rfen.1 Zu diesem Zweck werden die Variablen in OrderingSequence so umbenannt, dass jede Variablendefinition einen eigenen Namen besitzt (beispielsweise doOrder1, . . . , doOrder4 fu¨r doOrder). Dadurch verhalten sich alle Variablen wie konstante Werte. Insbesondere sind Beziehungen zwischen Definition und Gebrauch einer Variablen nun explizit wiedergegeben. Ein besonderes Vorgehen ist notwendig, falls mehrere Definitionen einer Variablen auf verschiedenen Pfaden des Kontrollflusses in einem Knoten zusammentreffen (so in M erge und Header). In diesem Fall werden Φ-Funktionen eingefu¨gt, um die konkurrierenden Definitionen zusammenzufassen (beispielsweise doOrder4 = Φ(doOrder2, doOrder3) in M erge). Die Operanden einer ΦFunktion bilden gerade die Variablendefinitionen und der Funktionswert entspricht der Definition, die zur Laufzeit tatsa¨chlich ausgefu¨hrt wurde. 3
Aufbauend auf dieser Prozessrepra¨sentation lassen sich die Bedingungen von Verzweigungen und Schleifen analysieren. Die Bedingung der in OrderingSequence enthaltenen Schleife entspricht genau der Variablen doOrder2. Deren Wert wird durch eine Φ-Funktion im Schleifenkopf Header definiert. Diese fu¨hrt die konkurrierenden Definitionen der Variablen vor Ausfu¨hrung der Schleife (doOrder1) und nach Ausfu¨hrung eines Scheifendurchlaufs (doOrder4) zusammen. Dabei ist die Definition nach Ausfu¨hrung eines Durchlaufs ebenfalls durch eine Φ-Funktion angegeben, die die Werte auf den zwei mo¨glichen Pfaden innerhalb der Schleife zusammenfasst (doOrder2, doOrder3). Da alle Definitionen entweder einer Konstantenzuweisung oder einer Φ-Funktion entsprechen, ha¨ngt der Wert von doOrder2 lediglich vom Pfad des Kontrollflusses zur Laufzeit ab: Wird die Schleife zum ersten Mal ausgefu¨hrt, wird doOrder2 der Wert von doOrder1, also true, zugewiesen und die Schleifenbedingung daher erfu¨llt. Dasselbe gilt fu¨r jeden weiteren Durchlauf, solange bis die Zuweisung in Knoten n12 ausgefu¨hrt wird. Danach wird doOrder2 der Wert von doOrder3, also false, zugewiesen. In der Folge ist die Bedingung nicht mehr erfu¨llt und die Schleife wird abgebrochen.
Wir nennen Schleifenbedingungen dieser Art, in denen alle Variablen ausschließlich durch ineinander geschachtelte Φ-Funktionen und Konstantenzuweisungen definiert sind, dynamisch konstant. Da der Wert einer solchen Bedingung nur vom zur Laufzeit ausgefu¨hrten Kontrollflusspfad abha¨ngig ist, ko¨nnen die Datenabha¨ngigkeiten der Bedingung offenbar auch durch Kontrollabha¨ngigkeiten repra¨sentiert werden. Durch eine geeignete Transformation der zugeho¨rigen Schleife lassen sich die entsprechenden Kontrollabha¨ngigkeiten erzeugen.2 Auf diese Weise wird die Schleifenbedingung redundant und kann innerhalb des umstrukturierten Prozessfragments entfernt werden. 1 Aufgrund der statischen Betrachtungsweise werden auch Variablendefinitionen innerhalb von Schleifen als einmalige Definitionen angesehen. 2 Als eine Einschra¨nkung der Umstrukturierungsmethode werden solche Φ-Funktionen ausgeschlossen, die innerhalb von Schleifenko¨pfen anderer Schleifen definiert werden. n5
Vor der eigentlichen Transformation einer Schleife mit dynamisch konstanter Schleifenbedingung, wird diese in Normalform u¨berfu¨hrt. Die Normalform ist durch die Auftrennung aller Pfade des Kontrollflusses charakterisiert, auf denen in einem beliebigen Schleifendurchlauf unterschiedliche Werte fu¨r die Variablen der Schleifenbedingung definiert werden. Diese U¨berfu¨hrung ist fu¨r die Schleife des Prozessfragments OrderingSequence in Abbildung 3 dargestellt. Die Variable der dort vorhandenen Bedingung (doOrder2) kann, wie oben beschrieben, fu¨r einen beliebigen Schleifendurchlauf drei verschiedene Werte annehmen. Die Wahl des Wertes wird dabei durch den zuvor ausgefu¨hrten Kontrollflusspfad bestimmt. Um nun die Pfade aufzutrennen, muss der Knoten M erge aufgelo¨st werden, da er zwei der drei mo¨glichen Werte zusammenfu¨hrt (doOrder2 und doOrder3). Da der unmittelbare Nachfolger dieses Knotens gerade dem Schleifenkopf Header entspricht, reicht es dazu aus, die Vorga¨ngerknoten n10 und n13 direkt mit dem Kopf zu verbinden und die Operanden der darin enthaltenen Φ-Funktionen anzupassen (Operand doOrder4 durch doOrder2 und doOrder3 ersetzen). Anschließend kann der Knoten M erge entfernt werden.
Die Normalform wird dann als Blaupause im folgenden Transformationsschritt genutzt. In diesem Schritt werden mehrere Instanzen der Blaupause erzeugt und miteinander verbunden. Wir nennen den Schritt dementsprechend Schleifeninstanziierung. Jede Instanz repra¨sentiert eine mo¨gliche Belegung der in der Schleifenbedingung genutzten Variablen mit konstanten Werten. Fu¨r die Schleife in OrderingSequence werden so zwei Instanzen erzeugt, wie in Abbildung 4 dargestellt. In der ersten Instanz (Instance 1) wird die Variable doOrder2 durch den Wert true ersetzt, in der zweiten (Instance 2) durch den Wert false.
Instance 1 ... n10 n4: Branch ?(true())
True
False
Instance 2
False n15 :. H.eader n16: Branch ?(false())
True n17 ... n22 ...
n25 n24 : doOrder6 = false()
Abb. 4. Transformation unter Verwendung von Schleifeninstanzen
Dadurch ist die Schleifenbedingung in beiden Instanzen statisch auswertbar.
In der Folge lassen sich die Bedingung und die unmo¨glichen Kontrollflusspfade
in OrderingSequence entfernen (Kanten (n4, End) und (n16, n17)). Das
Ergebnis dieser Umstrukturierung ist in Abbildung 5 angegeben. Offenbar ist darin
der Abbruch der Schleifenausfu¨hrung, nach Empfang der Nachricht Complete,
explizit durch den Kontrollfluss wiedergegeben. Innerhalb des zugeho¨rigen
Petrinetzmodells [
Der vorliegende Beitrag beschreibt eine bereits vollsta¨ndig entwickelte Umstrukturierungsmethode fu¨r verteilte Gescha¨ftsprozesse der Sprache WS-BPEL. Die vorgestellte Methode ist in der Lage die Datenabha¨ngigkeiten einer bestimmten Art von Schleifen in semantisch a¨quivalente Kontrollabha¨ngigkeiten zu transformieren. Auf diese Weise ko¨nnen die Prozessmodelle bestehender Analysen pra¨zisiert und so die Verfa¨lschungen von Analyseergebnissen verringert werden.
Die vorgestellte Umstrukturierungsmethode kann auch auf
Verzweigungsbedingungen angewendet werden und ist nicht auf Bedingungen mit einer einzelnen
Variablen oder auf boolesche Variablen beschra¨nkt. Eine detaillierte Darstellung
der Methode, einschließlich der Beschreibung verwendeter Algorithmen und
einem Korrektheitsbeweis, erfolgt in einem technischen Bericht [