Normal Forms

상위 문서: Relational Database Design

개요

헤당 문서에서는 관계형 데이터베이스를 설계할 때 사용되는 여러 가지 서로 다른 정규형(normal form)들 중에서 가장 일반적으로 사용되는 정규형들을 다룬다.

Boyce–Codd Normal Form

Boyce–Codd Normal Form(BCNF)는 함수 종속성에 기반하여 발견할 수 있는 모든 중복(redundancy)을 제거한다. 릴레이션 스키마(relation scema) R이, 함수 종속성(function dependency) 집합 F에 대해, 다음 조건을 만족하면 R은 BCNF에 있다고 한다:

• α → β가 자명한 함수 종속성(trivial functional dependency)이어야 한다.
• α가 R 스키마에 대한 슈퍼키(superkey)이어야 한다.

또한, 데이터베이스 설계 전체가 BCNF에 있다(in)고 하려면, 그 설계를 구성하는 모든 릴레이션 스키마 각각이 BCNF에 있어야 한다.

예를 들어, 아래와 같은 릴레이션 스키마를 고려하자:

in_dep (ID, name, salary, dept_name, building, budget)

해당 릴레이션에서는 dept_name → building, budget 이라는 함수 종속성이 성립하지만 dept_name은 슈퍼키가 아니다. 즉, 해당 릴레이션은 BCNF에 있지 않다(not in). 따라서 해당 릴레이션은 in_dep를 instructor와 department로 분해하는 것이 더 나은 설계이다. 그 이유는 아래와 같다:

• Instructor 스키마는 BCNF에 있다.
  • instructor에서의 모든 비자명(nontrivial) 함수 종속성: ID → name, dept_name, salary
  • 이때 튜플의 모든 속성값은 ID 속성의 값을 통해 추적할 수 있으므로, ID는 슈퍼키이다.
• Department 스키마도 BCNF에 있다.
  • department 스키마에서의 비자명 함수 종속성: dept_name → building, budget
  • 마찬가지로 dept_name은 슈퍼키이고, 따라서 department 역시 BCNF에 있다.

Decomposing a Schema into BCNF

BCNF에 있지 않은 스키마를 분해하기 위해서는 아래의 일반 규칙을 따라야 한다.

스키마 R이 BCNF에 있지 않으면, 반드시 하나 이상의 비자명 함수 종속성 α → β가 존재하며, 이때 α는 R의 슈퍼키가 아니다.
이 경우, R을 두 개의 스키마 R1, R2로 대체(replace)한다:
R1 = (α ∪ β)
R2 = (R − (β − α))

이를 위의 in_dep 릴레이션을 분해하는데 적용하면 α = dept_name, β = {building, budget}이다. 따라서 아래와 같다:

(α ∪ β) = (dept_name, building, budget)
(R − (β − α)) = (ID, name, dept_name, salary)

이때 스키마를 한번 분해했더라도, 새로 생긴 스키마 중 하나 이상이 여전히 BCNF에 있지 않을 수 있으며, 그런 경우에는 분해를 반복해야 한다.

BCNF and Dependency Preservation

경우에 따라 BCNF로 분해하는 과정이 특정 함수 종속성의 효율적인 검사를 방해할 수 있다. 예를 들어, BCNF의 규칙을 따라 릴레이션을 분해하는 것은 종속성 보존(dependency preservation)을 어길 수 있다. 예를 들어, 다음 dept_advisor 스키마를 고려해보자:

dept_advisor (s_ID, i_ID, dept_name)

이 경우, 다음과 같은 함수 종속성이 성립한다고 가정하자:

1. i_ID → dept_name: 교수는 오직 하나의 학과에 대해서만 지도교수 역할을 한다.
2. (s_ID, dept_name) → i_ID: 학생은 주어진 학과에 대해 최대 한 명의 지도교수만 가질 수 있다.

해당 설계에서는 하나의 교수가 dept_advisor 릴레이션에 여러 번 등장할 때마다 학과 이름(dept_name)을 반복 저장해야 한다. 또한 i_ID가 슈퍼키가 아니기 때문에 dept_advisor는 BCNF가 아니다. 따라서, BCNF 분해 규칙에 따라 dept_advisor를 다음 두 스키마로 분해해야 한다.

(s_ID, i_ID)
(i_ID, dept_name)

이 두 스키마는 모두 BCNF에 있다. 하지만 문제는 BCNF로 분해한 후, (s_ID, dept_name) → i_ID라는 함수 종속성을 하나의 릴레이션만으로 검사할 수 없다는 점이다. 즉, (s_ID, dept_name) → i_ID를 검사하기 위해서는 분해된 두 릴레이션을 join 연산을 해서 다시 합쳐야만 가능하다. 즉, BCNF 분해를 하였을 때, 종속성 보존(dependency preservation)이 이루어지지 않았다.

Third Normal Form

BCNF는 모든 비자명한 함수 종속성이 α → β 형태를 가져야 하며, α는 슈퍼키여야 한다는 조건을 요구한다. 3NF(Third Normal Form)은 이러한 제약을 약간 완화하여, 다른 비자명한 함수 종속성을 허용한다. Relational 스키마 R이 함수 종속성 집합 F에 대해 3NF을 만족한다고 하기 위해서는, F⁺에 포함된 모든 함수 종속성 α → β은 다음 중 하나를 만족해야 한다:

• α → β는 자명한 함수 종속성이다.
• α는 R에 대한 슈퍼키이다.
• β - α에 속한 각 속성 A는 R의 어떤 후보키에 포함되어 있다.

BCNF를 만족하는 스키마는 항상 3NF도 만족한다. 왜냐하면 그 스키마의 모든 함수 종속성은 앞의 두 조건 중 하나를 항상 만족하기 때문이다. 따라서 BCNF는 3NF보다 더 제약이 강한 정규형이다. 이에 따라, 3NF의 정의는 BCNF에서 허용되지 않는 일부 함수 종속성을 허용한다. 예를 들어, 3NF 정의의 세 번째 조건만을 만족하는 함수 종속성 α → β는 BCNF에서는 허용되지 않지만, 3NF에서는 허용된다.

예를 들어, dept_advisor는 아래와 같은 스키마와 함수 종속성을 가진다:

dept_advisor(s_ID, i_ID, dept_name)
i_ID → dept_name       //i_ID는 슈퍼키가 아님
s_ID, dept_name → i_ID //제 2조건 만족

해당 스키마는 i_ID 속성이 슈퍼키가 아니기 때문에 BCNF에 속하지 않는다. 하지만 s_ID, dept_name이 superkey이고, α = i_ID, β = dept_name이므로 β - α = dept_name이고, dept_name은 후보키 {s_ID, dept_name}에 포함되므로 세 번째 조건을 만족한다. 즉, dept_advisor 스키마는 3NF에 해당된다.

Redundancy in 3NF

Figure 1. Redundancy in 3NF

3NF를 사용하는 스키마는 정보의 중복이나 null값 사용 등의 문제가 나타날 수 있다. 예를 들어, figure 1과 같이 3NF에 속하는 스키마가 아래와 같이 정의되어 있다고 하자:

R = (J, K, L)
F = { JK → L, L → K }

해당 스키마는 3NF이다. 왜냐하면 JK → L 조건에서 JK는 슈퍼키에 해당하므로, 조건 2를 만족하며, L → K에서 L은 슈퍼키가 아니지만, {K-L}은 후보키로서 동작할 수 있으므로 조건 3을 만족하기 때문이다. 하지만 해당 relation 테이블은 두가지 문제점을 가지고 있다. 먼저 l₁, k₁가 3번 반복되어, 정보의 중복이 나타난다. 또한 l2 → k2라는 정보를 저장하고 싶지만, J 속성에 이에 대응되는 값이 없어 null 값을 튜플에 삽입해야 한다는 것이다. 이러한 문제들은 함수 종속성들이 별도의 테이블에서 각각 표현되지 않았기 때문에 발생한다.

즉, 3NF의 장점은 함수 종속성 보존을 잃지 않고 항상 3NF를 기반으로 한 설계를 할 수 있다는 것이지만, 때로는 null 값의 사용이나 정보의 중복 등의 문제가 생길 수 있다는 단점이 있다.

Higher Normal Form

정규화(Normalization)의 목표는 관계 스키마 R와 함수 종속성 집합 F가 주어졌을 때, R이 "좋은 형태"인지 판단하고, 좋은 형태가 아니면, R을 {R1,R2,...,Rn}으로 분해하는 것이다. 이때 "좋은 분해란" 다음 조건을 만족해야 한다:

• 각 스키마가 3NF 또는 BCNF과 같은 좋은 형태일 것
• Lossless decomposition(무손실 분해)
• Dependency preserving(함수 종속성 보존)

즉, 정규화는 무손실성과 함수 종속성 보존을 유지하면서 정규형에 맞는 스키마로 분해하는 것이 핵심이다. 이때, 어떤 데이터베이스 스키마는 BCNF를 만족하더라도 충분히 정규화된 것처럼 보이지 않을 수 있다. 예를 들어 inst_info relation에 대한 스키마가 아래와 같이 주어져있다고 해보자.

inst_info(ID, child_name, phone)

Figure 2. BCNF Redundency example

이때 하나의 강사가 여러 자녀와 여러 휴대폰 번호를 가질 수 있으므로, figure 2와 같은 인스턴스가 생길 수 있다. 이는 동일한 정보가 각각의 자녀에 대해 따로 저장되었으므로, 정보의 중복이 발생한 인스턴스이다. 또한 새로운 전화 번호 981-992-3443을 추가하고 싶을 때에는 아래와 같이 David와 William 모두에 대해 각각 튜플을 넣어야 한다:

(99999, David,   981-992-3443)
(99999, William, 981-992-3443)

해당 relation 스키마가 이러한 문제점들을 가지고 있음에도, 해당 스키마에는 비자명한 함수 종속성이 존재하지 않으므로, BCNF를 만족한다. 즉, 함수 종속성을 이용한 스키마 분해는 불필요한 정보의 반복을 방지하기에는 충분치 않을 수 있다.

Fourth Normal Form

