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