BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-86-1102
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Data independent recursion in deductive databases
        TYPE:: Technical Report
      AUTHOR:: Naughton, Jeffrey F.
        DATE:: February 1986
       PAGES:: 36
    ABSTRACT:: 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 of the recursively defined relation: arbitrary
               initialization, and 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
               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
               proposed in Henschen and Naqvi [6] and in Bancilhon et al.
               [3].
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-86-1102