Semantic Correctness in Adaptive Process Management Systems [original]

Semantic Correctness in Adaptive Process

Management Systems

Linh Thao Ly, Stefanie Rinderle, and Peter Dadam

Dept. DBIS, University of Ulm, Germany

{thao.ly, stefanie.rinderle, peter.dadam}@uni-ulm.de

Abstract. Adaptivity in Process Management Systems (PMS) is key to

their successful applicability in pratice. Approaches have already been de-

veloped to ensure the system correctness after arbitrary process changes

at the syntactical level. However, still errors may be caused at the se-

mantical level. Therefore, the integration of application knowledge will

ﬂag a milestone in the development of process management technology.

In this paper, we introduce a framework for deﬁning semantic constraints

over processes in such a way that they can express real-world applica-

tion knowledge. On the other hand, these constraints are still manageable

concerning the eﬀort for maintenance and semantic process veriﬁcation.

This can be used, for example, to detect semantic conﬂicts when ap-

plying process changes (e.g., drug incompatibilities). In order to enable

the PMS to deal with such semantic conﬂicts we also introduce a notion

of semantic correctness and discuss how to (eﬃciently) verify semantic

correctness in the context of process changes.

Keywords: Semantic Correctness, Semantic Process Veriﬁcation, Se-

mantic Constraints, Adaptive Process Management Systems.

1 Introduction

Due to steadily changing conditions at the global market, companies are forced

to frequently adapt their business processes [1–4]. Therefore, adaptivity is the

key factor for the successful application of process management technology in

practice. Generally, process changes can take place at two levels – process type

and instance level [5,6]. Therefore, it is crucial for an adaptive process manage-

ment system (PMS) to support both kinds of changes. However, it is still not

suﬃcient to support process type and instance changes in an isolated manner.

An adaptive PMS must also allow for the interplay between process type and

instance changes [7]. A framework for the support of process type and instance

changes as well as for their interplay (i.e., the support of change propagation to

already individually modiﬁed instances) has been developed [3,8]. Within this

framework the structural (syntactical) correctness of the system is always pre-

served after arbitrary process changes. For example, it is automatically checked

by the PMS whether process changes will lead to structural errors, like deadlock-

causing cycles or not properly supplied input parameters, or to inconsistent in-

stance states. However, the framework abstracts from semantical aspects. Thus,

S. Dustdar, J.L. Fiadeiro, and A. Sheth (Eds.): BPM 2006, LNCS 4102, pp. 193–208, 2006.

Springer-Verlag Berlin Heidelberg 2006

194 L.T. Ly, S. Rinderle, and P. Dadam

semantic errors may arise, especially in the context of process changes intiti-

ated under time pressure. Consider, for example, process instance I reﬂecting

the treatment process for patient Smith as depicted in Fig. 1. Assume that, due

to suddenly arising headache, the drug Aspirin is administered to patient Smith.

This is achieved by inserting activity Administer Aspirin into instance I in an

ad-hoc manner by, for example, a nurse at her workplace.

Fig. 1. Semantic conﬂicts after process changes due to drug incompatibility and de-

pendencies between activities

However, in this treatment process, the drug Marcumar, which is not com-

patible to Aspirin, is already administered some activities ahead (semantic con-

ﬂict). Even if the process change is syntactically correct, it is not semantically.

Especially when the process instance is often modiﬁed in an ad-hoc manner

(for instance, Administer Marcumar was previously inserted as an ad-hoc mo-

diﬁcation) or when process changes at scheme level and at instance level occur

together, it is likely that those conﬂicts remain undetected by users. If the PMS

was aware of the incompatibility of these activities, it could prevent the user

from causing semantic conﬂicts by, for example, warn the user accordingly. In

Fig. 2, the user (a doctor with the appropriate authorization) still performs the

change operation but has to document the reason for overriding the semantic

constraint. Thus, it is possible to trace back semantic conﬂicts.

As motivated, it is crucial to be able to also integrate application knowledge

(i.e., semantic knowlegde) within the process change framework in order to avoid

semantic conﬂicts. In this context, many challenging questions arise:

–How to formalize and integrate application knowledge within an adaptive

PMS?

–How to deﬁne a notion of semantic correctness of processes after changes?

–How to support the eﬃcient veriﬁcation of the semantic correctness?

–How to maintain the knowledge base?

Semantic Correctness in Adaptive Process Management Systems 195

Fig. 2. Interaction scenario when a semantic conﬂict occurs

In this paper, we extend the framework presented in [3,8] by integrating appli-

cation knowledge into adaptive PMS. First of all, we provide a formalization for

semantic constraints imposed on business processes. In particular, we introduce

two fundamental kinds of semantic constraints (mutual exclusion constraints and

dependency constraints) which serve as a basis for the following considerations.

However, the set of semantic constraints can be easily extended. Based on the

notion of semantic constraints, a general criterion for the semantic correctness

of business processes (independently from the underlying process meta model) is

provided. We show how to verify semantic correctness of processes based on this

criterion, in particular in the context of process changes. For this, we exploit the

