|
|
|
@inproceedings{DBLP:conf/pods/MumickP91,
author = {Inderpal Singh Mumick and
Hamid Pirahesh},
title = {Overbound and Right-Linear Queries},
booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
publisher = {ACM Press},
year = {1991},
isbn = {0-89791-430-9},
pages = {127-141},
ee = {http://doi.acm.org/10.1145/113413.113425, db/conf/pods/MumickP91.html},
crossref = {DBLP:conf/pods/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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 righ-linear transformations, where applicable, are alternatives to the magic-sets transformation. In the presence of alternative optimization, 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. We 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 righ-]inear program can be written as an equivalent left-linear program, and vice versa.
Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
