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. Recent results by Gaifman et al. in “Proceedings, 2nd. IEEE Sympos. on Logic in Comput. Sci., June 1987,” pp. 106–115. show that the general problem is undecidable. We consider two types of initialization of the recursively defined relation: arbitrary initialization, and initialization by a given nonrecursive rule. This extends earlier work and is related to bounded tableau results by Sagiv in “Proceedings, ACM SIGACT-SIGMOD Sympos. on Principles of Database Systems, 1985,” pp. 171–180. 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 evaluation algorithms.