データモデリング§データベース設計論(立命館2022春講義)
35339, 35340
キーワード
データの高位設計，制約の洗い出し
DBMSの各々のスキーマに書き下す
性能の向上，DBのクラスタリングなど
6. アプリケーション/セキュリティ設計
2回目，
#ER図 Enitty-Relationship Model 機械的に論理モデルへ機械的に変換可能
用語
実体；実世界で他と区別可能なもの
実体集合：似た実体の集まり
属性：実体に対して表現したい情報
ドメイン：属性の取りうる値の集合
キー；実体を一位に区別可能な最小の属性集合
一般に複数ありうる
関連：2つ以上の実体のつながり
同一の実体集合間で関連を持つこともある（関連の意味付けが必要）
関連集合：似た関連の集まり
キー制約：ある実体が，ただ一つの関連に紐付けられる
参加制約(Participation Constraints)
全員参加(Total Participation)：
Aから見ると必ずBに関連がある
部分参加(Partial Participation):
Aから見ると必ずしもBに関連があるわけではない
3回目
4回目
関数従属性(Functional Dependency, FD) リレーションスキーマ$ R
空でない任意の属性集合$ X,Y
タプル$ t_1,t_2
$ t_1.Xは$ t_1の属性$ X上の射影を表す
$ t_1.X = t_2.Xで$ t_1.Y=t_2.Yなら
$ Rのインスタンス$ rは関数従属性$ X \to Yを満たす
属性$ Yの値は属性$ Xの値によって一意に定まる
諸注意
リレーションの主キー$ Xリレーションの全属性$ Yについて
$ X \to Y
関数従属性$ X \to Yについて$ Xが最小の属性集合であることは要求されない
全ての属性集合$ Yについて$ X \to Yを満たし
$ Xの部分集合$ Vが$ V \to Yを満たすような$ X
https://gyazo.com/d92dd5a426aa5df3cead11c8e93424fb
与えられた関数充足性の集合$ Fから帰結される全ての関数従属性を「$ Fの閉包」と読んで$ F^+で表す
反射律
$ X \supe Yなら$ X \to Y
例えば$ R=(A,B,C,D)について自明に$ ABC \to A
添加律
$ X \to Yなら任意の$ Zについて$ XZ \to YZ
推移律
$ X \to Y, Y \to Zなら$ X \to Z
これは健全性（導出されるFDは正しい），完全性（全FDを導出可能）を満たす ただし全部列挙するのは指数時間かかる
含意問題
ある関数従属性集合$ Fが与えられたとき，ある$ X \to Yは$ X \to Y \in F^+か？
判定には多項式時間ですむ
属性閉包$ X^+を求め，$ Y \in X^+を判定する
0, 初期値$ X^+ = X
1, $ U \sube X^+であるような$ U \to V \in Fがあるなら
$ (X^+)' := X^+ \cup Vとする
2, $ (X^+)'=X^+になるまで，1を繰り返す
https://gyazo.com/29344d2e6a02664e9664785b7b90aefa
最小被覆
関数従属性の集合から冗長なものを取り除く
関数従属性集合$ Fについて，$ Fの最小被覆$ Gは次を満たす
1, $ G^+と$ F^+は等しい
2, 全ての$ X \to A \in Gについて$ Aは単一の属性
3, $ X \to A \in G，$ Xの真部分集合$ Z \sub Xについて
$ G - \{ X \to A \} \cup \{Z \to A\}と$ Gは等価ではない
4, $ g \in Gについて$ G - \{ g\}と$ Gが等価ではない
https://gyazo.com/c49e7e3876a7e63c8d2338ecd3e00687
リレーション上の関数従属性(FD)$ X \to Aがどちらかを満たす 自明なFD，$ A \in X
端的には，自明でないFDは，キーの値によって他の属性の値が決まる．
https://gyazo.com/d8298eaaad9d83235a43d3d247e21bea
リレーション上の関数従属性(FD)$ X \to Aがどちらかを満たす 自明なFD，$ A \in X
$ Xがスーパーキー
$ Aがいずれかのキーの一部である
https://gyazo.com/6326e156722d77674155ef3f5c173f0a
推移的な従属性がある
https://gyazo.com/1290f17ccb6fe615984eb6ac7a12f68e
https://gyazo.com/8bf3a06e0a07aca20603ea3630a386b3
自明でない関数従属性$ X \to A
リレーションを分解する
$ Rを分解した$ R_1,R_2を自然結合すると$ Rに戻る https://gyazo.com/765dc9eadc79873ab3b286bebc61fce4
多値従属性(Multivalued Dependency, MVD) ある属性$ Xの値から，属性$ Yの値が他の属性に無関係無く複数決まる
$ X \to\to Y
$ X \to Y \implies X \to\to Y
全ての多値従属性$ X \to\to Yがどちらかを満たす $ Y \sube Xまたは$ XY=R
結合従属性$ \Join\{R_1,\cdots,R_n\}がある $ X \to\to Y \implies \Join\{ XY, X(R-Y) \}
全結合従属性$ \Join\{R_1,\cdots,R_n\}について 任意の$ iについて$ R_i = R
各$ R_iの属性が$ Rのスーパーキー
5回目
例えば
$ R(A,B,C,D)
$ C \to D,C \to A, B \to C
$ \{B\}^+ = \{BC\}^+ = \{ABCD\}
今
$ C \to D, C \to Aについて
$ Cが非スーパーキーで非キー属性
$ D,Aが非キー属性
$ B \to Cについて
$ Bがスーパーキ
$ A\underline{B}CD \rightarrowtail \underline{B}C,A\underline{C}D
$ B \to C , D \to A
$ \{BD\}^+ = \{ABCD\}
$ A\underline{B}C\underline{D} \rightarrowtail A\underline{BD},\underline{B}C
更に$ A\underline{BD} \rightarrowtail \underline{BD},A\underline{D}
最終的には
$ A\underline{B}C\underline{D} \rightarrowtail \underline{BD},A\underline{D},\underline{B}C
$ ABC \to D, D \to A
キーが2種類ある
$ \{ABC\}^+ = \{ABCD\}
$ \{BCD\}^+ = \{ABCD\}←こちらを採用
$ A\underline{BCD} \rightarrowtail \underline{BCD},A\underline{D}
もとの関数従属性$ ABC \to Dが消失
既にあるデータ（画面や帳簿など）からリレーションスキーマを抽出
13
最短距離の定義
$ d(C_1,C_2) = \min_{x_1\in C_1, x_2 \in C_2} d(x_1,x_2)
定義
$ d(C_1,C_2) = \frac{1}{|C_1||C_2|} \sum_{x_1 \in C_1} \sum_{x_2 \in C_2} d(x_1,x_2)
クラスタの平方和
$ n個の要素$ \{e_1 \cdots e_n\}で構成されたクラスタ$ A
$ p個の変数で説明されるような要素$ e_i = ({x_1}_i \cdots {x_p}_i)
クラスタ$ Aの平方和を以下
$ S_A = \sum^p_k \sum^n_i ({x_k}_i - \bar{x_k})^2
ただし$ \bar{x_k} = \frac{1}{n} \sum^n_i {x_k}_i
クラスタ$ Aと$ Bを統合した結果をクラスタ$ Cとする，
$ \Delta S_{AB} = S_C - (S_A + S_B)
この平方和を最小にするようなクラスタ$ Cを見つけ出していく