データベーススペシャリスト 2016年 午前2 問03

関数従属の推移【午前2解説】

正解の理由

解法ステップ

1. 与えられた関数従属性を整理する： $A\to B,B\to C$。
2. 推移律（transitivity）を使う： $A\to B$ と $B\to C$ から $A\to C$ を得る。
3. 拡大律（augmentation）で属性を付ける： $A\to B$ から $AC\to BC$ を得る。
4. 分解律（decomposition）で右辺を分ける： $AC\to BC$ から $AC\to B$（および $AC\to C$）を得る。
5. 包含律（反射律／reflexivity）により、任意の集合はその部分集合を決定する： 例えば $\{A,B,C\}\to \{A,B\}$ や $AC\to A$ は自明に成立する。
6. 上の手順で各選択肢の導出可否を判定する（属性閉包を用いるのが確実）。

選択肢別の誤答解説

• ア: {A, B, C} → {A, B}
  包含律（反射律）により自明に成立します。任意集合はその部分集合を決定するため、{A,B,C}→{A,B} は真です。
• イ: {A, C} → {A, B}
  $A\to B$ を拡大律で右辺に C を付けて $AC\to BC$ とし、分解律で $AC\to B$ を取り出せます。さらに包含律で $AC\to A$ も成立するため、{A,C}→{A,B} は導けます。
• ウ: {A, C} → {A, B, C}
  上記の理由に加え、$AC\text{toA}$（包含律）と $AC\to B$（拡大＋分解）および $AC\to C$（包含律）より $AC\to ABC$ が成立します。したがってウも導けます。
• エ: {B, C} → {A, C}
  これを成立させるには ${B,C}^{+}$（属性閉包）に A が含まれている必要があります。${B,C}^{+}$ を計算すると初期で {B,C} があり、$B\to C$ は既に C を含むため新しい属性を得られません。$A\to B$ は逆方向なので A を導けず、閉包に A は含まれません。従って {B,C}→{A,C} は導けません（選択肢エが導けない）。

よくある誤解

• 「ある属性集合がその部分集合を決定するのは拡大律で説明できる」と考える誤り。部分集合を決定する自明な関係は包含律（反射律）によるものであり、拡大律は X→Y から XZ→YZ を導く規則です。両者を混同しないこと。
• 関数従属は双方向だと誤解する（X→Y が成り立つと Y→X も成り立つと誤認する）。方向性が重要で、逆は一般に成り立ちません。
• 「右辺に属性があれば、その属性を含む任意の集合が左辺を決定する」と思う誤り。左辺の閉包に右辺が含まれるかをチェックする必要があります（属性閉包の計算が確実）。

補足コラム

1. 初期集合を X+ に入れる。
2. 既知の関数従属 Y→Z で Y⊆X+ となるものを見つけ、Z を X+ に追加する。
3. 追加がなくなるまで 2 を繰り返す。

• 計算 $A^{+}$: 初期 {A} → $A\to B$ より {A,B}、さらに $B\to C$ より {A,B,C}。従って A は関係 R のキーになっています。
• 計算 ${B,C}^{+}$: 初期 {B,C} → $B\to C$ は既に C を含むため何も増えず、${B,C}^{+}=B,C$。A は含まれません。

def closure(attrs, fds):
    closure = set(attrs)
    changed = True
    while changed:
        changed = False
        for left, right in fds:
            if set(left).issubset(closure) and not set(right).issubset(closure):
                closure |= set(right)
                changed = True
    return closure

fds = [("A","B"), ("B","C")]
print(closure("BC", fds))  # 出力: {'B','C'}
print(closure("A", fds))   # 出力: {'A','B','C'}

FAQ