Einführung

Ereignisgesteuerte Prozessketten (EPKs) wurden ursprünglich als eine nicht vollständig formalisierte Notation entwickelt, um Geschäftsprozesse zu modellieren. Dies reicht zwar aus, um Prozesse zu dokumentieren und über die Modelle zu diskutieren, für eine automatische Verarbeitung von EPK-Modellen (etwa in Werkzeugen zur Simulation oder Verifikation) muss jedoch eine formale Semantik der Modelle definiert werden.

Hierfür gibt es verschiedene Ansätze, die wir in Abschnitt 2 besprechen. Dort stellen wir auch die Probleme dar, die es bei der Definition einer EPK-Semantik gibt und geben an, wie diese von den verschiedenen Autoren gelöst wurden.

Im Abschnitt 3 werden die bekannten Ansätze bewertet. Insbesondere stellen wir die Frage, wie gut die verschiedenen Ansätze mit den in der Praxis vorhandenen (mitunter wenig strukturierten) Modellen arbeiten können. In Abschnitt 4 schlagen wir Stilregeln für "gut modellierte EPKs" vor. EPKs, die diesen Regeln folgen, lassen sich in Petri-Netze übersetzen, was kurz in Abschnitt 6 besprochen wird. In Abschnitt 5 zeigen wir häufige Fehler, die zur Verletzung der Stilregeln führen und deren (automatisch durchführbare) Korrektur. Im Abschnitt 7 werten wir 285 aus den verschiedensten Quellen gesammelte EPKs aus und überprüfen an diesen die Praxistauglichkeit unserer vorgeschlagenen Stilregeln.

Semantikdefinitionen für EPKs und auftretende Probleme

EPKs wurden ursprünglich eingeführt und verwendet, ohne ihre Semantik formal zu definieren. Demgegenüber bieten Petri-Netze, deren Semantik klar definiert ist, ebenso die Möglichkeit, Abläufe mit Parallelität und Entscheidungsknoten zu beschreiben. Die große Zahl bekannter Forschungsergebnisse aus dem Bereich der Petri-Netze sowie die gute Werkzeug-Unterstützung etwa zur Simulation von Petri-Netzen legen es nahe, zur Definition der Semantik einer EPK diese in ein Petri-Netz zu übersetzen.

Solche Übersetzungen wurden von verschiedenen Autoren vorgeschlagen, darunter van der Aalst [Aal99], Chen/Scheer [CS94], Langner, Schneider und Wehler [LSW97a,LSW97b] und Dehnert/van der Aalst [DA04]. Bei diesen Übersetzungen müssen jeweils Einschränkungen gemacht werden, die wir in den folgenden Unterabschnitten besprechen werden.

Einen anderen Weg beschreiten die Autoren Kindler und Cuntz [Kin04,Cun04,CK04]. Sie beschreiben die möglichen Abläufe eines EPK-Modells mit Hilfe eines Transitionssystems und geben ein Verfahren an, mit dem dessen Transitionsrelation bestimmt werden kann. Dieses Verfahren ist im dem Programm EPCtools implementiert, das zudem einige algorithmische Tricks benutzt, um die Berechnung auch für große EPKs effektiv ausführen zu können. Der Grund dafür, dass über Jahre hinweg immer wieder neue Vorschläge zur Definition einer Semantik gemacht wurden, liegt im Wesentlichen in den Problemen begründet, die in den beiden folgenden Unterabschnitten besprochen werden: der Nichtlokalität von Verknüpfungskonnektoren und der fehlenden Unterstützung mehrfacher Instanziierung.

Probleme durch nichtlokale Konnektoren

