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
hed241c7210911dd4
Venue
VLDB
Year
2020
Pagerank
8.2468757e-05
Overall Rank
2,591 | 82.59%
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 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
4,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,557 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.085853e-05
6,545 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7515992e-05
8,048 Progressive Join Algorithms Considering User Preference 2021 CIDR 5.4004443e-05
8,788 Towards Generating Hop-constrained s-t Simple Path Graphs 2023 SIGMOD 5.2767294e-05
9,410 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1826718e-05
9,490 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.1708619e-05
10,007 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0979044e-05
10,153 Threshold Queries in Theory and in the Wild 2022 VLDB 5.0715586e-05
10,301 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.040157e-05
10,370 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 4.9793485e-05
10,393 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 4.9793485e-05
11,027 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9793485e-05
11,492 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.9793485e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-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.0010679641
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
390 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019248147
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017101297
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016909926
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015341557
643 Evaluating Top-k Selection Queries 1999 VLDB 0.00015217076
684 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014798237
818 Hypertree Decompositions: Questions and Answers 2016 PODS 0.0001366708
849 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013504405
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
1,690 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 9.8609347e-05
2,006 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.199795e-05
2,290 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 8.6889284e-05
2,299 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6727773e-05
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3589894e-05
5,229 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.2196057e-05
5,489 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1095111e-05
5,646 Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections 1983 PODS 6.052788e-05
6,739 Computing Join Queries with Functional Dependencies 2016 PODS 5.6917027e-05
7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4595236e-05
8,154 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.3889102e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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