Correctness Criteria for Dynamic Changes in Workflow Systems: A Survey [original]

Correctness criteria for dynamic changes

in workﬂow systems––a survey

Stefanie Rinderle

, Manfred Reichert, Peter Dadam

Department Databases and Information Systems, Faculty of Computer Science, University of Ulm,

James-Franck-Ring, 89069 Ulm, Germany

Available online 25 January 2004

Abstract

The capability to dynamically adapt in-progress workﬂows (WF) is an essential requirement for any

workﬂow management system (WfMS). This fact has been recognized by the WF community for a long time

and diﬀerent approaches in the area of adaptive workﬂows have been developed so far. This survey sys-

tematically classiﬁes these approaches and discusses their strengths and limitations along typical problems

related to dynamic WF change. Along this classiﬁcation we present important criteria for the correct

adaptation of running workﬂows and analyze how actual approaches satisfy them. Furthermore, we provide

a detailed comparison of these approaches and sketch important further issues related to dynamic change.

Keywords: Workﬂow management; Adaptive systems; Dynamic workﬂow changes; Correctness criteria

1. Introduction

A rapidly changing environment and a turbulent market force any company to change their

business processes ever more frequently [1]. Process changes become necessary, for example, when

new laws come into eﬀect, optimized or restructured business processes are to be implemented,

exceptional situations occur, or reactions to a changed market are required. Therefore, a critical

This work was done within the research project ‘‘Change management in adaptive workﬂow management systems’’,

which is funded by the German Research Community (DFG).

Corresponding author. Tel.: +49-731-50-24229; fax: +49-731-50-24134.

E-mail addresses: [email protected] (S. Rinderle), [email protected] (M. Reichert),

[email protected] (P. Dadam).

doi:10.1016/j.datak.2004.01.002

www.elsevier.com/locate/datak

Data & Knowledge Engineering 50 (2004) 9–34

challenge for the competitiveness of any enterprise is its ability to quickly react to business process

changes and to adequately deal with them [16,31].

As pointed out in [17,22,28,34], basically, WF changes can take place at two levels––the WF

type and the WF instance level.Instance-speciﬁc changes are often applied in an ad-hoc manner

and become necessary in conjunction with real-world exceptions. They usually aﬀect only single

WF instances. As opposed to this, in conjunction with WF schema changes at the WF type level, a

collection of related instances may have to be adapted. There are many approaches supporting

such adaptive workﬂows [1,5,9,18,21,26,28,34]. All of them present very interesting, but partially

strongly diﬀering ideas and solutions. Therefore, it is an important job to summarize central

correctness criteria for adaptive workﬂows and to compare actual approaches along them. In this

survey, we focus on three fundamental issues regarding dynamic WF changes:

(1) Completeness. Users must not be unnecessarily restricted, neither by the applied WF meta

model nor the oﬀered change operations. Therefore, expressive control/data ﬂow constructs

must be provided [7]. For practical purposes, at minimum, change operations for inserting

and deleting activities as well as control/data dependencies between them are needed.

(2) Correctness. The ultimate ambition of any adaptive WF approach must be correctness of dy-

namic changes [1,5,9,18,21,26,28,34]. More precisely, we need adequate correctness criteria to

check whether a WF instance Iis compliant with a changed WF schema or not; i.e., whether

the respective change can be correctly propagated to Iwithout causing inconsistencies or er-

rors (like deadlocks or improperly invoked activity programs). These criteria must not be too

restrictive, i.e., no WF instance should be needlessly excluded from being adapted to a process

change.

(3) Change realization. Assuming that a dynamic change can be correctly propagated to an instance

I(along the stated correctness criteria), it should be possible to automatically migrate Ito the

new schema. In this context, one challenge is to correctly and eﬃciently adapt instance states.

In the following, we provide a classiﬁcation of actual approaches based on the operational

semantics of the underlying WF meta models and on the kind of correctness criteria applied for

dynamic WF changes (Sections 2 and 3). Section 3 introduces a selection of typical dynamic

change problems and discusses strengths and weaknesses of the approaches when dealing with

these problems. A detailed comparison of the diﬀerent approaches is presented in Section 4. We

sketch important change scenarios and existing approaches in Section 5 and close with a summary

in Section 6.

2. Workﬂow meta models of adaptive workﬂow approaches

Current approaches supporting adaptive workﬂows are based on diﬀerent WF meta models.

Very often, the solutions oﬀered by them are dependent on the expressiveness as well as on the

formal and operational semantics of the used formalism. Fig. 1 summarizes WF meta models for

which adaptive WF solutions have been realized. According to [15] we classify those meta models

with respect to their operational semantics and the evaluation strategies applied for executing WF

instances during runtime. The ﬁrst strategy uses only one type of (control ﬂow) token passing

10 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

through each WF instance (True-Tokens). The other strategy is based on two types of tokens––

True- and False-Tokens. (An early approach for True-/False-Tokens in bipolar synchronization

schemes was presented in [11].) Simplistically, True-Tokens trigger activities that are to be exe-

cuted next and False-Tokens describe skipped activities. Formalisms which solely use True-

Tokens include, for example, Petri-Nets [1,9,28] (cf. Section 2.1). Approaches which, in addition,

use False-Tokens to represent skipped activities or skipped execution branches can be found in the

area of graph-/activity-based meta models [5,18,21,26,34] (cf. Section 2.2). They can be further

divided according to the way they represent the tokens. One possibility is to gain them from

execution histories [5], which log events like activity start and completion. Alternatively, special

(model-inherent) activity markings, which represent a consolidated view on the history logs, can be

used [21,26,34].

In the following, for each approach shown in Fig. 1, we sketch the basic formalism used for WF

modeling and execution together with its structural and dynamic properties. This background

information is useful for better understanding the criteria applied by these approaches to guar-

antee dynamic change correctness (cf. Section 3).

2.1. Approaches with true-semantics

WF Nets.AWF Net is a labeled place/transition net N¼ðP;T;F;lÞrepresenting a control

ﬂow schema [28,29]. Thereby, Pdenotes the set of places, Tthe set of transitions, F