Abbildung 1 zeigt ein typisches OR-Konstrukt. Es könnte einer EPK, die die Auswahl von Bewerbern für eine Stelle eines wissenschaftlichen Mitarbeiters beschreibt, entnommen sein. Nach dem OR-Split werden eine, zwei oder alle der dargestellten Aktivitäten parallel ausgeführt, und der Ablauf wird nach dem OR-Join erst fortgesetzt, wenn alle begonnenen Aktivitäten beendet sind. Bei einer Übersetzung der EPK in ein Petri-Netz ergibt sich nun die Frage, wie der OR-Join-Konnektor in ein Petri-Netz-Konstrukt zu übersetzen ist. Das Problem hierbei ist, dass am OR-Join nicht bekannt ist, wie viele parallele Abläufe am OR-Split gestartet wurden, d.h. auf wie viele vom OR-Split gesendete Tokens gewartet werden soll. Diese Frage lässt verschiedene Antwortmöglichkeiten zu, die unter anderem in [Aal99], [Rit00] und [WEAtH05] diskutiert werden. Meist wird die Frage so beantwortet, dass der OR-Join erst dann Kontrollfluss-Tokens ("Prozessordner") weiterreicht, wenn an einem ankommenden Zweig ein Kontrollfluss-Token anliegt und für alle anderen

Referenzen prüfen Lebenslauf lesen

Referenzen geprüft Lebenslauf gelesen

Veröffentlichungen lesen

Veröffentlichungen gelesen

Abbildung

Probleme durch die Blockierung des Tokenflusses

Die üblichen EPK-Semantiken erlauben nicht die mehrfache Instanziierung von Ereignissen oder Funktionen. 1 Wird wie in [Rum99] der Zustand einer EPK durch die Zahl der Tokens ("Prozessmappen") auf den einzelnen Modellelementen (Ereignissen, Funktionen, Prozessegweisern und Konnektoren) definiert, kann es dennoch vorkommen, dass z.B. ein Kontrollfluss-Token eine Funktion erreicht, die bereits aktiv ist. Wie sich das Modell in diesem Falle verhalten soll, ist unklar.

Analoge Überlegungen gelten, wenn wir, wie in [Kin04] vorgeschlagen, einen Zustand einer EPK durch die Zahlen der Tokens auf den Kontrollflusskanten definieren. In der Regel wird hier davon ausgegangen, dass eine Kontrollflusskante, die schon durch ein Token belegt ist, "blockiert", d.h. keine weitere Tokens annehmen kann.

Ausführlich wird diese Frage in [Cun04] analysiert, wo auch eine alternative Semantikdefinition (die eine Belegung einer Kontrollflusskante mit mehreren Tokens erlaubt) besprochen wird.

Diskussion der vorhandenen Lösungsansätze

Die bekannten Lösungsvorschläge für die genannten Probleme lassen sich grob in zwei Klassen einteilen.

In die eine Klasse fallen die Ansätze, die die "gültigen" EPKs durch zusätzliche Regeln für Wohlgeformtheit beschränken. So betrachtet [Aal99] nur EPKs ohne OR-Join. [LSW97a] und [CS94] verlangen strukturierte EPK-Modelle (zu jedem Split-Konnektor gehört ein Join-Konnektor gleichen Typs, die Split/Join-Konstrukte sind sauber verschachtelt, außerdem fordert [LSW97a] zusätzliche Eigenschaften von per XOR-Konnektoren modellierten Iterationen).

Bei der Bewertung dieser Ansätze teilen wir die Einschätzung aus [vDAV05]

OR-Join-Konnektoren

