데이터베이스 정규화

Database Normalization

이상(Anormaly) 현상

정규화를 거치지 않은 데이터베이스에서 발생할 수 있는 현상
데이터들이 불필요하게 중복되어 릴레이션 조작에 예기치 못한 문제 발생
애트리뷰트들의 종속관계를 하나의 릴레이션에 표현하기 때문에 발생

이상 종류

삽입할 때 잘못 삽입됨, 갱신할 때 잘못 갱신됨 등의 일반적인 내용이다. 아래 정규화과정에서 예시 참고

삽입 이상(Insertion Anomaly)
- 데이터 삽입 시 의도와 다른 값들도 삽입됨
삭제 이상(Delete Anomaly)
- 데이터 삭제 시 의도와 다른 값들도 연쇄 삭제됨
갱신 이상(Update Anomaly)
- 속성값 갱신 시 일부 튜플만 갱신되어 모순 발생

정규화 목적

중복을 배제하여 삽입, 삭제, 갱신 이상의 발생을 방지
각 릴레이션에 중복된 종속성을 여러개의 릴레이션에 분할
어떠한 릴레이션이라도 데이터베이스 내에서 표현 가능하게 함
데이터 삽입 시 릴레이션을 재구성할 필요성 감소
효과적인 검색 알고리즘 생성 가능

정규화 과정

1NF

First Normal Form

1NF를 만족하려면 도메인이 원자값이어야 한다.

1NF를 만족하지 않는 릴레이션

수강과목	수강자
수학	홍길동
과학	임꺽정, 신사임당
사회	홍길동, 임꺽정


수강과목	수강자1	수강자2	수강자3
국어	홍길동
수학	신사임당	홍길동
영어	고길동	신사임당	홍길동

수강자 속성이 원자값이 아니다.
유사한 속성이 중복, 반복되는 경우도 정규화의 대상이 된다

발생할 수 있는 이상(Anomaly)의 예
- 갱신 이상: 홍길동이 사회과목을 '역사'로 바꾸었다. 그럼 임꺽정이 듣고 있는 사회 과목도 바뀌어버린다.
  - UPDATE 과목 SET 수강과목 = '역사' WHERE 수강과목 = '사회' AND 수강자 = '홍길동'
- 삭제 이상: 임꺽정이 '과학' 과목을 수강취소했다. 그럼 신사임당의 수강 정보도 삭제된다.
  - DELETE FROM 과목 WHERE 수강과목 = '과학' AND 수강자 = '임꺽정'
1NF를 만족시키는 릴레이션

수강과목	수강자	일련번호
수학	홍길동	1
과학	임꺽정	2
과학	신사임당	3
사회	홍길동	4
사회	임꺽정	5

가장 간단한 것은 원자값으로 분해해 튜플로 구분하고 다른 키를 추가하는 것이다.
실제로 복잡한 테이블은 이렇게 단순하게 분해해버리면 다른 중복 문제들이 많이 생겨 테이블 구조를 따져봐야한다.

2NF

Second Normal Form
2NF를 만족하려면 부분적 함수 종속을 제거해야 한다.

즉 완전 함수 종속이 되도록 해야 한다.
2NF를 만족하지 않는 릴레이션

학번	이름	소속학과	학과장
1901	홍길동	컴퓨터과	김교수
1845	임꺽정	전자과	박교수
1706	신사임당	기계과	천교수
1925	장영실	컴퓨터과	김교수

학번 <-> 이름+소속+학과장은 종속 관계가 있다.(한 학과내의 이름은 중복되지 않는다고 가정)
하지만 사실 학과장은 소속학과 하나만에도 종속(소속학과 <-> 학과장)되므로 이는 부분적인 종속관계가 포함되어 있다.
즉 학과장은 꼭 이 릴레이션에 있어야 할 필요도 없고, 이 릴레이션에 있는 순간 '김교수'와 같이 계속 중복적재 될것이다.

발생할 수 있는 이상(Anomaly)의 예
- 삽입 이상: 컴퓨터과, 전자과, 기계과 학생을 추가하고자 할 경우 중복 정보인 학과장 정보가 삽입되어야 한다.
- 갱신 이상: 컴퓨터과의 학과장이 변경될 경우, 하나만 변경하면 모순이 발생하므로 다 찾아서 변경해야 한다.
- 삭제 이상: 신사임당이 자퇴해서 삭제하고자 한다. 이 삭제로 인해 기계과 학과장의 정보가 사라져 버린다.
2NF를 만족시키는 릴레이션

학번	이름	소속학과
1901	홍길동	컴퓨터과
1845	임꺽정	전자과
1706	신사임당	기계과
1925	장영실	컴퓨터과

학과	학과장
컴퓨터과	김교수
전자과	박교수
기계과	천교수

이와 같이 릴레이션을 구분하는 것이 바람직하다.

3NF

Third Normal Form
3NF를 만족하려면 이행적 함수 종속을 제거해야 한다.

