Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Synthesizing object life cycles from business process models

  • Regular Paper
  • Published:
Software & Systems Modeling Aims and scope Submit manuscript

Abstract

Unified modeling language (UML) activity diagrams can model the flow of stateful business objects among activities, implicitly specifying the life cycles of those objects. The actual object life cycles are typically expressed in UML state machines. The implicit life cycles in UML activity diagrams need to be discovered in order to derive the actual object life cycles or to check the consistency with an existing life cycle. This paper presents an automated approach for synthesizing a UML state machine modeling the life cycle of an object that occurs in different states in a UML activity diagram. The generated state machines can contain parallelism, loops, and cross-synchronization. The approach makes life cycles that have been modeled implicitly in activity diagrams explicit. The synthesis approach has been implemented using a graph transformation tool and has been applied in several case studies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

References

  1. Aho, A., Sethi, R., Ullman, J.: Compilers: Principles, Techniques, and Tools. Addison Wesley, Reading (1986)

    Google Scholar 

  2. Börger, E., Cavarra, A., Riccobene, E.: An ASM semantics for UML activity diagrams. In: Rus, T. (ed.) Proceedings of the international conference on Algebraic Methodology and Software Technology (AMAST 2000), Lecture Notes in Computer Science 1826, pp. 293–308. Springer, Berlin (2000)

    Google Scholar 

  3. BPMN Task Force: Business Process Model and Notation (BPMN) Version 2.0. Object Management Group. OMG Document Number formal/2011-01-03 (2011)

  4. Cabanillas, C., Resinas, M., Cortés, A.R., Awad, A.: Automatic generation of a data-centered view of business processes. In: Mouratidis, H., Rolland, C. (eds.) CAiSE 2011. Lecture Notes in Computer Science, vol. 6741, pp. 352–366. Springer, Berlin (2011)

    Google Scholar 

  5. Dick, N., Huschens, J.: IAA the IBM insurance application architecture. In: Bernus, P., Mertins, K., Schmidt, G. (eds.) Handbook on Architectures of Information Systems, International Handbooks on Information Systems, pp. 619–637. Springer, Berlin (1998)

  6. Dumas, M., Fjellheim, T., Milliner, S., Vayssière, J.: Event-based coordination of process-oriented composite applications. In: van der Aalst, W.M.P., Benatallah, B., Casati, F., Curbera, F. (eds.) Business Process Management, vol. 3649, pp. 236–251. Springer, Berlin (2005)

    Chapter  Google Scholar 

  7. Engels, G., Förster, A., Heckel, R., Thöne, S.: Process modeling using UML. In: Dumas, M., van der Aalst, W., ter Hofstede, A. (eds.) Process-Aware Information Systems, pp. 85–117. Wiley, New York (2005)

    Google Scholar 

  8. Engels, G., Küster, J.M., Heckel, R., Groenewegen, L.: A methodology for specifying and analyzing consistency of object-oriented behavioral models. In: Tjoa, A.M., Gruhn, V. (eds.) Proceedings of ESEC / SIGSOFT FSE, pp. 186–195 (2001)

  9. Eshuis, R.: Symbolic model checking of UML activity diagrams. ACM Trans. Softw. Eng. Methodol. 15(1), 1–38 (2006)

    Article  Google Scholar 

  10. Eshuis, R.: Translating safe Petri nets to statecharts in a structure-preserving way. In: Cavalcanti, A., Dams, D. (eds.) Proceedings of FM 2009, Lecture Notes in Computer Science, vol. 5850, pp. 239–255. Springer, Berlin (2009)

    Google Scholar 

  11. Eshuis, R.: Statechartable Petri nets. Form. Asp. Comput. 25(5), 659–681 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Eshuis, R., Van Gorp, P.: Synthesizing object life cycles from business process models. In: Atzeni, P., Cheung, D.W., Ram, S. (eds.) Proceedings of ER 2012, Lecture Notes in Computer Science, vol. 7532, pp. 307–320. Springer, Berlin (2012)

    Google Scholar 

  13. Esparza, J.: Reduction and synthesis of live and bounded free choice Petri nets. Inf. Comput. 114(1), 50–87 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  14. Geiß, R., Batz, G.V., Grund, D., Hack, S., Szalkowski, A.: Grgen: a fast SPO-based graph rewriting tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) Proceedings of ICGT 2006, Lecture Notes in Computer Science, vol. 4178, pp. 383–397. Springer, Berlin (2006)

    Google Scholar 

  15. Giese, H., Graf, J., Wirtz, G.: Closing the gap between object-oriented modeling of structure and behavior. In: France, R.B., Rumpe, B. (eds.) Proceedings of UML’99, Lecture Notes in Computer Science, vol. 1723, pp. 534–549. Springer, Berlin (1999)

    Google Scholar 

  16. von Hanxleden, R., Fuhrmann, H., Spönemann, M.: KIELER–the KIEL integrated environment for layout eclipse rich client. In: Macii, E. (ed.) Proceedings of the Design, Automation and Test in Europe University Booth (DATE’11). Grenoble, France (2011)

  17. Harel, D.: On visual formalisms. Commun. ACM 31(5), 514–530 (1988)

    Article  MathSciNet  Google Scholar 

  18. Harel, D., Kugler, H.: Synthesizing state-based object systems from LSC specifications. Int. J. Found. Comp. Sci. 13(1), 5–51 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  19. Harel, D., Kugler, H.: The Rhapsody semantics of statecharts (or, on the executable core of the UML)—preliminary version. In: Ehrig, H., Damm, W., Desel, J., Große-Rhode, M., Reif, W., Schnieder, E., Westkämper, E. (eds.) Integration of Software Specification Techniques for Applications in Engineering, Lecture Notes in Computer Science, vol. 3147, pp. 325–354. Springer, Berlin (2004)

    Chapter  Google Scholar 

  20. Harel, D., Naamad, A.: The STATEMATE semantics of statecharts. ACM Trans. Softw. Eng. Methodol. 5(4), 293–333 (1996)

    Article  Google Scholar 

  21. Hecht, M., Ullman, J.: Characterizations of reducible flow graphs. J. ACM 21, 367–375 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  22. I-Logix: Rhapsody. http://www.ilogix.com (2005)

  23. Kumaran, S., Liu, R., Wu, F.Y.: On the duality of information-centric and activity-centric models of business processes. In: Bellahsene, Z., Léonard, M. (eds.) CAiSE, Lecture Notes in Computer Science, vol. 5074, pp. 32–47. Springer, Berlin (2008)

  24. Küster, J.M., Ryndina, K., Gall, H.: Generation of business process models for object life cycle compliance. In: Alonso, G., Dadam, P., Rosemann, M. (eds.) Proceedings of BPM, Lecture Notes in Computer Science, vol. 4714, pp. 165–181. Springer, Berlin (2007)

  25. Lin, C.P., Jeng, L.D., Lin, Y.P., Jeng, M.: Management and control of information flow in CIM systems using UML and Petri nets. Int. J. Comp. Integr. Manuf. 18(2&3), 107–121 (2005)

  26. Liu, R., Kumar, A.: An analysis and taxonomy of unstructured workflows. In: van der Aalst, W., Benatallah, B., Casati, F., Curbera, F. (eds.) Proceedings of 3rd Conference on Business Process Management (BPM 2005), Lecture Notes in Computer Science, vol. 3649, pp. 268–284. Springer, Berlin (2005)

  27. Massink, M., Latella, D., Gnesi, S.: On testing UML statecharts. J. Logic Algebr. Progr. 69(1–2), 1–74 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Mellor, S.J., Balcer, M.J.: Executable UML—A Foundation for Model-Driven Architecture. Addison Wesley object technology series. Addison-Wesley, Reading (2002)

    Google Scholar 

  29. Mendling, J., Hafner, M.: From WS-CDL choreography to BPEL process orchestration. J. Enterp. Inf. Manage. 21(5), 525–542 (2008)

    Article  Google Scholar 

  30. Nejati, S., Sabetzadeh, M., Chechik, M., Easterbrook, S.M., Zave, P.: Matching and merging of statecharts specifications. In: Proceedings of ICSE, pp. 54–64. IEEE Computer Society (2007)

  31. No Magic Inc: MagicDraw. http://www.magicdraw.com

  32. Redding, G., Dumas, M., ter Hofstede, A.H.M., Iordachescu, A.: Generating business process models from object behavior models. IS Manag. 25(4), 319–331 (2008)

    Google Scholar 

  33. Schrefl, M., Stumptner, M.: On the design of behavior consistent specializations of object life cycles in OBD and UML. In: Papazoglou, M.P., Spaccapietra, S., Tari, Z. (eds.) Advances in Object-Oriented Data Modeling, pp. 65–104. MIT Press, Cambridge (2000)

    Google Scholar 

  34. Shlaer, S., Mellor, S.: Object Oriented Life Cycles: Modeling the World in States. Prentice Hall, Englewood Cliffs (1991)

    Google Scholar 

  35. Software, I.R.: Rose. http://www.rational.com (2005)

  36. Sparx Systems: Enterprise Architect. http://www.sparxsystems.eu/EnterpriseArchitect

  37. Universal business language version, 2.1. OASIS (2013)

  38. UML Revision Taskforce: OMG UML Specification v. 1.5. Object Management Group. OMG Document Number formal/2003-03-01. http://www.uml.org (2003)

  39. UML Revision Taskforce: UML 2.3 Superstructure Specification. Object Management Group. OMG Document Number formal/2010-05-05 (2010)

  40. Van Gorp, P.: Applying traceability and cloning techniques to compose input-destructive model transformations into an input-preserving chain. In: Lano, K., Kolahdouz-Rahimi S. (eds.) 1st Workshop on Composition and Evolution of Model Transformations, King’s College, London, UK (2011)

  41. Van Gorp, P., Eshuis, R.: Transforming process models: executable rewrite rules versus a formalized java program. In: Petriu, D.C., Rouquette, N., Haugen, Ø. (eds.) Proceedings of MoDELS 2010, Lecture Notes in Computer Science, vol. 6395, pp. 258–272. Springer, Berlin (2010)

    Google Scholar 

  42. Whittle, J., Jayaraman, P.K.: Synthesizing hierarchical state machines from expressive scenario descriptions. ACM Trans. Softw. Eng. Methodol. 19(3), 8 (2010)

    Article  Google Scholar 

  43. Whittle, J., Schumann, J.: Generating statechart designs from scenarios. In: ICSE, pp. 314–323 (2000)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Rik Eshuis.

