Overbound and right-linear queries

Abstract

We study the optimization of a useful subclass of linear recursive queries. In addition to the general purpose magic-sets transformation, special optimization techniques, such as the right-linear and context right-linear transformation have been proposed for such programs. These, and in fact most optimization techniques for database queries are based on the idea of full sips, where all available predicates are passed into a subgoal. This is widely believed to be a sound heuristic. However, we use partial sips, that do not pass all predicates into a subgoal, to develop an optimization algorithm for a class of linear queries and show that our algorithm is better than the previously known techniques. We syntactically identify a class of programs for which partial sips are always preferable to full sips. The result provokes thought on the utility of partial sips, and will hopefully lead to more research in the area. The right-linear and context right-linear transformations, where applicable, are alternatives to the magic-sets transformation. In the presence of alternative optimizations, we need a way to choose between them. Given a program, can we choose one technique over another, confident that we are not discarding a good evaluation strategy For example, it has been shown that, where applicable, the right-linear transformation always performs better than magic-sets. However the above question has been left unanswered for many of the proposed optimizations for special forms of recursion. The study the problem for one class of optimization techniques, comparing the context right-linear and magic-sets transformations. Finally, we observe that right-linear and left-linear programs can be viewed as duals of each other. Every right-linear program can be written as an equivalent left-linear program, and vice versa.