Evaluation of the Size of a Query Expressed in Relational Algebra.

@inproceedings{DBLP:conf/sigmod/Richard81,
  author    = {Philippe Richard},
  editor    = {Y. Edmund Lien},
  title     = {Evaluation of the Size of a Query Expressed in Relational Algebra},
  booktitle = {Proceedings of the 1981 ACM SIGMOD International Conference on
               Management of Data, Ann Arbor, Michigan, April 29 - May 1, 1981},
  publisher = {ACM Press},
  year      = {1981},
  pages     = {155-163},
  ee        = {http://doi.acm.org/10.1145/582318.582343, db/conf/sigmod/Richard81.html},
  crossref  = {DBLP:conf/sigmod/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a probabilistic model for evaluating the size of relations derived from given relations through relational algebra operators. We define tools to estimate the derived relations size and we state the assumptions underwhich we perform such an evaluation.

The particular class of data base schemata in which we evaluate the derived relation size is characterized by properties such as independence between two relations having union-compatible domains or independence between distinct tuples in a relation. We show that, knowing the expected size of all projections of each relation in the database, we can compute the size of each query expressed in relational algebra and we give the results for each operator of this language (selection, projection, union, intersection, theta-join).

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

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

• 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/smod7592 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

Online Edition: ACM Digital Library

References

[CHIU 80]

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX

[CLAU 80]

Svend-Erik Clausen: Optimizing the evaluation of calculus expressions in a relational database system. Inf. Syst. 5(1): 41-54(1980) BibTeX

[CODD 70]

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

[CODD 71]

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

[DEMO 80]

Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX

[EPST 79]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX

[RICH 80]

...

Referenced by

1. Danièle Gardy, Claude Puech: On the Effects of Join Operations on Relation Sizes. ACM Trans. Database Syst. 14(4): 574-603(1989)
2. Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
3. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
4. Erol Gelenbe, Danièle Gardy: The Size of Projections of Relations Satisfying a Functional Dependency. VLDB 1982: 325-333
5. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198