Boyce-Codd Normal Form

3NF의 빈틈

정규화에서 살펴본 3NF의 조건을 다시 정리하면 다음과 같다.

3NF 조건: 릴레이션 $R$에서 비자명한¹ 함수 종속 $X \to A$에 대해, $X$가 슈퍼키이거나 $A$가 주요 속성이어야 한다.

핵심은 "또는 $A$가 주요 속성이어야 한다"라는 예외 조항이다. 이 예외 때문에 후보 키에 포함된 속성이 비후보키 결정자에 의해 결정되는 상황이 3NF에서 허용된다. 다음 예제에서 이것이 어떤 문제를 일으키는지 확인해보자.

수강-지도 릴레이션

학생이 과목을 수강할 때 특정 교수의 지도를 받는 시스템을 생각하자. 다음과 같은 제약 조건이 존재한다.

• 한 학생은 같은 과목을 한 번만 수강할 수 있다.
• 한 교수는 정확히 한 과목만 담당한다.
• 한 과목은 여러 교수가 담당할 수 있다.

이 제약 조건에서 도출되는 함수 종속은 다음과 같다.

• $\{\text{학생}, \text{과목}\} \to \text{교수}$ : 학생과 과목이 정해지면 지도 교수가 결정된다.
• $\text{교수} \to \text{과목}$ : 교수를 알면 담당 과목이 결정된다.

후보 키를 찾아보자. $\{\text{학생}, \text{과목}\}$은 모든 속성을 결정하므로 후보 키다. $\{\text{학생}, \text{교수}\}$도 교수가 과목을 결정하므로 모든 속성을 결정할 수 있어 역시 후보 키다. 따라서 이 릴레이션에는 두 개의 후보 키가 존재한다.

3NF이지만 이상 현상이 남아 있다

이 릴레이션이 3NF를 만족하는지 점검하자. 문제가 될 수 있는 함수 종속은 $\text{교수} \to \text{과목}$이다. 교수는 슈퍼키가 아니다 — 교수만으로는 학생을 특정할 수 없으므로 모든 속성을 결정하지 못한다. 하지만 과목은 두 후보 키 모두에 포함된 주요 속성prime attribute이다. 3NF의 예외 조항에 의해 이 종속은 허용된다.

그런데 실제로 이 릴레이션은 이상 현상을 안고 있다.

• 새로 부임한 "정교수"가 "운영체제"를 담당한다는 정보를 저장하려면, 아직 수강 학생이 없으므로 학생 컬럼에 NULL을 넣어야 한다. 학생은 기본 키의 일부인데 NULL이 들어가면 기본 키 제약에 위배된다.

• "박교수"의 담당 과목이 "자료구조"에서 "데이터베이스"로 바뀌면, 박교수가 등장하는 행 두 개(김철수, 박민수)를 모두 수정해야 한다. 하나만 수정하면 같은 교수인데 담당 과목이 다른 모순이 발생한다.

• 이영희가 수강을 취소하면, "최교수 → 자료구조"라는 담당 정보까지 함께 소실된다.

이상 현상의 원인은 $\text{교수} \to \text{과목}$이라는 함수 종속에서 교수가 후보 키가 아닌 결정자라는 점이다. 3NF는 종속의 오른쪽(피결정자)이 주요 속성이면 허용하지만, 결정자 자체의 자격은 검사하지 않는다.

BCNF의 정의

BCNF는 3NF의 예외 조항을 제거한다.

BCNF 조건: 릴레이션 $R$에서 모든 비자명한 함수 종속 $X \to A$에 대해, $X$가 슈퍼키여야 한다.

3NF에서 허용하던 "$A$가 주요 속성이면 괜찮다"는 예외가 사라졌다. 오직 슈퍼키만이 다른 속성을 결정할 수 있다. 다시 말해, 모든 결정자determinant가 후보 키(또는 슈퍼키)여야 한다 (Codd, 1974).

