Business Process Diagrams (BPDs) provide a rich graphical expressiveness for modeling not only business processes but also the development of collective human activities. In Multiagent platforms, BPDs has been used for decoupling the modeling of agent behavior from its implementation. Additionally, the annotation of BPD actions and events with conjunctive queries has opened the door for monitoring process development by querying a knowledge base. We study the properties of this annotation scheme for the re nement of activity diagrams through the removal of redundant nodes, the detection of disjoint alternative paths and the merge/split of event nodes.
BPMN is a standard notation for modeling business processes widely adopted
by industry that provides a rich graphical representation that can be used for
common understanding of processes [
On the other hand, the use of conjunctive queries has been previously
proposed for describing the meaning of events and actions [
Muehlen and Indulska performed a representational analysis of modeling
languages for business processes and business rules, nding that the most complete
combination is BPMN and SWRL [
This paper is organized as follows. We introduce basic notions of BPMN Business Process Diagrams and Conjunctive Queries in section 2. Then, in section 3 we introduce semantic descriptors on a BPD normal form, describe the properties provided by the use of conjunctive queries and show how these properties can be used for re ning a BPD by detecting disjoint alternative paths, deleting redundant nodes, and merging/splitting nodes. We conclude with closing remarks and future work in section 4. 2
Next we introduce the formal notions used for introducing conjunctive queries as semantic descriptors on top of BPMN BPDs. 2.1
Business Process Modeling and Notation (BPMN) provides a formal representation of Business Process Diagrams (BPDs), which basically describe a process in terms of events and tasks connected through control ows that indicate valid sequences in the process development. Gateways are special nodes connected through control ows that indicate whether the process develops in parallel (AND), alternatively (XOR) or optionally (OR). The beginning of the process is denoted by an initial event node and its conclusion by a set of end event nodes.
Figure 1 shows a subset of the graphical notation of the BPMN 2.0 speci
cation [
Industry has adopted XML le formats for authoring and exchanging BPDs
such as XML Process De nition Language (XPDL)[
We use the notation and properties of conjunctive queries given by Description
Logics (DL) [
A DL conjunctive query (CQ) has the form:
Q = (s1; :::sn):fT1; :::; Tmg where si is the set of distinguished variables, denoted Dis(Q), that de ne the resulting binding sets (the information retrieved), and Ti is a nite set of either concept clauses (s rdf:type C) or relation clauses (s r s'), where s; s0 2 (NV [ NC ), C is a concept/class and r is a relation/property both de ned in T , NV is a nite set of variables denoted V ar(Q), and NC is a nite set of constants.
In SPARQL, the query language for RDF[
Query containment between conjunctive queries can be decided
automatically observing the constraints and de nitions given in T , as proposed by [
Queries Q1 and Q2 are equivalent if Q1 v Q2 and Q2 v Q1, denoted Q1 Q2. Q1 and Q2 are considered disjoint if K becomes inconsistent whenever K j= Q1 u Q2 for any replacement of common variables in both queries, also denoted by Q1 u Q2 v ?. By de nition, if Q1 v Q2 then Q1 and Q2 are not disjoint.
Merge of two queries Q1 and Q2 is given by its intersection and it is denoted by Q1 u Q2, whereas the opposite operation is called split. 1 OWL Web Ontology Language. https://www.w3.org/TR/owl-features/
Semantic Description of Business Process Diagrams Now we introduce semantic descriptors for describing the meaning of lanes, actions and events, provide some basic properties for annotated nodes and show how these can be used for re ning a BPD. 3.1
In this paper we use the formalization of BPDs and the normal form proposed
in [
A Business Process Diagram W is represented by a set of pools (P), lanes (L), nodes (N) and control ows (F). Nodes (N) allowed in the diagram are: start events (N S ), intermediate events (N I ), end events (N E ), human tasks (N A) and gateways (N G). A gateway g 2 N G can be of type Parallel-AND (A), OptionalOR (O), or Exclusive-XOR (X), denoted respectively type(g; fA; O; Xg). Unconditional sequence ows are denoted as F (ni; nj ) 2 F, ni ! nj for short, where ni; nj 2 N . All nodes n 2 N are situated in a lane l 2 L, denoted in(n; l).
W = fP; L; N; Fg
N = N S [ N I [ N E [ N A [ N G
the conjunctive query Q for representing the meaning of a lane, an observable event, or human task n 2 (L [ N S [ N I [ N E [ N A) in a BPD W.
A lane descriptor describes the kind of individual that play a role in the activity. It has the form Ann(l; Ql), where l 2 L and Ql might represent an absolute or relative role. An absolute role annotation is given by a Ql = (?role):f?role a RoleClassg where RoleClass indicates the type of individual, denoted by ?role, associated to l. A relative role annotation is given by a Ql = (?role):f?role rel ?role2g where the role associated to the lane (?role) is de ned in terms of its relationship (rel) with a participant represented by another lane (?role2).
An event descriptor has the form Ann(z; Qz), where z 2 (N S [ N I [ N E ) and Qz is a conjunctive query describing a condition (constraints between individuals) that denotes the occurrence of the event.
A task descriptor has the form Ann(x; Qx), where x 2 N A,
Qx = (?act):f?act a T askClass : ?act doneBy ?role :
?act propi ?valueig;
TaskClass indicates the type of task performed or initiated by ?role, and the
task description is expressed by statements such as ?act propi ?valuei. According
to Activity Theory[
De nition 2 (Annotated BPD). An annotated BPD WD is a BPD W where each node n 2 (L [ N S [ N I [ N E [ N A) is annotated with exactly one semantic descriptor Ann(n; Q) 2 D. 3.2
The use of semantic descriptors allows to verify automatically if the meaning of a BPD node is equivalent to, disjoint with, or subsumed by another BPD node.
BPD node n2, denoted n1?n2, if and only if Q1 u Q2 v ? with respect to (w.r.t.) T , given Ann(n1; Q1) and Ann(n2; Q2).
BPD node n2, denoted n1 v n2, if Q1 v Q2 and Q2 6v Q1 w.r.t. T , given Ann(n1; Q1) and Ann(n2; Q2).
BPD node n2, denoted n1 n2, if and only if Q1 Q2 w.r.t. T , given Ann(n1; Q1) and Ann(n2; Q2).
These de nitions can be used for detecting redundant nodes, i.e. consecutive event nodes annotated with equivalent descriptions.
Theorem 1 (Node Redundancy). Given two consecutive event nodes z1; z2 2 (N S [ N I [ N E), z1 ! z2, such that z2 v z1, z2 will hold whenever z1 holds, making z2 redundant in the diagram.
Proof. During process monitoring, the occurrence of the event z2 will be evaluated right after z1. z2 being subsumed by z1 means that z2 will hold whenever z1 holds, hence checking the occurrence of z2 becomes unnecessary once z1 has occurred.
In the example of Figure 2, the event z7:2 is redundant as long as z7:2 v z5:1, making unnecessary the observation of z7:2. The following corollary complements Theorem 1.
Corollary 1. Given two consecutive event nodes z1; z2 2 (N S [ N I [ N E), z1 ! z2, such that z2 z1, either z1 or z2 becomes redundant.
Proof. Given that z1 will hold whenever z2 does and vice versa, either of the two can be chosen as redundant node.
Two other properties apply to event nodes preceded by the same gateway. Two BPD events zi and zj are called siblings, denoted as zijjzj , if both of them are directly preceded by a gateway g 2 N G, i.e. zi g ! zj .
Determining that all sibling events following to a gateway g are disjoint indicates that g must be XOR-Exclusive. Figure 3 shows two alternative scenarios as result of a medical consultation, denoted by two sibling events, z4:2 and z4:3, with their corresponding descriptors. Ann(z4:2) and Ann(z4:3) are disjoint as long as the cardinality of the boolean role followUp is constrained to a single value in the concept Prescription, stated in T as:
Prescription v
1 followUp
immediately preceded by a splitting gateway g 2 N G are disjoint to each other (zi?zj ), then g must be an event-driven exclusive (XOR) gateway, i.e. type(g; X). Proof. Once g is reached, process development will continue through g if and only if some event zi occur after g. Being disjoint every pair of sibling events, only one of them can occur at a given time, hence the rst that occur will continue process' monitoring, which is the de nition of an event-driven exclusive (XOR) gateway. In contrast, g cannot be parallel (AND) as long as once that zi holds the condition represented by any of its sibling will not hold anymore. For the same reason g cannot be optional (OR), i.e. more than one sibling cannot hold.
On the contrary, overlaps between sibling events following to an exclusive gateway violates process development rules.
ately preceded by a splitting Exclusive-XOR gateway g 2 N G such that zi zj , will provoke a violation of process monitoring after g.
Proof. Once g is reached, process development must continue through one and only one path given by the sibling event holding next. zi zj means that both events will hold, violating the rule imposed by the XOR gateway. Theorem 4. A pair of sibling events zijjzj immediately preceded by a splitting Exclusive-XOR gateway g 2 N G such that zi v zj , can potentially provoke a violation of process monitoring after g.
Proof. Observing zj means that zi will hold as well, enabling process development through both branches which constitutes a violation of the splitting XOR gateway rule. Nevertheless, observing zi does not assure that zj will hold as well, in which case the violation would not occur.
Semantic description of sibling events following XOR gateways have similar or complementary descriptions as long as they represent alternative scenarios. In these cases, annotations of sibling events have a common sub-expression that can be captured before the splitting gateway.
ered a common precondition for all sibling events zi preceded by g if and only if Qi Qg u Q0i for every Ann(zi; Qi) 2 D.
Given that the normal form does not allow to annotate gateways, the common precondition must be represented through the introduction of an intermediate event preceding the gateway.
Theorem 5. The observation of a precondition Qg, included in a set of disjoint sibling events zi following to the gateway g, can be represented through the introduction of an event node zg such that: np ! g is replaced by np ! zg ! g, and D = D [ Ann(zg; Qg) n Ann(zi; Qi) [ Ann(zi; Q0i).
Proof. Process monitoring requires observing zg before reaching g, and then evaluating every zi. Assuming world state does not change between the observation of zg and the observation of zi, the observation of Q0i simultaneously to Qg is by de nition equivalent to observing Qi.
In both alternatives shown in Figure 3 the doctor prescribes medication, but in z4:3 the patient requires follow up whereas in z4:2 he does not. Figure 4 shows an equivalent representation where the event z4:2 3 represents the common condition, and original events are replaced by the necessity of a follow up appointment (z4:3B) or not (z4:2B).
Properties provided by semantic descriptors also permits to validate if the work ow can be monitored properly. For instance, Theorem 2 provides a rule for checking the correspondence between XOR gateways and disjoint events.
Descriptors of nodes in the structure shown in Figure 4 must be also checked to prevent monitoring issues. For instance, if doctor's prescription (evaluated as common precondition) indicates both more medication and a follow-up appointment, and one of the exclusive alternative paths check for more medication whereas the other asks for the follow-up appointment, then monitoring could continue through both paths, but the XOR gateway forces to continue for only one (chosen arbitrarily).
Theorem 6. A common precondition zg subsuming at least two alternative events zi immediately following a XOR gateway g, i.e. zi v zg, will provoke a violation of process monitoring after g.
Proof. Assuming that all sibling events zi are evaluated immediately after the precondition zg, once that zg holds any zi will hold as well. Process monitoring will follow through the branch of the rst zi evaluated, despite another branch could be followed (the one indicated by the other zi v zg).
In the same circumstances but having a Parallel-AND gateway, the precondition becomes redundant.
Theorem 7. A common precondition zg is redundant in the diagram if it subsumes all alternative events zi immediately following a Parallel-AND gateway g, i.e. zg ! g ! zi and zi v zg.
Proof. Given that process monitoring continues through all branches of a splitting Parallel-AND gateway, the evaluation of zg before every zi is unnecessary as long as zi will necessarily hold once that zg holds.
Theorems 1 and 7, and corollary 1 are used for simplifying the BPD by absorbing redundant nodes. Theorem 5 is used for introducing common preconditions. Theorem 2 is used for signaling disjoint alternatives. Finally, theorems 3, 4 and 6 are used for warning about errors on process monitoring.
The following procedure can be used for validating and automatically re ning the annotated BPD WD: 1. Identify consecutive events z1 ! z2 such that z1; z2 2 (N I [ N E ), (a) if z1 v z2 then absorb z2.
i. if z2 2 N E then N I = N I n z1 and N E = N E [ z1.
(b) if z1 z2 then absorb z1. 2. For each splitting gateway g immediately followed by sibling events zijjzj , (a) If all pairs (zi; zj ) are disjoint (zi?zj ), then set type(g; XOR). (b) If exists a common precondition Qg such that Qi Qg u Q0i for each descriptor Ann(zi; Qi) of all sibling events zi, insert an event zg ! g, D = D [ Ann(zg; Qg) n Ann(zi; Qi) [ Ann(zi; Q0i). (c) If type(g; XOR) and zi zj , then warn: Monitoring violation after g. (d) If type(g; XOR) and zi v zj , then warn: Potential monitoring violation after g. 3. For each splitting gateway g preceded by an event zg and followed by two or more sibling events zi, (a) If type(g; AN D) and zi v zg for all zi, then absorb zg. (b) If type(g; XOR) and zi v zg for at least two zi, then warn: Monitoring violation after g.
In this procedure, the absorption of a node ni means that all the arcs nj ! ni must be replaced by arcs nj ! nk for each nk given by every arc ni ! nk in the diagram. Then node ni as well as all its incoming and outgoing arcs are removed from the diagram.
Given that all re nement strategies are local, the complexity of the previous procedure is bounded by the computation of query containment between annotations of sibling event nodes. The identi cation of a common precondition for a set of sibling events zi requires checking if exists a common subset of triplets Q0i in every Qi.
As long as query containment is not a standard reasoning service provided by state-of-the-art triplestores or DL reasoners it would be necessary to develop a tool that e ciently decide query containment among a set of CQs. Such a service would decide Q1 v Q2 by transforming Q2's variables into symbols, asserting the resulting statements in a graph and asking Q1 to it (using the desired reasoning level). 4
We introduced a taxonomy of semantic descriptors for annotating lanes, events and tasks in BPMN BPDs. The proposed notation not only provides a formal description of these elements but it can be also used for mapping the business process speci cation to its implementation in an agent-based software.
We demonstrated how using conjunctive queries as semantic descriptors can help to detect relationships between BPMN BPD events. These relationships are then used for re ning process speci cations by detecting disjoint alternative paths, deleting redundant nodes, and merging/splitting nodes.
We also illustrated why human actions should not only be represented through their immediate e ects, but breaking them down helps Multiagent System.to determine whether the activity takes place according to how it was modeled.
Semantic descriptors can be further used for determining common events or actions across diagrams, enabling the composition of BPDs. Diagram composition would enable to introduce the execution of MAS protocols in human activities, both modeled through BPDs. Semantic descriptors can be also further used for monitoring process/activity development by inquiring a RDF triple store representing world state.