Database Paper Browser

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
1707
Venue
PODS
Year
2017
Pagerank
0.0001686092
Overall Rank
770 | 94.66%
DOI
10.1145/3034786.3034789

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
1,054 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00014397587
3,374 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 7.1631303e-05
3,702 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8251643e-05
3,785 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7658346e-05
4,200 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.3618329e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
5,052 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 5.725952e-05
5,582 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 5.4211286e-05
5,845 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3057391e-05
5,963 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2485815e-05
5,973 Change Propagation Without Joins 2023 VLDB 5.2459364e-05
6,699 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 4.9534535e-05
7,064 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 4.8391823e-05
7,679 CORE: a Complex Event Recognition Engine 2022 VLDB 4.676558e-05
7,762 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.6542406e-05
7,865 Differentially Private Data Release over Multiple Tables 2023 PODS 4.6282846e-05
8,163 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5685178e-05
8,428 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5095504e-05
8,650 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 4.4710131e-05
8,673 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 4.4660157e-05
8,750 Efficient Enumeration for Annotated Grammars 2022 PODS 4.4520434e-05
8,964 Reservoir Sampling over Joins 2024 SIGMOD 4.4163852e-05
9,654 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 4.3067693e-05
9,706 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 4.2951473e-05
10,000 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.1905499e-05
10,010 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.1905499e-05
10,049 Approximate Query Processing under Updates 2026 SIGMOD 4.1905499e-05
10,159 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 4.1905499e-05
10,351 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 4.1905499e-05
10,357 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 4.1905499e-05
10,903 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.1905499e-05
10,923 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.1905499e-05
10,930 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 4.1905499e-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
97 Maintaining Views Incrementally 1993 SIGMOD 0.00050863077
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
1,114 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013871948
1,269 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012911894
1,556 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011383141
2,057 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 9.665853e-05
2,298 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0746479e-05
Previous Page 1 / 1 Next

Semantically Similar Papers