semantics of the applied change operations, for example when applying single

change operations (e.g., adhoc changes of process instances), or when applying

concurrent changes (e.g., propagating process schema changes to biased process

instances). Afterwards, we discuss diﬀerent possibilities to realize veriﬁcation of

semantic process correctness in an eﬃcient manner. One way based on exploit-

ing certain process meta-model properties is discussed in more detail. Finally, we

show how the semantic constraints can be organized within a domain repository.

This paper is structured as follows. In Sect. 2, a framework for the deﬁnition

of semantic constraints and the notion of semantic correctness are introduced.

In Sect. 3, we show how the semantic correctness of processes can be veriﬁed.

In Sect. 4, we show the application of the criterion when, for example, a block-

structured process model is used. In Sect. 5, a framework for organizing semantic

constraints is introduced. Related work is discussed in Sect. 6. Finally, Sect. 7

concludes with a summary and an outlook on future research.

2 Semantic Constraints and Semantic Correctness in

Adaptive Process Management Systems

As motivated in Sect. 1, it is desirable to integrate (semantic) application know-

ledge in the PMS in order to avoid semantic conﬂicts. It is in principle possible

to integrate even very complex application knowledge in adaptive PMS. By con-

necting the PMS with a knowledge-based system or an expert system (e.g. [9,

10]), for instance, application knowledge maintained in the external system can

be used by the PMS to avoid semantic conﬂicts. However, two important as-

pects inﬂuence the possibilities of integrating application knowledge in adaptive

PMS. First of all, it is an important question how and by whom the knowledge

base is maintained. The more application knowledge, and in particular the more

196 L.T. Ly, S. Rinderle, and P. Dadam

complex the knowledge, the greater is the eﬀort to keep the knowledge base

up-to-date. Thus, there is a risk that the knowledge, according to which the

semantic checks are performed, is outdated. In fact, this might be even more

dangerous than not performing semantic checks at all. Users might rely on the

semantic checks to ensure the semantic correctness of the process not knowing

that the knowledge base is outdated. As a consequence, it seems reasonable to

only integrate that kind of application knowledge which is really important and

which will really be kept up-to-date. Second, the goal of integrating application

knowledge is to enable the PMS to also perform process checks at the semantic

level. However, the eﬀort to perform these semantic checks must not lead to a

bottleneck, especially when changes on process schemes are propagated to many

running (and possibly ad-hoc modiﬁed) instances. This restricts the complexity

of application knowledge to be integrated in adaptive PMS.

The two aspects mentioned above need to be kept in mind when thinking about

integrating application knowledge in adaptive PMS. In future work, we will inves-

tigate the inﬂuence of these aspects in more detail. In this paper, we introduce two

fundamental kinds ofsemanticconstraints which canbe imposed on processes:mu-

tual exclusion constraints and dependency constraints. These constraints refer to

activities and impose certain conditions on how these activities can be used in the

process. By enabling the PMS to be aware of these fundamental constraints, many

semantic errors, for example the ones depicted in Fig. 1, can be avoided. On the

other hand, the introduced kinds of constraints are still manageable regarding the

eﬀort for maintenance and for semantic veriﬁcation.

Mutual exclusion constraints express that two activities are not compatible

and should not be executed together, for instance administering two incompa-

tible drugs. Please note, that this does not mean that these activities must

not occur in the same process. Due to the process structure, it depends on the

position of the activities whether the constraint is satisﬁed or not. In Fig. 3, a

semantic conﬂict occurs in the ﬁrst process fragment while the second process

fragment is semantically correct. Mutual exclusion constraints are symmetric.

Fig. 3. Semantic conﬂict dependent of process structure

Dependency constraints express that an activity is dependent of another activity,

i.e. these activities need to occur together in the process. In Fig. 1 for instance,

activity Perform Surgery is added to the process. However, in the treatment

process the activity Prepare Blood Bottles needs to be performed before and

Make Appointment for Follow-Up Examination needs to be performed after

Perform Surgery. These semantic dependencies of Perform Surgery cause a

semantic conﬂict, when only Perform Surgery is inserted to the process.

Semantic Correctness in Adaptive Process Management Systems 197

Whether a process change can be applied to a concrete process is, therefore,

not only a question of structural correctness or data ﬂows but also a question

of whether the semantic constraints over the process are violated by the process

change. For our following considerations we assume the uniqueness of activities

in a process (i.e. each activity may occur only once in a business process).

Deﬁnition 1 (Semantic constraint). Let Abe a set of activities1.Ase-

mantic constraint cis deﬁned as a tuple (type,source,target,position,userDeﬁned)

whereas

–type ∈{Exclusion, Dependency}

–source, target ∈A,source =target

–position ∈{pre, post, notSpecified}

–userDefined is a user-deﬁned parameter

The parameter type denotes whether the semantic constraint is a mutual ex-

clusion constraint or a dependency constraint. The second parameter source

denotes the source activity the constraint refers to while target denotes the tar-

get activity related to the source activity. Parameter position speciﬁes the order

the source and target activity are to be related to each other within the process

