Integrating Process Learning and Process Evolution - A Semantics Based Approach [original]

Integrating Process Learning and Process

Evolution – A Semantics Based Approach

Stefanie Rinderle1,BarbaraWeber

2,ManfredReichert

3, and Werner Wild4

1Dept. Databases and Information Systems, University of Ulm, Germany

[email protected]

2Quality Engineering Research Group, University of Innsbruck

[email protected]

3Information Systems Group, University of Twente, The Netherlands

[email protected]

4Evolution Consulting, Innsbruck, Austria

[email protected]

Abstract. Companies are developing a growing interest in aligning their

information systems in a process-oriented way. However, current process-

aware information systems (PAIS) fail to meet process flexibility require-

ments, which reduces the applicability of such systems. To overcome this

limitation PAIS should capture the whole process life cycle and all kinds

of changes in an integrated way. In this paper we present such a holis-

tic approach providing full process life cycle support by combining the

ADEPT framework for dynamic process changes with the concepts and

methods provided by case-based reasoning (CBR) technology. This al-

lows expressing the semantics of process changes, their memorization

and their reuse to perform similar changes in the future. If the same or

similar process instance changes occur frequently, potential process type

changes are suggested to the process engineer. The process engineer can

then perform a schema evolution and migrate running instances to the

new schema version by using the ADEPT framework. Finally, the case–

base related to the old schema version is migrated as well.

1 Introduction

Adaptive process management technology oﬀers a promising approach for realiz-

ing highly ﬂexible, process–oriented information systems [1,2,3,4]. In particular,

it enables dynamic process changes during runtime to handle exceptional situ-

ations and changing needs. Basically, such process changes can be made at two

levels – the process type and process instance level [5].

In our experience an adaptive process management system (PMS) must sup-

port both kinds of changes in an integrated way [6]. In the ADEPT project we

have elaborated a conceptual framework which enables changes at the process

instance and at the process type level. For the latter we support the subsequent

migration of both unbiased and biased process instances to the changed process

type schema. This is especially important for long–running process instances [7].

W.M.P. van der Aalst et al. (Eds.): BPM 2005, LNCS 3649, pp. 252–267, 2005.

Springer-Verlag Berlin Heidelberg 2005

Integrating Process Learning and Process Evolution 253

We denote process instances as unbiased if they are running according to the

original process schema they were derived from [8], whereas process instances

are denoted as biased when they have been individually modiﬁed by an ad–hoc

change [6].

So far, our work on adaptive processes (e.g., [7,8,9]) has not incorporated

application semantics, i.e., it has not considered the reasons for and the con-

text of a change. Instead, very similar to database technology, all checks and

procedures necessary to perform a dynamic change have been applied solely at

the syntactical level, which, nevertheless, is an important prerequisite for any

adaptive process management technology. To provide more intelligent support

to its users and to reuse knowledge about previously applied process changes

semantical aspects must be considered as well. This paper shows how adding

semantics contributes to the seamless integration of process changes into the

process life cycle (cf. Fig. 1).

Lab

test

Add / Reuse

Case LabTest

IQ(Q= 1...n)

Changed Process

Instances

Lab

test

CCBR

Instantiation

ProcessTypeChange

Process Instance Change

Notification

Thresholdexceeded

Process Instances

Process User

Process Engineer

Process

Engineer

Migrate

case-base

Prepare

Patient

Examine

patient

Make

appointment

Schema S‘:

Enter

order Inform

patient

Lab

Test

Make

appointment

Deliver

report

Prepare

Patient

Schema

Enter

order Inform

patient

Prepare

Patient

Examine

patient

Deliver

report

Make

appointment

Fig. 1. Process Life Cycle

In this paper we combine the ADEPT framework for process changes with

the concepts and methods provided by CBRFlow [10], a process change ap-

proach using case-based reasoning (CBR) technology. This allows us to express

the semantics of process changes and to provide users with information about

the context of and the reasons for process changes, ensuring the traceability of

instance changes. The latter is a crucial requirement in many domains (e.g., hos-

pitals have strict guidelines regarding the documentation of deviations from the

predeﬁned treatment process). Respective change information is stored as cases

254 S. Rinderle et al.

in a process schema speciﬁc case–base. This information can be used to sup-

port process actors in reusing information about similar ad-hoc changes which

have been applied to previously executed process instances. Change deﬁnition

requires signiﬁcant user experience, especially when further adaptations become

necessary (e.g., when deleting a particular activity, data-dependent activities

may have to be deleted as well [9]). Therefore, reuse of existing knowledge about

previous ad-hoc changes is highly desirable.

Furthermore, case–bases are continuously monitored in order to automati-

cally derive suggestions for process type changes from previously applied process

instance changes. In practice, necessary type changes are frequently indicated by

process instances whose execution deviates from the original process type schema

over and over again. In such a situation a process type change is desirable to

move the respective optimizations up to the process type level.

In the ADEPT framework a process type change is performed by deriving a

new version of the process type schema and – if possible and desired – by au-

tomatically migrating the already running process instances to this new schema

