応用情報技術者 2016年 春期 午前2 問27

3NF分解の合成法【午前2解説】

正解の理由

解法ステップ

1. 与えられた関係 R(a,b,c,d,e) と図示された従属を列挙する。図は次の FD を表すと読むのが自然：
   • a → b, a → c, a → d, a → e
   • b → c, b → e
2. RHS を分解し，冗長な従属を削る（最小被覆の作成）：
   • a → c は a → b と b → c から透過的に導ける → 削除
   • a → e は a → b と b → e から導ける → 削除 → 残る最小被覆：a → b, a → d, b → c, b → e
3. 合成法（最小被覆の各 FD の LHS と RHS をまとめる）：
   • a → b と a → d は LHS が同じ → R1(a,b,d)
   • b → c と b → e は LHS が同じ → R2(b,c,e)
4. 候補キーの確認（元の関係 R に対して）：
   • a+ = {a} → b (a→b) → c (b→c) → e (b→e) → d (a→d) ⇒ a+ = {a,b,c,d,e}，よって a が候補キー
   • よって a を含む部分スキーマがあれば lossless-join 条件は満たしやすい
5. 選択肢と照合：
   • 選択肢エは (a,b,d),(b,c),(b,d,e) を並べた構成で，(a,b,d) は上記 R1 に一致。
   • 残る属性群 b,c,e を (b,c) と (b,d,e) に分けても，結合によって元の b,c,e の情報を復元でき，FD も保存されるため妥当な分解である。

選択肢別の誤答解説

• ア: (a,b,c,d) と (b,d,e) に分ける構成。ここで (a,b,c,d) に a→b,a→c,a→d が入るが，b→e が保存されるためには (b,e) を持つスキーマが必要。アは b→c,b→e の両方を保存できないため依存性保存性を欠く。
• イ: (a,b,c,d),(b,c),(b,d,e) の3分割。左側に a を含むが，冗長に (b,c) を別に置いているので依存性や鍵の配置はやや冗長。選択肢エの方が最小被覆由来の分解に忠実。
• ウ: (a,b,d) と (b,d,c,e) の2分割。後者のスキーマは (b,c,e,d) をまとめたもので，a を含むスキーマが 1 つだけなので結合の可逆性は保たれるが，通常の合成法で得られる構成とは異なる整理のされ方をしており，選択肢エが合成法の手順により自然に対応する。

よくある誤解

1. 「最小被覆作成で RHS のまとめ忘れ」
   RHS を分解しておかないと，合成法で作るスキーマが不適切になりやすい（たとえば a → bc を a → b,c に分けずに扱うと候補キーや部分スキーマの集合がずれる）。
2. 「投影される FD の判定の誤り」
   あるスキーマに投影されたときにどの FD が残るかを正確に判断しないと，そのスキーマが 3NF を満たすかどうかの判定を誤る。投影は元の FD から導かれるすべての FD を考慮する必要がある。
3. 「部分スキーマの追加・分割を勝手にすると依存性保存や可逆性を壊す」
   分解・再結合は可逆性（lossless）と依存性保存を必ずチェックすること。単に属性を分けただけでは正規化の目的を達さない可能性がある。

補足コラム

• 合成法（synthesis algorithm）は，最小被覆を作り，LHS が同じ FD をまとめて部分スキーマを作る手順です。この方法は「依存性保存」と「実用的に損失のない結合（lossless-join）」を満たすことが保証されているので，試験問題の解法として標準的かつ安全です。
• 最小被覆の作り方は（1）RHS を単一属性に分解，（2）LHS の冗長属性を削除，（3）冗長な FD を削除、の順で行います。実務でも正規化設計の基礎となる重要な手順です。

FAQ