Estimating Block Accessses when Attributes are Correlated.

Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127

@inproceedings{DBLP:conf/vldb/ZandenTB86,
  author    = {Brad T. Vander Zanden and
               Howard M. Taylor and
               Dina Bitton},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Estimating Block Accessses when Attributes are Correlated},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {119-127},
  ee        = {db/conf/vldb/ZandenTB86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Most database systems fallaciously assume that attributes are independent. This assumption leads such systems to systematically overestimate the costs of queries and thus to select execution strategies that substantially increase the queries' prooessing time. In this paper we show how the concepts of Schur concavity and majorization can be used to efficiently estimate the cost of a query when the queried attribute is correlated with the clustering attribute. We will also examine how a block access distribution can be constructed when attributes are correlated in this manner.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" 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/vldb7588 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

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents

References

[Cardenas 1975]: Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975)
[Christodoulakis 1981]: ...
[Christodoulakis 1983a]: Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54
[Christodoulakis 1983b]: Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983)
[Christodoulakis 1984a]: Stavros Christodoulakis: Estimating Block Selectivities. Inf. Syst. 9(1): 69-79,(1984)
[Christodoulakis 1984b]: Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
[Demolombe 1980]: Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63
[Fagin et al.1979]: Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)
[Feller 1968]: ...
[Kamel and King 1985]: Nabil Kamel, Roger King: A Model of Data Distribution Based on Texture Analysis. SIGMOD Conference 1985: 319-325
[Kerschberg et al.1982]: Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
[Kotz and Johnson 1977]: ...
[Luk 1983]: W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983)
[Marshall and Olkin 1979]: Albert W. Marshall, Ingram Olkin: Inequalities: Theory of Majorization and Its Application. Academic Press 1979, ISBN 0-12-473750-1
[Merrett and Otoo 1979]: T. H. Merrett, Ekow J. Otoo: Distribution Models of Relations. VLDB 1979: 418-425
[Montgomery et al.1984]: ...
[Piatetsky-Shapiro et al.1984]: Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
[Siler 1976]: Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976)
[Vander Zanden et al.1985]: Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: A general framework for computing block accesses. Inf. Syst. 12(2): 177-190(1987)
[Yao 1977]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)
[Zahorjan et al.1983]: John Zahorjan, Barbara J. Bell, Kenneth C. Sevcik: Estimating Block Transfers When Record Access Probabilities are Non-Uniform. Inf. Process. Lett. 16(5): 249-252(1983)