On the Common Support of Workflow Type and Instance Changes under Correctness Constraints [original]

On the Common Support of Workﬂow Type and

Instance Changes under Correctness Constraints

Manfred Reichert, Stefanie Rinderle, and Peter Dadam

University of Ulm, Computer Science Faculty,

Dept. Databases and Information Systems

{reichert, rinderle, dadam}@informatik.uni-ulm.de

Abstract. The capability to rapidly adapt in-progress workﬂows (WF)

is an essential requirement for any workﬂow system. Adaptations may

concern single WF instances or a WF type as a whole. Especially for

long-running business processes it is indispensable to propagate WF

type changes to in-progress WF instances as well. Very challenging in

this context is to correctly adapt a (potentially large) collection of WF

instances, which may be in diﬀerent states and to which various ad-hoc

changes may have been previously applied. This paper presents a generic

framework for the common support of both WF type and WF instance

changes. We establish fundamental correctness principles, position for-

mal theorems, and show how WF instances can be automatically and

eﬃciently migrated to a modiﬁed WF schema. The adequate treatment

of conﬂicting WF type and WF instance changes adds to the overall com-

pleteness of our approach. By oﬀering more ﬂexibility and adaptability

the so promising WF technology will ﬁnally deliver.

1 Introduction

In real-world environments people are expected to ﬂexibly deal with exceptions.

Though they are trained to do so, this role is purely integrated with current

WF technology [1]. Either ad-hoc deviations from the modeled WF schema are

completely prohibited, thus requiring to bypass the WF system in exceptional

situations, or they may cause severe problems [2]. Ad-hoc adaptations of single

WF instances [2,3,4], however, represent only one kind of dynamic change. In

order to support evolutionary changes, adaptations may have to be applied at

the WF type level as well [3,5,6,7,8,9]. In principle, a WF type change can be

accomplished by modifying the respective WF schema accordingly. In doing so,

in-progress WF instances must not get into trouble due to the change. This

could be achieved by ﬁnishing them according to the old schema whereas future

instances are created from the new one. Obviously, this simple approach is only

suﬃcient for workﬂows with short duration, but raises problems in conjunction

with long-running processes. Therefore, very often it is desired to propagate a

This work was done within the research project “Change management in adaptive

workﬂow systems”, which is funded by the German Research Community (DFG).

R. Meersman et al. (Eds.): CoopIS/DOA/ODBASE 2003, LNCS 2888, pp. 407–425, 2003.

Springer-Verlag Berlin Heidelberg 2003

408 M. Reichert, S. Rinderle, and P. Dadam

type change ∆, which transforms the actual schema S into a new one, to in-

progress WF instances as well. Very challenging in this context is to correctly

adapt a (potentially large) collection of WF instances, which may be in diﬀerent

states and to which various ad-hoc changes may have been previously applied. In

the latter case, we have to deal with the problem that ∆shall be propagated to

WF instances whose current execution schema does not completely correspond

to the original schema S. Nevertheless, such “biased” WF instances must not be

needlessly excluded from change propagation.

In our previous work, we dealt with ad-hoc changes of single WF instances

and related WF graph transformations [2]. The main emphasis was put on im-

plementation and usability issues. The objective of this paper is to develop a for-

mal framework for both the propagation of WF type changes to already running

WF instances and ad-hoc changes of single WF instances. We present diﬀerent

change scenarios and have a look at fundamental principles concerning the de-

sign of adaptive WF models. For this, we establish basic correctness principles

and position formal theorems. Taking a simple, but powerful WF meta model,

we exemplarily show how correctness can be eﬃciently checked and which in-

formation is needed for this. In addition, we introduce well-deﬁned rules and

procedures for migrating WF instances to a modiﬁed schema.

Section 2 sketches the WF meta model, which we use in this paper to illus-

trate fundamental principles of our approach. However, the presented approach

is applicable in conjunction with comparable WF meta models as well. Section

3 develops our approach for dynamic WF changes, focusing on general correct-

ness principles as well as on implementable rules for ensuring correctness when

a change is applied. Section 4 deals with conﬂicting changes at the type and

instance level, and it shows under which conditions WF type changes may be

propagated to biased WF instances as well. We discuss related work in Section

5 and conclude with a summary in Section 6.

2 WF Modeling and Execution Basics

For each business process to be supported a WF type T has to be deﬁned. It is

represented by a WF schema graph S of which diﬀerent versions V1, ..., Vnmay

exist (reﬂecting the evolution of T). To simplify matters, we assume that there

is only one version Vnfrom which new WF instances can be created. This is

not really required. However, in the present paper we put the focus on formal

considerations and do not deal with versioning issues in more detail.

2.1 Modeling and Execution of Workﬂows

A WF schema comprises a set of activities and deﬁnes the control and data ﬂow

between them. Control ﬂow is modeled by linking activities with control edges,

which may be optionally associated with transition conditions. The use of control

edges must not lead to cyclic order relationships since this may cause deadlocks

at runtime (see below). Depending on the deﬁned control edges and the chosen

On the Common Support of Workﬂow Type and Instance Changes 409

NS = ACTIVATED NS = RUNNING ES = TRUE_SIGNALED

NS = SKIPPED NS = COMPLETED ES = FALSE_SIGNALED

lab test

prepare calc. dose give drug

another cycle?

age dose weight

age > 40

continue = true

b) Execution History of I

START(admit),

END(admit; write(age,25)),

START(send notice),

END(send notice),

START(prepare,1st),

END(prepare; write(weight,75)),

START(calc.dose; read(weight,75)),

END(calc.dose; write(dose,100)),

START(give drug; read(dose,100)),

END(give drug), START(another cycle?),

END(another cycle?, true),

START(prepare,2nd),

END(prepare; write(weight,72)),

START(calc.dose; read(weight,72)),

END(calc.dose; write(dose,90))

a) Instance I with Schema Graph S(T,V) and Marking M

S(T

data

element

transition condition

read data

link

loop egde

continue

control edge

write data

link

end notice

admit

Fig. 1. WF Instance Example

transition conditions, sequences, parallel branchings, and conditional branchings

can be described. For the modeling of loop backs, an additional edge type (loop

backward edge) is provided, which allows us to distinguish between “undesired”

and “desired” cycles. To simplify matters, we assume that an activity must

not have more than one outgoing loop edge and that the activity nodes which

constitute the loop body are well-deﬁned (cf. Def. 1). Finally, data ﬂow between

activities is realized by connecting them with global data elements. For this, read

and write data edges are provided. An example is depicted in Fig. 1. Formally:

Deﬁnition 1 (WF Schema Graph). A tuple S with S = (N, D, CtrlEdges,

LoopEdges, DataEdges, EC) is called a WF schema graph, if the following holds:

–N is a set of activities and D a set of data elements

–CtrlEdges ⊂N×N is a precedence relation

(notation: nsrc →ndst ≡(nsrc,n

dst)∈CtrlEdges)

–LoopEdges ⊂N×N is a set of loop backward edges

–DataEdges ⊆N×D×{read, write}is a set of read/write data links between

activities and data elements

–EC: CtrlEdges ∪LoopEdges → Conds(D) where Conds(D) denotes the set

of all valid transition conditions on data elements from D.

such that

1. Sfwd = (N, CtrlEdges) is an acyclic graph

2. ∀(n1,n

2)∈LoopEdges: n2∈pred(S, n1)

3. ∀(n1,n

2)∈LoopEdges: succ(S, n2)⊆Lbody(n1,n

2)∪succ(S, n1)∧

pred(S, n1)⊆Lbody(n1,n

2)∪pred(S, n2)

4. ∀(n1,n

2),(m1,m

2)∈LoopEdges: n1=m1

The sets pred(S,n)/succ(S,n) comprise all direct and indirect predeces-

sors/successors of n via control edges and Lbody(n1,n

2):= succ(S, n2)∩pred(S,

n1)∪{n1,n

2}.

410 M. Reichert, S. Rinderle, and P. Dadam

The status of a single WF activity is initially set to NOT ACTIVATED. When all pre-

conditions for activity execution are met (see below), it changes to ACTIVATED.

The activity is then either started automatically or corresponding work items

are inserted into user worklists. When starting execution, activity status changes

to RUNNING and the associated application component is invoked. Finally, at

successful termination, status passes to COMPLETED.

Execution of a newly created WF instance starts with those activities that

have no incoming control edge. When completing an activity, its outgoing edges

are either evaluated to TRUE SIGNALED or FALSE SIGNALED, depending on their

transition conditions. This, in turn, leads to re-evaluation of target activities.

Generally, an activity may be activated as soon as all incoming edges have been

signaled and at least of them is marked with TRUE SIGNALED. Consequently,

if all incoming edges are marked as FALSE SIGNALED, the activity cannot be

executed anymore. Its status is then set to SKIPPED, which may lead to cascaded

skipping of subsequent activities. A loop edge is evaluated whenever its source

activity terminates. If the associated loop condition evaluates to true, outgoing

control edges will not be evaluated, the loop edge will be signalled, and all

nodes contained within the loop body will be reset to their initial state. Finally,

execution of a WF instance will terminate if all activities are in one of the states

COMPLETED or SKIPPED.

Each WF instance Iis associated with a schema S = S(T,V), where T denotes

the WF type of Iand V the version of the WF schema graph to be taken for ex-

ecution. (Note that other WF instances may be based on S as well). The control

state of Iis captured by a marking function MS=(NS, ES). It assigns to each

activity n its current status NS(n) and to each control and loop edge its mark-

ing ES(e) (cf. Fig. 1). These markings are determined according to the rules de-

scribed above, whereas markings of already passed regions and skipped branches

are preserved (except loop backs). Concerning data elements, diﬀerent versions

of a data object may be stored, which is important for the context-dependent

reading of data elements and the handling of (partial) rollback operations.

Deﬁnition 2 (WF Instance). A WF instance Iis deﬁned by a tuple (T, V,

MS(T,V ),Val

S(T,V ),H) where

–T denotes the WF type of Iand V the version of the schema graph S :=

S(T,V) = (N, D, CtrlEdges, LoopEdges, ...) according to which Iis executed.

–MS=(NSS,ES

S) reﬂects the current marking of nodes NSS:N→ NodeStates

and edges ESS: CtrlEdges ∪LoopEdges → EdgeStates

–ValSis a function on D. Val

S(d)reﬂects for each data element d ∈D either

its current value or the value UNDEFINED (if d has not been written yet).

–H=<e

0,...,e

k>is the execution history of I. It logs information about

start / completion of activities. For each started activity X the values of the

data elements read by X and for each completed activity Y the values of the

data elements written by Y are logged (logical view).

As described above, WF instances preserve their markings when proceeding in

the ﬂow of control. Thus MSalways reﬂects a consolidated view of the previous

On the Common Support of Workﬂow Type and Instance Changes 411

execution of I. As we will see later, this property is very useful in connection

with dynamic WF instance changes. Formally:

Lemma 1 (Preserving Instance Markings). Let Ibe a WF instance with

schema graph S = (N, D, ...) and marking MS= (NS, ES). Further, let x ∈N

be an arbitrary activity node with NS(x) ∈{COMPLETED,SKIPPED}. Then:

∀n∈pred(S, x): NS(n) ∈{COMPLETED,SKIPPED}.

2.2 Deﬁning and Changing Schema Graphs

Table 1 contains some primitives that can be used to deﬁne and modify schema

graphs. Each primitive has a well-deﬁned semantics and is associated with for-

mal pre-/post-conditions, necessary to preserve (structural) correctness of the

respective schema (cf. Def. 1). In this paper, we exemplarily restrict our consid-

erations to the avoidance of deadlocks that may be caused due to cyclic order

relationships (via control edges). Generally, additional constraints exist. Con-

cerning data ﬂow, for example, no lost updates must occur during runtime and

all data elements read by an activity must always have been written by preceding

activities, independently of chosen execution branches. There are other primi-

tives (e.g., to update edge conditions), which we do not consider in the following.

Finally, change primitives serve as basis for deﬁning high-level operations (e.g.,

to shift an activity from its current to another position) and for deriving formal

conditions for them. However, this is outside the scope of this paper.

Table 1. Examples of Basic Change Primitives

addCtrlEdge(S, nsrc,ndst)Pre: (nsrc ∈ succ(S, ndst)∪{ndst})∧(∀(n1,n2)∈LoopEdges:

[nsrc ∈Lbody (n1,n2)⇔nsrc ∈Lbody(n1,n2)])

Post: CtrlEdges’ = CtrlEdges ∪{nsrc →ndst}

addActivity(S, nins, Preds, Succs) Pre: (∀p∈Preds, ∀s∈Succs: s ∈ pred(S, p)) ∧

(∀(n1,n2)∈LoopEdges:

(Preds ∪Succs) ⊆Lbody(n1,n2)∨

(Preds ∪Succs) ∩Lbody(n1,n2)=∅

Post: N’ = N ∪{nins}

CtrlEdges’ = CtrlEdges ∪{p→nins |p∈Preds}

∪{nins →s|s∈Succs}

deleteCtrlEdge(S, nsrc,ndst)Post: CtrlEdges’ = CtrlEdges ¬{nsrc →ndst}

deleteActivity(S, ndel)Post: N’ = N ¬{ndel}

CtrlEdges’ = CtrlEdges ¬{a→b|ndel ∈{a, b}} ∪

{p→s with EC(p →s)=ec|

p→ndel,ndel →s∈CtrlEdges ∧EC(ndel →s)=ec}

3 Dynamic Change Basics

In this section, we present issues related to dynamic change correctness in a

formal and rigorous style. Due to lack of space, we restrict our considerations to

changes deﬁnable by the primitives from Table 1. First of all, we do not make a

412 M. Reichert, S. Rinderle, and P. Dadam

diﬀerence between changes of single instances and adaptations of a collection of

instances (e.g., due to a type change). Instead we focus on fundamental issues

related to dynamic instance changes. In the following, let Ibe an instance with

schema graph S and marking MS. Assume that S is transformed into a correct

schema graph S’ by applying change ∆. Two challenging issues arise:

1. Can ∆be correctly propagated to I, i.e., without causing errors or inconsis-

tencies? For this case, Iis said to be compliant with S’.

2. Assuming Iis compliant with S’, how can we smoothly migrate it to S’

such that its further execution can be based on S’? Which state (marking)

adaptations become necessary in this context?

We will show that these two issues are fundamental for the design of any adap-

tive WF model. While the ﬁrst one concerns pre-conditions on the state of I, the

second issue is related to post-conditions that must be satisﬁed after the change

has been applied. In any case, we have to ﬁnd an eﬃcient solution, which en-

ables automatic and correct compliance checks as well as instance migrations. In

Section 3.1 we introduce general correctness principles which address the above

issues. Based on them, for the presented WF meta model (cf. Section 2) we de-

velop formal pre-conditions for ensuring compliance of instances with a modiﬁed

schema (cf. Section 3.2). Section 3.3 shows how to eﬃciently determine follow-up

markings of compliant WF instances when migrating them to the new schema.

Section 3.4 concludes with a discussion of diﬀerent change scenarios.

3.1 Dynamic Change Correctness

To illustrate potential problems that may result from the uncontrolled migration

of WF instances consider schema graph S from Fig. 2a. Let us assume that S is

correctly transformed into S’ by inserting two activities and a data dependency

between them (cf. Fig. 2a, 2b). Assume that this change shall be applied to

the instances from Fig. 2c) (currently based on S) but without performing any

compliance check. Concerning I1no problem would occur, since its execution has

not yet entered the change region. Uncontrolled migration of I2, however, would

cause malfunctions: Firstly, an inconsistent marking would result (cf. Lemma 1),

thus leading to an undeﬁned execution state. Secondly, activity give drug may

be invoked though the data element allergyData read by this activity may

not have been written. Concerning I3migration would be possible. However,

when migrating I3to S’, activation of activity prepare has to be undone and

corresponding work items must be removed from worklists. Additionally, the

newly inserted activity test must be activated. This example demonstrates that

applicability of a dynamic change depends on current instance state as well as

on applied change primitives. Furthermore, when migrating compliant instances,

markings and worklist structures must be correctly adapted.

Comparable with serializability in DBMS, we need general principles which

allow us to argue about the correctness of dynamic changes. In more detail,

we require a formal criterion for deciding whether a given WF instance can be

smoothly migrated to the modiﬁed schema or not. In addition, we must be able

On the Common Support of Workﬂow Type and Instance Changes 413

to determine correct new markings resulting from such a migration. One of our

design goals is to deﬁne these correctness criteria independently of the opera-

tional semantics of the used WF meta model and the oﬀered change operations.

This allows us to apply them in diﬀerent scope and to diﬀerent WF meta mod-

els, thus providing a good basis for reasoning about the correctness of rules and

methods for checking compliance and for migrating compliant instances.

Intuitively, instance Iis compliant with the modiﬁed schema S’ if Icould have

been executed according to S’ as well and would have produced the same eﬀects

on data elements [3,10]. Trivially, this will be always the case if Ihas not yet

entered the region aﬀected by the change. Generally, we need information about

previous execution to decide this property and to determine correct follow-up

markings for compliant instances. To derive such a general compliance principle,

at the logical level we make use of the execution history usually kept for each

WF instance (cf. Fig. 1 and 2). We assume that this history logs events related

to the start and termination of activity executions (cf. Def. 2).

WF schema S

inform prepare examine

a) WF type level

