Workflow and Process Synchronization with Interaction Expressions and Graphs [original]

Workflow and Process Synchronization with Interaction Expressions and Graphs

Christian Heinlein

Department of Databases and Information Systems, University of Ulm, Germany

[email protected]

Abstract

Current workflow management technology does not pro-

vide adequate means for

inter-workflow coordination

concurrently executing workflows are considered com-

pletely independent. While this simplified view might suf-

fice for one application domain or the other, there are

many real-world application scenarios where workflows −−

though independently modeled in order to remain com-

prehensible and manageable −− are semantically interrelat-

ed. As pragmatical approaches, like merging interdepen-

dent workflows or inter-workflow message passing, do

not satisfactorily solve the inter-workflow coordination

problem,

interaction expressions and graphs

are proposed

as a simple yet powerful formalism for the specification

and implementation of synchronization conditions in gen-

eral and inter-workflow dependencies in particular. In ad-

dition to a graph-based semi-formal interpretation of the

formalism, a precise formal semantics, an equivalent op-

erational semantics, an efficient implementation of the lat-

ter, and detailed complexity analyses have been developed

allowing the formalism to be actually applied to solve re-

al-world problems like inter-workflow coordination.

1. Introduction

Inter-workflow dependencies

Current workflow management systems (WfMS), whether

commercial products or research prototypes, do not pro-

vide adequate means for inter-workflow coordination as

concurrently executing workflows are considered com-

pletely independent. While this simplified view might suf-

fice for one application domain or the other, there are

many real-world application scenarios where workflows −−

though independently modeled in order to remain com-

prehensible and manageable −− are semantically interrelat-

ed. As a simple example from the domain of medicine,

consider the examination workflows depicted in Fig. 1 de-

scribing the performance of an ultrasonography (left) and

an endoscopy (right) including necessary pre- and post-

processing steps like scheduling, report writing, etc. As

long as these workflows refer to different patients, they

might well be executed independently by a WfMS. If the

1Author’s new address: Department of Computer Structures, University

of Ulm, Germany.

same patient is involved, however, the activities

prepare

inform

call

, and

perform

must be synchronized somehow

as they access a “limited resource,” that is, the patient un-

der consideration. If for example, the activities

order

schedule

prepare

, and

inform

(if present) of both work-

flows have already been performed, the activities

call

are

to be executed next, i. e., they will be inserted into the

worklists of appropriate users −− e. g., medical assistants

of the ultrasonography and endoscopy departments,

respectively −− by the WfMS. As soon as one of these ac-

tivities is actually executed, however, the other one should

temporarily disappear from the worklists −− or at least be-

come marked as currently not executable −− as a patient

cannot be called to a second examination as long as he

passes through the first one. Only after completion of the

first examination (activity

perform

of the corresponding

workflow), activity

call

of the other workflow should be-

come executable again, i. e., reappear in the appropriate

worklists.

Impracticable approaches

As current WfMSs neither provide adequate means to de-

scribe nor to implement such inter-workflow dependen-

cies, one might resort to rather pragmatical approaches

like merging interdependent workflows into a single

workflow to transform inter-workflow dependencies to

ordinary intra-workflow control flows. As soon as not on-

ly two, but maybe fiv e, ten or twenty interrelated work-

flows have to be merged, however, the resulting work-

flows will reach magnitudes which are no longer compre-

hensible nor manageable in practice. Furthermore, a host

of 2nmerged workflows would be necessary to capture

ev ery possible combination of noriginal workflows. Fi-

nally, typical intra-workflow control structures, like se-

quence, conditional and parallel branching, and possibly

loop, would force a workflow designer to prescribe a par-

ticular ordering of the examinations ultrasonography and

endoscopy (more precisely, of the activities

call

and

per-

form

of the corresponding workflows) in the example

above as these imperative language constructs do not al-

low to describe a sequential execution in either order. For

these reasons, the idea to simply “define away” in-

ter-workflow dependencies by translating them to well-

known intra-workflow control flows has to be abandoned.

2For the sake of simplicity, only the verb of an activity (e. g.,

prepare

in-

stead of

prepare patient

) is used throughout the following text.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

order examination

schedule examination

prepare patient

call patient

perform examination

write report

read report

ultrasonography

order examination

schedule examination

inform patient prepare patient

call patient

perform examination

write short report

read short report

write detailed report

read detailed report

endoscopy

Figure 1: Medical examination workflows

Another apparently attractive idea uses inter-workflow

messaging or event services provided by some WfMSs to

explicitly synchronize concurrently executing workflows.

As this approach retains the structure of the original

workflows, it avoids the creation of unmanageable “mega-

workflows.” Howev er, it does not solve the “combination-

al explosion” problem as the set of messages a particular

workflow must send and receive usually depends on the

fact which other workflows are executed concurrently.

Therefore, 2nvariations of each workflow would be nec-

essary in principle to describe its behaviour in every pos-

sible combination with nother workflows. Similarly, the

“mutual exclusion” problem, i. e., describing that the ex-

aminations can be performed in either order, cannot be

solved with this approach as inter-workflow messages

