Aritalab:Lecture/Database/Relational

関係データベース

関係データベースは、Edgar Coddが1970年に発表した関係モデルに基づいており、レコードが行にあたる表形式でデータを記述します。行にあたる各データを組 (tuple) と呼びます。表のことを関係変数とよび、列見出しを属性 (attribute) と呼びます。各表には必ず行を一意に特定できるキー (key) を持たせます。（ここでは関係変数よりも「表」という言葉を用います。）

エクセル表との違い

関係データベースを正しく機能させるため、テーブルが満たすべき重要な制約があります。データの整合性 (integrity) を保つ仕組みなので、まとめて整合性制約 (integrity constraint) と呼ばれます。

一意性制約 (unique constraint)

各テーブルは、行を一意に特定できる属性（またはその組みあわせ）を持たなくてはなりません。

主キー制約 (primary key constraint)

行を一意に特定できる属性（またはその組みあわせ）を主キーとして指定します。主キーは NULL 値をとれません。

属性全てをあわせれば行を特定できますが（一意性制約より）、それでは冗長です。可能な限り少ない属性数で行を特定するように主キーを設定し、通常はID番号のような更新されにくい属性を主キーに設定します。主キーになりうる属性を候補キー (candidate key)、主キーを部分集合として含む属性の集合をスーパーキー (super key) といいます。

参照整合性制約 (reference integrity constraint)

テーブル間で同じデータを共有する際、テーブル間でデータの不整合が起きないようにします。外部キー (foreign key) として設定される属性値は、他のテーブル中に存在しなくてはなりません。

関係代数

関係代数の基本演算子は以下の5つです。

selection, projection, union, cross-product, difference

これらの働きをみるのに以下の具体例を用います。

Instance P1 of proteins id protein name length 11 RelA 120 21 RelB 250 33 RelC 160

Instance P2 of proteins id protein name length 9 RelD 120 21 RelB 250 43 RelF 250

Instance R of binding id id experiment 11 9 A 11 21 A

selection (σ), projection (π)

選択 (selection), 射影　(projection) はそれぞれ、行を選択する操作と列を絞り込む操作に対応します。 選択における選択条件は数値の大小比較や論理関数 (∧ や ∨) で表現します。射影では属性名を指定します。

例

σlength > 200(P1) id protein name length 21 RelB 250

πid,length(P1) id length 11 120 21 250 33 160

union (∪), intersection(∩), set-difference (−), cross product (×)

集合演算は一般の論理関数に全くおなじで、和集合、積集合、差集合、直積をつかいます。直積は cartesian product とも呼び、指定された表に含まれる行の全ての組み合わせを生成します。

join

結合 (join) 演算は、理論的には直積集合からの選択および射影演算で実現できますがたいへん重要な演算です。以下の式がその定義です。

R ∞_c S = σ_c (R × S)

結合演算にはいくつかのバリエーションがあります。

Natural join

演算の際に条件を指定せず、テーブル間で共通する全項目が一致する場合に結合します

Equi join

演算の際に属性名を指定し、その属性項が一致する場合に結合します

Condition join

演算の際に属性名と結合条件まで指定し、その条件が満たされる場合に結合します

Semi join

条件が満たされたデータだけ返しますが、表どうしの結合をおこないません

Outer join

結合できないデータに関しては、足りない部分をNULLで埋めた表を返します

関係論理

関係代数がデータ処理を手続き的に記述するのに対し、関係論理では宣言的に記述します。

表記法

クエリは { T | p(T) } の形で記述します。T は組変数 (tuple variable)、 p(T) が以下で説明する論理式です。 演算子として op = {<, >, =, ≥, ≤, &neq;} を用意します。 アトミック式とは以下のいずれかです。

• 組変数 R, S ∈ Relation (テーブルのこと）
• R.a op S.b
• R.a op constant または constant op R.a

論理式はアトミック式 p や q を論理記号でつないだものです。

• 任意のアトミック式 p, q
• ¬ p, p ∧ q, p ∨ q, p → q
• ∃ R ( p (R) ), ∀ R ( p (R) )

関係完備

関係論理は否定演算を含むため、安全でない（結果のサイズが無限大になる）問い合わせを書けます。例えば { S | ¬ (S ∈ Rel) } という問い合わせには答えられない。テーブル内に存在するデータのみを用いて計算でき、存在するデータのみで構成される答えに内容を絞ってよければ、関係論理であらわせる問い合わせの表現力は、関係代数のそれに一致します。

ある問い合わせ言語が関係代数で記述できる問い合わせをすべて表現できるとき、その言語は関係完備 (relationally complete) といいます。