[ 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 ] |