[데이터베이스 설계] 함수 종속성 이론과 스키마 분해

1. 복잡한 함수 종속성 다듬기: 정규형 커버 (Canonical Cover)

- 주어진 함수 종속성(FD) 집합이 복잡하거나 불필요한 정보를 포함하는 경우에 '정규형 커버(Canonical Cover)' 사용 

 

정규형 커버란?

• 정규형 커버는 주어진 FD 집합 F와 논리적으로 동등하면서, 더 이상 단순화할 수 없는 최소한의 FD 집합

- Fc​를 의미

- 즉, F로부터 유추할 수 있는 모든 종속 관계를 Fc​로부터도 똑같이 유추 (F+=Fc+​).

- 정규형 커버는 다음 세 가지 조건을 만족해야 함

1. 불필요한 속성(Extraneous Attribute)이 없음
2. 모든 FD의 왼쪽(결정자)은 유일(Unique)함
3. 불필요한 FD가 없음

---

정규형 커버 계산 과정

• 정규형 커버는 다음과 같은 단계를 통해 계산
  
  

1. 결합 (Union Rule):
   - FD들의 결정자(LHS)가 같다면, 종속자(RHS)들을 하나로 합침
   - 예를 들어, ${A \rightarrow B, A \rightarrow C}$는 A→BC로 합칠 수 있음
2.  
   • 결정자(LHS)의 불필요한 속성 확인: 
     - AB→C에서 A가 불필요한지 확인하려면, A를 제외한 B만으로 C를 결정할 수 있는지(B→C)를 기존 FD 집합으로 증명
   • 종속자(RHS)의 불필요한 속성 확인: 
     - A→BC에서 C가 불필요한지 확인하려면, 해당 FD를 A→B로 바꾼 상태에서 여전히 A→C가 전체 FD 집합으로부터 유추되는지 확인
3. 불필요한 속성 제거:
   - 결정자 또는 종속자에 불필요한(extraneous) 속성이 있는지 확인하고 제거
4. 불필요한 FD 제거:
   - 특정 FD 전체가 다른 FD들에 의해 유추될 수 있다면 해당 FD를 제거

이 과정을 반복하면 최종적으로 가장 간결한 형태의 FD 집합인 정규형 커버를 얻을 수 있음

---

2. 스키마 분해의 핵심 원칙: 종속성 보존

• 스키마를 정규화하기 위해 테이블을 분해(Decomposition)할 때, 두 가지 목표를 달성
• 바로 무손실 조인(Lossless Join)과 종속성 보존(Dependency Preservation)

- 종속성 보존이란, 원래 스키마의 모든 함수 종속성을 분해된 테이블들 내에서 각각 검증할 수 있는 상태를 의미

- 만약 분해가 종속성을 보존하지 못한다면, 원래의 FD를 검증하기 위해 분해된 테이블들을 다시 조인(Join)해야 하는 상황이 발생

- 이는 데이터 삽입, 수정, 삭제 시에 큰 비용을 유발할 수 있으므로 매우 중요한 원칙

---

3. BCNF와 3NF 분해 알고리즘

BCNF (Boyce-Codd Normal Form)

• 테스트 방법:
  - 어떤 릴레이션 스키마 R이 BCNF를 만족하는지 확인하려면, 해당 스키마에 적용되는 모든 함수 종속성 α→β에 대해 결정자 α가 R의 슈퍼키(Superkey)인지 검사
  
• 주의할 점:
  - 최초의 스키마를 검증할 때는 주어진 FD 집합 F만 확인해도 충분하지만, 스키마가 분해된 후에는 F의 전체 폐포(F+)에 속하는 모든 FD를 고려
  - 예를 들어 $F = {A \rightarrow B, B \rightarrow C}$가 주어졌을 때, $R(A, C, D)$라는 스키마는 F에 속한 FD만으로는 BCNF 위반이 없어 보이지만, $F^+$에 포함된 A→C에 의해 BCNF를 위반하게 됨
  
   
• 분해 알고리즘:
  - BCNF가 아닌 릴레이션을 발견하면, BCNF를 위반하는 FD(α→β)를 기준으로 $(\alpha \cup \beta)$와 (R−β) 두 개의 릴레이션으로 분해하는 과정을 반복

3NF (Third Normal Form)

• 특징:
  - BCNF보다 조금 완화된 정규형으로, BCNF 분해 시 발생할 수 있는 '종속성 보존 실패' 문제를 해결하기 위해 사용
  - 항상 무손실 조인과 종속성 보존을 만족하는 분해가 가능
• 분해 알고리즘: 3NF 분해는 다음 단계를 따름.
  
  1. 주어진 FD 집합의 정규형 커버(Fc​)를 계산
  2. Fc​에 있는 각 FD α→β에 대해, 하나의 릴레이션 스키마(α∪β)를 생성
  3. 만들어진 릴레이션 중에 원래 스키마 R의 후보 키(Candidate Key)를 포함하는 릴레이션이 하나도 없다면, 후보 키만으로 구성된 릴레이션을 추가로 생성
  4. (선택) 다른 릴레이션에 완전히 포함되는 중복 릴레이션이 있다면 제거