トランザクション管理機構

トランザクション
Ｒｅｃｏｖｅｒａｂｌｉｔｙ
• あるscheduleは障害からの回復が容易で
あり、又、別のscheduleは回復処理が複雑
になることがある。
• 従って、回復可能なscheduleを明らかにす
ることは重要。或いは、回復が容易な
scheduleを明らかにすることが重要
• Recoverable schedule:一旦コミットしたらroll backはしな
い。
• Sa:r1(X);r2(X);w1(X);r1(Y);w2(X);c2;w1(Y);c1
– recoverable.
• Sc:r1(X);w1(X);r2(X);r1(Y);w2(X);c2;a1;
– Unrecoverable
• Sd:r1(X);w1(X);r2(X);r1(Y);w2(X);w1(Y);c1;c2;
– T2のc,aをT1の後に持ってゆく
• Se:r1(X);w1(X);r2(X);r1(Y);w2(X);w1(Y);a1;a2;
– T1がアボートするとT2もアボート
• Recoverable scheduleではコミットしたトランザクションの
ロールバックは不要
• しかし、cascade rollback
Casecade rollback
• 親がアボートすると子供は全てロールバックしなくてはな
らない。
• 極めてコストが高い
• Cascadeless scheduling
– トランザクションは常にコミットされたデータのみをread
• Strict Schedule
– Transaction can neither read nor write an itemX until the last
transaction that wrote X has committed(or aborted)
• Sf:w1(X,5);w2(X,8);a1
– これはcascadeless しかし non-strict
Serializability
• これまではrecoverabilityについて見てきた。
これからは並行トランザクションの正当性
について考える。
r1(X);
X:=X-N;
w1(X);
r1(Y);
Y:=Y+N;
w1(Y);
T1
r2(X);
X:=X+M;
w2(X);
T2
インターリーブしないと(a)か(b)しかない。
インターリーブを許すと以下も有り得る
Serializability
• どのスケジュールを許すのか？
• Schedule
– Serial
– Non-serial
• トランザクションが互いに独立であるとすると、
serial scheduleは正しいと言っても良いであろう。
• トランザクションの順序はここで問題にしていな
い。トランザクションそれぞれが正しいデータベー
スの状態遷移を保証するものと考える。（ACID
のC)
• あるschedule Sが serializableとは, ある
serial scheduleに等価であることを指す。
– N!個もの多数のserial schedule 更に多くの
interleaved scheduleが有り得る
– Non-serial scheduleはSerial scheduleに
equivalentであるものとnon-equivalentであるも
のの２つに分類可能
• Serial scheduleとequivalentであるなら正当
なことは当然
Equivalence between Schedules
• 2つのscheduleが等価であるとは、個々のデータ
アイテムに対してそれに施される操作が同一順
である時を指す。
• Conflict equivalence
– Two schedules are said to be conflict equivalent if the
order of any two conflicting operations is the same in
both schedules. (r1-w2, w1-w2)
• A schedule S is conflict serializable if it is conflict
equivalent to some serial schedule S’.
Test for conflict serializability
• Selialization graph
– Directed Graph G=(N,E)
– node N={T1,T2,…….,Tn}
– edge E={e1,e2,……..,em},
• ei = ( Tj → Tk ) j, k ∈1,,,n
• TjのoperationがTkのconflicting operationの前に出現
algorithm
• 各Tiに対してノードを作成
• rj（X)；wi(X) なら Tｊ → Ti
• wj(X);ri(X) なら Tj → Ti
• wj(X);wi(X) なら Tj → Ti
• サイクルがなければ serializable
– Topological sort
• 理解を助けるべくエッジにconflictする
データアイテム名を記載することが有る
４つの例に対するserialization graphの作成例
３つのトランザクションが並行実行される場合の例
T1, T2, T3がそれぞれ、X,Y そして、X，Y，Z，
そして、Y,Zにアクセスする。
これらがインターリーブする時それらは serializable
かどうか判定出来る必要がある。

Download Report