Disjoint and Overlapping Process Changes: Challenges, Solutions, Applications [original]

Disjoint and Overlapping Process Changes:

Challenges, Solutions, Applications

Stefanie Rinderle, Manfred Reichert, and Peter Dadam

University of Ulm, Faculty of Computer Science,

Dept. Databases and Information Systems

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

Abstract. Adaptive process–aware information systems must be able

to support ad–hoc changes of single process instances as well as schema

modiﬁcations at the process type level and their propagation to a col-

lection of related process instances. So far these two kinds of (dynamic)

process changes have been mainly considered in an isolated fashion. Es-

pecially for long-running processes, however, it must be possible to ade-

quately handle the interplay between type and instance changes as well.

One challenge in this context is to determine whether concurrent process

type and process instance changes have the same or overlapping eﬀects

on the original process schema or not. Information about the degree

of overlap is needed, for example, to determine whether and – if yes –

how a process type change can be propagated to individually modiﬁed

process instances as well. This paper provides a formal framework for

dealing with overlapping and disjoint process changes and presents ade-

quate migration strategies depending on the particular degree of overlap.

In order to obtain a canonical representation of changes an algorithm is

introduced which purges change logs from noisy information. Finally, a

powerful proof-of-concept prototype exists.

1 Introduction

To stay competitive at the market for companies it becomes more and more

important to adequately support their business by process–aware information

systems (PAIS) [1]. Doing so it is not suﬃcient to implement business processes

only once and to let the PAIS then run eternally without any adaptations. In

fact the ability to quickly react to market changes or exceptional situations by

appropriate process changes is key to success [2,3,4,5,6,7]. Basically, in a PAIS

changes can take place at two levels – the process type or the process instance

level. Process type changes become necessary, for example, to adapt the PAIS

to optimized business processes or to new laws [8,9]. In particular, applications

supporting long-running processes (e.g., handling of leasing contracts or medical

treatments) and the process instances controlled by them are aﬀected by such

type changes [8,9]. As opposed to this, changes of single process instances have

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, Z. Tari (Eds.): CoopIS/DOA/ODBASE 2004, LNCS 3290, pp. 101–120, 2004.

Springer-Verlag Berlin Heidelberg 2004

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

deliver

goods

get

order

compose

order

confirm

order

pack

goods

send form send shirt

size

compose

order pack

goods deliver

goods

send

form send

shirt

size

get

order

size

send

form send

shirt

size

Process Type Level:

Type Schema S:

Type Schema S’:

Process Type Change

'T = ( serialInsert( S, send form, collect data, compose order),

serialInsert(S, send shirt, compose order, pack goods),

deleteActivity(S, confirm order), addDataElement(S, size), …)

Process Instance Level:

I1 on S: I1 on S’:

I2 on S:

I3 on SI3 := S + 'I3(S): I3 on S’ +

I3(S’) with 'I3(S’) = deleteActivity(S, pack goods)

I4 on SI4 := S + 'I4(S): I4 on S’ ('I4(S’) = ):

non-compliant!

com

leted

activated

TRUE_si

naled

size

'I3 and 'T disjoint

'I4 and 'T overlap,

more precisely 'I3 and 'T equivalent

migrate

unbiased biased

old bias new bias

Fig. 1. Process Type and Instance Changes (Example)

often to be carried out in an ad-hoc manner in order to deal with an exceptional

situation or evolving process requirements [8,9].

Process type changes are handled by modifying the respective process

schema. Very often it is desired to propagate a process type change to related

process instances as well. Process instances for which this is possible are called

compliant, i.e., they can be migrated to the new process schema [3,10]. Adapting

a single process instance during runtime, in turn, logically results in an instance-

speciﬁc schema (i.e., a process instance schema diﬀering from the original schema

this instance was created from). In the following, we call such individually mod-

iﬁed process instances biased (e.g., instances I3and I4in Fig. 1).

Currently there are only few adaptive process management systems (PMS)

which support both kinds of changes in one system [7,11]. All these PMS have in

common that once an instance has been individually modiﬁed (i.e., it possesses

an instance-speciﬁc process schema due to an ad–hoc change), it can no longer

beneﬁt from process type changes; i.e., changes of the schema they were originally

Disjoint and Overlapping Process Changes 103

created from. However, doing so is not suﬃcient in many cases, especially in

connection with long-running processes as we have learned from several case

studies within medical and automotive environments. In order to come to a

complete solution, therefore, it must be possible to propagate process schema

changes are carried out at the type level to biased instances as well.

When analyzing the interplay between process type and process instance

changes we are faced with several challenges. In [8] we have already discussed

the problem of structural and state–related conﬂicts that may arise when prop-

agating a process type change to a biased process instance. Structural conﬂicts

between type and instance changes, for example, may lead to deadlock–causing

cycles or incomplete input data for activity executions [8].

Another fundamental issue not treated so far concerns the handling of over-

lapping type and instance changes; i.e., the handling of concurrent changes1on a

process schema that partially have the same eﬀects on this schema. In this paper

we give insights into fundamental challenges and solution approaches for coping

with such overlapping changes. One example is depicted in Fig. 1 where process

type change ∆Tand process instance change ∆I4(of instance I4) both insert

activities send form and send shirt (into schema S). Propagating type change

∆Tto instance–speciﬁc schema SI4would therefore lead to multiple insertion of

the same activities. Usually, this would not correspond to the user’s intention

who, for example, has already anticipated a process optimization by an ad–hoc

modiﬁcation at the instance level. Furthermore ∆Tand ∆I4both delete the

same activity conﬁrm order. As a consequence ∆Tactually could not be applied

to SI4since conﬁrm order is not longer present.

One prerequisite to adequately deal with such cases is to eﬀectively detect

whether (concurrent) process type and process instance changes overlap. An-

other challenge is to correctly migrate biased process instances to a modiﬁed

type schema even if the instance–speciﬁc changes overlap with the process type

change. Basically the problem is that the current representation of the instance–

speciﬁc schema, which is based on original schema Splus bias ∆I(S), must be

transformed into a representation based new schema Splus bias ∆I(S). Doing

so oﬀers several advantages: If Iis actually re–linked to Sit can beneﬁt from

further process optimizations of S. Furthermore, reassigning instances to their

actual schema version contributes to an optimal management and redundancy–

free storage of process schemes and instances. Looking again at instance I4from

Fig. 1 we can observe that ∆Tand ∆Ido exactly the same, i.e., they have the

same eﬀects on the original process schema S. We therefore call them equiva-

lent. For the above reasons, for equivalent changes a desired migration strategy

would be to abstain from any propagation of ∆Ton I4but to re–link or migrate

I4to S. In the latter case, representation of I4on Swould no longer require

maintenance of an instance–speciﬁc change, i.e., ∆I(S)=∅(cf. instance I4on

Sin Fig. 1). Assume now that an additional activity send reminder has been

1In the following, we assume that certain instance–speciﬁc changes took place before

the process type change occurs. Nevertheless, we call such changes concurrent since

they work on the same original process schema.

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

inserted into I4. Then ∆Tand ∆I4would no longer be equivalent but ∆Tbe

subsumed by ∆I4. For this case an adequate migration strategy is to migrate

I4to S(i.e., to re–link I4to S) but to further maintain the insertion of send

reminder as instance–speciﬁc change ∆

I4based on S. We conclude that for any

adaptive PMS it becomes necessary to detect whether process type and process

instance changes overlap, and to also determine the degree of overlap. This, in

turn, is fundamental in order to apply adequate migration strategies.

In this paper we provide fundamental deﬁnitions for disjoint,overlapping, and

equivalent process changes. Doing so is important in order to be able to provide

adequate migration strategies. We illustrate this by means of selected scenar-

ios. Based on formal deﬁnitions for disjoint and overlapping process changes

we discuss diﬀerent approaches for detecting them. Thereby structural,opera-

tional, and hybrid approaches are presented and estimated along their speciﬁc

strengths and limitations. We derive an adequate approach to detect to which

degree concurrent process changes overlap. This approach comprises a sophisti-

cated method to purge unnecessary information (noise) from change transaction

logs, i.e., we aim at ﬁnding a canonical respresentation of change transaction logs.

Such noise within change logs, for example, may result from mutually compensat-

ing changes. Furthermore, taking purged change transaction logs the necessary

information to decide on the degree of overlap between concurrent changes is

extracted. Altogether, this method provides the basis for being able to apply

adequate migration strategies for any kind of biased instance.

The remainder of this paper is organized as follows: In Section 2.1 we shortly

introduce WSM Nets as the process meta model taken to illustrate the pre-

sented results. The formal framework – deﬁnitions for disjoint, overlapping and

equivalent changes – as well as migration strategies are provided in Section 2.2.

In Section 3 we discuss diﬀerent approaches for detecting the degree of overlap

between process type and process instance changes and a method to purge noise

from change transaction logs in Section 4. We close with a discussion of related

work in Section 5 and a summary in Section 6.

2 Disjoint and Overlapping Process Changes

In this paper, we exemplarily use WSM Nets (as for example applied in ADEPT

[9]) and the change operations based on them. However, most of the presented

results are independent of the used process meta model. Section 2.1 gives back-

ground information on WSM Nets necessary for further understanding of the

paper. Based on this, Section 2.2 introduces deﬁnitions for diesjoint an overlap-

ping changes and exemplarily presents migration strategies for selected scenarios.

2.1 Background Information

A process schema is represented by attributed, serial-parallel process graphs with

additional links for synchronizing parallel paths [6].

Disjoint and Overlapping Process Changes 105

Deﬁnition 1 (WSM Net). A tuple S = (N, D, NT, CtrlE, SyncE, LoopE,

DataE) is called a WSM Net if the following holds:

–N is a set (bag) of activities and D a set of process data elements

–NT: N →{StartFlow, EndFlow, Activity, AndSplit, AndJoin,

XOrSplit, XOrJoin, StartLoop, EndLoop}

NT assigns to each node of the WSM Net a respective node type.

–CtrlE ⊂N×N is a precedence relation

–SyncE ⊂N×N is a precedence relation between activities of parallel

branches

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

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

activities and data elements

A WSM Net Sis structurally correct if the following constraints hold:

1. Shas a unique start node Start and a unique end node End.

2. Except for nodes Start and End each activity node of Shas at least one

incoming and one outgoing control edge e∈CtrlE.

3. Sblock := (N, CtrlE, LoopE) is structured following a block concept, for

which control blocks (sequences, branchings, loops) can be nested but must

not overlap.

4. Sfwd =(N,CtrlE,SyncE) is an acyclic graph, i.e., the use of control and

sync edges must not lead to deadlock-causing cycles.

5. Sync links must not cross the boundary of a loop block; i.e., an activity from

a loop block must not be connected with an activity from outside the loop

block via a sync link (and vice versa).

6. For activities with mandatory input parameters linked to global data el-

ements it has to be ensured that respective data elements will be always

written by a preceding activity at runtime.

7. Parallel write accesses on data elements (and consequently lost updates on

them) have to be avoided.

Taking a WSM Net Snew process instances can be created and started.

Logically, each instance Iis associated with an instance-speciﬁc schema SI:=

S+∆I(for unbiased instances ∆I(S)=∅and consequently SI=Sholds).

The execution state of Iis captured by marking function MSI=(NSSI,ES

SI).

It assigns to each activity nits current status NS(n) and to each control edge

its marking ES(e). Markings are determined according to well deﬁned marking

rules [6], 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. Formally:

Deﬁnition 2 (Process Instance). A process instance I is deﬁned by a tuple

(S, ∆I,MSI,Val

SI,ΠS

I) where

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

–S = (N, D, NT, CtrlE, SyncE, ...) denotes the process schema I was derived

from. We call S the original schema of I.

–∆Icomprises instance-speciﬁc changes opI

1,...,op

mthat have been applied

to I so far. We call ∆Ithe bias of I. Schema SI:= S+∆I(with SI=

(NI,D

I,NT,CtrlE

I,...)) which results from the application of ∆Ito S, is

called the instance–speciﬁc schema of I.

–MSI= (NSSI,ES

SI) describes node and edge markings of I:

NSSI:NI→{NotActivated, Activated, Running, Completed,

Skipped}

ESSI:(CtrlEI∪SyncEI∪LoopEI)→

{NotSignaled, TrueSignaled, FalseSignaled}

–ValSIis a function on DI. It reﬂects for each data element d ∈DIeither

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

–ΠS

I=<e

0,...,e

k>is the execution history of I. e0,...,e

kdenote the start

and end events of activity executions.

Activities marked as Activated are ready to ﬁre and can be worked on.

Their status then changes to Running. As an example take instance I1from

Fig. 1: Activity get order is completed whereas activity compose order is ac-

tivated. Activities with marking Skipped cannot be longer selected for execution.

Table 1 presents a selection of high-level change operations which can be used

to deﬁne or modify WSM Nets. These change operations include formal pre- and

post-conditions. They automatically perform the necessary schema transforma-

tions whereas schema correctness (cf. correctness constraints 1. – 7. for WSM

Nets) is ensured. One typical example of such a change operation is the insertion

of an activity and its embedding into the process context.

When applying a series of connected change operations opi(i=1,...,n), e.g.,

when inserting two activities and a data dependency between them, it is often

desired to apply either all of these change operations or none of them (atomicity).

In order to achieve this, change operations op1,...,op

nmust be carried out

within same change transaction ∆=(op1,...,op

n)(change for short).

2.2 Formal Framework

In Sect. 1 we have already introduced the notions of disjoint and overlapping

changes informally. In this section we give formal deﬁnitions of these concepts

which serve as theoretical underpinning for the following considerations. First of

all, we abstract from whether changes are carried out at the type or at the in-

stance level. More precisely, we base our considerations on two arbitrary changes

(or change sets) ∆1and ∆2concurrently applied on the same schema S.

Let Sbe a (correct) process schema and ∆1and ∆2two changes which trans-

form Sinto another (correct) process schema S1and S2respectively (notation:

S1:= S+∆1and S2:= S+∆2). Generally, disjointness and overlapping are

special relations between two changes of the same schema. The challenging ques-

tion is how to deﬁne a relation on changes. Either this can be done by directly

Disjoint and Overlapping Process Changes 107

Table 1. A Selection of High-Level Change Operations on WSM Nets

Change Operation op Eﬀects on Schema S

Applied to Schema S

Additive Change Operations

serialInsert(S, X, A, B) insertion of activity X between

two directly succeeding activities A and B

parallelInsert(S, X, (A, B)) insertion of activity X parallel to control block with

start activity A and end activity B

insertSyncEdge(S, src, dest) insertion of sync edge linking two activities src and dest

from parallel execution paths

Subtractive Change Operations

deleteActivity(S, X) deletes activity X from schema S

deleteSyncEdge(S, edge) deletes synchronization edge ∈SyncE from schema S

Order-Changing Operations

serialMove(S, X, A, B) moves activity X from current position

to position between directly succeeding activities A and B

Attribute Changing Operations

changeActivityAttribute(S, X, attr, nV) changes value of attribute attr of activity X to nV

changeEdgeAttribute(S, edge, attr, nV) changes value of attribute attr of edge ∈CtrlE ∪SyncE to nV

Data Flow Change Operations

addDataElement(S, d, dom, defVal) adds data element d with domain dom

and default value defVal to S

deleteDataElement(S, d) deletes data element d from S

addDataEdge(S, (X, d, mode)) adds data edge (X, d, mode) linking activity X

with data element d(mode ∈{read, write})

deleteDataEdge(S, dataEdge)) deletes data edge dataEdge from S

comparing ∆1and ∆2or by correlating their eﬀects on the original schema S.

Eﬀects of ∆1and ∆2on S, in turn, are reﬂected by resulting process schemes

S1and S2. Consequently, a relation between changes ∆1and ∆2can be de-

termined by ﬁnding a relation between S1and S2. – In the workﬂow literature

several (equivalence) relations for process schemes have been discussed [2,12,

13]. In the context of this work, the relation between concurrent changes aﬀects

the behavior of the resulting process schemes. Therefore, we base our further

considerations on a behavorial equivalence relation for process schemes which is

known as trace equivalence [10,13].

Deﬁnition 3 (Trace Equivalence Between Process Schemes). Let S1and

S2be two process schemes. S1and S2are equivalent with respect to their possible

traces (formally: S1≡trace S2) iﬀ each execution history ΠS1

Iproducible on S1

can be generated on S2as well and vice versa.

Intuitively, two process schemes S1and S2are trace equivalent if each pos-

sible behavior of S1(represented by its execution histories) can be simulated

by process schema S2and vice versa. Based on trace equivalence we now intro-

duce an adequate deﬁnition for overlapping and disjoint changes. Intuitively, two

change transactions ∆1and ∆2overlap if they have (partially) the same eﬀects

on the underlying process schema S. This is the case if ∆1and ∆2manipulate

the same – already existing – elements of Sor insert the same activities into S.

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

Overlapping eﬀects on already existing elements of a process schema may result

from subtractive, order–changing, or attribute–changing operations (cf. Table

1). Subtractive changes that overlap may aﬀect the applicability of ∆1on S2

and vice versa (cf. Fig. 1). Overlapping order–changing and attribute–changing

operations may mutually override the eﬀects of each other. Assume, for exam-

ple, that change ∆1moves an activity Xto position A(resulting in S1) and

∆2moves Xto position B(resulting in S2). Then applying ∆1to S2would

override the eﬀects of ∆1and vice versa. Both problems – change applicability

and overriding of change eﬀects – can be avoided if ∆1and ∆2are commutative,

i.e., applying ∆2on S1leads to a process schema which is trace equivalent to

the process schema that results when applying ∆1on S2. Formally:

Deﬁnition 4 (Commutativity of Changes). Let S be a (correct) schema

and ∆1and ∆2be two changes transforming S into (correct) schema S1and S2

respectively. We call ∆1and ∆2commutative if the application of ∆1to S2and

the application of ∆2to S1result in trace equivalent schemes, formally:

∆1,∆2commutative ⇐⇒ (S + ∆1)+∆2≡trace (S + ∆2)+∆1

Thus commutativity is a ﬁrst property for characterizing disjoint changes.

However, it is not strong enough to cover disjointness of additive changes (e.g.,

insertions of new activities) as well. In particular, commutativity does not ex-

clude the (undesired) multiple insertion of the same activity (cf. Fig. 1). In order

to avoid this eﬀect, we additionally claim that the sets of activities which are

newly inserted by ∆1and ∆2respectively have to be disjoint. Formally:

Deﬁnition 5 (Disjoint and Overlapping Changes). Let S = (N, D, CtrlE,

SyncE, DataE, ...) be a WSM Net and ∆1and ∆2be two change transactions

which transform S into WSM Nets S1and S2with

Si=(Ni,D

i,CtrlE

i, SyncEi, ...),i=1,2

I) We denote ∆1and ∆2as disjoint (notation: ∆1∩∆2=∅)iﬀthe

following properties hold:

(1) ∆1and ∆2are commutative (cf. Def. 4)

(2) (N1\N)∩(N2\N)=∅2

