増永良文著 リレーショナルデータベース入門 [第3版]を読む

アカデミックな本らしい

第1章

• データ: 記号の集まり
• 意味: データに意味解釈を与えたもの
• 情報: 意味が受け手の持っている知識と比較して増える場合のもの
• 価値付き情報: 受け手の価値観に従って価値を有すると判断された情報

概念モデル

実世界が認識され記号化されたもの
ERモデルとか

論理モデル

概念モデルをDBMSで管理可能な形式に変換したもの
リレーショナルデータベーススキーマとか
概念スキーマと呼ばれるもの

ERモデルとリレーショナルデータモデルの違いを認識できてなかった。

ERモデル

実体を個々の実体として認識しようとするのではなくて，総体としてとらえようということである．たとえば，学生を認識するときに，学生のA君，Bさんという認識をするのではんくて，A君，Bさん等々をひっくるめて，抽象的「学生」というとらえ方をしよう，ということである

言われてみればそうだけどその認識はなかった

関連型

実体型との関連を表す関連型を導入

• R(関連型)が多対多のとき、その主キーは和集合K⋃Hである -> ちょっとよくわからなかった 複合主キーは直積なのかと思ってたけど…

• 弱実体型: 実体型と組になることで一意に識別できる型

• 所有実体型: 弱実体型に一意識別能力を与える実体型

• 部分キー: 所有実体型の主キーと一緒にすると弱実体を識別できる属性

• 識別関連型(ID関連型): 所有実体型と弱実体型の関連

ERモデルは(中略)実世界の記述にユニーク性がない

• 学生と科目の関係を関連型としてとらえることもできるし、実体型としてとらえることもできる

第2章 リレーショナルデータモデル

~2.5

• ドメイン(定義域): 集合、有限集合でも無限でもいい
• タップル: ドメインの直積の元
• リレーション: 有限個ドメインの直積の任意の有限部分集合
• 濃度(cardinality): リレーションのタップルの総数
• ドメイン関数: 属性名からドメインへの写像
• リレーションスキーマ: 有限の属性名を集めたもの
  • リレーションが時変なのに対して、リレーションスキーマは時不変である
  • リレーションスキーマをドメイン関数で写像したものをリレーションスキーマのインスタンスという

リレーションスキーマRである性質Pが成り立つということは、RのすべてのインスタンスR'に対してその性質Pが成り立つときおよびそのときのみである

リレーションスキーマを定義していくことがデータベース設計者の仕事、インスタンスを作成していくことはデータ入力作業にあたる

~2.13

• ドメインがシンプルである: ドメインの元が原始的(atomic)、すなわち分解不可能な値であること

  • 他のドメインの直積は許されない

• 第一正規形: リレーションの各ドメインがシンプルであること

• 候補キー: リレーションのタップルを一意識別できる属性の集合で、極小のもの

  • リレーションスキーマには候補キーは必ず存在する

• 空は値ではない

  • 従って、空値(null value)という表現はおかしい

• 空の意味は14種類もあるらしい

  • unk (unknown): 属性値は存在するが、未知である
  • dne (does not exisit): 属性値は存在しない
  • ni (no-information): 属性値が存在するのかしないのか、わからない

• 表明(assertion): リレーション定義とは別でデータベース全体でみたすべき制約

「上司よりも高給を取っている社員がいてはいけない」表明

CREATE ASSERTION 給与制約
    CHECK (NOT EXISTS
        (SELECT X.*
          FROM 社員X, 社員Y, 部門Z
          WHERE X.所属 = Z.部門番号
          AND Z.部門長 = Y.社員番号
          AND X.給与 > Y.給与))

第3章 データ操作言語

リレーショナル代数

リレーショナル代数: データ操作言語の1つ

8つの演算を持つ

• 4つの集合演算
  • 和集合
  • 差集合
  • 共通集合
  • 直積
