DBScholar

Back to papers

Insert-Only versus Insert-Delete in Dynamic Query Evaluation

Summary: Dynamic query evaluation for full conjunctive Q under updates; insert-only sequences on an empty DB incur O(N^{w(Q)}) total time, matching static evaluation and yielding constant amortized inserts for alpha-acyclic Q. Allowing inserts and deletes, reduce to Q_hat by encoding tuple lifespans; total time O~(N^{w(Q_hat)}), tight via static evaluation of Q_hat, achieving amortized optimal updates for hierarchical and Loomis–Whitney joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hcb84e8b7009f92e1
Venue
PODS
Year
2024
Pagerank
5.6586279e-05
Overall Rank
6,876 | 53.78%
DOI
10.1145/3695837

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{khamis_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Insert-Only versus Insert-Delete in Dynamic Query Evaluation}},
        url = {https://dl.acm.org/doi/10.1145/3695837},
        doi = {10.1145/3695837},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Khamis, Mahmoud Abo and Kara, Ahmet and Olteanu, Dan and Suciu, Dan},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
10,028 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0925155e-05
10,365 Size Bound-Adorned Datalog 2026 PODS 4.9793485e-05
10,377 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9793485e-05
10,387 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9793485e-05
10,544 Approximate Query Processing under Updates 2026 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
408 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00018900199
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015341557
812 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013729015
978 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00012731074
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
2,087 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.068879e-05
3,112 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6357579e-05
3,187 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5546613e-05
3,673 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.1092596e-05
4,699 F-IVM: Learning over Fast-Evolving Relational Data 2020 SIGMOD 6.4633894e-05
5,057 Change Propagation Without Joins 2023 VLDB 6.2927647e-05
6,101 Complex Event Recognition in the Big Data Era 2017 VLDB 5.8868179e-05
6,219 Incremental View Maintenance For Collection Programming 2016 PODS 5.8471493e-05
6,386 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8040725e-05
6,955 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6342744e-05
Previous Page 1 / 1 Next

Semantically Similar Papers