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

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

正規形

第1正規形にできるのは自明として、第2正規形にできない無限関係表とかありそう

選択公理

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

テーブル\( 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」は無限個の無限長の条件の前後どちらに置いてもよい。