Additional information

Communicated by Professor Brian Henderson-Sellers.

Appendix: Formal definitions

Appendix: Formal definitions

This appendix contains formal definitions of the syntax of activity diagrams and state machines (Appendix 9.1), the filtering rules (Appendix 9.2), the transformation rules that result in state machines (Appendix 9.3), the refactoring rules that deal with cross-synchronization (Appendix 9.4), plus a proof of correctness (Appendix 9.5).

1.1 Activity diagrams and state machines

An activity diagram is a graph that specifies the ordering of activities and the flow of objects that are used by the activities.

Definition 1

(Activity diagrams) An activity diagram is a tuple \((A,O,C,E,guard,instate)\) where

  • \(A\) is the set of activities;

  • \(O\) is the set of object nodes. For this paper, we assume that all object nodes refer to the same object, which is therefore not formalized;

  • \(C\) is the set of control nodes, also called pseudo-nodes, partitioned into sets \(\{i\}\), \(DM\), \(FJ\), \(F\), where

    • \(i\) is the unique start node, which has no predecessor;

    • \(DM\) is the set of decisions and merges;

    • \(FJ\) is the set of forks and joins;

    • \(F\) is the set of final nodes, which have no successors;

  • \(E \subseteq A \cup O \cup C \times A \cup O \cup C\) is the set of flow edges, where an edge that enters or leaves an object node in \(O\) is called an object flow; all other edges are control flows;

  • \(guard: E \rightarrow L\) is a partial function assigning a guard label from the set of labels \(L\) to an edge. We only allow guard labels on edges leaving decision nodes;

  • \(instate: O \rightarrow \mathcal {S}\) is a function that specifies for each object node the unique state in \(\mathcal {S}\) that the object is in.

