Towards Parameterized Hardness on Maintaining Conjunctive Queries
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-26
DOI: 10.1145/3801917 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Qichen Wang. Die Arbeit nennt 38 Literaturangaben. Gefördert von: Ministry of Education, Singapore, Nanyang Technological University.
Abstract (Originalsprache)
We investigate the fine-grained complexity of dynamically maintaining the result of fixed self-join free conjunctive queries under single-tuple updates. Prior work shows that free-connex queries can be maintained in update time O (| D |δ) for some δ ∈ [0.5, 1], where | D | is the size of the current database. However, a gap remains between the best known upper bound of O (| D |) and lower bounds of Ω(| D | 0.5-∈ ) for any ∈ >> 0. We narrow this gap by introducing two structural parameters to quantify the dynamic complexity of a conjunctive query: the height k and the dimension d . We establish new fine-grained lower bounds showing that any algorithm maintaining a query with these parameters must incur update time Ω(| D |1-1/max( k,d )-∈), unless widely believed conjectures fail. These yield the first super-√| D | lower bounds for maintaining free-connex queries, and suggest the tightness of current algorithms when considering arbitrarily large k and d . Complementing our lower bounds, we identify a data-dependent parameter, the generalized H -index h ( D ), which is upper bounded by | D |1/ d , and design an efficient algorithm for maintaining star queries, a common class of height 2 free-connex queries. The algorithm achieves an instance-specific update time O ( h ( D ) d -1) with linear space O (| D |). This matches our parameterized lower bound and provides instance-specific performance in favorable cases.
Förderung
- Ministry of Education, Singapore
- Nanyang Technological University
Zitieren
APA
Wang, Q. (2026). Towards Parameterized Hardness on Maintaining Conjunctive Queries. Proceedings of the ACM on Management of Data, 4(2), 1-26. https://doi.org/10.1145/3801917
Vancouver
Wang Q. Towards Parameterized Hardness on Maintaining Conjunctive Queries. Proceedings of the ACM on Management of Data. 2026;4(2):1-26. doi:10.1145/3801917
BibTeX
@article{Wang2026,
author = {Wang, Qichen},
title = {Towards Parameterized Hardness on Maintaining Conjunctive Queries},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--26},
doi = {10.1145/3801917}
}
EUVIMED