II) We denote ∆1and ∆2as overlapping (notation: ∆1∩∆2=∅) if they are

not disjoint.

As it can be seen from Def. 5 the notion of overlapping concurrent changes

is still relatively rough. As indicated in the introduction it is possible to further

classify overlapping changes according to their degree of overlap. One of these

subclasses is formed by equivalent changes, i.e., changes which have exactly the

same eﬀects on original schema S. Formally:

Deﬁnition 6 (Equivalent Change Transactions). Let S be a WSM Net and

∆1and ∆2be two change transactions which transform S into WSM Nets S1

2We abstract from realization details regarding the concurrent insertion of the same

activity. Informally, two process activities are considered as equal iﬀ they use the

same activity template and the same semantic identiﬁer.

Disjoint and Overlapping Process Changes 109

and S2. Then ∆1and ∆2are equivalent, i.e., ∆1≡∆2iﬀ S1and S2are trace

equivalent (cf. Def. 3). Formally:

∆1≡∆2⇐⇒ S1≡trace S2

A very interesting application of Def. 5 and Def. 6 is the correct handling of

concurrent process type and process instance changes as described in Section 1.

More precisely, based on the particular degree of overlap between process type

change ∆Tand process instance change ∆I(which can be determined based on

Def. 5 and 6) diﬀerent migration strategies have to be applied. To illustrate this,

in the following, we present the migration strategies for disjoint and equivalent

process type and instance changes.

Policy 1 (Migrating Instances With Disjoint Bias). LetSbea(correct)

process type schema and ∆Tbe a process type change which transforms S into

another (correct) type schema S’. Let further I = (S, ∆I,...) be a process in-

stance on S with instance–speciﬁc schema SI:=S+∆I. Finally, let ∆Tand ∆I

be disjoint changes (cf. Def. 5), i.e., ∆T∩∆I=∅. Then:

I can correctly migrate to S’ preserving ∆Ion S’, i.e., I = (S’, ∆I,...):⇐⇒

1. S∗

I:= (S+∆I)+∆Tis a correct schema (according to the structural cor-

rectness constraints 1. – 7. set out for the used process meta model); i.e.,

∆Tcan be correctly applied to SI=S+∆I(Structural Correctness).

2. Iis compliant with S∗

I; i.e., the (reduced) execution history ΠS

Iof I on SI

can be produced on S∗

Ias well (State-Related Correctness).3

We call the migration strategy introduced in Policy 1 the standard migration

case. When applying it to an instance I, which is both structurally and state–

related compliant with S, we actually propagate ∆Tto Iand migrate Ito S

preserving instance–speciﬁc change ∆Ion S. Generally, migrating a process in-

stance Ifor which instance change ∆Ioverlaps with type change ∆Tis called the

advanced migration case. As discussed above, adequate strategies for this case

depend on the degree of overlap between process type and instance changes. It

ranges from equivalence of the changes (cf. Def. 6) to minor overlapping between

them. To give an idea of these advanced strategies we sketch the one for dealing

with equivalent process type and process instance changes.

Policy 2 (Migrating Instances With Equivalent Bias).

Let S be a (correct) process type schema and ∆Tbe a process type change

which transforms S into another (correct) type schema S. Let further I = (S,

∆I,...) be a process instance on S with instance execution schema SI:=S+

∆I. Finally let ∆Tand ∆Ibe equivalent changes, i.e., ∆T≡∆I. Then I can

correctly migrate to S’ with resulting bias ∆I=∅on S’, i.e., I = (S’, ∅,...).

3How to eﬃciently ensure compliance and how to automatically adapt instance mark-

ings when migrating them to the changed process type schema is extensively dis-

cussed in [14].

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

If an instance change ∆Iis equivalent with process type change ∆Tthe

advanced migration strategy is to re–link instance Ito the new process type

schema Swithout applying any further changes or checks. In the sequel, instance

change ∆Iis nulliﬁed due to the application of ∆T, i.e., ∆I(S)=∅.

An example is depicted in Fig. 1 where instance change ∆I4is equivalent

with type change ∆T(obviously Sand SI4are trace equivalent). Consequently,

we can re–link I4to S’ and we can set ∆I4(S)=∅. Due to lack of space, for

dealing with further degrees of overlap we refer to [15].

3 Detecting the Degree of Overlap Between Concurrent

Process Changes

Let Sbe a (correct) process schema and let I=(S, ∆I,...) be a (biased) process

instance on S(with bias ∆I). Let further ∆Tbe a type change transforming S

into another (correct) process schema S. Then the challenging question arises

whether ∆Tand ∆Iare disjoint or whether they are overlapping each other

(cf. Def. 5). A naive solution would be to directly check Def. 5. Doing so would

require materialization of resulting process schemes S(∆T,∆I):= (S+∆T)+∆I

and S(∆I,∆T):= (S+∆I)+∆Tand explicit veriﬁcation of trace equivalence

between S(∆T,∆I)and S(∆I,∆T). However, this approach is not applicable in

practice for three reasons:

1. ∆Tcannot be always applied to SI:= S+∆Iand vice versa ∆Ito S:= S+

∆T(e.g., if ∆Tand ∆Idelete the same activities). Consequently, S(∆T,∆I)

and S(∆I,∆T)respectively cannot be materialized.

2. Even if S(∆T,∆I)and S(∆I,∆T)can be materialized the veriﬁcation of trace

equivalence would require to determine all execution histories producible on

S(∆T,∆I)and S(∆I,∆T). This, in turn, would demand reachability analyses

for both schemes resulting in exponential complexity.

3. Assume that we can materialize both S(∆T,∆I)and S(∆I,∆T)and determine

all possible execution histories. Nevertheless we would have to replay all

these execution histories on the mutually other process schema. Due to the

possibly large number of creatable execution histories and their large volume

a severe performance penalty can be caused.

For these reasons we have to ﬁnd better suited approaches to verify Def. 5

for ∆Tand ∆I. The information we can use for this purpose comprises pro-

cess schemes S, SI, and Sand changes ∆Tand ∆I. Intuitively, taking this

information we come to the following three kinds of approaches (cf. Fig. 2):

(1) structural approaches which directly compare process schemes S, SI, and S,

(2) operational approaches directly contrasting changes ∆Iand ∆T(i.e., look-

ing at the two sets of applied change operations), and (3) hybrid approaches

(cf. Sect. 4) combining approaches (1) and (2). In the following we present these

variants and systematically rate their particular stenghts and limitations.

Disjoint and Overlapping Process Changes 111