릴레이션 스키마 R은 함수 및 다값 종속성(multivalued dependency) 집합 D를 가지고 있다고 하자. 이때 D⁺에 포함된 모든 다중값 종속성 α →→ β에 대해 아래 조건 중 하나 이상이 성립할 때 4NF(Fourth Normal Form)에 속한다고 한다:

• α →→ β가 자명한 다중값 종속성이다.
• α가 R의 슈퍼키이다.

이때 데이터베이스 설계가 4NF에 속한다는 것은 그 설계를 구성하는 모든 릴레이션 스키마들이 4NF에 속한다는 것을 의미한다. 이때 4NF의 정의는 첫번째 조건에서 함수 종속성이 아닌 다중값 종속성을 사용한다는 점에서만 BCNF와 구분된다. 또한, 모든 4NF 스키마는 BCNF에 속한다. 만약 어떤 스키마 R이 BCNF에 속하지 않는다는 것은, R에는 비자명한 비자명한 함수 종속성 α → β가 존재하며, 이때 α는 슈퍼키가 아니라는 의미이다. 근데 α → β이면 α →→ β이므로, 따라서 R은 4NF가 될 수 없다. 따라서, 모든 BCNF에 속하지 않는 스키마 R은 4NF에도 속하지 않는다.

Restriction of Multivalued Dependencies

릴레이션 스키마 R이 있고, 그것을 R₁, R₂, ..., R_n으로 분해했다고 하자. 분해된 각 릴레이션 스키마 R_n가 4NF에 속하는지 확인하려면, 각 R_i에서 어떤 다값 종속성이 성립하는지 찾아야 한다. 함수 종속성 집합 F에 대해, F를 R_i에 제한(restriction)한 것은, R_i의 속성들만 포함하는 F⁺의 함수 종속성이다. 마찬가지로, 함수 및 다중값 종속성 집합 D를 고려할 때, D를 R_i에 제한한 D_i는 아래와 같이 구성된다.

• R_i의 속성들 만을 포함하는 D⁺의 함수 종속성들
• 다음 형태의 다중값 종속성들: α →→ (β ∩ R_i)
  • 이는 다중값 종속성 α →→ β가 전체 R에 대해서 성립하지만, R_i에서는 β의 일부만 존재할 수 있으므로, 교집합을 통해 이를 나타내는 것이다.

4NF Decomposition Algorithm

자세한 내용은 4NF Decomposition Algorithm 문서를 참조해 주십시오.

More Normal Forms

4NF는 결코 궁극적인 형태의 정규형이 아니다. 다만, 다중값 종속성을 활용해 함수 종속성만으로는 제거할 수 없는 일부 형태의 중복을 처리할 뿐이다. 그리하여 다중값 종속성 보다 더욱 일반화된 제약조건이 존재하는데, 그것이 바로 조인 종속성(join dependency)과 해당 종속성을 이용한 5NF(Fifth Normal Form)이다. 또한 이보다 더 일반적인 제약조건도 존재하며, 이는 DKNF(Domain-Key Normal Form)이라는 정규형으로 이어진다. 하지만 이런 일반화된 제약조건들을 사용하는 데는 문제가 있다. 이는 다루기 어려울 뿐더러, 해당 제약 조건들에 대해 정확하고 완전한 추론 규칙 체계가 존재하지 않는다는 것이다. 따라서 PJNF와 DKNF는 실제로 거의 사용되지 않는다.

First Normal Form

1NF(First Normal Form)은 도메인의 원자성(atomicity)와 큰 관련이 있다. 도메인이 원자적(atomic)하다는 것은 해당 도메인의 값들이 더 이상 나눌 수 없는 불가분의 단위라는 것을 의미한다. 즉, 하나의 속성 값은 하나의 값만을 가져야 한다는 것이다. 예를 들어 "CS2023"이라는 학번은 "CS"(전공)와 "2023"(입학년도)으로 나누어 해석할 수 있으므로 비원자적이다. 이때 1NF의 정의는 어떤 릴레이션 스키마 R에 대해, R의 모든 속성들의 도메인이 원자적이라는 것이다. 만약 1NF를 만족하지 않는다면, 복잡한 저장 방식이 필요하거나, 중복 저장을 야기할 수 있다. 이는 가장 기본적인 정규형이므로, 본 위키에서 특별한 언급이 없다면 모든 릴레이션이 1NF를 만족한다고 가정한다.

이때 중요한 점은 도메인의 원자성이 해당 도메인의 속성이 아니라 사용 방식에 달려있다는 것이다. 위에서 관찰했듯이 문자열은 일반적으로 원자적이지만, 문자열을 부분으로 나누어 해석하면 그것은 더 이상 원자적이지 않다. "CS2023"과 같은 방식으로 데이터를 저장하고 그 문자열의 일부분을 통해 전공과 입학년도를 얻는다면, 이는 정보를 인코딩한것에 불과하다. 이는 정보가 DB 스키마가 아닌 응용 프로그램 로직에 묻혀버리기 때문에, 유지보수성, 이식성, 확장성 모두에서 문제를 유발하므로 나쁜 설계 방식이다.