データベーストランザクションスケジュール

Order of execution of transactions in transaction processing

データベースやトランザクション処理（トランザクション管理）の分野において、システムのスケジュール（または履歴）は、システム内で実行される一連のトランザクションの実行順序を記述する抽象モデルです。スケジュールは、システム内で同時に実行される一連のトランザクションによって実行される、時間順に並べられた操作（アクション）のリストであることが多いです。特定の操作間の時間的順序がシステムによって決定されない場合は、半順序が使用されます。このような操作の例としては、読み取り操作の要求、読み取り、書き込み、中止、コミット、ロックの要求、ロックなどがあります。多くの場合、スケジュールにはトランザクション操作タイプのサブセットのみが含まれます。

スケジュールは、データベースの同時実行制御理論における基本的な概念です。実際には、ほとんどの汎用データベースシステムでは、競合シリアライズ可能かつ厳密なリカバリが可能なスケジュールが採用されています。

表記

グリッド表記:

• 列:スケジュール内のさまざまなトランザクション。
• 行:操作(アクションとも呼ばれます)の時間順序。

操作（別名、アクション）:

• R(X):対応するトランザクションはオブジェクトXを「読み取り」ます（つまり、Xに格納されているデータを取得します）。これは、「書き込み」操作中にデータを単に上書きするのではなく、変更（例：X=X+4）できるようにするためです。スケジュールがグリッドではなくリストとして表される場合、アクションは次のように表されます。ここで、は特定のトランザクションに対応する番号です。 ${\displaystyle Ri(X)}$ ${\displaystyle i}$
• W(X):対応するトランザクションはオブジェクトXに「書き込み」ます（つまり、Xに格納されているデータを変更します）。スケジュールがグリッドではなくリストとして表される場合、アクションは次のように表されます。ここで、は特定のトランザクションに対応する番号です。 ${\displaystyle Wi(X)}$ ${\displaystyle i}$
• Com.:これは、対応するトランザクションが前のアクションを正常に完了し、そのすべての変更をデータベースに永続的に保存した「コミット」操作を表します。

あるいは、スケジュールは、順序付けられた各操作のペア間にアーク (つまり、有向エッジ)が存在する有向非巡回グラフ(または DAG) で表すこともできます。

例

スケジュールの例は次のとおりです。

D

T1	T2	T3
R(X)
W(X)
コム。
	R(Y)
	W(Y)
	コム。
		R(Z)
		W(Z)
		コム。

この例では、列はスケジュールD内の異なるトランザクションを表しています。スケジュールDは3つのトランザクションT1、T2、T3で構成されています。最初にT1がオブジェクトXの読み取りと書き込みを行い、次にコミットします。次にT2がオブジェクトYの読み取りと書き込みを行い、コミットします。最後にT3がオブジェクトZの読み取りと書き込みを行い、コミットします。

上記のスケジュール D は、次のようにリストとして表すことができます。

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

行動の期間と順序

通常、データベースにおける同時実行制御を推論するために、操作はアトミック（つまり、ある時点で発生し、継続時間は設定されない）としてモデル化されます。しかし、実際に実行される操作には、必ずある程度の継続時間が必要です。

スケジュール内のトランザクション操作はインターリーブ（つまり、複数のトランザクションを並行して実行できる）できますが、各トランザクション内の操作間の時間順序は変更されません。スケジュール内のトランザクション操作がインターリーブする場合（つまり、スケジュールが競合直列化可能だが直列化できない場合）、スケジュールは部分順序です。スケジュール内のトランザクション操作がインターリーブしない場合（つまり、スケジュールが直列化可能）は、 スケジュールは全順序です。

スケジュールの種類

完全なスケジュールとは、各トランザクションに対してアボート（ロールバックとも呼ばれます）またはコミットのいずれかのアクションを含むスケジュールです。トランザクションの最後のアクションは、コミットまたはアボートのいずれかです。アトミック性を維持するために、トランザクションはアボートされた場合、すべてのアクションを取り消す必要があります。

シリアル

実行されたトランザクションがインターリーブされていない場合、スケジュールはシリアルです(つまり、シリアル スケジュールとは、実行中のトランザクションが終了するまでトランザクションが開始されないスケジュールです)。

スケジュール D はシリアル スケジュールの例です。

D

T1	T2	T3
R(X)
W(X)
コム。
	R(Y)
	W(Y)
	コム。
		R(Z)
		W(Z)
		コム。

シリアル化可能

スケジュールは、結果がシリアル スケジュールと同等である場合に シリアル化可能です。

スケジュール E では、トランザクションのアクションが実行される順序は D と同じではありませんが、最終的には E は D と同じ結果になります。

E

T1	T2	T3
R(X)
	R(Y)
		R(Z)
W(X)
	W(Y)
		W(Z)
コム。	コム。	コム。

直列化可能性は、データ項目内のデータの一貫性を保つために使用されます。これは、同時トランザクションのスケジュールの正確性に関する主要な基準であり、すべての汎用データベースシステムでサポートされています。直列化不可能なスケジュールは、誤った結果を生成する可能性が高く、非常に有害となる可能性があります（例えば、銀行内での金銭取引など）。^{[1] [2] [3]}

アプリケーションが複数のトランザクション間の特定の順序を要求した場合、その順序は基盤となる直列化メカニズムとは独立して適用されます。これらのメカニズムは通常、特定の順序とは無関係であり、これらのトランザクションの複数の直列化順序と通常は互換性のある、予測不可能な部分的な順序を生成します。

矛盾する行動

次の 3 つの条件がすべて満たされる場合にのみ、 2 つのアクションは競合している (競合するペア) と言われます。

1. アクションは異なるトランザクションに属します。
2. アクションの少なくとも 1 つは書き込み操作です。
3. これらのアクションは同じオブジェクトにアクセスします（読み取りまたは書き込み）。^{[4] [5]}

同様に、2 つのアクションが競合するとみなされるのは、それらが非可換である場合のみです。同様に、2 つのアクションが競合するとみなされるのは、読み取りと書き込み、書き込みと読み取り、または書き込みと書き込みの競合である場合のみです。

次のアクション セットは競合しています:

• R1(X), W2(X), W3(X) (3つの矛盾するペア)

次のアクション セットは競合しません。

• R1(X)、R2(X)、R3(X)
• R1(X)、W2(Y)、R3(X)

競合は遅延や中止の根本的な原因であるため、可換性などを利用して競合を減らすとパフォーマンスが向上します。

要求された競合する操作が実際に実行された場合、競合は具体化されます。多くの場合、トランザクションによって要求/発行された競合する操作は、別のトランザクションによって保持されている操作のオブジェクトのロックによって遅延され、実行されないこともあります。または、トランザクションの一時的なプライベート ワークスペースに書き込んで具体化され、コミット時にデータベース自体にコピーされる場合もあります。要求/発行された競合する操作がデータベース自体で実行されない限り、競合は具体化されません。つまり、具体化されていない競合は、優先順位グラフのエッジでは表されません。

紛争の等価性

スケジュール S1 と S2 は、次の 2 つの条件が両方とも満たされる場合にのみ、競合同等であるとされます。

1. スケジュール S1 と S2 の両方に同じトランザクション セットが含まれており、各トランザクションは同じ順序で同じアクションを実行します。
2. 両方のスケジュールには、同じ競合ペアのセットがあります（各競合ペア内のアクションは同じ順序になります）。^[6]これは、すべての競合する操作（つまり、競合するペア内の操作）が両方のスケジュールで同じ順序になることを要求することと同じです。

同様に、2つのスケジュールが競合同等であるとは、各トランザクションのアクションの順序を維持しながら、競合しない操作のペア（隣接しているかどうかに関係なく）を交換することによって、一方を他方に変換できる場合にのみ言えます。^[4]

同様に、2つのスケジュールが競合同等であるとは、競合しない隣接する操作のペアを異なるトランザクションで交換することによって、一方を他方に変換できる場合にのみ言えます。^[7]

競合シリアライズ可能

スケジュールが 1 つ以上のシリアル スケジュールと競合同等である場合、 そのスケジュールは競合シリアル化可能であると言われます。

同様に、スケジュールが競合直列化可能であるのは、コミット済みのトランザクションのみを考慮した際に、その優先順位グラフが非循環である場合のみです。なお、グラフがコミットされていないトランザクションも含むように定義されている場合、コミットされていないトランザクションを含む循環が発生しても、競合直列化可能性違反は発生しないことに注意してください。

スケジュール K はシリアル スケジュール <T1,T2> と競合同等ですが、<T2,T1> とは競合同等ではありません。

K

T1	T2
R(A)
	R(A)
W(B)
コム。
	W(A)
	コム。

競合直列化可能性は、優先順位グラフのサイクル内の任意のトランザクションを再開するか、2フェーズロック、タイムスタンプ順序付け、または直列化可能なスナップショット分離を実装することによって強制できます。^[8]

ビューの同等性

2 つのスケジュール S1 と S2 は、次の条件が満たされる場合にビュー同等であるとされます。

1. S1 のトランザクションがオブジェクト X の初期値を読み取る場合、 S2 でも同じトランザクションが初期値を読み込みます。 ${\displaystyle T_{i}}$ ${\displaystyle T_{i}}$
2. トランザクションが S1 で書き込んだ値 (オブジェクト X の値) を読み取る場合、S2 でも読み取る必要があります。 ${\displaystyle T_{i}}$ ${\displaystyle T_{j}}$
3. S1 のトランザクションがオブジェクト X の最終書き込みを実行すると、S2 でも同じトランザクションが実行されます。 ${\displaystyle T_{i}}$ ${\displaystyle T_{i}}$

さらに、2 つのビュー同等のスケジュールには、各トランザクションが同じ順序で同じアクションを持つように、同じトランザクション セットが含まれている必要があります。

以下の例では、スケジュール S1 と S2 はビュー同等ですが、S1 も S2 もスケジュール S3 とビュー同等ではありません。

S1		シーズン2		S3
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
R(B) (1)			R(A)		R(A)
W(B)			W(A)		W(A)
コム。		R(B) (1)			R(B) (1)
	R(A)	W(B)			W(B)
	W(A)	コム。		R(B) (2)
	R(B) (2)		R(B) (2)	W(B) (3)
	W(B) (3)		W(B) (3)	コム。
	コム。		コム。		コム。

S3 が S1 および S2 とビュー同等であるための条件は、次の理由により、対応する上付き文字で満たされませんでした。

1. T1 は S1 と S2 で B の初期値を読み取りましたが、T2 は S3 で B の初期値を読み取ったため、ビュー同等性の最初の条件を満たしませんでした。
2. T2 は S1 と S2 で B に対して T1 によって書き込まれた値を読み取りましたが、T1 は S3 で B に対して T2 によって書き込まれた値を読み取ったため、ビューの等価性の 2 番目の条件に失敗しました。
3. S1 と S2 では T2 が B の最終書き込みを実行しましたが、S3 では T1 が B の最終書き込みを実行したため、ビューの等価性の 3 番目の条件を満たしませんでした。

2つのスケジュールがビュー同等かどうかを素早く分析するには、両方のスケジュールをリストとして記述し、各アクションの添え字でどのビュー同等条件に一致するかを指定します。両方のスケジュールですべてのアクションの添え字が同じ（または添え字がない）場合のみ、スケジュールはビュー同等です。

• S1: R1(A)_{初期読み取り}、W1(A)、R1(B)_{初期読み取り}、W1(B)、Com1、R2(A) _{T1 によって書き込まれる}、W2(A)_{最終書き込み}、R2(B) _{T1 によって書き込まれる}、W2(B)_{最終書き込み}、Com2
• S2: R1(A)_{初期読み取り}、W1(A)、R2(A) _{T1 によって書き込み}、W2(A)_{最終書き込み}、R1(B)_{初期読み取り}、W1(B)、Com1、R2(B) _{T1 によって書き込み}、W2(B)_{最終書き込み}、Com2
• S3: R1(A)_{初期読み取り}、W1(A)、R2(A) _{T1 による書き込み}、W2(A)_{最終書き込み}、R2(B)_{初期読み取り}、W2(B)、R1(B) _{T2 による書き込み}、W1(B)_{最終書き込み}、 Com1、Com2

ビューシリアル化可能

スケジュールがビューシリアル化可能とは、あるシリアルスケジュールとビューが同等である場合を指します。定義上、競合シリアル化可能なスケジュールはすべてビューシリアル化可能であることに注意してください。

G

T1	T2
R(A)
	R(A)
W(B)

上記の例（競合シリアライザブルの説明で示した例と同じ）は、ビューシリアライザブルと競合シリアライザブルの両方であることに注意してください。ただし、ビューシリアライザブルでありながら競合シリアライザブルではないスケジュールも存在します。これは、ブラインド書き込みを実行するトランザクションを含むスケジュールです。

H

T1	T2	T3
R(A)
	W(A)
	コム。
W(A)
コム。
		W(A)
		コム。

上記の例は競合シリアル化可能ではありませんが、ビューと同等のシリアル スケジュール <T1,| T2,| T3> があるため、ビュー シリアル化可能です。

スケジュールがビューシリアル化可能かどうかを判断することはNP 完全であるため、ビューシリアル化可能性は実用的な意味を持ちません。^{[引用が必要]}

回復可能

リカバリ可能なスケジュールでは、トランザクションは、その変更を読み取ったすべてのトランザクションがコミットされた後にのみコミットされます。トランザクションが別のトランザクションからの変更を読み取り、それに依存した後にコミットして中止した 場合、スケジュールはリカバリ不能になります。 ${\displaystyle T_{i}}$ ${\displaystyle T_{j}}$ ${\displaystyle T_{i}}$ ${\displaystyle T_{j}}$

F		F2		J
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
	R(A)		R(A)		R(A)
	W(A)		W(A)		W(A)
コム。		アボート			コム。
	コム。		アボート	アボート

これらのスケジュールはリカバリ可能です。スケジュールFは、T1がT2より先にコミットするため、T2が読み取った値が正しく、T2自身もコミットできるため、リカバリ可能です。スケジュールF2では、T1がアボートした場合、T2はAの値が誤っているため、アボートする必要があります。どちらの場合も、データベースは整合性の取れた状態のままです。

スケジュールJは、T1が書き込んだ値をT2が先に読み取ったにもかかわらず、T1より先にT2がコミットしたため、回復不能です。T2がコミットした後にT1がアボートしたため、T2が読み取った値は誤りです。トランザクションはコミット後にロールバックできないため、スケジュールは回復不能です。

カスケードレス

カスケードレススケジュール（別名「カスケードアボート回避（ACA）スケジュール」）は、ダーティリードを禁止することでカスケードアボートを回避するスケジュールです。カスケードアボートは、あるトランザクションのアボートによって、別のトランザクションが最初のトランザクションによるオブジェクトへの変更を読み取り、それに依存していたためにアボートを引き起こす場合に発生します。ダーティリードは、あるトランザクションが別のトランザクションのコミットされていない書き込みからデータを読み取る場合に発生します。^[9]

以下の例は、回復可能に関する説明で挙げたものと同じです。

F		F2
T1	T2	T1	T2
R(A)		R(A)
W(A)		W(A)
	R(A)		R(A)
	W(A)		W(A)
コム。		アボート
	コム。		アボート

この例では、F2は回復可能ですが、連鎖的なアボートは回避できません。T1がアボートした場合、T2はT1によって書き込まれた未コミットの値を既に読み取っているため、スケジュールの正確性を維持するためにはT2もアボートする必要があることがわかります。

以下は、連鎖的な中断を回避する回復可能なスケジュールです。ただし、T1によるAの更新は常に失われることに注意してください（T1が中断されるため）。

F3

T1	T2
	R(A)
R(A)
W(A)
	W(A)
アボート
	専念

T1がコミットされた場合、このスケジュールはシリアル化できないことに注意してください。カスケードアボートの回避はスケジュールの回復に十分ですが、必須ではありません。

厳しい

任意の2つのトランザクションT1とT2において、T1の書き込み操作がT2の競合する操作（読み取りまたは書き込み）に先行する場合、T1のコミットまたは中止イベントもT2の競合する操作に先行する、というスケジュールは厳密です。例えば、上記のスケジュールF3は厳密です。

厳密なスケジュールはカスケードレスですが、逆は成り立ちません。厳密なスケジュールにより、データベースの障害からの効率的な復旧が可能になります。

直列化可能性クラスの関係

次の式は、直列化可能性クラスと回復可能性クラス間の階層的 (包含) 関係を示しています。

• シリアル ⊂ 競合シリアル化可能 ⊂ ビューシリアル化可能 ⊂ すべてのスケジュール
• シリアル ⊂ 厳密 ⊂ カスケードレス (ACA) ⊂ 回復可能 ⊂ すべてのスケジュール

ベン図（下記）は上記の条項を図式的に表したものです。

直列化可能性と回復可能性のクラスのベン図

参照

• スケジュール（プロジェクト管理）
• 強力で厳密な 2 フェーズ ロック(SS2PL または厳密さ)。
• スナップショット分離をシリアル化可能にする^[8]スナップショット分離で。
• グローバル直列化可能性では、グローバル直列化可能性の問題とその解決策提案について説明します。
• 線形化可能性、並行コンピューティングにおけるより一般的な概念。

参考文献

1. Philip A. Bernstein、Vassos Hadzilacos、Nathan Goodman (1987): データベースシステムにおける同時実行制御と回復 (無料PDFダウンロード)、Addison Wesley Publishing Company、ISBN 0-201-10715-5
2. Gerhard Weikum、Gottfried Vossen (2001): Transactional Information Systems、Elsevier、ISBN 1-55860-508-8
3. Maurice Herlihy、J. Eliot B. Moss.トランザクショナルメモリ：ロックフリーデータ構造のアーキテクチャ的サポート.第20回国際コンピュータアーキテクチャシンポジウム (ISCA '93) 議事録. 第21巻第2号、1993年5月.
4. 「DBMSにおける競合シリアル化可能性」GeeksforGeeks . 2015年12月29日. 2023年11月27日閲覧。
5. シルバーシャッツ、アブラハム、コルト、ヘンリー・F、スダルシャン、S (2020).データベースシステムの概念（第7版）. ニューヨーク：マグロウヒル・エデュケーション. p. 814. ISBN 978-1-260-08450-4。
6. ラーマクリシュナン、ラグー;ゲールケ、ヨハネス (2000)。データベース管理システム。コンピュータ サイエンス シリーズ (第 2 版)。ボストン：マグロウヒル。 p. 540.ISBN​ 978-0-07-232206-4。
7. ガルシア＝モリーナ、ヘクター、ウルマン、ジェフリー・D、ウィドム、ジェニファー（2009年）『データベースシステム：完全版』ピアソン国際版（第2版）アッパーサドルリバー、ニュージャージー州：ピアソン／プレンティス・ホール、pp.  891– 892. ISBN 978-0-13-187325-4。
8. Michael J. Cahill、Uwe Röhm、Alan D. Fekete (2008):「Serializable isolation for snapshot databases」、2008 ACM SIGMOD international conference on Management of data の議事録、pp. 729-738、バンクーバー、カナダ、2008年6月、ISBN 978-1-60558-102-6(SIGMOD 2008 最優秀論文賞)
9. 「DBMSにおけるCascadeless」GeeksforGeeks . 2019年8月6日. 2023年11月29日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Database_transaction_schedule&oldid=1324291919"