(e.g., the surgery depends on the preparation of blood bottles and the bottles

have to be prepared before (pre) the surgery). The last parameter userDefined

can be used for several purposes, for instance for additionally describing the

constraint. Furthermore, it might also be used to indicate the importance of the

constraint. For instance, to indicate whether a constraint is merely a recom-

mendation or whether it is more severe. This information can be used by the

PMS client to create an appropriate feedback for the user. As an example, the

constraint mentioned above would look like this:

(Dependency,Perform surgery,Prepare blood bottles,pre,

Blood bottles need to be prepared for the patient and stored in

the surgery room before the surgery can take place)

In Def. 2, the satisfaction of semantic constraints is deﬁned taking the notion

of execution trace as a basis. According to Def. 2, the constraint above, for

example, is satisﬁed over a process if the source activity (Perform surgery)is

not included in this process. In case it is, the constraint is satisﬁed, if Prepare

blood bottles is always performed before Perform surgery in each possible

execution trace of the process, in which Perform surgery appears.

Deﬁnition 2 (Satisfaction of semantic constraints). Let Abe a set of ac-

tivities which can be used to specify a process p of type T. Let Qbe the set of

all possible execution traces of p. A trace q∈Qis deﬁned by q:=<e

1,...,e

with events ei=End(t)

2,t∈A. Then, we deﬁne the following functions:

1Within the ADEPT framework, for example, Arefers to the activity repository

containing all relevant activities in the context of a certain process type T.

2We abstract from start events in the traces.

198 L.T. Ly, S. Rinderle, and P. Dadam

–activities: Q →Awith activities(q):= {t1,...,t

n}with

q=<e

1,...,e

k>∧∀tl∃eiwith ei=End(tl), l = 1, ..., n; i = 1, ..., k (i.e.,

activities denotes a function that returns the set of all activities included in

an execution trace q).

–processActs(p):={t1,...,t

n}with

∀tl∃q∈Qwith tl∈activities(q), l = 1, ..., n (i.e., processAtcs returns

all activities included in the process p).

–traceSucc: A×Q→Awith traceSucc(t, σ):= {t1,...,t

n}with

σ=<e

1,...,e

k>,t1,...,t

n∈activities(σ)∧∀tl:∃ei,e

j∈σwith

ei=End(tl), ej= End(t), l = 1, ..., n; i, j = 1, ..., k ∧i<j(i.e.,

traceSucc denotes a function which returns all direct or indirect successors

of a given activity t within an execution trace σ).

–tracePred: A×Q→Awith tracePred(t, σ):= {t1,...,t

n}with

σ=<e

1,...,e

k>,t1,...,t

n∈activities(σ)∧∀tl:∃ei,e

j∈σwith

ei=End(tl), ej= End(t), l = 1, ..., n; i, j = 1, ..., k ∧i>j(i.e.,

tracePred denotes a function which returns all direct or indirect predecessors

of a given activity t within an execution trace σ).

Let a1,a2∈Abe two activities, a1=a2. Then, a semantic constraint c =

(type, source, target, position, userDeﬁned) with source=a1and target=a2is

satisfied over process p (formally: satisﬁed(c, p) = True) iﬀ one of the fol-

lowing conditions holds:

–type ∈{Exclusion,Dependendency}and a1/∈processActs(p)

–type = Exclusion, position = pre and ∀execution traces φ∈Q:

a1∈activities(φ)⇒a2/∈tracePred(a1,φ)

–type = Exclusion, position = post and ∀execution traces φ∈Q:

a1∈activities(φ)⇒a2/∈traceSucc(a1,φ)

–type = Exclusion, position = notSpeciﬁed and ∀execution traces φ∈Q:

a1∈activities(φ)⇒a2/∈traceSucc(a1,φ)and a2/∈tracePred(a1,φ)

–type = Dependendency, position = pre and ∀execution traces φ∈Q:

a1∈activities(φ)⇒a2∈tracePred(a1,φ)

–type = Dependendency, position = post and ∀execution traces φ∈Q:

a1∈activities(φ)⇒a2∈traceSucc(a1,φ)

–type = Dependendency, position = notSpeciﬁed and ∀execution traces φ∈Q:

a1∈activities(φ)⇒(a2∈tracePred(a1,φ)or a2∈traceSucc(a1,φ))

Otherwise, c is violated over p (formally: satisﬁed(c, p) = False).

For a process type (e.g., the treatment process), many constraints might be

relevant. Even if the process was modelled semantically correct at buildtime,

due to possible (unforeseen) process changes, activities might be deleted from

or added to the process at runtime. Furthermore, mutual exclusion constraints

cannot be modelled in the control-ﬂow of a process. In these cases, the constraints

imposed on the process will help to ensure a semantically correct execution. Now,

based on the notion of satisfaction of constraints, a semantic correctness criterion

for business processes can be deﬁned.

Semantic Correctness in Adaptive Process Management Systems 199

Deﬁnition 3 (Semantic correctness of business processes). Let T be a

process type and let p be a process of type T. Let further Cpbe the set of all

semantic constraints deﬁned over p. Process p is semantically correct ⇐⇒

∀c∈Cp:satisfied(c, p)=True

Using Def. 1–3, it is possible to state for each business process whether the

business process is semantically correct or not.

3 On Preserving Semantic Correctness of Processes

As speciﬁed in Def. 3, a process (no matter whether it is a process instance or

a process schema) is semantically correct only if all of its semantic constraints

are satisﬁed. Consequently, the semantic constraints of the process need to be

analyzed when checking the process’ semantic correctness. Not all the constraints

on a process, however, are relevant. Depending on the situation in which the

semantic check is initiated, it is possible to restrict the set of relevant constraints

to be veriﬁed and thus to reduce the eﬀort for semantic process veriﬁcation. We

now have a closer look on that.

In Sect. 3.1, we show how the semantic correctness of process schemes can be

veriﬁed. In Sect. 3.2, we show how to ensure the semantic correctness of a process

when ad-hoc process adaptations are carried out. In Sect. 3.3, we consider how

to maintain the semantic correctness when schema evolution is performed. For

the remainder of this section, let pbe the process to be veriﬁed and let Cvp be

the set of the constraints to be veriﬁed in the respective situation.

3.1 Semantic Correctness of Process Schemes

Basically, there are two ways of ensuring the semantic correctness of process

schemes depending on the way the process models are constructed. If a process

model is built by applying process changes to an “empty” schema the PMS

might perform a semantic check each time a change operation is applied and

check whether the semantic correctness of the process is still preserved after

the change or not (cf. 3.2). The second possibility is to take an already existing

process model3and to verify the correctness of the complete process schema

at once. In this case, it is necessary to verify, whether the constraints imposed

on the process are satisﬁed or not. However, constraints, for which the source

activity is not included in the process, are always satisﬁed over this process by

deﬁnition. Thus, these constraints need not be considered.

More formally: Cvp Schema={c∈Cp;c(source)4∈processActs(p)}

3.2 Semantic Correctness After Applying Ad-Hoc Process Changes

In our framework, an ad-hoc process change is considered semantically applicable

to a process if its application still preserves the semantic correctness of the

3This is, for instance, relevant when a process model is imported to the PMS or the

process schema is obtained by applying process mining techniques.

4c(source) denotes the source parameter of the constraint c.

200 L.T. Ly, S. Rinderle, and P. Dadam

process. The naive way of verifying the semantic correctness of a process after a

process change is to verify the complete process model, as described in Sect. 3.1.

However, this eﬀort can be reduced by exploiting the semantics of the applied

change operations (e.g., which activity has been inserted at which position).

Thus, depending on which change operation is requested, only a smaller subset

of constraints on the process needs to be veriﬁed. In the following, we discuss

the interplay between change operations of type Insert,Delete and Move and

the set of constraints to be veriﬁed.

When inserting an activity tinto process p, all semantic constraints over p

which have tas source parameter need to be veriﬁed since they might be violated.

However, since dependency constraints which do not have tas source parameter

cannot be violated by the addition of t, only mutual exclusion constraints with t

as target parameter need to be considered. We can even further restrict the set of

interesting exclusion constraints to those constraints whose source parameter is

among the activities of pand whose target parameter corresponds to the inserted

activity t. That is because all exclusion constraints, whose source parameter are

not included in the process, are satisﬁed by deﬁnition.

More formally: Cvp Insertion={c∈Cp;(c(source)=t)or(c(type)5=Exclusion

and c(source)∈processActs(p)andc(target)6=t)}.

When deleting an activity tfrom process p, all semantic constraints over p

with tas source parameter are satisiﬁed by deﬁnition. Similar to the insertion of

activities, all constraints for which toccurs as target parameter are potentially

interesting for correctness checks. However, mutual exclusion constraints with t

as target parameter cannot be violated by the deletion of t. Only dependency

constraints with tas target parameter and for which the source parameter is

included in pmight be violated by the deletion operation and therefore need to

be veriﬁed.

More formally: Cvp Deletion={c∈Cp;c(type)=Dependency and c(source)∈

processActs(p)andc(target)=t}.

The moving of an activity tfrom its original position within process pto

anewpositionpos can be understood as being equivalent of deleting tand

inserting tat pos afterwards7. Consequently, all constraints that which might be

violated after applying deletion and insertion operations need to be veriﬁed.

More formally: Cvp Move =Cvp Deletion ∪Cvp Insertion.

3.3 Semantic Correctness for Process Schema Evolution

In addition to ad-hoc changes at the instance level, adaptive PMS must support

the modiﬁcation of process schemes at the type level followed by the migra-

tion of running instances to the modiﬁed process schema as well. The semantic

correctness of the process schema after applying the changes can be veriﬁed

5c(type) denotes the type of the constraint c (Dependency or Exclusion).

6c(target) denotes the target parameter of the constraint c.

7In conjunction with data ﬂow aspects, moving is not always equivalent to deleting

and inserting. However, this assumption can be used to derive statements about

possible semantic conﬂicts here.

Semantic Correctness in Adaptive Process Management Systems 201