cannot be used to temporarily disable activities which

have already been enabled by the WfMS. Therefore, the

idea of reducing inter-workflow dependencies to bare

message passing has likewise to be abandoned.

A common problem of both approaches not mentioned

so far is their fundamental inability to deal with dynamic

workflow ensembles where the number and the actual par-

ticipants of a set of concurrently executing workflows is

not known in advance and might change with time. As

currently executing workflows might always terminate

and additional workflows can be initiated by a user at any

time, however, dynamically evolving ensembles are actu-

ally the normal case and must thus be supported accord-

ingly.

Extended regular expression formalisms

In order to find a satisfactory solution to the inter-work-

flow coordination problem at all, it is absolutely neces-

sary to strictly separate inter-workflow synchronization

aspects from individual workflow descriptions and to use

an extremely flexible and declarative formalism for their

specification. In some sense, this means to reapply a basic

principle of workflow management, that is, the separation

of the overall control and data flow specification of a

workflow from the implementation of individual applica-

tion modules, one level higher: Inter-workflow synchro-

nization aspects are extracted from individual workflows

and described on a separate level using a tailored and

well-suited formalism.

In the past, similar approaches have been proposed and

successfully used for the synchronization of parallel pro-

grams [1, 5, 19]. Instead of directly encoding synchro-

nization conditions using, e. g., semaphor or message

passing operations in individual procedure implementa-

tions, an abstract formalism based on extended regular ex-

pressions is used to describe them separately in a com-

pact, legible and easily adaptable manner. The basic idea

with these formalisms is to interpret the language of an

expression, i. e., the set of words it accepts, as set of per-

missible execution sequences of actions where actions

correspond to the start or termination of individual proce-

dures or −− when applied to the problem of inter-workflow

dependencies −− workflow activities. By that means, it is

indeed possible to specify synchronization conditions in a

very flexible and declarative way that avoids the problems

mentioned before. Furthermore, as such expressions con-

stitute general integrity constraints on actions which do

not depend on their specific use in individual workflows,

the cardinality nas well as the actual members of a set of

concurrently executing workflows are irrelevant.

Despite the fact that many similar formalisms have

been proposed over the years (cf. Fig. 2), each of them

lacks one important aspect or the other. By carefully

analysing the overall spectrum of operators provided by

these formalisms, one can identify three pairs of comple-

mentary or dual operators: There are two basic composi-

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

regular

expressions

CoCoA

execution rules

[4]

path

expressions

[1]

synchronization

expressions

[5]

ev ent and flow

expressions

[16, 17]

???

parameters

quantifiers

conjunction

parallel

composition

parallel

iteration

parallel

iteration

parallel

composition

conjunction

quantifiers

parameters

Figure 2: Formalisms based on extended regular expressions

tion operators, sequential and parallel composition,two

corresponding closure operators, sequential and parallel

iteration, and two Boolean operators, disjunction and

conjunction.3Furthermore, the concept of parametric ex-

pressions and quantifiers can be found in a very restricted

form in some approaches. Besides the fact, that none of

the formalisms proposed so far is conceptually compre-

hensive or complete with respect to the others, most of

them do not allow operators to be arbitrarily combined,

but impose considerable restrictions on their nesting. In

path expressions, for example, the parallel iteration opera-

tor must not contain other parallel iterations, while

operands of a parallel composition in synchronization ex-

pressions must have disjoint alphabets.

Interaction expressions and graphs

This lack of orthogonality on the one hand and the con-

ceptual incompleteness of the formalisms on the other

hand calls for the development of a new formalism to de-

scribe synchronization requirements which is at least con-

ceptually complete and fully orthogonal and thus can fill

the hole depicted by the question marks in Fig. 2. Despite

its conceptual completeness, such a formalism should also

be flexibly extensible with user-defined operators in order

to be optimally useful in different application domains.

Furthermore, it should be readily comprehensible even for

mathematically ignorant persons, which suggests the use

of a graphical representation instead of or in addition to a

formal notation. Last but not least, the proposed formal-

ism must be efficiently implementable in order to be prac-

tically useful, and the implementation should be −− in con-

trast to, e. g., Petri nets and process algebras −− completely

deterministic.

In order to meet these requirements, interaction ex-

pressions and graphs have been developed in the author’s

Ph. D. thesis [6, 7] as a simple yet powerful formalism for

the expression- or graph-based specification and imple-

mentation of inter-action dependencies, i. e., synchroniza-

tion conditions. Interaction graphs, which constitute the

graphical, user-oriented view of the formalism, are intro-

3Note that regular expressions provide just the first operator of each

pair: sequential composition (sequence), sequential iteration (Kleene

closure), and disjunction (choice).

duced in Sec. 2, while interaction expressions, their for-

mal counterpart, are treated in Sec. 3. Sections 4, 5, and 6

dealing with the operational semantics, implementation,

and complexity of interaction expressions, respectively,

pave the way for their practical application which is illus-

trated in Sec. 7 by describing their integration with work-

flow management systems. Finally, Sec. 8 concludes the

paper.

2. Interaction graphs

In the following, the basic ideas and concepts of interac-

