Automatic Generation of a Data-Centered View of Business Processes

Automatic Generation of a Data-Centered View of Business Processes Cristina Cabanillas1, Manuel Resinas1, Antonio Ruiz-Cort´es1,andAhmedAwad 2 1Universidad de Sevilla, Spain {cristinacabanillas,resinas,aruiz}@us.es 2Hasso Plattner Institute at the University of Potsdam [email protected]potsdam.de Abstract. Most commonly used business process (BP) notations, such as BPMN, focus on defining the control flow of the activities of a BP, i.e., they are activity-centered. In these notations, data play a secondary role, just as inputs or outputs of the activities. However, there is an increasing interest in analysing the life cycle of the data objects that are handled in a BP because it helps understand how data is modified during the execution of the process, detect data anomalies such as checking whether an activity requires a data object in a state that is unreachable, and check data compliance rules such as checking whether only a certain role can change the state of a data object. To carry out such an analysis, it is very appealing to provide a mechanism to transform from the usual activity-centered model of a BP to the set of life cycles of all the data objects involved in the process (i.e., a data-centered model). Unfortunately, although some proposals describe such transformation, they do not deal with data anomalies in the original BP model nor include information about the activities of the BP that are executed in the state transitions of the data object, which limits the analysis capabilities of the life cycle models. In this paper, we describe a model-driven procedure to automatically transform from an activity-centered model to a data-centered model of a BP that solves the aforementioned limitations of other proposals. Keywords: business process, data management, object life cycle, data anomalies, Petri net, reachability graph. 1 Introduction It is widely known that business processes (BPs) involve different kinds of elements, to be named control flow, time, data and resources. However, most This work has been partially supported by the European Commission (FEDER), Spanish Government under the CICYT project SETI (TIN2009-07366); and projects THEOS (TIC-5906) and ISABEL (P07-TIC-2533) funded by the Andalusian Local Government. commonly used BP models and notations focus on the control flow and the timing of activities in the BP. As a consequence, in most BP models, data (e.g., documents, reports, invoices, emails and the like) play a secondary role, just as inputs or outputs of the activities of the process. Nevertheless, understanding and analysing how data is modified during the execution of a BP is getting an increased interest from both industry and academy. For instance, BPMN, the de-facto standard for BP modelling, has incorporated more advanced constructs for data management in its last version [1]. In addition, there is an increasing number of research proposals to analyse the way data is used in a BP to detect anomalies [2,3,4] and to define data-aware compliance rules [5] for BPs. Therefore, providing a mechanism to transform from the usual activity-centered view of a BP to a data-centered view that focuses on the data handled during the process is very appealing to this goal of understanding and analysing how data is modified during the execution of a BP. In this paper we describe a model-driven procedure based on Petri nets for carrying out this transformation automatically. In particular, the input of the procedure is a BP diagram expressed in BPMN 2.0 (cf. Figure 1). We use this notation because it is the de-facto standard for BP modelling. Such diagrams represent data objects connected to the BP activities that use them either to read them or write them, or for both things. A data object has a type and can have one or more states along the execution of a process. For instance, in the BP of opening a bank account, the data object application filled by the new customer could go through states sent,accepted and stored. The output of the procedure is a data-centered view composed of the set of object life cycles (OLCs) of all the data objects that are involved in a BP. They represent the allowed transitions between the states of the data object according to the BP diagram. In addition, these transitions also include information about the activities of the BP that are executed in the transition between states of the data object (cf. Figure 2). Furthermore our procedure also deals with some data anomalies that may appear in a BP model (cf. Section 4 for more details). Our approach has the following advantages: (i) it is fully automated; (ii) it is based on Petri nets, which allows us to use efficient and well-tested Petri net algorithms; (iii) since it includes information about the activities that are executed in each transition, it provides the same full information required to understand BP execution as activity-centered process diagrams; and (iv) it is robust in the sense that it provides an accurate data-centered view despite having a BP with data anomalies as input. Moreover, it informs the user about these data anomalies. The remaining of the paper is organised as follows. Section 2 introduces a use case used to exemplify the output produced by the procedure. Section 3 contains the description of the whole procedure for OLC generation. In Section 4 the detection and handling of data anomalies is introduced. Section 5 contains a summary of related work and in Section 6 we draw a set of conclusions and outline some future work. INTERNATIONAL OLYMPIC COMMITTEE INTERNATIONAL OLYMPIC COMMITTEE Collect candidates Assess candidates Approve accepted candidates Vote Check winner Delete last position Is there a winner? Notify results Publish winner Candidatures created Candidatures assessed Candidatures selected Reso l u t i o n created Candidatures updated Reso l u t i o n updated Reso l u t i o n notified Reso l u t i o n published Candidatures stored No Yes Fig. 1. Business process for assigning the venue for the Olympic Games 2 Use Case To illustrate our approach we use the BP for assigning the venue for the Olympic Games (Figure 1) as use case in this paper1. The International Olympic Committee is in charge of this process. This committee first receives the applications of the cities that want to organize the Olympic Games. Each city is evaluated in order to keep only those which fulfill all the requirements. After this filter is applied, an approval of the final candidates is necessary. Once the list of candidates is ready, a secret voting is carried out. If there is consensus and only one city is selected, then the winner venue is published. Otherwise, the least voted city is eliminated from the list of candidates and a new voting is performed. This is repeated until there are only two cities left. Then, the city with a greatest number of votes wins. There are two data objects in this BP model. Data object Candidates represents a document that contains a list of the cities that applied for the venue. The information of each candidate in the document includes the name of the city, its description, what it offers for each requirement needed, and the mark given by the committee to discern between accepted and rejected candidates. This document may be updated during the voting repetitive process. Data object Resolution represents the result of the voting and, thus, is a document with the same list of candidates and the number of votes each of them received. Again, this data object will be updated if more than one voting is performed. If there is no winner yet, the resolution is notified. Otherwise, the resolution is completed with the features of the final venue and published. The output of the procedure presented in this paper is a set of finite-state machines (FSM) representing the life cycles of the data objects modelled in a 1Note that this process is used for illustration purposes only, so there may be differences with the actual process of the Olympic Games venue selection process. Collect candidates Assess candidates Approve accepted candidates Approve accepted candidates Vote Check winner Check winner Delete last position Is there a winner? Notify results No Vote Check winner Notify results Check winner Is there a winner? Publish winner Yes Publish winner created published updated notified Fig. 2. Object life cycle of data object Resolution of the business process in Fig. 1 BP. Figure 2 depicts the life cycle of data object Resolution of our use case. The life cycles of a data object have one start state (represented with a filled circle), one final state (represented with a semi-filled circle), and one or more intermediate states (represented with a rectangle) that correspond with states of the data object in the BP model. Transitions (represented with directed arrows) connect two states and contain the parts of the BP that are executed in the transition between states of the data object. 3 BP2OLC Procedure BP2OLC is our approach to automatically generate the OLCs of the data objects represented in a BPMN model2. As depicted in Figure 3, it is a three-step procedure based on model transformations which involves four different models. The procedure must be carried out for each data object type present in the BP model. We assume the source BP model has the following features: 1. As far as control flow is concerned, the BP model is sound, which basically means it has no control flow deadlocks and terminates properly [6]. 2. There is only one copy of each data object in each instance of the process, e.g., there is only one data object Resolution in one instance of the process. 2All the terms referring to elements of a BP model are used in the same sense as in the BPMN 2.0 specification [1]. A2 A3 A4 A5A1 D1 created D1 blocked D1 unblocked D1 stored created blockedunblocked stored          Fig. 3. Overview of the BP2OLC procedure Besides, data objects are created within the BP instance that uses them (i.e. data objects created outside of the process are not considered). 3. Each data object has always a state. In case an appearance of a data object in the BP model is not associated with any state, this appearance will be ignored. 4. The BP model can contain data objects connected to any kind of activity (sub-processes are treated like task activities). Only XOR gateways can be used. Assumption 1 is made because control-flow soundness is out of the scope of this paper. Assumptions 2 and 3 are reasonable and have also been made elsewhere [2]. The last assumption is related to the reach of the current approach. 3.1 Step 1. From BPMN Model to Petri Net We believe that providing a semantic mapping [7] between a BPMN model and a target domain such as Petri nets, whose semantics has been formally defined, is a good approach because it allows one to use the techniques specific to the target semantic domain for analysing the source models. We chose Petri nets for two reasons: (i) plenty of processing algorithms on Petri nets have already been developed and can be useful for our purpose [6,8]; and (ii) the transformation of the control flow of a BP model into an equivalent Petri net has already been described in [6]. Definition 1. APetri net is a 3-tuple PN =(TPN,P,F),where: –TPN ={t1,t 2, ..., tn}is the set of transitions of the Petri net, represented graphically as rectangles. –P={p1,p 2, ..., pn}is the set of places of the Petri net, represented graphically as circles. –F⊆(P×TPN)(TPN ×P)is the set of arcs of the Petri net (flow relation), represented as arrows. Amarking (state) or markup assigns a nonnegative integer to each place of a Petri net. If it assigns to place pa nonnegative integer k,wesaythatpis marked with ktokens. Pictorially, we place kblack dots (tokens) in place p.Amarkup Table 1. Mapping for data objects association with loop activities                                         !                     !  Pr ev A APo st A DataObject state1 DataObject state2 Pr evA DataObject_state1 A A Po st A AAPostA DataObject_state2 Pr ev A APo st A DataObject DataObject state2 Pr ev A APo st A DataObject state2 Pr evA DataObject_state1 A A Po st A AAPostA DataObject_state 2 A A DataObject_stateN is denoted by M, an m-vector, where mis the total number of places. The pth component of M, denoted by M(p), is the number of tokens in place p. The firing of an enabled transition will change the token distribution (marking) in a net [8]. We use the set of rules introduced by Awad et al. [2] to do the semantic mapping between elements of a BP model with data objects and elements of aPetrinet.LetEBP be the set of flow nodes of a BP (model), i.e. activities, gateways and events, DBP the set of states of a data object of that BP, and WRITERSBP ⊆EBP be the set of activities of the BP that write that data object. The result of the semantic mapping is a Petri net with the following characteristics: –The places of the Petri net are of two different kinds: control places PCand data places PD. Therefore P=PCPDand PCPD=∅. •PC={pc1,pc 2, ..., pcn}corresponds to those places that represent sequence flow elements (arrows)of the business process. Each pci=(eii,eo i), where eii,eo i∈EBP is a pair of values composed of the two flow nodes of the business process that the sequence flow element connects. •PD={pd1,pd 2, ..., pdn}=DBP corresponds to those places that represent states of the data object whose object life cycle we are generating. There is exactly one data place for each possible state of the data object. –The transitions of the Petri net represent flow nodes of the business process model. It follows an n: 1 relationship, i.e., each transition represents only one flow node of the business process and a flow node may appear several times in a Petri net. Function elem :TPN →EBP represents such relation. An example of the transformation rules is depicted in Table 1, which illustrates an extension of the catalogue of transformations proposed in [2] to deal with loop activities. As stated in [1], a loop activity executes the inner activity as long as a loop condition evaluates to true. An attribute can be set to specify a maximal number of iterations. An example of loop activity is an activity Update order that updates an order in a restaurant (by customer’s command) until an event or a received message indicates no more updates are allowed. For more details about the other transformations we refer the reader to [2]. Finally, note that there is a small difference between this mapping and the one presented in [2] because in this paper we consider no data objects are supposed to exist before the execution of a BP in our BP2OLC procedure, whereas [2] considers data objects have an initial state when instantiating a BP. This difference causes the transformation in [2] referring to the writing of the data object has to be slightly changed for the first writing of the object in our BP2OLC procedure, in order to comply with our assumption 2. It means the first time the data object is written, the responsible transition of the Petri net does not have any input data places. 3.2 Step 2. Reachability Graph from Petri Net Definition 2. Areachability graph related to a Petri net is a 3-tuple RGPN = (N,M,TRG),where: –N={n1,n 2, ..., nn}is the set of nodes of the reachability graph. ∀ni∈N,•ni and ni•represent immediately previous and next nodes of ni, respectively. –M:P×N→Nrepresents the markup of the net. –TRG ⊆(N×N)are the transitions of the reachability graph. The reachability graph is obtained by analysing the Petri net by means of wellknown algorithms. Each node of the reachability graph represents a reachable marking state of the net and each arc a possible change of state, i.e. the firing of a transition. However, due to the characteristics of our semantic mapping between BPMN and Petri net, in the reachability graph resulting from such Petri nets it holds that M(p, n)∈[0,1],∀n∈N,∀p∈P. In addition, the information about the markup of the net contained in every node always corresponds with both a sequence flow of the BP model and a state of the data object, as illustrated in Figure 4. It means there is always one token in a control place of the Petri net and one in a data place, except in the beginning (until an activity writes the data object for the first time) and in the final nodes of the reachability graph (in which, on the contrary, all the tokens in control places have been consumed). Given the previous definitions, the following functions can be defined: –Function map :TRG →TPN is defined to map the transitions of a reachability graph into the transitions of a Petri net. –Function state :N→PDreturns the state of the data object of the business process model contained in the current node of the reachability graph. state(n)={pd∈PD:M(pd,n)=1}. END END XOR1 Act1 , , , ... ... XOR1 Fig. 4. Content of the arcs and nodes of a reachability graph –Function flow :P(N)→P(PC) returns the set of sequence flow elements of the business process model contained in a set of nodes of the reachability graph. flow(N)={pc∈Pc:∃n∈N(M(pc,n)=1))}. –Function activity :N→EBP returns the flow node of the business process model contained in the input arc of the current node of the reachability graph. activity(n)={ei∈EBP :pc=(ei,e o)∧M(pc,n)=1}. The node of the reachability graph with no input arrows is called firstNode ∈ N:∃•firstNode and it is the start node of a reachability graph. The nodes of the reachability graph with no output arrows, whose input is called END andwithnotokensinacontrolplacearenormal final nodes of the reachability graph. We will describe abnormal final nodes in Section 3.3. 3.3 Step 3. Object Life Cycle from Reachability Graph Definition 3. An object life cycle of a data object of a business process is a 2-tuple OLC =(SOLC ,T OLC),where: –SOLC ={s1,s 2, ..., sn}is the set of states in which the data object can be. ∀si∈SOLC,•siand si•represent immediately previous and next states of state si, respectively. Let start ∈Sand end ∈Sbe the start and the final states of the OLC, respectively. Then, SOLC \(start end)=PD=DBP –TOLC ⊆SOLC ×SOLC ×P(N)is the set of transitions that appear in the object life cycle. Each transition contains a set of nodes of the reachability graph from which it has been generated. Function replace :TOLC ×N× P(N)→TOLC replaces the set of nodes before node N in the path of a transition for a specific set of nodes. We have defined Algorithms 1 and 2 to obtain an OLC from a reachability graph. Algorithm 1 receives the reachability graph resulting from the previous step and the list of activities of the BP that write the data object. Its output is the OLC together with a set of data anomalies found while creating it. Algorithm 1. Algorithm to initialize an object life cycle, call Algorithm 2 from a reachability graph and post-process nodes already processed in Algorithm 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,firstNode,START STATE,∅,∅,∅,∅,S OLC,T OLC) 5: (SOLC,T OLC,PNODES,PP,WARN)←RG2OLC(INPUT) 6: found ←1 // Post-processing of nodes in PP 7: while found =0do 8: found ←0 9: for all (node, assocP ath)∈PP do 10: for all (si,s o,path)∈TOLC do 11: if node ∈path then 12: found ←found +1;newT ←(si,s o,path) 13: TOLC ←TOLC replace(newT, node, assocP ath) 14: end if 15: end for 16: end for 17: end while 18: return (SOLC,T OLC,WARN) Its behaviour consists of calling Algorithm 2 with the appropriate parameters and post-processing the resulting reachability graph. Algorithm 2 is a recursive algorithm that builds an OLC by processing a reachability graph node by node from its start node. Its input set and steps are described below. Input of Algorithm 2. –WRIT ⊆Eis the set of activities that write the data object. –cNode ∈Nis the node being processed. –cState ∈Dis the current state of the data object. –PNODES ⊆Nis the set of already processed nodes. –PATH ⊆Ncontains a set of nodes of the reachability graph, which is the information required in the transitions of the object life cycle. –PP ={pair1,pair 2, ..., pairn},wherepairi=(node, assocP ath),node i∈ N, assocP athi⊆Nis a set of pairs containing a node of the reachability graph and a set of nodes associated to that node, which conceptually corresponds to the path contained in variable PATH when processing that node. –WARN ⊆Nis a set of nodes related to deadlocks in the Petri net. –S OLC ⊆SOLC is the set of states of the resulting object life cycle. –T OLC ⊆TOLC is the set of transitions of the resulting object life cycle. Check for and add new transitions (lines 3-7). A new transition of one of thetypesshowninFigures5aand5bmustbeaddedtotheOLCincasethat a new state of the data object is found in the reachability graph. If, on the contrary, the node shows that the data object is still in the current state but