Aritalab:Lecture/Database/Relational

Revision as of 14:30, 14 September 2011

関係データベース

関係データベースは、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) として設定される属性値は、他のテーブル中に存在しなくてはなりません。

以上の制約を、以下の具体例を用いて考えてみましょう。酵母２ハイブリッドアッセイの実験結果を、3つのテーブルを用いてデータベース化します。

• 一意性制約を満たすために、"Bait"テーブルと"Prey"テーブルでは id という属性を用いています。タンパク質名を id の代わりに用いてもよいかもしれませんが、万一、同じ綴り方をするタンパク質で配列が異なる場合に備えたほうが良いからです。"Binding"テーブルでは、結合するタンパク質のペアによって一意性制約が保たれています。
• "Bait"テーブルと"Prey"テーブルの主キーは id です。"Binding"テーブルの主キーは { bait, prey } です。
• "Binding"テーブルに登録される bait, prey 番号は、それぞれ "Bait", "Prey" テーブルに存在しなくてはなりません。そのため、両方の属性を外部キーとしてそれぞれ"Bait", "Prey" テーブルと関連付けます。

SQLではテーブルを以下のように作成します。

CREATE TABLE Bait (id   CHAR(10), name CHAR (20), length INTEGER,
                 PRIMARY KEY (id))
CREATE TABLE Prey (id   CHAR(10), name CHAR (20), length INTEGER,
                 PRIMARY KEY (id))
CREATE TABLE Rel (bait CHAR(10), prey CHAR(10), experiment CHAR(50),
                 PRIMARY KEY (bait, prey),
                 FOREIGN KEY (bait) REFERENCES Bait (id),
                 FOREIGN KEY (prey) REFERENCES Prey (id))
 :
INSERT INTO Bait (id, name, length) VALUES (11, 'ProA', 120)
INSERT INTO Bait (id, name, length) VALUES (21, 'ProB', 250)
INSERT INTO Bait (id, name, length) VALUES (33, 'ProC', 160)
 :

PRYMARY KEY, FOREIGN KEY という部分に注目してください。

関係代数

関係データベースにおける問い合わせの数学的モデルが関係代数 (relational algebra) です。 基本演算子は以下の5つです。

selection (σ), projection (π)

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

例

SELECT *
FROM Bait B
WHERE B.length > 200

SELECT DISTINCT P.length
FROM Prey P
WHERE P.id > 5

SQLで DISTINCT 指定をすると、結果の表から同一の値を除いてくれます。

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

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

join ( ∞ )

結合 (join) 演算は、理論的には直積集合からの選択および射影演算で実現できますがたいへん重要な演算です。以下の式がその定義です^[1]。つまり、直積したテーブルからある条件で組を抜き出します。

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

Natural join

演算の際に条件を指定せず、テーブル間で共通する全項目が一致する場合に結合します。joinさせる属性を指定しない方法なので、実用上は使われません。

Equi join

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

Condition join

演算の際に属性名だけでなく他の結合条件も指定し、その条件が満たされる場合に結合します

Semi join

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

この例では、Baitテーブルの組のうち、Bindingテーブルと共通項があるものだけが抜き出されています。

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) といいます。

1. ↑ 本当は三角形の蝶ネクタイ型で演算を表現するのですが、HTMLでよい記号がないので無限大の記号を使っています。
2. ↑ Semijoin のオペレータは、三角形の蝶ネクタイ型から、縦棒部分を除いた記号で表現します。HTMLでは表示できないので、比例関係に用いる記号で代用しています。