11. 데이타 종속성과 정규화.

Presentation on theme: "11. 데이타 종속성과 정규화."— Presentation transcript:

1 11. 데이타 종속성과 정규화

2  데이타의 논리적 표현 관계 스킴(relational scheme)의 설계
관계 모델을 이용하여 어떻게 실세계를 정확히 표현할 것인가? i. 애트리뷰트, 엔티티, 관계성을 파악 ⅱ. 관련된 애트리뷰트들을 릴레이션으로 묶음 데이타 종속성 : 애트리뷰트들간의 관계성 효율적인 데이타 조작 데이타의 중복성 iii. 변칙적 성질의 예방 이상(anomaly)

3 ▶ 이상 (anomaly) example : 수강 릴레이션 기본키 : 학번, 과목 번호 학번 과목번호 성적 학년 100
C413 A 4 E412 200 C123 B 3 300 C312 1 C324 C 400 500 2 수강 기본키 : 학번, 과목 번호

4 ▶ 이상(2) 삭제이상(deletion anomaly) 삽입이상(insertion anomaly)
200번 학생이 'C123'의 등록을 취소 ⇒ 3학년이라는 정보도 함께 삭제됨 연쇄 삭제(triggered deletion)에 의한 정보의 손실(loss of information) 삽입이상(insertion anomaly) 600번 학생이 2학년이라는 사실을 삽입 ⇒ 어떤 과목을 등록하지 않는 한 삽입이 불가능 (∵ 과목 번호가 기본 키) 원하지 않는 정보의 강제 삽입 갱신이상(update anomaly) 400번 학생의 학년을 4에서 3으로 변경 ⇒ 학번이 400인 4개의 투플 모두를 갱신시켜야 함 중복데이타의 일부 갱신으로 정보의 모순성(inconsistency) 발생

5 ▶ 이상의 원인과 해결책 이상의 원인 이상의 해결 애트리뷰트들 간에 존재하는 여러 종속관계를 하나의 릴레이션에 표현
애트리뷰트들 간의 종속관계를 분석하여 여러개의 릴레이션으로 분해(decomposition) ⇒ 정규화(normalization)

6 ▶ 스키마 설계와 변환 스키마 설계 : 데이타베이스의 논리적 설계 스키마 변환의 원리
① 애트리뷰트들과 이들의 제약 조건 (종속성)들을 수집 ② 수집된 결과를 명시된 제약 조건에 따라 여러 개의 릴레이션으로 분할 ⇒ 스키마 변환 (schema transformation) 스키마 변환의 원리 ① 정보의 무손실 ② 데이타의 중복성 감소 ③ 분리의 원칙

7  함수 종속(FD) 정의 어떤 릴레이션 R에서, 애트리뷰트 X의 값 각각에 대해 애트리뷰트 Y의 값이 하나만 연관
 애트리뷰트 Y는 애트리뷰트 X에 함수 종속 X  Y 애트리뷰트 X는 Y를 (함수적으로) 결정 X를 결정자(determinant) Y를 종속자(dependent) X, Y는 복합 애트리뷰트일 수 있음

8  함수 종속(2) ☞Note 릴레이션 R에서 애트리뷰트 X가 키이면, R의 모든 애트리뷰트 Y에 대해 X  Y 성립
즉, x( X)값이 하나 이상의 투플값으로 존재가능

9  함수 종속 다이어그램 수강 릴레이션 ( 기본키: 학번, 과목번호) 학년 학번 성적 과목번호 {학번, 과목번호}  성적
학번  학년

10 ▶ 완전 함수 종속과 부분 함수 종속 복합 애트리뷰트 X에 대하여 X  Y가 성립할 때
완전 함수 종속 (full functional dependency) X’  X 이고 X’  Y 를 만족하는 애트리뷰트 X'이 존재하지 않음 부분 함수 종속 (partial functional dependency) X’  X 이고 X’  Y 를 만족하는 애트리뷰트 X'이 존재함

11 ▶ 완전 함수 종속과 부분 함수 종속(2) 예: 수강 릴레이션의 함수 종속 학번  학년 {학번,과목번호}  성적
학번  학년 {학번,과목번호}  성적 (학년)은 (학번)에 완전 함수 종속, 그러나 {학번,과목번호}에는 부분 함수 종속, (성적)은 {학번,과목번호}에 완전 함수 종속

12 ▶ 완전 함수 종속과 부분 함수 종속(3) 함수 종속에 대한 추론 규칙 ☞ Note
R1: (반사, reflexive) A  B이면 A  B이다. 또한 A  A이다 R2: (첨가, augmentation) A  B이면 AC  BC이고 AC  B이다. R3: (이행, transitive) A  B이고 B  C이면 A  C이다. R4: (분해, decomposition) A  BC이면 A  B이다. R5: (결합, union) A  B이고 A  C이면 A  BC이다. ☞ Note 함수 종속은 데이타의 의미(data semantics) 를 표현 예: “학번  학년”의 의미는 “학생은 하나의 학년에만 속한다” 의미적 제약 조건 DBMS는 함수 종속을 유지하기 위하여 함수 종속을 스키마에 명세하는 방법과 함수 종속을 보장하는 방법을 제공하여야 함

13  기본 정규형 정규형(Normal Form) 정규화(Normalization)의 원칙
어떤 일련의 제약 조건을 만족하는 릴레이션 정규화(Normalization)의 원칙 정규화 ＝ 스키마 변환 (S  S') ① 무손실 표현 같은 의미의 정보 유지 그러나 더 바람직한 구조 ② 데이타의 중복성 감소 ③ 분리의 원칙 독립적인 관계는 별개의 릴레이션으로 표현 릴레이션 각각에 대해 독립적 처리가 가능

14 ▶ 제1정규형 (1NF) 정의 예 : 수강지도 릴레이션 모든 도메인이 원자값(atomic value)만으로 된 릴레이션
예 : 수강지도 릴레이션 수강지도 (학번,지도교수,학과,과목번호,성적) 기본 키 : {학번,과목번호} 함수 종속 : {학번,과목번호}  성적 학번  지도교수 학번  학과 지도교수  학과 학번 과목번호 성적 학과 지도교수

15 ▶ 제1정규형(2) 학번 과목번호 성적 학과 100 C413 A 컴퓨터 E412 200 C123 B 전기 300 C312
400 수강 지도 지도교수 P1 P2 P3

16 ▶ 제1정규형(3) 1NF에서의 이상 ① 삽입이상 ② 삭제이상 ③ 갱신이상
500번 학생의 지도교수가 P4라는 사실의 삽입은 어떤 교과목을 등록하지 않는 한 삽입 불가능 ② 삭제이상 200번 학생이 C123의 등록을 취소하여 이 투플을 삭제할 경우 지도교수가 P2라는 정보까지 손실됨 ③ 갱신이상 400번 학생의 지도교수를 P1에서 P3로 변경할 경우 학번이 400인 4개 투플의 지도교수 값을 모두 P3로 변경해야 함

17 ▶ 제1정규형(4) 1NF 이상의 원인 1NF 이상의 해결 기본키에 부분 함수 종속된 애트리뷰트가 존재
기본키로 식별되는 개체와 무관한 애트리뷰트가 존재 두가지 상이한 정보가 포함 1NF 이상의 해결 프로젝션으로 릴레이션을 분해 (부분 함수 종속을 제거) ⇒ 2NF

18 ▶ 제2정규형 (2NF) 1NF 2NF 프로젝션 조인 정의 무손실 분해(nonloss decomposition)
프로젝션하여 분해된 릴레이션들은 자연 조인을 통해 원래의 릴레이션으로 복귀 가능 원래의 릴레이션에서 얻을 수 있는 정보는 분해된 릴레이션들로 부터도 얻을 수 있음 그러나, 그 역은 성립하지 않음 (500번 학생의 지도교수가 P4라는 정보는 원래의 릴레이션에서 표현할 수 없음) 1NF 2NF 프로젝션 조인

19 ▶ 제2정규형(2) ☞ Note: Heath의 무손실 분해 R(A,B,C)에서 함수 종속 A  B가 성립하면
⇒ R1(A,B), R2(A,C) 로 무손실 분해 가능

20 ▶ 제2정규형(3) 예 : 수강지도 ⇒ 지도, 수강 릴레이션 지도 (학번, 지도교수, 학과) 기본 키 : {학번}
예 : 수강지도 ⇒ 지도, 수강 릴레이션 지도 (학번, 지도교수, 학과) 기본 키 : {학번} 수강 (학번, 과목번호, 성적) 기본 키 : {학번, 과목번호} 외래 키 : {학번} 참조 : 지도 학번 과목번호 학과 지도교수 성적

21 ▶ 제2정규형(4) 학번 학과 100 컴퓨터 200 전기 300 400 지도 지도교수 P1 P2 P3 과목번호 성적 C413
A E412 C123 B C312 C324 C 학번 100 200 300 400 수강

22 ▶ 제2정규형(5) 2NF(지도 릴레이션)에서의 이상 2NF 이상의 원인 ① 삽입이상 ② 삭제이상 ③ 갱신이상
어떤 지도교수가 특정 학과에 속한다는 사실의 삽입 불가능 ② 삭제이상 300번 학생의 투플을 삭제하면 지도교수 P3가 컴퓨터공학과에 속한다는 정보 손실 ③ 갱신이상 지도교수 P1의 소속이 컴퓨터공학과에서 전자과로 변경된다면 학번이 100과 400번인 두개의 투플을 모두 변경하여야 함 2NF 이상의 원인 이행적 함수 종속이 존재

23 ▶ 제2정규형(6) ☞ Note : 2NF 이상의 해결 이행적 함수 종속 (TD, Transitive Dependency)
A  B이고 B  C ⇒ A  C (즉, 애트리뷰트 C는 애트리뷰트 A에 이행적 함수 종속) 2NF 이상의 해결 프로젝션으로 릴레이션 분해 (이행적 함수 종속을 제거) ⇒ 3NF

24 ▶ 제3정규형 (3NF) 정의(3NF) 무손실 분해
원래의 릴레이션에서 얻을 수 있는 정보는 분해된 릴레이션들로부터도 얻을 수 있으나 그 역은 성립하지 않음 (지도교수 P4가 수학과에 속한다는 정보의 표현) 2NF 3NF 프로젝션 조인

25 ▶ 제3정규형(2) 예 : 지도 ⇒ 학생지도, 지도교수학과 릴레이션 학생지도 (학번, 지도교수) 기본 키 : {학번}
예 : 지도 ⇒ 학생지도, 지도교수학과 릴레이션 학생지도 (학번, 지도교수) 기본 키 : {학번} 외래 키 : {지도교수} 참조 : 지도교수학과 지도교수학과 (지도교수, 학과) 기본 키 : {지도교수} 지도교수 학과 학번 학번 100 200 300 400 학생지도 지도교수 P1 P2 P3 학과 컴퓨터 전기 지도교수 P1 P2 P3 지도교수학과

26 ▶ 제3정규형(3) ☞ Note 키가 아닌 애트리뷰트 값의 갱신시 불필요한 부작용(이상) 발생 없음
모든 이진 릴레이션은 3NF에 속함

27 ▶ 제3정규형(4) 3NF의 약점 i . 복수의 후보키를 가지고 있고 ii . 후보키들이 복합 애트리뷰트들로 구성되고
⇒ 적용 불가능 ⇒ 보다 일반적인 Boyce/Codd Normal Form(BCNF)을 제안

28 ▶ 보이스/코드 정규형(BCNF) 정의 릴레이션 R이 BCNF에 속하면 R은 제1, 제2, 제3 정규형에 속함
릴레이션 R의 모든 결정자가 후보키이면 릴레이션 R은 BCNF에 속한다. 릴레이션 R이 BCNF에 속하면 R은 제1, 제2, 제3 정규형에 속함 강한 제3정규형(strong 3NF)이라고도 함

29 ▶ 보이스/코드 정규형(2) 예(3NF) : 수강과목 릴레이션 제약 조건 수강과목 (학번,과목,교수)
각 과목에 대한 한 학생은 오직 한 교수의 강의만 수강 각 교수는 한 과목만 담당 한 과목은 여러 교수가 담당할 수 있음 수강과목 (학번,과목,교수) 후보키 : {학번,과목}, {학번,교수} 기본키 : {학번,과목} 함수종속 : {학번,과목}  교수 교수  과목 수강과목 학번 과목 교수 100 프로그래밍 P1 100 자료구조 P2 학번 200 프로그래밍 P1 교수 200 자료구조 P3 과목 300 자료구조 P3 300 프로그래밍 P4

30 ▶ 보이스/코드 정규형(3) 3NF(수강과목 릴레이션)에서의 이상 ⇒ 원인 : 교수가 결정자이지만 후보키가 아님 ① 삽입이상
교수 P5가 자료구조를 담당한다는 사실의 삽입은 학번(수강 학생)이 있어야 가능 ② 삭제이상 100번 학생이 자료구조를 취소하여 투플을 삭제하면 P2가 담당교수라는 정보도 삭제됨 ③ 갱신이상 P1이 프로그래밍 과목 대신 자료구조를 담당하게 되면 P1이 나타난 모든 투플을 변경하여야 함 ⇒ 원인 : 교수가 결정자이지만 후보키가 아님

31 ▶ 보이스/코드 정규형(4) 예(BCNF) : 수강과목 ⇒ 수강교수, 과목교수 교수 과목 학번 수강교수(학번, 교수)
기본 키 : {학번, 교수} 외래키 : {교수} 참조 : 과목교수 과목교수(교수, 과목) 기본 키 : {교수} 과목 프로그래밍 자료구조 교수 P1 P2 P3 P4 과목교수 학번 100 200 수강교수 교수 P1 P2 P3 300 P4 교수 과목 학번

32  고급 정규형 과목(C) 화일구조 데이타베이스 교수(P) P1 P2 P3 과목 목록(UCPT) 교재(T) T1 T2 T3
 비정규형 (Rpeating Croup) 교수(P) 과목(C) 교재(T) P1 화일구조 T1 T2 P2 P3 데이타베이스 T3 T4 T5 개설 과목(CPT)  BCNF ∵(키에 속하지 않는 결정자 애트리뷰트가 없음) 기본키: (과목, 교수, 교재)

33  고급 정규형(2) 개설교과목에서의 변경 이상 BCNF 이상의 원인
P4가 데이타베이스를 담당한다는 정보삽입 시 3개의 교재에 대한 투플을 삽입해야 함 BCNF 이상의 원인 즉, 과목은 교수나 교재의 값 하나를 결정하는 것이 아니라 값의 집합(set of values)을 결정 과목 교수|교재 (화일구조)  { P1, P2 } (화일구조)  { T1, T2 }

34  고급 정규형(3) 다치 종속 (MVD, Multi-Valued Dependency)
정의: 릴레이션 R(A,B,C)에서 어떤 (A, C)값에 대응하는 B값의 집합이 A값에만 종속되고 C값에 독립이면 다치 종속 A B가 성립 , 즉 (A,C)  { B }  A  { B } A multi-determines B B is multi-dependent on A A B이면 A C도 성립 즉, A B|C 모든 FD는 MVD이나, 역은 성립하지 않음 즉, A  B이면 A B가 성립 MVD를 가진 릴레이션의 분해(Fagin의 정리) R(A,B,C)에서 MVD A B|C이면 R1(A,B)와 R2(A,C)로 무손실 분해 가능

35 ▶ 제4정규형 (4NF) 정의 BCNF를 이용한 정의 의미
릴레이션 R에서 MVD A B가 존재할 때 R의 모든 애트리뷰트들이 A에 함수 종속(FD)이면 R은 4NF (즉 R의 모든 애트리뷰트 X에 대해 A  X 이고 A가 후보키) BCNF를 이용한 정의 릴레이션 R이 BCNF에 속하고 모든 MVD가 FD이면 R은 4NF 의미 어떤 릴레이션 R이 4NF이라면 MVD가 없거나, MVD A B|C가 있을 경우 A에 대응되는 B와 C의 값은 하나씩 이어야 하며 이때 A는 후보키라는것을 의미한다.

36 ▶ 제4정규형(2) 예 교수(P) 과목(C) 교재(T) P1 화일구조 T1 T2 P2 P3 데이타베이스 T3 T4 T5
개설 교과목  BCNF ∵(키에 속하지 않는 결정자 애트리뷰트가 없음) 기본키: (과목, 교수, 교재) MVD 과목 교수|교재 과목(C) 교재(T) 화일구조 T1 T2 데이타베이스 T3 T4 T5 과목교재 4NF 과목(C) 화일구조 데이타베이스 교수(P) P1 P2 P3 과목 교수

37 ▶ 제5정규형(5NF) 예 : 릴레이션 SPC(4NF) SPC를 프로젝션하여 세 개의 SP,PC,CS를 생성
세 개의 릴레이션 SP,PC,CS를 조인해서는 SPC의 재생성이 가능하나 그 어느 두 개의 조인만으로는 재생성 불가능

38 프로젝션과 조인 프로젝션 조인 SPC SK PK CK S1S1S2S1 P1P2P1P1 C2C1C1C1 프로젝션 SP SK PK
첫번째 조인 SK PK CK S1S1S1 P1P1P2 C2C1C1 S2 P1 C2 C1 부당투플 프로젝션 조인 두번째 조인

39 ▶ 제5정규형(2) 3-분해 릴레이션 릴레이션 SPC가 세 개의 프로젝션 SP,PC,CS의 조인과 동등하다는 것은
(S1,P1)  SP (P1,C1)  PC  (S1,P1,C1)  SPC (C1,S1)  CS 즉 다음의 순환적 제약조건(3D)을 만족 (S1,P1,C2)  SPC (S2,P1,C1)  SPC  (S1,P1,C1)  SPC (S1,P2,C1)  SPC SPC : 3-분해 릴레이션 : 3D 제약조건을 만족

40 ▶ 제5정규형(3) n-분해 릴레이션(n>2)
n개의 프로젝션으로만 무손실 분해될 수 있으며 m(m<n)개의 프로젝션으로는 무손실 분해가 불가능한 릴레이션

41 ▶ 제5정규형(4) 조인 종속(JD, Join Dependency)
릴레이션 R이 그의 프로젝션 A, B, ..., Z의 조인과 동일하면 R은 JD *(A, B, ..., Z)을 만족. 이때 A,B,...,Z는 R의 애트리뷰트들에 대한 부분 집합. 릴레이션 R(A,B,C)가 JD *(AB,AC)을 만족하면, 한쌍의 MVD A B|C도 성립. JD는 MVD의 일반형, MVD는 JD의 특별한 경우(2-분해) SPC 릴레이션은 JD *(SP, PC, CS)를 만족 3-분해 릴레이션 JD를 만족하는 n-분해 릴레이션은 n개의 프로젝션으로 분해해야 함.

42 ▶ 제5정규형(5) 릴레이션에서의 갱신이상 ① 삽입이상
릴레이션 SPC’에서 (S2,P1,C1)의 삽입시 (S1,P1,C1)의 삽입 필요 역은 성립 않음 SK PK CK S1 P1 C2 P2 C1 SPC’

43 ▶ 제5정규형(6) 릴레이션의 갱신이상(con’t) ② 삭제이상  이상의 원인 : SPC는 3-분해 릴레이션
릴레이션 SPC에서 (S1,P1,C1)의 삭제시 다른 투플 중 어느 하나를 함께 삭제하여야 함 (S2,P1,C1)의 삭제는 이상 없이 가능  이상의 원인 : SPC는 3-분해 릴레이션  이상의 해결 : 릴레이션 SPC를 3-분해함 S1 P1 C2 P2 C1 S2 SK PK CK SPC

44 ▶ 제5정규형(7) 제5정규형(5NF) 정의 프로젝션-조인 정규형(PJ/NF) 예1:
릴레이션 R에 존재하는 모든 조인 종속이 R의 후보키를 통해 성립되면, R은 5NF 프로젝션-조인 정규형(PJ/NF) 예1: SPC : JD *(SP,PC,CS)는 후보키 (S,P,C)를 통하지 않으므로 NF이 아님 SP,PC,SC : 5NF

45 ▶ 제5정규형(8) 제5정규형 (5NF) (con’t) 예2:
학생(학번,이름,학과,학년) 릴레이션의 후보키가 학번과 이름일 경우 JD *((학번,이름,학과), (학번,학년)) JD *((학번,이름), (학번,학년), (이름,학과)) 위의 JD는 모두 후보키를 통해 성립되므로 5NF

46  정규형들 간의 관계 정규화 과정 (무손실 분해) 비정규 릴레이션 원자값이 아닌 결정자가 후보키가 도메인을 분해
1NF 부분 함수종속 제거 2NF 이행 함수 종속 제거 3NF 결정자가 후보키가 아닌 함수종속(FD) 제거 BCNF 함수종속이 아닌 다치종속(MVD) 제거 4NF 후보키를 통하지 않은 조인종속(JD) 제거 5NF

47  정규형들 간의 관계(2) 정규형들 간의 포함 관계 정규 또는 비정규 릴레이션 1NF 2NF 3NF BCNF 4NF 5NF
(PJ/NF) 4NF BCNF 3NF 2NF 1NF 정규 또는 비정규 릴레이션

48  정규형들 간의 관계(3) ☞ Note 릴레이션의 정규화는 실제 데이타 값이 아니라 개념적인 측면에서 다루어져야 함
릴레이션의 정규화는 실제 데이타 값이 아니라 개념적인 측면에서 다루어져야 함 실제 정규화 과정은 정규형의 순서와 다를 수 있음

49  정규형들 간의 관계(4) ☞ Note 현실적으로 모든 릴레이션을 반드시 5NF에 속하도록 분해할 필요는 없음
기본키 : 학번 FD : 전화번호→주소 학생전화(학번,이름,전화번호) : 5NF 전화주소(전화번호,주소) : 5NF  이름, 전화번호, 주소는 분리하지 않고 사용하는 것이 편리하므로 위의 5NF으로의 분해는 무의미함