tion graphs will be introduced by presenting some typical

examples of synchronization conditions taken from the

domain of medical examination workflows. To sav e space

for the more technical aspects of the formalism presented

in subsequent sections, operators are not defined verbose-

ly but rather explained on the fly without going into de-

tails.

As a first example, Fig. 3 shows an interaction graph

specifying a generic integrity constraint for patients by

describing necessary synchronization requirements for the

activities

prepare

inform

call

, and

perform

. As all these

activities refer to a particular patient pas well as a partic-

ular examination x, they possess corresponding parame-

ters pand xcontaining, for example, a social security

number identifying a patient and a symbolic value like

sono

endo

representing an examination, respectively.4

The ellipses containing flash symbols, which −− in contrast

to the predefined circular operators −− constitute a user-de-

fined operator, represent a mutual exclusion describing

that a patient pmight either pass through exactly one ex-

amination x(middle branch) or be prepared for or in-

formed about several examinations xsimultaneously (up-

per and lower branch, respectively). The “for some x”

quantifiers x

...

xspecify that their body, i. e., the sub-

graph in between, must be traversed for exactly one arbi-

trarily chosen value of the parameter x, while the body of

the “for all p” quantifier p

...

pmight be traversed con-

currently and independently for all possible values of the

4In the workflows of Fig. 1, these parameters have been omitted for the

sake of simplicity. They might be considered global workflow variables

which are implicitly passed to all activities of a workflow.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

prepare

patient

p,x

call

patient

p,x

perform

examination

p,x

inform

patient

p,x

p p

Figure 3: Integrity constraint for patients

parameter p. Thus, these operators constitute generaliza-

tions of the basic “either or” (disjunction) and “as well as”

(parallel composition) branchings, respectively, depicted

in Fig. 4. Finally, the “arbitrarily parallel” operators

... allow an arbitrary number of concurrent and in-

dependent traverses of their body.5

Figure 4: Basic branching operators:

“either or” (left) and “as well as” (right)

User-defined operators

To complete the example above, Fig. 5 shows a possible

definition of the mutual exclusion operator “flash” as a

constant repetition (sequential iteration) of an “either or”

branching containing the mutual exclusive branches x,y,

and z.6Employing such kinds of templates does not only

simplify the graphs containing them, but also increases

their level of abstraction as a user of the “flash” operator

does not need to know its precise definition but only its

abstract meaning. Therefore, frequently occurring or fair-

ly complicated application-specific operators might be

predefined by an “interaction graph expert” and applied

afterwards even by inexperienced users.

Modular combination of graphs

Figure 6 shows another example of an interaction graph

specifying a generic capacity restriction for examination

departments by describing that for each kind of examina-

5As a mnemonic aid, a single circle (whether small or large) expresses

that one branch must be chosen, while a double circle requires both or

all branches to be traversed. Finally, three circles represent an arbitrary

number of parallel traverses.

6It is also possible to give a more general definition where the number

of branches is variable.

tion x(quantifier x

...

x) three concurrent and indepen-

dent instances (multiplier

3... 3

) of the sequence

call

−−

perform

might be executed repeatedly (sequential itera-

tion ... ). Each of these sequences might be traversed

with an arbitrary patient p(quantifier p

...

p). This

means effectively, that each examination department x

can treat at most three patients psimultaneously.

Having specified separate synchronization conditions

for patients (Fig. 3) and examination departments (Fig. 6),

a coupling operator is employed to combine these inde-

pendently developed subgraphs into a single interaction

graph representing their semantic conjunction (cf. Fig. 7).

More precisely, the combined graph permits the execution

of a particular activity if and only if it is permitted by all

subgraphs containing this activity. Applied to the graph

of Fig. 7 this means that the execution of

call

and

perform

is permitted if and only if it is permitted by both branches

of the coupling operator ... , while

prepare

and

inform

are permitted as soon as they are permitted by the upper

branch. In contrast to a strict conjunction operator (denot-

ed ... ) which permits execution of an activity if and

only if it is permitted by all its branches, the more loosely

coupling employed in Fig. 7 is usually much more intuiti-

ve and useful in practice as a subgraph should not prohibit

the execution of activities which it does not explicitly

mention. This kind of open-world assumption −− there

might be activities which are either unknown or irrelevant

at the time a graph is developed −− supports a modular de-

velopment of small interaction graphs describing particu-

lar aspects or facets of a synchronization condition and

their seamless integration into larger graphs afterwards. In

contrast, formalisms providing strict conjunction only [5]

or no explicit conjunction operator at all [16, 17] force

graph developers to augment the individually developed

subgraphs with auxiliary branches or special synchroniza-

tion symbols before combining them into larger graphs

[7].

3. Interaction expressions

Having introduced interaction graphs in a rather informal

and descriptive manner so far, interaction expressions will

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

Figure 5: Definition of the mutual exclusion operator

call

patient

p,x

perform

examination

p,x

x x

Figure 6: Capacity restriction for examination departments

prepare

patient

p,x

call

patient

p,x

perform

examination

p,x

inform

patient

p,x

p p

call

patient

p,x

