【DB入門】無損失結合分解の必要十分条件

北川 博之著「データベースシステム（オーム社）」を参考に，データベースシステムの知識をまとめます。

無損失結合分解の必要十分条件

$\rho=\{RS_{1},RS_{2}\}$をリレーションスキーマ$RS$の分解とし，$F$を$RS$に関する関数従属性集合とします。このとき，分解$\rho$が無損失結合分解となる必要十分条件は，

1. $RS_{1}\cap RS_{2}~\rarr~RS_{1}-RS_{2}\in F^{+}$
2. $RS_{1}\cap RS_{2}~\rarr~RS_{2}-RS_{1}\in F^{+}$

のいずれかが成り立つことです。ただし，$F^{+}$は$F$の閉包を表します。

関数従属性は多値従属性に拡張することもできます。

補足

この必要十分条件は，1977年にRissanenによるリレーションの独立性を議論する論文 [1] 中の定理として発表されました。日本語で噛み砕くと，「分解後のリレーションに共通した属性から，自身以外の属性への関数従属性があること」となります。具体的には，$\{A,B,C\}$というリレーションスキーマの$\{A,B\}$と$\{B,C\}$への分解を考えたときに，仮に関数従属性が一切ない場合は必要十分条件のいずれも満たさないため，この分解は無損失結合分解とはなりません。一方，仮に分解後の両方に存在する$B$に対する関数従属性，すなわち$\{B\rarr A\}$もしくは$\{B\rarr C\}$が存在する場合には，この分解は無損失結合分解となります。

[1] Rissanen Jorma. "Independent components of relations." ACM TODS 2.4 (1977): 317-325.

例

下記のようなリレーションを考えます。

$x$	$y$	$z$
$x_{1}$	$y_{1}$	$z_{1}$
$x_{1}$	$y_{1}$	$z_{2}$
$x_{2}$	$y_{1}$	$z_{1}$

このリレーションには，$y\rarr x$という関数従属性も$y\rarr z$という関数従属性も存在しません。このリレーションを，下のような二つのリレーションに分解したとします。

必要十分条件によれば，この分解は無損失結合分解ではないため，これらのリレーションを再度自然結合して一つのリレーションに戻した場合に，余分な情報が付け加えられてしまうはずです。実際に自然結合してみます。

$x$	$y$	$z$
$x_{1}$	$y_{1}$	$z_{1}$
$x_{1}$	$y_{1}$	$z_{2}$
$x_{2}$	$y_{1}$	$z_{1}$
$x_{2}$	$y_{1}$	$z_{2}$

予想通り，最後$(x_{2},y_{1},z_{2})$というタプルが余計に付け加えられてしまいました。それでは，リレーションに元から関数従属性がある場合はどうなるでしょうか。

$x$	$y$	$z$
$x_{1}$	$y_{1}$	$z_{1}$
$x_{2}$	$y_{1}$	$z_{1}$
$x_{2}$	$y_{2}$	$z_{2}$

このリレーションには，$y\rarr z$という関数従属性があります。このとき，必要十分条件によれば，$y$を共通部分として先ほどと同様に分解したものは無損失結合分解となっているはずです。

これらのリレーションの自然結合は，以下のようになります。

$x$	$y$	$z$
$x_{1}$	$y_{1}$	$z_{1}$
$x_{2}$	$y_{1}$	$z_{1}$
$x_{2}$	$y_{2}$	$z_{2}$

分解前のリレーションと全く等価になっています。したがって，この分解は無損失結合分解になります。

参考文献