Running Instances I

, …, I

1) Operational Approach

Comparing High - Level Change Operations

Advantages:

precise information

easy deduction of migration strategies

deduction of rules for user

Limitations:

con

text

dependent changes

compensating changes

hidden changes

overriding changes

2) Structural Approaches

♦

Delta - Analysis and Inheritance

Approaches

♦

Pure Approach: Comparing Type and

Insta nce Schemes

♦

Aggregated Approach: Comparing

Change Regions

Advantages:

no problem with context-dependent changes

no problem with compensating changes

no problem with overriding changes

Limitations:

not applicable for order - changing operations

complexity

deriving migration strategies?

(materialization of instance schema S I

)

3) Hybrid Approach:

Combine Operational Approach (Purged Changes) With Aggregated Structural Approach

Purged Change

Transaction Log Files

Fig. 2. Approach Overview to Detect Overlapping of Changes

3.1 Structural Approaches

The essence of all structural approaches is to compare process type schema S:=

S+∆Twith process instance schema SI:= S+∆Iin order to gain information

about the degree of overlap between ∆Tand ∆I. A promising approach to

analyze the diﬀerence between two process schemes, the so called Delta Analysis,

has been presented in [16] and used by v.d. Aalst and Basten in [12]. In [12] Delta

Analysis is based on four inheritance relations on process schemes. Roughly

speaking a process schema S1is a subclass of process schema S2if it can do

everything S2can do and more. With this, for example, v.d. Aalst and Basten

determine the Greatest Common Divisor (GCD) for process schemes S1and S2

which represents the common superclass of S1and S2. Though this approach

is very promising it cannot be adopted to the problem described in this paper

since it shows the reverse line of attack as the following example illustrates:

a) WF Net S:

S1:

x t

S2: y

Superclass

S1:

S2:

Superclass??

Fig. 3. Determining the Greatest Common

Divisor (Examples)

Consider process schemes S1and S2

(represented by WF Nets [2]–aPetri

Net based formalism) as depicted in

Fig. 3a). Applying the approach pre-

sented by v.d. Aalst and Basten [12]

we start from process schemes S1and

S2and determine the common super-

class S. By contrast, in our approach

we already have common divisor S

and derive process type schema S

and process instance schema SIby

applying ∆Tand ∆Irespectively.

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

However, considering the Delta Analysis approach we can already recognize

one common limitation of all structural approaches: they are not able to ade-

quately deal with order–changing operations. One example is depicted in Fig.

3b) where we cannot ﬁnd a process schema which represents a common behavior

for schemes S1and S2.

As a second possibility, consider the so called pure structural approach

(cf. Fig. 2). Here we exploit the set–based representation of WSM Nets (cf.

Sect. 2.1) and directly compare activity sets Nand NI, edge sets CtrlEand

CtrlEI,SyncEand SyncEI,DataEand DataEI,LoopEand LoopEI, and

data element sets Dand DIregarding the two process schemes

•S=(N,D

,NT,CtrlE, SyncE, LoopE, DataE) and

•SI=(NI,D

I,NT,CtrlE

I, SyncEI, LoopEI, DataEI).

However, doing so is unnecessarily expensive. Actually we do not have to

compare ”whole” activity and edge sets since they have been derived starting

with same original schema S, i.e., starting with the same activity and edge sets.

In other words we already know a common divisor S=(N,D,...) for Sand

SI. Therefore we can reduce complexity by exploiting the common ancestry of

Sand SIwhat results in a third method which we call aggregated structural

approach (cf. Fig. 2). More precisely, the aggregated structural approach works

by comparing diﬀerences between process type schema Sand original schema

Sand between process instance schema SIand original schema S. These

diﬀerences can be easily determined by building the following diﬀerence sets:

•Nadd

∆T:= N\Nand Nadd

∆I:= NI\N

•Ndel

∆T:= N\Nand Ndel

∆I:= N\NI

•CtrlEadd

∆T:= CtrlE\CtrlE and CtrlEadd

∆I:= CtrlEI\CtrlE

•and so on (cf. [17])

A ﬁrst example is depicted in Fig. 4a). Both ∆Tand ∆I1serially insert

activity Xat the same position (”between Band C”) into S1whereas ∆I2

serially inserts another activity Ybetween Aand B. Obviously, ∆Tand ∆I1

overlap since they oﬀend against claim (2) for disjoint changes (cf. Def. 5).

Using the aggregated structural approach, we obtain Nadd

∆T=Nadd

∆I1={X}. This

corresponds to the expected result, i.e., the multiple insertion of same activity

X. Regarding instance I2on S1,∆Tand ∆I2are disjoint according to Def. 5.

Application of the aggregated structural approach results in Nadd

∆T∩Nadd

∆I2=∅,

Ndel

∆T∩Ndel

∆I2=∅,CtrlEadd

∆T∩CtrlEadd

∆I2=∅, and CtrlEdel

∆T∩CtrlEdel

∆I2=∅.

Interpreting this result, we can state that ∆Tand ∆I2are disjoint.

These ﬁrst two examples from Fig. 4a) show that the aggregated structural

approach works ﬁne for insert (and delete) operations. Reason is that we are able

to precisely determine which activities have been inserted or deleted. In contrast,

for move operations the aggregated structural approach (and consequently the

pure structural approach) may be too imprecise4. Fig. 4b) shows a respective

4It is not suﬃcient to map a move operation onto respective delete and insert opera-

tions. Since activities are not really deleted or inserted structural approaches fail.

Disjoint and Overlapping Process Changes 113

A B C

C B A D

A B C D

A B X C

A Y B C

B A C D

C B

A D

S1: S1’: S2: S2’:

T = serialInsert(S, X, B, C)

T = serialMove(S, B, C, D)

I1 on SI1

= S

1 +

I1 with

I1 = serialInsert(S, X, B, C)

I2 on SI2

= S

1 +

I2 with

I2 = serialInsert(S, Y, A, B)

I1 on SI1 = S2 +

I1 with

I1 = serialMove(S, B, C

, D)

I2 on SI2 = S2 +

I2 with

= serialMove (S, A, B, C)

a) Process Type Level: b) Process Type Level:

Process Instance Level: Process Instance Level:

Fig. 4. Inserting and Moving Activities (Examples)

example: For all three changes on schema S2,Nadd

∆T=Nadd

∆I1=Nadd

∆I2=∅and

Ndel

∆T=Ndel

∆I1=Ndel

∆I2=∅holds (no activity has actually been inserted or

deleted). Determining the sets of newly inserted and deleted control edges for ∆T

and ∆I1yields CtrlEadd

∆T=CtrlEadd

∆I1={(A, C),(C, B),(B,D)}and CtrlEdel

∆T

=CtrlEdel

∆I1={(A, B),(B,C),(C, D)}respectively. From this result we can

conclude that ∆T∩∆I1=∅. Comparing the respective edge sets for ∆Tand

∆I2again we obtain: CtrlEadd

∆T∩CtrlEadd

∆I2=∅and CtrlEdel

∆T∩CtrlEdel

∆I2=∅.

This indicates that ∆T∩∆I2=∅holds. However, these results are too imprecise

since in both cases we cannot exactly determine which activity has been actually

moved. In case ∆Tand ∆I1are solely based on structural considerations, activity

Cas well as activity Bcould have been moved. When comparing ∆Twith ∆I2

we can only conclude that these changes actually overlap but we are not able

to make further statements. Both eﬀects – not knowing which activities have

been moved and imprecise statements about overlapping – are aggravated if

change transactions comprise several move operations. In summary, taking this

imprecise information it is not possible to derive adequate migration strategies.

3.2 Operational Approach

A solution to overcome the drawback of structural approaches in conjunction

with order–changing operations – not knowing which activities have been actu-

ally moved – may be to directly compare applied changes ∆Tand ∆I. Obvi-

ously, ∆Tand ∆Icontain precise information about applied changes in general

and about actually moved activities in particular. However, this operational ap-

proach also shows limitations. As summarized in Fig. 2 change transaction logs

may contain information about change operations which actually have no or only

hidden eﬀects on the underlying process schema. Reason is that the users who

deﬁne changes (i.e., the process designer or the end user) do not always act in a

goal–oriented way when modifying a process schema. In fact they may try out

the best solution resulting in noisy information within the change logs:

1. The ﬁrst group of changes without any eﬀects on Sare compensating

changes, i.e., changes mutually compensating their eﬀects. A simple exam-

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

ple is depicted in Fig. 5 where activity Zis ﬁrst inserted (between Fand

G) and afterwards deleted by the user. Therefore the respective operations

serialInsert(S,Z,F,G) and delete(S,Z) have no visible eﬀects on S.

2. The second category of noise in change logs comprises changes which only

have hidden eﬀects on S’. Such hidden changes always arise from deleting an

activity which is then inserted again at another position. This actually has

the eﬀect of a move operation. An example is given in Fig. 5 where activity

Eis ﬁrst deleted an then inserted again between Yand G. The eﬀect behind

is the same as of the respective move operation serialMove(S, E, Y, G).

3. There are changes overriding eﬀects of predeceding changes (note that a

change transaction is an ordered series of single change operations). Again

consider Fig. 5 where the eﬀect of the hidden move operation serialMove(S,

E, Y, G) (cf. 2.) is overwritten by move operation serialMove(S, E, F,

G), i.e., in Sactivity Eis ﬁnally placed between Fand G.

'T = ( serialInsert(S, X, C, F) ,

serialInsert (S, Y, X, F),

serialInsert (S, Z, F, G),

deleteActivity(S, E),

serialInsert (S, E, Y, G),

deleteActivity(S, Z),

serialMove(S, E, F, G))

G B F

Process Type Schema S: Process Type Schema S’:

Context-Dependent Changes

Compensating

Changes

Overriding Change

Hidden Change

No or Hidden

Effects on S’

Fig. 5. Process Type Change Transaction (Example)

However, the presence of compensating, hidden, or overriding changes within

a change transaction is a cumbersome but conquerable problem. Reason is that

we can ﬁnd methods to purge a change transaction from these kinds of changes

(cf. Alg. 1). Doing so is essential in order to ﬁnd a canonical and minimal view on

change logs. This, in turn, is necessary to be able to determine which activities

actually have been moved by a change.

A much more severe limitation of the operational approach is its disability

to adequately deal with context–dependent changes, i.e., changes which are mu-

tually based on each other. An example is depicted in Fig. 5: First, activity Xis

inserted serially between Cand F. Based on this a second activity Yis inserted

between Xand F. Obviously, the second insertion uses the newly added activity

of the ﬁrst insertion as change context.

Disjoint and Overlapping Process Changes 115

Why are such context–dependent process type and process instance changes

critical when applying the operational approach? Fig. 6 illustrates the under-

lying problem. Obviously, ∆Tand ∆Iare equivalent since Sand SIare trace

equivalent. Unfortunately, this equivalence relation cannot be determined based

on the depicted change transaction logs since ∆Tand ∆Ihave inserted activities

X, Y and Zin diﬀerent orders. Therefore the operational approach sketched so

far would only detect an overlapping (multiple insertion of same activities) but

not be able to determine the degree of overlap, i.e., the total equivalence between

∆Tand ∆I.

Process Type Schema S: Process Type Schema S’:

'T = ( serialInsert(S, X, A, B),

serialInsert(S, Y, X, B)

serialInsert(S, Z, Y, B))

A B

X Y Z B

Process Instance Schema SI = S + 'I :

I = ( serialInsert(S, Y, A, B),

serialInsert(S, Z, Y, B)

serialInsert(S, X, A, Y))

Fig. 6. Equivalent Process Type and Instance Changes (Example)

At this point an important conclusion is that structural approaches have no

problems with context–dependent changes. Consider again Fig. 6. Applying the

aggregated structural approach (cf. Sect. 3.1) we get Nadd

∆T=Nadd

∆I,Ndel

∆T=Ndel

∆I,

CtrlEadd

∆T=CtrlEadd

∆I, and CtrlEdel

∆T=CtrlEdel

∆Iand therefore ∆T≡∆Iholds.

In summary, at this point we have the following situation (cf. Fig. 2): Struc-

tural approaches are able to cope with context–dependent changes as well as

with compensating, hidden and overriding changes. Reason is that structural

approaches are based on the actual eﬀects on a process schema. However, they

are unable to adequately deal with order–changing operations. In contrast, when

applying the operational approach we are able to precisely determine which

activities have been moved but we are not able to handle context–dependent

changes. Altogether, in the following section we combine both methods to a hy-

brid approach in order to exploit the particular strengths and to overcome the

particular limitations.

4 The Hybrid Approach

The hybrid approach presented in the following combines elements of structural

and operational approaches (cf. Sect. 3). How this approach works in general

is presented in Sect. 4.1. How we can apply the hybrid approach to concurrent

