expressiveness of restricted recursive queries
We study the effect of various syntactic restrictions on the expressive power of database logic programs. We find natural examples of programs which require recursively defined predicates of arbitrarily large width, require rules with arbitrarily many recursive calls, or require nonlinear rules, but can be evaluated in NC 2 .
express recursion queries effect power database logic program program examples rules