version [7,8]. This may include the migration of both unbiased and biased process

instances. Interestingly, not only processes but also case-bases evolve over time.

When a case–base is ”migrated” to a new process schema version, it should only

keep information which is still relevant for instances of the new process schema

(and for changes to them). In our approach a process schema evolution is al-

ways accompanied by the evolution of the related case-base. This poses several

challenges which will be discussed later in this paper.

In Section 2 we provide background information. Section 3 presents funda-

mentals of CBR and their application to process instance changes. In Section 4

we show how to learn from instance changes by using CBR techniques and we

provide an overview of our process evolution approach. The evolution of case–

bases is described in Section 5. We discuss related work in Section 6 and close

with a summary and an outlook in Section 7.

2 Background Information

In this section we give basic deﬁnitions for process type schemes and process

instances as needed for our further considerations. To improve readability we

restrict the discussion to Activity Nets [11]; however, our approach is applicable

to more complex process meta models as well (e.g., WSM Nets [7]).

For each business process to be supported a process type Tis deﬁned. It is

represented by a process type schema which may exist in diﬀerent versions.

Definition 1 (Process Type Schema). A tuple S with S = (N, D, CtrlEdges,

DataEdges, EC) is called a process schema, 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)

Integrating Process Learning and Process Evolution 255

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

activities and data elements

–EC: CtrlEdges → Conds(D) where Conds(D) denotes the set of all valid

transition conditions on data elements from D.

For a process type schema several correctness constraints exist, e.g., (N,

CtrlEdges) must be an acyclic graph to ensure the absence of deadlocks.

At runtime new process instances are created from a process schema Sand

are then executed. Each instance Iis associated with an instance-speciﬁc schema

SI:= S+∆I1. S = S(T,V) denotes the original process schema Sfrom which

instance Iwas derived, whereby T is the process type of Iand V the version of

the process type schema. ∆I={op1, ..., opn}comprises the change operations

opi(i = 1, ..., n) applied to I so far (cf. Fig. 4). In this context a change operation

opi=(opType,s,paramList) (i = 1, ..., n) is speciﬁed by an operation type (e.g.,

insertion of an activity), a subject (e.g., the newly inserted activity), and a list

of parameters (e.g., position of the newly inserted activity). Selected change

operations are shown in Table 1.

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

eits marking ES(e). Markings are determined according to well deﬁned rules,

markings of already passed regions and skipped branches are preserved.

Definition 2 (Process Instance). A process instance I is defined by a tuple

(T, V, ∆I,MSI,Val

SI)where

–T denotes the process type of Iand V the version of the process schema S

:= S(T,V) = (N, D, CtrlEdges, ...) instance I was derived from. We call S

the original schema of I.

–∆Icomprises the instance-specific changes op1,...,op

mthat have been ap-

