Database Paper Browser

Back to papers

AJAR: Aggregations and Joins over Annotated Relations

Summary: Shows multiway join algorithms plus generalized hypertree decompositions (GHDs) suffice for aggregate-join queries over annotated relations, achieving best-known runtimes. Characterizes equivalent aggregation orders and valid GHDs and decomposes them into unconstrained sub-GHDs to leverage GHD results for tighter bounds, distributed variants, and efficient approximate GHD search. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1688
Venue
PODS
Year
2016
Pagerank
9.3767985e-05
Overall Rank
2,173 | 84.90%
DOI
10.1145/2902251.2902293

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 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
2,281 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.122455e-05
3,022 Secure Yannakakis: Join-Aggregate Queries over Private Data 2021 SIGMOD 7.6942462e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
5,085 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.7040225e-05
5,497 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4741034e-05
5,650 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.3887172e-05
5,728 Conjunctive Queries with Comparisons 2022 SIGMOD 5.350072e-05
5,772 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 5.3313794e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8556471e-05
7,059 Residual Sensitivity for Differentially Private Multi-Way Joins 2021 SIGMOD 4.8404261e-05
7,060 Fast Matrix Multiplication for Query Processing 2024 PODS 4.8401037e-05
7,117 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8205884e-05
7,161 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 4.8086254e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
7,584 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.7015411e-05
7,920 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 4.6120304e-05
8,587 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4853975e-05
9,801 Threshold Queries in Theory and in the Wild 2022 VLDB 4.2777144e-05
10,049 Approximate Query Processing under Updates 2026 SIGMOD 4.1905499e-05
10,560 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 4.1905499e-05
10,973 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.1905499e-05
11,222 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank Cited Paper Year Venue Pagerank
31 Provenance Semirings 2007 PODS 0.00078516827
341 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026850764
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
564 FAQ: Questions Asked Frequently 2016 PODS 0.00020002796
1,255 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013011216
2,804 Hypertree Decompositions and Tractable Queries 1999 PODS 8.1039107e-05
5,050 DunceCap: Query Plans Using Generalized Hypertree Decompositions 2015 SIGMOD 5.7268774e-05
8,195 DunceCap: Compiling Worst-Case Optimal Query Plans 2015 SIGMOD 4.5573236e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,526 Simplicity Done Right for Join Ordering 2021 CIDR 6.1079584e-05
4,466 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 6.1545841e-05
8,972 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4150824e-05
8,065 Efficient Computation of Quantiles over Joins 2023 PODS 4.5899218e-05
2,281 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.122455e-05
8,587 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4853975e-05
1,621 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011105663
8,163 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5685178e-05
12,199 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.1905499e-05
5,085 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.7040225e-05