ðTPÞ[ðPTÞthe set of directed arcs, and lthe labeling function, which assigns a label to each

transition. Data ﬂow issues are excluded. A WF Net must have one initial place iand one ﬁnal

place f. In [28] a sound WF Net has to be connected, safe, and deadlock free as well as free of dead

transitions. Furthermore, sound WF Nets always properly terminate, i.e., the end state––which

contains one token in fand no other tokens––is always reachable. The behavior of a WF instance

is described by a marked WF net ðN;mÞwith marking function mand associated ﬁring rules. A

transition tis enabled if each of its input places contains a token. If tﬁres, all tokens from its input

places are removed and to each output place of ta token is added.

Flow Nets. The operational semantics of Flow Nets [8–10] is comparable to (safe) WF Nets but

with one major diﬀerence: Places can be equipped with more than one token. Chautauqua [10]

oﬀers an implementation where Flow Nets are generalized to Information Control Networks

(ICN). An ICN bases WF enactment on instance-speciﬁc data tokens. Diﬀerent WF instances are

distinguished by coloured tokens and are controlled by the same ICN.

MILANO Nets. Another Petri-Net-based approach is oﬀered by MILANO [1,2]. As opposed to

WF Nets and Flow Nets the expressiveness of MILANO Nets is restricted to marked, acyclic

Fig. 1. Meta models of approaches supporting adaptive workﬂow.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 11

Free-Choice Petri Nets (so called Net Models (NM)). Data ﬂow is not explicitly considered. An

NM Scan be mapped to a Sequential Model (SM) which represents global states and state

transitions of S. Thus, SM corresponds to the reachability graph of S.

Interestingly, the above approaches abstract from internal activity states, i.e., they only dif-

ferentiate between activated and non-activated transitions. As we will see later, this coarse clas-

siﬁcation may be unfavorable in conjunction with certain kind of dynamic changes.

2.2. Approaches with true/false-semantics

As opposed to the above approaches, the following WF meta models distinguish between

diﬀerent states an activity may go through. Generally, initial status of an activity is set to

NotActivated. It changes to Activated when all preconditions are met. Activity execution is

then either started automatically or corresponding worklist entries are generated. When starting

activity execution its status changes to Running. Finally, at successful termination, status passes

to Completed. In addition, some of the models assign status Skipped to activities belonging to

non-selected execution branches. Usually, in addition, an execution history PS

I¼he0;...;ekiis

maintained for each instance Iwith ei2fðSa;hvar;valiÞ;ðEa;hvar;valiÞg. For each started

activity Xthe values of process data elements read by Xand for each completed activity Ythe

values of data elements written by Yare logged.

2.2.1. Case 1: approaches based on history logs

WIDE Graphs: WIDE [5] uses an activity-based WF meta model which allows the modeling of

sequential, parallel, conditional, and iterative activity executions. A WF schema has to meet

several constraints to be correct: ﬁrst there must be a path from the start activity to all other

activities and the end activity has to be reachable from all of them. The other constraints refer to

the correct use of splits and joins. Furthermore, each WF schema Sis associated with a set of

global process variables whose values may be read or written by activity instances during runtime.

A particular instance Iis described by its schema Sand its execution history PS

I. As opposed to

the following approaches, WIDE only logs activity completion events.

TRAMs Graphs. In TRAMs [18]––in contrast to other graph-/activity-based approaches––

control ﬂow is not realized by control edges. Instead, it is described in a declarative way by using

conditions for starting/ﬁnishing activities. WF schema correctness is preserved by invariants, i.e.,

schema-related conditions which must be fulﬁlled. Data ﬂow is explicitly speciﬁed by connecting

output and input parameters of subsequent activities. TRAMs distinguishes between activity

states Activated,Running and Completed, and logs status changes in the execution history

Iof the respective instance I.

2.2.2. Case 2: approaches using model inherent markings

WASA2Activity Nets. WASA2[33,34] uses an activity-based meta model. A WF schema

S¼ðVS;CS;DSÞis a tuple with sets of activity nodes VS, control connectors CSVSVS, and data

connectors DSVSVS. Similar to TRAMs, the ﬂow of data is modeled by connectors which

map output and input parameters of subsequent activities. A WF schema Sis correct iﬀ all input

parameters are correctly mapped onto a type-conform output parameter and the graph structure

is acyclic, i.e., loops are excluded. A WF instance I is described by an instance graph

12 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

I¼ðVI;CI;DIÞwhose state is denoted by model-inherent activity markings. WASA2distinguishes

between markings NotActivated,Activated,Running,Completed, and Skipped.

Breeze Activity Nets. Similar to TRAMs and WASA2, Breeze [25,26] uses model-inherent

activity markings. A WF schema is described by a directed acyclic graph W¼hN;Fiwith ﬁnite

set of activity nodes Nand ﬂow relation FNN. It is possible to model sequences, parallel/

conditional branches and complex activities. WF data is described by a set of WF variables. A

schema is correct if there is a unique initial node niand a unique ﬁnal node nf, and for all n2N

there is a path from nito nfvia n. Breeze also ensures correct data provision of invoked activities.

ADEPT WSM-Nets. Another approach with model-inherent markings is oﬀered by Well-

Structured Marking-Nets (WSM-Nets) as applied in ADEPT [21]. WF schemes are represented by

serial-parallel graphs S¼ðN;D;NodeType;CtrlE;SyncE;LoopE;DataE;ECÞwith activity set N,

data element set D, and distinguishable node/edge types. Branchings of diﬀerent type and loops

are modeled in a block-oriented fashion. However, this restrictive structure can be relaxed by the

use of sync edges (SyncE), which allow to deﬁne precedence relations between activities of parallel

branches. Data ﬂow is modeled by connecting global process variables (D) with activities (N) either

by read or write data edges (DataE). A schema is correct iﬀ Sfwd ¼ðN;CtrlE;SyncEÞis an acyclic

graph, i.e., the use of sync edges must not lead to deadlock-causing cycles [21]. An instance I

is deﬁned by a tuple (S;NSS;ESS;ValS;PS

I) where Sdenotes the corresponding schema and

NSS:N7!fNotActivated;Activated;Running;Completed;Skippedgpossible node

states. ValSis a function on D. It reﬂects for each data element d2Deither its current value or

UNDEFINED (if dhas not been written yet). Finally, PS

Iis the execution history of I.

Comparing the above formalisms we can ﬁnd many diﬀerences. For example, only WF Nets,

Flow Nets, WIDE Graphs, and ADEPT WSM-Nets allow the modeling of loops. Data ﬂow issues

are factored out by WF Nets and MILANO Nets. While WIDE only logs end entries of activities,

the execution histories in TRAMs and ADEPT store the start entries of activities as well.

3. Classiﬁcation and dynamic change correctness

In this section, we present a classiﬁcation of the approaches introduced in Section 2. It is based

on the correctness criteria applied in connection with dynamic WF changes. This classiﬁcation is

fundamental for better understanding the diﬀerent solutions as well as their strengths and limi-

tations. In doing so, we do not make a diﬀerence between changes of single instances and

adaptations of a collection of instances (e.g., due to a WF type change). Instead we focus on

fundamental correctness issues related to dynamic WF changes. In the following, let Sbe a WF

schema and let Ibe an instance based on S. Assume that Sis transformed into another correct

schema S0by applying change D. What schema correctness exactly means depends on the struc-

tural and dynamic correctness properties of the used WF meta model (cf. Section 2).

3.1. Classiﬁcation and problem framework

Fig. 2 presents a two-dimensional classiﬁcation: The ﬁrst dimension (marked on the vertical

axis) is grouped by the kind of correctness criteria the diﬀerent approaches are based on. The

second dimension (marked on the horizontal axis) indicates on which information the diﬀerent

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 13

approaches check their particular correctness criterion. Regarding the ﬁrst dimension, we dis-

tinguish between approaches founding their correctness criteria on WF graph equivalence––WF

Nets,MILANO Nets, and WASA2Activity Nets––and approaches with correctness criteria based

on WF trace equivalence–Flow Nets,WIDE Graphs,Breeze Activity Nets,TRAMs Graphs and

ADEPT WSM-Nets. The core idea of graph equivalence is either to compare the respective WF

schema before and after the change [28] or to map the WF instance graph of Ito the changed WF

schema S0[1,34]. Depending on the ‘‘degree of coverage’’ it can be decided whether change Dis

applicable to Ior not. Generally, trace equivalence focuses on the work done by Iso far

[5,18,23,26]. If it could have been achieved on S0as well, Ican be migrated to S0.Apredictive

approach is oﬀered by Flow Nets [9] where, in addition, future instance execution on the changed

schema is taken into account. Regarding the second dimension, approaches can be further dis-

tinguished depending on how they check their particular correctness criterion. Some of them

consider complete history information of respective instances [5] whereas others use a consoli-

dated view of previous instance execution [18,24].

We show how the approaches from Fig. 2 ensure correctness in conjunction with dynamic WF

changes. In addition, for comparison purposes, we exemplarily discuss the approaches along ﬁve

typical problems related to dynamic change (cf. Fig. 3). Due to lack of space we cannot cover all

problems arising in this context. Particularly, we do not consider side-eﬀects of control ﬂow

modiﬁcations on WF aspects other than control and data ﬂow (e.g. temporal constraints).

Nevertheless, the following problems are very typical in the context of dynamic changes and

therefore provide a good basis for comparing existing approaches.

(1) Changing the Past (CP). The CP problem corresponds to the rule of thumb not to ‘‘change the

past of an instance’’. Neglecting this rule may lead to inconsistent instance states (e.g., live-

locks or deadlocks) or missing input data of subsequent activity executions (see Fig. 3(1)).

(2) Loop Tolerance (LT). The LT problem refers to an approachÕs ability to correctly and reason-

ably deal with changes on loop structures (see Fig. 3(2)). In particular, approaches should not

Fig. 2. Classiﬁcation of approaches along the applied correctness criteria.

For example, there is considerable work in the literature focussing on the interplay between dynamic WF changes

and the correct handling of time [20,26].

14 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

needlessly exclude instances from migrating to a new schema solely based on the fact that the

respective changes concern loops.

(3) Dangling States (DS). The DS problem arises in conjunction with approaches not distinguish-

ing between activated and started activities (see Fig. 3(3)). As a consequence, very often

such approaches either forbid the deletion of activated activities––what is too restrictive––

or they allow the deletion of already started activities––what leads, for example, to loss of

work.

(4) Order Changing (OC). The OC problem refers to correctly adapting instance markings when

applying order changing operations like parallelization, sequentialization, and swapping of

activities (see Fig. 3(4)).

(5) Parallel Insertion (PI). As opposed to (4) the PI problem arises when inserting a new parallel

branch. Concerning Petri-Nets, for example, after such a change we may have to insert addi-

tional tokens to avoid deadlocks in the sequel (see Fig. 3(5)). The OC and PI problems are

closely related to the dynamic change bug as it has been presented in [28].

In the following we refer to these characteristic problems as the dynamic change problems, and

we show how the diﬀerent approaches supporting adaptive workﬂows deal with them.

3.2. Approaches based on graph equivalence

The approaches discussed in this section base their particular correctness criteria on graph

equivalence [1,28,29,33,34]. Here we can further distinguish between approaches which do [1,34]

and which do not use instance execution histories [28] for checking compliance.

Fig. 3. Five typical problems regarding dynamic workﬂow change.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 15

3.2.1. Approaches not requiring instance execution information

WF Nets. The core idea of the approach presented in [28] is as follows: An instance Ion schema

S(represented by a marked WF Net) is compliant with the modiﬁed schema S0:¼SþD,ifSand

S0are related to each other under given inheritance relations; i.e., either Sis a subclass of S0or vice

versa. In this context, the following two kinds of basic inheritance relations are provided [28]: A

schema Sis a subclass of another schema S0if one cannot distinguish the behaviors of Sand S0(1)

either when only executing tasks of Swhich are also present in S0or (2) when arbitrary tasks of S

are executed but only eﬀects of those tasks are taken into account which are present in S0as well.

Thus, inheritance relation (1) works by blocking and inheritance relation (2) works by hiding a

subset of tasks of S. More precisely, blocking of tasks means that these tasks are not considered

for execution. Hiding tasks implies that the tasks are renamed to the silent task s. (A silent task s

has no visible eﬀects and is used, for example, for structuring purposes.) One example is depicted

in Fig. 5(1) where the newly inserted activities Xand Yare hidden by labeling them to the silent

task s. In addition, further inheritance relations can be achieved by combining hiding and

blocking of WF tasks. Based on these inheritance relations we can state the following correctness

criterion.

Correctness Criterion 1 (Compliance under inheritance relations). Let Sbe a WF schema which is

correctly transformed into another WF schema S0. Then instance Ion Sis compliant with S0if S

and S0are related to each other under inheritance (for a more formal deﬁnition see [28]).

The challenging question is how to ensure Criterion 1. In [28] van der Aalst and Basten present

an elegant way by providing special change operations which automatically preserve one of the

four presented inheritance relations between the original and the changed schema. These change

operations comprise additive and subtractive changes or, more precisely, the insertion and dele-

tion of cyclic structures, sequences, parallel and alternative branches. Let therefore again schema

Sbe transformed into schema S0by change D. In order to check whether Dis an inheritance

preserving change and therefore Sand S0are related under inheritance (cf. Criterion 1) the authors

deﬁne precise conditions with respect to Sand S0.

As an example take the insertion of a cyclic structure Ncinto S(resulting in S0) where Ncand S

have exactly one place in common (see Fig. 4). Then it can be ensured that S0is a subclass of S

when hiding Xand Yin Nc. Checking inheritance of arbitrary WF schemes is PSPACE-complete

Fig. 4. Inheritance preserving change.

16 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

[28]. However, a powerful diagnosis tool called Woﬂan has been developed [28,32] to automati-

cally decide inheritance rules for two given schemes.

As it can be seen from Fig. 5(1), using Criterion 1 it is possible to change already passed WF

regions (CP problem). One problem in this context is to correctly adapt control ﬂow tokens.

However, by using anonymous tokens (i.e., excluding data tokens) the CP problem is simpliﬁed.

Using inheritance relations as described above restricts the set of applicable changes to additive

and subtractive ones. More precisely, there is no adequate inheritance relation based on hiding or

blocking activities when applying an order-changing operation. Consequently, the OC problem

(cf. Fig. 3) is factored out. Nevertheless, van der Aalst and Basten [28] oﬀer an original and very

important contribution by ensuring compliance for many practically relevant changes without

need for accessing instance data.

After having decided whether an instance Ion Sis compliant with S0or not (cf. Criterion 1), we

need rules to adapt the marking of Ion S0. For this purpose, [28] provides transfer rules based on

inheritance relations (cf. Deﬁnition 1). After inserting activities, cyclic structures or alternative

branches, necessary marking adaptations are realized by directly mapping tokens of Sonto S0.

The insertion of parallel branches is more complicated since in some cases we have to insert

Fig. 5. Correctness checking and marking adaptations in [28,29].

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 17

additional tokens to avoid deadlocks. One example is given in Fig. 5(5) where we add one token to

an input place of the parallel join transition.

3.2.2. Approaches using complete execution information

WASA2Activity Nets. WASA2[29,33,34] also uses graph equivalence to state formal correct-

ness for dynamic changes. As opposed to WF Nets WASA2additionally takes instance infor-

mation into account. More precisely, the execution state of an instance is described by its purged

instance graph which is derived from original schema Sby deleting all activities which have not

been started yet and by removing all associated control and data edges.

Formally, a mapping m:VI7!VS0between WF instance I¼ðVI;CI;DIÞand WF schema S0¼

ðVS0;CS0;DS0Þassigns to every instance node n2VIa unique schema node mðnÞ2VS0. With this, the

following correctness criterion based on valid mappings between instance and schema graph can be

stated:

Correctness Criterion 2 (Valid mapping). Let I¼ðVI;CI;DIÞbe a purged WF instance graph

derived from WF schema S¼ðVS;CS;DSÞ. Let further Dbe a change which correctly transforms S

into another schema S0¼ðVS0;CS0;DS0Þ. Then: Iis compliant with S0iﬀ a valid mapping m: VI7!V0

exists; i.e.

ð8i0;j02VS0with 9ði0;j0Þ2CS09i;j2VI:i0¼mðiÞ;j0¼mðjÞ^ði;jÞ2CIÞand vice versa ^

ð8k;l02VS0with 9ðk0;l0Þ2DS09k;l2VI:k0¼mðkÞ;0

l¼mðlÞ^ðk;lÞ2DIÞand vice versa

Intuitively, an instance Ican be migrated to a changed schema S0if each completed activity of I

is also contained in S0and all control and data dependencies existing in Ihave counterparts in S0

(cf. Fig. 6(5)). Criterion 2 can be paraphrased using the notion of schema prefixes [33] which leads

to Criterion 3.

Correctness Criterion 3 (Schema prefix). Let I¼ðVI;CI;DIÞbe a purged WF instance graph

derived from WF schema S¼ðVS;CS;DSÞ. Let further Dbe a change which transforms Sinto

another schema S0¼ðVS0;CS0;DS0Þ. Then: Iis compliant with S0iﬀ Iis a preﬁx of S0, i.e.,

VIVS0,CICS0,DIDS0and 8ðp;qÞ2ðCS0CIÞ[ðDS0DIÞ:q62 VI.

Instance graph I4from Fig. 6(5) is a preﬁx of S0but I3in Fig. 6(4) is not. From Fig. 6(1) we can

see that Criteria 2 and 3 prohibit changes of already passed graph regions. Thus, correct data

provision of activities and consistent instance states are guaranteed. Since WASA2Activity Nets

are acyclic (cf. Section 2.2) the LT problem (cf. Fig. 3) is not present. Details about how Criteria 2

and 3 can be checked and instances be adapted to the changed schema have not been available.

However, a powerful prototype exists. Interestingly, for some cases Criteria 2 and 3 are too

restrictive regarding the OC problem (cf. Fig. 3). An example is depicted in Fig. 6(4) where I3

could be smoothly migrated to S0but no valid mapping between I3and S0exists.

MILANO Nets. Only a special class of schema transformations is considered, namely parall-

elization, sequentialization and swapping of activities [1]. In doing so, special constraints (sum-

marized by the Minimal Critical Speciﬁcation (MCS)) are obeyed for the underlying Sequential

Model (cf. Section 2). For these restricted changes the following correctness criterion is provided:

18 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

Correctness Criterion 4 (Safe states). Let Sbe a WF schema and Ian instance on S. Let further D

be a change which transforms Sinto another correct WF schema S0. Then: Iis compliant with S0if

Iis not in an unsafe state on Sregarding S0. A state of Sis unsafe regarding S0if this state is not

present in S0.

Potential states of Sand S0can be determined by constructing their Sequential Models

(reachability graphs). An example for an instance with unsafe state is depicted in Fig. 7(1). For

such cases MILANO postpones instance migration until the instance will be in a safe state again.

Doing so cultivates the CP problem (cf. Fig. 3). The LT and the PI problem cannot be evaluated

since the underlying WF schemes are acyclic and parallel insertion is not supported (cf. Section

2.1). Parallelization of activities is always allowed, but no details are given how to adapt instance

markings in this context (cf. Fig. 7(5)).

3.3. Approaches based on trace equivalence

In this section we discuss approaches which base dynamic change correctness on trace equiv-

alence (cf. Fig. 2).

Fig. 6. Criteria 2 and 3 [33,34] applied to typical change problems.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 19

3.3.1. Predictive approaches

Flow Nets oﬀer a ﬁrst approach based on trace equivalence [8,9]. In [9], WF instance changes on

Sare carried out by substituting the marked sub-net N1of S, which is aﬀected by D, by another

marked sub-net N2, which reﬂects the modiﬁcations set out by D. Thereby, N1is referred to as the

old and N2as the new change region (cf. Fig. 8(4)). As the authors point out, the selection of the

change regions cannot be ﬁxed. Roughly, the old change region is deﬁned as the smallest marked

sub-net containing all activities aﬀected by D.

For the following considerations, please remember that 

idenotes the initial and 

fthe ﬁnal

marking of S(cf. Section 2.1). Furthermore, we formally deﬁne the FiringSequenceSet (FSS)ofa

schema Sas follows: Let mand m0be two markings on S. Then FSSðS;m;m0Þis the set of all

possible ﬁring sequences leading from mto m0on S.

Correctness Criterion 5 (Pre-change firing sequence). Let Ibe an instance on WF schema Swith

marking mand let x2FSSðS;

i;mÞ. Let further Dbe a change which transforms Sinto another

correct WF schema S0and let m0be the resulting marking of Ion S0. Then Iis compliant with S0iﬀ

•FSSðS;m;

fÞ 6¼;)FSSðS0;m0;

fÞ 6¼;;

•8x02FSSðS0;m0;

fÞ)ðx02FSSðS;m;

