Ashish Gupta
ABSTRACT
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.
- BR87.Catriel Beeri and B.aghu Ramakrishnan. On the power of magic. In Proceedings o} the Sizth Symposium on Principles of Database Systems (PODS), pages 269-283, San Diego, CA, March 1987. ACM SIGACT-SIGMOD- SIGART. Google Scholar
Digital Library
- GM92.Ashish Gupta and Inderpa} Singh Mumick. Magic-sets transformation in non-recursive systems. Technical report, Stanford University, Stanford, CA 94305, USA, 1992. To be published.Google Scholar
- ISO90.ISO_ANSI. Iso-ansi working draft: Database language sql2 and sql3; x3h2; iso/iec jtcl/sc21/wg3, 1990.Google Scholar
- MFPR90.Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic is relevant. In Proceeding# of A CM SIGMOD 1990 international Conference on Management o} Data, pages 247-258, Atlantic City, NJ, May 23-25 1990. Google ScholarDigital Library
- MPR90.Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. The magic of duplicates and aggregates. In Proceedings oJ the Sixteenth International Conference on Very Large Databases (VLDB), pages 264- 277, Brisbane, Australia, August 13-16 t990. Google ScholarDigital Library
- Mum91.Inderpal Singh Mumick. Query Optimization in Deductive and Relational Databases. PhD thesis, Stanford University, Stanford, CA 94305, USA, December 1991.Google Scholar
- Nau86.Jeffrey F. Naughton. Data independent recursion in deductive database#. In P#oeeedings of the Fifth Symposium on Principles of Database Systems (PODS), pages 267-279, Cambridge, MA, 1986. Google ScholarDigital Library
- TS84.H. Tamald and T. Sato. Unfold/fold transformations in logic programs. In S. A. Tarnhnd, editor, Proc. of #he Second International Con. ference on Logzc Programming, pages 127- 138, Uppsala, Sweden, 1984.Google Scholar
- Ull89.Jeffrey D. Ultman. Principles of Database and Knowledge-Base Systems, Volumes I and #. Computer Science Press, 1989. Google ScholarDigital Library
Index Terms
- Magic-sets transformation in nonrecursive systems
Recommendations
On the Equivalence of Recursive and Nonrecursive Datalog Programs
Special issue: dedicated to the memory of Paris KanellakisWe study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. Since nonrecursive Datalog programs are equivalent to unions of conjunctive queries, we study also the problem of ...
Magic conditions
Much recent work has focused on the bottom-up evaluation of Datalog programs [Bancilhon and Ramakrishnan 1988]. One approach, called magic-sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation ...
Magic conditions
PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMuch recent work has focussed on the bottom-up evaluation of Datalog programs. One approach, called Magic-Sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts ([BMSU86, ...
Comments