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) BibTeX

[BlE 75]

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

[Cod 70]

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

[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) BibTeX

[FKe 77]

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

[Got 75]

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

[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) BibTeX

[Hoa 72]

...

[Mer 78]

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

[Mer 78]

...

[Pec 75]

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

[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) BibTeX

Referenced by

1. Paolo Ciaccia, Dario Maio: Domains and Active Domains: What This Distinction Implies for the Estimation of Projection Sizes in Relational Databases. IEEE Trans. Knowl. Data Eng. 7(4): 641-655(1995)
2. Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244
3. Chung-Min Chen, Nick Roussopoulos: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994: 161-172
4. Yannis E. Ioannidis, Stavros Christodoulakis: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM Trans. Database Syst. 18(4): 709-748(1993)
5. Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267
6. Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513
7. Meng Chang Chen, Lawrence McNamee, Norman S. Matloff: Selectivity Estimation Using Homogeneity Measurement. ICDE 1990: 304-310
8. Danièle Gardy, Claude Puech: On the Effects of Join Operations on Relation Sizes. ACM Trans. Database Syst. 14(4): 574-603(1989)
9. Rafiul Ahad, K. V. Bapa Rao, Dennis McLeod: On Estimating the Cardinality of the Projection of a Database Relation. ACM Trans. Database Syst. 14(1): 28-40(1989)
10. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
11. Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127
12. Francesco M. Malvestuto: Modelling Large Bases of Categorial Data With Acyclic Schemes. ICDT 1986: 323-340
13. Nabil Kamel, Roger King: A Model of Data Distribution Based on Texture Analysis. SIGMOD Conference 1985: 319-325
14. Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
15. T. H. Merrett: Comments on "Note on the Expected Size of a Join". SIGMOD Record 13(1): 13(1982)