fÞ_xx02FSSðS0;

i;

fÞÞ.

Criterion 5 presupposes that the marking m0resulting from the migration of instance Ito the

changed schema S0is known. Then starting from m0it has to be veriﬁed that all ﬁring sequences x0

Fig. 7. Typical change problems in MILANO [1].

20 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

leading from m0to the terminal marking on S0are either producible on Sstarting from mas well

(cf. Fig. 8(1)) or ﬁring sequence xleading to mon Scan be continued on S0by x0(cf. Fig. 8(2)).

Criterion 5 is very interesting in the context of the CP problem (cf. Fig. 3): On the one hand it

allows ‘‘pure’’ changes of the past (cf. Fig. 8(1), i). On the other hand, it forbids changes which

aﬀect both already passed regions and regions which will be entered in the sequel (cf. Fig. 8(1), ii).

Whether Criterion 5 is loop tolerant or not depends on the deﬁnition of the pre-change ﬁring

sequence x(cf. Fig. 8(2)).

Regarding the OC problem (cf. Fig. 3) the authors present two kinds of change operations and

a special change class, the Synthetic Cut-Over Change (SCOC). Applying SCOC, the old change

region N1is maintained in S0together with N2(for an example see Fig. 8(4)); i.e., S0contains two

Fig. 8. Pre-change criterion and SCOC [9] applied to typical change problems.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 21

