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 are NC -computable. At a finer level, we relate k nested uses of recursion exactly to AC k , k ?1. We also give corresponding results for complex objects.
query languages queries recursion relation algebra relational database complexity object divide-and-conquer