perform

examination

p,x

x x

Figure 7: Coupling of independently developed subgraphs

be defined in the following as an equivalent formal nota-

tion with a precisely specified semantics. Expressed the

other way round, interaction graphs are merely a graphi-

cal notation of interaction expressions, just like syntax

charts constitute a graphical representation of context-free

grammars.

To formally define the semantics of an interaction ex-

pression x,twolanguages called Φ(x)and Ψ(x)are intro-

duced containing the complete and partial words of x,

respectively.7Intuitively, a complete word w∈Φ

(x)con-

stitutes a sequence of actions which is derived by com-

7As another mnemonic aid, Φ(pronounced fi) contains “final” or com-

plete words, whereas Ψ(psi) contains partial words.

pletely traversing the corresponding interaction graph

from left to right according to particular rules and record-

ing the visited actions.8Similarly, a partial word

w∈Ψ

(x)is obtained by partially traversing the graph,

i. e., prematurely terminating the traverse. As it is possible

−− typically by inappropriate uses of the coupling

operator −− to construct graphs with “dead ends” (i. e.,

8The rectangular nodes of an interaction graph represent so called activ-

ities possessing a positive duration in time. In contrast, actions corre-

spond to points in time without any duration. As the exact duration of an

activity Ais irrelevant, it is implicitly mapped to a sequence of two ac-

tions, ASand AT, representing the start and termination of A, respec-

tively.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

graphs possessing partial but not complete words), partial

words cannot be simply derived as prefixes of complete

words but have to be defined separately.

Table 1 summarizes the definition of interaction ex-

pressions x(first and second column) where yand zcon-

stitute recursively defined subexpressions. Furthermore, a

represents an abstract action

a∈Γ=

{[

a0,a1,...,an

]



n∈IN0,a0∈Λ,a1,...,an∈Ω ∪ Π

}

consisting of an action name a0∈Λand zero or more ar-

guments a1,...,an∈Ω ∪ Π which are either concrete

values

∈Ωor formal parameters p ∈Π. Here, Λ,Ω,

and Πdenote arbitrary sets of names, values, and parame-

ters, respectively, for which the conditions Ω∩Π=∅

and Ω=∞shall hold. Furthermore, for each expres-

sion x, Tab. 1 defines its set of complete and partial words

(third and fourth column, respectively) where brackets

〈...〉are used to denote abstract words ∈Γ* and Σrepre-

sents the set of concrete actions,

Σ=

{[

a0,a1,...,an

]



n∈IN0,a0∈Λ,a1,...,an∈Ω

}

whose arguments aiare all concrete values. Consequently,

aconcrete word w ∈Σ* corresponds to a sequence of

concrete actions executed in the real world.

The concatenation (UV) and Kleene closure (U*) of

languages U,V⊆Σ* is defined as usual, whereas the

shuffle of words u,v∈Σ* and languages U,V⊆Σ*as

well as the corresponding closure is defined as follows

[17, 5]:9

u⊗v=

{

u1v1...unvn

n∈IN, u1,v1,...,un,vn∈Σ*,

u1...un=u,v1...vn=v

}

U⊗V=u∈U,v∈V

∪u⊗v

{

w∈Σ*∃u∈U,v∈V:w∈u⊗v

}

i=1

⊗Ui=











{

〈〉

}

(

n−1

i=1

⊗Ui

)

⊗Un

for n=0,

for n>0,

U#= ∞

n=0

∪n

i=1

⊗U=

u1,...,un∈U

n∈IN0

∪u1⊗...⊗un.

For an expression y, a parameter p∈Π, and a value

∈Ω,y

pdenotes the expression derived from yby re-

placing every occurrence of the parameter pwith the

value

. Infinite unions and intersections are defined as

usual, whereas the shuffle of infinitely many languages

∈Σ*(

∈Ω) is either empty or can be reduced to a

union of finite shuffles if all participants U

contain the

empty word [7]:

9Note that, in the first definition, uiand vido not represent actions ∈Σ,

but subwords ∈Σ* consisting of zero or more actions.

∈Ω

⊗U











1≠...≠

n∈Ω

n∈IN

∪n

i=1

⊗U

∅

if 〈〉 ∈U

otherwise.

for all

∈Ω,

Finally, Tab. 1 defines the alphabet

(x)of expressions x

(last column) which is needed for the definition of the al-

phabet complement

x(y)=

(x)\

(y). Unfortunately,

space does not permit a more detailed motivation and ex-

planation of the definitions given in this section.

Based on the definitions of Tab. 1, two interaction ex-

pressions x1and x2are considered equal or equivalent,if

they possess the same alphabet and accept the same com-

plete and partial words.10 Given this equivalence relation,

numerous useful properties of interaction expressions,

like commutativity, associativity, or idempotence of oper-

ators, which are intuitively evident, can be formally

proven [7].

Furthermore, interaction expressions can be compared

with well-known formalisms like regular expressions and

context-free grammars regarding their expressiveness.

While it is obvious that interaction expressions are more

expressive than regular expressions, their relation to

context-free grammars is not yet exactly determined.

On the one hand, there are expressions, e. g.,

x=(a−b−c)(

a−b−c), whose language,

Φ(x)=

{

〈an,bn,cn〉 n∈IN0

}

, is not context-free. On

the other hand, there are context-free grammars specify-

ing, e. g., palindromes, whose language is presumably not

expressible with interaction expressions as they −−

deliberately −− do not allow recursive expressions. As

these questions are of little relevance for practical applica-

tions of interaction expressions, they hav e not been inves-

tigated in more detail.

4. Operational semantics of interaction

expressions

Given the formal semantics of interaction expressions, it

is possible in principle to construct an algorithm solving

the word problem −− giv en an interaction expression xand

a concrete word w, decide whether wis a partial or com-

plete word of x−− by more or less directly transforming

the definitions of Ψ(x)and Φ(x)into executable code.

The problem with this algorithm is, however, that it is

hopelessly inefficient as its complexity grows exponen-

tially with respect to the length of the word wev en for

very simple expressions x[18, 7]. In order to obtain a

more efficient and practically useful implementation of

interaction expressions, it is thus necessary to introduce

an operational state model comparable in some sense to

finite state machines (FSM) typically used for the imple-

mentation of regular expressions.

10 More precisely, as x1and x2might contain unbound parameters, every

pair of concretizations (x1)

1,...,

p1,..., pkand (x2)

1,...,

p1,..., pk(for arbitrary pa-

rameters p1,..., pk∈Π and values

1,...,

k∈Ω) must accept the

same complete and partial words.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

Table 1: Formal semantics of interaction expressions

Category xΦ(x)Ψ(x)

(x)

atomic expression a

{

〈a〉

}

∩Σ*

{

〈〉,〈a〉

}

∩Σ*

{

}

option yΦ(y)∪

{

〈〉

}

Ψ(y)

(y)

sequential composition y−zΦ(y)Φ(z)Ψ(y)∪Φ

(y)Ψ(z)

(y)∪

(z)

sequential iteration yΦ(y)*Φ(y)*Ψ(y)

(y)

parallel composition yzΦ(y)⊗Φ

(z)Ψ(y)⊗Ψ

(z)

(y)∪

(z)

parallel iteration yΦ(y)#Ψ(y)#

(y)

disjunction yzΦ(y)∪Φ

(z)Ψ(y)∪Ψ

(z)

(y)∪

(z)

conjunction yzΦ(y)∩Φ

(z)Ψ(y)∩Ψ

(z)

(y)∪

(z)

Φ(y)⊗

x(y)*∩Ψ

(y)⊗

x(y)*∩

Φ(z)⊗

x(z)*Ψ(z)⊗

x(z)*

synchronization yz

(y)∪

(z)

disjunction quantifier py

∈Ω

∪Φ

(

)

∈Ω

∪Ψ

(

)

∈Ω

∪

(

)

parallel quantifier py

∈Ω

⊗Φ

(

)

∈Ω

⊗Ψ

(

)

∈Ω

∪

(

)

synchr. quantifier py

∈Ω

∩Φ

(

)

⊗

(

)

∈Ω

∩Ψ

(

)

⊗

(

)

∈Ω

∪

(

)

conjunction quantifier py

∈Ω

∩Φ

(

)

∈Ω

∩Ψ

(

)

∈Ω

∪

(

)

For that purpose, every interaction expression xis as-

signed an initial state

(x)where a state −− in contrast to

FSMs −− might be a complex, hierarchically structured

mathematical object. Furthermore, a state transition

function

is defined which maps a state sand an action a

to a successor state s′=

a(s). Finally, two state predi-

cates,

(s)and

(s), are introduced which correspond di-

rectly to the sets Ψ(x)and Φ(x)of the formal semantics

(cf. below). The nature of these definitions allows them to

be transformed to executable program code quite directly.

To further improve the efficiency of the so constructed

implementation, an equivalence relation is introduced for

states based on the predicates

and

and an optimiza-

tion function

is defined which maps some states sto

equivalent, but less complex states ˆs=

(s)which can be

processed more efficiently.

Intuitively, the state model formalizes the descriptive

idea of traversing an interaction graph. That means, the

initial state

(x)of an expression xdescribes the starting

position of a walker (or a group of walkers) who wants to

walk through the corresponding interaction graph, while a

state transition

a(s)represents the traverse of an ac-

tion a. A successor state

w(x), derived from the initial

state

(x)by applying a sequence of state transitions cor-

responding to a word w, describes the set of all possible

positions the walker(s) might have reached after travers-

ing the sequence of actions w. Such a state is said to be

valid, which is equivalent to its predicate

being true, if

the sequence wis permissible, i. e., constitutes a partial

word of x. It is called a final state, which is equivalent to

its predicate

being true, if the walker(s) might have

reached the end of the graph after traversing the actions

of w.

To actually guarantee the correctness of the state mod-

el with respect to the formal semantics of interaction ex-

pressions, the following equivalences must hold for every

word w∈Σ*:

w∈Ψ

(x)⇔

(

w(x)) = true,

w∈Φ

(x)⇔

(

w(x)) = true.