• 4つのリレーショナル代数に特有の演算
  • 射影
  • 選択
  • 結合
  • 商

和両立(union compatible): 次元が同じ、ドメイン関数が同じ

• ドメインが同じであればいいので、属性名は異なっていても良い

集合演算

和集合演算: 和両立のリレーションR, Sに対して、R ∪ S = \{t | t \in R \lor t \in S\}

差集合演算: 和両立のリレーションR, Sに対して、R-S = \{t| t \in R \land \lnot (t \in S) \}

共通集合演算: 和両立のリレーションR, Sに対して、R\cap S = \{t| t \in R \land t \in S\}

直積演算(Cartesian product): R\times S = \{ (r,s) | r \in R \land s \in S\}

リレーショナル演算

射影: 列の取り出し
選択: 行の取り出し

• θ比較可能: ドメイン関数が等しい、かつ任意のタプルtに対して、t[A_i]\theta t[A_j]の真偽が常に定まる

• θ選択演算: A_iとA_jがθ比較可能な時、R[A_i \theta A_j] = {t | t \in R \land t[A_i] \theta t[A_j}

  • t[A_i]またはt[A_j]がnullを取る可能性がある時、3値論理に拡張する必要がある。
  • 商品[売価 >= 500] みたいな演算はリレーション代数に入っていない。定値リレーションを導入すると同様に定義できる

• θ結合演算: A_iとB_jがθ比較可能な時、R[A_i \theta B_j ]S = {(t, u) | t \in R \land u \in S \land t[A_i] \theta t[B_j]}

  • 直積と、θ選択演算で定義できる： R[A_i \theta B_j ]S = (R\times S)[R.A_i \theta S.B_j]

自然結合、外部結合をフォーマルに定義してる。数式長いので省略

商演算: divisor(割る方のリレーション) を全て含むタプルを抽出(割る方の列はなくなる)
R \div S = \{t | t\in R[A_1, ... A_{n-m} \land (\forall u \in S)((t, u) \in R) ]\}

• (R \times S) \div S = R なので \div 記号が使われてる

リレーショナル代数表現

リレーショナル代数表現(relational algebra expression): 要するにクエリ

これを定義したいモチベがあまりわからなかった

3値論理

IS 演算子の真理値表

マジでそのまま

推量θ選択演算

R[A_i \theta_\omega A_j] = \{t | t \in R \land t[A_i] \theta t[A_j] \ \mathrm{IS} \ \mathrm{UNKNOWN} \}

θ演算の結果が不定のタプルだけ出す、と読めるけどそれ定義して何が嬉しいのかよくわからず

リレーショナル論理

わかったような、わからんような

リレーション R_1 \dots R_n の集まりをリレーショナルデータベース DB とする。
DBにデータ操作言語Lが与えられ、Lで許される操作を有限回使って得られるリレーションの全体集合をL(\mathrm{DB}) とおく

リレーショナル完備：Lがリレーショナル完備(relational complete)とは、
L(DB) \supseteq \mathrm{リレーショナル代数}(DB) = \mathrm{リレーショナル論理}(DB)

SQLはリレーショナル完備である

4章

• リレーションがその分解成分の自然結合を取ると復元できるとき、その分解を情報無損失分解であるという

• 情報損失分解: リレーションを適当に分解すると、自然結合したときにもとのリレーションにはないタップルが出現する

  • これを結合のわなという
  • フォーマルには、R \subseteq R_1 * R_2

情報無損失分解の一意性

R_1 R_2をRの部分集合とするとき、AをR_1のみのリレーション, Bを共通部分, CをR_2のみのリレーションとすると
R[A_1, \dots A_k B_1 \dots B_k]とR[B_1 \dots B_k C_1 \dots C_k]に分解されることをいう

このときRに多値従属性があるという

自明な多値従属性
R(A_1, \dots A_k, B_1, \dots B_l)に対して
A_1, \dots A_k \rightarrow\rightarrow B_1, \dots B_l | \phi
を自明な多値従属性という

関数従属性

関数従属性は多値従属性の特殊な場合である

関数従属性A_1 \dots A_k \rightarrow B_1 \dots B_lとは次の条件を満たすことである
\forall t, s \in R(t[A_1, \dots A_k] = s[A_1 \dots A_k]) \Rightarrow t[B_1 \dots B_l] = s[B_1 \dots B_l]

B_1 \dots B_l がAの部分集合か空集合であるとき、自明な関数従属性という。

完全関数従属性

関数従属性X \rightarrow Yについて、Xの任意の真部分集合に対してYへの関数従属性が成立しないとき、YはXに完全関数従属しているという

推移律

X\rightarrow YかつY \rightarrow ZならばX \rightarrow Zである。

反射律

Y \subseteq XならばX \rightarrow Yである。

添加律

X \rightarrow YかつZ \subseteq WならばX \cup W \rightarrow Y \cup Zである。

推移律、添加律、反射律を合わせてアームストロングの公理系という。
アームストロングは、以上3つを仮定すると関数従属性を全て証明できることを示した。

陽に宣言された、つまり所与の関数従属性の集合F=\{f_1 \dots f_p\}ってのがなんのことなのかわからない

閉包

Fから導出される関数従属性の全体（Fを含む）をFの閉包と呼ぶ
リレーションスキーマRの属性集合Xについて、Fに関する閉包を求める問題を含意問題という

• アルゴリズムはp100

含意問題の応用として、リレーションスキーマRに関数従属性の集合Fが与えられた時に候補キーを求める問題がある。
候補キーは関数従属性を使って次のように定義できる

Rの属性集合Kが候補キーであるとは、次の２つの条件を満たすときをいう

• Kの閉包 K^+ = \Omega_R
• Kのどのような新部分集合に対して前項が成立しない

\Omega_Rってなんだっけ？ -> Rを構成する全ての属性集合

求め方

• R の属性集合Xがスーパキーかどうかは、X^+を計算して、X^+=\Omega_Rならスーパキー
• Xの各要素Aに対して\{X-A\}を作り、その閉包を求める。そのうちどれかが\Omega_Rになれば、スーパキーではあるが候補キーでない。
• RとFが与えられた時に、\Omega_Rは少なくともスーパキーである。これに対して再帰的に前2つの操作を適用すれば候補キーがもとまる

Fの閉包

• Fの閉包を求めるのには一般に指数オーダーの時間がかかる

等価性

関数従属性の集合FとGが与えられたとき、FとGは等価か、すなわちF^+=G^+かを求める問題は難しくない

• FにX\rightarrow Yが存在すれば、XのGに対する閉包X^+を求め、それにYが含まれているかを調べれば良い

極小被覆

G が Fの極小被覆であるとは、

• (a) GとFは等価
• (b) Gの全ての関数従属性は、単一の属性Aを使って、X\rightarrow Aの形
• (c) G に関数従属性 X\rightarrow AとXの真部分集合Zが存在して、G-\{X\rightarrow A\} \cup \{Z \rightarrow A\}がG と等価でない
• (d) Gの関数従属性gが存在して、G-\{g\}がGと等価でない

アルゴリズムはp105へ

• 多項式オーダー、O(|\Omega_R|^2 \times |F|^3)
• 極小被覆は唯一に定まらない(このため最小被覆とは言わない)

第２正規系 (2nd normal form; 2NF)

• R は第一正規系である。
• Rの全ての非キー属性はRの各候補キーに完全関数従属している。

非キー属性: いかなる候補キーにも属していない属性
完全関数従属: 関数従属であり、あらゆる真部分集合に対して関数従属でない

第３正規系 (3rd normal form; 3NF)

推移的関数従属性

X, Y, Z をリレーションスキーマRの属性集合とし、

• X \rightarrow Y
• Y \rightarrow X でない
• Y \rightarrow Z

とする。ただし、Y \rightarrow Zは自明でないとする。
このとき、

• X\rightarrow Z
• Z \rightarrow X でない
  が成立する。このとき、X \rightarrow Zを推移的関数従属性と呼び、ZはXに推移的に関数従属するとよぶ

第３正規系の定義

• (1) Rは第２正規系である
• (2) Rの全ての非キー属性はRのいかなる候補キーにも推移的に関数従属していない

ボイスコッド正規系 (BCNF)

要は候補キーから候補キーへの推移的関数従属性を禁止する正規系っぽい

X \rightarrow YをRの関数従属性とするとき、次のいずれかが成立することをいう

• X \rightarrow Yは自明な関数従属性である。
• XはRのスーパキーである

第３正規系であることは含まれている？

• BCNF 分解は関数従属性を保存しない

第４正規系 (4NF)

次のいずれかが成立することをいう

• X \rightarrow\rightarrow Y は自明な多値従属性である
• XはRのスーパキーである

結合従属性

(x,y) (y,z), (z,x) を射影R[X, Y] R[Y, Z] R[Z, X] の元とするならば、タップル(x,y,z)もRのタップルでなければならないとき、リレーションR(X, Y, Z)は3-分解可能と言う
このとき、リレーションRには結合従属性*(X,Y,Z)が存在していると言う。

第５正規系 (5NF)

*(X_1, X_2, \dots X_n) をRの結合従属性とするとき、次のいずれかが成立することを言う

• *(X_1, X_2, \dots X_n)は自明な結合従属性である
• 各X_iはRのスーパキーである

ここでが自明であるとは、X_1, \dots X_nのうち一つが\Omega_Rに等しいときをいう。

第５正規系への分解は、第４正規系が関数従属性を保存しなかったように、結合従属性を保存しない。

さっぱりわからん

合成的手法によるデータベース設計

リレーションを徒に高次に正規化するのではなく、第３正規系止まりとするのが良いのではないかと言う共通認識ができている。バーンシュタインが示した合成的手法(sythesis approach)により、関数従属性保存、第３正規系、情報無損失分解が揃ったデータベース設計が行える。

1. Fの極小被覆Gを一つ見つける
2. Xを決定子に持つGの全ての関数従属性X\rightarrow B_1 \dots X\rightarrow B_k に対してY=\{B_1 \dots B_k\}とし、リレーションスキーマR(X,Y)を作る。この操作をGの全ての関数従属性に対して行う。その結果、\{R_1(X_1, Y_1) \dots R_m(X_m, Y_m)\}を得る
3. \{R_1 \dots R_m\}の中にRの候補キーを含むリレーションスキーマが存在すれば、これが所望の分解である。もしそうでなければ、Rの候補キーの一つをKとしてR'(K)を作ると、\{R'(K), R_1, \dots R_m\}が所望の分解である

