Ranked Enumeration of Conjunctive Query Results
arXiv:1902.02698 · doi:10.46298/lmcs-21(2:14)2025
Abstract
We study the problem of enumerating answers of Conjunctive Queries ranked according to a given ranking function. Our main contribution is a novel algorithm with small preprocessing time, logarithmic delay, and non-trivial space usage during execution. To allow for efficient enumeration, we exploit certain properties of ranking functions that frequently occur in practice. To this end, we introduce the notions of {\em decomposable} and {\em compatible} (w.r.t. a query decomposition) ranking functions, which allow for partial aggregation of tuple scores in order to efficiently enumerate the output. We complement the algorithmic results with lower bounds that justify why restrictions on the structure of ranking functions are necessary. Our results extend and improve upon a long line of work that has studied ranked enumeration from both a theoretical and practical perspective.
References in corpus (6)
- Open Problems from CCCG 2002
- Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs
- Ranked Enumeration of Conjunctive Query Results
- Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
- Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
- Enumeration Algorithms for Conjunctive Queries with Projection