###### tags: `TransactionalInformationSystems`

# 4章-2 ロックスケジューラ

実装の詳細には踏み込まない(ロックテーブルやトランザクションの粒度など)

## ロックスケジューラの概要

トランザクションはデータアイテムへの操作を行いたいとき、そのアイテムへのロックを要求する。アイテムが既に他のトランザクションによってロックされていたとき、ロック競合が発生しているとスケジューラは判断し、トランザクションにロック待機を命じてブロックする。ロックが解放されたタイミングで待機中のトランザクションを探して再開する。

ロックにはread lockとwrite lockの2種類があり、共存しうるのはread lock同士のみ。つまりロックが既にかかっていて別のトランザクションがロックを要求する際、両方がread lockである場合のみ許可される。ロックは$rl(x),wl(x)$,ロックの解放は$ru(x),wu(x)$のように表記する。ロックスケジューラは与えられたトランザクションにこれらの操作を加えて拡張する。

少なくとも一方が$wl$で同じデータアイテムに対する別トランザクションによるロック$pl(x),ql(x)$を競合するロック(in conflict)と呼ぶことにする。

ロックスケジューリングアルゴリズムは以下の手順で進む。ステップ$o_i(x)\ (o \in \{r,w\})$が到着したとき、

1. 他のトランザクションが$x$にロックをかけていなかったなら、ロック$ol_i(x)$をセットする。
2. 他のトランザクションが$x$にロックをかけていたら、ロックが競合するかを調べる。
1. 競合するロックが無いなら$ol_i(x)$をセットする。(実際にはロックをかけ直すのではなく、ロックテーブルに$t_i$がロックした旨を記録するのみ)
2. 競合するロックがあったらトランザクション$t_i$をブロックする。

ロックの制御に関して、スケジューラが生み出すスケジュール$s$に満たしてほしい最低限の規則は以下の感じになる。ただし、対象とするトランザクションは$s$内に全体が含まれるものに限る。

---

### ロック規則

well-formed lockingの条件

- LR1：$t_i$が$r_i(x)[w_i(x)]$を含むとき、$s$のそれ以前の時点で$rl_i(x)[wl_i(x)]$を含み、それ以後の時点で$ru_i(x)[wu_i(x)]$を含む。
- LR2：$t_i$がアクセスするデータアイテム$x$の全てについて、スケジュール$s$に含まれる$rl_i(x)$と$wl_i(x)$はそれぞれ高々一回。
- LR3：$ru_i(.),wu_i(.)$はトランザクション内で高々一回。

要は、データ操作するなら前後にロックの取得と解放を挟んでいること、ロックの取得と解放は不必要に行わないこと、という常識的な条件。

LR1-LR3は競合するロックに関して何も述べていないことに注意。ロックがロックたる意味を持たせるためにはLR4も必要となる。

- LR4：$x$に関するロックがある時点で$t_i$と$t_j (i\neq j)$に保持されている場合、それらのロックは競合しない。

---

データ操作、終了操作に加えてロック操作も加わったので表記を整理し、$DT(s)$で$s$の$r,w,c,a$のみへの射影を表すことにする。(ロックを除いたData&Termination operationsの意味合い)

## 2相ロックプロトコル

---

### 定義：2相ロック(2PL)

スケジューラ(ロックプロトコル)が2相であるとは、任意の出力$s$と$t_i\in trans(s)$に対して、最初のロック解放ステップ以降にロック取得ステップが出現しないこととする。

これを満たすスケジューラを2PLスケジューラと呼ぶ。

---

つまり、1トランザクションの中でロックを取得するフェーズとロックを開放するフェーズが厳密に区別されているスケジューラを指す。

2PLスケジューラでは「ロック変換」(read lockを後にwrite lockに昇格する操作)も許される。この場合ロックの解放はLIFO、つまりwrite lock→read lockの順に行う必要がある。

---

### 補題4.1