versions of the modiﬁed subnet. How this ‘‘fusion’’ of old and new change region is carried out

depends on the applied change. In [9] two change scenarios––Upsizing and Downsizing––are

introduced. Upsizing means that N2can ‘‘do more’’ than N1, i.e., the set of all valid ﬁring se-

quences on N1is a subset of all valid ﬁring sequences on N2. Downsizing is the dual counterpart of

upsizing, i.e., N2can ‘‘do less’’ than N1. For example, Fig. 8(4) shows an upsizing. In this case, the

SCOC can be constructed by sticking N1and N2together over ﬂow-jumpers (cf. Fig. 8(4)). Flow-

jumpers are transitions, which map each marking of N1to a marking of N2[8]. This way of

constructing the SCOC in conjunction with upsizing operations is correct regarding Criterion 5.

In the other case––downsizing––the SCOC is constructed by merging N1and N2over one output

place, i.e., instances with tokens in N1are further executed according to the old net.

3.3.2. Using complete history information

WIDE Graphs. A widely-used correctness property is the compliance criterion introduced by [5].

Intuitively, change Dof schema Scan be correctly propagated to WF instance Ion Siﬀ the

execution of I, taken place so far, can be ‘‘simulated’’ on the modiﬁed schema S0as well. Since

WIDE works with a history-based execution model, compliance is based on trying to replay the

execution history PS

Iof instance Ion the changed schema S0. Formally

Correctness Criterion 6 (Restrictive compliance criterion). Let Sbe a WF schema and Ibe a WF

instance on Swith execution history PS

I. Let further Sbe transformed into another schema S0by

change operation D. Then Iis compliant with S0if PS

Ican be replayed on S¼SþDas well, i.e., all

events stored in PS

Icould also have been logged by an instance on S0in the same order as set out

by PS

Criterion 6 forbids changes of the past (cf. Fig. 9(1)). However, it is too restrictive in conjunction