수강-지도 릴레이션에서 $\text{교수} \to \text{과목}$의 결정자인 교수는 슈퍼키가 아니므로 BCNF를 위반한다. 이제 이 위반을 분해를 통해 해소해야 한다.

BCNF 분해 알고리즘

BCNF를 위반하는 함수 종속 $X \to A$를 발견하면, 릴레이션 $R$을 다음 두 릴레이션으로 분해한다.

$R_1 = \pi_{X \cup A}(R), \quad R_2 = \pi_{R - A}(R)$

즉, 위반하는 종속의 결정자와 피결정자를 하나의 릴레이션으로 추출하고, 원래 릴레이션에서 피결정자를 제거한다. 이 과정을 모든 릴레이션이 BCNF를 만족할 때까지 반복한다.

수강-지도 릴레이션에 적용하면, 위반 종속 $\text{교수} \to \text{과목}$에 대해 다음과 같이 분해된다.

교수-과목 릴레이션 ($R_1$)

학생-교수 릴레이션 ($R_2$)

교수-과목 릴레이션에서 교수는 기본 키이며, $\text{교수} \to \text{과목}$은 키에 의한 종속이므로 BCNF를 만족한다. 학생-교수 릴레이션에서 기본 키는 $\{\text{학생}, \text{교수}\}$이고 비자명한 함수 종속이 존재하지 않으므로² 역시 BCNF를 만족한다.

이상 현상이 해소되었다. "정교수 → 운영체제"를 교수-과목 릴레이션에 수강 학생 없이 삽입할 수 있고, 교수의 담당 과목 변경은 한 행만 수정하면 되며, 학생의 수강 취소가 교수-과목 관계를 소실시키지 않는다.

종속 보존의 트레이드오프

분해된 두 릴레이션을 다시 살펴보자. 원래 릴레이션에는 $\{\text{학생}, \text{과목}\} \to \text{교수}$라는 함수 종속이 있었다. 이 종속은 "한 학생은 같은 과목을 한 번만 수강한다"는 비즈니스 규칙을 반영한다.

그런데 분해 후에 이 종속을 검증할 수 있을까? 교수-과목 릴레이션에는 학생 속성이 없고, 학생-교수 릴레이션에는 과목 속성이 없다. $\{\text{학생}, \text{과목}\} \to \text{교수}$를 검증하려면 두 릴레이션을 조인해야만 한다. 이것이 종속 보존dependency preservation의 실패다.

종속 보존이 실패하면 실무적으로 두 가지 문제가 발생한다.

1. 단일 릴레이션의 제약 조건만으로는 비즈니스 규칙을 강제할 수 없다. 예를 들어 학생-교수 릴레이션에 (김철수, 최교수)를 삽입하면, 최교수도 자료구조를 담당하므로 김철수가 자료구조를 두 교수 밑에서 동시에 수강하는 모순이 발생할 수 있다. 이 위반은 두 릴레이션을 조인해야만 감지된다.
2. 조인 기반의 무결성 검사는 비용이 높다. 삽입이나 갱신 때마다 조인을 수행해야 하므로, 트랜잭션 처리량이 중요한 시스템에서는 실용적이지 않다. 이 경우 애플리케이션 레벨에서 트리거(trigger)나 어서션(assertion)으로 무결성을 보완해야 한다.

3NF와 BCNF 사이의 선택

이 트레이드오프가 3NF와 BCNF 사이의 선택을 결정한다.

정규화에 적었듯이 3NF까지는 무손실 조인과 종속 보존을 동시에 만족하는 분해가 항상 존재한다. BCNF에서는 무손실 조인은 보장되지만, 종속 보존은 희생될 수 있다. 실무에서는 대부분의 릴레이션이 3NF와 BCNF를 동시에 만족하며, 두 정규형이 충돌하는 경우는 위 예제처럼 후보 키가 여러 개이고 서로 겹치는 특수한 구조에서 발생한다.

BCNF 분해의 무손실 조인 증명

BCNF 분해가 항상 무손실 조인을 보장하는 이유를 확인하자. 위반 종속 $X \to A$에 대해 $R$을 $R_1(X, A)$과 $R_2(R - A)$로 분해했다.

