Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries

Summary: Degree-aware heavy/light framework for static and dynamic evaluation of hierarchical queries with arbitrary free variables, trading preprocessing, update time, and enumeration delay via a tunable light/heavy threshold. Recovers prior bounds and, for a restricted subclass, achieves OMv‑conditioned worst-case optimal update time and enumeration delay. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1777
Venue: PODS
Year: 2020
Pagerank: 6.7658346e-05
Overall Rank: 3,785 | 73.70%
DOI: 10.1145/3375395.3387646

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9168117e-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,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
7,762	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.6542406e-05
8,428	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5095504e-05
8,750	Efficient Enumeration for Annotated Grammars	2022	PODS	4.4520434e-05
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-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,049	Approximate Query Processing under Updates	2026	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,231	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013141213
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
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,582	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.4211286e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
9,654	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	4.3067693e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
11,256	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.1905499e-05
9,706	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.2951473e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
8,428	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5095504e-05