이행적 함수 종속: A→B 이고 B→C 일 때 A→C 인 관계
3NF를 만족하지 않는 릴레이션
- 소속학과는 특정 대학에 속한다. 즉 대학은 소속학과에 종속된다.
- 홍길동 → 컴퓨터과이고 컴퓨터과→공대일 때, 홍길동→공대인 관계가 성립한다.

학번	이름	소속학과	대학
1901	홍길동	컴퓨터과	공대
1845	임꺽정	전자과	공대
1706	신사임당	경제	경상
1925	장영실	경영	경상

발생할 수 있는 이상(Anomaly)의 예
- 삽입 이상: 컴퓨터과, 전자과 학생을 추가하고자 할 경우 더이상 불필요한 중복정보인 대학 정보가 삽입되어야 한다.
- 갱신 이상: 컴퓨터과의 소속 대학이 'IT대학'으로 변경되었다. 하나만 변경하면 모순이 발생하므로 다 찾아서 변경해야 한다.
- 삭제 이상: 홍길동이 자퇴해서 삭제하고자 한다. 이 삭제로 인해 컴퓨터과의 대학 정보가 사라져 버린다.
3NF를 만족시키는 릴레이션

학번	이름	소속학과
1901	홍길동	컴퓨터과
1845	임꺽정	전자과
1706	신사임당	경제
1925	장영실	경영

소속학과	대학
컴퓨터과	공대
전자과	공대
경제	경상
경영	경상

BCNF

Boyce and Codd Normal Form
BCNF를 만족하려면 결정자이면서 후보 키가 아닌 속성을 제거해야 한다.

BCNF를 만족하지 않는 릴레이션


학번	과목	교수
100	데이터베이스	홍길동
100	자료구조	임꺽정
200	네트워크	장영실
300	네트워크	장영실
300	인공지능	유관순

제약사항
- 한 학생은 동일한 과목에 대해 한 교수에게만 수강 가능
- 각 교수는 하나의 과목만 담당
- 한 과목은 여러 교수가 담당 가능
후보 키: (학번, 과목)
함수적 종속성
- (학번, 과목) → 교수
- 교수 → 과목

발생할 수 있는 이상(Anomaly)의 예
- 삽입 이상: 200 학생이 데이터베이스를 수강하고자 할 경우, 현재 불필요한 홍길동 교수 정보가 한번 더 삽입된다.
- 갱신 이상: 장영실 교수의 담당 과목이 알고리즘으로 변경되면, 장영실 교수의 과목을 수강하는 모든 학생들의 튜플도 검색해서 수정해야 한다.
- 삭제 이상: 300 학생이 자퇴해서 삭제하고자 한다. 이 삭제로 인해 인공지능 과목을 유관순 교수가 담당하고 있다는 정보가 사라진다.
BCNF 분해 방법
- 함수적 종속성 Z → X가 있으며 Z가 후보 키가 아닌 경우, (R - X)와 ZX로 릴레이션을 분리
- 예시. 함수적 종속성 (교수 → 과목)이 있으며, 교수가 후보 키가 아니기 때문에, (학번, 교수), (교수, 과목)으로 분리
BCNF 분해의 특징
- 무손실 조인 분해
- 종속성 유지가 불가능할 수 있음(예시의 경우 함수적 종속성 "(학번, 과목) → 교수"를 유지할 수 없음)
BCNF를 만족시키는 릴레이션
- 삽입 이상 해결: 200 학생이 데이터베이스를 수강하기 위해, 홍길동 교수의 정보가 삽입될 필요가 없어진다.
- 갱신 이상 해결: 장영실 교수의 담당 과목을 변경하기 위해 다른 튜플들을 검색해서 수정할 필요가 없다.
- 삭제 이상 해결: 300 학생이 자퇴하면, 300 학생의 수강 정보만 삭제하면 된다.

학번	교수
100	홍길동
100	임꺽정
200	장영실
300	장영실

과목	교수
데이터베이스	홍길동
자료구조	임꺽정
네트워크	장영실

4NF

Fourth Normal Form
4NF를 만족하려면 다치 종속성을 제거해야 한다.

다치 종속성(MVD, Multi-Valued Dependency) A →→ B: A 값 하나에 B 값의 집합이 대응하고, 그 집합이 다른 속성 C 와 독립인 관계
4NF를 만족하지 않는 릴레이션
- 한 과목은 여러 교수가 가르치고, 여러 교재를 쓴다. 교수와 교재는 서로 관계가 없다(과목 →→ 교수, 과목 →→ 교재)

과목	교수	교재
데이터베이스	홍길동	교재A
데이터베이스	홍길동	교재B
데이터베이스	임꺽정	교재A
데이터베이스	임꺽정	교재B

