A Query Language for NC

摘要

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 areNC-computable. At a finer level, we relateknested uses of recursion exactly toACk,k⩾1. We also give corresponding results for complex objects.