AbstractWe analyze the optimization effect of the ``magic sets'' rewriting technique for datalog queries and present some supplementary or alternative techniques that avoid many shortcomings of the basic technique. Given a magic sets rewritten query, the set of facts generated for the original, nonmagic predicates by the seminaive bottom-up evaluation is characterized precisely. It is shown that -- because of the additional magic facts -- magic sets processing may result in generating an order of magnitude more facts than the straightforward naive evaluation. A refinement of magic sets called factorized magic sets is defined. These magic sets retain most of the efficiency of original magic sets in regards to the number of nonmagic facts generated and have the property that a linear-time bound with respect to seminaive evaluation is guaranteed in all cases. An alternative technique for magic sets, called envelopes, which has several desirable properties over magic sets, is introduced. Envelope predicates are never recursive with the original predicates; thus, envelopes can be computes as a preprocessing task. Envelopes also allow the utilization of multiple sideways information passing strategies (sips) for a rule. An envelope-transformed program may be ``readorned'' according to another choice of sips and reoptimized by magic sets (or envelopes), thus making possible an optimization effect that cannot be achieved by magic sets based on a particular choice of sips.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in:
- Seppo Sippu and Eljas Soisalon-Soininen. An optimization strategy for recursive queries in logic databases. In Proceedings of the Fourth International Conference on Data Engineering, pages 470-477, Los Angeles, California, USA, 1-5 February 1988. IEEE Computer Society.
- Seppo Sippu and Eljas Soisalon-Soininen. Multiple SIP strategies and bottom-up adorning in logic query optimization. In S. Abiteboul and P. C. Kanellakis, editors, ICDT'90, Third International Conference on Database Theory, volume 470 of Lecture Notes in Computer Science, pages 485-498, Paris, France, 12-14 December 1990. Springer.
Categories and Subject Descriptors: H.2.4 [Database Management]: Systems -- query processing; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving -- logic programming
General Terms: Algorithms, Languages, Theory
Additional Key Words and Phrases: Datalog, envelopes, logic query, magic sets
Selected references
- François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 1-16, Cambridge, Massachusetts, 24-26 March 1986.
- François Bancilhon and Raghu Ramakrishnan. An amateur's introduction to recursive query processing strategies. In Carlo Zaniolo, editor, Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, pages 16-52, Washington, D.C., 28-30 May 1986. SIGMOD Record 15(2), June 1986.
- Catriel Beeri and Raghu Ramakrishnan. On the power of magic. In Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 269-283, San Diego, California, 23-25 March 1987.
- Catriel Beeri and Raghu Ramakrishnan. On the power of magic. Journal of Logic Programming, 10(1/2/3-4):255-299, January 1991.
- Allen Van Gelder. A message passing framework for logical query evaluation. In Carlo Zaniolo, editor, Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, pages 155-165, Washington, D.C., 28-30 May 1986. SIGMOD Record 15(2), June 1986.
- Ashish Gupta and Inderpal Singh Mumick. Magic-sets transformation in nonrecursive systems. In Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 354-367, San Diego, California, 2-4 June 1992.
- Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic conditions. In Proceedings of the Nith ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 314-330, Nashville, Tennessee, 2-4 April 1990.
- Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, and Raghu Ramakrishnan. Magic is relevant. In Hector Garcia-Molina and H. V. Jagadish, editors, Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pages 247-258, Atlantic City, NJ, 23-25 May 1990. SIGMOD Record 19(2), June 1990.
- Jeffrey F. Naughton. One-sided recursions. Journal of Computer and System Sciences, 42(2):199-236, April 1991.
- Raghu Ramakrishnan. Magic templates: A spellbinding approach to logic programs. Journal of Logic Programming, 11(3-4):189-216, October/November 1991.
- H. Seki. On the power of Alexander templates. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 150-159, Philadelphia, Pennsylvania, 29-31 March 1989.
- Jeffrey D. Ullman. Implementation of logical query languages for databases. ACM Transactions on Database Systems, 10(3):289-321, September 1985.
- Jeffrey D. Ullman. Bottom-up beats top-down for Datalog. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 140-149, Philadelphia, Pennsylvania, 29-31 March 1989.