Optimization of recursive database query languages
Jeffrey F. Naughton · 1987
Recently, logic-based languages have received a lot of attention both in logic programming systems and in extended relational database systems. If these systems are to be practical, they will require powerful optimization techniques, especially for recursions. In this thesis we present three such optimizations. We first consider how to detect bounded recursions, that is, recursions that can be replaced by equivalent nonrecursive definitions. By varying the problem parameters, one can produce classes of recursions for which the bounded recursion problem ranges from linearly decidable to NP-hard to undecidable. Next we consider removing redundant predicates from unbounded recursions. We prove that detecting redundant predicates is undecidable, but give an algorithm to detect and remove redundant predicates that is complete for a large subset of recursions. Finally, we define a useful class of recursions, the one-sided recursions. We show how to detect one-sided recursions, give two simple evaluation algorithms for one-sided recursions, and discuss some properties of one-sided recursions that make evaluating selections on one-sided recursions particularly simple.