Normalization

Normalization

정규화는 간단하게 말하면 비 정상상태의 테이블을 정상상태로 만들어 주는 것을 의미한다.

 

비 정상상태

비 정상상태의 테이블은 insert, update, delete의 명령을 수행할 때 적절치 못하게 동작하는 테이블을 의미한다.

- insert시 쓸데없는 null값을 허용하는 경우

회원 정보를 저장할 때 ID가 null값이 들어가는 상황

- update시 데이터의 불 일치가 일어나는 경우

같은 ID값을 갖고있는 회원의 이름이 다르게 저장되는 상황

- delete시 특정 튜플이 모두 삭제되는 경우

교수가 강의가 끝나 course_id를 지웠는데, 해당 column의 데이터가 모두 삭제되는 상황

 

Lossless Decomposition

비 정상상태를 해결하는 방법은 보통의 경우 테이블을 작은 테이블로 분해하면 해결되는 경우가 많다.

하지만, 무턱대고 테이블을 분해하면 나중에 join 연산 시 쓸데없는 데이터가 생성되는 등

논리적으로 데이터베이스를 구성하는데 어려움을 겪을 수 있다.

 

<Fig. 01>

위의 경우 (ID, name, street, city, salary)와 같은 스키마는 굳이 분리하지 않아도 정상적인 테이블로 만들 수 있다.

하지만 이것을 무리하게 (ID, name), (name, street, city, salary)로 분리하면

join 연산 시 의미 없는 튜플을 생성하게 되는 것이다.

 

이런 분해를 Lossy Decomposition 이라 한다.

 

그렇다면 Lossless Decomposition의 조건, 하는 방법을 알아보자.

 

분해된 테이블을 join 연산 시 원본 테이블이 나오면 Lossless Decomposition이 가능하다.

 

Functional Dependencies

Lossless Decomposition을 달성하기 위해 함수적 종속성을 이용할 것이다.

함수적 종속성을 이용한 정규화 방식에는 2NF, 3NF, BCNF가 있다.

 

함수적 종속성은 아래와 같은 수식으로 표현이 가능하다.

$$ \alpha \subseteq R \; and \; \beta \subseteq R $$

then functional dependency

$$ \alpha \rightarrow \beta $$

여기서 알파, 베타는 스키마 R의 키(attribute의 부분집합) 이다.

 

예로 들어보자.

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

위와 같은 스키마에선 아래와 같은 함수적 종속성이 있음을 유추해볼 수 있다.

$$ ID \rightarrow dept\_name $$

$$ dept\_name \rightarrow building $$

만약 함수적 종속성이 위 두 경우밖에 없을 경우 아래와 같이 표현할 수 있다.

 $$ F = \{ ID \rightarrow dept\_name, \; dept\_name \rightarrow building \} $$

 

하지만 논리적으로 연쇄법칙에 의해 아래와 같은 함수적 종속성도 존재할 수 있다.

$$ ID \rightarrow building $$

이 경우 아래와 같은 closure of F도 만들어진다.

$$ F+ = \{ ID \rightarrow dept\_name, \; dept\_name \rightarrow building, \; ID \rightarrow building \} $$

 

즉, 함수적 종속성은 알파의 키가 결정되면 베타의 키가 결정된다는 뜻이 되는데,

잘 생각해보면 candidate key는 모든 튜플을 결정할 수 있는 key들을 의미한다.

따라서 후보키의 경우 아래와 같은 식도 성립한다.

$$ C \rightarrow R \; and \; for \; no \; \alpha \subset C, \; \alpha \rightarrow R $$

 

이러한 함수적 종속성은 자명하기에 모든 테이블에서 성립하는 관계이다.

이런 자명한 함수적 종속성에는 아래와 같은 종속성도 있다.

$$ \alpha \rightarrow \beta \; is \; trivial \; if \; \beta \subseteq \alpha $$

Example

$$ ID, \; name \rightarrow ID $$

$$ name \rightarrow name $$

 

그렇다면, 함수적 종속성과 Lossless Decomposition은 무슨 관계일까?

R을 R1, R2로 Decompose 하는 경우, 아래의 함수적 종속성 중 하나를 만족하면 Lossless하게 분해 가능하다.

$$ R_1 \cap R_2 \rightarrow R_1 $$

or

$$ R_1 \cap R_2 \rightarrow R_2 $$

즉, 두 스키마에 공통으로 존재하는 인자가 하나 이상의 테이블을 완벽하게 결정지을 수 있다면,

두 스키마는 Lossless하게 분해되었다는 뜻이다.

 

예를 들어, 위에 <Fig. 01> 에서는 두 스키마에 공통으로 존재하는 인자가 name인데,

