Back to papers
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
Summary: Framework for ranked enumeration of conjunctive queries under selective dioids, unifying DP and extending k-shortest-path to cyclic CQs. Achieves data-complexity-optimal top-1 and delay; reveals a tradeoff with batch and beats them all.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 12066
- Venue
- VLDB
- Year
- 2020
- Pagerank
- 6.8251643e-05
- Overall Rank
- 3,702 | 74.28%
- DOI
-
10.14778/3397230.3397250
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 16 of 16 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 3,386 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.151562e-05 |
| 5,527 |
Representing Paths in Graph Database Pattern Matching |
2023 |
VLDB |
5.4573655e-05 |
| 5,845 |
Optimal Join Algorithms Meet Top-k |
2020 |
SIGMOD |
5.3057391e-05 |
| 5,859 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2963939e-05 |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 7,165 |
Ranked Enumeration of Join Queries with Projections |
2022 |
VLDB |
4.807833e-05 |
| 7,845 |
Progressive Join Algorithms Considering User Preference |
2021 |
CIDR |
4.6327267e-05 |
| 8,666 |
Towards Generating Hop-constrained s-t Simple Path Graphs |
2023 |
SIGMOD |
4.467539e-05 |
| 9,157 |
REmatch: a novel regex engine for finding all matches |
2023 |
VLDB |
4.380727e-05 |
| 9,654 |
Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration |
2021 |
PODS |
4.3067693e-05 |
| 9,743 |
Output-Sensitive Evaluation of Regular Path Queries |
2025 |
PODS |
4.2856385e-05 |
| 9,801 |
Threshold Queries in Theory and in the Wild |
2022 |
VLDB |
4.2777144e-05 |
| 9,940 |
Worst-Case-Optimal Similarity Joins on Graph Databases |
2024 |
SIGMOD |
4.241573e-05 |
| 10,002 |
Clustering with Set Outliers and Applications in Relational Clustering |
2026 |
PODS |
4.1905499e-05 |
| 10,928 |
Improved Approximation Algorithms for Relational Clustering |
2024 |
PODS |
4.1905499e-05 |
| 10,973 |
Relational Algorithms for Top-k Query Evaluation |
2024 |
SIGMOD |
4.1905499e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 21 of 21 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 8 |
Optimal Aggregation Algorithms for Middleware [Extended Abstract] |
2001 |
PODS |
0.0015436578 |
| 401 |
Conjunctive-Query Containment and Constraint Satisfaction |
1998 |
PODS |
0.00024281448 |
| 551 |
Supporting Incremental Join Queries on Ranked Inputs |
2001 |
VLDB |
0.00020310856 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 623 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018976192 |
| 673 |
Supporting Top-k Join Queries in Relational Databases |
2003 |
VLDB |
0.00018325667 |
| 770 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.0001686092 |
| 802 |
Evaluating Top-k Selection Queries |
1999 |
VLDB |
0.00016440813 |
| 1,255 |
Aggregation and Ordering in Factorised Databases |
2013 |
VLDB |
0.00013011216 |
| 1,322 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012595941 |
| 1,452 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011922523 |
| 2,007 |
Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width |
2001 |
PODS |
9.8123766e-05 |
| 2,014 |
IO-Top-k: Index-access Optimized Top-k Query Processing |
2006 |
VLDB |
9.7982231e-05 |
| 3,009 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7230513e-05 |
| 3,088 |
FDB: A Query Engine for Factorised Relational Databases |
2012 |
VLDB |
7.5940302e-05 |
| 3,374 |
On the Enumeration Complexity of Unions of Conjunctive Queries |
2019 |
PODS |
7.1631303e-05 |
| 5,151 |
Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections |
1983 |
PODS |
5.6551e-05 |
| 5,331 |
Optimizing and Parallelizing Ranked Enumeration |
2011 |
VLDB |
5.5642069e-05 |
| 5,379 |
Robust and Efficient Algorithms for Rank Join Evaluation |
2009 |
SIGMOD |
5.5375923e-05 |
| 6,822 |
Computing Join Queries with Functional Dependencies |
2016 |
PODS |
4.9101655e-05 |
| 7,761 |
Optimal Enumeration: Efficient Top-k Tree Matching |
2015 |
VLDB |
4.6543114e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,732 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9435849e-05 |
| 422 |
Measuring the Complexity of Join Enumeration in Query Optimization |
1990 |
VLDB |
0.00023654556 |
| 144 |
Optimization of Nonrecursive Queries |
1986 |
VLDB |
0.00041430126 |
| 8,065 |
Efficient Computation of Quantiles over Joins |
2023 |
PODS |
4.5899218e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1905499e-05 |
| 5,859 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2963939e-05 |
| 3,386 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.151562e-05 |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 10,336 |
Towards Efficient Random-Order Enumeration for Join Queries |
2026 |
VLDB |
4.1905499e-05 |
| 7,165 |
Ranked Enumeration of Join Queries with Projections |
2022 |
VLDB |
4.807833e-05 |