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.2157154e-05
Overall Rank
2,602 | 82.56%
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,766 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0221503e-05
4,714 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4395938e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
5,574 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.0628579e-05
6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7298671e-05
8,071 Progressive Join Algorithms Considering User Preference 2021 CIDR 5.3800399e-05
8,815 Towards Generating Hop-constrained s-t Simple Path Graphs 2023 SIGMOD 5.2567916e-05
9,445 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1630894e-05
9,530 REmatch: a novel regex engine for finding all matches 2023 VLDB 5.151324e-05
10,048 Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration 2021 PODS 5.0786422e-05
10,192 Threshold Queries in Theory and in the Wild 2022 VLDB 5.052396e-05
10,336 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.0211131e-05
10,448 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 4.9605343e-05
10,471 Clustering with Set Outliers and Applications in Relational Clustering 2026 PODS 4.9605343e-05
11,097 Instance-Optimal Acyclic Joins: From Theory to Systems 2026 VLDB 4.9605343e-05
11,550 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.9605343e-05
11,581 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9605343e-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.0010688884
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.0001918714
505 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017162373
511 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017061618
639 Answering Conjunctive Queries under Updates 2017 PODS 0.00015289346
647 Evaluating Top-k Selection Queries 1999 VLDB 0.00015165562
685 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014747128
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013623401
848 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013463236
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,695 Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width 2001 PODS 9.8317087e-05
2,019 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.1666472e-05
2,298 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 8.6645337e-05
2,316 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6404062e-05
2,526 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.3274934e-05
5,254 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.1964074e-05
5,512 Compressed Representations of Conjunctive Query Results 2018 PODS 6.0867282e-05
5,661 Gyo Reductions, Canonical Connections, Tree And Cyclic Schemas And Tree Projections 1983 PODS 6.0299179e-05
6,761 Computing Join Queries with Functional Dependencies 2016 PODS 5.6705551e-05
7,769 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4391973e-05
8,177 Optimizing and Parallelizing Ranked Enumeration 2011 VLDB 5.3685485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 322 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB
2 144 Optimization of Nonrecursive Queries 1986 VLDB
3 10,449 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS
4 7,459 Efficient Computation of Quantiles over Joins 2023 PODS
5 10,663 Query Optimization for Database-Returning Queries 2026 SIGMOD
6 4,714 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS
7 2,766 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS
8 5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB
9 11,138 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB
10 6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB