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
Secondary volumes: Selected Papers of the 24th International Conference on Database Theory (ICDT 2021)
Published on: May 16, 2025
Accepted on: March 9, 2025
Submitted on: November 2, 2021
Keywords: Computer Science - Databases
Funding:
    Source : OpenAIRE Graph
  • CRII: III: Partition-aware Parallel Query Processing; Funder: National Science Foundation; Code: 1850348
  • III: Small: Task-aware Materialization for Fast Data Analytics; Funder: National Science Foundation; Code: 1910014

Consultation statistics

This page has been seen 1519 times.
This article's PDF has been downloaded 772 times.