Discovering Object-centric Petri Nets

• Autorzy: van der Aalst, Wil M. P. , Berti, Alessandro
• Języki publikacji: EN

Abstrakty

EN

Techniques to discover Petri nets from event data assume precisely one case identifier per event. These case identifiers are used to correlate events, and the resulting discovered Petri net aims to describe the life-cycle of individual cases. In reality, there is not one possible case notion, but multiple intertwined case notions. For example, events may refer to mixtures of orders, items, packages, customers, and products. A package may refer to multiple items, multiple products, one order, and one customer. Therefore, we need to assume that each event refers to a collection of objects, each having a type (instead of a single case identifier). Such object-centric event logs are closer to data in real-life information systems. From an object-centric event log, we want to discover an object-centric Petri net with places that correspond to object types and transitions that may consume and produce collections of objects of different types. Object-centric Petri nets visualize the complex relationships among objects from different types. This paper discusses a novel process discovery approach implemented in PM4Py. As will be demonstrated, it is indeed feasible to discover holistic process models that can be used to drill-down into specific viewpoints if needed.

Słowa kluczowe

EN

multiple viewpoint models; Petri nets; process discovery; process mining

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 175, nr 1-4
• Strony: 1--40
• Opis fizyczny: Bibliogr. 63 poz., rys., tab., wykr.

Twórcy

autor

van der Aalst, Wil M. P.

• Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany,
• Fraunhofer Institute for Applied Information Technology, Sankt Augustin, Germany

autor

Berti, Alessandro

• Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany,
• Fraunhofer Institute for Applied Information Technology, Sankt Augustin, Germany

Bibliografia

