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
- 12065
- Venue
- VLDB
- Year
- 2020
- Pagerank
- 6.8220943e-05
- Overall Rank
- 3,715 | 74.16%
- 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,387 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.1573735e-05 |
| 5,517 |
Representing Paths in Graph Database Pattern Matching |
2023 |
VLDB |
5.4626107e-05 |
| 5,855 |
Optimal Join Algorithms Meet Top-k |
2020 |
SIGMOD |
5.3006096e-05 |
| 5,858 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2997454e-05 |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 7,166 |
Ranked Enumeration of Join Queries with Projections |
2022 |
VLDB |
4.8124491e-05 |
| 7,840 |
Progressive Join Algorithms Considering User Preference |
2021 |
CIDR |
4.6371736e-05 |
| 8,668 |
Towards Generating Hop-constrained s-t Simple Path Graphs |
2023 |
SIGMOD |
4.4718257e-05 |
| 9,157 |
REmatch: a novel regex engine for finding all matches |
2023 |
VLDB |
4.3849295e-05 |
| 9,653 |
Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration |
2021 |
PODS |
4.3109001e-05 |
| 9,744 |
Output-Sensitive Evaluation of Regular Path Queries |
2025 |
PODS |
4.2897489e-05 |
| 9,798 |
Threshold Queries in Theory and in the Wild |
2022 |
VLDB |
4.2818172e-05 |
| 9,940 |
Worst-Case-Optimal Similarity Joins on Graph Databases |
2024 |
SIGMOD |
4.2456408e-05 |
| 10,003 |
Clustering with Set Outliers and Applications in Relational Clustering |
2026 |
PODS |
4.1945683e-05 |
| 10,924 |
Improved Approximation Algorithms for Relational Clustering |
2024 |
PODS |
4.1945683e-05 |
| 10,970 |
Relational Algorithms for Top-k Query Evaluation |
2024 |
SIGMOD |
4.1945683e-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 |
| 7 |
Optimal Aggregation Algorithms for Middleware [Extended Abstract] |
2001 |
PODS |
0.0015496097 |
| 407 |
Conjunctive-Query Containment and Constraint Satisfaction |
1998 |
PODS |
0.00024004562 |
| 552 |
Supporting Incremental Join Queries on Ranked Inputs |
2001 |
VLDB |
0.00020310903 |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 626 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018973823 |
| 674 |
Supporting Top-k Join Queries in Relational Databases |
2003 |
VLDB |
0.00018327585 |
| 772 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.00016876498 |
| 805 |
Evaluating Top-k Selection Queries |
1999 |
VLDB |
0.00016437265 |
| 1,259 |
Aggregation and Ordering in Factorised Databases |
2013 |
VLDB |
0.00012995821 |
| 1,328 |
Hypertree Decompositions: Questions and Answers |
2016 |
PODS |
0.00012565612 |
| 1,442 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011956109 |
| 2,009 |
IO-Top-k: Index-access Optimized Top-k Query Processing |
2006 |
VLDB |
9.7977564e-05 |
| 2,015 |
Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width |
2001 |
PODS |
9.7901938e-05 |
| 3,006 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7299363e-05 |
| 3,082 |
FDB: A Query Engine for Factorised Relational Databases |
2012 |
VLDB |
7.6014248e-05 |
| 3,371 |
On the Enumeration Complexity of Unions of Conjunctive Queries |
2019 |
PODS |
7.1696145e-05 |
| 5,155 |
Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections |
1983 |
PODS |
5.660316e-05 |
| 5,323 |
Optimizing and Parallelizing Ranked Enumeration |
2011 |
VLDB |
5.5693009e-05 |
| 5,373 |
Robust and Efficient Algorithms for Rank Join Evaluation |
2009 |
SIGMOD |
5.5425231e-05 |
| 6,824 |
Computing Join Queries with Functional Dependencies |
2016 |
PODS |
4.9144789e-05 |
| 7,762 |
Optimal Enumeration: Efficient Top-k Tree Matching |
2015 |
VLDB |
4.6583829e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,728 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9483326e-05 |
| 423 |
Measuring the Complexity of Join Enumeration in Query Optimization |
1990 |
VLDB |
0.00023669348 |
| 143 |
Optimization of Nonrecursive Queries |
1986 |
VLDB |
0.00041510555 |
| 8,061 |
Efficient Computation of Quantiles over Joins |
2023 |
PODS |
4.5943269e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1945683e-05 |
| 5,858 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2997454e-05 |
| 3,387 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.1573735e-05 |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 10,324 |
Towards Efficient Random-Order Enumeration for Join Queries |
2026 |
VLDB |
4.1945683e-05 |
| 7,166 |
Ranked Enumeration of Join Queries with Projections |
2022 |
VLDB |
4.8124491e-05 |