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
1987
Venue
PODS
Year
2024
Pagerank
5.7885064e-05
Overall Rank
6,732 | 53.82%
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
9,845 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.2094004e-05
10,148 Size Bound-Adorned Datalog 2026 PODS 5.093636e-05
10,160 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 5.093636e-05
10,170 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 5.093636e-05
10,342 Approximate Query Processing under Updates 2026 SIGMOD 5.093636e-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
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
438 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00018471721
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
816 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013827772
960 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00012945163
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
2,059 LINVIEW: Incremental View Maintenance for Complex Analytical Queries 2014 SIGMOD 9.2471145e-05
3,136 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.7210541e-05
3,206 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6367549e-05
4,609 F-IVM: Learning over Fast-Evolving Relational Data 2020 SIGMOD 6.6081313e-05
4,865 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 6.4731692e-05
4,985 Change Propagation Without Joins 2023 VLDB 6.412102e-05
5,988 Complex Event Recognition in the Big Data Era 2017 VLDB 6.0177874e-05
6,193 Incremental View Maintenance For Collection Programming 2016 PODS 5.9471978e-05
6,332 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.9107433e-05
7,451 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6135032e-05
Previous Page 1 / 1 Next

Semantically Similar Papers