2PLスケジューラの出力を$s$とする。各トランザクション$t_i\in commit(DT(s))$に対し以下が成り立つ。

1. $o_i(x)\in CP(DT(s)) \ (o\in \{r,w\})$ に対し、$ol_i(x)<o_i(x)< ou_i(x)$ が出現する。
2. 他のトランザクション$t_j$と衝突するステップ$p_i(x),q_j(x)$が$CP(DT(s))$に存在するとき、$pu_i(x)<ql_j(x)$または$qu_j(x)<pl_i(x)$が成り立つ。
3. $p_i(x), q_i(y)$が$CP(DT(s))$に出現するとき、$pl_i(x)<qu_i(y)$が成り立つ。

つまり、データ操作の前後にはロックの取得と解放があり、衝突するステップ間ではロック期間が被らず、ロックの取得フェーズと解放フェーズは区別される。
1と2はLR1-4によるもので、3は2相ロックの定義によるもの。

---

### 補題4.2

2PLスケジューラの出力$s$に対し、$CP(DT(s))$の衝突グラフを$G$とする。$G$は以下を満たす。

1. 辺$(t_i,t_j)$があるとき、あるデータアイテム$x$に対して衝突するデータ操作$p_i(x),q_j(x)$があり、$pu_i(x)<ql_j(x)$となる。
2. $(t_1,t_2,\ldots,t_n)$が$G$におけるパスのとき、任意のデータアイテム操作$p_1(x),q_n(y)$に対して$pu_1(x)<ql_n(y)$となる。
3. $G$は閉路を持たない。

#### 証明

1.

辺$(t_i,t_j)$があるとき、衝突するステップ$p_i(x)<q_j(x)$がある。ここから$pl_i(x)<p_i(x)<pu_i(x), ql_j(x)<q_j(x)<qu_j(x)$。補題4.1(2)からさらに (a)$pu_i(x)<ql_j(x)$ か (b)$qu_j(x)<pl_i(x)$ が成り立つ。 (b)を仮定すると$q_j(x)<p_i(x)$が導かれて矛盾するので、(a)が成り立つので示された。

2.

$n$に関する帰納法で示す。$n=1$のときは(1)で示されている。$n=k$で帰納法仮定を置き、長さ$k+1$の$G$におけるパス$(t_1,\ldots,t_{k+1})$を考える。仮定から任意のデータアイテム$x$と$z$で$pu_1(x)<ol_k(z)$。
ここで辺$(t_k,t_{k+1})$があることから、(1)より任意のアイテム$y$について$vu_k(y)<ql_{k+1}(y)$。補題4.1(3)より同じトランザクション$t_k$内では$ol_k(z)<vu_k(y)$なので、これらを全て合わせて$pu_1(x)<ql_{k+1}(y)$を得る。

3.

閉路$t_1\rightarrow \cdots \rightarrow t_1$を持つと仮定すると、(2)より$pu_1(x)<ql_1(y)$となって2相ロックの性質に矛盾する。$\square$

---

補題4.1(3)の2相ロックの性質が$G$に閉路を作らない作用をしているため、CSR安全になる。

### 定理4.1

2相ロックスケジューラはCSR安全、すなわち$Gen(2PL)\subset CSR$。

---

ただし、2PLスケジューラはCSRに属するパターンを全て出力できるわけではないことに注意。

2PLの出力であることはCSRであるための十分条件だが必要条件ではない。

もっと言えば2PLはorder preserving conflict serializableですらある。

### 定理4.2

$Gen(2PL)\subset OCSR$

---

### デッドロックへの対応

複数のデータアイテムをロックするトランザクション同士が、お互いのロックの解放を待機して動作が進まなくなる状態。ナイーブな2PLスケジューラではデッドロックを防げない。例えば$s=r_1(x)w_2(y)w_2(x)c_2w_1(y)c_1$を入力された場合。

ロック変換も同様のデッドロックを引き起こしうる。

スケジューラがデッドロックを引き起こすスケジュールを出力する場合、それを検出して修正する段階が必要になる。

---

一つ目の方法はwaits-for graph(WFG)/待機グラフを使う方法。辺$(t_i,t_j)$が、「$t_i$が$t_j$の解放を待っている」ことを指すように構築する。WFGの閉路を検出すればそれがデッドロックを示している。

#### WFGの閉路検出の頻度は？

- 連続検出：ロック取得要求の却下が起こるたび(=トランザクションがブロックされるたび)に閉路検出を行う。
- 周期検出：決められた時間ごとに閉路検出を行う。

このように閉路を検出するたびに、閉路の中から少なくとも1つのトランザクションを選んでabortし、最初からやり直す必要がある。

#### abortするトランザクションの選び方は？

1. Last blocked: 直近にブロックされたトランザクション。
2. Random: 閉路の中からランダムに選んだトランザクション。
3. Youngest: 開始時刻が直近のトランザクション。
4. Minimum locks: ロックの数が最少のトランザクション。
5. Minimum work: リソースの消費量が最小のトランザクション。
6. Most cycles: abortすることで消せる閉路の数が最大のトランザクション。
7. Most edges: abortすることで除去できる辺の数が最大のトランザクション。

youngest, minimum locks, minimum workはabortによるリソースの無駄を最小限にするためのヒューリスティクスだが、毎回abortするトランザクションに同一のものが選ばれやすく、そのトランザクションがいつまでたっても終わらないという問題(starvation/飢餓)が起こりやすいので考慮が必要。

---

二つ目の方法はdeadlock prevension(デッドロック予防)で、循環待機をそもそも起こさないために可能な限りトランザクションをブロックしない。

#### 制限のかけ方のバリエーション

1. Wait-die: $t_i$からのロック要求が$t_j$と競合する場合、$t_i$が$t_j$よりも先に開始していたなら要求をブロックする。そうでないなら$t_i$は最初からやり直す。(=トランザクションは自分より若いものからのみブロックされうる)
2. Wound-wait: $t_i$からのロック要求が$t_j$と競合する場合、$t_i$が$t_j$よりも先に開始していたなら$t_j$を最初からやり直す。そうでないなら$t_i$がブロックされる。(=トランザクションは自分より古いものからのみブロックされ得、自分より若く競合するものをkillできる)
3. Immediate restart: $t_i$からのロック要求が$t_j$と競合する場合、$t_i$を最初からやり直す。(=トランザクションはブロックされない)
4. Running priority: $t_i$からのロック要求が$t_j$と競合する場合、$t_j$が既に他の競合に関して待機していたなら、$t_j$を最初からやり直し$t_i$の要求を許可する。そうでないなら$t_i$をブロックする。(=アクティブなトランザクションの方がブロックされているトランザクションよりも優先度が高い)

最初からやり直されるトランザクションがデッドロックに巻き込まれているとは限らないため、偽陰性を減らすことを重視する保守的な方法。

---

三つ目の方法はタイムアウト。各トランザクションがアクティベートされてから一定時間経つとデッドロックと判断してabortする。

---

## 2相ロックのバリアント

### 定義：保守的な2PL

保守的な2PL(Conservative 2PL, C2PL)のもとでは、任意のトランザクションにおいて、最初のread/writeステップの前に必要なロックの取得が全て行われる。

2CPLの利点はデッドロックを起こさないことだが、トランザクションの実行前に読み込むデータアイテムと書き込むデータアイテムを全て宣言する必要があり、プログラムとして利用するための制限が大きい。

### 定義：厳密な2PL

厳密な2PL(Strict 2PL, S2PL)のもとでは、任意のトランザクションにおいて、獲得したwrite lockを終了まで保持し続ける。

S2PLは回復の観点でも追加の特性を持つ。

### 定義：強い2PL