process type and instance changes is illustrated in Sect. 4.2.

4.1 Purging Change Logs and Consolidated Activity Sets

Let Sbe a (correct) process schema and let ∆be a change which transforms

Sinto another correct process schema S:= S+∆. Informally, the hybrid ap-

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

proach works as follows: First, the activity sets actually inserted into and deleted

from S–Nadd

∆and Ndel

∆(cf. Sect. 3.1) – are determined (structural approach).

Taking this information the change log capturing ∆is purged. More precisely,

this purging is accomplished by scanning the log of change ∆=(op1,...,op

in reverse order and by determining for each change operation opi(i=1,...,n)

whether it actually has any eﬀects on S. If so we incorporate opiinto a new –

intially empty – change log ∆purged. Finally, in order to reduce the number of

necessary change log scans to one we use an auxiliary set Ato memorize which

activities have been already handled. In detail, the following considerations are

made when determining ∆purged:

–Assume that we ﬁnd a log entry opifor an operation inserting activity X

between activities src and dest into Sand that Xis not yet present in A,

i.e., opiis the last change operation within ∆which manipulates X.IfX

has been already present in S(X∈ Nadd

∆)ahidden change is found (cf.

Sect. 3.2). Consequently, a respective log entry for an operation moving X

between src and dest is created and written into ∆purged.

–If log entry opidenotes an operation deleting activity Xfrom Sand X∈ A

but Xis still present in S(X∈ Ndel

∆) then we have found a compensating

change. Therefore opi(and the respective insert operation) are left outside

∆purged.

–If log entry opidenotes an operation moving activity Xto a position between

activities src and dest and opiis the last operation within ∆which has eﬀects

regarding X(X∈ A) we have to distinguish between two cases: If Xhas

been inserted before opi(X∈Nadd

∆) we write a new log entry in ∆purged

denoting an operation inserting Xbetween src and dest.IfXhas been also

present in S(X∈ Nadd

∆) we write opiunalteredly into ∆purged.

In the following, the consolidated activity sets (Nadd

∆,Ndel

∆,Nmove

∆)

(cf. Def. 7) will serve as the basis for determining the degree of overlap between

changes. Note that Nadd

∆and Ndel

∆can be determined using the aggregated struc-

tural approach (cf. Sect. 3.1) but we have to use purged change logs (operational

approach) in order to obtain Nmove

∆.

A formalization of the method described above is given in Alg. 1. For the

sake of simplicity we restrict this description to serial insert operations. However

adopting parallel and branch insertions runs analogously.

Deﬁnition 7 (Purged Change Transaction; Consolidated Activity

Sets). Let S = (N, D, ...) be a (correct) process schema. Let further ∆

be a change which transforms S into another (correct) process schema S’ =

(N,S,...). Then the purged representation of ∆,∆purged and the consolidated

activity sets (Nadd

∆,Ndel

∆,Nmove

∆)can be determined by applying Algorithm 1.

Disjoint and Overlapping Process Changes 117

Algorithm 1. PurgeConsolidate(S, N, N’, ∆=(op1,...,op

n))−→

(∆purged,(Nadd

∆,Ndel

∆,Nmove

∆))

A:=∅;∆purged =∅;

Nadd

∆:= N\N;Ndel

∆:= N\N;

fori=nto1do{

if (opi= serialInsert(S, X, src, dest)) {

if (X ∈ A) {

A:=A∪{X}; //X not considered so far

if(X ∈ Nadd

∆){//X actually not inserted −→ hidden move

if (src =cpred(S, X) ∧dest =csucc(S, X)5){//Xmoved to another position?

∆purged.addFirst(serialMove(S, X, src, dest))//adds entry at beginning of ∆purged;

Nmove

∆:= Nmove

∆∪{X};}} else {

∆purged.addFirst(serialInsert(S, X, src, dest));}} continue};

if (opi= serialMove(S, X, src, dest)) {

if (X ∈ A) {

A:=A∪{X};

if (X ∈Nadd

∆){

∆purged.addFirst(serialInsert(S, X, src, dest)); }else {

if (src =cpred(S, X) ∧dest =csucc(S, X)) {

∆purged.addFirst(serialMove(S, X, src, dest));

Nmove

∆:= Nmove

∆∪{X};}} continue;}

if (opi= delete(S, X)) {

if (X ∈ A) {

A:=A∪{X};

if(X ∈Ndel

∆){

∆purged.addFirst(delete(S, X));}}}

∆purged.addFirst(opi);

}

return (∆purged,(Nadd

∆,Ndel

∆,Nmove

∆));

4.2 Application to Concurrent Process Type and Instance Changes

A practically relevant application of the hybrid approach introduced in Sect.

4.1 is to determine the degree of overlap between concurrent process type and

process instance changes. We illustrate this by the following example:

Fig. 7 shows the mode of operation of Alg. 1 applied to the log of change ∆Tin

Fig. 5. Initially, Alg. 1 determines the sets of newly inserted and deleted activities

regarding schema S, i.e., Nadd

∆T={X, Y }and Ndel

∆T=∅. Based on this informa-

tion change log ∆Tis traversed once (in reverse direction) and purged from noisy

operations op6,op

5,op

4,op

3. Algorithm 1 ﬁnishes with purged change transac-

tion ∆purged

T=(serialInsert(S, X, C, G), serialInsert(S, Y, X, G),

serialMove(S, E, F, G)) (cf. Fig. 7). Based on this purged change log the

set of activities actually moved by ∆Tcan be determined as Nmove

∆T={E}.

Together with the set of newly inserted and deleted activities we obtain consol-

idated activity sets (Nadd

∆T,Ndel

∆T,Nmove

∆T)=({X, Y },∅,{E}).

Purging change logs from noisy information has several advantages: First,

the purged form of a change log can be used as the canonical representation of

this change, i.e., if we have to compare changes (what we actually have to do

when determining the degree of overlap between them) we can use the purged

form as an adequate basis. Furthermore, purged change logs are also suﬃcient

to determine the diﬀerence between changes. This, for example, is necessary if

we want to calculate the instance bias after migration to the changed schema (if

5c pred(S, X) (c succ(S, X)) denotes all direct predecessors (successors) of X in S.

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

Change Log (in reverse order): Initialization:

Purged Change Log

A = ;

Tadd = {X, Y};

Tdel = ;

'T= ( 'purgedT= (

op7 = serialMove(S, E, F, G), E  A  A = {E};

E N

Tadd new pos.  op3 = serialMove(S, E, F, G),

op6 = deleteActivity(S, Z), Z  A  A = {E, Z};

Z N

Tdel;

op5 = serialInsert (S, E, Y, G), E  A;

op4 = deleteActivity(S, E), E  A;

op3 = serialInsert (S, Z, F, G), Z  A;

op2 = serialInsert (S, Y, X, F), Y  A  A = {E, Z, Y};

Y  N

Tadd  op2 = serialInsert(S, Y, X, F),

op1 = serialInsert(S, X, C, F)) X  A  A = {E, Z, Y,X};

X  N

Tadd  op1 = serialInsert(S, X, C, F),

Fig. 7. Purging A Change Log (Example)

bias and respective type change are not disjoint or equivalent). A more detailed

treatment of these issues can be found in [17].

5 Discussion

In the workﬂow literature, there are many approaches either dealing with process

type changes (”schema evolution”) or single process instance changes [11,7,2,3,

4,5]. Thereby, main focus has been put on providing appropriate correctness

criteria for deciding about compliance of unbiased instances. Although there

are some approaches [7,11] that provide common support for process type and

instance changes there is no interplay between them. WASA2[7], for example,

realizes changes of single process instances by deriving a new schema version with

exactly one running instance. Consequently, individually modiﬁed instances are

excluded from further process type changes.

Commutativity (cf. Sect. 2.2) is an important property in the context of

concurrent changes in cooperative applications. In [18], operations commute if

the state changes on an object as well as the values returned by the operations are

independent of the order in which they are executed. W¨asch and Klas claim that

concurrent changes on complex objects can be correctly carried out if they are

commutative followed by a history merge of the respective changes [19]. In this

paper, we use commutativity to deﬁne disjointness of changes. However, we do

not restrict correctness of concurrent changes on commutativity but we provide

advanced solutions for non commutative and therefore overlapping changes.

As discussed in Section 3.1 an interesting structural approach to compare

process schemes is the Delta Analysis based on inheritance relations [12]. The

used inheritance relations as well as our deﬁnition of disjointness and overlap-

ping are based on equivalence notions between process schemes. V.d. Aalst and

Basten use branching bisimilarity as equivalence relation [12,2,20,21]. There are

Disjoint and Overlapping Process Changes 119

actual effects

Fig. 8. Purging A Change Log (Prototype)

several other notions of equivalence between process schemes [13]. In [22], for

example, v. Glabbeek and Goltz provide a very nice classiﬁcation of semantic

equivalences based on the basic notions of bisimulation and trace equivalence.

Another approach to provide semantic equivalence of process schemes is given

[23]. This work oﬀers interesting methods to maintain the semantical meaning of

a process schema before and after the change by applying semantics–preserving

transformations.

6 Summary

In this paper, we have established a formal framework for dealing with concurrent

process changes. An important application of this results is the propagation of

process type changes to biased process instances. Based on the particular degree

of overlap between process type and instance change we have to choose diﬀerent

migration strategies. To be able to decide to which degree process changes overlap

we have presented an advanced approach which comprises structural aspects as

well as operational solutions like purging change transactions.

We have implemented the presented concepts within a proof–of–concept pro-

totype. Within this prototype migration of unbiased process instances as well as

migration of biased instances with disjoint bias can be correctly and eﬃciently

carried out. Furthermore, it can be precisely determined to which degree process

type and instance changes overlap. Alg. 1 for purging change logs has been im-

plemented. Fig. 8 depicts the example change log from Fig. 7 and the resulting

purged change log.

References

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

2. v.d. Aalst, W., Basten, T.: Inheritance of workﬂows: An approach to tackling

problems related to change. Theoret. Comp. Science 270 (2002) 125–203

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

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

Engineering 24 (1998) 211–238

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

In: Proc. COOCS’95, Milpitas, CA (1995) 10–21

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

workﬂow processes. IJCIS 9(2000) 93–116

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

without losing control. JIIS 10 (1998) 93–129

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

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

8. Rinderle, S., Reichert, M., Dadam, P.: On dealing with structural conﬂicts between

process type and instance changes. In: Proc. BPM’04. LNCS, Potsdam (2004)

9. Reichert, M., Rinderle, S., Dadam, P.: On the common support of workﬂow type

and instance changes under correctness constraints. In: Proc. CoopIS ’03, Catania,

Italy (2003) 407–425

10. Rinderle, S., Reichert, M., Dadam, P.: Correctness criteria for dynamic changes in

workﬂow systems – a survey. Data and Knowledge Engineering, Special Issue on

Advances in Business Process Management 50 (2004) 9–34

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

J.: IntelliGEN: A distributed workﬂow system for discovering protein-protein in-

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

12. v.d. Aalst, W., Basten, T.: Identifying commonalities and diﬀerences in object life

cycles using behavorial inheritance. In: Proc. ICATPN ’01, Newcastle, UK (2001)

32–52

13. Kiepuszewski, B.: Expressiveness and Suitability of Languages for Control Flow

Modelling in Workﬂows. PhD thesis, Queensland University of Technology, Bris-

bane (2002) (available via http://www.tm.tue.nl/it/research/patterns).

14. Rinderle, S., Reichert, M., Dadam, P.: Flexible support of team processes by

adaptive workﬂow systems. Distributed and Parallel Databases 16 (2004) 91–116

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

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

16. Guth, V., Oberweis, A.: Delta analysis of petri net based models for business

processes. In: Proc. Applied Informatics. (1997) 23–32

17. Rinderle, S.: Schema Evolution In Process Management Systems. PhD thesis,

University of Ulm (2004) (to appear).

18. Badrinath, B., Ramamritham, K.: Semantics-based concurrency control: Beyond

commutativity. ACM Transactions on Database Systems 17 (1992) 163–199

19. W¨asch, J., Klas, W.: History merging as a mechanism for concurrency control in

cooperative environments. In: Proc. RIDE’96, New Orleans (1996) 76–85

20. Basten, T.: Branching bisimilarity is an equivalence indeed! Information Processing

Letters 58 (1996) 141–147

21. Verbeek, E.: Veriﬁcation of WF–Nets. PhD thesis, Technical University of Eind-

hoven (2004)

22. v. Glabbeek, R., Goltz, U.: Reﬁnement of actions and equivalence notions for

concurrent systems. Acta Informatica 37 (2001) 229–327

23. Frank, H., Eder, J.: Equivalence transformations on statecharts. In: Proc.

SEKE’00, Chicago (2000) 150–158