【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\}$

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

参考文献

オーム社
¥1,500 (2024/05/19 21:58時点 | Amazon調べ)
シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.