COMPUTERWORLD
pod kapotou
StromovΘ protokoly

Sφla dvoufßzovΘho uzamykacφho protokolu spoΦφvala v tom, ₧e protokol zajiÜ¥oval uspo°ßdatelnost pro ka₧d² legßlnφ rozvrh. Vφme ji₧ takΘ, ₧e v modelu ploch²ch transakcφ s jednoduch²mi objekty jde o podmφnku nutnou, tj. uspo°ßdatelnost implikuje dvoufßzovost. V jin²ch modelech transakcφ lze pou₧φt i jinΘ protokoly, obecn∞ nedvoufßzovΘ protokoly, vedoucφ takΘ ke korektnφm rozvrh∙m. Ukß₧eme zde specißlnφ p°φpad tzv. stromovΘho protokolu vhodnΘho nap°. pro hierarchickΘ databßze, ale i pro jinΘ stromovΘ struktury dat, jako jsou nap°. B-stromy.

Budeme p°edpoklßdat pouze v²luΦnΘ zßmky W_LOCK, tj. po provedenφ W_LOCK(X) m∙₧e b²t objekt X jak Φten, tak zapisovßn. V stromovΘm protokolu m∙₧e ka₧dß transakce T pou₧φvat zßmky s nßsledujφcφmi pravidly:

  1. Prvnφ W_LOCK(X) transakce T lze pou₧φt na jakΘmkoli objektu X.
  2. DalÜφ objekt m∙₧e b²t uzamΦen transakcφ T pouze kdy₧ p°edch∙dce byl v T uzamΦen.
  3. Objekty mohou b²t odemknuty kdykoliv.
  4. Prvek, kter² byl transakcφ T zamknut a odemknut nem∙₧e b²t nßsledn∞ znovu zamknut v T.

Lze ukßzat, ₧e vÜechny rozvrhy, kterΘ jsou legßlnφ pod stromov²m uzamykacφm protokolem jsou uspo°ßdatelnΘ a na rozdφl od dvoufßzov²ch protokol∙ zde nedochßzφ k uvßznutφ.

Uva₧ujme strom na obrßzku 1 a transakce

T1: W_LOCK(B); W_LOCK(E); UNLOCK(E); W_LOCK(D); UNLOCK(B); W_LOCK(G); UNLOCK(D); UNLOCK(G).

T2: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H).

T3: W_LOCK(B); W_LOCK(E); UNLOCK(E); UNLOCK(B).

T4: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H).

 

 

 

Obr. 1 Hierarchickß databßze

Jeden z mo₧n²ch uspo°ßdateln²ch rozvrh∙ transakcφ T1,...,T4 je v tabulce 1.

T1

T2

T3

T4

W_LOCK(B)

     

W_LOCK(D)

   

W_LOCK(H)

   

UNLOCK(D)

   

W_LOCK(E)

     

UNLOCK(E)

     

W_LOCK(D)

     

UNLOCK(B)

     

 

W_LOCK(B)

 

 

W_LOCK(E)

 

UNLOCK(H)

   

W_LOCK(G)

     

UNLOCK(D)

     

   

W_LOCK(D)

   

W_LOCK(H)

   

UNLOCK(D)

   

UNLOCK(H)

 

UNLOCK(E)

 

 

UNLOCK(B)

 

UNLOCK(G)

     

Tab. 1 Uspo°ßdateln² rozvrh transakcφ T1,...,T4

DalÜφ p°φklad specißlnφho p°φpadu stromovΘho protokolu se t²kß B-strom∙. Ukß₧eme zßrove≥, jak se realizujφ fyzickΘ zßmky, tj. jak se °eÜφ p°φpad vφcenßsobnΘho vstupu do fyzickΘ struktury. Pro prßci s B-stromy budeme uva₧ovat operace READ(X) a operaci UPDATE(X). Prvnφ z nich znamenß nalezenφ a p°eΦtenφ listovΘho uzlu s objektem X z B-stromu, druhß p°edstavuje bu∩ INSERT(X) nebo DELETE(X), tj. aktualizaci B-stromu prost°ednictvφm objektu X.

Pro operaci UPDATE lze u B-strom∙ objevit jednu p°irozenou vlastnost, kterß nßm urΦuje, jak velk² kus B-stromu musφ b²t uzamΦen, aby operace UPDATE mohla b²t provedena.

Uzel B-stromu nazveme bezpeΦn², jestli₧e mß

(i) mΘn∞ ne₧ m-1 klφΦ∙ (pro operaci INSERT)

(ii) vφce ne₧ é m/2ù - 1 klφΦ∙ (pro operaci DELETE)

