Wyniki wyszukiwania - BazTech

1

Szacowanie selektywności zapytań oparte na transformacie Hougha i metodzie PCA

Augustyn D., Kostrzewa D.

Studia Informatica

|

2012

|

Vol. 33, nr 2A

211-227

PL

Oszacowanie selektywności zapytania jest istotnym elementem procesu uzyskiwania optymalnego planu wykonania tego zapytania. Wyznaczenie selektywności wymaga użycia nieparametrycznego estymatora rozkładu wartości atrybutu, na ogół histogramu. Wykorzystanie wielowymiarowego histogramu jako reprezentacji łącznego rozkładu wielowymiarowego jest nieekonomiczne z powodu zajętości pamięciowej takiej reprezentacji. W artykule zaproponowano nową metodę, nazwaną HPCA, oszczędną pod względem zajętości, gdzie rozkład dwuwymiarowy w przybliżeniu może być reprezentowany w postaci zbioru histogramów jednowymiarowych. Metoda HPCA opiera się na transformacji Hougha i metodzie analizy składowych głównych. Dzięki HPCA można uzyskiwać dokładniejsze oszacowania selektywności zapytań niż te, otrzymane przy wykorzystaniu standardowych 2-wymiarowych histogramów.

EN

Query selectivity estimation is an important element of obtaining optimal query execution plan. Selectivity estimation requires a nonparametric estimator of attribute values distribution – commonly a histogram. Using a multidimensional histogram as a representation of a joint multidimensional distribution of attributes values is not space-efficient. The paper introduces a new space-efficient method called HPCA, where a 2-dimesional distribution may be represented by a set of 1-dimensional histograms. HPCA is based on Hough transform and principal component analysis method. Using HPCA commonly gives more accurate selectivity estimation than standard methods based on a 2-dimensional histogram.

2

Zastosowanie sieci Bayesa w szacowaniu selektywności zapytań w optymalizatorze zapytań serwera bazy danych Oracle

Augustyn D., Warchał Ł.

Studia Informatica

|

2011

|

Vol. 32, nr 1A

25-42

PL

Artykuł opisuje zastosowanie sieci Bayesa do wyznaczania selektywności zapytań. Wartość selektywności zapytania pozwala na wstępne oszacowanie rozmiaru zbioru wynikowego zapytania, co z kolei pozwala na wybór optymalnego sposobu realizacji zapytania. Obliczenie selektywności dla zapytań z warunkiem selekcji opartym na kilku atrybutach tablicy wymaga użycia estymatora wielowymiarowej funkcji gęstości prawdopodobieństwa dla rozkładu wartości atrybutów. Sieć Bayesa może stanowić oszczędną, w sensie zajętości pamięci, reprezentację wielowymiarowego rozkładu wartości atrybutów. Artykuł omawia sposób rozszerzenia funkcjonalności optymalizatora zapytań, tzn. użycia modułów systemu Weka do implementacji metody wyznaczania selektywności (oparej na koncepcji sieci Bayesa) w ramach optymalizatora SZBD Oracle.

EN

The paper presents applying Bayesian network-based method of a selectivity estimation. The query selectivity allows estimate query result size, which allows to choose the optimal method of query execution. Obtaining the selectivity for a query with a selection condition based on many attributes, requires an estimator of a multidimensional probability density function of attribute values. Bayesian network can be used as a memory-efficient representation of the multidimensional distribution of attribute values. The article shows Bayesian network approach applied for extending the functionality of the query optimizer. Some Weka modules are used for implementing Bayesian network-based selectivity estimation in Oracle DBMS optimizer.

3

Metoda analizy głównych składowych w szacowaniu selektywności zapytań

Augustyn D.

Studia Informatica

|

2011

|

Vol. 32, nr 2A

21-36

PL

Selektywność zapytania jest parametrem pozwalającym określić spodziewany rozmiar wyniku zapytania. Oszacowanie selektywności wymagane jest do wyznaczania optymalnego sposobu realizacji zapytania. Zadaniem tym zajmuje się moduł optymalizatora SZBD. Obliczanie selektywności jest szczególnie utrudnione w zapytaniach z warunkami wieloatrybutowymi, gdzie potrzebny jest nieparametryczny estymator wielowymiarowego rozkładu wartości atrybutów. Zastosowanie wielowymiarowego histogramu w takiej roli może być zbyt kosztowne pod względem zajętości pamięci, szczególnie w przypadku wysokiej wymiarowości zagadnienia. W takiej sytuacji użyteczne może być podejście wykorzystujące metodę analizy składowych głównych, redukujące wymiarowość. Dodatkowo można zastosować metodę mnożenia selektywności, wyznaczonych niezależnie z jednowymiarowych rozkładów brzegowych, określonych w zredukowanej przestrzeni. Upraszcza to i przyspiesza przedstawioną w artykule metodę szacowania selektywności. W artykule opisano również sposób implementacji zaproponowanego rozwiązania w SZBD Oracle, z wykorzystaniem modułu rozszerzającego działanie optymalizatora zapytań – Oracle Data Cartridge Interface Statistics.

EN

Query selectivity allows to estimate the size of query results. It is required for obtaining the optimal method of query execution. This is a main goal of a query optimizer activities. Selectivity calculations for queries with a complex multi-attribute selection condition require a non-parametric estimator of multi-dimensional probability density function of distribution of table attribute values. Using a multi-dimensional histogram as a representation of multi-dimensional distribution is very space-consuming for high dimensions. The approach based on Principal Component Analysis allows to reduce dimensionality and makes the representation space efficient. Additionally the attribute value independence rule (with multiplicity of simple selectivities) may be used in a dimensions-reduced space so the method of the PCA-based selectivity estimation becomes simpler and more effective. The paper also presents the implementation of the proposed solution in DBMS Oracle as the extension of the query optimizer by using Oracle Data Cartridge Interface Statistics module.

4

Metoda estymacji jądrowej w szacowaniu selektywności zapytań

Augustyn D.

Studia Informatica

|

2002

|

Vol. 23, nr 4

191-207

PL

W artykule dokonany został przegląd wybranych metod estymacji nieparametrycznej, wykorzystanych do szacowania współczynnika selektywności zapytań. Artykuł koncentruje się głównie na metodzie estymacji jądrowej, użytej do przybliżania nieznanej funkcji gęstości, opisującej rozkład wartości atrybutu tablicy bazy danych. Estymowana funkcja gęstości pozwala na oszacowanie selektywności zapytań wykorzystywanej przez optymalizator zapytań. Pokazana jest koncepcja wykorzystania metody estymacji jądrowej dla wyznaczania selektywności łącznie dla zbioru atrybutów, bez zakładania niezależności tychże, na podstawie wielowymiarowego estymatora jądrowego.

EN

The article presents a survey of methods of nonparametric estimation used' for estimation of query selectivity. The article mainly focuses on kernel estimation used for approximation of unknown density function of distribution of values from database table attribute. An approximation of density function lets calculate a query selectivity, used by database query optimizer. The paper presents multidimensional kernel estimator used for calculation of common query selectivity for set of attribute without the assumption of attributes independence.