[ Pobierz całość w formacie PDF ]

relacj R, je li B(R) Mk. Ujmijmy to inaczej  przy sortowaniu relacji R w k przebiegach
minimaln liczb buforów jest M = (B(R))1/k.
Algorytm sortuj cy w ka dym przebiegu wczytuje wszystkie dane z dysku i ponownie je zapisuje.
Dlatego k-przebiegowy algorytm sortuj cy wymaga 2kB(R) dyskowych operacji wej cia-wyj cia.
Rozwa my teraz koszt wieloprzebiegowego z czenia R(X, Y) S(Y, Z) (jest to reprezen-
tatywna operacja dwuargumentowa na relacjach). Niech j(M, k) to najwi ksza liczba bloków,
taka e w k przebiegach z wykorzystaniem M buforów mo na z czy relacje maj ce w sumie
j(M, k) lub mniej bloków. Oznacza to, e z czenie jest mo liwe, je li B(R) + B(S) j(M, k).
W ostatnim przebiegu nale y scali M posortowanych podlist z obu relacji. Ka da z podlist
jest sortowana za pomoc k  1 przebiegów, dlatego nie mo e by d u sza ni s(M, k  1) = Mk  1,
co w sumie daje M s(M, k  1) = Mk. Tak wi c B(R) + B(S) Mk. Po odwróceniu ról parametrów
mo na ponadto stwierdzi , e do obliczenia z czenia w k przebiegach potrzeba (B(R) + B(S))1/k
buforów.
Przy okre laniu liczby dyskowych operacji wej cia-wyj cia potrzebnych w algorytmach
wieloprzebiegowych nale y pami ta , e  inaczej ni przy sortowaniu  dla z cze i innych
operacji na relacjach nie trzeba uwzgl dnia zapisu ko cowego wyniku na dysk. Dlatego sor-
towanie podlist wymaga 2(k  1)(B(R) + B(S)) operacji, a kolejnych B(R) + B(S) operacji
potrzeba na wczytanie posortowanych podlist w ostatnim przebiegu. W sumie oznacza to
(2k  1)(B(R) + B(S)) operacji.
672 15. WYKONYWANIE ZAPYTA
15.8.3. Wieloprzebiegowe algorytmy oparte na haszowaniu
W operacjach na du ych relacjach istnieje powi zana rekurencyjna technika haszowania. Rela-
cj (lub relacje) nale y podzieli przez haszowanie na M  1 kube ków, przy czym M to liczba
dost pnych buforów w pami ci. Operacje jednoargumentowe nale y wykona osobno na ka -
dym kube ku. Operacje dwuargumentowe, takie jak z czenie, trzeba przeprowadzi na ka dej
parze odpowiadaj cych sobie kube ków, tak jakby by y ca ymi relacjami. Technik t mo na
opisa rekurencyjnie.
PRZYPADEK PODSTAWOWY: Je li w operacji jednoargumentowej relacja mie ci si w M
buforach, nale y wczyta j do pami ci i wykona operacj . Je eli w operacji dwuargumentowej
jedna z relacji mie ci si w M  1 buforach, trzeba wykona operacj , wczytuj c relacj do pa-
mi ci g ównej, a nast pnie wczyta drug relacj blok po bloku do M-tego bufora.
INDUKCJA: Je eli adna relacja nie mie ci si w pami ci g ównej, nale y za pomoc haszo-
wania podzieli obie na M  1 kube ków, co opisano w punkcie 15.5.1. Nast pnie trzeba reku-
rencyjnie wykonywa operacj na ka dym kube ku (lub ka dej parze) i akumulowa dane wyj-
ciowe z wszystkich kube ków (lub par).
15.8.4. Wydajno wieloprzebiegowych algorytmów
opartych na haszowaniu
Dalej w tek cie obowi zuje za o enie, e przy haszowaniu relacji krotki dzielone s mo liwie
równomiernie mi dzy kube ki. W praktyce za o enie mo na cz ciowo spe ni , wybieraj c
w pe ni losow funkcj haszuj c , jednak rozk ad krotek w kube kach zawsze b dzie nieco nie-
równomierny.
Najpierw rozwa my operacj jednoargumentow , na przyk ad lub na relacji R z wyko-
rzystaniem M buforów. Niech u(M, k) b dzie liczb bloków najwi kszej relacji, jak mo e
obs u y k-przebiegowy algorytm haszowania. Liczb u mo na zdefiniowa rekurencyjnie
w nast puj cy sposób.
PRZYPADEK PODSTAWOWY: u(M, 1) = M, poniewa relacja R musi mie ci si w M
buforach (a wi c B(R) M).
INDUKCJA: Zak adamy, e pierwszy krok to podzia relacji R na M  1 kube ków o równej
wielko ci. Dlatego mo na obliczy u(M, k) w opisany tu sposób. Kube ki w nast pnym prze-
biegu musz by na tyle ma e, e mo na je obs u y w k  1 przebiegach. Kube ki maj wi c
rozmiar u(M, k  1). Poniewa R dzielona jest na M  1 kube ków, konieczne jest, aby u(M, k)
= (M  1)u(M, k  1).
Po rozwini ciu rekurencji okazuje si , e u(M, k) = M(M  1)k  1 lub  w przybli eniu dla
du ego M  u(M, k) = Mk. Mo na te wykona jedn z jednoargumentowych operacji na rela-
cji R w k przebiegach przy M buforach i za o eniu, e M (B(R))1/k.
Podobn analiz mo na przeprowadzi dla operacji dwuargumentowych. Rozwa my z -
czenie (tak jak w punkcie 15.8.2). Niech j(M, k) b dzie górnym ograniczeniem rozmiaru mniej- [ Pobierz całość w formacie PDF ]