Data Independent Recursion in Deductive Databases

摘要

Some recursive definitions in deductive database systems can be replaced by equivalent nonrecursive definitions. In this paper we give a linear-time algorithm that detects many such definitions, and specify a useful subset of recursive definitions for which the algorithm is complete. It is unlikely that our algorithm can be extended significantly, as recent results by Gaifman (5) and Vardi (19) show that the general problem is undecidable. We consider two types of initialization by a given nonrecursive rule. This extends earlier work by Minker and Nicolas (10), and by Ioannidis (7), and is related to bounded tableau results by Sagiv (14). Even if there is no equivalent nonrecursive definition, a modification of our algorithm can be used to optimize a recursive definition and improve the efficiency of the compiled algorithms.