2020-07-09 (Thu.)
\(\def\null{\mathrm{null}}\def\A{\mathcal{A}}\def\D{\mathcal{D}}\def\dom{\mathrm{dom}}\def\Bool{\mathrm{Bool}}\) \(\def\mvdarrow{\rightarrow\!\!\!\rightarrow}\def\fdarrow{\rightarrow}\)
部分的に厳密でない定義が出てきてしまう. 書き直せたら書き直したい.
適当な（無限を許す）集合のクラス \[\D = \{D_\lambda \}_\lambda\] についてこの各 \(D_\lambda\) を ドメイン と呼ぶ. このうちのいくつかを特に, プリミティブなドメインと呼ぶことにする. そしてそれ以外の全てのドメインは, プリミティブなドメインの組み合わせから適当な操作で得られる集合であるとする（直積集合とか冪集合など）.
\(R\) が関係であるとは, ある有限個のドメイン \(D_1, D_2, \ldots, D_N\) の直積の部分集合であること: \[R \subset D_1 \times D_2 \times \cdots \times D_N.\]
関係 \(R\) の各要素のことをタプルと呼ぶ. \[r = (x_1, x_2, \ldots, x_n) \in R; x_i \in D_i\]
タプル \(r\) に対してその各要素 \(x_i\) を属性値とかカラム値と呼ぶ. 添字 \(i\) を属性とかカラムと呼ぶ.
特別な値 \(\null\) を用意する. ドメイン \(D\) に対して \(x \in D\) と書いたとき, これは集合 \(D\) に属するかまたは \(x = \null\) であると意味を拡張する \((x \in D \cup \{\null\})\). 部分集合についても同様の拡張をする. 特に関係 \(R \subset D_1 \times D_2 \times \cdots \times D_N\) と書いた時, \((x_1, x_2, \ldots, x_n) \in R\) は \(x_i = \null\) でありえる.
\(=\) の意味も拡張する. 空値はどの値とも等しくない: \[\forall x, x \ne \null.\] 特に \(\null \ne \null\). 代わりに null かを判定する述語 \(\null?\) を用意しておく.
同じドメインに異なる意味を与えたい. そこで関係をドメインではなく名前で定義する.
名前とはシンボルのことで, ある無限集合 \(\A\) の要素を名前（属性名, カラム名）と呼ぶことにする. 各名前には一意にドメインを対応付ける: \[\dom \colon \A \to \D.\]
これを以て関係を再定義する.
互いに相異なる \(A_i \in \A\) に対して, 関係 \(R(A_1, A_2, \ldots, A_N)\) とは \[R \subset \dom A_1 \times \dom A_2 \times \cdots \times \dom A_N\] のこと.
添字 \(i\) を属性（カラム）と呼んだのに対して, 名前 \(A_i\) を 属性名（カラム名） と呼んだりする.
関係 \(R(A_1, A_2, \ldots, A_N)\) について, 全ての \(\dom A_i\) がプリミティブであるとき, \(R\) は第一正規形を満たすという.
関係 \(R(A_1, A_2, \ldots, A_N)\) のタプル \(r = (x_1, x_2, \ldots, x_n) \in R\) (\(x_i \in \dom A_i\)) について, \[r[A_i] = x_i\] \[r[A_i, A_j, \ldots, A_k] = (x_i, x_j, \ldots, x_k)\] と書くことにする.
名前集合 \(\A\) に対して, 名前列とは相異なる \(0\) 個以上有限個の名前 \(A_i \in \A\) を一列に並べて丸括弧で括った \[A = (A_1, A_2, \ldots, A_N)\] と書いたもの. 特にゼロ個の要素を並べた \(()\) も列だとする.
二つの列について, それらが等しいとは並べた要素数が等しく, 中の要素もそれぞれ等しいこと. \((A_1, \ldots, A_N) = (B_1, \ldots, B_N) \iff \forall i, A_i = B_i\).
列 \(A=(A_1,A_2,\ldots,A_N)\) に対して, 順序を忘れて集合にしたものを \(\overline{A} = \{A_1,A_2,\ldots,A_N\}\) と書くことにする.
列 \(A'\) が列 \(A\) の 部分列 であるとは, \(\overline{A'} \subset \overline{A}\) であって, \(A\) の中での順序を保っているもののこと. 部分列の関係を \(\subset\) と同じ気持ちで \(\prec\) と書く.
列 \(A\) と \(B\) との共通列 \(A \land B\) とは \(\overline{A} \cap \overline{B}\) の要素を \(A\) の順序で並べたもの.
列 \(A\) と \(B\) の直和（結合） \(A + B\) とは \(A\) の後ろに \(B\) を続けて並べたもの. ただし名前列の場合は中の要素は相異なるようにしたいので, 名前が被った場合はエイリアスとして, 別な名前をつけることで区別する. これは後述する関係代数での直積演算で詳細に述べる.
列 \(A\) と \(B\) の差 \(A - B\) とは \(A\) の内, \(B\) に登場するものを取り除いたもの. \((1, 2, 3) - (2, 4, 6) = (1, 3)\).
列 \(A\) と \(B\) の和 \(A \lor B\) とは \(\overline{A} \cup \overline{B}\) の要素を \(A\) の順序で, \(A\) に登場しないものは \(B\) の順序で並べたもの. \(A \lor B = A + (A - B)\). \((1, 2) \lor (1, 3) = (1, 2, 3)\).
また今後は, 名前列 \(A = (A_1, \ldots, A_n)\) の上の関係 \(R(A_1, \ldots, A_n)\) を \(R(A)\) と書くことにする.
関係 \(R(A)\) について, 名前列 \(A\) の空でない部分列 \(K (\prec A)\) が \(R\) の 候補キー であるとは, \[\forall r, r' \in R, r[K] = r'[K] \implies r = r'\] を満たす中で（\(\prec\) に関して）極小なもののこと. 最悪 \(A\) そのものが（極小とは限らないが）この性質を満たすので少なくとも一つは存在する. 候補キーはただ一つとは限らない.
| R | ID | ID1 | ID2 |
|---|---|---|---|
| 1 | 1 | 1 | |
| 2 | 1 | 2 | |
| 3 | 2 | 1 | |
| 4 | 2 | 2 |
例えばこの \(R\) の候補キーは (ID) 及び (ID1, ID2) の二つある.
候補キーの内のどれか一つを選んで 主キー と呼ぶ. どれを主キーにするかがいわば関係に与える意味になる.
データベースとは以上の \((\D, \A, \dom)\) 及び, その上の有限個の関係集合 \(\{R_1, R_2, \ldots, R_M\}\) のこと.
データベースが与えられたとき, 関係の上の代数を構築する. この代数演算はいくつかの関係から別の関係を作る. 最初に与えられる関係の集合について閉じてるわけではないので, この演算で作ることの出来る関係全体はもっと大きなクラスになる.
次の8つの演算を定める:
二つの関係 \(R(A), S(B)\) について, 名前列が等しい \((A=B)\) とする. この関係を「\(R\) と \(S\) は両立している (compatible)」と呼ぶことにする.
和はこのように両立した二つの関係について定義される.
両立した関係 \(R(A), S(A)\) について, この和を \(R \cup S\) と書いて次で定める: \[R \cup S := \{ r \mid r \in R \lor r \in S\}\]
この新しく出来た \(R \cup S\) は \((R \cup S)(A)\) という新しい関係になっている.
両立してる二つの関係 \(R(A), S(A)\) について差は次で定められる: \[R - S := \{ r \mid r \in R \land r \not\in S\}\]
両立してる二つの関係 \(R(A), S(A)\) について \[R \cap S := \{ r \mid r \in R \land r \in S\}\]
ここで \(R \cap S = (R \cup S) - (R - S) - (S - R)\) である. 従って共通演算は直接与えなくても再現できる.
二つの関係 \(R(A), S(B)\) について, \[R \times S := \{ (r, s) \mid r \in R, s \in S \}\] と定める.
これは \((R \times S)(A + B)\) という関係であり, このタプルを \(r = (x_1, \ldots, x_m) \in R\) と \(s = (y_1, \ldots, y_n) \in S\) に対して \((r, s) = (x_1, \ldots, x_m, y_1, \ldots, y_n)\) と書くことにする.
カラム名について, \(A \land B \ne ()\) の場合に \(A+B\) を単に結合とすると名前が被ってしまう. そこで \(A=(A_1, \ldots, A_m), B=(B_1, \ldots, B_n)\) に対して, \[A+B = (R.\!A_1, ~ \ldots, ~ R.\!A_m, ~ S.\!B_1, ~ \ldots, ~ S.\!B_n)\] とリネームすることで回避する. ただし名前が被らない場合は特にリネームはしないで済ます.
タプルに対して射影を定義したが, 同じことが関係に対して出来る.
関係 \(R(A)\) とこの名前の部分列 \(A' \prec A\) について, \[R[A'] := \{ r[A'] \mid r \in R \}.\]
二つのドメインの \(D_i, D_j\) の上の比較演算子 \[\theta \colon D_i \times D_j \to \Bool\] \[(x, y) \mapsto x \theta y\] があるとする.
このとき関係 \(R(A)\) があって, \(\dom A_i = D_i, \dom A_j = D_j\) だとする. このとき, \[R[A_i \theta A_j] := \{ r \in R \mid r[A_i] ~ \theta ~ r[A_j] \}\] とする.
これを \(\theta\)-選択 という. 例えば \(\leq\) に対して \(\leq\)-選択と言う.
選択の定義は以上だが, 便利なので次のようなことも出来るようにする. 定数 \(c\) について, \[R[A_i \theta c] := \{ r \in R \mid r[A_i] ~ \theta ~ c \}.\] これは定数 \(c\) だけからなる関係 \(C\) を以て \((R \times C)\) から選択することで再現できる. なのでこれの糖衣構文だということにする.
二つの関係 \(R(A), S(B)\) 及び, \(\dom A_i, \dom B_j\) の上の比較演算子 \(\theta\) があるとする. \[\theta \colon \dom A_i \times \dom B_j \to \Bool\]
このとき \[R[A_i \theta B_j]S := \{(r,s) \in R \times S \mid r[A_i] ~ \theta ~ s[B_j] \}.\]
これを \(\theta\)-結合 という. この結合は \(R[A_i \theta B_j]S = (R \times S)[A_i \theta B_j]\) と書けるので, このような糖衣構文だと思うこともできる.
また自然に, 複数の比較演算子 \(\theta^1, \theta^2, \ldots\) で以て \(R [A_{i_1} \theta^1 B_{j_1}, A_{i_2} \theta^2 B_{j_2}, \ldots]S\) も定義できる.
\(R(A), S(B)\) の名前列に空でない共通列 \(C = A \land B \ne ()\) があったとする. このとき \(C = (C_1, \ldots, C_k)\) について次のように \(=\)-結合をとったものを 自然結合 と呼ぶ.
\[R \ast S := (R[C_1=C_1, \ldots, C_k=C_k]S)[A \lor B].\]
例くらい書いておくと,
| \(R_1\) | \(A_1\) | \(A_2\) |
|---|---|---|
| 1 | 2 |
| \(R_2\) | \(A_2\) | \(A_3\) |
|---|---|---|
| 2 | x | |
| 2 | y |
に対しては,
| \(R_1 \ast R_2\) | \(A_1\) | \(A_2\) | \(A_3\) |
|---|---|---|---|
| 1 | 2 | x | |
| 1 | 2 | y |
二つの関係が \(R(A + B), S(B)\) とあるとき, \[R \div S := \{ r \in R[A] \mid \forall s \in S, (r, s) \in R\}\] を 商 という.
特に \((R \times S) \div S = R\) である.
関係 \(R(A)\) を次のようにして二つの関係に 分解 する. まず, 名前列 \(A\) を重なる二つに分解する.
これによって \(R_1 = R[X_1], R_2 = R[X_2]\) の二つに射影することが出来る. 名前が重なっているので自然結合することができ, 関係 \[(R_1 \ast R_2)(A_1, \ldots, A_n)\] を得るが, 一般に \[R \subset R_1 \ast R_2\] が成立する. そして一般には \[R \ne R_1 \ast R_2\] である.
任意の \(r \in R\) が \(r \in R_1 \ast R_2\) であることを確認すればよい. \(r_1 = r[X_1] \in R_1\). \(r_2 = r[X_2] \in R_2\). この二つの自然結合はまさに \(r\) そのもの. ほとんど自明.
反例を一つ見れば良い.
| \(R\) | \(A_1\) | \(A_2\) | \(A_3\) |
|---|---|---|---|
| 1 | a | x | |
| 2 | a | x | |
| 2 | a | y |
これを \(X_1=(A_1,A_2)\) と \(X_2=(A_2,A_3)\) に分割すると,
| \(R_1\) | \(A_1\) | \(A_2\) |
|---|---|---|
| 1 | a | |
| 2 | a |
| \(R_2\) | \(A_2\) | \(A_3\) |
|---|---|---|
| a | x | |
| a | y |
これを自然結合すると, どのタプルでも \(r_1[A_2] = r_2[A_2]\) が成り立つようになってるので,
| \(R_1 \ast R_2\) | \(A_1\) | \(A_2\) | \(A_3\) |
|---|---|---|---|
| 1 | a | x | |
| 1 | a | y | |
| 2 | a | x | |
| 2 | a | y |
を得てしまう.
自然結合が元の関係に一致するような分解を 情報無損失分解 という.
関係 \(R(A)\) は以下の時に限って情報無損失分解される.
名前列 \(A\) を \(X_1, X_2\) に分解したとする. \(C = X_1 \land X_2\), \(D = X_2 - X_1\) とする. このときに次が成り立つこと \[\forall r, r' \in R, r[C] = r'[C] \implies (r[X_1], r'[X_2])[A] \in R.\]
あんまり定理という程でもなくて, \(R_1 \ast R_2 \subset R\) というのを, そのまま言い換えてるだけ. \(r[C]=r'[C]\) というのが自然結合で結合される条件を言ってて, このとき任意に \(R_1, R_2\) から持ってきたタプルを結合したものが \(R\) に属してる, と言ってるだけ.
\(R(A)\) と \(X, Y \prec A\) について \[X \mvdarrow Y\] とは \(R(A)\) が \(R[X \lor Y]\) と \(R[X \lor (A - Y)]\) とに情報無損失分解されること. \[X \mvdarrow Y \iff R = R[X \lor Y] \ast R[X \lor (A - Y)]\]
このとき \(Y\) は \(X\) に 多値に従属する といい, 逆に \(X\) は \(Y\) を 多値に決定する という.
この \(Y\) と \(A-Y\) の関係は当然対称的なので, \[X \mvdarrow Y \iff X \mvdarrow A-Y\] である. この二つを合わせて \[X \mvdarrow Y \mid A-Y\] と書いたりもする.
同じことを言い直すが, 名前列 \(A\) を適当な二つ \(A_1, A_2\) (ただし \(A_1 \lor A_2 = A, A_1 \land A_2 \ne ()\)) に分解してこのとき, \[A_1 \land A_2 \mvdarrow A_1 \mid A_2 \iff R[X_1] \ast R[X_2] = R\]
自明な多値従属性として \(Y \prec X \implies X \mvdarrow Y\) がある. これは \(R[X \lor Y] = R[X], R[X \lor (A-Y)]=R[A]\) なので当然に情報無損失分解. 特に \(X \mvdarrow ()\) である.
\(r \in R(A)\) と \(X, Y \prec A\) について, \(r[X]\) が決まるとき \(r[Y]\) が決定することを, \(Y\) は \(X\) に関数的に従属するという. これを \[X \fdarrow Y\] と書く.
\[X \fdarrow Y \iff (\forall r, r' \in R(A), r[X] = r'[X] \implies r[Y], r'[Y])\]
自明な関数従属性として \(Y \prec X\) のときは常に \(X \fdarrow Y\).
\(X \fdarrow Y\) であるような \(X\) の内, 極小なものを \(X^*\) とする. \(X^* \fdarrow Y\) を 完全関数従属 という. \(R(A)\) の主キーが \(X\) であるとはまさに \(X \fdarrow A\) が完全関数従属であることを言う.
関数従属ならば多値従属である. \[X \fdarrow Y \implies X \mvdarrow Y.\]
ゴールの多値従属性について再確認すると, \(R(A)\) について,
従って \(X \fdarrow Y \implies X \mvdarrow Y\) を確認するためには, \(X \fdarrow Y\) と \(r[X] = r'[X]\) を仮定して, \((r[X_1], r'[X_2])[A] \in R\) が成り立つことを確認できればよい.
\(X \fdarrow Y \iff (r[X]=r'[X] \implies r[Y] = r'[Y])\) なので, \(r[X]=r'[X]\) と合わせて \(r[Y] = r'[Y]\) を得る. 従って \(r[X_1] = r[X \lor Y] = r'[X \lor Y] = r'[X_1]\). \((r[X_1], r'[X_2])[A] = (r'[X_1], r'[X_2])[A] = r' \in R\).
ということで多値従属性が確認できた.
関係 \(R(A)\) について,
これに, 適当な関数従属性の集合
を宣言して, \(F\) を 1-3 のルールで膨らましたものを \(F^+\) という. \(F^+\) に入ってるルールが確かに \(R(A)\) で関数従属性になっていることを健全性 (soundness) といい, 逆に \(R(A)\) であり得る関数従属性が \(F^+\) に入ってることを完全性 (completeness) という.
名前列 \(X\) について, \(X\) の（\(F\) に関する）閉包 \(X^+\) を次で定める: \[X^+ := \{Y \mid (X \fdarrow Y) \in F^+\}\]
\(R(A)\) について, \(A\) を \(A_1, A_2, \ldots, A_n\) に分割する. ただしこのとき, \(A_1 \lor A_2 \lor \cdots \lor A_n = A\) であるとする.
このときに \[R = R[A_1] \ast R[A_2] \ast \cdots \ast R[A_n]\] が成り立つことを結合従属性といい, \(\ast(A_1, A_2, \ldots, A_n)\) などと書く. \(n=2\) の場合を多値従属性と呼んだので, 結合従属性は多値従属性と一般化だとみなせる. \[\ast(A_1, A_2) \iff (A_1 \land A_2 \mvdarrow A_1 \mid A_2)\]