Jest to podstawowa funkcja każdego SZBD. Musi on mieć mechanizm dziennika bazy danych, gdzie odnotowuje się informacje na temat transakcji. Każda transakcja jest zapisywana w postaci identyfikatora transakcji oraz starej i nowej wartości elementarnej jednostki. Są różne rozwiązania, najczęściej tylko zapisuje się wartości zmieniane, ale są też systemy zapisujące wszystkie wartości. W pierwszym przypadku jest więc to tylko zabezpieczenie przed awarią, w drugim może także odnosić się do parametrów eksploatacyjnych.
Różne systemy przyjmują różne jednostki elementarne. Niektóre dzienniki zapisują całe stare i nowe wartości, inne natomiast zapisują tylko starą i nową zawartość pola. Gdy się coś dopisuje nowego, to zapisuje się starą wartość i to co dodane.
Mówi się że transakcja się wypełniła, gdy wykonała się od początku do końca.
W SZBD mówi się że transakcja się wypełniła gdy wszystkie zmiany są zapisane i w dzienniku i w bazie danych oraz we wszystkich obszarach obszarach roboczych.
Przyjmuje się dwufazową strategię wypełnienia :
1) transakcja nie może zapisać do bazy danych dopóty, dopóki się nie wypełniła w dzienniku baz danych;
2) transakcja nie może być wypełniona dopóty, dopóki nie zapisze w dzienniku wszystkich dokonywanych przez siebie zmian na jednostce elementarnej.
Najczęściej wykorzystuje się mechanizmy blokowania. Między zablokowaniem i odblokowaniem realizowane są również inne mechanizmy.
Zabezpieczenie przed awarią polega na tym, że gdy wystąpi awarią, to na podstawie dziennika odtworzone zostają operacje, które się wypełniły (od pewnego momentu). Na podstawie dziennika anuluje się transakcje niewypełnione i powtarza się wykonanie tych transakcji, które się wypełniły. Ważna jest wielkość dziennika, metody jego przeszukiwania, itp...
Blokowanie nie jest jedyna metodą realizowania współbieżności. Inna jest tzw. metoda optymistyczna (metoda znaczników czasowych, metoda walidacji) . Elementy bazy danych nie są tu blokowane (oszczędza to czas realizacji). Ta metoda nie traci czasu na blokowanie, lecz realizuje transakcję lub umieszcza ją w kolejce Ta metoda wymaga pewnego czasu na realizację transakcji. Jest efektywna gdy nie ma konfliktów między transakcjami. Zasada tej metody polega na nadawaniu każdej transakcji znacznika czasowego. Są one liczbami generowanymi w każdym takcie zegara. Istnieje szeregowalność pojawiających się transakcji. Każda transakcja ma inny znacznik czasowy, niezależnie od tego co chce robić. Znaczniki powinny być jak najmniejszymi liczbami. Należy często kopiować bazę, aby znaczniki nie były zbyt duże. Najczęściej są one 16-bitowe.
Dla każdej jednostki bazy danych zapamiętywane są:
- czas odczytu – najmniejszy znacznik czasowy należący do transakcji odczytującej tą jednostkę;
- czas zapisu – największy znacznik czasowy, który zapisuje jednostkę.
Transakcje w systemie pojawiają się szeregowo. Znacznik jest porównywany z czasem zapisu i odczytu, aby sprawdzić, czy transakcję można realizować czy też umieścić ją w kolejce.
Podczas realizacji transakcji nie jest możliwe aby transakcja mogła odczytywać jednostki jeżeli zostały one zapisane już po wykonaniu tej transakcji. Czyli jeżeli transakcja ma znacznik czasowy t1 i chce czytać, to nie może tego zrobić, jeżeli da tej jednostki czas zapisu t2 jest większy od t1 ( t2 > t1 ). Transakcja jest odrzucana.
Jeżeli dwie transakcje mają różne znaczniki czasowe i chcą zapisywać, to nie są odrzucane ale sprawdza się czy nie pojawił się jakiś odczyt pomiędzy nimi.
Załóżmy że transakcja zgłasza się znacznikiem czasowym t , gdy będzie chciała wykonać operację na jednostce X to dla tej jednostki będą podane dwa czasy: tr i tW .
Zasady :
1) operację wykonujemy jeżeli X = READ i t ³ tW lub jeżeli X =WRITE i znaczniki czasowe t ³ tr i t ³ tW Jeżeli t>tr , to czas odczytu jednostki X przybiera wartość t. Jeżeli t>tW , to czas zapisu jednostki X przybiera wartość t;
2) Jeżeli X=WRITE i zachodzi zależność tr £ t £ tW to transakcja nie jest realizowana (nie robimy ale i nie odrzucamy);
3) Jeżeli X=READ i t<tW lub X=WRITE i t<tr to transakcję odrzucamy
Optymalizacja zapytań
Zadaniem SZBD jest jak najszybsze udostępnienie informacji użytkownikowi (gdy użytkownik zadaje zapytanie, to baza danych powinna jak najszybciej znaleźć odpowiedź). Zamiast mówić o optymalizacji czasu mówi się o optymalizacji całego zapytania. Będzie to suboptymalizacja (czyli nie najlepsza).
Optymalizacja zapytania polega na przeanalizowaniu kontekstu w celu przeorganizowania zapytania – zamienia kolejność wykonywania operacji na bazie, tak aby odpowiedzieć użytkownikowi na zapytanie i nie pogubić wyników.
Np.: złączanie tabel:
- jedna z kolumn A,B
- druga z kolumn C,D
Przyjmujemy, że w obu tabelach jest określona ilość rekordów: nAB , nCD .
Aby te relacje połączyć sprowadzamy je przez obszar roboczy pamięci operacyjnej zawierający m bloków dal relacji AB i jeden blok dal relacji CD.
nAB m
nCD 1
bAB – ilość rekordów AB w jednym bloku z m.
Obliczamy całkowitą ilość dostępów do bloków, niezbędną dla odczytów AB – i
Podobnie:
INT – część całkowita
Rozważmy pierwszy sposób łączenia relacji: ściągamy pierwszą partię rekordów AB oraz i2*dostęp do CD. Potem ściągamy drugą partię i (i2-1)*bCD itd., aż do wykonania (i2-1)*bCD (dostęp do CD) i ściągamy i2 porcji AB.
Oznaczamy : ildI – ilość dostępów przy pierwszym sposobie: ildI = i1( i2-1) + 1
Drugi sposób: najpierw ściągamy paczkę rekordów CD a potem do tego pojedynczy AB, pierwsza partia rekordów CD i i1 rekordów z AB, druga partia rekordów CD oraz i1-1 dostępu do AB itd., na końcu i2 partię rekordów CD i dla niej wykonujemy i1-1 dostępów do AB.
ildII = i2( i1-1) + 1
Wprowadzamy oznaczenia:
d warunek – selekcja , Õ nazwa podrelacji – rzut
Mamy relacje AB i CD i dokonujemy następującego zapytania:
ÕA ( d B=C Ç D=” 99” ( AB x CD ))
odpowiedź nie zmieni się, gdy zapytanie to zostanie przekształcone do innej formy:
ÕA ( d B=C ( AB x d D=”99” (CD))
wykonanie zapytania w tej formie będzie szybsze jeżeli ilość rekordów wśród CD o wartości 99 będzie niewielka.
Optymalizator zapytań polega na zmianie początkowego zapytania w wersję oszczędniejszą czasowo. Algorytm optymalizacji oparty jest na drzewie wyrażeń.
Relacja równozłączeniowa – mamy dwie relacje R i S i równozłączenie dotyczy dwóch wybranych atrybutów z tych relacji (C z R i D z S) . Równozłączenie zapiszemy przy pomocy symboli:
Operacja selekcji może być zastąpiona równaniem :
Wnioski z działań algebraicznych na bazach danych:
1) Selekcje wykonuje się tak wcześnie jak jest to tylko możliwe. Selekcja wpływa na zmniejszenie czasu wykonywania o rząd wielkości, bo ma ona tendencję do zawężania pośrednich wyników wielokrotnych;
2) Łączyć należy niektóre selekcje z poprzedzającym je iloczynem kartezjańskim w celu utworzenia złączenia lub rozłączenia, które może być efektywniejsze od samego iloczynu kartezjańskiego;
3) Należy łączyć jednoargumentowe w pewne ciągi – w jedną operację wielowarunkową.
Przy wykonywaniu przekształceń należy posłużyć się następującymi prawami:
1) prawo przemienności dla złączeń i iloczynów
2) prawo łączności dla złączeń i iloczynów
3) prawo kaskada rzutów
Zakładamy że atrybuty { A1..An } Ì { B1..Bm} wykonujemy najpierw
ÕA1...An (ÕB B2...Bm (R)) º ÕA1...An ®
4) kaskada selekcji
dF1 (dF2 R)) º dF2 (dF1 (R)) º dF1 Ç F2 (R)
5) przemienność selekcji i rzutów
ÕA1...A k (dF (E)) º dF (ÕA1..A k (E))
6) przemienność selekcji i iloczynu kartezjańskiego
dF (E1 x E2 ) º dF(E1) x E2
Z tego prawa wypływają również inne związki:
- jeżeli F = F1 Ç F2 to dF (E1 x E2 ) º dF1(E1) x dF2(E2 )
- jeżeli F1 dotyczy atrybutów relacji E1, F2 dotyczy zarówno E1 jak i E2, to można zapisać:
dF (E1 x E2 ) º dF2(dF1(E1) x E2 )
7) przemienność selekcji z sumą
dF (E1 È E2 ) º dF(E1) È dF(E2)
8) przemienność selekcji z różnicą
dF (E1 \ E2 ) º dF(E1) \ dF(E2)
9) przemienność rzutów z iloczynem kartezjańskim
Przyjmujemy E1E2 – relacje A1...An – atrybuty relacji E1
B1..Bm – atrybuty dokładnie tylko E...
wips1