M2HSE - metoda estymacji selektywności pewnej klasy zapytań zakresowych oparta na wielowymiarowym rozkładzie wartości atrybutów oraz rozkładach brzegowych

• Autorzy: Augustyn D.

Warianty tytułu

EN

M2HSE - the selectivity estimation method based on multidimensional attribute values distribution and marginal ones for some kind of range queries

• Języki publikacji: PL

Abstrakty

PL

Selektywność jest parametrem wyznaczanym przez bazodanowy optymalizator zapytań w celu wczesnego oszacowania rozmiaru danych spełniających warunek zapytania. Jest to czynność niezbędna do znalezienia optymalnego planu wykonania zapytania. Selektywność jest na ogół oszacowywana na podstawie histogramów, które są nieparametrycznymi estymatorami rozkładów wartości atrybutów. Wyznaczanie selektywności dla zapytań z warunkiem selekcji opartym na kilku atrybutach wymaga wykorzystania wielowymiarowego histogramu estymującego łączny rozkład wartości atrybutów. Dokładność histogramów wielowymiarowych spada wraz ze wzrostem liczby wymiarów, co jest powszechnie znane pod nazwą problemu przekleństwa wymiarowości. Natomiast jednowymiarowe histogramy zbudowane dla pojedynczych atrybutów, które charakteryzują rozkład brzegowy, opisują ten jednowymiarowy rozkład dokładniej, ale oczywiście nie opisują zależności pomiędzy atrybutami. W niniejszym artykule zaproponowano metodę wyznaczania selektywności, opartą na histogramach opisujących zarówno rozkład łączny, jak i rozkłady brzegowe. Zaproponowana metoda (nazwana M2HSE) dotyczy pewnej klasy zapytań, w których zakresowy warunek selekcji oparty jest na wielu atrybutach. Dla takich zapytań przedstawiona metoda może pozwolić na wyznaczenie dokładniejszych przybliżeń wartości selektywności niż klasyczne metody, wykorzystujące histogramy opisujące tylko rozkład łączny albo tylko rozkłady brzegowe (gdzie zastosowane jest założenie o niezależności atrybutów).

EN

Selectivity is a parameter obtained by database query optimizer for early estimation of size of data that satisfying a query condition. This is needed for finding the optimal query execution plan. Commonly, selectivity is estimated using histograms that are non-parametric estimators of attribute values distribution. Obtaining a selectivity for a query with a selection condition bases on a few attributes requires a multimensional histogram estimating joint distribution. Accuracy of multidimensional histograms decreases for high dimensions. It is well-known as the curse of dimensionality problem. One-dimensional histograms describing marginal distributions are more accurate, but they do not describe dependency between attributes. In this paper we propose a method of selectivity estimation based on both types of histograms describing either a multidimensional joint distribution or marginal ones. The method (named M2HSE) may be used for some kind of queries with a range selection condition based on many attributes. For such kind of queries, this method may give more accurate selectivity estimations than classical methods based on multidimensional histogram only or marginal histograms only (where the AVI rule is assumed).

Słowa kluczowe

PL

estymacja selektywności zapytań; histogram; wielowymiarowy rozkład wartości atrybutów; rozkład brzegowy

EN

query selectivity estimation; histogram; multidimensional distribution of attribute values; marginal distribution

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2013
• Tom: Vol. 34, nr 2A
• Strony: 43--56
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Augustyn D.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska

Bibliografia

• 1. Ioannidis Y.: The History of Histograms (abridged). Proc. of VLDB Conference, 2003.
• 2. Poosala V., Ioannidis Y. E.: Selectivity Estimation Without the Attribute Value Independence Assumption. Proc. of the 23rd VLDB Conference, Athens, Greece 1997, s. 486÷495.
• 3. Gunopulos D., Kollios G., Tsotras V. J.: Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. ACM SIGMOD 2000, Dallas 2000, s. 137÷154.
• 4. Lee J., Deok-Hwan K., Chin-Wan Ch.: Multi-dimensional Selectivity Estimation Using Compressed Histogram Estimation Information. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, Philadelphia 1999, s. 205÷214.
• 5. Yan F., Hou W.-C., Jiang Z., Luo C., Zhu Q.: Selectivity estimation of range queries based on data density approximation via cosine series. Data & Knowledge Engineering 63(3), SienceDirect, 2007, s. 855÷878.
• 6. Augustyn D. R.: Asymptotically error-optimal shape of sampling zone for query selectivity estimation method based on discrete cosine trans form. Theoretical and Applied Informatics, Vol. 24 , No. 1, Versita, Warsaw 2012, s. 3÷22.
• 7. Chakrabarti K., Garofalakis M., Rastogi R., Shim K.: Approximate Query Processing Using Wavelets. VLDB Journal, Vol. 10, No. 2÷3, Springer-Verlag, New York 2001, s. 199÷223.
• 8. Getoor L., Taskar B., Koller D.: Selectivity estimation using probabilistic modes. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, New York 2001, s. 461÷472.
• 9. Augustyn D. R., Kostrzewa D.: Szacowanie selektywności zapytań oparte na transformacie Hougha i metodzie PCA. Studia Informatica, Vol. 33, No. 2A (105), Gliwice 2012, s. 211÷227.
• 10. Augustyn D. R.: Applying advanced methods of query selectivity estimation in Oracle DBMS. Advances in Soft Computing. Man-Machine Interactions. Springer-Verlag, Berlin-Heidelberg 2009, s. 585÷593.
• 11. Augustyn D. R., Warchał Ł.: Zastosowanie sieci Bayesa w szacowaniu selektywności zapytań w optymalizatorze zapytań serwera bazy danych Oracle. Studia Informatica, Vol. 32, No. 1A (94), Gliwice 2011, s. 25÷42.