by using the considerations for ad-hoc changes made in Sect. 3.2. In case the

schema change is semantically correct, it will also be semantically correct when

being applied to unbiased instances (i.e., instances which still run according to

the process schema they have been started on). However, the direct applica-

tion of the schema change to biased instances (i.e., instances which have already

been individually modiﬁed) might lead to semantic conﬂicts between type and

instance changes. Assume that at instance level drug Marcumar has been ad-

ministered for process instance I as an ad-hoc change. Afterwards, at process

type level, activity Administer Aspirin is inserted into the associated process

schema and is to be propagated to I.MigratingIto the modiﬁed process schema

then causes a semantic conﬂict, even though the migration can be performed in

a syntactically correct manner. Therefore, we have to check whether the process

changes at type level are semantically applicable to the biased instances. We

assume that the biased instances are semantically correct after the individually

applied process instance changes. The propagation of changes at type level to

a biased instance is semantically correct if the type changes are semantically

applicable to the biased instance as ad-hoc instance change or vice versa (cf.

Sect. 3.2).

Due to only considering biased instances, the number of instances to be

checked is highly decreased. However, it is possible to further decrease the num-

ber of instances and relevant constraints to be veriﬁed. For example, if the change

operations applied to a process instance constitute a superset of the change op-

erations applied to the process schema (or vice versa), no semantic conﬂicts can

occur. Due to space restrictions, we omit further details. For details on superset

relations between change operations we refer to [8,11].

For an eﬃcient implementation of the considerations in Sect. 3, employing

indexing techniques in order to easily access the relevant constraints in the re-

spective situations seems very useful. After having considered, which constraints

need to be veriﬁed in diﬀerent situations, in the next section we consider how to

verify those constraints.

4 On Optimizing Semantic Process Veriﬁcation

The semantic correctness criterion for business processes deﬁned in Sect. 2 is

generic and can be applied to any process meta-model (e.g., Petri Nets [1] or

BPEL4WS Nets [12]). For verifying the criterion, reachability analysis can be

applied (i.e., by calculating all possible execution traces and checking them for

certain order relations between activities according to the semantic constraints)

which might be very costly. Therefore, we want to investigate diﬀerent meth-

ods to ensure the semantic correctness criterion which are less expensive. In

this paper, we present an approach which makes use of certain properties of

the underlying process meta-model, namely block-structuring (e.g., WSM Nets

[3]). However, we intend to also develop model-independent methods in future

work.

202 L.T. Ly, S. Rinderle, and P. Dadam

4.1 Background Information

This section summarizes background information on WSM Nets [13,14] as pro-

cess description formalism in order to present an optimized veriﬁcation method

for semantic correctness.

Aprocess schema is represented by a WSM Net which deﬁnes the process

activities as well as the control and data ﬂow between them. When using WSM

Nets the control ﬂow schema can be represented by attributed, serial-parallel

graphs. In order to synchronize activities from parallel paths additional links

can be used [15]. In this paper we abstract from cyclic structures within the

process meta model in order to provide a fundament for an optimized semantic

correctness veriﬁcation. Further on, a WSM Net comprises a set of data elements

and a set of data edges. A data edge links an activity with a data element and

either represent a read access of this activity or a write access. The total set of

data edges constitutes the data ﬂow schema.

Deﬁnition 4 (WSM Net). A tuple S = (N, D, NT, CtrlEdges, SyncEdges,

DataEdges, BC) is called a WSM Net, if the following holds:

–N is a set of process 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 process schema a respective node type.

–CtrlEdges ⊂N×N is a precedence relation deﬁnining the valid order of

activities (notation: nsrc →ndst ≡(nsrc,n

dst)∈CtrlEdges)

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

branches

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

activities and data elements

–BC: N → Conds(D) where Conds(D) denotes the set of all valid transition

conditions on data elements from D. BC(n) is undeﬁned for nodes n with

NT(n) =XOrSplit.

Which constraints have to hold such that a process schema S is well-structured

is summarized in [15,8] (e.g., absence of deadlock–causing cycles and correctly

supplied input parameters). In the context of this paper, the block-structuring

property is important, i.e., for all activities of node type AndSplit (XOrSplit)

there is a unique activity of node type AndJoin (XOrJoin) and blocks (sequences

as well as parallel and alternatives branchings can be nested but must overlap).

In this paper we abstain from deﬁning process instances (see [3]) since this is

not relevant for the following considerations.

4.2 On Exploiting Process Meta Model Properties

From the general constraint satisfaction criteria presented in Sect. 2 we derived

meta-model speciﬁc conditions on WSM Nets. Using these meta-model speciﬁc

criteria the satisfaction of semantic constraints and thus the semantic correctness

of a process can be veriﬁed in an optimized way. For all semantic constraints in

Semantic Correctness in Adaptive Process Management Systems 203

Def. 1, such meta-model speciﬁc criteria can be derived. Due to space restrictions,

however, we abstain from presenting all the criteria. Instead, as an example, we

show how a particular meta-model speciﬁc criterion can be derived. Consider

