Nov∞jÜφ verze relaΦnφch databßzov²ch server∙ se ve v²Φtu sv²ch novinek Φasto zmi≥ujφ o haÜovan²ch spojenφch, kterß mohou v²razn∞ zlepÜit provedenφ tΘto Φasov∞ nejnßroΦn∞jÜφ relaΦnφ operace. Nejprve ale krßtce o tom, jakΘ jinΘ algoritmy jsou pro spojenφ v relaΦnφm serveru k dispozici. Nenφ jich mnoho. Z klasick²ch algoritm∙ jsou Φasto uvßd∞ny dva:

• metoda vno°en²ch cykl∙,
• metoda set°φd∞nφ-slΘvßnφ.

Tyto algoritmy jsou zcela nezajφmavΘ. Budeme p°edpoklßdat, ₧e relace, kterΘ spojujeme jsou R a S, prostor v poΦtu strßnek pot°ebn² pro tyto relace je p_R, resp. p_S. Dßle budeme p°edpoklßdat, ₧e R je menÜφ ne₧ S, tj. p_R £ p_S a ₧e ve vnit°nφ pam∞ti mßme k dispozici prostor velikosti M strßnek.

V prvnφm z algoritm∙ se spojenφ °ßdk∙ tabulek provßdφ sekvenΦnφm prolΘzßnφm obou relacφ ve dvou cyklech tak, ₧e se porovnßvß ka₧d² °ßdek s ka₧d²m. To lze d∞lat pouze v p°φpadech, ₧e relace ve vn∞jÜφm cyklu (zde R) je dostateΦn∞ malß. PoΦet Φtenφ strßnek je v danΘm p°φpad∞

p_R + p_S* p_R

Ve druhΘ metod∞, je nutnΘ relace R a S nejprve set°φdit. Pak se Φtou sekvenΦn∞, postupn∞ se provßdφ porovnßnφ n-tic a v positivnφm p°φpad∞ se vytvß°φ n-tice v²sledku. Neuva₧uje-li se Φas pot°ebn² ke t°φd∞nφ, p°eΦte se celkem

p_R + p_S

strßnek. Oba algoritmy lze modifikovat se zlepÜenφm ΦasovΘ slo₧itosti, existujφ-li pro atribut A indexy.

Implementace relaΦnφch S╪BD ukßzaly, ₧e jestli₧e nejsou dostupnΘ indexy k spojovacφm atribut∙m relacφ a jestli₧e v²sledek spojenφ nemusφ b²t set°φd∞n podle hodnot spojovacφch atribut∙, je nejlepÜφ pou₧φt pro spojenφ haÜovßnφ.

Vysv∞tlφme princip tΘto metody na nejjednoduÜÜφ variant∞ - klasickΘm haÜovßnφ. Dßle ukß₧eme variantu tzv. GRACE algoritmu, pou₧itΘho p∙vodn∞ v hardwarov∞ orientovanΘ verzi spojenφ v japonskΘm projektu 5. generace poΦφtaΦ∙. Jde o p°φpad, kdy ₧ßdnou z relacφ nelze haÜovat celou do vnit°nφ pam∞ti. Budeme p°edpoklßdat, ₧e relace, kterΘ spojujeme jsou R a S, prostor pot°ebn² pro tyto relace je p_R, resp. p_S. Dßle budeme p°edpoklßdat, ₧e R je menÜφ ne₧ S, tj. p_R £ p_S a ₧e ve vnit°nφ pam∞ti mßme k dispozici prostor velikosti M strßnek.

NejjednoduÜÜφ variantou spojenφ pomocφ haÜovßnφ je metoda naz²vanß spojenφ klasick²m haÜovßnφm. Ve vnit°nφ pam∞ti se alokuje prostor, do kterΘho lze haÜovat celou relaci R (viz heslo HaÜovßnφ DatabßzovΘ abecedy). Proto₧e k haÜovßnφ je nutnΘ pou₧φt v∞tÜφ prostor ne₧ p_R, budeme dßle uva₧ovat koeficient F, kter² v souΦinu s p_R vede ke skuteΦnΘ velikosti pot°ebnΘho prostoru. Obvykle F= 1,25, tj. relace R zabφrß 80% vyhrazenΘho prostoru. Tedy é p_R *Fù < M, kde é xù p°i°azuje x nejbli₧Üφ celΘ Φφslo v∞tÜφ nebo rovnΘ x.

Algoritmus klasickΘho haÜovßnφ spoΦφvß v tom, ₧e po zahaÜovßnφ relace R do vnit°nφ pam∞ti se sekvenΦn∞ Φte relace S, haÜuje se hodnota s.A pro ka₧d² prvek s z S, a k nφ se nachßzφ p°φm²m p°φstupem odpovφdajφcφ n-tice r z R ulo₧enΘ ve vnit°nφ pam∞ti. Je-li spln∞na podmφnka spojenφ, nap°. s.A = r.A, generuje se odpovφdajφcφ n-tice v²sledku.

Je z°ejmΘ, ₧e tento algoritmus vy₧aduje (bez uklßdßnφ v²sledku)

p_R + p_S

operacφ Φtenφ strßnek. Je tedy lepÜφ ne₧ metoda set°φd∞nφ-slΘvßnφ, proto₧e nevy₧aduje Φas pot°ebn² ke t°φd∞nφ. Pro realizaci algoritmu staΦφ é p_R *Fù + 1 strßnek na Φtenφ, 1 strßnka pro vytvß°enφ v²sledku.

V obecnΘm p°φpad∞, kdy se relace R (a tedy ani S) nevejde do vnit°nφ pam∞ti, rozd∞lujφ se relace R a S na vhodnΘ disjunktnφ podmno₧iny (kapsy) a spojujφ se pouze korespondujφcφ podmno₧iny. Toto rozd∞lenφ nemusφ b²t jednoduchΘ, proto₧e je navφc nutnΘ, aby danΘ podmno₧iny m∞ly rozumnou specifikovanou velikost v zßvislosti na dostupnΘ vnit°nφ pam∞ti.

Algoritmy s rozd∞lovßnφm relacφ majφ dv∞ fßze. V prvnφ se provßdφ rozd∞lenφ R a S. V druhΘ fßzi se Φßst R (resp. Φßsti R) haÜuje do vnit°nφ pam∞ti, Φtou se n-tice s z odpovφdajφcφ Φßsti S, haÜovßnφm hodnoty s.A se najdou eventußlnφ odpovφdajφcφ n-tice r a generujφ se spojenΘ n-tice do v²sledku.

Ob∞ relace jsou haÜovßny na atributu A pomocφ haÜovacφ funkce h. Pro jednotlivΘ hodnoty z A jsou pro relaci R, resp. S vytvß°eny kapsy ukazatel∙ na n-tice z R, resp. S. Ka₧dß kapsa HR_i odpovφdß t∞m n-ticφm z R, jejich₧ hodnota atributu A se haÜuje na hodnotu i (kolize se soust°e∩ujφ do jednΘ kapsy). Tedy h zobrazuje atribut A do mno₧iny {0,1,...,m-1}, tj. i je z tΘto mno₧iny. Podobn∞ uva₧ujeme i pro relaci S, kde kapsy oznaΦujeme HS _i.

Kapsy lze je realizovat jako datovΘ struktury ve vnit°nφ pam∞ti. SekvenΦnφm Φtenφm obou relacφ se kapsy naplnφ ukazateli na n-tice, tj. p°esn∞ji °eΦeno ukazatelem na strßnku, kde se n-tice nalΘzß (+ event. relativnφ Φφslo n-tice). Je z°ejmΘ, ₧e pro potencionßlnφ spojenφ p°ichßzejφ v ·vahu pouze n-tice z odpovφdajφcφch si kapes, tj. z HR_i a HS_i. Dφky tomu, ₧e haÜovacφ funkce nenφ prostß, mohou ale existovat v dan²ch kapsßch n-tice r, resp. s tak, ₧e r.A ¹ s.A.

Situaci lze ukßzat na obr. 1. Vytvß°enφ kapes vlastn∞ odpovφdß rozd∞lenφ relace R, resp. S na m podrelacφ. Pak se p°evede problΘm spojenφ na realizaci spojenφ pro dvojice odpovφdajφcφch si podrelacφ. Pro odpovφdajφcφ kapsy odpovφdajφ ₧lutΘ Φtverce t∞m dvojicφm, kterΘ jdou potencionßln∞ spojit.

Obr. 1 Adepti na spojenφ v korespondujφcφch si kapsßch

