Au oma ic Gene a ion o a Da a-Cen e ed View
o Business P ocesses
C is ina Cabanillas1, Manuel Resinas1,
An onio Ruiz-Co ´es1,andAhmedAwad
2
1Uni e sidad de Se illa, Spain
{c is inacabanillas, esinas,a uiz}@us.es
2Hasso Pla ne Ins i u e a he Uni e si y o Po sdam
[email p o ec ed]po sdam.de
Abs ac . Mos commonly used business p ocess (BP) no a ions, such
as BPMN, ocus on defining he con ol flow o he ac i i ies o a BP,
i.e., hey a e ac i i y-cen e ed. In hese no a ions, da a play a seconda y
ole, jus as inpu s o ou pu s o he ac i i ies. Howe e , he e is an in-
c easing in e es in analysing he li e cycle o he da a objec s ha a e
handled in a BP because i helps unde s and how da a is modified du -
ing he execu ion o he p ocess, de ec da a anomalies such as checking
whe he an ac i i y equi es a da a objec in a s a e ha is un eachable,
and check da a compliance ules such as checking whe he only a ce ain
ole can change he s a e o a da a objec . To ca y ou such an analy-
sis, i is e y appealing o p o ide a mechanism o ans o m om he
usual ac i i y-cen e ed model o a BP o he se o li e cycles o all he
da a objec s in ol ed in he p ocess (i.e., a da a-cen e ed model). Un-
o una ely, al hough some p oposals desc ibe such ans o ma ion, hey
do no deal wi h da a anomalies in he o iginal BP model no include
in o ma ion abou he ac i i ies o he BP ha a e execu ed in he s a e
ansi ions o he da a objec , which limi s he analysis capabili ies o
he li e cycle models. In his pape , we desc ibe a model-d i en p oce-
du e o au oma ically ans o m om an ac i i y-cen e ed model o a
da a-cen e ed model o a BP ha sol es he a o emen ioned limi a ions
o o he p oposals.
Keywo ds: business p ocess, da a managemen , objec li e cycle, da a
anomalies, Pe i ne , eachabili y g aph.
1 In oduc ion
I is widely known ha business p ocesses (BPs) in ol e diffe en kinds o el-
emen s, o be named con ol flow, ime, da a and esou ces. Howe e , mos
This wo k has been pa ially suppo ed by he Eu opean Commission (FEDER),
Spanish Go e nmen unde he CICYT p ojec SETI (TIN2009-07366); and p ojec s
THEOS (TIC-5906) and ISABEL (P07-TIC-2533) unded by he Andalusian Local
Go e nmen .
commonly used BP models and no a ions ocus on he con ol flow and he im-
ing o ac i i ies in he BP. As a consequence, in mos BP models, da a (e.g.,
documen s, epo s, in oices, emails and he like) play a seconda y ole, jus as
inpu s o ou pu s o he ac i i ies o he p ocess.
Ne e heless, unde s anding and analysing how da a is modified du ing he ex-
ecu ion o a BP is ge ing an inc eased in e es om bo h indus y and academy.
Fo ins ance, BPMN, he de- ac o s anda d o BP modelling, has inco po a ed
mo e ad anced cons uc s o da a managemen in i s las e sion [1]. In addi-
ion, he e is an inc easing numbe o esea ch p oposals o analyse he way da a
is used in a BP o de ec anomalies [2,3,4] and o define da a-awa e compliance
ules [5] o BPs. The e o e, p o iding a mechanism o ans o m om he usual
ac i i y-cen e ed iew o a BP o a da a-cen e ed iew ha ocuses on he da a
handled du ing he p ocess is e y appealing o his goal o unde s anding and
analysing how da a is modified du ing he execu ion o a BP.
In his pape we desc ibe a model-d i en p ocedu e based on Pe i ne s o
ca ying ou his ans o ma ion au oma ically. In pa icula , he inpu o he
p ocedu e is a BP diag am exp essed in BPMN 2.0 (c . Figu e 1). We use his
no a ion because i is he de- ac o s anda d o BP modelling. Such diag ams
ep esen da a objec s connec ed o he BP ac i i ies ha use hem ei he o
ead hem o w i e hem, o o bo h hings. A da a objec has a ype and can
ha e one o mo e s a es along he execu ion o a p ocess. Fo ins ance, in he BP
o opening a bank accoun , he da a objec applica ion filled by he new cus ome
could go h ough s a es sen ,accep ed and s o ed. The ou pu o he p ocedu e
is a da a-cen e ed iew composed o he se o objec li e cycles (OLCs) o all he
da a objec s ha a e in ol ed in a BP. They ep esen he allowed ansi ions
be ween he s a es o he da a objec acco ding o he BP diag am. In addi ion,
hese ansi ions also include in o ma ion abou he ac i i ies o he BP ha
a e execu ed in he ansi ion be ween s a es o he da a objec (c . Figu e 2).
Fu he mo e ou p ocedu e also deals wi h some da a anomalies ha may appea
in a BP model (c . Sec ion 4 o mo e de ails).
Ou app oach has he ollowing ad an ages: (i) i is ully au oma ed; (ii) i
is based on Pe i ne s, which allows us o use efficien and well- es ed Pe i
ne algo i hms; (iii) since i includes in o ma ion abou he ac i i ies ha a e
execu ed in each ansi ion, i p o ides he same ull in o ma ion equi ed o
unde s and BP execu ion as ac i i y-cen e ed p ocess diag ams; and (i ) i is
obus in he sense ha i p o ides an accu a e da a-cen e ed iew despi e ha ing
a BP wi h da a anomalies as inpu . Mo eo e , i in o ms he use abou hese
da a anomalies.
The emaining o he pape is o ganised as ollows. Sec ion 2 in oduces a
use case used o exempli y he ou pu p oduced by he p ocedu e. Sec ion 3
con ains he desc ip ion o he whole p ocedu e o OLC gene a ion. In Sec ion
4 he de ec ion and handling o da a anomalies is in oduced. Sec ion 5 con ains
a summa y o ela ed wo k and in Sec ion 6 we d aw a se o conclusions and
ou line some u u e wo k.
INTERNATIONAL OLYMPIC COMMITTEE
INTERNATIONAL OLYMPIC COMMITTEE
Collec
candida es
Assess
candida es
App o e
accep ed
candida es Vo e Check
winne
Dele e las
posi ion
Is he e a winne ?
No i y
esul s
Publish
winne
Candida u es
c ea ed
Candida u es
assessed
Candida u es
selec ed
Reso l u i o n
c ea ed
Candida u es
upda ed
Reso l u i o n
upda ed
Reso l u i o n
no i ied
Reso l u i o n
published
Candida u es
s o ed
No
Yes
Fig. 1. Business p ocess o assigning he enue o he Olympic Games
2 Use Case
To illus a e ou app oach we use he BP o assigning he enue o he Olympic
Games (Figu e 1) as use case in his pape 1. The In e na ional Olympic Com-
mi ee is in cha ge o his p ocess. This commi ee fi s ecei es he applica ions
o he ci ies ha wan o o ganize he Olympic Games. Each ci y is e alua ed in
o de o keep only hose which ulfill all he equi emen s. A e his fil e is ap-
plied, an app o al o he final candida es is necessa y. Once he lis o candida es
is eady, a sec e o ing is ca ied ou . I he e is consensus and only one ci y
is selec ed, hen he winne enue is published. O he wise, he leas o ed ci y
is elimina ed om he lis o candida es and a new o ing is pe o med. This
is epea ed un il he e a e only wo ci ies le . Then, he ci y wi h a g ea es
numbe o o es wins.
The e a e wo da a objec s in his BP model. Da a objec Candida es ep e-
sen s a documen ha con ains a lis o he ci ies ha applied o he enue. The
in o ma ion o each candida e in he documen includes he name o he ci y,
i s desc ip ion, wha i offe s o each equi emen needed, and he ma k gi en
by he commi ee o disce n be ween accep ed and ejec ed candida es. This
documen may be upda ed du ing he o ing epe i i e p ocess. Da a objec
Resolu ion ep esen s he esul o he o ing and, hus, is a documen wi h he
same lis o candida es and he numbe o o es each o hem ecei ed. Again,
his da a objec will be upda ed i mo e han one o ing is pe o med. I he e is
no winne ye , he esolu ion is no ified. O he wise, he esolu ion is comple ed
wi h he ea u es o he final enue and published.
The ou pu o he p ocedu e p esen ed in his pape is a se o fini e-s a e
machines (FSM) ep esen ing he li e cycles o he da a objec s modelled in a
1No e ha his p ocess is used o illus a ion pu poses only, so he e may be diffe -
ences wi h he ac ual p ocess o he Olympic Games enue selec ion p ocess.
Collec
candida es
Assess
candida es
App o e
accep ed
candida es
App o e
accep ed
candida es Vo e Check
winne
Check
winne
Dele e las
posi ion
Is he e a winne ?
No i y
esul s
No
Vo e Check
winne
No i y
esul s
Check
winne
Is he e a winne ?
Publish
winne
Yes
Publish
winne
c ea ed
published
upda ed no i ied
Fig. 2. Objec li e cycle o da a objec Resolu ion o he business p ocess in Fig. 1
BP. Figu e 2 depic s he li e cycle o da a objec Resolu ion o ou use case.
The li e cycles o a da a objec ha e one s a s a e ( ep esen ed wi h a filled
ci cle), one inal s a e ( ep esen ed wi h a semi-filled ci cle), and one o mo e
in e media e s a es ( ep esen ed wi h a ec angle) ha co espond wi h s a es o
he da a objec in he BP model. T ansi ions ( ep esen ed wi h di ec ed a ows)
connec wo s a es and con ain he pa s o he BP ha a e execu ed in he
ansi ion be ween s a es o he da a objec .
3 BP2OLC P ocedu e
BP2OLC is ou app oach o au oma ically gene a e he OLCs o he da a ob-
jec s ep esen ed in a BPMN model2. As depic ed in Figu e 3, i is a h ee-s ep
p ocedu e based on model ans o ma ions which in ol es ou diffe en models.
The p ocedu e mus be ca ied ou o each da a objec ype p esen in he BP
model. We assume he sou ce BP model has he ollowing ea u es:
1. As a as con ol flow is conce ned, he BP model is sound, which basically
means i has no con ol flow deadlocks and e mina es p ope ly [6].
2. The e is only one copy o each da a objec in each ins ance o he p ocess,
e.g., he e is only one da a objec Resolu ion in one ins ance o he p ocess.
2All he e ms e e ing o elemen s o a BP model a e used in he same sense as in
he BPMN 2.0 specifica ion [1].
A2
A3
A4
A5A1
D1
c ea ed
D1
blocked
D1
unblocked
D1
s o ed
c ea ed
blockedunblocked
s o ed
   
 



Fig. 3. O e iew o he BP2OLC p ocedu e
Besides, da a objec s a e c ea ed wi hin he BP ins ance ha uses hem (i.e.
da a objec s c ea ed ou side o he p ocess a e no conside ed).
3. Each da a objec has always a s a e. In case an appea ance o a da a objec
in he BP model is no associa ed wi h any s a e, his appea ance will be
igno ed.
4. The BP model can con ain da a objec s connec ed o any kind o ac i i y
(sub-p ocesses a e ea ed like ask ac i i ies). Only XOR ga eways can be
used.
Assump ion 1 is made because con ol-flow soundness is ou o he scope o his
pape . Assump ions 2 and 3 a e easonable and ha e also been made elsewhe e
[2]. The las assump ion is ela ed o he each o he cu en app oach.
3.1 S ep 1. F om BPMN Model o Pe i Ne
We belie e ha p o iding a seman ic mapping [7] be ween a BPMN model and
a a ge domain such as Pe i ne s, whose seman ics has been o mally defined,
is a good app oach because i allows one o use he echniques specific o he
a ge seman ic domain o analysing he sou ce models. We chose Pe i ne s o
wo easons: (i) plen y o p ocessing algo i hms on Pe i ne s ha e al eady been
de eloped and can be use ul o ou pu pose [6,8]; and (ii) he ans o ma ion
o he con ol flow o a BP model in o an equi alen Pe i ne has al eady been
desc ibed in [6].
De ini ion 1. APe i ne is a 3- uple PN =(TPN,P,F),whe e:
–TPN ={ 1,
2, ..., n}is he se o ansi ions o he Pe i ne , ep esen ed
g aphically as ec angles.
–P={p1,p
2, ..., pn}is he se o places o he Pe i ne , ep esen ed g aphi-
cally as ci cles.
–F⊆(P×TPN)(TPN ×P)is he se o a cs o he Pe i ne ( low ela ion),
ep esen ed as a ows.
Ama king (s a e) o ma kup assigns a nonnega i e in ege o each place o a
Pe i ne . I i assigns o place pa nonnega i e in ege k,wesay ha pis ma ked
wi h k okens. Pic o ially, we place kblack do s ( okens) in place p.Ama kup

