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

このプロジェクトは凍結しました。副問合せとかEXISTSとかのSELECTが外側の束縛変数参照するやつどうやって実装すればいいんですか...

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

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} ) $$

第1正規形

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

第2正規形

第3正規形

ボイス・コッド正規形

第4正規形

第5正規形

SQL

凍結しました。

結論