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.6559492e-05
Overall Rank
6,881 | 53.76%
DOI
10.1145/3695837
PDF
Download (CC BY 4.0)

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,033 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0901047e-05
10,377 Size Bound-Adorned Datalog 2026 PODS 4.9769913e-05
10,389 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9769913e-05
10,399 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9769913e-05
10,555 Approximate Query Processing under Updates 2026 SIGMOD 4.9769913e-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.00021236408
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
408 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00018894165
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015334386
813 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013722638
977 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00012730241
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012068611
2,087 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.0661817e-05
3,114 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6321464e-05
3,188 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5510881e-05
3,675 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.1058941e-05
4,702 F-IVM: Learning over Fast-Evolving Relational Data 2020 SIGMOD 6.46033e-05
5,061 Change Propagation Without Joins 2023 VLDB 6.2897936e-05
6,103 Complex Event Recognition in the Big Data Era 2017 VLDB 5.8840311e-05
6,223 Incremental View Maintenance For Collection Programming 2016 PODS 5.8443814e-05
6,389 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8014043e-05
6,958 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6316072e-05
Previous Page 1 / 1 Next

Semantically Similar Papers