Table 1. Mapping o da a objec s associa ion wi h loop ac i i ies
  

 

     
  

   
  
    
    
     
!




 



    

    
!

P e A APo s A
Da aObjec
s a e1
Da aObjec
s a e2
P e - A
Da aObjec _s a e1
A
A
Po s A
A- A- Pos A
Da aObjec _s a e2
P e A APo s A
Da aObjec Da aObjec
s a e2
P e A APo s A
Da aObjec
s a e2
P e - A
Da aObjec _s a e1
A
A
Po s A
A- A- Pos A
Da aObjec _s a e
2
A
A
Da aObjec _s a eN
is deno ed by M, an m- ec o , whe e mis he o al numbe o places. The p h
componen o M, deno ed by M(p), is he numbe o okens in place p. The fi ing
o an enabled ansi ion will change he oken dis ibu ion (ma king) in a ne [8].
We use he se o ules in oduced by Awad e al. [2] o do he seman ic
mapping be ween elemen s o a BP model wi h da a objec s and elemen s o
aPe ine .Le EBP be he se o flow nodes o a BP (model), i.e. ac i i ies,
ga eways and e en s, DBP he se o s a es o a da a objec o ha BP, and
WRITERSBP ⊆EBP be he se o ac i i ies o he BP ha w i e ha da a
objec . The esul o he seman ic mapping is a Pe i ne wi h he ollowing
cha ac e is ics:
–The places o he Pe i ne a e o wo diffe en kinds: con ol places PCand
da a places PD. The e o e P=PCPDand PCPD=∅.
•PC={pc1,pc
2, ..., pcn}co esponds o hose places ha ep esen se-
quence flow elemen s (a ows)o he business p ocess. Each pci=(eii,eo
i),
whe e eii,eo
i∈EBP is a pai o alues composed o he wo flow nodes o
he business p ocess ha he sequence flow elemen connec s.
•PD={pd1,pd
2, ..., pdn}=DBP co esponds o hose places ha ep e-
sen s a es o he da a objec whose objec li e cycle we a e gene a ing.
The e is exac ly one da a place o each possible s a e o he da a objec .
–The ansi ions o he Pe i ne ep esen flow nodes o he business p ocess
model. I ollows an n: 1 ela ionship, i.e., each ansi ion ep esen s only
one flow node o he business p ocess and a flow node may appea se e al
imes in a Pe i ne . Func ion elem :TPN →EBP ep esen s such ela ion.
An example o he ans o ma ion ules is depic ed in Table 1, which illus a es
an ex ension o he ca alogue o ans o ma ions p oposed in [2] o deal wi h
loop ac i i ies. As s a ed in [1], a loop ac i i y execu es he inne ac i i y as
long as a loop condi ion e alua es o ue. An a ibu e can be se o speci y a
maximal numbe o i e a ions. An example o loop ac i i y is an ac i i y Upda e
o de ha upda es an o de in a es au an (by cus ome ’s command) un il an
e en o a ecei ed message indica es no mo e upda es a e allowed. Fo mo e
de ails abou he o he ans o ma ions we e e he eade o [2].
Finally, no e ha he e is a small diffe ence be ween his mapping and he one
p esen ed in [2] because in his pape we conside no da a objec s a e supposed
o exis be o e he execu ion o a BP in ou BP2OLC p ocedu e, whe eas [2]
conside s da a objec s ha e an ini ial s a e when ins an ia ing a BP. This diffe -
ence causes he ans o ma ion in [2] e e ing o he w i ing o he da a objec
has o be sligh ly changed o he fi s w i ing o he objec in ou BP2OLC
p ocedu e, in o de o comply wi h ou assump ion 2. I means he fi s ime
he da a objec is w i en, he esponsible ansi ion o he Pe i ne does no
ha e any inpu da a places.
3.2 S ep 2. Reachabili y G aph om Pe i Ne
De ini ion 2. A eachabili y g aph ela ed o a Pe i ne is a 3- uple RGPN =
(N,M,TRG),whe e:
–N={n1,n
2, ..., nn}is he se o nodes o he eachabili y g aph. ∀ni∈N,•ni
and ni• ep esen immedia ely p e ious and nex nodes o ni, espec i ely.
–M:P×N→N ep esen s he ma kup o he ne .
–TRG ⊆(N×N)a e he ansi ions o he eachabili y g aph.
The eachabili y g aph is ob ained by analysing he Pe i ne by means o well-
known algo i hms. Each node o he eachabili y g aph ep esen s a eachable
ma king s a e o he ne and each a c a possible change o s a e, i.e. he fi ing o a
ansi ion. Howe e , due o he cha ac e is ics o ou seman ic mapping be ween
BPMN and Pe i ne , in he eachabili y g aph esul ing om such Pe i ne s i
holds ha M(p, n)∈[0,1],∀n∈N,∀p∈P. In addi ion, he in o ma ion abou
he ma kup o he ne con ained in e e y node always co esponds wi h bo h a
sequence flow o he BP model and a s a e o he da a objec , as illus a ed in
Figu e 4. I means he e is always one oken in a con ol place o he Pe i ne
and one in a da a place, excep in he beginning (un il an ac i i y w i es he
da a objec o he fi s ime) and in he final nodes o he eachabili y g aph (in
which, on he con a y, all he okens in con ol places ha e been consumed).
Gi en he p e ious defini ions, he ollowing unc ions can be defined:
–Func ion map :TRG →TPN is defined o map he ansi ions o a eacha-
bili y g aph in o he ansi ions o a Pe i ne .
–Func ion s a e :N→PD e u ns he s a e o he da a objec o he busi-
ness p ocess model con ained in he cu en node o he eachabili y g aph.
s a e(n)={pd∈PD:M(pd,n)=1}.
END
END
XOR1
Ac 1
,
,
,
...
...
XOR1
Fig. 4. Con en o he a cs and nodes o a eachabili y g aph
–Func ion low :P(N)→P(PC) e u ns he se o sequence flow elemen s
o he business p ocess model con ained in a se o nodes o he eachabili y
g aph. low(N)={pc∈Pc:∃n∈N(M(pc,n)=1))}.
–Func ion ac i i y :N→EBP e u ns he flow node o he business p ocess
model con ained in he inpu a c o he cu en node o he eachabili y
g aph. ac i i y(n)={ei∈EBP :pc=(ei,e
o)∧M(pc,n)=1}.
The node o he eachabili y g aph wi h no inpu a ows is called i s Node ∈
N:∃• i s Node and i is he s a node o a eachabili y g aph. The nodes
o he eachabili y g aph wi h no ou pu a ows, whose inpu is called END
andwi hno okensinacon olplacea eno mal final nodes o he eachabili y
g aph. We will desc ibe abno mal final nodes in Sec ion 3.3.
3.3 S ep 3. Objec Li e Cycle om Reachabili y G aph
De ini ion 3. An objec li e cycle o a da a objec o a business p ocess is a
2- uple OLC =(SOLC ,T
OLC),whe e:
–SOLC ={s1,s
2, ..., sn}is he se o s a es in which he da a objec can be.
∀si∈SOLC,•siand si• ep esen immedia ely p e ious and nex s a es o
s a e si, espec i ely. Le s a ∈Sand end ∈Sbe he s a and he inal
s a es o he OLC, espec i ely. Then, SOLC (s a end)=PD=DBP
–TOLC ⊆SOLC ×SOLC ×P(N)is he se o ansi ions ha appea in he
objec li e cycle. Each ansi ion con ains a se o nodes o he eachabili y
g aph om which i has been gene a ed. Func ion eplace :TOLC ×N×
P(N)→TOLC eplaces he se o nodes be o e node N in he pa h o a
ansi ion o a speci ic se o nodes.
We ha e defined Algo i hms 1 and 2 o ob ain an OLC om a eachabili y
g aph. Algo i hm 1 ecei es he eachabili y g aph esul ing om he p e ious
s ep and he lis o ac i i ies o he BP ha w i e he da a objec . I s ou -
pu is he OLC oge he wi h a se o da a anomalies ound while c ea ing i .
Algo i hm 1. Algo i hm o ini ialize an objec li e cycle, call Algo i hm 2 om a
eachabili y g aph and pos -p ocess nodes al eady p ocessed in Algo i hm 2 (RG2OLC)
1: IN: RGDP N =(N,M,TRG ); WRITERS
BP
2: OUT: SOLC;TOLC;WARN ⊆N
3: SOLC ←{START STATE};TOLC ←∅
4: INPUT ←(WRITERS, i s Node,START STATE,∅,∅,∅,∅,S
OLC,T
OLC)
5: (SOLC,T
OLC,PNODES,PP,WARN)←RG2OLC(INPUT)
6: ound ←1 // Pos -p ocessing o nodes in PP
7: while ound =0do
8: ound ←0
9: o all (node, assocP a h)∈PP do
10: o all (si,s
o,pa h)∈TOLC do
11: i node ∈pa h hen
12: ound ← ound +1;newT ←(si,s
o,pa h)
13: TOLC ←TOLC  eplace(newT, node, assocP a h)
14: end i
15: end o
16: end o
17: end while
18: e u n (SOLC,T
OLC,WARN)
I s beha iou consis s o calling Algo i hm 2 wi h he app op ia e pa ame e s
and pos -p ocessing he esul ing eachabili y g aph. Algo i hm 2 is a ecu si e
algo i hm ha builds an OLC by p ocessing a eachabili y g aph node by node
om i s s a node. I s inpu se and s eps a e desc ibed below.
Inpu o Algo i hm 2.
–WRIT ⊆Eis he se o ac i i ies ha w i e he da a objec .
–cNode ∈Nis he node being p ocessed.
–cS a e ∈Dis he cu en s a e o he da a objec .
–PNODES ⊆Nis he se o al eady p ocessed nodes.
–PATH ⊆Ncon ains a se o nodes o he eachabili y g aph, which is
he in o ma ion equi ed in he ansi ions o he objec li e cycle.
–PP ={pai 1,pai
2, ..., pai n},whe epai i=(node, assocP a h),node
i∈
N, assocP a hi⊆Nis a se o pai s con aining a node o he eachabili y
g aph and a se o nodes associa ed o ha node, which concep ually
co esponds o he pa h con ained in a iable PATH when p ocessing
ha node.
–WARN ⊆Nis a se o nodes ela ed o deadlocks in he Pe i ne .
–S
OLC ⊆SOLC is he se o s a es o he esul ing objec li e cycle.
–T
OLC ⊆TOLC is he se o ansi ions o he esul ing objec li e cycle.
Check o and add new ansi ions (lines 3-7). A new ansi ion o one o
he ypesshowninFigu es5aand5bmus beadded o heOLCincase ha
a new s a e o he da a objec is ound in he eachabili y g aph. I , on he
con a y, he node shows ha he da a objec is s ill in he cu en s a e bu