5章 SQL

知っていることは飛ばす

• リレーションは集合であり、同じタップルが表れることはなかったのに対し、SQLの表はmultisetである
• SELECT句は射影演算、FROM句は直積演算、WHERE句は選択演算
  • したがって処理は、FROM -> WHERE -> GROUP BY -> HAVING -> SELECT の順

SQLのリレーショナル完備性

リレーショナル代数の5つの独立な演算、和、差、直積、射影、選択が存在することを示す

• 和: UNION
• 差: EXCEPT
• 直積: 結合

SELECT R.*, S.*
FROM R, S

• 射影: SELECT
• 選択: WHERE

PL/I

まあいいか

動的SQL

こんなんあるんだ。
今ならクエリビルダがやっちゃいそう。
まだ使われてるのかな。

オブジェクト指向拡張

• ROW型

CREATE TABLE 学校(
    学校名 NCHAR VARYING(20),
    所在地 ROW(町 NCHAR VARYING(10), 区 NCHAR VARYING(10), 郵便番号 CHAR(8))
)

INSERT INTO 学校
VALUES (N'お茶の水小学校', ROW(N'大塚', N'文京', '123-4567'))

• ユーザ定義型

CREATE TYPE 学校型 AS(
    学校名 NCHAR VARYING(20),
    所在地 ROW(町 NCHAR VARYING(10), 区 NCHAR VARYING(10), 郵便番号 CHAR(8))
)

