wykład
Przetwarzanie transakcyjne
Cz.1
Opracował: dr inż. Janusz DUDCZYK
1
2
Baza danych jest spójna, jeżeli jej stan odpowiada stanowi świata rzeczywistego.
3
1. spójności BD ą� transformacja BD z jednego stanu spójnego do innego stanu spójnego.
2. Odporność na awarie sprzętowo-programowe.
3. Obsługa równoległa.
4
1
2
Jako przykład rozważmy system bankowy i aplikację przelewającą kwotę N z konta A na konto B.
AWARIA
Przelew kwoty N
$
$
5
Konto A Konto B
3
DEFINICJA
6
7
ACID
8
ACID
9
 Cechy transakcji
10
Read
Write
Begin End
Commit
Transaction Transaction
Partially
Committed
Active
Committed
Abort
Abort
Terminated
Faild
Stany transakcji
Active
Stany transakcji
Partially Committed
Save point:
Committed
Release savepoint
Failed
11
Rollback to savepoint
Terminated
Read
Write
Begin End
Commit
Transaction Transaction
Partially
Committed
Active
Committed
Abort
Abort
Terminated
Faild
1. (Begin_Transaction) uruchamia transakcję, która jest aktywna.
2. (Read, Write) dokonuje się w stanie aktywnym transakcji.
3. (Abort) przeprowadza transakcję ze stanu Active do stanu Failed, a następnie Terminate.
4. Kończenie transakcji z jej zatwierdzeniem przeprowadza ją ze stanu Active do Partially committed
transakcja jest gotowa do zatwierdzenia.
12
13
Poziom użytkownika: zbiór poleceń języka SQL, tj. select, insert, update, delete, commit,
rollback - tzw. transakcja logiczna.
14
Poziom SZBD - transakcja fizyczna, która jest zarządzana przez odpowiedni moduł SZBD.
Formalny model transakcji przedstawiono powyżej.
Transakcją Ti nazywamy uporządkowaną parę:
.
Zbiór operacji zawiera:
- odczyt (R),
- zapis (W),
- zatwierdzenie transakcji (C),
15
- wycofanie transakcji (A).
Dalsza notacja:
16
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.
sekwencyjne wykonywanie
r1(x)w1(x)r2(y)w2(y)c1
transakcji
r1(x)w1(x)w2(y)c1
współbieżne wykonywanie
transakcji
r2(y)
b
a
Graf skierowany, digraf - DG
c d
17
Trzy kryteria podziału transakcji: porządek operacji, zależność operacji, typ operacji.
18
KONIEC WYKA
ADU
Cz. 1
19
Graf skierowany - uzupełnienie
To uporządkowana para zbiorów, z których jeden zawiera
wierzchołki grafu, a drugi składa się z krawędzi grafu.
Ruch możliwy jest tylko w kierunku wskazanym przez
krawędzie.
Graf skierowany G definiuje dwójka G=
V-dowolny, niepusty zbiór wierzchołków;
E-podzbiór iloczynu kartezjańskiego V x V
Elementy E(G)  krawędzie grafu
Moc zbioru V  to rząd grafu G oznaczony przez /V/
Moc zbioru E  to rozmiar grafu G oznaczony przez //G//
20
Graf acykliczny - uzupełnienie
Graf nie zawierający cykli (cykl  to droga
zamknięta, której koniec jest identyczny
z początkiem)
l� cykl Hamiltona  cykl prosty, przebiegający przez wszystkie wierzchołki
grafu;
l� cykl prosty  cykl, w którym żaden wierzchołek nie powtarza się;
l� cykl Eulera  cykl zawierający wszystkie krawędzie grafu i przechodzący
przez nie dokładnie jeden raz;
l� cykl własny  w multigrafie cykl złożony z jednej krawędzi, który zaczyna
i kończy się w tym samym wierzchołku (tzw. pętlą własna wierzchołka).
Graf acykliczny  w przypadku grafów nieskierowanych spójnych grafy
acykliczne są równoważne drzewom, a niespójne  lasom.
21
Problem NP - zupełny
NPC  problem zupełny, w klasie NP, ze
względu na redukcje wielomianowe. Oznacza
to, że jeśli potrafimy rozwiązać jakikolwiek
problem NP-zupełny w czasie
wielomianowym, to potrafimy rozwiązać w
czasie wielomianowym wszystkie problemy
NP.
Problemy NP-zupełne (problem cyklu Hamiltona, komiwojażera,
kolorowania grafu, pokrycia wierzchołkowego).
22
Problem P
(determinictic polynomial)  deterministycznie wielomianowy
l� To problem decyzyjny dla, którego rozwiązanie
można znalez
ć w czasie wielomianowym.
l� Różnica pmiędzy problemem P i NP polega na tym,
że w przypadku P znalezienie rozwiązania ma mieć
złożoność wielomianową, podczas, gdy dla NP
sprawdzenie podanego z zewnątrz rozwiązania ma
mieć taką złożoność.
l� Każdy P jest NP
l� Czy NP jest P?  dotychczas nierozwiązane
23
Czas wielomianowy
l� To czas działania algorytmów wielomianowych, tj.:
takich, dla których najgorszy czas działania dla
danych wejściowych rozmiaru  n wynosi O(nk), dla
stałej  k
l� Notacja dużego O (asymptotyczne tempo wzrostu),
tj.: zachowanie wartości funkcji wraz ze wzrostem jej
argumentów;
l� O  opisuje, jak szybko dana funkcja rośnie lub
maleje, abstrahując od konkretnej postaci tych
zmian.
24