- transakcja i jej własności,
- formalny model transakcji,
- sekwencyjne i współbieżne realizacje zbioru transakcji,
- uszeregowalność transakcji.
Wprowadzenie
Jeżeli w systemie bankowym będzie równocześnie działać wiele aplikacji przelewu (co jest typowe w rzeczywistości), wówczas ich równoczesna praca może powodować powstawanie danych niespójnych, czyli nieprawdziwych - mogą się pojawiać stany kont w rzeczywistości niewystępujące.
Rozwiązaniem omówionych problemów jest wprowadzenie mechanizmu tzw. transakcji. Transakcja jest sekwencją logicznie powiązanych operacji na bazie danych, która przeprowadza bazę danych z jednego stanu spójnego w inny stan spójny. Typy operacji na bazie danych obejmują: odczyt i zapis danych oraz zakończenie i akceptację (zatwierdzenie), lub wycofanie transakcji.
1. rozpoczęcie transakcji - begin,
2. pomniejszenie stanu konta A o kwotę N,
3. powiększenie stanu konta B o kwotę N,
4. zatwierdzenie transakcji - commit.
Atomowość oznacza, że zbiór operacji wchodzących w skład transakcji jest niepodzielny, to znaczy albo zostaną wykonane wszystkie operacje transakcji albo żadna. Dotyczy to również wszystkich operacji transakcji wykonywanych na obiektach rzeczywistych (tak zwane akcje rzeczywiste) – np. wypłata gotówki z bankomatu.
Spójność oznacza, że transakcja przeprowadza bazę danych z jednego stanu spójnego do innego stanu spójnego. W trakcie wykonywania transakcji baza danych może być przejściowo niespójna. Transakcja nie może naruszać ograniczeń integralnościowych.
Izolacja oznacza, że transakcje są od siebie logicznie odseparowane. Transakcje oddziałują na siebie poprzez dane. Mimo współbieżnego wykonywania, transakcje widzą stan bazy danych tak, jak gdyby były wykonywane w sposób sekwencyjny.
Trwałość oznacza, że wyniki zatwierdzonych transakcji nie mogą zostać utracone w wyniku wystąpienia awarii systemu. Zatwierdzone dane w bazie danych, w przypadku awarii, muszą być odtwarzalne.
- atomowa jeżeli pieniądze zostaną poprawnie przetransferowane z konta A do B;
- spójna jeżeli kwota odjęta z konta A jest równa kwocie dodanej do konta B;
- izolowana jeżeli inne transakcje wykonywane współbieżnie, czytające i modyfikujące konta A i B, nie mają wpływu na tę transakcję;
- trwała jeżeli po zakończeniu transakcji, baza danych trwale odzwierciedla nowe stany kont A i B.
- Active: transakcja jest aktywna, jest w czasie realizowania swoich operacji;
- Partially committed: transakcja jest częściowo zatwierdzona;
- Committed: transakcja została zatwierdzona;
- Failed: transakcja została wycofana;
- Terminated: transakcja zakończyła się zatwierdzeniem lub wycofaniem.
Przejścia z jednego stanu do drugiego są opisane tzw. diagramem stanów transakcji przedstawionym na slajdzie. Rozpoczęcie transakcji (Begin Transaction) uruchamia transakcję, która jest aktywna. Każda operacja zapisu lub odczytu danych w ramach tej transakcji dokonuje się w stanie aktywnym transakcji. Kończenie transakcji z jej wycofaniem (Abort) przeprowadza transakcję ze stanu Active do stanu Failed, a następnie Terminate. Kończenie transakcji z jej zatwierdzeniem przeprowadza ją ze stanu Active do Partially committed - transakcja jest gotowa do zatwierdzenia. Z tego stanu można jeszcze transakcję wycofać, np. w sytuacji awarii systemu. Ostateczne zatwierdzenie transakcji przeprowadza ją do stanu Committed, a następnie do Terminated, co kończy działanie transakcji.
End_transaction oznacza, ze wszystkie operacje odczytu i/lub zapisu transakcji zostały wykonane. W tym momencie, zachodzi konieczność podjęcia decyzji, czy zmiany wprowadzone przez transakcję mają być wprowadzone do bazy danych (zatwierdzenie transakcji) czy też mają być wycofane z bazy danych.
Commit oznacza zatwierdzenie (akceptacja transakcji), czyli pomyślne zakończenie transakcji - zmiany wprowadzone przez transakcję mają być wprowadzone do bazy danych.
Rollback oznacza wycofanie transakcji, czyli niepoprawne zakończenie transakcji i konieczność wycofania z bazy danych wszystkich ewentualnych zmian wprowadzonych przez transakcję.
W dalszej części wykładu będziemy stosowali następującą notację:
- ri(x) oznacza odczyt danej x przez i-tą transakcję;
- ri(x, wartość) oznacza odczyt danej x przez i-tą transakcję, przy czym 'wartość' jest aktualnie odczytaną wartością danej x;
- wi(x) oznacza zapis danej x przez i-tą transakcję;
- wi(x, wartość) oznacza zapis danej x przez i-tą transakcję, przy czym 'wartość' jest aktualnie zapisywaną wartością danej x;
- ci oznacza zatwierdzenie i-tej transakcji;
- ai oznacza wycofanie i-tej transakcji.
Każda transakcja może być reprezentowana przez graf skierowany: G = (V, A), gdzie:
- V jest zbiorem węzłów odpowiadających operacjom transakcji Ti;
- A jest zbiorem krawędzi reprezentujących porządek na zbiorze operacji.
Dwa przykłady grafu transakcji przedstawiono na slajdzie. W pierwszym z nich, pierwsza operacja transakcji pierwszej odczytuje daną x (r1(x)), następnie zapisuje/modyfikuje tę daną (w1(x)). Pierwszą operacją drugiej transakcji jest operacja odczytu danej y (r2(y)), następną operacją jest zapis danej y (w2(y)) przez transakcję drugą. Ostatnią jest operacja zatwierdzenia transakcji pierwszej (c1). Pierwszy przykład reprezentuje sekwencyjnie wykonywane transakcje. Drugi przykład reprezentuje współbieżnie wykonywane transakcje.
- porządek operacji,
- zależność operacji,
- typ operacji.
Zgodnie z pierwszym kryterium wyróżnia się transakcje realizowane sekwencyjnie (tj. jedna po drugiej) i transakcje realizowane współbieżnie (tj. równocześnie). Zgodnie z drugim kryterium wyróżnia się transakcje zależne od danych i transakcje niezależne od danych. W transakcji zależnej do danych, zbiór danych adresowanych przez transakcję może nie być w całości znany w momencie rozpoczęcia transakcji. Zbiór ten jest określany dynamicznie w trakcie pracy transakcji, zależnie od danych przetworzonych przez wcześniejsze polecenia. Ze względu na trzecie kryterium wyróżnia się transakcje wyłącznie odczytujące dane i transakcje modyfikujące dane.
Częściowo uporządkowaną sekwencją operacji należących do zbioru współbieżnie wykonywanych transakcji nazywamy realizacją (historią). Realizacja modeluje, formalnie, współbieżne wykonanie zbioru transakcji.
Formalnie, realizacją S zbioru n transakcji T1, T2, ..., Tn nazywamy takie uporządkowanie operacji współbieżnie wykonywanych transakcji, w którym, dla każdej transakcji Ti w realizacji S , porządek wykonania operacji transakcji Ti jest taki sam jak częściowy porządek w zbiorze operacji transakcji Ti.
Jako przykład zaakceptowanej projekcji rozważmy realizację przedstawioną na slajdzie. Transakcja T0 zapisuje daną x (w0(x)), następnie daną y (w0(y)) i zatwierdza te operacje (c0). Następnie transakcje T1 i T2 są realizowane współbieżnie. T1 odczytuje daną x (r1(x)), następnie T2 (r2(x)) odczytuje tę samą daną x. Kolejne operacje to: zapis danej x przez T1 (w1(x)), odczyt danej y przez T1 (r1(y)), zapis danej x przez T2 (w2(x)), zatwierdzenie T2 (c2), zapis danej y przez T1 (w1(y)), zatwierdzenie T1, odczyt danej x przez Tf, odczyt danej y przez Tf i zatwierdzenie Tf.
Przykład grafu realizacji dla transakcji T1, T2, Tf przedstawiono na slajdzie.
Stan bazy danych reprezentuje zbiór wartości wszystkich danych w bazie. Obraz bazy danych widziany przez transakcję Ti jest zbiorem wartości danych odczytywanych przez transakcję Ti.
Przejdziemy teraz do omówienia problematyki uszeregowalności realizacji. Przyjmiemy następujące założenia:
- każda realizacja sekwencyjna jest poprawna;
- każda realizacja współbieżna równoważna dowolnej realizacji sekwencyjnej tego samego zbioru transakcji jest również poprawna.
Po pierwsze, gdy dotyczą tej samej danej. Innymi słowy, operacje na różnych danych nigdy nie są konfliktowe.
Po drugie, operacje konfliktowe muszą należeć do różnych transakcji.
Po trzecie, jedna z dwóch operacji oi lub oj musi być operacją zapisu.
Łatwo zauważyć, że następujące pary operacji mogą znajdować się w konflikcie:
- ri(x ) i wj(x ),
- wi(x ) i rj(x ),
- wi(x ) i wj(x ).
Obecnie, po wprowadzeniu relacji poprzedzania, możemy formalnie zdefiniować pojęcie równoważności dwóch realizacji. Mówimy, że dwie realizacje r(TAU ) = (Tr(TAU) , <r ) i r ( TAU) = (Tr(TAU) , <r ) są konfliktowo' równoważne , jeżeli dla każdej pary operacji oi(x ) i oj(x ) w realizacji r(TAU ), takich, że oi(x ) -> oj(y ), zachodzi również oi(x ) -> oj(y ) w realizacji r ( TAU). Obecnie, sformułujemy kryterium poprawności współbieżnej realizacji zbioru transakcji nazywane kryterium konfliktowej uszeregowalności.
Definicja kryterium konfliktowej uszeregowalności brzmi następująco. Realizacja r(TAU ) zbioru transakcji T jest konfliktowo uszeregowalna wtedy i tylko wtedy, gdy jest ona konfliktowo równoważna dowolnej sekwencyjnej realizacji zbioru TAU.
W jaki sposób można zweryfikować czy dana realizacja współbieżna spełnia kryterium konfliktowej uszeregowalności? W celu weryfikacji konfliktowej uszeregowalności realizacji konstruujemy graf konfliktowej uszeregowalności realizacji. Grafem konfliktowej uszeregowalności realizacji r(TAU ) nazywamy skierowany graf CSRG(r(TAU )) = (V , A ), taki, w którym zbiór wierzchołków V odpowiada transakcjom ze zbioru T, natomiast zbiór krawędzi zawiera relacje poprzedzania transakcji Ti i Tj: A = {(Ti , Tj ) : Ti -> Tj }.
Możemy obecnie, korzystając z grafu konfliktowej uszeregowalności sformułować twierdzenie, pozwalające w sposób algorytmiczny weryfikować, czy dana realizacja współbieżna jest poprawna, tj. konfliktowo-uszeregowalna. Realizacja r(TAU ) zbioru transakcji T jest konfliktowo-uszeregowalna wtedy i tylko wtedy, gdy jej graf konfliktowej uszeregowalności CSRG(r(TAU )) jest acykliczny.
Poprawność powyższego twierdzenia wynika bezpośrednio z własności spójności transakcji. Zgodnie z własnością spójności, każda transakcja transformuje bazę danych z jednego stanu spójnego do innego stanu spójnego. Stąd wynika, że każda realizacja sekwencyjna zbioru transakcji zachowuje spójność bazy danych, gdyż jest ona sekwencją transformacji odwzorowujących bazę danych z jednego do innego stanu spójnego. Z definicji grafu konfliktowej uszeregowalności wynika, że graf ten, dla dowolnej realizacji sekwencyjnej, musi być acykliczny. Z definicji kryterium konfliktowej uszeregowalności wynika, że dowolna realizacja współbieżna jest poprawna, jeżeli jest ona równoważna dowolnej realizacji sekwencyjnego tego samego zbioru transakcji. Z definicji równoważności realizacji wynika, że graf konfliktowej uszeregowalności realizacji współbieżnej musi być również acykliczny, jeżeli realizacja ta jest konfliktowo-uszeregowalna. Co kończy skrótowy dowód poprawności podanego twierdzenia.
Transakcja T2 odczytuje wartości danych x i y zapisane przez transakcję T1, która następnie, jest wycofywana. Zauważmy, że po restarcie systemu, transakcja T2 nie zostanie poprawnie odtworzona, gdyż powinna ona odczytać stan bazy danych sprzed wykonania transakcji T1.
Mówimy, że transakcja Ti czyta daną x z transakcji Tj w realizacji H jeżeli:
1. wj[x] < ri[x ];
2. aj < ri[x ]
3. jeżeli istnieje operacja wk[x] taka, że wj[x] < wk[x] < ri[x ], wtedy ak < ri[x ].
Mówimy, że transakcja Ti czyta z transakcji Tj w realizacji H, jeżeli Ti czyta dowolna daną z transakcji Tj w realizacji H.
Korzystając z wprowadzonych pojęć, możemy obecnie zdefiniować nowe klasy realizacji transakcji.
Mówimy, że realizacja H jest odtwarzalna (ang. recoverable ) (RC ) wówczas, jeżeli transakcja Ti czyta z transakcji Tj (i różne od j ) w realizacji H i ci należy do realizacji H , to cj < ci
Mówimy, że realizacja H unika kaskadowych wycofań (ang. avoids cascading aborts ) (ACA ) wówczas, jeżeli transakcja Ti czyta z transakcji Tj (i różne od j ), to cj < ri [x ]
Mówimy, że realizacja H jest ścisła (ang. strict ) (ST ) wówczas, jeżeli wj [x ] < oi [x ] (i różne od j ), zachodzi aj < oi [x ] lub cj < oi [x ], gdzie oi [x ] jest jedną z operacji ri [x ] lub wi [x ]
Rozważmy realizację H1. Realizacja H1 jest realizacją konfliktowo-uszeregowalną, ale nie jest realizacja odtwarzalną. Transakcja T2 czyta daną y z transakcji T1, ale c2 < c1. Łatwo również zauważyć, że realizacja H1 nie należy do klasy realizacji ACA jak również ST.
Rozważmy realizację H2. Realizacja H2 jest realizacją konfliktowo-uszeregowalną. Ponadto, jest również realizacją odtwarzalną. Transakcja T2 czyta daną y z transakcji T1, ale tym razem c1 < c2. Realizacja H2 nie należy do klasy realizacji ACA jak również ST.
Rozważmy realizację H3. Realizacja H3 jest realizacją konfliktowo-uszeregowalną i odtwarzalną. Ponadto, jest ona również realizacja unikającą kaskadowych wycofań (należy do klasy ACA). Transakcja T2 czyta daną y z transakcji T1 i spełniony jest warunek c1 < r2[y]. Realizacja H3 nie jest natomiast realizacją ścisłą.
Wreszcie, rozważmy realizację H4. Realizacja H4 jest realizacją konfliktowo-uszeregowalną, odtwarzalną unikającą kaskadowych wycofań oraz realizacją ścisłą.
Zbiór realizacji ścisłych zawiera się w zbiorze realizacji unikających kaskadowych wycofań, który, z kolei, zawiera się w zbiorze realizacji odtwarzalnych. Diagram przedstawiony na slajdzie ilustruje zależności pomiędzy zbiorami realizacji RC, ACA i ST. Na diagramie zaznaczono również przynależność przykładowych realizacji H1, H2, H3 i H4.
Mówiąc o własnościach transakcji, stwierdziliśmy, że jedną z czterech własności transakcji jest własność izolacji. Korzystając z wprowadzonych dotychczas pojęć, własność izolacji transakcji możemy zdefiniować formalnie. Własność izolacji transakcji oznacza, że transakcja jest konfliktowo-uszeregowalna i ścisła.
