{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:08Z","timestamp":1778807888348,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"Hong Kong Research Grant Council","award":["12200524, C2004-21GF, C2003-23Y"],"award-info":[{"award-number":["12200524, C2004-21GF, C2003-23Y"]}]},{"DOI":"10.13039\/501100006374","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","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":[[2025,6,9]]},"abstract":"<jats:p>This paper studies the hardness of maintaining self-join-free conjunctive queries over a dynamic database, where tuples can be inserted or deleted. The worst-case complexity of this problem under arbitrary updates has been well understood. It is known that most practical queries require \u03a9(\u221a|D|) maintenance time for each update to ensure O(1)-delay enumeration, barring a very restricted class of queries (known as \"q-hierarchical\" queries). Nonetheless, most real-world update sequences are not arbitrary, far away from the worst-case scenario; instead, they are so \"nice\" that queries can greatly benefit from their inherent structure in query maintenance. In this paper, we aim to understand the hardness of query maintenance under different update sequences, in particular, the insertion-only (or deletion-only), first-in-first-out (FIFO), arbitrarily worse sequences, as well as their \"mixed\" sequences. We first provide a comprehensive characterization of queries that can be maintained in O(1) time for O(1)-delay enumeration over FIFO sequences. Then, we address mixed sequences, which may exhibit insertion-only or FIFO patterns on subqueries but lack a specific pattern in totality, and introduce a structural dichotomy for determining whether the input query can be maintained in O(1) time for O(1)-delay enumeration over mixed sequences.<\/jats:p>","DOI":"10.1145\/3725254","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-25","source":"Crossref","is-referenced-by-count":2,"title":["Towards Update-Dependent Analysis of Query Maintenance"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695837"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_5_1","volume-title":"Computer Science Logic","author":"Bagan Guillaume","unstructured":"Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic. Springer Berlin Heidelberg, Berlin, Heidelberg, 208-222."},{"key":"e_1_2_1_6_1","first-page":"479","volume-title":"JACM","volume":"30","author":"Beeri C.","year":"1983","unstructured":"C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. 1983. On the desirability of acyclic database schemes. JACM, Vol. 30, 3 (1983), 479-513."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017. Answering Conjunctive Queries under Updates. In PODS. 303--318.","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_8_1","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2018. Answering UCQs under Updates and in the Presence of Integrity Constraints. In ICDT."},{"key":"e_1_2_1_9_1","unstructured":"Johann Brault-Baron. 2013. On the relevance of \u00e9num\u00e9ration: complexitye in propositional and first order logics. Ph.D. Dissertation. University of Caen."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Nofar Carmeli and Luc Segoufin. 2023. Conjunctive Queries With Self-Joins Towards a Fine-Grained Enumeration Complexity Analysis. In PODS. 277--289.","DOI":"10.1145\/3584372.3588667"},{"key":"e_1_2_1_11_1","first-page":"295","volume-title":"Foundations and Trends\u00ae in Databases","volume":"4","author":"Chirkova Rada","year":"2012","unstructured":"Rada Chirkova and Jun Yang. 2012. Materialized views. Foundations and Trends\u00ae in Databases, Vol. 4, 4 (2012), 295-405."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_14_1","volume-title":"Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks.","author":"Hanauer Kathrin","year":"2022","unstructured":"Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. 2022. Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Muhammad Idris Martin Ugarte and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD. 1259--1274.","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_17_1","volume-title":"28th International Conference on Database Theory.","author":"Kara Ahmet","year":"2024","unstructured":"Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2024. Tractable conjunctive queries over static and dynamic relations. In 28th International Conference on Database Theory."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915246"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405954"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380586"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:46Z","timestamp":1755904726000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725254"],"URL":"https:\/\/doi.org\/10.1145\/3725254","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}