Speichereffiziente Repräsentation instanzspezifischer
Änderungen in Prozess-Management-Systemen
Ulrich Kreher, Manfred Reichert
Institut für Datenbanken und Informationssysteme, Universität Ulm,
{Ulrich.Kreher, Manfred.Reichert}@uni-ulm.de
Zusammenfassung
Neben Funktionen für die Steuerung und Verwaltung von Prozessen muss ein Prozess-Manage-
ment-System (PMS) auch eine gewisse Flexibilität für Endbenutzer bieten. So sollte es bei-
spielsweise möglich sein, zur Laufzeit fallspezifisch und flexibel vom vordefinierten Prozess
abzuweichen, d. h. die betreffende Prozessinstanz strukturell zu modifizieren. Entsprechende
Ad-hoc-Änderungen dürfen jedoch weder zu Lasten der Robustheit des PMS noch auf Kosten
der Systemperformanz gehen, insbesondere wenn eine große Zahl von Instanzen verwaltet
werden muss. Robustheitsaspekte im Zusammenhang mit der Unterstützung von Flexibilität
des PMS sind bereits in mehreren Arbeiten theoretisch untersucht worden. In diesem Beitrag
untersuchen wir, wie Flexibilität in Prozess-Management-Systemen systemintern realisiert
werden kann und wie dies möglichst performant bewerkstelligbar ist. Dazu diskutieren wir
verschiedene Realisierungskonzepte sowie einige Implementierungsvarianten für Änderungen
auf Prozessen und bewerten diese sowohl qualitativ als auch quantitativ. Eine der vorgestellten
Implementierungsvarianten ist aktuell im ADEPT2-PMS umgesetzt.
1 Einleitung
Prozess-Management-Systeme (PMS) erlauben durch die Trennung von Prozess- und Anwendungs-
logik eine flexible Komposition von Anwendungsdiensten [22]. Diese Flexibilität wird jedoch nicht
nur a-priori bei der Prozessmodellierung bzw. -erstellung benötigt, sondern auch zur Laufzeit
[12, 15]. Sie ist bereits in mehreren Arbeiten untersucht worden [18, 3, 31], jedoch konzentrieren
sich diese überwiegend auf theoretische Aspekte wie der Korrektheit dynamischer Änderungen
[16, 17] oder der Semantik angebotener Änderungsmuster [29, 27]. Außerdem wird meist nur eine
Art von Prozessadaptionen betrachtet, d. h. entweder Änderungen einzelner Prozessinstanzen oder
Änderungen an Prozessvorlagen und deren Propagation auf laufende Prozessinstanzen. Für eine
hohe Benutzerakzeptanz ist jedoch die Unterstützung beider Änderungsarten und vor allen Din-
gen deren Kombination unabdingbar. Dies ist im adaptiven Prozess-Management-System (PMS)
ADEPT2 der Fall [7, 25, 23, 20]. Neben umfassenden Anforderungen an das dynamischen Änderun-
gen zugrundeliegende theoretische Modell ergeben sich durch Kombination beider Änderungsarten
auch weitreichende Konsequenzen für deren praktische Umsetzung. In diesem Beitrag untersuchen
wir, wie diese praktische Umsetzung konkret aussehen kann. Aufbauend auf der effizienten Reprä-
sentation von Vorlagen- und (unveränderten) Prozessinstanzen [10] gilt unser Hauptaugenmerk
der Effizienz der Realisierung.
1.1 Problembeschreibung
In einem Prozess-Management-System werden Prozessvorlagen verwaltet [10]. Dabei wird die Pro-
zessstruktur häufig graphbasiert mittels Knoten und Kanten repräsentiert [14, 13, 18, 16, 1]. Kno-
ten repräsentieren Aktivitäten, die innerhalb eines Prozesses durchgeführt werden müssen, Kanten
1
unveränderteProzessinstanzenV V
Iº
veränderteProzessinstanzenVIV+º D
ü
ü
u
u
I10
ü
ü
u
I11
p
ü
ü
ü
ü ü
I9
ü
ü
ü ü
u
I8
ü
üu
p
I7
ü
ü
ü
ü
p
I5
ü
ü
p
I2
Prozessvorlage
(VersioneinesProzesstyps)
Prozesstyp
(Versionsbaum)
A
B
C
D E F
W,V2.0
A
B
C
D E F
G
W,V.2.2
ZYX
V1.1
V1.0
V2.1
W
V2.2
V2.0
Knotenzustände:
: ACTIVATED
: SELECTED
: RUNNING
: COMPLETED
: SKIPPED
: FAILED
p
q
u
ü
û
Õ
ü
ü
ü
ü ü p
I6
ü
ü
ü
üp
I4
u
I3
ü
ü
ü
u
I1
Abbildung 1: Verwaltung von Prozessgraphen in einem adaptiven PMS (logische Sicht)
entsprechen (Reihenfolge-)Abhängigkeiten zwischen diesen Aktivitäten. Eine konkrete Prozessaus-
führung erfolgt auf Grundlage einer Prozessinstanz, die eine Prozessvorlage mit Zustandsinforma-
tionen versieht. Diese Zustandsinformationen spiegeln sich in Knotenzuständen wider, wobei die
Gesamtheit der Zustände aller Knoten einer Prozessinstanz den jeweils aktuellen Instanzzustand
definiert. Ferner wird die Ausführung jeder Prozessinstanz in Ausführungs- und Datenhistorien
protokolliert [2, 9, 28]. Prozessvorlagen werden zur einfacheren Verwaltung in Prozesstypen kate-
gorisiert (s. Abb. 1)
Flexibilität wird von einem PMS insbesondere durch die rasche und fehlerfreie Änderbarkeit
von Prozessen unterstützt [21, 6]. Dies betrifft einerseits Schemaevolution, also das Ändern von
Prozessvorlagen (sog. Vorlagenänderungen) und ggf. die Propagation dieser Änderungen auf lau-
fende Prozessinstanzen (Migration von Instanzen) [24, 30], andererseits die Möglichkeit, ausge-
wählte laufende Prozessinstanzen jederzeit individuell ändern zu können (sog. Instanzänderungen
oder instanzspezifische Änderungen, siehe Instanz I10 rechts in Abb. 1) [18]. Beide Aspekte bilden
unabhängige Dimensionen des „Problemraums“ der effizienten Repräsentation von Vorlagen- und
Instanzdaten. Eine weitere Dimension bilden die verschiedenen Prozesstypen innerhalb eines PMS
(links in Abb. 1). Allerdings kann davon abstrahiert werden, da Änderungen auf Vorlagenebene
sinnvollerweise nur innerhalb der Prozessvorlagen eines Prozesstyps (d. h. eines Versionsbaums)
durchgeführt werden und die Prozesstypen damit voneinander unabhängig sind.
Wie in [10] diskutiert, ist eine weitere Dimension durch die Speicherart gegeben, in der Pro-
zessdaten repräsentiert werden. Gemeint ist die Speicherrepräsentation in Primär- und Sekun-
därspeicher, wobei die Repräsentation der Prozessdaten jeweils unterschiedlich sein kann. Damit
ergibt sich die in Abb. 2 gezeigte Struktur. Während wir die Bereiche I und II bereits in [10] disku-
tiert haben, untersuchen wir in diesem Beitrag den Bereich III sowie zusätzlich die Dimension der
Vorlagen(-änderungen) der Bereiche I bis III. Der Bereich IV ist Gegenstand zukünftiger Arbeiten;
prinzipiell lassen sich die Überlegungen zur Repräsentation von unveränderten Prozessinstanzen in
Primär- und Sekundärspeicher (I und II) aber auf veränderten Instanzen (III und IV) übertragen.
1.2 Anforderungen
Die Anforderungen an die effiziente Unterstützung instanzspezifischer Änderungen sind mit den
Anforderungen bei der Repräsentation von Vorlagen und unveränderten Instanzen vergleichbar
[10]. Zusätzlich müssen beide Änderungsarten in Kombination miteinander unterstützt werden.
2
Speicher
Instanz
Vorlage
(VersioneinesProzesstyps)
Prozesstyp A
I
II
III
IV
primär
sekundär
unverändert verändert
1.0
2.1
2.0
Abbildung 2: Problemdimensionen bei der Verwaltung von Prozessdaten
Wir zeigen, dass dies Auswirkungen auf die Repräsentation unveränderter Instanzen (Bereich I
und II) hat. Zu beachten ist, dass instanzspezifische Änderungen in bestimmten Einsatzszenarien
eines PMS den Normalfall bilden [5, 4] und damit eine performante Repräsentation unabdingbar
ist.
Die Effizienz der Repräsentation von Vorlagen- und Instanzdaten spiegelt sich zum einen im
Primärspeicherbedarf der Prozessdaten und zum anderen in der Laufzeit verschiedener Funktionen
wider. Hierzu zählen insbesondere das Weiterschalten im Prozess (nach Beendigung von Aktivitä-
ten) sowie die transitive Bestimmung von Vorgängerknoten, d. h. die Ermittlung von Knoten, die
direkt oder indirekt Vorgänger eines bestimmten Knotens sind.
Eine weitere wichtige Anforderung ist die weitgehende Transparenz von instanzspezifischen Än-
derungen für diese Funktionen. Die entsprechenden Datenstrukturen sollten intern so dargestellt
werden, dass für Zugriffe kein Unterschied zwischen einer unveränderten und einer veränderten
Instanz besteht. Dies soll natürlich nur gelten, sofern der Unterschied für den Zugriff nicht re-
levant ist, wie beispielsweise bei der Schemaevolution veränderter Instanzen. Dies erleichtert die
Implementierung erheblich, da dieselben Algorithmen sowohl für unveränderte als auch veränder-
te Prozessinstanzen anwendbar bleiben. Auch die Partitionierung von Prozessdaten [10] ist für
die Unterstützung von Flexibilität sehr hilfreich. Auch dies muss weitgehend transparent realisiert
werden. Des weiteren sollten auch Anfragen von Kollektionen von Instanzen möglichst unverändert
und effizient auch mit instanzspezifischen Änderungen funktionieren.
Dieser Beitrag gliedert sich wie folgt: In Kapitel 2 stellen wir Änderungsoperationen auf Prozessen
und deren Anwendung im Rahmen von Schemaevolution, instanzspezifischer Änderungen sowie
die Anwendung einer Schemaevolution mit geänderten Instanzen. Kapitel 3 diskutiert verschiedene
Konzepte für die Realisierung von Prozessänderungen. Eines dieser Realisierungskonzepte wird in
Kapitel 4 in zwei Implementierungsvarianten in konkrete Datenstrukturen umgesetzt. Anschlie-
ßend werden diese beiden Implementierungsvarianten sowie die weiteren Realisierungskonzepte in
Kapitel 5 quantitativ verglichen. Hierzu stellen wir die entsprechende Testumgebung und den Ab-
lauf der Messungen vor, bevor wir die Messergebnisse ausführlich diskutieren und interpretieren.
Abschließend folgen in Kapitel 6 eine Zusammenfassung und ein Ausblick.
2 Grundlagen
Für die interne Repräsentation von Änderungen an Prozessvorlagen und -instanzen ist es wichtig,
wie entsprechende Prozessanpassungen generell durchgeführt werden und welche Auswirkungen
die Änderungen in Bezug auf spätere Zugriffe auf systeminterne Datenstrukturen haben, z. B.
Anfragen nach den aktuell laufenden Schritte eines Prozesses. In diesem Abschnitt stellen wir
zuerst einige generelle Aspekte von Änderungen vor, die für das weitere Verständnis des Aufsat-
3
unveränderteProzessvorlage diverseÄnderungen
aufderProzessvorlage
Änderungskontexte
derentsprechendenÄnderungen
Abbildung 3: Änderungskontexte beim Einfügen, Löschen und Verschieben von Knoten
zes wichtig sind. Anschließend gehen wir im Detail auf die vom ADEPT2-System unterstützen
Prozessänderungen ein. Zum einen sind dies Änderungen auf Prozessvorlagen und ggf. deren Pro-
pagation auf zugehörige Prozessinstanzen (Schemaevolution), zum anderen Änderungen einzelner
Prozessinstanzen (instanzspezifische Änderungen).
2.1 Änderungsoperationen
Um die korrekte Durchführbarkeit von Änderungen auf Prozessen zu gewährleisten (Instanz I10 in
Abb. 1), definiert das Änderungsrahmenwerk des ADEPT2-Systems eine umfassende theoretische
Grundlage [21, 19]. Hierzu gehört insbesondere eine wohldefinierte Menge an Änderungsopera-
tionen (z. B. Einfügen, Löschen oder Verschieben eines Knotens (Abb. 3) oder Einfügen eines
Verzweigungs-/Schleifenblocks). Diese Änderungen können verschieden komplex sein, bauen letzt-
lich aber alle auf einfachen Änderungsprimitiven auf. Letztere beschränken sich auf das Erzeugen,
Ändern und Löschen einzelner Knoten und Kanten des jeweiligen Prozessgraphen. Höherwerti-
ge Änderungsoperationen fassen mehrere Änderungsprimitive so zusammen, dass bei Anwendung
der Änderungsoperation auf einen Prozessgraphen dieser immer von einer gültigen Struktur in
eine andere gültige Struktur überführt wird. Dazu müssen Einschränkungen bezüglich der Pro-
zessgraphstruktur (z. B. Einhaltung von Blockstruktur, keine isolierten Knoten) eingehalten wer-
den. Darüber hinaus gibt es im Fall einer Prozessinstanz weitere Einschränkungen bezüglich des
Prozesszustands. Beispielsweise müssen alle Vorgänger eines laufenden Prozessschritts entweder
abgeschlossen oder „abgewählt“ worden sein, und alle Nachfolger müssen sich noch in ihrem In-
itialzustand befinden. Änderungsoperationen bei deren Durchführung dies nicht gewährleistet ist,
dürfen erst gar nicht angewandt werden. So ist etwa das Einfügen eines neuen Knotens vor ei-
nem bereits abgeschlossenen Schritt nicht zulässig. Wir sprechen in einem solchen Fall von der
Unverträglichkeit der Instanz mit den aus der Änderung resultierenden Prozessvorlage.
Mehrere Änderungsoperationen können in einer Änderungstransaktion zusammengefasst wer-
den. Dadurch können beispielsweise komplexe Änderungen atomar durchgeführt werden. Ein Bei-
spiel hierfür ist das Ersetzen eines Knotens durch einen anderen Knoten, was durch die beiden
Änderungsoperationen Einfügen und Löschen realisiert werden kann. Strukturell ist der resultie-
rende Prozess nach der Anwendung jeder einzelnen Änderungsoperation korrekt, die semantische
Konsistenz ist jedoch erst nach Abschluss der Änderungstransaktion hergestellt.
Änderungsoperationen betreffen immer einen bestimmen Bereich eines Prozessgraphen, den
sogenannten Änderungskontext. Dieser ist je nach Änderungsoperation unterschiedlich. So um-
fasst der Änderungskontext beim (seriellen) Einfügen eines Knotens die zwei Knoten zwischen
4
denen der neue Knoten eingefügt wird; beim Verschieben von Knoten umfasst der Änderungskon-
text die Kante, die die ursprüngliche Position des verschobenen Knotens „überspringt“, die zwei
Knoten zwischen denen der verschobene Knoten eingefügt wird sowie den verschobenen Knoten
selbst (Abb. 3). Der Änderungsbereich markiert damit die Stellen, an denen die Graphstruktur in
der internen Datenrepräsentation angepasst werden muss, um die entsprechenden Änderungen zu
realisieren.
Ebenso wie die Ausführung einer Prozessinstanz in einer Ausführungs- und Datenhistorie pro-
tokolliert wird (z. B. aus Gründen der Nachvollziehbarkeit) [10], werden alle Änderungen einer
Prozessvorlage oder -instanz in einer Änderungshistorie protokolliert [26]. Diese beinhaltet Infor-
mationen über Änderungstransaktionen, angewandte Änderungsprimitive sowie Änderungskon-
texte. Ähnlich wie Knotenmarkierungen bei Prozessinstanzen eine konsolidierte Sicht auf die Aus-
führungshistorie ermöglichen, bietet die interne Repräsentation von Änderungen eine konsolidierte
Sicht auf die Änderungshistorie.
2.2 Schemaevolution und instanzspezifische Änderungen
Im Prozess-Management-System ADEPT2 kann eine vollständige Menge an Änderungsoperatio-
nen sowohl auf Prozessvorlagen als auch auf Prozessinstanzen angewandt werden. Im ersten Fall
enstehen Prozessvorlagen, die eine neue Version des entsprechenden Prozesstyps bilden und die
vorherigen Prozessvorlagen ablösen. Die Änderungen, die auf der ursprünglichen Prozessvorlage
vorgenommen worden sind, können im Rahmen einer Schemaevolution auch auf bereits laufende
Prozessinstanzen der ursprünglichen Vorlage propagiert werden [24]. Dabei werden diese Pro-
zessinstanzen noch während ihrer Ausführung auf die neue Prozessvorlage migriert, sofern dies
gewünscht und möglich ist. Konkret sind mehrere Randbedingungen zu beachten. Beispielswei-
se ist es zwecks Gewährleistung einer korrekten Prozessausführung nicht gestattet, Änderungen
auf eine laufende Prozessinstanz zu propagieren, wenn die betroffene Instanz den entsprechenden
Änderungskontext bereits durchlaufen hat. Wäre dies erlaubt, würde durch die Schemaevolution
nachträglich die Vergangenheit der Prozessausführung verändert bzw. „manipuliert“ (vgl. Instanz
2 in Abb. 4).
Im Fall von instanzspezifischen Änderungen gelten die durchgeführten Änderungen nur für
eine einzelne laufende Prozessinstanz, während bei einer Schemaevolution bzw. Instanzmigration
die Änderungen potentiell für alle Instanzen einer Prozessvorlage gelten. Dementsprechend muss
in der internen Repräsentation von Instanzdaten gewährleistet werden, dass die entsprechenden
Änderungen nur für die betroffene Prozessinstanz gelten. In diesem Fall sind die der Instanz
zugrundeliegenden Prozessstrukturen Änderungen unterworfen und entsprechen damit nicht mehr
den durch die entsprechende Prozessvorlage bereitgestellten Prozessstrukturen.
Wie bei der Schemaevolution ist es auch bei instanzspezifischen Änderungen nicht zulässig,
die Vergangenheit zu manipulieren, d. h. hier gelten weitgehend diesselben Korrektheitskriterien
für die Anwendung von Änderungsoperationen. Allerdings ist die Reihenfolge für die Überprüfung
sowie die Durchführung der Änderungen etwas anders. Wir werden dies nun im Detail vorstellen
(vgl. Abb. 4)
Ablauf einer Schemaevolution
Der erste Schritt einer Schemaevolution ist die Erzeugung einer neuen Prozessvorlage V′basie-
rend auf einer bereits existierenden Prozessvorlage V(im Sinne von Klonen). Die neu erzeugte
Prozessvorlage wird anschließend einer Menge von Änderungen ∆Funterworfen. Dabei wird vor
Anwendung einer jeden Änderungsoperation strukturelle Verträglichkeit der Instanz mit der resul-
tierenden (Zwischen-)Vorlage geprüft (z. B. Einhaltung der Blockstruktur) und ggf. die Struktur
der Prozessvorlage entsprechend geändert.
Sind alle gewünschten Änderungen der Prozessvorlage erfolgt und auf V′angewandt worden,
können die Änderungen auf laufende Instanzen von Vpropagiert werden. Dazu wird zuerst über-
prüft, ob ∆Fbezüglich des aktuellen Instanzzustands verträglich ist, d. h. ob der Änderungsbereich
von ∆Fbereits abgeschlossene Teile der Instanz betrifft. Ist dies der Fall, kann die Instanz nicht
5
Instanz 1 basierend auf V’:
Instanzebene
üpüüü~
......
3. F nicht verträglich mit Zustand von Instanz 2, Instanz zu weit fortgeschritten, daD
SKIPPEDACTIVATEDACTIVATEDNOTnNSExnNxninsert,,_)(:'|
Typebene
Vorlage V’ABCDEHGF
Vorlagenänderung:F = insertNode(G, B, D),insertNode(H, E, F)D
1. F strukturell verträglich mit V2. Erzeugung V' = V + FDDüpüüInstanz 1 basierend auf V:Instanz 2 basierend auf V:ABCDEFVorlage Vüüpüüüüpü3. F verträglich mit Zustand von Instanz 14. Migration und ZustandsanpassungDüup
Instanzänderung:G = insertNode(G, A, C)D
1. G strukturell verträglich mit Instanz n2. G verträglich mit Zustand von Instanz nDD3. Erzeugung instanzspezifische Vorlage V* = V + GD4. ZustandsanpassunguüpInstanz n basierend auf V* = V + G:DInstanz n basierend auf V:üup
Abbildung 4: Vorlagen- und Instanzänderung (logische Sicht)
auf die neue Vorlage V′migriert werden und muss auf der alten Prozessvorlage Vverbleiben, d. h.
auf ihrer Grundlage zu Ende geführt werden. Ist ∆Fdagegen bezüglich des Zustands verträglich,
wird die Instanz auf die neue Vorlage migriert, d. h. sie erfährt logisch diesselben strukturel-
len Änderungen ∆Fwie ihre ursprüngliche Vorlage V. Anschließend müssen an der Instanz ggf.
noch Zustandsanpassungen vorgenommen werden, etwa wenn durch ∆Fein neuer Knoten vor
einem aktuell ausführbaren, aber noch nicht ausgeführten Knoten eingefügt wird (vgl. Instanz 1
in Abb. 4). In diesem Fall wird der neue Knoten als ausführbar markiert und dessen Nachfolger
auf den Initialzustand zurückgesetzt [18, 17].
Ablauf einer instanzspezifischen Änderung
Bei Anwendung einer Änderungstransaktion ∆Gauf einer Prozessinstanz finden diesselben Über-
prüfungen statt, allerdings in anderer Reihenfolge. Da eine Instanz einen Zustand besitzt, wird
sofort nach Feststellung der strukturellen Verträglichkeit auch die Verträglichkeit bezüglich des
Zustands geprüft. Erst anschließend werden strukturelle Änderungen und ggf. eine Zustandsan-
passung durchgeführt (vgl. Instanz n in Abb. 4). Die strukturellen Änderungen führen dann zu
einer Vorlage V∗, die nur für die veränderte Instanz gilt. Daneben werden alle Überprüfungen
bei instanzspezifischen Änderungen für jede Änderungsoperation sofort durchlaufen. Dies erlaubt,
bei jeder Änderungsoperation sofort sowohl auf Struktur- als auch auf Zustandsverträglichkeit zu
überprüfen und ggf. die Änderungsoperation sofort zurückzuweisen. Bei einer Schemaevolution
dagegen wird jede Überprüfungsphase jeweils für eine Menge von Änderungsoperationen (also die
entsprechende Änderungstransaktion) ausgeführt, bevor die nächste Überprüfungsphase stattfin-
det. Dies liegt daran, dass die Änderungen auf einer Vorlage eingebracht werden und dort nur
strukturelle Verträglichkeit geprüft werden kann; Zustandsverträglichkeit lässt sich erst bei der
Propagation auf betroffene Instanzen testen.
Kombination von Schemaevolution und instanzspezifischen Änderungen
Lässt man sowohl Schemaevolution als auch instanzspezifische Änderungen zu, wie dies im
ADEPT2-System der Fall ist, können auch bereits veränderte Prozessinstanzen von einer Sche-
6
Realisierung
instanzspezifischerÄnderungen
individuelle
Instanzgraphen(ÄR-1) Deltas
strukturelle
Instanzdeltas(ÄR-3)
operationale
Instanzdeltas(ÄR-2)
gekapselte
Vorlagen(ÄR-3-1) Substitutions-
vorlagen(ÄR-3-2)
Abbildung 5: Klassifikation der Realisierungskonzepte instanzspezifischer Änderungen
maevolution betroffen sein [23, 20, 25]. In diesem Fall müssen die Änderungen auf der Vorlage
sowie die instanzspezifischen Änderungen miteinander verglichen werden. So ist es beispielsweise
denkbar, dass die instanzspezifischen Änderungen genau den Änderungen der Schemaevolution
entsprechen, weil bei der Instanz diese Änderungen bereits vorweggenommen wurden. Änderun-
gen auf Prozessvorlagen und -instanzen können auch echte Teilmengen voneinander sein oder sich
überlappen [23]. In allen Fällen ist es das Ziel, die Instanz auf die neue Prozessvorlage zu migrieren
und die instanzspezifischen Änderungen entsprechend anzupassen. Durch diese Anpassung wird
eine neue Menge an instanzspezifischen Änderungen erzeugt, die nicht mehr auf der ursprünglichen
Prozessvorlage sondern auf der geänderten Prozessvorlage beruhen.
Für die interne Repräsentation von Änderungen ist somit neben der Unterscheidung zwischen
Änderungen an Prozessvorlagen sowie Änderungen an einzelnen Prozessinstanzen auch die Ver-
gleichbarkeit beider Änderungsarten wichtig. Andernfalls ist es nicht möglich, diese in Kombination
miteinander durch ein PMS zu unterstützen.
3 Realisierungskonzepte für instanzspezifische Änderungen
In Bezug auf die interne Repräsentation der einer bestimmten Instanz zugrundeliegenden Pro-
zessstruktur, unterscheiden wir zwischen Vorlagenkopie (Variante VG-1) und Vorlagenreferenz
(Variante VG-2) [10]. Bei der Vorlagenkopie werden intern für jede Prozessinstanz eigene Daten-
strukturen für die Abbildung der jeweiligen Prozessstruktur angelegt, während diese bei Vorla-
genreferenzen nur einmal pro Vorlage existieren und von den entsprechenden Prozessinstanzen
ledigilch referenziert werden. Offensichtlich benötigen Vorlagenreferenzen wesentlich weniger Spei-
cher und sind deshalb für die Realisierung der Datenstrukturen für Prozessvorlagen und -instanzen
vorzuziehen. Mit dieser Repräsentationsform lassen sich allerdings instanzspezifische Änderungen
nicht direkt realisieren. Diese Art von Änderungen müssen auf einer Prozessvorlage durchgeführt
werden, die nur für die jeweils abzuändernde Prozessinstanz gilt (instanzspezifische Prozessvorla-
ge). In den folgenden Abschnitten stellen wir alternative Ansätze dafür vor, wie auf Grundlage von
Vorlagenreferenzen und sinnvollen Erweiterungen instanzspezifische Änderungen realisiert werden
können.
Die einfachste Realisierungsvariante für die Repräsentation instanzspezifischer Änderungen ist
die Verwendung individueller Instanzgraphen (Variante ÄR-1). Diese entsprechen einer normalen
Vorlagenkopie (Variante VG-1), allerdings besitzt eine Instanz nur dann einen individuellen, von
einer Vorlage abgeleiteten Instanzgraph (und keine einfache Referenz wie bei Variante VG-2),
wenn die Prozessinstanz Änderungen unterworfen worden ist. Der individuelle Instanzgraph selbst
repräsentiert eine vollständige Prozessvorlage wie bei Variante VG-1.
Alternativ lassen sich instanzspezifische Änderungen auch mit einer Vorlagenreferenz (Variante
VG-1) realisieren, indem neben der Referenz die Unterschiede (Deltas) zwischen der durch die Än-
derungen resultierenden instanzspezifischen Vorlage und der ursprünglichen Vorlage gespeichert
7
werden. Dies führt dann nicht zu einer vollständigen (geänderten) Prozessvorlage und somit nicht
zu einem explizit gespeicherten individuellen Instanzgraphen. Werden die zusätzlich zur Vorlagen-
referenz existierenden Änderungen geeignet repräsentiert, kann die resultierende instanzspezifische
Vorlage bei Bedarf erzeugt werden.
Die Realisierung der Deltas wiederum kann auf zwei Arten erfolgen: Die instanzspezifisch an-
gewandten Änderungsoperationen können direkt als Operationen (z. B. als Änderungshistorie)
repräsentiert werden (Variante ÄR-2, sog. operationale Instanzdeltas), oder es werden die aus den
Änderungsoperationen resultierenden Graphstrukturen gespeichert (Variante ÄR-3, sog. struktu-
relle Instanzdeltas). Die geänderten Graphstrukturen werden intern durch Mengen von hinzuge-
fügten, geänderten (hierzu zählen auch verschobene Knoten) und gelöschten Knoten und Kanten
repräsentiert. Auch hier kann man wieder zwei Realisierungsarten unterscheiden: Gekapselte Vor-
lagen (Variante ÄR-3-1), die implizit und transparent zwischen geänderten Prozessstrukturen und
der ursprünglichen Vorlage unterscheiden, sowie Substitutionsvorlagen (Variante ÄR-3-2), bei de-
nen explizit zwischen geänderten Graphstrukturen und ursprünglicher Vorlage unterschieden wird
(Abb. 5).
In diesem Kapitel werden die Varianten ÄR-1, ÄR-2 und ÄR-3 im Detail vorgestellt und mitein-
ander verglichen. Wie erwähnt, entsprechen die Anforderungen an diese Varianten im Kern wieder
den Anforderungen an Repräsentationen unveränderter Instanzen (vgl. [10]): niedriger Speicher-
bedarf, horizontale und vertikale Partitionierbarkeit, weitgehende Transparenz für Algorithmen,
instanzübergreifende Anfragen (Sekundärspeicher) und Unterstützung von Schemaevolution [20].
Die Varianten ÄR-3-1 und ÄR-3-2 für die Realisierung von strukturellen Instanzdeltas werden in
Kapitel 4 ausführlich diskutiert.
3.1 Variante ÄR-1: Individuelle Instanzgraphen
Eine naheliegende Lösung zur Realisierung von Instanzänderungen bieten individuelle Instanzgra-
phen. Dabei wird für die Durchführung von Änderungen eine vollständige Kopie der zugrundelie-
genden Vorlage angelegt (vgl. [10], Variante VG-1), auf der dann die entsprechenden Änderungen
auch durchgeführt werden. Die Instanz referenziert anschließend das neu erstellte, instanzspe-
zifische Vorlagenobjekt (Abb. 6). Im Vergleich zu Vorlagenkopien (bei unveränderten Instanzen
[10]) wird hier jedoch nur im Fall von instanzspezifischen Änderungen eine Vorlagenkopie ange-
legt, nicht dagegen für unveränderte Instanzen. Letztere referenzieren jeweils die ursprüngliche
Prozessvorlage.
Zugriffe auf die internen Datenstrukturen erfolgen bei unveränderten als auch bei veränderten
Instanzen gleich, d. h. in beiden Fällen wird bei Zugriffen auf strukturelle Informationen die
Referenz auf die für die Instanz gültige Vorlage aufgelöst und die Anfrage entsprechend auf der
Vorlage verarbeitet. Hierdurch ist eine vollständige Transparenz von Instanzänderungen gegeben.
Individuelle Instanzgraphen werden intern wie vollwertige Vorlagen verwaltet. Das Anlegen
eines individuellen Instanzgraphen ist weitgehend identisch mit dem Ändern einer Prozessvorlage
vor einer Schemaevolution, d. h. die Vorlage wird geklont und anschließend der Klon direkt struk-
turell geändert. Im Gegensatz zu einer Prozessvorlage kann ein individuelle Instanzgraph jedoch
nicht (neu) instanziert werden, und es gibt exakt eine darauf laufende Instanz.
Problematisch an diesem Konzept ist die Verwendung der gleichen Konstrukte, nämlich Vorla-
genobjekte, sowohl für Instanz- als auch für Vorlagenänderungen. Ein Zusammentreffen beider Än-
derungsarten, also die Änderung der ursprünglichen Vorlage einer individuell geänderten Instanz,
lässt sich dabei nur sehr schwer realisieren. Beim Umhängen (verträglicher) laufender Instanzen
auf eine neue Vorlage1, werden geänderte Instanzen nicht berücksichtigt, da sie nicht mehr die
ursprüngliche Vorlage sondern nunmehr einen individuellen Instanzgraphen referenzieren. Solche
Instanzen können nur migriert werden, indem die Vorlagenänderungen der Schemaevolution auch
auf dem individuellen Instanzgraphen durchgeführt werden, oder indem dieser komplett verworfen
und, basierend auf einer Kopie der neuen Vorlage, entsprechend neu aufgebaut wird.
1Gemeint ist die Migration von Instanzen von einer alten Prozessvorlage auf eine neue Prozessvorlage bei Sche-
maevolution [24].
8
A
B
C
D E F
W,V2.0
p
üü üü ü
I6 p
üü üü
I4
I3 u
I1 u
üü ü
I5 üü ü p
I2 u
üp
ADB E F
W,V2.0*
A
B
C
D E F
W,V2.0*
G
veränderte
Prozessinstanzen unveränderte
Prozessinstanzen
Abbildung 6: Änderungen repräsentiert durch individuelle Instanzgraphen (ÄR-1)
Instanzebene
Typebene
VorlageV’
A
B
C
D E H
G
F
Vorlagenänderung:
F=insertNode(G, B, D),
insertNode(H, E, F)
D
A
B
C
D E F
VorlageV
Instanz6basierendaufV :*=V+ GD
ü
u
p
Instanzänderung:
G=deleteNode(E)D
InstanznbasierendaufV’*=V+ F+ G:D D
ü
p
u
Instanzänderung:
G=deleteNode(E)D
Vorlagenänderung:
F=insertNode(G, B, D),
insertNode(H, D, F)
D
Abbildung 7: Schemaevolution mit ind. Instanzgraphen und angepasstem Änderungskontext
Beide Varianten zur Durchführung der Schemaevolution bei vorhandenen individuellen In-
stanzgraphen sind sehr aufwendig, da in jedem Fall Änderungen wiederholt werden müssen: dies
betrifft entweder die Änderungen zum Zeitpunkt der instanzspezifischen Änderung oder die Vor-
lagenänderungen (Abb. 7). Dies ist besonders kritisch, da für die korrekte Durchführung der Mi-
gration einer geänderten Instanz in jedem Fall die Vorlagen- und Instanzänderungen zuvor noch
auf Überlappungen und komplementäre Änderungen verglichen werden müssen. Dazu wird ei-
ne entsprechende Änderungshistorie benötigt, da die zu wiederholenden Änderungsoperationen
entsprechend angepasst werden müssen: Beispielsweise kann ein Knoten auf Instanzebene gelöscht
sein, hinter dem auf Vorlagenebene eine Änderung vorgenommen wird. Damit existiert der Kontext
der entsprechenden Änderung auf Vorlagenebene nicht mehr auf Instanzebene. Dies erfordert die
Neuermittlung des Kontexts für die Änderungsoperation auf Instanzebene. Beim Zusammenfüh-
ren der Änderungen auf Vorlagen- und Instanzebene können Änderungsoperationen auch komplett
entfallen, etwa wenn auf Instanzebene vorhandene Änderungen auch auf der Vorlage durchgeführt
worden sind.
Beispielsweise wurde in Instanz 6 in Abb. 7 der Knoten E gelöscht. Wird auf Vorlagenebene
ein Knoten H zwischen Knoten E und Knoten F eingefügt, so muss bei Propagation dieser Vor-
lagenänderungen auf Instanz n der Änderungskontext angepasst werden. Aus dem Einfügen von
Knoten H zwischen den Knoten E und F wird ein Einfügen des Knotens H zwischen Knoten D
(dem Vorgängerknoten von E) und Knoten F.
9
A
B
C
D E F
W,V2.0
p
üü üü ü
I6 p
üü üü
I4
I3 u
I1 u
üü ü
I5 üü ü p
I2 u
üpInsert(G,D,E)
+
+
Delete(C)
veränderte
Prozessinstanzen
unveränderte
Prozessinstanzen
Abbildung 8: Änderungen mittels operationaler Instanzdeltas (ÄR-2)
Insgesamt sind individuelle Instanzgraphen sehr einfach in der Realisierung und bieten trotz-
dem eine vollständige Transparenz von Instanzänderungen. Es wird jedoch relativ viel Speicher-
platz benötigt, da die Erstellung vollständiger Vorlagenkopien auch Redundanzen bezüglich der
Vorlageninformationen mit sich bringt. Noch schwerer wiegt jedoch der sehr große Laufzeitaufwand
für die Durchführung einer Schemaevolution für geänderte Instanzen, da beide Änderungsarten
intern gleich realisiert werden und kein direkter Vergleich der Änderungen möglich ist.
3.2 Variante ÄR-2: Operationale Instanzdeltas
Operationale Instanzdeltas unterscheiden sich in zwei Aspekten von individuellen Instanzgraphen:
Einerseits werden nur Unterschiede gegenüber der ursprünglichen Vorlage verwaltet (Deltas). Da-
durch kann auf die ursprüngliche Vorlage nicht verzichtet werden, es bleibt aber der Bezug zu ihr
bestehen. Andererseits werden Instanzänderungen nicht als Graphstrukturen, sondern als Ände-
rungsoperationen gespeichert. Dies entspricht (einem Teil) der Änderungshistorie (Abb. 8).
Gegenüber individuellen Instanzgraphen ist die Durchführung von Instanzänderungen mit ope-
rationalen Instanzdeltas sehr effizient: Neben der für zahlreiche Funktionen benötigten Änderungs-
historie müssen keine zusätzlichen Datenstrukturen erzeugt und verwaltet werden. Dafür müssen
vor Zugriffen auf geänderte Instanzen erst die entsprechenden Änderungen durchgeführt werden.
Dies kann beispielsweise auf einer temporären Kopie der ursprünglichen Vorlage erfolgen, wodurch
Auswirkungen auf andere, unveränderte Instanzen verhindert werden. Dies ist mit Variante ÄR-
1 vergleichbar, wobei der individuelle Instanzgraph nur bei Bedarf erzeugt wird, was insgesamt
jedoch noch immer sehr aufwendig sein kann (Abb. 9).
Große Vorteile besitzt die Realisierung operationaler Instanzdeltas im Zusammenhang mit der
Realisierung von Schemaevolution. Da die Instanzänderungen direkt in Form von Operationen
vorliegen, kann der Vergleich mit den entsprechenden Vorlagenänderungen sehr effizient erfolgen.
Dabei können bei Bedarf relativ einfach die Kontexte von Änderungsoperationen in den opera-
tionalen Instanzdeltas geändert oder ganze Änderungsoperationen entfernt werden. Anschließend
können die geänderten Instanzen ohne zusätzliche strukturellen Anpassungen auf die neue Vorlage
umgehängt werden; die Instanzdeltas wurden bereits bei dem Vergleich entsprechend angepasst.
Während operationale Instanzdeltas sehr effizient Instanz- und Vorlagenänderungen ermöglichen,
gestalten sich Zugriffe auf die zugrundeliegenden Prozessstrukturen problematisch. Dabei muss
jedesmal die resultierende instanzspezifische Vorlage erzeugt werden, um benötigte Informationen
(z. B. Vorgänger/Nachfolger eines Knotens) ermitteln zu können, da diese Information nicht di-
rekt aus der Änderungshistorie ermittelt werden kann bzw. nur mit einem sehr hohen Aufwand
(Abb. 9). Ohne diesen gravierenden Nachteil wären operationale Instanzdeltas sehr gut für die
Realisierung instanzspezifischer Änderungen geeignet. Sie benötigen zudem keinerlei zusätzlichen
Speicherplatz, da eine Änderungshistorie zu Dokumentationszwecken in jedem Fall erforderlich ist.
10
A
B
C
D E F u
ü ü ü Insert(G,D,E)
ü ü ü ü p
+
+
A
B
C
D E F
G
1. temporäreErzeugung
derinstanzspez.Vorlage
2. Nachfolgerbestimmung
3. Zustandsanpassung
Abbildung 9: Weiterschalten mit Rekonstruktion der instanzspezifischen Vorlage
3.3 Variante ÄR-3: Strukturelle Instanzdeltas
Strukturelle Instanzdeltas bewegen sich zwischen individuellen Instanzgraphen und operationalen
Instanzdeltas. Dabei werden wie bei operationalen Instanzdeltas nur Instanzänderungen und keine
vollständigen Vorlagen verwaltet. Änderungen liegen jedoch nicht operational sondern wie bei
invidiuellen Instanzgraphen als realisierte Graphstrukturen vor. Dazu wird bei Instanzänderungen
der von der Änderung betroffene Bereich (Änderungskontext) der ursprünglichen Vorlage kopiert
und anschließend geändert. Bei Zugriffen substituiert diese Kopie (das Subsitutionsobjekt) den
entsprechenden Bereich der ursprünglichen Vorlage.
In Abb. 10 ist bei Instanz I5 der Knoten C gelöscht worden. Da hierbei eine Verzweigung
aufgelöst worden, müssen durch das Löschen der Knotentyp der Knoten A und D geändert wer-
den, wodurch der Änderungskontext die Knoten A und C sowie durch Wegfall der Parallelität
auch Knoten B umfasst. Dieser Änderungskontext wurde entsprechend der Änderungsoperation
manipuliert, d. h. Knoten C wurde gelöscht, und der Kontext bildet nun das Substitutionsobjekt.
Durch die Überlagerung des Substitutionsobjekts auf die entsprechenden Knoten der ursprüngli-
chen Vorlage entsteht die für I5 gültige instanzspezifische Vorlage.
A
B
C
D E F
W,V2.0
p
üü üü ü
I6 p
üü üü
I4
I3 u
I1 u
üü ü
I5 üü ü p
I2 u
üp
ADB
D E
G
veränderte
Prozessinstanzen unveränderte
Prozessinstanzen
Abbildung 10: Änderungen mittels strukturellen Instanzdeltas (ÄR-3)
Damit vereinen strukturelle Instanzdeltas die Vorteile individueller Instanzgraphen und opera-
tionaler Instanzdeltas. Einerseits kann die instanzspezifische Vorlage bei Bedarf schnell erzeugt
werden und ermöglicht anschließend direkte Zugriffe auf die Graphstrukturen der instanzspezifi-
schen Vorlage. Andererseits ist der Speicherbedarf sehr gering, da gegenüber der ursprünglichen
Vorlage keine redundanten Informationen verwaltet werden.
Konzeptionell sind zwei Arten der Substitution möglich: einfache und hierarchische (also mehr-
fache) Substitution (Abb. 11). Bei der einfachen Substitution existiert für eine geänderte Instanz
jeweils nur ein Substitutionsobjekt, auch wenn die entsprechende Instanz mehrmals geändert wor-
11
den ist. Dagegen führt bei hierarchischer Substitution jede Änderungstransaktion zu einem eigenen
Substitutionsobjekt, das die vorherigen überlagert. In Abb. 11 wurde Knoten C gelöscht und ein
Knoten G zwischen Knoten D und E hinzugefügt. Links sieht man die resultierende einfache Sub-
stitution, rechts die hierarchische Substitution. Die resultierende instanzspezifische Vorlage ergibt
sich jeweils aus der Überlagerung aller Substitutionsobjekte in der Reihenfolge ihrer Erzeugung.
Hierarchische Subsitution hat den Vorteil, dass die Substitutionsobjekte zum Zeitpunkt der
Änderung sehr schnell erzeugt werden können. Dabei ist irrelevant, ob bereits Substitutionsobjekte
exisitieren oder nicht. Eine Änderung beruht immer auf der zum Änderungszeitpunkt gültigen
(logischen) Vorlage einer Instanz. Dies führt jedoch potentiell zu einem höheren Speicherbedarf,
da ggf. redundante Informationen verwaltet werden. Dies ist beispielsweise der Fall, wenn durch
komplementäre Änderungen vorherige Änderungen aufgehoben werden oder ein Änderungskontext
für mehrere Substitutionsobjekte gilt (Knoten D in Abb. 11). In so einem Fall ist ein konsolidiertes
Substitutionsobjekt speichereffizienter.
A
B
C
D E F
Vorlage
AB
einfachesSubstitut
D E
G
A
B
C
D E F
D E
G
2. Substitut
ADB
1. Substitut
Vorlage
Abbildung 11: Einfache und hierarchische Substitution bei strukturellen Instanzdeltas
Genau dies ist die Funktionsweise der einfachen Substitution. Hierbei wird bei einer Änderung
unterschieden, ob sie sich auf eine bereits vorhandene Änderung bezieht und dann zu einer Modi-
fikation des Substitutionsobjekts führt, oder ob eine Änderung einen unveränderten Bereich der
ursprünglichen Vorlage betrifft und das Substitutionsobjekt entsprechend erweitert wird. Damit
ist die Durchführung von Änderungen aufwendiger als bei hierarchischer Substitution, es wird
jedoch weniger Speicher benötigt und der Zugriff auf die instanzspezifische Vorlage ist wesentlich
effizienter, da nicht mehrere Subsitutionsobjekte unterschieden und überlagert werden müssen.
Insgesamt ist die einfache Substitution deshalb vorzuziehen.
3.4 Qualitativer Vergleich der Realisierungskonzepte
Tabelle 1 zeigt einen qualitativen Vergleich der vorgestellten Realisierungskonzepte bezüglich ver-
schiedener Anforderungen. Am kritischsten sind der Primärspeicherbedarf sowie die Laufzeit der
verschiedenen Realisierungen. Beide Aspekte werden wir in Kapitel 5 noch detailliert anhand von
Messungen untersuchen.
Der Primärspeicherbedarf bei Variante ÄR-1 ist insgesamt sehr hoch. Insbesondere bei geringfü-
gigen Änderungen, etwa beim Löschen eines einzelnen Knotens, wird viel redundante Information
im Vergleich zur ursprünglichen Prozessvorlage gespeichert. Diesen Nachteil vermeiden operatio-
nale und strukturelle Instanzdeltas, d. h. hier wird signifikant weniger Speicherplatz benötigt.
Weitgehend umgekehrt verhält es sich bezüglich der Laufzeit. Variante ÄR-2 ist ineffizient, da die
Änderungen nicht strukturell vorliegen und erst rekonstruiert werden müssen. Der Aufwand hängt
dabei von der Art und der Komplexität der Änderungen ab. Einfache Änderungen, wie das Lö-
schen eines Knotens, sind noch relativ effizient handhabbar. Jedoch wird das Laufzeitverhalten bei
mehreren komplexen Änderungen schnell problematisch. Wesentlich besser verhält sich dagegeben
12
Tabelle 1: Bewertung der Realisierungskonzepte instanzspezifischer Änderungen
ÄR-1
Individuelle
Instanzgraphen
ÄR-2
Operationale
Instanzdeltas
ÄR-3
Strukturelle
Instanzdeltas
Primärspeicherbedarf - + + Unterstützung:
Laufzeit ++ -- + ++: sehr gut
Transparenz ++ - O +: gut
Partitionierung + - O O: neutral
Schemaevolution - ++ O -: schlecht
Anfragen an Kollektionen von Instanzen ++ - + --: sehr schlecht
Variante ÄR-3, hier liegen die Änderungen schon in Graphstrukturen vor. Es muss bei Zugrif-
fen lediglich noch eine Substitution vorgenommen werden. Dagegen unterscheidet sich der Zugriff
auf instanzspezifische Vorlagen bei Variante ÄR-1 nicht vom Zugriff auf Vorlagen unveränderter
Prozessinstanzen. Dies ist bezüglich der Laufzeit am effizientesten.
Auch die weiteren untersuchten Anforderungen werden von den Realisierungskonzepten sehr
unterschiedlich unterstützt. Bei Variante ÄR-1 sind Änderungen vollständig transparent und des-
halb mit der Realisierung unveränderter Instanzvorlagen vergleichbar. Sie bietet daher bezüglich
Transparenz, Partitionierung und Anfragen an Kollektionen von Instanzen gute bis sehr gute Un-
terstützung (vgl. [10]). Dagegen ist eine Partitionierung von Variante ÄR-2 schwierig, da aus der
Operation selbst nicht sofort hervorgeht, welche Bereiche von ihrer Anwendung betroffen sind. Bei
Variante ÄR-3 ist der Änderungskontext dagegen bekannt, die Substitutionsobjekte bilden jedoch
nicht unbedingt einen zusammenhängenden Prozessgraphen, weshalb sich die Partitionierung et-
was aufwendiger als bei unveränderten Vorlagen gestaltet. Ähnlich verhält es sich bei Anfragen an
Kollektionen von Instanzen. Diese sind bei Variante ÄR-2 sehr schwierig in der Umsetzung, da die
Auswirkungen einzelner Operationen nicht absehbar sind. Bei Variante ÄR-3 muss für Anfragen
die Substitution nur vorgenommen werden, wenn sich die Anfrage auf einen geänderten Bereich
einer Vorlage bezieht.
Große Auswirkungen hat die Wahl des Realisierungskonzepts für instanzspezifische Änderun-
gen auf die Durchführung einer Schemaevolution. Hierfür ist Variante ÄR-2 am besten geeignet,
da der Vergleich der Vorlagen- und Instanzänderungen direkt erfolgen kann. Wird anschließend die
Migration durchgeführt, müssen die instanzspezifischen Änderungen (ebenso wie die entsprechen-
de Änderungshistorie) allerdings angepasst werden, da sie dann relativ zur neuen Prozessvorlage
benötigt werden. Da Variante ÄR-2 direkt über die Änderungshistorie realisiert ist, müssen neben
der Änderungshistorie keine weiteren Datenstrukturen für die Repräsentation der instanzspezifi-
schen Änderungen angepasst werden. Dagegen sind sowohl bei Variante ÄR-1 als auch bei Variante
ÄR-3 zusätzlich zur Manipulation der Historie strukturelle Anpassungen nötig. Diese gestalten sich
bei strukturellen Deltas (ÄR-3) jedoch einfacher, da die enstprechenden Datenstrukturen direkt
die Unterschiede zwischen der ursprünglichen Vorlage und der instanzspezifischen Vorlage reprä-
sentieren, während bei Variante ÄR-1 eine geänderte Instanz unabhängig von der ursprünglichen
Vorlage ist. Durch diese Unabhängigkeit können die Unterschiede nur durch einen Vergleich der
vollständigen Objekte abgeleitet werden.
Im folgenden betrachten wir vor allem Variante ÄR-3 (strukturelle Instanzdeltas) näher, da
diese qualitativ einen guten Kompromiss darstellt. Insbesondere der Primärspeicherbedarf und die
relativ geringe Laufzeit überzeugen.
4 Implementierungsvarianten
Nachdem wir im vorherigen Kapitel das Realisierungskonzept der strukturellen Instanzdeltas als
gute Lösung für die Repräsentation instanzspezifischer Änderungen identifiziert haben, untersu-
chen und vergleichen wir in diesem Kapitel verschiedene Implementierungsvarianten hierzu. Kon-
kret sind drei Möglichkeiten denkbar (vgl. Abb. 5, Abb. 12):
13
•Temporäre Realisierung: Vor einem Zugriff wird die vollständige logische Vorlage physisch
realisiert, wodurch die Zugriffe (z. B. beim Weiterschalten im Prozess) wie bei unveränderten
Instanzen funktionieren
•Substitutionsvorlagen: Hierbei wird vor jedem Zugriff auf einen Knoten oder eine Kante
überprüft, ob das entsprechende Element ein Bestandteil der strukturellen Instanzdeltas
ist oder nicht. Dem entsprechend findet der Zugriff dann auf den Instanzdeltas (eben den
Substitutionsvorlagen) oder auf der ursprünglichen Vorlage statt.
•Gekapselte Vorlagen: Jeder Zugriff auf einen Knoten oder eine Kante wird sowohl auf der
ursprünglichen als auch auf den strukturellen Instanzdeltas durchgeführt. Die Vereinigung
beider Ergebnisse bildet anschließend das eigentliche Resultat des Zugriffs.
instanzspez.
Typebene
TemporäreRealisierung
Typebene
A
B
C
D E F
VorlageV
strukt. Instanzdeltas
G=insertNode(G, D, E)D
D E
G
Instanzebene
p
ü
I6 u
A
B
C
D E
GF
Substitutionsvorlage
D E
G
Überlagerung,
ggf.Weiterleitungder Anfrage
Vereinigung
derErgebnisse
GekapselteVorlage
Abbildung 12: Ermittlung der Prozessstruktur bei den Implementierungsvarianten
Da bei Zugriffen nicht immer die gesamte Vorlage benötigt wird, sondern oftmals nur einzelne Teile
des Prozessgraphen, ist die temporäre Realisierung der vollständigen Vorlage unnötig aufwendig,
sowohl bezüglich Speicherbedarf als auch hinsichtlich der Laufzeit für die Rekonstruktion. Im
folgenden werden wir deshalb nur Substitutionsvorlagen und gekapselte Vorlagen weiter betrachten
und ihre Funktionsweise anhand repräsentativer Beispiele verdeutlichen. Abschließend folgt ein
qualitativer Vergleich der Implementierungsvarianten. Ein quantitativer Vergleich schließt sich in
Kapitel 5.
4.1 Variante ÄR-3-1: Substitutionsvorlagen
Implementierungsvariante ÄR-3-1 (Substitutionsvorlagen) ist dadurch gekennzeichnet, dass eine
geänderte Instanz zwei zugrundeliegende Vorlagen besitzt und beide explizit referenziert: die ur-
sprüngliche Vorlage sowie das Substitutionsobjekt (Teilvorlage) – bei einfacher Substitution exi-
stiert höchstens ein Subsitutitonsobjekt, bei hierarchischer Substitution wären es mehrere (vgl.
Abb. 11). Zusätzlich ist bei der Instanz hinterlegt, welches Objekt für welchen Bereich bzw. wel-
che Knoten gültig ist (Abb. 13). Da bei unveränderten Instanzen nur eine gültige Vorlage existiert,
kann hier auf diese Information verzichtet werden.
Um die Funktionsweise von Substitutionsvorlagen zu verdeutlichen, werden wir im folgenden
die konkrete Realisierung einer unveränderten Instanz, einer Instanz mit gelöschten Knoten, einer
Instanz mit einem hinzugefügten Knoten sowie eine Instanz, die beide Änderungen der beiden
anderen Instanzen enthält, erläutern. Der gelöschte Knoten ist dabei so gewählt, dass daraus
eine komplexe Änderung resultiert, da durch das Löschen des Knotens ein leerer Zweig in einer
Verzweigung entsteht. Da dies kein gültiges Prozessmodell darstellt, soll der leere Zweig im Rahmen
14
derselben Änderungsoperation gleich mitgelöscht werden. Dies verdeutlicht die Realisierung von
Substitutionsvorlagen bei komplexen Änderungen. Der zweite Fall stellt eine einfache Änderung
dar; dabei wird ein Knoten in einer Sequenz eingefügt. Im dritten Fall ist die Vereinigung der
Änderungen aus Fall 1 und 2 und stellt eine komplexe Änderung dar, die sowohl die vorderen
als auch die hinteren Teile der Prozessvorlage umfasst. Das Verschieben von Knoten wird nicht
explizit betrachtet, da dies durch die Verknüpfung von Löschen und Hinzufügen realisiert wird.
Die aus diesen Änderungen resultierenden vollständigen Vorlagen sind in Abb. 6 links unten zu
sehen.
A
B
C
D E F
VorlageW
logischeSicht
D E
G
SubstitutQ
ADB
SubstitutP
AB
SubstitutR
D E
G
Knoten Knotentyp ...
A SEQUENCE
D SEQUENCE
Quellknoten Zielknoten Kantentyp ...
A B CONTROL
B D CONTROL
D E CONTROL
TeilvorlageP
Knoten Knotentyp ...
D AND-Join
G SEQUENCE
E SEQUENCE
Quellknoten Zielknoten Kantentyp ...
B D CONTROL
C D CONTROL
D G CONTROL
G E CONTROL
E F CONTROL
TeilvorlageQ
Knoten Knotentyp ...
A AND-Split
B SEQUENCE
C SEQUENCE
D AND-Join
E SEQUENCE
F SEQUENCE
Quellknoten Zielknoten Kantentyp ...
A B CONTROL
A C CONTROL
B D CONTROL
C D CONTROL
D E CONTROL
E F CONTROL
Vorlage W Instanz1
Vorlage
A
Knoten Zustand Vorlage ...
A RUNNING W
B NOT_ACTIVATED W
C NOT_ACTIVATED W
D NOT_ACTIVATED W
E NOT_ACTIVATED W
F NOT_ACTIVATED W
Instanz2
Instanz12
W
W
Vorlage
Vorlage
Q
R
Knoten Zustand Vorlage ...
A RUNNING W
B NOT_ACTIVATED W
C NOT_ACTIVATED W
D NOT_ACTIVATED Q
G NOT_ACTIVATED Q
E NOT_ACTIVATED Q
F NOT_ACTIVATED W
Instanz5
Vorlage
W
P
Knoten Zustand Vorlage ...
A RUNNING P
B NOT_ACTIVATED W
D NOT_ACTIVATED P
E NOT_ACTIVATED W
F NOT_ACTIVATED W
physischeSicht
TeilvorlageR
Knoten Knotentyp ...
A SEQUENCE
D SEQUENCE
G SEQUENCE
E SEQUENCE
Quellknoten Zielknoten Kantentyp ...
A B CONTROL
B D CONTROL
D G CONTROL
G E CONTROL
E F CONTROL
Knoten Zustand Schema ...
A RUNNING R
B NOT_ACTIVATED R
D NOT_ACTIVATED R
G NOT_ACTIVATED R
E NOT_ACTIVATED R
F NOT_ACTIVATED W
Abbildung 13: Realisierung von Substitutionsvorlagen (ÄR-3-1)
Abb. 13 zeigt die logische und die physische Sicht auf eine unveränderte Instanz (Instanz 1)
und zwei geänderte Instanzen (Instanzen 5 und 2) sowie die entsprechenden Substitute (logische
Sicht) bzw. (Teil-)Vorlagen (physische Sicht). In Instanz 5 wurde Knoten C zusammen mit dem
entsprechenden Teilzweig einer Verzweigung gelöscht, was sich in Substitut P widerspiegelt (linke
Seite von Abb. 13). Für die Realisierung dieser Änderung wurden alle betroffenen Knoten mit
sämtlichen Attributen sowie alle ein-/ausgehenden Kanten von der ursprünglichen Vorlage auf
eine neue Teilvorlage P kopiert und dort geändert. Ein Knoten ist von einer Änderung betroffen,
wenn seine Attribute oder die Menge seiner ein-/ausgehenden Kanten modifiziert wird.
Beim Löschen von Knoten C entsteht ein leerer Zweig, der auch entfernt wird. Dadurch werden
die Knoten A und D modifiziert. Diese ändern ihren Typ von Verzweigungs- bzw. Vereinigungs-
knoten zu einfachen Sequenzknoten2. Die Kanten A-B, B-D und D-E werden nicht modifiziert,
sie werden aber bei Teilvorlage P benötigt, um den Übergang vom Substitut P zur usprünglichen
Vorlage W zu realisieren (sog. Kontextkanten). Ohne die Kante D-E würde die für den Knoten D
gültige Teilvorlage P keinen Nachfolger für D liefern. Das liegt daran, dass die Information über
die jeweils gültige (Teil-)Vorlage in Instanzobjekten (rechte Spalte in Abb. 13) nur für Knoten
existiert, nicht aber für Kanten.
Nach Erzeugung der Substitutionsvorlage wird noch das Instanzobjekt angepasst (Abb. 13,
2Dabei ist es unerheblich, ob es sich um parallele oder alternative Verzweigungen handelt.
15
rechts in der Mitte). Dazu wird Teilvorlage P als gültige Vorlage bei Knoten A und D hinterlegt.
Knoten C wird aus der Zustandsliste gelöscht und ist damit nicht mehr erreichbar. Es existieren
zwar noch die Kanten A-C und C-D in Vorlage W, diese werden jedoch nicht mehr berücksichtigt,
da Zugriffe auf Knoten A und D ausschließlich über die Teilvorlage P erfolgen, die diese Kanten
aber nicht besitzt.
Beim Hinzufügen eines neuen Knotens G bei Instanz 2 werden neben Knoten G genau die Kno-
ten auf Teilvorlage Q kopiert, deren Attribute bzw. ein-/ausgehende Kanten modifziert werden.
Dies sind im vorliegenden Fall Knoten D und F. Zusätzlich werden noch die zugehörigen Kanten
(B-D, C-D, E-F) sowie die neu hinzugekommenen Kanten (D-G, G-E) übernommen. Analog zum
Löschen von Knoten C bei Instanz 5 muss die Kante D-E der Vorlage W bei Instanz 2 nicht weiter
berücksichtigt werden, da sie nach den entsprechenden Anpassungen im Instanzobjekt nicht mehr
erreicht werden kann. Diese Anpassungen beschränken sich auf das Einfügen des Knotens G in
die Zustandsliste sowie das Hinterlegen von Teilvorlage Q bei den Knoten D, G und E (Abb. 13,
rechts unten).
Bei einem Zugriff auf eine geänderte Instanz muss vor jedem einzelnen Knotenzugriff auf die (lo-
gische) instanzspezifische Vorlage überprüft werden, welche (Teil-)Vorlage für den entsprechenden
Knoten gültig ist. Beispielsweise verläuft die Bestimmung der transitiven Nachfolger von Knoten
B in Instanz 2 folgendermaßen: Zuerst wird die für B gültige Vorlage bestimmt. In der Zustands-
tabelle ergibt sich hierfür Vorlage W (3. Spalte). In Vorlage W wiederum ergibt sich aufgrund der
Kontrollkante B-D der Knoten D als Nachfolger von B. Für den Knoten D ergibt sich aus Instanz
2 Teilvorlage Q. Aus dieser wiederum wird aufgrund der Kontrollkante D-G der Knoten G als
Nachfolger von D bestimmt. Auch für Knoten G gilt, wie in Instanz 2 hinterlegt, Teilvorlage Q.
Hieraus lässt sich der Nachfolger E ermitteln. Über die Kontextkante E-F von Teilvorlage Q ergibt
sich der Knoten F als Nachfolger von E. Für Knoten F gilt die ursprüngliche Vorlage W. Da dort
Knoten F der Endknoten ist, gibt es keine weiteren Nachfolgerknoten mehr.
An diesem Beispiel wird deutlich, wie die Kontextkanten den Übergang zwischen Vorlage W
und Teilvorlage Q ermöglichen, also die Kanten, die in einen geänderten Bereich ein- und ausgehen.
Diese sind zu diesem Zweck sowohl in der ursprünglichen Vorlage als auch im Substitutionsobjekt
hinterlegt.
Instanz 12 schließlich vereinigt das Löschen von Knoten C und das Hinzufügen von Knoten G.
Wie aus Abb. 13 ersichtlich, gilt hier für die meisten Knoten die Teilvorlage R. Dies liegt daran,
dass die ursprüngliche Vorlage relativ klein und damit vorderer und hinterer Teil der Prozessvor-
lage dicht beieinander liegen. Mit einer größeren Vorlage gälte für mittlere Knoten durchaus noch
Vorlage W. Die Abbildung macht auch deutlich, dass die Knoten- und Kantenmengen in Teil-
vorlage R nicht ganz die Vereinigungen der Knoten- und Kantenmengen von Teilvorlage P und
Teilvorlage Q sind. Knoten D ist von beiden Änderungen betroffen, da er Kontextknoten ist. Na-
heliegendeweise existiert er in Teilvorlage R aber nur einmal. Außerdem gibt es durch das Löschen
von Knoten C in Teilvorlage R die Kontextkante C-D nicht, und auch die Kante D-E existiert
nicht, da sie durch die Kante D-G ersetzt wird.kaum signifikante
4.2 Variante ÄR-3-2: Gekapselte Vorlagen
Bei Implementierungsvariante ÄR-3-2 (gekapselte Vorlagen) besitzt das Substitutionsobjekt (Wrap-
per) diesselbe Schnittstelle wie eine vollständige Vorlage. Dies entspricht den Software-Entwurfs-
mustern Decorator bzw. Wrapper [8]. Dadurch besteht für eine Instanz kein Unterschied zwischen
Zugriffen auf Vorlage und Wrapper, was zu vollständiger Transparenz führt (Abb. 14). Die in
einem Wrapper gekapselten instanzspezifischen Änderungen werden direkt bei Zugriffen berück-
sichtigt. Hierzu wird eine Anfrage sowohl vom Vorlagenobjekt als auch vom Wrapper bearbeitet
und die beiden Teilergebnisse anschließend vereinigt.
Bei Durchführung instanzspezifischer Änderungen werden wie bei Implementierungsvariante
ÄR-3-1 (Substitutionsvorlagen) alle Knoten mit Änderungen in das Substitutionsobjekt (in diesem
Fall der Wrapper) übernommen. Bei gekapselten Vorlagen findet jedoch keine Substitution ganzer
Graphbereiche statt, sondern es werden einzelne Knoten und Kanten ersetzt.
16
WrapperP
WrapperQ
WrapperR
Knoten Knotentyp ...
A AND-Split
B SEQUENCE
C SEQUENCE
D AND-Join
E SEQUENCE
F SEQUENCE
Quellknoten Zielknoten Kantentyp ...
A B CONTROL
A C CONTROL
B D CONTROL
C D CONTROL
D E CONTROL
E F CONTROL
Vorlage W Instanz1
Vorlage
Instanz2
Instanz12
Vorlage
Vorlage
Instanz5
Vorlage
Knoten Zustand ...
A RUNNING
B NOT_ACTIVATED
D NOT_ACTIVATED
E NOT_ACTIVATED
F NOT_ACTIVATED
Knoten Zustand ...
A RUNNING
B NOT_ACTIVATED
C NOT_ACTIVATED
D NOT_ACTIVATED
E NOT_ACTIVATED
F NOT_ACTIVATED
Knoten Zustand ...
A RUNNING
B NOT_ACTIVATED
C NOT_ACTIVATED
D NOT_ACTIVATED
G NOT_ACTIVATED
E NOT_ACTIVATED
F NOT_ACTIVATED
Knoten Knotentyp ...
A SEQUENCE
C deleted
D SEQUENCE
Knoten Knotentyp ...
G SEQUENCE
Quellknoten Zielknoten Kantentyp ... geloescht?
A C CONTROL ja
C D CONTROL ja
Quellknoten Zielknoten Kantentyp ... geloescht?
D E CONTROL ja
D G CONTROL
G E CONTROL
physischeSicht
logischeSicht
A
B
C
D E F
Vorlage W
D E
G
SubstitutQ
ADB
SubstitutP
AB
SubstitutR
D E
G
Knoten Zustand ...
A RUNNING
B NOT_ACTIVATED
D NOT_ACTIVATED
G NOT_ACTIVATED
E NOT_ACTIVATED
F NOT_ACTIVATED
Knoten Knotentyp ...
A SEQUENCE
C deleted
D SEQUENCE
G SEQUENCE
Quellknoten Zielknoten Kantentyp ... geloescht?
A C CONTROL ja
C D CONTROL ja
D E CONTROL ja
D G CONTROL
G E CONTROL
Abbildung 14: Realisierung von gekapselten Vorlagen (ÄR-3-2)
Beim Löschen von Knoten C in Instanz 5 werden die Knoten A und D in den Wrapper P über-
nommen und jeweils die Änderung des Knotentyps vermerkt (siehe resultierende Datenstrukturen
in Abb. 14, Wrapper B) . Zusätzlich werden die gelöschten Knoten und Kanten (im Beispiel Kno-
ten C und Kanten A-C und C-D) explizit verwaltet und damit auch in Wrapper B übernommen.
Dafür gibt es im Gegensatz zu Variante ÄR-3-1 (Substitutionsvorlagen) jedoch keine Redundanzen
zwischen ursprünglicher Vorlage und Wrapper (z. B. Kanten A-B und B-D), da keine Kontext-
kanten benötigt werden. In Instanz 5 wird abschließend noch Knoten C aus der Zustandstabelle
entfernt (Abb. 14, rechts in der Mitte). Auch bei den Instanzobjekten wird bei Variante ÄR-3-2
weniger Speicherplatz benötigt als bei Implementierungsvariante ÄR-3-1, da nur eine Vorlage refe-
renziert wird und bei Knoten keine Unterscheidung bezüglich der gültigen (Teil-)Vorlage benötigt
wird. In Abb. 14 spiegelt sich dies im Fehlen der entsprechenden Spalte wider.
Das Hinzufügen eines Knotens ist bei gekapselten Vorlagen einfacher als bei Implementierungs-
variante ÄR-3-1 (vgl. Abb. 13 und Abb. 14). Um den neuen Knoten G zwischen D und E in Instanz
2 einzufügen, wird er zusammen mit den ein-/ausgehenden Kanten (D-G, G-E) in Wrapper Q hin-
terlegt. Zusätzlich wird noch die ursprüngliche Kante D-E als gelöscht markiert. Die Änderung
schließt mit der Aufnahme von G in die Zustandstabelle von Instanz 2 (Abb. 14, rechts unten).
Die Bestimmung der transitiven Nachfolger von Knoten B der Instanz 2 werden wie bei Im-
plementierungsvariante ÄR-3-1 iterativ bestimmt. Dazu werden in jedem Schritt die (direkten)
Nachfolger des jeweiligen Knotens sowohl mittels der ursprünglichen Vorlage (Vorlage W) als auch
mittels Substitutionsobjekt (Wrapper Q) bestimmt und die einzelnen Ergebnisse entsprechend zu-
sammengefasst. Aufgrund von Vorlage W und Kante B-D ergibt sich der Knoten D als Nachfolger
von B, während Wrapper Q keine von B ausgehende Kontrollkante besitzt und somit auch keinen
Nachfolgerknoten für B liefert. Aus beiden Informationen ergibt sich Knoten D als Nachfolger
von B. Als Nachfolger von D wiederum liefert Vorlage W den Knoten E, während Wrapper Q
den Knoten G als Nachfolger liefert und zusätzlich die Information, dass die Kante D-E gelöscht
ist und somit Knoten E nicht mehr länger Nachfolger von D ist. Somit ergibt sich Knoten G als
17
alleiniger Nachfolger von D. Dessen Nachfolgerknoten wiederum ist der Vorlage W nicht bekannt,
wohingegen Wrapper Q den Knoten E ermittelt, der damit der korrekte Nachfolger von G ist.
Der Nachfolger von Knoten E wird wie der Nachfolger von Knoten B ermittelt: Vorlage W liefert
Knoten F, Wrapper Q kennt keinen Nachfolgerknoten, womit F als (letzter) Nachfolger bestimmt
ist.
Im Gegensatz zu ÄR-3-1 sind bei der Anwendung beider Änderungen bei Instanz 12 die Knoten-
und Kantenmengen von Wrapper R die echte Vereinigung der Knoten- und Kantenmengen von
Wrapper P und Wrapper Q. Dies liegt daran, dass bei gekapselten Vorlagen auch gelöschte Knoten
und Kanten explizit vorgehalten werden, während diese bei ÄR-3-1 (Substitutionsvorlagen) gleich
entsprechend entfernt werden. Letztere ist damit jedoch etwas aufwendiger zu implementieren.
Wie in Abb. 14 ersichtlich, haben umfangreichere Änderungen auch hier keine Auswirkungen auf
die Menge der zu verwalteten Daten für die Repräsentation von Änderungen. Das heißt, obwohl
sowohl der vordere Teil als auch der hintere Teil der Prozessvorlage von Änderungen betroffen ist,
wird die Repräsentation des (logischen) Substitutionsobjekts (in diesem Fall Substitut R) nicht
größer als wenn die Änderungen einen zusammenhängenden Teil der Prozessvorlage beträfen.
Charakteristisch für Variante ÄR-3-2 ist, dass nicht eine nicht nur an die gültige (Teil-)Vorlage
geht, sondern dass sie sowohl von der ursprüngliche Vorlage als auch vom Wrapper bearbeitet
wird. Die ermittelten Ergebnisse werden anschließend entsprechend vereinigt, wobei das Ergeb-
nis vom Wrapper höhere Priorität hat. Diese Vereinigung ist potentiell aufwendig, da es sich
dabei um Mengenoperationen handelt. Allerdings sind die ermittelten Knotenmengen meistens
nicht besonders groß: Bei Prozessvorlagen sind die meisten Knoten sequentiell angeordnet, was
zu zweielementigen Mengen bei der Bestimmung direkter Vorgänger-/Nachfolgerknoten führt –
ein Knoten von der ursprünglichen Vorlage und ein Knoten vom Wrapper. Lediglich bei Verzwei-
gungs-/Vereinigungsknoten werden die Mengen größer, aber auch hier sind mehr als 2*4 Elemente
in der Menge sehr selten. Dadurch bleiben die notwendigen Mengenoperationen effizient.
Insbesondere für sukzessive Zugriffe ist mit Variante ÄR-3-2 aber eine Verbesserung sehr leicht
möglich, indem temporär die logische instanzspezifische Vorlage realisiert wird. Hierzu werden
einfach die Vereinigung der gesamten Knoten- und Kantentabellen von Vorlage und Wrapper
erzeugt und die im Wrapper als gelöscht markierten Objekte enfernt. Dadurch ergibt sich direkt
auf Ebene der Datenstrukturen von Knoten- und Kantenmengen das resultierende vollständige
logische Schema, ohne dass Änderungsoperationen aufwendig nachgespielt werden müssen.
4.3 Qualitativer Vergleich der Implementierungsvarianten
Sowohl Implementierungsvariante ÄR-3-1 (Substitutionsvorlagen) als auch Variante ÄR-3-2 (ge-
kapselte Vorlagen) realisieren strukturelle Instanzdeltas. Es gibt jedoch signifikante Unterschiede
bezüglich der verwalteten Information und dem Ablauf von Zugriffen. Dies äußert sich auch im
Speicherbedarf und in der Zugriffszeit. So ist bei Variante ÄR-3-1 vor jedem Zugriff auf Vorlagen-
informationen jeweils ein zusätzlicher Zugriff auf die geänderte Instanz notwendig, um die gültige
(Teil-)Vorlage zu bestimmen. Anschließend kann die gewünschte Information direkt bestimmt wer-
den. Bei Variante ÄR-3-2 sind mehrere Zugriffe nötig, um die jeweilige Information in der Vorlage
und im Wrapper zu bestimmen und um die so bestimmten Ergebnisse anschließend geeignet zu-
sammenzufassen, also zusätzliche Knoten aus dem Wrapper der Ergebnismenge hinzuzufügen und
im Wrapper als gelöscht markierte Knoten zu entfernen. Wie erwähnt, ist das Zusammenfassen
jedoch nicht allzu zeitaufwendig, da die bei einem Wrapper-/Vorlagenzugriff bestimmten Knoten-
und Kantenmengen nicht sehr groß sind. Dies liegt daran, dass Prozesse meistens eine eher se-
quentielle Struktur besitzen. Zudem kann die Situation durch horizontale Partitionierung weiter
verbessert werden.
Implementierungsvariante ÄR-3-2 benötigt gegenüber Variante ÄR-3-1 weniger Speicherplatz,
da nur die Änderungen der ursprünglichen Vorlage verwaltet werden und damit keine Redundan-
zen existieren wie etwa Kontextkanten. Es reicht sogar aus, nur die wirklich geänderten Attribute
eines Knotens bzw. einer Kante zu speichern und nicht das komplette Knoten-/Kantenobjekt
bereitzustellen. Das Vermerken von gelöschten Objekten bei Variante ÄR-3-2 erfordert zwar zu-
18
sätzlichen Speicherbedarf, jedoch ist dieser nur wenig höher als bei Variante ÄR-3-1 (vgl. Abb. 13,
Teilvorlage P und Abb. 14, Wrapper P). Zudem wird die Information über gelöschte Objekte für
den Vergleich von Vorlagenänderungen mit Instanzänderungen bei Schemaevolution benötigt. Bei
Variante ÄR-3-1 muss diese erst rekonstruiert werden.
Für Implementierungsvariante ÄR-3-2 spricht auch die vollständige Transparenz und die ein-
fache Erzeugung der logischen instanzspezifische Vorlage. Durch die Kapselung ist es sehr leicht
möglich, bei großer Anzahl von Änderungen einen Wrapper durch einen vollständigen individuellen
Instanzgraphen zu ersetzen (vgl. Realisierungskonzept ÄR-1, Abschnitt 3.1).
5 Quantitativer Vergleich
Zwecks quantitativer Vergleichbarkeit haben wir die vorgestellten Realisierungskonzepte für indi-
viduelle Instanzgraphen, operationale Instanzdeltas und strukturelle Instanzdeltas in den beiden
Implementierungsvarianten Substitutionsvorlagen und gekapselte Vorlagen prototypisch imple-
mentiert. Anhand der vorgenommenen Implementierungen werden Messungen bezüglich Speicher-
bedarf und Laufzeit durchgeführt, wobei die Messungen von der Anzahl der Instanzänderungen
abhängen.
Für den quantitativen Vergleich der Realisierungskonzepte ziehen wir Messungen im Rahmen
dieser Arbeit rein theoretischen Betrachtungen vor. Einerseits sollen die Einflüsse der Laufzeit-
umgebung (etwa die laufzeitkritische Durchführung von Mengenoperationen) mit in die Messung
eingehen, andererseits soll die Laufzeit möglichst konkret ermittelt werden und nicht nur abstrakt
(etwa mittels O-Notation). Bevor wir die Messergebnisse vorstellen und interpretieren, erläutern
wir zuerst die Testumgebung, in der wir die Messungen durchgeführt haben, sowie den Ablauf der
Messungen.
5.1 Testumgebung
Die Implementierung der Realisierungskonzepte erfolgt in Java, die Messungen wurden auf einer
Java-Laufzeitumgebung von Sun (32 Bit) durchgeführt. Als Basis-Datentypen für die Datenstruk-
turen werden boolean (8 Bit-Datentyp), byte (8 Bit-Datentyp), short (16 Bit-Datentyp), Refe-
renzen (32 Bit-Datentyp), Zeichenketten (Unicode, jeweils 16 Bit pro Zeichen) sowie Arrays dieser
Basis-Datentypen verwendet. Prozessvorlagen, geänderte Prozessvorlagen (d. h. individuelle In-
stanzgraphen, Teilvorlagen und Wrapper) und Prozessinstanzen sind jeweils als eigene Javaobjekte
realisiert. Prozessvorlagen besitzen Arrays vom Datentyp short als Objektvariablen für Knoten-
typen, Kanten-Quellknoten, Kanten-Zielknoten und Kantentypen. Prozessinstanzen besitzen eine
Referenz auf das entsprechende Prozessvorlagenobjekt sowie ein Array vom Datentyp byte für
die Knotenzustände. Der Index der Arrays wird als Knoten-ID bzw. Kanten-ID interpretiert, der
Inhalt an der Stelle im Array ist der entsprechende Attributwert.
Wird eine Prozessinstanz geändert, wird das referenzierte Prozessvorlagenobjekt durch ein
eigenes Objekt des entsprechenden Realisierungskonzepts ersetzt. Dieses referenziert dann die ur-
sprüngliche Vorlage und ist damit der Instanz und der ursprünglichen Vorlage zwischengeschaltet.
Dies gilt nicht für ÄR-1 (individuelle Instanzgraphen), hier wird eine neues normales Vorlagenob-
jekt erzeugt, das die ursprüngliche Vorlage komplett ersetzt. Allerdings werden in der Implemen-
tierung hier zusätzlich die gelöschten Knoten mit im ersetzenden Vorlagenobjekt abgelegt. Dies ist
für diese Änderungsrepräsentation eigentlich nicht notwendig, es erleichtert aber die Ermittlung
der Unterschiede zwischen dem individuellen Instanzgraphen und der ursprünglichen Vorlage.
Bei ÄR-3-1 (Substitutionsvorlagen) wird ein Vorlagenobjekt erzeugt, das die Objektvariablen
einer normalen Vorlage zur Aufnahme neuer und geänderter Prozessstrukturen besitzt und zu-
sätzlich ein Array, welches das Vorlagenobjekt (entweder das Substitutionsobjekt this oder die
ursprüngliche Vorlage) referenziert, das für einen bestimmten Knoten gültig ist. Das Objekt für
gekapselte Vorlagen (ÄR-3-2) benötigt dieses Array nicht, und hat dementsprechend nur eine Re-
ferenz auf das ursprüngliche Vorlagenobjekt. Dafür besitzt diese Objekt neben den Arrays für die
19
hinzugefügten und geänderten Prozessstrukturen zwei Arrays vom Datentyp boolean für gelöschte
Knoten und Kanten.
Bei der Implementierung von ÄR-2 (operationale Instanzdeltas) gibt es für jede durchgeführte
Änderung ein eigenes Änderungsobjekt. Deren Objektvariablen entsprechen den für die jeweili-
ge Änderungsoperation notwendigen Informationen, z. B. eine Knoten-ID vom Typ short für
das Änderungsobjekt zum Löschen eines Knotens. Die Änderungsobjekte werden in einem Ar-
ray bei der entsprechenden Instanz referenziert. Vor einem Zugriff auf die Prozessinstanz werden
die Änderungsoperationen neu auf die ursprüngliche Vorlage angewandt und damit temporär ein
individueller Instanzgraph erstellt. Dieser gilt dabei immer nur für eine Anfrage, z. B. transiti-
ve Vorgängerbestimmung oder eine Zustandsänderung eines Knotens. Das heißt, der individuelle
Instanzgraph wird einmal für die komplette transitive Vorgängerbestimmung erzeugt, aber jedes
Mal für eine Zustandsänderung eines Knotens.
5.2 Messungsablauf
Ausgangspunkt der Messungen ist eine unveränderte Instanz. Die entsprechende Prozessvorlage
besitzt 100 Knoten, die sequentiell angeordnet sind. Hiervon wird der Speicherbedarf für die Da-
tenstrukturen gemessen, die für die Repräsentation der instanzspezifischen Änderungen notwendig
sind. Der Speicherplatz für die Instanzdaten (z. B. Zustandsinformation) sowie der von der ur-
sprünglichen Vorlage belegte Speicher sind nicht in der Messung enthalten, da diese unabhängig
von der gewählten Änderungsrepräsentation sind. Der Speicherbedarf wird absolut angegeben.
Außerdem wird die Zeit für die Bestimmung aller Vorgänger des letzten Knotens der Sequenz
sowie die Zeit für das Weiterschalten eines Knotens ermittelt. Um Laufzeitunterschiede einzelner
Messsungen zu minimieren, wird die Vorgängerbestimmung 10.000 Mal durchgeführt und alle Er-
gebnisse arithmetisch gemittelt. Auch das Weiterschalten wird 10.000 Mal durchgeführt. Allerdings
wird zusätzlich jeder Knoten der Prozessinstanz weitergeschaltet, d. h. jeder Knoten der Instanz
wird pro Durchlauf einmal „gestartet“ und einmal „beendet“. Das Ergebnis wird ansschließend
durch die Anzahl der Knoten (100) dividiert, um somit den Mittelwert für das Weiterschalten
eines Knotens dieser Instanz zu erhalten, bevor auch hier der Mittelwert über alle 10.000 gemesse-
nen Zeiten gebildet wird. Die Implementierung der Prozessinstanz basiert auf Vorlagenreferenzen
mit expizliten Markierungen [10]. Die transitive Vorgängerbestimmung ist ein komplexer Daten-
zugriff. Dieser erfolgt iterativ, wobei in jedem Schritt die jeweiligen Vorgänger eines Knotens
ermittelt und der Ergebnismenge hinzugefügt werden. Dabei dürfen die Vorgänger jedes Knotens
nur einmal ermittelt werden, um nicht in eine Endlosschleife zu geraten.
Die Zeitmessungen bei der Vorgängerbestimmung und beim Weiterschalten werden jeweils
in Relation zur Laufzeit einer unveränderten Instanz gesetzt. Das heißt, ohne Änderungen ist der
relative Zeitbedarf sohwohl für das Weiterschalten als auch für die transitive Vorgängerbestimmung
jeweils 1.
Da die Messungen bezüglich der Anzahl an Änderungen ermittelt werden sollen, wird nach
dem Durchlaufen aller Messungen wie eben beschrieben bei jedem Realisierungskonzept eine In-
stanzänderung durchgeführt. Diese beinhaltet das Hinzufügen eines Knotens in die Sequenz sowie
das Entfernen eines bereits vorhandenen Knotens. Dadurch bleibt die Anzahl der Knoten der
Prozessvorlage über alle Messungen konstant. Bei jedem Durchlauf „wandert“ jedoch ein Knoten
von der ursprünglichen Prozessvorlage auf die geänderte Prozessvorlage. Dies erfolgt für jeden
Knoten der ursprünglichen Sequenz einmal, so dass am Ende zwar diesselben Graphstrukturen
wie zu Beginn des Tests existieren, diese jedoch ausschließlich über Änderungen erzeugt wurden
und die ursprüngliche Vorlage komplett überlagert ist. Damit sind pro Realisierungskonzept 100
Messdurchläufe nötig. Hierdurch erhalten wir die gewünschten Messergebnisse pro Realisierungs-
konzept abhängig von der Anzahl an durchgeführen Änderungen.
Die Art der Änderung ist weitgehend vernachlässigbar. Lediglich bei ÄR-2 und bei ÄR-3-1
sind bei komplexeren Änderungsoperationen größere Änderungskontexte notwendig, so dass der
Speicherbedarf etwas höher sein wird als beim vorliegenden Messungsablauf.
20
5.2.1 Speicherbedarf
Abb. 15 zeigt den absoluten Speicherbedarf der verschiedenen Implementierungen in Abhängigkeit
von der Anzahl der vorgenommenen Instanzänderungen. Am Speicherbedarf von 0 Byte bei 0 Än-
derungen mit operationalen Instanzdeltas wird deutlich, dass sich der gemessene Speicherbedarf
nur auf die Repräsentation von instanzspezifischen Änderungen bezieht.
0
500
1000
1500
2000
2500
3000
3500
4000
4500
0 10 20 30 40 50 60 70 80 90 100
Anzahl Änderungstransaktionen
(1 Transaktion = 1 Knoten löschen + 1 Knoten hinzufügen)
Speicherbedarf pro Instanz in Byte (ohne Instanzdaten)
ÄR-1 (individuelle Instanzgraphen)
ÄR-2 (operationale Instanzdeltas)
ÄR-3-1 (Substitutionsvorlagen)
ÄR-3-2 (gekapselte Vorlagen)
Abbildung 15: Speicherbedarf für Realisierungskonzepte
Sehr auffällig an der Messung ist der schnelle Anstieg bei Realisierungskonzept ÄR-2 (operatio-
nale Instanzdeltas), obwohl man intuitiv hierfür eigentlich mit weniger Speicherbedarf als bei den
anderen Realisierungskonzepten rechnet. Das liegt in dieser Implementierung daran, dass für jede
durchgeführte Änderungsoperation ein eigenes Änderungsobjekt angelegt wird, was relativ viel
Speicher für Objektmetainformationen benötigt. Eine andere, potentiell bessere Realisierungmög-
lichkeit ist, Zeichenketten anstelle von Änderungsobjekten zu verwenden (z. B. „DeleteNode B“),
vergleichbar einem Änderungsprotokoll. Dies führte jedoch in der Implementierung überraschen-
derweise zu einem noch schnelleren Anstieg des Speicherbedarfs. Der Grund hierfür könnte in der
relativ aufwendigen Repräsentation von Zeichenketten in Java (2 Byte pro Zeichen) liegen. Des-
halb ist Realisierungskonzept ÄR-2, wie in Abb. 15 zu sehen, nur bis zu einer mittleren Anzahl
an Änderungen für die Repräsentation geeignet.
Realisierte Graphstrukturen (Realisierungskonzept ÄR-1, Implementierungsvarianten ÄR-3-1
und ÄR-3-2) benötigen ab einer mittleren Anzahl von Änderungen wesentlich weniger Speicher-
platz als operationale Instanzdeltas: Implementierungsvariante ÄR-3-2 ist im vorliegenden Sze-
nario ab 10 Änderungstransaktionen (d. h. 10 Einfügungen und 10 Löschungen) besser, ab 25
Änderungen ist Implementierungsvariante ÄR-3-1 und ab 30 Änderungen sogar Realisierungskon-
zept ÄR-1 (vollständige individuelle Instanzgraphen) besser als Implementierungsvariante ÄR-3-1.
Der Speicherbedarf für die Implementierungsvarianten ÄR-3-1 (Substitutionsvorlagen) und ÄR-3-2
(gekapselte Vorlagen) besitzt eine vergleichbare Steigung. Die Implementierungsvariante ÄR-3-1
ist aber aufgrund der redundanten Information (z. B. Kontextknoten) insgesamt größer.
Realisierungskonzept ÄR-1 (individuelle Instanzgraphen) ist erwartungsgemäß für wenige Än-
derungen sehr groß. Sie benötigt jedoch bei steigender Anzahl von Änderungen nur wenig zu-
sätzlichen Speicherbedarf. Dieser Anstieg ist ausschließlich darauf zurückzuführen, dass gelöschte
Knoten bei dieser Implementierung explizit verwaltet werden, d. h. sie werden als gelöscht markiert.
Kanten werden dagegen physisch gelöscht. Würde man auch Knoten physisch löschen, wäre der
Speicherbedarf von individuellen Instanzgraphen in dem verwendeten Anwendungsfall konstant,
da pro Änderungstransaktion ein Knoten hinzugefügt und einer entfernt wird.
21
5.2.2 Laufzeit (Zugriffe)
Abb. 16 zeigt das Ergebnis der Messungen für das Weiterschalten abhängig von der Anzahl Än-
derungen für die verschiedenen Änderungsrepräsentationen jeweils relativ zum Weiterschalten bei
einer unveränderten Prozessinstanz. Abb. 17 zeigt die Ergebnisse für die Bestimmung aller tran-
sitiven Vorgänger des letzten Knotens der getesteten Knotensequenz.
0,0
2,0
4,0
6,0
8,0
10,0
12,0
14,0
16,0
18,0
20,0
0 10 20 30 40 50 60 70 80 90 100
Anzahl Änderungstransaktionen
(1 Transaktion = 1 Knoten löschen + 1 Knoten hinzufügen)
Laufzeit relativ zu unveränderter Instanz
ÄR-1 (individuelle Instanzgraphen)
ÄR-2 (operationale Instanzdeltas)
ÄR-3-1 (Substitutionsvorlagen)
ÄR-3-2 (gekapselte Vorlagen)
Abbildung 16: Zugriffsdauer beim Weiterschalten
Sehr auffällig ist in beiden Fällen die hohe Laufzeit von Realisierungskonzept ÄR-2. Insbeson-
dere beim Weiterschalten (vgl. Abb. 16) ist der Anstieg bezüglich der Anzahl der Änderungen
sehr ausgeprägt. Dies liegt insgesamt an der aufwendigen temporären Rekonstruktion der aus den
Änderungen resultierenden logischen Vorlage. Da diese im Falle des Weiterschaltens vor jedem
Zugriff erfolgt, während sie bei der Vorgängerbestimmung nur einmal erfolgt, fällt der Aufwand
für die Rekonstruktion gegenüber dem des Zugriffs hier wesentlich mehr ins Gewicht als bei der
Vorgängerbestimmung.
Bei Realisierungskonzept ÄR-1 gibt es sowohl beim Weiterschalten als auch bei der transiti-
ven Vorgängerbestimmung kaum Unterschiede in der Laufzeit verglichen mit einer unveränderter
Instanz. Dies ist einleuchtend, da der Zugriff beides Mal identisch abläuft, d. h. es gibt keinerlei
Unterschied zwischen dem Zugriff auf eine uneränderte Instanz und einer veränderten Instanz mit
individuellem Instanzgraphen.
Auffällig ist, dass auch Implementierungsvariante ÄR-3-1 ein zu Realisierungskonzept ÄR-1
vergleichbares Laufzeitverhalten besitzt. Dies zeigt, dass die Bestimmung der gültigen Vorlage vor
jedem Knotenzugriff keine wesentlichen Auswirkungen hat. Der leichte Anstieg der Zugriffszeit
sowohl bei individuellen Instanzgraphen als auch im Zusammenhang mit Substitutionsvorlagen
bei größerer Anzahl an Änderungen kann mit dem höheren Speicherbedarf erklärt werden. Bei
beiden Verfahren steigt dieser gegenüber einer unveränderten Instanz an (vgl. Abschnitt 5.2.1),
wodurch die Laufzeitumgebung (z. B. Speicherverwaltung) beeinträchtigt wird. Dieser wiederum
beeinflusst indirekt die Laufzeit.
Bei Implementierungsvariante ÄR-3-2 ist der Zugriff etwas langsamer als bei Implementierungs-
variante ÄR-3-1 und Realisierungskonzept ÄR-1, da potentiell aufwendigere Mengenoperationen
nötig werden, z. B. zum Filtern von gelöschten Knoten. Mit steigender Anzahl an Änderungen
werden diese Operationen noch aufwendiger, da die zu durchsuchende Knoten- und Kantenmenge
größer wird, was den relativen Anstieg gegenüber den beiden schnelleren Verfahren erklärt.
22
0,5
1,0
1,5
2,0
2,5
3,0
3,5
0 10 20 30 40 50 60 70 80 90 100
Anzahl Änderungstransaktionen
(1 Transaktion = 1 Knoten löschen + 1 Knoten hinzufügen)
Laufzeit relativ zu unveränderter Instanz
ÄR-1 (individuelle Instanzgraphen)
ÄR-2 (operationale Instanzdeltas)
ÄR-3-1 (Substitutionsvorlagen)
ÄR-3-2 (gekapselte Vorlagen)
Abbildung 17: Zugriffsdauer bei der transitiven Vorgängerbestimmung
5.3 Fazit
Die Realisierung instanzspezifischer Änderungen mittels Realisierungskonzept ÄR-2 (operationale
Instanzdeltas) ist aufgrund der Zugriffszeit und des Speicherbedarfs nicht für die Repräsentation
im Primärspeicher geeignet. In Form einer Änderungshistorie im Sekundärspeicher sind sie absolut
notwendig, z. B. für Schemaevolution [20] und das Nachvollziehen von Änderungen.
Aufgrund der Zugriffszeiten ist Implementierungsvariante ÄR-3-1 eine sehr gutes Konzept bei
geringem Speicherbedarf. Die prototypische Implementierung offenbarte jedoch eine sehr komple-
xe und damit fehleranfällige Realisierung. Insbesondere die Verwaltung der Kanten hat sich als
problematisch herausgestellt, da bei zu ändernden oder zu löschenden Kanten vorab nicht immer
festgestellt werden kann, ob die Kante bereits Bestandteil des Substitutionsobjekts oder nur in
der ursprünglichen Vorlage vorhanden ist. Im ersten Fall muss sie ggf. physisch gelöscht werden,
im zweiten Fall nicht, da dies Auswirkungen auf alle Instanzen der entsprechenden Vorlage hätte.
Bei komplexen Änderungen ist zudem eine Verschlechterung des Speicherbedarfs zu erwarten, da
ein größerer Änderungskontext zu speichern ist.
Realisierungskonzept ÄR-1 benötigt bei wenigen Änderungen vergleichsweise viel Speicher-
platz, weshalb sich diese Variante erst ab einer Vielzahl von Instanzänderungen empfiehlt. Dies
lässt sich sehr gut in Kombination mit gekapselten Vorlagen realisieren, da diese den Wechsel
zur Repräsentation mittels individueller Instanzgraphen zur Laufzeit ermöglichen, d. h. sobald die
Änderungen eine bestimmte Grenze überschreiten, kann bei der Implementierung von Variante
ÄR-3-2 nahtlos zu eienr Implementierung des Realisierungskonzepts ÄR-1 gewechselt werden. Va-
riante ÄR-3-2 benötigt zudem am wenigsten Speicherplatz (bis 100 einfache Änderungen). Sie hat
zwar etwas schlechtere Zugriffszeiten als Implementierungsvariante ÄR-3-1 und Realisierungskon-
zept ÄR-1, die Zugriffszeiten sind jedoch immer noch sehr effizient. Zudem ist Variante ÄR-3-2
einfach zu implementieren.
6 Zusammenfassung und Ausblick
Flexibilität ist für ein breit einsetzbares Prozess-Management-System unabdingbar. Dies darf je-
doch nicht auf Kosten der Performanz gehen. In diesem Beitrag wurde untersucht, wie sich umfas-
sende Flexiblität, nämlich sowohl Änderungen an einzelnen laufenden Prozessinstanzen als auch
die Propagation von Änderungen von Prozessvorlagen auf laufende Instanzen effizient realisie-
23
ren lassen. Besonderes Augenmerk wurde dabei auch auf ein effizientes Zusammenspiel beider
Änderungsarten gelegt. Dazu wurden verschiedene Realisierungskonzepte und Implementierungs-
varianten umfassend diskutiert und miteinander verglichen. Neben einem qualitativen Vergleich
wurden auch eine prototypische Implementierung vorgenommen, die anhand von Messungen einen
quantitativen Vergleich ermöglicht. Die gewonnenen Erkenntnisse wurden bereits in einem Soft-
warewerkzeug für Schemaevolution und instanzspezifische Änderungen umgesetzt [11].
Die in diesem Beitrag diskutieren Realisierungskonzepte und Implementierungsvarianten bil-
den eine ausgezeichnete Ausgangsbasis für eine weitergehende Untersuchung. Dabei sollen weitere
Varianten im Detail untersucht und bewertet werden. Hierzu zählen die temporäre Realisierung
der logischen instanzspezifischen Vorlage für komplexe Funktionen mit häufigen Zugriffen auf die
Vorlage sowie hybride Verfahren, etwa der Wechsel zwischen gekapselten Vorlagen (ÄR-3-2) und
individuellen Instanzgraphen (ÄR-1). Außerdem können die Auswirkungen von Ein-/Auslagern
aus bzw. in den Sekundärspeicher untersucht werden; hierbei spielt die absolute Größe der Daten-
strukturen eine wichtige Rolle. Ebenso sind Varianten für die Repräsentation von Änderungen im
Sekundärspeicher sowie die Durchführung einer Schemaevolution ohne und mit instanzspezifischen
Änderungen Gegenstand weiterer Forschung.
Literatur
[1] Business Process Modeling Notation (BPMN). Technischer Bericht Version 1.2, OMG, Janu-
ary 2009.
[2] W.M.P. van der Aalst, B.F. van Dongen, J. Herbst, L. Maruster, G. Schimm, und A.J.M.M.
Weijters:Workflow mining: A Survey of Issues and Approaches. Data & Knowledge Engi-
neering, 47(2):237–267, 2003.
[3] M. Adams, A.H.M. ter Hofstede, D. Edmond, und W.M.P. van der Aalst:Worklets: A
Service-Oriented Implementation of Dynamic Flexibility in Workflows. In: On The Move to
Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE, Band 4275 der
Reihe LNCS, Seiten 291–308, Montpellier, November 2006. Springer.
[4] S. Bassil, M. Benyoucef, R.K. Keller, und P. Kropf:Addressing Dynamism in E-negotiations
by Workflow Management Systems. In: 13th International Workshop on Database and Expert
Systems Applications (DEXA), Seiten 655–659, Aix-en-Provence, 2002.
[5] S. Bassil, R.K. Keller, und P. Kropf:A Workflow-Oriented System Architecture for the
Management of Container Transportation. In: Business Process Management, Band 3080 der
Reihe LNCS, Seiten 116–131, Potsdam, June 2004. Springer.
[6] P. Dadam und M. Reichert:The ADEPT Project: A Decade of Research and Development
for Robust and Flexible Process Support – Challenges and Achievements. Computer Science
– Research and Development, 23(2):81–97, May 2009.
[7] P. Dadam, M. Reichert, S. Rinderle, M. Jurisch, H. Acker, K. Göser, U. Kreher, und M. Lau-
er:Towards Truly Flexible and Adaptive Process-Aware Information Systems. In: Information
Systems and e-Business Technologies, Band 5 der Reihe LNBIP, Seiten 72–83, Klagenfurt,
Austria, April 2008. Springer.
[8] E. Gamma, R. Helm, R. Johnson, und J. Vlissides:Design Patterns: Elements of Reusable
Object-oriented Software. Addison-Wesley, 1995.
[9] M. Kloppmann, D. König, F. Leymann, G. Pfau, und D. Roller:Enabling Technology: Ein
J2EE-basiertes Business Process Management System zur Ausführung von BPEL-und Web
Service-basierten. IT-Information Technology, 46(4):184–192, 2004.
24
[10] U. Kreher, M. Reichert, S. Rinderle-Ma, und P. Dadam:Effiziente Repräsentation von
Vorlagen- und Instanzdaten in Prozess-Management-Systemen. Technical Report UIB-2009-
08, University of Ulm, Ulm, 2009.
[11] M. Lauer, S. Rinderle, und M. Reichert:Repräsentation von Schema- und Instanzobjekten
in adaptiven Prozess-Management-Systemen. In: GI-Jahrestagung, Nummer 2, Seiten 555–
560, Ulm, 2004.
[12] R Lenz und M. Reichert:IT Support for Healthcare Processes – Premises, Challenges,
Perspectives. Data & Knowledge Engineering, 61(1):39–58, 2007.
[13] F. Leymann: Web Services Flow Language (WSFL 1.0). IBM Technical White Paper, IBM,
2001.
[14] F. Leymann und W. Altenhuber:Managing Business Processes as an Information Resour-
ce. IBM Systems Journal, 33(2):326–348, 1994.
[15] D. Müller, J. Herbst, M. Hammori, und M. Reichert:IT Support for Release Management
Processes in the Automotive Industry. In: Business Process Management, Band 4102 der
Reihe LNCS, Seiten 368–377, Vienna, October 2006. Springer.
[16] P. Muth, D. Wodtke, J. Weissenfels, G. Weikum, und A. Kotz Dittrich:Enterprise-Wide
Workflow Management Based on State and Activity Charts. In: A. Dogaç, L. Kalinichenko,
T. Özsu, und A. Sheth (Herausgeber): Workflow Management Systems and Interoperability,
Band 164 der Reihe NATO ASI Series F: Computer and System Sciences, Seiten 281–303,
Istanbul, 1998. Springer.
[17] M. Reichert: Dynamische Ablaufänderungen in Workflow-Management-Systemen. Dissertati-
on, Universität Ulm, Mai 2000.
[18] M. Reichert und P. Dadam:ADEPTflex — Supporting Dynamic Changes of Workflows
Without Losing Control. Journal of Intelligent Information Systems, 10(2):93–129, 1998.
[19] M. Reichert und P. Dadam:Enabling Adaptive Process-aware Information Systems with
ADEPT2. In: Handbook of Research on Business Process Modeling, Seiten 173–203. Hershey,
New York, New York, 2009.
[20] M. Reichert, S. Rinderle, und P. Dadam:On the Common Support of Workflow Type and
Instance Changes under Correctness Constraints. In: On The Move to Meaningful Internet
Systems 2003: CoopIS, DOA, and ODBASE, Band 2888 der Reihe LNCS, Seiten 407–425,
Catania, 2003. Springer.
[21] M. Reichert, S. Rinderle-Ma, und P. Dadam:Flexibility in Process-aware Information Sy-
stems. In: LNCS Transactions on Petri Nets and Other Models of Concurrency (ToPNoC),
Band 5460 der Reihe LNCS, Seiten 115–135, Eindhoven, 2009. Springer.
[22] M. Reichert und D. Stoll:Komposition, Choreographie und Orchestrierung von Web Ser-
vices: Ein Überblick. EMISA-Forum, 24(2):21–32, 2004.
[23] S. Rinderle, M. Reichert, und P. Dadam:Disjoint and Overlapping Process Changes: Challen-
ges, Solutions, Applications. In: On The Move to Meaningful Internet Systems 2004: CoopIS,
DOA, and ODBASE, Band 3290 der Reihe LNCS, Seiten 101–120, Agia Napa, Cyprus, 2004.
Springer.
[24] S. Rinderle, M. Reichert, und P. Dadam:Flexible Support of Team Processes by Adaptive
Workflow Systems. Distributed and Parallel Databases, 16(1):91–116, 2004.
[25] S. Rinderle, M. Reichert, und P. Dadam:On Dealing with Structural Conflicts between Pro-
cess Type and Instance Changes. In: Business Process Management, Band 3080 der Reihe
LNCS, Seiten 274–289, Potsdam, Germany, June 2004. Springer.
25
[26] S. Rinderle, M. Reichert, M. Jurisch, und U. Kreher:On Representing, Purging, and Utili-
zing Change Logs in Process Management Systems. In: Business Process Management, Band
4102 der Reihe LNCS, Seiten 241–256, Vienna, October 2006. Springer.
[27] S. Rinderle-Ma, M. Reichert, und B. Weber:On the Formal Semantics of Change Patterns
in Process-aware Information Systems. In: Proceedings of the 27th Int’l Conference on Con-
ceptual Modeling (ER’08), Band 5231 der Reihe LNCS, Seiten 279–293, Barcelona, October
2008. Springer.
[28] H. Wächter und A. Reuter:The ConTract Model. In: A.K. Elmagarmid (Herausgeber):
Database Transaction Models for Advanced Applications. Morgan Kaufmann Publishers, 1992.
[29] B. Weber, M. Reichert, und S. Rinderle-Ma:Change Patterns and Change Support Fea-
tures – Enhancing Flexibility in Process-Aware Information Systems. Data & Knowledge
Engineering, 66(3):438–466, 2008.
[30] M. Weske: Object-Oriented Design of a Flexible Workflow Management System. In: Advances
in Databases and Information Systems (ADABIS), Band 1475 der Reihe LNCS, Seiten 119–
130, Poznan, September 1998. Springer.
[31] M. Weske: Formal Foundation and Conceptual Design of Dynamic Adaptations in a Work-
flow Management System. In: R. Sprague (Herausgeber): Proc. 34th Hawaii International
Conference on System Sciences (HICSS-34). IEEE Computer Society Press, 2001.
26
