@inproceedings{AboKhamisKaraOlteanuetal., author = {Abo Khamis, Mahmoud and Kara, Ahmet and Olteanu, Dan and Suciu, Dan}, title = {Insert-Only versus Insert-Delete in Dynamic Query Evaluation}, series = {Proceedings of the ACM on Management of Data}, volume = {2}, booktitle = {Proceedings of the ACM on Management of Data}, number = {5}, publisher = {ACM}, doi = {10.1145/3695837}, pages = {1 -- 26}, abstract = {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.}, language = {en} }