{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:40:07Z","timestamp":1757310007858},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>\n            Modern application domains such as Composite Event Recognition (CER) and real-time Analytics require the ability to dynamically refresh query results under high update rates. Traditional approaches to this problem are based either on the materialization of subresults (to avoid their recomputation) or on the recomputation of subresults (to avoid the space overhead of materialization). Both techniques have recently been shown suboptimal: instead of materializing results and subresults, one can maintain a data structure that supports efficient maintenance under updates and can quickly enumerate the full query output, as well as the changes produced under single updates. Unfortunately, these data structures have been developed only for aggregate-join queries composed of equi-joins, limiting their applicability in domains such as CER where temporal joins are commonplace. In this paper, we present a new approach for dynamically evaluating queries with multi-way\n            <jats:italic>\u03b8<\/jats:italic>\n            -joins under updates that is effective in avoiding both materialization and recomputation of results, while supporting a wide range of applications. To do this we generalize Dynamic Yannakakis, an algorithm for dynamically processing acyclic equi-join queries. In tandem, and of independent interest, we generalize the notions of acyclicity and free-connexity to arbitrary\n            <jats:italic>\u03b8<\/jats:italic>\n            -joins. We instantiate our framework to the case where\n            <jats:italic>\u03b8<\/jats:italic>\n            -joins are only composed of equalities and inequalities (&lt;, \u2264, =, &gt;, \u2265) and experimentally compare this algorithm, called IEDyn, to state of the art CER systems as well as incremental view maintenance engines. IEDyn performs consistently better than the competitor systems with up to two orders of magnitude improvements in both time and memory consumption.\n          <\/jats:p>","DOI":"10.14778\/3192965.3192966","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T19:56:10Z","timestamp":1527018970000},"page":"733-745","source":"Crossref","is-referenced-by-count":10,"title":["Conjunctive queries with inequalities under updates"],"prefix":"10.14778","volume":"11","author":[{"given":"Muhammad","family":"Idris","sequence":"first","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles &amp; TU Dresden"}]},{"given":"Mart\u00edn","family":"Ugarte","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}]},{"given":"Hannes","family":"Voigt","sequence":"additional","affiliation":[{"name":"TU Dresden"}]},{"given":"Wolfgang","family":"Lehner","sequence":"additional","affiliation":[{"name":"TU Dresden"}]}],"member":"320","published-online":{"date-parts":[[2018,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of databases","author":"Abiteboul S.","year":"1995"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376634"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28608-0_16"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(81)90002-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247620"},{"key":"e_1_2_1_10_1","volume-title":"Complex event processing. IT-Information Technology Methoden und innovative Anwendungen der Informatik und Informationstechnik","author":"Buchmann A.","year":"2009"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2009","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368962"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1827418.1827427"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.03.056"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187677"},{"key":"e_1_2_1_16_1","first-page":"443","volume-title":"VLDB Conference","author":"DeWitt D. J.","year":"1991"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007645"},{"key":"e_1_2_1_18_1","unstructured":"EsperTech. Esper complex event processing engine. http:\/\/www.espertech.com\/.  EsperTech. Esper complex event processing engine. http:\/\/www.espertech.com\/."},{"key":"e_1_2_1_19_1","volume-title":"production systems, and computer-integrated manufacturing","author":"Groover M. P.","year":"2007"},{"key":"e_1_2_1_20_1","first-page":"562","volume-title":"VLDB Conference","author":"Hellerstein J. M.","year":"1995"},{"key":"e_1_2_1_21_1","unstructured":"M. Idris. Queries in sase tesla esper and sql for dbt\/iedyn expression. http:\/\/cs.ulb.ac.be\/~midris\/iedyn.html.  M. Idris. Queries in sase tesla esper and sql for dbt\/iedyn expression. http:\/\/cs.ulb.ac.be\/~midris\/iedyn.html."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0441-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559867"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915246"},{"key":"e_1_2_1_28_1","volume-title":"SIGMOD 2018","author":"Nikolic M.","year":"2018"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1108\/09685220810862733"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1619258.1619264"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1107499.1107504"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142520"},{"key":"e_1_2_1_37_1","first-page":"82","volume-title":"VLDB Conference","author":"Yannakakis M.","year":"1981"},{"key":"e_1_2_1_38_1","first-page":"416","volume-title":"VLDB Conference","author":"Yoshikawa M.","year":"1984"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593671"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3192965.3192966","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:14:23Z","timestamp":1672226063000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3192965.3192966"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.14778\/3192965.3192966"],"URL":"https:\/\/doi.org\/10.14778\/3192965.3192966","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}