関係代数演算
本日のリレーション
今回は下記の【サッカー部】，【テニス部】，【学部リスト】を対象に解説します． 【サッカー部】と【テニス部】は，学籍番号，氏名，学年，学部，また， 【学部リスト】は，学部，キャンパス，教員数で構成されています． また，下線は主キーを表しています．
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 |
| A003 | 内田弘 | 3 | 工学部 |
| B003 | 杉江弘子 | 3 | 人文学部 |
【サッカー部】
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| A002 | 岩村優 | 1 | 工学部 |
| B003 | 杉江弘子 | 3 | 人文学部 |
| C004 | 仙波あすか | 1 | 国際関係学部 |
【テニス部】
| 学部 | キャンパス | 教員数 |
|---|---|---|
| 工学部 | 春日井 | 30 |
| 人文学部 | 春日井 | 20 |
| 国際関係学部 | 名古屋 | 25 |
【学部リスト】
リレーションに対する演算
数値に対して足算や掛算などの四則演算が定義できるように， リレーションにも演算を定義することができます． リレーションに対する演算は4つの集合演算と， 4つの 関係代数演算（リレーショナル代数演算） で構成されています （商演算は殆ど用いることがないため，今回は割愛します）．
集合演算は下記の4つです．
- 和集合演算（Union Operation）
- 差集合演算（Set Difference Operation）
- 共通集合演算（Intersection Operation）
- 直積演算（Direct Product Operation）
関係代数演算は下記の4つです．
- 射影演算（Projection Operation）
- 選択演算(Selection Operation)
- 結合演算（Join Operation）
- 商演算（Division Operation）
これらの演算は，リレーショナルデータベースにおける検索や更新に該当し， 後に述べるSQLで表現が可能となっています． 今回はこれらの演算がどのように表現され， どのような結果になるかを学びましょう．
和両立
集合演算に含まれる和集合演算，差集合演算，共通集合演算を適用するには， リレーションが和両立と呼ばれる条件を満たしている必要があります．
和両立
リレーション$R_1$と$R_2$が下記の条件を満たすとき和両立であるという．
- $R_1$と$R_2$の次数が等しい
- $R_1$と$R_2$の対応するドメインが等しい
例えば，【サッカー部】と【テニス部】の関係を確認してみましょう． いずれのリレーションも4つの属性で構成されているため次数は4です． また，各属性のドメインは下記のように表現できると考えられ， リレーション間で対応がとれていると言えます． よって，【サッカー部】と【テニス部】は 和両立 であり， 和集合演算，差集合演算，共通集合演算が適用可能です．
$$D_1 = (A001, A002, A003, B003, C004)$$ $$D_2 = (岩城隼人,岩村優,内田弘,杉江弘子,仙波あすか)$$ $$D_3 = (1, 2, 3, 4)$$ $$D_4 = (工学部,人文学部,国際関係学部)$$
集合演算
和集合演算
和集合演算は下記のように定義されます．
和集合演算
$R_1$と$R_2$の和集合$R_1 \cup R_2$を次のように定義する． $$ R_1 \cup R_2 = \left\{ t|t \in R_1 \lor t \in R_2 \right\} $$
ここで，記号$\lor$は 論理和 を表しています． $【サッカー部】\cup【テニス部】$の演算結果は下記のようになります． それぞれのリレーションからタプルを取り出し，それらを合わせていることが分かります． ただし，両方のリレーションに存在する$(B003,杉江弘子,3,人文学部)$は， 和集合したリレーションには1つしか存在しないことに注意してください．
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 |
| A003 | 内田弘 | 3 | 工学部 |
| B003 | 杉江弘子 | 3 | 人文学部 |
| A002 | 岩村優 | 1 | 工学部 |
| C004 | 仙波あすか | 1 | 国際関係学部 |
差集合演算
差集合演算は下記のように定義されます．
差集合演算
$R_1$と$R_2$の差集合$R_1 - R_2$を次のように定義する． $$ R_1 - R_2 = \left\{ t|t \in R_1 \land \lnot(t \in R_2) \right\} $$
ここで，記号$\land$は 論理積 ，$\lnot$は 否定 を表しています． $【サッカー部】-【テニス部】$の演算結果は下記のようになります． 【サッカー部】に存在し，かつ，【テニス部】には存在しないタプルが対象となります． $(B003,杉江弘子,3,人文学部)$は【テニス部】にも存在しているため， リレーションから取り除かれています．
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 |
| A003 | 内田弘 | 3 | 工学部 |
共通集合演算
共通集合演算は下記のように定義されます．
共通集合演算
$R_1$と$R_2$の共通集合$R_1 \cap R_2$を次のように定義する． $$ R_1 \cap R_2 = \left\{ t|t \in R_1 \land t \in R_2 \right\} $$
$【サッカー部】\cap【テニス部】$の演算結果は下記のようになります． 【サッカー部】と【テニス部】の両方に存在するタプルが対象となります． 上述したように$(B003,杉江弘子,3,人文学部)$だけが両方のリレーションに存在していますね．
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| B003 | 杉江弘子 | 3 | 人文学部 |
直積集合演算
直積集合演算は下記のように定義されます．
直積集合演算
$R_1$と$R_2$の直積集合$R_1 \times R_2$を次のように定義する． $$ R_1 \times R_2 = \left\{ (t_1,t_2) |t_1\in R_1 \land t_2 \in R_2 \right\} $$
$【サッカー部】\times【テニス部】$の演算結果は下記のようになります． 直積演算は，第2回で解説したドメインの直積と同じように， それぞれのリレーションからタプルを取り出し，それらを組み合わせた新しいリレーションを形成します． このとき，各属性が演算前のどちらのリレーションに属していたかを明確にするため， リレーション名.属性名という表記を用いることがあります（ドット記法）．
| サ.学籍番号 | サ.氏名 | サ.学年 | サ.学部 | テ.学籍番号 | テ.氏名 | テ.学年 | テ.学部 |
|---|---|---|---|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 | A002 | 岩村優 | 1 | 工学部 |
| A001 | 岩城隼人 | 2 | 工学部 | B003 | 杉江弘子 | 3 | 人文学部 |
| A001 | 岩城隼人 | 2 | 工学部 | C004 | 仙波あすか | 1 | 国際関係学部 |
| A003 | 内田弘 | 3 | 工学部 | A002 | 岩村優 | 1 | 工学部 |
| A003 | 内田弘 | 3 | 工学部 | B003 | 杉江弘子 | 3 | 人文学部 |
| A003 | 内田弘 | 3 | 工学部 | C004 | 仙波あすか | 1 | 国際関係学部 |
| B003 | 杉江弘子 | 3 | 人文学部 | A002 | 岩村優 | 1 | 工学部 |
| B003 | 杉江弘子 | 3 | 人文学部 | B003 | 杉江弘子 | 3 | 人文学部 |
| B003 | 杉江弘子 | 3 | 人文学部 | C004 | 仙波あすか | 1 | 国際関係学部 |
例題1
【八百屋】と【果物屋】の和集合，差集合，共通集合，直積集合を求めよ．
| 商品番号 | 商品名 | 価格 |
|---|---|---|
| G1 | ニンジン | 100円 |
| G2 | トマト | 200円 |
| G3 | スイカ | 500円 |
| 商品番号 | 商品名 | 価格 |
|---|---|---|
| G4 | イチゴ | 300円 |
| G5 | ブドウ | 200円 |
| G3 | スイカ | 500円 |
関係代数演算
射影演算
射影演算は下記のように定義されます．
射影演算
$R$の射影$R[X]$を次のように定義する． ここで，$R$の属性集合が$A=(a_1, a_2, \cdots, a_n)$であり， その部分集合が$X = (x_1, x_2, \cdots,x_k) \in A$である． $$ R[X] = R(x_1, x_2, \cdots, x_k) $$
上記の定義は分かりにくいですが，具体例で考えれば簡単です． 例えば，$【サッカー部】[氏名,学部]$の演算結果は下記のようになります． 射影演算は，属性を指定して，リレーションを縦方向に切り出す操作を表しています． 指定する属性は，一つでも，複数でも構いません．
| 氏名 | 学部 |
|---|---|
| 岩城隼人 | 工学部 |
| 内田弘 | 工学部 |
| 杉江弘子 | 人文学部 |
選択演算
選択演算は下記のように定義されます．
選択演算
$R$の選択$R[a_i = x]$を次のように定義する． ここで，$R$の属性集合が$A=(a_1, a_2, \cdots, a_n)$である． $$ R[a_i = x] = \left\{ t | t \in R \land t[a_i] = x \right\} $$
具体例で考えましょう． 例えば，$【サッカー部】[学年=3]$の演算結果は下記のようになります． 選択演算は，属性の値を指定して，リレーションを横方向に切り出す操作を表しています． ここでは，$[学年=3]$と指定しているため，学年が3と一致するタプルだけが抽出されます． このとき，「$=$」のような記号を 比較演算子 と呼び， 等号($=$)，不等号($\neq$)，より小さい($<$)，より大きい($>$)，以下($<=$)，以上($>=$)などの記号を用いることが出来ます．
| 学籍番号 | 氏名 | 学年 | 学部 |
|---|---|---|---|
| A003 | 内田弘 | 3 | 工学部 |
| B003 | 杉江弘子 | 3 | 人文学部 |
結合演算
結合演算は下記のように定義されます．
結合演算（内部結合）
$R_1$と$R_2$の結合$R_1[a_i = b_i]R_2$を次のように定義する． ここで，$R_1$の属性集合が$A=(a_1, a_2, \cdots, a_n)$であり， $R_2$の属性集合が$B=(b_1, b_2, \cdots, b_n)$である． $$ R_1[a_i = b_i]R_2 = \left\{ (t_1,t_2) | t_1 \in R_1 \land t_2 \in R_2 \land t_1[a_i] = t_2[b_i] \right\} $$
具体例で考えましょう． 例えば，$【サッカー部】[学部=学部]【学部リスト】$の演算結果は下記のようになります． 結合演算は，直積集合演算を適用した後で，選択演算を適用した結果と一致します． つまり，$【サッカー部】\times 【学部リスト】$の演算結果から， 指定された属性（ここでは「学部」）の値（例えば「工学部」）が一致するタプルのみを選択するという操作です． ここでも， ドット記法 が用いられることに注意してください．
| サ.学籍番号 | サ.氏名 | サ.学年 | サ.学部 | 学.学部 | 学.キャンパス | 学.教員数 |
|---|---|---|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 | 工学部 | 春日井 | 30 |
| A003 | 内田弘 | 3 | 工学部 | 工学部 | 春日井 | 30 |
| B003 | 杉江弘子 | 3 | 人文学部 | 人文学部 | 春日井 | 20 |
しかし，この場合，サ.学部 と学.学部 の両方がリレーションに混在することになってしまい冗長に感じます． そこで，条件を指定するのではなく，一致するドメインを自動的に条件に設定し，結合する演算が用意されています． これを 自然結合(Natural Join) と呼び，$R_1 * R_2$ で表現します． 例えば，$【サッカー部】*【学部リスト】$の演算結果は下記のようになります． ここでは，学部 は同じドメインであることから，自動的に条件に設定されることになります． 先程とは異なり冗長な属性が取り除かれていることが分かります．
| 学籍番号 | 氏名 | 学年 | 学部 | キャンパス | 教員数 |
|---|---|---|---|---|---|
| A001 | 岩城隼人 | 2 | 工学部 | 春日井 | 30 |
| A003 | 内田弘 | 3 | 工学部 | 春日井 | 30 |
| B003 | 杉江弘子 | 3 | 人文学部 | 春日井 | 20 |
例題2
【テニス部】と【学部リスト】の結合と自然結合を求めよ．ただし，結合は学部の一致を条件とする．
例題3
結合演算には，上記で述べた内部結合，自然結合の他に左外部結合がある．左外部結合の特徴を調べよ．