[ Pobierz całość w formacie PDF ]
Poniewa zak adamy, e M jest znacznie wi ksze ni 1, zwykle stosowane jest uproszczone
przybli enie tej regu y:
B( (R)) M
Zauwa my, e zwykle nie mo na okre li rozmiaru (R), nie obliczaj c samego (R). Je li
rzeczywisty rozmiar b dzie wi kszy od oszacowanego (B( (R)) jest wi ksze od M), trzeba po-
nie istotne koszty zwi zane z prze adowywaniem, poniewa bloki przechowuj ce ró ne krot-
ki z R trzeba cz sto przenosi do pami ci i z niej usuwa .
Grupowanie
Operacja grupowania, L, zwraca zero lub wi cej atrybutów grupuj cych i zwykle jeden lub
wi cej atrybutów zagregowanych. Po utworzeniu w pami ci g ównej jednego wpisu dla ka dej
grupy dla ka dej warto ci atrybutów grupuj cych mo na przejrze krotki z R po jednym
bloku na raz. Wpis dla grupy sk ada si z warto ci atrybutów grupuj cych i zakumulowanej
warto ci ka dej agregacji.
Dla agregacji MIN(a) lub MAX(a) nale y zapisa minimaln lub maksymaln warto atry-
butu a dla wszystkich sprawdzonych ju krotek z grupy. Je li to konieczne, nale y zmie-
ni minimum lub maksimum przy pobraniu ka dej krotki z grupy.
Dla agregacji COUNT nale y doda 1 dla ka dej pobranej krotki z danej grupy.
Dla agregacji SUM(a) nale y doda warto atrybutu a do zakumulowanej sumy dla danej
grupy (pod warunkiem, e a jest ró ne od NULL).
AVG(a) to trudny przypadek. Trzeba przechowywa dwie zakumulowane warto ci liczb
krotek w grupie i sum warto ci atrybutu a w tych krotkach. Obie warto ci nale y oblicza
tak, jak dla agregacji COUNT i SUM. Po sprawdzeniu wszystkich krotek z R trzeba podzieli
sum przez liczb krotek, aby uzyska redni .
Po wczytaniu wszystkich krotek z R do bufora wej ciowego i u yciu ich do obliczenia agre-
gacji dla odpowiednich grup mo na utworzy dane wyj ciowe, zapisuj c krotk dla ka dej grupy.
Warto zauwa y , e do czasu sprawdzenia ostatniej krotki nie mo na rozpocz tworzenia da-
nych wyj ciowych dla operacji . Dlatego algorytm ten nie pasuje do modelu dzia ania iteratorów.
W metodzie Open trzeba zako czy grupowanie, zanim za pomoc metody GetNext b dzie mo na
pobra pierwsz krotk .
Aby przetwarzanie ka dej krotki w pami ci by o wydajne, trzeba w pami ci g ównej u y
struktury danych umo liwiaj cej znalezienie wpisu dla ka dej grupy na podstawie warto ci
atrybutów grupuj cych. Jak opisano to w kontek cie operacji , dobrze nadaj si do tego ty-
powe struktury danych stosowane w pami ci g ównej, takie jak tablice z haszowaniem i drzewa
zbalansowane. Nale y jednak pami ta , e kluczem wyszukiwania dla tych struktur s tylko
atrybuty grupuj ce.
638 15. WYKONYWANIE ZAPYTA
Operacje na niesklastrowanych danych
Wszystkie obliczenia dotycz ce liczby dyskowych operacji wej cia-wyj cia wymaganych
dla omawianych operacji s oparte na za o eniu, e relacje podane jako operandy s skla-
strowane. W zwykle rzadkich sytuacjach, kiedy operand R nie jest sklastrowany,
wczytanie wszystkich krotek z R mo e wymaga T(R), a nie B(R) dyskowych operacji
wej cia-wyj cia. Zauwa my jednak, e mo na przyj , i ka da relacja zwracana przez
operator jest sklastrowana nie ma powodu, aby zapisywa tymczasow relacj w nie-
sklastrowany sposób.
Liczba dyskowych operacji wej cia-wyj cia potrzebnych dla tego jednoprzebiegowego algo-
rytmu wynosi B (jest tak w ka dym jednoprzebiegowym algorytmie dla operatora jednoargu-
mentowego). Liczba niezb dnych buforów pami ci M nie jest powi zana z B w aden prosty
sposób, cho zwykle M ma warto mniejsz ni B. Problem polega na tym, e wpisy dla grup
mog by d u sze lub krótsze ni krotki z R, a liczba grup mo e by równa liczbie krotek z R
lub mniejsza. Jednak zwykle wpisy dla grup nie s d u sze od krotek z R, a grup jest du o
mniej ni krotek.
15.2.3. Algorytmy jednoprzebiegowe
dla operacji dwuargumentowych
Dalej opisano operacje dwuargumentowe sum , cz wspóln , ró nic , iloczyn i z czenie.
Poniewa w niektórych przypadkach trzeba odró ni wersje operatorów oparte na zbiorach
i wielozbiorach, wyst puj przy nich indeksy dolne Z (dla zbiorów) i W (dla wielozbiorów).
Przyk adowo W oznacza sum wielozbiorów, a Z ró nic zbiorów. Aby upro ci omawia-
nie z cze , uwzgl dniono tylko z czenia naturalne. Z czenie równo ciowe mo na zaimple-
mentowa w ten sam sposób (po odpowiednim przemianowaniu atrybutów), a z czenia
[ Pobierz całość w formacie PDF ]