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

このプロジェクトは本当に完全に凍結しました。

現在の温度: -60℃

この記事では、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で十六元数が出てくることはないので、十六元数と記号が被る心配はない。

関係データベース

1. 関係データベース(リレーショナルデータベース、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正規形であるとは、第1正規形であって、かつ全ての関係スキーマの元が、主キーの元であるか、もしくは「主キーに関数従属するが、主キーのどの真部分集合にも関数従属しない」ことである。

たとえば、関係スキーマが\( \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 \)に分割すればよい。

次の例を考えよう:

全ての数学者と全ての論文にそれぞれ自然数の通し番号を与える。番号\( i \)が与えられた数学者を数学者\( i \)、番号\( j \)が与えられた論文を論文\( j \)と呼ぶことにする。

関係スキーマが\( \underline{\mathrm{Mathematician}}, \underline{\mathrm{Paper}}, \mathrm{Role}, \mathrm{Length} \)であるような関係表を考える。また、\( \{ (\mathrm{Mathematician}, i), (\mathrm{Paper}, j), (\mathrm{Role}, s), (\mathrm{Length}, t), \} \)がこの関係表のタプルであるとき、次のような条件を満たしているとする:

• 数学者\( i \)は論文\( j \)の筆者である。
• \( s \)は数学者\( i \)の論文\( j \)での役割を示す(英語などで書かれた)文字列である。
• \( t \)は論文\( j \)のページ数である。

このとき、この関係表は第2正規形ではない。なぜなら、\( \mathrm{Length} \)は一元集合\( \mathrm{Paper} \)に関数従属するからである。日常の言葉で言えば、「論文のページ数」は「数学者と論文の組」ではなく論文そのものに対する属性だからである。

これを第2正規形にするには、\( \underline{\mathrm{Mathematician}}, \underline{\mathrm{Paper}}, \mathrm{Role}, \mathrm{Length} \)を\( \underline{\mathrm{Mathematician}}, \underline{\mathrm{Paper}}, \mathrm{Role} \)と\( \underline{\mathrm{Paper}}, \mathrm{Length} \)の2つの関係表に分割すればよい。逆に、この2つの表を1つに戻すためには、\( \mathrm{Paper} \)の値、すなわち論文の番号が同じタプル同士を「結合させて」元の表のタプルを得ればよい。この操作は自然結合と呼ばれるが、それについては後で述べる。

第3正規形

関係表が第3正規形であるとは、第2正規形であって、かつ関係スキーマの任意の互いに交わらないどれもが空でない部分集合\( A, B, C \)が、「\( C \)は\( B \)に関数従属し、かつ\( B \)は\( A \)に関数従属する」という条件を満たさないことである。

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

これを第3正規形にするためには、この関係表を\( \underline{X}, \underline{Y}, F \)と\( \underline{F}, G \)に分割すればよい。

次の例を考えよう:

第2正規形の例で用意した論文の通し番号をここでも使う。関係スキーマを\( \underline{\mathrm{Paper}}, \mathrm{Date}, \mathrm{Weekday} \)とする。\( \{ (\mathrm{Paper}, j), (\mathrm{Date}, d), (\mathrm{Weekday}, w), \} \)がこの関係表のタプルであるとき、次のような条件を満たしているとする:

• \( d \)は論文\( j \)の発表日を示す(YYYY-MM-DDのような形式の)文字列である。
• \( w \)は\( d \)の曜日を表す整数である。月曜日を\( 1 \)とし、日曜日を\( 7 \)とする。

この関係表は第3正規形ではない。なぜなら、\( \mathrm{Weekday} \)は\( \mathrm{Date} \)に関数従属し、\( \mathrm{Date} \)は\( \mathrm{Paper} \)に関数従属するからである。日常の言葉で言えば、曜日は論文ではなく日付に対する属性だからである。

これを第3正規形にするには、\( \underline{\mathrm{Paper}}, \mathrm{Date}, \mathrm{Weekday} \)を\( \underline{\mathrm{Paper}}, \mathrm{Date} \)と\( \underline{\mathrm{Date}}, \mathrm{Weekday} \)の2つの関係表に分割すればよい。逆に、この2つの表を1つに戻すためには、第2正規形を第1正規形にしたときと同じように自然結合を行えばよい。

ボイス・コッド正規形

関係表がボイス・コッド正規形であるとは、任意の関係スキーマの部分集合\( A, B \)に対し、\( B \)が\( A \)に関数従属するならば、次の2つの少なくとも1つ(論理的OR)を満たしていることである:

• \( B \subset A \)
• \( A \)はスーパーキー

次の関係表を考える:

\( T \)

\( \underline{\mathrm{A}} \)	\( \underline{\mathrm{B}} \)	\( \mathrm{C} \)	\( \mathrm{D} \)
\( 1 \)	\( x \)	\( a \)	\( 2 \)
\( 1 \)	\( z \)	\( c \)	\( 3 \)
\( 2 \)	\( x \)	\( d \)	\( 1 \)
\( 2 \)	\( y \)	\( b \)	\( 1 \)
\( 2 \)	\( z \)	\( c \)	\( 4 \)
\( 3 \)	\( x \)	\( d \)	\( 4 \)
\( 3 \)	\( z \)	\( c \)	\( 5 \)

この関係表は第3正規形であるが、ボイス・コッド正規形ではない。なぜならば、\( \mathrm{B} \)は\( \mathrm{C} \)に関数従属する(\( \mathrm{C} \)列の値から\( \mathrm{B} \)列の値が一意に決まる)が、\( \{ \mathrm{C} \} \subset \{ \mathrm{B} \} \)ではなく、かつ\( \{ \mathrm{C} \} \)はスーパーキーではないからである。

これをボイス・コッド正規形にするためには、\( \{ \mathrm{A}, \mathrm{B} \} \)ではなく\( \{ \mathrm{A}, \mathrm{C} \} \)を主キーにすればよい。すると、第2正規形ですらなくなるため、第2正規形、第3正規形、ボイス・コッド正規形にする手続きを再帰的に行う。この手続きは有限回で終了し、最終的にボイス・コッド正規形が得られる。

私は第4・第5正規形をZFCに実装する驚くべき方法を発見したが、それを記すにはこの余白は狭すぎる。

SQL

SQLは次のような形式を持つ\( \mathbb{S}^* \)の元である。

$$ \mathrm{SELECT}\ L_1\ \mathrm{FROM}\ T\ [\mathrm{WHERE}\ \psi]\ [\mathrm{GROUP\ BY}\ L_2]\ [\mathrm{HAVING}\ \phi]\ [\mathrm{ORDER\ BY}\ L_3] $$

[]内はあってもなくてもよい。また、記号で察した通りSQLには述語論理が組み込まれている。変数を束縛する順はFROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BYらしい。p進大好きbotが匙を投げるレベル

結論

凍結しました。

SQLとは、以下のように定義される演算子である:

[ここにとんでもなく複雑かつ難解でifやforを連打することによりデータベースエンジニア、数学者だけでなくプログラマにも理解できないであろう論理記号の列および番号付きリストを悪用した複雑な制御構造を挿入]