Causal Behavioural Profiles - Efficient Computation, Applications and Evaluation

• Autorzy: Weidlich M. , Mendling J. , Polyvyanyy A. , Weske M.
• Języki publikacji: EN

Abstrakty

EN

Analysis of behavioural consistency is an important aspect of software engineering. In process and service management, consistency verification of behavioural models has manifold applications. For instance, a business process model used as system specification and a corresponding workflow model used as implementation have to be consistent. Another example would be the analysis to what degree a process log of executed business operations is consistent with the corresponding normative process model. Typically, existing notions of behaviour equivalence, such as bisimulation and trace equivalence, are applied as consistency notions. Still, these notions are exponential in computation and yield a Boolean result. In many cases, however, a quantification of behavioural deviation is needed along with concepts to isolate the source of deviation. In this article, we propose causal behavioural profiles as the basis for a consistency notion. These profiles capture essential behavioural information, such as order, exclusiveness, and causality between pairs of activities of a process model. Consistency based on these profiles is weaker than trace equivalence, but can be computed efficiently for a broad class of models. In this article, we introduce techniques for the computation of causal behavioural profiles using structural decomposition techniques for sound free-choice workflow systems if unstructured net fragments are acyclic or can be traced back to S- or T-nets. We also elaborate on the findings of applying our technique to three industry model collections.

Słowa kluczowe

EN

causal behavioural profiles; formal methods; behavioural abstraction; Structural Decompositions; exclusiveness; concurrency; order relations; causality; optionality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 3/4
• Strony: 399--435
• Opis fizyczny: Bibliogr. 76 poz., wykr.

Twórcy

autor

Weidlich M.

autor

Mendling J.

autor

Polyvyanyy A.

autor

Weske M.

• Hasso Plattner Institute, Univ. of Potsdam, Prof.-Dr.-Helmert-Str. 2-3, 14482 Potsdam, Germany,

Bibliografia

