ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A New Way to Compute the Product and Join of Relations.

Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187
@inproceedings{DBLP:conf/sigmod/Kim80,
  author    = {Won Kim},
  editor    = {Peter P. Chen and
               R. Clay Sprowls},
  title     = {A New Way to Compute the Product and Join of Relations},
  booktitle = {Proceedings of the 1980 ACM SIGMOD International Conference on
               Management of Data, Santa Monica, California, May 14-16, 1980},
  publisher = {ACM Press},
  year      = {1980},
  pages     = {179-187},
  ee        = {http://doi.acm.org/10.1145/582250.582278, db/conf/sigmod/Kim80.html},
  crossref  = {DBLP:conf/sigmod/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents a new method of computing the product or join of n relations in a paged-memory environment. The method, termed the nested-block method, is an attempt to take maximum advantage of available main-memory buffer space. The problem of finding an optimal allocation of main-memory buffer space for the nested-block method of scanning n relations poses a nonlinear integer-programming problem. This paper first describes the operation of the nested-block method, and derives corresponding cost formula. It then presents an efficient heuristic algorithm for determining a near-optimal allocation of main-memory buffer space. The need to compute the product of relations arises naturally in processing n-relation queries. Conventional techniques for computing the join of relations can be complemented by the nested-block method. This paper examines these two important applications of the nested-block method.

Copyright © 1980 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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter P. Chen, R. Clay Sprowls (Eds.): Proceedings of the 1980 ACM SIGMOD International Conference on Management of Data, Santa Monica, California, May 14-16, 1980. ACM Press 1980 BibTeX
Contents

Online Edition: ACM Digital Library

References

[1]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[2]
...
[3]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[4]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[5]
E. F. Codd: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68 BibTeX
[6]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[7]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[8]
...
[9]
Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX
[10]
...
[11]
Robert M. Pecherer: Efficient Exploration of Product Spaces. SIGMOD Conference 1976: 169-177 BibTeX
[12]
James B. Rothnie Jr.: An Approach to Implementing a Relational Data Management System. SIGMOD Workshop, Vol. 1 1974: 277-294 BibTeX
[13]
...
[14]
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
[15]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[16]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[17]
...
[18]
...
[19]
...
[20]
...
[21]
...
[22]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[23]
S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77 BibTeX
[24]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
  2. Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla: Seeking the Truth About ad hoc Join Costs. VLDB J. 6(3): 241-256(1997)
  3. Jussi Myllymaki, Miron Livny: Relational Joins for Data on Tertiary Storage. ICDE 1997: 159-168
  4. Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, Limsoon Wong: A Data Transformation System for Biological Data Sources. VLDB 1995: 158-169
  5. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  6. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
  7. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  8. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  9. Mauro Negri, Giuseppe Pelagatti: Distributive Join: A New Algorithm for Joining Relations. ACM Trans. Database Syst. 16(4): 655-669(1991)
  10. Joel L. Wolf, Balakrishna R. Iyer, Krishna R. Pattipati, John Turek: Optimal Buffer Partitioning for the Nested Block Join Algorithm. ICDE 1991: 510-519
  11. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
  12. Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180
  13. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
  14. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
  15. Robert B. Hagmann: An Observation on Database Buffering Performance Metrics. VLDB 1986: 289-293
  16. Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
  17. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  18. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  19. Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
  20. Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264
  21. T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:23 2009