データベーススペシャリスト 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