c) WF instance level (instances on S)

addActivity(S,test,{inform},{prepare}), addActivity(S,give drug,{prepare},{examine}),

addDataElement(S,allergyData),

addDataLink(S,test,allergyData,write), addDataLink(S,give drug,allergyData, read)

inform examine prepare

I1:

examine

I3:

prepare

inform

execution history of I1: START(inform)

execution history of I2: START(inform), END(inform), START(prepare)

execution history of I3: START(inform), END(inform)

inform prepare test

examine

I2:

prepare

inform

examine give drug

allergyData

b) Schema Change

WF schema S’

Fig. 2. Schema Graph and Related Instances

Obviously, instance Iwith history His compliant with S’ and can migrate

to S’ if Hcould have been produced on S’ as well. We then obtain a correct new

marking by “replaying” all events from Hon S’ in sequential order. Taking our

example from Fig. 2 this property holds for I1and I3but does not apply to I2.

When replaying H3on S’ we obtain node markings as sketched above.

The described criterion is still too restrictive to serve as general correct-

ness principle. Concerning loop changes it may needlessly exclude instances

from migrations. As an example take instance Ifrom Fig. 1 where the de-

picted loop is in its 2nd iteration. Assume that schema S is modiﬁed by apply-

ing change addActivity(S, perform test, {prepare},{give drug}). Tak-

ing the above criterion this change would not be allowed since previous loop

iteration of Iis not compliant with the new schema; i.e., Hcannot be pro-

duced based on the modiﬁed schema. However, excluding such instances from

migrations very often is not in accordance with practice. To overcome this re-

strictiveness we relax the above criterion by (logically) discarding those history

414 M. Reichert, S. Rinderle, and P. Dadam

entries produced within another loop iteration than the last (completed loops) or

the current one (running loops). We denote this reduced view Has redH. Based

on this we now deﬁne a general correctness principle for dynamic WF changes:

Axiom 1 (Dynamic Change Correctness) Let I= (T, V, MS,Val

S,H)be

a WF instance with correct schema graph S = S(T,V) and marking MS. Assume

that S is transformed into a correct schema graph S’ by applying change ∆. Then:

1. ∆can be correctly propagated to Iiﬀ redHcan be produced on S’ as well

(For this case, Iis said to be compliant with S’).

2. Assume Iis compliant with S’. When propagating ∆to Ithe correct marking

MSof Ion S’ can be obtained by replaying redHon S’.

These two basic properties satisfy our design goals since they do not de-

pend on the operational semantics of the used WF meta model and the changes

applied. Axiom 1 can therefore serve as fundamental correctness principle for

adaptive workﬂow. Furthermore, it does not needlessly exclude instances from

migrations on condition their execution will not get into trouble due to the

change. Altogether Axiom 1 provides a good basis for arguing about dynamic

change correctness. However, it would certainly be no good idea to guarantee

compliance and to determine new markings of compliant instances by accessing