OR-Joins sind das EPK-Notationselement, über dessen semantische Bedeutung am meisten diskutiert wurde[Aal99, LSW97a, Rit00

Die informelle Semantik für OR-Joins, die eindeutig einem OR-Split zugeordnet sind, lautet: "Warte, bis alle vom OR-Split losgeschickten Tokens eingetroffen sind und leite das Token dann an die abgehende Kontrollflusskante weiter". Es ist dann u.a. ein Weg zu finden, wie der OR-Join erfährt, auf welche Tokens er warten muss. [LSW97a] beschreibt hierfür eine Lösung mit Hilfe boolescher Netze (also 0/1-markierter Petri-Netze). Der OR-Split sendet mit 1 markierte Tokens auf den Kontrollflusskanten, auf denen Kontrollfluss stattfinden soll und mit 0 markierte Tokens auf den anderen "nicht aktivierten" Kanten. Der OR-Join wartet nun, bis an allen eingehenden Kontrollflusskanten ein Token eintrifft. Ist mindestens eines davon ein 1-Token , dann wird der Kontrollfluss an die vom OR-Join abgehende Kante weitergeleitet.

Unglücklicherweise ist für diese elegante Lösung ein hoher Preis zu bezahlen: [LSW97a] betrachtet nur EPKs, die sehr strengen Wohlgeformtheits-Kriterien entsprechen. Ein erheblicher Teil der in der Praxis vorkommenden EPKs mit OR-Joins entspricht diesen Kriterien nicht. Somit ist [LSW97a] 4 tragen der in der Praxis verbreiteten Gewohnheit Rechnung, den Kontrollfluss durch "Aussprünge" aus einem Split/Join-Konstrukt zu unterbrechen oder durch ein Endereignis ganz abzubrechen. 3 Wir betrachten nun nur solche EPKs als zulässig, für die alle OR-Joins ein wohlstrukturiertes Konstrukt entsprechend Def. 1 beenden. Insbesondere muss dieses Konstrukt dann mit einem OR-Split beginnen, d.h. jedem OR-Join muss ein OR-Split zugeordnet sein. Die Klasse der lt. unserer Definition zulässigen EPKs ist größer als die Klasse der in [LSW97a] betrachteten EPKs, da zum einen weniger strenge Anforderungen an XOR-Konnektoren in Iterationen gestellt werden, zum anderen die Regeln 3 und 4 in Def. 1 hinzukommen. Im Abschnitt 7 werden wir sehen, dass unsere Definition für zulässige EPKs nahezu keine der von uns gesammelten 285 in der Praxis vorkommenden EPKs unnötigerweise als "unzulässig" ausschließt.

Im Gegensatz zu den in 4.1 und 4.2 genannten Stilregeln, zu deren Test eine Verhaltensanalyse des Modells nötig ist, lassen sich die Stilregeln für OR-Konstrukte mittels statischer Analyse der EPK nachweisen. Dies kann ähnlich zu dem aus [LSW97a] bekannten Vorgehen geschehen, wobei jedoch "Aussprünge" aus Split/Join-Konstrukten und an beliebigen Stellen erlaubte Endereignisse zusätzliche Überlegungen erfordern.

Häufige Fehler und deren Korrektur

[LSW97a] nennt zahlreiche Modellierungsfehler, die teilweise mittels statischer Analyse einer EPK gefunden werden können. Eine solche Analyse müssen wir nach unserem Ansatz ohnehin durchführen, um die Gültigkeit der in Def. 1 aufgeführten Regeln zu prüfen. Bei dieser Gelegenheit können einige typische Modellierungsfehler gleich erkannt und verbessert werden.

Wir haben bei den von uns gesammelten EPKs typische Fehler an OR-Joins analysiert. Oft wurden OR-Joins genutzt, wenn ein XOR-oder AND-Join angebracht gewesen wäre (siehe Abb. 6a)-c), wo wieder Funktionen und Ereignisse weggelassen sind.) Ebenso wurde oft die optionale Ausführung fehlerhaft modelliert (siehe Abb. 6d)). Natürlich ändert sich bei allen in Abb. 6 gezeigten Änderungen nicht die Semantik der EPK, vom theoretischen Standpunkt aus sind die Korrekturen sogar unnötig. Wir bezeichnen diese Modelle trotz- 3 Man kann natürlich einwenden, dass entsprechend der genannten Gewohnheiten modellierte EPKs schlecht modelliert sind, da ein Endereignis erreicht werden kann, wenn noch Synchronisationen ausstehen. Die Zielrichtung dieser Veröffentlichung ist aber eine andere: Wir nehmen zur Kenntnis, welche Modelle in der Praxis vorhanden sind und versuchen, diese so gut wie möglich zu analysieren.

Übersetzung in Petri-Netze

