BD-2st-1.2-w13.tresc-1.1-Slajd33

Z Studia Informatyczne
Wersja z dnia 12:41, 29 sie 2006 autorstwa PKrzyzagorski (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Problem znajdowania optymalnego drzewa połączeń (2)

Problem znajdowania optymalnego drzewa połączeń (2)


Zauważmy, że, de facto, problem znajdowania optymalnego drzewa połączeń można traktować jako problem optymalizacyjny - problem poszukiwania optymalnego stanu w przestrzeni stanów zawierającej wszystkie możliwe drzewa połączeń dla danego zapytania. Stan optymalny jest to stan o najmniejszej wartości funkcji kosztu.

Z tego punktu widzenia, można rozpatrywać działanie optymalizatora zapytań w trzech aspektach:

- Modelu planu wykonywania zapytania (struktura drzewa połączeń),

- Algorytmu przeszukiwania przestrzeni stanów,

- Funkcji kosztów.

Jak już wspominaliśmy, większość komercyjnych systemów zarządzania bazami danych ogranicza się do analizy drzew lewostronnie zagnieżdżonych. Mimo przyjęcia określonego kształtu drzewa połączeń, nadal liczba możliwych drzew, które należy przeanalizować, i których koszt należy oszacować, może być bardzo duża. Pozostaje zatem problem wyboru strategii przeszukiwania przestrzeni możliwych drzew połączeń. Funkcja kosztu, stosowana przez optymalizatory, opiera się na oszacowaniach rozmiarów wyników operatorów, które przedstawiliśmy ma poprzednich slajdach.


<< Poprzedni slajd | Spis treści | Następny slajd >>