Графовые паттерны в несогласованных декларативных моделях процессов

Декларативные модели процессов широко используются в process mining для гибкого описания поведения процессов с помощью наборов ограничений. Однако модели, автоматически извлекаемые из журналов событий, могут содержать несогласованные ограничения, что затрудняет их интерпретацию и делает их непригодными для исполнения, проверки соответствия или дальнейшего анализа. Существующие методы анализа согласованности либо опираются на автоматные конструкции с высокой асимптотической сложностью в худшем случае, либо используют эвристики, ориентированные на минимальные несогласованные подмножества (MIS), которые не дают полного формального описания обнаруживаемых ими паттернов несогласованности. В данной работе предлагается графовый подход к анализу несогласованности для ограниченного фрагмента языка Declare. Мы представляем зависимости между ограничениями с помощью графа следования задач и характеризуем несогласованность посредством трёх типов структурных свидетелей. На основе этого описания мы сначала выявляем кандидаты в несогласованные подмножества, а затем проверяем, является ли кандидат минимальным несогласованным подмножеством, с помощью специализированных процедур верификации. В отличие от подходов, основанных на автоматах, предлагаемый метод избегает явного построения произведений автоматов и вместо этого опирается на графовый анализ и конструктивное построение трасс. Мы реализовали предложенный подход и провели его экспериментальную оценку на реальных журналах событий, показав, что он практически применим и обеспечивает конкурентоспособное время работы.

1. W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, 2011.

2. W. M. P. van der Aalst, M. L. Rosa, and F. M. Santoro, “Business Process Management,” Business & Information Systems Engineering, vol. 58, no. 1, pp. 1–6, 2016.

3. M. Pesic, H. Schonenberg, and W. M. P. van der Aalst, “Declare: Full Support for Loosely-Structured Processes,” in Proceedings of the 11th IEEE International Enterprise Distributed Object Computing Conference (EDOC), 2007, pp. 287–300.

4. W. M. P. van der Aalst, M. Pesic, and H. Schonenberg, “Declarative Workflows: Balancing between Flexibility and Support,” Computer Science - Research and Development, vol. 23, no. 2, pp. 99–113, 2009.

5. F. M. Maggi, R. P. J. C. Bose, and W. M. P. van der Aalst, “Efficient Discovery of Understandable Declarative Process Models from Event Logs,” in Proceedings of the International Conference on Advanced Information Systems Engineering, 2012, pp. 270–285.

6. C. D. Ciccio and M. Mecella, “On the Discovery of Declarative Control Flows for Artful Processes,” ACM Transactions on Management Information Systems, vol. 5, no. 4, pp. 24:1–24:37, 2015.

7. C. D. Ciccio, F. M. Maggi, M. Montali, and J. Mendling, “Resolving Inconsistencies and Redundancies in Declarative Process Models,” Information Systems, vol. 64, pp. 425–443, 2017.

8. C. Corea, M. Deisen, and P. Delfmann, “Resolving Inconsistencies in Declarative Process Models Based on Culpability Measurement,” in Proceedings of the 14th International Conference on Wirtschaftsinformatik (WI), 2019, pp. 1–16.

9. A. P. Sistla and E. M. Clarke, “The Complexity of Propositional Linear Temporal Logics,” Journal of the ACM, vol. 32, no. 3, pp. 733–749, 1985.

10. C. Corea, J. Grant, and M. Thimm, “Measuring inconsistency in declarative process specifications,” in Proceedings of the International Conference on Business Process Management, 2022, pp. 289–306.

11. A. Hunter and S. Konieczny, “Measuring Inconsistency through Minimal Inconsistent Sets,” in Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), 2008, pp. 358–366.

12. C. D. Ciccio and M. Montali, “Declarative Process Specifications,” in Process Mining Handbook, Springer, 2022, pp. 119–147.

13. F. M. Maggi, M. Westergaard, M. Montali, and W. M. P. van der Aalst, “Runtime Verification of LTL-Based Declarative Process Models,” in Runtime Verification, in Lecture Notes in Computer Science, vol. 7186. 2012, pp. 131–146.

14. M. de Leoni, F. M. Maggi, and W. M. P. van der Aalst, “Aligning Event Logs and Declarative Process Models for Conformance Checking,” in Business Process Management, in Lecture Notes in Computer Science, vol. 7481. Springer, 2012, pp. 82–97.

15. M. Montali, F. Chesani, P. Mello, and F. M. Maggi, “Towards Data-Aware Constraints in Declare,” in Proceedings of the 28th Annual ACM Symposium on Applied Computing, 2013, pp. 1391–1396.

16. D. Borrego and I. Barba, “Conformance Checking and Diagnosis for Declarative Business Process Models in Data-Aware Scenarios,” Expert Systems with Applications, vol. 41, no. 11, pp. 5340–5352, 2014.

17. A. Burattin, F. M. Maggi, and A. Sperduti, “Conformance Checking Based on Multi-Perspective Declarative Process Models,” Expert Systems with Applications, vol. 65, pp. 194–211, 2016.

18. G. D. Giacomo, R. D. Masellis, M. Grasso, F. M. Maggi, and M. Montali, “Monitoring Business Metaconstraints Based on LTL and LDL for Finite Traces,” in Business Process Management, in Lecture Notes in Computer Science, vol. 8659. 2014, pp. 1–17.

19. A. Alman, C. D. Ciccio, D. Haas, F. M. Maggi, and J. Mendling, “Rule Mining in Action: The RuM Toolkit,” in Proceedings of the ICPM Doctoral Consortium and Tool Demonstration Track 2020, in CEUR Workshop Proceedings, vol. 2703. 2020, pp. 51–54.

20. I. Donadello, F. Riva, F. M. Maggi, and A. Shikhizada, “Declare4Py: A Python Library for Declarative Process Mining,” in BPM 2022 Demos & Resources Forum, in CEUR Workshop Proceedings, vol. 3216. 2022, pp. 117–121.

21. I. Kuhlmann, C. Corea, and J. Grant, “An ASP-Based Framework for Solving Problems Related to Declarative Process Specifications,” in Proceedings of the 21st International Workshop on Nonmonotonic Reasoning, 2023, pp. 129–132.

22. N. Sch"utzenmeier, M. K"appel, L. Ackermann, S. Jablonski, and S. Petter, “Automaton-Based Comparison of Declare Process Models,” Software and Systems Modeling, vol. 22, pp. 667–685, 2023.