~CHRISTODOULAKIS, S., AND FORD, D.A. Retrieval performance versus disc space utilization ~on WORM optical discs. In Proceedings of the 1989 ACM-SIGMOD International Conference ~on Management of Data (Portland, Or., June). ACM, New York, 1989, pp. 306-314.

Digital Library

Google Scholar

[6]

~DEWITT, D. J., KATZ, R. H., OLKEN, F., SHAPIRO, L. D., STONEBRAKER, M. R., AND WOOD, D. ~Implementation techniques for main memory database systems. In ?roceedings of the 1984 ~ACM-S1GMOD International Conference on Management of Data (Boston, Mass., June 18-21 ). ~ACM, New York, 1984, pp. 1-8.

Digital Library

Google Scholar

[7]

~FAGIN, R. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM ~30, 3 (July 1983), 514-550.

Digital Library

Google Scholar

[8]

~GOODMAN, N., AND StlMUELI, O. Tree queries. A simple class of relational queries.,4CM ~Trans. Data& Svst. 7, 4 (Dec. 1982), 653-677.

Digital Library

Google Scholar

[9]

~GRAEFE, G. Rule-based query optimization in extens~ble database systems. Ph.D disserta- ~tion, Department of Computer Scmnce, Univ of W~sconsm-Madison, Madison, Wisc., Nov. ~1987.

Digital Library

Google Scholar

[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

Google Scholar

[11]

~IBAR^KI, T., ~,ND KAMEDA, T. Oil the optimal nesting order for computing N-relational ~joins. ACM Trans Database S~6t. 9, 3 (Sept. 1984), 483 502.

Digital Library

Google Scholar

[12]

~KRISHNAMURTHY, R., BORAL, H., AND ZANIOLO, C. Optm~izat~on of nonrecurs~ve queries. In ~Proceedings of the lnternattonal Conjerence on Ven, Lalge Data Bases (Kyoto, Japan, Aug.), ~1986, pp. 128-137.

Digital Library

Google Scholar

[13]

~LEVENE, M., AND LOlZOU, G. T-acyclic database schemes and nested transactions. In Nested ~Relattons and Complex Objects m Databases, S. Abiteboul, P. C. Fischer, and H.-J. Schek, eds., ~Sprmger-Verlag, Berlin, 1989, pp. 313 323.

Digital Library

Google Scholar

[14]

~ONo, K., ^ND LOHMAN, G. M. Measuring the complexity of join enumeration m query ~optimization. In Proceedings of the Internatzonal Conference on k~ry Large Data Bases (Bris- ~banc, Australia, Aug.). 1990, pp. 314 325.

Digital Library

Google Scholar

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

Google Scholar

[16]

~RICHARDSON, J. P., LU, H.,\ND MIKKILINENI, K. Design and evaluation of parallel pipelined ~join algorithms. In Proceedings of the 1087 ACM-SIGMOD Internatzottal Conference on ~Management of Data (San Francisco, Calif., May 27 29) ACM, New York, 1987, pp. 399 409.

Digital Library

Google Scholar

[17]

~RISSANEN, J Independent components of relations. ACM Trmzs. Datab Syst 2, 4 (Dec. ~1977), 317 325.

Digital Library

Google Scholar

[18]

~ROSENTHAL, A., DAYAL, U., AND REINER, D. Speeding a query optimizer: The pilot pass ~approach. Manuscript, 1990.

Google Scholar

[19]

~SAGIV, Y. Can we use the universal instance assumption without using nulls? In Procee&ngs ~of the 1981 ACM-SIGMOD Internattonal Conference on Mattagement of Data (Ann Arbor, ~Mich., Apr. 29 May 1). ACM, New York, 1981, pp. 108 120.

Digital Library

Google Scholar

[20]

~SEIANGER, P. G., ASTRAHAN, M. M., CtqAMBERtAN, D. D., LORIE, P. A., AND PRICE, T. G. ~Access path selection in a relational database system. In Proceedings of the 1979 ACM- ~SIGMOD bzternatzonal Confere~zce otl Management o} Data (Boston, Mass., May 30-June 1). ~ACM, New York, 1979, pp. 23 34.

Digital Library

Google Scholar

[21]

