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.00016876498
Overall Rank
772 | 94.64%
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,056 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.0001441128
3,371 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 7.1696145e-05
3,715 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8220943e-05
3,781 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7723513e-05
4,197 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.367895e-05
4,708 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.980172e-05
5,055 Enumeration on Trees with Tractable Combined Complexity and Efficient Updates 2019 PODS 5.7312839e-05
5,576 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 5.426344e-05
5,855 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3006096e-05
5,962 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2536266e-05
5,967 Change Propagation Without Joins 2023 VLDB 5.250976e-05
6,695 Maintaining Acyclic Foreign-Key Joins under Updates 2020 SIGMOD 4.9582125e-05
7,069 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 4.8438319e-05
7,695 CORE: a Complex Event Recognition Engine 2022 VLDB 4.6757592e-05
7,761 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.658708e-05
7,864 Differentially Private Data Release over Multiple Tables 2023 PODS 4.6327272e-05
8,159 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5729025e-05
8,437 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5138778e-05
8,652 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 4.4753042e-05
8,677 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 4.4703012e-05
8,754 Efficient Enumeration for Annotated Grammars 2022 PODS 4.456315e-05
8,959 Reservoir Sampling over Joins 2024 SIGMOD 4.4206222e-05
9,653 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 4.3109001e-05
9,707 Towards Update-Dependent Analysis of Query Maintenance 2025 PODS 4.299267e-05
10,001 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.1945683e-05
10,010 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.1945683e-05
10,049 Approximate Query Processing under Updates 2026 SIGMOD 4.1945683e-05
10,159 Efficient Influential Community Search over Dynamic Graphs 2026 SIGMOD 4.1945683e-05
10,339 A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity 2025 PODS 4.1945683e-05
10,345 Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation 2025 PODS 4.1945683e-05
10,899 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.1945683e-05
10,919 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.1945683e-05
10,926 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 4.1945683e-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
95 Maintaining Views Incrementally 1993 SIGMOD 0.00050896659
502 Worst-case Optimal Join Algorithms 2012 PODS 0.00021526612
1,110 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013968198
1,268 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012931993
1,557 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 0.00011392493
2,063 Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability 2014 PODS 9.6447857e-05
2,296 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0776226e-05
Previous Page 1 / 1 Next

Semantically Similar Papers