PR

リレーショナル・データベース(RDB)のデータ構造やSQL命令による様々なデータ操作については,多くの人が知っていることだろう。しかしRDB技術の根底にある「集合論」を詳しく語れる人は少ないはずだ。集合論とRDBの結びつきを理解すれば,RDBの本質が見えてくる。

 ITエンジニアの皆さんなら,米IBMサンノゼ研究所に在籍していたE.F.コッド博士(Edger.F.Codd,1923~2003)をご存知だろう。コッド博士は1970年,「A Relational Model of Data for Large Shared Banks(大規模共有データバンクのためのリレーショナル・モデル)」という有名な論文を発表した。現在の「リレーショナル・データベース(RDB)」(「関係データベース」とも呼ぶ)は,この論文が起源となって誕生したものだ。

 コッド博士が数学の「集合論」を基に,表を使うRDBの仕組みを考案したことはよく知られている。だが,なぜ集合論とRDBが結びつくのかを意識したことがある人は,それほど多くはないのではないだろうか。

 集合論とRDBの結びつきを知れば,これまで以上にRDBの理解が深まることは間違いない。なぜなら,集合論はRDBの「データ構造」と「データ操作」の両方に深くかかわっているからだ。「データ構造」とはデータをどのような形式で持つかを指し,「データ操作」とは必要なデータを抽出するための演算方法を指す。以下で,RDBのこれらの機能を司る集合論について詳しく見ていこう。

同じ属性を持つ要素の集まり

 学生時代に数学の授業で集合論を学んだ人は多いことと思うが,念のため,集合論の基礎を復習しておこう。

 「集合」とは簡単に言えば,同じ属性を持つデータの集まりのことである。集合論では1つひとつのデータのことを「要素」または「元(げん)」と呼ぶ。集合を数式で示す場合は,集合全体をアルファベット1文字で表し,式の右辺を「{ 」と「 }」で囲んで要素を列挙する。

 例えば,「1桁の自然数」という属性を持つ要素の集合を「X」とすれば,数式は次のように表せる。

X={ 1,2,3,4,5,6,7,8,9 }

 集合を円で表して図示する場合もよくある。このような図を「ベン図(Venn dia-gram)」と呼ぶ。図1は,集合Xをベン図で表したものだ。円の中に集合Xの要素(1,2,3,4,5,6,7,8,9)が格納されていると考える。円の外側は,集合Xの属性に合わない要素の集合であり,これを「補集合」と呼ぶ。Xの補集合は,「XC」と表す。添え字のcは,「complement(補集合)」という意味である。

図1●「集合」と「補集合」を表したベン図
図1●「集合」と「補集合」を表したベン図
同じ属性を持つデータ(「要素」または「元」と呼ぶ)の集まりを「集合」と呼ぶ。「補集合」とはその集合以外のデータの集まりを指す

「集合」同士を演算する

 集合論では,集合同士で様々な演算を行うことができる。これを「集合演算」と呼ぶ。集合演算によって,複数の集合に共通する要素を抽出したり,すべての要素を抽出したりすることが可能だ。演算結果も集合になる

 集合演算には,「和(結び)」,「差」,「積(交わり)」,「直積」という4つの種類がある。それぞれ「∪」,「-」,「∩」,「×」という演算記号を使って表す。例えば,集合Xと集合Yの和なら,「X∪Y」となる。見た目の形状から,∪は「カップ(cup)」,∩は「キャップ(cap)」と呼ぶ。

 図2に示したように,和,差,積の3つの集合演算は,ベン図で表すと分かりやすい。直積はベン図で表すことができないため,「表」を使って演算結果を示すことになる(詳しくは後述する)。

図2●ベン図で表した「集合演算」の例
図2●ベン図で表した「集合演算」の例
集合演算には「和(結び,記号は∪)」,「差(記号は-)」,「積(交わり,記号は∩)」,「直積(記号は×)」の4種類がある。和,差。積はベン図で表すと理解しやすい
[画像のクリックで拡大表示]

 「集合」とは簡単に言えば,同じ属性を持つデータの集まりのことである。集合論では1つひとつのデータのことを「要素」または「元(げん)」と呼ぶ。集合を数式で示す場合は,集合全体をアルファベット1文字で表し,式の右辺を「{ 」と「 }」で囲んで要素を列挙する。

 例えば,「1桁の自然数」という属性を持つ要素の集合を「X」とすれば,数式は次のように表せる。

集合演算にも基本法則がある

 連載の第4回で取り上げたブール代数の論理演算を覚えているだろうか。集合演算でも論理演算と同様,「交換法則」や「結合法則」などの基本法則が成り立つ。それだけではない。和と積の演算を相互に変換する「ド・モルガンの法則」も成り立つのだ。

 なぜ,集合演算でも論理演算の法則が成り立つのだろうか。それは,そもそも論理演算とは,「真(1)」の集合と「偽(0)」の集合に対する集合演算だからだ。以下に,集合演算における基本法則の具体例を示しておこう。

【交換法則】
X∪Y=Y∪X
X∩Y=Y∩X

【結合法則】
X∪(Y∪Z)=(X∪Y)∪Z
X∩(Y∩Z)=(X∩Y)∩Z

【分配法則】
X∪(Y∩Z)=(X∪Y)∩(X∪Z)
X∩(Y∪Z)=(X∩Y)∪(X∩Z)

【ド・モルガンの法則】
(X∪Y)C=XC∩YC
(X∩Y)C=XC∪YC

 集合演算でこうした法則が成り立つことも,ベン図で表せば容易に確認できる。例えば,「(X∪Y)C=XC∩YC」というド・モルガンの法則なら,図3のようにベン図で示すことができ,「XとYの結びの補集合」と「Xの補集合とYの補集合の交わり」が同じ結果になることが分かる。

図3●集合演算でも「ド・モルガンの法則」が成り立つ
図3●集合演算でも「ド・モルガンの法則」が成り立つ
集合演算でも,論理演算のド・モルガンの法則( (X∪Y)C=XC∩YC,( X∩Y)C=XC∪YC )が成り立つ。「(X∪Y)C」と「XC∩YC」をベン図で表してみると,それらの結果が同じになることが分かる