関係データベースについて
本項では，関係データベースの数学的基礎について解説します．基本的には，関係代数（relational algebra）と関係論理（relational logic）が関係データベースの数学的基礎となります．なお，関係代数と関係論理は，等価な理論であることが知られています．両者の違いは，関係代数は問合せを手続き的に記述するが，関係論理では問合せを宣言的に記述する，というところです．
● ドメインとタプル
さて，関係データベースの理論を展開するためには，まず，関係の概念を理解しなくてはなりません．関係とは，複数の実体の間に成立する性質といえます．よって，関係を定義するためには，ドメイン（domain）が必要です．なおドメインは，｢定義域｣と呼ばれることもあります．ここで，ドメインは，値の集合とします．
いま，n個のドメインD1，D2，…，Dnを考えます．ここで，各Diはすべて異なる集合である必要はありません．ドメインD1，D2，…，Dnの直積（direct product）は，D1×D2×…Dnと書かれ，次のように定義されます．
D1×D2×…Dn＝{（d1，d2，…，dn）｜d1∈D1，d2∈D2，…，dn∈Dn}
なお，直積はデカルト積（Cartesian product）と呼ばれることもあります．また，D1＝D2＝…＝Dn＝Dの場合，これらの直積はDnと書かれます．そして，直積D1×D2×…×Dnの要素（d1，d2，…，dn）をタプル（tuple）と呼び，属性の組を表しています．
◇例題１
いま，ドメインD1，D2，D3を，
D1＝{赤間，鈴木}，D2＝{10，20，30}，D3＝{CS，IS}
とすると，直積D1×D2×D3は，
{（赤間，10，CS），（赤間，10，IS），（赤間，20，CS），（赤間，20，IS），
（赤間，30，CS），（赤間，30，IS），（鈴木，10，CS），（鈴木，10，IS），
（鈴木，20，CS），（鈴木，20，IS），（鈴木，30，CS），（鈴木，30，IS）}
となります．
次に，関係（relation）を定義します．ドメインD1，D2，…，Dn上の関係Rは，直積D1×D2×…×Dnの有限部分集合です．ここで，Di（1 ≦ i ≦ n）はRのi番目のドメイン，nはRの次数（degree），Rを構成するタプルの数をRの濃度（cardinality）と呼びます．一般に次数nの関係は，n項関係（n-ary relation）と呼ばれます．とくに，n＝1の場合は単項関係（unary relation），n＝2の場合は二項関係（binary relation）と呼ばれます．また，関係は空集合であってもよいのですが，この場合，関係はタプルを一つももたない関係と解釈されます．さらに，ドメインは理論的には無限集合であってもよいのですが，データベースで利用される関係としては有限集合のみが考慮されます．
◇例題2
いま，次のような関係データベース「成績」を考えましょう．
成績
 |
