データベーススペシャリスト 2022年 午前2 問04

関数従属の最小被覆【午前2解説】

正解の理由

• A→B, B→C, C→B, {A,D}→E （これがX）
• A→C, B→C, C→B, {A,D}→E （これがY）

解法ステップ

1. Wを単項右辺に分解する。
   • A→{B,C} をA→B, A→Cに分解。
   • 他は既に単項右辺（{A,D}→E, {A,C,D}→E, B→C, C→B）。
   • 結果: A→B, A→C, {A,D}→E, {A,C,D}→E, B→C, C→B。
2. 左辺の最小化（各従属の左辺属性が不要か検査）。
   • {A,C,D}→Eは左辺のA,Dだけで十分かを確認。{A,D}→Eが既にあるため {A,C,D}→Eは冗長（左辺を減らしても別に {A,D}→Eがある）で削除可能。
   • {A,D}→Eの左辺のAまたはDを外せない（単独ではEを導けない）のでそのまま。
3. 従属そのものの冗長性検査（ある従属が他の従属から導出可能か）。
   • A→CはA→BとB→Cがあるとき、A→BとB→CよりA→Cが導出可能：A→B, B→C ⇒ A→C。従ってA→Cは冗長となる（ただしA→Bを削除した場合は話が変わる）。
   • {A,C,D}→Eは {A,D}→Eがあれば冗長（部分集合左辺が存在するため）なので削除。
   • B→CとC→Bは互いに独立に必要（どちらか一方から他方は導けない）。
4. 得られる最小被覆の候補
   • X: A→B, B→C, C→B, {A,D}→E（上記操作で得られる標準的な最小被覆）
   • 別の等価な最小被覆としてY: A→C, B→C, C→B, {A,D}→E（A→Bを削除しA→Cを残すことで成立）
   • Zは {A,C,D}→Eを残しB→Cを削除しているなどでWの冗長除去として適切でない

選択肢別の誤答解説

• ア: Xだけ
  • Xは正しい最小被覆だが、YもWから冗長を取り除いた別の等価な最小被覆であるため「Xだけ」は誤り。
• イ: XとY
  • 正しい。前述の通りXとYはどちらもWと同じ意味（同じ閉包）を保ちながら冗長性を除去した最小被覆である。
• ウ: YとZ
  • Yは正しいがZは不適切。Zは {A,C,D}→Eのように左辺が冗長な従属を残しており、またB→Cを欠いているためWの冗長除去の結果として妥当でない。
• エ: Zだけ
  • 間違い。Zは既に述べたようにWからの冗長除去として正しくない（部分左辺の冗長を除去しておらず、元の依存を保持していない）。

よくある誤解

• 「最小被覆は一意である」
  • 誤り。最小被覆は一意とは限らず、同値な（同じ閉包を持つ）複数の最小被覆が存在することがある（本問のXとYがその例）。
• 「右辺を単項にすればそれで終わり」
  • 右辺を単項にするのは第一段階だが、その後に左辺の不要属性除去と、従属自体が他から導出可能かのチェックを必ず行う必要がある。

補足コラム

1. 右辺を単項に分解（A→BCをA→B, A→Cに分解）。
2. 各従属について左辺の各属性が不要か検査して取り除く（属性Xを外しても右辺が導出可能かをclosureで確認）。
3. 従属自体が他の従属から導出可能か（冗長か）を検査し、導出可能なら削除する。

FAQ