Shaleen Deep ; Paraschos Koutris - Ranked Enumeration of Conjunctive Query Results

lmcs:8638 - Logical Methods in Computer Science, May 16, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:14)2025
Ranked Enumeration of Conjunctive Query ResultsArticle

Authors: Shaleen Deep ; Paraschos Koutris

    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.


    Volume: Volume 21, Issue 2
    Published on: May 16, 2025
    Accepted on: March 9, 2025
    Submitted on: November 2, 2021
    Keywords: Computer Science - Databases

    Consultation statistics

    This page has been seen 469 times.
    This article's PDF has been downloaded 192 times.