plied to I so far2.Wecall∆Ithe bias of I. Schema SI:= S+∆I(with

SI=(NI,D

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

the instance–specific schema of I.

–MSI=(NS

SI,ES

SI) describes node and edge markings of I:

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

Skipped}

ESSI:(CtrlEdgesI)→{NotSignaled, TrueSignaled, FalseSignaled}

–ValSIis a function on DI. It reflects for each data element d ∈DIeither

its current value or the value UNDEFINED (ifdhasnotbeenwrittenyet).

Table 1 presents a selection of high-level change operations on process

schemes which can be used to create or modify schemes at the type as well

as at the instance level. These change operations also include formal pre- and

1For unbiased instances ∆I(S)=∅and consequently SI=Sholds.

2Thereby an operation opj:= (opT ypej,s

j, paramListj) (j = 1, ..., m) consists of

an operation type opTypej,thesubjectsjof the change, and a parameter list

paramListj(cf. Tab. 1).

256 S. Rinderle et al.

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

tions while ensuring schema correctness. An example for such a change operation

is the insertion of an activity and its embedding into the process context.

Table 1. A Selection of High-Level Change Operations on Process Schemes

Change Operation opType subject paramList Eﬀects on S

op Applied to S

Additive Change Operations

sInsert(S, X, A, B) Insert X S, A, B inserts activity X between two directly

succeeding activities A and B

cInsert(S, X, A, B, sc) Insert X S, A, B, sc inserts activity X between two directly

succeeding activities A and B as a new

branch with selection code sc; edge (A,

B) gets selection code ”default”

Subtractive Change Operations

delAct(S, X) Delete X S deletes activity X from schema S

Order-Changing Operations

sMove(S, X, A, B) Move X S, A, B moves activity X from its current posi-

tion to position between directly suc-

ceeding activities A and B

3 Providing Change Semantics Through CCBR

In this section we describe how CBR can be used to capture the semantics of

process changes, how these changes can be memorized, and how they can be

retrieved and reused when similar changes become necessary in the future.

3.1 Introduction to Case-Based Reasoning

Case-based reasoning (CBR) is a contemporary approach to problem solving

and learning [12]. New problems are dealt with by drawing on past experiences

– described in cases and stored in case–bases – and by adapting their solutions

to the new problem situation. Reasoning by using past experiences is a powerful

and frequently applied way to solve problems by humans [13]. A physician, for

example, remembers previous cases to determine the disease of a new patient. A

banker working on a diﬃcult loan decision uses her experiences about previous

cases in order to decide whether to grant a loan or not.

A case is a contextualized piece of knowledge representing an experience [12],

which typically consists of a problem description and the corresponding solution.

As opposed to most other approaches in Artiﬁcial Intelligence, CBR uses spe-

ciﬁc knowledge of past experiences to solve new problems. CBR also contributes

to incremental and sustained learning: every time a new problem is solved, in-

formation about it and its solution is retained and therefore immediately made

available for solving future problems [13].

Conversational CBR (CCBR) is an extension of the CBR paradigm, which

actively involves users in the inference process [14]. A CCBR system can be char-

acterized as an interactive system that, via a mixed-initiative dialogue, guides

users through a question-answering sequence in a case retrieval context (cf.

Integrating Process Learning and Process Evolution 257

Title

Description

Question-Answer Pairs

Question Answer

Patient has diabetes? Yes

What is the patient’s age? > 40

Actions

sInsert LabTest S, PreparePatient, Examine Patient

Operation Type Subject Parameters

Select Operation Type Insert

Select Activity/Edge Lab Test

Please Answer the Questions

Question Answer

Patient has diabetes? Yes

What is the patient’s age? > 40

Lab Test required

Title

125

Case ID

100%

Similarity

Reputation Score

Display List of Cases

Fig. 2. CCBR User Dialogs - Adding a New Case and Retrieving Similar Cases

Fig 2). Unlike traditional CBR, CCBR neither requires the user to provide a

complete a priori problem speciﬁcation for case retrieval nor requires him to

provide knowledge about the relevance of each feature for problem solving. In-

stead, the system assists the user in ﬁnding relevant cases by presenting a set of

questions to assess the given situation. It guides users who can supply already

known information on their initiative. Therefore, CCBR is especially suitable for

handling exceptional or unanticipated situations that cannot be dealt with in a

fully automated way.

3.2 Conversational Case-Based Reasoning and Adaptive Workflows

In our approach CCBR is used to provide semantical information about changes

to process instances. This information can be reused when either similar ad-hoc

modiﬁcations become necessary or to trigger process type changes.

Case Representation. In our context, a case crepresents a concrete ad-hoc

modiﬁcation to one or more process instances providing the context of and the

reasons for the deviation (cf. Fig. 2). It consists of a textual problem description

pd which brieﬂy describes the exceptional or unanticipated situation which made

the ad-hoc modiﬁcation necessary. The reasons for the change are described as

question-answer pairs {q1an1, ..., qnann}. Each question-answer pair denotes

a condition under which the modiﬁcation has become necessary; they are used

to retrieve similar cases when a problem arises in the future. The solution part

sol (i.e., the list of actions) contains the change operations (and related context

information) to be executed to deal with the exceptional or unanticipated situ-

ation. Finally, the reputation score rScore of a case indicates how successfully

it has been reused in the past, i.e., the trust users can have into the semantical

correctness of this case. The reputation score is calculated as the sum of the

feedback scores (see below).

Definition 3 (Case). A case c is a tuple (pd, {q1an1, ..., qnann}, sol, rScore)

where

–pd is a textual problem description

–{q1an1, ..., qnann}denotes a set of question-answer pairs

258 S. Rinderle et al.

–sol = {opj|opj=(opT ypej,s

j, paramListj), j = 1, ..., k}is the solution

part of the case denoting a list of change operations (i.e., the changes that

have been applied to one or more process instances; cf. Def. 2)

–rScore indicates how successfully case chas been applied in the past. It is

calculated as the sum of the feedback scores.

All information on process instance changes related to a process schema

version Sare stored as cases in the associated case-base of S.

Definition 4 (Case–Base). A case–base cbT,V is a tuple (T, V, {c1,...,c

m},

freqT,V )) where

–S := S(T,V) denotes the schema version cbT,V is currently associated with

–{c1,...,c

m}denotes a set of cases

–freqT,V (ci)denotes the frequency ciwas reused in connection with schema

version S(T,V) in the past, formally:

freqT,V :{c1,...,c

m} → N

Case Retrieval. When deviations from the predeﬁned process schema become

necessary, the user initiates a case retrieval dialog in the CCBR component.

The system then assists her in ﬁnding already stored similar cases (i.e., change

scenarios in our context) by presenting a set of questions. The user may apply

a ﬁlter to the case-base and/or answer any of the questions in arbitrary order.

Filtering is done by speciﬁying an operation type opT ype and a subject son

which the operation is supposed to operate on. Cases not matching the ﬁlter

criteria are removed from the displayed list of cases. The system then searches

for similar cases by calculating the similarity for each case in the ﬁltered case-

base and displays the top nranked cases (ordered by decreasing similarity) as

well as their reputation scores. This is repeated for any other question answered

by the user. Case similarity is calculated by dividing the number of correctly

answered questions minus the number of incorrectly answered questions by the

total number of questions in the case [15].

