- Tytuł:
-
Asymptotically error - optimal shape of sampling zone for query selectivity estimation method based on discrete cosine transform
Asymptotycznie optymalny kształt strefy próbkowania w metodzie szacowania selektywności zapytań, opartej na dyskretnej transformacie kosinusowej - Autorzy:
- Augustyn, D. R.
- Powiązania:
- https://bibliotekanauki.pl/articles/375810.pdf
- Data publikacji:
- 2012
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
query selectivity estimation
probability density function
discrete cosine transform
calculus of variations
isoperimetric problem - Opis:
-
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.
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. - Źródło:
-
Theoretical and Applied Informatics; 2012, 24, 1; 3-22
1896-5334 - Pojawia się w:
- Theoretical and Applied Informatics
- Dostawca treści:
- Biblioteka Nauki
Artykuł