ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Design and Analysis of a Relational Join Operation for VLSI.

M. J. Menon, David K. Hsiao: Design and Analysis of a Relational Join Operation for VLSI. VLDB 1981: 44-55
@inproceedings{DBLP:conf/vldb/MenonH81,
  author    = {M. J. Menon and
               David K. Hsiao},
  title     = {Design and Analysis of a Relational Join Operation for VLSI},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {44-55},
  ee        = {db/conf/vldb/MenonH81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we will first prqpase a new organization of processors and memories for hardware realization of the relational join operation. Algorithmic analysis of the time complexity of the join operation shows that it is linear in the cardinalities of the source, target and result relations which is optimal.

Queueing analysis of the join operation is also used to arrive at closed-form equations for various design parameters such as the sizes of the memories associated with the processors. It is seen that in order to perform joins at a rate commensurate with the output rate of relational tuples, the memories associated with the processors in the hardware must satisfy certain constraints of speed and size. The various constraints and their order of importance are clearly indicated.

We also show how to select an optimum chip design for the join operation, where the design is considered optimal if it gives the best performance for a certain fixed cost. This method may be employed by database machine designers in order to arrive at the optimal values for

(1) the number of processors on a chip, and
(2) the sizes of the memories to be placed on a chip.

Due to the length of the paper, it is not possible to describe the extensions of this method to perform inequality joins and m-way joins. We also exclude a favorable comparison of this method with other schemes proposed for some other database machines. However, the reader may obtain detailed expositions on the extensions and comparative study in the References9.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
...
[7]
...
[8]
...
[9]
...
[10]
...
[11]
...
[12]
...
[13]
...
[14]
...
[15]
...

Copyright © Tue Mar 16 02:21:56 2010 by Michael Ley (ley@uni-trier.de)