###### tags: `TransactionalInformationSystems`

# 8章 リレーショナルデータベースにおけるConcurrency Control

## 概要

本章では、セマンティックな情報が豊富に使える状況での同時実行制御について考える。構文(シンタックス)的には非可換として扱われる操作同士でも、それらの操作の意味(セマンティクス)が与えられていれば、それを活かして可換にできるケースがある＝より並列な実行が可能になる。

特に今回着目するのは、RDBの基礎となっているリレーショナルモデルおよびSQLである。この状況下でのスケジュールは階層的なオブジェクトモデルになる。リレーションや集合への操作はレコードレベルの操作から構成され、さらにレコードレベルの操作はページレベルの操作から構成される。

スケジュールの構造は平坦なものに限定して考えていく。つまり、2層スケジュールかつ$L_1$の操作はあらかじめ孤立している。より一般的なモデルへの拡張は6章、7章の内容をそのまま適用すればよい。

行うアプローチは3つ：
1. 述語指向のCC。ロックの競合を、SQL文WHERE句の条件一致から判断する。
2. SQLのupdate文を基礎的な構成要素とするトランザクションにおける意味論的な同値性のクラスを考える。
3. トランザクションを、静的解析によって許されうる限り複数要素に分割して独立にスケジュールする。

**注意** 本書が執筆された時点での最先端は7章で紹介されたレコードレベルロックであり、本章の内容はあくまで付加的な題材、理論的な興味を出ない。(2022年現在ではどうだろうか、読了したら現在のオープンソースDBを調べたい)

## 述語指向のConcurrency Control

リレーショナルモデルの概念をある程度定義しておく。リレーション(テーブル)は名前$R$と属性集合$A_1,...,A_n$からなるスキーマ(テーブルヘッダ)を持ち、$R=(A_1,...,A_n)$と表記する。各属性にドメイン集合$dom(A_i)$が割り当てられており、リレーションスキーマのインスタンス(これをリレーションとも呼ぶ)$r$は$r\subseteq dom(A_1) \times \cdots \times dom(A_n)$を満たす部分集合として定義される。リレーションの元はタプルと呼ばれる。リレーションスキーマにはキー制約や関数従属性が付加されることもある。

リレーションに対するトランザクション制御を考えると、まず思いつくのはタプル単位(レコード単位)でのロックになる。ただこれには、現在リレーションに存在しないタプルに対してはロックが働かず、これが問題を引き起こしうる。

これに対処する方法として、レコード単位ではなく、述語の条件を満たすレコードを(それが実際のリレーション内に存在しなくても)全てロックする述語指向のロックを考える。

---

$C$をリレーション$R$の属性に対する条件の集合として、各条件は$A_i=a$もしくは$A_i\neq a \ (1\leq i\leq n$ かつ$a\in dom(A_i))$という形であるとする。単純のため、相互に排他な条件は含まないものとする。条件集合$C$は、それを満たすようなタプルの集合を引き起こす：

$$H(C) = \{\mu \in dom(A_1) \times \cdots \times dom(A_n) \mid \mu \textrm{ satisfies } C\}$$

$H(C)$はベクトル空間であることから超平面とも呼ばれる。