• メソッドを定義できる
• サブタイプ(継承)が定義できる

CREATE TYPE 大学型 UNDER 学校型 AS (学部名 NCHAR VARYING(10))

6章 DBMS標準アーキテクチャ

ANSI/X3/SPARC がDBMSの3層アーキテクチャを定義している

ロール

• 組織体管理者
• データベース管理者
• アプリケーションシステム管理者

機能

• 概念スキーマプロセッサ
• 外部/概念データベース変換

データ辞書

メタデータのデータベース

3層スキーマ

概念スキーマ

リレーショナルモデルとかネットワークモデルとかハイアラキカルデータモデルとかオブジェクト指向データモデルとか

内部スキーマ

ISAMファイルやB+ treeとか
概念スキーマをストレージ/コンピュータシステムを実装するための構文的・意味的構造

データベース管理者が内部スキーマを定義する

• マジで？日常用語のDBAと割と意味が違う気もする（言語やアルゴリズムを実装することはないと思う）けど、ここにインデックス貼るといいとかそういう話をしている？
• 構文的・意味的構造って何〜

外部スキーマ

ビューのこと

あるいはUIとか（アプリケーションを含んでいるのか不明）

データ独立性

物理的データ独立性

1つのリレーションは1つのファイルで実装される。

• リレーション <-> ファイル
• タップル <-> レコード
• 属性 <-> フィールド

