ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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 BibTeX

References

[Cardenas 1975]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[Christodoulakis 1981]
...
[Christodoulakis 1983a]
Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54 BibTeX
[Christodoulakis 1983b]
Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983) BibTeX
[Christodoulakis 1984a]
Stavros Christodoulakis: Estimating Block Selectivities. Inf. Syst. 9(1): 69-79,(1984) BibTeX
[Christodoulakis 1984b]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[Demolombe 1980]
Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX
[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) BibTeX
[Feller 1968]
...
[Kamel and King 1985]
Nabil Kamel, Roger King: A Model of Data Distribution Based on Texture Analysis. SIGMOD Conference 1985: 319-325 BibTeX
[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) BibTeX
[Kotz and Johnson 1977]
...
[Luk 1983]
W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983) BibTeX
[Marshall and Olkin 1979]
Albert W. Marshall, Ingram Olkin: Inequalities: Theory of Majorization and Its Application. Academic Press 1979, ISBN 0-12-473750-1
BibTeX
[Merrett and Otoo 1979]
T. H. Merrett, Ekow J. Otoo: Distribution Models of Relations. VLDB 1979: 418-425 BibTeX
[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 BibTeX
[Siler 1976]
Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976) BibTeX
[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) BibTeX
[Yao 1977]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[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) BibTeX

Referenced by

  1. Arun N. Swami, K. Bernhard Schiefer: Estimating Page Fetches for Index Scans with Finite LRU Buffers. VLDB J. 4(4): 675-701(1995)
  2. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
  3. Arun N. Swami, K. Bernhard Schiefer: Estimating Page Fetches for Index Scans with Finite LRU Buffers. SIGMOD Conference 1994: 173-184
  4. Pai-Cheng Chu: Estimating Block Selectivities for Physical Database Design. IEEE Trans. Knowl. Data Eng. 4(1): 89-98(1992)
  5. Peter Bodorik, J. Spruce Riordon, James S. Pyra: Deciding on Correct Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 4(3): 253-265(1992)
  6. Kyu-Young Whang, Brad T. Vander Zanden, Howard M. Taylor: A Linear-Time Probabilistic Counting Algorithm for Database Applications. ACM Trans. Database Syst. 15(2): 208-229(1990)
  7. Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
  8. Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989)
  9. Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
  10. Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
  11. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:28 2009