BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-86-1114
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Optimizing function-free recursive inference rules
        TYPE:: Technical Report
      AUTHOR:: Naughton, Jeffrey F.
        DATE:: May 1986
       PAGES:: 30
    ABSTRACT:: Recursive inference rules arise in recursive definitions in
               logic programming systems and in database systems with
               recursive query languages. Let D be a recursive definition of
               a relation t. We say that D is minimal if for any predicate p
               in a recursive rule in D, p must appear in a recursive rule
               in any definition of t. We show that testing for minimality
               is in general undecidable. However, we do present an
               efficient algorithm for a useful class of recursive rules,
               and show how to use it to transform a recursive definition to
               a minimal recursive definition. Evaluating the optimized
               definition will avoid redundant computation without the
               overhead of caching intermediate results and run-time
               checking for duplicate goals.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-86-1114