We put some constraints on the edge relation \(E\):

  • the induced graph is weakly connected, so for every pair of nodes \(n_1,n_2 \in A \cup O \cup C\), there is an undirected path between \(n_1\) and \(n_2\);

  • \(i\) has no predecessor;

  • each node \(f \in F\) has no successors;

  • each activity \(a \in A\) has one incoming control flow and one outgoing control flow.

  • each control node \(n \in C{\setminus }(\{i\} \cup F)\), except the initial and final nodes, has a predecessor and a successor.

As explained in Sect. 2, we consider in this paper only activity diagrams that process a single stateful object. Each different state of the object is represented with an object node. The stateful object has a life cycle that is represented in a state machine.

A state machine is hierarchical hypergraph [17], consisting of nodes arranged in a tree and directed hyperedges. There are three types of nodes: BASIC, AND, and OR. BASIC nodes are leaves of the tree, while AND and OR node are internal. The state machine formalization used here stems from earlier work [11]. That work also defines an execution semantics of state machines.

Definition 2

A state machine is a tuple \((N,H,source\), \(target, guard, child, default,r)\), where

  • \(N\) is a set of nodes, which is partitioned into sets \(BN\), \(AN\), and \(ON\), where

    • \(BN\) is a finite set of BASIC nodes, which are not decomposed into other nodes;

    • \(AN\) is a finite set of AND nodes, which specify parallel decomposition;

    • \(ON\) is a finite set of (X)OR nodes, which specify exclusive-or decomposition;

  • \(H\) is a finite set of hyperedges, \(N \cap H = \emptyset \);

  • \(source: H \rightarrow \mathcal {P}(N)\) is a function defining the non-empty set of source nodes for each hyperedge;

  • \(target: H \rightarrow \mathcal {P}(N)\) is a function defining the non-empty set of target nodes for each hyperedge;

  • \(guard: H \rightarrow L\) is a partial function assigning a guard label from \(L\) to a hyperedge;

  • \(child \subseteq N \times N\) is a predicate that relates a child node to its parent node, so \((n,n') \in child\) means \(n\) is child of \(n'\). We require that \(child\) arranges the nodes in \(N\) in a rooted tree, so every node in \(N\), except the root, has one parent node, and every node is indirectly child of the root. We require \(x \in BN\) if and only if \(\{y ~|~(y,x) \in child\}=\emptyset \), so only BASIC nodes have no children.

  • \(default: ON \rightarrow N\) is a function that identifies for each OR node \(n\) one of its children as the default node: \(default(n)\in children(n)\). As defined below in the semantics, if a hyperedge \(h\) enters \(n\) but does not explicitly enter any of its children, then \(h\) enters \(default(n)\).

  • \(r \in N\) is the root of the tree induced by \(child\). For technical reasons, \(r\) is required to be an OR node.

1.2 Filtering rules

Formal definitions are presented for the filtering rules presented in Sect. 3. Each rule operates on an activity diagram \((A,O,C,E,guard,instate)\) and consists of a (pre)condition and an effect, which is the new activity diagram tuple \((A',O',C',E',guard',instate')\). We only define the elements of the tuple that are changed, so if for instance \(A'\) is omitted, then \(A'=A\).

To define the rules in a concise way, we introduce additional notation. Let \(n \in A \cup O \cup C\) be a node. Then \(in(n)=\{~n'~|~(n',n) \in E~\}\) and \(out(n)=\{~n'~|~(n,n')\in E~\}\). For a binary relation \(R\), the relation \(R(x \leftarrow y)\) is the relation obtained by replacing each appearance of \(y\) with \(x\) in each tuple of \(R\) [13].

