Minimize linear mutual recursion by rule unfolding

摘要

We minimize the number of recursive predicates in a linear mutualnrecursion by the rule unfolding technique. The minimization is based onna newly proposed syntactic equivalence called the unfolding-equivalence.nAlgorithms for testing unfolding-equivalence and constructing annunfolding-equivalent recursion with the fewest possible number ofnrecursive predicates are presented. We study the role of the unfoldingntechnique in optimizing deductive databases through reducing thesennumbers