一句话：提出带小预处理、对数延迟和可控空间的合取查询结果排名枚举算法，并给出必要性下界。
本文研究按给定排名函数枚举合取查询（Conjunctive Query）结果的问题。主要贡献是一种新算法，具有较小的预处理时间、对数级延迟和执行期间非平凡的空间开销。为支持高效枚举，作者利用实践中常见排名函数的性质，引入相对于查询分解的可分解性与兼容性概念，使元组分数可部分聚合，从而快速产生有序输出。论文还用下界说明为何必须对排名函数结构施加限制，并扩展、改进了此前关于排名枚举的理论与实践工作。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-1902-02698,
title = {Ranked Enumeration of Conjunctive Query Results},
author = {Shaleen Deep and Paraschos Koutris},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 2},
year = {2025},
doi = {10.46298/lmcs-21(2:14)2025}
}