Nenφ-li uzel bezpeΦn², bude UPDATE ovliv≥ovat p°edch∙dce tohoto uzlu (d∙sledek Üt∞penφ nebo slΘvßnφ uzl∙). Pro ka₧d² uzel v B-stromu bude existovat fronta, do kterΘ se budou uklßdat po₧adavky na zamykßnφ. Tyto po₧adavky budou ud∞leny v souladu s pravidly v²luΦn²ch a sdφlen²ch zßmk∙, tj. jeden uzel m∙₧e b²t uzamΦen souΦasn∞ nejv²Üe jednφm v²luΦn²m zßmkem nebo n∞kolika sdφlen²mi zßmky. Nesmφ vÜak b²t uzamΦen souΦasn∞ sdφlen²m (R_LOCK) a v²luΦn²m (W_LOCK) zßmkem. P°ipome≥me, ₧e sdφlenΘ zßmky umo₧≥ujφ pouze Φtenφ.

Pro B-stromy ukß₧eme dva protokoly, zvlßÜ¥ pro Φtenφ B-stromu a zvlßÜ¥ pro aktualizaci. V obou algoritmech uzamykßnφ p°edpoklßdßme hloubku stromu v∞tÜφ ne₧ 1.

  • protokol pro READ

1. Umφsti R_LOCK do ko°ene B-stromu

2. P°eΦti ko°en B-stromu do vyrovnßvacφ pam∞ti (b∞₧n² uzel)

3. while b∞₧n² uzel nenφ list do

begin umφsti R_LOCK na nßslednφka uzlu b∞₧nΘho uzlu; uvolni zßmek uzlu b∞₧nΘho uzlu; p°eΦti nßslednφka b∞₧nΘho uzlu

end

  • protokol pro UPDATE

1. Umφsti W_LOCK do ko°ene B-stromu

2. P°eΦti ko°en B-stromu do vyrovnßvacφ pam∞ti (b∞₧n² uzel)

3. while b∞₧n² uzel nenφ list do

begin umφsti W_LOCK na nßslednφka uzlu b∞₧nΘho uzlu;

p°eΦti nßslednφka do b∞₧nΘho uzlu;

if b∞₧n² uzel je bezpeΦn² then uvolni zßmky vÜech uzamΦen²ch p°edch∙dc∙

end

VÜimn∞me si, ₧e protokol pro READ udr₧uje v₧dy jen jeden uzamknut² uzel v transakci, u protokolu pro UPDATE jich m∙₧e b²t vφce.

Uva₧ujme Φßst B-stromu s m=3 (obrßzek 2). B-strom obsahuje klφΦe z domΘny atributu nap°. JM╔NO_F (jmΘno filmu) a do stromu se bude pouze zapisovat (tj. pro bezpeΦnost staΦφ spln∞nφ vlastnosti (i)). Chceme-li nap°. vlo₧it do B-stromu klφΦ Filosofskß historie, vypl²vß z algoritmu vklßdßnφ do B-stromu, ₧e na cest∞ z ko°ene stromu 6 do listu 0 je bezpeΦn² uzel 6 a 2. Tedy W_LOCK bude aplikovßn t°ikrßt - sice na uzly 6, 2, 0, ovÜem s tφm, ₧e uzel 6 bude uvoln∞n jeÜt∞ p°ed vstupem do uzlu 0. Zarßmovanß Φßst obrßzku 2 ukazuje zamknutou v∞tev stromu t∞sn∞ p°ed operacemi Üt∞penφ uzlu 0 (bude se opravovat i uzel 2). Odemknutφ uzl∙ 2 a 0 bude nßsledovat a₧ po t∞chto operacφch.

 

 

 

 

 

6

Karla - -

2 5 -

 

2 5

F.L .V∞k - - Poklad - -

0 4 - 3 1 -

 

0 4

BabiΦka F.L.V∞k - Karla - -

Z3 Z5 - Z1 - -

Obr. 2 Zamykßnφ B-stromu

Zßv∞rem poznamenejme, ₧e protokol pro aktualizaci B-stromu je specißlnφm p°φpadem stromovΘho protokolu. Je tedy garantovßna uspo°ßdatelnost pro jak²koli legßlnφ rozvrh, zajiÜt∞na je absence uvßznutφ. StromovΘ protokoly majφ proti dvoufßzov²m uzamykacφm protokol∙ dv∞ v²hody. Umo₧≥ujφ d°φve odmykat objekty a zabra≥ujφ uvßznutφ. Obojφ p°ispφvß k zv²Üenφ pr∙chodnosti transakΦnφho provozu.



<seznam dφl∙ serißlu>   <COMPUTERWORLD>