[함수종속] 최소 집합(Minimal Cover)

F = { AB → D, B → CD, A → BC } 의 최소 커버(Minimal Cover, Canonical Cover)를 구하는 과정

 

[Step 1] 우변(피결정자)의 속성 분해 (Decomposition)

먼저, 모든 함수적 종속성의 우변(Right-Hand Side)에 하나의 속성만 오도록 분해합니다.

(암스트롱의 분해 규칙 적용)

• AB → D (변경 없음)
• B → CD ▶ B → C, B → D
• A → BC ▶ A → B, A → C

현재 집합 F_1: { AB → D, B → C, B → D, A → B, A → C }

---

[Step 2] 좌변(결정자)의 불필요한 속성 제거 (LHS Simplification)

좌변에 두 개 이상의 속성이 있는 경우(여기서는 $AB \rightarrow D$), 일부 속성을 제거해도 종속성이 성립하는지 확인합니다.

1. 대상: AB → D
2. 검증: A를 제거하고 B → D가 성립하는가?
   • 현재 집합 F_1에 이미 B → D가 존재합니다.
   • 따라서 AB → D에서 A는 불필요한 속성(Extraneous Attribute)입니다.
   • 더 나아가, B → D가 이미 리스트에 있으므로 AB → D 규칙 자체가 중복이 되어 제거됩니다.

현재 집합 F_2: { B → C, B → D, A → B, A → C }

---

[Step 3] 중복되는 함수 종속성 제거 (Redundancy Removal)

남은 종속성들끼리 서로 유도 가능한지(이행성 등) 확인하여 중복을 제거합니다.

1. A → C 검증:
   • 나머지 규칙들(A → B, B → C)을 봅니다.
   • A는 B를 결정하고(A → B), 그 B는 다시 C를 결정합니다(B → C).
   • 이행성 규칙(A → B → C)에 의해 A → C는 자동으로 성립합니다.
   • 따라서 A → C는 중복이므로 제거합니다.
2. 나머지 검증:
   • A → B: 다른 규칙으로 유도 불가 (필수)
   • B → C: 다른 규칙으로 유도 불가 (필수)
   • B → D: 다른 규칙으로 유도 불가 (필수)

최종 집합: { A → B, B → C, B → D }

---