ファイル中のレコードの位置決めをする方法をアクセス法（access method）という

要はファイルシステムやアクセス法をDBユーザに影響を与えずにできること = 物理的データ独立 ということらしい

論理的データ独立性

アプリケーションプログラムを実世界の変化による概念スキーマの変化から不変に保つこと

• そんなことできんの？

アプリケーションはビューだけに依存しろと言っているように聞こえるが実際どれぐらい守られているのか不明

• ビューを使っても更新時に異状が発生する場合がある。詳しくは次章

DBMSの3大機能

• メタデータ管理
• 質問処理
• トランザクション管理

メタデータ管理

• 概念スキーマ、外部スキーマ、内部スキーマを格納する
• システムカタログ: どのようなリレーションにどのような情報が入っているかの情報
  • カタログリレーションとして実装

実体は DEFINITION_SCHEMA と呼ばれるスキーマに格納される。これはプログラマが直接いじれないようになっている。
代わりに INFORMATION_SCHEMAというビューの集まりを参照できる。

質問処理

内部スキーマレベルのアクセスコードを生成する処理

RDBMSの場合、質問は非手続き的なため、DBMSが処理コストが最小のアクセスコードを生成する必要がある(詳しくは9章)

トランザクション管理

障害時回復(recovery)と同時実行制御(concurrency control) 12章で

7章　ビュー

ビュー更新問題

結合ビューへの更新は意味的曖昧性を持っており必ずしも現実世界を反映しない。
ただし選択ビューは更新可能である

ビューの更新可能性

なんか色々あるが便利な結論が出ていないのを理解した

体現ビュー

OLAPやDWHで積極的に使われる

8章 ファイル編成とアクセス法

• ファイル編成: ファイルを編成するレコード群の間にどのような関係性があるかの設定

• アクセス法: ファイルから所望のレコードをどのように見つけ出すか

ファイル編成

• ヒープ編成: レコードが二次記憶に書き込まれた時刻順にレコードに順番を付ける直列編成ともいう
  • アクセス方は基本的に線形探索
• 順次編成: ファイルを構成するレコードのあるフィールド（キー）の昇順または降順でソートして順番づけする
  • 高速アクセス
  • 削除、書き換え、挿入にともないソートし直さないといけないのが非効率的
• 直接編成: ハッシュ編成あるいはランダム編成ともいう。ハッシュ関数で二次記憶上の位置を求める
  • 範囲問い合わせが非効率的
  • ハッシュ関数に偏りがあると更新が非効率的

アクセス法

• 順次アクセス法: 先頭レコードから順に行き着く方法
• インデックス法: キーとレコードの格納番地の対応表（インデックス）を作成する

ヒープ編成ファイルにインデックスを貼ってもいいし、順次編成ファイルにインデックスを貼らずに順次アクセスしてもよい

ファイルスキャン

線形探索: O(n)
二分探索: O(logn)
ブロック探索: O(\sqrt{n})

以上総称してファイルスキャンという

インデックス法

インデックスは2項ファイルであって、第1フィールドはフィールドの値、第2フィールドはレコードの格納番地のポインタ

インデックスレコードのスキャンアクセスが可能
インデックスを用いてファイルのレコードの位置決めをする方法をインデックススキャンという

インデックスを張ったフィールドについてその順番でディスクに格納されているとき、FはAに関して順次という。このとき、Aを順序フィールドという
AがFの（候補）キーであるとき、Aを順序キーという。

順序キーに定義されたインデックスを1次インデックスという。
それ以外のインデックスを2次インデックスという。
2次インデックスの対象フィールドが候補キーでない場合、間接ブロックで二重参照してレコード特定する。

• DBMS上で候補キーかどうかって（自明な場合を除いて）わからないのでは？自明な場合で十分ということなのかな

Dense index: 順序インデックスで、全部の値をインデックスに格納
Sparse index: 順序インデックスで、一部だけ格納（ソートされているので、ないやつは間を走査すれば見つかる）

多段インデックス: 木でインデックスを表現（sparse indexの拡張）

順序キー上に多段インデックスを張ってアクセスする方法をインデックス付き順次アクセス法（Indexed Sequential Access Method: ISAM）という。
ISAMでアクセスするファイルをISAMファイルという

インデックスの1ノードに入る順序キー値とポインタのタプルの最大数をオーダーという
ナイーブな木でインデックスを構成すると、挿入時に非平衡木になってしまい、レコードによってアクセス回数のばらつきが出てしまう。

B+ tree

よくわからんけど葉ノードにデータポインタの個数の制約と、中間ノードにデータポインタが入らないようにする制約があるのがキモっぽい？
これによって平衡木が保たれる

キーの物理的な（ディスク上の）順序性は要求していない

レコード挿入

葉ノードに空きがあれば入れる。なければ、ノード分割する。

• ノード分割回数の最悪値オーダーがわからん。

レコード削除

ポインタが空にしたときに、データポインタ個数の制約に抵触する場合、きょうだいノードを見つけてデータポインタを再分配する。あるいは、自分とどちらかのきょうだいノードを合体する。

ハッシュ法

ハッシュ関数について書いてある
動的ハッシュ法について書いてある

9章 RDBMS の質問処理とその最適化

構文解析、最適化、コード生成、実行の4ステップで実行される

コスト式

C=C_{I/O}+ \omega \times C_{CPU}
C_{I/O}はフェッチしたページ総数、C_{CPU}はCPU使用率、オメガは重み係数。
C_{I/O}はインデックスとデータページの数に分けられる。

10章 トランザクションと障害時回復

主記憶のデータが2次記憶に書き出されるタイミングはOS任せ、ページ置換アルゴリズムによる。
主記憶に書いてプログラム上トランザクションが終了したが、書いたデータが2次記憶に書き出される前に障害になった場合どうするか？
2次記憶に書かれたかどうかの状態遷移を管理して解決する。
プログラムが実行終了したらコミット待ち状態に遷移し、失敗したら失敗状態に遷移する。それぞれコミットが行われたらコミット状態、ロールバックが行われたらロールバック状態に移行する。

