Minimizing function-free recursive inference rules

Abstract

Recursive inference rules arise in recursive definitions in logic programming systems and in database systems with recursive query languages. LetDbe a recursive definition of a relationt.Dis consideredminimalif for any predicatepin a recursive rule inD,pmust appear in a recursive rule in any definition oft. It is shown that testing for minimality is, in general, undecidable. However, an efficient algorithm for a useful class of recursive rules is presented, and it is used to transform a recursive definition to a minimal recursive definition. Evaluating the minimized definition avoids redundant computation without the overhead of caching intermediate results and run-time checking for duplicate goals.