3 構造記述
千里之行，始于足下．
– 老子
3.1 学習目標
- リレーションの概念を理解する．
- 直積，濃度，次数の概念を理解し，計算できる．
- リレーションスキーマとインスタンスの違いを理解する．
- 第1正規形の概念を理解し，非第1正規形リレーションを正規化できる．
3.2 データモデルの要素
- 構造記述：データベースの構成要素の記述
- 意味記述：データベースの一貫性制約の記述
- 操作記述：データベース操作言語
3.3 リレーションとは
3.3.1 ドメイン
定義 3.1 (ドメイン) ドメイン（domain，定義域）は属性の取り得る値の集合である．一般に D で表す．
例 3.1
- 年齢：D_1 = \{0, 1, 2, \ldots, 120\}．
- 性別：D_2 = \{\text{"M"}, \text{"F"}, \text{"NULL"}\}．
- 人名：D_3 = \{x \mid x \text{ は人名}\}．
3.3.2 直積
定義 3.2 直積（Cartesian product）は集合 A と B の直積であり，A \times B = \{(a, b) \mid a \in A, b \in B\} である．直積の要素はタプル（tuple，組）と呼ばれる．
例 3.2 A = \{1, 2, 3\}, B = \{3, 4\} のとき，A と B の直積は次のようになる．
A \times B = \{(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)\}
3.3.3 リレーション
定義 3.3 リレーション（relation）は D_1, D_2, \ldots, D_n をドメインとするとき，D_1, D_2, \ldots, D_n 上のリレーションRとは D_1 \times D_2 \times \ldots \times D_n の任意の有限部分集合として定義する．
例 3.3 D_1 = \{1, 2, 3\}, D_2 = \{a, b\} のとき，リレーション R の例は次のようになる．
R = \{(1, a), (2, b), (3, a)\}
例 3.4 D_1 = \{\text{"Tom"}, \text{"Mary"}\}, D_2 = \{1, 2, \ldots, 120\} のとき，リレーション R の例は次のようになる．
R = \{(\text{"Tom"}, 20), (\text{"Mary"}, 30), (\text{"Tom"}, 40)\}
3.3.4 濃度と次数
定義 3.4 濃度（cardinality）はリレーションのタプルの数をリレーションの濃度という．次数（degree）はリレーションが定義されるドメインの数をリレーションの次数という．
例 3.5 R = \{(1, a), (2, b), (3, a)\} の濃度は3，次数は2である．
3.3.5 テーブルとリレーション
リレーションをテーブル（table）として表すことができる．テーブルの行はリレーションのタプルであり，テーブルの列はリレーションのドメインに対応する．
例 3.6 ドメイン D_1 = \{\text{"Tom"}, \text{"Mary"}\}, D_2 = \{0, 1, 2, \ldots\} のリレーション R\{(\text{"Tom"}, 25), (\text{"Mary"}, 30)\} をテーブルで表すと次のようになる．
| Tom | 25 |
| Mary | 30 |
- D_2を年齢のドメインとするとき，TomとMaryの年齢はそれぞれ25歳と30歳である．
3.4 リレーションスキーマとインスタンス
属性名（attribute name）はテーブルの列の名前であり，リレーション名（relation name）はテーブルの名前である．
定義 3.5 A_i を属性名，D_i をドメイン，i=1, 2, \ldots, n とするとき，\text{dom}: A_i \to D_i をドメイン関数（domain function）という．
例 3.7 D_1=\{x \mid x \text{は人名}\}, D_2=\{0, 1, 2, \ldots\} のリレーション R\{(\text{"Tom"}, 25), (\text{"Mary"}, 30)\} を考える．
リレーション名は社員であり，属性名は名前と年齢である．テーブルで表すと次のようになる．
| 名前 | 年齢 |
|---|---|
| Tom | 25 |
| Mary | 30 |
年齢と名前のドメイン関数はそれぞれ次のようになる．
\text{dom}(\text{名前}) = D_1 = \{x \mid x \text{は人名}\}
\text{dom}(\text{年齢}) = D_2 = \{0, 1, 2, \ldots\}
3.4.1 ドメイン関数を用いたリレーションの定義
定義 3.6 リレーション R は \text{dom}(A_1) \times \text{dom}(A_2) \times \ldots \times \text{dom}(A_n) の有限部分集合である．
3.4.2 リレーションスキーマとインスタンス
定義 3.7 \boldsymbol{R} をリレーション名，A_1, A_2, \ldots, A_n を属性名，\text{dom} をドメイン関数とするとき，リレーションスキーマ（relation schema）は \boldsymbol{R}(A_1, A_2, \ldots, A_n) で表す．このとき，R \subseteq \text{dom}(A_1) \times \text{dom}(A_2) \times \ldots \times \text{dom}(A_n) を \boldsymbol{R} のインスタンス（instance）という．
3.5 第1正規形
定義 3.8 リレーションスキーマ \boldsymbol{R}(A_1, A_2, \ldots, A_n) が第1正規形（1NF, first normal form）であるとは，任意のドメインがシンプルであることをいう． シンプルはドメインの元が原子的（atomic），即ち分解不可能（nondecomposable）な値であることを指す．
3.5.1 非第1正規形
ドメインを複数のドメインの直積として定義する入れ子型リレーションは非第1正規形である．
例 3.8 \text{dom}(\text{学生名}) = \text{dom}(\text{姓}) \times \text{dom}(\text{名}) のとき，次のリレーションは非第1正規形である．
| 学生番号 | 学生名 | … |
|---|---|---|
| 9375 | (田中, 太郎) | … |
| 9376 | (山田, 花子) | … |
| … | … | … |
この非第1正規形リレーションを正規化すると次のようになる．
| 学生番号 | 姓 | 名 | … |
|---|---|---|---|
| 9375 | 田中 | 太郎 | … |
| 9376 | 山田 | 花子 | … |
| … | … | … | … |
べき集合（power set）として定義されるドメインも非第1正規形である．
例 3.9 \text{dom}(\text{科目}) = \mathcal{P}(\text{dom}(\text{科目名}))のとき，次のリレーションは非第1正規形である．
| 学生番号 | 科目 |
|---|---|
| 9375 | {数学, 物理, 化学} |
| 9376 | {英語, 数学} |
| … | … |
この非第1正規形リレーションを正規化すると次のようになる．
| 学生番号 | 科目 |
|---|---|
| 9375 | 数学 |
| 9375 | 物理 |
| 9375 | 化学 |
| 9376 | 英語 |
| 9376 | 数学 |
| … | … |
3.6 練習問題
3.6.1 非第1正規形からの正規化
以下のようなリレーションがある：
| 注文ID | 顧客名 | 商品一覧 |
|---|---|---|
| 1001 | 佐藤 | {りんご, バナナ, オレンジ} |
| 1002 | 鈴木 | {バナナ, パイナップル} |
- 上記リレーションが 非第1正規形 である理由を説明せよ．
- このリレーションを 第1正規形 に正規化せよ．
- 正規化後のリレーションに対し，リレーションスキーマを明記し，そのインスタンスをテーブル形式で記述せよ．
3.6.2 リレーションスキーマとインスタンス
リレーションスキーマ \boldsymbol{R}(A_1, A_2, A_3, A_4) について，各属性は以下のように定義される．
- A_1：学籍番号
- A_2：氏名
- A_3：年齢
- A_4：所属（学部名）
以下の問いに答えよ．
- \boldsymbol{R} の具体的なインスタンスを 3件分，テーブル形式で作成せよ．
- そのインスタンスをリレーション R として 集合表記 で表せ．
- R の 濃度 と 次数 を求めよ．
- \text{dom}(A_4)（所属）の ドメイン を定義せよ．