一句话：研究带分组聚合的合取查询在注解数据库上的细粒度复杂度，给出答案字典序直接访问的易处理条件。
论文研究带分组与聚合的合取查询的细粒度复杂度。min、max、count、sum 等聚合可转化为交换半环注解数据库上的合取查询。目标是 loglinear 时间构造数据结构，以对数时间按给定字典序直接访问答案；因答案数可能远超输入，结构需紧凑表示答案空间。已有工作给出无聚合无注解下的易处理条件，并对无自连接查询证明必要性。本文证明当注解不参与字典序时这些结果仍适用于注解数据库；针对无法有效半环表示的 count-distinct 建立相应条件；并分析聚合值与注解值进入序，以及加法幂等半环等情形对复杂度的影响。
We study the fine-grained complexity of conjunctive queries with grouping and aggregation. For common aggregate functions (e.g., min, max, count, sum), such a query can be phrased as an ordinary conjunctive query over a database annotated with a suitable commutative semiring. We investigate the ability to evaluate such queries by constructing in loglinear time a data structure that provides logarithmic-time direct access to the answers ordered by a given lexicographic order. This task is nontrivial since the number of answers might be larger than loglinear in the size of the input, so the data structure needs to provide a compact representation of the space of answers. In the absence of aggregation and annotation, past research established a sufficient tractability condition on queries and orders. For queries without self-joins, this condition is not just sufficient, but also necessary (under conventional lower-bound assumptions in fine-grained complexity). We show that all past results continue to hold for annotated databases, assuming that the annotation itself does not participate in the lexicographic order. Yet, past algorithms do not apply to the count-distinct aggregation, which has no efficient representation as a commutative semiring; for this aggregation, we establish the corresponding tractability condition. We then show how the complexity of the problem changes when we include the aggregate and annotation value in the order. We also study the impact of having all relations but one annotated by the multiplicative identity (one), as happens when we translate aggregate queries into semiring annotations, and having a semiring with an idempotent addition, such as the case of min, max, and count-distinct over a logarithmic-size domain.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2303-05327,
title = {Direct Access for Answers to Conjunctive Queries with Aggregation},
author = {Idan Eldar and Nofar Carmeli and Benny Kimelfeld},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 2},
year = {2026},
doi = {10.46298/lmcs-22(2:9)2026}
}