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

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

スケジュールは、データベース同時実行制御理論の基本的な概念です。実際には、ほとんどの汎用データベース システムでは、競合を直列化できるスケジュールと厳密に回復可能なスケジュールが採用されています。

グリッド表記:

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

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

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

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

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

この例では、列はスケジュール 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 はシリアル スケジュールの例です。

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

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

シリアル化可能性は、データ項目内のデータを一貫した状態に保つために使用されます。これは、同時トランザクションのスケジュールの正確さの主要な基準であり、すべての汎用データベース システムでサポートされています。シリアル化できないスケジュールは、誤った結果を生成する可能性が高く、非常に有害になる可能性があります (たとえば、銀行内でお金を扱う場合)。^{[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)、R4(X)、R5(X)、R6(X)、R7(X)、R8(X)、R9(X)、R10(X)、R11(X)、R12(X)、R13(X)、R14(X)、R15(X)、R16(X)、R17(X)、R18(X)、R19(X)、R20
• R1(X)、W2(Y)、R3(X)

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

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

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

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

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

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

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

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

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

競合直列化可能性は、優先順位グラフのサイクル内の任意のトランザクションを再開するか、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 とビュー同等ではありません。

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

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

スケジュールは、何らかのシリアル スケジュールとビュー同等である場合に、ビュー シリアル 化可能です。定義により、競合シリアル化可能なすべてのスケジュールは、ビュー シリアル化可能であることに注意してください。

上記の例 (競合シリアライズ可能の説明での例と同じ) は、ビュー シリアライズ可能かつ競合シリアライズ可能であることに注目してください。ただし、競合シリアライズ可能ではないビュー シリアライズ可能なスケジュールもあります。これらのスケジュールは、ブラインド書き込みを実行するトランザクションです。

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

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

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

これらのスケジュールは回復可能です。スケジュール F は、T1 が T2 より前にコミットし、T2 が読み取った値が正しくなるため回復可能です。その後、T2 は自身をコミットできます。F2 スケジュールでは、T1 が中止された場合、読み取った A の値が正しくないため、T2 も中止する必要があります。どちらの場合も、データベースは一貫性のある状態のままになります。

スケジュール J は、T1 によって書き込まれた値を以前に読み取ったにもかかわらず、T2 が T1 より前にコミットしたため、回復不能です。T2 がコミットした後に T1 が中止されたため、T2 によって読み取られた値は間違っています。トランザクションはコミット後にロールバックできないため、スケジュールは回復不能です。

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

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

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

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

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

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

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

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

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

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

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