Title :
Query result size estimation using the Trapezoidal Attribute Cardinality Map
Author :
Oommen, B. John ; Thiyagarajah, Murali
Author_Institution :
Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont., Canada
Abstract :
Histogram techniques are used to efficiently estimate query result sizes in most of the modern-day database systems. In a recent work (Oommen and Thiyagarajah, 1999), we introduced a new histogram-like approximation strategy, called the Rectangular Attribute Cardinality Map (R-ACM), which approximates the density function within a given sector by a rectangular cell. In this paper, we introduce another histogram-like approximation strategy, called the Trapezoidal Attribute Cardinality Map (T-ACM) that approximates the density function within a given sector by a trapezoidal cell, where the slope of the trapezoid is obtained so as to fix the actual probability mass within the cell. We present numerous analytic and experimental results concerning the T-ACM demonstrating its superiority over the traditional equi-width and equi-depth histograms for query result size estimation. We hope that with the R-ACM introduced in (Oommen and Thiyagarajah, 1999), the T-ACM could become an invaluable tool for query optimization in the future database systems
Keywords :
database theory; maximum likelihood estimation; optimisation; probability; query processing; R-ACM; Rectangular Attribute Cardinality Map; T-ACM; Trapezoidal Attribute Cardinality Map; density function approximation; equi-depth histograms; equi-width histograms; experimental results; histogram-like approximation strategy; probability; query optimization; query result size estimation; Bibliographies; Computer errors; Computer science; Councils; Database systems; Density functional theory; Histograms; Probability; Sampling methods; Statistical distributions;
Conference_Titel :
Database Engineering and Applications Symposium, 2000 International
Conference_Location :
Yokohama
Print_ISBN :
0-7695-0789-1
DOI :
10.1109/IDEAS.2000.880582