Minimizing Expansions of Recursions
Report ID: TR-150-88Author: Naughton, Jeffrey F. / Sagiv, Yehoshua
Date: 1988-04-00
Pages: 23
Download Formats: |PDF|
Abstract:
In recent years function-free horn clauses have received a lot of attention as database query languages. Recursive definitions in such a language are particularly problematic in that they are hard to implement efficiently. As most evaluation procedures at least implicitly evaluate the expansion of the recursion, it is natural to consider optimizing the recursion by minimizing its expansion. In this paper we show how attempts to minimize expansions of recursions lead naturally to the issues of recursively redundant predicates and bounded recursions. We review current results, prove several new results about interelement redundancy in expansions, and show how both recursively redundant predicates and bounded recursions are closely related to the existence of various types of paths in a graph constructed from the rule.