|
|
|
@inproceedings{DBLP:conf/pods/GuptaM92,
author = {Ashish Gupta and
Inderpal Singh Mumick},
title = {Magic-sets Transformation in Nonrecursive Systems},
booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 2-4, 1992, San Diego,
California},
publisher = {ACM Press},
year = {1992},
isbn = {0-89791-519-4},
pages = {354-367},
ee = {http://doi.acm.org/10.1145/137097.137908, db/conf/pods/GuptaM92.html},
crossref = {DBLP:conf/pods/92},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
A nonrecursive system is any database system whose query language does not support recursive queries. Thus, many existing commerical SQL database systems are nonrecursive systems. Query optimization is an important issue for nonrecursive queries, and the magic-sets transformation has been shown to improve the performance of nonrecursive queries by many orders of magnitude [MFPR90]. It is thus important to use the magic-sets transformation in nonrecursive systems.
However, there is a problem. The magic-sets optimization can transform a nonrecursive query into a recursive query. Since a recursive query cannot be executed by a nonrecursive system, such a transformation is fatal. The magic-sets transformation cannot therefore be used in nonrecursive systems.
In this paper we present algorithms that achieve the optimization of the magic-sets transformation while guaranteeing that the transformed program will be nonrecursive whenever the original program is nonrecursive. The algorithms can be extended to the supplementary magic-sets transformation. We also define a new optimization technique for recursive and nonrecursive queries, covered subgoal elimination, that can eliminate subgoals from a rule, and can sometimes convert a recursive query into a nonrecursive one.
The algorithms presented in this paper are of practical relevance since they make it possible to incorporate the magic-sets transformation into existing commercial database systems.
Copyright © 1992 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.