with loops, i.e., it is not loop tolerant as can be seen from Fig. 9(2). Obviously, PS

I2cannot be

produced on S0. Therefore, I2is excluded from migration to S0though there would be no problems

when proceeding execution of I2based on S0. Since [5] gives no information about how to check

Criterion 6, we assume that compliance is ensured by trying to replay the whole execution history

on the changed schema. Thus, we get the necessary marking adaptations automatically when

checking compliance without additional eﬀort. However, doing so causes an overhead due to the

possibly extensive volume of history data which is normally not kept in main memory [18].

Similarly, several other approaches [26,27] exist which propose correctness criteria based on

instance execution information.

3.3.3. Using a consolidated view on the execution history

TRAMs [18] uses Criterion 6 as well. However, replaying each history entry of an instance on

the changed schema is considered as too ineﬃcient, especially when a large number of instances

has to be migrated. Therefore, TRAMs provides migration conditions based on which compliance

of a WF instance with the changed schema can be checked more eﬃciently (cf. Table 1).

Due to the declarative control ﬂow deﬁnition and the absence of explicit control edges, the

insertion of activities is a complex change; i.e., ﬁrst a new activity node Ais inserted and then it is

embedded into the control ﬂow by setting the start conditions of A(‘‘incoming edges’’) and the

intended successors (‘‘outgoing edges’’). Fig. 10(1) depicts the aggregated migration conditions for

22 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

the insertion of two activities and a data dependency between them. Fig. 10(4) shows the par-

allelization of activities. To our best knowledge TRAMs Graphs are acyclic and consequently

problem LT cannot be decided on.

3.3.4. Using model-inherent markings

WSM-Nets. ADEPT [21,24] is based on a correctness criterion which works in conjunction with

loop-related and data ﬂow changes as well. It takes up Criterion 6 but modiﬁes it to be loop-

tolerant. Here, the key to solution is to diﬀerentiate between previous and current/future loop

iterations; i.e., considerations are restricted to the relevant parts of the execution history (cf.

Deﬁnition 1).

Deﬁnition 1 (Reduced Execution History PS

I red ). Let Ibe a WF instance with execution history

I. The reduced execution history PS

I red is obtained as follows: In the absence of loops PS

I red is

identical to PS

I. Otherwise, it is derived from PS

Iby discarding all history entries related to other

loop iterations than the last one (completed loop) or the actual iteration (running loop). (Note

that PS

I red can be easily produced at the presence of nested loops as well.)

Fig. 9. Checking compliance by replaying the complete execution history [5].

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 23

As an example take Fig. 11(2). It shows the reduced execution history of instance I2on S.

Taking Deﬁnition 1 an instance Ion Sis compliant with a changed schema S0iﬀ the reduced

execution history of Ican be produced on S0as well.

Correctness Criterion 7 (Comprehensive compliance criterion). Let Ibe a WF instance on WF

schema Swith execution history PS

Iand reduced execution history PS

I red respectively. Assume

further that change Dtransforms Sinto the correct WF schema S0. Then

•Iis compliant with S0iﬀ PS

I red can be replayed on S0as well.

•In case of compliance the resulting marking of Ion S0is correct.

The challenging question is how to check Criterion 7 without accessing voluminous history

data. To guarantee compliance, for each kind of change ADEPT uses quickly checkable marking

Table 1

Examples of migration conditions in TRAMs (cf. [18])

Change DMigration condition for instance I

Insertion of activity ANone

Modifying start condition scAof activity AðSA62 PS

IÞ_ðSA2PS

I^scAholdsÞ

Deletion of activity AS

A62 PS

Insertion of read (write) data edge for Activity AS

A62 PS

IðEA62 PS

IÞ

Underline: PS

Idenotes execution history of Ion S;SA=EA: start/end event of activity A

Fig. 10. Migration conditions of TRAMs.

24 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

conditions on WSM-Nets. Table 2 exemplarily summarizes conditions for the change operations

applied in Fig. 11.

To eﬃciently adapt markings of compliant instances when migrating them to the changed

schema, ADEPT restricts the necessary re-evaluations to those nodes and edges which constitute

the context of the change region [22]. For each change operation initial node and edge sets to be

evaluated are determined. Depending on the result of their marking evaluation the inspection of

additional nodes and edges may become necessary. In this context, ADEPT beneﬁts from well-

deﬁned marking rules as well as the way node markings are represented in WSM-Nets (preserving

markings of passed regions). As an example take change Din Fig. 11(2). In the course of the

Fig. 11. Analyzing the ADEPT/WSM-Net approach [22–24].

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 25

following adaptation, Xhas to be marked as Activated and marking of Cis re-evaluated to

NotActivated. Both, the migration conditions (cf. Table 2) and the marking adaptation

algorithm have been implemented in a powerful prototype.

3.4. Coping with non-compliant instances

Breeze [25,26] introduces a 3-phase modiﬁcation process for WF schema evolution. The ﬁrst

phase refers to change deﬁnition. In the second one, it is tried to bring the aﬀected instances into

conformity with the changed schema. In doing so, instances are grouped with respect to their

compliance with the changed schema (cf. Criterion 6). For non-compliant instances the compliance

graph is constructed which serves to migrate these instances to the changed schema as well. This

graph consists of compensation activities based on which non-compliant instances are par-

tially rolled back into a compliant state. The third phase handles instance migration. To our

best knowledge, a detailed discussion about how compliance of instances can be checked is

missing.

An alternative approach supporting delayed migrations of non-compliant instances is oﬀered by

Flow Nets [9]. As an example consider Fig. 8(2). Even if instance Ion Sis not compliant with S0

within the actual iteration of a loop, a delayed migration of Ito the new change region is possible

when another loop iteration takes place. ADEPT has adopted this concept and suggests keeping

such (temporarily) non-compliant instances pending to migrate [24].

Finally, in MOKASSIN [13], application programmers as well as users are burdened with the

job to deal with non-compliant WF instances.

Table 2

Examples of migration conditions for WSM-Nets (cf. [24])

Change operation DMigration condition for instance

I(Icompliant with S0() )

Control ﬂow change operations

Dinserts an activity ninsert with associated

control and sync edges