the following semantic constraint over the treatment process from Sect. 1:

c1:(Dependency,Perform surgery,Prepare blood bottles,pre,...)

If Perform surgery does not occur in the treatment process, then c1is satis-

ﬁed by deﬁnition and consequently not of further interest for semantic process

veriﬁcation (cf. Sect. 3). In case Perform surgery occurs in the process, it is

necessary that Prepare Blood Bottles is a direct or indirect predecessor of

Perform surgery in the treatment process for c1to be satisﬁed. Otherwise,

it is not possible that Prepare Blood Bottles is performed before Perform

Surgery,eachtimePerform Surgery is performed. However, this is not suf-

ﬁcient, since this execution order is not guaranteed. When verifying semantic

constraints, it is necessary to also take the process structure into account. If

Prepare Blood Bottles is contained in the inner part of an XOR-block while

Perform Surgery is not, Prepare Blood Bottles is not sure to be performed

each time Perform Surgery is performed. Therefore, c1is not satisﬁed over the

process depicted in Fig. 4.

Prepare blood

bottles

Perform surgery

Fig. 4. Prepare blood bottles is not sure to be performed each time Perform

surgery is performed

From this example we conclude the following conditions for the satisfaction

of that kind of dependency constraints over block-structured meta models:

A semantic dependency constraint cdep=(Dependency, source, target, pre, ...)

over a process prepresented by a WSM Net S=(N, D, NT, ...)withsource ∈

N(i.e. source ∈processActs(p)) is satisﬁed (i.e., satisfied(cdep,p)=True)if

and only if the two following conditions hold:

–target ∈pred∗(S, source)(necessary condition)

–∀s∈Nwith NT(S)=XOrSplit:target ∈inBlock(S, s)⇒source ∈

inBlock(S, s)(suﬃcient condition), where:

•pred∗(S, n)(succ∗(S, n)) denotes the set of all direct and indirect prede-

cessors (successors) of n in S8

•inBlock(S, s):=succ∗(S, s)∩pred∗(S, join(S))

•join(S, s) yields the unique associated join for split node s

8Note that pred∗(succ∗) refers to structural predecessors (successors) whereas

tracePred (traceSucc) refers to predecessors (successors) within execution traces.

204 L.T. Ly, S. Rinderle, and P. Dadam

In the following we show that these conditions ensure the semantic correctness.

Proof sketch. Let cdep=(Dependency, source, target, pre, userDefined)bea

semantic dependency constraint over a process prepresented by a WSM Net

S=(N, D, NT, ...) with the set of all execution traces Φfor which source ∈N

holds. Then, the following proposition  is to be proven (cf. Def. 2):

satisfied(cdep,p)=True ⇐⇒

(target ∈pred∗(S, source)) ∧

(∀s∈Nwith NT(S)=XOrSplit:target ∈inBlock(S, s)⇒

source ∈inBlock(S, s))

 ⇐⇒

∀φ∈Φ:source ∈activities(φ)⇒target ∈tracePred(source, φ)(i)⇐⇒

(target ∈pred∗(S, source)) ∧

(∀s∈Nwith NT(S)=XOrSplit:target ∈inBlock(S, s)⇒

source ∈inBlock(S, s)) (ii)

“=⇒”: Proof by contradiction (i.e. ((i) =⇒(ii)) ⇐⇒ (¬(ii) =⇒¬(i)))

Let us assume that (ii) does not hold (i.e. ¬(ii) holds). Let us ﬁrst assume that

the necessary condition does not hold, i.e. target /∈pred∗(S, source). This means

that there is no path from source to target in p. Then, there are four possibilities:

1. target /∈N=⇒source /∈traceP red(target, Φ)

2. target ∈succ∗(S, source)=⇒source /∈tracePred(target, Φ)

3. target and source are in an parallel block

4. target ∈Nand target in an XOR-path while source is in the other XOR-

path

Possibilities 1 and 2 are clear. If the third possibility is true, then cdep is also

violated since, due to the interleavings of parallelly executed activities, there

might be at least one trace, where target and source do not occur in the required

ordering relation. If the fourth possibility is true, then either source or target are

executed during an process execution. Thus cdep is violated as well. As shown,

all possibilites that are left when the necessary condition is not true lead to the

violation of cdep (¬(i)).

Now let us assume that the necessary condition holds, but not the suﬃcient

condition. This means: ∃s, NT (S)=XOrSplit with target ∈inBlock(S, s)∧

source /∈inBlock(S, s). Since target ∈pred∗(source)) holds (necessary condi-

tion), we can construct an execution trace of pby not chosing the XOR-path

which target is on while still executing source. This leads to ¬(i). 

The reverse direction ”⇐=” can be proven analogously.

The satisfaction criterion for dependency constraints for block-structured pro-

cess meta-models presented above can be veriﬁed very eﬃciently. Special con-

structs of the meta-models, for instance references to the split and join nodes,

can be exploited by the PMS in order to ﬁnd out whether the respective con-

straint is satisﬁed or not. However, using the meta-model speciﬁc criterion it

is also possible to leave the veriﬁcation to an external reasoning system (e.g.

RACER [9]). In this case, information about the process structure need to be

Semantic Correctness in Adaptive Process Management Systems 205

mapped to rules in the reasoning system in order enable it to apply inference

techniques. We intend to further investigate these implementation alternatives

in future work.

5 A Framework for Semantic Constraints

In our approach, a set of semantic constraints is assigned to a process. However,

several processes may share constraints. In this section, we present a framework

for organising semantic constraints such that they can be reused easily.

Additional

process specific

constraints

Domain

constraints

Selection of relevant domain

constraints

Constraints on Treatment Process

Treatment Process

Activity

Repository

Process

Repository

references

Domain Constraints

Repository

Domain: Minimally

invasive cardiac surgery

Constraints:...

Domain: Minimally

invasive cardiac surgery

Constraints: ...

Domain: Minimally

invasive cardiac surgery

Constraints:...

Process Engineer

Fig. 5. Organisation of constraints in a domain constraints repository

The three main components of the framework are the domain repository,the

process repository,andtheactivity repository (cf. Fig. 5). Semantic constraints

are organised in the domain repository. In particular, constraints are assigned

to domains, for instance the domain Minimally invasive cardiac surgery.Thus,

a domain contains a set of constraints that are typical of this domain. The

constraints presented in this paper refer to activities which are organized in an

activity repository. For future work, we also plan to introduce constraints that

refer to other abstraction levels, for instance abstraction levels in the activity

repository. Process types (process schemes) are organized in a process repository.

Each process type is assigned a domain of the domain repository. Thus, it is

possible to assign a default set of domain constraints to a process. However,

processes that are assigned to the same domain might still have diﬀerent semantic

constraints that are not captured in the domain. Therefore, for each process type,

the process designer can specify additional semantic constraints for the process

or leave out some unnecessary domain constraints.

6 Related Work

The issue of integrating semantics in process management systems has often been

adressed in literature. In particular, there are interesting approaches from the

206 L.T. Ly, S. Rinderle, and P. Dadam

clinical domain concerning the formalization of clinical guidelines in a computer-

readable way, e.g. [16,17] and GLIF3 [18] or GUIDE [19]. However, so far, this

information cannot be directly used for automatical analyses by the PMS.

Current approaches on adaptive PMS mainly focus on structural aspects

(e.g., [3,4,8,20]) or have a diﬀerent notion of semantic correctness (e.g., [21,

1]). Many related approaches focus on the aspect of integrating heterogenous

resources. In particular, activities and their parameters are often described us-

ing ontologies, e.g. [22–24] and also many approaches concerning semantic web

service composition, for instance [25,26]. When a process is composed, the PMS

can check, whether the activities and their parameters semantically ﬁt together.

However, these approaches do not consider semantic constraints over processes,

for instance mutual exclusion constraints, the way we do.

As discussed in Sect. 2, approaches from the ﬁeld of Artiﬁcial Intelligence,

in particular knowledge-based systems, e.g. [27,10,9], can be used to integrate

application knowledge in PMS. This is also closely related to approaches con-

cerning the integration of business rules in PMS. Application knowledge can be

sourced out into a Business Rule Engine, e.g. commercially available systems

like ILOG [28]. Thus, decision processes, for instance, which outgoing paths of

an activity to follow, can be supported taking also background knowledge into

account. This approach, however, is not directly suitable for situations like the

one outlined in our example scenario since this situation concerns not only the

occurrence of an activity in the process but also the relations between activi-

ties (cf. Fig. 3). In [29,30], an approach to ensure the integrity of processes is

introduced. Rules, realized as database triggers, are applied, when certain data

conditions occur. Using the change framework presented in [3,8] the process is

adapted in an ad-hoc manner according to the triggered rule. Our approach,

however, goes further since for the semantic veriﬁcation, structural information

about the process is needed.

In [31] van der Aalst et al. introduced an approach for verifying given proper-

ties of past processes by applying process mining techniques. This approach can

help detecting constraint violations. However, the approach introduced in [31]

is orthogonal to our work because it aims on analysing past processes on cer-

tain aspects while our intention is to ensure the semantic correctness of running

processes. Thus, these two approaches can complement each other.

We consider our approach to be orthogonal to the approaches mentioned in

this section.

7 Conclusion and Outlook

In this paper, we introduced a framework for the integration of application

knowledge within an adaptive PMS by using semantic constraints. Based on

these constraints, a generic criterion for semantic correctness of processes has

been provided. We have shown how this criterion can be generally ensured.

Furthermore, we have addressed the issue of verifying semantic correctness after

process changes. Exemplarily for block-structured process meta-models, we have

shown how semantic process veriﬁcation can be realized in an eﬃcient manner.

Semantic Correctness in Adaptive Process Management Systems 207

Finally, an architecture for the integration of semantic constraints within an

adaptive PMS has been presented.

Using our approach, all semantic conﬂicts caused by violation of dependency

and mutual exclusion constraints can be avoided. However, the expressiveness

of the presented constraints is limited. Therefore, in future work we will extend

our framework, e.g. by introducing context restrictions on constraints concerning

their validity (e.g., time or location) or by introducing constraints on other

levels of granularity than the activity level (e.g. data). Furthermore, we want

to develop further methods to eﬃciently verify semantic correctness within an

adaptive PMS. For example, we want to analyze how the information referred

to by semantic constraints can be organized (e.g., within an ontology) in order

to decrease evaluation eﬀort. All considerations are to be implemented within

the adaptive PMS ADEPT (e.g. [15]).

Acknowledgement. We thank Michael Nahler for the valuable results of his

Master thesis ([32]) which have partially been incorporated in this paper.

References

1. 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

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

Engineering 24 (1998) 211–238

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

adaptive workﬂow systems. DPD 16 (2004) 91–116

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

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

5. 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. DPD 13 (2003) 43–72

6. Reichert, M., Rinderle, S., Dadam, P.: On the modeling of correct service ﬂows

with BPEL4WS. In: EMISA’04. (2004) 117–128

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

workﬂow systems – a survey. DKE 50 (2004) 9–34

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

University of Ulm (2004)

9. Haarslev, V., M¨oller, R.: Description of the racer system and its applications. In:

Proceedings International Workshop on Description Logics (DL-2001), Stanford,

USA, 1.-3. August. (2001) 131–141

10. Hayes-Roth, F.: Rule-based systems. Commun. ACM 28 (1985) 921–932

11. Rinderle, S., Weber, B., Reichert, M., Wild, W.: Integrating process learning and

process evolution - a semantics based approach. In: BPM’05. (2005)

12. Andrews, T., Curbera, F., Dholakia, H., et al., Y.G.: BPELWS - Business Process

Execution Language for Web Services. (2003) BEA Systems, International Business

Machines Corporation, Microsoft Corporation, SAP AG, Siebel Systems.

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

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

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

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

208 L.T. Ly, S. Rinderle, and P. Dadam

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

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

16. Maviglia, S., Zielstorﬀ, R., Paterno, M., Teich, J., Bates, D., Kuperman, G.: Au-

tomating complex guidelines for chronic disease: Lessons learned. Journal of Amer-

ican Medical Inf. Ass. 10 (2003) 154–165

17. Blaser, R., Schnabel, M., Heger, O., Opitz, E., Lenz, R., Kuhn, K.: Improving

pathway compliance and clinician performance by using information technology.

In: MIE’05. (2005)

18. Boxwala, A., Peleg, M., Tu, S.: GLIF3: a representation format for sharable

computer-interpretable clinical practice guidelines. Biomed Inform. 37 (2004)

147–61

19. Quaglini, S., Stefanelli, M., Cavallini, A., G, G.M., Fassino, C., C, C.M.: Guideline-

based careﬂow systems. Artif Intell Med 20 (2000) 5–22

20. Weske, M.: Flexible modeling and execution of workﬂow activities. In: Proc. Hawaii

Int’l Conf. on System Sciences, Hawaii (1998) 713–722

21. van der Aalst W. M. P., Basten, T., Verbeek, H.M.W., Verkoulen, P.A.C., Voorho-

eve, M.: Adaptive workﬂow: On the interplay between ﬂexibility and support.

Interprise Information Systems (2000) 63–70

22. Pathak, J., Caragea, D., Honovar, V.: Ontolgy-extended component-based work-

ﬂows: A framework for constructing complex workﬂows from semantically hetero-

geneous software components. In: SWDB’04. (2005) 41–56

23. Bowers, S., Lin, K., Lud¨ascher, B.: On integrating scientiﬁc resources through

semantic registration. In: SSDBM’04. (2004)

24. Kim, J., Gil, Y., Spraragen, M.: A knowledge-based approach to interactive work-

ﬂow composition. In: ICAPS 04. (2004)

25. Cardoso, J., Sheth, A.: Semantic e-workﬂow composition. JIIS. 21 (2003) 191–225

26. Zhang, R., Arpinar, I.B., Aleman-Meza, B.: Automatic composition of semantic

web services. In: Intl. Conf. on Web Services, Las Vegas NV, June 2003. (2003)

27. Hayes-Roth, F., Jacobstein, N.: The state of knowledge-based systems. Commun.

ACM 37 (1994) 26–39

28. Ader, M.: Ilog components for business process management solutions (2002)

29. Greiner, U., Ramsch, J., Heller, B., L¨oﬄer, M., M¨uller, R., Rahm, E.: Adap-

tive guideline-based treatment workﬂows with adaptﬂow. In: CGP 2004. (2004)

113–117

30. M¨uller, R., Greiner, U., Rahm, E.: Agentwork: A workﬂow system supporting

rule-based workﬂow adaption. DKE 51 (2004) 223–256

31. v. d. Aalst, W., de Beer, H., van Dongen, B.: Process mining and veriﬁcation of

properties: An approach based on temporal logic. In: CoopIS’05. (2005) 130–147

32. Nahler, M.: Semantical conﬂicts in adaptive process managament systems (2005)

(in german).