• [1] Ehrenfeucht A, Rozenberg G. Partial (Set) 2-Structures - Part 1 and Part 2. Acta Informatica, 1989. 27(4):315-368. doi:10.1007/BF00264612.
• [2] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2015. doi:10.5555/2851516.
• [3] Badouel E, Darondeau P. Theory of Regions. In: Reisig W, Rozenberg G (eds.), Lectures on Petri Nets I: Basic Models, volume 1491 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1998 pp. 529-586. doi:10.1007/3-540-65306-6_22.
• [4] Desel J, Reisig W. The Synthesis Problem of Petri Nets. Acta Informatica, 1996. 33(4):297-315. doi:10.1007/s002360050046.
• [5] Kleijn J, Koutny M, Pietkiewicz-Koutny M, Rozenberg G. Applying Regions. Theoretical Computer Science, 2017. 658:205-215. doi:10.1016/j.tcs.2016.01.040.
• [6] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri Nets from Finite Transition Systems. IEEE Transactions on Computers, 1998. 47(8):859-882. doi:10.1109/12.707587.
• [7] Carmona J, Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. A Symbolic Algorithm for the Synthesis of Bounded Petri Nets. In: Applications and Theory of Petri Nets (Petri Nets 2008). 2008 pp. 92-111. doi:10.1007/978-3-540-68746-7_10.
• [8] Carmona J, Cortadella J, Kishinevsky M. New Region-Based Algorithms for Deriving Bounded Petri Nets. IEEE Transactions on Computers, 2010. 59(3):371-384. doi:10.1109/TC.2009.131.
• [9] Kleijn J, Koutny M, Pietkiewicz-Koutny M. Regions of Petri nets with a/sync connections. Theoretical Computer Science, 2012. 454:189-198. doi:10.1016/j.tcs.2012.04.016.
• [10] Darondeau P. On the Synthesis of Zero-Safe Nets. In: Concurrency, Graphs and Models, volume 5065 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2008 pp. 364-378. doi:10.1007/978-3-540-68679-8_25.
• [11] Bergenthum R, Desel J, Lorenz R, Mauser S. Process Mining Based on Regions of Languages. In: Alonso G, Dadam P, Rosemann M (eds.), International Conference on Business Process Management (BPM 2007), volume 4714 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2007 pp. 375-383. doi:10.1007/978-3-540-75183-0_27.
• [12] Lorenz R, Bergenthum R, Desel J, Mauser S. Synthesis of Petri Nets from Finite Partial Languages. In: Basten T, Juhás G, Shukla S (eds.), International Conference on Application of Concurrency to System Design (ACSD 2007). IEEE Computer Society, 2007 pp. 157-166. doi:10.1109/ACSD.2007.34.
• [13] Bergenthum R, Desel J, Lorenz R, Mauser S. Synthesis of Petri Nets from Finite Partial Languages. Fundamenta Informaticae, 2008. 88(4):437-468. doi:10.1109/ACSD.2007.34.
• [14] van Dongen B, Desel J, van der Aalst WMP. Aggregating Causal Runs into Workflow Nets. In: Jensen K, van der Aalst WMP, Marsan MA, Franceschinis G, Kleijn J, Kristensen L (eds.), Transactions on Petri Nets and Other Models of Concurrency (ToPNoC VI), volume 7400 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2012 pp. 334-363. doi:10.1007/978-3-642-35179-2_14.
• [15] Bergenthum R, Desel J, Mauser S, Lorenz R. Synthesis of Petri Nets from Term Based Representations of Infinite Partial Languages. Fundamenta Informaticae, 2009. 95(1):187-217. doi:10.3233/FI-2009-147.
• [16] Lorenz R, Juhás G. How to Synthesize Nets from Languages: A Survey. In: Henderson S, Biller B, Hsieh M, Shortle J, Tew JD, Barton RR (eds.), Proceedings of the Wintersimulation Conference (WSC 2007). IEEE Computer Society, 2007 pp. 637-647. doi:10.1109/WSC.2007.4419657.
• [17] Lorenz R, Juhas G. Towards Synthesis of Petri Nets from Scenarios. In: Donatelli S, Thiagarajan P (eds.), Application and Theory of Petri Nets 2006, volume 4024 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2006 pp. 302-321. doi:10.1007/11767589_17.
• [18] Bergenthum R, Desel J, Lorenz R, Mauser S. Synthesis of Petri Nets from Scenarios with VipTool. In: Applications and Theory of Petri Nets (Petri Nets 2008), volume 5062 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2008 pp. 388-398. doi:10.1007/978-3-540-68746-7_25.
• [19] Lorenz R, Desel J, Juhas G. Models from Scenarios. In: Jensen K, van der Aalst WMP, Balbo G, Koutny M, Wolf K (eds.), Transactions on Petri Nets and Other Models of Concurrency (ToPNoC VII), volume 7480 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2013 pp. 314-371. 10.1007/978-3-642-38143-0_9.
• [20] Carmona J, Cortadella J, Kishinevsky M. A Region-Based Algorithm for Discovering Petri Nets from Event Logs. In: Business Process Management (BPM 2008). 2008 pp. 358-373. doi:10.1007/978-3-540-85758-7_26.
• [21] Solé M, Carmona J. Process Mining from a Basis of State Regions. In: Lilius J, Penczek W (eds.), Applications and Theory of Petri Nets 2010, volume 6128 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2010 pp. 226-245. doi:10.1007/978-3-642-13675-7_14.
• [22] van Zelst S, van Dongen B, van der Aalst WMP, Verbeek H. Discovering Workflow Nets Using Integer Linear Programming. Computing, 2018. 100(5):529-556. doi:10.1007/s00607-017-0582-5.
• [23] van der Aalst WMP. A Practitioner’s Guide to Process Mining: Limitations of the Directly-Follows Graph. In: International Conference on Enterprise Information Systems (Centeris 2019), volume 164 of Procedia Computer Science. Elsevier, 2019 pp. 321-328. doi:10.1016/j.procs.2019.12.189.
• [24] Leemans S, Fahland D, van der Aalst WMP. Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour. In: Lohmann N, Song M, Wohed P (eds.), Business Process Management Workshops, Int. Workshop on Business Process Intelligence (BPI 2013), vol. 171 of Lecture Notes in Business Information Processing. Springer, 2014 pp. 66-78. doi:10.1007/978-3-319-06257-0_6.
• [25] Leemans S, Fahland D, van der Aalst WMP. Scalable Process Discovery with Guarantees. In: Gaaloul K, Schmidt R, Nurcan S, Guerreiro S, Ma Q (eds.), Enterprise, Business-Process and Information Systems Modeling (BPMDS 2015), volume 214 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2015 pp. 85-101. doi:10.1007/978-3-319-19237-6_6.
• [26] Augusto A, Conforti R, Marlon M, La Rosa M, Polyvyanyy A. Split Miner: Automated Discovery of Accurate and Simple Business Process Models from Event Logs. Knowledge Information Systems, 2019. 59(2):251-284. doi:10.1007/s10115-018-1214-x.
• [27] van der Aalst WMP. Object-Centric Process Mining: Dealing With Divergence and Convergence in Event Data. In: Ölveczky P, Salaün G (eds.), Software Engineering and Formal Methods (SEFM 2019), volume 11724 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2019 pp. 3-25. doi:10.1007/978-3-030-30446-1_1.
• [28] Li G, Medeiros de Carvalho R, van der Aalst WMP. Automatic Discovery of Object-Centric Behavioral Constraint Models. In: Abramowicz W (ed.), Business Information Systems (BIS 2017), volume 288 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2017 pp. 43-58. doi:10.1007/978-3-319-59336-4_4.
• [29] van Eck M, Sidorova N, van der Aalst WMP. Guided Interaction Exploration in Artifact-centric Process Models. In: IEEE Conference on Business Informatics (CBI 2017). IEEE Computer Society, 2017 pp. 109-118. doi:10.1109/CBI.2017.42.
• [30] van Eck M, Sidorova N, van der Aalst WMP. Multi-instance Mining: Discovering Synchronisation in Artifact-Centric Processes. In: Daniel F, Sheng Q, Motahari H (eds.), Business Process Management Workshops, International Workshop on Business Process Intelligence (BPI 2018), volume 342 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2018 pp. 18-30. doi:10.1007/978-3-030-11641-5_2.
• [31] Fahland D, de Leoni M, van Dongen B, van der Aalst WMP. Behavioral Conformance of Artifact-Centric Process Models. In: Abramowicz A (ed.), Business Information Systems (BIS 2011), volume 87 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2011 pp. 37-49. doi:10.1007/978-3-642-21863-7_4.
• [32] Fahland D, de Leoni M, van Dongen B, van der Aalst WMP. Many-to-Many: Some Observations on Interactions in Artifact Choreographies. In: Eichhorn D, Koschmider A, Zhang H (eds.), Proceedings of the 3rd Central-European Workshop on Services and their Composition (ZEUS 2011), CEUR Workshop Proceedings. CEUR-WS.org, 2011 pp. 9-15. URL: http://ceur-ws.org/Vol-705/paper1.pdf.
• [33] Lu X, Nagelkerke M, van de Wiel D, Fahland D. Discovering Interacting Artifacts from ERP Systems. IEEE Transactions on Services Computing, 2015. 8(6):861-873. doi:10.1109/TSC.2015.2474358.
• [34] van der Aalst WMP. Process Mining: Data Science in Action. 2016. doi:10.1007/978-3-662-49851-4_1.
• [35] IEEE Task Force on Process Mining. XES Standard Definition. www.xes-standard.org, 2013.
• [36] Lu X, Fahland D, van der Aalst WMP. Conformance Checking Based on Partially Ordered Event Data. In: Fournier F, Mendling J (eds.), Business Process Management Workshops, International Workshop on Business Process Intelligence (BPI 2014), volume 202 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2015 pp. 75-88. doi:10.1007/978-3-319-15895-2_7.
• [37] van der Aalst WMP, Stahl C. Modeling Business Processes: A Petri Net Oriented Approach. MIT Press, Cambridge, MA, 2011. ISBN: 978-0-262-01538-7.
• [38] Jensen K, Kristensen L. Coloured Petri Nets. Springer-Verlag, Berlin, 2009. doi:10.1007/b95112.
• [39] Berti A, van der Aalst WMP. StarStar Models: Using Events at Database Level for Process Analysis. In: Ceravolo P, Keulen M, Lopez MG (eds.), International Symposium on Data-driven Process Discovery and Analysis (SIMPDA 2018), volume 2270 of CEUR Workshop Proceedings. CEUR-WS.org, 2018 pp. 60-64. URL: http://ceur-ws.org/Vol-2270/short3.pdf.
• [40] Berti A, van der Aalst WMP. Discovering Multiple Viewpoint Models from Relational Databases. In: Ceravolo P, Keulen M, Lopez MG (eds.), Postproceedings International Symposium on Data-driven Process Discovery and Analysis, volume 379 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2020 pp. 24-51. doi:10.1007/978-3-030-46633-6_2.
• [41] Leemans S, Fahland D, van der Aalst WMP. Scalable Process Discovery and Conformance Checking. Software and Systems Modeling, 2018. 17(2):599-631. doi:10.1007/s10270-016-0545-x. doi:10.1007/s10270-016-0545-x.
• [42] Berti A, van der Aalst WMP. Reviving Token-based Replay: Increasing Speed While Improving Diagnostics. In: Proceedings of the International Workshop on Algorithms and Theories for the Analysis of Event Data (ATAED 2019), volume 2371 of CEUR Workshop Proceedings. CEUR-WS.org, 2019 pp. 87-103. URL: http://ceur-ws.org/Vol-2371/ATAED2019-87-103.pdf.
• [43] Rozinat A, van der Aalst WMP. Conformance Checking of Processes Based on Monitoring Real Behavior. Information Systems, 2008. 33(1):64-95. doi:10.1016/j.is.2007.07.001.
• [44] van der Aalst WMP. The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers, 1998. 8(1):21-66. doi:10.1142/S0218126698000043.
• [45] van der Aalst WMP, Hee K, ter Hofstede A, Sidorova N, Verbeek H, Voorhoeve M, Wynn M. Soundness of Workflow Nets: Classification, Decidability, and Analysis. Formal Aspects of Computing, 2011. 23(3):333-363. doi:10.1007/s00165-010-0161-4.
• [46] Leemans S, Fahland D, van der Aalst WMP. Discovering Block-structured Process Models from Event Logs: A Constructive Approach. In: Colom J, Desel J (eds.), Applications and Theory of Petri Nets 2013, volume 7927 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2013 pp. 311-329. doi:10.1007/978-3-642-38697-8_17.
• [47] OMG. Business Process Model and Notation (BPMN). Object Management Group, formal/2011-01-03, 2011. URL: https://www.omg.org/spec/BPMN/2.0/PDF.
• [48] Scheer A. Business Process Engineering: Reference Models for Industrial Enterprises. Springer-Verlag, Berlin, 1994. ISBN: 978-3-540-58234-2.
• [49] IBM. IBM MQSeries Workflow - Getting Started With Buildtime. IBM Deutschland Entwicklung GmbH, Boeblingen, Germany, 1999. URL: ftp://public.dhe.ibm.com/ps/products/workflow/docu/v322/pdf/enu/fmcu0mst.pdf.
• [50] van der Aalst WMP, ter Hofstede A, Kiepuszewski B, Barros A. Workflow Patterns. Distributed and Parallel Databases, 2003. 14(1):5-51. doi:10.1023/A:1022883727209.
• [51] van der Aalst WMP, Barthelmess P, Ellis C, Wainer J. Workflow Modeling using Proclets. In: Etzion O, Scheuermann P (eds.), 7th International Conference on Cooperative Information Systems (CoopIS 2000), volume 1901 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2000 pp. 198-209. doi:10.1007/10722620_20.
• [52] van der Aalst WMP, Barthelmess P, Ellis C, Wainer J. Proclets: A Framework for Lightweight Interacting Workflow Processes. International Journal of Cooperative Information Systems, 2001. 10(4):443-482. doi:10.1142/S0218843001000412.
• [53] Bhattacharya K, Gerede C, Hull R, Liu R, Su J. Towards Formal Analysis of Artifact-Centric Business Process Models. In: Alonso G, Dadam P, Rosemann M (eds.), International Conference on Business Process Management (BPM 2007), volume 4714 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2007 pp. 288-304. doi:10.1007/978-3-540-75183-0_21.
• [54] Cohn D, Hull R. Business Artifacts: A Data-centric Approach to Modeling Business Operations and Processes. IEEE Data Engineering Bulletin, 2009. 32(3):3-9. doi:10.1.1.183.76.
• [55] Lohmann N. Compliance by Design for Artifact-Centric Business Processes. In: Rinderle S, Toumani F, Wolf K (eds.), Business Process Management (BPM 2011), volume 6896 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2011 pp. 99-115. doi:10.1016/j.is.2012.07.003.
• [56] Nigam A, Caswell N. Business artifacts: An Approach to Operational Specification. IBM Systems Journal, 2003. 42(3):428-445. doi:10.1147/sj.423.0428.
• [57] Fahland D. Describing Behavior of Processes with Many-to-Many Interactions. In: Donatelli S, Haar S (eds.), Applications and Theory of Petri Nets 2019, volume 11522 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2019 pp. 3-24. doi:10.1007/978-3-030-21571-2_1.
• [58] de Murillas EGL, Reijers H, van der Aalst WMP. Connecting Databases with Process Mining: A Meta Model and Toolset. In: Schmidt R, Guedria W, Bider I, Guerreiro S (eds.), Enterprise, Business-Process and Information Systems Modeling (BPMDS 2015), volume 248 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2016 pp. 231-249. doi:10.1007/s10270-018-0664-7.
• [59] Li G, de Murillas EGL, de Carvalho RM, van der Aalst WMP. Extracting Object-Centric Event Logs to Support Process Mining on Databases. In: Mendling J, Mouratidis H (eds.), Information Systems in the Big Data Era, CAiSE Forum 2018, volume 317 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2018 pp. 182-199. doi:10.1007/978-3-319-92901-9_16.
• [60] van der Aalst WMP, Artale A, Montali M, Tritini S. Object-Centric Behavioral Constraints: Integrating Data and Declarative Process Modelling. In: Proceedings of the 30th International Workshop on Description Logics (DL 2017), volume 1879 of CEUR Workshop Proceedings. 2017 URL: http://ceur-ws.org/Vol-1879/paper51.pdf.
• [61] van der Aalst WMP, Li G, Montali M. Object-Centric Behavioral Constraints. CoRR, 2017. abs/1703.05740. URL: http://arxiv.org/abs/1703.05740.
• [62] Artale A, Calvanese D, Montali M, van der Aalst WMP. Enriching Data Models with Behavioral Constraints. In: Borgo S (ed.), Ontology Makes Sense (Essays in honor of Nicola Guarino). IOS Press, 2019 pp. 257-277. doi:10.3233/978-1-61499-955-3-257.
• [63] van der Aalst WMP, Pesic M, Schonenberg H. Declarative Workflows: Balancing Between Flexibility and Support. Computer Science - Research and Development, 2009. 23(2):99-113. doi:10.1007/s00450-009-0057-9.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu
"Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja
sportu (2020).

Identyfikatory

DOI

10.3233/FI-2020-1946