技术摘要：基于 PRAM 的常数时间工作高效查询求值

问题陈述

本文研究了在并发读并发写并行随机存取机（CRCW PRAM）模型下，以并行常数时间（$O(1)$）求值关系代数查询的问题。虽然已知理论结果（Immerman [Imm89, Imm99]）表明所有关系代数查询均可在常数时间内以多项式工作量完成求值，但这些算法的效率——即计算步骤总数（工作量）——尚未得到系统研究。

朴素的并行求值往往导致高得令人难以接受的工作量上界（例如，某些无环查询为 $O(IN^4)$），并产生分散在内存中而非紧凑的输出表示。此外，PRAM 模型中存在根本性障碍：

1. 紧凑表示：无法在常数时间内使用多项式数量的处理器对数组进行紧凑化（移除空单元格）或排序（推论 2.2）。
2. 去重：在不进行排序的情况下生成每个元组恰好出现一次的结果集是困难的，而排序在常数时间内也是不可能的。
3. 下界：对于一般合取查询（例如 $k$-团），电路深度的下界意味着常数时间并行算法需要超多项式工作量（$\omega(n^{k/4})$），这使得任意查询的工作效率成为不可能。

核心问题在于确定对于哪些受限的查询类（无环查询、半连接代数、最坏情况最优连接），可以设计出工作高效的常数时间算法，其定义为对任意 $\varepsilon > 0$ 实现 $O(T^{1+\varepsilon})$ 的工作量，其中 $T$ 是最优串行算法的运行时间。

方法论

作者通过解决内存表示和数据移动的挑战，开发了一个常数时间并行查询求值框架。

1. 数据结构与设置

本文基于数据访问能力分析了三种设置：

• 通用设置：数据值是任意的；仅可用相等性测试（Equal）。
• 有序设置：数据值具有线性序；可用 LessThan。
• 字典设置：数据值是小整数（从活跃域映射到 $\{1, \dots, c|D|\}$）。该设置作为哈希的代理。

关系被表示为数组（可能包含空/未填充单元格）。为了处理完美紧凑化的不可能性，作者利用$\lambda$-近似紧凑化，其中输出数组大小最多为有效元组数量的 $(1+\lambda)$ 倍。

2. 核心算法工具

方法论严重依赖 Goldberg 和 Zwick [GZ95] 的技术：

• 近似前缀和：用于在紧凑化过程中以 $O(1)$ 时间和 $O(n^{1+\varepsilon})$ 工作量计算元素的新位置。
• 填充排序：将多项式大小的整数排序到 $(1+\lambda)$-填充数组中，耗时常数时间，工作量为 $O(n^{1+\varepsilon})$（命题 2.11）。
• 处理器分配：使用一致的前缀和将处理器高效地分配给任务（例如，连接元组组）（引理 2.7）。
• 哈希与链接：在字典设置中，数组哈希表允许实现工作量最优的搜索和去重（$O(n)$ 工作量）。在有序设置中，前驱/后继链接使得无需哈希即可实现高效搜索。

3. 查询求值策略

求值通过查询计划（关系算子的树结构）进行。作者通过分析中间关系的大小推导界限：

• 半连接代数：使用半连接、投影和选择。
• 无环查询：改编 Yannakakis 算法，利用完整的归约阶段 followed by 自底向上的连接阶段。
• 一般合取查询：使用广义超树分解将复杂查询归约为无环查询。
• 最坏情况最优连接：实现属性消除连接算法的并行版本（基于 [NPRR18]），仔细管理组紧凑化以避免二次爆炸。

主要贡献与结果

1. 基本限制与工具

• 下界：本文证明，精确的紧凑化和排序无法在常数时间内使用多项式数量的处理器完成。因此，任何为半连接或连接生成 $\lambda$-紧凑输出的常数时间算法都需要 $\Omega(n^{1+\varepsilon})$ 的处理器（定理 5.1）。
• 近似紧凑化与排序：作者形式化了 $\lambda$-近似紧凑化和填充排序的使用，作为绕过这些下界的主要机制，实现 $O(n^{1+\varepsilon})$ 的工作量。