8n2fx2Njninsert !x2ðCtrlE0[SyncE0Þg :

NSðnÞ2fNotActivated;Activated;Skippedg_

ninsert is inserted into an already skipped branch of an

XOR-branching

Data ﬂow change operations

Dinserts a data element dNone

Ddeletes a data element dNo read or write access on dby an activity with state

Running or Completed

Dinserts/deletes a read edge d!nNSðnÞ2fNotActivated;Activated;Skippedg

Dinserts/deletes a write edge n!dNSðnÞ 6¼ Completed

Complex change operations

Dinserts/deletes a set of control or sync

edges AddedEdges/DeletedEdges

8e¼nsrc !ndest 2AddedEdges :NSðndestÞ2

fNotActivated;Activated;Skippedg_

ðNSðndestÞ2fRunning;Completedg^

NSðnsrcÞ¼Completed ^

ðð9ei¼Ensrc ;ej¼Sndest Þ2PS

I red ^i<jÞÞ

26 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

4. Exterminating dynamic change problems––a comparison

As can be seen from Table 3 all presented approaches are based on formal correctness criteria.

Obviously, there is a trade-oﬀ between complexity of the used WF meta model and the ﬂexibility

oﬀered by the system during runtime. The more powerful the meta model is the more complex

dynamic WF changes are to handle. Agostini and De Michelis [1] have realized this in a very early

stage and therefore vote to keep the meta model as simple as possible in order to achieve a

maximum of ﬂexibility. For this reason, for example, loops cannot be modeled in MILANO, but

must be handled dynamically (via backward jumps) if need be. Furthermore, MILANO limits

adaptability to control ﬂow changes, while data ﬂow is managed at the level of single activities.

Obviously, this simpliﬁes the usersÕs view on the process. However, in general, control ﬂow

changes cannot be treated in a isolated manner and independently from data ﬂow and other

workﬂow aspects.

Furthermore, Table 3 gives a comparison of the diﬀerent approaches regarding compliance

checking and marking adaptations. In [28], an elegant way for checking compliance as well as for

automatically adapting instance markings is presented. WASA2[34] does not explicitly provide

compliance checks. We assume that a valid mapping (cf. Deﬁnition 2) is determined by comparing

nodes, control ﬂow and data ﬂow edges of the purged instance graph for each instance. Though

both, replaying whole execution history (WIDE) and checking migration conditions (TRAMs,

ADEPT) can be done with the same complexity, generally, there is a giant diﬀerent in real eﬀort.

Reason is that one has to cope with probably extensive data [18] usually not kept in primary

storage. However, replaying the complete history information on the changed schema [5] we get

the necessary instance markings free to the door whereas in ADEPT, for example, a marking

adaptation algorithm has to be applied.

Table 4 compares the diﬀerent approaches from Fig. 1 with respect to their ability to solve the

dynamic change problems (cf. Fig. 3).

(1) Changing the Past (CP). From Fig. 4 it can be seen that all Petri-Net based approaches with

True-Semantics (WF Nets, MILANO Nets, and Flow Nets) allow changes of already passed

regions of an instance. As mentioned in Section 3 doing so may cause two problems––incomplete

input data when invoking activities and inconsistent instance execution. Such problems have been

Table 3

Comparison of meta models, correctness criteria and marking adaptation

Expressiveness Completeness

of changes

Formal

criteria

Compliance

checks

Marking

adaptations

General Loops DF

WF Nets + + n.a. )+++ +

WASA2+ n.a. + + + n.a. n.a.

MILANO n.a. n.a. )+ n.a. n.a.

Flow Nets + + + + + n.a. +

WIDE + + + + + + +

Breeze 0 n.a. + + 0 n.a. n.a.

TRAMs + n.a. + + 0 + n.a.

ADEPT 0 + + + + + +

DF: data ﬂow; n.a.: ‘‘not addressed’’; : ‘‘simplicity issues’’.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 27

partially factored out in the presented approaches since data ﬂow is not considered. As an

example take instance I1on S0in Fig. 5(1). Obviously, the newly inserted activity Xwill never be

executed, i.e., the execution state of I1is not clearly deﬁned. Assume that WF Nets do not exclude

data ﬂow and therefore activities Xand Ycan be inserted with the data dependency between them

(see Fig. 5(1)). This change would be considered as insertion of a parallel branch (projection

inheritance) and a token be added to place data, but with unclear data semantics. Interestingly,

this problem is excluded by Flow Nets since common changes of the past and the future are

forbidden (cf. Fig. 8(1), ii). Therefore, only the problem of inconsistent instance execution states

remains.

(2) Loop Tolerance (LT). Many of the presented approaches use acyclic WF models whereby

problem LT is factored out. The exclusion of loops, however, is out of touch with practical

requirements. As discussed in Section 3, it depends on the exact deﬁnition of the pre-change ﬁring

sequence (cf. Criterion 5) whether Flow Nets are loop-tolerant or not. Anyway, Criterion 6 is too

restrictive in conjunction with loops. Therefore ADEPT uses Criterion 7, which is loop-tolerant.

(3) Dangling States (DS). This problem of being unable to distinguish between activated and

running activities is mainly present in Petri-Net based approaches. Transitions usually represent

real-world tasks and consume a certain piece of time. If one of them is deleted the challenging

question is how to handle in-progress work associated with this transition. In contrast, ap-

proaches which explicitly diﬀer between activity states Activated and Running like WASA2,

TRAMs and ADEPT take care of this and ensure that running activities are not disturbed by

dynamic changes.

(4) Order-Changing (OC). This problem appears in conjunction with correctness criteria where

certain WF instances are needlessly excluded from migrating to the changed schema. As shown in

Section 3.2.2, strict graph equivalence is too restrictive in certain cases.

(5) Parallel-Insertion (PI). This problem refers to the necessary marking adaptations when

inserting a parallel branch such that no deadlocks occur. The only Petri-Net based approach

which presents concrete adaptation rules in this context is oﬀered by WF Nets. The suggested

strategies ensure a correct control ﬂow in the sequel. However, with respect to data ﬂow,

semantics of the newly inserted tokens remains unclear. In ADEPT, markings are automatically

adapted when migrating compliant instances to the changed schema. The respective algorithms

[22] are based on the marking and execution rules of WSM Nets with their True/False-Semantics.

Table 4

Comparison by means of ﬁve typical change problems (cf. Fig. 3)

(1) CP (2) LT (3) DS (4) OC (5) PI

WF Nets Possibly critical + Possibly critical + +

WASA2Prevented )Prevented 0 +

MILANO Possibly critical )Possibly critical + )

Flow Nets Possibly critical ? Possibly critical + +

WIDE Prevented )Possibly critical + +

Breeze Prevented )?++

TRAMs Prevented )Prevented + +

ADEPT Prevented + Prevented + +

28 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

5. Change scenarios and their realization in existing approaches

In the previous sections emphasis has been put on fundamental correctness issues related to

dynamic WF changes. So far it has been circumstantial whether a single WF instance or a col-

lection of instances is subject to change. In this section we have a closer look at diﬀerent change

scenarios and related requirements. We provide a short categorization of adaptive research WF

engines which includes Chautauqua [10], WASA2[34], Breeze [26], and ADEPT [21] whose basics

have been already described in Sections 2–4. In addition, we consider the respective approaches

followed by AgentWork [20], EPOS [19], and DYNAMITE [12] as well as the ﬂexibility oﬀered by

commercial tools.

5.1. Changes of single WF instances

Adaptations of single WF instances become necessary when exceptional situations occur or the

structure of a WF dynamically evolves. Both scenarios can be found, for example, in hospital and

engineering environments [12,20]. Besides state-related correctness properties instance-speciﬁc

changes pose several challenging issues. In particular, change predictability inﬂuences the way how

WF instances are adapted during runtime. Regarding evolving workﬂows, for example, necessary

changes and their scope are often known at buildtime [12,19,20]. Consequently, respective

adaptations can be pre-planned and automated. In contrast ad-hoc changes have to be applied as

response to unforeseen exceptions [21]. Usually, user interaction becomes necessary in order to

deﬁne the respective runtime change. Of course, we cannot always see WF instance changes in

terms of black and white, but the distinction between pre-planned and ad-hoc change contributes

to classify existing approaches.

5.1.1. Approaches supporting ad-hoc instance changes

In Breeze and WASA2, instance changes can be deﬁned by the use of a graphical WF editor.

Using a WF editor for change deﬁnition, however, is only conceivable for expert users. If changes

shall be deﬁnable by end users as well, application-tailored user interfaces must be oﬀered to them.

Obviously, this requires comprehensive programming interfaces. Only few approaches provide

such interfaces [21,34]. ADEPT, for example, oﬀers a change API which enables change deﬁnition

on WSM Nets at a high semantic level, e.g., to jump forward in the ﬂow or to insert a new step

between two sets of activities [21]. Very important in this context is to ensure that none of the

guarantees which have been achieved by formal checks at buildtime are violated due to the ad hoc

change. Note that this does not only require compliance checks and marking adaptations, but also

checks with impact to correctness properties of the WF schema itself (e.g. regarding data ﬂow).

Therefore ADEPT uses well-deﬁned correctness properties for WF models, formal pre- and

postconditions for change operations, and advanced change protocols [21].

5.1.2. Approaches supporting pre-planned instance changes

Support for automatic WF changes is provided by AgentWork [20], DYNAMITE [12], and

EPOS [19], but may be realizable on top of adaptive WfMS like WASA2, ADEPT, or InConcert

as well. The overall aim is to reduce error-prone and costly manual WF adaptations. In order to

realize automatic WF adaptations, ﬁrstly, the WfMS must be able to detect logical failures in

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 29

which WF instance changes become necessary. Second, it must determine necessary adaptations,

identify the instances to be adapted, correctly introduce the change to them, and notify respec-

tive users. This poses many additional issues ranging from the consistent speciﬁcation of pre-

planned changes at buildtime up to their concrete realization during runtime. Existing approaches

supporting automatic WF instance changes can be classiﬁed according to diﬀerent criteria. The

most important one concerns the basic method used for automatic failure detection and for

change realization. We distinguish between rule-based, process-driven, and goal-based ap-

proaches.

Rule-based approaches use ECA (Event/Condition/Action) models to automatically detect

logical failures and to determine necessary WF changes. However, most of them limit adaptations

to currently executed activities [4,6]. In contrast, AgentWork [20] enables automatic adaptations

of the yet unexecuted regions of running WF instances as well. Basic to this is a temporal ECA

rule model which allows to specify adaptations at an abstract level and independently of concrete

WF models. When an ECA rule ﬁres, temporal estimates are used to determine which parts of the

running WF instance are aﬀected by the detected exception. Respective WF regions are either

adapted immediately (predictive change) or––if this is not possible––at the time they are entered

(reactive change).

Goal-based approaches formalize process goals (e.g., process outputs). In ACT [3], necessary

instance adaptations (e.g., substituting the failed activity by an alternative one) are automatically

performed if an activity failure leads to goal violation. EPOS [19], in addition, automatically

adapts WF instances when process goals themselves change. Both approaches apply planning

techniques to automatically ‘‘repair’’ workﬂows in such cases. However, current planning

methods do not provide complete solutions since important aspects (e.g., treatment of loops) are

not considered.

Process-driven approaches restrict the possible variants of WF schemes as well as WF changes in

advance. DYNAMITE, for example, uses graph grammars and graph reduction rules for this [12].

Automatic adaptations are performed depending on the outcomes of previous activity executions.

Interestingly, process-driven as well as goal-based approaches have been primarily applied in the

ﬁeld of engineering workﬂows. Both DYNAMITE and EPOS provide build-in functions to

support dynamically evolving WF instances.

Instance-speciﬁc changes pose several other challenges. For example, one must decide on the

duration of an instance change. Concerning loop-related adaptations, ADEPT diﬀerentiates be-

tween loop-permanent and loop-temporary changes [21]. The latter are only valid for the current

loop iteration. The handling of such temporary changes is not trivial since permanent changes

must not depend on them in order to avoid potential errors. AgentWork [20] even follows a more

advanced approach by allowing rule designers to specify temporal constraints indicating how long

WF adaptations shall be valid.

5.1.3. Ad-hoc changes in commercial tools

Production WFMS like WebSphere MQ Workﬂow and Staﬀware [14] provide powerful process

support functions but tend to be very inﬂexible. Particularly, ad-hoc changes of running WF

instances are not supported. Unlike these WFMS, engines such as TIBCO InConcert, SER

Workﬂow, and FileNet Ensemble allow on-the-ﬂy adaptations of in-progress instances. For

example, users may dynamically insert or delete activities for a given instance in such a way that

30 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

the past of this instance cannot be changed.

Though ad-hoc WFMS provide high ﬂexibility, they

have failed to adequately support end users. Particularly, they do not support them in deﬁning

changes and in dealing with potential side-eﬀects resulting from them (e.g., missing input data of

an activity due to the deletion of a preceding step). Since one cannot expect from the end user to

cope with such problems, this increases the number of errors and therefore limits the practical

usability of respective WFMS.

Case handling systems like FLOWer (Pallas Athena) [30] try to address ﬂexibility issues from

another viewpoint. Unlike traditional WFMS, case handling provides a higher operational ﬂex-

ibility and aims at avoiding dynamic changes. More precisely, users are allowed to inspect, add or

modify data elements before the activities, which normally produce them, are started. Conse-

quently, the decision about which activities can be executed next is based on the available data

rather than on information about the activities executed so far. Since FLOWer allows to dis-

tinguish between optional and mandatory data elements, a broad spectrum of processes can be

covered with this data-driven approach. FLOWer also enables the deﬁnition of causal depen-

dencies between activities. The question remains, whether this mixed view on processes (process-

driven, data-driven) contributes to completely avoid dynamic changes.

5.2. Workﬂow type changes and change propagation

WF schema changes at the type level may become necessary, for example, to adapt business

processes to a new law or to realize process optimizations. In any case we are confronted with the

problem of how to migrate a potentially large number of WF instances I1;...;Inrunning on the

old schema Sto the new schema S0. Basically, things seem to be the same as for dynamic changes

of single WF instances. However, in addition, we are confronted with the problem that the WF

type change may have to be propagated to WF instances whose current execution schema

SI:¼SþDdoes not completely correspond to S(due to a previous instance change D). To ex-

clude such instances from migrating to the new schema S0, however, is out of touch with reality,

particularly in case of long-running ﬂows. Interestingly, none of the WF engines supporting WF

type changes and change propagation has dealt with this problem so far. In WASA2, for example,

individually modiﬁed instances cannot be further adapted to later type change. Chautauqua [10]

even does not support changes of single instances at all, since instances of a particular type are

always connected to the same Flow Net.

Usually, commercial WfMS do not allow change propagation to in-progress instances when a

WF schema is modiﬁed at the type level. Instead, simple versioning concepts are used to ensure

that already running instances can be ﬁnished according to the old schema. One exception is

oﬀered by Staﬀware [14]. However, there are several critical aspects arising in this context. For

example, running activities can be deleted without any user information. If the deleted activity is

ﬁnished the returned results disappear to the nirvana. Furthermore, Staﬀware suﬀers from the CP

problem which may lead to missing input data and activity program crashes at runtime. Finally,

Staﬀware is by far too restrictive (e.g., insertions before activated tasks are forbidden).

In order to avoid undesired side-eﬀects on other cases, for each instance a private schema is kept.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 31

6. Summary

In this paper we have systematically compared approaches supporting adaptive workﬂows. We

have elaborated their strengths and weaknesses along typical dynamic change problems. In doing

so, main emphasis has been put on model properties and correctness criteria since they provide the

basis for any adaptive WfMS. Furthermore we have sketched diﬀerent change scenarios and

categorized existing approaches supporting them. Though there has been substantial progress in

the ﬁeld of adaptive WfMS during the last years, there is still enough room for further research.

Particularly, usability and implementation issues have not been addressed in suﬃcient detail.

Furthermore, many non-trivial interdependencies among diﬀerent kind of changes exist which

must be carefully understood before we come to a complete solution. For example, current

adaptive WfMS do not allow propagating WF type changes to individually modiﬁed WF in-

stances. As discussed, however, this is very important for the adequate support of long-running

workﬂows [22].

References

[1] A. Agostini, G. DeMichelis, Improving ﬂexibility of workﬂow management systems. In: BPMÕ00, LNCS, vol. 1806,

2000, pp. 218–234.

[2] A. Agostini, G. DeMichelis, A light workﬂow management system using simple process models, Int. J. Collab.

Comp. [16] 335–363.

[3] C. Beckstein, J. Klausner, A planning framework for workﬂow management, in Proceedings of Workshop

Intelligent Workﬂow and Process Management, Stockholm, 1999.

[4] F. Casati, S. Ceri, S. Paraboschi, G. Pozzi, Speciﬁcation and implementation of exceptions in workﬂow

management systems, ACM TODS 24 (3) (1999) 405–451.

[5] F. Casati, S. Ceri, B. Pernici, G. Pozzi, Workﬂow evolution, Data and Knowledge Engineering 24 (3) (1998) 211–

238.

[6] D. Chiu, Q. Li, K. Karlapalem, Web interface-driven cooperative exception handling in ADOME, Informations

Systems 26 (2) (2001) 93–120.

[7] D. Edmond, A.H.M. ter Hofstede, A reﬂective infrastructure for workﬂow adaptability, Data and Knowledge

Engineering 34 (3) (2000) 271–304.

[8] C. Ellis, K. Keddara, A workﬂow change is a workﬂow, in: BPM Õ00, LNCS, vol. 1806, 2000, pp. 516–534.

[9] C.A. Ellis, K. Keddara, G. Rozenberg, Dynamic change within workﬂow systems, in: Proceedings of International

ACM Conference COOCS Õ95, Milpitas, CA, August 1995, pp. 10–21.

[10] C.A. Ellis, C. Maltzahn, The Chautauqua workﬂow system, in: Proceedings of the International Conference on

System Science, Maui, HI, 1997.

[11] H.J. Genrich, P.S. Thiagarajan, A theory of bipolar synchronization schemes, Theoret. Comput. Sci. 30 (3) (1984)

241–318.

[12] P. Heimann, G. Joeris, C. Krapp, B. Westfechtel, DYNAMITE: dynamic task nets for software process

management, in: Proceedings of the 18th International Conference Software Engineering (ICSE), Berlin, March

1996, pp. 331–341.

[13] G. Joeris, O. Herzog, Managing evolving workﬂow speciﬁcations, in: Proceedings of International Conference on

CoopIS Õ98, New York City, 1998, pp. 310–321.

[14] B. Kiepuszewski, Expressiveness and suitability of languages for control ﬂow modelling in workﬂows, Ph.D.

Thesis, Queensland University of Technology, Brisbane, 2002. Available from <http://www.tm.tue.nl/it/research/

patterns>.

[15] B. Kiepuszewski, A.H.M. ter Hofstede, C.J. Bussler, On structured workﬂow modelling, in: CAiSEÕ00, LNCS, vol.

1789, 2000, pp. 431–445.

32 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34

[16] M. Klein, C. Dellarocas, A. Bernstein (Eds.), Int. J. Collab. Comp. 9 (3–4) (2000) 346–456 (Special issue on

adaptive workﬂow systems).

[17] K. Kochut, J. Arnold, A. Sheth, J. Miller, E. Kraemer, B. Arpinar, J. Cardoso, IntelliGEN: a distributed

workﬂow system for discovering protein–protein interactions, Distrib. Parallel Databases 13 (1) (2003) 43–

72.

[18] M. Kradolfer, A. Geppert, Dynamic workﬂow schema evolution based on workﬂow type versioning and workﬂow

migration, in: CoopIS Õ99, Edinburgh, 1999, pp. 104–114.

[19] C. Liu, R. Conradi, Automatic replanning of task networks for process model evolution, in: Proceedings

of European Software Engineers Conference, Garmisch-Partenkirchen, Germany, 1993, pp. 434–450.

[20] R. M€

uller, Event-oriented dynamic adaptation of workﬂows. Ph.D. Thesis, University of Leipzig, Germany,

2002.

[21] M. Reichert, P. Dadam, ADEPTflex-supporting dynamic changes of workﬂows without losing control, JIIS 10 (2)

(1998) 93–129.

[22] M. Reichert, S. Rinderle, P. Dadam, On the common support of workﬂow type and instance changes under

correctness constraints, in: CoopIS Õ03, LNCS, vol. 2888, Catania, Italy, 2003, pp. 407–425.

[23] S. Rinderle, M. Reichert, P. Dadam, Evaluation of correctness criteria for dynamic workﬂow changes, in: BPMÕ03,

LNCS, vol. 2678, Eindhoven, The Netherlands, 2003, pp. 41–57.

[24] S. Rinderle, M. Reichert, P. Dadam, Flexible support of team processes by adaptive workﬂow systems, Distribut.

Parallel Databases 2004 (to appear).

[25] S. Sadiq, Handling dynamic schema changes in workﬂow processes, in: Proceedings of the 11th Australian

Database Conference 2000.

[26] S. Sadiq, O. Marjanovic, M. Orlowska, Managing change and time in dynamic workﬂow processes, IJCIS 9 (1–2)

(2000) 93–116.

[27] W.M.P.v.d. Aalst, Exterminating the dynamic change bug: a concrete approach to support worfklow change,

Inform. Syst. Frontiers 3 (3) (2001) 297–317.

[28] W.M.P.v.d. Aalst, T. Basten, Inheritance of workﬂows: an approach to tackling problems related to change,

Theoret Comp. Sci. 270 (1–2) (2002) 125–203.

[29] W.M.P.v.d. Aalst, M. Weske, G. Wirtz, Advanced topics in workﬂow management: Issues, requirements, and

solutions, Int. J. Integrat. Design Process Sci. 7 (3) (2003).

[30] W.M.P.v.d. Aalst, P. Berens, Beyond workﬂow management: product-driven case handling, in: Proceedings of the

Conference on Supp. Group Work, New York, 2001, pp. 42–51.

[31] W.M.P.v.d. Aalst, S. Jablonski (Eds.), Flexible workﬂow technology driving the networked economy, Int. Comp.

Syst.: Sci. Eng. 15 (5) (2000).

[32] H.M.W. Verbeek, W.M.P.v.d. Aalst, Woﬂan 2.0 A petri-net-based workﬂow diagnosis tool, in: ICATPN Õ00,

LNCS, vol. 1825, pp. 455–464, Aarhus, June 2000.

[33] M. Weske, Workﬂow management systems: Formal foundation, Conceptual design, implementation aspects,

University of M€

unster, Germany, 2000. Habilitation Thesis.

[34] M. Weske, Formal foundation and conceptual design of dynamic adaptations in a workﬂow management system,

in: HICSS-34, 2001.

Stefanie Rinderle studied Mathematics and Economy at the University of Augsburg, Germany. At present she

is a Ph.D. candidate of the Databases and Information Systems Department of the University of Ulm,

Germany. Her research interests include change management in adaptive workﬂow management systems,

workﬂow schema evolution, and business process modeling.

S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34 33

Peter Dadam has been full professor at the University of Ulm and director of the Department Databases and

Information Systems since 1990. Before he came to the University he had been director of the research

department for Advanced Information Management (AIM) at the IBM Heidelberg Science Center (HDSC).

At the HDSC he managed the AIM-P project on advanced database technology and applications. Current

reserach areas include distributed, cooperative information systems, workﬂow management, and database

technology and its use in advanced application areas.

Manfred Reichert is assistant professor at the Department Databases and Information Systems at the Uni-

versity of Ulm. He ﬁnished his Ph.D. thesis on adaptive workﬂow systems in May 2000. Current research

topics include enterprise-wide workﬂows, enterprise application integration and workﬂow, process visuali-

zation, and diﬀerent aspects related to workﬂow technology.

34 S. Rinderle et al. / Data & Knowledge Engineering 50 (2004) 9–34