Author's personal copy
Integration and verification of semantic constraints
in adaptive process management systems
Linh Thao Ly
*
, Stefanie Rinderle, Peter Dadam
Ulm University, Faculty of Engineering and Computer Science, Institute of Databases and Information Systems,
James-Franck-Ring, 89069 Ulm, Germany
Accepted 12 June 2007
Available online 23 June 2007
Abstract
Adaptivity in process management systems is key to their successful applicability in practice. Approaches have been
already developed to ensure system correctness after arbitrary process changes at the syntactical level (e.g., avoiding incon-
sistencies such as deadlocks or missing input parameters after a process change). However, errors may be still caused at the
semantical level (e.g., violation of business rules). Therefore, the integration and verification of domain knowledge will flag
a milestone in the development of adaptive process management technology. In this paper, we introduce a framework for
defining semantic constraints over processes in such a way that they can express real-world domain knowledge on the one
hand and are still manageable concerning the effort for maintenance and semantic process verification on the other hand.
This can be used to detect semantic conflicts (e.g., drug incompatibilities) when modeling process templates, applying ad
hoc changes at process instance level, and propagating process template modifications to already running process
instances, even if they have been already individually modified themselves; i.e., we present techniques to ensure semantic
correctness for single and concurrent changes which are, in addition, minimal regarding the set of semantic constraints to
be checked. Together with further optimizations of the semantic checks based on certain process meta model properties
this allows for efficiently verifying processes. Altogether, the framework presented in this paper provides the basis for pro-
cess management systems which are adaptive and semantic-aware at the same time.
2007 Elsevier B.V. All rights reserved.
Keywords: Semantic correctness; Semantic process verification; Semantic 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 man-
agement technology in practice. Generally, process changes can take place at two levels – instance level (e.g.,
adapting a particular process instance to the needs of a customer) and process template level (e.g., adapting
0169-023X/$ - see front matter 2007 Elsevier B.V. All rights reserved.
doi:10.1016/j.datak.2007.06.007
*
Corresponding author. Tel.: +49 731 50 24194; fax: +49 731 50 24134.
E-mail addresses: [email protected] (L.T. Ly), stefanie.rinderle@uni-ulm.de (S. Rinderle), peter.dadam@uni-ulm.de (P. Dadam).
Available online at www.sciencedirect.com
Data & Knowledge Engineering 64 (2008) 3–23
www.elsevier.com/locate/datak
Author's personal copy
the process template due to legal changes) [5,6]. Thus, it is crucial for an adaptive process management system
(PMS) to support both kinds of changes. However, it is still not sufficient to support process template and
instance changes in an isolated manner. An adaptive PMS must also allow for the interplay between process
template and instance changes [7]. A framework for the support of process template and instance changes as
well as for their interplay (i.e., the support of change propagation to already individually modified instances)
has been developed [3,8]. Within this framework the syntactical correctness of the process is always preserved
after arbitrary process changes. For example, it is automatically checked by the PMS whether process changes
will lead to structural errors, such as deadlock-causing cycles, not properly supplied input parameters, or to
inconsistent instance states.
Ensuring syntactical correctness, however, is often not sufficient. In particular, for processes undergoing
frequent changes performed by various staff members, mechanisms to ensure the semantic correctness of
the processes become necessary. For this purpose, mechanisms to integrate semantic domain knowledge into
adaptive PMS are required. In this paper, we introduce a framework for supporting semantic knowledge inte-
gration and semantic process verification in the context of changes at process instance and at process template
level as well as for their interplay.
1.1. Problem description and challenges
In many application domains, it is not possible to foresee and thus model all possible exceptions and nec-
essary deviations at buildtime. Thus, frequent ad hoc modifications on process instances, for instance adding a
special treatment for a particular patient, are the normal case in these domains. It is, therefore, an important
requirement to support ad hoc changes in an user-friendly way such that even non-expert users (e.g., a nurse at
a hospital workstation) are able to perform ad hoc process instance deviations if necessary. However, perform-
ing ad hoc modifications of process instances can also be a source of semantic errors. Consider, for example,
process instance I reflecting the treatment process for patient Smith as depicted in Fig. 1. Assume that, due to
a suddenly arising headache, drug Aspirin is administered to patient Smith. This is achieved by inserting task
Administer Aspirin into instance I in an ad hoc manner by, for example, a nurse at her workstation.
However, in this treatment process, the drug Marcumar, which is not compatible to Aspirin, is already admin-
istered some tasks ahead (semantic conflict). Even if the process change is syntactically correct, it is not
semantically.
In particular, if a process instance is often modified in an ad hoc manner (e.g., Administer Marcumar
was previously inserted as an ad hoc modification) or if changes at process template level and at process
instance level are merged (i.e., when propagating process template changes to individually modified process
instances), it is likely that such semantic conflicts occur and that they remain undetected even by process
experts. This leads to a contradictory situation: On the one hand, a lot of time and effort is spent on modeling
structurally and semantically correct process templates at buildtime. On the other hand, however, due to per-
forming semantically conflicting process changes, semantic errors creep in at runtime possibly affecting the
success of the process.
Administer
Marcumar
...
Administer
Aspirin
Insert
„Administer Aspirin“
Process instance I (Treatment for Patient Smith)
... ...
Perform
Surgery
Insert
„Perform Surgery“
1 2
„Administer Aspirin“
imcompatible with
„Administer Marcumar“
Make Appointment
for Follow-Up
Examination
Prepare
Blood Bottles
To be
performed
after „Perform
Surgery“
To be
performed
before
„Perform
Surgery“
Dependencies of „Perform Surgery“
Node states: Edge states:
True-signaled
False-signaled
Activated
Completed
...
Running
Skipped
Fig. 1. Semantic conflicts after process changes due to drug incompatibility and dependencies between tasks.
4L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
If the PMS was aware of the incompatibility of the two tasks in the above mentioned example (cf. Fig. 1), it
could prevent arising semantic conflicts by, for example, warn the user accordingly. In Fig. 2, the user (a doc-
tor with the necessary authorization) still administers Aspirin despite the semantic conflict, but he has to doc-
ument the reason for overriding the semantic constraint. Generally, documentation and traceability of
violations of guidelines and best practices are highly relevant for many application domains (e.g., the medical
or the automotive domain) since it becomes possible to trace back semantic conflicts which might cause, e.g.,
failures in the production.
In order to ensure the semantic correctness of processes – even across various changes – adequate mecha-
nisms are required. Domain knowledge – e.g., knowledge about incompatible tasks – needs to be integrated
within the process change framework in order to enable adaptive PMS to be semantic-aware. In this context,
many challenging questions arise:
•How to formalize and integrate domain knowledge (e.g., business rules [9], medical guidelines [10,11], etc.)
within an adaptive PMS?
•How to define a notion of semantic correctness for process templates and process instances and support its
efficient verification?
•How to determine whether changes on process templates, process instances, and the propagation of tem-
plate changes to running process instances are semantically correct?
•How to integrate semantic verification into the interaction scenarios of an adaptive PMS?
Integrating domain knowledge within adaptive PMS and ensuring semantic correctness of running pro-
cesses at any time will mark a milestone in the practical application of such systems.
1.2. Contribution
In this paper, we present a framework for integrating domain knowledge into adaptive PMS and for per-
forming semantic process verification in an efficient way. 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. Both kinds of constraints have been identified as highly relevant for different application
domains (i.e., the medical or the insurance domain). However, this basic set of semantic constraints can be
easily extended as we will show in future work. Based on the notion of semantic constraints, a general criterion
for the semantic correctness of business processes (independent from the underlying process meta model) is
provided. Most of these results have been presented in [12]. In this paper, we refine the semantic correctness
criterion in order to account for state-related differences between process templates and process instances. Fur-
thermore, we extend our fundamental work by showing how semantic correctness of processes can be verified,
ranging from verifying semantic correctness for process templates at buildtime to verifying semantic correct-
ness of process changes. For this, we exploit the semantics of the applied change operations, for example when
applying single change operations (e.g., ad hoc changes of process instances), or when applying concurrent
changes (e.g., propagating process template changes to biased process instances). Afterwards, we discuss dif-
ferent possibilities to realize verification of semantic process correctness in an efficient manner. One way based
on exploiting certain process meta model properties is discussed in more detail. Finally, we show how the
semantic constraints can be organized within a domain repository.
Process Instance I
(Treatment for Patient Smith)
Insert
„Administer Aspirin“ Syntax check:
o.k.
Semantic check:
semantic conflict
Reason: ...
Enter reason:
Still execute insert
...
Fig. 2. Interaction scenario when a semantic conflict occurs.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 5
Author's personal copy
In Section 2, we present considerations on integrating semantics in adaptive PMS and motivate our
approach. In Section 3, a framework for the definition of semantic constraints and the notion of semantic cor-
rectness are introduced. In Section 4, we show how the semantic correctness of process templates and the
semantic correctness of process changes can be verified. The migration of running instances to a new template
is dealt with in Section 5. In Section 6, we show the application of the correctness criterion when, for example,
a block-structured process model is used. In Section 7, considerations on the integration of semantic verifica-
tion in adaptive PMS as well as a framework for organizing semantic constraints are presented. Related work
is discussed in Section 8. Finally, Section 9concludes with a summary and an outlook on future research.
2. On integrating semantics in adaptive PMS
As motivated in Section 1, it is desirable to integrate (semantic) domain knowledge into the PMS in order to
enable semantic-aware process management technology. Basically, it is possible to integrate even very complex
domain knowledge into adaptive PMS. By connecting the PMS with a knowledge-based system or an expert
system (e.g. [13]), for instance, domain knowledge maintained in the external system can be used to avoid
semantic conflicts. However, two aspects influence the possibilities of integrating domain knowledge into
adaptive PMS. First, it is an important question how and by whom the knowledge base is maintained. The
more domain knowledge, and in particular the more complex the knowledge, the greater is the effort 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 such
domain knowledge which is really important and which will really be kept up-to-date. Second, the goal of inte-
grating domain knowledge is to enable the PMS to also perform correctness checks at the semantic level. How-
ever, the effort to perform these semantic checks must not lead to a bottleneck, especially when changes on
process templates are propagated to a multitude of running and possibly ad hoc modified instances (for some
application domains, e.g., large hospitals, several thousands of instances may be active at the same time).
The two aspects mentioned above should be kept in mind when thinking about how to integrate domain
knowledge into adaptive PMS. Therefore, we introduce two fundamental kinds of semantic constraints which
can be imposed on processes: mutual exclusion constraints and dependency constraints. The reason is that
these kinds of constraints are very common in practice as we know from preliminary case studies (e.g.,
[14]). Exclusion and dependency constraints refer to tasks and impose certain conditions on how these tasks
can be used in the process. By enabling the PMS to be aware of these constraints, many semantic errors, for
example the ones depicted in Fig. 1, can be avoided. Furthermore, the introduced kinds of constraints are still
manageable regarding the effort for maintenance and semantic verification. We take these two kinds of con-
straints as a starting basis in order to find out, how semantic constraints and semantic verification can be
incorporated into the mechanisms of an adaptive PMS. In future work, we want to extend our approach step
by step in order to further investigate on the right balance between expressiveness of constraints, effort for
maintenance, and analyzability.
3. Semantic correctness for business processes
In this paper, we introduce two fundamental kinds of semantic constraints: mutual exclusion constraints
and dependency constraints. Mutual exclusion constraints express that two tasks are not compatible and
should not be executed together (e.g., administering two incompatible drugs). Mutual exclusion constraints
are symmetric. Dependency constraints express that a task is dependent of another task, i.e., these tasks have
to occur together in the process. In Fig. 1, for instance, task Perform Surgery is added to the process. How-
ever, in the treatment process the task 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 conflict, when only Perform Surgery is
inserted into the process.
6L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
At buildtime, a set of semantic constraints can be assigned to a process template which the template itself
as well as the process instances running according to this template have to comply with. Basically, it is pos-
sible to extend or restrict the set of inherited semantic constraints for certain process instances. However, an
extended or restricted constraint set at instance level has to be considered when checking semantic correct-
ness accordingly. In the remainder of this paper we assume that process instances inherit the set of semantic
constraints from their referenced process template. Furthermore, we assume the uniqueness of tasks in a
process (i.e., each task may occur only once in a business process). In future work, we will extend our con-
siderations to deal with other kinds of processes as well. In the following definition the structure of a seman-
tic constraint is determined.
Definition 1 (Semantic constraint). Let Abe a set of tasks.
1
A semantic constraint c=(type,source,target,
position,userDefined) whereas
•type 2{Exclusion,Dependency},
•source;target 2A,source5target,
•position 2{pre,post,notSpecified},
•userDefined is a user-defined parameter.
The parameter type denotes whether the semantic constraint is a mutual exclusion constraint or a depen-
dency constraint. The second parameter source denotes the source task the constraint refers to while target
denotes the target task related to the source task. Parameter position specifies in which order the source
and target task are to be related to each other within the process (e.g., the surgery depends on the prep-
aration of blood bottles and the bottles have to be prepared before the surgery (pre)). According to Def-
inition 1, there are six possible constraint types. The last parameter userDefined can be used for several
purposes, e.g., for additionally describing the constraint or to indicate the importance of the constraint.
In the latter case we can express if a constraint is merely a recommendation or if its violation leads to
severe problems in the sequel. By exploiting such information the PMS is able to create an appropriate
feedback for the user in case of violations. 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)
Based on the notion of semantic constraints a general criterion for semantic correctness is defined in the
following. Basically, semantic correctness needs information on how tasks can be used within in a process
and in which ordering relations they occur. All this information is captured within so called execution traces.
Therefore, we take execution traces as a basis for our formal criterion for semantic correctness. In addition,
defining the semantics of the constraints based on execution traces allows for a meta model independent
understanding of constraints. In Definition 2, we define the notion of execution traces and some useful func-
tions over them.
Definition 2 (Execution trace). Let Abe a set of tasks which can be used to specify a process template S.An
execution trace r:=he
1
,...,e
k
iover Scontains events e
i
= End(t)
2
,t2A. The set of all possible execution
traces over Sis denoted as Q
S
.
A process instance Iis defined as a tuple I:¼ðS;
rÞwhere Sdenotes the process template which captures
the structure of I
3
and execution trace
rcaptures the current execution state of I. Then Q
I
denotes the set of all
possible execution traces over process instance Iwith QI:¼fr2QSj9 ~
rwith r¼
r~
rg.
1
Within the ADEPT framework, for example, Arefers to the task repository containing all relevant tasks in the context of a certain
process type T.
2
We abstract from start events in the traces.
3
Since a process instance Ican be individually modified, the structure of Idoes not necessarily correspond to the structure of the
template Iwas started on.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 7
Author's personal copy
Useful functions over execution traces are:
•Function traceTasks(r) returns the set of all tasks constituting the execution trace r. Formally:
traceTasks:Q½SjI7!2Awith traceTasksðhe1;...;ekiÞ :¼ft2Aj9eiwith e
i
=End(t) where i=1,...,k}.
•Function possibleTasks([SjI]) returns all tasks which are executable for a process template Sor a process
instance I. Formally:
possibleTasksð½SjIÞ :¼Sn
i¼1traceTasksðriÞfor Q
[SjI]
={r
1
,...,r
n
}.
•Function traceSucc(t,r) returns the set of all direct and indirect successors of the task tin r. Formally:
traceSucc:AQ½SjI7!2Awith traceSuccðt;he1;...;ekiÞ :¼ft02Aj9ei,e
j
with e
i
=End(t0)^e
j
=End(t)^
j<i, where i,j=1,...,k}.
•Function tracePred(t,r) returns the set of all direct and indirect predecessors of the task t in r. Formally:
tracePred:AQ½SjI7!2Awith tracePredðt;he1;...;ekiÞ :¼ft02Aj9ei,e
j
with e
i
=End(t0)^e
j
=End(t)^
j>i, where i,j=1,...,k}.
In Fig. 3, the execution traces of example process templates and process instances are depicted. For process
template S
1
, two execution traces can be generated. This is because, for all instances of S
1
, either Bor Cwill be
executed (due to the XOR-split) resulting in two different kinds of instances of S
1
. Based on the current exe-
cution trace of I
1
(which is empty) the same execution traces as over S
1
can be generated. In contrast, the set of
possible execution traces of instance I
2
differs from the set of possible execution traces over S
1
, due to the cur-
rent execution trace of I
2
.InI
2
, task Bhas been executed whereas task Chas been skipped. Hence, Bneces-
sarily occurs in all possible execution traces over I
2
whereas Cdoes not occur in any of them.
Based on the of notion execution traces, we can define a trace-based satisfaction criterion for semantic con-
straints which we first want to motivate by means of some examples. Consider again the process template S
1
in
Fig. 3. Constraint c1 is violated when Cand Eare executed together, which is the case with trace ACDEFH.
Constraint c2 is violated if Cis executed but not G. This is the case with both the possible traces over S
1
. Con-
straint c3 is violated if His executed without Bbeing executed previously. Since Bis situated in an XOR-
branch, this situation occurs if Bis skipped and Cis executed instead (reflected by trace ACDEFH). In order
to avoid all possible semantic conflicts, the semantic correctness has to be ensured for all possible executions
(reflected by all possible execution traces) of a process template or a process instance. We refer to a semantic
constraint as being violated over a process if there are possible execution traces of the process violating the
constraint (cf. Definition 3). According to the set of possible execution traces over S
1
, the constraints c1,
c2,andc3 are not satisfied over S
1
(i.e., violated). For process instance I
1
, the very same applies. For process
instance I
2
, however, none of the semantic constraints are violated according to the only possible execution
trace over I
2
. Since task Cis skipped, c1 as well as c2 can never be violated. Also constraint c3 cannot be
violated since Bis already executed.
These examples show that constraints might be satisfied over a process instance, but not over the corre-
sponding template. This is because, generally, the traces which can be generated over a process instance at
a certain execution state form a subset of the traces, which can be generated over its process template. The
Fig. 3. Impact of execution states on the satisfaction of semantic constraints.
8L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
examples also show that the satisfaction of a constraint over a process template is constant over time (in case
no conflicting changes are made (cf. Section 4)), whereas the satisfaction of a constraint over a process
instance may vary due to its ongoing execution. All these aspects are accounted for in the following definition
of a satisfaction criterion for semantic constraints.
Definition 3 (Satisfaction criterion for semantic constraints). Let Abe a set of tasks which can be used to
specify process template Sand let Ibe a process instance derived from S. Let further Q
S
(Q
I
) be the set of
possible execution traces over S(I) and let a
1
,a22Abe two tasks, a
1
5a
2
. Then semantic constraint
c=(type,source,target,position,userDefined) with source =a
1
and target =a
2
is satisfied over S(I)–
formally: satisfied(c,[SjI]) = True – iff one of the following conditions holds:
•type 2{Exclusion,Dependency} and a
1
62 possibleTasks([SjI])
•type =Exclusion,position =pre and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))a
2
62
tracePred(a
1
,r)
•type =Exclusion,position =post and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))a
2
62
traceSucc(a
1
,r)
•type =Exclusion,position =notSpecified and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))a
2
62 trace-
Succ(a
1
,r)anda
2
62 tracePred(a
1
,r)
•type =Dependency,position =pre and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))a
2
2
tracePred(a
1
,r)
•type =Dependency,position =post and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))a
2
2
traceSucc(a
1
,r)
•type =Dependency,position =notSpecified and "execution traces r2Q
[SjI]
:a
1
2traceTasks(r))(a
2
2
tracePred(a
1
,r)ora
2
2traceSucc(a
1
,r))
Otherwise, cis violated over P(I), formally: satisfied(c,[SjI]) = False.
Based on the satisfaction criterion for semantic constraints, a semantic correctness criterion for process
templates and process instances can be defined.
Definition 4 (Semantic correctness of process template/instance). Let Sbe a process template and I¼ðS;
rÞbe
a process instance on S. Let further C
S
be the set of all semantic constraints imposed on S. Then, S(I)is
semantically correct M"c2C
S
:satisfied(c,[SjI]) = True.
Definitions 1–4 build the formal basis for semantic process verification and semantic change verification.
How the verification is conducted (in particular, how to avoid the calculation of all possible execution traces
over a process which has exponential complexity) is discussed in the following.
4. Semantic verification of process templates and process instance modifications
Verifying the semantic correctness of a process template (instance) based on Definition 4 might be expensive
depending on the number of semantic constraints imposed on the process template (instance) on the one hand
and the number of possible execution traces on the other hand. The verification effort, however, can be
decreased by restricting the set of semantic constraints to be checked as well as by avoiding a complete calcu-
lation and analysis of possible execution traces over the process template (instance). In Section 4.1, we present
considerations on how to minimize the amount of constraints to be verified for a process template. In Section
4.2, we show how to identify potentially violated constraints when ad hoc process adaptations are carried out.
4.1. On optimizing semantic verification of process templates
Basically, if a process template S specified over task set Ais built by applying process changes to an
‘‘empty’’ template the PMS might perform a semantic check each time a change operation is applied and check
whether the semantic correctness of the template is still preserved after the change or not (cf. Section 4.2). It is,
however, also important for an adaptive PMS to support the verification of a completely modeled process
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 9
Author's personal copy
template S. This is, for instance, necessary when Swas modeled with a tool not supporting stepwise semantic
verification and Sis imported into and executed by the PMS. In this case, it is necessary to verify whether the
constraints imposed on Sare satisfied or not. However, constraints, whose source task is not included in S, are
always satisfied over Sby definition (cf. Definition 3) and, thus, do not have to be verified. Altogether, the set
of constraints to be verified for the template Sand its constraint base C
S
is given by Cv
Swith:
Cv
S¼fc¼ð...;source;target;...Þ2CSjsource 2possibleTasksðSÞg
4.2. On checking semantic correctness after process instance changes
In our framework, an ad hoc process change is considered semantically applicable to a process instance I,if
its application still preserves the semantic correctness of I. The naive way of verifying the semantic correctness
of an instance Iafter a change is to verify the complete set of constraints Cv
Iobtained by applying the consid-
erations presented in Section 4.1. As we will show, this effort can be reduced by exploiting the semantics of the
applied change operations (e.g., which task has been inserted at which position). Thus, depending on which
change operation is requested, only a subset of constraints imposed on instance Ineeds to be verified. Consider
for example the process instance I
1
in Fig. 4. In order to verify whether the insertion of Gis semantically appli-
cable, we can exploit the fact that I
1
was semantically correct before the modification (i.e., all constraints
imposed on I
1
are satisfied before the change). Thus, there is no need to reverify each constraint. Instead, only
constraints which might be violated by the change operations are relevant. In Fig. 4, constraint c2,c3, and c4
do not affect the task to be inserted (G). Hence, they cannot be violated by the insertion of G.
Table 1 gives an overview of change operations, their effects, and the set of semantic constraints to be ver-
ified in order to verify the semantic applicability of the respective change operation. In the following, the
results presented in the table are explained in more detail.
4
When inserting a task ainto process instance I, all semantic constraints over Ihaving aas source parameter
need to be verified since they might be violated. For example, if ais dependent of or is incompatible to another
task, this is expressed by the semantic constraints associated with a(i.e., constraints having aas source param-
eter). For process instance I
1
in Fig. 4, this applies to constraint c1. Since mutual exclusion constraints are
symmetric, also mutual exclusion constraints with aas target parameter might be violated by the insertion
of a. In our example, this applies to constraint c5.
All other constraints are sure to be satisfied. Dependency constraints not having aas source parameter can-
not be violated by the addition of a(e.g., c2 and c3 in Fig. 4). Also exclusion constraints not affecting acan-
not be violated either (e.g., c4 in Fig. 4). The reason is that the process is supposed to be semantically correct
before applying the insertion. Hence, all constraints imposed on the process not related to aare supposed to be
satisfied over I. These constraints, therefore, can be excluded from satisfaction checks.
Based on information on the process instance, the set of potentially violated exclusion constraints can be
further minimized: Only those with source parameter in possibleTasks(I) (i.e., source is included in Iand is not
skipped) with target parameter corresponding to the inserted task acan be violated. That is because all exclu-
sion constraints, whose source parameter are not included in the process or will not come to execution, are
satisfied by definition (cf. Definition 3). As a result, in Fig. 4, only c1 needs to be verified in order to find
out whether the insert operation is semantically applicable.
Ad-hoc modification applicable regarding
the structure and the execution state of I1
Ad-hoc modification semantically
applicable to I1??
Constraints on I1
c1: (Dependency, G, D, post, ...)
c2: (Dependency, F, C, pre, ...)
c3: (Dependency, H, Q, notSpecified, ...)
…
c4: (Exclusion, C, X, post, ...)
c5: (Exclusion, W, G, notSpecified, ...)
...
F
AB
C
D
E
G
Instance I1
Fig. 4. Minimizing the set of potentially violated constraints for instance changes.
4
In this paper, we restrict our considerations to the most common change operations: Insert,Delete, and Move.
10 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
When deleting a task afrom process I, all semantic constraints over Iwith aas source parameter are sat-
isfied by definition. Similar to the insertion of tasks, all constraints for which aoccurs as target parameter are
potentially interesting for correctness checks. However, mutual exclusion constraints with aas target param-
eter cannot be violated by the deletion of a. Only dependency constraints with aas target parameter and whose
source parameter is included in Iand is not skipped (i.e., in possibleTasks(I)) might be violated by the deletion
operation and, therefore, need to be verified.
Moving a task afrom its original position within process Ito a new position pos can be understood as being
equivalent of deleting aand inserting aat pos afterwards.
5
Consequently, all constraints which might be vio-
lated after applying deletion and insertion operations need to be verified.
Generally, these considerations can also be applied in order to verify changes at template level. Note that
changes might be applicable to a process instance which are not semantically applicable to the corresponding
template. Due to the current execution trace of the instance, semantic constraints might be satisfied over the
instance after a process change while not beeing satisfied over the corresponding template after the same pro-
cess change (cf. Section 3).
5. On checking semantic correctness for process template evolution
In addition to ad hoc changes at the instance level, adaptive PMS must also support modifications of pro-
cess templates. This becomes necessary, for instance, when changes in laws and policies need to be adopted in
the business process (process optimization). In those cases, it is not only necessary to be able to modify the
process template but also to propagate template changes to instances already running according to the old
template (cf. Fig. 5). As mentioned, for semantically verifying the template change, the considerations made
in Section 4.2 can be applied. The question of whether and how running instances can be migrated to the new
template version is more challenging.
Table 1
Change operations, their effects, and the set of semantic constraints to be verified
Operation applied to
instance I
Effect Constraints to be verified (Cv
I)
Insert(I,a,pos) Inserts task ainto instance Iat
position pos
Cv
I¼{c=(type,source,target,...)2C
I
j(source =a)_
(type =Exclusion ^source 2possibleTasks(I)^target =a)}
Delete(I,a) Deletes task afrom instance ICv
I={c=(type,source,target,...)2C
I
j(type =Dependency
^source 2possibleTasks(I)^target =a)}
Move(I,a,pos) Moves task ato the position pos
in instance I
Cv
Icorresponds to the union of the constraint sets to be verified when
performing Delete(I,a) and Insert(I,a,pos)
5
In conjunction with data flow aspects, moving is not always equivalent to deleting and inserting. However, this assumption can be used
to derive statements about possible semantic conflicts here.
AB
C
D
EF
Process template S
ABCEF
New process template version S’
AB
C
D
EF
AB
C
D
EF
AB
C
D
EG
F
Instance migration
Instances running on S
Evolution of S
AB
C
D
EF
AB
C
D
EF
ABCEG F
AB
C
D
EF
AB
C
D
EF
AB
C
D
EG
F
Instances still running on S
Instances migrated to S’
Fig. 5. Propagating process template changes to running process instances.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 11
Author's personal copy
In order to be migrated to the new template version, it is important that instances are not only syntactically
but also semantically compliant to the new template. In current literature, the problem of testing syntactical
compliance of instances has already been tackled. In [8,15], a change framework for efficient syntactical
instance migration is introduced. Using this framework it can be checked, for example, whether migrating
an instance to the new template would cause structural (e.g., deadlocks-causing cycles or not correctly sup-
plied input parameters) or state-related inconsistencies. This has been accomplished for arbitrary running pro-
cess instances. Since process instances can be individually modified via ad hoc changes this is not a trivial task.
The problem of testing semantic compliance, to our best knowledge, is novel in the context of adaptive PMS.
In general, a process instance Iis semantically compliant with a new process template version S0, if the tem-
plate changes are semantically applicable to Ias an ad hoc change. However, trying to apply the template
change to each running process instance is not feasible in practice since there might be thousands of instances
to be checked. In this paper, we present more efficient mechanisms to find out, whether instances can be
migrated to the new template without violating any semantic constraints. For this purpose, first of all, it is
determined which instances can be migrated to the new template version in a syntactically correct manner.
Then, the semantic checks are only applied to the set of syntactically compliant instances. For a better under-
standing, some background information on the syntactical instance migration framework is provided in the
next section.
5.1. Background information: syntactical instance migration
In the framework presented in [8,15], instances to be checked for syntactical compliance are classified
according to the relation between their individual changes and the template changes (cf. Fig. 6). The reason
for doing this is that the migration strategy to be applied (i.e., whether the instance is compliant with the tem-
plate changes and if so which instance adaptions become necessary) is based on the degree of overlap between
instance and template changes [8]. Our basic idea is to check whether the classification for syntactical compli-
ance is useful for checking semantic compliance as well. This would be very beneficial since the classification
has to be accomplished in any case and could be used for semantic verification at no extra costs.
As shown in Fig. 6, instances can be divided into two main classes: unbiased instances and biased instances.
Unbiased instances are instances, which have not been individually modified so far (cf. Fig. 7). Biased
instances have already been individually modified. Depending on the degree of overlap between instance
and template changes, they can be further divided into subclasses: instances with disjoint bias and instances
with overlapping bias.
Informally, instance and template changes are disjoint if they affect different areas of the underlying process
structure. In Fig. 7, instance I
6
belongs to this class. Instances with overlapping bias comprise instances which
have changes partly or fully overlapping with the changes of the template. There are three subclasses to this
class: equivalent bias,subsumption equivalent bias, and partially equivalent bias (again, this distinction is nec-
essary for finding adequate migration strategies afterwards).
In the following, let DIbe the instance changes on a process instance Iand DSbe the template changes on
process template S.
collection of proces instances running on
the old template version
unbiased
instances
biased
instances
instances with
overlapping bias
instances with
disjoint bias
partially
equivalent bias
equivalent
bias
subsumption
equivalent bias
SC Non-SC
SC Non-SC SC Non-SC
SC Non-SC
SC Non-SC SC Non-SC
I subsumes Δ
Δ
Δ
Δ
Δ
S
S subsumes
I
SC: syntactically compliant instances
Non-SC: syntactically non-compliant instances
Fig. 6. Classification of instances according to the syntactical migration framework.
12 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
Instances with equivalent bias have the same modifications as the template (cf. instance I
2
in Fig. 7).
Instances with subsumption equivalent bias can be further divided into two classes: DI subsumes DSand
DS subsumes DI. For instance I
3
in Fig. 7, for example, the instance changes comprise the template changes
plus a delete operation. Thus, I
3
belongs to the class DI subsumes DSwhereas instance I
4
belongs to the class
DS subsumes DI. Instances with partially equivalent bias have changes in common with the new template ver-
sion. However, there are also changes on the template which do not correspond to the instance changes and
vice versa. In Fig. 7, instance I
5
belongs to this class.
Based on the classification presented in Fig. 6 it can be checked whether the instances are syntactically com-
pliant or syntactically non-compliant with a modified process templated. Checking for semantic compliance of
instances which are not syntactically compliant with the new template does not make sense. Therefore, in this
paper, we focus on efficiently checking the semantic compliance of syntactically compliant instances. As
already mentioned, the classification depicted in Fig. 6 can be used as input for semantic migration tests at
no extra costs. In Section 5.3, we show how this classification can be employed in order to reduce semantic
verification efforts.
5.2. The basic scenario: semantic migration of unbiased process instances
In case a template change DSis semantically correct on S, it will also be semantically correct when being
applied to unbiased instances. This is because unbiased instances only differ from the template in point of their
execution states. Thus, changes semantically applicable on a process template are a subset of changes seman-
tically applicable on the template’s unbiased instances (cf. Section 3). As a consequence, unbiased instances are
A
Template S1
AB
C
D
EFB
C
D
EH
GF
Template S2
SΔ
Δ
Δ
Δ
Δ
Δ
Δ
ΔΔ
ΔΔ
1= {Insert(S1,G,pos), Insert(S1,H,pos)}
Subsumption equivalent bias: a) I subsumes S
Instance I3
I3= {Insert(I3,G,pos), Insert(I3,H,pos), Insert(I3,N,pos)}
AB
C
D
EH
GFN
F
Subsumption equivalent bias: b) S subsumes I
AB
C
D
E
G
Instance I4
I4= {Insert(I4,G,pos)}
Partially equivalent bias
Instance I5
A G C
BE F I5= {Insert(I5,G,pos), Delete(I5,D)}
Disjoint bias
I6= {Insert(I6,K,pos)}
K
AB
C
D
EF
Instance I6
c1: (Exclusion, K, H, notSpecified)
c2: (Exclusion, H, M, post)
...
c3: (Dependency, H, D, pre)
c4: (Dependency, H, C, pre)
...
Constraint base
Instance I1
Unbiased instances
AB
C
D
EFI1= Ø
A
Equivalent bias
B
C
D
EH
GF
Instance I2
I2= {Insert(I2,G,pos), Insert(I2,H,pos)}
Fig. 7. Process template and instance changes with different degrees of overlap.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 13
Author's personal copy
semantically compliant to the new process template version and can be migrated without any further checks.
In Fig. 7, for example, instance I
1
can be migrated to S
2
without any additional semantic checks.
5.3. The advanced scenario: concurrent process changes
Contrary to unbiased instances, applying template changes to biased instances may lead to semantic con-
flicts between process template and process instance changes (concurrent changes). Fig. 8 gives an example of
how merging the changes by migrating instance I
6
to the new template version S
2
causes a semantic conflict. At
the template level, task Gand Hare inserted resulting in the new template S
2
. Instance I
6
was individually mod-
ified at runtime by inserting task K. Propagating template changes to I
6
, however, causes a semantic conflict.
This is because, the insertion of His not semantically applicable to I
6
, since Kis not compatible to H. Imagine,
for instance, that, at template level, Aspirin is administered while at instance level, Marcumar is administered.
Even though the resulting instance would be syntactically correct, I
6
cannot be migrated to S
2
in a semanti-
cally correct way.
In Section 5.3.1, we show how the amount of instances to be verified can be further reduced in order to
reduce the effort for verifying biased instances. Then, in Section 5.3.2, we present considerations on how to
minimize the amount of constraints to be checked depending on the semantics of the change operations made
at template and instance level.
5.3.1. Identifying semantically critical instances
As mentioned before, it only makes sense to migrate biased instances, which are syntactically compliant
with the new template version. Depending on the ad hoc changes applied to the instance so far, however, it
is not necessary to check all syntactically compliant instances for semantic compliance. Based on the classifi-
cation of the syntactically compliant instances as presented in Section 5.1, we provide different semantic
migration strategies in order to reduce semantic verification efforts.
Equivalent bias: Since template and instance changes are equivalent, instances of this class are syntactically
identical to the new template version (cf. instance I
2
in Fig. 7). Thus, no semantic conflicts can ever occur when
migrating these instances to the new template. As a consequence, it is not necessary to carry out any semantic
migration checks for these instances. Instead, they can be migrated without any semantic checks.
Subsumption equivalent bias: This class is further divided into two subclasses:
DIsubsumes DS: Instances of this class can be semantically migrated to a new template version S0without
any further semantic checks. This is because all template changes are already included (i.e., anticipated) in
the set of changes on the process instance. For instance I
3
in Fig. 9, for example, task Nis inserted addi-
tionally to the changes made at template level. The changes Ihas in common with S0cannot lead to a
semantic conflict in case of a migration (this is comparable to instances in the class equivalent changes).
Furthermore, Iis supposed to be semantically correct due to semantic verification of the ad hoc changes
on I. Hence, also the additional changes on I(e.g., the insertion of Ninto I
3
in Fig. 9), cannot semantically
conflict with the template changes (i.e., the remaining changes on I). Thus, instances of this class can also be
migrated without any semantic checks (cf. Fig. 9).
DSsubsumes DI: Since DSsubsumes DI, migrating Ito S0means to propagate those template changes to I,
which are not included in DI. For I
4
in Fig. 9, this would mean to propagate the insertion of Hto I
4
. Since
Template S1
AB
C
D
EF
K
AB
C
D
EF
Individually modified Instance I6running on S1
K
B
C
D
EHF
G
A
- syntactically correct
- semantically incorrect
Migration of I6to S2
Template S2
AB
C
D
EH
GFc1: (Exclusion, K, H, notSpecified)
...
Constraint base
S1= {Insert(S1,G,pos), Insert(S1,H,pos)}
Δ
Fig. 8. Semantic conflict due to concurrent changes at template and instance level.
14 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
all instance changes DIare already anticipated by DS, a propagation cannot lead to a semantic conflict
between the change operations. After a migration, Iis structurally identical to S0(cf. Fig. 9). As a conse-
quence, instances of this class can also be migrated without any semantic checks.
Disjoint bias DS\DI= ø: Contrary to the instances considered so far, migrating instances of this class to a
new template version S0may cause semantic conflicts. Since the instance changes and the template changes are
disjoint, semantic conflicts may be caused by the interplay of these changes (e.g., insertion of two incompatible
tasks at template and at instance level). Consequently, it has to be checked whether instances of this class are
semantically compliant to S0. This is true, if DSis semantically applicable to Ias an ad hoc change (cf. Section
5.3.2). Partially equivalent bias DS\DI5ø: Similar to instances with disjoint changes, instances whose
changes are partially equivalent to the template changes may be semantically incorrect if migrated to the
new template version. This is because the changes made on Sbut not on I(i.e., DSnDI) may be conflicting
with changes made on Ibut not on S(i.e., DInDS) when being propagated to I.InFig. 7, this applies to
the insertion of Hinto I
5
. This would cause a semantic conflict, since Hneeds Dto be executed previously (con-
straint c3) but Dhas already been deleted from I
5
. Thus, instances with partially equivalent bias have to be
verified. However, it is not necessary to check whether DSis semantically applicable to Ias a whole (as for
instances with disjoint changes). Since changes which DSand DIhave in common are semantically applicable
on I, these changes are compatible to other ad hoc changes made on I. In our example, the insertion of Ghas
already been applied to I
5
. Thus, this change operation cannot conflict with other changes on I
5
. Conse-
quently, instances of this class are semantically compliant with S0,ifDSnDIis semantically applicable to I
as an ad hoc change (e.g., deletion of Dfor instance I
5
in Fig. 7). For the calculation of DSnDI, we refer to [8].
Using the considerations presented above unnecessary semantic migration checks can be avoided. As
summed up by Table 2, only instances of the classes partially equivalent bias and disjoint bias have to be
checked for semantic compliance. For instances of the class partially equivalent bias, the verification effort
can be reduced by minimizing the set of changes to be checked.
In the next section, we show how to minimize the set of constraints to be verified for instances of both these
classes.
I subsumes S
Instance I3
I3= {Insert(I3,G,pos), Insert(I3,H,pos), Insert(I3,N,pos)} I3’ = {Insert(I3,N,pos)}
A
Template S1
AB
C
D
EFB
C
D
EH
GF
Template S2
S1= {Insert(S1,G,pos), Insert(S1,H,pos)}
AB
C
D
EH
GFNAB
C
D
EH
GFN
S subsumes I
Instance I4
I4= {Insert(I4,G,pos)}
F
AB
C
D
E
GF
AB
C
D
E
GH
IΔ4’ = Ø
Migration
to S2
Migration
to S2
Δ
Δ
ΔΔ
ΔΔ
Δ
Δ
Fig. 9. Migration of instances from the class subsumption equivalent changes.
Table 2
Instance classes and changes to be semantically verified
Instance class Changes to be semantically verified
Unbiased ;
Equivalent bias ;
DIsubsumes DS;
DSsubsumes DI;
Partially equivalent bias DS
Disjoint bias DSnDI
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 15
Author's personal copy
5.3.2. Identifying potentially violated constraints
In this section, we present how the checks for semantic compliance necessary for instances with disjoint or
partially equivalent changes can be optimized. In particular, an instance Iof the class disjoint bias (partially
equivalent bias) is semantically compliant if the templates changes DS(DSnDI) are semantically applicable
to Ias an ad hoc change, respectively. For applying this compliance criterion, the considerations for ad
hoc changes in order to identify potentially violated constraints presented in Section 4.2 can be employed.
Take, for example, instance I
5
from Fig. 10. Instance I
5
belongs to the class partially equivalent bias.Asa
result, it is semantically compliant with S
2
, if the insertion of His semantically applicable to I
5
. Applying
the considerations for identifying critical constraints for ad hoc changes from Section 4.2, the constraints
c2,c3, and c4 are identified as potentially violated. However, different from verifying the applicability of
ad hoc changes, more semantic information is available when verifying the semantic compliance of instances
with a new template version. It is known that the template change is semantically applicable to the template
and the instance change is semantically applicable to the instance. This information can be exploited to further
narrow down the set of constraints potentially violated by only considering constraints which might be vio-
lated by the interplay, i.e. the merge, of both the template and instance changes.
In Table 3, for each combination of change operations at instance and template level the corresponding
constraint types which might be violated by the interplay of both the changes are listed. If, for example, task
ais inserted into instance Iwhile task bis inserted into template Sresulting in S0, only exclusion constraints
affecting both of the inserted tasks can be violated when the Iis migrated to S0.
In Fig. 10, only constraints need to be verified which can be violated by the application of both the changes
Insert(I
5
,H,pos) and Delete(I
5
,D). According to Table 3, only a constraint of type (Depen-
dency,H,D,2...)can possibly be violated. Only constraint c3 corresponds to this type and, therefore, has
to be verified. In our example, c3 would be violated by the change propagation. Hence, I
5
cannot be seman-
tically migrated to S
2
.
In Section 5, we narrowed down the set of instances to be semantically verified based on the degree of over-
lap between instance and template changes. Furthermore, we showed how to minimize the set of constraints to
be verified by exploiting the semantics of the change operations. In the next section we consider how to opti-
mize the verification of these constraints.
Migration of Instance I5
I5= {Insert(I5,G,pos), Delete(I5,D)}
A G C
BE F
A
Template S1
AB
C
D
EFB
C
D
EH
GF
Template S2
S1= {Insert(S1,G,pos), Insert(S1,H,pos)}
A G C
BEFH
Propagating template
changes to I5
c1: (Exclusion, K, H, notSpecified)
c2: (Exclusion, H, M, post)
...
c3: (Dependency, H, D, pre)
c4: (Dependency, H, C, pre)
...
Constraint base
Apply Insert(I5,H,pos)
Conflicting changes
according to the
constraint base?
Δ
Δ
Fig. 10. Identifying potentially violated constraints for propagating template changes to instances.
Table 3
Potentially violated constraint types depending on the applied change operations at template and instance level
Insert(I,a,pos) Delete(I,a) Move(I,a,pos)
Insert(S,b,pos) (Exclusion,b,a,...) (Dependency,b,a,...) (Exclusion,b,a,...)
(Exclusion,b,a,...) (Exclusion,a,b,...)
(Dependency,b,a,...)
Delete(S,b) (Exclusion,a,b,...) (Dependency,a,b,...)
Move(S,b,pos) (Exclusion,b,a,...) (Dependency,b,a,...) (Dependency,b,a,...)
(Exclusion,a,b,...) (Dependency,a,b,...)
(Dependency,a,b,...) (Exclusion,b,a,...)
(Exclusion,a,b,...)
16 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
6. On optimizing verification strategies based on process meta model properties
The trace-based satisfaction criterion for semantic constraints introduced in Section 3is generic and can be
applied to any process meta model (e.g., Petri Nets [1] or BPEL4WS Nets [16]). 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 tasks according to the semantic constraints) which might be very costly. There-
fore, we want to investigate different methods to verify the satisfaction of constraints 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-indepen-
dent methods in future work.
6.1. Background information
This section summarizes background information on WSM Nets [17,15] as process description formalism in
order to present an optimized verification method for semantic correctness.
Aprocess template is represented by a WSM Net which defines the process tasks as well as the control and
data flow between them. When using WSM Nets the control flow template can be represented by attributed,
serial–parallel graphs. In order to synchronize tasks from parallel paths additional links can be used [18].In
this paper we abstract from cyclic structures within the process meta model in order to provide a fundament
for an optimized semantic correctness verification. Further on, a WSM Net comprises a set of data elements
and a set of data edges. A data edge links a task with a data element and either represent a read access of this
task or a write access. The total set of data edges constitutes the data flow template.
Definition 5 (WSM Net). A tuple S=(N,D,NT,CtrlEdges,SyncEdges,DataEdges,BC) is called a WSM
Net, if the following holds:
•Nis a set of process tasks and Da set of process data elements
•NT:N#{StartFlow, EndFlow, Task, AndSplit, AndJoin, XOrSplit, XOrJoin, StartLoop,
EndLoop}NT assigns to each node of the process template a respective node type.
•CtrlEdges N·Nis a precedence relation definining the valid order of tasks (notation: n
src
!n
dst
(n
src
,
n
dst
)2CtrlEdges)
•SyncEdges N·Nis a precedence relation between tasks of parallel branches
•DataEdges N·D·{read, write} is a set of read/write data links between tasks 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 undefined for nodes n with NT(n)5XOrSplit.
Which constraints have to hold such that a process template Sis well-structured is summarized in [18,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 tasks of node type AndSplit (XOrSplit) there is a
unique task of node type AndJoin (XOrJoin) and blocks (sequences as well as parallel and alternatives
branchings) can be nested but must not overlap.
6.2. On exploiting process meta model properties
For each type of semantic constraint, we derived structural and state-related conditions on WSM Nets
which ensure the trace-based constraint satisfaction criterion presented in Section 3. Using these meta model
specific conditions the satisfaction of semantic constraints and, thus, the semantic correctness of a process can
be verified in an optimized way. Due to space restrictions, however, we abstain from presenting all conditions
in this paper. Instead, we show how meta model specific conditions can be derived for one example constraint
type. First, we focus on process templates. Later, we extend our considerations to process instances. Consider
the following semantic constraint over the treatment process from Section 1:
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 17
Author's personal copy
c1:ðExclusion;AdministerAspirin;AdministerMarcumar;notSpecified;...Þ
In general, an exclusion constraint is always satisfied if either the source or the target task is not included in the
set of tasks constituting the template. Due to the absence of at least one of the two tasks, no execution of the
template is possible which violates the constraint. The only way target and source task can both occur in a
process template without violating c
1
is on different branches of an XOr-block. In this case, the tasks can only
be executed exclusively which ensures the semantic correctness of all of the template’s possible executions. In
Fig. 11,c
1
is not satisfied over process template S
1
, since there are possible execution traces over S
1
for which
both of the incompatible tasks are executed.
From this example we conclude the following conditions for the satisfaction of exclusion constraints of type
c
ex
=(Exclusion,source,target,notSpecified,...) over block-structured process templates:
A semantic constraint c
ex
imposed on a process template S represented by a WSM Net (N,D,NT,...)is
satisfied if and only if one of the following conditions holds.
•source 62 N(i.e. source does not occur in S);
•target 62 N(i.e. target does not occur in S);
•MinBlock(S,source,target)=(blockStart,blockEnd)withblockStart =XOrSplit, where MinBlock
denotes a function which returns the start and end task of the minimal block surrounding the given tasks
[19].
In [12], we presented the structural satisfaction conditions for dependency constraints and proved that they
ensure the trace-based satisfaction criterion.
In general, the structural satisfaction criterion for process templates can also be applied to process
instances. However, due to the current execution state of the process instances, this is too restrictive. The rea-
son is that there are situations in which the semantic constraint is satisfied over a process instance (due to its
execution states) but not over the corresponding process template (cf. Section 3). Take for example instance I
1
in Fig. 11. Constraint c
1
is satisfied over I
1
but not over S. This is because for I
1
, task Administer Aspirin
has already been skipped. Thus, for all possible execution traces of I
1
,Administer Aspirin and Admin-
ister Marcumar will not occur together, independently from whether Administer Marcumar will be exe-
cuted later on or not. Since exclusion constraints are symmetric, the same applies if Administer Marcumar
is skipped. Thus, for process instances the structural satisfaction criterion has to be complemented by addi-
tional state-related satisfaction criterion in order to account for these situations.
A semantic constraint c
ex
=(Exclusion,source,target,notSpecified,...) over a process instance I¼ðS;
rÞ
with Scapturing the structure of Iis satisfied if and only if one of the following conditions holds:
•c
ex
is satisfied over S(structural condition)
•ExState(source)=SKIPPED, where ExState denotes a function which returns the execution state marking
for the corresponding node
•ExState(target)=SKIPPED
The structural/state-related satisfaction conditions on block-structured process meta models derived can be
verified very efficiently. In particular, special properties of the meta models, for instance references to the cor-
responding split/join node of a block and topological sorting [19], can be exploited by the PMS in order to find
out whether the respective constraint is satisfied or not.
Administer Aspirin
Process template S1Administer
Marcumar Administer Aspirin Administer
Marcumar
Instance I1
Fig. 11. Satisfaction of exclusion constraints over process templates and instances.
18 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
7. Architectural considerations
In this section, we present our ideas on integrating semantic verification into the verification mechanisms of
an adaptive PMS. In addition, we present our ideas on organizing semantic constraints in order to facilitate
constraint reuse.
7.1. Architectural integration
As pointed out previously, semantic verification is coupled with structural verification. In Fig. 12, an exam-
ple interaction for verifying an ad hoc change is depicted. At first, an ad hoc change is initiated be the user.
Since ad hoc changes are often performed by end-users, the workflow client needs to provide adequate fea-
tures. The change request is then processed to the process engine. Internally, a module is required to coordi-
nate the verification process. First, the structural verification is triggered for the change request. In case the
change is not syntactically applicable, the change can be denied immediately. In our example, the change does
not cause any syntactical errors. Thus, semantic verification is triggered. Depending on the results, the coor-
dinator can allow or deny the change and provide an appropriate feedback.
7.2. Organization of 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 organizing semantic constraints for their easy reuse.
Process engine
Structural
verification module
Semantic
verification module
Workflow client
1. Initiate ad-hoc change
2. Request ad-hoc change
3. Change syntactically
applicable?
4. Change semantically
applicable?
5. Allow or deny change
Verification coordinator
Fig. 12. Interaction scenario for verifying ad hoc changes.
Additional
process specific
constraints
Domain
constraints
Selection of relevant domain
constraints
Constraints on Treatment Process
Treatment Process
Task
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. 13. Organization of constraints in a domain constraints repository.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 19
Author's personal copy
The three main components of the framework are the domain repository, the process repository, and the task
repository (cf. Fig. 13). Semantic constraints are organized in the domain repository. In particular, constraints
are assigned to domains (e.g., 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 tasks which are
organized in a task repository. For future work, we also plan to introduce constraints that refer to other
abstraction levels, for instance abstraction levels in the task repository. Process templates are organized in
a process repository. Each process template 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 different semantic constraints that are not captured in the domain. Therefore, for each
process template, the process designer can specify additional semantic constraints for the process or leave out
some unnecessary domain constraints. Thus, it is possible to tailor an individual set of constraints for each
process template.
8. Related work
The discussion ranges from approaches which we consider as being most related to ours to related work
which can be seen as orthogonal to our approach.
Rule/Constraint-Based Process Specification: In [20–22], approaches dealing with the specification of inter-
task interdepencies are introduced. One of the main concerns in [21,22] is to provide a scheduler which sched-
ules the tasks (and their events like commit or abort) according to the specified dependencies. A workflow is
considered a set of dependencies between tasks which are specified using different formalisms, e.g., computa-
tional tree logic (CTL) [21]. Although focussing on inter-workflow dependencies, the basic ideas of the
approach presented in [23] are quite similar to the approaches mentioned before. One of the main differences
is that the approach in [23] uses an extension of regular expressions for expressing legal executions of
workflows.
For verifying the runtime execution, a state automaton based approach is employed. Due to their transac-
tional background, [20–23] focus on scheduling upcoming event requests (e.g., the start of a task) according to
predefined dependencies whereas in our approach, violations of dependencies shall be detected as early as pos-
sible (i.e., in advance). Furthermore, also the aspect of process change is not addressed. In [24], an approach to
declaratively specify process models using a graphical notation which can be mapped to formulas in Linear
Temporal Logic (LTL) is presented. In order to enact the process model, the LTL formulas can be synthesized
into automatons.
Other approaches on constraint-based process specifications have been introduced, for example using Con-
current Transaction Logic (CRT) [25] or path constraints [26]. These approaches aim at providing a formalism
which allows for defining local and global dependencies (constraints) between tasks and also for verification of
the specified constraints. However, the verification is only considered for the static case (comparable to seman-
tically verifying a process template). In [27–29] workflows are modeled based on rules or constraints. However,
these approaches do not aim at verifying semantic constraints.
Adaptive/flexible PMS: Current approaches on adaptive PMS mainly focus on structural aspects (e.g.,
[3,4,8,30]) or have a different notion of semantic correctness (e.g., [31,1]).
Some approaches (e.g., [32,33]) aim at enabling more flexible process executions. The basic idea is to allow
the execution of a partly defined process template (core process). At runtime, once the flexible parts of the
process (predefined as a pocket of flexibility which is comparable to an unspecified subprocess) is reached,
a process expert can complete the specification of the subprocess. The subprocess is then verified based on con-
straints (e.g., composition constraints), which are used to restrict the composition possibilities. Although these
approaches rather aim at allowing for more flexibility they are very inspiring for our work, especially the con-
straints they introduced. However, the verification of the subprocess can be compared to verifying a process
template. Verification of real ad hoc changes at runtime are not addressed.
In [34,35], an approach for ensuring the integrity of process instances based on rule-based process adapta-
tion is introduced. Rules are applied, when certain conditions (e.g., too high blood pressure) apply. Using the
ADEPT framework [18] the process is adapted in an ad hoc manner according to the rule triggered. This
20 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
approach is not directly applicable to process verification but is interesting for preserving the semantic integ-
rity of process instances at runtime.
Integration of heterogenous sources: Many related approaches focus on integrating heterogenous resources
(e.g., [36–38]) and semantic web service composition (e.g., [39,40]). In particular, tasks and their parameters
are often described using ontologies. When a process is composed, the PMS can check, whether the tasks
and their parameters semantically fit together. However, these approaches do not consider semantic con-
straints over processes.
Knowledge-based systems: Besides, there are also approaches which we consider as being orthogonal to our
work. Interesting in this context are knowledge-based systems [13]. In such systems, expert knowledge can be
deposited. Recently, knowledge-based systems became more popular in the form of Business Rule Manage-
ment Systems (BRMS), e.g., commercially available systems like ILOG JRules [41]. BRMS provide conve-
nient interfaces for managing and deploying business rules (e.g., ‘‘if credit risk >50%, then refuse loan’’).
By employing techniques known from knowledge-based systems, the rules can be evaluated in the Business
Rule Engine (BRE) of the BRMS. In the context of PMS, a BRE is primarily used for decision making
(e.g., which outgoing paths of a task to follow). This is done by predefining decision making points in the pro-
cess and business objects (e.g., a customer’s credit risk) used for passing data from the PMS to the BRE and
vice versa. At runtime, the BRE is then invoked and can operate over the predefined business objects [9,41].
Approaches concerning the integration of organizational memory information systems (OMIS) into process
management (e.g., [42,43]) can also be considered orthogonal to our work. In particular, [42,43] deal with pro-
viding background information (e.g., former experience with a particular customer) based on context infor-
mation (e.g., the customer) in order to support users when executing knowledge-intense tasks.
A Posteriori Verification: In [44] an approach for verifying properties of past processes by verifying execu-
tion logs is introduced. This approach can help detecting constraint violations. However, being an a posteriori
verification approach this approach is orthogonal to our work. These two approaches can complement each
other.
9. Summary and outlook
Our objective is to enable adaptive PMS to perform semantic verification. However, semantic verification
must not be conducted in an isolated manner. In fact, semantic verification must be incorporated into typical
adaptive PMS interaction scenarios such as ad hoc changes and template evolution. In this paper, we intro-
duced a framework for the integration of domain knowledge within an adaptive PMS by using semantic con-
straints. 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 of process changes and verifying the semantic compliance of individu-
ally modified process instances with a modified template. Exemplarily for block-structured process meta mod-
els, we have shown how semantic process verification can be realized in an efficient manner. Finally, an
architecture for the integration of semantic constraints within an adaptive PMS has been presented.
Using our approach, all semantic conflicts caused by violation of dependency and mutual exclusion con-
straints 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 task
level (e.g., data). Furthermore, we want to develop further methods to efficiently verify semantic correctness
within an adaptive PMS. For example, we want to analyze how the information referred to by semantic con-
straints can be organized (e.g., within an ontology) in order to decrease evaluation effort. All considerations
are to be implemented within the adaptive PMS ADEPT2 (www.aristaflow.com).
References
[1] W. van der Aalst, T. Basten, Inheritance of workflows: an approach to tackling problems related to change, Theor. Comput. Sci. 270
(1–2) (2002) 125–203.
[2] F. Casati, S. Ceri, B. Pernici, G. Pozzi, Workflow evolution, DKE 24 (3) (1998) 211–238.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 21
Author's personal copy
[3] S. Rinderle, M. Reichert, P. Dadam, Flexible support of team processes by adaptive workflow systems, DPD 16 (1) (2004) 91–116.
[4] M. Weske, Formal foundation and conceptual design of dynamic adaptations in a workflow management system, in: HICSS ’01,
IEEE Computer Society, Washington, DC, USA, 2001, p. 7051.
[5] K. Kochut, J. Arnold, A. Sheth, J. Miller, E. Kraemer, B. Arpinar, J. Cardoso, IntelliGEN: a distributed workflow system for
discovering protein–protein interactions, DPD 13 (1) (2003) 43–72.
[6] M. Reichert, S. Rinderle, P. Dadam, On the modeling of correct service flows with BPEL4WS, in: EMISA ’04, 2004, pp. 117–128.
[7] S. Rinderle, M. Reichert, P. Dadam, Correctness criteria for dynamic changes in workflow systems – a survey, DKE 50 (1) (2004) 9–
34.
[8] S. Rinderle, Schema Evolution in Process Management Systems, Ph.D. Thesis, University of Ulm, 2004.
[9] A. Rowe, S. Stephens, Y. Guo, The use of business rules with workflow systems, in: W3C Workshop on Rule Languages for
Interoperability, 2005.
[10] A. Boxwala, M. Peleg, S. Tu, GLIF3: a representation format for sharable computer-interpretable clinical practice guidelines,
Biomed. Inform. 37 (3) (2004) 147–161.
[11] S. Quaglini, M. Stefanelli, A. Cavallini, G. Micieli, C. Fassino, C. Mossa, Guideline-based careflow systems, Artif. Intell. Med. 20 (1)
(2000) 5–22.
[12] L.T. Ly, S. Rinderle, P. Dadam, Semantic correctness in adaptive process management systems, in: BPM ’06, LNCS, vol. 4102,
Springer, 2006, pp. 193–208.
[13] F. Hayes-Roth, N. Jacobstein, The state of knowledge-based systems, Commun. ACM 37 (3) (1994) 26–39.
[14] B. Schultheiß, J. Meyer, R. Mangold, T. Zemmler, M. Reichert, The modelling of a surgery process, Interne Ulmer Informatik-
Berichte DBIS-6, Ulm University, Institute of Databases and Informations Systems, in german, 1996 (in German).
[15] S. Rinderle, M. Reichert, P. Dadam, Disjoint and overlapping process changes: challenges, solutions, applications, in: CoopIS ’04,
2004, pp. 101–120.
[16] T. Andrews, F. Curbera, H. Dholakia, Y. Goland, et al., BPELWS – Business Process Execution Language for Web Services, BEA
Systems, International Business Machines Corporation, Microsoft Corporation, SAP AG, Siebel Systems, 2003.
[17] S. Rinderle, M. Reichert, P. Dadam, On dealing with structural conflicts between process type and instance changes, in: BPM ’04,
2004, pp. 274–289.
[18] M. Reichert, P. Dadam, ADEPT
flex
– supporting dynamic changes of workflows without losing control, JIIS 10 (2) (1998) 93–129.
[19] M. Reichert, Dynamic Changes in Workflow-Management-Systems, Ph.D. Thesis, University of Ulm, Computer Science Faculty,
2000 (in German).
[20] J. Klein, Advanced rule driven transaction management, in: Proceedings of IEEE COMPCON ’93, 1991, pp. 562–567.
[21] P. Attie, M. Singh, A. Sheth, M. Rusinkiewicz, Specifying and enforcing intertask dependencies, in: Proceedings of the VLDB ’93,
Morgan Kaufmann Publishers Inc., 1993, pp. 134–145.
[22] M.P. Singh, Semantical considerations on workflows: an algebra for intertask dependencies, in: Workshop on Database Programming
Languages, Springer-Verlag, London, UK, 1996, p. 5.
[23] C. Heinlein, Workflow and process synchronisation with interaction expressions and graphs, in: ICDE ’01, IEEE Computer Society,
Washington, DC, USA, 2001, pp. 243–252.
[24] M. Pesic, W. van der Aalst, A declarative approach for flexible business processes management, in: Business Process Management
Workshops, 2006, pp. 169–180.
[25] H. Davulcu, M. Kifer, C.R. Ramakrishnan, I.V. Ramakrishnan, Logic based modeling and analysis of workflows, in: PODS, 1998,
pp. 25–33.
[26] W. Fan, S. Weinstein, Specifying and reasoning about workflows with path constraints, in: ICSC, 1999, pp. 226–235.
[27] P. Dourish, J. Holmes, A. MacLean, P. Marqvardsen, A. Zbyslaw, Freeflow: mediating between representation and action in
workflow systems, in: CSCW ’96, ACM Press, New York, NY, USA, 1996, pp. 190–198.
[28] G. Knolmayer, R. Endl, M. Pfahrer, Modeling processes and workflows by business rules, in: W. van der Aalst et al. (Eds.), BPM
’00, LNCS, vol. 1806, Springer, 2000, pp. 16–29.
[29] J. Wainer, F. de Lima Bezerra, P. Barthelmess, Tucupi: a flexible workflow system based on overridable constraints, in: ACM SAC
’04, 2004, pp. 498–502.
[30] M. Weske, Flexible modeling and execution of workflow activities, in: Proceedings of the Hawaii International Conference on System
Sciences, Hawaii, 1998, pp. 713–722.
[31] W. van der Aalst, T. Basten, H. Verbeek, P. Verkoulen, M. Voorhoeve, Adaptive workflow: on the interplay between flexibility and
support, Interprise Inform. Syst. (2000) 63–70.
[32] S. Sadiq, M. Orlowska, W. Sadiq, Specification and validation of process constraints for flexible workflows, Inf. Syst. 30 (5) (2005)
349–378.
[33] S. Deng, Z. Yu, Z. Wu, H. Lican, Enhancement of workflow flexibility by composing activities at run-time, in: ACM SAC ’04, 2004,
pp. 667–673.
[34] U. Greiner, J. Ramsch, B. Heller, M. Lo
¨ffler, R. Mu
¨ller, E. Rahm, Adaptive guideline-based treatment workflows with AdaptFlow,
in: CGP ’04, 2004, pp. 113–117.
[35] R. Mu
¨ller, U. Greiner, E. Rahm, AgentWork: a workflow system supporting rule-based workflow adaption, DKE 51 (2004) 223–256.
[36] J. Pathak, D. Caragea, V. Honovar, Ontology-extended component-based workflows: a framework for constructing complex
workflows from semantically heterogeneous software components, in: SWDB ’04, 2005, pp. 41–56.
[37] S. Bowers, K. Lin, B. Luda
¨scher, On integrating scientific resources through semantic registration, in: SSDBM ’04, IEEE Computer
Society, Washington, DC, USA, 2004, p. 349.
22 L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23
Author's personal copy
[38] J. Kim, M. Spraragen, Y. Gil, An intelligent assistant for interactive workflow composition, in: International Conference on
Intelligent User Interfaces, ACM Press, 2004, pp. 125–131.
[39] J. Cardoso, A. Sheth, Semantic e-workflow composition, JIIS 21 (3) (2003) 191–225.
[40] R. Zhang, I. Budak Arpinar, B. Aleman-Meza, Automatic composition of semantic web services, in: International Conference on
Web Services, 2003, pp. 38–41.
[41] ILOG, ILOG JRules and IBM MQWF – White Paper, 2005.
[42] A. Abecker, A. Bernardi, S. Ntioudis, L. van Elst, R. Herterich, C. Houy, M. Legal, G. Mentzas, S. Mu
¨ller, Workflow-embedded
organizational memory access: the DECOR project, in: IJCAI ’01, Workshop on Knowledge Management and Organizational
Memories, 2001.
[43] C. Wargitsch, T. Wewers, F. Theisinger, An organizational-memory-based approach for an evolutionary workflow management
system – concepts and implementation, in: HICSS (1), 1998, pp. 174–183.
[44] W. van der Aalst, H. de Beer, B.van Dongen, Process mining and verification of properties: an approach based on temporal logic, in:
CoopIS ’05, 2005, pp. 130–147.
Linh Thao Ly studied Computer Science at the University of Ulm (Germany). At present she is a Ph.D. candidate
of the Institute of Databases and Information Systems of the University of Ulm. Her research interests include
adaptive process management systems and integration and verification of semantic constraints in process man-
agement systems.
Stefanie Rinderle obtained her Ph.D. in Computer Science at the Institute of Databases and Information Systems,
University of Ulm (Germany) where she is currently teaching and working on her habilitation. During her
postdoc Stefanie stayed at the University of Twente (The Netherlands), the University of Ottawa (Canada), and
the Technical University of Eindhoven (The Netherlands) where she worked on several projects on process
visualization and modeling as well as on process mining. Her research interests include adaptive process man-
agement systems, integration of application knowledge, and the controlled evolution of organizational structures
and access rules.
Peter Dadam has been full professor at the University of Ulm and director of the Institute of Databases and
Information Systems since 1990. Before he came to the University he had been director of the research department
for Advanced Information Management (AIM) at the IBM Heidelberg Science Center (HDSC). At the HDSC he
managed the AIM-P project on advanced database technology and applications. Current researach areas include
distributed, cooperative information systems, workflow management, and database technology and its use in
advanced application areas.
L.T. Ly et al. / Data & Knowledge Engineering 64 (2008) 3–23 23
