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

[BR91]

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

[Day87]

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

[DMP93]

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

[FF93]

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

[GM92]

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

[GW87]

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

[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)

[Kim82]

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

[Loh88]

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

[MFPR90a]

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

[MFPR90b]

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

[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)

[MPR90]

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

[MPR94]

...

[Mum91]

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

[Mur82]

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

[NT88]

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

[PHH88]

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

[Ram88]

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

[RSS92]

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

[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

[TPCD94]

...

[Ull88]

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

[Ull89]

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

[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-