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.7723513e-05
Overall Rank: 3,781 | 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.9224501e-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,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
7,761	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.658708e-05
8,437	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5138778e-05
8,754	Efficient Enumeration for Annotated Grammars	2022	PODS	4.456315e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-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,049	Approximate Query Processing under Updates	2026	SIGMOD	4.1945683e-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
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
586	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019685374
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,238	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013114581
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
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,576	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.426344e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
9,653	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	4.3109001e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
11,254	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.1945683e-05
9,707	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.299267e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
8,437	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5138778e-05