발생할 수 있는 이상(Anomaly)의 예
- 삽입 이상: 데이터베이스 과목에 교재C 를 추가하려면 교수 수만큼(홍길동, 임꺽정) 튜플을 넣어야 한다
- 삭제 이상: 임꺽정 교수를 빼려고 튜플을 지울 때 일부만 지우면 교재 정보가 어긋난다
4NF를 만족시키는 릴레이션: (과목, 교수), (과목, 교재)로 분해한다. 공통 속성 과목이 각 다치 종속의 결정자이므로 무손실 분해다

과목	교수
데이터베이스	홍길동
데이터베이스	임꺽정

과목	교재
데이터베이스	교재A
데이터베이스	교재B

5NF

Fifth Normal Form
5NF를 만족하려면 조인 종속성 제거해야 한다.

조인 종속성(JD, Join Dependency): 릴레이션을 셋 이상으로 분해한 뒤 조인해야만 원래 릴레이션이 복원되는 관계. 두 개로는 무손실 분해가 안 되고 세 개로는 되는 경우다
5NF(PJNF, 프로젝트-조인 정규형)는 모든 조인 종속성이 후보 키를 통해서만 성립하는 상태다
5NF를 만족하지 않는 릴레이션
- 공급(공급자, 부품, 프로젝트)에서 "공급자가 그 부품을 공급하고, 그 부품이 프로젝트에 쓰이고, 공급자가 그 프로젝트에 납품하면 반드시 공급자가 그 부품을 그 프로젝트에 공급한다"는 규칙이 있는 경우
발생할 수 있는 이상(Anomaly)의 예
- 삽입 이상: 위 규칙 때문에 튜플 하나를 넣으면 규칙을 맞추기 위해 다른 튜플도 함께 넣어야 한다
5NF를 만족시키는 릴레이션: (공급자, 부품), (부품, 프로젝트), (공급자, 프로젝트) 세 릴레이션으로 분해한다. 셋을 모두 조인하면 원래 릴레이션이 복원되고, 둘만 조인하면 가짜 튜플이 생긴다

무손실 조인 분해

Lossless Join Decomposition; 무손실 분해

정규화는 릴레이션을 여러 개로 분해하는 과정이다. 분해한 릴레이션들을 다시 자연 조인했을 때 원래 릴레이션과 정확히 같은 튜플이 나오면 무손실 조인 분해라고 한다. 원래 없던 튜플(가짜 튜플, spurious tuple)이 생기면 손실 분해다. 튜플이 늘어나는데도 '손실'이라 부르는 것은, 어느 튜플이 진짜인지 구분할 정보를 잃었기 때문이다.

정규화에서 분해가 지켜야 할 두 조건은 다음과 같다.

무손실 조인: 반드시 지켜야 한다. 어기면 데이터가 틀려진다
종속성 보존: 원래의 함수적 종속성을 분해된 릴레이션 안에서 검사할 수 있는 것. 가능하면 지킨다. 3NF 까지는 두 조건을 모두 만족하는 분해가 항상 있지만, BCNF 는 종속성 보존을 포기해야 할 때가 있다(위 BCNF 예)

판정 조건

릴레이션 R 을 R1 과 R2 로 분해할 때, 함수적 종속성 집합 F 에 대해 다음 중 하나가 성립하면 무손실 조인 분해다.

(R1 ∩ R2) → (R1 − R2)
(R1 ∩ R2) → (R2 − R1)

즉 두 릴레이션의 공통 속성이 적어도 한쪽 릴레이션의 키(슈퍼키)여야 한다. 셋 이상으로 분해할 때는 행렬(tableau)을 만들어 함수적 종속성을 적용해 보는 검사법(chase)을 쓴다.

예

학생(학번, 학과, 학과장)에 함수적 종속성 학번 → 학과, 학과 → 학과장 이 있다. 김교수는 컴퓨터과와 소프트웨어과의 학과장을 겸임한다(학과장 → 학과 는 성립하지 않는다).

학번	학과	학과장
1901	컴퓨터과	김교수
1925	소프트웨어과	김교수

무손실 분해: R1(학번, 학과), R2(학과, 학과장)
- 공통 속성 학과 → 학과장 이므로 학과는 R2 의 키다. 조건 (R1 ∩ R2) → (R2 − R1) 을 만족한다
- R1 ⋈ R2 는 원래의 두 튜플만 돌려준다
손실 분해: R1(학번, 학과장), R2(학과, 학과장)
- 공통 속성 학과장은 어느 쪽의 키도 아니다(학과장 → 학번, 학과장 → 학과 모두 성립하지 않음)
- R1 ⋈ R2 를 하면 학과장 '김교수'로 묶여 네 튜플이 나온다

학번	학과	학과장
1901	컴퓨터과	김교수
1901	소프트웨어과	김교수
1925	컴퓨터과	김교수
1925	소프트웨어과	김교수

굵게 표시한 두 튜플이 가짜 튜플이다. 1901 학생이 어느 학과인지 알 수 없게 되었다

정규형별 분해의 성질

정규형	무손실 조인	종속성 보존
3NF	항상 가능	항상 가능
BCNF	항상 가능	보장되지 않음
4NF	항상 가능	보장되지 않음

같이 보기