ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

well-formedなトランザクションとlegalなスケジュール

データベース アーキテクチャ

はじめに

Transaction management におけるwell-formedなトランザクションとlegalなスケジュールについて説明します。

主に以下の資料を参考にします。
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
P60付近を参照ください。
ここでは exclusive locks を前提としています。本エントリでもこれに倣います。
shared locks も含めた議論はもう少し後のページにあります。

"Transactional Information Systems"も参考にしています。

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

well-formedなトランザクションの定義

read/write操作する対象をアイテムAとします。

トランザクションTiのアイテムAに対するread/write操作pi(A)が "critical section" に含まれるとき、そのトランザクションTiはwell-formedです。"critical section" とはAに対する一連の操作をlock/unlockのペアで区切ることを指します。

Ti: … li(A) … pi(A) … ui(A) ...

この説明だと、トランザクション内で同じアイテムの操作に対し、複数回に分けてlock/unlockすることが認められているかがあいまいです。

Ti: li(A) pi(A) ui(A) li(A) pi(A) ui(A)

この点について、トランザクション本では以下の定義がされています。

LR2: For each x accessed by ti, schedule s has at most one rli(x) and at most one wli(x) step; in other words, locks of the same type are set at most once per transaction and per data item.
※LR1, LR3は省略した
Transactional Information Systems, P132

ここでは read lock (shared) と write lock (exclusive) を区別して考えている点が異なりますが、各トランザクションの各アイテム毎に最大1回だけロックする、とあります。つまり、トランザクション内で同じアイテムの操作を異なる "critical section" に分けることは認めていないとわかります。

legalなスケジュールの定義

スケジュールSでトランザクションTiがアイテムAに対するロックを保持している間、他のトランザクションがAに対してロックを保持することがなければ、そのスケジュールSはlegalです。つまり、legalなスケジュールでは同じアイテムに対して異なるトランザクションが同時にロックを保持することを認めていません。

well-formedとlegalの関係

well-formedか否かはトランザクションに対してであり、legalか否かはスケジュールに対してです。よって、これは個別に判定する必要があります。

S1 : l1(A) r1(A) w1(B) u1(A)
T1はAに対するロックしか保持してないのにBに対する操作を行っています。よってこれはill-formed（well-formedではない）といえます。

S2 : l1(A) l1(B) r1(A) w1(B) l2(B) u1(A) u1(B) r2(B) w2(B) u2(B)
T1がBに対するロックを保持している間にT2もBに対するロックを保持しています。このスケジュールSは not legal です。
T1についてだけ見れば、well-formedといえます。

S3 : l1(A) r1(A) u1(A) l1(B) w1(B) u1(B) l2(B) r2(B) w2(B) u2(B)
T1, T2ともにwell-formedであり、S3はlegalといえます。

なお、well-formedなトランザクションで構成されたlegalなスケジュールであっても、serializabilityを保証することはできません（Ghost updateが起こりえます）。serializabilityを保証する手法として two-phase locking (2PL) protocol があります。

参考

別の資料にはwell-formedなトランザクションが同じアイテムに対して2回ロックしてはならない、と説明しています。

  • Well-formed transaction
    • locks data object before accessing it
    • does not lock the same data object twice
    • unlocks all the locked objects before completion
http://www.cs.virginia.edu/~son/662.pdffiles/cc06.pdf