[ Pobierz całość w formacie PDF ]

Krotki o tej samej warto ci porównywanych atrybutów musz mie ci si w M blokach.
15.4.8. Wydajniejsze z czenie przez sortowanie
Je li bardzo du a liczba krotek o identycznej warto ci z czanych atrybutów nie stanowi zagro-
enia, mo na zaoszcz dzi dwie dyskowe operacje wej cia-wyj cia na blok przez po czenie
drugiego etapu sortowania z samym z czeniem. Ten algorytm to z czenie przez sortowanie
(ang. sort join; inne nazwy to z czenie przez scalanie lub z czenie przez sortowanie ze scala-
niem). Aby obliczy R(X, Y) S(Y, Z) z wykorzystaniem M buforów w pami ci g ównej,
nale y wykona poni sze kroki.
(1) Utworzy posortowane podlisty o wielko ci M przy u yciu Y jako klucza sortowania
dla R i S.
(2) Przenie pierwszy blok ka dej podlisty do bufora. Zak adamy, e liczba podlist nie prze-
kracza M.
(3) Wielokrotnie znale najmniejsz warto y atrybutów Y w ród pierwszych dost pnych
krotek wszystkich podlist. Trzeba znale wszystkie krotki z obu relacji o warto ci y, na
przyk ad u ywaj c niektórych z M dost pnych buforów na ich zapisanie, je li istnieje
mniej ni M podlist. Nale y zwróci z czenie wszystkich krotek z R z wszystkimi krot-
kami z S maj cymi t sam warto atrybutów Y. Je li bufor jednej z podlist zostanie
opró niony, trzeba usun go z dysku.
Przyk ad 15.7. Ponownie wró my do problemu z przyk adu 15.4  z czenia relacji R i S
o rozmiarach 1000 oraz 500 bloków przy dost pnych 101 buforach. Nale y podzieli R na 10,
a S  na 5 podlist (ka da o d ugo ci 100) i je posortowa 3. 15 buforów mo na wykorzysta na
analizowane bloki ka dej z podlist. Je li zdarzy si sytuacja, w której wiele krotek ma t sam
warto atrybutów Y, mo na zapisa je w pozosta ych 86 buforach.
Na ka dy blok danych wykonywane s trzy dyskowe operacje wej cia-wyj cia. Dwie z nich
s u do tworzenia posortowanych podlist. Nast pnie ka dy blok ka dej takiej podlisty nale y
ponownie wczyta do pami ci g ównej w procesie wielo cie kowego scalania. Dlatego czna
liczba dyskowych operacji wej cia-wyj cia to 4500.
Ten algorytm z czenia przez sortowanie jest wydajniejszy od algorytmu z punktu 15.4.6,
cho nie zawsze mo na z niego skorzysta . W przyk adzie 15.7 stwierdzono, e liczba dysko-
wych operacji wej cia-wyj cia wynosi tu 3(B(R) + B(S)). Algorytm mo na zastosowa do da-
nych niemal tak du ych, jak w poprzednim algorytmie. Rozmiar posortowanych podlist to
M bloków, a na dwóch listach mo e by najwy ej M podlist. Dlatego wystarczaj cy jest wymóg:
B(R) + B(S) M2.
3
Technicznie mo na uporz dkowa podlisty, aby mia y d ugo po 101 bloków. Wtedy ostatnia podlista
z R ma 91 bloków, a ostatnia podlista z S  96 bloków. Jednak wtedy koszty s dok adnie takie same.
652 15. WYKONYWANIE ZAPYTA
15.4.9. Omówienie algorytmów opartych na sortowaniu
W tabeli 15.11 zamieszczono analizy algorytmów omówionych w podrozdziale 15.4. W punk-
tach 15.4.6 i 15.4.8 napisano, e w algorytmach z czenia obowi zuj ograniczenia dotycz ce
liczby krotek o tej samej warto ci porównywanych atrybutów. Przy naruszeniu ograniczenia
konieczne mo e by zastosowanie z czenia zagnie d onego.
Operatory Potrzebne M (w przybli eniu) Dyskowe operacje wej cia-wyj cia Punkt
, , 3B 15.4.1, 15.4.2, 15.4.3
B
, ,  3(B(R) + B(S)) 15.4.4, 15.4.5
B(R) B(S)
5(B(R) + B(S)) 15.4.6
max(B(R), B(S)
3(B(R) + B(S)) 15.4.8
B(R) B(S)
15.11. Wymogi zwi zane z pami ci g ówn i dyskowymi operacjami wej cia-wyj cia
dla algorytmów opartych na sortowaniu
15.4.10. wiczenia do podrozdzia u 15.4
wiczenie 15.4.1. Dla ka dej z podanych operacji napisz iterator, który wykorzystuje algorytm
opisany w podrozdziale: a) eliminowanie powtórze ( ), b) grupowanie ( L), c) cz wspólna
zbiorów, d) ró nica wielozbiorów, e) z czenie naturalne.
wiczenie 15.4.2. Je li B(R) = B(S) = 10 000 i M = 1000, jakie s wymogi dotycz ce dysko-
wych operacji wej cia-wyj cia dla: a) sumy zbiorów, b) prostego z czenia przez sortowanie, c)
wydajniejszego z czenia przez sortowanie opisanego w punkcie 15.4.8.
! wiczenie 15.4.3. Za ó my, e drugi przebieg algorytmu opisanego w podrozdziale nie wyma-
ga wszystkich M buforów, poniewa istnieje mniej ni M podlist. Jak mo na zmniejszy liczb
dyskowych operacji wej cia-wyj cia, wykorzystuj c dodatkowe bufory? [ Pobierz całość w formacie PDF ]
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • mons45.htw.pl
  • Wątki
    Powered by wordpress | Theme: simpletex | © (...) lepiej tracić niż nigdy nie spotkać.