冗長な関数従属性の排除

関数従属集合 $W$ の冗長性を順に検証し、極小被覆（最小被覆）を求めます： 1. 右辺の単一属性化：$A \to \{B, C\}$ は分解規則により $A \to B$ と $A \to C$ に分解されます。 2. 推移律による冗長性の排除： - $B \to C$ と $C \to B$（$B$ と $C$ の相互従属）が存在するため、 ・$A \to B$ と $B \to C$ から $A \to C$ が導出できるため、$A \to C$ は冗長として除去可能。 ・逆に $A \to C$ と $C \to B$ から $A \to B$ が導出できるため、$A \to B$ を冗長として除去することも可能。 3. 左辺（決定子）の冗長性の排除： - $\{A, D\} \to E$ が成立する場合、$A \to C$ より $\{A, D\} \subseteq \{A, C, D\}$ なので、$\{A, C, D\} \to E$ の左辺にある $C$ は冗長であり、$\{A, C, D\} \to E$ は除去されます。 したがって、極小被覆としては以下の2組が成立します： ・$X = \{A \to B, B \to C, C \to B, \{A, D\} \to E\}$ ・$Y = \{A \to C, B \to C, C \to B, \{A, D\} \to E\}$ 一方、$Z$ は $\{A, C, D\} \to E$ の左辺の冗長性（$C$）が排除されておらず、また $B \to C$ も欠落しているため不適切です。 よって、冗長な関数従属をなくしたものは $X$ と $Y$ であり、イ が正解です。 $Y$ も $A o C$ を残して $A o B$ を排除した正しい極小被覆であるため、$X$ だけとするのは誤りです。 $Z$ は決定子に冗長な属性 $C$ を含んでおり、冗長性が排除されていません。 $Z$ は冗長性が残存しているため誤りです。

関係 R(A,B,C,D,E)R(A, B, C, D, E) に対し, 関数従属の集合 W={A→{B,C},{A,D}→E,{A,C,D}→E,B→C,C→B}W = \{A \to \{B, C\}, \{A, D\} \to E, \{A, C, D\} \to E, B \to C, C \to B\} がある。関数従属の集合 X,Y,ZX, Y, Z のうち, WW の冗長な関数従属をなくしたものはどれか。

X={A→B,B→C,C→B,{A,D}→E}X = \{A \to B, B \to C, C \to B, \{A, D\} \to E\} Y={A→C,B→C,C→B,{A,D}→E}Y = \{A \to C, B \to C, C \to B, \{A, D\} \to E\} Z={A→B,C→B,{A,C,D}→E}Z = \{A \to B, C \to B, \{A, C, D\} \to E\}

出典2022r04a_db_am2_問4
ア
XX だけ
イ
XX と YY
ウ
YY と ZZ
エ
ZZ だけ