Inderpal Singh Mumick
Hamid Pirahesh
ABSTRACT
Much 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, BR87, Ram88]). It is widely believed that the principal application of the Magic-Sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the Magic-Set transformation to use predicates other than equality (X > 10, for example). This Extended Magic-Set technique has practical utility in “real” relational databases, not only for recursive queries, but for non-recursive queries as well; in ([MFPR90]) we use the results in this paper and those in [MPR89] to define a magic-set transformation for relational databases supporting SQL and its extensions, going on to describe an implementation of magic in Starburst ([HFLP89]). We also give preliminary performance measurements.
In extending Magic-Sets, we describe a natural generalization of the common class of bound (b) and free (ƒ) adornments. We also present a formalism to compare adornment classes.
- BKMR89.Isaac Balbin, David B. Kemp, Krishnamurthy Meenakshi, and Kotagiri Ramamohanarao. Propagating Constraints in Recursive Deductive Databases. In North American Conference on Logic Programming (NACLP), Cleveland, Ohio, October 16-20 1989.Google Scholar
- BMSU86.Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic Sets and other Strange Ways to Implement Logic Programs. In Proceedings of the Fifth Symposium on Principles of Database Systems (PODS), pages 1-15, ACM SIGACT- SIGMOD-SIGART, March 1986. Google ScholarDigital Library
- BR87.Catriel Beeri and Raghu Ramakrishnan. On the Power of Magic. In Proceedings of the Sixth Symposium on Principles of Database Systems (PODS), pages 269-283, ACM SIGACT-SIGMOD-SIGART, March 1987. Google ScholarDigital Library
- HFLP89.Laura M. Haas, J. C. Freytag, Guy M. Lohman, and Hamid Pirahesh. Extensible Query Processing in Starburst. In Proceedings of A CM SIGMOD 1989 International Conference on Management of Data, Portland, OR, pages 377-388, May 1989. Google ScholarDigital Library
- HP88.Waqar Hasan and Hamid Pirahesh. Query Rewrite Optimization in Starburst. Research Report, RJ 6337 (62349), IBM Research Division, Computer Science, Almaden Research Center, San Jose, California 95120- 6099, August 4 1988.Google Scholar
- ISO88.ISO_ANSI. Working Draft; Database Language SQL2. 1988.Google Scholar
- MPR89.Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. Duplicates and Aggregates in Datalog. Research Report, IBM Reseaxch Division, Computer Science, Almaden Research Center, San Jose, California 95120-6099, December 1989.Google Scholar
- MFPR90.Inderpal Singh Mumick, Sheldon J. Finkelstein, IIamid Pirahesh, and Raghu Ramakrishnan. Magic is Relevant. Submitted to SIGMOD 1990. Google ScholarDigital Library
- Mor88.Katherine A. Morris. An Algorithm for Ordering Subgoals in HAIL!. in Proceedings of the Seventh Symposium on Principles of Database Systems (PODS), pages 82-88, ACM SIGACT-SIGMOD-SIGART, March 1988. Google ScholarDigital Library
- Ram88.Raghu Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programs. In Robert A. Kowalski and Keneth A. Bowen, editors, Logic Programming: Proceedings of the Fifth International Conference and Symposium, Seattle, Vol 1, pages 140-159, MIT Press, Cambridge, MA, August 1988.Google Scholar
- Ull88.Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, Volume 1. Computer Science Press, 1988. Google ScholarDigital Library
Index Terms
- Magic conditions
Recommendations
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 ...
Implementation of magic-sets in a relational database system
We describe the implementation of the magic-sets transformation in the Starburst extensible relational database system. To our knowledge this is the first implementation of the magic-sets transformation in a relational database system. The Starburst ...
Magic-sets transformation in nonrecursive systems
PODS '92: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsA 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 ...
Comments