Exploiting data-distribution patterns in modeling tuple selectivities in a database

DOI10.1016/0020-0255(93)90038-NMaRDI QIDQ1803861zbMATH OpenFDO

Authors Yanyan Li

Publication date 29 June 1993

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(93)90038-N

zbMATH Keywords

data distributionquery evaluationtuple selectivity

Mathematics Subject Classification ID

Database theory (68P15)

Review text

The paper concerns an estimation of the number of tuples satisfying a database query. The model is based on data distribution and is independent of an used database system. Queries are considered over one relation modelled as multidimensional bit map. A partial-range query specifies a hyperrectangle within a bit map. The main idea of the paper is the following: if the 1's in the bit map are distributed not homogeneously, then the map is divided into cells in which the 1's are distributed homogeneously. Much of the paper is devoted to obtaining the best trade-off between storage requirements for bit map representation and accuracy of estimates of the number of 1's is any hyperrectangle. The authors discuss in the first four chapters a number of other approaches related to the problem. In Chapter 5, they define a new notion of homogeneity and compare it with related notions occurred in the literature. Chapter 6 contains a new method based on sampling. It is shown that it requires a sample size of 100 to produce accurate estimates 95\% of the time. The paper is written in detail but not homogeneously. All new ideas are presented rather briefly in comparing to the parts explaining other approaches etc. Any discussion concerning an implementation of the method in a database environment is not presented here.

Recommendations

• scientific article; zbMATH DE number 2084426
• scientific article; zbMATH DE number 4213430
• scientific article; zbMATH DE number 3887116
• Heuristics for selecting robust database structures with dynamic query patterns
• Tuple source relational model: A source-aware data model for multidatabases

Cites work

• A stochastic evaluation model for database organizations in data retrieval systems
• Estimating block selectivities
• Implications of certain assumptions in database performance evauation

Cited in

(11)

• Cardinality estimation in numeric on-line databases
• Evaluating clustering factor approach to estimating block selectivities
• Selectivity and cost estimation for joins based on random sampling
• Safe projections of binary data sets
• scientific article; zbMATH DE number 1717355 (Why is no real title available?)
• Some estimations in database queries
• Statistical profile estimation in database systems
• Estimating optimal parameters for parallel database hardware
• scientific article; zbMATH DE number 591246 (Why is no real title available?)
• Estimating block selectivities
• An extensible model of selectivity estimation

This page was built for publication: Exploiting data-distribution patterns in modeling tuple selectivities in a database

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803861)