The Notion of Consistency and Predicate Locks in a Database System

October 2, 2021

トランザクションを並行実行するときに、直列実行した場合と同じ実行結果をえるには、各トランザクションがロックを解放後に新しいロックを獲得してはならないことを示した。 その場合もデッドロックがおきうるが、それは並列実行を終了するためにはいつロックをかければよいかという議論である。 ここでは、並列実行が終了した場合に直列実行と同じ結果になる一貫性を保証できるロックの順序を問う。

nステップのトランザクション\(T\)を系列 \({\rm \boldsymbol{T}}=((T, a_i, e_i))^n_{i=1}\)とかく。 \(T\)はステップ\(i\)にエンティティ\(e_i\)に対してアクション\(a_i\)を実行する。 アクションは、\(\text{lock}\), \(\text{unlock}\), エンティティの状態を変える操作のいずれかである。 ロックを、排他ロックと共有ロックのように区別せず、エンティティに\(\text{lock}\)以外にアクションを実行するための操作としてあつかう。 また、\(\text{lock}\)していないエンティティを\(\text{unlock}\)したり、\(\text{lock}\)されたエンティティに重ねて\(\text{lock}\)をかけることはない。 \(a_i=\text{lock}\)であれば\(i-1\)までに\(T\)が\(e_i\)をロックしておらず、また\(a_i\neq \text{lock}\)であればステップ\(i\)まで\({\rm \boldsymbol{T}}\)が\(e_i\)を\(\text{lock}\)しているなら、\({\rm \boldsymbol{T}}\)はwell-formedである。

\({\rm \boldsymbol{T}}_1, \dots ,{\rm \boldsymbol{T}}_n\)のアクションを並べた系列をスケジュール\({\rm \boldsymbol{S}}((T_i, a_i, e_i))^m_{i=1}\)とよぶ。 すべての\(k\)について、\({\rm \boldsymbol{S}}(k)=(T, a, e)\)かつ、\(k\)において\({\rm \boldsymbol{T}}\)だけが\(e\)をロックしているとき、\({\rm \boldsymbol{S}}\)はlegalである。

ここまでの用語で主題の定理を厳密にいいかえると、任意のトランザクションの集合の要素\(T\)がwell-formedかつ一度ロックを解放したら新しいロックを獲得しないとき、\(T\)の任意のlegalな\({\rm \boldsymbol{S}}\)には一貫性がある。 以下では、証明の概略をのべる。

\({\rm \boldsymbol{S}}\)の依存関係\(\textit{DEP}({\rm \boldsymbol{S}})\)を、\({\rm \boldsymbol{S}} = (\dots , (T_1, a_i,e),\dots ,(T_2, a_j, e) ,\dots)\)であり\(i<k<j\)かつ\(e_k=e\)をみたす\(k\)がない\((T_1, e, T_2)\)の集合で定義する。 依存関係にもとづくトランザクションの順序関係\(<\)を、ある\(e\)について\((T_i, e, T_j)\)かつその時にかぎり、\(T_i<T_j\)と定義し、これを全順序\(< <\)に拡張することをめざす。

空でないwell-formedな\(T_i\)には、\(T_i\)の\(\text{unlock}\)が出現する\({\rm \boldsymbol{S}}\)上での最初のステップの番号\(\text{SHRINK(}{\rm \boldsymbol{T}}_i\text{)}\)がある。 このとき、任意のトランザクションとエンティティについて、\((T_1, e, T_2)\in \textit{DEP}({\rm \boldsymbol{S}})\)であれば\(\text{SHRINK(}{\rm \boldsymbol{T}}_1\text{)}\)は\(\text{SHRINK(}{\rm \boldsymbol{T}}_2\text{)}\)よりも小さくなる。 なぜなら、\((T_1, e, T_2)\in \textit{DEP}({\rm \boldsymbol{S}})\)であれば定義から\({\rm \boldsymbol{S}} = (\dots , (T_1, a_i,e),\dots ,(T_2, a_j, e) ,\dots)\)で\(i, j\)の間に\(e_k = e\)となる\(k\)のない\(i, j\)があり、\({\rm \boldsymbol{S}}\)はlegalなので\(i\)までに\({\rm \boldsymbol{T}}_1\)だけがロックし、\(T_2\)がwell formedであるため\(j\)までに\({\rm \boldsymbol{T}}_2\)だけが\(e\)をロックするため、\(a_i\)が\(\text{unlock}\)で\(a_j\)が\(\text{lock}\)になるからである。 よって、\({\rm \boldsymbol{T}}_1<{\rm \boldsymbol{T}}_2\)であれば\(\text{SHRINK(}{\rm \boldsymbol{T}}_1\text{)}\)は\(\text{SHRINK(}{\rm \boldsymbol{T}}_2\text{)}\)よりも小さい。 よって、\(<\)を全順序\(< <\)に拡張できる。

最後に、\({\rm \boldsymbol{S}}\)のトランザクションの関係が\({\rm \boldsymbol{T}}_1 < < {\rm \boldsymbol{T}}_2 \dots < < {\rm \boldsymbol{T}}_n\)であるとき\(n\)についての帰納法で\({\rm \boldsymbol{S}}\)が\({\rm \boldsymbol{T}}_1,\dots,{\rm \boldsymbol{T}}_n\)と等価であることを示す。これは直列的な実行系列と\({\rm \boldsymbol{S}}\)が等価であり、一貫性のあるスケジュールである。 \(n=1\)のときは明らか。 \({\rm \boldsymbol{S}}\)は\({\rm \boldsymbol{S}}'={\rm \boldsymbol{T}}_1((T_i, a_i, e_i)\in {\rm \boldsymbol{S}} \mid T_i \neq T_1)^m_{i=1}\) と等価であり、仮定より \(((T_i, a_i, e_i)\in {\rm \boldsymbol{S}} \mid T_i \neq T_1)^m_{i=1}\)は\({\rm \boldsymbol{T}}_2,\dots ,{\rm \boldsymbol{T}}_n\)と等しい。

論文をこちらからダウンロードできます。