関係代数演算

Image from Gyazo

本日のリレーション

今回は下記の【サッカー部】,【テニス部】,【学部リスト】を対象に解説します. 【サッカー部】と【テニス部】は,学籍番号,氏名,学年,学部,また, 【学部リスト】は,学部,キャンパス,教員数で構成されています. また,下線は主キーを表しています.

学籍番号 氏名 学年 学部
A001 岩城隼人 2 工学部
A003 内田弘 3 工学部
B003 杉江弘子 3 人文学部

【サッカー部】

学籍番号 氏名 学年 学部
A002 岩村優 1 工学部
B003 杉江弘子 3 人文学部
C004 仙波あすか 1 国際関係学部

【テニス部】

学部 キャンパス 教員数
工学部 春日井 30
人文学部 春日井 20
国際関係学部 名古屋 25

【学部リスト】

リレーションに対する演算

数値に対して足算や掛算などの四則演算が定義できるように, リレーションにも演算を定義することができます. リレーションに対する演算は4つの集合演算と, 4つの 関係代数演算(リレーショナル代数演算) で構成されています (商演算は殆ど用いることがないため,今回は割愛します).

集合演算は下記の4つです.

関係代数演算は下記の4つです.

これらの演算は,リレーショナルデータベースにおける検索や更新に該当し, 後に述べる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$),より小さい($<$),より大きい($>$),以下($\leq$),以上($\geq$)などの記号を用いることが出来ます.

学籍番号 氏名 学年 学部
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

【テニス部】と【学部リスト】の結合と自然結合を求めよ.ただし,結合は学部の一致を条件とする.

参考書籍