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

以上の制約を、以下の具体例を用いて考えてみましょう。酵母２ハイブリッドアッセイの実験結果を、3つのテーブルを用いてデータベース化します。
{|
|
{| class="wikitable"
|+ "Bait" table of proteins
|-
! id || name || length || ... other attributes
|-
| 11 || ProA || 120 || ...
|-
| 21 || ProB || 250 || ...
|-
| 33 || ProC || 160 || ...
|}
|
{| class="wikitable"
|+ "Prey" table of proteins
|-
! id || name || length || ... other attributes
|-
| 9 || ProD || 120 || ...
|-
| 21 || ProB || 250 || ...
|-
| 43 || ProF || 250 || ...
|}
|
{| class="wikitable"
|+ "Binding" table of yeast 2-hybrid assays
|-
! bait || prey || experiment || ... other attributes
|-
| 11 || 9 || assay A  || ...
|-
| 11 || 21 || assay B  || ...
|}
|}

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

SQLではテーブルを以下のように作成します。
<pre>
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)
 :
</pre>

PRYMARY KEY, FOREIGN KEY という部分に注目してください。各テーブルにPRIMARY KEYを配置し、各レコードのID番号とします。テーブル間で参照する際の整合性を保つために、FOREIGN KEYを設定します。

==関係代数==
関係データベースにおける問い合わせの数学的モデルが関係代数 (relational algebra) です。
基本演算子は以下の5つです。
<center>
selection, projection, union, cross-product, difference
</center>

===selection (&sigma;), projection (&pi;)===
選択 (selection), 射影　(projection) はそれぞれ、行を選択する操作と列を絞り込む操作に対応します。
選択における選択条件は数値の大小比較や論理関数 (&and; や &or;) で表現します。射影では属性名を指定します。
;例
{|
! 演算内容 || 関係代数による表現 || 結果 || SQL による問い合わせ
|-
| 長さが200以上のBaitタンパク質を求める
| &sigma;<sub>length > 200</sub>(Bait)
|
{| class="wikitable"
|-
! id || name || length
|-
| 21 || RelB || 250
|}
|
<pre>
SELECT *
FROM Bait B
WHERE B.length > 200
</pre>

|-
| idが5以降のPreyタンパク質の長さを求める
| &pi;<sub>length</sub>( &sigma;<sub>id > 5</sub> (Prey) )
|
{| class="wikitable"
|-
! length
|-
| 120
|-
| 250
|}
|
<pre>
SELECT DISTINCT P.length
FROM Prey P
WHERE P.id > 5
</pre>
|}
SQLで DISTINCT 指定をすると、結果の表から同一の値を除いてくれます。

===union (&cup;), intersection(&cap;), set-difference (&minus;), cross product (&times;)===
集合演算は一般の論理関数に全くおなじで、和集合、積集合、差集合、直積をつかいます。直積は cartesian product とも呼び、指定された表に含まれる行の全ての組み合わせを生成します。

{|
! 演算内容 || 関係代数 || 結果
|-
| 和
| Prey &cup; Bait
|align="center"|
{| class="wikitable"
! id || name || length || ... others
|-
| 11 || ProA || 120 || ...
|-
| 21 || ProB || 250 || ...
|-
| 33 || ProC || 160 || ...
|-
| 9 || ProD || 120 || ...
|-
| 43 || ProF || 250 || ...
|}
|-
| 積 || Prey &cap; Bait
|align="center"|
{| class="wikitable"
! id || name || length || ... others
|-
| 21 || ProB || 250 || ...
|}
|-
| 差
| Bait &minus; Prey
|align="center"|
{| class="wikitable"
! id || name || length || ... others
|-
| 11 || ProA || 120 || ...
|-
| 33 || ProC || 160 || ...
|}
|-
| 直積
| Bait &times; Binding
|align="center"|
{| class="wikitable"
! id || name || length || ... others || bait || prey || experiment || ... others
|-
| 11 || ProA || 120 || ... || 11 || 9 || assay A  || ...
|-
| 21 || ProB || 250 || ... || 11 || 9 || assay A  || ...
|-
| 33 || ProC || 160 || ... || 11 || 9 || assay A  || ...
|-
| 11 || ProA || 120 || ... || 11 || 21 || assay B  || ...
|-
| 21 || ProB || 250 || ... || 11 || 21 || assay B  || ...
|-
| 33 || ProC || 160 || ... || 11 || 21 || assay B  || ...
|}
|}