|
「成績」において，関係は次のように定義されます．
D1＝{学生の集合}，D2＝{科目の集合}，
D3＝{n｜0 ≦ n ≦ 100，nは整数である}
とすると，D1×D2×D3の有限部分集合Rは，
{（赤間，データベース，80），（鈴木，データベース，90），
（鈴木，人工知能，60），（増永，データベース，100），
（増永，人工知能，70），（山本，人工知能，50）}
となります．ここで，Rの次数は3，関係の濃度は6となります．
さて，データベース中のデータは，｢一貫性｣をもっていなければなりません．一貫性とは，矛盾せず意味があるということです．一貫性を保持するためには，一つの表には同じタプルがあってはなりません．関係データベースでは，特定なタプルを識別する属性を候補キー（candidate key）と呼びます．一つの表には複数のキーがある場合もありますが，その中から一つ任意に選んだものは，主キー（primary key）と呼ばれます．表「成績」では，候補キーは「学生名」と「科目」です．
なお，上記のように定義された関係は，次のような性質をもちます．まず，関係はタプルの集合ですが，タプルの順序と重複は数学的には意味がありません．すなわち，関係はタプルの集合として定義されるので，集合の性質から，複数の同一のタプルは排除されます．また，タプルの要素の順序も数学的には意味をもちません．しかし，実際のデータベースではタプルの要素の順序にはある程度実用上の意味をもたせることが多くあります．さらに，関係を定義するドメインは，これ以上細分化されない値から構成されます．すなわち，タプルの各要素は原子値でなくてはなりません．よって，各タプルは関係に関して十分な情報をもつことになります．たとえば，タプルの要素として日付の値を取るとすると，“2002-6-1”は原子値です．この値は，さらに，“2002”，“6”，“1”のように細分化することも考えられますが，日付としては“2002-6-1”が意味をもつ最小の値となります．
さて，関係データベースでは，フィールド名として属性名が用いられます．よって，属性名から関係を定義することもできます．いま，属性AiにドメインDi（1 ≦ i ≦ n）を対応させる関数domを，
dom（Ai）＝Di
と定義します．また，属性A1，A2，…，Anをもつ関係Rを，R（A1，A2，…，An）と書くことにします．なお，R（A1，A2，…，An）は関係スキーマ（relational schema）と呼ばれることもあります．すると関係R（A1，A2，…，An）は，dom（A1）×dom（A2）×…×dom（An）の有限部分集合として定義することができます．
● Coddの関係代数
Coddは参考文献5）で，関係データモデルとして関係代数を提案しましたが，後に参考文献6）で，関係代数の厳密な形式化を行いました．ここで代数とは，ある構造に関する操作を記述する理論です．よって関係代数は，関係データベースにおけるデータ操作を形式化できます．また前述したように，関係代数は操作的な理論であるため，実際のデータ操作のアルゴリズムと深く密接しています．Coddの関係代数は8個の代数演算から構成されますが，集合演算と関係モデルの基本演算に分類されます（表4）．
| 〔表4〕Coddの関係代数 | ||||||||||||||||||
|
これらの演算が関係代数の形式化としてすべて必要なわけではありません．じつは和，差，直積，選択，射影の5個の演算から残りの演算を定義することもできます．また，関係データベースの問い合わせ言語は少なくとも上記の関係代数と同等の記述力をもつ必要があり，このとき，問い合わせ言語は関係代数的に完全（relationally complete）であるといいます．
各演算の詳細を解説します．関係に関する演算を定義する前に，和両立（union compatible）といわれる概念を定義します．すなわち，二つの関係R（A1，…，An），S（B1，…，Bm）は，次の条件
(1) n＝m
(2) すべてのi（1 ≦ i ≦ n）について，dom（Ai）＝dom（Bi）である
を満足するならば，和両立といわれます．なお和両立は，関係演算の定義に不可欠な概念です．
和は，二つの関係の和集合を取る演算です．なお和，共通，直積はn個の関係に対しても定義可能です．いま，二つの和両立な関係をR，Sとすると，和R ∪ Sは，次のように定義される関係となります．
R ∪ S＝{t｜t ∈ R ∨ t ∈ S}
ここで，∨は宣言を表すので，tはRまたはSのタプルとなります．なお，和を取ると，タプルが重複する可能性があります．前述したようにタプルの重複は許されないので，重複するタプルは一つのタプルとなります．次の例題3は，関係データベースにおける和を図示しています．
◇例題3
いま，次のような研究プロジェクトに関する二つの関係データベース「学生」，「研究員」を考えます．
学生
|
|
研究員
|
|
すると学生 ∪ 研究員は，図4のようになります．
| 〔図4〕和 | ||||||||||
|
なお和においては，フィールド名が変更されています．二つの関係の和においては，これらの関係の各属性名のドメインは等しいのですが，フィールド名が同じである必要はありません．よって「学生名」と「研究員名」から「名前」という新しいフィールド名を付けています．また，和の結果，タプル（伊藤，1）は重複するので，一つが除去されています．
共通は，二つの和両立な関係の共通集合を取る演算です．R，Sの共通R ∩ Sは，次のように定義されます．
R ∩ S＝{t｜t ∈ R ∧ t ∈ S}
ここで∧は連言を表すので，tはRかつSのタプルとなります．よって，共通は空集合になる可能性があります．
◇例題4
二つの関係データベースを例題3と同じとすると，学生∩研究員は図5のようになります．ここでも，例題3と同様に，フィールド名を変更しなければなりません．
| 〔図5〕共通 学生∩研究員 | ||||
|
差は，二つの和両立な関係の差集合を取る演算です．R，Sの差R−Sは，次のように定義されます．
R−S＝{t｜t ∈ R ∧ t ∈/ S}
ここで，t ∈/ SはtがSの要素でないことを表しています．よってR−Sは，RにあるがSにないタプルです．
◇例題5
学生−研究員は，図6のようになります．
| 〔図6〕差 学生−研究員 | ||||||
|
直積は，二つの関係を乗ずる演算です．二つの関係R（A1，…，An），S（B1，…，Bm）の直積R×Sは，次のように定義されます．
R×S＝{（r，s）｜r ∈ R ∧ s ∈ S}
よって，m行i列のデータベースとn行j列のデータベースの直積は，（m×n）行（i+j）列のデータベースとなります．
◇例題6
いま，新たに関係データベース「代表者」を考えます．
代表者
|
|
そうすると，研究員×代表者は，図7のようになります．
| 〔図7〕直積 研究員×代表者 | ||||||||||||||||||||
|
なお直積の結果，部分的には意味のないデータベースが生成されることがあります．
次に，関係モデルに固有な演算について説明します．これらの演算は直観的なものですが，数学的な記述は複雑なものもあるので，注意が必要です．
まず選択は，ある条件を満足するタプルを選択する演算です．ここで選択条件としては，
(1) 属性Aと定数cの比較演算
(2) 二つの属性A，Bの比較演算
(3) 属性と計算式の比較演算
(4) 上記の比較演算の命題結合演算
を書くことができます．ここで比較演算子としては，<，>，≦，≧，＝，≠があります．また命題結合とは，命題を論理記号∧，∨，¬で結合した式です．(1)のタイプの条件は，A > 2.0の形であり，一般にAΘcとも書かれます．(2)のタイプの条件は，A＝Bの形であり，一般にAΘBとも書かれます．(3)のタイプの条件は，比較演算の項として計算式を書くことができるもので，A＝B＊2などがその例です．(4)のタイプの条件は，(1)，(2)，(3)の形の条件を論理記号で結合した論理式の形であり，A ≠ B ∧ A > B＊2などがその例です．
いま選択条件をFとすると，選択御目σF（R）は次のように定義されます．
σF（R）＝{t｜t ∈ R ∧ PF（t）}
ただし，PF（t）はタプルtが選択条件Fを満足するとき真になる述語です．なお，選択条件FがAΘBの場合，選択は制約（restriction）と呼ばれることもあります．
◇例題7
関係データベース「学生」で，プロジェクト番号が1より大きいタプルを選択します（図8）．
| 〔図8〕選択 σプロジェクト番号＞1（学生） | ||||||
|
射影は，関係から指定された属性を取り出し，新しい関係を生成する演算です．よって，関係データベースではフィールド（列）を減らす操作になります．なお，射影により同一なタプルが残る場合には1個のみにします．いま関係R（A1，…，An）において，集合{A1，…，An}の任意の部分集合をX＝{Ak1，Ak2，…，Akm}とします（1 ≦ k1 ≦ … ≦ km ≦ n）．そうすると，射影πXは，次のように定義されます．
πX（R）＝{u｜t ∈ R ∧μ t［X］}
ただし，t［X］はタプルtからXの属性Ak1，Ak2，...，Akmの値のみを残し，他の属性の値を削除したタプルです．
◇例題8
次のような関係データベース「講義」を考えます．
講義
|
|
ここで，「教員名」および「科目名」のフィールドを射影すると，図9のようになります．
| 〔図9〕射影 π教員名，科目名（学生） | ||||||||||
|
結合は，二つの関係からある条件を満足するタプルを取り出し，新しい関係を生成する演算です．関係RとSの条件Fによる結合R 
FSは，直積と選択により，次のように定義されます．
R FS＝σF（R×S）
ここで，Fが＝である場合は，とくに等結合（equi-join）といわれます．なお，等結合においては2個の等しい属性が現れますが，等しい属性を1個にする操作を含めた等結合は，自然結合（natural join）と呼ばれます．よって自然結合は，等結合と射影により記述することができます．
以降の内容は本誌を参照ください
Copyright 2002 赤間世紀