Output-Optimal Algorithms for Join-Aggregate Queries

经典的 Yannakakis 框架是解决定义在可交换半环上的无环连接聚合查询的最先进方法。已经证明，对于任何自由连通的连接聚合查询，Yannakakis 框架的时间复杂度为 $O(N + \OUT)$，其中 $N$ 是数据库的输入大小，$\OUT$ 是查询结果的输出大小。这已经是输出最优的了。然而，对于剩余的无环但非自由连通查询，Yannakakis 框架的时间复杂度仅知道一个一般的上界 $O(N \cdot \OUT)$。我们首先展示了通过“半环算法”计算无环连接聚合查询的下界 $\Omega\left(N \cdot \OUT^{1- \frac{1}{\outw}} +\OUT\right)$，其中 $\outw$ 被确定为输入查询的“输出宽度”，$N$ 是数据库的输入大小，$\OUT$ 是查询结果的输出大小。例如，对于链矩阵乘法查询，$\outw=2$，对于带有 $k$ 个关系的星形矩阵乘法查询，$\outw=k$。我们对 Yannakakis 框架进行了更紧密的分析，并展示了 Yannakakis 框架在“聚合分层”查询类上已经是输出最优的了。然而，对于大量剩余的非聚合分层查询，例如链矩阵乘法查询，Yannakakis 框架确实需要 $\Theta(N \cdot \OUT)$ 时间。接下来，我们探索了 Yannakakis 框架的混合版本，并提出了一种输出最优的算法，用于在 $\O\left(N\cdot \OUT^{1-\frac{1}{\outw}} + \OUT\right)$ 时间内计算任何一般的无环连接聚合查询，与输出宽度相关的下界匹配，差异仅为多项式对数因子。据我们所知，这是自 1981 年以来计算无环连接聚合查询的第一个多项式改进。

解决问题：论文旨在解决acyclic join-aggregate queries的计算问题。

关键思路：论文提出了一个混合Yannakakis框架的算法，能够在输出大小和输入规模的多项式时间内计算acyclic join-aggregate queries。

其他亮点：论文给出了acyclic join-aggregate queries的下界和上界，提出了一个新的算法，能够在输出大小和输入规模的多项式时间内计算acyclic join-aggregate queries。实验结果表明，该算法比现有算法更有效。

相关研究：最近的相关研究包括“Efficient Algorithms for Acyclic Join Queries”和“Optimal and Streaming Algorithms for Matrix Chain Product”。