The corresponding proof constitutes a very large struc-

tural induction using several smaller computational induc-

tions (verifying properties of the states

w(x)for the dif-

ferent categories of expressions x) as lemmas. Further-

more, an auxiliary theorem must be proven in parallel to

make sure that quantifier expressions, though constituting

conceptually infinite expressions, can nevertheless be im-

plemented using states of final size [7].

5. Implementation of interaction expressions

As already mentioned in Sec. 4, the nature of the defini-

tions of the functions

, and

allows them to be

transformed to executable program code quite directly. It

turns out, however, that the state predicate

is dispens-

able if invalid states are already recognized by the opti-

mization function

and mapped to a special null state.

Furthermore, as the state transition function

and the op-

timization function

are always applied successively, it

makes sense to combine them into a single optimized

state transition function ˆ

a(s)=

(

a(s)). The remaining

functions,

(x),ˆ

a(s), and

(s), can be readily imple-

mented using any suitable programming language.

Assuming corresponding functions

init()

trans()

and

final()

in C++, it is easily possible to implement

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

functions

word()

and

action()

solving the following

problems (cf. Fig. 8):

// Return initial state of expression x.

State init(Expr x);

// Perform an optimized state transition

// of state s with action a.

State trans(State s, Action a);

// Determine whether s is a final state.

bool final(State s);

// Solve the word problem for expr. x.

int word(Expr x, Action* w, int n) {

State s = init(x);

for (int i = 0; i < n; i++) {

s = trans(s, w[i]);

}

if (final(s)) return 2; // Complete,

else if (s) return 1; // partial,

else return 0; // or illegal word.

}

// Solve the action problem for expr. x.

