Towards Update-Dependent Analysis of Query Maintenance

Summary: Update-aware maintenance of self-join-free conjunctive queries in dynamic DBs; shifts from worst-case to practical update patterns. Characterizes O(1) maintenance with O(1)-delay enumeration for FIFO updates; reveals a dichotomy for mixed sequences. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2020
Venue: PODS
Year: 2025
Pagerank: 5.2094004e-05
Overall Rank: 9,845 | 32.46%
DOI: 10.1145/3725254

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (University of Waterloo)
2. Qichen Wang (Hong Kong Baptist University)

BibTeX Citation

@inproceedings{hu_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Towards Update-Dependent Analysis of Query Maintenance}},
        url = {https://dl.acm.org/doi/10.1145/3725254},
        doi = {10.1145/3725254},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiao and Wang, Qichen},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
61	Maintaining Views Incrementally	1993	SIGMOD	0.00039026867
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
3,087	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.7702906e-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,985	Change Propagation Without Joins	2023	VLDB	6.412102e-05
5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	6.064817e-05
6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.9107433e-05
6,732	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.7885064e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
2	9,819	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
3	10,342	Approximate Query Processing under Updates	2026	SIGMOD
4	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD
6	10,160	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
7	5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
8	6,732	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS
9	636	Answering Conjunctive Queries under Updates	2017	PODS
10	10,170	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS