> [!abstract] Introduction > [[Normalization]]에서 3NF까지 적용하면 대부분의 이상 현상이 해소됩니다. 그러나 3NF는 비주요 속성에 대한 규칙만 정의할 뿐, 주요 속성*prime attribute*이 관여하는 함수 종속까지 통제하지는 못합니다. Boyce-Codd 정규형*Boyce-Codd Normal Form*, BCNF는 이 빈틈을 메우는 더 강한 조건으로, "모든 결정자가 후보 키여야 한다"는 단순하지만 강력한 원칙을 제시합니다. 이 글에서는 3NF로는 해결되지 않는 이상 현상을 구체적 예제로 살펴보고, BCNF 분해 알고리즘과 그에 수반되는 종속 보존 트레이드오프를 다룹니다. ## 3NF의 빈틈 [[Normalization]]에서 살펴본 3NF의 조건을 다시 정리하면 다음과 같다. > **3NF 조건**: 릴레이션 $R$에서 비자명한[^trivial-fd] 함수 종속 $X \to A$에 대해, $X$가 슈퍼키이거나 $A$가 주요 속성이어야 한다. 핵심은 "또는 $A$가 주요 속성이어야 한다"라는 예외 조항이다. 이 예외 때문에 후보 키에 포함된 속성이 비후보키 결정자에 의해 결정되는 상황이 3NF에서 허용된다. 다음 예제에서 이것이 어떤 문제를 일으키는지 확인해보자. ### 수강-지도 릴레이션 학생이 과목을 수강할 때 특정 교수의 지도를 받는 시스템을 생각하자. 다음과 같은 제약 조건이 존재한다. - 한 학생은 같은 과목을 한 번만 수강할 수 있다. - 한 교수는 정확히 한 과목만 담당한다. - 한 과목은 여러 교수가 담당할 수 있다. 이 제약 조건에서 도출되는 함수 종속은 다음과 같다. - $\{\text{학생}, \text{과목}\} \to \text{교수}$ — 학생과 과목이 정해지면 지도 교수가 결정된다. - $\text{교수} \to \text{과목}$ — 교수를 알면 담당 과목이 결정된다. 후보 키를 찾아보자. $\{\text{학생}, \text{과목}\}$은 모든 속성을 결정하므로 후보 키다. $\{\text{학생}, \text{교수}\}$도 교수가 과목을 결정하므로 모든 속성을 결정할 수 있어 역시 후보 키다. 따라서 이 릴레이션에는 두 개의 후보 키가 존재한다. | <u>학생</u> | <u>과목</u> | 교수 | |------|------|------| | 김철수 | 자료구조 | 박교수 | | 김철수 | 알고리즘 | 이교수 | | 이영희 | 자료구조 | 최교수 | | 박민수 | 자료구조 | 박교수 | | 박민수 | 알고리즘 | 이교수 | ### 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). ![[bcnfVenn.svg]] 수강-지도 릴레이션에서 $\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$) | <u>교수</u> | 과목 | |------|------| | 박교수 | 자료구조 | | 이교수 | 알고리즘 | | 최교수 | 자료구조 | **학생-교수** 릴레이션 ($R_2$) | <u>학생</u> | <u>교수</u> | |------|------| | 김철수 | 박교수 | | 김철수 | 이교수 | | 이영희 | 최교수 | | 박민수 | 박교수 | | 박민수 | 이교수 | 교수-과목 릴레이션에서 교수는 기본 키이며, $\text{교수} \to \text{과목}$은 키에 의한 종속이므로 BCNF를 만족한다. 학생-교수 릴레이션에서 기본 키는 $\{\text{학생}, \text{교수}\}$이고 비자명한 함수 종속이 존재하지 않으므로[^no-fd-r2] 역시 BCNF를 만족한다. 이상 현상이 해소되었다. "정교수 → 운영체제"를 교수-과목 릴레이션에 수강 학생 없이 삽입할 수 있고, 교수의 담당 과목 변경은 한 행만 수정하면 되며, 학생의 수강 취소가 교수-과목 관계를 소실시키지 않는다. ## 종속 보존의 트레이드오프 분해된 두 릴레이션을 다시 살펴보자. 원래 릴레이션에는 $\{\text{학생}, \text{과목}\} \to \text{교수}$라는 함수 종속이 있었다. 이 종속은 "한 학생은 같은 과목을 한 번만 수강한다"는 비즈니스 규칙을 반영한다. 그런데 분해 후에 이 종속을 검증할 수 있을까? 교수-과목 릴레이션에는 학생 속성이 없고, 학생-교수 릴레이션에는 과목 속성이 없다. $\{\text{학생}, \text{과목}\} \to \text{교수}$를 검증하려면 **두 릴레이션을 조인해야만** 한다. 이것이 종속 보존*dependency preservation*의 실패다. 종속 보존이 실패하면 실무적으로 두 가지 문제가 발생한다. 첫째, 단일 릴레이션의 제약 조건만으로는 비즈니스 규칙을 강제할 수 없다. 예를 들어 학생-교수 릴레이션에 (김철수, 최교수)를 삽입하면 — 최교수도 자료구조를 담당하므로 — 김철수가 자료구조를 두 교수에게 동시에 수강하는 모순이 발생할 수 있다. 이 위반은 두 릴레이션을 조인해야만 감지된다. 둘째, 조인 기반의 무결성 검사는 비용이 높다. 삽입이나 갱신 때마다 조인을 수행해야 하므로, 트랜잭션 처리량이 중요한 시스템에서는 실용적이지 않다. 이 경우 애플리케이션 레벨에서 트리거*trigger*나 어서션*assertion*으로 무결성을 보완해야 한다. ### 3NF와 BCNF 사이의 선택 이 트레이드오프가 3NF와 BCNF 사이의 선택을 결정한다. | | 3NF | BCNF | |---|-----|------| | 이상 현상 | 주요 속성 관련 이상 가능 | 함수 종속 기반 이상 완전 제거 | | 무손실 조인 | 항상 보장 | 항상 보장 | | 종속 보존 | 항상 보장 | 보장되지 않을 수 있음 | | 적용 시점 | 종속 보존이 중요한 경우 | 데이터 무결성이 최우선인 경우 | [[Normalization]] 포스트에서 언급했듯, 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의 정리[^heath-theorem-ref]에 의해 이 분해는 무손실 조인이다. 이 성질은 분해를 반복해도 유지되므로, BCNF 분해 알고리즘의 최종 결과는 항상 무손실 조인을 만족한다. ## 3NF와 BCNF가 동치인 경우 모든 릴레이션에서 3NF와 BCNF가 충돌하는 것은 아니다. 다음 조건 중 하나라도 만족하면 3NF인 릴레이션은 자동으로 BCNF도 만족한다. 첫째, 후보 키가 하나뿐인 경우. 3NF 예외 조항이 작동하려면 $A$가 주요 속성이어야 하는데, 후보 키가 하나이고 $X$가 슈퍼키가 아니라면 $A$가 주요 속성이 되기 어렵다[^single-candidate-key]. 둘째, 모든 후보 키가 단일 속성인 경우. 비후보키 결정자 $X$에 의해 결정되는 속성이 주요 속성이 되려면 후보 키에 포함되어야 하는데, 후보 키가 단일 속성이면 그 속성 자체가 슈퍼키가 되어 모순이다. 셋째, 비주요 속성이 없는 경우. 모든 속성이 어떤 후보 키에 포함되어 있다면, 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. [^trivial-fd]: 비자명한 함수 종속*nontrivial functional dependency*이란 피결정자가 결정자의 부분집합이 아닌 경우를 말한다. $X \to A$에서 $A \subseteq X$이면 항상 성립하는 자명한 종속이므로 정규형 판별에서 제외한다. [^no-fd-r2]: 학생-교수 릴레이션에서 $\text{학생} \to \text{교수}$는 성립하지 않는다. 한 학생이 여러 교수에게 지도받을 수 있기 때문이다. $\text{교수} \to \text{학생}$도 성립하지 않는다. 한 교수가 여러 학생을 지도하기 때문이다. 따라서 기본 키 $\{\text{학생}, \text{교수}\}$ 전체만이 유일한 결정자이며, 이는 슈퍼키이므로 BCNF를 만족한다. [^heath-theorem-ref]: Heath의 정리(1971). $R_1 \cap R_2$가 $R_1$ 또는 $R_2$의 슈퍼키이면 분해는 무손실 조인이다. 상세한 설명은 [[Normalization]]을 참고하라. [^single-candidate-key]: 엄밀히 말하면, 후보 키가 하나이고 단일 속성이면 항상 성립한다. 후보 키가 하나이더라도 복합 키이면 3NF ≠ BCNF인 경우가 존재할 수 있다. 예를 들어 $R(A, B, C)$에서 후보 키가 $\{A, B\}$이고 $C \to B$라는 종속이 있으면 3NF($B$는 주요 속성)이지만 BCNF($C$는 슈퍼키가 아님)는 위반한다.