BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-84-1009
       ENTRY:: May 27, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Complexity of a top-down capture rule
        TYPE:: Technical Report
      AUTHOR:: Sagiv, Yehoshua
      AUTHOR:: Ullman, Jeffrey D.
        DATE:: July 1984
       PAGES:: 38
    ABSTRACT:: Capture rules were introduced in [U] as a method for planning
               the evaluation of a query expressed in first-order logic. We
               examine a capture rule that is substantiated by a simple
               top-down implementation of restricted Horn clause logic. A
               necessary and sufficient condition for the top-down algorithm
               to converge is shown. It is proved that, provided there is a
               bound on the number of arguments of predicates, the test can
               be performed in polynomial time; however, if the arity of
               predicates is made part of the input, then the problem of
               deciding whether the top-down algorithm converges is NP-hard.
               We then consider relaxation of some of our constraints on the
               form of the logic, showing that success of the top-down
               algorithm can still be tested in polynomial time if the
               number of arguments is limited and in exponential time if
               not.
       NOTES:: [Adminitrivia V1/Prg/19950527]
         END:: STAN//CS-TR-84-1009