利用者:Nayuta Ito/プロジェクト・SQL

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

~~この記事では、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) \} $の形の集合である。

[ここに関係表のvisualizationを挿入]

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 $がその部分集合$ 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制約という)ものを関係表ごとに一つ固定し、それを主キーと呼ぶ。主キーになり得る候補キーであって主キーに選ばれなかったものを代理キーという。

関係表は多くの場合何らかの表として使われる(だから関係「表」というのである)。表に行の通し番号が与えられている場合、その通し番号のみからなる一元集合が主キーとなる場合が多い。

第1正規形

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

第2正規形

第3正規形

ボイス・コッド正規形

第4正規形

第5正規形

SQL

凍結しました。

結論