ZSBD-2st-1.2-w6.tresc-1.1-Slajd15

Z Studia Informatyczne
Wersja z dnia 16:27, 11 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

Hierarchia ścieżek binarnych

Hierarchia ścieżek binarnych


Alternatywą dla relacji ASR są hierarchie kombinacji ścieżek binarnych. W rozwiązaniu tym, w binarnej relacji ścieżek jest materializowany tylko pierwszy i ostatni element ścieżki. Ponieważ może być wiele ścieżek prowadzących od tego samego źródła do tego samego celu ścieżki, dodatkowo jest pamiętana liczba tych ścieżek.

Na slajdzie pokazano przykład relacji binarnej dla bazy danych z poprzedniego slajdu. Relacja ta będzie zawierała dwie krotki reprezentujące ścieżki prowadzące od studenta Józefa Nowaka do imion jego wykładowców. Obydwie ścieżki są jednokrotne.

Zwróćmy uwagę, że pokazana relacja binarna pozwoli na przyspieszenie nawigacji jedynie wzdłuż kompletnych ścieżek. Przechowywane w niej dane będą nieprzydatne dla przyśpieszenia nawigacji w zapytaniach zawierających jedynie fragment maksymalnej ścieżki. Dlatego kompletne rozwiązanie obejmuje całą hierarchię relacji binarnych dla fragmentów ścieżek. W ogólności, hierarchia ta nie musi być kompletna. Wystarczy, że będzie ona zawierać tylko i wyłącznie relacje binarne, które będą przydatne w konkretnym zastosowaniu, dla określonego podzbioru wszystkich potencjalnych ścieżek zapytań.

Przykład na slajdzie pokazuje kompletną hierarchię relacji binarnych dla maksymalnej ścieżki składającej się z pięciu elementów: A0.A1.A2.A3.A4. Najniższy poziom hierarchii zawiera relacje binarne dla wszystkich ścieżek długości dwóch elementów, które są fragmentem ścieżki maksymalnej. Następny poziom zwiera relacje binarne dla wszystkich ścieżek o długości trzech elementów. Najwyższy poziom zawiera relację binarną dla maksymalnej ścieżki.

Tak jak dla relacji ASR również, w wypadku hierarchii relacji binarnych na każdej relacji zakłada się dwukierunkowe szybkie struktury dostępu.


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