Digital Object Identifier (DOI) 10.1007/s00450-002-0122-0
Informatik Forsch. Entw. (2002) 17: 177–197
© Springer-Verlag 2002
Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration
von Workflow-Instanzen bei der Evolution von Workflow-Schemata
Stefanie Rinderle, Manfred Reichert, Peter Dadam
Abteilung Datenbanken und Informationssysteme, Universit¨
at Ulm, 89069 Ulm (e-mail: {rinderle, reichert, dadam}@informatik.uni-ulm.de)
Eingegangen am 2. Juli 2002 / Angenommen am 15. Oktober 2002
Zusammenfassung. Sollen Workflow-Management-Sys-
teme (WfMS) in umfassender Weise f¨
ur die rechnerbasierte
Verwaltung und Steuerung von Gesch¨
aftsprozessen einsetzbar
sein, m¨
ussen die von ihnen verwalteten Workflow-Schemata
und -Instanzen bei Bedarf rasch anpassbar sein. Dabei
m¨
ussen die auf Basis eines (alten) Workflow-Schemas er-
zeugten Instanzen auch nach dessen ¨
Anderung ungest¨
ort
weiterlaufen k¨
onnen, etwa durch Bereitstellung geeigneter
Versionskonzepte. Sehr viel schwieriger wird es, wenn
die angewandten Schema¨
anderungen – wo gew¨
unscht und
m¨
oglich – auch auf die bereits (vielleicht in großer Zahl)
laufenden Workflow-Instanzen ¨
ubertragen werden sollen.
Dies bei Bedarf zu k¨
onnen – und zwar ohne Inkonsistenzen
oder Fehler zu verursachen – ist aber ungemein wichtig,
wenn ein WfMS breit und flexibel einsetzbar sein soll. In
diesem Beitrag wird ein Ansatz zur effizienten Pr¨
ufung der
Vertr¨
aglichkeit von Workflow-Instanzen mit einem ge¨
ander-
ten Workflow-Schema vorgestellt. Durch Einbeziehung aller
Beschreibungskonstrukte (z.B. auch Schleifen und Daten-
߬
usse) und damit zusammenh¨
angender Fragestellungen wird
dar¨
uber hinaus zum ersten Mal die Grundlage f¨
ur ein umfas-
sendes ¨
Anderungsmanagement geschaffen. Außerdem wird
aufgezeigt, wie der Benutzer bei der Migration vertr¨
aglicher
Instanzen auf das neue Schema konkret unterst¨
utzt werden
kann.
Schl¨
usselw¨
orter: Workflow-Management – Adaptive Work-
flows – Schema-Evolution – Vertr¨
aglichkeit – Migration
Abstract. A promising technology to enhance the flexibili-
ty of business processes is offered by workflow management
systems (WfMS). In principle, changes of the process logic
of application systems can be easily accomplished by mo-
difying the (graphical) workflow (WF) schema accordingly.
In doing so, it is extremely important that already running
WF instances will not be disturbed. In current WfMS, this is
achieved by the use of simple versioning concepts. WF schema
adaptations, however, get much more difficult if the applied
changes are to be propagated to already running WF instan-
Diese Arbeit wurde im Rahmen des Projekts „ ¨
Ande-
rungsmanagement in adaptiven Workflow-Management-Systemen”
der Deutschen Forschungsgemeinschaft (DFG) erstellt.
ces as well. On the one hand such a feature is indispensa-
ble for many process-centered applications, on the other hand
dynamic changes must not violate WF consistency. This pa-
per presents a comprehensive framework for propagating WF
schema changes to in-progress WF instances. In particular, we
show how this can be done in an efficient manner and without
causing inconsistencies or errors in the sequel. We establish
well-defined criteria for checking whether a particular WF in-
stance is compliant with the new WF schema or not, and we
indicate which information becomes necessary in this context.
Furthermore, we discuss how compliant WF instances can be
automatically migrated to the new schema.
Keywords: Workflow management, Adaptive workflows,
Schema evolution, Compliance, Migration
CR Subject Classification: H.4, J.1
1 Einleitung
F¨
ur Unternehmen gewinnt die elektronische Unterst¨
utzung
ihrer Gesch¨
aftsprozesse zunehmend an Bedeutung. Sowohl
f¨
ur traditionelle Anwendungssysteme als auch f¨
ur An-
wendungen im sich rasch entwickelnden E-Business-Bereich
wird in verst¨
arktem Maße eine aktive Prozessunterst¨
utzung
gew¨
unscht [8,12,17]. Prozessorientierte Informationssysteme
sollen die Durchf¨
uhrung unternehmensweiter und -¨
ubergrei-
fenderAbl¨
aufe aktiv koordinieren,Anwendungskomponenten
prozessorientiert integrieren, Benutzer ablaufbezogen unter-
st¨
utzen, den Fortgang der Prozesse ¨
uberwachen und ihren rea-
len Verlauf m¨
oglichst l¨
uckenlos dokumentieren [20,28].
Sollen Gesch¨
aftsprozesse in solch umfassender Weise
unterst¨
utzt werden, ist zu beachten, dass prozessorientierte
Anwendungen sehr viel h¨
aufiger angepasst werden m¨
ussen
als funktionsorientierte Informationssysteme [12,23]. ¨
Ande-
rungen k¨
onnen etwa erforderlich werden, wenn neue ge-
setzliche Bestimmungen in Kraft treten, optimierte oder neu
gestaltete Prozesse umgesetzt werden sollen [18] oder auf
ein ver¨
andertes Marktgeschehen reagiert werden muss [17].
Wichtig ist, dass notwendige Prozess¨
anderungen bei Bedarf
178 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
rasch erfolgen k¨
onnen. Idealerweise sollte auch die M¨
oglich-
keit bestehen, die bereits laufenden „alten” Prozesse – soweit
gew¨
unscht und sinnvoll – auf die neue Abwicklung umzustel-
len. Eine solche Prozessunterst¨
utzung findet man bei heutigen
betrieblichen Informationssystemen entweder gar nicht oder
aber sie ist h¨
ochst unflexibel implementiert. H¨
aufig ist die Ab-
laufsteuerung direkt in den Anwendungsprogrammen codiert,
was die Anwendungsentwicklung sehr aufwendig und fehler-
tr¨
achtig gestaltet.
Eine vielversprechende Technologie bieten Workflow-
Management-Systeme (WfMS) [20,25,28]. Charakteristisch
ist hier die Trennung von Prozesslogik undAnwendungscode,
d.h. die Ablauflogik der unterst¨
utzten Arbeitsprozesse (engl.
Workflow, WF) wird dem WfMS explizit durch (graphische)
Modellierung der Prozesse bekannt gemacht und nicht im
Programmcode „versteckt”. Zu diesem Zweck muss f¨
ur je-
den zu unterst¨
utzenden Prozess-Typ ein WF-Schema erstellt
und im System hinterlegt werden. Ein solchesWF-Schema be-
schreibt die verschiedenenAspekte einesArbeitsprozesses wie
Kontroll- und Daten߬
usse, Bearbeiterzuordnungen oder Aus-
nahmebehandlungen. Des Weiteren k¨
onnen den WF-Schritten
(Aktivit¨
aten) Anwendungskomponenten zugeordnet werden,
die dann w¨
ahrend der WF-Bearbeitung zur Ausf¨
uhrung kom-
men.Ausgehend von einem solchen WF-Schema k¨
onnen neue
WF-Instanzen erzeugt werden, f¨
ur die das WfMS die Durch-
f¨
uhrung von Aktivit¨
aten koordiniert, anstehende Aktivit¨
aten
denAnwendern ¨
uberArbeitslisten anbietet, deren fristgerechte
Durchf¨
uhrung ¨
uberwacht und die zugeh¨
origen Anwendungs-
programme (mit den richtigen Daten) aufruft.
1.1 Problembeschreibung
Anpassungen k¨
onnen einen WF-Typ (bzw. sein Schema) als
Ganzes oder auch nur einzelne Instanzen betreffen. Bei ¨
An-
derungen aufTypebene ist zu fordern, dass die auf Basis des al-
ten WF-Schemas erzeugten Instanzen ungest¨
ort weiterlaufen.
Dies l¨
asst sich z.B. durch geeignete Versionierungskonzepte
f¨
ur WF-Schemata erreichen, gem¨
aß denen zuk¨
unftige Instan-
zen nach dem neuen Schema ausgef¨
uhrt werden, w¨
ahrend be-
reits aktive Instanzen nach dem alten Schema weiterlaufen.
Dies ist f¨
ur Prozesse mit kurzer Dauer ausreichend, wirft aber
f¨
ur lang laufende Prozesse, etwa beim Entwurf technischer
Systeme [8] oder bei Behandlungsprozessen im Krankenhaus
[12], erhebliche Probleme auf. Hier muss dann ggf. f¨
ur l¨
angere
Zeit eine Koexistenz von Instanzen alter und neuer Form und
damit ein Durcheinander bei der Prozessabwicklung in Kauf
genommen werden. Zudem ist eine Fortf¨
uhrung der Prozes-
se auf Grundlage des alten Schemas nicht immer akzeptabel,
etwa wenn dadurch gesetzliche Vorschriften oder Gesch¨
afts-
regeln des Unternehmens (z.B. Behandlungsrichtlinien eines
Krankenhauses) verletzt werden.
Von Anwenderseite besteht deshalb h¨
aufig der Wunsch,
die auf Schemaebene definierten ¨
Anderungen auch auf die
bereits (vielleicht in großer Zahl) laufenden WF-Instanzen
zu ¨
ubertragen. Wir sprechen von der Propagation einer WF-
Schema¨
anderung auf laufendeWF-Instanzen bzw. von der Mi-
gration dieser („alten”) WF-Instanzen auf das ge¨
anderte WF-
Schema. Dies bei Bedarf zu k¨
onnen, und zwar ohne dass es
dadurch zu Inkonsistenzen oder Fehlern kommt, ist unerl¨
ass-
lich, wenn ein WfMS breit und flexibel einsetzbar sein soll.
KommerzielleWfMS bieten hierf¨
ur keine ausreichende Unter-
st¨
utzung. Sie erlauben es entweder gar nicht, die ¨
Anderungen
eines Schemas auf laufende Instanzen zu propagieren, oder
aber dies kann zu Inkonsistenzen und Systemabst¨
urzen f¨
uhren
[26].
F¨
ur die Ab¨
anderung von WF-Schemata und die Migration
von WF-Instanzen auf das neue WF-Schema sind folgende
Eigenschaften zu fordern:
•Korrektheit/Konsistenz: Eine WF-Instanz darf nur dann
auf das ge¨
anderte WF-Schema migriert werden, wenn es
dadurch in der Folge nicht zu unerw¨
unschten Effekten
kommt.
•Anpassungen im laufenden Betrieb und Effizienz: Die
Propagation von ¨
Anderungen eines WF-Schemas auf
(„alte”) WF-Instanzen muss im laufenden Betrieb m¨
og-
lich sein. Dies bedingt, dass die bei Migrationen not-
wendigen Korrektheits¨
uberpr¨
ufungen und Zustandsan-
passungen, selbst bei großer Instanzzahl, effizient durch-
f¨
uhrbar sind. Beispielsweise sollten hierf¨
ur ben¨
otigte
Sperren auf Instanzen bestimmte Zeitschranken nicht
¨
uberschreiten.
•Vollst¨
andigkeit: Es m¨
ussen alle Aspekte eines
WF-Schemas, die von ¨
Anderungen betroffen sein
k¨
onnen, ber¨
ucksichtigt werden. Insbesondere d¨
urfen
wichtige Elemente (z.B. Schleifen und Daten߬
usse) nicht
unber¨
ucksichtigt bleiben, nur weil dies die Komplexit¨
at
der Betrachtungen reduziert.
•Benutzerfreundlichkeit: Bei Migrationen sind teure Be-
nutzerinteraktionen (m¨
oglichst) zu vermeiden. Dies w¨
urde
zum einen zu Verz¨
ogerungen bei der Ausf¨
uhrung der WF-
Instanzen f¨
uhren, zum anderen w¨
aren betroffene Benutzer
(z.B. Modellierer bzw. Prozessverantwortliche) vielfach
¨
uberfordert.
Weitere Anforderungen betreffen den Umgang mit nicht
migrierbaren WF-Instanzen, die Einbeziehung von Semantik-
Aspekten bei Vertr¨
aglichkeitspr¨
ufungen, das Zusammenspiel
von ¨
Anderungen auf Typ- und Instanz-Ebene (im Kontext von
Ad-hoc- ¨
Anderungen) sowie ¨
Anderungen anderer Bestand-
teile prozessorientierter Informationssysteme (z.B. des Or-
ganisationsmodells). Auf diese Aspekte wird in diesem Bei-
trag aus Platzgr¨
unden nicht eingegangen (siehe [33,39]).
Die Evolution von WF-Schemata weist gewisse Parallelen
zu Schema¨
anderungen in DBMS auf [4,10,11]. Die Probleme
sind relativ ¨
ahnlich, wenn man nur die Abbildung der Ele-
mente (Knoten, Kanten) des alten WF-Schemas auf das neue
WF-Schema betrachtet. Bezieht man jedoch die Instanzebene
(also die laufenden Prozesse) mit ein, ist zu beachten, dass
sich jede Instanz in einem anderen Zustand befinden kann.
Abh¨
angig vom konkreten Zustand sowie von den angebo-
tenen Migrationsoperationen, kann eine Migration zul¨
assig
sein oder nicht. Sowohl f¨
ur diese Einteilung von Instanzen als
auch f¨
ur die (konkrete) Durchf¨
uhrung von Migrationen sind
effiziente L¨
osungen gefordert. Eine l¨
angere Blockierung der
(vielleicht sehr vielen) betroffenenWF-Instanzen w¨
ahrend der
Analyse- und Migrationsphase sollte deshalb vermieden oder
zumindest auf die tats¨
achlich betroffenen WF-Instanzen die-
ses Typs eingeschr¨
ankt werden.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 179
1.2 Beitrag
Im ADEPT-Projekt arbeiten wir seit einigen Jahren an der
Entwicklung einer Technologie, die es erm¨
oglichen soll, un-
ternehmensweite Gesch¨
aftsprozesse zu modellieren, zu steu-
ern, zu ¨
uberwachen und sie auf einfache Weise – bei Be-
darf auch im laufenden Betrieb – flexibel zu ver¨
andern [6,
12,31,29]. In unseren bisherigen Ver¨
offentlichungen haben
wir uns mit Ad-hoc- ¨
Anderungen einzelner WF-Instanzen und
mit der Modellierung planbarer Abweichungen befasst [7,
12,31,32]. Schwerpunkte bildeten dabei die Definition ge-
eigneter ¨
Anderungsoperationen (bzw. Graphtransformations-
regeln) sowie Korrektheits-, Skalierbarkeits- und Implemen-
tationsaspekte. Die wichtigsten Konzepte haben wir proto-
typisch im ADEPT-WfMS [19] umgesetzt, das mittlerweile
auch von Partnern f¨
ur die Realisierung anspruchsvoller WF-
Anwendungen eingesetzt wird [5,27].
Ziel des vorliegenden Beitrags ist die Entwicklung eines
theoretisch fundierten und umfassenden Ansatzes f¨
ur WF-
Typ ¨
anderungen und deren Propagation auf laufende WF-
Instanzen. Dazu sind zun¨
achst geeignete, ¨
uberpr¨
ufbare Kri-
terien erforderlich, durch deren Anwendung sich die Kon-
sistenz von WF-Instanzen auch bei ihrer Migration auf ein
ge¨
andertes WF-Schema sicherstellen l¨
asst. Dabei m¨
ussen die
betroffenen WF-Instanzen (bzw. Ausschnitte davon) f¨
ur eine
bestimmte Zeitspanne angehalten werden, um zu verhindern,
dass sie in ihrer Ausf¨
uhrung weiterschreiten und deshalb der
Zustand, der als Grundlage f¨
ur die Analysen herangezogen
wird, nicht mehr aktuell ist. F¨
ur die meisten Anwendungen
ist es jedoch nicht akzeptabel, dass die zu Analyse- und An-
passungszwecken n¨
otigen Sperren auf laufenden Instanzen zu
lange gehalten werden. Deshalb stellen wir in diesem Bei-
trag erstmals einfache Korrektheitspr¨
ufungen f¨
ur WF-Instanz-
migrationen vor, die sich durch eine Minimierung der hierf¨
ur
ben¨
otigten Information und Reduzierung der Komplexit¨
at er-
forderlicher Analysen auszeichnen.
Die effiziente Pr¨
ufung auf Vertr¨
aglichkeit ist jedoch nur
eine Seite der Medaille. Ebenso wichtig ist die Durchf¨
uhrung
der Migrationen selbst. Wir diskutieren hierzu prinzipielle L¨
o-
sungsans¨
atze und stellen ein Verfahren vor, mit dem sich die
bei Instanzmigrationen notwendigen Zustandsanpassungen
automatisch und effizient vornehmen lassen. Dabei soll einer-
seits der Umfang erforderlicher Zustandsneubewertungen auf
ein Minimum reduziert werden, andererseits soll imAnschluss
wieder ein korrekterAusf¨
uhrungszustand resultieren. Ein wei-
teres wichtiges Anliegen dieses Beitrags ist, die vorgestellten
Analyseverfahren nicht auf einfache Basiskonstrukte einzu-
schr¨
anken, sondern auch Instanzmigrationen in Verbindung
mit Schleifen¨
anderungen und Datenflussanpassungen zu be-
trachten. F¨
ur all diese F¨
alle werden wir in diesem Beitrag
einfach ¨
uberpr¨
ufbare, pr¨
azise Bedingungen angeben.
Kapitel 2 behandelt wichtige Grundlagen, die f¨
ur das wei-
tere Verst¨
andnis erforderlich sind. In Kapitel 3 definieren wir
Kriterien f¨
ur die Vertr¨
aglichkeit von Instanzen mit einem ge-
¨
anderten Schema. Wir zeigen, unter welchenVoraussetzungen
diese erf¨
ullt sind und wie sie sich effizient ¨
uberpr¨
ufen lassen.
Kapitel 4 behandelt die Migration vertr¨
aglicher WF-Instanzen
auf ein ge¨
andertes Schema und diskutiert Strategien f¨
ur den
Umgang mit nicht migrierbaren F¨
allen. In Kapitel 5 verglei-
chen wir unserenAnsatz zun¨
achst mit generellenAlternativen,
bevor wir dann ausgew¨
ahlte Ans¨
atze aus der Literatur disku-
tieren. Der Beitrag schließt mit einer Zusammenfassung und
einem Ausblick.
2 Grundlagen
Den folgenden Betrachtungen legen wir das von uns ent-
wickelteADEPTWorkflow-Metamodell [29,31] zugrunde. Es
ist einerseits ausdrucksm¨
achtig genug, um reale Prozesse ab-
bilden zu k¨
onnen [12], andererseits sind die beschreibbaren
WF-Schemata sowohl f¨
ur Entwerfer als auch Anwender gut
verst¨
andlich. Modelliert werden k¨
onnen alle relevanten As-
pekte eines Arbeitsprozesses, wie Kontroll- und Daten߬
usse,
Bearbeiterzuordnungen, zeitliche Abh¨
angigkeiten oder plan-
bare Abweichungen [6,30,31]. Dar¨
uber hinaus hat sich das
ADEPT-Metamodell im Zusammenhang mit anderen wich-
tigen Aspekten, wie statischen und dynamischen Modell-
analysen [29], Ad-hoc- ¨
Anderungen einzelner WF-Instanzen
[31] oder verteilter Ausf¨
uhrung von Workflows [6] sehr gut
bew¨
ahrt. Auch das Zusammenspiel dieser Aspekte haben wir
eingehend untersucht [7,19]. Wir werden im Folgenden dar-
legen, dass das ADEPT-Metamodell auch f¨
ur die Evolution
von WF-Schemata und die kontrollierte Migration von Instan-
zen gut geeignet ist.
2.1 WF-Modellierung und -Ausf¨
uhrung
Die Spezifikation einesArbeitsprozesses erfolgt durch graphi-
sche Modellierung des WF-Schemas. Dieses legt u.a. dieAus-
f¨
uhrungsreihenfolgen und -bedingungen von Aktivit¨
aten fest.
Intern werden solche Kontroll߬
usse durch attribuierte WF-
Graphen repr¨
asentiert, die sich durch unterscheidbare Knoten-
und Kantentypen auszeichnen. Dieser Ansatz erleichtert zum
einen die (effiziente)Analyse vonWF-Schemata, zum anderen
ist er f¨
ur die interpretative Ausf¨
uhrung der WF-Graphen n¨
utz-
lich [29]. Zur formalen Repr¨
asentation eines Schemas Sund
zur pr¨
azisen Definition von Schema¨
anderungen verwenden
wir eine mengenbasierte Darstellung S = (N, E, ...),
wobei Ndie Knotenmenge und Edie Kantenmenge von S
beschreibt.
Jeder Kontrollkante ewird ein Kantentyp ET(e) aus
EdgeTypes = {CONTROL E, SYNC E, LOOP E}
zugeordnet. Dabei definiert CONTROL E„normale”
Reihenfolgebeziehungen, SYNC E„wartet-auf”-Be-
ziehungen zwischen Aktivit¨
aten paralleler Ablaufzweige
und LOOP ESchleifenr¨
uckspr¨
unge [31]. Des Weiteren
besitzt jeder Knoten neinen Typ NT(n) aus der Menge
NodeTypes = {STARTFLOW, ENDFLOW, ACTIVITY,
STARTLOOP, END-LOOP, AND-Split, AND-Join,
XOR-Split, XOR-Join}. Auf Grundlage dieser Modell-
elemente k¨
onnen Sequenzen, Parallel-Verzweigungen
(AND-Split, AND-Join), Alternativ-Verzweigungen
(XOR-Split, XOR-Join) und Schleifen (STARTLOOP,
ENDLOOP) modelliert werden. In unserem Ansatz erfolgt
dies ¨
uber ein Blockkonzept, das wir auch in diesem Bei-
trag verwenden. Die angestellten Betrachtungen lassen
sich unter gewissen Voraussetzungen aber auch auf andere
WF-Ausf¨
uhrungsmodelle ¨
ubertragen.
Ausgehend von einem WF-Schema Sk¨
onnen neue WF-
Instanzen erzeugt und gestartet werden. Damit der WF-Server
180 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
c) Ablaufhistorien:
Ablaufhistorie
(I1 auf S):
...
START(A), END(A),
START(B), END(B),
START(C)
Ablaufhistorie
(I2 auf S):
...
START(A), END(A),
START(B), END(B),
START(D), END(D),
START(C), END(C),
START(E), END(E),
a) Modellierungszeit
WF-Schema S:
b) Ausführungszeit
WF-Instanz I1:
A
B
D
C
E
F
…
…
WF-Instanz I2:
A
B
D
C
E
F
…
…
ET = EdgeType
NT = NodeType
…
A
B
D
C
E
F
…
ET=CONTROL_E
NT=AND-Split NT=AND-Join
Knotenzustände Kantenzustände
NS = ACTIVATED ES = TRUE_SIGNALED
NS = RUNNING
NS = COMPLETED
Abb. 1. Modellierung und Ausf¨
uhrung von Workflows in ADEPT
die f¨
ur eine bestimmte Instanz zur Ausf¨
uhrung anstehenden
Aktivit¨
aten ermitteln kann, ben¨
otigt er entsprechende Zu-
standsinformationen. Dazu werden auf Instanzebene jedem
Knoten nund jeder Kante eZustandsmarkierungen NS(n)
bzw. ES(e) zugeordnet. Ihre Festlegung erfolgt nach wohl
definierten Regeln (siehe sp¨
ater), wobei die Markierungen
durchlaufener Bereiche (mit Ausnahme von Schleifenr¨
uck-
spr¨
ungen) erhalten bleiben. Zus¨
atzlich werden Knoten und
Kanten der Ablaufpfade, die nicht mehr durchlaufen werden,
als abgew¨
ahlt markiert.1Der Zustand einer einzelnen Akti-
vit¨
at ist initial NOT ACTIVATED und geht bei ihrer Aktivie-
rung in ACTIVATED ¨
uber. Bei manuellen Aktivit¨
aten wer-
den dann entsprechende Arbeitsauftr¨
age in die Arbeitslisten
potenzieller Bearbeiter eingetragen. Wird eine aktivierte Ak-
tivit¨
at zur Bearbeitung ausgew¨
ahlt und gestartet, geht sie in
den Zustand RUNNING ¨
uber. Dabei werden entsprechende
Arbeitsauftr¨
age aus den Arbeitslisten anderer Benutzer ent-
fernt. Bei erfolgreicher Beendigung erh¨
alt die Aktivit¨
at den
Status COMPLETED. Steht dagegen fest, dass sie in der Folge
nicht mehr ausf¨
uhrbar ist, wird ihr der Zustand SKIPPED zu-
gewiesen. Kanten wird initial der Zustand NOT SIGNALED
zugeordnet. Im Verlauf der Ausf¨
uhrung werden sie entweder
mit TRUE SIGNALED oder FALSE SIGNALED markiert.
Grundlegend ist auch die Ablaufhistorie einer WF-Instanz
(vgl. Abb. 2), in welcher unter anderem Informationen zum
Start und Ende von Aktivit¨
aten protokolliert werden. Pr¨
aziser
ausgedr¨
uckt, schreibt jede Aktivit¨
at beim ¨
Ubergang in den
Zustand RUNNING einen Starteintrag, beim ¨
Ubergang in den
Zustand COMPLETED einen Endeintrag in die Ablaufhistorie.
2.2 Definition und ¨
Anderung von WF-Schemata
Eine zentrale Forderung bei der Erstellung und ¨
Anderung von
WF-Schemata ist, dass die Korrektheit und Konsistenz von
Schema- und Instanzdaten zu jedem Zeitpunkt gew¨
ahrleistet
sind. Zu diesem Zweck f¨
uhrt das ADEPT-WfMS schon zur
Modellierzeit eine Vielzahl an Korrektheitspr¨
ufungen durch.
1Aufgrund der Struktureigenschaften von ADEPT WF-Graphen
k¨
onnen die aktuellen Knotenmarkierungen einer WF-Instanz auch
aus den Zust¨
anden der gerade bearbeiteten Aktivit¨
aten sowie den
Verzweigungsentscheidungen bereits beendeter XOR-Split- und
Schleifenendknoten abgeleitet werden.
Insbesondere m¨
ussen sowohl f¨
ur laufende als auch f¨
ur zu-
k¨
unftige WF-Instanzen unerw¨
unschte Effekte wie Daten-
Inkonsistenzen,Verklemmungen oder fehlerhafteAufrufe von
Aktivit¨
atenprogrammen ausgeschlossen werden [29]. Not-
wendige Voraussetzung hierf¨
ur ist, dass nach Modifikation
eines (korrekten) Quell-Schemas Swieder ein korrektes Ziel-
Schema S’ resultiert. F¨
ur diesen statischen Fall wird zun¨
achst
nur die korrekte Transformation des WF-Schemas (ohne In-
stanzen) betrachtet. Sie bildet nicht den Fokus dieserArbeit, ist
aber eine wichtige Voraussetzung f¨
ur die korrekte Migration
von Instanzen.
In unserem Ansatz kommen wir dem nach, indem der Mo-
dellierer auf semantisch hoher Ebene ein WF-Schema Smit-
tels eines syntaxgesteuerten WF-Editors sowie einer vollst¨
an-
digen Menge von Modifikationsoperationen (z. B. f¨
ur das Ein-
f¨
ugen einer Aktivit¨
at zwischen zwei Knotenmengen oder das
L¨
oschen von Schleifenbl¨
ocken) korrekt ab¨
andern kann [31,
29]. Die Korrektheit f¨
ur den statischen Fall wird durch for-
maleVor- und Nachbedingungen in Bezug auf dieAnwendung
dieser ¨
Anderungsoperationen sichergestellt. Intern lassen sich
solche Operationen auf einfache Einf¨
uge- und L¨
oschopera-
tionen von Knoten und Kanten abbilden, so dass wir uns in
diesem Beitrag weitgehend auf diese Elementaroperationen
beschr¨
anken werden.
3 Effiziente Vertr¨
aglichkeitspr¨
ufungen
bei ¨
Anderungen des WF-Schemas
Fokus dieses Abschnitts bildet die grundlegende Frage, an-
hand welcher Informationen das WfMS ¨
uberpr¨
ufen soll, ob
¨
Anderungen eines WF-Schemas korrekt auf laufende WF-
Instanzen propagiert werden k¨
onnen. Dazu definieren wir in
Abschnitt 3.1 ein allgemeing¨
ultiges, formales Kriterium zur
Feststellung der Vertr¨
aglichkeit von WF-Instanzen mit einem
ge¨
anderten WF-Schema. Wie sich dieses Kriterium in der
Praxis effizient ¨
uberpr¨
ufen l¨
asst, zeigen die Abschnitte 3.2
(f¨
ur Kontrollfluss- ¨
Anderungen) und 3.3 (f¨
ur Datenfluss- ¨
An-
derungen).
Wie das nachfolgende Beispiel zeigt, darf eine ¨
An-
derungspropagation niemals unkontrolliert erfolgen. Anson-
sten k¨
onnen im Verlauf der weiteren WF-Ausf¨
uhrung ernst-
hafte Probleme wie Verklemmungen oder fehlerhafte Akti-
vit¨
atenprogrammaufrufe resultieren.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 181
Logischer Ausführungsgraph für Instanz I1
WF-Schema-Verwaltung
Puffer
B
C
D
E LE
L
s
A
B
C
D
E L
E
Ls
A
Instanzdaten Vorlagendaten
WF-Markierungen WF-Schemata
Hauptspeicher
Logische
Ausführungsschicht
Markierungen
I1
I
2
A LS B C D E LE
A LS B C D E LE
…
Cache
WF-Instanz-Datenverwaltung
• Versionen und zugehörige
WF-Schemata (intern als
Versionsbaum verwaltet)
• Aktivitätenvorlagen (mit
zugeordneten Anwendungs-
komponenten)
A
B
C
D E
B
C
D
E LE
Ls
A
WF-Typen:
T1:
WF-Instanzen:
Markierungen
Bearbeiter
Ablaufhistorie I
3 (vereinfacht):
START(A,1), END(A,1), START(Ls,1), END(LS,1), START(B,1),
END(B,1), START(C,1), START(D,1), END(D,1), END(C,1),
START(E,1), END(E,1), START(LE,1), END(LE,1), START(Ls,2),
END(LS,2), START(B,2), END(B,2), START(C,2), START(D,2),
END(D,2), END(C,2), START(E,2), END(E,2), START(LE,2),
END(LE,2), START(Ls,3), END(LS,3), START(B,3), END(B,3),
START(C,3), START(D,3), END(D,3), END(C,3), START(E,3),
END(E,3), START(LE,3), END(LE,3), START(Ls,4), END(LS,4),
START(B,4), END(B,4), START(C,4), START(D,4), END(D,4),
END(C,4), START(E,4), END(E,4), START(LE,4), END(LE,4),
START(Ls,5), END(LS,5), START(B,5), END(B,5), START(C,5),
START(D,5), END(D,5), END(C,5), START(E,5), END(E,5),
START(LE,5), END(LE,5), START(Ls,6), END(LS,6), START(B,6),
END(B,6), START(C,6), START(D,6), END(D,6), END(C,6),
START(E,6), END(E,6), START(LE,6), END(LE,6),…
T2:
Persistenzschicht
Markierungen
I1
I2
I3
A LS B C D E LE
A LS B C D E LE
A LS B C D E LE
Abb. 2. Schema- und Instanzverwal-
tung in WfMS (vereinfacht)
Beispiel In das Schema Saus Abb. 3a werden zwei neue
Schritte und eine Datenabh¨
angigkeit zwischen ihnen ein-
gef¨
ugt, so dass wieder ein korrektes Schema S’ resul-
tiert. Abb. 3b zeigt von Sabgeleitete Instanzen I1und
I2. Bei Propagierung der Schema¨
anderung auf I1w¨
urde
der Schritt Allergietest durchf¨
uhren in einen be-
reits durchlaufenen Bereich eingef¨
ugt, wodurch das Ausgabe-
datum Allergietyp vor Aktivierung des datenabh¨
angigen
Schritts Arznei verordnen nicht mehr geschrieben wer-
den k¨
onnte. Liest die neu eingef¨
ugteAktivit¨
at Arznei ver-
ordnen dieses Datum obligat, bleiben Eingabeparameter
des zugeordneten Aktivit¨
atenprogramms unversorgt, was zu
schwerwiegenden Konsequenzen f¨
uhren kann (z. B. Pro-
grammabst¨
urze). F¨
ur I2dagegen k¨
onnte Allergietest
durchf¨
uhren dasAusgabedatum schreiben, so dass dieAk-
tivit¨
at Arznei verordnen korrekt versorgt werden kann.
3.1 Vertr¨
aglichkeit von WF-Instanzen
mit dem ge¨
anderten WF-Schema
Angenommen auf Typebene wird nun ein korrektes WF-
Schema Sin ein wiederum korrektes Schema S’ transfor-
miert. Dann d¨
urfen die vorgenommenen ¨
Anderungen nur dann
auf eine Instanz Ivon Spropagiert werden, wenn Iauch
auf Grundlage von S’ korrekt ausf¨
uhrbar ist, d.h. wenn die
WF-Instanz I- entsprechend ihrem bisherigen Verlauf - auch
gem¨
aß S’ ausgef¨
uhrt h¨
atte werden k¨
onnen und dabei die-
selben Effekte auf WF-Variablen (bzw. WF-Daten) bewirkt
h¨
atte (insbesondere darf es infolge einer Migration nicht zu
einer „Verf¨
alschung” der Vergangenheit kommen). Wir nen-
nen Idann vertr¨
aglich mit S’.
Die spannende Frage ist nun, unter welchen Bedingun-
gen f¨
ur WF-Instanzen zuverl¨
assige Vertr¨
aglichkeitsaussagen
getroffen werden k¨
onnen und welche Informationen f¨
ur ent-
sprechende ¨
Uberpr¨
ufungen (minimal) ben¨
otigt werden. Intui-
tiv ist klar, dass man hierf¨
ur gewisse Daten zum bisherigen
Verlauf der WF-Ausf¨
uhrung ben¨
otigt. ImADEPT-WfMS wer-
den, wie in einigen anderen Ans¨
atzen auch, Informationen
zum Start und Ende von Aktivit¨
atenbearbeitungen in einer
Ablaufhistorie verwaltet, die u.a. auch f¨
ur das korrekte R¨
uck-
setzen von WF-Instanzen im Fehlerfall genutzt wird. Bei Ver-
wendung der Ablaufhistorie Aeiner WF-Instanz Ikann Ver-
tr¨
aglichkeit mit dem ge¨
anderten WF-Schema S’ zugesichert
werden, wenn Aauch bei Ausf¨
uhrung auf S’ erzeugbar ge-
wesen w¨
are. Formal:
Definition 3.1 (Vertr¨
aglichkeits-Kriterium). Sei S=
(N, E, ...)ein korrektes WF-Schema und I eine davon abge-
leitete WF-Instanz mit Ablaufhistorie A=<e
0,...,e
t>und
Markierung Mt;e0,...,e
tentsprechen dabei den Start-/End-
ereignissen zu laufenden bzw. beendeten Aktivit¨
aten, deren se-
182 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
quenzielleAnwendung auf I dieWF-Instanz von ihrer Anfangs-
markierung M0,¨
uber Zwischenmarkierungen M1,...,M
t−1,
in ihre aktuelle Markierung Mt¨
uberf¨
uhrt hat (kurz: M0[e0>
M1[e1>...M
t−1[et>M
t).2
S werde nun durch eine ¨
Anderung ∆auf das (korrekte)
WF-Schema S’transformiert. Sei M
tdie Markierung des Aus-
f¨
uhrungsgraphen von I, der sich ergibt, wenn ∆auf I pro-
pagiert wird und anschließend eine Neubewertung des Zu-
stands des Ausf¨
uhrungsgraphen (nach wohl definierten Re-
geln) durchgef¨
uhrt wird. Dann ist I genau dann vertr¨
aglich
mit S’, wenn dieselbe Folge von Ereignissen e0,...,e
t, aus-
gehend von einer Anfangsmarkierung M
0, auf WF-Schema S’
anwendbar ist und im Anschluss wieder die konsistente Mar-
kierung M
tresultiert. Formal:
I ist vertr¨
aglich mit S’:⇔M
0[e0>,...,[et>M
t
Beispiel (Vertr¨
aglichkeits-Kriterium). F¨
ur Instanz I1in
Abb. 3b ist der Schritt Patient aufkl¨
aren beendet
und der Schritt Patient untersuchen gestartet. Dem-
entsprechend enth¨
alt die Ablaufhistorie Informationen zum
Start bzw. Ende dieser Aktivit¨
aten. Wird nun auf Schema-
ebene die Aktivit¨
at Allergietest durchf¨
uhren vor
Patient vorbereiten eingef¨
ugt, k¨
onnte f¨
ur I1die bis-
herige Ablaufhistorie nicht mehr auf dem ge¨
anderten Schema
S’ erzeugt werden. Damit ist I1nicht vertr¨
aglich mit S’ und
kann demzufolge nicht auf S’ migriert werden. Im Falle von
Instanz I2sind noch keine Eintr¨
age in die Ablaufhistorie ge-
schrieben worden, so dass I2vertr¨
aglich mit S’ ist.
Obiges Kriterium ist unabh¨
angig vom verwendeten WF-
Ausf¨
uhrungsmodell und bildet deshalb eine gute Ausgangs-
basis f¨
ur unsere weiteren Betrachtungen. Insbesondere kann
eine WF-Instanz, die gem¨
aß dieser Definition vertr¨
aglich mit
einem ge¨
anderten WF-Schema ist, problemlos migriert wer-
den. Dar¨
uber hinaus bleiben orthogonale Systemfunktionen
(z.B. semantisches Rollback) unver¨
andert bestehen, eine
Eigenschaft, die f¨
ur die Implementation adaptiver WfMS es-
senziell ist. Jedoch stellt sich die Frage, wie sich f¨
ur (eine
große Zahl von) WF-Instanzen Vertr¨
aglichkeit mit dem neuen
Schema effizient feststellen l¨
asst. Obwohl es in der Literatur
bereits einige Vorschl¨
age f¨
ur die Evolution von WF-Schemata
gibt (z.B. [9,22,24,34,37]) findet man hierzu – von einigen
Ausnahmen abgesehen (z.B. [24]) – keine detaillierten Aus-
sagen. Ebenso wenig wurde bisher versucht, den Umfang der
notwendigen ¨
Uberpr¨
ufungen und der hierf¨
ur ben¨
otigten Da-
ten geeignet einzuschr¨
anken, etwa durch Einbeziehung der
speziellen Semantik von ¨
Anderungsoperationen (z.B.Vertr¨
ag-
lichkeit bei Einf¨
uge- und L¨
oschoperationen) oder durch geeig-
nete Verdichtung von Informationen aus der Ablaufhistorie.
Schließlich ist bei vielen Ans¨
atzen unklar, wie f¨
ur vertr¨
agli-
che Instanzen die Migration auf das neue Schema konkret er-
folgen soll. In der Praxis f¨
uhrt dies dazu, dass die vorgeschla-
genen L¨
osungskonzepte zu restriktiv sind, sich zu komplex f¨
ur
Benutzer darstellen oder aber zu „l¨
uckenhaften” Implemen-
tierungen f¨
uhren. So werden von einigen Ans¨
atzen viele WF-
Instanzen von einer Migration ausgeschlossen, f¨
ur die eine
¨
Anderungspropagation problemlos m¨
oglich w¨
are (etwa bei
¨
Anderungen in Verbindung mit Schleifen). Einige Ans¨
atze re-
duzieren die Komplexit¨
at dadurch, dass sie auf bestimmte, f¨
ur
2Mi[ei>M
i+1 bedeutet, dass Midurch Anwendung des Ereig-
nisses eiin Mi+1 ¨
uberf¨
uhrt wird.
die Praxis wichtige Modellelemente (z.B. Schleifen) g¨
anzlich
verzichten. Entsprechend eingeschr¨
ankt ist ihr Einsatzspek-
trum.
Definition 3.1 bildet die formale Grundlage f¨
ur die nach-
folgenden Betrachtungen. Allerdings w¨
are es naiv, f¨
ur jede
Instanz zu untersuchen, ob ihre komplette Ablaufhistorie auf
dem ge¨
anderten WF-Schema „nachgespielt” werden kann.
Der Umfang dieser Historie kann bereits f¨
ur einzelne Instan-
zen sehr groß sein. So m¨
ussen alle relevanten Ereignisse (z.B.
zum Start und zur Beendigung von Aktivit¨
aten) protokol-
liert werden (vgl. Abb. 6). Daneben umfasst ein Historienein-
trag auch Informationen zu Bearbeitern oder Zeitpunkten. Sie
werden ben¨
otigt, um im Fehlerfall ein korrektes R¨
ucksetzen
der WF-Instanz in einen fr¨
uheren Bearbeitungszustand durch-
f¨
uhren zu k¨
onnen. Die Historiengr¨
oße kann in Verbindung
mit Schleifen betr¨
achtlich sein, da f¨
ur jede Iteration die Infor-
mationen zur Ausf¨
uhrung der Schleifen-Aktivit¨
aten protokol-
liert werden. Dar¨
uber hinaus wird die Ablaufhistorie in den
meisten WfMS nicht im Hauptspeicher gehalten, sondern auf
Externspeicher ausgelagert (sieheAbb. 2). Dies ist in der Regel
ausreichend, da Zugriffe auf die komplette Ablaufhistorie nur
in Verbindung mit eher seltenen Operationen (z.B. Rollback,
Crash-Recovery) erforderlich sind.
Nachfolgend zeigen wir, dass f¨
ur Vertr¨
aglichkeitspr¨
u-
fungen in der Regel nicht die kompletten Historiendaten
notwendig sind, sondern in der Mehrzahl der F¨
alle wesent-
lich weniger Informationen ausreichen. Des Weiteren werden
wir im Zusammenhang mit Schleifen sehen, dass hier Infor-
mationen zu aktuellen Knotenmarkierungen f¨
ur die Vertr¨
ag-
lichkeitspr¨
ufungen gen¨
ugen, d.h. auf Historiendaten fr¨
uherer
Schleifeniterationen muss beiVertr¨
aglichkeitspr¨
ufungen nicht
zur¨
uckgegriffen werden. Dies ist f¨
ur die Implementierung ad-
aptiver WfMS sehr hilfreich.
In den Abschnitten 3.2 und 3.3 stellen wir einfach
¨
uberpr¨
ufbare Vertr¨
aglichkeitsbedingungen vor, die auf Mar-
kierungsinformationen basieren, so dass bei der ¨
Anderungs-
propagation aufw¨
andige Zugriffe auf die komplette Ablauf-
historie entfallen. Außerdem werden zum ersten Mal auch
¨
Anderungen auf Schleifen und Daten߬
ussen systematisch be-
trachtet.
3.2 Vertr¨
aglichkeit bei Kontrollfluss¨
anderungen
Gegeben sei ein korrektes WF-Schema Smit davon abgeleite-
ten, laufenden WF-Instanzen I1,...,In.Swerde durch eine
¨
Anderung ∆auf ein korrektes WF-Schema S’ transformiert.
Wir wollen zeigen, dass die Vertr¨
aglichkeit einer WF-Instanz
Ikmit S’ zugesichert werden kann, wenn Ikvor der Migra-
tion bestimmte Zustandsmarkierungen aufweist. Dadurch ga-
rantieren wir die Konsistenz der betroffenen WF-Instanz auch
nach Propagation der Schema¨
anderungen. Wir werden zeigen,
dass solche Vorbedingungen – ganz abgesehen vom Umfang
der ben¨
otigten Informationen – einfach und effizient ¨
uberpr¨
uf-
bar sind. Aus Darstellungsgr¨
unden unterscheiden wir im Fol-
genden zwischen azyklischen WF-Graphen (Graphklasse 1)
und WF-Graphen mit Schleifen (Graphklasse 2), wobei f¨
ur
Letztere das Vertr¨
aglichkeitskriterium aus Def. 3.1 noch we-
niger restriktiv gestaltet werden muss. Dabei beschr¨
anken wir
uns zun¨
achst auf Kontrollflussaspekte und klammern Daten-
߬
usse zwischen Aktivit¨
aten (siehe Abschnitt 3.3) noch aus.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 183
Patient
aufklären Patient
vorbereiten Patient
untersuchen
Arznei
verordnen
Allergietest
durchführen
Allergietyp
Schema S:
a) WF-Schemaebene
Patient
untersuchen
Patient
aufklären Patient
vorbereiten
Patient
untersuchen
Patient
aufklären
Patient
vorbereiten
Instanz I1:
Instanz I2:
b) WF-Instanzebene
NS = ACTIVATED NS = RUNNING
NS = COMPLETED ES = TRUE_SIGNALED
Ablaufhistorie (I1 auf S): … START(Patient aufklären),END(Patient aufklären),START(Patient vorbereiten)
Ablaufhistorie (I2 auf S): … Abb. 3. Einf¨
ugen von Ak-
tivit¨
aten
Zus¨
atzlich differenzieren wir zwischen additiven, subtraktiven
und ordnungsver¨
andernden Operationen, um pr¨
azise ange-
ben zu k¨
onnen, welche Informationen f¨
ur Vertr¨
aglichkeitspr¨
u-
fungen jeweils ben¨
otigt werden.
3.2.1 WF-Graphen ohne Schleifen (Graphklasse 1)
F¨
ur WF-Graphen der Klasse 1 lassen sich sequenzielle, paral-
lele und alternative Ausf¨
uhrungspfade modellieren. Beispiele
zeigen Abb. 1 und 4. Bei Verwendung von XOR-Verzwei-
gungen wird es Pfade geben, f¨
ur die sich bei der Ausf¨
uh-
rung (z.B. abh¨
angig von WF-relevanten Daten) ergibt, dass
sie nicht bearbeitet werden sollen. Sie werden entsprechend
als SKIPPED markiert. Beispielsweise wurde beiAusf¨
uhrung
von Instanz I1in Abb. 4b der Pfad mit Selektions-Code sc1
gew¨
ahlt3(vgl. Historie aus Abb. 4c), weshalb die Aktivit¨
aten
der anderen Ablaufzweige (D,E,Fund G) als SKIPPED mar-
kiert sind. Wichtig ist, dass solche Aktivit¨
aten keine Eintr¨
age
in die Ablaufhistorie schreiben, was durch Abb. 4c illustriert
wird.
Tabelle 1 zeigt f¨
ur additive und subtraktive ¨
Anderungen,
welche formalen Bedingungen erf¨
ullt sein m¨
ussen, damit ei-
ne WF-Instanz Ivertr¨
aglich mit dem ge¨
anderten WF-Schema
S’ ist. Dabei wird vorausgesetzt, dass das aus der ¨
Anderung
hervorgegangene WF-Schema S’ korrekt ist, insbesondere
muss S’ wieder ein Vertreter der Graphklasse 1 sein. Wir dis-
kutieren die angegebenen Bedingungen und ihre Vorz¨
uge im
Folgenden anhand von Beispielen, verzichten aus Platzgr¨
un-
den aber weitgehend auf formale Darstellungen und Beweise
(siehe [33]).
a) Additive ¨
Anderungsoperationen. Gegeben sei ein WF-
Schema der Graphklasse 1 und eine WF-Instanz Iauf S.S
werde durch Einf¨
ugen einer Aktivit¨
at oder Hinzunahme ei-
ner Kontroll- bzw. Sync-Kante in das WF-Schema S’ (der
Graphklasse 1) transformiert. Bei Einf¨
ugen einer Aktivit¨
at
kommen zus¨
atzlich Kontrollabh¨
angigkeiten hinzu, um diese
Aktivit¨
at in den WF-Kontext einzubetten. Tabelle 1.1 fasst zu-
sammen, unter welchen Bedingungen Ivertr¨
aglich mit S’
ist. Hieraus geht auch pr¨
azise hervor, welche Markierungen
oder Historiendaten f¨
ur die Vertr¨
ag¨
lichkeitspr¨
ufung ben¨
otigt
werden. Beim Einf¨
ugen von Aktivit¨
aten kann Vertr¨
aglichkeit
demnach zugesichert werden, wenn sich die (direkten) Nach-
folger des neu eingef¨
ugten Schritts ninsert aktuell in einem der
3In ADEPT kann ein Selektions-Code von einem Aktivit¨
aten-
programm geliefert werden, er kann aber auch Ergebnis einer
Pr¨
adikatevaluation sein (entsprechende Pr¨
adikate sind dann dem
XOR-Splitknoten zugeordnet).
beiden Zust¨
ande ACTIVATED oder NOT ACTIVATED befin-
den. Knoten im Zustand NOT ACTIVATED sind generell un-
problematisch. Bereits aktivierte Knoten werden zwar schon
in Arbeitslisten zur Auswahl angeboten, sind aber noch nicht
gestartet worden. Insbesondere haben sie noch keine Eintr¨
age
in die Historie geschrieben, so dass sie bei Bedarf problemlos
aus den Arbeitslisten entfernt werden k¨
onnen.
Bei alternativen Ablaufzweigen kann Vertr¨
aglichkeit auch
f¨
ur den Fall zugesichert werden, dass ein direkter Vorg¨
anger
oder Nachfolger (oder beide) von ninsert im Quell-Schema S
aktuell die Markierung SKIPPED besitzt oder ninsert in einen
leeren Teilzweig, dessen Kante als FALSE SIGNALED mar-
kiert wurde, eingef¨
ugt wird. F¨
urAktivit¨
aten, die als SKIPPED
markiert sind, werden in der Historie keine Eintr¨
age proto-
kolliert. Damit hat das Einf¨
ugen von Knoten in abgew¨
ahlte
Teilzweige keinen Effekt auf die Vertr¨
aglichkeit einer WF-
Instanz mit dem neuen WF-Schema. Beispielsweise kann f¨
ur
I2aus Abb. 4b eine neue Aktivit¨
at Xohne Probleme vor C
eingef¨
ugt werden. Der Status von Xwird dann ebenfalls als
SKIPPED bewertet, so dass sich die Historie ausAbb. 4c auch
auf dem ge¨
anderten Schema erzeugen l¨
asst.
F¨
ur das Einf¨
ugen einer Kontroll-/Sync-Kante kann man
Vertr¨
aglichkeit zusichern, wenn der Zielknoten der Kante noch
nicht gestartet wurde (vgl. Tab. 1.1). In Abb. 1b etwa kann
D→Cnicht in I1eingef¨
ugt werden, da sich Cbereits im
Zustand RUNNING befindet, der Knoten Daber noch nicht
beendet wurde. Dies ist auch aus der Historie von I1(vgl.
Abb. 1c) ersichtlich: Chat seinen Starteintrag geschrieben,
ohne dass ein Eintrag zu Dexistiert. Folglich l¨
asst sich die-
se Historie auf dem ge¨
anderten Schema nicht mehr erzeugen.
Jedoch k¨
onnen Kontroll- und Sync-Kanten auch noch dann
in eine WF-Instanz eingef¨
ugt werden, wenn ihr Quell- und
Zielknoten bereits beendet sind, diese aber ihre Historienein-
tr¨
age in der Reihenfolge der neuen Kontrollabh¨
angigkeit ge-
schrieben haben. Zur Feststellung sind allerdings gewisse In-
formationen aus derAblaufhistorie n¨
otig. Eine Einf¨
ugung von
D→Cin I2etwa ist m¨
oglich. Zwar besitzen hier so-
wohl Quell- als auch Zielknoten den Status COMPLETED, je-
doch haben Cund Dihre Historieneintr¨
age in der „richtigen”
Reihenfolge geschrieben (siehe Abb. 1c).
Das Einf¨
ugen einer Sync-Kante nsrc →ndest zwischen
bisher parallel ausf¨
uhrbaren Knoten nsrc und ndest ist un-
kritisch (vgl. Tab. 1.1), solange der Zielknoten ndest einen der
Zust¨
ande NOT ACTIVATED, ACTIVATED oder SKIPPED
besitzt. Grund ist, dass ndest in diesem Fall (noch) keinen
Historieneintrag geschrieben hat. Andernfalls gilt NS(ndest)
∈{RUNNING, COMPLETED}und die Vertr¨
aglichkeit von I
mit dem neuen Schema ist nicht immer gew¨
ahrleistet. Dies ist
184 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
a) WF-Schemaebene:
b) WF-Instanzen auf S:
c) Ablaufhistorien:
Ablaufhistorie (I1
auf S):
... START(A), END(A), START(XORSplit),
END(XORSplit, sel_code = sc1), START(B),
END(B), START(C)
Ablaufhistorie (I2 auf S):
... START(A), END(A), START(XORSplit),
END(XORSplit, sel_code = sc3), START(D),
END(D), START(E), START(F), END(F), END(E),
START(G), END(G), START(XORJoin)
XOR-Split XOR-Join
sc1
sc2 (default)
sc3
A
B C
D
E
F
G
H
S:
AND-Split AND-Join
Instanz I1:
H
D
E
F
G
B C
A
Instanz I2:
A
B C
D
E
F
G
H
NS=NodeState,
NS = ACTIVATED
NS = SKIPPED
NS = RUNNING
NS = COMPLETED
ES = EdgeState
ES = FALSE_SIGNALED
ES = TRUE_SIGNALED
H
Abb. 4. WF-Graph mit Parallel- und Alternativ-Verzweigung (Graphklasse 1)
Tabelle 1. ¨
Anderungsoperationen f¨
ur Graphklasse 1
a) Additive ¨
Anderungsoperationen(Graphklasse 1)
Einf¨
ugen von Eine Instanz Imit Historie Aist vertr¨
aglich mit S’ ⇔
Aktivit¨
atenknoten [∀n∈{x∈N|ninsert →x∈E’}:NS(n) ∈{NOT ACTIVATED, ACTIVATED, SKIPPED}]∨
ninsert [ninsert wird in einen abgew¨
ahlten Teilzweig einer XOR-Verzweigung eingef¨
ugt]
Kontrollkante NS(ndest)∈{NOT ACTIVATED, ACTIVATED, SKIPPED}∨
nsrc →ndest [NS(nsrc)=COMPLETED ∧NS(ndest)∈{RUNNING, COMPLETED}) mit
(∃ei=END(nsrc),ej=START(ndest)∈A∧i<j)]
Sync-Kante NS(ndest)∈{NOT ACTIVATED, ACTIVATED, SKIPPED}∨
nsrc →ndest (NS(nsrc)=COMPLETED ∧NS(ndest)∈{RUNNING, COMPLETED}) mit
(∃ei=END(nsrc),ej=START(ndest)∈A∧i<j)) ∨
(nsrc und ndest (NS(nsrc)=SKIPPED ∧NS(ndest)∈{RUNNING, COMPLETED}) mit
bisher parallel ∀n∈Ncritical mit NS(n) =SKIPPED:
angeordnet) ∃ei=START(ndest),ej=END(n) ∈Amit j<i),
wobei Ncritical =(c pred∗(S, nsrc)¬c pred∗(S, ndest))
(cpred∗(S, n) bezeichnet dabei die Menge aller direkten und indirekten Vorg¨
angerknoten
von nbzgl. Kanten des Typs CONTROL Eim WF-Schema S)
b) Subtraktive ¨
Anderungsoperationen (Graphklasse 1)
L¨
oschen von Eine Instanz Iist vertr¨
aglich mit S’ ⇔
Aktivit¨
atenknoten NS(ndelete)∈{NOT ACTIVATED, ACTIVATED, SKIPPED}
ndelete ∈N
Kontroll- oder
Sync-Kante keine Bedingung
nsrc →ndest
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 185
A B C D E
x
A E C
D
B
Quellschema S:
Zielschema S’:
x
Abb. 5. Verschieben von Aktivit¨
aten
nur der Fall, wenn nsrc bereits beendet ist und seinen Endein-
trag in der Historie vor dem Starteintrag von ndest geschrie-
ben hat. Gilt dagegen NS(nsrc)=SKIPPED, ist Inur dann
vertr¨
aglich mit S’, wenn alle Vorg¨
angerknoten von nsrc mit
Status ungleich SKIPPED ihre Endeintr¨
age in der Ablauf-
historie vor dem Starteintrag von ndest geschrieben haben.
b) Subtraktive ¨
Anderungsoperationen. F¨
ur subtraktive ¨
An-
derungen, bei denen Aktivit¨
aten bzw. Kanten aus dem WF-
Schema gel¨
oscht werden, sindVertr¨
aglichkeitspr¨
ufungen voll-
st¨
andig auf Grundlage von Zustandsmarkierungen durch-
f¨
uhrbar. Intuitiv ist klar, dass man nur solche Aktivit¨
aten l¨
o-
schen darf, die noch keinen Historieneintrag geschrieben ha-
ben (vgl. Tab. 1.2). Bei nicht aktivierten Knoten sind keineAn-
passungen notwendig, ansonsten m¨
ussen ggf. Arbeitslisten-
eintr¨
age gel¨
oscht werden, bevor mit der WF-Kontrolle fortge-
fahren werden kann. L¨
oscht man bspw. Knoten D (mit Status
ACTIVATED) aus Instanz I1in Abb. 1b, kann die Historie
aus Abb. 1c auch auf dem ge¨
anderten Schema erzeugt wer-
den. Allerdings m¨
ussen bei Migration von I1auf das neue
Schema die bisherigen Eintr¨
age zu D aus Arbeitslisten ent-
fernt werden. Da eine als SKIPPED markierte Aktivit¨
at kei-
nen Historieneintrag geschrieben hat, ist hier das L¨
oschen im-
mer unkritisch. So hat in Abb. 4b die als SKIPPED markierte
Aktivit¨
at E von I1keinen Historieneintrag geschrieben (vgl.
Abb. 4c). Damit kann diese Historie auch auf dem WF-Schema
erzeugt werden, das sich nach L¨
oschen von E ergibt. Beim L¨
o-
schen von Kanten werden Reihenfolgebeziehungen zwischen
Aktivit¨
aten aufgehoben, so dass bzgl. Vertr¨
aglichkeit keine
Status-Bedingungen gestellt werden m¨
ussen.
c) Ordnungsver¨
andernde Operationen. Wir betrachten nun
ordnungsver¨
andernde Operationen als eine spezielle, f¨
ur die
Praxis sehr wichtige Art von WF-Graphtransformationen. Sie
¨
andern die Anordnungsbeziehungen zwischen Aktivit¨
aten-
knoten, ohne dass die Knotenmenge selbst modifiziert wird.
Entsprechende ¨
Anderungen werden etwa notwendig, wenn
die Bearbeitungsreihenfolge von Knoten vertauscht werden
soll oder - allgemeiner - wenn ein Knoten von seiner aktuel-
len Position im WF-Graphen an eine andere Stelle verscho-
ben werden soll. Prinzipiell kann man ordnungsver¨
andernde
Operationen auf eine Menge elementarer Kanteneinf¨
uge- und
Kantenl¨
oschoperationen zur¨
uckf¨
uhren.
Beispiel (Verschieben von Aktivit¨
aten). Schema Sin Abb. 5
umfasst sequenziell angeordnete Aktivit¨
aten A, B, C, D
und E. Im Folgenden wird eine parallele Anordnung von B
und Dgew¨
unscht, wie im Zielschema dargestellt. Dazu muss
Dzun¨
achst aus seinem Kontext im WF-Graphen herausgel¨
ost
werden (Entfernen von C→Dund D→E). Anschließend
wird Ddurch Einf¨
ugen der Kontrollkanten A→D,D→C
und C→Eparallel zum Knoten Bangeordnet.
Kantenl¨
oschoperationen sind, wie bereits gezeigt, un-
kritisch, da bestehende Reihenfolgebeziehungen zwischen
Aktivit¨
aten aufgel¨
ost werden. Beispielsweise besteht nach
Entfernen der Kontrollkanten C→Dund D→Ein Abb. 5
keine Reihenfolgebeziehung mehr zwischen diesen Kno-
ten. Kanteneinf¨
ugeoperationen haben keine Auswirkung auf
die Vertr¨
aglichkeit von WF-Instanzen mit dem neuen WF-
Schema, wenn sie Reihenfolgebeziehungen zwischen Akti-
vit¨
aten festlegen, die schon im Quellschema Sbestanden oder
(transitiv) auch im Zielschema S’ weiterhin gelten. Ein Bei-
spiel hierf¨
ur ist das Einf¨
ugen von C→Ein Abb. 5, da C
bereits f¨
ur Instanzen des Schemas Simmer vor Eausge-
f¨
uhrt wird. Kritisch sind nur solche Einf¨
ugeoperationen, die
neue Reihenfolgebeziehungen zwischen Aktivit¨
aten definie-
ren, die in Snoch nicht enthalten waren, jedoch f¨
ur das Ziel-
schema S’ gelten. In Abb. 5 wird z.B. durch Einf¨
ugen von
D→Ceine neue Reihenfolgebeziehung festgelegt, was die
Beachtung des Status von Cerfordert. Im Allgemeinen er-
geben sich die Voraussetzungen f¨
ur die Vertr¨
aglichkeit von I
mit S’ durch Aggregation der entsprechenden Bedingungen
der angewandten Elementaroperationen. Formal:
Instanz Ivon Smit Historie Aist vertr¨
aglich mit S’
⇔
∀e=nsrc →ndest ∈AddedEdges:4
NS(ndest)∈{NOT ACTIVATED, ACTIVATED}∨
(NS(ndest)∈{RUNNING, COMPLETED}∧
NS(nsrc)=COMPLETED ∧
((∃ei= END(nsrc), ej=START(ndest)) ∈A∧
i<j))
Ein Beweis hierzu findet sich in [33]. Ordnungsver¨
andern-
de Operationen sind ein Beispiel f¨
ur komplexe ¨
Anderungen,
die sich aus der Hintereinanderausf¨
uhrung von Elementar-
operationen ergeben. Sind die geforderten Vertr¨
aglichkeits-
bedingungen f¨
ur die Einzeloperationen erf¨
ullt, gilt dies auch
f¨
ur die komplexe Gesamtoperation.
3.2.2 WF-Graphen mit Schleifen (Graphklasse 2)
Im Folgenden erweitere Graphklasse 2 die Graphklasse 1
um die M¨
oglichkeit zur Definition von Schleifen. In ADEPT
bildet jede Schleife eines WF-Graphen einen Kontrollblock
mit eindeutigen Start- und Endknoten, die ¨
uber eine Schlei-
fenr¨
ucksprungkante verkn¨
upft sind. Schleifenbl¨
ocke k¨
onnen
geschachtelt sein. Modellintern werden sie durch speziel-
le Knoten- und Kantentypen (START LOOP, END LOOP,
LOOP EDGE) repr¨
asentiert (vgl. Abb. 7). Durch die Unter-
scheidbarkeit zwischen „normalem” Fortschritt im Kontroll-
fluss und Schleifenr¨
uckspr¨
ungen ist es insbesondere m¨
og-
lich, „gew¨
unschte” Zyklen von „unerw¨
unschten” Zyklen, de-
ren Auftreten zur Laufzeit zu Verklemmungen f¨
uhrt, zu un-
terscheiden. Außerdem ist zur Laufzeit einfach zu ermitteln,
4Menge der in S’ neu hinzugekommenen Kanten
186 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
Ablaufhistorie einer Instanz (basierend auf
S
):
…
//1. Iteration
START(START_LOOP,1,0,18456,456287),
END(START_LOOP,1,0,2457,2468),
START(Patient aufnehmen,1,0,14579,4567),
END(Patient aufnehmen,1,0,4583,457543),
START(Patient untersuchen,1,0,12879,457),
END(Patient untersuchen,1,0,47893,24679),
START(Dosis berechnen,1,0,789647,46785),
END(Dosis berechnen,1,0,457936,31647),
START(Arznei verordnen,1,0,78965,24379),
END(Arznei verordnen,1,0,787965,3465489),
START(END_LOOP,1,45793,3465548),
END(END_LOOP,1,1,24692,341682),
//2. Iteration
START(START_LOOP,2,1,246987,46276),
END(START_LOOP,2,1,35779,26578),
START(Patient aufnehmen,2,1,24569,15566),
END(Patient aufnehmen,2,1,12484,12486)
NT=
START_LOOP
Patient
aufnehmen
Patient
untersuchen
Dosis
berechnen
Arznei
verordnen
NT=
END_LOOP
Allergietest
durchführen
Schema S:
ET=LOOP_EDGE
Ereignistyp Aktivität Iterationszähler Verzweigungsentscheidung Bearbeiter Zeitstempel Abb. 6. Ausschnitt aus einem Therapie-Prozess mit Ab-
laufhistorie
wann es zu einem Schleifenr¨
ucksprung kommt. Bei einem sol-
chen R¨
ucksprung werden die Knoten- und Kantenmarkierun-
gen des Schleifenk¨
orpers wieder auf NOT ACTIVATED bzw.
NOT SIGNALED zur¨
uckgesetzt.
Wie erw¨
ahnt ist ein zentrales Anliegen unseres Ansatzes,
WF-Instanzmigrationen nach ¨
Anderungen aller m¨
oglichen
Modellkonstrukte zu erm¨
oglichen. Das Kriterium aus Def.
3.1 ist hierf¨
ur allerdings noch zu restriktiv. Wie das folgende
Beispiel zeigt, w¨
are eine Migration von WF-Instanzen bei
schleifenbezogenen ¨
Anderungen des WF-Schemas praktisch
nie m¨
oglich.
Beispiel (Vertr¨
aglichkeit bei ¨
Anderungen innerhalb von
Schleifen). Wir betrachten Abb. 6. Angenommen, es ist ei-
ne WF-Instanz gegeben, die auf dem Quell-Schema Sdie
dargestellte Ablaufhistorie erzeugt hat. Es ist offensicht-
lich, dass diese Historie bei Ausf¨
uhrung des durch Einf¨
ugen
von Allergietest durchf¨
uhren entstandenen WF-
Schemas S’ nicht erzeugbar ist. F¨
ur WF-Instanzen von S’
w¨
urden n¨
amlich bereits in der ersten Schleifen-Iteration Ein-
tr¨
age zum Start und Ende von Allergietest durch-
f¨
uhren in die Ablaufhistorie geschrieben. Damit ist eine
Migration der WF-Instanz nach dem in Def. 3.1 vorgestellten
Kriterium ausgeschlossen, obwohl strukturell und semantisch
keine Probleme auftreten w¨
urden. Diese Einschr¨
ankung ist
zum einen unn¨
otig, zum anderen ist sie f¨
ur vieleAnwendungen
nicht akzeptabel. EinTherapieprozess kann z.B. mehrere iden-
tische Behandlungszyklen umfassen, zwischen denen gr¨
oßere
Zeitabst¨
ande liegen. Schema¨
anderungen m¨
ussen hier aus me-
dizinischen und juristischen Gr¨
unden auf aktuelle bzw. zu-
k¨
unftige Behandlungszyklen anwendbar sein [35].
Wir wenden uns nun der Frage zu, wann ¨
Anderungen eines
WF-Schemas mit Schleifen auf bereits laufendeWF-Instanzen
propagiert werden k¨
onnen. Wie gezeigt, wird bei strikter An-
wendung von Def. 3.1 ggf. die Migrationen von Instanzen
ausgeschlossen, f¨
ur die bei der ¨
Anderungspropagierung keine
inkonsistenten Zust¨
ande oder Fehler resultieren w¨
urden. Dies
schr¨
ankt den Benutzer unn¨
otig ein, was denWunsch nach einer
„Auflockerung” des bisherigen Vertr¨
aglichkeits-Kriteriums
aufwirft. Wichtig sind wieder die Sicherstellung der Konsis-
tenz von Modell- und Instanzdaten sowie die effiziente ¨
Uber-
pr¨
ufbarkeit entsprechender Regeln. Wir ben¨
otigen also f¨
ur
Schleifen ein erweitertes Vertr¨
aglichkeitskriterium. Aus for-
maler Sicht bieten sich zwei Vorgehensweisen an. Entweder
werden alle bisherigen Schleifeniterationen linearisiert, d.h.
es erfolgt – logisch gesehen – eine Hintereinanderausf¨
uhrung
aller Iterationen des Schleifenk¨
orpers, oder f¨
ur Schleifenaus-
f¨
uhrungen werden nur diejenigen Historieneintr¨
age ber¨
uck-
sichtigt, die in der aktuellen bzw. letzten Schleifeniteration
erzeugt wurden. Den folgenden Betrachtungen legen wir die
2. Variante zugrunde.
Definition 3.2 (Iterationsbereinigte Ablaufhistorie). Sei I
eine Instanz eines WF-Schemas S (der Graphklasse 2) mit
Ablaufhistorie A=<e
0,...,e
k>. Die iterationsbereinigte
Ablaufhistorie Ared von I entstehe durch Streichen von Ein-
tr¨
agen aus Agem¨
aß folgender Regeln:
Gelte zun¨
achst Ared := A.F
¨
ur jede durch ihren Anfangs-
- und Endknoten (LS,L
E) eindeutig definierte Schleife aus
S werden nun alle zugeh¨
origen Historieneintr¨
age gestrichen,
die nicht von der aktuellen bzw. letzten Schleifeniteration er-
zeugt wurden. Formal:
Falls ∃ex∈A
red mit ex=START(LS,i),i>0∧
∃ey∈A
red mit ey=START(LS,i+1),
dann entferne alle Eintr¨
agee=START(n,µ)bzw.
e=END(n,µ)aus Ared,f
¨
ur die gilt:
n∈(c succ∗(S, LS)∩c pred∗(S, LE))
∪{LS,L
E}∧µ<i
(c succ∗(S, LS)∩c pred∗(S, LE) entspricht dabei der Kno-
tenmenge des Schleifenk¨
orpers.)
Die iterationsbereinigteAblaufhistorie entsteht durch Ent-
fernen aller Historieneintr¨
age, die von Aktivit¨
aten eines
Schleifenk¨
orpers in einer anderen als der letzten (bei be-
endeten Schleifen) bzw. aktuellen (bei noch laufenden Schlei-
fen) Iteration geschrieben wurden. Ared repr¨
asentiert logisch
betrachtet eine WF-Instanz, bei der alle Schleifen maximal
einmal durchlaufen wurden. F¨
ur WF-Instanzen der Graph-
klasse 1 gilt trivialerweise A=Ared. Wir geben nun ein
modifiziertes Vertr¨
aglichkeitskriterium f¨
ur WF-Graphen mit
(geschachtelten) Schleifen an, gem¨
aß dem eine Instanz von
Sgenau dann vertr¨
aglich mit dem aus einer ¨
Anderung resul-
tierenden Schema S’ ist, wenn sich die iterationsbereinigte
Ablaufhistorie auch auf S’ erzeugen l¨
asst.
Definition 3.3 (Vertr¨
aglichkeit bei Schleifen). Sei I
eine Instanz eines WF-Schemas S mit Ablaufhistorie
A=<e
0,...,e
k>und iterationsbereinigter Ablaufhistorie
Ared =<e
i1,...,e
in>.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 187
b) WF-Instanzen auf S
Instanz I:
..
C
E
..
3. Schleifeniteration
c) Ablaufhistorie
...
//1. Iteration:
START(Ls,1,FALSE), END(LS,1), START(B,1), END(B,1, sel_code=1),
START(E,1), END(E,1), START(G,1), END(G,1), START(F,1), END(F,1),
START(H,1), END(H,1), START(I,1), END(I,1), START(LE,1),
END(LE,1,loop_condition = TRUE),
//2. Iteration:
START(LS,2,TRUE), END(LS,2),START(B,2), END(B,2, sel_code=2),
START(C,1), END(C,1), START(D,1), END(D,1), START(I,2), END(I,2),
START(LE,2), END(LE,2, loop_condition = TRUE)
//3. Iteration:
START(LS,3,TRUE), END(LS,3),START(B,3), END(B,3,sel_code=1),
START(E,2), END(E,2)
TRUE
a) WF-Schemaebene
NT=START_LOOP NT=END_LOOP
sc1
sc2
(default)
S:
B
..
I
EH
..
FALSE
ET=LOOP_EDGE
LS LE
D
G
D
B
F
LS LE
NS=NodeState,
NS = ACTIVATED
NS = SKIPPED
NS = RUNNING
NS = COMPLETED
ES = EdgeState
ES = FALSE_SIGNALED
ES = TRUE_SIGNALED
Abb. 7. WF-Graph der Klasse 2
S werde durch eine ¨
Anderung ∆auf das (korrekte) WF-
Schema S’ transformiert. Sei M
tdie Markierung des Aus-
f¨
uhrungsgraphen von I, der sich ergibt, wenn ∆auf I pro-
pagiert wird und anschließend eine Neubewertung des Zu-
stands des Ausf¨
uhrungsgraphen durchgef¨
uhrt wird. Dann ist
I genau dann vertr¨
aglich mit S’, wenn die Folge von Ereig-
nissen ei1,...,e
in, ausgehend von einer Anfangsmarkierung
M
0, auch auf S’anwendbar ist und im Anschluss wieder eine
korrekte Markierung M
tresultiert. Formal:
I ist vertr¨
aglich mit S’:⇔M
0[ei1>,...,[ein>M
t
Beispiel (Vertr¨
aglichkeit bei Schleifen). Wir betrachten die
Instanz aus Abb. 7b. Hier ergibt sich
Ared =<START(LS,3,TRUE), END(LS,3),
START(B,3), END(B, 3,sel code=1),
START(E,2), END(E,2)>.
Diese Historie ist auch auf dem ge¨
anderten WF-Schema,
das nach Einf¨
ugen von Aktivit¨
at X zwischen G und H
resultiert, erzeugbar. Damit ist die Instanz vertr¨
aglich zum
ge¨
anderten WF-Schema, d.h. die Restriktionen des in Def.
3.1 angegebenen Vertr¨
aglichkeitskriteriums bestehen nicht
mehr.
Wir betrachten zun¨
achst die inAbschnitt 3.2.1 diskutierten
Schema¨
anderungen. Um f¨
ur Instanzen entscheiden zu k¨
onnen,
ob sie im Sinne von Def. 3.3 vertr¨
aglich mit einem ge¨
ander-
ten WF-Schema sind, gen¨
ugt es, dieselben Voraussetzungen
zu fordern wie bei WF-Graphen der Klasse 1. Grund daf¨
ur ist,
dass bei Verwendung der iterationsbereinigten Ablaufhistorie
– sie ist f¨
ur die Vertr¨
aglichkeitspr¨
ufung maßgebend – Schlei-
fenr¨
ucksprungkanten keine Relevanz haben, d.h. man erh¨
alt –
logisch betrachtet – einen Graphen ohne Schleifen. Der Voll-
st¨
andigkeit halber sei erw¨
ahnt, dass ADEPT f¨
ur die Defini-
tion von Schema¨
anderungen spezielle Operationen anbietet,
etwa f¨
ur das Einf¨
ugen, L¨
oschen und ¨
Andern von Verzwei-
gungsbl¨
ocken und deren Teilzweigen. Außerdem ist es m¨
og-
lich, Schleifen in ein WF-Schema einzuf¨
ugen bzw. daraus zu
l¨
oschen. Dar¨
uber hinaus k¨
onnen in ADEPT unter gewissen
Voraussetzungen auch neue Schleifen um existierende Bl¨
ocke
des WF-Schemas eingef¨
ugt oder Schleifenr¨
ucksprungkanten
entfernt werden. Die Vorbedingungen f¨
ur Vertr¨
aglichkeitspr¨
u-
fungen bei Anwendung dieser speziellen Operationen werden
in [29] diskutiert.
3.3 Vertr¨
aglichkeit bei Datenfluss¨
anderungen
Unsere bisherigen Betrachtungen haben sich auf Kontroll-
flussaspekte beschr¨
ankt. Im Allgemeinen werden bei WF-
-Schema¨
anderungen jedoch auch Anpassungen des model-
lierten Datenflusses erforderlich. Inwieweit solche Daten-
fluss¨
anderungen die Vertr¨
aglichkeit von WF-Instanzen mit
dem ge¨
anderten WF-Schema beeintr¨
achtigen, soll nun behan-
delt werden.
3.3.1 Datenflussmodellierung und -steuerung in ADEPT
In ADEPT erfolgt der Datenaustausch zwischen Aktivit¨
aten
¨
uber globale Prozessvariablen (sog. Datenelemente). Der Da-
tenfluss wird modelliert, indem man Eingabe- und Ausgabe-
parameter von Aktivit¨
aten ¨
uber Datenkanten mit diesen Da-
tenelementen verkn¨
upft. Dabei wird jeder Eingabeparameter
mittels genau einer Lesekante und jeder Ausgabeparameter
¨
uber genau eine Schreibkante an die Datenelemente ange-
bunden. Ein Beispiel zeigt Abb. 8a. Hier schreibt Bdas Da-
tenelement d2, das nachfolgend von Cund Dgelesen wird.
Die Gesamtheit aller einem WF-Schema zugeordneten Da-
tenelemente und Datenkanten bezeichnen wir als Datenfluss-
-Schema (DF-Schema).F
¨
ur sie bestehen in ADEPT gewis-
se Korrektheitsforderungen, etwa dass beim Start eines Akti-
vit¨
atenprogramms stets alle obligaten Eingabeparameter ver-
sorgt sein m¨
ussen. ZurAusf¨
uhrungszeit einer WF-Instanz ver-
waltet ADEPT f¨
ur jedes Datenelement ein oder mehrere Ver-
sionen eines Datenobjekts. Bei einem Schreibzugriff auf ein
Datenelement wird stets eine neue Version des Datenobjekts
angelegt, d.h. Datenobjekte werden niemals physisch ¨
uber-
schrieben. Die Verwaltung der verschiedenen Versionen ist
wichtig f¨
ur das kontextabh¨
angige Lesen von Datenelementen
und das korrekte Zur¨
ucksetzen im Fehlerfall (f¨
ur Details sie-
he [29]). Der Datenkontext einer WF-Instanz umfasst also f¨
ur
jedes Datenelement eine Datenhistorie, die diesem Daten-
element eine geordnete Liste der Versionen des verwalteten
Datenobjekts zuordnet.
188 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
Datenhistorie:
2
Æ
aktueller Wert
1
d1 d2
/
5 5
2 ?
d3
Schreibkante
Lesekante
Wert eines Datenobjekts
1
Ablauf-
ereignisse START(A) END(A) START(B) END(B) START(C)
geschriebene
Datenelemente - (d1,5)
(d2,1) - (d2,2) -
gelesene
Datenelemente - - - - (d1,5)
a) WF-Instanz b) Erweiterte Ablaufhistorie
/ /
Abb. 8. ¨
Anderung des
DF-Schemas
3.3.2 ¨
Anderungen des Datenfluss-Schemas
und Vertr¨
aglichkeit von WF-Instanzen
¨
Anderungen des DF-Schemas k¨
onnen sowohl als begleiten-
de Anpassungen zu Kontrollfluss- ¨
Anderungen (z.B. L¨
oschen
einer Aktivit¨
at mit Entfernen der assoziierten Datenkanten)
als auch als eigenst¨
andige Operationen durchgef¨
uhrt wer-
den. Letzteres ist z.B. zur nachtr¨
aglichen Korrektur von Feh-
lern bei der Datenflussmodellierung notwendig. Als Ope-
rationen f¨
ur die Ab¨
anderung von DF-Schemata unterst¨
utzt
ADEPT das Einf¨
ugen und L¨
oschen von Datenelementen bzw.
Datenkanten. Die bisher definierten Vertr¨
aglichkeitskriterien
m¨
ussen nun dahingehend erweitert werden, dass sie auch bei
Datenfluss- ¨
Anderungen sinnvoll anwendbar sind.
Beispiel (Inkonsistentes Lesen). Wir betrachten die Instanz
aus Abb. 8a. Aktivit¨
at Cbefindet sich aktuell im Zustand
RUNNING, hat also das Datenelement d1bereits gelesen.
Wird nun die Lesekante von Cauf d1gel¨
oscht und eine
neue Lesekante von Cauf d2eingef¨
ugt – diese ¨
Anderung
ist auf Schemaebene korrekt – kann es beim Zur¨
ucksetzen im
Fehlerfall zu Problemen kommen, da unter Umst¨
anden falsche
Parameterwerte bei eventuellen R¨
ucksetzoperationen heran-
gezogen werden [29]. Bei Zugrundelegung des bisher vor-
gestellten Vertr¨
aglichkeitskriteriums w¨
are der skizzierte Fall
jedoch zul¨
assig.
Aus diesem Grund ben¨
otigen wir ein angepasstes Ver-
tr¨
aglichkeitskriterium, das auch Datenflussaspekte einbezieht.
Hierzu reichern wir die bisherige Ablaufhistorie f¨
ur WF-
Instanzen um Informationen aus den Datenelementhistorien
an. Bezogen auf Abb. 8a k¨
onnte sich eine solche erweiterte
Ablaufhistorie wie in Abb. 8b darstellen. Aus ihr geht ein-
deutig hervor, welche Datenelemente eine Aktivit¨
at mit wel-
chen Werten gelesen bzw. geschrieben hat. Formal:
Definition 3.4 (Erweiterte Ablaufhistorie). Seien S ein kor-
rektes WF-Schema mit Kontrollfluss-Schema CFS = (N, E,
...) und DF-Schema DFS und I eine WF-Instanz auf S mit
Ablaufhistorie A. Dann heißt Aext die um Datenelementzu-
griffe erweiterte Ablaufhistorie von A, wenn Aext f¨
ur jeden
Starteintrag einer Aktivit¨
at die Werte der gelesenen Daten-
elemente und f¨
ur jeden Endeintrag entsprechend die Werte
geschriebener Datenelemente enth¨
alt:
Aext :=<e
(d(1)
1,v(1)
1),...,(d(1)
n,v(1)
n)
1,...,e
(d(k)
1,v(k)
1),...,(d(k)
m,v(k)
m)
k>
Ein Tupel (d(µ)
i,v(µ)
i)beschreibt dabei einen Lese- bzw.
Schreibzugriff von eµauf das Datenelement d(µ)
i(mit zugeh¨
o-
rigem Wert v(µ)
i).
Auf Grundlage dieser Definition geben wir nun ein modi-
fiziertes Vertr¨
aglichkeitskriterium f¨
ur WF-Instanzen an, das
auch in Verbindung mit ¨
Anderungen des DF-Schemas an-
wendbar ist (hier zun¨
achst ohne Ber¨
ucksichtigung von Schlei-
fen):
Definition 3.5 (Vertr¨
aglichkeit bei Kontroll- und Daten-
fluss¨
anderungen). Seien S ein korrektes WF-Schema mit
Kontrollfluss-Schema CFS = (N, E, ...) und DF-Schema DFS
und I eine WF-Instanz von S mit erweiterter Ablaufhistorie
Aext =<e
(d(1)
1,v(1)
1),...,(d(1)
n,v(1)
n)
1,...,e
(d(k)
1,v(k)
1),...,(d(k)
m,v(k)
m)
k>.
S werde durch eine ¨
Anderung ∆auf das (korrekte)WF-Schema
S’ transformiert. Dann:
I vertr¨
aglich mit S’:⇔A
ext ist auch auf S’erzeugbar
Zum einen m¨
ussen die in Def. 3.1 geforderten Bedin-
gungen f¨
ur Kontrollfluss¨
anderungen weiter erf¨
ullt sein, zum
anderen muss zus¨
atzlich gelten, dass jede bereits gestartete
Aktivit¨
at bei Ausf¨
uhrung auf dem neuen Schema dieselben
Datenelemente lesen w¨
urde und dass jede beendete Aktivit¨
at
dieselben Datenelemente geschrieben h¨
atte. Nun stellt sich
die Frage, wie die Vertr¨
aglichkeit einer WF-Instanz bei ¨
An-
derungen des DF-Schemas ¨
uberpr¨
uft werden kann. Ziel ist
wieder, einfache Bedingungen anzugeben, bei deren Einhal-
tung die Vertr¨
aglichkeit der betrachteten WF-Instanz mit dem
ge¨
anderten WF-Schema gew¨
ahrleistet ist. Tab. 2 fasst zu-
sammen, welche Statusvoraussetzungen f¨
ur DF- ¨
Anderungs-
operationen zu fordern sind, um Vertr¨
aglichkeit im Sinne von
Def. 3.5 zusichern zu k¨
onnen. Das Einf¨
ugen eines Datenele-
ments ist immer m¨
oglich, da im Verlauf der WF-Ausf¨
uhrung
noch keine Aktivit¨
aten lesend oder schreibend darauf zuge-
griffen haben. Das L¨
oschen eines Datenelements ist nur dann
unkritisch, wenn noch keine Lese- oder Schreibzugriffe statt-
gefunden haben. Lesekanten auf Datenelemente k¨
onnen ein-
gef¨
ugt oder gel¨
oscht werden, wenn die zugeh¨
orige Aktivit¨
at
noch nicht gestartet wurde. Schreibkanten k¨
onnen sogar noch
manipuliert werden, wenn die zugeh¨
origeAktivit¨
at bereits ge-
startet, aber noch nicht beendet wurde.
Wie bereits erw¨
ahnt, werden auch beim Einf¨
ugen und L¨
o-
schen von Aktivit¨
aten begleitende Anpassungen des Daten-
flusses vorgenommen. Hier sind die Voraussetzungen aus Tab.
2 automatisch erf¨
ullt, wenn die Statusbedingungen f¨
ur die ent-
sprechende Knoteneinf¨
uge- bzw. Knotenl¨
oschoperation gel-
ten (vgl. Tab. 1).
Zu untersuchen bleibt, wie Def. 3.3 (Vertr¨
aglichkeit bei
Schleifen) und Def. 3.5 zusammenspielen. Als Basis f¨
ur beide
Varianten desVertr¨
aglichkeitskriteriums dient eine modifizier-
te Ablaufhistorie Aext,red. Dazu wir Azun¨
achst gem¨
aß Def.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 189
Tabelle 2. ¨
Anderungsoperationen auf dem DF-Schema
Iist vertr¨
aglich mit S’ ⇔
Datenelement dwird in das Datenfluss-Schema [Es existiert keine Aktivit¨
at mit Status RUNNING oder COMPLETED,
eingef¨
ugt bzw. gel¨
oscht die lesend oder schreibend auf dieses Datenelement zugegriffen hat.]
Einf¨
ugen/L¨
oschen von Iist vertr¨
aglich mit S’ ⇔
Lesekante d→n NS(n) ∈{NOT ACTIVATED, ACTIVATED, SKIPPED}
Schreibkante n→d NS(n) =COMPLETED
3.4 reduziert (→A
red) und dann um die Informationen aus
der Datenhistorie angereichert (→A
ext). Eine WF-Instanz I
ist genau dann vertr¨
aglich mit einem ge¨
anderten Schema S’,
wenn Aext,red auch auf S’ erzeugbar ist.
4 Migration vertr¨
aglicher WF-Instanzen
Wir gehen nun darauf ein, wie vertr¨
agliche WF-Instanzen au-
tomatisch und korrekt auf das neue WF-Schema migriert wer-
den k¨
onnen. Dazu sei ein WF-Schema Sgegeben, das in ein
wiederum korrektes WF-Schema S’ abge¨
andert wird. Ferner
seien I1,..., InInstanzen, die auf Grundlage von Serzeugt
wurden und die vertr¨
aglich mit S’ sind. F¨
ur sie stellt sich nun
die Frage, wie ihre Migration auf S’ konkret erfolgen soll.
Insbesondere muss f¨
ur jede Instanz Ikgekl¨
art werden, ob
ihre bisherigen Zustandsmarkierungen und Arbeitslistenein-
tr¨
age unver¨
andert ¨
ubernommen werden k¨
onnen oder ob An-
passungen erforderlich werden. Das betrifft auch den Status
von Knoten und Kanten, die infolge der Schema¨
anderung neu
erzeugt wurden.
Abh¨
angig von Art und Umfang einer Schema¨
anderung so-
wie aktuellem Status einer zu migrierenden WF-Instanz Ik
k¨
onnen die erforderlichen Zustandsanpassungen mehr oder
weniger umfangreich ausfallen. Betrifft die Schema¨
anderung
einen Bereich des WF-Graphen, den die Instanz aktuell noch
nicht betreten hat, so sind – abgesehen von der Initialisierung
neu hinzukommender Knoten und Kanten – keine Zustands-
anpassungen erforderlich. Anders verh¨
alt es sich, wenn der
Kontext einer ¨
Anderung auch Knoten und Kanten umfasst,
die bereits markiert wurden. So kann es beim Einf¨
ugen einer
Aktivit¨
at (und ihrer Kontextkanten) erforderlich werden, dass
die Aktivierung bisher aktivierter (und damit in Arbeitslisten
gestellter) Schritte wieder aufgehoben oder umgekehrt die neu
hinzugef¨
ugte Aktivit¨
at sofort aktiviert wird. ¨
Ahnliches gilt
auch f¨
ur das Einf¨
ugen oder Entfernen von Kontroll- bzw. Sync-
Kanten auf Instanzebene. F¨
ur komplexe Schema¨
anderungen,
die mehrere Elementaroperationen umfassen, k¨
onnen die not-
wendigen Markierungsanpassungen sehr viel umfangreicher
ausfallen. Hier ist die Beantwortung der Frage, wie Markierun-
gen bei Instanzmigrationen effizient und konsistent angepasst
werden k¨
onnen, im Allgemeinen nicht trivial.
Wir geben im Folgenden ein Verfahren an, mit dem sich
die Knoten- und Kantenmarkierungen von Instanzen bei Mi-
grationen automatisch anpassen lassen. Dabei werden jeweils
nur Knoten und Kanten der von der ¨
Anderung betroffenen
Bereiche des WF-Graphen neu bewertet, wodurch sich der
Gesamtaufwand gegen¨
uber einer Neubewertung aller Knoten
und Kanten erheblich reduzieren l¨
asst. Des Weiteren stellt das
Verfahren sicher, dass f¨
ur eine WF-Instanz nach ihrer Migra-
tion wieder ein korrekter und konsistenter Zustand resultiert.
4.1 Grundlagen
Grundlegend f¨
ur das nachfolgende Verfahren sind die be-
reits erw¨
ahntenAusf¨
uhrungseigenschaften desADEPT-Meta-
modells: Zum einen bleiben Markierungen beendeter bzw.
nicht mehr ausf¨
uhrbarer Knoten beim Fortschreiten des
Kontrollflusses (in Vorw¨
artsrichtung) erhalten, zum ande-
ren gibt es f¨
ur die Markierung und Ausf¨
uhrung von Akti-
vit¨
atenknoten wohl definierte, einfach implementierbare Re-
geln, vergleichbar den Schaltregeln bei Petri-Netzen [28].
Markierungsregeln geben (abh¨
angig vom Knotentyp) an, wel-
che Ausgangskanten bei Beendigung der Aktivit¨
at mit TRUE
und welche mit FALSE markiert werden sollen. Umgekehrt
definieren Ausf¨
uhrungsregeln die Bedingungen, die f¨
ur ein-
gehende Kanten eines Knotens gelten m¨
ussen, damit er als
ACTIVATED bzw. SKIPPED markiert werden darf (siehe
Abb. 9).
4.2 (Initiale) Bestimmung neu zu bewertender Knoten
und Kanten
Im Allgemeinen sollten bei einer Migration nur diejenigen
Knoten und Kanten einer Neubewertung unterzogen werden,
f¨
ur die potenziell eine Statusanpassung erforderlich wird. Wir
zeigen zuerst, wie sich diese eingeschr¨
ankte Knoten- bzw.
Kantenmenge bestimmen l¨
asst. Im nachfolgenden Abschnitt
gehen wir dann darauf ein, wie hiervon ausgehend die Neu-
bewertung der Zustandsmarkierungen bei der Migration einer
vertr¨
aglichen WF-Instanz erfolgen kann.
Ermittelt werden m¨
ussen die Menge Echeck der Kanten
und die Menge Ncheck der Knoten, deren Status bei der Mi-
gration von Instanzen neu bewertet werden soll. Tabelle 3 gibt
an, wie sich diese Mengen bei Anwendung elementarer ¨
An-
derungen darstellen. So muss beim Einf¨
ugen einer Aktivit¨
at
X(inkl. ihrer Kontextkanten) der Status ihrer direkten Nach-
folgerknoten sowie der in Xeinm¨
undenden Kontrollkanten
neu bewertet werden, um inkonsistente Markierungen aus-
schließen zu k¨
onnen (vgl. Tab. 3, 2. Zeile). (Eine Neube-
wertung von Xselbst wird nur dann erforderlich, wenn ei-
ne der in X einm¨
undenden Kanten mit TRUE SIGNALED
bzw. FALSE SIGNALED markiert werden kann.) Bei Hin-
zuf¨
ugen einer Kontroll- oder Sync-Kante nsrc →ndest wie-
derum m¨
ussen sowohl die Kante als auch ihr Zielknoten ndest
neu bewertet werden (vgl. Tab. 3, 3. Zeile). Letzteres ist auch
dann erforderlich, wenn die Kante selbst zu NOT SIGNALED
190 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
Ausführung:
ACTIVITY
AND-Join
XOR-Join
ACTIVITY
Alle Eingangskanten signalisiert
Markierung:
ACTIVITY
AND-Split
XOR-Split
ENDLOOP, LOOP_E
Beendigung von X
X X
1
2
sel_code=1
X X
X X
1
2
true
false
true
false
loopcond=true
X X
X X
X X
X X
NS=NodeState,
NS = ACTIVATED
NS = SKIPPED
NS = RUNNING
NS = COMPLETED
ES = EdgeState
ES = FALSE_SIGNALED
ES = TRUE_SIGNALED
Abb. 9. Ausf¨
uhrungs-
und Markierungsregeln
(exemplarische Darstel-
lung)
Tabelle 3. Anzupassende Knoten- und Kantenmengen (Auswahl)
Angewandte Operation op... ... und neu zu bewertende Knoten und Kanten
Hinzuf¨
ugen eines Aktivit¨
atenknotens X Ncheck(op) := {n∈N’ |X→n∈E’}
(inkl. Kontextkanten) Echeck(op) := {nsrc →ndest ∈E’ |ndest =X}
Hinzuf¨
ugen einer Echeck(op) := {nsrc →ndest}
Kontroll- bzw. Sync-Kante nsrc →ndest Ncheck(op) := {ndest}
L¨
oschen einer Kontroll- bzw. Sync-Kante nsrc →ndest Ncheck(op) := {ndest}
L¨
oschen eines Aktivit¨
atenknotens X Echeck(op) := Eadd
(inkl. Hinzunahme oder Ncheck(op) := {n∈N|X→n∈E}
Entfernen von Kontextkanten) (Eadd: Menge der neu hinzukommenden Kanten)
Einf¨
ugen eines neuen Teilzweigs Z Echeck(op) := {e}
in eine XOR-Verzweigung (e: Kontextkante XOR-Splitknoten →Z)
Einf¨
ugen eines Schleifenblocks (n1,n2) mit Ncheck(op) := {n∈N’ |n2→n∈E’}
Startknoten n1und Endknoten n2Echeck(op) := {nsrc →ndest |ndest =n
1}
Algorithmus 1. (Bestimmung von Echeck und Ncheck bei komple-
xen ¨
Anderungen)
input
op1,...,op
n: Zur Anwendung kommende
Elementaroperationen
output
Echeck,Ncheck: Menge der neu zu bewertenden
Kanten/Knoten
begin
Echeck := ∅;Ncheck := ∅; //Initialisierung
for i:=1 to n do //Aggregation
Echeck:= Echeck ∪Echeck(opi);
Ncheck:= Ncheck ∪Ncheck(opi);
done
Echeck:= Echeck ∩E’; Ncheck:= Ncheck ∩N;
end
evaluiert. F¨
ur diesen Fall muss eine m¨
oglicherweise bereits
erfolgte Aktivierung von ndest aufgrund des Hinzuf¨
ugens der
Kante wieder aufgehoben werden.
Wie lassen sich Echeck und Ncheck bei Anwendung kom-
plexer ¨
Anderungen, die mehrere Operationen op1,...,op
n
umfassen, ermitteln? DieVermutung liegt nahe, dass sich diese
Mengen durch Vereinigung der aus der Anwendung elemen-
tarer Operationen resultierenden Mengen Echeck(opi)bzw.
Ncheck(opi)bestimmen lassen. Dem ist jedoch nicht immer
so, da sich Einzeloperationen bei der Definition der Gesamt-
schema¨
anderung aufeinander beziehen k¨
onnen. Insbesondere
k¨
onnen durch Anwendung von opidie Effekte vorangehend
definierter ¨
Anderungen opi−1,...,op
1teilweise wieder auf-
gehoben werden.Algorithmus 1 ber¨
ucksichtigt diesenAspekt.
Hier ergibt sich Echeck durchVereinigung der entsprechenden
Kantenmengen der angewandten Operationen op1,...,op
n,
wobei noch diejenigen Kanten entfernt werden, die im neu-
en WF-Schema nicht enthalten sind. Sie wurden im Verlauf
der ¨
Anderungsdefinition zwar erzeugt, sind dann aber infol-
ge der Anwendung weiterer Operationen wieder weggefallen.
Was Ncheck anbetrifft, m¨
ussen nur Knoten betrachtet werden,
die bereits im Quell-Schema Senthalten waren. (Das nachfol-
gende Verfahren ist so konstruiert, dass neu hinzugekommene
Aktivit¨
aten nur bewertet werden, wenn eine einm¨
undende
Kante im Verlauf des Verfahrens neu markiert wird.) Algo-
rithmus 1 zieht also nur die unbedingt notwendigen Knoten-
-/Kantenmengen zur Neubewertung heran, wodurch die f¨
ur
Algorithmus 2 ben¨
otigten Eingabegr¨
oßen minimal gehalten
werden.
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 191
Algorithmus 2 (Neubewertung von Zustandsmarkierungen bei Migrationen)
input
NS,ES: Bisherige Knoten-/Kantenmarkierungen von I(bezogen auf S=(N, E))
Echeck,Ncheck: Menge der neu zu bewertenden Kanten bzw. Knoten
output
NS,ES: Neu berechnete Knoten-/Kantenmarkierungen von I(bezogen auf S’=(N’, E’))
begin
// Initialisierung von ES
forall e∈E’ do
if e∈Ethen // Kante war bereits in bisheriger Kantenmenge E enthalten
ES’(e):= ES(e)
else // Kante mit NOT SIGNALED initialisieren
ES’(e):= NOT SIGNALED
done
// Initialisierung von NS
forall n∈N’ do
if n∈Nthen // Knoten war bereits in bisheriger Knotenmenge N enthalten
NS’(n):= NS(n)
else // Knoten mit NOT ACTIVATED initialisieren
NS’(n):= NOT ACTIVATED
done
// Neubewertung der Kanten aus Echeck bzw. der Knoten aus Ncheck
repeat
while Echeck =∅do
Entnehme eine Kante e=nsrc →ndest aus Echeck;
¨
Uberpr¨
ufe durch Anwendung der ADEPT-Markierungsregeln auf nsrc,ob
emit ES(e)= TRUE SIGNALED bzw. ES(e)= FALSE SIGNALED
markiert werden darf - falls ja, passe Kantenmarkierung entsprechend an
if Markierung von ege¨
andert then
Ncheck := Ncheck ∪{ndest}
endif
done
while Ncheck =∅do
Entnehme einen Knoten naus Ncheck;
if NS’(n) ∈{ACTIVATED, NOT ACTIVATED}then
¨
Uberpr¨
ufe durch Anwendung der ADEPT-Ausf¨
uhrungsregeln auf n,
ob dieser Knoten mit NS(n)∈{NOT ACTIVATED, ACTIVATED, SKIPPED}
markiert werden darf - falls ja, passe die Markierung entsprechend an
Falls NS(n)auf SKIPPED gesetzt wurde:
Echeck:= Echeck ∪{e=n
src →ndest ∈E’ |nsrc =n}
endif
done
until Echeck =∅and Ncheck =∅;
end
4.3 Verfahren zur Anpassung von Markierungen
bei Migrationen
Ein Schema Swerde durch Anwendung der Operationen
op1,...,op
nin ein wiederum korrektes Schema S’ abge¨
an-
dert. Ferner seien Echeck und Ncheck durchAlgorithmus 1 be-
stimmt. Algorithmus 2 (siehe unten) bestimmt dann die neuen
Knoten- und Kantenmarkierungen (NS’, ES’) einer mit S’
vertr¨
aglichen WF-Instanz Ivon Snach ihrer Migration auf
S’. Im Kern basiert er auf den beschriebenen Ausf¨
uhrungs-
und Markierungsregeln (vgl. Abb. 9). Ausgangspunkt bilden
die bei der ¨
Anderungsdefinition ermittelten Mengen Ncheck
und Echeck. Ergeben sich bei der Bewertung von Knoten und
Kanten jedoch Anpassungen, werden ggf. auch weitere Kno-
ten und Kanten neu bewertet (z.B. kaskadierende Markierung
der Knoten abgew¨
ahlter Zweige).
Mittels Algorithmus 1 und 2 werden Art und Umfang der
erforderlichen Statusanpassungen gegen¨
uber denAlternativen
1 und 2 (vgl. Abschnitt 4.1) erheblich vereinfacht bzw. redu-
ziert.W¨
ahrendAlgorithmus 1 nur einmalig bei der ¨
Anderungs-
definition anzuwenden ist, mussAlgorithmus 2 f¨
ur jede zu mi-
grierende Instanz ausgef¨
uhrt werden. Der Aufwand von Algo-
rithmus 2 kann durch O(n)(nist die Anzahl der Aktivit¨
aten-
knoten des WF-Schemas) abgesch¨
atzt werden. Hinzu kommt
f¨
ur jede Instanz noch der Aufwand O(n)f¨
ur die Vertr¨
aglich-
keitspr¨
ufung (ein Vergleich mit anderen Verfahren findet sich
in Abschnitt 5). Durch die Konstruktion des Verfahrens ist in
der Mehrzahl der F¨
alle aber nur eine kleine Teilmenge der
Knoten und Kanten neu zu bewerten. Dies gilt selbst dann,
wenn die ¨
Anderungen in verschiedenen Bereichen des WF-
Graphen vorgenommen wurden (im Gegensatz etwa zu dem in
[13] beschriebenen Ansatz). Da WF-Schemata mehrere Dut-
192 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
zend (oder noch mehr) Aktivit¨
aten umfassen k¨
onnen [35], ist
eine solche Reduzierung auch zwingend erforderlich.
Schließlich kann man formal zeigen, dass bei Anwendung
dieses Verfahrens auf vertr¨
agliche Instanzen im Anschluss
wieder eine konsistente Markierung resultiert. Dieselbe Mar-
kierung erh¨
alt man auch, wenn man die komplette Ablauf-
historie auf dem neuen Schema „nachspielt”. Dies w¨
are aber
mit einem wesentlich h¨
oheren Aufwand verbunden, da dann
sehr viel mehr Knoten und Kanten, in Verbindung mit Schlei-
fen gegebenenfalls sogar mehrfach, bewertet werden m¨
ussten.
F¨
ugt man z.B. in das Schema aus Abb. 7a eine neue Aktivit¨
at
Xzwischen Eund Gein, so m¨
ussen bei unserem Ansatz le-
diglich die neu hinzukommende Kontrollkante E→Xsowie
die Knoten Gund Xneu bewertet werden, um nach Migration
der Instanz wieder eine konsistente Markierung zu erhalten.
Beispiel (Markierungsanpassungen). Wir betrachten eine
Schema¨
anderung, bei der Anordnungsbeziehungen zwischen
Knoten modifiziert werden. Im WF-Graphen ausAbb. 10a sol-
len B und C nun parallel angeordnet werden. Intern wird diese
¨
Anderung durch Hinzunahme der Kanten B→Dund A→
Csowie durch Entfernen von B→Crealisiert. Alg. 1 liefert
Ncheck ={C, D}und Echeck ={A→C,B→D}. Ge-
geben seien nun Instanzen I1und I2von S(vgl. Abb. 10c).
Sowohl I1als auch I2sind aufgrund ihrer aktuellen Markie-
rungen vertr¨
aglich mit S’ und k¨
onnen deshalb migriert wer-
den. Bei Migration von I1auf S’ werden die beiden Kanten
B→Dund A→Cgem¨
aß Alg. 2 mit TRUE SIGNALED
markiert. Sowohl f¨
ur Dals auch Cerfolgt jedoch keine An-
passung der Knotenmarkierung, da die Bedingungen f¨
ur die
Ausf¨
uhrung dieser Knoten entweder noch nicht erf¨
ullt sind
(Knoten D) oder der betreffende Knoten bereits gestartet wur-
de (Knoten C). Bei Migration von I2werden zun¨
achst die
Markierungen von B→Dund A→Cneu bewertet, wo-
bei lediglich A→Cmit TRUE SIGNALED markiert werden
kann. Die anschließende Bewertung von Cergibt, dass dieser
Knoten mit ACTIVATED markiert und somit in Arbeitslisten
gestellt werden kann.
Die Algorithmen 1 und 2 funktionieren in Verbindung
mit beliebig komplexen ¨
Anderungen. Das trifft auch f¨
ur ¨
An-
derungen von Verzweigungen und Schleifen zu, etwa das Ein-
f¨
ugen neuer Teilzweige in eine XOR-Verzweigung. Hier kann
es auf Instanzebene sogar vorkommen, dass der neu hinzuge-
f¨
ugte Zweig nach Neubewertung der Markierungen vollst¨
an-
dig „abgew¨
ahlt” wird (d. h. Knoten mit SKIPPED und Kanten
mit FALSE SIGNALED bewertet sind). Schließlich liefertAl-
gorithmus 2 auch wichtige Informationen zur Anpassung von
Arbeitslisten. So m¨
ussen f¨
ur jede Aktivit¨
at des alten Schemas,
die vor der Migration aktiviert war und deren Aktivierung bei
der Neubewertung der Markierungen aufgehoben wird, Ar-
beitslisteneintr¨
age wieder entfernt werden. Umgekehrt m¨
us-
sen f¨
ur bisher nicht aktivierte bzw. neu hinzukommende Kno-
ten, die nach Neubewertung den Status ACTIVATED besitzen,
Arbeitslisteneintr¨
age generiert werden.
4.4 Umgang mit nicht vertr¨
aglichen WF-Instanzen
Der Umgang mit nicht vertr¨
aglichen Instanzen stellt eben-
falls eine wichtige Herausforderung dar. In der Literatur (z.B.
[34]) wird hierzu meist vorgeschlagen, nicht vertr¨
agliche WF-
Instanzen bei Bedarf in ihrer Ausf¨
uhrung soweit zur¨
uckzu-
setzen, dass sie wieder einen mit S’ vertr¨
aglichen Zustand er-
reichen. Ein solch partielles Zur¨
ucksetzen ist auch in ADEPT
m¨
oglich. Wir haben dar¨
uber hinaus weiterf¨
uhrende Strategien
entwickelt [33], von denen im Folgenden eine (besonders in-
teressante) Variante im Zusammenhang mit ¨
Anderungen auf
Schleifen vorgestellt wird. Gegeben sei dazu eine WF-Instanz,
die zum Zeitpunkt der ¨
Anderungsdefinition nicht vertr¨
aglich
mit dem ge¨
anderten Schema S’ ist. Wird nun die Schleifen-
r¨
ucksprungkante sp¨
ater mit TRUE SIGNALED bewertet, er-
folgt eine Neubewertung aller Knoten des Schleifenk¨
orpers
mit NOT ACTIVATED. Damit sind die Voraussetzungen f¨
ur
eine Migration von Iauf S’ (entsprechend Def. 3.3) „versp¨
a-
tet” erf¨
ullt. Frage ist nun, wie mit solchen WF-Instanzen um-
gegangen werden soll. In keinem Fall darf eine unvertr¨
agliche
WF-Instanz sofort auf das neue WF-Schema migrieren, da an-
sonsten die eingangs genannten Probleme resultieren k¨
onnen.
Prinzipiell k¨
onnten solche WF-Instanzen dauerhaft nach dem
alten Schema weiterlaufen, unabh¨
angig davon, ob sie in der
Folge wieder in einen vertr¨
aglichen Zustand gelangen oder
nicht. Dies widerspricht jedoch dem Prinzip, dem Benutzer
eine m¨
oglichst große Menge migrierbarer Instanzen zu bie-
ten. Eine alternative Variante ist die verz¨
ogerte Migration von
Instanzen (delayed migration).
Beispiel (Verz¨
ogerte Migration). In Abb. 11 laufen zum Zeit-
punkt t=1drei WF-Instanzen I1,I
2und I3auf WF-
Schema S. Zum Zeitpunkt t=2findet eine Schema¨
anderung
statt, die Sauf S’ transformiert und infolge derer die bis-
herigen Instanzen auf S’ migrieren sollen (Migration M1).
I1sei zum Zeitpunkt t=2vertr¨
aglich mit S’ und kann
folglich sofort auf S’ migriert werden. I3sei zum Zeitpunkt
t=2und zu keinem der folgenden Zeitpunkte vertr¨
aglich
mit S’ und soll deshalb weiterhin Schema Sverwenden. I2
ist zwar zum Zeitpunkt t=2nicht vertr¨
aglich mit S’. Das
System erkennt jedoch, dass I2sich innerhalb einer Schleifen-
ausf¨
uhrung befindet und damit evtl. verz¨
ogert auf S’ migriert
werden kann. Deshalb wird I2als „pending to migrate (M1)
to S’ ” eingestuft. In diesem Zustand wartet I2auf einen
potenziellen Schleifenr¨
ucksprung. Das entsprechende Ereig-
nis wird intern in einer ECA-Tabelle (Event ConditionAction)
verwaltet. Tritt eine Bewertung der Schleifenr¨
ucksprungkante
mit TRUE SIGNALED ein, wird die zugeh¨
orige Aktion, n¨
am-
lich eine Migration von I2auf S’, ausgel¨
ost.
Ereignisse k¨
onnen UND/ODER-verkn¨
upft sein. So kann
eine verz¨
ogerte Migration bei verschiedenen Schleifenr¨
uck-
spr¨
ungen stattfinden, wenn sich die Ausf¨
uhrung der WF-
Instanz zum Zeitpunkt der Schema¨
anderung innerhalb einer
geschachtelten Schleife befindet. Wird die R¨
ucksprungkante
einer inneren Schleife nicht mit TRUE SIGNALED bewertet,
kann die Migration noch bei Signalisierung der R¨
ucksprung-
kante der ¨
außeren Schleife stattfinden.
Interessant ist der Fall, dass sich eine Instanz Imit Sche-
ma Sim Zustand „pending” befindet (also auf eine verz¨
ogerte
Migration auf ein Schema S’ wartet) und in dieser Phase ei-
ne weitere Schema¨
anderung S’ →S’’ stattfindet. Zun¨
achst
ist Ivon dieser ¨
Anderung nicht betroffen, da sich Iauf einer
Schemaversion vor der von der ¨
Anderung betroffenen Version
befindet. Kommt es jedoch sp¨
ater zur verz¨
ogerten Migration
von Iauf S’, muss analysiert werden, ob die letzte Schema-
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 193
A
B
C
D E
F
G
H
b) Zielschema S’:
A B C D
G
F
EH
a) Quellschema S:
d) Instanzen auf S’: c) Instanzen auf S:
A
B
C
D E
F
G
H
I1’:
A B C D
G
F
EH
I1:
A
B
C
D E
F
G
H
I2’:
A B C D
G
F
EH
I2:
X AND-Split AND-Join
Verschiebe C von aktueller
Position parallel zu B
Knotenzustände: Kantenzustände:
NS = ACTIVATED NS = COMPLETED ES = TRUE_SIGNALED
NS = RUNNING
Abb. 10. Ordnungsver¨
andernde Operation auf
WF-Schema in ADEPT
t = 1: t = 2: t = 3:
S
I1 I
2 I
3
loop_edge
S
Æ
S’
M1 S’
I3 I
1 (migrated)
I2 (pending M1) I3 I
1 (migrated)
I2 (delayed migration)
Event Condition Action
Loop_Back ES(loop_edge) = migrate I2 to S’
TRUE_SIGNALED
Abb. 11. Prinzip der verz¨
ogerten Migration (delayed migration)
¨
anderung ebenfalls auf Ipropagiert werden kann. Auch hier
k¨
onnen wieder die diskutierten F¨
alle – eine Migration ist so-
fort, verz¨ogert oder ¨
uberhaupt nicht m¨
oglich – eintreten.
5 Diskussion und Bewertung
Zun¨
achst diskutieren wir in Abschnitt 5.1 generelle Verfah-
ren f¨
ur Vertr¨
aglichkeitsanalysen und Instanzmigrationen und
vergleichen sie mit unserem Ansatz. Danach gehen wir in Ab-
schnitt 5.2 auf ausgew¨
ahlte Verfahren im Detail ein.
5.1 Bewertung und Vergleich alternativer Ans¨
atze
Welche Vorgehensweisen sind f¨
ur Vertr¨
aglichkeitsanalysen
und Migrationen von Instanzen generell denkbar?
Ansatz 1: Verfahren mit Einbeziehung der kompletten Ablauf-
historie. Einige Ans¨
atze (z.B. [9]) verwenden f¨
ur Vertr¨
aglich-
keitsanalysen und Migrationen die komplette Ablaufhistorie,
indem sie versuchen, alle bisherigen Ablaufereignisse zum
Start und Ende von Aktivit¨
aten auf dem neuen Schema „nach-
zuspielen”. Diese Vorgehensweise ist prinzipiell unabh¨
angig
von den zurAnwendung gekommenen ¨
Anderungsoperationen
sowie dem zugrundegelegten WF-Metamodell.
Ansatz 2: Verfahren ohne Historiendaten. Bei diesen Ver-
fahren, die z.B. bei Petri-Netzen anzutreffen sind, wird ledig-
lich der aktuelle Zustand (z.B. Token-Belegungen von Stel-
len) der zu migrierenden Instanzen ber¨
ucksichtigt. ¨
Ublicher-
weise wird zun¨
achst der von der ¨
Anderung betroffene Bereich
des Netzes bestimmt und dann die ¨
Anderungspropagation auf
diejenigen Instanzen eingeschr¨
ankt, deren Ausf¨
uhrung sich
aktuell nicht in diesem Bereich befindet (Variante 1). Alter-
nativ dazu wird vorgeschlagen, die Migrationen und die da-
durch notwendigen Markierungsanpassungen manuell durch
Benutzer vornehmen zu lassen (Variante 2). Dazu m¨
ussen ent-
weder Anwender f¨
ur jede Instanz entsprechende Adaptionen
durchf¨
uhren [14] oder der Modellierer gibt Regeln zur Abbil-
dung der Markierungen zwischen Quell- und Zielschema vor
[2,3].
Ansatz 3: Verfahren mit Verwendung „verdichteter”
Historieninformation. Hierunter fallen Vorschl¨
age wie
der in diesem Beitrag entwickelte Ansatz f¨
ur die system-
seitige Durchf¨
uhrung von Vertr¨
aglichkeitsanalysen und die
automatische Migration vertr¨
aglicher Instanzen. Insbeson-
dere sollen unn¨
otige Zugriffe auf die komplette Historie
vermieden werden und konsistente Markierungsanpassungen
erfolgen. Konsistent bedeutet, dass sich f¨
ur eine Instanz Ik
nach ihrer Migration auf das neue Schema S’ dieselben Zu-
194 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
standsmarkierungen ergeben, die man auch bei vollst¨
andiger
Ausf¨
uhrung von Iauf Grundlage von S’ erhalten h¨
atte.
Wir diskutieren nun die Vorteile unserer Vorgehensweise
gegen¨
uber den Ans¨
atzen 1 und 2.
Bewertung von Ansatz 1. Ansatz 1 gestaltet sich f¨
ur Work-
flows mit vielen Aktivit¨
ateninstanzen sehr aufwendig. Durch
das „Nachspielen” von Ablaufereignissen ergibt sich bereits
f¨
ur WF-Instanzen ohne Schleifen jeweils ein Aufwand von
O(n)(nist dabei die Anzahl der Knoten). In Verbindung
mit Schleifen, die m¨
oglicherweise viele Iterationen durchlau-
fen, kann der Historienumfang und damit der Rechenaufwand
noch gr¨
oßer ausfallen. Sei beispielhaft ein WF-Schema mit 20
Aktivit¨
aten gegeben, wobei 10 Aktivit¨
aten in einer Schleife
mit durchschnittlich 5 Iterationen eingebettet sind. Dann er-
gibt sich f¨
ur 20000 laufende WF-Instanzen eine durchschnitt-
liche Ablaufhistoriengr¨
oße von ca. 70 MB, wohingegen die
ben¨
otigte Markierungsinformation auf 0,2 MB nach oben be-
schr¨
ankt ist.5
Dar¨
uber hinaus ist Ansatz 1 in Bezug auf ¨
Anderungen
innerhalb von Schleifen zu restriktiv. Aufgrund der Historien-
eintr¨
age zu bereits beendeten Iterationen wird m¨
oglicherwei-
se eine Instanzmigration verboten, obwohl sie in der weite-
ren Ausf¨
uhrung nicht zu Inkonsistenzen f¨
uhren w¨
urde. Diese
Einschr¨
ankung kann mit dem von uns vorgestellten Vertr¨
ag-
lichkeitskriterium auf Schleifen (siehe Def. 3.3) aufgehoben
werden. Zu beachten ist auch, dass die Ablaufhistoriendaten
aufgrund ihrer Gr¨
oße ¨
ublicherweise nicht im Hauptspeicher
gehalten werden, so dass teure Externspeicherzugriffe not-
wendig werden. Abgesehen davon werden bei Ansatz 1 zahl-
reiche unn¨
otige Markierungsanpassungen in Bereichen vorge-
nommen, die von den ¨
Anderungen ¨
uberhaupt nicht betroffen
sind. Außerdem kann nicht direkt festgestellt werden, welche
Arbeitslisteneintr¨
age anzupassen sind. Ansatz 1 ist aus diesen
Gr¨
unden – besonders bei großer Instanzzahl – nicht praktika-
bel.
Bewertung von Ansatz 2. Der komplette Verzicht auf
Historien- oder Verlaufsdaten, wie von Ansatz 2 propagiert,
f¨
uhrt in der Praxis ebenfalls zu zahlreichen Problemen. Die
vorgestellte Variante 1 erweist sich bei genauerer Betrach-
tung als zu restriktiv, da auch solche Instanzen von einer
¨
Anderungspropagation ausgeschlossen werden k¨
onnen, die
bei Anwendung unseres Verfahrens problemlos migrierbar
sind.Aufgrund der speziellen Eigenschaften vieler Petri-Netze
(z.B. keine klare Trennung von Kontroll- und Datenfluss)
k¨
onnen zudem ¨
Anderungsbereiche in Relation zum Gesamt-
netz sehr groß werden, so dass u.U. die Mehrzahl der Instan-
zen von einer Migration ausgeschlossen wird. Abgesehen da-
von ist die Bestimmung der von der ¨
Anderung betroffenen
Bereiche i. A. sehr aufwendig. Bei dem in [1] vorgestellten
Ansatz etwa betr¨
agt die Komplexit¨
at hierf¨
ur O(n4∗(n!)2).
Zus¨
atzlich muss noch f¨
ur jede Instanz gepr¨
uft werden, ob sie
5Ein einzelner Historieneintrag einer WF-Instanz umfasst in
ADEPT etwa Informationen wie Ereignistyp (Short, 2 Bytes),
Aktivit¨
atenbezeichner (Long, 8 Bytes), Bearbeiter (Long,
8 Bytes), Zeitstempel (Long, 8 Bytes), Iterationsz¨
ahler
(Short, 2 Bytes) undVerzweigungsentscheidung (Short, 2
Bytes). Damit ergibt sich pro Historieneintrag eine Gr¨
oße von
30 Bytes. Dagegen wird zur Speicherung der jeweiligen Knoten-
markierung bei unserem Ansatz nur 1 Byte ben¨
otigt.
sich in ihrer Ausf¨
uhrung aktuell in diesem Bereich befindet.
Hierf¨
ur muss die Token-Belegung des Gesamtnetzes unter-
sucht werden, woraus ein Aufwand von O(n)f¨
ur jede Instanz
resultiert. Um dem Problem zu begegnen, dass mit Variante
1 zu viele Instanzen von einer ¨
Anderungspropagation aus-
geschlossen werden, gibt es Vorschl¨
age aus dem Petri-Netz-
Bereich, die Migration f¨
ur einzelne Instanzen nach Verlassen
des ¨
Anderungsbereichs nachzuholen. Dies erfordert jedoch,
dass nach jedem normalen Schalten einerTransition zus¨
atzlich
¨
uberpr¨
uft werden muss, ob dieser Fall schon eingetreten ist.
Damit erh¨
oht sich die Komplexit¨
at des Verfahrens auf O(n2).
Variante 2 verfolgt einen g¨
anzlich anderen Ansatz, indem so-
wohl die Vertr¨
aglichkeitsanalysen als auch die Markierungs-
anpassungen auf den Benutzer verlagert werden. Um sicher-
zustellen, dass es dabei in der Folge nicht zu Verklemmungen
kommt, m¨
ussten zudem f¨
ur jede Instanz aufwendige Erreich-
barkeitsanalysen (mit exponentieller Komplexit¨
at) durchge-
f¨
uhrt werden. Dies w¨
urde zu erheblichen Verz¨
ogerungen bei
der Instanz-Ausf¨
uhrung f¨
uhren.Variante 2 ist deshalb eher von
theoretischer Natur und w¨
urde in der Praxis so nicht akzeptiert
werden.
Bewertung von Ansatz 3. Bei Verwendung verdichteter
Historiendaten, wie in dem von uns entwickelten Ansatz 3,
betr¨
agt der Aufwand f¨
ur Vertr¨
aglichkeitsanalysen schlech-
testenfalls O(n). Dieser Fall tritt in ADEPT aber praktisch
nie auf. W¨
ahlt man z.B. f¨
ur das Einf¨
ugen eines Aktivit¨
aten-
knotens ninsert eine realistische Wahrscheinlichkeitsvertei-
lung f¨
ur die Anzahl der Nachfolger von ninsert, bel¨
auft sich
die erwarteteAnzahl an Zustands¨
uberpr¨
ufungen auf zwei. Ein
wesentlicher Vorteil bei den von uns durchgef¨
uhrten Vertr¨
ag-
lichkeitsanalysen ist auch, dass wir gezielt die Semantik der
zur Anwendung gekommenen ¨
Anderungsoperationen nutzen.
Ein weiterer Vorteil liegt darin, dass die ben¨
otigten Markie-
rungsdaten aufgrund ihrer geringen Gr¨
oße in der Mehrzahl
der F¨
alle im Hauptspeicher gehalten werden k¨
onnen. Dar¨
uber
hinaus k¨
onnen die bei Migrationen notwendigen Zustands-
anpassungen automatisch erfolgen. Die Komplexit¨
at des vor-
gestellten Verfahrens betr¨
agt O(n). Wie gezeigt, wird man in
der Mehrzahl der F¨
alle mit wesentlich geringerem Rechenauf-
wand zum Ziel kommen.
5.2 Diskussion ausgew¨
ahlter Ans¨
atze
Ein erster L¨
osungsansatz zur Evolution von WF-Schemata
wurde im Bereich der Petri-Netze in [13] pr¨
asentiert. F¨
ur
die WF-Modellierung und -Steuerung werden sog. Flussnetze
verwendet, welche zur Laufzeit mehrere WF-Instanzen mit
unterscheidbaren Marken kontrollieren. Eine ¨
Anderung des
Schemas erfolgt formal durch eine Netztransformation, wo-
bei ein markiertes Subnetz durch ein anderes markiertes Sub-
netz ersetzt wird. Wie in Abschnitt 5.1 (Ansatz 2, Variante
2) diskutiert, erfordert die ¨
Uberpr¨
ufung der Korrektheit des
resultierenden Netzes komplexe Erreichbarkeitsanalysen f¨
ur
jede Instanz. Hinzu kommt, dass der Modellierer f¨
ur jede WF-
Instanz die Markierungsanpassungen selbst vornehmen muss
[14]. Außerdem bleiben Fragestellungen wie Anpassungen
von Daten߬
ussen oder Arbeitslisten unbeantwortet.
Ein Beispiel f¨
ur Ansatz 2, Variante 1 aus Abschnitt 5.1 fin-
det sich in [1]. Hierbei kann eine WF-Instanz nicht auf ein mo-
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 195
Tabelle 4. Vergleich verschiedener Ans¨
atze
Bewertungsaspekte Ansatz 1 Ansatz 2 (Var.1) Ansatz 2 (Var.2) Ansatz 3
[9] [1] [14] ADEPT
Vertr¨
aglichkeitsanalysen
-pr
¨
azise formale Bedingungen ++ +++
- Reduzierung d. Analyse-/Anpassungsaufwands
•durch Ausnutzung der ¨
Anderungssemantik −− − − +
•durch Verdichtung der Zustandsinformation −− +◦++
Gesamtaufwand f¨
ur Vertr¨
aglichkeitsanalysen O(n)O(n4∗(n!)2)O(en)O(n)
O(n2)∼2 Op.
- Kosten durch Externspeicherzugriffe −− +++
- Autom. Erkennung aller migrierbaren Instanzen ◦− −−++
Automatische Migration vertr¨
aglicher Instanzen +◦−−+
(automatische Zustandsanpassungen) O(n)
Praxistauglichkeit ◦−− −−+
difiziertes Petri-Netz migrieren, solange sie sich in ihrer Aus-
f¨
uhrung im von der ¨
Anderung betroffenen Bereich befindet.
Die Anpassung von Netzmarkierungen bei der Propagation
von Schema¨
anderungen wird als schwieriges Problem (dyna-
mic change bug) erkannt [2,3]. Als L¨
osung wird vorgeschla-
gen, dass der Modellierer eine Funktion zur Abbildung der
Markierungen zwischen Quell- und Zielnetz angibt, die dann
auf jede Instanz anwendbar ist [2]. Dieser Ansatz ist aber al-
lein aus kombinatorischen Gr¨
unden nicht immer praktikabel.
Das gilt besonders f¨
ur den Fall, dass durch das Netz nicht nur
der Kontrollfluss, sondern auch die Datenfl¨
usse zwischen Ak-
tivit¨
aten abgebildet werden. Abschließend sei erw¨
ahnt, dass
Petri-Netze noch weitere Probleme, wie fehlende Verlaufs-
markierungen, mangelhafte Trennung von Kontroll- und Da-
tenfluss und implizite Schleifen-Modellierung aufweisen.
Einige Ans¨
atze zur Evolution von WF-Schemata verwen-
den ein graph-basiertes WF-Metamodell. In WIDE [9] werden
dem Modellierer ¨
Anderungsoperationen angeboten, mit deren
Hilfe ein Schema S in ein korrektes Schema S’ transformiert
werden kann (statischer Fall). Zur Sicherstellung der Korrekt-
heit bei Migration der von S abgeleiteten, noch laufenden In-
stanzen auf S’ (dynamischer Fall) wird erstmals ein Vertr¨
ag-
lichkeits-Kriterium verwendet. Leider fehlen Angaben dazu,
ob bzw. wie sich unter Verwendung der kompletten Ablauf-
historie (sieheAbschnitt 5.1,Ansatz 1)Vertr¨
aglichkeit konkret
feststellen l¨
asst und wie Instanzen nach ihrer Migration auf das
ge¨
anderte Schema anzupassen sind.
Versionierungskonzepte bilden einen Schwerpunkt in
TRAM [24]. Bei ¨
Anderung eines WF-Typs wird eine neue
Version abgeleitet und als Sohnknoten im Versionsbaum ge-
speichert. Dann wird versucht, die nach der alten Version ω
laufenden Instanzen unter Erhalt des in [9] definierten Ver-
tr¨
aglichkeits-Kriteriums auf die abgeleitete Version ωzu mi-
grieren. Dabei denken die Autoren ¨
uber eine effiziente ¨
Uber-
pr¨
ufung der zur neuen Version vertr¨
aglichen Instanzen nach
und schlagen die Definition sog. Migrationsbedingungen vor,
anhand derer f¨
ur jede Instanz ¨
uberpr¨
uft werden kann, ob sie
zu einem bestimmten Zeitpunkt auf ωmigriert werden kann.
Es gibt keine Hinweise zur Vertr¨
aglichkeit von Instanzen bei
Datenfluss¨
anderungen oder im Umgang mit Schleifen.
Aktuelle Ergebnisse stammen aus dem Projekt BREEZE
[34]. Die Autoren orientieren sich dabei am ADEPT-Meta-
modell, wobei der Fokus auf der Behandlung nicht vertr¨
ag-
licher WF-Instanzen liegt. WF-Instanzen, die nicht vertr¨
aglich
mit dem ge¨
anderten WF-Schema S’ sind, sollen ¨
uber teilwei-
ses Rollback (dargestellt durch ein spezielles Konstrukt, den
sog. Vertr¨
aglichkeits-Graphen) in einen vertr¨
aglichen Zustand
r¨
uckversetzt werden. Dies ist theoretisch zwar sehr interessant,
kann aber nicht immer durchgef¨
uhrt werden, da Aktivit¨
aten
in der Praxis oftmals nicht kompensierbar sind. Es wird we-
der diskutiert, wie WF-Instanzen (effizient) migriert werden
k¨
onnen, noch wie Schleifen oder Daten߬
usse behandelt wer-
den sollen.
Einen regelbasierten Ansatz bietet ULTRAflow [15]. Be-
sonderes Augenmerk wird hier auf die Modifikation der
Implementierung und der Metadaten von Schritten gelegt.
Um einen konsistenten Zugriff der einzelnen Instanzen auf
die ge¨
anderten Spezifikationen zu regeln, werden spezielle
Synchronisationsverfahren verwendet. Zwecks Reduzierung
der Komplexit¨
at klammern die Autoren jedoch z.B. L¨
osch-
operationen oder Datenflussaspekte ganz aus.
Objektorientierte Ans¨
atze finden sich in [21,22,36,38]. In
MOKASSIN [22,21] werden ¨
Anderungen durch Kapselung
von ¨
Anderungsprimitiven in den WF-Instanzen realisiert, d.h.
die Instanzen selbst sind f¨
ur den Erhalt der Konsistenz bei
¨
Anderungen zust¨
andig. Das Vertr¨
aglichkeits-Kriterium wird
als zu restriktiv eingestuft und eine L¨
osung ¨
uber ein fein-
granulares Versionierungskonzept diskutiert. Aussagen zur
(effizienten) ¨
Uberpr¨
ufbarkeit der Vertr¨
aglichkeit von WF-
Instanzen fehlen. Abgesehen davon erschweren die angebo-
tenen Konzepte zur Erweiterbarkeit die Propagierung von
Schema¨
anderungen auf laufende Instanzen. In WASA2wird
ebenfalls ein m¨
achtigesVersionierungskonzept angeboten [36,
37].Auch hier diskutiert derAutor M¨
oglichkeiten zur effizien-
ten ¨
Uberpr¨
ufung der Vertr¨
aglichkeit, indem er eine Abbildung
zwischen dem ge¨
anderten Schema und dem Subworkflow, der
sich aus dem Status der zu untersuchenden Instanz ergibt, vor-
schl¨
agt. Hierbei handelt es sich um einen der wenigenAns¨
atze,
zu denen auch Erfahrungen aus der Implementierung der vor-
gestellten Konzepte vorliegen [38]. Detaillierte Betrachtungen
196 S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen
zu Schleifen oder zur Anpassung von Daten߬
ussen wurden
unseres Wissens noch nicht ver¨
offentlicht.
In [16] werden nur Schema¨
anderungen ohne Instanz-
migrationen betrachtet. Allerdings ist der Ansatz im Hinblick
auf Semantikaspekte bei Schema¨
anderungen interessant. Als
WF-Metamodell werden Statecharts verwendet, ¨
uber deren
¨
Aquivalenz die Semantik von modellierten Abl¨
aufen nach
¨
Anderungen erhalten bleiben soll. F¨
ur WfMS, die Ad-hoc-
-Abweichungen vom vorgeplanten Ablauf unterst¨
utzen (wie
z.B. ADEPT), er¨
offnen sich hierdurch interessante M¨
oglich-
keiten der automatischen oder semi-automatischen Schema-
Adaption.
6 Zusammenfassung und Ausblick
In diesem Beitrag haben wir einen umfassenden und theo-
retisch fundierten Ansatz f¨
ur die bei WF-Schema¨
anderun-
gen notwendigen Vertr¨
aglichkeitspr¨
ufungen und WF-Instanz-
migrationen vorgestellt. Besonderes Augenmerk lag dabei auf
Korrektheits- und Konsistenzaspekten, Benutzerfreundlich-
keit und Effizienz. Den daraus resultierenden Anforderungen
werden wir einerseits durch effiziente Pr¨
ufung auf Vertr¨
ag-
lichkeit mit dem neuen Schema und andererseits durch au-
tomatische Anpassung von Zust¨
anden bei der Migration ver-
tr¨
aglicher Instanzen gerecht. Wir haben teilweise eine formale
Darstellung gew¨
ahlt, um pr¨
azise Aussagen dar¨
uber treffen zu
k¨
onnen, wann eine Instanz auf ein neues Schema migriert wer-
den darf und welche Informationen f¨
ur entsprechende ¨
Uber-
pr¨
ufungen ben¨
otigt werden. Dies ist f¨
ur die Implementati-
on eines solchen Konzepts essenziell. Auch f¨
ur die Migra-
tion vertr¨
aglicher Instanzen haben wir einen Ansatz vorge-
stellt. Wir haben uns nicht nur auf Kontroll߬
usse beschr¨
ankt,
sondern auch Datenflussaspekte behandelt. Dabei haben wir
Querbez¨
uge und Zusammenh¨
ange aufgezeigt. Erstmals wer-
den in dieser Arbeit auch Schleifen in die Untersuchungen zu
Vertr¨
aglichkeitspr¨
ufungen einbezogen, relevante Problemstel-
lungen diskutiert und L¨
osungsans¨
atze aufgezeigt. Dabei wer-
den Varianten des in diesem Falle zu restriktiven herk¨
ommli-
chen Vertr¨
aglichkeitskriteriums vorgestellt. Die gewonnenen
Ergebnisse sind nicht nur spezifisch f¨
ur ADEPT g¨
ultig, son-
dern k¨
onnen auch auf vergleichbareAusf¨
uhrungsmodelle [26,
34,36,37] ¨
ubertragen werden.
Insgesamt werden die vorgestellten Konzepte und Ver-
fahren den eingangs genannten Anforderungen gerecht.
Wie erw¨
ahnt, bestehen aber noch weiter gehende Anfor-
derungen. Ihre ad¨
aquate Handhabung und die Entwicklung
entsprechender L¨
osungskonzepte werden Bestandteil unse-
rer zuk¨
unftigen Forschungsarbeiten sein. Hierbei soll auch
der Frage nachgegangen werden, ob bzw. inwieweit WF-
Schema¨
anderungen auch aufWF-Instanzen propagiert werden
k¨
onnen, deren Ausf¨
uhrungsgraph in Folge einer Ad-hoc- ¨
An-
derung strukturell vom urspr¨
unglichen WF-Schema abweicht
[31]. Bisherige Ans¨
atze beziehen Ad-hoc- ¨
Anderungen entwe-
der gar nicht ein oder aber sie lassen f¨
ur diesen Fall die Pro-
pagierung von Schema¨
anderungen nicht mehr zu. Außerdem
werden wir Semantik-Aspekte bei Vertr¨
aglichkeitspr¨
ufungen
sowie die ¨
Anderung weiterer Bestandteile des WfMS in unse-
re Untersuchungen einbeziehen.Von besonderem Interesse f¨
ur
uns ist das Zusammenspiel der verschiedenen Konzepte und
deren Umsetzung in einem lauff¨
ahigen System. Nur so l¨
asst
sich ¨
uberpr¨
ufen, ob die betreffenden Konzepte in der Praxis
und bei Anwendung auf komplexe Ablaufbeispiele ad¨
aquat
umsetzbar sind. Die in diesem Beitrag beschriebenen Kon-
zepte werden derzeit prototypisch umgesetzt.
Literatur
1. van der Aalst, W.M.P.: Exterminating the Dynamic Change Bug:
A Concrete Approach to Support Workflow Change. Information
Systems Frontiers 3(3): 297–317 (2001)
2. van der Aalst, W.M.P., Basten, T.: Inheritance of Workflows: An
Approach to Tackling Problems Related to Change. Theoretical
Computer Science 270(1-2): 125–203 (2002)
3. van der Aalst, W.M.P., Jablonski, S.: Dealing with Workflow
Change: Identification of Issues and Solutions. Int’l Journal
of Comp. Systems, Science and Engineering, 15(5): 267–276
(2000)
4. Andany, J., Leonard, M., Palisser, C.: Management of Schema
Evolution in Databases. Proc. Int’l Conf. on Very Large Databa-
ses, Barcelona, Sept. 1991, pp. 161–170
5. Bassil, S., Benyoucef M., Keller R., Kropf P.: Addressing Dyna-
mism in E-negotiations by Workflow Management Systems. Proc.
13th Int’l Workshop on Database and Expert Systems Applica-
tions (DEXA’2002), Aix-en-Provence, France, September 2002
6. Bauer, T., Dadam, P.: Efficient Distributed Workflow Manage-
ment Based on Variable Server Assignments. Proc. CAiSE ’00,
Stockholm, Juni 2000, pp. 94–109
7. Bauer, T., Reichert, M., Dadam, P.: Adaptives und verteiltes
Workflow-Management. Proc. Datenbanksysteme in B¨
uro, Tech-
nik und Wissenschaft, Oldenburg, M¨
arz 2001, pp. 47–66
8. Beuter, T., Dadam, P., Schneider, P.: The WEP Model: Adequate
Workflow-Management for Engineering Processes. Proc. Europ.
Concurrent Engineering Conf. 1998, Erlangen, April 1998
9. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workflow Evolution.
Data and Knowledge Engineering 24(3): 211–238 (1998)
10. Conrad, S.: F¨
oderierte Datenbanksysteme – Konzepte der Da-
tenintegration. Springer, 1997
11. Dadam, P.: Verteilte Datenbanken und Client/Server-Systeme.
Springer, 1996
12. Dadam, P., Reichert, M., Kuhn, K.: Clinical Workflows - The
Killer Application for Process-oriented Information Systems?
Proc. 4th Int’l Conf. on Business Information Systems (BIS ’00),
Poznan, 2000, pp. 36–59
13. Ellis, C.A., Keddara, K., Rozenberg, G.: Dynamic Change wi-
thin Workflow Systems. Proc. Int’l ACM Conf. on Organizational
Comp. Sys. (COOCS ’95), Milpitas, CA, Aug. 1995, pp. 10–21
14. Ellis, C.A., Maltzahn, C.: The Chautauqua Workflow System.
Proc. 30th Int’l Conf. on System Science, Maui, Hawaii, 1997
15. Fent, A., Reiter, H., Freitag, B.: Design for Change: Evolving
Workflow Specifications in ULTRAflow, Proc. Int’l Conf. on Ad-
vanced Information Systems Engineering (CAISE ’02), Toronto,
May 2002, pp. 516–534
16. Frank, H., Eder, J.: Equivalence Transformations on Statecharts.
Proc. 12th Int’l Conf. on Software Engineering and Knowledge
Engineering (SEKE ’00), Chicago, July 2000, pp. 150–158
17. Gartner Group:Why E-Business Craves Workflow Technology,
Report, T-09-4929, Dec. 1999
18. Hammer, M., Champy, J.: Reengineering the Corporation. Har-
per Collins Publ. 1993
19. Hensinger, C., Reichert, M., Bauer, T., Strzeletz, T., Dadam, P.:
ADEPTworkflow – Advanced Workflow Technology for the Effi-
cient Support of Adaptive, Enterprise-wide Processes. Proc. Soft-
ware Demonstration Track (EDBT ’00), Konstanz, M¨
arz 2000,
pp. 29–30
S. Rinderle et al.: Effiziente Vertr¨
aglichkeitspr¨
ufung und automatische Migration von Workflow-Instanzen 197
20. Jablonski, S., B¨
ohm, M., Schulze, W.: Workflow Management
Entwicklung von Anwendungen und Systemen. dpunkt, 1999
21. Joeris, G.: Defining Flexible Workflow Execution Beha-
viors. Proc. GI-Workshop, Enterprise-wide and Cross-enterprise
Workflow-Management (Informatik ’99), Oct. 1999, pp. 49–55
22. Joeris, G., Herzog, O.: Managing Evolving Workflow Specifi-
cations. Proc. Int’l Conf. on Cooperative Information Systems
(CoopIS ’98), New York City, August 1998, pp. 310-321
23. Kappel, G.: Reorganizing Object Behavior by Behavior Compo-
sition - Coping with Evolving Requirements in Office Systems.
Proc. BTW ’91, Kaiserslautern, March 1991, pp. 446–453
24. Kradolfer, M., Geppert, A.: Dynamic Workflow Schema Evoluti-
on Based on Workflow Type Versioning and Workflow Migration.
Proc. CoopIS ’99, Edinburgh, Sept. 1999, pp. 104–114
25. Leymann, F., Roller, D.: Production Workflow. Prentice Hall,
2000
26. Martschat, U.: Vergleich und Bewertung von Producti-
on Workflow-Management-Systemen. Diplomarbeit, Universit¨
at
Ulm, Fakult¨
at f¨
ur Informatik, 2001
27. M¨
uller, R., Rahm, E.: Dealing with Logical Failures for Colla-
borating Workflows. Proc. Int’l 5th Conf. on Cooperative Infor-
mation Systems, Eilat, 2000, pp. 210–223
28. Oberweis, A.: Modellierung und Ausf¨
uhrung von Workflows mit
Petri-Netzen. Teubner, 1996
29. Reichert, M.: Dynamische Ablauf¨
anderungen in Workflow-
Management-Systemen. Dissertation, Universit¨
at Ulm, Fakult¨
at
f¨
ur Informatik, 2000
30. Reichert, M., Bauer, T., Fries, T., Dadam, P.: Modellierung plan-
barer Abweichungen in Workflow-Management-Systemen. Proc.
Modellierung ’02, Tutzing, M¨
arz 2002, pp. 183–194
31. Reichert, M., Dadam, P.: ADEPTflex - Supporting Dynamic
Changes of Workflows Without Losing Control. Journal of In-
telligent Information Systems 10(2): 93–129, (1998)
32. Reichert M., Rinderle S.: ¨
Anderungsrechte in adap-
tiven Workflow-Management-Systemen. Proc. Sichere
Gesch¨
aftsprozesse, St. Leon-Rot, September 2002, pp. 30–
42
33. Rinderle, S., Reichert, M., Dadam, P.: Effiziente Ver-
tr¨
aglichkeitspr¨
ufung und automatische Migration von
Workflow-Instanzen bei der Evolution von Workflow-
Schemata. Ulmer Informatik-Berichte, Nr. 2002-01, April
2002, http://www.informatik.uni-ulm.de/pw/berichte
34. Sadiq, S., Orlowska, M.: On Capturing Exceptions in Workflow
Process Models. Proc. 4th Int’l Conf. on Business Information
Systems (BIS ’00), Poznan, April 2000
35. Schultheiß, B., Meyer, J., Mangold, R., Zemmler, T., Reichert,
M.: Prozessentwurf f¨
ur den Ablauf einer station¨
aren Chemothe-
rapie. DBIS-5, Universit¨
at Ulm, Nov. 1995
36. Weske, M.: Flexible Modeling and Execution of Workflow Acti-
vities. Proc. 31st Int’l Conf. on System Sciences, Hawaii, 1998,
pp. 713–722
37. Weske, M.: Adaptive Workflows based on Flexible Assignment of
Workflow Schemes and Workflow Instances. Proc. GI-Workshop,
Enterprise-wide and Cross-enterprise Workflow-Management
(Informatik ’99), Oktober 1999, pp. 42–48
38. Weske, M., H¨
undling, J., Kuropka, D., Schuschel, H.: Ob-
jektorientierter Entwurf eines flexiblen Workflow-Management-
Systems. Informatik - Forschung und Entwicklung 13(4): 179–
195, (1998)
39. Wiedemuth-Catrinescu, U.: Evolution von Organisationsmodel-
len in Workflow-Management-Systemen. Diplomarbeit, Univer-
sit¨
at Ulm, Fakult¨
at f¨
ur Informatik, 2002
Stefanie Rinderle studierte Wirtschafts-
mathematik in Augsburg. Seit ihrem Di-
plom im November 2000 ist sie wis-
senschaftliche Mitarbeiterin der Univer-
sit¨
at Ulm, Abteilung Datenbanken und In-
formationssysteme. Ihre Interessen liegen
in den Bereichen Workflow-Management
und ¨
Anderungsmanagement in adaptiven
Workflow-Systemen.
Manfred Reichert ist seit Oktober 2002
Juniorprofessor in der Abteilung Da-
tenbanken und Informationssysteme der
Universit¨
at Ulm. Hier promovierte er
im Juli 2000 zum Thema “Dynami-
sche Ablauf¨
anderungen in Workflow-
Management-Systemen”. Aktuelle Ar-
beitsgebiete sind unternehmensweite und
-¨
ubergreifende WF-Anwendungen, EAI
und Workflow sowie verschiedene Aspek-
te von WfMS.
Peter Dadam ist seit 1990 Professor f¨
ur In-
formatik an der Universit¨
at Ulm und Leiter
derAbteilung Datenbanken und Informati-
onssysteme. Davor war er Leiter derAbtei-
lung Advanced Information Management
am Wissenschaftlichen Zentrum der IBM
in Heidelberg. Seine aktuellen Arbeits-
gebiete sind: Verteilte, kooperative Infor-
mationssysteme, Workflow-Management,
Datenbanktechnologie und deren Anwen-
dungen in anspruchsvollen Anwendungs-
gebieten.
