{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:37Z","timestamp":1778807917690,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"UZH Global Strategy and Partnerships Funding Scheme","award":["K-34112-02-01"],"award-info":[{"award-number":["K-34112-02-01"]}]},{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]},{"name":"NSF-SHF","award":["2312195"],"award-info":[{"award-number":["2312195"]}]},{"name":"NSF-IIS","award":["2314527"],"award-info":[{"award-number":["2314527"]}]},{"DOI":"10.13039\/501100006374","name":"Simons Institute for the Theory of Computing, University of California Berkeley","doi-asserted-by":"publisher","award":["Program on Logic and Algorithms in Databases and AI"],"award-info":[{"award-number":["Program on Logic and Algorithms in Databases and AI"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>We study the dynamic query evaluation problem: Given a full conjunctive query Q and a sequence of updates to the input database, we construct a data structure that supports constant-delay enumeration of the tuples in the query output after each update.<\/jats:p>\n          <jats:p>\n            We show that a sequence of N insert-only updates to an initially empty database can be executed in total time O(N\n            <jats:sup>w(Q)<\/jats:sup>\n            ), where w(Q) is the fractional hypertree width of Q. This matches the complexity of the static query evaluation problem for Q and a database of size N. One corollary is that the amortized time per single-tuple insert is constant for acyclic full conjunctive queries.\n          <\/jats:p>\n          <jats:p>\n            In contrast, we show that a sequence of N inserts and deletes can be executed in total time \u00d5(N\n            <jats:sup>w(Q')<\/jats:sup>\n            ), where Q' is obtained from Q by extending every relational atom with extra variables that represent the \"lifespans\" of tuples in the database. We show that this reduction is optimal in the sense that the static evaluation runtime of Q' provides a lower bound on the total update time for the output of Q. Our approach achieves amortized optimal update times for the hierarchical and Loomis-Whitney join queries.\n          <\/jats:p>","DOI":"10.1145\/3695837","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-26","source":"Crossref","is-referenced-by-count":5,"title":["Insert-Only versus Insert-Delete in Dynamic Query Evaluation"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"RelationalAI, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8155-8070","authenticated-orcid":false,"given":"Ahmet","family":"Kara","sequence":"additional","affiliation":[{"name":"OTH Regensburg, Regensburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--46678-0_5"},{"key":"e_1_2_1_2_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Mahmoud Abo Khamis George Chichirim Antonia Kormpa and Dan Olteanu. 2022. The Complexity of Boolean Conjunctive Queries with Intersection Joins. In PODS. 53--65. https:\/\/doi.org\/10.1145\/3517804.3524156","DOI":"10.1145\/3517804.3524156"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2017. What Do Shannon-Type Inequalities Submodular Width and Disjunctive Datalog Have to Do with One Another?. In PODS. 429--444. https:\/\/doi.org\/10.1145\/3034786.3056105","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2402.02001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_8_1","unstructured":"Anonymous Author(s). 20xx. Insert-Only versus Insert-Delete in Dynamic Query Evaluation. (20xx)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017. Answering Conjunctive Queries Under Updates. In PODS. 303--318. https:\/\/doi.org\/10.1145\/3034786.3034789","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587137"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000020"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212685"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137829"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.14"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Monika Henzinger Sebastian Krinninger Danupon Nanongkai and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In STOC. 21--30. https:\/\/doi.org\/10.1145\/2746539.2746609","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Muhammad Idris Mart\u00edn Ugarte and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD. 1259--1274. https:\/\/doi.org\/10.1145\/3035918.3064027","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00590--9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4614--8265--9_395"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2019.4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Ahmet Kara Milos Nikolic Dan Olteanu and Haozhe Zhang. 2020. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. In PODS. 375--392. https:\/\/doi.org\/10.1145\/3375395.3387646","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(3:11)2023"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-023-00817-W"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Christoph Koch. 2010. Incremental Query Evaluation in a Ring of Databases. In PODS. 87--98. https:\/\/doi.org\/10.1145\/1807085.1807100","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-013-0348--4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Christoph Koch Daniel Lupei and Val Tannen. 2016. Incremental View Maintenance For Collection Programming. In PODS. 75--90. https:\/\/doi.org\/10.1145\/2902251.2902286","DOI":"10.1145\/2902251.2902286"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002--9904--1949-09320--510.1090\/S0002--9904--1949-09320--5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ARTINT.2018.12.004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Hung Q. Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques Results and Open Problems. In PODS. 111--124. https:\/\/doi.org\/10.1145\/3196959.3196990","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610519"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Milos Nikolic and Dan Olteanu. 2018. Incremental View Maintenance with Triple Lock Factorization Benefits. In SIGMOD. 365--380. https:\/\/doi.org\/10.1145\/3183713.3183758","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Milos Nikolic Haozhe Zhang Ahmet Kara and Dan Olteanu. 2020. F-IVM: Learning over Fast-Evolving Relational Data. In SIGMOD. 2773--2776. https:\/\/doi.org\/10.1145\/3318464.3384702","DOI":"10.1145\/3318464.3384702"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Mihai Patrascu. 2010. Towards Polynomial Lower Bounds for Dynamic Problems. In STOC. 603--610. https:\/\/doi.org\/10.1145\/1806689.1806772","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442322.3442325"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool Publishers. https:\/\/doi.org\/10.2200\/S00362ED1V01Y201105DTM016","DOI":"10.2200\/S00362ED1V01Y201105DTM016"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2021.09.004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/ICDT.2014.13"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Qichen Wang and Ke Yi. 2020. Maintaining Acyclic Foreign-Key Joins under Updates. In SIGMOD. 1225--1239. https:\/\/doi.org\/10.1145\/3318464.3380586","DOI":"10.1145\/3318464.3380586"},{"key":"e_1_2_1_46_1","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. 82--94."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695837","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695837","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:31:57Z","timestamp":1755916317000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695837"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695837"],"URL":"https:\/\/doi.org\/10.1145\/3695837","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}