Um nun EPKs, die unseren Stilregeln entsprechen und somit gültig sind, in Petri-Netze zu übersetzen, können wir die in [LSW97a] angegebene Übersetzung übernehmen. Zusätzlich müssen Iterationen (Abb. 2d)) entsprechend der Semantik der XOR-Konnektoren behandelt werden, und es muss dafür gesorgt werden, dass "Aussprünge", die ein Split-Join-Konstrukt vorzeitig beenden (vgl. Abb. 4) 0-Tokens an den nachgeordneten OR-Join senden (und dieser die 0-Tokens ggf. an weitere nachgeordnete OR-Joins weiterreicht). Beide Erweiterungen des Übersetzungsalgorithmus aus [LSW97a] sind recht einfach, denn wir wissen nach der statischen Analyse zu der in Def. 1 gegebenen Stilregel, ob ein XOR-Split die Situation aus Abb. 2c) oder d) oder einen "Aussprung" wie in Abb. 4 darstellt.

Tab. 1 fasst die wesentliche Ergänzung zu der in [LSW97a] angegebenen Übersetzung zusammen. Sie stellt für alle möglichen Split-Konnektoren dar, wie mit 0 und 1 markierte Tokens an die ausgehenden Kontrollflusskanten (symbolisiert durch die Variablen x und y) weitergeleitet werden, wenn auf der eingehenden Kontrollflusskante (symbolisiert durch die Variable z) ein mit 0 oder 1 markiertes Token eintrifft. Die Angabe "0" oder " nachzulesen. EPKs mit kleinen syntaktischen Fehlern haben wir toleriert; 9 Modelle, die in unseren Quellen als "EPK" bezeichnet wurden, hatten jedoch solch gravierende syntaktische Fehler (etwa Aktivitäten, von denen mehrere Kontrollflusskanten ausgehen), dass wir sie beim besten Willen nicht mehr als EPK ansehen konnten und sie daher für die weitere Analyse ignorieren mussten.

Für die verbleibenden 276 EPK-Modelle fanden wir folgendes heraus:

• Keines der Modelle benutzt bewusst die Interpretation, dass zwei an einem XOR-Join zugleich ankommende Tokens den Ablauf blockieren. Wann immer in einem Modell mehr als ein Token zugleich am XOR-Join ankommen konnte, war das Modell klar erkennbar fehlerhaft. Damit ist die in Abschnitt 4.2 vorgeschlagene lokale Semantik von XOR-Joins bei gleichzeitigem Verbot von EPKs, bei denen mehrere Tokens zugleich einen XOR-Join erreichen, sinnvoll.

• 190 EPKs verwendeten keine OR-Joins.

• Die verbleibenden 86 EPKs enthielten insgesamt 151 OR-Joins. 94 davon entsprachen den Stilregeln aus Abschnitt 4.3.

Das eigentlich interessante Resultat ergab sich nun bei der ("in Handarbeit" durchgeführten) Untersuchung der 57 OR-Joins, die nicht den Stilregeln aus Abschnitt 4.3 entsprachen.

Auf 45 davon traf einer der in Abb. 6 gezeigten Fälle zu, d. h. sie sollten besser durch einen anderen Join-Konnektor ersetzt werden. Wie schon erwähnt, kann diese Ersetzung automatisch erfolgen.

Für 10 weitere EPKs, deren OR-Joins nicht den Stilregeln entsprachen, ergab eine genauere Betrachtung, dass diese offensichtlich fehlerhaft waren. 4Wir fanden nur zwei EPKs, die nicht den Stilregeln entsprechen und trotzdem als korrekt modelliert angesehen werden könnten. Beide benutzten das in Abb. 7 gezeigte Konstrukt. Da in diesem Konstrukt ein Token am AND-Join "steckenbleibt", wenn nur eine der Ausnahmen eintritt (was übrigens dann auch verbietet, dieses Konstrukt in einer Schleife mehrfach durchlaufen zu lassen), sollte eine solche Modellierung vermieden werden, so dass eine Einstufung des Modells als "unzulässig" durchaus vertretbar ist.

Ausnahme A aufgetreten

Ausnahme B aufgetreten alles normal normale Verarbeitung

Ausnahmeverarbeitung

Abbildung 7: EPK, die unsere Stilregeln verletzt

Zusammenfassung

Die im letzten Kapitel genannten Zahlen belegen, dass unsere Stilregeln von nahezu allen in der Praxis anzutreffenden Modellen befolgt werden. Dies geschieht meist schon intuitiv, man kann die Regeln dem Modellierer aber auch mit wenigen (bewusst informell