Magic-sets transformation in nonrecursive systems

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.

REFERENCES

• BR87: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 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.
• ISO90: ISO_ANSI. Iso-ansi working draft: Database language sql2 and sql3; x3h2; iso/iec jtcl/sc21/wg3, 1990.
• MFPR90: I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.247-258, May 23-26, 1990, Atlantic City, New Jersey, United States
• MPR90: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• Mum91: Inderpal Singh Mumick. Query Optimization in Deductive and Relational Databases. PhD thesis, Stanford University, Stanford, CA 94305, USA, December 1991.
• Nau86: Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15420]
• 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.
• Ull89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

General Terms:
Algorithms, Languages, Theory