[ Pobierz całość w formacie PDF ]
wych ka d krotk o pozytywnej warto ci licznika (warto ta wyznacza liczb kopii).
Aby obliczy R W S, tak e trzeba wczyta krotki z S do pami ci g ównej i ustali liczb
wyst pie ró nych krotek. Krotk t z licznikiem o warto ci c mo na traktowa jak c powodów,
640 15. WYKONYWANIE ZAPYTA
aby nie kopiowa t do danych wyj ciowych przy wczytywaniu krotek z R. Przy wczytywaniu
krotki t z R nale y sprawdzi , czy t wyst puje w S. Je li nie, t kopiowana jest do danych wyj-
ciowych. Je eli t pojawia si w S, trzeba sprawdzi warto c powi zan z t. Je li c = 0, nale y
skopiowa t do danych wyj ciowych. Przy c > 0 t nie jest kopiowana, natomiast trzeba zmniejszy
warto c o 1.
Iloczyn
Nale y wczyta S do M 1 buforów pami ci g ównej. Nie jest potrzebna adna specjalna struk-
tura danych. Nast pnie wczytywany jest ka dy blok z R. Ka d krotk t z R nale y z czy
t z ka d krotk S z pami ci g ównej. Z czone krotki trzeba doda do danych wyj ciowych.
Algorytm ten wymaga du ej ilo ci czasu procesora na krotk z R, poniewa ka d z nich
trzeba dopasowa do M 1 bloków pe nych krotek. Jednak dane wyj ciowe tak e s du e,
a czas w przeliczeniu na krotk z tych danych jest krótki.
Z czenie naturalne
W tym i innych algorytmach z czenia przyj to, e relacja R(X, Y) jest z czana z S(Y, Z),
gdzie Y reprezentuje wszystkie atrybuty wspólne dla R i S, X to wszystkie atrybuty z R, które
nie wyst puj w S, a Z to atrybuty z S nieobecne w R. Nadal zak adamy, e S to mniejsza relacja.
Aby obliczy z czenie naturalne, nale y wykona nast puj ce operacje.
(1) Wczyta wszystkie krotki z S i umie ci je w pami ci g ównej we wspomagaj cej wyszu-
kiwanie strukturze (z atrybutami Y jako kluczem wyszukiwania). Mo na wykorzysta na
to M 1 bloków pami ci.
(2) Wczyta ka dy blok z R do jednego pozosta ego bufora pami ci g ównej. U ywaj c struk-
tury u atwiaj cej wyszukiwanie, nale y dla ka dej krotki t z R znale krotki z S o zgod-
nych atrybutach Y. Dla ka dej pasuj cej krotki z S trzeba utworzy krotk przez z czenie
jej z t. Wynikowa krotka jest umieszczana w danych wyj ciowych.
Podobnie jak wszystkie jednoprzebiegowe algorytmy dwuargumentowe, ten wymaga B(R)
+ B(S) dyskowych operacji wej cia-wyj cia do wczytania operandów. Dzia a dla B(S) M 1
(w przybli eniu dla B(S) M).
Nie omawiamy tu z cze innych ni naturalne. Warto pami ta , e z czenie równo ciowe
jest obliczane w zasadzie tak samo, jednak trzeba uwzgl dni fakt, i równe atrybuty z obu re-
lacji mog mie ró ne nazwy. Z czenie warunkowe, które nie jest z czeniem równo ciowym,
mo na zast pi z czeniem równo ciowym lub iloczynem, po którym nast puje selekcja.
15.2.4. wiczenia do podrozdzia u 15.2
wiczenie 15.2.1. Dla ka dej z podanych operacji napisz iterator z wykorzystaniem algorytmu
opisanego w tej sekcji: a) projekcja, b) usuwanie powtórze ( ), c) grupowanie ( L), d) suma
zbiorów, e) cz wspólna zbiorów, f) ró nica zbiorów, g) cz wspólna wielozbiorów, h) ró -
nica wielozbiorów, i) iloczyn, j) z czenie naturalne.
wiczenie 15.2.2. Dla ka dego z operatorów z wiczenia 15.2.1 okre l, czy operator jest blokuj cy
(czyli czy pierwsze dane wyj ciowe mo na utworzy dopiero po wczytaniu wszystkich danych
wej ciowych). Ujmijmy to inaczej operator blokuj cy to taki, dla którego jedyne mo liwe
iteratory wykonuj wszystkie wa ne zadania w funkcji Open.
15.3. Z CZENIA ZAGNIE D ONE 641
wiczenie 15.2.3. W tabeli 15.9 pokazano wymogi dotycz ce pami ci i dyskowych operacji
wej cia-wyj cia dla algorytmów opisanych w tym i nast pnym podrozdziale. Za o ono jednak,
e wszystkie argumenty s sklastrowane. Jak zmieni si warto ci, je li jeden lub oba argumenty
nie s sklastrowane?
! wiczenie 15.2.4. Przedstaw algorytmy jednoprzebiegowe dla ka dego z poni szych operato-
rów z rodziny z cze :
a) R S przy za o eniu, e R mie ci si w pami ci (definicj z czenia cz ciowego przed-
stawiono w wiczeniu 2.4.8).
b) R S przy za o eniu, e S mie ci si w pami ci.
c) R S przy za o eniu, e R mie ci si w pami ci (definicj nierównoz czenia cz cio-
wego przedstawiono w wiczeniu 2.4.9).
d) R S przy za o eniu, e S mie ci si w pami ci.
e) R S przy za o eniu, e R mie ci si w pami ci (definicje z cze zewn trznych zawiera
L
punkt 5.2.7).
f) R S przy za o eniu, e S mie ci si w pami ci.
L
[ Pobierz całość w formacie PDF ]
© 2009 Silni rządzą, słabych rzuca się na pożarcie, ci pośredni gdzieś tam przemykają niezauważeni jak pierd-cichacz. - Ceske - Sjezdovky .cz. Design downloaded from free website templates