Implementation of Magic-sets in a Relational Database System.

@inproceedings{DBLP:conf/sigmod/MumickP94,
  author    = {Inderpal Singh Mumick and
               Hamid Pirahesh},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Implementation of Magic-sets in a Relational Database System},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {103-114},
  ee        = {http://doi.acm.org/10.1145/191839.191860, db/conf/sigmod/MumickP94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

• We use a cost-based heuristic for determining join order (sips) before applying magic.
• We push all equality and non-equality predicates using magic, replacing traditional predicate pushdown optimizations.
• We apply magic to full SQL with duplicates, aggregation, null values, and subqueries.
• We integrate magic with other relational optimization techniques.
• The implementation is extensible.

Copyright © 1994 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BMSU86]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX

[BR91]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) BibTeX

[Day87]

Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX

[DMP93]

Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156 BibTeX

[FF93]

Jerome Fessy, Béatrice Finance: Early Experience with Recursion Optimization in an Extensible Rewriter. Australian Database Conference 1993: 262-273 BibTeX

[GM92]

Ashish Gupta, Inderpal Singh Mumick: Magic-sets Transformation in Nonrecursive Systems. PODS 1992: 354-367 BibTeX

[GW87]

Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX

[HCL+90]

Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX

[Kim82]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[Loh88]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX

[MFPR90a]

Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 BibTeX

[MFPR90b]

Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330 BibTeX

[MNS+87]

Katherine A. Morris, Jeffrey F. Naughton, Yatin P. Saraiya, Jeffrey D. Ullman, Allen Van Gelder: YAWN! (Yet Another Window on NAIL!). IEEE Data Eng. Bull. 10(4): 28-43(1987) BibTeX

[MPR90]

Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX

[MPR94]

...

[Mum91]

Inderpal Singh Mumick: Query Optimization in Deductive and Relational Databases. Ph.D. thesis, Department of Computer Science, Stanford University 1991
BibTeX

[Mur82]

M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX

[NT88]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[PHH88]

Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX

[Ram88]

Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX

[RSS92]

Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250 BibTeX

[SAC+79]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[TPCD94]

...

[Ull88]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ull89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[VRK+90]

Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey: Design Overview of the Aditi Deductive Database System. Workshop on Deductive Databases 1990: 0- BibTeX

Referenced by

1. Qi Cheng, Jarek Gryz, Fred Koo, T. Y. Cliff Leung, Linqi Liu, Xiaoyan Qian, K. Bernhard Schiefer: Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. VLDB 1999: 687-698
2. Jia Liang Han: Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations. VLDB J. 7(1): 1-11(1998)
3. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
4. Hamid Pirahesh, T. Y. Cliff Leung, Waqar Hasan: A Rule Engine for Query Transformation in Starburst and IBM DB2 C/S DBMS. ICDE 1997: 391-400
5. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
6. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
7. Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458
8. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
9. Kotagiri Ramamohanarao, James Harland: An Introduction to Deductive Database Languages and Systems. VLDB J. 3(2): 107-122(1994)
10. Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67