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.6372471e-05
Overall Rank
6,900 | 53.75%
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,072 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0732737e-05
10,443 Size Bound-Adorned Datalog 2026 PODS 4.9605343e-05
10,455 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9605343e-05
10,465 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9605343e-05
10,620 Approximate Query Processing under Updates 2026 SIGMOD 4.9605343e-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
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
408 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00018836656
639 Answering Conjunctive Queries under Updates 2017 PODS 0.00015289346
815 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013682594
979 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00012697012
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
2,083 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.0563677e-05
3,122 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6091671e-05
3,199 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5261206e-05
3,684 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 7.0834345e-05
4,716 F-IVM: Learning over Fast-Evolving Relational Data 2020 SIGMOD 6.4389681e-05
5,080 Change Propagation Without Joins 2023 VLDB 6.2689958e-05
6,119 Complex Event Recognition in the Big Data Era 2017 VLDB 5.8645748e-05
6,213 Incremental View Maintenance For Collection Programming 2016 PODS 5.8312546e-05
6,397 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.7822506e-05
6,979 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6129856e-05
Previous Page 1 / 1 Next

Semantically Similar Papers