$R_1$과 $R_2$의 공통 속성은 $X$이다. $R_1$은 $\{X, A\}$로만 구성되어 있고 $X \to A$가 성립하므로, $X$는 $R_1$의 모든 속성을 결정한다. 즉 $X$가 $R_1$의 슈퍼키다. Heath의 정리³에 의해 이 분해는 무손실 조인이다.

이 성질은 분해를 반복해도 유지되므로, BCNF 분해 알고리즘의 최종 결과는 항상 무손실 조인을 만족한다.

3NF와 BCNF가 동치인 경우

모든 릴레이션에서 3NF와 BCNF가 충돌하는 것은 아니다. 다음 조건 중 하나라도 만족하면 3NF인 릴레이션은 자동으로 BCNF도 만족한다.

1. 모든 후보 키가 단일 속성인 경우. BCNF 위반 종속 $X \to A$가 존재한다면 $X$는 슈퍼키가 아니다. 3NF의 예외 조항이 적용되려면 $A$가 주요 속성이어야 하는데, 후보 키가 모두 단일 속성이면 $A$ 자체가 후보 키, 즉 슈퍼키가 된다. 그러면 $X \to A$와 $A \to R$에 의해 $X$도 슈퍼키가 되어 모순이다.
2. 후보 키가 정확히 하나이고 단일 속성인 경우. 위 조건의 특수한 형태로, 역시 같은 논리로 3NF와 BCNF가 동치가 된다⁴.

실무에서 설계하는 릴레이션 대부분은 이 조건 중 하나에 해당하므로, 3NF와 BCNF의 차이가 문제되는 경우는 상대적으로 드물다. 그럼에도 BCNF를 이해해야 하는 이유는, 후보 키가 복합적이고 서로 겹치는 릴레이션에서 발생하는 미묘한 이상 현상을 설명하는 유일한 도구이기 때문이다.

---

출처

• Codd, E. (1974) 'Recent Investigations in Relational Data Base Systems', Proceedings of the IFIP Congress, pp. 1017–1021.
• Elmasri, R. and Navathe, S. (2015) Fundamentals of Database Systems. 7th edn. Pearson.
• Silberschatz, A., Korth, H. and Sudarshan, S. (2019) Database System Concepts. 7th edn. McGraw-Hill.
• Bernstein, P. (1976) 'Synthesizing Third Normal Form Relations from Functional Dependencies', ACM Transactions on Database Systems, 1(4), pp. 277–298.

각주

1. 비자명한 함수 종속nontrivial functional dependency이란 피결정자가 결정자의 부분집합이 아닌 경우를 말한다. $X \to A$에서 $A \subseteq X$이면 항상 성립하는 자명한 종속이므로 정규형 판별에서 제외한다. ↩

2. 학생-교수 릴레이션에서 $\text{학생} \to \text{교수}$는 성립하지 않는다. 한 학생이 여러 교수에게 지도받을 수 있기 때문이다. $\text{교수} \to \text{학생}$도 성립하지 않는다. 한 교수가 여러 학생을 지도하기 때문이다. 따라서 기본 키 $\{\text{학생}, \text{교수}\}$ 전체만이 유일한 결정자이며, 이는 슈퍼키이므로 BCNF를 만족한다. ↩

3. Heath의 정리(1971). $R_1 \cap R_2$가 $R_1$ 또는 $R_2$의 슈퍼키이면 분해는 무손실 조인이다. 상세한 설명은 Normalization에 있다. ↩

4. "단일 속성"이라는 조건이 중요하다. 후보 키가 하나이더라도 복합 키이면 3NF ≠ BCNF인 경우가 존재한다. 예를 들어 $R(A, B, C)$에서 후보 키가 $\{A, B\}$이고 $C \to B$라는 종속이 있으면, $B$는 주요 속성이므로 3NF를 만족하지만 $C$는 슈퍼키가 아니므로 BCNF를 위반한다. ↩