一句话：在 CRCW PRAM 上为关系代数、无环查询、半连接代数和最坏情况最优连接查询给出常数时间且弱工作高效的求值算法。
本文研究 CRCW PRAM 模型下查询求值的常数时间并行算法。虽然已知关系代数查询可在合适 CRCW PRAM 上常数时间求值，但朴素算法的处理器数或工作量可达多项式级，且结果在内存中高度分散。文章分析了实现常数时间 PRAM 查询求值的障碍，并为关系算子设计算法，重点考察三类已有高效串行算法的问题：无环查询、半连接代数查询，以及最坏情况最优框架下的连接查询。在数据值为数据库规模的多项式大小或关系已适当排序等温和假设下，作者借助 Goldberg 与 Zwick (1995) 的近似前缀和与压缩算法，给出常数时间算法；其工作量相对于最优串行时间 T 可达到 O(T^(1+ε))（任意 ε>0），即弱工作高效。
The article studies query evaluation in parallel constant time in the CRCW PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time on an appropriate CRCW PRAM model, this article is interested in the efficiency of evaluation algorithms, that is, in the number of processors or, asymptotically equivalent, in the work. Naive evaluation in the parallel setting results in huge (polynomial) bounds on the work of such algorithms and in presentations of the result sets that can be extremely scattered in memory. The article discusses some obstacles for constant-time PRAM query evaluation. It presents algorithms for relational operators and explores three settings, in which efficient sequential query evaluation algorithms exist: acyclic queries, semijoin algebra queries, and join queries -- the latter in the worst-case optimal framework. Under mild assumptions -- that data values are numbers of polynomial size in the size of the database or that the relations of the database are suitably sorted -- constant-time algorithms are presented that are weakly work-efficient in the sense that work $\mathcal{O}(T^{1+\varepsilon})$ can be achieved, for every $\varepsilon>0$, compared to the time $T$ of an optimal sequential algorithm. Important tools are the algorithms for approximate prefix sums and compaction from Goldberg and Zwick (1995).
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{KeppelerSS26,
title = {Work-Efficient Query Evaluation in Constant Time with PRAMs},
author = {Jens Keppeler and Thomas Schwentick and Christopher Spinrath},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 2},
year = {2026},
doi = {10.46298/lmcs-22(2:27)2026}
}