DBScholar

Back to papers

Answering Conjunctive Queries under Updates

Summary: Defines q‑hierarchical conjunctive queries: linear preprocessing yields a structure enabling constant‑delay enumeration and constant‑time updates/restarts under tuple insertions/deletions. Provides tight dichotomies: non‑q‑hierarchical (self‑join‑free/Boolean/counting) queries provably lack sublinear update/delay (OMv/OV lower bounds). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1706
Venue
PODS
Year
2017
Pagerank
0.0001551856
Overall Rank
636 | 95.64%
DOI
10.1145/3034786.3034789

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{berkholz_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Answering Conjunctive Queries under Updates}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034789},
        doi = {10.1145/3034786.3034789},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Berkholz, Christoph and Keppeler, Jens and Schweikardt, Nicole},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
816 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013827772
2,468 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.5358494e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-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,063 Enumeration for FO Queries over Nowhere Dense Graphs 2018 PODS 6.9307541e-05
4,097 Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates 2018 PODS 6.9038261e-05
4,371 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.738679e-05
4,985 Change Propagation Without Joins 2023 VLDB 6.412102e-05
5,066 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.3771079e-05
5,383 Compressed Representations of Conjunctive Query Results 2018 PODS 6.2374576e-05
5,579 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 6.1637419e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-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
7,195 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.6765621e-05
7,335 Reservoir Sampling over Joins 2024 SIGMOD 5.64193e-05
7,558 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.5993651e-05
7,574 CORE: a Complex Event Recognition Engine 2022 VLDB 5.5938402e-05
7,850 Differentially Private Data Release over Multiple Tables 2023 PODS 5.5316993e-05
8,235 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4608734e-05
8,673 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.3872753e-05
8,691 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.3839057e-05
8,924 Efficient Enumeration for Annotated Grammars 2022 PODS 5.3483178e-05
9,184 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.3058708e-05
9,719 Subset Sampling over Joins 2026 PODS 5.2319816e-05
9,819 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.214913e-05
9,845 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.2094004e-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,174 A Unifying Algorithm for Hierarchical Queries 2026 PODS 5.093636e-05
10,183 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 5.093636e-05
10,342 Approximate Query Processing under Updates 2026 SIGMOD 5.093636e-05
10,448 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 5.093636e-05
10,636 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 5.093636e-05
10,641 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 5.093636e-05
11,121 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 5.093636e-05
11,140 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
411 Worst-case Optimal Join Algorithms 2012 PODS 0.00018902089
954 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00012997301
1,041 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012453494
1,699 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.975915e-05
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
2,448 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 8.5693075e-05
Previous Page 1 / 1 Next

Semantically Similar Papers