Definition 3

(Rule R1) Condition. There is a node \(n \in A \cup C\) such that \({{|}{in(n)}{|}}={{|}{out(n)}{|}}=1\).

Effect. Let \(\{n_1\}=in(n)\) and \(\{n_2\}=out(n)\). Then

  • \(A'=A {\setminus } \{n\}\);

  • \(C'=C {\setminus } \{n\}\);

  • \(E'=(E \cap ((A'\cup O'\cup C') \times (A'\cup O' \cup C') )) \cup (n_1,n_2)\)

  • \(instate'=instate \cap (O' \times S)\).

Definition 4

(Rule R2) Condition. There are decisions/merges \(d_1,d_2 \in DM\) such that \((d_1,d_2) \in E\) and \({{|}{in(d_2)}{|}}=~1\).

Effect.

  • \(C'=C {\setminus } \{d_2\}\);

  • \(E'=(E {\setminus } \{(d_1,d_2)\})(d_1 \leftarrow d_2)\);

  • \(guard'=(guard \cap ((A \cup O \cup C')\times L)) \oplus \{(d_2,x)\mapsto g~|~x \in A \cup O \cup C' \wedge g=guard((d_1,d_2)) \wedge guard(d_2,x)\}\),

where \(\oplus \) denotes function overriding.

Definition 5

(Rule R3) Condition. There are decisions/merges \(d_1,d_2 \in DM\) such that \((d_1,d_2) \in E\) and \({{|}{out(d_1)}{|}}=~1\).

Effect.

  • \(C'=C {\setminus } \{d_1\}\);

  • \(E'=(E {\setminus } \{(d_1,d_2)\})(d_2 \leftarrow d_1)\);

Definition 6

(Rule R4) Condition. There is a decision/merge \(n \in DM\) such that \((n,n) \in E\).

Effect.

  • \(C'=C {\setminus } \{n\}\);

  • \(E'=E {\setminus } \{(n,n)\}\);

Definition 7

(Rule R5) Condition. There are fork/joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\) and there is a simple path of length 2 or more from \(n_1\) to \(n_2\).

Effect.

  • \(E'=E {\setminus } \{(n_1,n_2)\}\);

Definition 8

(Rule R6) Condition. There is a fork or join \(n \in FJ\) and a final node \( f\in F\) such that \((n,f) \in E\) and \({{|}{out(f)}{|}}>1\).

Effect.

  • \(C'=C {\setminus } \{f\}\);

  • \(E'=E {\setminus } \{(n,f)\}\);

Definition 9

(Rule R7) Condition. There are forks or joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\), \({{|}{out(n_1)}{|}}>1\) and \({{|}{in(n_2)}{|}}=1\).

Effect.

  • \(C'=C {\setminus } \{n_2\}\);

  • \(E'=(E {\setminus } \{(n_1,n_2)\})(n_1 \leftarrow n_2)\);

Definition 10

(Rule R8) Condition. There are forks or joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\), \({{|}{out(n_1)}{|}}=1\) and \({{|}{in(n_2)}{|}}>1\).

Effect.

  • \(C'=C {\setminus } \{n_1\}\);

  • \(E'=(E {\setminus } \{(n_1,n_2)\})(n_2 \leftarrow n_1)\);

Definition 11

(Rule R9) Condition. There is a decision \(d \in DM\) and object node \(o \in O\) such that

  • there is a fork \(f \in FJ\) such that \(in(d)=\{f\}=in(o)\);

  • \(out(d)=out(o)\);

  • \(out(d),out(o) \subseteq FJ\).

Effect.

  • \(C'=C {\setminus } \{d\}\);

  • \(E'=E \cap (( A \cup O \cup C') \times ( A \cup O \cup C')) \);

  • \(guard'=(guard \cap ((A \cup O \cup C')'\times L)) \oplus \{(o,x)\mapsto g~|~x \in N' \wedge g=guard((d,x))\}\).

Definition 12

(Rule R10) Condition. There is a merge \(m \in DM\) and object node \(o \in O\) such that

  • there is a join \(j \in FJ\) such that \(out(m)=\{j\}=out(o)\);

  • \(in(m)=in(o)\);

  • \(in(m),in(o) \subseteq FJ\).

Effect.

  • \(C'=C {\setminus } \{m\}\);

  • \(E'=E \cap (( A \cup O \cup C') \times ( A \cup O \cup C')) \);

1.3 Transformation rules

There are three transformation rules. Each rule operates on an expanded activity diagram. An expanded activity diagrams contains AND/OR trees, the leaves of which are object nodes or control nodes that are not bars. The internal nodes of each tree are AND and OR nodes. Edges only connect bars and OR nodes that root the AND/OR trees.

We first define expanded activity diagram; next, we define the initialization rule that transforms a filtered activity diagram into an expanded activity diagram.

Definition 13

(Expanded activity diagram) An expanded activity diagram is a tuple \((A,O,C,E,guard, instate, AN\), \(ON,parent)\) where

  • \(A\), \(O\), \(C\), \(guard\), and \(instate\) are as defined for activity diagrams;

  • \(E \subseteq (ON \cup FJ) \times (ON \cup FJ)\) is the edge relation, now defined between OR nodes and fork and joins only;

  • \(ON\) is the set of OR nodes;

  • \(AN\) the set of \(AND\) nodes;

  • \(parent: (O\cup C \cup AN \cup ON) \rightarrow (AN\cup ON)\) is a function that maps a child node to its unique parent node.

Definition 14

(Initialization) Condition. None of the filtering rules R1–R8 apply to the activity diagram \((A,O,C,E\), \(guard,instate)\), so \(A=\emptyset \). There is no edge connecting two forks/joins: \( E \cap (FJ \times FJ)=\emptyset \). If the latter constraint is violated, so there are forks or joins \(n_1\), \(n_2 \in FJ\) and \((n_1,n_2)\in E\) then a dummy object node \(o\) can be inserted between the forks/joins, so \((n_1,n_2)\) is replaced with \((n_1,o)\) and \((o,n_2)\) in \(E\).

Effect. The expanded activity diagram is defined as the tuple \((A',O',C',E',guard',instate',AN',ON',parent')\), where

  • \(A'=A\);

  • \(O'=O\);

  • \(C'=C\);

  • \(E'=E(on_n \leftarrow n)\) for each \(n \in A \cup O \cup (C{\setminus } FJ)\);

  • \(guard'=\{~(on_n,x)\mapsto g~|~n \in DM \wedge x \in A \cup O \cup C \wedge g=guard(on_n,x)~\}\)

  • \(instate'=\emptyset \);

  • \(AN'=AN\);

  • \(ON'=\{~on_o~|~o \in O~\} \cup \{~on_c~|~c \in C {\setminus } FJ~\} \);

  • \(parent'=\{~(n,on_n)~|~n \in O'\cup C'~\} \).

The transformation rules T1 and T2 operate on expanded activity diagrams. As the filtering rules, each transformation rule has a condition and an effect, which is the definition of the new activity diagram \((A',O',C',E',guard'\), \(instate'\), \(AN',ON',parent')\).

We define two versions of T1. Version a operates on an edge connecting two OR nodes. Version b operates on a fork/join node that has a single predecessor and a single successor, both of which are OR nodes. Such a fork/join results after applying T2a to the source and target sets of the fork/join.

Definition 15

(Rule T1a) Condition. Let there be nodes \(o_1,o_2 \in ON\) such that \(out(o_1)=\{o_2\}\) and \(in(o_2)=\{o_1\}\), and for every fork/join \(n \in FJ\), \(o_1\) and \(o_2\) are not both input or both output for \(n\), so \(o_1,o_2 \not \in in(n)\) and \(o_1,o_2 \not \in out(n)\).

Effect. Let \(o\) be a fresh OR node, so \(o\not \in ON\).

  • \(E'=E{\setminus } \{(o_1,o_2)\}\);

  • \(ON'=(ON {\setminus }\{o_1,o_2\}) \cup o\);

  • \(parent'=parent(o_1 \leftarrow o,o_2\leftarrow o)\).

Definition 16

(Rule T1b) Condition. Let there be nodes \(o_1,o_2 \in ON\) such that there is a fork/join \(n \in FJ\) such that \(out(o_1)=\{n\}\) and \(in(o_2)=\{n\}\), and for every other fork/join \(n' \in FJ\), \(o_1\) and \(o_2\) are not both input or both output for \(n'\), so \(o_1,o_2 \not \in in(n')\) and \(o_1,o_2 \not \in out(n')\).

Effect. Let \(o\) be a fresh OR node, so \(o\not \in ON\).

  • \(C'=C {\setminus } \{n\}\);

  • \(E'=E{\setminus } \{(o_1,n),(n,o_2)\}\);

  • \(ON'=(ON {\setminus }\{o_1,o_2\}) \cup o\);

  • \(parent'=parent(o_1 \leftarrow o,o_2\leftarrow o)\).

Definition 17

(Rule T2a) Condition. Let there be a fork/join \(n \in FJ\) and a set \(X\) of OR nodes such that \(in(n)=X\) or \(out(n)=X\) such that for each pair of nodes \(x_1,x_2 \in X\), \(in(x_1)=in(x_2)\) and \(out(x_1)=out(x_2)\).

Effect. Let \(a\) and \(o\) be a fresh AND and OR node, respectively, so \(a\not \in AN\) and \(o \not \in ON\).

  • \(E'=E(o \leftarrow X)\);

  • \(AN'=AN \cup \{a\}\);

  • \(ON'=ON \cup \{o\}\);

  • \(parent'=parent \cup \{ ~(x,a)~|~x \in X~\} \cup \{(a,o)~\}\)

In the definition, \(E(o\leftarrow X)\) abbreviates \(E(o \leftarrow x_1, \ldots , o \leftarrow x_n) \) where \({{|}{X}{|}}=n\).

Rule T2b is a minor variation on T2 that is needed if T3 has been applied. In that case, an expanded activity diagram results in which there are no edges but only OR nodes that root the AND/OR trees. One of these AND/OR trees is rooted by the node whose incident edges were removed in T3.

Definition 18

(Rule T2b) Condition. Let \(X\) be a set of OR nodes. Each node \(x \in X\) has no parent, and every OR node \(o \in ON{\setminus } X\) does have a parent. The set of edges \(E\) is empty.

Effect. Let \(a\) and \(o\) be a fresh AND and OR node, respectively, so \(a\not \in AN\) and \(o \not \in ON\).

  • \(AN'=AN \cup \{a\}\);

  • \(ON'=ON \cup \{o\}\);

  • \(parent'=parent \cup \{ ~(x,a)~|~x \in X~\} \cup \{(a,o)\}\).

Definition 19

(Rule T3) Let there be a fork \(f\) and join \(j\), where \(f,j \in FJ\) and an OR node \(o \in ON\) such that \((f,o),(o,j)\in E\).

Condition. T1 and T2 are not applicable, and \({{|}{out(f)}{|}}>1\) and \({{|}{in(j)}{|}}>1\).

Effect. All edges from and to \(o\) are removed, so

  • \(E'=E \cap (((ON{\setminus }{o}) \cup n ) \times ((ON{\setminus }{o}) \cup n ) )\);

Definition 20

(Finalization) Let \(AD=(A,O,C,E,guard\), \(instate)\) be the filtered activity diagram and let \(EAD\)= \((A,O,C,E\),\(guard,instate,AN,ON,parent)\) be the expanded activity diagram that results after repeatedly applying T1, T2, and T3 to the expanded activity diagram derived from \(AD\).

Condition. Rules T1, T2, and T3 are not applicable to \(EAD\). Next, the set of edges of \(EAD\) must be empty, so \(E_{EAD}=\emptyset \). This condition implies that the set of forks and joins of \(EAD\) is empty.

Effect. The state machine tuple becomes \((N',H'\), \(source'\), \(target',guard',child',default',r')\), where

  • \(N'=BN' \cup AN' \cup ON'\), where

    • \(BN'=\{~instate(o)~|~o \in O_{AD}~\} \cup (C_{AD} {\setminus } FJ_{AD})\)

    • \(AN'=AN_{EAD}\)

    • \(ON'=ON_{EAD}\)

  • \(H'=FJ \cup \{ ~e \in E_{AD}~|~{{|}{in(e)}{|}}={{|}{out(e)}{|}}=1~\}\)

  • \(source'=\{~(x,y) \mapsto \{x\} ~|~(x,y) \in E_{AD} \cap H'~\} \cup \{~n \mapsto in(n)~|~n \in FJ_{AD}~\}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\).

  • \(target'=\{~(x,y) \mapsto \{y\} ~|~(x,y) \in E_{AD} \cap H'~\} \cup \{~n \mapsto out(n)~|~n \in FJ_{AD}~\}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\)

  • \(guard'=\{h \mapsto g~|~ h \in H' \wedge h \in E_{AD} \wedge g=guard_{AD}(h)\}\)

  • \(child'=parent_{EAD}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\)

  • \(default'=\{~(on_i,i)~\}\)

  • \(r'= on_i\)

Function \(default\) only specifies the default completion for the root node, which contains the initial node of the activity diagram as BASIC node. The default nodes are redundant for regular edges since the source set and target set of each hyperedge are complete: no default nodes need to be added to enter a valid configuration [11].

1.4 Refactoring

If T3 was applied to synthesize a state machine, then the generated state machine is not consistent with the filtered activity diagram, and the state machine needs to be refactored, as discussed in Sect. 5.

The refactoring rules use state machines with events and guards. Consequently, the state machine tuples are expanded with a set \(E\) of events and partial functions \(event, action:H\rightarrow E\). Next, we allow guard conditions to reference BASIC nodes using predicate \((n)\), where \(n \in BN\), which is true if \(n\) is currently active. The intended meaning is that if for hyperedge \(h\), these functions are defined, \(h\) is enabled if \(event(h)\) occurs, its states in \(source(h)\) are active, and \(guard(h)\) evaluates to true. If \(h\) is taken, \(action(h)\) is generated.

We now define an initialization rule and two refactoring rules. As before, when defining the new state machine tuples, only the changed elements are defined.

Definition 21

(Initialization refactoring) Let \((N,H,source\), \(target,guard,child,default,r)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine.

Condition. Node \(O\) was processed in T3.

Effect. The state machine tuple becomes \((N',H',source'\), \(target',guard',child',default',r',E',event',action')\), where

  • \(N'=BN' \cup AN' \cup ON'\), where

    • \(BN'=BN \cup \{~\text {init}_O\}\)

    • \(AN'=AN\)

    • \(ON'=ON\)

  • \(child'=child \cup \{(\text {init}_O,O)\}\)

  • \(default'=default \cup \{(O,\text {init}_O)\}\)

  • \(E'=\emptyset \)

  • \(event'=\emptyset \)

  • \(action'=\emptyset \)

The first refactoring rule processes hyperedges that enter the OR node \(O\) that was processed in T3.

Definition 22

(Refactoring-1) Let \((N,H,source,target\), \(guard,child,default,r,event,action)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine. Let \(h \in H\) be a hyperedge.

Condition. The initialization rule has been applied. Node \(O\) was processed in T3. A target node of \(h\) is contained in \(O\), so there is a BASIC node \(n\in target(h)\) such that \(child^*(n,O)\).

Effect. The state machine tuple becomes \((N',H',source'\), \(target',guard',child',default',r',event',action')\), where

  • \(H'=H \cup \{\text {copy}_h\}\)

  • \(source'= source \cup \{(\text {copy}_h,\text {init}_O)\}\)

  • \(target'= (target\, \cup \, \{(\text {copy}_h,X)\}) \oplus \{(h,target(h){\setminus } X) \}\)

  • \(E'=E \cup \{\text {event}_h\}\)

  • \(event'=event \cup \{(\text {copy}_h,\text {event}_h)\}\)

  • \(action'=action \cup \{(h,\text {event}_h)\}\)

where \(X=\{~n~|~n \in target(h)\wedge child^*(n,O)\})\).

In the definition of \(target\), operator \(\oplus \) denotes function overriding.

The second refactoring rule processes hyperedges that leave the OR node \(O\) that was processed in T3.

Definition 23

(Refactoring-2) Let \((N,H,source,target\), \(guard,child,default,r,event, action)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine. Let \(h \in H\) be a hyperedge.

Condition. The initialization rule has been applied. Node \(O\) was processed in T3. A source node of \(h\) is contained in \(O\), so there is a BASIC node \(n\in source(h)\) such that \(child^*(n,O)\).

Effect. The state machine tuple becomes \((N', H', source'\), \( target', guard', child', default', r', E', event', action')\), where

  • \(H'=H \cup \{\text {copy}_h\}\)

  • \(source'= (source \cup \{(\text {copy}_h,X)\}) \oplus \{(h,source(h){\setminus } X) \}\)

  • \(target'= target \cup \{\text {copy}_h,(\text {init}_O)\}\)

  • \(guard'=guard \oplus \{h \mapsto g ~|~g=guard(h) \wedge \bigwedge _{x \in X}{}(x)\}\)

  • \(E'=E \cup \{\text {event}_h\}\)

  • \(event'=event \cup \{(\text {copy}_h,\text {event}_h)\}\)

  • \(action'=action \cup \{(h,\text {event}_h)\}\)

where \(X=\{~n~|~n \in source(h)\wedge child^*(n,O)\})\).

1.5 Correctness

We prove the transformation from filtered activity diagrams to state machines correct for a subset of activity diagrams. We first introduce auxiliary definitions.

Definition 24

(Minimal areas) Let \(AD=(A,O,C\), \(E,guard,instate)\) be a filtered activity diagram such that no edge \((x,y) \) connects two fork/join nodes, so \(E \cap (FJ \times FJ)=\emptyset \). An area is a set \(X \subseteq A \cup O \cup C\) such that for each \(x \in X\),

  • if \(x \in FJ\) then \(in(x)\subseteq X \iff out(x)\subseteq X\);

  • if \(x \not \in FJ\) then \(in(x) \cup out(x) \subseteq X\).

A minimal area for a set \(Y \subseteq A \cup O \cup C\) of nodes is an area \(X\) such that \(Y \subseteq X\) and \(X\) is minimal, so for each area \(Z\), if \(Z \subset X\) then \(Y \not \subseteq Z\).

For instance, for Fig. 5, the minimal area for {} is set {, }, while the minimal area for {,} is the set of successor nodes upto and including the merge node.

Definition 25

(Consistent areas) Let \(AD=(A,O,C,E\), \(guard,instate)\) be an activity diagram such that no edge \((x,y) \) connects two fork/join nodes, so \(E \cap (FJ \times FJ)=\emptyset \). A fork/join node \(n \in FJ\) has consistent areas if for each pair of disjoints set \(X,Y\) such that \(X,Y \subseteq in(n) \) or \(X,Y \subseteq out(n) \) the minimal areas of \(X\) and \(Y\) are disjoint. Activity diagram \(AD\) has consistent areas if each fork/join node \(n \in FJ\) has consistent areas.

For instance, the activity diagram in Fig. 5 has consistent areas. For example, the minimal areas for sets {} and {, } are disjoint.

The activity diagram in Fig. 14 does not have consistent areas. The minimal areas for sets { and {} overlap, since both contain . Also, the activity diagram in Fig. 16a does not have consistent areas: the minimal area for {} is a subset of the minimal area for {}, which is the entire set of nodes minus the fork.

Theorem 1

Let \(AD=(A,O,C,E,guard,instate)\) be a filtered activity diagram, so \(A=\emptyset \) and let \(SC=(N,H,source,target,guard,child,default,r)\) be the state machine that results by applying the transformation rules T1, T2, and T3. If \(AD\) has consistent areas, then \(AD\) and \(SC\) have equivalent behavior.

Proof

Activity diagram \(AD\) maps into a marked Petri net \(PN=(P,T,F,M)\) where

  • \(P= (O \cup C ) {\setminus } FJ\)

  • \(T= FJ \cup \{t_{(x,y)} | (x,y) \in E \wedge x,y \not \in FJ \}\)

  • \(F= \{(x,y)| (x,y) \in E \wedge ((x \in FJ \wedge y \not \in FJ ) \vee (x \not \in FJ \wedge y \in FJ)) \}\) \(\cup \, \{(x,t_{(x,y)}),(t_{(x,y)},y) | (x,y) \in E \wedge x,y \not \in FJ \} \)

  • \(M=\{(i,1)\} \cup \{(x,0)|x \in P{{\setminus }}\{i\}\}\)

The definition states that every node in \((O \cup C) {\setminus } FJ\) maps to a Petri net place. Every node in \(FJ\) and every edge \(e \in E\) that is not incident to a fork or a join maps to a Petri net transition. For every edge that connects two nodes in \(FJ\), a place is created. The flow relation \(F\) is defined accordingly.

Elsewhere [10] we have defined transformation rules T1 and T2 plus the notion of areas in the context of Petri nets. There, we proved that that if \(PN\) has consistent areas and the areas are nestable, so for every pair of overlapping areas \(X,Y\) either \(X \subseteq Y\) or \(Y \subseteq X\), then applying transformation rules T1 and T2 to \(PN=(P,T,F,M)\) results in a state machine \(SC\) that has equivalent behavior, in the sense that the reachable markings of \(PN\) are isomorphic to the reachable configurations of \(SC\).

We now argue that if rule T3 has been applied, the behavior of the filtered activity diagram is preserved in the refactored state machine. Let \(O\) be an OR node to which T3 is applied. Let \(f \in FJ\) be a fork node of which \(O\) is a target node in the reduced activity diagram. In the filtered activity diagram, if \(f\) is taken then all nodes in \(in(f)\) are left and all nodes in \(out(f)\) are entered. The state machine before refactoring contains a hyperedge \(f\) whose source set by construction (Def. 20) equals \(in(f)\) and whose target set equals \(out(f)\). Refactoring rule 1 ensures that when in the refactored state machine hyperedge \(f\) is taken, every BASIC node that is entered is in the target set of \(f\) before refactoring. Since \(AD\) has consistent areas, if \(in(f)\) is active, then no node in \(out(f)\) is active. Therefore, \(f\) only leaves BASIC nodes that are sources of \(f\) before refactoring, plus the fresh node \(init_O\). Therefore, when \(f\) is taken in the filtered activity diagram, the nodes left and entered correspond to the BASIC nodes left and entered when hyperedge \(f\) is taken in the refactored state machine.

Symmetrically, let \(j \in FJ\) be a join node of which \(O\) is a source node in the reduced activity diagram. Refactoring rule 2 ensures that when in the refactored state machine hyperedge \(j\) is taken, every BASIC node that is left is in the source set of \(j\) before refactoring, and every BASIC node that is entered is either in the target set of \(j\) before refactoring or \(init_O\). Because of the guard condition, \(j\) only leaves BASIC nodes that are sources of \(j\) before refactoring. Therefore, when \(j\) is taken in the filtered activity diagram, the nodes left and entered correspond to the BASIC nodes left and entered when hyperedge \(j\) is taken in the refactored state machine.

Consequently, the behavior of the refactored state machine corresponds to that of the filtered activity diagram. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Eshuis, R., Van Gorp, P. Synthesizing object life cycles from business process models. Softw Syst Model 15, 281–302 (2016). https://doi.org/10.1007/s10270-014-0406-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10270-014-0406-4

Keywords

Navigation