強い2PL(Strong 2PL, SS2PL)のもとでは、任意のトランザクションにおいて、獲得したロックを終了まで保持し続ける (read lockかwrite lockかは問わない)。

---

### 定理4.3

$Gen(SS2PL) \subset Gen(S2PL) \subset Gen(2PL)$

### 定理4.4

$Gen(SS2PL) \subset COCSR$

この性質は分散システムの文脈で役に立つ。

### ロックの順序共有

2PLを緩和し、もう少し幅広いスケジュールを出力できるようにすることを目指す。

ここまでのロックは共有ロックと排他ロックの2つのモードしかなかったが、新たな種類のロックモードを考える。このモードは、「2つのロックがデータ操作の順番と同じ順に要求されているならば共有を許可する」というもの。このモードをordered sharing(順序共有)と呼ぶ。

このモードにおけるロック間の順序を矢印で表記する。つまり、$pl_i(x)<_s ql_j(x), p_i(x)<_s q_j(x)$ならば$pl_i(x)\rightarrow ql_j(x)$と書く。

排他ロックの部分を順序共有に置き換えることで、ロック共有テーブルが8種類生じ得る。

順序共有ロックの定義を改めて定式化する。

---

#### ロック獲得規則

- OS1: 2つのロックの順序共有$pl_i(x)\rightarrow ql_j(x) (i\neq j)$が許可されているとき、$t_i$が$pl_i(x)$を$ql_j(x)$の前に行っているなら、$p_i(x)$も$q_j(x)$の前に行われなければならない。

これだけだとまだCSRは保証できない。ロックの解放についてもまた規則を定める必要がある。$pl_i(x)\rightarrow ql_j(x)$の関係があって$t_i$がまだ一つもロックを解放していないとき、$t_j$は$t_i$に「依存している」。そのような$t_i$が存在するとき、$t_j$は「保留されている」。

- OS2: トランザクションが保留されているとき、ロックを解放することができない。

---

これらを踏まえて、ロックスケジューラを完成するまでには以下の過程を踏むことになる。

1. ロック規則LR1-LR4の適用
2. 順序共有規則OR1-OR2の適用
3. 2相ロックの適用
4. 採用するロック共有テーブルを決める(どのread/write lockを順序共有にするか)

排他ロックを全て順序共有ロックで置き換えた2PLをO2PLとする。

### 補題4.3(OS1から従う補題)

$x$が$pl_i(x)\rightarrow ql_j(x)$で順序共有ロックされていて$pl_i(x)<ql_j(x)$のとき、$p_i(x)<q_j(x)$である。

### 補題4.4(OS2から従う補題)

$pl_i(x)\rightarrow ql_j(x)$かつ$pl_i(x)<ql_j(x)$のとき、$t_i$のロック解放操作で、$t_j$の全ロック解放操作よりも先に行われるものが存在する。

### 補題4.5

$pl_i(x)$と$ql_j(x)$が競合していて順序共有が許されておらず$pl_i(x)<ql_j(x)$のとき、$pu_i(x)<ql_j(x)$となる。

つまり、順序共有が許可されないケースで$t_i$が$t_j$よりも先にロックしていて競合が発生した時、$t_j$がロックする前に$t_i$が解放している必要がある。

