Normalization

데이터 중복(Redundancy)과 이상(Anomaly)현상은 bad FD(Functional Dependency)들이 존재할 때 발생. 이러한 bad FD들을 단계별로 찾아내어 소거하는 것이 정규화의 기본 개념.

• 후보키에 부분 종속되는 FD들을 소거하면 2NF 만족.
• 후보키에 이행 종속되는 FD들을 소거하면 3NF 만족.
• 슈퍼키가 아닌 것에 종속되는 FD들을 소거하면 BCNF 만족.

Anomalies in DBMS

• 갱신 이상(Modification Anomaly): 반복된 데이터 중에 일부를 갱신 할 시 데이터의 불일치 발생.

• 삽입 이상(Insertion Anomaly): 불필요한 정보를 함께 저장하지 않고서는 어떤 정보를 저장할 수 없음.

• 삭제 이상(Deletion Anomaly): 필요한 정보를 함께 삭제하지 않고서는 어떤 정보를 삭제할 수 없음.

예시

Student_ID	Name	Department	Club
1	Kim	Finance	Soccer
2	Lee	Mathematics	Dance
2	Lee	Mathematics	Cooking
3	Park	CS	Reading
3	Park	CS	Chess

• 갱신 이상: 만약 Lee의 학과가 Mathematics에서 CS로 바뀌었다고 가정. 테이블의 2,3번째 행의 Mathematics를 둘 다 바꾸지 않고 하나만 바꾼다면 Lee의 부서가 어디인지 알 수 없게됨.

• 삽입 이상: 새로운 학과 Philosophy가 신설되었고 아직 학생은 없다고 가정. 이 학과에 관한 정보는 불필요한 정보를 함께 입력하지 않는 한 위 테이블에 입력 불가.

• 삭제 이상: 만약 Finance 학과에 속한 학생이 Kim 한 명 뿐이라고 가정. Kim의 정보를 삭제하면 Finance 부서에 대한 정보도 삭제됨.

Normalization

자주 쓰이는 4가지 정규화 방식

• First normal form (1NF)
• Second normal form (2NF)
• Third normal form (3NF)
• Boyce & Codd normal form (BCNF)

First normal form (1NF)

1NF를 만족하려면 다음의 조건 만족해야함.

• 각 속성들은 atomic value 가져야함.

emp_id	emp_name	emp_addr	emp_phone
1	Kim	Seoul	1234
2	Lee	Busan	5678 0000
3	Park	Suwon	3534
4	Choo	Daegu	9999 7777

Lee와 Choo는 emp_phone 속성값이 각각 2개(multiple values)이므로 조건 위반.
따라서 다음과 같이 테이블을 변경함으로써 1NF 조건 만족.

emp_id	emp_name	emp_addr	emp_phone
1	Kim	Seoul	1234
2	Lee	Busan	5678
2	Lee	Busan	0000
3	Park	Suwon	3534
4	Choo	Daegu	9999
4	Choo	Daegu	7777

Second normal form (2NF)

2NF를 만족하려면 다음과 같은 조건 성립해야함.

• 1NF 만족
• non prime attribute가 후보키의 진부분 집합에 종속되면 안됨.
  즉, X -> Y (X: 후보키의 진부분 집합, Y: non prime attribute).
  만약 종속된다면 이를 부분 종속이라함.

prime attribute: 후보키에 속하는 속성.
non prime attribute: 후보키에 속하지 않는 속성.

prof_id	course	age
1	DB	45
1	Algorithms	45
2	Network	45
3	Data structure	40
3	Algorithms	40

후보키: {prof_id, course}
Non prime attribute: age

각 속성값은 atomic하기 때문에 1NF 만족.
하지만 non prime attribute인 age가 후보키의 진부분 집합 원소인 prof_id에 종속되므로 2NF 불만족.
2NF가 되기 위해 테이블을 두개로 분리해야함.

prof_info table:

prof_id	age
1	45
2	45
3	40

기본키: {prof_id}

prof_course table:

prof_id	course
1	DB
1	Algorithms
2	Network
3	Data structure
3	Algorithms

기본키: {prof_id, course}

Thrid normal form (3NF)

3NF를 만족하려면 다음과 같은 조건 성립해야함.

• 2NF 만족
• non prime attribute는 후보키에 이행 종속되어선 안됨.
  즉,X -> Y -> Z(X: 후보키, Y,Z: non prime attribute)인 경우 Z는 X에 이행 종속이며 3NF 불만족.

보다 더 단순한 조건:
모든 FD: X -> Y에 대하여 아래 조건 성립시 3NF.

• X는 슈퍼키(=X는 후보키 포함)
  또는
• Y는 prime attribute(=Y는 어떤 후보키의 구성원)

emp_id	emp_name	emp_zip	emp_city	emp_district
1	Kim	98754	Seoul	Gangnam
2	Lee	74878	Busan	Sasang
3	Park	72264	Busan	Saha
4	Choo	12234	Daegu	Dalseong
5	Ko	01003	Seoul	Gangbuk

슈퍼키: {emp_id},{emp_id,emp_name},{emp_id,emp_name,emp_zip}..등등
후보키: {emp_id}
non prime attribute: emp_id를 제외한 모든 속성

위 테이블에서 emp_city & emp_district는 emp_zip에 종속.
그리고 emp_zip은 emp_id에 종속.
따라서 emp_city & emp_district는 emp_id에 이행 종속.
3NF를 만들기 위해 위 테이블은 두 개의 테이블로 분리.

employee table:

emp_id	emp_name	emp_zip
1	Kim	98754
2	Lee	74878
3	Park	72264
4	Choo	12234
5	Ko	01003

기본키: {emp_id}

emp_zip table:

emp_zip	emp_city	emp_district
98754	Seoul	Gangnam
74878	Busan	Sasang
72264	Busan	Saha
12234	Daegu	Dalseong
01003	Seoul	Gangbuk

기본키: {emp_zip}

Boyce Codd normal form (BCNF)

3.5NF라고도 함.
BCNF를 만족하려면 다음의 조건 만족해야함.

• 함수 종속성 X -> Y에 대하여 X는 슈퍼키이어야함.

회사의 사원들은 하나 이상의 부서에서 일한다고 가정.

emp_id	emp_nationality	emp_dept	dept_type	emp_dept_no
1	Korean	Marketing	D451	123
1	Korean	Designing	D451	777
2	American	Manufacturing	D942	010
2	American	Developing	D942	841

위 테이블에 존재하는 함수 종속성:
emp_id -> emp_nationality
emp_dept -> {dept_type, emp_dept_no}

기본키: {emp_id, emp_dept}

함수 종속성에서 emp_id는 슈퍼키 아님. emp_dept도 슈퍼키 아님. 따라서 BCNF 불만족.
BCNF 만족하기 위해 테이블을 3개로 분리.

emp_country table:

emp_id	emp_nationality
1	Korean
2	American

emp_dept table:

emp_dept	dept_type	emp_dept_no
Marketing	D451	123
Designing	D451	777
Manufacturing	D942	010
Developing	D942	841

emp_dept_mapping table:

emp_id	emp_dept
1	Marketing
1	Designing
2	Manufacturing
2	Developing

함수 종속성:
emp_id -> emp_nationality
emp_dept -> {dept_type,emp_dept_no}

기본키:
emp_nationality table: {emp_id}
emp_dept table: {emp_dept}
emp_dept_mapping table: {emp_id, emp_dept}

분리 후 emp_id는 emp_nationality table의 기본키이므로 슈퍼키 만족. emp_dept도 emp_dept table의 기본키이므로 슈퍼키 만족. 따라서 BCNF 만족.