Zastosowanie predykcji rozkładu wartości atrybutu w celu poprawy dokładności estymacji selektywności zapytań

• Autorzy: Augustyn D.

Warianty tytułu

EN

Applying prediction of attribute value distribution for improvement of query selectivity estimation accuracy

• Języki publikacji: PL

Abstrakty

PL

Parametr selektywności jest wykorzystywany w procesie optymalizacji zapytań. Uzyskanie selektywności wymaga nieparametrycznego estymatora rozkładu wartości atrybutu, tj. histogramu. Histogramy są tworzone w ramach procesu aktualizacji statystyk. Dla dużych baz danych aktualizacja statystyk jest wykonywana raczej rzadko, np. tylko w momentach małego obciążenia systemu. To powoduje, że histogramy nie opisują aktualnego rozkładu danych. Aby uzyskać bardziej aktualne histogramy, powinno się zastosować mechanizm predykcji rozkładu. Pozwoli to na bardziej dokładną estymację selektywności. W niniejszym artykule zaproponowano metodę ekstrapolacji rozkładu wartości atrybutów. Metoda ta dokonuje predykcji momentów szukanego, ekstrapolowanego rozkładu. W celu jego wyznaczenia opisywana metoda wykorzystuje zasadę maksimum entropii z uwzględnieniem wartości momentów znalezionych w ramach procedury predykcji.

A selectivity parameter is needed in query optimization process. Obtaining the query selectivity requires a non-parametric estimator of attribute value distribution, i.e. a histogram. Histograms are produced during update statistics process. For large databases the update statistics process is performed rather seldom, e.g. only during time of low workload of a system. This results that histograms do not describe actual data distribution. To obtain a more accurate histogram, a prediction mechanism should be introduced. This results obtaining a more accurate estimation of selectivity. 24 D. R. Augustyn The method of extrapolation of attribute value distribution is proposed in this paper. This method predicts moments of the extrapolated distribution. It uses the maximum entropy principle for obtaining the extrapolated distribution subject to the predicted values of the distribution moments.

Słowa kluczowe

PL

estymacja selektywności zapytań; histogram; zasada maksimum entropii rozkładu; ewolucja funkcji gęstości prawdopodobieństwa; predykcja szeregów czasowych

EN

query selectivity estimation; histogram; maximum entropy principle; evolution of probability density function; time series prediction

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

Twórcy

autor

Augustyn D.

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

Bibliografia

• 1. Jaynes E. T.: Papers on Probability, Statistics, and Statistical Physics. Springer, 1989.
• 2. Buck B., Macaulay V. A.: Maximum entropy in action: a collection of expository essays. Clarendon Press, 1991.
• 3. Saad T.: The Maximum Entropy Method for Reconstructing Density Distributions, 2013, http://www.tsaad.net/docs/tsaad-maximum-entropy-method.pdf.
• 4. Find minimum of constrained nonlinear multivariable function – MATLAB, 2013, http://www.mathworks.com/help/optim/ug/fmincon.html;jsessionid=efda3f7c6d73ec5a 5ed6bd50605e?s_tid=doc_12b.
• 5. Akaike Final Prediction Error for estimated model – MATLAB, 2013, http://www.mathworks.com/help/ident/ref/fpe.html.
• 6. Design exact radial basis network – MATLAB, 2013, http://www.mathworks.com/ help/nnet/ref/newrbe.html.
• 7. System Identification Toolbox Documentation – MATLAB, 2013, http://www.mathworks.com/help/ident/index.html#linear-model-identification.
• 8. Niederliński A.: Systemy komputerowe automatyki przemysłowej. Zastosowania. Tom 2. WNT, Warszawa 1985.
• 9. 1-D data interpolation – MATLAB, 2013, http://www.mathworks.com/help/matlab/ ref/interp1.html.
• 10. Ljung L.: System Identification: Theory for the User. Prentice Hall 1998.
• 11. Haber R., Keviczky L.: Nonlinear System Identification – Input-Output Modeling Approach. Springer 1999.
• 12. 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.
• 13. Augustyn D. R.: 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.
• 14. Oracle 10g. Using extensible optimizer, 2010, http://download.oracle.com/docs/cd/ B14117 01/appdev.101/b10800/dciextopt.htm. Wpłynęło do Redakcji 16 stycznia 2013 r.