Case Reuse. When a user decides to reuse an existing case, the actions speciﬁed

in the solution part of the case are forwarded to and performed by the ADEPT

change engine. The reuse counter is incremented and a work item is created for

this user for evaluating the ad-hoc change later on to maintain the quality of the

case-base.

Adding a New Case. If no similar cases can be found when performing a

process instance change, the user adds a new case c=(pd, {q1an1,...,},sol,1)

to case-base cbT,V . She enters this case by brieﬂy describing the current problem

pd and by entering a set of question-answer pairs to describe the reasons for the

ad-hoc deviation. Question-answer pairs can be entered either by selecting the

question from a list of previously deﬁned questions (i.e., reusing questions from

existing cases) or, if there is no suitable question in the system, by deﬁning a new

one and by giving the appropriate answer. The user then speciﬁes the actions

to perform by selecting the desired operation types opT ype1,...,opType

p. She

Integrating Process Learning and Process Evolution 259

further deﬁnes the subjects s1,...,s

pthey operate on (e.g., activities and control

edges), and provides the parameters for each selected operation. Moreover, the

reuse counter of the case is initialized to 1. Finally, the case is stored in case-base

cbT,V of process schema S=S(T,V) and thus immediately made available for

future reuse.

Ensuring Semantical Correctness through Evaluation Mechanisms. In

our approach we use the concept of reputation to indicate how successfully an ad-

hoc modiﬁcation represented by a case has been applied in the past. Whenever a

user adds or reuses a case she is encouraged to provide feedback on the performed

process instance change. For this, a work item representing the feedback task

is generated and inserted in the worklist of this particular user. She then can

later rate the performance of the respective ad-hoc modiﬁcation either with 2

(highly positive), 1 (positive), 0 (neutral) , -1 (negative) or -2 (highly negative),

and may optionally specify additional comments. The reputation score of a case

is calculated as the sum of feedback scores regarding the ad-hoc modiﬁcation

speciﬁedinthiscase.Whileahighreputationscoreofacaseisanindicator

for its semantical correctness, negative feedback probably results from problems

after performing a process instance change. As ADEPT ensures the syntactical

correctness of changes, a negative feedback thus indicates semantical problems.

Negative feedback therefore results in an immediate notiﬁcation of the process

engineer, who can then deactivate the case to prevent its further reuse. The case

itself, however, remains in the system to allow for learning from failures as well

as to maintain traceability.

Example 1. As depicted in Fig. 3 the examination of a patient usually takes

place after a preparation step. Before an examination the physician recognizes

that the patient suﬀers from diabetes and he detects several other important risk

factors. The physician decides to request an additional lab test for this patient

to be performed after activity Prepare patient and before activity Examine

Patient. As the system contains no similar cases, the physician enters a new

case describing the situation and the action to be taken (cf. Fig. 2). ADEPT then

checks whether inserting activity Lab Test is possible for the respective process

instance, and, if so, applies the speciﬁed insert operation to that instance. The

latter includes updating the instance markings and all user worklists. If, for

example, Prepare patient is completed and Examine Patient is activated,

this activation will be undone (i.e., respective work items are removed from all

user worklists) and the newly inserted activity Lab test becomes immediately

activated. In any case, the newly inserted activity is treated like any other process

step, i.e., the same scheduling and monitoring facilities exist.

When talking with another diabetic patient later on, the physician vaguely

remembers that there has been a similar situation before and initiates the CCBR

sub-system to retrieve similar cases. For example, as he still remembers that he

had performed an additional lab test he selects the Insert operation type as well

as the Lab Test activity to optionally ﬁlter the case-base. He then answers the

questions presented by the system, ﬁnds the previously added case, and reuses

it (cf. Fig. 2).

260 S. Rinderle et al.

Enter

order

Examine

patient

Deliver

report

Make

appointment

Prepare

Patient

Prepare

Patient

Examine

patient

Make

appointment

Deliver

report

Prepare

Patient

Examine

patient

Make

appointment Prepare

Patient

Examine

patient

Make

appointment

Lab

test

Process Instance I:

Enter

order

Prepare

Patient

Examine

patient

Make

appointment

Lab

test

Prepare

Patient

Examine

patient

Make

appointment

Deliver

report

Prepare

Patient

Examine

patient

Make

appointment Prepare

Patient

Examine

patient

Make

appointment

Lab

test

Process Instance I:

Enter

order

Prepare

Patient

Examine

patient

Make

appointment

Lab

test

Prepare

Patient

Examine

patient

Make

appointment

Deliver

report

Prepare

Patient

Examine

patient

Make

appointment Prepare

Patient

Examine

patient

Make

appointment

Lab

test

Process Instance I:

Enter

order

Prepare

Patient

Examine

patient

Make

appointment

Reuse Frequency 104

Question-Answer Pairs

Question Answer

Patient has diabetes? Yes

What is the patient’s age? > 40

Actions

sInsert LabTest S, PreparePatient, Examine Patient

Operation Type Subject Parameters

Case ID 1

Title Lab test required

Reputation Score 104

Perform Process Type Changes

Lab

test

Deliver

patient

Schema Version S := S(T,1)

Enter

order

Lab test

Examine

patient

Deliver

report

Make

appointment

sc1: age > 40 

diabetes =„yes“

Prepare

Patient

patData patData

sc2: default

Process Engineer

Schema Version S‘ := S(T,2)

Process

User

Fig. 3. Perform Process Type Change

4 Process Learning and Seamless Process Evolution

When the same or similar changes occur frequently, the process engineer is noti-

ﬁed about the potential need for a process type change (Sect. 4.1). The process

engineer can then perform a change of the process type schema and migrate

running instances to the new schema version by using the ADEPT framework

(Sect. 4.2).

4.1 On Suggesting Process Optimizations

To derive suggestions for process type changes from a collection of previous

instance changes we need the following information:

–Case–base cbT,V =(T,V,{c1, ..., cm},freq

T,V )

–rIT,V denoting the number of process instances created from schema version

S:=S(T,V)

–thr denoting a conﬁgurable threshold (0 ≤thr ≤1)

If there is a case cj∈cbT,V with

freqT,V (cj)

rIT,V

≥thr (1)

Integrating Process Learning and Process Evolution 261

the process engineer is notiﬁed that a process type change should be considered.

In this notiﬁcation the system suggests the solution part soljof the respective

case cjas the process type change to be applied, but allows the process engineer

to customize it if desired.

Example 2. Let rIT,V =10397,thr=0.01,cb

T,V ={c1= (..., sol1={insert(S,

X, A, B)},...)},andfreqT,V (c1)= 104. As freqT,V (cj)

rIT,V =104

10397 exceeds threshold

0.01, the system suggests to pull change operation sInsert(S, X, A, B) up to the

process type level.

Generally, the situation is more complex, as a certain change operation may

have been applied to several instances for diﬀerent reasons. Note that in our

approach this is reﬂected by sets of diﬀerent question-answer pairs in separate

cases. As a consequence the respective case–base contains distinct cases, i.e.,

cases with the identical solution parts but diﬀerent question-answer pairs. Then

equation (1) is no longer adequate and must be adapted for a set of cases.

Example 3. Let rIT,V =10397 and thr = 0.01;cb

T,V now becomes:

cbT,V ={c1= (..., sol1={sInsert(S, X, A, B)}, ...),

c2= (..., sol2={sInsert(S, X, A, B)}, ...),

c3= (..., sol3={sInsert(S, X, A, B)}, ...), ... }with

freqT,V (c1)=48,freqT,V (c2)=23,andfreqT,V (c3)=33

Exceeding the threshold thr can be determined by summing over the frequen-

cies of all cases which have the same solution part, i.e., if there is a set of cases

cbT,V (sol) := {csol =(..., sol, ...)∈cbT,V )}with

cj∈cbT,V (sol)freqT,V (cj)

rIT,V

≥thr (2)

Thus, in the example above a process type change is indicated and the system

suggests sol as process type change to the process engineer (e.g., sInsert(S,

X, A, B)).

Equation (2) still does not reﬂect the most general scenario as the solution

parts of the cases indicating a process type change may not be identical but may

have one or more overlapping changes.

Example 4. Assume the following example (rIT,V =10397 and thr = 0.01):

cbT,V ={c1= (..., sol1={sInsert(S, X, A, B), delAct(S, C)}, ...),

c2= (..., sol2={sInsert(S, X, A, B)}, ...),

c3= (..., sol3={sInsert(S, X, A, B)}, ...), ... }with

freqT,V (c1)=48,freqT,V (c2)=23,andfreqT,V (c3)=33

All cases contain the same change operation sInsert(S, X, A, B) but case

c1contains an additional change operation delAct(S, C).Thisisnotrelevant

for the evaluation of the case-base and the suggested process type change. (Note

that the migration of the respective process instances is handled by the process

262 S. Rinderle et al.

schema evolution framework [7].) This can be taken into account by determining

the following set

cbT,V (sub sol) := {c=(..., sol, ...)∈cbT,V )|sub sol ⊆sol }

and by applying equation (3):

cj∈cbT,V (sub sol)freqT,V (cj)

rIT,V

≥thr (3)

In this case sub sol is suggested to the process engineer as the process type

change to perform (sInsert(S, X, A, B) in our example).

The process engineer has to examine the cases that exceeded the threshold

as well as the cases with overlapping solution parts in order to decide how to

perform the process type change. When a change operation is relevant for all

process instances it can be pulled up to the process type level. In most situations

the change operations cannot directly be applied to the process schema as the

changes have been performed in a particular context. Examining the question-

answer pairs allows the process engineer to gain valuable insights into the context

of a change operation as each question-answer pair represents a (semantic) con-

dition under which the case was applied. Assume, for example, that a particular

change operation has been primarily performed for patients older than 40 years

who suﬀer from diabetes. Therefore, the solution part of the case is not directly

pulled up to the process type level, but the process engineer inserts the neces-

sary XOr nodes and transitions (cf. Fig. 3). However, it must be ensured that

the necessary data, e.g., patient’s age and diabetes (yes/no), is provided to the

running process instances after applying the respective process type change, i.e.,

to guarantee that all necessary data is available within the system.

In the ADEPT approach change operations have formal pre- and postcon-

ditions which ensure their correct application, in particular a correct data ﬂow

after applying the changes. Therefore, if we can insert a new XOrSplit at the

process type level it is guaranteed that all necessary data is available at runtime,

as ADEPT allows the application of correct changes only. Data availability can

be achieved if either the activities preceding the XOr-Split set the respective

data elements (e.g., activity admit patient writes patient age and diseases)

or parameter provisioning services are inserted directly before the XOrSplit. At

runtime these services ask the user for the missing information.

4.2 Process Schema Evolution and Process Instance Migration

Assume that the process engineer decides to apply change operation cInsert(S,

Lab test, Prepare Patient, sc1) as depicted in Fig. 3 and 4. The challenge

is then to migrate the already running process instances to the new schema

version S’. As we can see from Fig. 4 we are confronted with diﬀerent kinds

of running process instances: instances still running according to their original

schema (unbiased instances, e.g., I1) and instances which have already been indi-

vidually modiﬁed (biased instances, e.g., I2–I4). We further have to distinguish

between biased instances for which their instance–speciﬁc change (bias) overlaps

the process type change (e.g., I3,I4) and biased instances with a disjoint bias

Integrating Process Learning and Process Evolution 263

Process Type Level:

Enter

order

Examine

patient

Deliver

report

Make

appointment

Prepare

Patient

Schema Version S := S(T,1)

Enter

order

Lab test

Examine

patient

Make

appointment

sc1: age > 40 

diabetes =„yes“

Prepare

Patient

patData patData

sc2: default

Schema Version S‘ := S(T,2)

I1on S: Migration Policy 1:

adapt markings

Migration Policy 1:

adapt markings

CompletedActivated

Process Instance Level:

Lab test

'T= cInsert(S, Lab test, Prepare Patient,

Examine Patient, sc1)

I1on S‘:

unbiased

I3on S: I3on S‘:

I2on S: disjoint bias Migration Policy 2:

adapt markings +

keep bias on S‘

Migration Policy 2:

adapt markings +

keep bias on S‘

I2on S‘:

subsumption equivalent bias Migration Policy 3:

adapt markings +

bias on S‘ = 

Migration Policy 3:

adapt markings +

bias on S‘ = 

I4on S: I4on S‘:

'I3(S)= {sInsert(S, Lab test, Prepare Patient, Examine Patient)} 'I3(S‘)= 

'I4(S)= {sInsert(S, Lab test, Prepare Patient, Examine Patient),

delAct(S, deliver Report)

'I4(S‘)= [delAct(S‘, deliver Report)}

provide suggestion

to user

provide suggestion

to user

partially equivalent

Deliver

report

'I2(S)= {delAct(S, deliver Report)}

Fig. 4. Process Instance Migration

(e.g., I2). Process instances with overlapping bias have already anticipated the

process type change (cf. Sect. 4.1) and require a diﬀerent migration policy than

the process instances with disjoint bias (for details see [16]).

For unbiased process instances state–related compliance with the new schema

version has to be checked [8]. Compliant instances are then migrated to the new

schema version by applying marking adaptations (as, for example, depicted in

Fig. 4 for instance I1). Process instances with disjoint bias can be migrated to

the new schema version Sif they are compliant regarding their state and their

structure [6]. In Fig. 4 instance I2has a disjoint bias and is compliant with S.

Therefore I2is migrated to the new schema version by adapting its marking and

keeping its instance–speciﬁc bias in the new schema version (cf. Tab. 2).

The most interesting question is how to deal with the process instances which

have totally or partially anticipated the process type change (resulting in an

overlap of process type and instance–speciﬁc changes). The migration policy to

be applied to such instances depends on the particular degree of overlap between

process type and instance–speciﬁc changes, which can be determined precisely by

ahybrid approach (for details see [7,16]). Table 2 shows the diﬀerent degrees of

overlap and the related migration policies; default migration policies for partially

equivalent changes can only be provided in certain situations.

In Fig. 4, for example, instance I3would be classiﬁed as having a subsumption

equivalent bias related to type change ∆T.∆I3and ∆Tboth insert activity lab

264 S. Rinderle et al.

Table 2. Degrees of Overlap Between Changes and Related Migration Policies

Degree of Overlap between ∆Tand ∆IMigration Policy

∆Tand ∆Idisjoint, i.e., ∆T∩∆I=∅•apply ∆Ton SI:= S+∆I

•migrate I to S’

•∆I(S)=∆I(S)

∆Tand ∆Iequivalent, i.e., ∆T≡∆I•migrate I to S’

•∆I(S)=∅

∆Tsubsumes ∆I, i.e., ∆T≺∆I•migrate I to S’

•calculate ∆I(S)

∆Isubsumes ∆T, i.e., ∆I≺∆T•migrate I to S’

•∆I(S)=∅