• [1] van der Aalst, W. M. P.: Verification of Workflow Nets, ICATPN, 1248, 1997, 407-426.
• [2] van der Aalst, W. M. P.: The Application of Petri Nets to Workflow Management, Journal of Circuits, Systems, and Computers, 8(1), 1998, 21-66.
• [3] van der Aalst, W. M. P.: Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques, BPM, 1806, 2000, 161-183.
• [4] van der Aalst,W. M. P., Hirnschall, A., Verbeek, H. M.W.: An Alternative Way to Analyze Workflow Graphs, CAiSE, 2348, 2002, 535-552.
• [5] van der Aalst, W. M. P., Reijers, H. A., Weijters, A. J. M. M., van Dongen, B. F., de Medeiros, A. K. A., Song, M., Verbeek, H. M. W. E.: Business process mining: An industrial application, Inf. Syst., 32(5), 2007, 713-732.
• [6] van der Aalst, W. M. P., Weijters, T., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs, IEEE Trans. Knowl. Data Eng., 16(9), 2004, 1128-1142.
• [7] Alstrup, S., Harel, D., Lauridsen, P. W., Thorup, M.: Dominators in Linear Time, SIAM J. Comput., 28(6), 1999, 2117-2132.
• [8] Basten, T., van der Aalst, W. M. P.: Inheritance of Behavior, JLAP, 47(2), 2001, 47-145.
• [9] Battista, G. D., Tamassia, R.: On-Line Maintenance of Triconnected Components with SPQR-Trees, Algorithmica, 15(4), 1996, 302-318.
• [10] Best, E.: Structure Theory of Petri Nets: the Free Choice Hiatus, Advances in Petri Nets (W. Brauer, W. Reisig, G. Rozenberg, Eds.), 254, Springer, 1986, ISBN 3-540-17905-4, 168-205.
• [11] Brauer,W., Gold, R., Vogler,W.: A survey of behaviour and equivalence preserving refinements of Petri nets, Applications and Theory of Petri Nets (G. Rozenberg, Ed.), 483, Springer, 1989, ISBN 3-540-53863-1, 1-46.
• [12] Bravetti, M., Bultan, T., Eds.: Web Services and Formal Methods - 7th International Workshop, WS-FM 2010, Hoboken, NJ, USA, September 16-17, 2010. Revised Selected Papers, vol. 6551 of Lecture Notes in Computer Science, Springer, 2011, ISBN 978-3-642-19588-4.
• [13] Curran, T. A., Keller, G., Ladd, A.: SAP R/3 Business Blueprint: Understanding the Business Process Reference Model, Prentice-Hall, 1997.
• [14] Davies, I., Green, P., Rosemann, M., Indulska, M., Gallo, S.: How Do Practitioners Use Conceptual Modeling in Practice?, Data Knowl. Eng., 58(3), 2006, 358-380.
• [15] Dayal, U., Eder, J., Koehler, J., Reijers, H. A., Eds.: Business Process Management, 7th International Conference, BPM 2009, Ulm, Germany, September 8-10, 2009. Proceedings, vol. 5701 of Lecture Notes in Computer Science, Springer, 2009, ISBN 978-3-642-03847-1.
• [16] Decker, G., Mendling, J.: Process Instantiation, Data Knowl. Eng., 68, 2009.
• [17] Desel, J., Esparza, J.: Free Choice Petri Nets, Cambridge University Press, 1995, ISBN 0-521-46519-2.
• [18] Dijkman, R., Dumas, M., Garc´ıa-Ba˜nuelos, L., Käärik, R.: Aligning Business Process Models, 13th International IEEE Enterprise Distributed Object Computing Conference (ECOC), 2009.
• [19] Dijkman, R. M., Dumas, M., Ouyang, C.: Semantics and analysis of business process models in BPMN, Information & Software Technology, 50(12), 2008, 1281-1294.
• [20] van Dongen, B., Jansen-Vullers, M., Verbeek, H., van der Aalst, W. M. P.: Verification of the SAP reference models using EPC reduction, state space analysis, and invariants, Computers in Industry, 58(6), 2007, 578-601.
• [21] van Dongen, B. F., Dijkman, R. M., Mendling, J.: Measuring Similarity between Business Process Models, CAiSE (Z. Bellahsene, M. Léonard, Eds.), 5074, Springer, 2008, ISBN 978-3-540-69533-2, 450-464.
• [22] Dumas, M., Garc´ıa-Ba˜nuelos, L., Dijkman, R. M.: Similarity Search of Business Process Models, IEEE Data Eng. Bull., 32(3), 2009, 23-28.
• [23] Dwyer, M. B., Avrunin, G. S., Corbett, J. C.: Property Specification Patterns for Finite-State Verification, FMSP (M. A. Ardis, J. M. Atlee, Eds.), ACM, 1998, ISBN 0-89791-954-8, 7-15.
• [24] Eshuis, R., Wieringa, R.: Tool Support for Verifying UML Activity Diagrams, IEEE Trans. Software Eng., 30(7), 2004, 437-447.
• [25] Esparza, J., Heljanko, K.: Unfoldings: a partial-order approach to model checking, Springer, 2008.
• [26] Esparza, J., Silva, M.: Circuits, Handles, Bridges and Nets, Applications and Theory of Petri Nets, 483, 1989, ISBN 0-387-53863-1, 210-242.
• [27] Euzenat, J., Shvaiko, P.: Ontology Matching, Springer-Verlag, 2007.
• [28] Fahland, D., Favre, C., Jobstmann, B., Koehler, J., Lohmann, N., Völzer, H., Wolf, K.: Instantaneous Soundness Checking of Industrial Business Process Models, in: Dayal et al. [15], 278-293, 278-293.
• [29] van Glabbeek, R. J.: Handbook of Process Algebra, chapter The Linear Time - Brancing Time Spectrum I. The semantics of concrete, sequential processes, Elsevier, 2001.
• [30] van Glabbeek, R. J., Goltz, U.: Refinement of Actions and Equivalence Notions for Concurrent Systems, Acta Inf., 37(4/5), 2001, 229-327.
• [31] Goedertier, S., Martens, D., Vanthienen, J., Baesens, B.: Robust Process Discovery with Artificial Negative Events, Journal of Machine Learning Research, 10, 2009, 1305-1340.
• [32] Greco, G., Guzzo, A., Pontieri, L., Sacc`a, D.: Discovering Expressive Process Models by Clustering Log Traces, IEEE Trans. Knowl. Data Eng., 18(8), 2006, 1010-1027.
• [33] Gschwind, T., Koehler, J., Wong, J.: Applying Patterns during Business Process Modeling, BPM'08: Proceedings of the 6th International Conference on Business Process Management, Springer-Verlag, Berlin, Heidelberg, 2008, ISBN 978-3-540-85757-0, 4-19.
• [34] Gutwenger, C., Mutzel, P.: A Linear Time Implementation of SPQR-Trees, Graph Drawing, 1984, 2001, ISBN 3-540-41554-8, 77-90.
• [35] Johnson, R., Pearson, D., Pingali, K.: The Program Structure Tree: Computing Control Regions in Linear Time, PLDI, 1994, 171-185.
• [36] Kiepuszewski, B., ter Hofstede, A. H. M., van der Aalst, W. M. P.: Fundamentals of Control Flow in Workflows, Acta Inf., 39(3), 2003, 143-209.
• [37] Kiepuszewski, B., ter Hofstede, A. H. M., Bussler, C.: On StructuredWorkflow Modelling, CAiSE (B. Wangler, L. Bergman, Eds.), 1789, Springer, 2000, ISBN 3-540-67630-9, 431-445.
• [38] Kindler, E.: On the semantics of EPCs: A Framework for Resolving the Vicious Circle, BPM, 3080, 2004, 82-97.
• [39] Kovalyov, A., Esparza, J.: A Polynomial Algorithm to Compute the Concurrency Relation of Free-Choice Signal Transition Graphs, Prof. of the International Workshop on Discrete Event Systems, WODES'96, The Institution of Electrical Engineers, Edinburgh, 1996, 1-6.
• [40] Küster, J., Gerth, C., Förster, A., Engels, G.: Detecting and Resolving Process Model Differences in the Absence of a Change Log, BPM, 5240, 2008, 244-260.
• [41] Li, C., Reichert, M., Wombacher, A.: On Measuring Process Model Similarity Based on High-Level Change Operations, ER (Q. Li, S. Spaccapietra, E. S. K. Yu, A. Olivé, Eds.), 5231, Springer, 2008, ISBN 978-3-540-87876-6, 248-264.
• [42] Lohmann, N.: A Feature-Complete Petri Net Semantics for WS-BPEL 2.0, WS-FM, 4937, 2008, 77-91.
• [43] Lohmann, N., Verbeek, E., Dijkman, R. M.: Petri Net Transformations for Business Processes - A Survey, T. Petri Nets and Other Models of Concurrency, 2, 2009, 46-63.
• [44] McMillan, K. L.: A Technique of State Space Search Based on Unfolding, Formal Methods in System Design, 6(1), 1995, 45-65.
• [45] de Medeiros, A. K. A., van der Aalst, W. M. P., Weijters, A. J. M. M.: Quantifying Process Equivalence based on Observed Behavior, Data Knowl. Eng., 64(1), 2008.
• [46] Mendling, J.: Metrics for Process Models: Empirical Foundations of Verification, Error Prediction, and Guidelines for Correctness, vol. 6 of Lecture Notes in Business Information Processing, Springer, 2008, ISBN 978-3-540-89223-6.
• [47] Mendling, J., van Dongen, B. F., van der Aalst, W. M. P.: Getting rid of OR-joins and multiple start events in business process models, Enterprise IS, 2(4), 2008, 403-419.
• [48] Mendling, J., Verbeek, H. M. W., van Dongen, B. F., van der Aalst, W. M. P., Neumann, G.: Detection and prediction of errors in EPCs of the SAP reference model, Data Knowl. Eng., 64(1), 2008, 312-329.
• [49] Murata, T.: Petri nets: Properties, analysis and applications, Proceedings of the IEEE, 77(4), 1989, 541-580.
• [50] Nejati, S., Sabetzadeh, M., Chechik, M., Easterbrook, S. M., Zave, P.: Matching and Merging of Statecharts Specifications, ICSE, IEEE Computer Society, 2007, 54-64.
• [51] Pernici, B., Ed.: Advanced Information Systems Engineering, 22nd International Conference, CAiSE 2010, Hammamet, Tunisia, June 7-9, 2010. Proceedings, vol. 6051 of Lecture Notes in Computer Science, Springer, 2010, ISBN 978-3-642-13093-9.
• [52] Polyvyanyy, A., Garc´ıa-Ba˜nuelos, L., Dumas, M.: Structuring Acyclic Process Models, BPM (R. Hull, J. Mendling, S. Tai, Eds.), 6336, Springer, 2010, ISBN 978-3-642-15617-5, 276-293.
• [53] Polyvyanyy, A., Smirnov, S., Weske, M.: The Triconnected Abstraction of Process Models, in: Dayal et al. [15], 229-244, 229-244.
• [54] Polyvyanyy, A., Vanhatalo, J., Völzer, H.: Simplified Computation and Generalization of the Refined Process Structure Tree, in: Bravetti and Bultan [12], 25-41, 25-41.
• [55] Pomello, L., Rozenberg, G., Simone, C.: A survey of equivalence notions for net based systems, Advances in Petri Nets: The DEMON Project (G. Rozenberg, Ed.), 609, Springer, 1992, ISBN 3-540-55610-9, 410-472.
• [56] Rahm, E., Bernstein, P. A.: A survey of approaches to automatic schema matching, VLDB Journal, 10(4), 2001, 334-350.
• [57] Rosenblum, L. Y., Yakovlev, A.: Analyzing Semantics of Concurrent Hardware Specifications, ICPP (3), 1989, 211-218.
• [58] Rozinat, A., van der Aalst, W. M. P.: Conformance checking of processes based on monitoring real behavior, Inf. Syst., 33(1), 2008, 64-95.
• [59] Schrefl, M., Stumptner, M.: Behavior-consistent Specialization of Object Life Cycles, ACM Trans. Softw. Eng. Methodol., 11(1), 2002, 92-148.
• [60] Vanhatalo, J., Völzer, H., Koehler, J.: The Refined Process Structure Tree, BPM, 5240, 2008, 100-115.
• [61] Vanhatalo, J., Völzer, H., Koehler, J.: The Refined Process Structure Tree, Data and Knowledge Engineering (DKE), 68(9), 2009, 793-818.
• [62] Vanhatalo, J., Völzer, H., Leymann, F.: Faster and More Focused Control-Flow Analysis for Business Process Models Through SESE Decomposition, ICSOC, 4749, 2007, 43-55.
• [63] Vanhatalo, J., Völzer, H., Leymann, F., Moser, S.: Automatic Workflow Graph Refactoring and Completion, ICSOC (A. Bouguettaya, I. Krüger, T. Margaria, Eds.), 5364, 2008, ISBN 978-3-540-89647-0, 100-115.
• [64] Weidlich, M., Dijkman, R. M., Mendling, J.: The ICoP Framework: Identification of Correspondences between Process Models, in: Pernici [51], 483-498, 483-498.
• [65] Weidlich, M., Elliger, F., Weske, M.: Generalised Computation of Behavioural Profiles Based on Petri-Net Unfoldings, in: Bravetti and Bultan [12], 101-115, 101-115.
• [66] Weidlich, M., Mendling, J., Weske, M.: Efficient Consistency Measurement Based on Behavioral Profiles of Process Models, IEEE Trans. Software Eng., 37(3), 2011, 410-429.
• [67] Weidlich, M., Polyvyanyy, A., Desai, N., Mendling, J.: Process Compliance Measurement Based on Behavioural Profiles, in: Pernici [51], 499-514, 499-514.
• [68] Weidlich, M., Polyvyanyy, A., Desai, N., Mendling, J., Weske, M.: Process compliance analysis based on behavioural profiles, Inf. Syst., 36(7), 2011, 1009-1025.
• [69] Weidlich, M., Polyvyanyy, A., Mendling, J., Weske, M.: Efficient Computation of Causal Behavioural Profiles Using Structural Decomposition, Petri Nets (J. Lilius, W. Penczek, Eds.), 6128, Springer, 2010, ISBN 978-3-642-13674-0, 63-83.
• [70] Weidlich, M., Weske, M., Mendling, J.: Change Propagation in Process Models Using Behavioural Profiles, IEEE SCC, IEEE Computer Society, 2009, 33-40.
• [71] Weidlich, M., Ziekow, H., Mendling, J.: Optimising Complex Event Queries over Business Processes Using Behavioural Profiles, Business Process Management Workshops (M. zur Muehlen, J. Su, Eds.), 66, Springer, 2010, ISBN 978-3-642-20510-1, 743-754.
• [72] Weidlich, M., Ziekow, H., Mendling, J., Günther, O., Weske, M., Desai, N.: Event-based Monitoring of Process Execution Violations, Proceedings of the 9th International Conference on Business Process Management (BPM 2011) (S. Rinderle, F. Toumani, K. Wolf, Eds.), number 6896 in LNCS, Spring, 2011, 182-198, To appear.
• [73] Weijters, A. J. M. M., van der Aalst, W. M. P., de Medeiros, A. K. A.: Process Mining with the Heuristics Miner Algorithm, BETA Working Paper Series WP 166, Eindhoven University of Technology, Eindhoven, 2006.
• [74] Winskel, G.: Petri Nets, Algebras, Morphisms, and Compositionality, Inf. Comput., 72(3), 1987, 197-238.
• [75] Wombacher, A.: Evaluation of Technical Measures for Workflow Similarity Based on a Pilot Study, OTM Conferences (1) (R. Meersman, Z. Tari, Eds.), 4275, Springer, 2006, ISBN 3-540-48287-3, 255-272.
• [76] Wombacher, A., Rozie, M.: Evaluation of Workflow Similarity Measures in Service Discovery, Service Oriented Electronic Commerce (M. Schoop, C. Huemer, M. Rebstock, M. Bichler, Eds.), 80, GI, 2006, ISBN 3-88579-174-9, 51-71.