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
hade2c75e815c4a2f
Venue
PODS
Year
2017
Pagerank
0.00015289346
Overall Rank
639 | 95.72%
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 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
815 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013682594
2,526 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3274934e-05
2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-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
4,173 Enumeration for FO Queries over Nowhere Dense Graphs 2018 PODS 6.7507874e-05
4,205 Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates 2018 PODS 6.7244719e-05
4,487 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5628751e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,080 Change Propagation Without Joins 2023 VLDB 6.2689958e-05
5,170 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2330027e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
5,512 Compressed Representations of Conjunctive Query Results 2018 PODS 6.0867282e-05
5,719 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 6.0026773e-05
6,397 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.7822506e-05
6,882 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.6412354e-05
6,900 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6372471e-05
7,361 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.528228e-05
7,490 Reservoir Sampling over Joins 2024 SIGMOD 5.499011e-05
7,724 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4530482e-05
7,738 CORE: a Complex Event Recognition Engine 2022 VLDB 5.4476676e-05
8,030 Differentially Private Data Release over Multiple Tables 2023 PODS 5.3871505e-05
8,300 Subset Sampling over Joins 2026 PODS 5.3434957e-05
8,855 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2486885e-05
8,859 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2481795e-05
9,114 Efficient Enumeration for Annotated Grammars 2022 PODS 5.208561e-05
9,398 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1672232e-05
10,048 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0786422e-05
10,072 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0732737e-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,469 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9605343e-05
10,477 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9605343e-05
10,620 Approximate Query Processing under Updates 2026 SIGMOD 4.9605343e-05
10,708 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 4.9605343e-05
10,955 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9605343e-05
11,150 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 4.9605343e-05
11,154 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 4.9605343e-05
11,527 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9605343e-05
11,546 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9605343e-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
62 Maintaining Views Incrementally 1993 SIGMOD 0.00038944207
397 Worst-case Optimal Join Algorithms 2012 PODS 0.0001911958
982 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00012687016
1,071 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012154243
1,734 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7545941e-05
1,821 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5466386e-05
2,488 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 8.3790632e-05
Previous Page 1 / 1 Next

Semantically Similar Papers