the whole execution history and trying to replay it on the modiﬁed schema since

this may cause a performance penalty. Note that histories comprise voluminous

data and are usually not kept in primary storage. In the following we present

optimized rules and procedures for ensuring correctness according to Axiom 1.

3.2 Rules for Checking Compliance

For the WF meta model from Section 2 and related change primitives we exem-

plarily show under which conditions compliance (cf. Axiom 1,1) can be guaran-

teed. Our basic design principles have been as follows:

1. We consider change semantics and context in order to derive precise compli-

ance rules and to state which information is needed for checking them.

2. We make use of dynamic properties of the WF model. Particularly, the

derivation of compliance rules beneﬁts from activity markings which already

provide a consolidated view on the (reduced) history of a WF instance.

We omit unnecessary details and focus on compliance rules for selected primitives

from Table 1. Based on them, one can easily develop high-level change opera-

tions and related compliance rules. Since the latter can be derived by merging

compliance conditions of the change primitives applied and by discarding unnec-

essary expressions (e.g., conditions on nodes not present in the original schema

graph), we do not further consider complex change operations in this paper.

Let Ibe an instance with schema S, marking MS, and history H. Assume

that S is transformed into correct schema S’ by applying one of the primitives

from Table 1. The challenge is to ﬁnd conditions under which we can ensure

compliance of Iwith S’ (cf. Axiom 1,1). Table 2 summarizes some well-founded

compliance conditions. Based on them we can state the following theorem:

On the Common Support of Workﬂow Type and Instance Changes 415

Table 2. Examples of Compliance Rules

Change Operation ∆ ... ... and Related Compliance Condition Compliant(S, ∆, NS, ES, ValS,H)

addActivity( (∀n∈Preds: NS(n) =SKIPPED)∨

S,nins,Preds,Succs) (∀n∈Succs: NS(n) ∈{NOT ACTIVATED, ACTIVATED}∨(NS(n) =SKIPPED ∧

∀m∈succ(S,n):NS(m) ∈{NOT ACTIVATED, ACTIVATED, SKIPPED})

addCtrlEdge( NS(ndst)∈{NOT ACTIVATED, ACTIVATED}

S, nsrc,ndst)∨

(NS(ndst)∈{RUNNING, COMPLETED}∧NS(nsrc)∈{COMPLETED}∧

(with EC(nsrc →ndst)= (ei=END(nsrc),ej=START(ndst)∈H,⇒i<j)) ∨

=True) (NS(ndst)∈{RUNNING, COMPLETED}∧NS(nsrc)=SKIPPED ∧

(∀n∈N1with NS(n)=COMPLETED,ej=END(n),ei=START(ndst)∈H,⇒j<i))

∨

(NS(ndst)=SKIPPED ∧NS(nsrc)∈{NOT ACTIVATED, ACTIVATED, RUNNING, COMPLETED}∧

(∀n∈N2:NS(n)∈{NOT ACTIVATED, ACTIVATED, SKIPPED}))

∨

(NS(ndst)=SKIPPED ∧NS(nsrc)=COMPLETED ∧(∀n∈N2with NS(n)∈{RUNNING, COMPLETED}:

(ej=START(n),ei=END(nsrc)∈H,⇒j>i)}))

∨

(NS(ndst)=NS(nsrc)=SKIPPED ∧

(∀s∈N2with NS(s)∈{RUNNING, COMPLETED},∀p∈N1with NS(p)=COMPLETED:

ei=END(p),ej=START(s) ∈H,⇒j>i))

where N1:= pred(S, nsrc)¬pred(S, ndst)∪{nsrc},

N2:= succ(S, ndst)¬succ(S, nsrc)∪{ndst}

deleteActivity(S,ndel)NS(ndel)) ∈{NOT ACTIVATED, ACTIVATED, SKIPPED}

deleteCtrlEdge( (NS(ndst)∈NOT ACTIVATED, ACTIVATED)∨

S,nsrc,ndst)(ES(nsrc →ndst)=FALSE SIGNALED ∧((∃n→ndst ∈CtrlEdges, n =nsrc)∨

(∀n∈succ(S, ndst): NS(n) ∈{RUNNING, COMPLETED})) ∨

(ES(nsrc →ndst)=TRUE SIGNALED ∧(( ∃ n→ndst ∈CtrlEdges, n =nsrc)∨

(∃e=n→ndst ∈CtrlEdges, n =nsrc with ES(e) =FALSE SIGNALED ))

addDataElement(S,d) no condition

deleteDataElement(S,d) val(d) = UNDEFINED

addDataLink(S,n,d,read) NS(n) ∈{NOT ACTIVATED, ACTIVATED, SKIPPED}

addDataLink(S,n,d,write) NS(n) =COMPLETED

Theorem 1 (Compliance Rules). Let Ibe a WF instance with schema graph

S, marking MS= (NS, ES), data values ValS, and execution history H. Assume

that S is transformed into a correct schema graph S’ by applying change operation

∆to it. Then: Iis compliant with S’ (according to Axiom 1,1) ⇔

Compliant(S, ∆, NS, ES, ValS,H)=TRUE (cf. Table 2).

Due to lack of space we omit formal proofs. Instead we exemplarily describe

compliance conditions for the primitives addActivity and addCtrlEdge. Re-

garding insertion of an activity nins between two node sets P reds and Succs

compliance can be guaranteed if all nodes from Succs actually possess one of the

markings ACTIVATED or NOT ACTIVATED. In this case, none of the successors of

nins has yet written any entry into H. Furthermore, compliance can be ensured

if all nodes from P reds are marked as SKIPPED. Then nins is skipped as well,

i.e., its insertion has no eﬀect on compliance. Finally, nins may be inserted as

predecessor of a skipped node provided that none of the successors of this node

has a marking other than ACTIVATED,NOT ACTIVATED,orSKIPPED (see Fig. 3).

admit

prepare

X - ray

report

take blood

lab test A

lab test B

validate

aftercare

e >= 50

age < 50

The addition of a control edge nsrc →

ndst will always be possible if NS(ndst)

∈{ACTIVATED,NOT ACTIVATED}applies.

In case ndst is marked as SKIPPED com-

pliance can be guaranteed if all succes-

sors of ndst (less the successors of nsrc)

possess one of the markings ACTIVATED,

NOT ACTIVATED,orSKIPPED.

Under certain conditions dynamic insertion of a control edge nsrc →ndst

is even allowed if ndst has been already started or completed. As an example

416 M. Reichert, S. Rinderle, and P. Dadam

(S, M

p(x)=

false

p(x)

(S’, M

S’

addActivity(S, X, {A}, {C})

CalculateMarking

NS = ACTIVATED NS = RUNNING

NS = SKIPPED NS = COMPLETED

ES = TRUE_SIGNALED ES = FALSE_SIGNALED

Re-evaluated

Markings

Fig. 3. Insertion before a Skipped Node

take the process schema (medical workﬂow) from the previous ﬁgure. Assume

that an additional control edge is inserted between activities test B and X-ray.

Concerning instances for which both activities are completed insertion is (only)

allowed if test B had written its end entry into Hbefore the start entry of

X-ray was logged. As a second example, consider an instance Iwhere test B is

marked as SKIPPED and X-ray as COMPLETED. Taking this marking Iwould be

only compliant with S’ if take blood had been completed before X-ray started

(N1={take blood}).

Compliance conditions for the deletion of activities and control edges as well

as for data ﬂow changes are summarized in Table 2. In a similar way we can derive

compliance rules for other primitives, e.g., insertion or deletion of loop edges or

update of transition conditions. Altogether we can state that compliance – as

postulated by Axiom 1,1 – can be checked on basis of current activity markings;

i.e., we usually must not explicitly check the producibility of whole execution

histories on the modiﬁed schema.

3.3 How to Correctly Adapt Workﬂow Instance Markings?

We have described how compliance can be ensured and which information is

needed. Our main goal was to prevent access to the whole execution history. By

holding this maxim we now show how compliant instances can be migrated to

the changed schema. One problem to be solved is the eﬃcient and correct adap-

tation of activity markings. According to Axiom 1,2 the marking of a migrated

instance must be the same as it could be obtained when replaying the respective

(reduced) history on the new schema. How extensive marking adaptations turn

out for instance Idepends on the kind and scope of the change. Except for initial-

ization of newly inserted nodes and edges, no adaptations will become necessary

if execution of Ihas not yet entered the change region. In other cases extensive

marking adaptations may be required. An activity X, for example, may have to

be deactivated if control edges are inserted with Xas target activity. Conversely,

a newly added activity will have to be immediately activated or skipped if all

predecessors possess a ﬁnal marking. As shown in Fig. 3 it may even become

necessary to undo the skipping of nodes when inserting an activity.

We now describe how markings can be automatically and eﬃciently adapted

when migrating compliant instances. Initially, we can restrict marking evalua-

tions to those nodes and edges, which constitute the context of a change region.

We sketch how these sets can be determined for selected change primitives as well

On the Common Support of Workﬂow Type and Instance Changes 417

as for complex changes. Based on this, we present an algorithm which correctly

calculates new markings for compliant instances.

Table 3. Node and Edge Sets to be Evaluated

op = addActivity(S, nins, Preds, Succs) Ncheck(op):= Succs (∪{nins}if Preds = ∅)

Echeck(op):={p→nins ∈CtrlEdges’ |p∈Preds}

op = deleteActivity(S, ndel)Ncheck(op):={n∈N|ndel →n∈CtrlEdges }

Echeck(op):=∅

op = addCtrlEdge(S, nsrc,n

dst)Ncheck(op):={ndst},Echeck(op):={nsrc →ndst}

op = deleteCtrlEdge(S, nsrc,n

dst)Ncheck(op)={ndst}

Table 3 shows node and edge sets whose markings must be initially evalu-

ated when the respective change operation op is applied – we denote these sets as

Ncheck(op) and Echeck(op) respectively. Depending on the evaluation result, in-

spection of additional nodes and edges may become necessary. As a ﬁrst example,

take the dynamic insertion of an activity nins. Firstly, all incoming control edges

of nins must be evaluated. Depending on this, nins either has to be activated,

skipped, or left in its initial state. (Note that an initial evaluation of nins only

becomes necessary if P reds =∅holds.) Secondly, all successors of nins must be

re-evaluated as well. Due to the insertion of nins, activation or skipping of these

activities may have to be undone. Regarding the insertion of a control edge, the

marking of both, the newly added edge and its target node ndst have to be re-

evaluated, i.e., we obtain Ncheck(op)={ndst}and Echeck(op):={nsrc →ndst}.

The latter will be also required if the evaluation of the edge marking results in

NOT SIGNALED (for this case ndst may have to be deactivated).

Concerning a complex change ∆=op1,...,op

nthe total node and edge sets

Ncheck(∆) and Echeck(∆) to be (initially) evaluated can be determined with

Algorithm 1. In principle, we obtain them by unifying the corresponding sets of

the applied change operations. However, since these operations can be based on

each other, there may be temporarily generated nodes or edges not present in

the resulting schema graph anymore. This is considered by Algorithm 1.

Algorithm 1: CalcEvalSet(S, S’, ∆=op1,...,op

n)−→ Ncheck(∆), Echeck (∆)

Echeck(∆):=∅;Ncheck(∆):=∅;

for i:=1 to n do

Echeck(∆):= Echeck (∆)∪Echeck (opi); Ncheck(∆):= Ncheck (∆)∪Ncheck (opi);

done

Echeck(∆):= Echeck (∆)∩E’; Ncheck(∆):= Ncheck (∆)∩N’;

Let Ibe an instance with schema S and marking MS. Assume S is trans-

formed into a correct schema S’ by applying change ∆=op1,...,op

n. Assume

418 M. Reichert, S. Rinderle, and P. Dadam

Algorithm 2: CalcMarking(S, S’, (NS, ES),Ncheck(∆),Echeck(∆))−→ (NS’, ES’)

Ncheck:= Ncheck (∆);E

check:= Echeck (∆);

forall e∈E’ ∩Edo ES’(e) = ES(e) done;

forall e∈E’ ¬Edo ES’(e) = NOT SIGNALED done

forall n∈N’ ∩Ndo NS’(n) = NS(n) done;

forall n∈N’ ¬Ndo NS’(n) = NOT ACTIVATED done

repeat

while Echeck =∅do

fetch an edge e=nsrc →ndst from Echeck;

determine marking newES of e according to marking of nsrc and transition cond. EC’(e)

if ES’(e) =newES then

ES’(e) := newES , Ncheck := Ncheck ∪{ndst}

endif

done

while Ncheck =∅do

fetch a node nfrom Ncheck;

determine marking newNS of n according to markings of incoming control edges of n.

if NS’(n) =newNS then

if newNS = SKIPPED or NS’(n) = SKIPPED then

Echeck:= Echeck ∪{e=n

src →ndst ∈E’ |nsrc =n}

endif

NS’(n) := newNS

endif

done

until Echeck =∅and Ncheck =∅;

further that Iis compliant with S’. Algorithm 2 then correctly determines new

marking MSof Ion S’. Basic to this are the marking and execution rules of

our WF meta model. Algorithm 2 starts with sets Ncheck(∆) and Echeck(∆)as

input. If the markings of respective nodes or edges are adapted during execution

of Algorithm 2, context nodes and edges will be re-evaluated as well, etc. By

means of Algorithms 1 and 2, total expenditure for marking adaptations can be

signiﬁcantly reduced when compared to the re-evaluation of all node and edge

markings or the complete replay of all history events on the new schema. Never-

theless, our approach guarantees correctness according to Axiom 1,2. Formally:

Theorem 2 (Optimized Marking Adaptations). Let I= (T, V, MS,Val

H) be an instance with schema S = S(T,V) and marking MS. Assume that

change ∆transforms S into a correct schema S’ and I is compliant with S’.

Then: With CalculateMarking(S, S’, MS,Ncheck(∆),Echeck(∆)) (cf. Alg. 2) we

obtain the correct marking MSof I(cf. Axiom 1,2) when migrating it to S’;

i.e., we obtain the same marking as it would result when replaying Hon S’.

While Algorithm 1 has to be carried out only once at change deﬁnition time,

Algorithm 2 must be applied for each instance to be migrated. The complexity

of Algorithm 2 can be estimated by O(n) (where ncorresponds to the number

of activities of schema S’). Additionally, for each WF instance complexity O(n)

arises from the described compliance checks.

As a ﬁrst example, take the activity insertion from Fig. 3. As already shown,

the depicted instance is compliant with the modiﬁed schema. With Algorithm 1

we obtain Ncheck ={C}and Echeck ={A→X}. Furthermore, when running Al-

On the Common Support of Workﬂow Type and Instance Changes 419

gorithm 2 with these sets as input, the newly inserted activity X will be activated

whereas skipping of C and activation of E will be undone. A second example,

which shows a change at the type level (parallel ordering of activities that have

been executed serially so far) and its propagation to compliant instances is de-

picted in Fig. 4. Note that both, necessary checks and marking adaptations can

be completely automated in our approach. Thus the “dynamic change bug” as

discussed in WF literature (e.g. [9,11]) is not present in our approach.

A B C

Type Level

Instance Level

I1:

S’

deleteCtrlEdge(S,B,C)

addCtrlEdge(S,A,C)

addCtrlEdge(S.B.D)

Ncheck

= {C,D}

Echeck = {A

C, B

(Alg. 1)

CalculateMarking

(Alg. 2)

A B C

I2:

NS = ACTIVATED NS = RUNNING

NS = COMPLETED ES = TRUE_SIGNALED

Fig. 4. Instance Migrations Due To Type Change

3.4 Realizing Workﬂow Type and Workﬂow Instance Changes

The presented correctness principles, compliance rules, and migration proce-

dures are applicable for both WF schema evolution (incl. change propagation to

running instances) and ad-hoc changes of single instances.

WF schema evolution: First of all, we allow designers to restrict the set

of migratable instances by specifying appropriate selection predicates (based on

WF attributes). For each selected instance Ithe WfMS checks whether it is

compliant with the modiﬁed schema or not. In the former case Iis re-linked to

the new schema S’ and its further execution is based on S’ (cf. Fig. 5 b). Among

other things this includes adaptation of markings and related data structures as

described. Non-compliant instances may be ﬁnished according to the old schema

version or be rolled back to a compliant state to enable their migration. In

connection with loops such a compliant state may be reachable when a loop

enters its next iteration. A discussion of this special case and the support of

delayed instance migrations, however, is outside the scope of this paper.

(Ad-hoc) changes: An ad-hoc change of instance Imay become necessary,

for example, to deal with exceptional situations. For change deﬁnition, high-

level operations are oﬀered to users (e.g., to jump forward in the ﬂow or to shift

activities) which are based on the described primitives. All runtime deviations are

420 M. Reichert, S. Rinderle, and P. Dadam

S(T, V1)

S(T

instance level

worklist structures

adapt

I1 I2

execution schema

graph S(T,V) +

applying

ad-hoc change

to I2

Scenario 1

T type level

S(T, V1)

I1 I2 I3 …

S(T

V1)

S(T,V1)

S(T

V1)

instance level

worklist structures

work items

T type level

S(T, V1)

I2 …

S(T

V1)

S(T

V2)

S(T

V2)

instance level

worklist structures

insert/delete

work items

S(T, V2)

I1 I3 …

migrating compliant

instances I1 + I3

schema change T

Scenario 2

Fig. 5. Managing Type and Instance Changes

properly integrated with respect to authorization and are logged in the change

history of I. Obviously, this results in an instance-speciﬁc execution schema SI

=S+∆Iwhich diﬀers from the original schema S (cf. Def. 3) – ∆Iis called the

bias of I(with respect to S) and describes the set of instance-speciﬁc changes

op1

I,...,op

Ithat have been applied to Iso far. Execution of Ias well as future

change deﬁnitions are logically based on SI(cf. Fig. 5 a).

Deﬁnition 3 (Biased Instance). A biased instance Iis described by a tuple

(T, V, ∆I,M

S+∆I,Val

S+∆I,H), where S = S(T,V) corresponds to the schema

version from which Iwas created and ∆Icomprises instance-speciﬁc changes

op1

I,...,op

Ithat have been applied to Iso far. Schema SI:= S + ∆I, which

results from the application of ∆Ito S, is called the execution schema of I.

Trivially, the execution schema SIof an unbiased instance I(with ∆I=∅)

corresponds to its original schema S. A biased instance always keeps the reference

to its original schema. As we will see in the next section, under certain conditions

this allows us to propagate type changes to biased instances as well. How biased

instances are “physically” represented, whether SIis materialized or only ∆Iis

stored and other implementation issues are outside the scope of this paper.

4 Conﬂicting Type and Instance Changes

Biased WF instances must not be needlessly excluded from adapting to a WF

type change. As an example take a patient treatment process. Even though

physicians may have deviated from the original WF schema S at the instance level

(e.g., by inserting or skipping activities) this must not prohibit the propagation

of future WF type changes to these instances on condition that they are not

conﬂicting with current instance state and previously applied ad-hoc changes.

In this section, we sketch what is needed and which issues arise in this context.

Let I=(T,Vn,∆

I, ...) be a biased WF instance (cf. Def. 3) which was created

from schema version S = S(T, Vn) and to which instance-speciﬁc changes op1

...,op

I– described by bias ∆I– have been applied so far. Assume that a new

schema version S’ = S(T, Vn+1) is derived from S by applying WF type change

∆T(= op1

T,...,op

T)toit(S’=S+∆T). Then the following issues arise:

On the Common Support of Workﬂow Type and Instance Changes 421

1. May ∆Tbe propagated to Ias well though the current execution schema

SI=S+∆Iof Idiﬀers from the original schema S?

2. If change propagation is possible how can it be eﬃciently and correctly ac-

complished? Which execution schema SI’ (and marking MS

I) must result?

4.1 Correctness Issues

Comparable to the migration of unbiased instances (cf. Section 3) we introduce

a general criterion that allows us to argue about the two issues described above.

Obviously, when propagating a WF type change ∆Tto a biased WF instance

Iwe do not only have to consider its current marking MSIbut must also deal

with structural and semantical conﬂicts that may exist between the “concurrent”

changes ∆Iand ∆T(Note that ∆Ias well as ∆Thave been based on S). In this

paper we restrict our considerations to structural conﬂicts. A comprehensive

treatment of semantically conﬂicting changes is given in [12].

Axiom 2 (Propagating Type Changes To Biased Instances) LetTbea

WF type with actual schema version S = S(T,Vn). Assume that a new schema

version S’= S(T,Vn+1) is derived by applying type change ∆Tto S. Then:

∆Tmay be propagated to WF instance I= (T, Vn,∆I, ...) :⇔

1. S* = (S + ∆I)+∆Tis a correct schema graph, i.e., ∆Tcan be correctly

applied to the execution schema SI=(S+∆I).

2. Iis compliant with S*; i.e., the reduced execution history redH(cf. Section

3.1) can be produced on S* as well. The marking MS∗resulting from this is

considered as a correct state.

According to Axiom 2 type change ∆Tmay be propagated to a biased in-

stance Iif ∆Tcan be correctly applied to the execution schema of Iand does

not conﬂict with its current marking. The resulting schema S* = SI+∆T

must therefore satisfy the correctness properties of the used WF meta model

(cf. Section 2). In addition, Imust be compliant with S* according to Ax-

iom 1. As an example take schema S = S(T,V) from Fig. 6. Assume that

type change ∆1

T=[addCtrlEdge(S,E,D)] is applied to S. Then condition 1

of Axiom 2 is not satisﬁed since the resulting schema SI+∆1

Tcontains a

deadlock-causing cycle. ∆1

Tmust therefore be not propagated to I. As opposed

to this, type change ∆2

T=[addActivity(S,Y,{D},{E})] may be propagated to

Isince the conditions deﬁned by Axiom 2 are met. As a last example take ∆3

=[deleteDataLink(S,C,d,write),deleteActivity(S,C)]. It is quite evident

that propagation of ∆3

Tto Iwould result in an incorrect data ﬂow schema since

X (which was inserted by a previous instance change) would read data element

d with undeﬁned value.

4.2 Checking Correctness

The challenge is to eﬃciently verify the conditions from Axiom 2. A naive so-

lution would be to ﬁrst generate schema SI+∆Tand then to check whether

422 M. Reichert, S. Rinderle, and P. Dadam

S: I:

I = [ addCtrlEdge(SI, D, B),

addActivity(SI, X, {E},



addDataLink(SI, X, d, read) ]

d d

Fig. 6. Original Schema and Biased Instance

it satisﬁes the required structural and dynamic properties. Generally this would

be too expensive, in particular if diﬀerent WF aspects (control ﬂow, data ﬂow,

etc.) are concerned or ∆Tshall be propagated to a large number of instances.

Instead we must deﬁne appropriate rules for excluding conﬂicts between type

and instance changes for as many cases as possible. Concerning the absence of

deadlock-causing cycles, for example, the following conﬂict rule can be used:

Lemma 2 (Deadlock Prevention). Let T be a WF type with actual schema

version S = S(T, Vn) and I = (T, Vn,∆I, ...) be a biased instance with execution

schema SI=S+∆I. Assume that type change ∆Ttransforms S into a correct

schema S’ = S(T,Vn+1). Then: S* = (S + ∆I)+∆Tdoes not contain deadlock-

causing cycles if the following condition holds:

∀s1→d1∈AddedCtrlEdges∆T,∀s2→d2∈AddedCtrlEdges∆I:

d1∈ pred(S, s2)∨d2∈ pred(S, s1)

(AddedCtrlEdges∆denotes the set of control edges inserted by change primitives

addActivity and addCtrlEdge from ∆.)

Taking change ∆1

Tfrom Section 4.1 the condition of this lemma is not satis-

ﬁed. Concerning ∆2

T, however, deadlocks can be excluded. Though the condition

set out by Lemma 2 will not always be necessary, it is suﬃcient to exclude po-

tential deadlocks. In particular, the related checks can be based on the original

schema graph S and be accomplished by simple graph algorithms (with complex-

ity O(n)). Generally, for each change operation we have to deﬁne corresponding

conﬂict rules. Concerning data ﬂow changes, for example, we can exclude poten-

tial conﬂicts by ensuring that the data element sets for which ∆Iand ∆Thave

inserted or deleted data edges are disjoint. In our example from Section 4.1, ∆I

has inserted a read data link with source d and ∆3

Tremoved a write data link

with target d. Thus a potential conﬂict exists, which requires additional checks.

4.3 Propagating Type Changes to Biased Instances

Assume that schema S is correctly transformed into a new schema S’ by applying

type change ∆Tto it. Assume further that I= (T, Vn,∆I, ...) is an instance to

which ∆Tcan be correctly propagated according to Axiom 2. Then the question

arises how we can migrate this biased instance to the new schema version of type

T. Due to lack of space we only consider changes based on the primitives from

Table 1. For them the following theorem applies:

On the Common Support of Workﬂow Type and Instance Changes 423

Theorem 3 (Commutativity of Type and Instance Changes). LetTbe

a WF type with actual schema graph version S = S(T, Vn) and I= (T, Vn,∆I,

...) be a biased instance (with type T). Assume that type change ∆Ttransforms

S into S’ = S(T,Vn+1) and ∆Tcan be correctly propagated to I(according to

Axiom 2). Then: ∆Tand ∆Iare commutative, i.e., ∆Ican be correctly applied

to S’ as well and (S + ∆I)+∆T≡(S + ∆T)+∆I(=S’+∆I).

According to this theorem, type and instance changes are commutative pro-

vided that the speciﬁed conditions are met. In particular, this property allows

us to treat type changes and related change propagation similar to the unbiased

case (cf. Section 3.4). More precisely, a type change can be propagated to a bi-

ased instance Iby re-linking this instance to the new schema S’ (cf. Fig. 7) and

by re-calculating marking MS

Ifor the resulting execution schema SI’. Note that

SI’ can be simply derived by applying bias ∆Ito S’. Though at ﬁrst glance it

seems to make no signiﬁcant diﬀerence whether we apply ∆Tto SIor ∆Ito S’

the latter variant oﬀers several advantages with respect to the management of

schema versions and propagation of future type changes. Due to lack of space

we abstain from further details.

Type level

S = S(T, Vn)

I1 I2 I3

instance level

Type level

S = S(T, Vn)

S’

’+

instance level

S’ = S(T, Vn+1)

I2 I3

migrating compliant

instances I2 and I3

type change

unbiased biased

X X

X bias

S’ +

Fig. 7. WF Type Change and Propagation To Biased and Unbiased WF Instances

5 Related Work

One of the ﬁrst approaches which has used a generic correctness criterion for dy-

namic WF changes was developed within the WIDE project [10]. WIDE applies

a history-based compliance criterion to guarantee correctness when migrating

instances to a modiﬁed schema. Concerning loops, however, this criterion is too

restrictive. Furthermore, issues related to data ﬂow changes, marking adapta-

tions and conﬂicting changes are not considered. Similar correctness criteria have

been applied in TRAMs and BREEZE. TRAMs [7] focuses on schema versioning

concepts. To eﬃciently manage instance migrations the deﬁnition of migration

conditions is proposed for every change operation. Based on them, it can be

decided whether an instance can migrate to the new version or not. BREEZE [3]

also uses formal compliance criteria but focuses on the handling of non-compliant

WF instances. Furthermore it deals with the correct treatment of temporal con-

straints at the presence of dynamic changes.

424 M. Reichert, S. Rinderle, and P. Dadam

Petri-Net based approaches for adaptive WF [9,11,13] must deal with the

problem that actual state tokens of a net instance do not represent a view on

previous instance execution as in our work. This, in turn, complicates compliance

checking and marking adaptations in order to avoid the “dynamic change bug”

[9]. [11] suggests the construction of a hybrid WF schema which reﬂects parts of

both the old and the new WF schema. Additionally, the designer must explicitly

specify rules for mapping tokens between old and new net versions. Actual results

from the Petri Net ﬁeld come from [9,14]. As correctness criterion branching

bisimularity is proposed: An instance Ican migrate to a modiﬁed schema if each

action of I can be simulated on this schema as well. Unfortunately, branching

bisimularity can be only ensured for special change operations and excludes, for

example, order-changing operations. Apart from this, other issues addressed by

our work (e.g., eﬃcient compliance checks, treatment of loops, conﬂicting type

and instance changes) have not been discussed in these papers.

In MOKASSIN [8] change primitives are encapsulated within WF instances.

The compliance criterion is considered as being too restrictive. Instead, a more

granular version concept is proposed. However, correctness issues are completely

factored out by the authors. Another versioning approach has been oﬀered by

WASA2[4], which uses a correctness criterion based on the mapping of WF

instances against WF schemes. In WASA2, biased instances cannot be adapted

to type changes anymore as opposed to our approach. Furthermore, changes

in conjunction with loops have not been dealt with. Finally, ULTRAFlow [15]

presents a rule-based approach. Changes are realized by modifying the implemen-

tation and meta data of activities. Special synchronization methods guaranteeing

consistent access of instances on modiﬁed speciﬁcations are provided. However,

ULTRAFlow totally factors out important change operations (e.g., deletion of

activities) and does not consider data ﬂow issues.

A formal treatment and comparison of correctness criteria of some of the

above approaches has been given in [16].

6 Summary and Outlook

In many domains, like hospitals, engineering environments, or oﬃces, process-

centered applications will not be accepted whenever rigidity comes with them.

Creating WF-based applications without a vision for adaptive WF is therefore

shortsighted and expensive. Indeed, insuﬃcient ﬂexibility and adaptability have

been primary reasons why WF technology failed in many process automation

projects in the past. Both, the capability to quickly and correctly propagate WF

type changes to in-progress WF instances and the support of ad-hoc adaptations

will be key ingredients in the next generation of WfMS, ultimately resulting in

highly adaptive process-oriented applications.

In this paper we have focused on the common support of WF type and WF

instance changes and have discussed limitations of current approaches. The very

important aspect of our work is its formal foundation. We have given general

axioms and theorems which are fundamental for the correct handling of dynamic

On the Common Support of Workﬂow Type and Instance Changes 425

WF changes. The treatment of conﬂicting type and instance changes adds to

the completeness of our approach. Finally, there is already a powerful proof-of-

concept prototype which demonstrates the feasibility of the presented concepts.

There are many other challenging issues related to adaptive workﬂow which

must be better understood before we obtain a complete solution. First of all,

we believe that usability issues constitute a ﬁeld that would beneﬁt by more

intense study of the research community. Additionally, dynamic changes may

also concern other components of the process-centered information system, like

the organizational database, security constraints, temporal constraints [3], actor

and resource assignments, or activity programs. Finally, we consider it as very

important to incorporate more semantics into the dynamic change process [12].

References

1. van der Aalst, W., van Hee, K.: Workﬂow Management. MIT Press (2002)

2. Reichert, M., Dadam, P.: ADEPTflex - supporting dynamic changes of workﬂows

without losing control. Int’l J Intelligent Information Systems 10 (1998) 93–129

3. Sadiq, S., Marjanovic, O., Orlowska, M.: Managing change and time in dynamic

workﬂow processes. Int’l J Cooperative Information Systems 9(2000)

4. Weske, M.: Formal foundation and conceptual design of dynamic adaptations in a

workﬂow management system. In: Proc. HICSS-34, Maui, Hawaii (2001)

5. Edmond, D., ter Hofstede, A.: A reﬂective infrastructure for workﬂow adaptability.

Data and Knowlege Engineering 34 (2000) 271–304

6. Kochut, K., Arnold, J., Sheth, A., Miller, J., Kraemer, E., Arpinar, B., Cardoso,

J.: Intelligen: A distributed workﬂow system for discovering protein-protein inter-

actions. Distributed and Parallel Databases 13 (2003) 43–72

7. Kradolfer, M., Geppert, A.: Dynamic workﬂow schema evolution based on workﬂow

type versioning and workﬂow migration. In: Proc. CoopIS’99, Edinburgh (1999)

8. Joeris, G., Herzog, O.: Managing evolving workﬂow speciﬁcations. In: Proc. CoopIS

’98, New York (1998) 310–321

9. van der Aalst, W.: Exterminating the dynamic change bug: A concrete approach

to support worfklow change. Information Systems Frontiers 3(2001) 297–317

10. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workﬂow evolution. Data and Knowledge

Engineering 24 (1998) 211–238

11. Ellis, C., Keddara, K., Rozenberg, G.: Dynamic change within workﬂow systems.

In: Proc. Int’l Conf. on Org. Comp. Sys., Milpitas, CA (1995) 10–21

12. Rinderle, S., Reichert, M., Dadam, P.: On dealing with semantically conﬂicting

business process changes. Technical Report UIB-2003-04, University of Ulm (2003)

13. Agostini, A., De Michelis, G.: Improving ﬂexibility of workﬂow management sys-

tems. In: Proc. Int’l Conf. BPM’00, LNCS 1806. (2000) 218–234

14. van der Aalst, W., Basten, T.: Inheritance of workﬂows: An approach to tackling

problems related to change. Theoretical Computer Science 270 (2002) 125–203

15. Fent, A., Reiter, H., Freitag, B.: Design for change: Evolving workﬂow speciﬁcations

in ULTRAﬂow. In: Proc. CAISE ’02. (2002) 516–534

16. Rinderle, S., Reichert, M., Dadam, P.: Evaluation of correctness criteria for dy-

namic workﬂow changes. In: Proc. Int’l Conf. BPM’03. (2003) 41–57