===join ( <big>&infin;</big> ) ===
結合 (join) 演算は、理論的には直積集合からの選択および射影演算で実現でき、たいへん重要です。以下の式がその定義です。（本当は三角形の蝶ネクタイ型で演算を表現するのですが、HTMLでよい記号がないのでここでは無限大の記号を使っています。）つまり、直積したテーブルからある条件で組を抜き出す演算のことです。
<center>
R <big>&infin;</big><sub>c</sub> S = &sigma;<sub>c</sub> (R &times; S)
</center>
結合演算にはいくつかのバリエーションがあります。
;Natural join
:演算の際に条件を指定せず、テーブル間で共通する全項目が一致する場合に結合します。joinさせる属性を指定しない方法なので、実用上は使われません。
;Equi join
:演算の際に属性名を指定し、その属性項が一致する場合に結合します。
{|
! 関係代数 || 結果
|-
| Bait &infin;<sub>id=bait</sub> Binding
|
{| class="wikitable"
! id || name || length || ... others || prey || experiment || ... others
|-
| 11 || ProA || 120 || ... ||  9 || assay A  || ...
|-
| 11 || ProA || 120 || ... || 21 || assay B  || ...
|}
|}
;Condition join
:演算の際に属性名だけでなく他の結合条件も指定し、その条件が満たされる場合に結合します
{|
! 関係代数 || 結果
|-
| Bait &infin;<sub>id=bait and prey > 10</sub> Binding
|
{| class="wikitable"
! id || name || length || ... others || prey || experiment || ... others
|-
| 11 || ProA || 120 || ... || 21 || assay B  || ...
|}
|}
;Semi join
:条件が満たされたデータだけ返しますが、表どうしの結合をおこないません
{|
! 関係代数 || 結果
|-
| Bait ∝<sub>id=bait</sub> Binding<ref>Semijoin のオペレータは、三角形の蝶ネクタイ型から、縦棒部分を除いた記号で表現します。HTMLでは表示できないので、比例関係に用いる記号で代用しています。</ref>
|
{| class="wikitable"
! id || name || length || ... others
|-
| 11 || ProA || 120 || ...
|}
|}
この例では、Baitテーブルの組のうち、Bindingテーブルと共通項があるものだけが抜き出されています。
;Outer join
:結合できないデータに関しては、足りない部分をNULLで埋めた表を返します。
{|
! 関係代数 || 結果
|-
| Bait ∝<sub>id=bait</sub> Binding
|
{| class="wikitable"
! id || name || length || ... others || prey || experiment || ... others
|-
| 11 || ProA || 120 || ... || 9 || assay A  || ...
|-
| 11 || ProA || 120 || ... || 21 || assay B  || ...
|-
| 21 || ProB || 250 || ... || NULL || NULL  || NULL ...
|-
| 33 || ProC || 160 || ... || NULL || NULL ||  NULL ...
|}
|}

==関係論理==

関係代数がデータ処理を手続き的に記述するのに対し、関係論理では同じ処理を論理式を用いて宣言的に記述します。
テーブルの属性は T.id のように参照します。

;例
* 長さが 200 以上で bait にも prey にも出てくるタンパク質
<center>
{ A | &exist;B &isin; Bait, &exist;P &isin; Prey ( (A.id = B.id) &and; (B.name = P.name) &and; B.length >= 200 ) }
</center>
{ A | A に関する制約式 } という形を、制約を満たす A を含む集合と考えます。


===表記法===
クエリは { ''T'' | ''p(T)'' } の形で記述します。''T'' は組変数 (tuple variable)、 ''p(T)'' が以下で説明する論理式です。
演算子として '''op''' = {<, >, =, &ge;, &le;, &ne;} を用意します。
アトミック式とは以下のいずれかです。
* 組変数 R, S &isin; テーブル
* R.a '''op''' S.b
* R.a '''op''' ''constant'' または ''constant'' '''op''' R.a
関係論理式とはアトミック式 p や q を論理記号でつないだものです。
* 任意のアトミック式 p, q
* &not; p, p &and; q, p &or; q, p &rarr; q
* &exist; R ( p (R) ), &forall; R ( p (R) )

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

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

;関係完備となる5オペレータ
* selection (&omega;)
* projection (&pi;)
* set union (&cup;)
* set intersection (&cap;)
* cross product (&times;)

Join 演算は cross product と selection を組み合わせて定義されます。set difference (&minus;) は A &minus; B = A - (A &cap; B) と定義できます。関係完備となるオペレータは上記の5つに限ったわけではありません。Set differenceを入れてintersectionを抜いた　selection (&omega;), projection (&pi;), set union (&cup;), set difference (&minus;), cross product (&times;) でも関係完備になります。しかしデータを組み合わせる cross product (&times;) や選び出す selection (&omega;), projection (&pi;) を無くすことはできません。

;注
<references/>