HaÜovanΘ spojenφ s rozd∞lovßnφm relacφ je vhodnΘ vytvß°et tehdy, kdy₧ se n-tice odpovφdajφcφ jednΘ kapse vejdou do vnit°nφ pam∞ti. Pak je slo₧itost spojenφ, kterΘ se v algoritmu realizuje nap°. pomocφ hnφzd∞n²ch cykl∙, lineßrnφ v poΦtu °ßdk∙ obou relacφ. PoΦet strßnek Φten² ve fßzi rozd∞lovßnφ relacφ je p_R + p_S, v dalÜφ fßzi Φinφ n_R + n_S, tj. musφme p°eΦφst strßnku pro ka₧dou uva₧ovanou n-tici. Celkov² poΦet Φtenφ je tedy

p_R + p_S + n_R + n_S

co₧ se zatφm nezdß p°φliÜ v²hodnΘ.

Pro vlastnφ spojenφ lze op∞t vyu₧φt haÜovßnφ. Podrelaci R_i se p°i naΦφtßnφ do vnit°nφ pam∞ti haÜuje p°es atribut A do odpovφdajφcφho adresovΘho prostoru. Pak p°i Φtenφ S_i pro 1 strßnce haÜujeme s.A, vstupujeme k n-ticφm R a provßdφme Φi neprovßdφme spojenφ. Velikost M souvisφ s m. Z°ejm∞ musφ platit

(p_R/m) * F + 1 < M

┌sp∞ch metody patrn∞ zßvisφ i na tom, zdali se poda°φ vytvo°it vÜechny kapsy (zhruba) stejn∞ velkΘ.

Tato verze bude realistiΦt∞jÜφ. Nevyu₧φvajφ se kapsy, ale relace se dokomponujφ na Φßsti a ty se uklßdajφ na disk. Pro ob∞ fßze se pou₧ije Ö (p_R*F) strßnek vnit°nφ pam∞ti. Zbytek (do M strßnek) je mo₧nΘ vyu₧φt pro uklßdßnφ Φßstφ rozd∞len²ch relacφ. Pro i-tou Φßst disponujeme v prostoru M strßnek jednou strßnkou (buffer_i). Algoritmus probφhß v nßsledujφcφch krocφch:

(1) Zvol haÜovacφ funkci h tak, ₧e relaci R lze rozd∞lit do m = Ö (p_R *F) Φßstφ p°ibli₧n∞ stejnΘ dΘlky.

(2) ╚ti relaci R a haÜuj ji do (v²stupnφch) vyrovnßvacφch pam∞tφ. Kdykoli se bufferi, 0£ i£ m-1, naplnφ, zapiÜ ho na disk. Po p°eΦtenφ celΘ relace R zapiÜ vÜechny bufferi na disk.

(3) ╚ti relaci S a zpracuj ji stejn∞ jako relaci R.

Pro 0 £ i £ m-1 prove∩ kroky (4) a (5).

(4) ╚ti Ri a haÜuj ji do pam∞ti velikosti Ö (p_R *F). Zd∙vodn∞nφ: proto₧e vÜechny Ri jsou p°ibli₧n∞ stejn∞ velkΘ, jejich velikost je srovnatelnß s p_R /m = p_R / Ö (p_R *F) = Ö (p_R /F) strßnkami. Vy₧adujφ tedy prostor F* Ö (p_R /F) = Ö (p_R *F) strßnek.

(5) ╚ti n-tice z Si a haÜuj je na hodnot∞ atributu A. Existujφ-li odpovφdajφcφ n-tice relace Ri, generuj v²sledek.

V²hodnΘ je, ₧e Φßsti relace S mohou b²t libovolnΘ velikosti. Pot°ebujeme pro n∞ pouze 1 strßnku pam∞ti. PoΦet I/O operacφ (neuva₧ujeme-li zßpis v²sledku) Φinφ

3(p_R + p_R)

Uvß₧φme-li, ₧e existujφ servery, jejich₧ kapacita vnit°nφ pam∞ti je n∞kolik Gbyte, pak i alternativa spojenφ s klasick²m haÜovßnφm je zcela postaΦujφcφ, nebo¥ je velmi pravd∞podobnΘ, ₧e celß relace R (ne-li dokonce ob∞) se vejde do vnit°nφ pam∞ti.