A query language for NC
A query language for NC
复制标题
NC 查询语言
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
V. Tannen
中科院分区：
文献类型：
--
作者：
Dan Suciu;V. Tannen
我们表明，一种对集合的分治递归形式与关系代数一起，恰好能够表达在有序关系数据库上可在NC（并行计算复杂性类）中计算的查询。在更精细的层面上，我们将递归的k层嵌套使用恰好与ACk（k≥1，另一种并行计算复杂性类）相关联。我们还针对复杂对象给出了相应的结果。
We show that a form of divide and conquer recursion on sets together with the relational algebra expresses exactly the queries over ordered relational databases which are NC-computable. At a finer level, we relate k nested uses of recursion exactly to ACk, k≥1. We also give corresponding results for complex objects.