Avoiding Cartesian Products in Programs for Multiple Joins.

Shinichi Morishita: Avoiding Cartesian Products in Programs for Multiple Joins. PODS 1992: 368-379

@inproceedings{DBLP:conf/pods/Morishita92,
  author    = {Shinichi Morishita},
  title     = {Avoiding Cartesian Products in Programs for Multiple Joins},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {368-379},
  ee        = {http://doi.acm.org/10.1145/137097.137911, db/conf/pods/Morishita92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Avoiding Cartesian products is a common heuristic to reduce the search space of join expressions (orderings) over some set of relations. However, this heuristic cannot guarantee optimal join expressions in its search space because the cheapest Cartesian-product-free (CPF, for short) join expression could be significantly worse than an optimal non-CPF join expression. In a recent PODS, Tay [9] gave some conditions on actual relations that ensure the existence of an optimal CPF join expression; however, the conditions turn out to be applicable only in special cases. In this paper, we do not put any restrictions on actual relations, and we introduce a novel technique that derives programs consisting of joins, semijoins, and projections from CPF join expressions. Our main result is that for every join expression, there exists an equivalent CPF join expression from which we can derive a program whose cost is within a constant factor of the cost of an optimal join expression.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. 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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. 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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1010 KB]

References

[1]: Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[2]: Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[3]: Nathan Goodman, Oded Shmueli: The Tree Projection Theorem and Relational Query Processing. J. Comput. Syst. Sci. 28(1): 60-79(1984) BibTeX
[4]: Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172 BibTeX
[5]: 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
[6]: ...
[7]: Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX
[8]: Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[9]: Y. C. Tay: On the Optimality of Strategies for Multiple Joins. J. ACM 40(5): 1067-1086(1993) BibTeX
[10]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[11]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[12]: Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[13]: Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]