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.2429717e-05
Overall Rank
2,593 | 82.58%
DOI
10.14778/3397230.3397250
PDF
Download (CC BY-NC-ND 4.0)

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.0487636e-05
4,700 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4609577e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,559 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.082972e-05
6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7488764e-05
8,054 Progressive Join Algorithms Considering User Preference 2021 CIDR 5.3978878e-05
8,797 Towards Generating Hop-constrained s-t Simple Path Graphs 2023 SIGMOD 5.2742315e-05
9,420 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1802184e-05
9,501 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.168414e-05
10,012 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0954911e-05
10,157 Threshold Queries in Theory and in the Wild 2022 VLDB 5.0691578e-05
10,308 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.0377711e-05
10,382 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 4.9769913e-05
10,405 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 4.9769913e-05
11,036 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9769913e-05
11,498 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.9769913e-05
11,532 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9769913e-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.0010679903
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019245666
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017093562
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016902116
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015334386
643 Evaluating Top-k Selection Queries 1999 VLDB 0.0001521012
684 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014791388
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013660715
849 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013498306
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012068611
1,690 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 9.8565419e-05
2,008 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.1956849e-05
2,293 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 8.685044e-05
2,302 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6687541e-05
2,517 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3550625e-05
5,233 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.2167391e-05
5,492 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1066968e-05
5,648 Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections 1983 PODS 6.0499227e-05
6,745 Computing Join Queries with Functional Dependencies 2016 PODS 5.6890943e-05
7,756 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4570169e-05
8,160 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.3863592e-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,383 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS
4 7,438 Efficient Computation of Quantiles over Joins 2023 PODS
5 10,601 Query Optimization for Database-Returning Queries 2026 SIGMOD
6 4,700 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,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB
9 11,077 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB
10 6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB