Distribution Models of Relations.

@inproceedings{DBLP:conf/vldb/MerrettO79,
  author    = {T. H. Merrett and
               Ekow J. Otoo},
  editor    = {Antonio L. Furtado and
               Howard L. Morgan},
  title     = {Distribution Models of Relations},
  booktitle = {Fifth International Conference on Very Large Data Bases, October
               3-5, 1979, Rio de Janeiro, Brazil, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1979},
  pages     = {418-425},
  ee        = {db/conf/vldb/MerrettO79.html},
  crossref  = {DBLP:conf/vldb/79},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We show how relations can be modelled in fast memory by a distribution of tuples in a multidimensional space. Given distributions for operand relations we derive distributions for the relations that result from applying the relational algebra. We apply the result for the natural join to optimize the evaluation of an expression involving two joins. We suggest further applications. The analysis for division leads to a generalization of that operator.

C.R. Categories: 3.72, 4.33, 4.34 Key words and phrases: database, distribution of tuples, relational algebra, cost model, expression evaluation.

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

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[AdD 76]

...

[AsC 75]

Morton M. Astrahan, Donald D. Chamberlin: Implementation of a Structured English Query Language. Commun. ACM 18(10): 580-588(1975)

[BlE 75]

Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977)

[Cod 70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)

[Cod 72]

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)

[FKe 77]

Antonio L. Furtado, Larry Kerschberg: An Algebra of Quotient Relations. SIGMOD Conference 1977: 1-8

[Got 75]

Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63

[Hal 75]

Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976)

[Hoa 72]

...

[Mer 78]

T. H. Merrett: Relations as Programming Language Elements. Inf. Process. Lett. 6(1): 29-33(1977)

[Mer 78]

...

[Pec 75]

Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49

[SmC 75]

John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975)