基本情報技術者 2014年 春期 午前（科目A） 問26

依存性保存と無損失分解【午前解説】

正解の理由

• a→b, a→c, a→d, a→e
• b→f, b→g
• c→g, c→h
• d→i
• e→i, e→j

1. 無損失分解（lossless）：元の関係の候補キーが a であることを示せるため、テーブル1 がそのキー a を含んでおり、全体の分解は無損失となる。具体的に $a^{+}$ を計算すると全属性を含むため $a$ は候補キーです。したがってテーブル1 を含む分解は結合して元に戻せます。
2. 可能な限りの従属性を各テーブルに局所的に保持している：b→f,b→g はテーブル2 に、e→i,e→j はテーブル3 に、a→b,c,d,e はテーブル1 に含まれ、直接検査できるようになっています。

解法ステップ

1. 図から全ての基本FDを列挙する（上に示した一覧）。
2. 候補キーを求める：$a$ の閉包を計算する。
   • $a^{+}$ は a→b,c,d,e により {a,b,c,d,e} を含む。
   • さらに b→f,g、c→h、d→i、e→i,j を順に適用すると最終的に全属性 {a…j} を含む。よって $a$ が候補キーである。
   • 表現： $a^{+}=\{a,b,c,d,e,f,g,h,i,j\}$。
3. 各選択肢について、いずれかのテーブルが原関係の候補キーを含むか（無損失の簡便条件）、および各FDの左右が同一テーブルに含まれるか（依存性保存の観点）を確認する。
4. 無損失かつ実務上妥当な依存性配置を満たす組合せを選ぶ。

選択肢別の誤答解説

• ア: テーブル1 に a 単独、テーブル2 に (b,c,d,e)、テーブル3 に (f,g,h,i,j)。
  • 問題点：原関係の候補キー a を含むテーブルが a 単独では派生属性（b,c,d,e）を保持しないため、a による全属性の復元ができない。無損失条件を満たさない（少なくとも容易に示せるキー包含がない）。
• ウ: テーブル1 (a,b,f,g,h)、テーブル2 (c,d)、テーブル3 (e,i,j)。
  • 問題点：a→c,d,e のうち c,d,e が分散している。特に a が原関係の候補キーであるにもかかわらず、候補キーを含むテーブルが完全ではなく、無損失性の簡便条件が満たされない。また c→g,h を保持する配置になっていない。
• エ: テーブル1 (a,c,d)、テーブル2 (b,f,g,h)、テーブル3 (e,i,j)。
  • 問題点：a→b が満たされない（b が別テーブル）。結果として a が候補キーであることを利用できず、無損失の確認ができない。さらに b→f,g はテーブル2 で良いが a に関する従属性の分散が大きい。

よくある誤解

1. 無損失分解＝依存性保存だと誤解する
   • 無損失（結合で元に戻せる）と依存性保存（各 FD を個々の分解表で検査可能）は別概念です。分解は無損失でも一部の FD がテーブル単位では検査できないことがあります（本問では c→g,c→h,d→i が該当）。
2. トランジティブに左辺が変わると自動的に FD が保存されると考える誤り
   • a→b と b→g があっても、それが c→g を導出するわけではありません。導出可能かは属性間の関係で決まります。
3. 「左右が別テーブルなら必ずダメ」との短絡判断
   • 別テーブルに分かれていても分解が無損失であれば情報は失われず、結合して検査すれば元の従属性を確認できます。運用上はトレードオフ（性能/制約チェックの場所）を検討します。

補足コラム

• 依存性の投影（projection）：あるテーブルスキーマに対して元の FD 群からそのスキーマ上で成立する FD を求める操作を「投影」と言います。本問では投影結果をテーブルごとに列挙すると保存される従属性が明確になります。
  • テーブル1 (a,b,c,d,e) に投影される FD： a→b,c,d,e（およびその派生）
  • テーブル2 (b,f,g,h) に投影される FD： b→f,g
  • テーブル3 (e,i,j) に投影される FD： e→i,j
    これらの合併が元の FD 群と一致しない場合、依存性は保存されていないことになります。
• 無損失の簡便チェック：分解のうちどれか一つの分割部が原関係のスーパーキー（候補キー）を含むなら、その分解は無損失になります。本問では a が原関係の候補キーであり、テーブル1 に a が含まれるため条件を満たします。

FAQ