これらの定義により、スケジュールの衝突グラフを見ると、各衝突辺$(t,t')$について、$t'$の全ての解放操作の前に少なくとも一つ$t$の解放操作がある(そのロックが排他であると順序共有であるとに関わらず)ため、衝突グラフに閉路が存在しない。よってCSRとなる。

### 定理4.5

8種類のロックテーブルを$LT_i (1\leq i\leq 8)$とし、それらにより作られる履歴を$Gen(LT_i)$と表記する。このとき$Gen(LT_i)\subseteq CSR$となる。

---

O2PLは全ての排他ロックを順序共有ロックで置き換えるため、OCSRですらある。

### 定理4.6

$Gen(O2PL) \subseteq OCSR$

---

逆もまた然りで、OCSRに属するスケジュールをO2PLは全て生成できる。

### 定理4.7

$OCSR \subseteq Gen(O2PL)$ すなわち $Gen(O2PL)=OCSR$

ただ、O2PLは純粋なロックスケジューラではない(データアクセスの順序を知るために追加の実装と計算オーバヘッドが発生し、効率的でない)ためあまり実用的ではない

---

## 利他的なロック

2相ロックでは、非常に長く多くのリソースを占有するトランザクションがあるときに深刻なパフォーマンスの問題を引き起こす。対処法として、一応3章で導入したような相対的なserializabilityを考えることもできるが、これはアプリケーションの側でトランザクションの特性を指定しなければならない(システム側の保証だけで話が済まなくなる)ため、他のアプローチを探る。

対処のためのアイディアは、もう操作し終えたデータアイテムは他のトランザクションに譲れるということ。

このアイディアに基づいた2PLの拡張を利他的ロック(altruistic locking, AL)と呼ぶ。
基本は2PLのようにロックの取得フェーズと解放フェーズを持つが、特定の条件の下で、衝突するトランザクションが同じデータアイテムへのロックを同時に保持することが許される。

これを実現するため、lockとunlockの他にdonate(贈与)というアクセス制御操作を追加する。ロックしているがもう使わないデータアイテムをスケジューラに知らせ、他のトランザクションに使ってもらう。

donateを$d_i(x)$のように表記する。

### 利他ロック規則

- AL1: 贈与したアイテムは二度と読み書きできない。つまり、$d_i(x)$と$o_i(x)\ (o\in \{r,w\})$があるとき、$o_i(x)<d_i(x)$
- AL2: 贈与したアイテムは最終的にロック解放される。つまり、$o_i(x)$の後に$d_i(x)$が続くとき、$ou_i(x)$もあって$d_i(x)<_s ou_i(x)$である。
- AL3: データを贈与した場合のみ例外的に同一のデータアイテムへの競合するロックが許される。つまり、$o_i(x),p_j(x)$が競合して$o_i(x)<_s p_j(x)$であったとき、$ou_i(x)<_s pl_j(x)$か、あるいは$d_i(x)$も$s$に出現して$d_i(x)<_s pl_j(x)$が成り立つ。

$t_j$が$t_i$によって贈与されたアイテムをロックしていて$t_i$がまだそれを解放していないとき、$t_j$は$t_i$の後続(in the wake of)ということにする。

$t_j$内の単一のステップについては後続、$t_j$の全てのステップが$t_i$の後続なら$t_j$は「完全に$t_i$の後続である」と称する。

また、トランザクション$t_j$は以下の条件を満たすとき$t_i$に「恩義がある」(indebted)と称する。
$o_i(x),d_i(x),p_j(x)\in op(s)$ が存在し、
- $p_j(x)$が$t_i$の後続であり、かつ
- $o_i(x)$と$p_j(x)$が衝突しているか、
- ある操作$q_k(x)$で$d_i(x)<_s q_k(x) <_s p_j(x)$を満たすものが存在して$o_i(x)$と$p_j(x)$の両方と衝突している。

デッドロックを引き起こさないため、一度$t_i$に贈与されたアイテムを利用し、$t_i$と衝突する操作を実行したトランザクションは完全に$t_i$の後続である必要がある。また、間接的な衝突を引き起こす第3のトランザクションもconflict serializabilityに関わってくるので、恩義の定義の方が重要になる。これにもとづいて新たな利他ロック規則を定義する。

- AL4: トランザクション$t_j$が$t_i$に恩義があるとき、$t_i$がロックの解放を始めるまで、$t_j$は完全に$t_i$の後続でなければならない。つまり、任意の操作$p_j(x)$に対して、$p_j(x)$が$t_i$の後続であるか、あるロック解放$ou_i(y)$が存在して$ou_i(y)<_s p_j(x)$とならなければならない。

---

2PLに加え、AL1-4を満たしたスケジューラをALと表記する。AL1-4によって定義された贈与操作$d$によって2PLを拡張しただけなので、従来の2PLによるスケジュールは全て受理できる。

### 定理4.8

$Gen(2PL) \subset Gen(AL)$

#### 証明

ALに含まれるが2PLに含まれないのは$s=r_1(x)w_2(x)c_2w_3(y)c_3r_1(y)c_1$。$t_2$は$x$について$t_1$と衝突するので2PLは$s$を生成できないが、ALなら、$t_1$が$x$を贈与することで$t_2$が$x$に対する書き込みを実行できるため$s$を生成できる。$\square$

ただしALもCSRを全て生成できるわけではない。

### 定理4.9

$Gen(AL)\subset CSR$

---

## 非2相のロックプロトコル

2相性を用いず、またデッドロックも引き起こさないロックプロトコルを考えていく。ただし、限定的なアクセスパターンにのみ適しており、一般的な状況ではパフォーマンスが低い。

データアイテムへのアクセスパターンが木構造を辿る構造をしている状況を想定することで、ロックを必ずしも2相にする必要がなくなる。

### Write-Only Tree Locking(書き込み限定ツリーロック)

読み込み操作が存在しないときは特にシンプルなモデルになる。データアイテムを木構造で階層化し、データアクセスが木をトップダウンで下るパターンに限定されている場合を考える。(現実にはB+木へのアクセスパターンが似ている)

書き込み限定ツリーロックプロトコル(Write-only tree locking, WTL)はLR1-LR4に加えて以下のルールを要求する。

- WTL1: 根以外の任意のノード$x$について、トランザクション$t_i$が$x$の親$y$へのwrite lockを保持している場合のみ$wl_i(x)$をセットすることができる。
- WTL2: $wu_i(x)$の後には二度と$wl_i(x)$が許されない。

### 補題4.6

$x$をロックするのが$t_i$が$t_j$の先であるとき、$x$の全ての子孫$v$をロックする順番も$t_i$が先である。

#### 証明

$x$から$v$へのパスを$(x,z_1,\ldots, z_n, v)$とする。
$x$をロックするのが$t_i$が$t_j$の先で、どちらも$v$をロックするとき、$wl_i(x)$の存在から$wl_j(x)$がセットできず、WTL1より$wl_i(z_1)<wu_i(x)<wl_j(x)<wl_j(z_1)$となる。これがパスの全ての辺で成り立つ。$\square$

これをもとに

### 定理4.10

$Gen(WTL)\subseteq CSR$

#### 証明

WTL出力の衝突グラフの辺$(t_i,t_j)$とする。このとき、衝突する操作$w_i(x)$と$w_j(x)$が存在する。WTLの規則から$t_i$は$t_j$が$x$をロックする前に$x$のロックを解放する。補題4.6と、任意のトランザクションは根をロックすることから、$t_i$は$t_j$よりも先に木の根をロックする。そうすると、$t_i$が根のロックを解放するのも$t_j$がロック取得するよりも先になる。したがって、$G$上で辺が存在するとき、木の根のロックとその解放にも辺と同じ順番が存在することになり、したがって$G$には閉路が存在しない。$\square$

しかもデッドロックを引き起こさない。

### 定理4.11

WTLはデッドロックを起こさない。

#### 証明

$t_i$が根のロック取得を待機しているとき、他のロックを取得することができない。待っているのが$t_j$によるロックの解放だったとき、$t_j$は$t_i$によるロック取得の前にロックを解放する。帰納的に考えれば、待機グラフに閉路が存在すると仮定すると「$t_i$がロック取得する前に$t_i$がロック解放する」となり矛盾。よって待機グラフに閉路が存在しない。$\square$

木の中の一部のアイテムにアクセスするだけでも、根から逐一ロックを辿っていかなければならないのでパフォーマンスは悪化する。一応、木構造以外のアクセスパターンにも適用はできるが、同じ問題は付いて回る。

### Read/Write Tree Locking(読み書き可能ツリーロック)

読み込み操作も可能にしてツリーロックを一般化する。

WTLによるスケジュールの特徴は、全てのトランザクションは「親をロック、子をロック、親を解放」というように親から子へのパターンをなぞる必要があり、他のトランザクションを追い越すことがないというもの。read lockを共有ロックにし、単純に追い越しを許可してしまうとCSRにならないため、適切な規則が必要になる

アイディアは、読み込み操作の周辺(pitfallと呼ぶ)でのみ2相プロトコルを適用するもの。

トランザクション$t$で読み込むデータアイテムと書き込むデータアイテムをそれぞれ$RS(t), WS(t)$と表記する。木の中で$RS(t)$に対応するノードがなす連結成分を$C_1,...,C_m$とする。$t$のpitfallは以下の形をした集合。

$$C_i\cup \{x\in WS(t)\mid xはy\in C_i の子または親\} \ (1\leq i\leq m)$$

WTLに読み込みに関する次の規則を追加する。

- RWTL1: pitfall内ではトランザクションは2相ロックを行う。すなわち、pitfall内のアイテムの解放を始めてよいのは、全アイテムの取得を終えてから。

RWTLの安全性を示していく。

### 補題4.7

$T$をデータベースツリー、$t$をRWTLの規則に従う$T$上のトランザクションとする。$V\subseteq RS(t)\cup WS(t)$を$T$の連結な部分木とする。$\Pi_V(t)$もまたRWTLの規則に従う。

### 補題4.8

トランザクション$t$が$V\subseteq RS(t)\cup WS(t)$上で2相であるとする。任意の$W\subseteq RS(t)\cup WS(t)$に対し$\Pi_W(t)$は$V\cup W$上で2相である。

### 定理4.8

$Gen(RWTL)\subseteq CSR$

これも衝突グラフが閉路を持たないため。

RWTLはさらに一般化することもできる。RWTL1規則に類するものとしてDAG1を考えるとDAGロックプロトコルになる。

- DAG1: トランザクションが$x$をロックするのが許されるのは、$x$の祖先の半数以上をロックできている場合のみ。

---

### ロックプロトコルの幾何学的な解釈

ここではトランザクションが2つのみの状況を考える。

2次元ユークリッド平面を考え、x軸、y軸に等間隔で点をとり、それらの点列を各トランザクションのステップ列と考える。
すると、スケジュールは単調増加なグラフとなる。衝突するステップ同士は平面上の点となっているが、スケジュールの左右にこれら衝突するステップが分かれて存在すると、実行順が逆=衝突グラフに閉路が存在してしまうためCSRにならない。

#### 定理4.13

2つのトランザクション$t_1,t_2$からなるスケジュール$s$がCSRに属する$\Leftrightarrow s$を表す曲線がどの2つの衝突する点も分割しない。

ロックの取得・解放操作を追加すると、回避する必要があるのは衝突する点でなく長方形領域に一般化される。(競合するロックの取得/解放が各辺の始点/終点に対応)

#### 定理4.14

ロックの取得/解放操作を加えた2つのトランザクション$t_1,t_2$からなるスケジュール$s$が$DT(s)\in CSR \Longleftrightarrow s$を表す曲線が衝突する長方形領域を(1つの側に)分割しない。

#### これらの性質から得られる観察

衝突領域を回避した曲線は、ロックの取得と解放をきちんと交互に行えているという意味でlegalだが、衝突点を同じ側に置けていないのでCSRでない。ただ、衝突領域を全て連結にできれば、衝突領域を回避することそれ自体が衝突点を同じ側に置く=CSRにすることにつながるため、コンパイル時にCSRスケジューリングができる可能性を秘める。