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.00015334386
Overall Rank
637 | 95.73%
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
813 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013722638
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3550625e-05
2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
3,114 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6321464e-05
3,188 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5510881e-05
4,152 Enumeration for FO Queries over Nowhere Dense Graphs 2018 PODS 6.7731796e-05
4,186 Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates 2018 PODS 6.7467768e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,061 Change Propagation Without Joins 2023 VLDB 6.2897936e-05
5,147 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2536517e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,492 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1066968e-05
5,709 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 6.0225917e-05
6,389 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8014043e-05
6,881 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6559492e-05
7,341 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5465684e-05
7,471 Reservoir Sampling over Joins 2024 SIGMOD 5.5172544e-05
7,616 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4822011e-05
7,711 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4711392e-05
7,724 CORE: a Complex Event Recognition Engine 2022 VLDB 5.4657408e-05
8,013 Differentially Private Data Release over Multiple Tables 2023 PODS 5.4050229e-05
8,285 Subset Sampling over Joins 2026 PODS 5.3612232e-05
8,837 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2661006e-05
8,841 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2655908e-05
9,095 Efficient Enumeration for Annotated Grammars 2022 PODS 5.2258409e-05
9,372 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1843659e-05
10,012 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0954911e-05
10,033 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0901047e-05
10,389 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9769913e-05
10,399 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9769913e-05
10,403 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9769913e-05
10,411 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9769913e-05
10,555 Approximate Query Processing under Updates 2026 SIGMOD 4.9769913e-05
10,647 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 4.9769913e-05
10,894 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9769913e-05
11,089 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 4.9769913e-05
11,093 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 4.9769913e-05
11,475 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9769913e-05
11,494 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9769913e-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.00039040346
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
978 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00012725823
1,066 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012194105
1,726 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7857214e-05
1,813 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5759542e-05
2,482 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 8.3992826e-05
Previous Page 1 / 1 Next

Semantically Similar Papers