name은 두 테이블을 완벽하게 결정짓지 못한다. 따라서 Lossy Decomposition이 이루어 진 것이다.

하지만, 위에 in_dep 예시에서 dept_name으로 분해시 공통으로 존재하는 인자는 dept_name이 되는데,

dept_name은 (ID, name, salary, dept_name)을 완벽하게 결정짓지는 못하지만,

(dept_name, building, budget)은 완벽하게 결정지을 수 있기 때문에 Lossless Decomposition이 가능한 것이다.

 

Dependency Preservation

함수적 종속성을 만족하면 Lossless Decomposition을 만족하는 것이 맞지만,

Lossless Decomposition이 된다면 함수적 종속성을 반드시 유지할 수 있는 것은 아니다.

예를 들어보자.

 

$$ R = \{A, \; B, \; C \} $$

$$ F = \{A \rightarrow B, \; B \rightarrow C \} $$

위 R은 아래와 같은 두 방법으로 Lossless Decomposition이 가능하다.

 

$$ R_1 =(A, \; B), \; R_2 = (B, \; C) $$

$$ R_1 = (A, \; B), \; R_2 = (A, \; C) $$

위의 경우에는 함수적 종속성을 확인하려고 하니 F에 명시된대로 바로 종속성이 유지됨을 확인할 수 있다.

하지만 아래의 경우에는 함수적 종속성을 확인하기 위해 R1, R2를 join 연산하여 F+를 얻어내야만 R2의 종속성을 확인할 수 있다.

 

이렇듯 테이블을 무손실 분해 하는 방법은 여러 방법이 있지만, 함수적 종속성이 모두 유지되는 것은 아니다.

 

1NF (Normal Form)

제1 정규형을 만족하는지 확인하는 방법은 다음과 같다.

 

Ralation의 모든 attribute가 atomic 하면 1NF를 만족한다.

즉, 하나의 attribute에 여러 정보를 담고 있으면 그 tuple을 여러 tuple로 분해하면 1NF를 달성할 수 있다.

 

하지만, 1NF을 만족하는 경우에는 비 정상상태에서 언급한 문제들이 여전히 발생할 수 있다.

 

2NF

제2 정규형을 만족하는지 확인하는 방법은 다음과 같다.

 

1NF을 만족하면서 후보키의 진 부분집합이 함수적 종속성을 갖는 경우

종속성을 갖는 attribute끼리 그 테이블을 분해해야 2NF를 만족한다.

즉, 후보키의 진 부분집합이 나머지 attribute와 어떠한 함수적 종속성도 갖지 말하야 한다.

 

아래 예시를 들어보자.

후보키 {Manufacturer, Model} 의 진 부분집합 {Manufacturer} 이 함수적 종속성

Manufacturer -> Manufacturer country를 갖는 경우,

종속성을 갖는 Manufacturer, Manufacturer country끼리 테이블을 분해해야 2NF를 만족한다.

 

사실 2NF은 당연시하게 만족해야 하는 이유가 있는데,

후보키 자체는 모든 튜플을 유일하게 결정지을 수 있는 attribute의 최소 집합을 의미한다.

즉, 후보키에서 attribute 한 개만 빼도 모든 튜플을 유일하게 결정지을 수 없게 된다.

하지만, 후보키의 진 부분집합, 즉, 모든 튜플을 유일하게 결정지을 수 없는 키가 특정 attribute를 결정지을 수 있다는 것은

후보키가 사실은 슈퍼키라는 뜻이 되어버리기 때문에 분해를 해주는 것이다.

 

하지만, 2NF을 만족하는 경우에도 비 정상상태에서 언급한 문제들이 여전히 발생할 수 있다.

 

BCNF (Boyce-Codd Normal Form)

BC정규형을 만족하는지 확인하는 방법은 다음과 같다.

 

R의 모든 함수적 종속성 F와 그 closure F+가 아래와 같이 표현한다고 가정,

$$ \alpha \rightarrow \beta $$

$$ \alpha \rightarrow \beta \subseteq F+, \; \alpha \subseteq R \; and \; \beta \subseteq R $$

아래의 조건 중 최소 하나를 만족하면 R은 BCNF를 만족한다.

$$ \alpha \rightarrow \beta \; is \; trivial \; (i.e., \; \beta \subseteq \alpha ) $$

$$ \alpha \; is \; superkey \; for \; R $$

 

위 조건은 어찌보면 너무나 당현한 것이다.

첫 번째 조건은 Functional Dependencies에서 자명한 함수적 종속성에서 언급했 듯 자명하고,

두 번째 조건 역시 슈퍼키는 모든 튜플을 유일하게 결정할 수 있는데, 특정 attribute를 결정하는 것 역시 당연하다.

 

