関数従属性とは
リレーションスキーマ $\mathbf{R}$ に関数従属性(Functional Dependency)$X \to Y$ が存在するとは、
$\mathbf{R}$ の任意のインスタンス $R$ に対して、以下の条件が成立するときをいう。
ただし、$X, Y$ は $\mathbf{R}$ の属性集合($X, Y \subseteq \Omega_\mathbf{R} $)。
$$ {}^\forall t, t' \in R, \qquad t[X] = t'[X] \implies t[Y] = t'[Y] $$
このとき、$X$ を決定子(determinant)、$Y$ を被決定子(resultant)という。
関数従属性の諸性質
以下 $X, Y, Z, W$ は属性集合を表す。
アームストロングの公理系
ざっくりいうと、陽に与えられた関数従属性たちから、下の3つの性質を使うことであらゆる関数従属性を過不足なく導出することができる。
A1. 自明な関数従属性(反射律)
$$ Y \subseteq X \implies X \to Y$$
A2. 添加律
$$ X \to Y \land Z \subseteq W \implies X \cup W \to Y \cup Z $$
A3. 推移律
$$ X \to Y \land Y \to Z \implies X \to Z $$
他の主な性質
性質1
A1.自明な関数従属性
とA3.推移律
から
$$ X \to Y \cup Z \implies X \to Y, X \to Z $$
性質2
A2.添加律
から特に
$$ X \to Y \implies X \cup Z \to Y \cup Z $$
性質3
性質2
から特に
$$ X \to Y \implies X \to X \cup Y $$
性質4
性質3
とA3.推移律
から
$$ X \to Y \land X \to Z \implies X \to Y \cup Z $$
性質5
性質2
とA3.推移律
から
$$ X \to Y \land Y \cup W \to Z \implies X \cup W \to Z $$
特別な関数従属性
完全関数従属性
関数従属性 $X \to Y$ について、「$Y$ が$X$に完全関数従属する」とは、以下の条件が成立するときをいう。
$$ {}^\forall X' \subsetneq X, \quad X' \not\to Y $$
部分関数従属性
関数従属性 $X \to Y$ について、「$Y$ が$X$に部分関数従属する」とは、以下の条件が成立するときをいう。
$$ {}^\exists X' \subsetneq X \mbox{ s.t. }\ X' \to Y $$
※この場合「$Y$ が$X'$に部分関数従属する」という言い方は誤りであることに注意!
推移的関数従属性
関数従属性について、$X \to Y$ , $Y \not\to Y$ , $Y \to Z$ が成立している。ただし $Y \to Z$ は自明な関数従属性ではない($Z \nsubseteq Y$)。
すると、$X \to Z$ かつ $Z \not\to X$ が成立する。このとき「$Z$ が $X$ に推移的に関数従属する」という。