TY - CHAP A1 - Abo Khamis, Mahmoud A1 - Kara, Ahmet A1 - Olteanu, Dan A1 - Suciu, Dan T1 - Insert-Only versus Insert-Delete in Dynamic Query Evaluation T2 - Proceedings of the ACM on Management of Data N2 - We study the dynamic query evaluation problem: Given a full conjunctive query 𝑄 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.We show that a sequence of 𝑁 insert-only updates to an initially empty database can be executed in total time O(𝑁 w(𝑄 ) ), where w(𝑄) is the fractional hypertree width of 𝑄. This matches the complexity of the static query evaluation problem for 𝑄 and a database of size 𝑁 . One corollary is that the amortized time per single-tuple insert is constant for 𝛼-acyclic full conjunctive queries. In contrast, we show that a sequence of 𝑁 inserts and deletes can be executed in total time eO(𝑁 w( b𝑄 ) ), where b𝑄 is obtained from 𝑄 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 b𝑄 provides a lower bound on the total update time for the output of 𝑄. Our approach achieves amortized optimal update times for the hierarchical and Loomis-Whitney join queries. Y1 - 2024 U6 - https://doi.org/10.1145/3695837 VL - 2 IS - 5 SP - 1 EP - 26 PB - ACM ER -