利用者:Nayuta Ito/無限データベース

ここでは、表が無限個あるデータベースや、無限の列または行を持つ関係表について考える。また、それらを扱うための無限長のSQLについても扱う。「無限」は可算無限とは限らず、非可算無限を扱うこともある。

正規形

任意の関係表は第2正規形にできる。以下でこのことを示す。

主キーの集合を\( A \)とし、\( A \)の冪集合\( \mathfrak{P}(A) \)の各元ごとに主キーがその元であるような関係表を用意する。

主キーでない各属性に対し、「その属性が完全関数従属しているような\( \mathfrak{P}(A) \)の元」を(複数あるときは任意に1つ選んで)とり、その元が主キーとなっているような関係表にその属性を追加する。この操作は列が無限にあってもwell-definedである。

\( A \)そのものが主キーとなっている関係表を除き、主キーしかない関係表を削除する。

以上により得られた関係表の集まりは、全ての関係表に部分的関数従属関係が存在せず、したがって第2正規形である。

この構成法から、可算無限個の列が主キーとなっている場合、第2正規形にするために連続体濃度の関係表が構成されることがあることがわかる。

まだ解いていない問題

関係表\( T(\underline{C_{-1}}, \underline{C_0}, C_1, C_2, \cdots) \)に対し、

$$ C_1 \rightarrow C_0, C_2 \rightarrow C_1, \cdots $$

という無限の関数従属性が存在するとき、これをボイス・コッド正規形にできるか?

選択公理

以下に選択公理と同値な命題を示す。

テーブル\( T_1, T_2, \cdots \)(非可算でもよい)が空でないとする。このとき、

SELECT COUNT(*) FROM \( T_1, T_2, \cdots \)

は1行以上のレコードを返す。

実数

全ての\( i \in \mathbb{N} \backslash \{ 0 \} \)に対し、次のテーブルが用意されている:

\( T_i \)

D

\( 0 \)

\( 1 \)

このとき、次のSQLを実行すると、\( 0.00111\cdots = 0.01000 \cdots \)のような重複込みの\( 0 \)以上\( 1 \)以下の全ての\( 2 \)進実数が得られる:

SELECT FIRST="0.", * FROM \( T_1, T_2, \cdots \)

重複なしで取り出してみる。

SELECT FIRST="0.", * FROM \( T_1, T_2, \cdots \) WHERE NOT ((\(T_1\)=1 AND \(T_2\)=1 AND \(T_3\)=1 AND \( \cdots \)) OR (\(T_2\)=1 AND \(T_3\)=1 AND \( \cdots \)) OR (\(T_3\)=1 AND \( \cdots \)) OR \( \cdots \))

このSQLの長さはω^2である。

1/2以上1/4未満の実数だけを取り出してみる。

SELECT FIRST="0.", * FROM \( T_1, T_2, \cdots \) WHERE \(T_1\) = 1 AND \(T_2\) = 0 AND NOT ((\(T_1\)=1 AND \(T_2\)=1 AND \(T_3\)=1 AND \( \cdots \)) OR (\(T_2\)=1 AND \(T_3\)=1 AND \( \cdots \)) OR (\(T_3\)=1 AND \( \cdots \)) OR \( \cdots \))

「\(T_1\) = 1 AND \(T_2\) = 0」は無限個の無限長の条件の前後どちらに置いてもよい。

SQL

\( \mathbb{N} \)

id

\( 0 \)

\( 1 \)

\( 2 \)

\( \vdots \)

SELECT id FROM \( \mathbb{N} \) WHERE id * id = 9;

これで自然数に対する方程式が解ける。