On the optimality of strategies for multiple join

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the optimality of strategies for multiple join

Full text

Pdf (1.31 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 5 (November 1993) table of contents

Pages: 1067 - 1086

Year of Publication: 1993

ISSN:0004-5411

Author

Y. C. Tay

National University of Singapore, Kent Ridge, Singapore

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 25, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174147.174151 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
	2	Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
	3	Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
	4	S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
	5	Stavros Christodoulakis , Daniel Alexander Ford, Retrieval performance versus disc space utilization on WORM optical discs, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.306-314, June 1989, Portland, Oregon, United States
	6	David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	7	Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983 [doi>10.1145/2402.322390]
	8	Nathan Goodman , Oded Shmueli, Tree queries: a simple class of relational queries, ACM Transactions on Database Systems (TODS), v.7 n.4, p.653-677, Dec. 1982 [doi>10.1145/319758.319775]
	9	Goetz Graefe, Rule-based query optimization in extensible database systems, 1987
	10	~HONEYMAN, P. Extension lores. In Proccedttzga of the International Conference on Very Lal~c ~Data Bases (Montreal, Canada, Oct ). ACM, New York, 1980, pp. 239-244
	11	Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
	12	Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
	13	Mark Levene , George Loizou, &ggr;-acyclic database schemes and nested relations, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
	14	Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
	15	~OSBORN, S.L. Normal forms for relational databases Res. Rep. CS-78-06, Dept. of Com- ~puter Science, Umv Waterloo, Waterloo, Ont., Canada, 1978.
	16	James P. Richardson , Hongjun Lu , Krishna Mikkilineni, Design and evaluation of parallel pipelined join algorithms, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.399-409, May 27-29, 1987, San Francisco, California, United States
	17	Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
	18	~ROSENTHAL, A., DAYAL, U., AND REINER, D. Speeding a query optimizer: The pilot pass ~approach. Manuscript, 1990.
	19	Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
	20	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	21	A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
	22	Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
	23	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	24	~WH4NG, K.Y. Query optimizatJon m Office-by-Example. IBM Rcs. Rep. RCl1571. IBM ~T J. Watson Research Center, Yorktown Heights, N.Y. 1985.
	25	Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
	26	~Y^NNAKAMS, M. Algorithms for acyclic database schemes. In Proceedtngs of the blternattonal ~Conference on k~rv Large Data Bases (Cannes, France, Sept.). 1982, pp. 82-94
	27	S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979 [doi>10.1145/320071.320072]

CITED BY 4

	Shinichi Morishita, Avoiding Cartesian products for multiple joins, Journal of the ACM (JACM), v.44 n.1, p.57-85, Jan. 1997
	Augustine C. Ikeji , Farshad Fotouhi, Computation of partial query results with an adaptive stratified sampling technique, Proceedings of the fourth international conference on Information and knowledge management, p.145-149, November 29-December 02, 1995, Baltimore, Maryland, United States
	Ram D. Gopal , R. Ramesh , Stanley Zionts, Criss-Cross Hash Joins: Design and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.637-653, July 2001
	Yingying Tao , Qiang Zhu , Calisto Zuzarte , Wing Lau, Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.279-293, October 06-09, 2003, Toronto, Ontario, Canada