2. 关系算子

本文提出了 $O(1)$ 时间的基本关系算子算法，其工作量界限因设置而异：

• 字典设置：算子如 Select、Project、SemiJoin 和 Difference 实现线性工作量 $O(IN)$（或$O(IN \cdot |D|^\varepsilon)$ 空间）。
• 有序设置：如果关系已预排序并链接，算子实现 $O(IN^{1+\varepsilon})$ 或 $O(IN \cdot |S|^\varepsilon)$ 的工作量。
• 通用设置：在没有假设的情况下，算子如 Project 和 Join 需要二次工作量 $O(IN^2)$，这被证明是该设置下的最优解。

3. 查询求值结果

主要结果总结在论文的表 4 中，提供了不同查询类的工作量界限：

• 半连接代数：

  • 字典设置：工作量 $O(IN)$。这是工作量最优的。
  • 有序/通用设置：工作量分别为 $O(IN^{1+\varepsilon})$ 或 $O(IN^2)$。

• 无环合取查询（CQs）：

  • 字典设置：工作量 $O((IN \cdot OUT)^{1+\varepsilon})$。
  • 自由连通无环 CQ：工作量 $O((IN + OUT)^{1+\varepsilon})$。
  • 这些界限与 Yannakakis 算法的串行复杂度相匹配（至多相差 $1+\varepsilon$ 因子）。

• 一般合取查询（有界广义超树宽度）：

  • 字典设置：工作量 $O((IN^{ghw(q)} \cdot OUT)^{1+\varepsilon})$，对于自由连通变体为 $O((IN^{fghw(q)} + OUT)^{1+\varepsilon})$。

• 最坏情况最优连接查询：

  • 本文提出了一种自然连接查询的常数时间并行算法，实现工作量 $O((agm(q, D) + |D|)^{1+\varepsilon})$，其中 $agm(q, D)$ 是 AGM 界限（连接结果的最坏情况大小）。这在字典设置中成立，无需预排序输入；在有序设置中，如果输入适当排序也成立。

4. 设置转换

作者展示了如何将数据库从通用和有序设置转换到字典设置：

• 通用到字典：需要 $O(|D|^2)$ 工作量来构建数据值的字典（哈希映射）。这为基于字典的算法的工作量界限增加了 $O(IN^2)$ 项。
• 有序到字典：如果关系是按属性排序的，可以在 $O(|D|^{1+\varepsilon})$ 工作量内构建字典，从而保留字典设置的近线性界限。

意义与主张

本文将自己定位为常数时间并行查询求值中工作高效性的基础性研究（“奠定基础”）。

• 适度主张：作者明确指出，他们不声称存在一个单一的固定算法，对所有 $\varepsilon$ 都具有 $W \in O(T^{1+\varepsilon})$ 的界限。相反，他们提供了一个统一算法，其中 $\varepsilon$ 是一个参数，且隐藏常数依赖于 $\varepsilon$。
• 工作高效性定义：鉴于在常数时间内实现严格工作量最优性（$O(T)$）的困难，本文提出该模型的实际效率概念为 $O(T^{1+\varepsilon})$。
• 实用性与理论：虽然 PRAM 模型是理论性的，但作者指出并行性在现代硬件中的日益相关性。结果表明，对于受限但重要的查询类（无环、半连接、最坏情况最优连接），常数时间并行求值不仅是可能的，而且在总工作量方面可以变得非常高效。
• 局限性：本文承认，对于一般合取查询（如 $k$-团），由于电路复杂性下界，常数时间工作高效性是不可能的。它还指出，动态设置（在更新下维护结果）仍是未来工作的开放领域，因为当前结果是静态的。

总之，本文确立了通过利用近似紧凑化、填充排序以及特定的查询结构属性（无环性、超树宽度），可以在常数并行时间内求值关系查询，其工作量界限相对于串行算法几乎是最优的。