Report Number: CS-TR-84-1009
Institution: Stanford University, Department of Computer Science
Title: Complexity of a top-down capture rule
Author: Sagiv, Yehoshua
Author: Ullman, Jeffrey D.
Date: July 1984
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/84/1009/CS-TR-84-1009.pdf