Expressiveness of restricted recursive queries

Abstract

We study the effect of various syntactic restrictions on the expressive power of database logic programs. We find natural examples of programs which (i) require recursively defined predicates of arbitrarily large width, (ii) require rules with arbitrarily many recursive calls, or (iii) require nonlinear rules, but can be evaluated in NC2.