{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:15:57Z","timestamp":1790846157731,"version":"4.1.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T00:00:00Z","timestamp":1638921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID - Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]},{"name":"Bijzonder Onderzoeksfonds (BOF) of Hasselt University","award":["BOF20ZAP02"],"award-info":[{"award-number":["BOF20ZAP02"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>Complex event recognition (CER) has emerged as the unifying field for technologies that require processing and correlating distributed data sources in real time. CER finds applications in diverse domains, which has resulted in a large number of proposals for expressing and processing complex events. Existing CER languages lack a clear semantics, however, which makes them hard to understand and generalize. Moreover, there are no general techniques for evaluating CER query languages with clear performance guarantees.<\/jats:p><jats:p>In this article, we embark on the task of giving a rigorous and efficient framework to CER. We propose a formal language for specifying complex events, called<jats:italic>complex event logic<\/jats:italic>(CEL), that contains the main features used in the literature and has a denotational and compositional semantics. We also formalize the so-called selection strategies, which had only been presented as by-design extensions to existing frameworks. We give insight into the language design trade-offs regarding the strict sequencing operators of CEL and selection strategies.<\/jats:p><jats:p>With a well-defined semantics at hand, we discuss how to efficiently process complex events by evaluating CEL formulas with unary filters. We start by introducing a formal computational model for CER, called<jats:italic>complex event automata<\/jats:italic>(CEA), and study how to compile CEL formulas with unary filters into CEA. Furthermore, we provide efficient algorithms for evaluating CEA over event streams using constant time per event followed by output-linear delay enumeration of the results.<\/jats:p>","DOI":"10.1145\/3485463","type":"journal-article","created":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T22:18:08Z","timestamp":1639001888000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["A Formal Framework for Complex Event Recognition"],"prefix":"10.1145","volume":"46","author":[{"given":"Alejandro","family":"Grez","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile &amp; Millennium Institute for Foundational Research on Data Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile &amp; Millennium Institute for Foundational Research on Data Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mart\u00edn","family":"Ugarte","sequence":"additional","affiliation":[{"name":"Millennium Institute for Foundational Research on Data Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7793-9049","authenticated-orcid":false,"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"UHasselt \u2013 Hasselt University, Diepenbeek, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","unstructured":"Apache. n.d. Apache FlinkCEP. Retrieved June 14 2021 from https:\/\/ci.apache.org\/projects\/flink\/flink-docs-release-1.13\/docs\/libs\/cep\/.","DOI":"10.1007\/978-3-319-63962-8_303-2"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"EsperTech. n.d. Esper Enterprise Edition Website. Retrieved January 28 2021 from http:\/\/www.espertech.com\/.","DOI":"10.37388\/CP2021\/v29n30a07"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872855"},{"key":"e_1_3_3_5_2","volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases: The Logical Level. Addison-Wesley."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0108-y"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376634"},{"key":"e_1_3_3_8_2","first-page":"255","volume-title":"Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A)","author":"Aho Alfred V.","year":"1990","unstructured":"Alfred V. Aho. 1990. Algorithms for finding patterns in strings. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). North Holland, 255\u2013300."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453869"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3117809"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.65"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.11.018"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15918-3_5"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872854"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3093742.3095106"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2356476"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000264"},{"key":"e_1_3_3_20_2","volume-title":"Proceedings of the 2007 Conference on Innovative Data Systems Research (CIDR\u201907)","author":"Barga Roger S.","year":"2007","unstructured":"Roger S. Barga, Jonathan Goldstein, Mohamed H. Ali, and Mingsheng Hong. 2007. Consistent streaming through time: A vision for event stream processing. In Proceedings of the 2007 Conference on Innovative Data Systems Research (CIDR\u201907). 363\u2013374."},{"key":"e_1_3_3_21_2","volume-title":"Transductions and Context-Free Languages","author":"Berstel Jean","year":"2013","unstructured":"Jean Berstel. 2013. Transductions and Context-Free Languages. Springer-Verlag."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.10.009"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970403"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1524\/itit.2009.9058"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410300214X"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Benjamin Carle and Paliath Narendran. 2009. On extended regular expressions. In Language and Automata Theory and Applications . Lecture Notes in Computer Science Vol. 5457. Springer 279\u2013289.","DOI":"10.1007\/978-3-642-00982-2_24"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2010.06.010"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335432"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2010403.2010410"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1658185.1658190"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1827418.1827427"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.03.056"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187677"},{"key":"e_1_3_3_34_2","volume-title":"A General Algebra and Implementation for Monitoring Event Streams","author":"Demers Alan","year":"2005","unstructured":"Alan Demers, Johannes Gehrke, Mingsheng Hong, Mirek Riedewald, and Walker White. 2005. A General Algebra and Implementation for Monitoring Event Streams. Technical Report. Cornell University."},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","unstructured":"Alan Demers Johannes Gehrke Mingsheng Hong Mirek Riedewald and Walker White. 2006. Towards expressive publish\/subscribe systems. In Proceedings of the 10th International Conference on Advances in Database Technology (EDBT\u201906) . 627\u2013644.","DOI":"10.1007\/11687238_38"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46146-9_54"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00557-w"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_3_3_42_2","first-page":"Article 5, 18 p","volume-title":"Proceedings of the 22nd International Conference on Database Theory (IDCT\u201919)","author":"Grez Alejandro","year":"2019","unstructured":"Alejandro Grez, Cristian Riveros, and Mart\u00edn Ugarte. 2019. A formal framework for complex event processing. In Proceedings of the 22nd International Conference on Database Theory (IDCT\u201919). Article 5, 18 pages."},{"key":"e_1_3_3_43_2","unstructured":"Alejandro Grez Cristian Riveros Mart\u00edn Ugarte and Stijn Vansummeren. 2020. On the expressiveness of languages for complex event recognition. In Proceedings of the 23rd International Conference on Database Theory (ICDT\u201920) . Article 15 17 pages. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.15"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/1537195"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497566"},{"key":"e_1_3_3_46_2","first-page":"213","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT\u201914)","author":"He Yeye","year":"2014","unstructured":"Yeye He, Siddharth Barman, and Jeffrey F. Naughton. 2014. On load shedding in complex event processing. In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914). 213\u2013224."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989304"},{"key":"e_1_3_3_48_2","article-title":"Algorithmic techniques for processing data streams","author":"Ikonomovska Elena","year":"2013","unstructured":"Elena Ikonomovska and Mariano Zelke. 2013. Algorithmic techniques for processing data streams. Dagstuhl Follow-ups 5 (2013), 237\u2013274.","journal-title":"Dagstuhl Follow-ups"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_3_3_50_2","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","year":"2013","unstructured":"Leonid Libkin. 2013. Elements of Finite Model Theory. Springer Science & Business Media."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989416"},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","unstructured":"D. Luckham. 1996. Rapide: A Language and Toolset for Simulation of Distributed Systems by Partial Orderings of Events . Technical Report. Computer Science Laboratory Stanford University.","DOI":"10.1090\/dimacs\/029\/18"},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","unstructured":"Konstantinos Mamouras Mukund Raghothaman Rajeev Alur Zachary G. Ives and Sanjeev Khanna. 2017. StreamQRE: Modular specification and efficient evaluation of quantitative queries over streaming data. In Proceedings of the 38th ACM SIGPLAN Conference on Progamming Language Design and Implementation (PLDI\u201917) . 693\u2013708 https:\/\/doi.org\/10.1145\/3140587.3062369","DOI":"10.1145\/3062341.3062369"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559867"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/65.283931"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.5555\/1515915.1515921"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328905.3329762"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1108\/09685220810862733"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/1619258.1619264"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39274-0_3"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265567"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142520"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593671"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847253"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485463","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:15Z","timestamp":1750188615000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,8]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485463"],"URL":"https:\/\/doi.org\/10.1145\/3485463","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,8]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}