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.00015341557
Overall Rank
637 | 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
812 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013729015
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3589894e-05
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
3,112 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 7.6357579e-05
3,187 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5546613e-05
4,152 Enumeration for FO Queries over Nowhere Dense Graphs 2018 PODS 6.7763853e-05
4,186 Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates 2018 PODS 6.74997e-05
4,463 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5877664e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
5,057 Change Propagation Without Joins 2023 VLDB 6.2927647e-05
5,145 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 6.2566119e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,489 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1095111e-05
5,708 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 6.0254441e-05
6,386 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 5.8040725e-05
6,876 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6586279e-05
7,338 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5491953e-05
7,467 Reservoir Sampling over Joins 2024 SIGMOD 5.5198675e-05
7,609 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4847975e-05
7,705 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4737304e-05
7,717 CORE: a Complex Event Recognition Engine 2022 VLDB 5.4683294e-05
8,008 Differentially Private Data Release over Multiple Tables 2023 PODS 5.4075828e-05
8,279 Subset Sampling over Joins 2026 PODS 5.3637624e-05
8,828 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2685945e-05
8,832 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2680847e-05
9,085 Efficient Enumeration for Annotated Grammars 2022 PODS 5.2283159e-05
9,363 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.1868213e-05
10,007 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0979044e-05
10,028 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 5.0925155e-05
10,377 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9793485e-05
10,387 Towards Parameterized Hardness on Maintaining Conjunctive Queries 2026 PODS 4.9793485e-05
10,391 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9793485e-05
10,399 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.9793485e-05
10,544 Approximate Query Processing under Updates 2026 SIGMOD 4.9793485e-05
10,636 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 4.9793485e-05
10,885 Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases 2026 VLDB 4.9793485e-05
11,080 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 4.9793485e-05
11,084 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 4.9793485e-05
11,469 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9793485e-05
11,488 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9793485e-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.

Previous Page 1 / 1 Next

Semantically Similar Papers