この$H(C)$に相当するタプルを全てロックするのが述語指向のロックであり、そのようなタプルが実際のリレーションインスタンスに存在しようとしなかろうと一律に制御を適用することになる。二つのロックモード$m_t, m_{t'}$が競合しないための条件は

- $t=t'$ or
- $m_t, m_{t'}$のどちらも共有ロック or
- $H(C_t)\cap H(C_{t'}) = \emptyset$

となる。

### スケジューラの問題

述語指向のロックでは、従来のロックとは異なる問題が発生する。

まず、複数のロックと同時に競合しうるという問題がある。したがって、ロック競合が原因で待機していたトランザクションを再開するときも、単純に再開するだけとはいかず、他のロックとも競合していないかのチェックが必要になる。

次に、$H(C_t)\cap H(C_{t'}) = \emptyset$ の判定問題はSAT問題、すなわちNP完全であり、一般には効率が悪い。ただし、インデックスの制御においてはこの問題が表面化せず、効率よく述語ロックを扱える(9章)。

### Precision Locking

充足可能性テストをなるべくやりたくない、軽量化したいという動機でprecision lockingというバリアントもある。全てのロックがテストを経ずにいったん許可されるが、タプルへの読み書きを行った時点でタプルと述語ロックとの競合検査が発生し、競合した時点でその操作が拒否される。書き込みはもはや述語指向でなくタプル単位になってしまっているので、書き込みを行う文の前には、自動的に対象範囲を述語ロックするための読み込み文が挿入される必要がある。

## IDMトランザクションの制御

この節では、平坦なトランザクションかつ、全ての操作がInsert, Update, Deleteのいずれかであるようなモデルにおける同時実行制御を考える。これはSQLをモデル化したものであり、操作をInsert, Delete, Modifyと言い換えて略し「IDMトランザクションモデル」と呼ばれる。

### シンタックス

$R$をリレーションスキーマとする。シンタックスは以下の通り。

- 挿入$i_R(C)$：$C$を満たすタプルを挿入する。ここで$C$は$R$の完全なタプルを指定できる条件とする。
- 削除$d_R(C)$：$C$を満たすタプル群を削除する。
- 編集$m_R(C_1;C_2)$：$C_1$を満たすタプル群を$C_2$に編集する。

### セマンティクス

各更新操作のセマンティクスは*effect*(影響)で定義する。$r$をスキーマ$R$上のリレーションとする。

- $eff[i_R(C)](r) := r\cup \{C\}$
- $eff[d_R(C)](r) := r- H(C)$
- $eff[m_R(C_1;C_2)](r) := (r-H(C_1))\cup \{m_R(C_1;C_2)(\mu)\mid \mu\in H(C_1)\cap r\})$

ただし、ここで$m_R(C_1;C_2)(\mu)$は、タプル$\mu_2 \in H(C_2)$で

$$\mu_2(A) = \begin{cases} \mu_1(A) & (C_1|_A=C_2|_A) \\ a & (\textrm{"A=a"}\in C_2)\end{cases}$$

を満たすものとする。

これらをもってIDMトランザクションをフォーマルに定義する。最終状態同値性もページモデルトランザクションとの類推で定義できる。

---

### 定義：IDMトランザクション

DBスキーマ$D$に対するIDMトランザクションとは、$D$に対する上記の更新操作の有限列である。

IDMトランザクション$t=u_1 ...u_m$の影響を
$$eff(t) := eff[u_1]\circ \cdots \circ eff[u_m]$$
で定義する。

### 定義：トランザクション間の同値性

$$t \approx t' \Longleftrightarrow eff(t)=eff(t')$$

与えられたIDMトランザクションに対する同値性の検査は多項式時間で可能。

### 定義：Final State Serializability

$s$がfinal state serializable $\Longleftrightarrow$ serialな履歴$s'$が存在して$s\approx s'$

final state serializableな履歴のクラスを$FSR_{IDM}$と表記する。

---

ただしFSRの判定はやはりNP完全であり、実用的にはCSRに類するものが必要になる。

そのため、まずIDMトランザクションでの可換性を定義する。

条件集合$C_1,C_2,C_3,C_4$に対し以下の同値性が成り立つことから、これら隣接する操作を可換とする。

1. $i(C_1)i(C_2) \approx i(C_2)i(C_1)$
2. $d(C_1)d(C_2) \approx d(C_2)d(C_1)$
3. $d(C_1)i(C_2) \approx i(C_2)d(C_1) \textrm{ if } C_1 \neq C_2$
4. $m(C_1;C_2)m(C_3;C_4) \approx m(C_3;C_4)m(C_1;C_2) \textrm{ if } C_3 \neq C_1,C_2 \textrm{ and } C_1 \neq C_4$
5. $m(C_1;C_2)i(C_3) \approx i(C_3)m(C_1;C_2) \textrm{ if } C_1 \neq C_3$
6. $m(C_1;C_2)d(C_3) \approx d(C_3)m(C_1;C_2) \textrm{ if } C_3 \neq C_1,C_2$

これらの規則による関係を$\leftrightarrow$で表記し、その反射及び推移閉包を$\leftrightarrow^*$で表記する。$t\leftrightarrow^* t'$のとき明らかに$t\approx t'$であるが、その逆は必ずしも言えない。すなわち、可換性に基づいた削減可能性のクラス(CSR)は影響の等価性のクラス(FSR)よりも厳しい正当性基準である。

---

### 定義：Conflict Serializability

$s$がconflict serializable $\Longleftrightarrow$ serialな履歴$s'$が存在して$s\leftrightarrow^* s'$

conflict serializableな履歴のクラスを$CSR_{IDM}$と表記する。

このモデルでのconflict serializabilityも衝突グラフの閉路存在性で特徴づけられる。

### 定義：衝突グラフ

IDMトランザクションの集合$T$と、その履歴$s$を考える。衝突グラフ$G(s)=(V,E)$は以下で定義される。

$$(t_i,t_j)\in E \Longleftrightarrow (\exists t_i, t_j\in V, j\neq i)(\exists u\in t_i)(\exists u'\in t_j)(u<_s u', uu'\not\approx u'u)$$

### 定理8.2

$s\in CSR_{IDM} \Longleftrightarrow G(s)$が閉路を持たない

#### 証明

$\Leftarrow$

$|T|$に関する帰納法で$s\leftrightarrow^*$を示す。$|T|=1$の時は自明。

$|T|<n$でserialなものと衝突同値と仮定する。$G(s)$が閉路を持たないとき、out-degreeが0であるようなノード$t\in V$が存在する。任意の操作ペア$(u,v)$で$u\in t, v\notin t, u<_s v$を満たすようなものは可換であり、したがって$s\leftrightarrow^* s_0 t$という形になる。$G(s_0)$は$G(s)$の部分グラフなので閉路を持たず、帰納法仮定から$s_0$はserialなスケジュール$s_1$と衝突同値。したがって$s$は$s_1 t$と衝突同値。

$\Rightarrow$

$G(s)$が閉路を持つとき、$s\notin CSR_{IDM}$であることを示せばよい。$s\in CSR_{IDM}$を仮定する。serialな$s'$が存在して$s\leftrightarrow^*$であり、$G(s)$が閉路を持つことから$s'$は$G(s)$のトポロジカル順に沿わない。したがってある$t_i,t_j\in V$が存在して$s= ...t_i ...t_j ...$だが$(t_j,t_i)\in E$となる。これは非可換な操作$u_j\in t_j, u_i\in t_i$の存在を意味し、$s$と$s'$が可換操作により並び替えられたことと矛盾する。$\square$

---

### CSRとFSRの中間にあるクラス階層(演習問題8.4)

グラフ$G$と頂点の部分集合$A$に対し、$coalesce(A,G)$を、$A$を1つの頂点に縮約したグラフと定義する。

$k\geq 0$に対し、IDM serializabilityのクラス$SR_k$を以下のように定義する。

#### 定義：k-degree serializability

スケジュール$s$が$s\in SR_k \Longleftrightarrow$

衝突グラフ$G(s)$について、サイズ$k$の頂点部分集合$T_k$が存在して

1. $coalesce(T_k ,G(s))$が閉路を持たず、かつ
2. $\pi_{T_k}(s)\in FSR_{IDM}$ である

$coalesce(T_k ,G(s))$が閉路を持たないとき、$s\leftrightarrow^* s'\pi_{T_k}(s)s''$ ($s's''$が$T-T_k$のserialな履歴かつ$s'$は完全なトランザクションのみ含む) が成り立つ。したがってこのとき、$\pi_{T_k}(s)$がserializableであれば$s$全体がserializableである。

また、$SR_k$への所属判定は明らかに多項式時間で可能である。$k$個の頂点部分集合は多項式通りしかなく、そのそれぞれについて閉路の存在判定は多項式時間、最後にサイズ$k$の部分集合におけるFSR判定も$k!$*多項式時間であることから。

#### $SR_k$の性質

1. $SR_0 = SR_1 = CSR_{IDM}$
2. $SR_k\subset SR_{k+1} \subset FSR_{IDM}\ (k\geq 1)$
3. 任意のstrictでfinal state serializableな履歴$s$に対し、$s\in SR_k$であるような$k$が存在する。

#### 証明

$k=0,1$のケースでは、どちらも「$s\in SR_k \Leftrightarrow G(s)$が閉路を持たない」となるので$CSR_{IDM}$に等しい。

$1$以上の$k$に対して$s\in SR_k$を考えると、ある$T_k$が存在する。$coalesce(T_k ,G(s))$をトポロジカルソートしたときに$T_k$に相当するノードの直前のもの$u$を含めた$T_{k+1}$を考える。このとき$coalesce(T_{k+1} ,G(s))$は明らかに閉路を持たない。次に$\pi_{T_{k+1}}(s)$であるが、こちらは$s\leftrightarrow^* s'u\pi_{T_k}(s)s''$であることと$\pi_{T_k}(s) \in FSR_{IDM}$であることから$\pi_{T_{k+1}}(s) \in FSR_{IDM}$であり、したがって$s\in SR_{k+1}$。
(直前のノードが存在しないなら直後のものを選ぶ)

strictな$s\in FSR_{IDM}$に対し、$G(s)$の頂点全てを$T_k$に選べば自明に$s \in SR_k$である。$\square$

この結果から、$SR_k$は$CSR$と$FSR$の中間にあり、$k$が大きくなるほど$FSR$に収束していく。

---

FSRはトランザクションの最終状態を気にするという意味でグローバルな同値性、CSRは隣接操作の可換性を気にするという意味でローカルな同値性である。これらの中間択として、衝突の定義をより広い視点にした拡張衝突同値性を考える。衝突が、操作同士ではなく、操作とそのprefixに相当する操作群との間に考慮される。

### 定義：拡張衝突グラフ・Extended Conflict Serializability

$s$を$T=\{t_1,...,t_n\}$からなる履歴とする。

1. 拡張衝突グラフ$EG(s)=(T,E)$は以下で定義される。
$$(t_i,t_j)\in E \Leftrightarrow (\exists u\in t_j) s=s'us'' \textrm{ and } \pi_{\{t_i\}}(s')u\not\approx u\pi_{\{t_i\}}(s')$$
2. $s$は$EG(s)$が閉路を持たないときextended conflict serializableとする。

このクラスを$ECSR_{IDM}$と定義する。

### 定理8.3

任意のデータベーススキーマに対し、$CSR_{IDM}\subset ECSR_{IDM} \subset FSR_{IDM}$

#### 証明

$CSR_{IDM}\subset ECSR_{IDM}$は、衝突グラフに閉路が無いなら拡張衝突グラフに閉路がないので明らか。

$ECSR_{IDM} \subset FSR_{IDM}$は$|T|$についての帰納法で示す。$|T|=1$の場合は明らか。

$|T|<n$の場合に成立すると仮定する。$|T|=n$の状況で$s\in ECSR$を考える。$EG(s)$にout-degreeのないノード$t$が存在し、$t$の操作が最後に起こるように$s$を編集できる。よって$s'=\pi_{T-\{t\}}(s)t$に対し$s\approx s'$となり、帰納法仮定と合わせて$s\in FSR_{IDM}$である。$\square$

---

### 関数従属性の存在下でのSerializability

関数従属性

$$A_{i_1}...A_{i_k} \rightarrow A_j$$

が定義されている状況を考える。ただしこの意味は、リレーション内の任意の2つのタプル$t,t'$に対して

$$(t.A_{i_1} = t'.A_{i_1}) \land ... \land (t.A_{i_k} = t'.A_{i_k}) \Rightarrow (t.A_j = t'.A_j)$$

である。

関数従属性の集合$F$が与えられたとき、Fを満たすリレーションのみを対象にして考えることで、serializabilityを拡張することができる。

履歴$s$を考える。あるserialな履歴$s'$が存在して、任意の$F$を満たすリレーション$r$に対して$eff(s)(r)=eff(s')(r)$を満たすことを、$F$についてserializableと定義する。このように定義すると拡張がうまくいかないので、serialな履歴の存在条件を緩和する。つまり、$r$ごとに違うserialな履歴を許すことにする。

### 定義：State Serializability

$R$を、関数従属性$F$を持つリレーションスキーマとする。履歴$s$が$F$についてstate serializableとは、$F$を満たす任意のリレーション$r$に対してあるserialな履歴$s_r$が存在し、$eff(s)(r)=eff(s_r)(r)$を満たすこととする。

このクラスを$SSR^F$と表記する。

この状況下でも、CSRの類似物である$CSSR^F$を考えることができる。
与えられた$F$を満たす任意の状態$d$について、$G(s)$を見て、$d$と関係のない衝突辺は無視して進め、閉路の存在判定を行う。閉路がどの場合にも存在しなければ$CSSR$といえる。

### 定理8.4

$CSR_{IDM}\subset CSSR^F \subset SSR^F$

## トランザクション分割

長いトランザクションはパフォーマンスに影響を及ぼしうるので、できるだけ短い複数のトランザクションに分割して、独立にスケジューラに投げ込みたくなる。このとき、どこまで分割が許されるかを静的に解析する手段を考える。

### 定義：トランザクション分割

$t_i$をトランザクションプログラムとする。$t_i$の分割とは、順序付けられた$t_{i_1},...,t_{i_k}$で、$t_i$のデータベース操作がこれらトランザクション片のいずれか1つに含まれ、操作の実行順が保存されているものとする。

### 定義：分割グラフ

トランザクション集合$T$の分割を考える。分割グラフ$C(T)$とは、以下を満たす無向グラフとする。

1. $C(T)$の頂点は分割されたトランザクション片である。
2. $p,q$を異なるトランザクション由来のトランザクション片とする。$p$と$q$が衝突する操作を含むとき、$p$と$q$の間にラベル$c$の辺が存在する。
3. $p,p'$を同じトランザクション由来のトランザクション片のとき、$p,p'$の間にラベル$s$の辺が存在する。

ラベル$s$の辺と$c$の辺がそれぞれ1個以上含まれるような閉路をsc閉路という。これが分割の正当性を考えるうえで重要になる

分割したトランザクションが問題なく実行されるための条件を定義する。

### 定義：正当な分割

$T$の分割が正当とは、以下の規則に基づく分割されたトランザクションの実行方法が、あるserialな$T$の履歴と衝突同値であることとする。

1. トランザクション片が実行される順番は、分割前のもとのトランザクションでの順序に即する。
2. 各トランザクション片は、conflict serializabilityを満たすプロトコルで実行制御され、全ての操作が終わった時点でコミットされる。

### 定理8.5

分割グラフがsc閉路を持たないとき、その分割は正当である。

このトランザクション分割は、プログラムのセマンティックな知識を活用することができるとはいえ、コンパイル段階で静的な解析を行う必要があるため、パラメータが入ったケースには特殊な工夫が必要になる。

なおこの方法は、3章で導入された相対的なserializabilityと類似している。そちらで他トランザクションに対しての不可分単位に相当するものをプログラムが自動で解析しているといえる。