BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-86-1132
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Optimizing Datalog Programs
        TYPE:: Technical Report
      AUTHOR:: Sagiv, Yehoshua
        DATE:: March 1986
       PAGES:: 32
    ABSTRACT:: Datalog programs, i.e., Prolog programs without function
               symbols, are considered. It is assumed that a variable
               appearing in the head of a rule must also appear in the body
               of the rule. The input of a program is a set of ground atoms
               (which are given in addition to the program's rules) and,
               therefore, can be viewed as an assignment of relations to
               some of the program's predicates. Two programs are equivalent
               if they produce the same result for all possible assignments
               of relations to the extensional predicates (i.e., the
               predicates that do not appear as heads of rules). Two
               programs are uniformly equivalent if they produce the same
               result for all possible assignments of initial relations to
               all the predicates (i.e. both extensional and intentional).
               The equivalence problem for Datalog programs is known to be
               undecidable. It is shown that uniform equivalence is
               decidable, and an algorithm is given for minimizing a Datalog
               program under equivalence. A technique for removing parts of
               a program that are redundant under equivalence (but not under
               uniform equivalence) is developed. A procedure for testing
               uniform equivalence is also developed for the case in which
               the database satisfies some constraints.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-86-1132