> [!abstract] Introduction > [[Boyce-Codd Normal Form|BCNF]]까지 적용하면 함수 종속에 의한 이상 현상은 모두 제거됩니다. 그러나 하나의 속성이 다른 속성의 **값 집합**을 독립적으로 결정하는 다치 종속*Multivalued Dependency*, MVD이 존재하면, BCNF를 만족하는 릴레이션에서도 중복이 발생합니다. 이 글에서는 다치 종속의 개념과 이를 해소하는 제4정규형*4NF*, 그리고 조인 종속*join dependency*과 제5정규형*5NF*을 살펴봅니다. ## BCNF의 한계 — 함수 종속 너머의 중복 다음 릴레이션을 보자. 직원이 보유한 기술과 구사하는 언어를 하나의 테이블에 저장한다. | <u>직원</u> | <u>기술</u> | <u>언어</u> | |------|------|------| | 김철수 | Java | 한국어 | | 김철수 | Java | 영어 | | 김철수 | Python | 한국어 | | 김철수 | Python | 영어 | | 이영희 | Go | 한국어 | 기본 키는 $\{\text{직원}, \text{기술}, \text{언어}\}$ 전체다. 모든 속성이 기본 키에 포함되어 있으므로 비주요 속성이 존재하지 않고, 비자명한 함수 종속도 없다[^no-nontrivial-fd]. 따라서 이 릴레이션은 BCNF를 만족한다. 그런데 김철수의 데이터를 보면, 기술 $\{\text{Java}, \text{Python}\}$과 언어 $\{\text{한국어}, \text{영어}\}$의 **모든 조합**이 행으로 존재한다. 이는 기술과 언어가 서로 독립적이라는 뜻이다 — 김철수가 Java를 할 수 있다는 사실과 영어를 구사한다는 사실은 아무 관련이 없다. 그런데 이 독립적인 두 사실이 하나의 릴레이션에 담겨 있기 때문에, 직원의 기술 수 $m$과 언어 수 $n$에 대해 $m \times n$개의 행이 필요하다. 이 구조에서 이상 현상이 발생한다. **삽입 이상**: 김철수가 Rust를 새로 배웠다면, 기존 언어 수만큼의 행(한국어, 영어)을 모두 추가해야 한다. 한 행만 추가하면 김철수가 Rust는 할 수 있지만 특정 언어만 구사하는 것처럼 보이는 모순이 발생한다. **삭제 이상**: 이영희가 Go를 더 이상 사용하지 않는다면, 유일한 행이 삭제되면서 "이영희는 한국어를 구사한다"는 정보까지 소실된다. **갱신 이상**: 김철수의 Java가 Kotlin으로 바뀌면, Java가 포함된 행 두 개를 모두 수정해야 한다. 이 문제들은 함수 종속과는 무관하다. BCNF가 다루는 것은 "X의 값이 Y의 값 하나를 결정하는" 관계인데, 여기서는 "직원의 값이 기술의 값 **집합**을 결정하는" 관계가 문제다. ## 다치 종속의 정의 릴레이션 $R(X, Y, Z)$에서 $X$의 값이 $Y$의 **값 집합**을 결정하되, 그 집합이 $Z$의 값과 무관할 때 다치 종속*Multivalued Dependency*이 존재한다고 하며, $X \twoheadrightarrow Y$로 표기한다 (Fagin, 1977). 형식적으로 정의하면, $X \twoheadrightarrow Y$는 다음을 의미한다. > $R$에서 $X$ 값이 같은 임의의 두 튜플 $t_1$, $t_2$에 대해, $t_1[X] = t_2[X]$이면 $t_3[X] = t_1[X]$, $t_3[Y] = t_1[Y]$, $t_3[Z] = t_2[Z]$인 튜플 $t_3$이 $R$에 존재해야 한다. 쉽게 말하면, $X$가 같은 튜플들의 $Y$ 값과 $Z$ 값을 교차 조합한 모든 튜플이 릴레이션에 있어야 한다는 것이다. 직원-기술-언어 릴레이션에서는 두 개의 다치 종속이 존재한다. - $\text{직원} \twoheadrightarrow \text{기술}$ — 직원이 보유한 기술 집합은 구사 언어와 무관하다. - $\text{직원} \twoheadrightarrow \text{언어}$ — 직원이 구사하는 언어 집합은 보유 기술과 무관하다. ### 함수 종속과의 관계 함수 종속은 다치 종속의 특수한 경우다. $X \to Y$이면 $X \twoheadrightarrow Y$도 성립한다 — $X$의 값이 $Y$의 값 하나를 결정한다면, 그것은 원소가 하나인 집합을 결정하는 것이므로 다치 종속의 정의를 자동으로 만족한다. 그러나 역은 성립하지 않는다. $X \twoheadrightarrow Y$라고 해서 $X \to Y$인 것은 아니다 — 직원이 기술 **집합**을 결정하지만, 기술 하나를 유일하게 결정하지는 못한다. ![[mvdVsFd.svg]] ### 자명한 다치 종속 다치 종속 $X \twoheadrightarrow Y$가 자명하다*trivial*는 것은 다음 중 하나가 성립하는 경우다. - $Y \subseteq X$: $Y$가 $X$의 부분집합이면 항상 성립한다. - $X \cup Y = R$: $Y$가 $R$의 나머지 속성 전체이면 항상 성립한다. 자명한 다치 종속은 어떤 릴레이션에서든 성립하므로 정규형 판별에서 제외한다. ### 보수 규칙 $R(X, Y, Z)$에서 $X \twoheadrightarrow Y$이면 $X \twoheadrightarrow Z$도 반드시 성립한다. 이를 보수 규칙*complementation rule*이라 한다. 직관적으로, $X$가 $Y$의 집합을 $Z$와 독립적으로 결정한다는 것은 곧 $Z$의 집합도 $Y$와 독립적으로 결정한다는 뜻이기 때문이다. 앞선 예제에서 $\text{직원} \twoheadrightarrow \text{기술}$과 $\text{직원} \twoheadrightarrow \text{언어}$가 쌍으로 존재하는 것은 우연이 아니라 보수 규칙의 필연적 결과다. ## 제4정규형 (4NF) > **4NF 조건**: 릴레이션 $R$에서 모든 비자명한 다치 종속 $X \twoheadrightarrow Y$에 대해, $X$가 슈퍼키여야 한다. 4NF는 BCNF의 함수 종속 조건을 다치 종속까지 확장한 것이다. BCNF가 "모든 비자명한 FD의 결정자가 슈퍼키"를 요구했듯, 4NF는 "모든 비자명한 MVD의 결정자가 슈퍼키"를 요구한다. 함수 종속이 다치 종속의 특수한 경우이므로, 4NF를 만족하면 BCNF도 자동으로 만족한다[^4nf-implies-bcnf]. 직원-기술-언어 릴레이션에서 $\text{직원} \twoheadrightarrow \text{기술}$의 결정자인 직원은 슈퍼키가 아니다(직원만으로 모든 속성을 결정하지 못한다). 따라서 4NF를 위반한다. ### 4NF 분해 4NF 위반을 해소하는 방법은 BCNF 분해와 동일한 원리다. 위반하는 다치 종속 $X \twoheadrightarrow Y$에 대해 릴레이션 $R$을 다음 두 릴레이션으로 분해한다. $R_1 = \pi_{X \cup Y}(R), \quad R_2 = \pi_{X \cup Z}(R)$ 직원-기술-언어 릴레이션에 적용하면 다음과 같다. **직원-기술** 릴레이션 ($R_1$) | <u>직원</u> | <u>기술</u> | |------|------| | 김철수 | Java | | 김철수 | Python | | 이영희 | Go | **직원-언어** 릴레이션 ($R_2$) | <u>직원</u> | <u>언어</u> | |------|------| | 김철수 | 한국어 | | 김철수 | 영어 | | 이영희 | 한국어 | 두 릴레이션 모두 비자명한 다치 종속이 없으므로[^decomposed-trivial] 4NF를 만족한다. 이상 현상이 해소되었다. 김철수가 Rust를 배우면 직원-기술 릴레이션에 한 행만 추가하면 된다. 이영희가 Go를 그만두어도 직원-언어 릴레이션의 "이영희 — 한국어"는 영향받지 않는다. 분해의 정당성도 확인할 수 있다. 두 릴레이션을 직원 속성으로 자연 조인하면 원래의 릴레이션이 정확히 복원된다 — 기술과 언어가 직원에 대해 독립적이므로 카르테시안 곱*Cartesian product*이 원래의 교차 조합과 일치한다. 이는 무손실 조인이다. ## 조인 종속과 제5정규형 다치 종속은 릴레이션을 **두 개**로 분해하면 해소된다. 그런데 두 개로는 무손실 분해가 불가능하지만 **세 개 이상**으로 분해하면 가능한 경우가 있다. 이런 상황을 설명하는 것이 조인 종속*Join Dependency*, JD이다. 릴레이션 $R$에 대해 조인 종속 $\bowtie(R_1, R_2, \ldots, R_n)$이 성립한다는 것은, $R$을 $R_1, R_2, \ldots, R_n$으로 프로젝션한 후 자연 조인하면 원래의 $R$이 복원된다는 뜻이다. 다치 종속은 $n = 2$인 조인 종속의 특수한 경우다. > **5NF (Project-Join Normal Form) 조건**: 릴레이션 $R$에서 모든 비자명한 조인 종속 $\bowtie(R_1, \ldots, R_n)$에 대해, 각 $R_i$가 $R$의 슈퍼키를 포함해야 한다. 5NF가 필요한 경우는 매우 드물다. 공급자-부품-프로젝트의 삼자 관계[^spj-example]가 대표적인 교과서 예제인데, 실무에서 이런 순환적 제약이 존재하는 릴레이션을 마주치는 경우는 거의 없다. 대부분의 실용적 데이터베이스 설계에서는 4NF까지 적용하면 충분하다. ## 정규형의 전체 계층 지금까지 [[Normalization]], [[Boyce-Codd Normal Form]], 그리고 이 글에서 다룬 정규형을 종합하면 다음과 같은 계층을 이룬다. ![[normalFormHierarchy.svg]] $\text{5NF} \subset \text{4NF} \subset \text{BCNF} \subset \text{3NF} \subset \text{2NF} \subset \text{1NF}$ 높은 정규형은 낮은 정규형의 조건을 모두 포함하며, 각 단계는 이전 단계에서 다루지 못한 특정 유형의 종속을 제거한다. 1NF~3NF는 부분·이행 함수 종속을, BCNF는 비후보키 결정자의 함수 종속을, 4NF는 비자명한 다치 종속을, 5NF는 비자명한 조인 종속을 제거한다. 실무에서는 3NF 또는 BCNF가 정규화의 사실상 종착점이며, 4NF와 5NF는 독립적인 다중값 속성이나 순환적 삼자 관계라는 특수한 구조에서만 필요하다. 어떤 정규형까지 적용할지는 데이터의 구조와 비즈니스 요구 사항에 따라 판단해야 한다. --- ## 출처 - Fagin, R. (1977) 'Multivalued Dependencies and a New Normal Form for Relational Databases', *ACM Transactions on Database Systems*, 2(3), pp. 262–278. - Fagin, R. (1979) 'Normal Forms and Relational Database Operators', *Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data*, pp. 153–160. - 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. [^no-nontrivial-fd]: 기본 키가 릴레이션의 모든 속성을 포함하므로, 비자명한 함수 종속의 결정자는 기본 키 자체(또는 그 상위집합)뿐이다. 기본 키는 슈퍼키이므로 BCNF 조건을 자동으로 만족한다. [^4nf-implies-bcnf]: 모든 함수 종속 $X \to Y$는 다치 종속 $X \twoheadrightarrow Y$를 함의한다. 따라서 4NF가 모든 비자명한 MVD의 결정자에 슈퍼키를 요구하면, FD의 결정자에도 슈퍼키가 요구되므로 BCNF를 포함한다. [^decomposed-trivial]: 직원-기술 릴레이션에서 $\text{직원} \twoheadrightarrow \text{기술}$은 $\text{직원} \cup \text{기술} = R_1$이므로 자명한 다치 종속이다. 자명한 MVD는 4NF 위반이 아니다. [^spj-example]: Supplier-Part-Project(SPJ) 예제. "공급자 S가 부품 P를 공급하고, 공급자 S가 프로젝트 J에 참여하고, 부품 P가 프로젝트 J에 사용된다"는 세 가지 이원 관계가 모두 성립하면 "공급자 S가 프로젝트 J에 부품 P를 공급한다"가 반드시 성립하는 순환적 제약 조건이다 (Fagin, 1979).