∆Tand ∆Ipartially equivalent, i.e., ∆T∆Idefault policies not always possible

→provide suggestion to user

test, but ∆Tadditionally creates an alternative branching. According to Table

2, I3canbemigratedtoSby adapting the instance markings of I3. The instance-

speciﬁc bias ∆I3(S) becomes empty after the migration. Comparing ∆Twith

∆I4we see that both changes are partially equivalent, thus we cannot provide a

default migration strategy [7], but only make a suggestion to the user (cf. Fig.

4). Note that there are optimizations regarding the determination of the precise

degree of overlap [7].

In total, we provide a complete framework for migrating process instances to

a new schema version even if they have anticipated the type change. This closes

the process life cycle depicted in Fig. 1.

5Case–BaseEvolution

Process type changes are accompanied by migrating compliant process instances

to the new schema version Sas well as migrating the associated case-base cb to

cb. The challenge is to decide which cases of case-base cb should be transfered

to cband which ones are already covered by the new schema version Sand can

therefore be dropped.

If a case or a group of cases exceeds the predeﬁned threshold the resulting

process type change can either be relevant for all process instances or only for

a particular subset (cf. Section 4.1). In the former scenario the solution parts

of the cases that triggered the change are directly reﬂected in the new process

schema S. Therefore, cases whose solution part is a subset of ∆Tare not trans-

ferred to the new case-base version cb. Cases whose solution parts are a true

superset of ∆Tare presented to the process engineer who then decides whether

to transfer these cases or not. Cases without overlapping solution parts are auto-

matically transferred to cbas they are not covered by S. In the latter scenario

the migration from cb to cbis more complicated. It involves ﬁnding the regions

of the process graph that are aﬀected by the process type change ∆T.Inour

example the change region corresponds to the subgraph induced by the newly

Integrating Process Learning and Process Evolution 265

CCBR:

cb := cbT,1:

c1: (..., {sInsert(S, X, C, D)}), freqS(c1) = 48

c2: (..., {sInsert(S, X, C, D)}), freqS(c2) = 23

c3: (..., {sInsert(S, X, C, D)}), freqS(c3) = 33

c4: (..., {sInsert(S, Y, A, B)}), freqS(c4) = 5

c5: (..., {deleteAct(S, D)}), freqS(c5) = 60

c6: (..., {deleteAct(S, E),

sInsert(S, Y, A, B)}), freqS(c6) = 2

cb‘ := cbT,2:

Case-Base Migration

'T1 = {sInsert(S, X, C, E), deleteAct(S, D)} 'T2 = {deleteAct(S‘, F)}

Process Type Level:

Enter

order

Examine

patient

Deliver

report

Make

appointment

A C D E

Prepare

Patient

Schema Version S := S(T,1)

Enter

order

Lab test

Examine

patient

Deliver

report

Make

appointment

D E

sc1: age > 40 

diabetes =„yes“

Prepare

Patient

patData patData

sc2: default

Schema Version S‘ := S(T,2)

Process Type

Change 'T

c4: (..., {sInsert(S, Y, A, B)}),

c5: (..., {deleteAct(S, D)})

c6: (..., {deleteAct(S, E),

sInsert(S, X, C, D)})

c7: (..., {sInsert(S, Y, A, B)})

c8: (..., {deleteAct(S, B)})

c1, c2, c3

c4, c6

c7, c8

dropped by process engineer

automatically transferred

transfered by process engineer

new cases for instances based on S'

Migration

'T= cInsert(S, Lab test, Prepare Patient, Examine Patient, sc1)

Fig. 5. Case–Base Evolution

inserted activity Xand the insertion context (i.e., activities Cand D). It can be

determined by applying the hybrid approach described in [7]. The cases which

contain change operations referring to activities or edges within these regions

as subjects or parameters are presented to the process engineer who then can

manually transfer relevant cases. All other case are automatically transferred to

case-base cb.

Example 5. As illustrated in Fig. 5 the process engineer has been notiﬁed to

perform a schema evolution as cases c1, ..., c3exceed the predeﬁned threshold

value. After migrating schema Sto Sthe process engineer hastomigratecase-

base cb to cbas well. Cases c4and c6are automatically transferred to cbas

they do not use activities or edges within the aﬀected process graph region. All

other cases are presented to the process engineer, who then decides to drop cases

c1, ..., c3which are already covered by the process type change and to transfer

case c5. Of course, new cases may be added to cbdue to ongoing ad-hoc changes

of instances based on S. Later on, migrating cbwill become necessary when

another process schema evolution takes place.

6 Related Work

Process Mining [17] and Delta Analysis [18,19] are techniques to improve the

quality of business processes. Though these approaches are very inspiring, they

do not answer how they feed the improved process type schemes into the system.

To our best knowledge this is accomplished by establishing the mined process

schemes as new process type schema versions. Already running process instances

266 S. Rinderle et al.

are then completed according to the ”old” (suboptimal) process type schema and

new instances are started according to the improved one. This leads to a ”gap”

within the process life cycle which can be closed by applying the derived process

optimization to the current process type schema. Already running process in-

