DBScholar

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
12253
Venue
VLDB
Year
2020
Pagerank
8.1747954e-05
Overall Rank
2,745 | 81.17%
DOI
10.14778/3397230.3397250

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{tziavelis_vldb20,
        title = {{Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries}},
        author = {Tziavelis, Nikolaos and Ajwani, Deepak and Gatterbauer, Wolfgang and Riedewald, Mirek and Yang, Xiaofeng},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {9},
        pages = {1582--1597},
        doi = {10.14778/3397230.3397250},
        url = {https://doi.org/10.14778/3397230.3397250},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,418 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.2255373e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.8836116e-05
8,024 Progressive Join Algorithms Considering User Preference 2021 CIDR 5.5052493e-05
8,650 Towards Generating Hop-constrained s-t Simple Path Graphs 2023 SIGMOD 5.3916003e-05
9,235 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.3016261e-05
9,312 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.289545e-05
9,819 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.214913e-05
9,961 Threshold Queries in Theory and in the Wild 2022 VLDB 5.1879626e-05
10,087 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.1558402e-05
10,153 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 5.093636e-05
10,176 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 5.093636e-05
11,144 Improved Approximation Algorithms for Relational Clustering 2024 PODS 5.093636e-05
11,183 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

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

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
382 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019546431
499 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017431827
509 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017220967
635 Evaluating Top-k Selection Queries 1999 VLDB 0.00015527042
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
673 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00015095061
814 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013841737
860 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013560445
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
1,673 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 0.00010040854
1,967 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.3804693e-05
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,392 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 8.6404947e-05
2,468 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.5358494e-05
5,138 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.3495536e-05
5,383 Compressed Representations of Conjunctive Query Results 2018 PODS 6.2374576e-05
5,526 Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections 1983 PODS 6.1864862e-05
6,672 Computing Join Queries with Functional Dependencies 2016 PODS 5.8070233e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-05
8,013 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.5073426e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 316 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB
2 143 Optimization of Nonrecursive Queries 1986 VLDB
3 10,154 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS
4 7,286 Efficient Computation of Quantiles over Joins 2023 PODS
5 10,394 Query Optimization for Database-Returning Queries 2026 SIGMOD
6 4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS
7 2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS
8 5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB
9 10,622 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB
10 6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB