😋

データベース - 従属性

2022/11/05に公開

Database

tech

関数従属性

Functional Dependency

$A_1 \dots A_n \rightarrow B_1 \dots B_m$
{ $A_1 \dots A_n$ }は{ $B_1 \dots B_m$ }を関数的に決定する。

Key

$A_1 \dots A_n$ の集合

Attributes { $A_1 \dots A_n$ }が他のすべてのattributes を関数的に決定する。
{ $A_1 \dots A_n$ }の真部分集合はkeyにならない。(minimal)

Superkey

Keyを含む集合

KeyはSuperkeyの一部分集合
KeyはminimalなSuperkey

FDの特性

推移律

$A_1 \dots A_n \rightarrow B_1 \dots B_m$ $\cap$ $B_1 \dots B_m \rightarrow C_1 \dots C_p \Rightarrow A_1 \dots A_n \rightarrow C_1 \dots C_p$

等価関係

FDの集合が等価：
FDの集合が満たすrelation instance集合が一致する。

{ $A\rightarrow B\ C$ }と{ $A\rightarrow B, A\rightarrow C$ }は等価

Trivial FD

$A_1 \dots A_n \rightarrow B_1 \dots B_n \cap \{B_1 \dots B_n\}\subseteq \{A_1 \dots A_n\}$

Attributesのclosureを求める

$A_1 \dots A_n \rightarrow B_1 \dots B_m$ があるとき、 $A_1 \dots A_n$ のclosureは $A_1 \dots A_n \cup B_1 \dots B_m$ である。

Minimal basis

FDの集合があるとき、そのminimal basisは、そのFDの集合を満たす最小のFDの集合である。
MBに含まれるFDの右辺は、単一attributeである。左辺は最小である。
つまり、左辺から一つでもattributeを取り除くと、FDの集合を満たさなくなる。

多値従属性

MVD

$A_1\dots A_n \twoheadrightarrow B_1\dots B_m$ が成立するとき、
各Aについて一致する任意のtuples $t, u$ について、
以下を満たすtuple $v$ が存在する
- $A$ について $t[A] = u[A] = v[A]$
- $B$ について $t[B] = v[B]$
- それ以外のattributesについて $u$ と一致

Trivial MVD

$A_1\dots A_n \twoheadrightarrow B_1\dots B_m, \{B_1,\dots,B_m\}\subseteq\{A_1,\dots,A_n\}$
これはどんなときでも成り立つ

MVDの特性

Rのattributtesが $\{A_1,\dots,A_n, B_1,\dots,B_m\}$ だけであるとき、 $A_1\dots A_n \rightarrow B_1\dots B_m$ は常に成立する。
推移律は使える
分解・統合はできない
FDはMVDの一種