Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence.

Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14

@inproceedings{DBLP:conf/sigmod/SalzaT89,
  author    = {Silvio Salza and
               Mario Terranova},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Evaluating the Size of Queries on Relational Databases with non
               Uniform Distribution and Stochastic Dependence},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {8-14},
  ee        = {http://doi.acm.org/10.1145/67544.66927, db/conf/sigmod/SalzaT89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The paper deals with the problem of evaluating how the originality of the attributes of a relation, i.e. the number of distinct values in each attribute, is affected by relational operations that reduce the cardinality of the relation. This is indeed an interesting problem in research areas such as database design and query optimization. Some authors have shown that non uniform distributions and stochastic dependence significantly affect the originality of the attributes. Therefore the models that have been proposed in the literature, based on uniformity and independence assumptions, in several situation can not be conveniently utilized. In this paper we propose a probabilistic model that overcomes the need of the uniformity and independence assumptions. The model is exact for non uniform distributions when the attributes are independent, and gives approximate results when stochastic dependence is considered. In the latter case the analytical results have been compared with a simulation, and proved to be quite accurate.

Copyright © 1989 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 ...

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library

References

[1]: Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX
[2]: Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[3]: Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983) BibTeX
[4]: Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[5]: 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
[6]: Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[7]: Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX
[8]: W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983) BibTeX
[9]: Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251 BibTeX
[10]: Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163 BibTeX
[11]: ...
[12]: ...
[13]: Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127 BibTeX
[14]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[15]: George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
BibTeX

Referenced by

Silvio Salza, Massimiliano Renzetti: A Modeling Tool for Workload Analysis and Performance Tuning of Parallel Database Applications. ADBIS 1997: 152-161
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)
Peter Bodorik, J. Spruce Riordon, James S. Pyra: Deciding on Correct Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 4(3): 253-265(1992)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]