void action(Expr x) {

State s = init(x);

while (true) {

Action a = ReadNextAction();

if (State t = trans(s, a)) {

printf("Accept.\n"); s = t;

}

else printf("Reject.\n");

}

Figure 8: Solution of the

word and action problems

1. The function

word()

solves the word problem, i. e., it

decides whether a sequence

actions is a com-

plete, partial, or illegal word of an interaction expres-

sion

and returns a corresponding integer value. For

that purpose, the initial state

is computed (func-

tion

init()

) and successively transformed using the

actions

w[i]

(function

trans()

). If the resulting

state

is a final state (function

final()

consti-

tutes a complete word of

; otherwise, if

is valid

(i. e., different from the null state),

is a partial word

; otherwise,

is illegal.

2. The function

action()

solves the so called action

problem. After computing the initial state

of the ex-

pression

, it successively reads actions

(function

ReadNextAction()

) and decides whether each such

action is currently permissible. For that purpose, a

“tentative” state transition is performed to check

whether the successor state

is valid. If it is,

is ac-

cepted and the state transition is actually performed by

replacing the current state

with the successor state

Otherwise,

is rejected and the current state

remains

unchanged.

As will be explained in Sec. 7, solving the action problem

is highly relevant for practical applications of interaction

expressions, while the solution of the word problem is

more or less a by-product of primarily theoretical interest.

6. Complexity of interaction expressions

Despite the fact that statements about the computational

complexity of interaction expressions are highly relevant

for practical applications, space does not permit to treat

this topic in much detail. Nevertheless, the main results

providing the basis for a successful practical employment

shall be briefly presented.

Generally, there is good news and bad news about the

complexity of interaction expressions. The bad news is, it

is possible to construct “malignant” expressions, i. e., ex-

pressions for which the complexity of a state transition (in

the current implementation) grows exponentially with re-

spect to the length of the action sequence processed so far.

The good news is, those expressions do not seem to occur

in practical applications. In order to substantiate this ad-

mittedly vague statement, extensive and detailed analyses

about the growth and evolution of states of expressions

have been carried out. These studies revealed several use-

ful subclasses of interaction expressions, e. g., qua-

si-regular expressions, completely and uniformly quanti-

fied expressions, etc., for which detailed criteria for their

“benignity” have been elaborated. For example, it can be

shown that quasi-regular expressions (i. e., expressions

not containing parallel iterations or quantifiers) are

“harmless” (the complexity of a state transition remains

constant) and that completely and uniformly quantified

expressions (which constitute the normal case of quanti-

fied expressions in practice) are “benign” (the complexity

of a state transition grows polynomially with respect to

the length of the action sequence processed so far). Fur-

thermore, these propositions can be used in combination

to evaluate step by step that a given expression is benign.

To put it in a nutshell, all practical examples consid-

ered so far −− including those presented in this paper −−

have been formally proven benign using the complexity

propositions developed in [7]. Furthermore, the actual de-

gree of the polynomial growth is rarely greater than 1

or 2. It turned out, that the careful selection of the opti-

mization function

(cf. Sec. 4) plays a crucial role in that

context as some of these expressions would indeed behave

malignant without optimization.

On the other hand, malignant expressions −− including

a suitable word for which they actually behave

malignant −− hav e to be selectively constructed and do not

seem to have any practical relevance.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

7. Integration with workflow management

systems

Having designed interaction expressions and graphs

(Sec. 2), defined their formal semantics (Sec. 3), devel-

oped, verified, and implemented an equivalent operational

semantics (Secs. 4 and 5), and finally proved its efficiency

for practically relevant expressions (Sec. 6), the question

remains how interaction expressions and graphs can actu-

ally be employed to synchronize the execution of real-

world activities. Assuming that these activities will be ex-

ecuted by some kind of interaction clients (typically

workflow management systems), a central scheduler or

interaction manager and a suitable coordination protocol

is needed to monitor and control the execution of actions

(cf. Fig. 9, left side).

To make sure that a client does not execute an action

which is currently not permitted by the given interaction

graph, the client has to ask the interaction manager for

permission first (step 1). Depending on the current state of

the graph, the interaction manager replies either yes or no

(step 2). If a positive answer is received, the client actual-

ly executes the respective action (step 3) and confirms its

execution (step 4) causing the interaction manager to per-

form a corresponding state transition of the graph

(step 5). Otherwise, the client must refrain from executing

the action now and try again later.

In order to avoid busy waiting in that case causing un-

necessary communication and interaction manager work-

load, a client can subscribe to a particular action (step 1,

right side of Fig. 9) causing the interaction manager to in-

form him about every status change of the respective ac-

tion (step 2), i. e., the client receives informational mes-

sages whenever the status of a subscribed action changes

from permissible to non-permissible or vice versa. These

messages can be used on the one hand to keep users’

worklists up to date (step 3) and on the other hand to wait

passively for the right moment to ask again for permission

to execute an action. Finally, if a client is no longer inter-

ested in the status of an action, a corresponding cancel

message (step 4) tells the interaction manager to stop

sending informations about this action.

In [7], these coordination and subscription protocols as

well as several alternative protocols, possessing different

complexity and particular advantages and disadvantages,

are discussed in more detail. Furthermore, to avoid the in-

teraction manager to become a bottleneck in a large sys-

tem, the protocols are generalized to application scenarios

involving multiple interaction managers. Finally, the em-

ployment of persistent message queues for the communi-

cation between interaction managers and clients as well as

recovery strategies for interaction managers are described.

8. Conclusion

Interaction expressions and graphs constitute a flexible

and expressive formalism for the specification and imple-

mentation of synchronization conditions in general and

inter-workflow dependencies in particular. In addition to a

declarative semi-formal interpretation (traversing interac-

tion graphs), a precise formal semantics, an equivalent op-

erational semantics, an efficient implementation of the lat-

ter, and detailed complexity analyses have been developed

allowing the formalism to be actually applied to solve re-

al-world problems like inter-workflow coordination.

Compared to approaches like workflow merging or in-

ter-workflow message passing, the employment of inter-

action graphs leads to a clean separation of synchroniza-

tion conditions and individual workflow definitions. Fur-

thermore, it supports the specification of general integrity

constraints on activities which are independent of their ac-

tual use in particular workflows. In contrast to other for-

malisms based on extended regular expressions, interac-

tion expressions are conceptually comprehensive and

completely orthogonal. Compared to other well-known

approaches for the specification of concurrent systems,

especially Petri nets [15, 11] and various kinds of process

algebras [8, 9, 14], their behaviour is fully deterministic,

ev en though this heavily complicates their operational se-

mantics and implementation [7].

Despite the fact that inter-workflow dependencies oc-

cur frequently in practical applications, they hav e not re-

ceived much attention in the workflow community yet.

Neither special issues of journals devoted to the overall

topic of workflow management [21−−25] nor books re-

flecting the state of the art in that field [20, 10] have really

addressed the problem so far. The same holds for confer-

ence and workshop proceedings in general where the

number of publications dealing with other workflow man-

agement problems, e. g., flexibility and scalability, is

steadily increasing. Two noteworthy exceptions are [2]

and [12]. Both approaches, however, are not able in prin-

ciple to deal with dynamically evolving workflow ensem-

bles whose participants are not known in advance and

might change with time. Therefore, the thorough develop-

ment of interaction expressions and graphs and their ap-

plication to coordinate dynamically evolving workflow

ensembles constitutes a pioneering approach towards a

general solution of the inter-workflow coordination prob-

lem.

In addition to a very mature core implementation of in-

teraction expressions based on the formally verified oper-

ational semantics (cf. Sec. 5), a syntax-driven editor for

interaction graphs has been developed to facilitate their

creation in practice. Furthermore, early versions of the co-

ordination and subscription protocols described in Sec. 7

have been implemented and tested for the WfMS ProMI-

nanD [13]. Their integration into the next generation

WfMS ADEPT [3] is a topic of future work.

Acknowledgement

Many thanks to Peter Dadam for supervising the Ph. D.

thesis [7] and to the members of the ADEPT team for the

good collaboration.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)

interaction

manager

interaction graph/expression

prepare

patient

p,x

call

patient

p,x

perform

examination

p,x

inform

patient

p,x

p p

interaction

client

actions

prepare

patient

p,x

inform

patient

p,x

interaction

client

actions

call

patient

p,x

perform

examination

p,x

1. ask

2. reply

4. confirm

3. execute

1. subscribe

2. inform

4. cancel

3. update

worklists

5. state

transition

Figure 9: Coordination and subscription protocols

References

[1] R. H. Campbell, A. N. Habermann: “The Specification of

Process Synchronization by Path Expressions.” In: E. Gelenbe,

C. Kaiser (eds.): Operating Systems. Lecture Notes in Computer

Science 16, Springer-Verlag, Berlin, 1974, 89−−102.

[2] F. Casati, S. Ceri, B. Pernici, G. Pozzi: “Semantic Work-

Flow Interoperability.” In: P. Apers, M. Bouzeghoub, G. Garda-

rin (eds.): Advances in Database Technology −− EDBT’96. Lec-

ture Notes in Computer Science 1057, Springer-Verlag, Berlin,

1996, 443−−462.

[3] P. Dadam, M. Reichert: “The ADEPT WfMS Project at the

University of Ulm.” In: 1st European Workshop on Workflow

and Process Management (Zürich, Switzerland, 1998). 1998.

[4] F. J. Faase, S. J. Even, R. A. de By: Introduction to CoCoA

(TransCoop Deliverable IV.3). Technical Report TC/REP/UT/

D4-3/033, University of Twente, The Netherlands, Febru-

ary 1996.

[5] L. Guo, K. Salomaa, S. Yu: “On Synchronization Lan-

guages.” Fundamenta Informaticae 25 (3+4) March 1996,

423−−436.

[6] C. Heinlein, P. Dadam: Interaction Expressions −− A Power-

ful Formalism for Describing Inter-Workflow Dependencies.

UIB 97-04, Fakultät für Informatik, Universität Ulm, Febru-

ary 1997.

[7] C. Heinlein: Workflow and Process Synchronization with In-

teraction Expressions and Graphs. Ph. D. Thesis (in German),

Fakultät für Informatik, Universität Ulm, 2000.

[8] M. Hennessy: Algebraic Theory of Processes. The MIT

Press, Cambridge, MA, 1988.

[9] C. A. R. Hoare: Communicating Sequential Processes. Pren-

tice-Hall, London, 1985.

[10] S. Jablonski, M. Böhm, W. Schulze (eds.): Workflow-Ma-

nagement. Entwicklung von Anwendungen und Systemen.

dpunkt-Verlag, Heidelberg, 1997.

[11] K. Jensen, G. Rozenberg (eds.): High-Level Petri Nets.

Theory and Application. Springer-Verlag, 1991.

[12] M. Kamath, K. Ramamritham: “Failure Handling and Co-

ordinated Execution of Concurrent Workflows.” In: Proc. 14th

Int. Conf. on Data Engineering (ICDE) (Orlando, FL, February

1998). IEEE Computer Society, 1998, 334−−341.

[13] B. Karbe: “Flexible Vorgangssteuerung mit ProMInanD.”

In: U. Hasenkamp, S. Kirn, M. Syring (eds.): CSCW −− Compu-

ter Supported Cooperative Work. Addison-Wesley, Bonn, 1994,

117−−133.

[14] R. Milner: Communication and Concurrency. Pren-

tice-Hall, New York, 1989.

[15] J. L. Peterson: “Petri Nets.” ACM Computing Surveys 9 (3)

September 1977, 223−−252.

[16] W. E. Riddle: “A Method for the Description and Analysis

of Complex Software Systems.” ACM SIGPLAN Notices 8 (9)

September 1973, 133−−136.

[17] A. C. Shaw: “Software Description with Flow Expres-

sions.” IEEE Transactions on Software Engineering SE-4 (3)

May 1978, 242−−254.

[18] A. C. Shaw: “On the Specification of Graphics Command

Languages and Their Processors.” In: R. A. Guedj,

P. J. W. ten Hagen, F. R. A. Hopgood, H. A. Tucker, D. A. Duce

(eds.): Methodology of Interaction. North-Holland Publishing

Company, Amsterdam, 1980, 377−−392.

[19] A. C. Shaw: “Software Specification Languages Based on

Regular Expressions.” In: W. E. Riddle, R. E. Fairley (eds.):

Software Development Tools. Springer-Verlag, Berlin, 1980,

148−−175.

[20] G. Vossen, J. Becker (eds.): Geschäftsprozeßmodellierung

und Workflow-Management. Modelle, Methoden, Werkzeuge. In-

ternational Thomson Publishing, Bonn, 1996.

[21] Special Issue on Workflow and Extended Transaction Sys-

tems. IEEE Data Engineering Bulletin 16 (2) June 1993.

[22] Special Issue on Workflow Systems. IEEE Data Engineer-

ing Bulletin 18 (1) March 1995.

[23] Special Issue on Software Support for Work Flow Manage-

ment. Distributed and Parallel Databases 3 (2) April 1995.

[24] Special Issue on Workflow Systems. Distributed Systems

Engineering Journal 3 (4) December 1996.

[25] Special Issue on Workflow and Process Management.

Journal of Intelligent Information Systems. Integrating Artificial

Intelligence and Database Technologies 10 (2) March 1998.

Proceedings of the 17th International Conference on Data Engineering (ICDE ’01)