BCNF를 만족하도록 테이블을 분해하는 예시를 들어보자.

in_dep (ID, name, salary, dept_name, building, budget) 위에서도 예시로 사용한 스키마다.

여기서 찾을 수 있는 함수적 종속성은 아래와 같다.

$$ ID \rightarrow name, \; salary, \; dept\_name, \; building, \; budget $$

$$ dept\_name \rightarrow building, \; budget $$

이 때 두 번째 함수적 종속성은 BCNF의 조건 2개를 모두 만족하지 못한다.

(trivial 하지않고, dept_name은 superkey도 아니다)

 

이 경우 BCNF를 만족하는 테이블로 분해하기 위해선 아래의 방법을 따르면 된다.

먼저 R이 BCNF를 위반하게 하는 함수적 종속성을 찾는다. (아래 함수적 종속성이 위반했다고 가정)

$$ \alpha \rightarrow \beta $$

이 함수적 종속성을 기반으로 아래의 두 테이블로 분해한다.

$$ (\alpha \cup \beta) $$

$$ (R - (\beta - \alpha)) $$

 

따라서 instructor (ID, name, salary, dept_name), department (dept_name, building, budget)과 같이 분해하면

이번엔 dept_name은 두 번째 조건을 만족하기 때문에 BCNF를 만족하게 된다.

 

하지만, BCNF를 만족하면서 함수적 종속성을 보존하는게 항상 가능한 것은 아니다.

위 예시의 경우 아래의 함수적 종속성이 보존되지 않는다.

$$ ID \rightarrow building, \; budget $$

 

3NF

제3 정규형을 만족하는지 확인하는 방법은 다음과 같다.

R의 모든 함수적 종속성 F와 그 closure F+가 아래와 같이 표현한다고 가정,

$$ \alpha \rightarrow \beta $$

$$ \alpha \rightarrow \beta \subseteq F+, \; \alpha \subseteq R \; and \; \beta \subseteq R $$

아래의 조건 중 최소 하나를 만족하면 R은 BCNF를 만족한다.

$$ \alpha \rightarrow \beta \; is \; trivial \; (i.e., \; \beta \subseteq \alpha ) $$

$$ \alpha \; is \; superkey \; for \; R $$

$$ Each \; attribute \; A \; in \; \beta - \alpha \; is \; contained \; in \; a \; candidate \; key \; for \; R $$

 

BCNF에서 베타에만 있는 attribute가 후보키에 속해있을 경우라는 유예 조건이 하나 추가되었다.

따라서 BCNF는 3NF보다 빡빡하게 제약을 거는 셈이다.

즉, BCNF를 만족하면 3NF을 만족하지만 역은 성립하지 않는다.

 

예를 들어보자.

dept_advisor (s_ID, i_ID, dept_name)은 아래와 같은 함수적 종속성을 갖는다.

$$ i\_ID \rightarrow dept\_name $$

$$ s\_ID, dept\_name \rightarrow i\_ID $$

이 스키마는 첫 번째 함수적 종속성 때문에 BCNF를 만족하지 않는다.

하지만 첫 번째 함수적 종속성은 3NF의 세 번째 조건은 충족한다.

(dept_name는 R의 후보키 {s_ID, dept_name}에 소속되기 때문)

 

3NF를 만족하는 경우 테이블을 굳이 분해하지 않아도 되기에 함수적 종속성을 보존할 수 있다.

하지만, 데이터의 중복 저장, null값 허용 등의 문제가 발생할 수 있다.

 

Design Goal

그렇다면 제약을 빡빡하게 건 BCNF를 사용하는 것이 반드시 좋을까?

BCNF에도 아래와 같은 맹점이 존재한다.

inst_info (ID, child_name, phone)의 예시를 살펴보자.

이 경우에는 함수적 종속성이랄 것이 없다.

따라서 정의에 따라 BCNF를 만족한다.

이 때 새로운 phone를 추가해야 하는 경우 쓸데없이 튜플 2개를 추가해야 하는 상황이 발생한다.

따라서 BCNF가 무조건 최선의 방법은 아니다.

 

따라서 함수적 종속성을 반드시 유지해야 하는 경우, 즉, BCNF를 사용했는데 join 연산을 많이 사용하는 경우에는

BCNF를 포기하고, 중복과 null값을 사용해도 3NF를 만족하는 디자인을 사용하는게 좋고,

함수적 종속성이 굳이 필요 없는 경우에는 BCNF 디자인을 사용하는게 좋다.

 

물론 최선은 BCNF를 만족하고, lossless join이 가능하고, 함수적 종속성이 보존되면 최고겠지만...