Estymacja selektywności zapytań z wykorzystaniem transformaty kosinusowej i falkowej

• Autorzy: Augustyn D.

Warianty tytułu

EN

The query selectivity estimation using cosine and wavelet transform

• Języki publikacji: PL

Abstrakty

PL

Przeglądowy artykuł opisuje metody estymacji selektywności pewnej klasy zapytań ze złożonymi warunkami selekcji. Proste metody, wykorzystywane komercyjnie, zakładają pewne uproszczenie - niezależność wartości atrybutów tablic. Inne, dokładniejsze, bazują na estymacji wielowymiarowego rozkładu wartości atrybutów. Prezentowane, zaawansowane metody wykorzystują transformaty kosinusową i falkową dla efektywnego wyznaczania selektywności opierając się na stratnie skompresowanym widmie częstości wartości atrybutów.

EN

The paper is a literature survey of query selectivity methods for some kind of queries with composed selection conditions. Some simple commercially used methods base on the simplified assumption of table attribute value independence. The other methods presented in this paper are more accurate. They are based on the estimation of the multi-dimensional distribution of attribute values. Described methods use the discrete cosine transform and the discrete wavelet one for the effective query estimation based on the loss compressed spectrum of the attribute value frequency vector.

Słowa kluczowe

PL

transformata falkowa; transformata kosinusowa; estymacja selektywności; relacyjna baza danych

EN

wavelet transform; cosine transform; selectivity estimation; relational database

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2008
• Tom: Vol. 29, nr 2A
• Strony: 55--65
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Augustyn D.

• Politechnika Śląska, Wydział Automatyki, Elektroniki i Informatyki, Instytut Informatyki Gliwice, ul.Akademicka 16, pokój 313,

Bibliografia

• 1. Possała V., loannidis Y. E.: Selecthnty Estimation without the Attribute Value Independ-ence Assumption. Proc. of the 23rd Int. Conf. on Very Large Databases, The VLDB Journal, Athens 1997.
• 2. Lee. 1, Deok-Hwan K., Chin-Wan CL: Multi-dimensional Selectrvity Estimation Using Compressed Histogram Estimation Information. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, Philadelphia 1999.
• 3. Matias Y., Vitter J. S., Wang M.: Wavelet-Based Histograms for Selectivity Estimation. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, Washington 1998.
• 4. Garofalakis M.: Wavelet-Based Approximation Techniąues in Database Systems. Exploratory DSP. Signal Processing Magazine, IEEE vol. 23 no. 6, 2006.
• 5. Gunopułos D., Kolłios G., Tsotras V. J.: Approximating Multi-Dimensional Aggregate Rangę Oueries Over Real Attributes. ACM SIGMOD 2000, Dallas 2000.
• 6. Gunopułos D., Kolios G., Tsotras V. I, Domeniconi C: Selectivity estimators for multidimensional rangę ąueries over real attributes. The international Journal on Very Large Data Bases. The VLDB Journal, vol. 14 no. 2, Springer Berlin / Heidelberg 2005.
• 7. Bruno N., Chanchuri S., Gravano L.: STHoles: A Multidimesional Workload-Aware Histogram. Proc. of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara 2001.
• 8. Augustyn D. R.: Szacowanie selektywności zapytań z wykorzystaniem metod estymacji jednowymiarowych rozkładów prawdopodobieństwa. Studia Informatica, vol. 29 no. 2 (76), Gliwice 2008