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

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

Algorytmy przeszukiwania

Algorytmy przeszukiwania


Jeżeli chodzi o algorytmy przeszukiwania przestrzeni możliwych drzew połączeń, to stosuje się trzy podstawowe podejścia:

- algorytmy dokładne,

- algorytmy przybliżone,

- metaheurystyki - algorytmy kombinatoryczne.

Algorytmy dokładne, stosowane, w praktyce, analizują wszystkie możliwe drzewa połączeń (tzw. pełne przeszukiwanie) lub ograniczają się do przejrzenia tylko niektórych podzbiorów. Najpopularniejszym algorytmem, stosowanym przez większość systemów komercyjnych, jest algorytm programowania dynamicznego. Koncepcja programowania dynamicznego polega na wypełnieniu tabeli kosztów wykonania połączeń tak, aby przechowywać tylko minimum danych potrzebnych do analizy. Tabela ta jest konstruowana, kolejno, dla pojedynczych relacji, par relacji, trojek relacji, itd. Wadą tych algorytmów jest zależność czasu optymalizacji od liczby operacji połączenia.

Algorytmy przybliżone, do znalezienia „najlepszego” planu stosują bądź heurystyki lub ograniczają się do optymalizacji regułowej, o której już mówiliśmy. Zasadniczą wadą tych algorytmów jest to, że, najczęściej, plan znaleziony przez algorytm przybliżony znacząco odbiega od „najlepszego” możliwego planu wykonania zapytania.

Trzecie z możliwych podejść do znajdowania najlepszego drzewa połączeń polega na zastosowaniu algorytmów kombinatorycznych takich jak: Iterative Improvement, Simulated Annealing, Tabu Search, algorytmy genetyczne. Algorytmy te pozwalają na znaczną penetrację przestrzeni możliwych drzew połączeń, a jednocześnie, czas optymalizacji nie zależy od liczby operacji połączenia. Jak pokazują badania, algorytmy, mimo, że nie znajdują optymalnych drzew połączeń, znajdują jednak plany znacznie efektywniejsze niż w przypadku stosowania prostych heurystyk. Jednak ich zasadniczą zaletą, w stosunku do algorytmów dokładnych, jest to, że pozwalają one optymalizować nawet bardzo duże zapytania ( o liczbie połączeń dochodzących do 100 operacji).

Problem optymalizacji zapytań jest ciągle obszarem aktywnych badań naukowych. Wiąże się to, z jednej strony, z problemem coraz bardziej złożonych zapytań i nowych typów danych, z drugiej, z nowymi potrzebami wynikającymi z popularności Internetu.


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