{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:58:03Z","timestamp":1760147883697,"version":"build-2065373602"},"reference-count":59,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T00:00:00Z","timestamp":1678233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Newcastle University"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>A temporal model describes processes as a sequence of observable events characterised by distinguishable actions in time. Conformance checking allows these models to determine whether any sequence of temporally ordered and fully-observable events complies with their prescriptions. The latter aspect leads to Explainable and Trustworthy AI, as we can immediately assess the flaws in the recorded behaviours while suggesting any possible way to amend the wrongdoings. Recent findings on conformance checking and temporal learning lead to an interest in temporal models beyond the usual business process management community, thus including other domain areas such as Cyber Security, Industry 4.0, and e-Health. As current technologies for accessing this are purely formal and not ready for the real world returning large data volumes, the need to improve existing conformance checking and temporal model mining algorithms to make Explainable and Trustworthy AI more efficient and competitive is increasingly pressing. To effectively meet such demands, this paper offers KnoBAB, a novel business process management system for efficient Conformance Checking computations performed on top of a customised relational model. This architecture was implemented from scratch after following common practices in the design of relational database management systems. After defining our proposed temporal algebra for temporal queries (xtLTLf), we show that this can express existing temporal languages over finite and non-empty traces such as LTLf. This paper also proposes a parallelisation strategy for such queries, thus reducing conformance checking into an embarrassingly parallel problem leading to super-linear speed up. This paper also presents how a single xtLTLf operator (or even entire sub-expressions) might be efficiently implemented via different algorithms, thus paving the way to future algorithmic improvements. Finally, our benchmarks highlight that our proposed implementation of xtLTLf (KnoBAB) outperforms state-of-the-art conformance checking software running on LTLf logic.<\/jats:p>","DOI":"10.3390\/info14030173","type":"journal-article","created":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T01:35:37Z","timestamp":1678325737000},"page":"173","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quickening Data-Aware Conformance Checking through Temporal Algebras"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1844-0851","authenticated-orcid":false,"given":"Giacomo","family":"Bergami","sequence":"first","affiliation":[{"name":"School of Computing, Faculty of Science, Agriculture and Engineering, Newcastle University, Newcastle Upon Tyne NE4 5TG, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2608-0881","authenticated-orcid":false,"given":"Samuel","family":"Appleby","sequence":"additional","affiliation":[{"name":"School of Computing, Faculty of Science, Agriculture and Engineering, Newcastle University, Newcastle Upon Tyne NE4 5TG, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0089-0395","authenticated-orcid":false,"given":"Graham","family":"Morgan","sequence":"additional","affiliation":[{"name":"School of Computing, Faculty of Science, Agriculture and Engineering, Newcastle University, Newcastle Upon Tyne NE4 5TG, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/170036.170072","article-title":"Mining Association Rules between Sets of Items in Large Databases","volume":"22","author":"Agrawal","year":"1993","journal-title":"SIGMOD Rec."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bergami, G., Maggi, F.M., Montali, M., and Pe\u00f1aloza, R. (November, January 31). Probabilistic Trace Alignment. Proceedings of the 2021 3rd International Conference on Process Mining (ICPM), Eindhoven, The Netherlands.","DOI":"10.1109\/ICPM53251.2021.9576856"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Sch\u00f6n, O., van Huijgevoort, B., Haesaert, S., and Soudjani, S. (2022, January 6\u20139). Correct-by-Design Control of Parametric Stochastic Systems. Proceedings of the 2022 IEEE 61st Conference on Decision and Control, Cancun, Mexico.","DOI":"10.1109\/CDC51059.2022.9992723"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Appleby, S., Bergami, G., and Morgan, G. (2022, January 22\u201324). Running Temporal Logical Queries on the Relational Model. Proceedings of the International Database Engineered Applications Symposium (IDEAS\u201922), Budapest, Hungary.","DOI":"10.1145\/3548785.3548786"},{"key":"ref_5","unstructured":"Sch\u00f6nig, S., Rogge-Solti, A., Cabanillas, C., Jablonski, S., and Mendling, J. (2016). Advanced Information Systems Engineering, Proceedings of the 28th International Conference, CAiSE 2016, Ljubljana, Slovenia, 13\u201317 June 2016, Springer."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/j.eswa.2016.08.040","article-title":"Conformance checking based on multi-perspective declarative process models","volume":"65","author":"Burattin","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Pesic, M., Schonenberg, H., and van der Aalst, W.M.P. (2007, January 15\u201319). DECLARE: Full Support for Loosely-Structured Processes. Proceedings of the 11th IEEE International Enterprise Distributed Object Computing Conference, Annapolis, MA, USA.","DOI":"10.1109\/EDOC.2007.14"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","article-title":"Introspective Sorting and Selection Algorithms","volume":"27","author":"Musser","year":"1997","journal-title":"Softw. Pract. Exp."},{"key":"ref_9","unstructured":"Bellatreche, L., Kechar, M., and Bahloul, S.N. (2021, January 14\u201316). Bringing Common Subexpression Problem from the Dark to Light: Towards Large-Scale Workload Optimizations. Proceedings of the 25th International Database Engineering & Applications Symposium, Montreal, QC, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-540-30232-2_23","article-title":"A Temporal Logic Based Framework for Intrusion Detection","volume":"Volume 3235","year":"2004","journal-title":"Proceedings of the Formal Techniques for Networked and Distributed Systems\u2014FORTE 2004: 24th IFIP WG 6.1 International Conference"},{"key":"ref_11","unstructured":"Ray, I. (2021). Security Vulnerabilities in Smart Contracts as Specifications in Linear Temporal Logic. [Master\u2019s Thesis, University of Waterloo]."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Buschj\u00e4ger, S., Hess, S., and Morik, K. (March, January 22). Shrub Ensembles for Online Classification. Proceedings of the the AAAI Conference on Artificial Intelligence 2022, Virtual.","DOI":"10.1609\/aaai.v36i6.20560"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"117176","DOI":"10.1016\/j.eswa.2022.117176","article-title":"A dynamic soft sensor of industrial fuzzy time series with propositional linear temporal logic","volume":"201","author":"Huo","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_14","unstructured":"Bergami, G., Francescomarino, C.D., Ghidini, C., Maggi, F.M., and Puura, J. (2021). Exploring Business Process Deviance with Sequential and Declarative Patterns. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"358","DOI":"10.3390\/jcp2020019","article-title":"The State of Ethereum Smart Contracts Security: Vulnerabilities, Countermeasures, and Tool Support","volume":"2","author":"Zhou","year":"2022","journal-title":"J. Cybersecur. Priv."},{"key":"ref_16","first-page":"28","article-title":"Smart contracts: Building blocks for digital markets","volume":"18","author":"Szabo","year":"1996","journal-title":"Extropy J. Transhumanist Thought"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Fionda, V., Greco, G., and Mastratisi, M.A. (2021, January 1\u20133). Reasoning About Smart Contracts Encoded in LTL. Proceedings of the AIxIA 2021\u2014Advances in Artificial Intelligence: 20th International Conference of the Italian Association for Artificial Intelligence, Virtual Event.","DOI":"10.1007\/978-3-031-08421-8_9"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1016\/j.promfg.2018.07.159","article-title":"Temporal Logic (TL)-Based Autonomy for Smart Manufacturing Systems","volume":"26","author":"Bank","year":"2018","journal-title":"Procedia Manuf."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4393","DOI":"10.1109\/TII.2021.3123194","article-title":"Programmable Logic Controllers Past Linear Temporal Logic for Monitoring Applications in Industrial Control Systems","volume":"18","author":"Mao","year":"2022","journal-title":"IEEE Trans. Ind. Informatics"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1007\/s00778-021-00655-8","article-title":"Unsupervised and scalable subsequence anomaly detection in large data series","volume":"30","author":"Boniol","year":"2021","journal-title":"Vldb J."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1186\/s12911-020-01323-7","article-title":"Modeling clinical activities based on multi-perspective declarative process mining with openEHR\u2019s characteristic","volume":"20-S","author":"Xu","year":"2020","journal-title":"BMC Med. Inform. Decis. Mak."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"9236","DOI":"10.1016\/j.eswa.2015.07.040","article-title":"Declarative process mining in healthcare","volume":"42","author":"Rovani","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1109\/JPROC.2018.2791463","article-title":"Predicting Frailty Condition in Elderly Using Multidimensional Socioclinical Databases","volume":"106","author":"Bertini","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"De Giacomo, G., Maggi, F.M., Marrella, A., and Patrizi, F. (2017, January 4\u20139). On the Disruptive Effectiveness of Automated Planning for LTLf-Based Trace Alignment. Proceedings of the AAAI Conference on Artificial Intelligence 2017, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11020"},{"key":"ref_25","unstructured":"Bergami, G., Maggi, F.M., Marrella, A., and Montali, M. (2021). Business Process Management, Springer International Publishing."},{"key":"ref_26","unstructured":"Bergami, G. (2021). A Logical Model for joining Property Graphs. arXiv."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Zhu, S., Pu, G., and Vardi, M.Y. (2019). First-Order vs. Second-Order Encodings for LTLf-to-Automata Translation. arXiv.","DOI":"10.1007\/978-3-030-14812-6_43"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1109\/TSE.1985.232223","article-title":"Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries","volume":"11","author":"Ceri","year":"1985","journal-title":"IEEE Trans. Software Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1145\/1189769.1189770","article-title":"Expressive power of an algebra for data mining","volume":"31","author":"Calders","year":"2006","journal-title":"ACM Trans. Database Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"103369","DOI":"10.1016\/j.artint.2020.103369","article-title":"SAT-based explicit LTLf satisfiability checking","volume":"289","author":"Li","year":"2020","journal-title":"Artif. Intell."},{"key":"ref_31","unstructured":"Petermann, A., Junghanns, M., M\u00fcller, R., and Rahm, E. (2014, January 5\u20136). FoodBroker-Generating Synthetic Datasets for Graph-Based Business Analytics. Proceedings of the 5th International Workshop, WBDB 2014, Potsdam, Germany."},{"key":"ref_32","unstructured":"Bergami, G. (2021). On Declare MAX-SAT and a finite Herbrand Base for data-aware logs. arXiv."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Pichler, P., Weber, B., Zugal, S., Pinggera, J., Mendling, J., and Reijers, H.A. (2011, January 29). Imperative versus Declarative Process Modeling Languages: An Empirical Investigation. Proceedings of the BPM 2011 International Workshops, Clermont-Ferrand, France.","DOI":"10.1007\/978-3-642-28108-2_37"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","article-title":"A Relational Model of Data for Large Shared Data Banks","volume":"13","author":"Codd","year":"1970","journal-title":"Commun. ACM"},{"key":"ref_35","first-page":"40","article-title":"MonetDB: Two Decades of Research in Column-oriented Database Architectures","volume":"35","author":"Idreos","year":"2012","journal-title":"IEEE Data Eng. Bull."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1648","DOI":"10.14778\/1687553.1687618","article-title":"Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct","volume":"2","author":"Boncz","year":"2009","journal-title":"Proc. VLDB Endow."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/49346.49347","article-title":"Extended Algebra and Calculus for Nested Relational Databases","volume":"13","author":"Roth","year":"1988","journal-title":"ACM Trans. Database Syst."},{"key":"ref_38","unstructured":"Wang, J., Ntarmos, N., and Triantafillou, P. (2017, January 21\u201324). GraphCache: A Caching System for Graph Queries. Proceedings of the International Conference on Extending Database Technology (EDBT) 2017, Venice, Italy."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s007780050014","article-title":"A Predicate-based Caching Scheme for Client-Server Database Architectures","volume":"5","author":"Keller","year":"1996","journal-title":"VLDB J."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Davey, B.A., and Priestley, H.A. (2002). Introduction to Lattices and Order, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511809088"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M.J., and Overmars, M.H. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_42","unstructured":"Elmasri, R., and Navathe, S.B. (2015). Fundamentals of Database Systems, Pearson. [7th ed.]."},{"key":"ref_43","unstructured":"Polyvyanyy, A., ter Hofstede, A.H.M., Rosa, M.L., Ouyang, C., and Pika, A. (2019). Process Query Language: Design, Implementation, and Evaluation. arXiv."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","article-title":"Optimal Scheduling for Two-Processor Systems","volume":"1","author":"Coffman","year":"1972","journal-title":"Acta Inform."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","article-title":"Methods for Visual Understanding of Hierarchical System Structures","volume":"11","author":"Sugiyama","year":"1981","journal-title":"IEEE Trans. Syst. Man. Cybern."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Bergami, G. (2021, January 14\u201316). On Efficiently Equi-Joining Graphs. Proceedings of the 25th International Database Engineering & Applications Symposium 2021, Montreal, QC, Canada.","DOI":"10.1145\/3472163.3472269"},{"key":"ref_47","unstructured":"Dittrich, J. (2016). Patterns in Data Management: A Flipped Textbook, CreateSpace Independent Publishing Platform."},{"key":"ref_48","unstructured":"Sch\u00f6nig, S. (2015). SQL Queries for Declarative Process Mining on Event Logs of Relational Databases. arXiv."},{"key":"ref_49","unstructured":"Shoshany, B. (2021). A C++17 Thread Pool for High-Performance Scientific Computing. arXiv."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Klemm, M., and Cownie, J. (2021). High Performance Parallel Runtimes, De Gruyter Oldenbourg.","DOI":"10.1515\/9783110632729"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Ristov, S., Prodan, R., Gusev, M., and Skala, K. (2016, January 11\u201314). Superlinear speedup in HPC systems: Why and when?. Proceedings of the 2016 Federated Conference on Computer Science and Information Systems (FedCSIS), Gda\u0144sk, Poland.","DOI":"10.15439\/2016F498"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.parco.2018.03.007","article-title":"Superlinear speedup phenomenon in parallel 3D Discrete Element Method (DEM) simulations of complex-shaped particles","volume":"75","author":"Yan","year":"2018","journal-title":"Parallel Comput."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1016\/0167-8191(95)00026-K","article-title":"An experience with super-linear speedup achieved by parallel computing on a workstation cluster: Parallel calculation of density of states of large scale cyclic polyacenes","volume":"21","author":"Nagashima","year":"1995","journal-title":"Parallel Comput."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1109\/TKDE.2011.170","article-title":"Extending BCDM to Cope with Proposals and Evaluations of Updates","volume":"25","author":"Anselma","year":"2013","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_55","unstructured":"Desai, B.C., and Cho, W. (2020, January 12\u201314). Hierarchical embedding for DAG reachability queries. Proceedings of the IDEAS 2020: 24th International Database Engineering & Applications Symposium, Seoul, Republic of Korea."},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Revesz, P.Z. (2010). Introduction to Databases\u2014From Biological to Spatio-Temporal, Springer. Texts in Computer Science.","DOI":"10.1007\/978-1-84996-095-3"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Revesz, P. (2010). Introduction to Databases: From Biological to Spatio-Temporal, Springer.","DOI":"10.1007\/978-1-84996-095-3"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Zaki, N.M., Helal, I.M.A., Awad, A., and Hassanein, E.E. (2022). Efficient Checking of Timed Order Compliance Rules over Graph-encoded Event Logs. arXiv.","DOI":"10.1007\/978-3-031-21595-7_11"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00778-021-00667-4","article-title":"Distributed temporal graph analytics with GRADOOP","volume":"31","author":"Rost","year":"2022","journal-title":"VLDB J."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/14\/3\/173\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:51:17Z","timestamp":1760122277000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/14\/3\/173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,8]]},"references-count":59,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["info14030173"],"URL":"https:\/\/doi.org\/10.3390\/info14030173","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2023,3,8]]}}}