「利用者:Nayuta Ito/プロジェクト・SQL」の版間の差分

2021年2月22日 (月) 08:40時点における版

このプロジェクトは凍結しました。集合関数とか何をどうやって束縛してるんですか...

~~この記事では、SQLのインタプリタをZFCで実装する。~~実装しません。複雑すぎました。多分理論上は可能なんじゃないかと思います。ZFCはC言語の亜種ではない。

導入

SQLは関係データベースと呼ばれる非常に複雑な集合に対して定義される非常に複雑な演算子である。SQLは演算子であるにもかかわらず、その記法があまりにも複雑であるため、Structured Query Languageと呼ばれることもある。

定数記号

NULLと呼ばれる特殊な定数記号が必要である。これはZFCの外に存在する必要はなく、空集合などで代用できる。この記事では、NULL={}を仮定するが、必ずしもそうである必要はない。

文字列

文字とは、$ 32 $以上$ 127 $以下の整数のことである。また、この表の対応によって実際の文字と整数とを同じように扱う。すなわち、文字「0」は$ 32 $を意味し、文字「R」は$ 82 $を意味する。

文字全体の集合を$ \mathbb{C^*} $とする。とくに、$ \mathbb{C^*} $と$ [48, 57] \cup [65, 90] \cup [97, 122] $との共通部分を$ \mathbb{C} $とする。SQLで複素数が出てくることはないので、複素数と記号が被る心配はない。

$ 1 $文字以上の有限の文字の列を文字列と呼ぶ。空列は文字列ではない。例えば、「R*」という文字列は$ 82, 42 $という数列であり、「Hello, World」という文字列は$ 72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100 $という数列である。

文字列全体の集合を$ \mathbb{S^*} $で表す。また、元が全て$ \mathbb{C} $の元であるような文字列全体の集合を$ \mathbb{S} $で表す。SQLで十六元数が出てくることはないので、十六元数と記号が被る心配はない。

関係データベース

関係データベース(リレーショナルデータベース、relational database、RDB)とは、$ 0 $個以上の関係表からなる集合である。ただし、
1. 関係表とは、組$ \langle N, R \rangle $である。ただし、
  1. $ N $は$ \mathbb{S} $の元である。表の名前を意味する。
  2. $ R $は表の本体であり、組$ \langle S, D \rangle $からなる。ただし、
    1. $ S = \{ S_1, \cdots, S_n\} $は関係スキーマと呼ばれる$ \mathbb{S} $の空でない有限部分集合である(たぶん無限でもよいが、一応有限を想定する)。
    2. $ D $は$ 0 $個以上のタプルの集合である。ただし、
      1. タプルとは、$ \{ (S_1, T_1), \cdots, (S_n, T_n) \} $の形の集合である。

関係表はその名前の通り表の形で表されることが多い。以下でも、関係表が表であるかのように記述することがあるが、もちろん関係表は上の定義により与えられるZFCで定義された集合である。

$ N $
$ S_1 $	$ \cdots $	$ S_n $
$ T_{11} $	$ \cdots $	$ T_{1n} $
$ T_{21} $	$ \cdots $	$ T_{2n} $
$ \ \ \vdots $	$ \ddots $	$ \ \ \vdots $
$ T_{m1} $	$ \cdots $	$ T_{mn} $

ただし、上の表において$ D = \{ \{ (S_1, T_{11}), \cdots, (S_1, T_{1n}) \}, \cdots, \{ (S_1, T_{m1}), \cdots, (S_1, T_{mn}) \} \} $である。$ R $は$ N $を除く表全体に対応し、$ D $は$ T_{ij} $からなる表本体に対応する。

例えば、巡回群$ C_3 $の演算表は次のような関係表として格納される:

$ MultTableOfC3 $
$ \mathrm{arg1} $	$ \mathrm{arg2} $	$ \mathrm{product} $
$ 0 $	$ 0 $	$ 0 $
$ 0 $	$ 1 $	$ 1 $
$ 0 $	$ 2 $	$ 2 $
$ 1 $	$ 0 $	$ 1 $
$ 1 $	$ 1 $	$ 2 $
$ 1 $	$ 2 $	$ 0 $
$ 2 $	$ 0 $	$ 2 $
$ 2 $	$ 1 $	$ 0 $
$ 2 $	$ 2 $	$ 1 $

関係表では縦軸と横軸を取ることができず、横軸しか存在しないため、群の演算表を関係表にする場合、群の位数の2乗の行数が必要となる。

SQLの実装には直接必要ないが、正規形の話をしたくなったので書く。その前に関数従属性の話をしないといけない。それに加えて主キーの話をしないといけない。その前に候補キーの話をしないといけない。その前にスーパーキーの話も入れておこう。

関数従属性

$ S $の部分集合を2つ取り、$ S_I = \{S_{i_1}, \cdots, S_{i_v} \}, S_J = \{S_{j_1}, \cdots, S_{j_w} \} $とする。このとき、$ S_J $が$ S_I $に関数従属しているとは、次のような2つのタプル$ T_A = \{ (S_1, T_1), \cdots, (S_n, T_n) \}, T'_A = \{ (S'_1, T'_1), \cdots, (S'_n, T'_n) \} $が存在しないことである:

$$ (S_{i_1} = S'_{i_1} \wedge \cdots \wedge S_{i_v} = S'_{i_v}) \wedge ( S_{j_1} \neq S'_{j_1} \vee \cdots \vee S_{j_w} \neq S'_{j_w} ) $$

また、$ S_I $が一元集合であるとき、その集合をその元と同一視し、「$ S_J $は$ S_{i_1} $に関数従属している」のように表現することがある。$ S_J $、もしくは$ S_I $と$ S_J $の両方が一元集合であるときも同様の同一視を行う。

スーパーキー

$ S $がその部分集合$ A $に関数従属しているとき、$ A $をその関係表のスーパーキーという。その定義から、$ S $自身はスーパーキーである。

候補キー

$ S $の部分集合$ A $がスーパーキーであるが、どんな$ A $の真部分集合もスーパーキーではないとき、$ A $をその関係表の候補キーという。

主キー

候補キー$ A = {A_1, \cdots, A_v} $であって、

$$ \exists T_A \in T, \exists w < v, (A_w, t) \in T_A \wedge t = \mathrm{NULL} $$

ではない(この制約を非NULL制約という)ものを関係表ごとに一つ固定し、それを主キーと呼ぶ。主キーになり得る候補キーであって主キーに選ばれなかったものを代理キーという。

関係表の(多くの場合左端の)列に行の通し番号が保存されている場合、その通し番号のみからなる一元集合が主キーとなる場合が多い。

また、主キーを明示するため、関係スキーマを列挙する際(表による表現も含む)に、主キーの元に下線を引くことがある。

上の$ C_3 $の演算表の例では、どの2列の組も主キーになりうる。しかし、主キーは「行を一意に識別するためのデータ」という意味合いがあるため、$ \{ \mathrm{arg1}, \mathrm{arg2} \} $が主キーに選ばれる。この場合、関係スキーマは

$$ \underline{\mathrm{arg1}}, \underline{\mathrm{arg2}}, \mathrm{product} $$

と表現される。データベースエンジニアは数学者ではないので、集合を表す$ \{ \} $は一般的に使用されない。

第1正規形

第1正規形とは、上の定義の全てのタプルに対する全ての$ T_i $が、数列や関係表といった繰り返し要素を持たないことである。といっても、ZFCでは全てが集合なので、$ T_i $をどう解釈するかにも依存する。

第2正規形

第2正規形には、主キーの概念を必要とする。

関係表が第2正規形であるとは、全ての関係スキーマの元が、主キーの元であるか、もしくは「主キーに関数従属するが、主キーのどの真部分集合にも関数従属しない」ことである。

たとえば、関係スキーマが$ \underline{X}, \underline{Y}, F, G, H $であり、各タプルが$ \{ x_i, y_j, f(y_j), g(x_i, y_j), h(x_i, y_j) \} $で与えられるような関係表が存在するとき、$ F $が$ \{ Y \} $に関数従属するため第2正規形ではない。

これを第2正規形にするためには、この関係表を$ \underline{X}, \underline{Y}, G, H $と$ \underline{Y}, F $に分割すればよい。現実における会社で発生しうる例であるが、$ X $が注文番号で$ Y $が商品番号に対応するとき、前者は注文された商品の一覧、後者は注文そのものの一覧に対応する^[1]。

第3正規形

ボイス・コッド正規形

第4正規形

第5正規形

SQL

凍結しました。

結論