stances are then smoothly migrated to the improved process type schema [15,20].

Related work also includes approaches dealing with process schema evolution

[1,2,4,21]. However, none of them covers the interplay between process type and

process instance changes, i.e., there is no approach which allows to migrate biased

process instances to a changed process type schema.

This paper is based on the idea of integrating ADEPT [9] and CCBR [10] (see

also [15]). In related work traditional CBR has been applied to conﬁgure com-

plex core processes by using process components [22]. Workﬂows are conﬁgured

during their instantiation by combining predeﬁned process components in order

to reduce the number of possible process variants. As each process instance has

to be conﬁgured before its start, this approach is more suitable for long-running,

complex core processes with a limited number of process instances; the process

conﬁguration is similar to a project planning task. Similarily, Madhusudan et al.

[23] use CBR to provide workﬂow modeling support by facilitating the reuse of

existing models and their components. In contrast to our approach, CBR tech-

niques are applied to support the modeling of business processes and not their

execution.

7 Summary and Outlook

The integration of ADEPT and CBRFlow oﬀers promising perspectives, as pro-

cess instance changes are enriched with semantic information. This, on the one

hand ensures the traceability of instance changes and on the other hand supports

users in reusing information about previous instance changes. Furthermore, our

approach provides techniques to automatically derive suggestions for process

type changes from previously applied instance changes. If the process engineer

decides to pull up an instance change to the process type level, already running

process instances can be smoothly migrated to the new process schema version.

Finally an evolution of the associated case–base is done.

Currently we implement a prototype integrating the concepts of ADEPT and

CBRFlow and plan to evaluate the resulting prototype in diﬀerent application

scenarios. Future work will focus on the semantic compliance of process type

and process instance changes when they are concurrently applied to the same

process schema. In this context the representation and the evaluation of semantic

information stored for process changes are challenging research topics.

References

1. v.d. Aalst, W., Basten, T.: Inheritance of workflows: An approach to tackling

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

2. Ellis, C., Keddara, K., Rozenberg, G.: Dynamic change within workflow systems.

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

Integrating Process Learning and Process Evolution 267

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

workflow systems – a survey. DKE 50 (2004) 9–34

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

workflow management system. In: Proc. HICSS-34. (2001)

5. Reichert, M., Rinderle, S., Dadam, P.: On the common support of workflow type

and instance changes under correctness constraints. In: Proc. Int’l CoopIS’03.

LNCS 2888, Catania, Italy (2003) 407–425

6. Rinderle, S., Reichert, M., Dadam, P.: On dealing with structural conflicts between

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

7. Rinderle, S.: Schema Evolution in Process Management Systems. PhD thesis,

University of Ulm (2004)

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

adaptive workflow systems. DPD 16 (2004) 91–116

9. Reichert, M., Dadam, P.: ADEPTflex - supporting dynamic changes of workflows

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

10. Weber, B., Wild, W., Breu, R.: CBRFlow: Enabling adaptive workflow manage-

ment through conversational case-based reasoning. In: Proc. ECCBR’04, Madrid

(2004) 434–448

11. Leymann, F., Altenhuber, W.: Managing business processes as an information

ressource. IBM Systems Journal 33 (1994) 326–348

12. Kolodner, J.L.: Case-Based Reasoning. Morgan Kaufmann (1993)

13. A. Aamodt, E.P.: Case-based reasoning: Foundational issues, methodological vari-

ations and system approaches. AI Communications 7(1994) 39–59

14. Aha, D.W., Mu˜noz-Avila, H.: Introduction: Interactive case-based reasoning. Ap-

plied Intelligence 14 (2001) 7–8

15. Weber, B., Rinderle, S., Wild, W., Reichert, M.: CCBR–driven business process

evolution. In: Proc. Int. Conf. on Cased based Reasoning (ICCBR’05), Chicago

(2005)

16. Rinderle, S., Reichert, M., Dadam, P.: Disjoint and overlapping process changes:

Challenges, solutions, applications. In: Proc. CoopIS’04, Cyprus (2004) 101–120

17. v.d. Aalst, W., van Dongen, B., Herbst, J., Maruster, L., Schimm, G., Weijters,

A.: Workflow mining: A survey of issues and approaches. DKE 27 (2003) 237–267

18. v.d. Aalst, W.: Inheritance of business processes: A journey visiting four notorious

problems. In: Proc. Petri Net Technology for Communication Based Systems.

LNCS 2472 (2003) 383–408

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

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

20. Weber, B., Reichert, M., Rinderle, S., Wild, W.: Towards a framework for the agile

mining of business processes. In: Proc. of BPM 05 BPI workshop. (2005)

21. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workflow evolution. DKE 24 (1998)

211–238

22. Wargitsch, C., Wewers, T., Theisinger, F.: An organizational memory-based ap-

proach for an evolutionary workflow management system. In: Proc. HICCS-31.

(1998) 174–183

23. Madhusudan, T., Zhao, J.: A case-based framework for workflow model manage-

ment. In: Proc. Int’l Conf. BPM’03, Eindhoven (2003) 354–369