5 操作記述
Young man, in mathematics you don’t understand things. You just get used to them.
– John von Neumann
5.1 学習目標
- 和両立を理解し，与えられたリレーションが和両立か判定できる．
- リレーション代数の基本演算を理解し，計算できる．
- 与えられたリレーションに対して，目的に応じた演算を適用できる．
5.2 リレーショナル代数
リレーショナル代数（relational algebra）はエドガー・F・コッドによって提案された，リレーションとして表現されたデータを操作するための代数的な演算の体系である．それを実装したデータベース言語はSQLである．
リレーション代数は次の基本演算から構成される．
- 和集合演算
- 差集合演算
- 共通集合演算
- 直積演算
- 射影演算
- 選択演算
- 結合演算
- 商演算
5.2.1 和両立
定義 5.1 リレーション\(R(A_1, A_2, \ldots, A_n)\)とリレーション\(S(B_1, B_2, \ldots, B_m)\)が和両立（union compatible）とは，次の二つの条件を満たすことである．
- \(n = m\)．
- \(\text{dom}(A_i) = \text{dom}(B_i)\)であり，\(1 \leq i \leq n\)．
例 5.1 ある大学の学生データベースには，2024年度入学生のデータを格納するリレーション学生2024と，2025年度入学生のデータを格納するリレーション学生2025がある．
- 学生2024(学籍番号, 氏名, 学科)
- 学生2025(学籍番号, 氏名, 学科)
学生2024と学生2025の次数は共に3であり，それぞれの属性の定義域は共通であるため，これらは和両立である．
例 5.2 A社とB社の社員を表すリレーションA社の社員とB社の社員がある．A社の社員が事務部と営業部のどちらかに所属するのに対し，B社の社員が開発部と研究部のどちらかに所属するとする．
- A社の社員(社員番号, 氏名, 部署)
- B社の社員(社員番号, 氏名, 部署)
A社とB社の部署の定義域は異なるため，これらは和両立ではない．
5.2.2 和集合演算
定義 5.2 \(R\) と \(S\) を和両立なリレーションとするとき，\(R\) と \(S\) の和集合は，\(R \cup S\) で書く．その定義は次の通りである．
\[ R \cup S = \{t \mid t \in R \text{ or } t \in S\} \]
\(R\) と \(S\) の和集合は，\(R\) または \(S\) に属するタプル全体の集合である．
例 5.3 ある大学は工学部と理学部を持っており，それぞれの学生を表すリレーション工学部学生と理学部学生がある．
- 工学部学生(学籍番号, 氏名, 学科)
- 理学部学生(学籍番号, 氏名, 学科)
工学部学生と理学部学生の和集合は，その大学の全学生を表すリレーションである．
例 5.4 ある大学のプログラミングとデータベースの授業を受講する学生を表すリレーションプログラミングとデータベースがある．
プログラミング(学籍番号, 氏名, 学科)
| 学籍番号 | 氏名 | 学科 |
|---|---|---|
| 202464 | 田中花子 | 機械工学科 |
| 202487 | 山田太郎 | 機械工学科 |
| … | … | … |
データベース(学籍番号, 氏名, 学科)
| 学籍番号 | 氏名 | 学科 |
|---|---|---|
| 202464 | 田中花子 | 機械工学科 |
| 202490 | 佐藤次郎 | 情報工学科 |
| … | … | … |
プログラミングとデータベースの和集合は，プログラミングまたはデータベースの授業を受講する学生を表すリレーションである．
| 学籍番号 | 氏名 | 学科 |
|---|---|---|
| 202464 | 田中花子 | 機械工学科 |
| 202487 | 山田太郎 | 機械工学科 |
| 202490 | 佐藤次郎 | 情報工学科 |
| … | … | … |
集合は異なる元の集まりであるため，重複するタプルは除かれる．
5.2.3 差集合演算
定義 5.3 \(R\)と\(S\)を和両立なリレーションとするとき，\(R\)と\(S\)の差集合は，\(R - S\)で書く．その定義は次の通りである．
\[R - S = \{t \mid t \in R \text{ and } t \notin S\}\]
\(R\)と\(S\)の差集合は，\(R\)に属し，\(S\)に属さないタプル全体の集合である．
例 5.5
- プログラミング(学籍番号, 氏名, 学科)
- データベース(学籍番号, 氏名, 学科)
プログラミングとデータベースの差集合は，プログラミングの授業を受講するがデータベースの授業を受講していない学生を表すリレーションである．
5.2.4 共通集合演算
定義 5.4 \(R\)と\(S\)を和両立なリレーションとするとき，\(R\)と\(S\)の共通集合は，\(R \cap S\)で書く．その定義は次の通りである．
\[R \cap S = \{t \mid t \in R \text{ and } t \in S\}\]
\(R\)と\(S\)の共通集合は，\(R\)にも属し，\(S\)にも属するタプル全体の集合である．
例 5.6
- プログラミング(学籍番号, 氏名, 学科)
- データベース(学籍番号, 氏名, 学科)
プログラミングとデータベースの共通集合は，プログラミングの授業とデータベースの授業の両方を受講する学生を表すリレーションである．
5.2.5 直積演算
定義 5.5 \(R(A_1, A_2, \ldots, A_n)\)と\(S(B_1, B_2, \ldots, B_m)\)をリレーションとするとき，\(R\)と\(S\)の直積は，\(R \times S\)で書く．その定義は次の通りである．
\[R \times S = \{(r, s) \mid r \in R \text{ and } s \in S\}\]
\(R\)と\(S\)の直積は，\(R\)のタプルと\(S\)のタプルの全ての組み合わせの集合である．
\(R(A_1, A_2, \ldots, A_n)\)と\(S(B_1, B_2, \ldots, B_m)\)をリレーションとするとき，\(R\)と\(S\)の直積\(R \times S\)の属性名は\(R.A_i\)と\(S.B_i\)で表す．
例 5.7 商品（商品番号，商品名）
| 商品番号 | 商品名 |
|---|---|
| 1 | りんご |
| 2 | みかん |
店舗（店舗番号，店舗名）
| 店舗番号 | 店舗名 |
|---|---|
| A | A店 |
| B | B店 |
商品と店舗の直積は，商品と店舗の全ての組み合わせを表すリレーションである．
| 商品.商品番号 | 商品.商品名 | 店舗.店舗番号 | 店舗.店舗名 |
|---|---|---|---|
| 1 | りんご | A | A店 |
| 1 | りんご | B | B店 |
| 2 | みかん | A | A店 |
| 2 | みかん | B | B店 |
5.2.6 射影演算
定義 5.6 \(R(A_1, A_2, \ldots, A_n)\)をリレーション，\(R\)の全属性集合を\(\{A_1, A_2, \ldots, A_n\}\)の部分集合を\(X=\{A_{i_1}, A_{i_2}, \ldots, A_{i_m}\}\)，ここに\(1 \leq i_1 < i_2 < \ldots < i_m \leq n\)とする．\(R\)の\(X\)上の射影を\(R[X]\)で表す．その定義は次の通りである．
\[R[X] = \{t[X] \mid t \in R\}\]
ここに，\(t=(a_1, a_2, \ldots, a_n) \in R\)とするとき，\(t[X]=(a_{i_1}, a_{i_2}, \ldots, a_{i_m})\)である．
例 5.8 商品（商品番号，商品名，価格）
| 商品番号 | 商品名 | 価格 |
|---|---|---|
| 1 | りんご | 100 |
| 2 | みかん | 80 |
商品の商品番号と商品名の射影は，商品番号と商品名のみを抽出したリレーションである．
| 商品番号 | 商品名 |
|---|---|
| 1 | りんご |
| 2 | みかん |
5.2.7 選択演算
定義 5.7 \(R(A_1, A_2, \ldots, A_n)\)をリレーション，\(A_i\)と\(A_j\)を\(\theta\)-比較可能な属性とする．ここに，\(\theta\)は比較演算子（\(=, \neq, <, \leq, >, \geq\)）である．\(R\)の\(A_i\)と\(A_j\)上の\(\theta\)-選択を\(R\left[A_i \theta A_j\right]\)で表す．その定義は次の通りである．
\[R\left[A_i \theta A_j\right]= \{t \mid t \in R \text{ and } t[A_i] \theta t[A_j]\}\]
ここに，\(A_i\)と\(A_j\)が\(\theta\)-比較可能とは，次の2つの条件を満たすことである．
- \(\text{dom}(A_i) = \text{dom}(A_j)\)
- \(t[A_i] \theta t[A_j]\)の真か偽が定義されている
\(R(A_1, A_2, \ldots, A_n)\)の属性\(A_i\)と\(c\)に関する\(\theta\)-選択を\(R\left[A_i \theta c\right]\)で表す．
\[R\left[A_i \theta c\right]= \{t \mid t \in R \text{ and } t[A_i] \theta c\}\]
例 5.9 商品（商品番号，商品名，価格）
| 商品番号 | 商品名 | 価格 |
|---|---|---|
| 1 | りんご | 100 |
| 2 | みかん | 80 |
商品の価格が100円以上の商品を抽出するための選択演算は，次のようになる．
\[\text{商品}\left[\text{価格} \geq 100\right]\]
| 商品番号 | 商品名 | 価格 |
|---|---|---|
| 1 | りんご | 100 |
5.2.8 結合演算
定義 5.8 \(R(A_1, A_2, \ldots, A_n)\)と\(S(B_1, B_2, \ldots, B_m)\)をリレーション，\(A_i\)と\(B_j\)を\(\theta\)-比較可能とする．\(R\)と\(S\)の\(A_i\)と\(B_j\)上の\(\theta\)-結合を\(R \left[A_i \theta B_j\right] S\)で表す．その定義は次の通りである．
\[R \left[A_i \theta B_j\right] S = \left\{(r, s) \mid r \in R \text{ and } s \in S \text{ and } r[A_i] \theta s[B_j]\right\}\]
例 5.10 社員（社員番号，社員名，部署）
| 社員番号 | 氏名 | 部署 |
|---|---|---|
| 1 | 田中 | E1 |
| 2 | 山田 | K2 |
| 3 | 佐藤 | E1 |
部署（部署番号，部署名）
| 部署番号 | 部署名 |
|---|---|
| E1 | 営業 |
| K4 | 開発 |
\(\text{社員}\left[\text{部署} = \text{部署番号}\right] \text{部署}\)の結果は，次のようになる．
| 社員.社員番号 | 社員.氏名 | 社員.部署 | 部署.部署番号 | 部署.部署名 |
|---|---|---|---|---|
| 1 | 田中 | E1 | E1 | 営業 |
| 2 | 山田 | K2 | K2 | 開発 |
| 3 | 佐藤 | E1 | E1 | 営業 |
5.2.9 商演算
定義 5.9 \(R(A_1, A_2, \ldots, A_{n-m}, B_1, B_2, \ldots, B_m)\)を\(n\)次，\(S(B_1, B_2, \ldots, B_m)\)を\(m\)次（\(n \geq m\)）のリレーションとする．\(R\)を\(S\)で割った商を\(R \div S\)で表す．その定義は次の通りである．
\[R \div S = \{t \mid t \in R(A_1, A_2, \ldots, A_{n-m}) \text{ and } \forall u \in S, (t, u) \in R\}\]
例 5.11 学生 テーブル
| 学籍番号 | 氏名 |
|---|---|
| 202401 | 山田太郎 |
| 202402 | 田中花子 |
| 202403 | 佐藤次郎 |
| 202404 | 鈴木一郎 |
履修 テーブル
| 学籍番号 | 科目 |
|---|---|
| 202401 | プログラミング |
| 202401 | データベース |
| 202402 | データベース |
| 202402 | ゲーム理論 |
| 202403 | プログラミング |
| 202403 | データベース |
プログラミングとデータベースの両方を履修している学生を検索することを考える．このとき，科目テーブルを次のようになる．
科目
| 科目 |
|---|
| プログラミング |
| データベース |
このとき，履修 ÷ 科目 の結果は，次のようになる．
| 学籍番号 |
|---|
| 202401 |
| 202403 |
5.3 リレーショナル代数表現
実リレーション（base relation）はデータベースに実際に格納されているリレーションである．リレーション演算から得られた結果もリレーションである．そのようなリレーションを導出リレーション（derived relation）と呼ぶ．
定義 5.10 リレーショナル代数表現（Relational Algebra Expression）
- リレーショナルデータベースの実リレーション\(R\)は表現である．
- \(R\)と\(S\)を表現とするとき，\(R\)と\(S\)が和両立であるなら，\(R \cup S\)，\(R - S\)，\(R \cap S\)は表現である．
- \(R\)と\(S\)を表現とするとき，\(R \times S\)は表現である．
- \(R\)を表現とするとき，\(R[X]\)は表現である．
- \(R\)を表現とするとき，\(R\left[A_i \theta A_j\right]\)，\(R\left[A_i \theta c\right]\)は表現である．
- \(R\)と\(S\)を表現とするとき，\(R \left[A_i \theta B_j\right] S\)は表現である．
- \(R\)と\(S\)を表現とするとき，\(R \div S\)は表現である．
- 以上の定義によって得られた表現のみがリレーショナル代数表現である．
5.4 演習
リレーション学生（学籍番号，学生名，学部），内定（学籍番号，法人番号，職種），会社（法人番号，会社名，所在地）があるとする．
問１ すべての学生の全データを求めよ．
学生
問２ 理工学部の学生の全データを求めよ．
学生[学部 = ‘理工’]
問３ 内定先を決まっている学生の学籍番号を求めよ．
内定[‘学籍番号’]
問４ 内定先を決まっていない理工学部の学生の学籍番号を求めよ．
学生[学部 = ‘理工’][‘学籍番号’] - 内定[‘学籍番号’]
問５ 理工学部の学生の内定先の法人番号を求めよ．
((学生[‘学籍番号’ = ‘学籍番号’]内定)[学生.学部 = ‘理工’])[内定.法人番号]
問６ 法人番号が’0001’の会社の内定を受けた学生の学籍番号と学生名を求めよ．
((学生[‘学籍番号’ = ‘学籍番号’]内定)[内定.法人番号 = ‘0001’])[学生.学籍番号, 学生.学生名]
5.5 練習問題
自由に設定したテーマに基づいてリレーショナルデータベースのスキーマを定義し、それを用いてすべての基本的なリレーショナル代数演算を含む例題を作成し、その解答を示しなさい。