ログ

ログは書き込みがあると直ちに安定記憶に強制書き込みされる。
（データページはOSのページ置換アルゴリズムに任せている）

波及ロールバック

ログにはトランザクションのreadも書いてある。
T1がアボートされたら、T1が書いたデータを読んでいたT2もアボートしないといけない（以下波及的にアボートの必要あり）から。
ただしこれはとても大変なので、T1が書いたデータをコミットするまでは他のトランザクションが読めないようにすることもある（2 phase lock）。この場合ログにREADは書かなくていい。

11章一旦飛ばす

12章 分散DBMS

透明性

DBユーザからの要求

• 位置に対する透明性
  • 物理的にどのサイトにデータが格納されているかを意識する必要がないこと
• 分割に対する透明性
  • 複数のサイトに分割してデータを保存したり移動したりしてもそれを意識する必要がないこと
• 複製に対する透明性
  • 複数のサイトにデータを複製して保存していても、それを意識する必要がないこと

13章 クライアントサーバーコンピューティングとデータベース

相互接続性と共通インターフェースの話が書いてある

OLTP (online transaction processing)

刻々と変化する実世界に対応して瞬時に多様なトランザクションを処理する。
さまざまなクライアントがネットワークを介してDBにアクセスするような、ふつーのDBを使うアプリケーションのことを言っている

OLAP (online analytical processing)

様々なデータを集計して1つの知識の塊にして意思決定を支援するシステム

スライシング: 多次元データベースから2次元の表を切り出す
ダイシング: 特定の値について多次元データベースをそのまま出す（次元は落ちない？）

11章 トランザクションの同時実行制御

同時実行制御しないときに起こる異状

• 遺失更新（lost update）
  • あるトランザクションによる更新が別のトランザクションにより失われて不整合になること
• 汚読（dirty read）
  • あるトランザクションが更新途中の値を別のトランザクションが読むこと
  • dirty readした値を元にcommitしてしまうと、それより前には戻せないので回復不可能スケジュール（non-recoverable schedule）となる
• non-repeatable read
  • トランザクション中に他のトランザクションがcommitした値を読むこと(dirty readはコミット前)
  • とくに同じ結果を期待するread処理の結果がタイミングによって異なること

14章 ビッグデータとNoSQL

CAP定理

共有データシステムにおいては、整合性、可用性、分断耐性の3つの性質のうち、高々2つしか両立させることができない。

分断耐性を放棄したのが従来のRDBMSであり、可用性を放棄したのがBigtableであり、整合性を放棄したのがDynamoである。

BASE

• Basically Available
  • CAP定理の意味で可用（って何？）
• Soft-state
  • 入力がなくてもシステムの状態が変化しうる
• Eventual Consistent
  • 新たな更新がなく、障害がなければ、すべてのデータの複製はいつかは整合状態となる

結果整合性

• 強い整合性
  • データの更新が完了した時点でどの複製にアクセスしても更新された結果（新しいデータ）を返すこと
• 弱い整合性
  • 結果整合性

N: データの複製数
W: 更新完了の返事を返すべき複製の数
R: 検索結果を返すべき複製の数

マスターはNこのスレーブに更新要求を送り、少なくともWこのスレーブから更新完了メッセージを受信したら、クライアントに更新完了メッセージを送る。
クライアントからデータ検索要求が来たら、Nこのスレーブに検索要求を出して、少なくともRこのスレーブから結果が返ってくれば、その中で最新のものをクライアントに検索結果として返す。

このとき、次の関係がある

1. W+R > N の場合、強い整合性で対処する
2. W+R \le Nの場合、結果整合性で対処する

本文誤植あり

N=3, W=1, R=1 とするシステムが多い

完全に良書でした