~SWAML A. Optimization of large join queries: Combining heuristics and combinatorial ~techniques. In Proceedings of the }989 ACM-SIGMOD Intenzational Conference on Manage- ~mozt of Data (Portland, Ore., June). ACM, New York, 1989, pp. 367 376.

Digital Library

Google Scholar

[22]

~SWAMT, A., aND Gum'^, A. Optimizing large join queries. In Proceedings of the 1988 ~ACM-S1GMOD bzternatzollal Conference on Management o/ Data (Chicago, Ill., June 1-3). ~ACM, New York, 1988, pp. 8-17.

Digital Library

Google Scholar

[23]

~ULLMAN, J.D. Princtples o} Database and IOzowledge-Base Systems, vol. 1. Computer Science ~Press, Rockville, Md., 1988.

Digital Library

Google Scholar

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

Google Scholar

[25]

~WONG, E, AND YOUSSEFI, K. Decomposition--A strategy for query processing. ACM Trans. ~Data& Syst. 1, 3 (Sept. 1976), 223 241.

Digital Library

Google Scholar

[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

Google Scholar

[27]

~Y^o, S.B. Optimization of query evaluation algorithms. ACM Tran3 Datab. Syst. 4, 2 (June ~1979), 133-155.

Digital Library

Google Scholar

Cited By

View all

Ikeji AFotouhi F(2006)Optimization of constrained queries with a hybrid genetic algorithmDatabase and Expert Systems Applications10.1007/BFb0054495(342-352)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054495
Tao YZhu QZuzarte CLau WHarris HWoodsworth AKark AMüller H(2003)Optimizing large star-schema queries with snowflakes via heuristic-based query rewritingProceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research10.5555/961322.961365(279-293)Online publication date: 6-Oct-2003
https://dl.acm.org/doi/10.5555/961322.961365
Gopal RRamesh RZionts S(2001)Criss-Cross Hash JoinsIEEE Transactions on Knowledge and Data Engineering10.1109/69.94073713:4(637-653)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.1109/69.940737
Show More Cited By

Index Terms

On the optimality of strategies for multiple join
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)
    2. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Avoiding Cartesian products for multiple joins

Computing the natural join of a set of relations is an important operation in relational database systems. The ordering of joins determines to a large extent the computation time of the join. Since the number of possible orderings could be very large, ...
New algorithms for join and grouping operations

Traditional database query processing relies on three types of algorithms for join and for grouping operations. For joins, index nested loops join exploits an index on its inner input, merge join exploits sorted inputs, and hash join exploits ...
Optimization of joins using random record generation method
A2CWiC '10: Proceedings of the 1st Amrita ACM-W Celebration on Women in Computing in India

Joins are statements that retrieve data from more than one table. A Join is characterized by multiple tables in the FROM clause, and the relationship between the tables is defined through the existence of a Join condition in the WHERE clause. In the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 40, Issue 5

Nov. 1993

311 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/174147

Editor:
F. Thomson Leighton
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1993

Published in JACM Volume 40, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
478
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ikeji AFotouhi F(2006)Optimization of constrained queries with a hybrid genetic algorithmDatabase and Expert Systems Applications10.1007/BFb0054495(342-352)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054495
Tao YZhu QZuzarte CLau WHarris HWoodsworth AKark AMüller H(2003)Optimizing large star-schema queries with snowflakes via heuristic-based query rewritingProceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research10.5555/961322.961365(279-293)Online publication date: 6-Oct-2003
https://dl.acm.org/doi/10.5555/961322.961365
Gopal RRamesh RZionts S(2001)Criss-Cross Hash JoinsIEEE Transactions on Knowledge and Data Engineering10.1109/69.94073713:4(637-653)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.1109/69.940737
Morishita S(1997)Avoiding Cartesian products for multiple joinsJournal of the ACM10.1145/256292.25629644:1(57-85)Online publication date: 15-Jan-1997
https://dl.acm.org/doi/10.1145/256292.256296
Ikeji AFotouhi FNicholas C(1995)Computation of partial query results with an adaptive stratified sampling techniqueProceedings of the fourth international conference on Information and knowledge management10.1145/221270.221363(145-149)Online publication date: 2-Dec-1995
https://dl.acm.org/doi/10.1145/221270.221363

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Avoiding Cartesian products for multiple joins

New algorithms for join and grouping operations

Optimization of joins using random record generation method

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations