Report Number: CS-TR-86-1114
Institution: Stanford University, Department of Computer Science
Title: Optimizing function-free recursive inference rules
Author: Naughton, Jeffrey F.
Date: May 1986
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.