Asymptotically error - optimal shape of sampling zone for query selectivity estimation method based on discrete cosine transform

• Autorzy: Augustyn D. R.

Warianty tytułu

PL

Asymptotycznie optymalny kształt strefy próbkowania w metodzie szacowania selektywności zapytań, opartej na dyskretnej transformacie kosinusowej

• Języki publikacji: EN

Abstrakty

EN

The problem of query selectivity estimation for database queries is critical for efficient query execution by database management systems. A query execution method strongly depends on early estimated size of a query result. This estimation determines a data access method used later during the query execution. The selectivity parameter is a fraction of table rows that satisfy a single-table query condition. For a selection condition of a range query where an attribute has a continuous domain, the selectivity is equivalent to a definite integral form probability density function (PDF) of attribute values distribution. For a compound selection condition based on many attributes we need a multidimensional space-efficient non-parametric estimator of multivariate PDF of attribute values distribution. A known approach based on Discrete Cosine Transform (DCT) spectrum as an representation of multidimensional PDF is considered. The energy compaction property of DCT lets omit a region of spectrum coefficients with small absolute values without significant losing an accuracy of selectivity estimation. An area of relevant spectrum coefficients is called a sampling zone. Results of experiments from previous works shows that applying the reciprocal shape of the sampling zone gives the least selectivity estimation error subject to a predetermined size of the zone. The main result of this work is a theoretical confirmation of only experimental results from previous works. The paper presents the proof of the theorem that the reciprocal shape of the sampling zone is asymptotically error-optimal. The proof is based on calculus of variations and the isoperimetric problem.

PL

Szacowanie selektywności zapytań jest krytyczne dla efektywnej realizacji zapytań w systemach zarządzania bazami danych. Sposób realizacji zapytania zależy od wstępnego oszacowania rozmiaru danych spełniających kryteria zapytania. Takie oszacowanie pozwala wybrać metodę dostępu do danych użytą później podczas realizacji zapytania. Selektywność dla zapytań jednotablicowych to stosunek liczby wierszy spełniających kryteria zapytania do liczby wszystkich wierszy tablicy. Dla zakresowych warunków zapytania, określonych na atrybutach z ciągła dziedziną, selektywność jest całką oznaczoną z funkcji gęstości prawdopodobieństwa (PDF), określającej rozkład wartości tego atrybutu. Dla złożonych warunków zapytania, opartych na kilku atrybutach, istnieje potrzeba użycia nieparametrycznego estymatora wielowymiarowej PDF, którego reprezentacja powinna być oszczędna pod względem zajętości pamięci. Jedno ze znanych podejść do konstrukcji takiego estymatora oparte jest na dyskretnej transformacie kosinusowej (DCT) - tzn. widmie z histogramu wielowymiarowego. Własność kompakcji energii pozwala na pominięcie nieznaczących współczynników widma DCT bez istotnej utraty oszacowania selektywności. Obszar znaczących współczynników widma nazywany jest strefą próbkowania. Wyniki prac eksperymentalnych innych autorów wskazują, że dla zadanego rozmiaru reprezentacji widma, optymalną strefą próbkowania (kształtem strefy o najmniejszym błędzie oszacowania selektywności) jest tzw. strefa odwrotnie proporcjonalna. Głównym wynikiem tego opracowania jest teoretyczne potwierdzenie tych eksperymentów. Artykuł przedstawia dowód twierdzenia o asymptotycznej optymalności strefy odwrotnie proporcjonalnej dla przypadku dwuwymiarowego. Dowód opiera się na elementach rachunku wariacyjnego i zagadnieniu izoperymetrycznym.

Słowa kluczowe

EN

query selectivity estimation; probability density function; discrete cosine transform; calculus of variations; isoperimetric problem

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2012
• Tom: Vol. 24, No. 1
• Strony: 3--22
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Augustyn D. R.

• Silesian Technical University, Institute of Informatics, 16 Akademicka St., 44-100 Gliwice, Poland,

Bibliografia

• 1. N. Bruno, S. Chaudhuri, L. Gravano: STHoles: a multidimensional workload-aware histogram, Proc. of ACM SIGMOD Int. Conf. on Management of Data 30(2), ACM, New York (2001) 211-222.
• 2. B. Brunt: The Calculus of Variations, Series Universitext. Springer-Verlag (2004).
• 3. K. Chakrabarti, M. Garofalakis, R. Rastogi, K. Shim: Approximate query processing using wavelets, The VLDB Journal 10(2-3), Springer-Verlag, New York (2001) 199-223.
• 4. D. Fuchsa, Z. Zhen Heb, B. S. Lee: Compressed histograms with arbitrary bucket layouts for selectivity estimation, Information Sciences. Volume 177, Issue 3, 1 (2007) 680-702.
• 5. L. Getoor, B. Taskar, D. Koller: Selectivity estimation using probabilistic models, Proc. of ACM SIGMOD Int. Conf. on Management of Data 30(2), ACM, New York (2001) 461-472.
• 6. D. Gunopulos, G. Kollios, V. J. Tsortas, C. Domeniconi: Selectivity estimator for multidimensional range queries over real attributes, The VLDB Journal 14(2), Springer-Verlag, New York (2005) 137-154.
• 7. Y. Ioannidis: The History of Histograms (abridged), Proc. of VLDB Conference (2003).
• 8. F. Korn, T. Johnson, H. V. Jagadish: Range Selectivity Estimation for Continuous Attributes, In Proc. International Conference on Scientific and Statistical Database Management (1999) 244-253.
• 9. L. Lee, K. Deok-Hwan, Ch. Chin-Wan: Multi-dimensional selectivity estimation using compressed histogram estimation information, Proc. of ACM SIGMOD Int. Conf. On Management of Data, ACM, Philadelphia (1999) 205-214.
• 10. Oracle 10g documentation, Using Extensible Optimizer Page http://download.oracle.com/docs/cd/B14117_01/appdev.101/b10800/dciextopt.htm
• 11. V. Possala, Y. E. Ioannidis: Selectivity estimation without the attribute value independence assumption, Proc. of the 23rd Int. Conf. on Very Large Databases, The VLDB Journal, Athens (1997) 486-495.
• 12. D. W. Scott, S. R. Sain: Multi-dimensional Density Estimator, Handbook of Statistics 24 North-Holland Publishing Co, Amsterdam (2004).
• 13. F. Yan,W-C. Hou, Z. Jiang, C. Luo, Q. Zhu: Selectivity estimation of range queries based on data density approximation via cosine series, Data & Knowledge Engineering 63(3), SienceDirect (2007) 855-878.