【DB入門】極小被覆の定義

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

極小被覆の定義

関数従属性集合$F$に等価な関数従属性集合のうち，以下の三つの条件

1. $M$中のすべての関数従属性の右辺は単一の属性である
2. $M$中のいかなる関数従属性$X\rarr A$に対しても，$M-\{X\rarr A\}$と$M$は等価ではない
3. $M$中のいかなる関数従属性$X\rarr A$および$Z\subset X$に対しても，$M-\{X\rarr A\}\cap\{Z\rarr A\}$と$M$は等価でない

を満たす$M$を$F$の極小被覆と呼びます。

補足

それぞれの条件を噛み砕いてみましょう。まず，対局的に捉えます。

1. 右辺の冗長性について
2. 左辺の極小性について
3. 左辺の冗長性について

1.の条件は，右辺の冗長性を排除しています。仮に複数の属性が従う関数従属性を極小被覆とした場合に，アームストロングの公理系から導かれる下記の分解律

• $X\rarr Y$かつ$Z\subseteq Y$のとき，$X\rarr Z$が成立する

を利用すれば，右辺を単一の属性にできますので，極小被覆では冗長性を排除したな単一属性を扱います。2.の条件は，左辺の極小性を担保しています。仮に$X\rarr A$を左辺から排除した場合に$M$から情報が抜け落ちない，ということを規定しています。3.の条件は，左辺の冗長性を排除しています。仮に左辺の属性集合の部分集合を左辺に置き換えた（共通部分を取った）場合に$M$から情報が抜け落ちない，ということを規定しています。

例

$\{A\rarr BC,B\rarr C,C\rarr B\}$の極小被覆を求めてみます。まず，条件1.に従って$A\rarr BC$を分解します。

• $\{A\rarr B,A\rarr C,B\rarr C,C\rarr B\}$

次に，2.の条件に従います。ここでは，$\{A\rarr C, C\rarr B\}$に論理的に含意されている$\{A\rarr B\}$を排除する方針と，$\{A\rarr B, B\rarr C\}$に論理的に含意されている$\{A\rarr C\}$を排除する方針があります。それぞれについて，

• $\{A\rarr C,B\rarr C,C\rarr B\}$
• $\{A\rarr B,B\rarr C,C\rarr B\}$

が得られます。これらは，三つの条件を全て満たすため極小被覆となります。

参考文献