데이터종속성과정규화
이장의주요내용 데이터의잘못된논리적표현으로인해발생하는이상현 상들 함수종속성 정규화 제 1 정규형, 제 2 정규형, 제 3 정규형, BCNF 제 4 정규형, 제 5 정규형 참고문헌 데이타베이스시스템, 이석호저, 정익사 (chapter 11 장 ), 2005 년 2
데이타의논리적표현 조직체가가지고있는대량의운용데이터를어떻게조직해야효율적으로관리할수있는가? 논리적데이타베이스설계문제 관계모델을이용하여어떻게실세계를정확히표현할것인가? 관계스키마설계 필요한애트리뷰트, 엔티티, 관계성을식별하고수집 위의요소들을릴레이션으로만듦 고려해야할사항 데이타종속성 (data dependancy) : 애트리뷰트들간의관계성 효율적인데이타처리 데이터의일관성유지등 설계가잘못되면실제데이터를처리할때부작용이발생하기쉬움
이상현상의예 1/3 이상현상 릴레이션을처리할때곤란한현상 예 ) 수강릴레이션 삭제이상발생 기본키 : { 학번, 과목번호 } 수강 학번 과목번호 성적 학년 100 C413 A 4 100 E412 A 4 200 C123 B 3 300 C312 A 1 300 C324 C 1 300 C413 A 1 400 C312 A 4 400 C324 A 4 400 C413 B 4 400 C412 C 4 500 C312 B 2 갱신이상발생 ( 학년 4 3) 600 2 삽입이상발생
이상현상의예 2/3 삭제이상 (deletion anomaly) 예 ) 200 번학생이 'C123' 의등록을취소할경우 정의 과목번호가기본키값의일부분이므로, 투플전체를삭제해야함 3 학년이라는정보도함께삭제됨 한튜플을삭제함으로써유지해야될정보까지도삭제되는연쇄삭제 (triggered deletion) 에의한정보의손실이발생하게되는현상 삽입이상 (insertion anomaly) 예 ) 600 번학생이 2 학년이라는사실만을삽입하려고할경우 정의 { 학번과과목번호 } 가기본키이므로, 어떤과목을등록하지않는한삽입이불가능 만일삽입하고자할경우, 가상의임시과목번호를함께삽입해야함 원하지않는데이터도함께삽입해야만되고그렇지않으면삽입이되지않는현상
이상현상의예 3/3 갱신이상 (update anomaly) 예 ) 학번이 400 번학생의학년을 4 에서 3 으로변경시키고자할경우 정의 학번이 400 인 4 개의투플에대해학년의값을모두를갱신시켜야함 만일일부투플만변경시킨다면, 학번 400 인학생의학년은 3 과 4, 즉두가지값을가지게됨 중복된투플들중에서일부투플의애트리뷰트값만을갱신시킴으로써정보의비일관성 (inconsistency) 이생기는현상
이상의원인과해결책 이상의원인 여러가지상이한종류의정보를하나의릴레이션으로표현하려하기때문 즉, 애트리뷰트들간에존재하는여러가지데이터종속관계를무리하게하나의릴레이션에표현하려는데서발생 해결방안 애트리뷰트들간의종속성 (dependency) 를분석하여하나의릴레이션에는기본적으로하나의종속성이표현되도록분해함 (decomposition) 이러한분해과정을정규화 (normalization) 라고함
스키마변환 일단만들어진릴레이션들을바람직한형태의릴레이션 들로다시변환하는것 스키마변환의원리 정보의무손실 최소의데이터중복 분리의원칙 하나의독립된관계성은하나의릴레이션으로분리시켜표현
함수종속 FD : Functional Dependency 애트리뷰트들의그룹핑을릴레이션스키마로바꾼것의적절성을정형적으로측정하기위한도구 애트리뷰트들의두개의집합사이의제약조건 데이터의의미를표현 정의 어떤릴레이션 R 에서 X 와 Y 를각각 R 의애트리뷰트라고하자. 애트리뷰트 X 의값각각에대해항상애트리뷰트 Y 의값이오직하나만연관되어있을때 애트리뷰트 Y 는애트리뷰트 X 에함수종속 X Y 이라고함 X : 결정자, Y : 종속자
함수종속예 예 ) 학생릴레이션 학번이름학년학과 학번 이름, 학번 학년, 학번 학과 이유 : 어떤학생의학번이정해지면, 그학번에대응하는이름, 학년, 학과의값은오직하나만있기때문
함수종속다이어그램 FD Diagram 한릴레이션에서애트리뷰트들간의복잡한함수종속관계를쉽게이해하기위해도식으로표현 예 ) 수강릴레이션 함수종속 학번과목번호성적학년 { 학번, 과목번호 } 성적 : 완전함수종속 { 학번, 과목번호 } 학년 : 부분함수종속 학번 학년 : 완전함수종속 학년 학번 과목번호 성적
완전함수종속과부분함수종속 복합애트리뷰트 X 에대하여 X Y 가성립할때 완전함수종속 (full functional dependency) X X 이고 X Y 를만족하는애트리뷰트 X' 이존재하지않음 부분함수종속 (partial functional dependency) X X 이고 X Y 를만족하는애트리뷰트 X' 이존재함
함수종속에대한추론규칙 어떤릴레이션 R 에존재하는함수종속에대해다음과같은추론규칙이성립됨 R1: ( 반사, reflexive) A B 이면 A B 이다. 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 이다.
기본정규형 (Normal Form) 정규형 (Normal Form) 어떤일련의제약조건을만족하는릴레이션 정규화란? 중복을최소화하고, 삽입, 삭제, 수정이상을최소화하기위해서함수적종속성과기본키를기반으로릴레이션스키마를분석하는과정 기본적인아이디어 서로독립적인관계는별개의릴레이션으로표현해야함 이렇게표현된릴레이션이어떤특정의제약조건을만족할때, 그제약조건을요건으로하는정규형에속한다고말함 제 1 정규형 ~ 제 5 정규형
정규형들간의포함관계 정규또는비정규릴레이션 1NF 2NF 3NF BCNF 4NF 5NF (PJ/NF)
정규형 (Normalization) 정규화 (Normalization) 의원칙 정규화 = 스키마변환 (S -> S') 1 무손실표현 같은의미의정보유지 그러나더바람직한구조 2 데이타의중복성감소 3 분리의원칙 독립적인관계는별개의릴레이션으로표현 릴레이션각각에대해독립적조작이가능 16
제 1 정규형 (1NF : First Normal Form) 정의 어떤릴레이션 R 에속한모든도메인이원자값 (atomic value) 만으로되어있다면제 1 정규형 (1NF) 에속한다 예 ) 수강지도릴레이션 함수종속 학번지도교수학과과목번호성적 { 학번, 과목번호 } 성적, 학번 지도교수, 학번 학과, 지도교수 학과 성적 학번 과목번호 지도교수 학과
제 1 정규형 : 수강지도릴레이션의예 수강지도릴레이션에서발생하는이상현상들 수강지도 삭제이상발생 삽입이상발생 학번 지도교수 학과 과목번호 성적 100 컴퓨터 C413 A 100 컴퓨터 E412 A 200 P2 전기 C123 B 300 P3 컴퓨터 C312 A 300 P3 컴퓨터 C324 C 300 P3 컴퓨터 C413 A 400 컴퓨터 C312 A 400 컴퓨터 C324 A 400 컴퓨터 C413 B 400 컴퓨터 C412 C 500 P4 갱신이상발생 ( P3)
제 1 정규형 : 1NF 에서의이상현상들 삽입이상 예 ) 500 번학생의지도교수가 P4 라는사실을삽입할경우 500 번인학생이어떤교과목을등록하지않으면기본키 { 학번, 과목번호 } 가 null 이되므로, 위의사실을삽입할수없음 삭제이상 예 ) 200 번학생이교과목 C123 의등록을취소할경우 학번이 200 번에관련된투플이하나만있는상황이므로, 이학생의지도교수가 P2 라는정보까지손실됨 갱신이상 예 ) 400 번학생의지도교수를 에서 P3 로변경할경우 만일학번이 400 인 4 개투플중일부만지도교수값을 P3 로변경할경우데이터의일관성을잃음
제 1 정규형 : 이상현상의원인및해결방안 1NF 이상의원인 기본키에부분함수종속된애트리뷰트가존재 두가지상이한정보가포함됨 해결방안 프로젝션으로릴레이션을분해 부분함수종속을제거 2NF
제 1 정규형 : 해결방안예 1NF : 지도교수와학과가기본키인 { 학번, 과목번호 } 에부분종속됨 성적 학번 과목번호 지도교수 학과 해결방안 수강지도 지도릴레이션과수강릴레이션으로분해 (2NF) 학번 지도교수 학과 학번 과목번호 성적
제 2 정규형 (2NF) 정의 어떤릴레이션 R 이 1NF 이고, 키에속하지않는애트리뷰트모두가기본키에완전함수종속이면, 제 2 정규형에속한다. 예 ) 지도, 수강릴레이션 수강 삭제이상발생 삽입이상발생 지도 갱신이상발생 ( 소속이컴퓨터 전자과 ) 학번 지도교수 학과 100 컴퓨터 200 P2 전기 300 P3 컴퓨터 400 컴퓨터 어떤교수가특정학과에소속된다는정보입력불가 학번 100 100 200 300 300 300 400 400 400 400 과목번호 C413 E412 C123 C312 C324 C413 C312 C324 C413 C412 성적 A A B A C A A A B C
제 2 정규형 : 지도릴레이션의이상 삽입이상 예 ) 어떤지도교수가특정학과에속한다는사실을삽입하려고할때삽입불가능 삽입할수있기위해서는이지도교수의지도를받는학생이있어야함 삭제이상 예 ) 300 번학생의투플을삭제하면지도교수 P3 가컴퓨터공학과에속한다는정보가손실됨 갱신이상 예 ) 지도교수 의소속이컴퓨터공학과에서전자과로변경된다면학번이 100 과 400 번인두개의투플을모두변경해야함
2NF 이상의원인 2NF 이상의원인 : 이행적함수종속이존재 이행적함수종속이란? TD, Transitive Dependency A B 와 B C A C 즉, 애트리뷰트 C 는애트리뷰트 A 에이행적함수종속 2NF 이상의해결방안 프로젝션으로릴레이션분해 이행적함수종속을제거 3NF
제 3 정규형 (3NF) 예 : 지도 학생지도, 지도교수학과릴레이션 학번 지도교수 지도교수 학과 학번 2NF 지도교수 학과 학생지도 학번 100 200 300 400 지도교수 P2 P3 지도교수학과 지도교수 P2 P3 학과컴퓨터전기컴퓨터 3NF 3NF 정의 어떤릴레이션 R 이 2NF 이고, 키에속하지않은모든애트리뷰트들이기본키에이행적함수종속이아닐때제 3 정규형에속한다
제 3 정규형의문제 3NF 의약점 i. 복수의후보키를가지고있고, ii. 후보키들이복합애트리뷰트들로구성되며, iii. 후보키들이서로중첩되는경우 적용불가능 보다일반적인 Boyce/Codd Normal Form(BCNF) 을제안
보이스 / 코드정규형 BCNF : Boyce/Codd Normal Form 정의 릴레이션 R 의모든결정자가후보키이면릴레이션 R 은 BCNF 에속한다. 릴레이션 R 이 BCNF 에속하면 R 은제 1, 제 2, 제 3 정규형에속함 강한제 3 정규형 (strong 3NF) 이라고도함
수강과목릴레이션예 제약조건 : 후보키 : { 학번, 과목 }, { 학번, 교수 } 각과목에대해한학생은오직한교수의강의만수강한다 각교수는한과목만담당한다 한과목은여러교수가담당한다. 학번 과목 3NF 교수 삽입이상발생 수강과목 학번 과목 100 프로그래밍 100 자료구조 200 프로그래밍 200 자료구조 300 자료구조 300 프로그래밍 자료구조 갱신이상발생 이프로그래밍 자료구조 교수 P2 P3 P3 P4 P5 삭제이상발생
3NF 에서의이상현상들 삽입이상 예 ) 교수 P5 가자료구조를담당한다는사실의삽입은적어도수강학생이한사람있어야가능 삭제이상 예 ) 100 번학생이자료구조를취소하여투플을삭제하면교수 P2 가자료구조과목을담당하고있다는정보도삭제됨 갱신이상 예 ) 교수 이프로그래밍과목대신자료구조를담당하게되면 이나타난모든투플들을변경하여야함 이상현상의원인 교수가결정자이지만후보키가아님
수강과목릴레이션에대한해결방안 수강과목 수강교수, 과목교수릴레이션 학번 교수 교수 과목 학번 과목 3NF 교수 수강교수 학번 100 100 200 200 300 300 교수 P2 P3 P3 P4 과목교수 교수 P2 P3 P4 과목프로그래밍자료구조자료구조프로그래밍 BCNF
제 4 정규형 예 ) 개설교과목릴레이션 교과목목록 개설교과목 과목 (C) 화일처리 데이타베이스 비정규형 교수 (P) P2 P3 교재 (T) T1 T2 T3 T4 T5 (Repeating Group) 과목 (C) 화일처리화일처리화일처리화일처리데이타베이스데이타베이스데이타베이스 교수 (P) P2 P2 P3 P3 P3 교재 (T) T1 T2 T1 T2 T3 T4 T5 BCNF ( 키에속하지않는결정자애트리뷰트가없음 )
개설교과목릴레이션의문제점과해결방안 갱신이상 새로운교수 P4 가데이타베이스를담당한다는정보삽입시, 3 개의교재 {T3, T4, T5} 에대한새로운 3 개의투플을삽입해야함 이상현상의원인 교수와교재가서로무관한것을한릴레이션으로묶어서표현한것이원인임 해결방안 과목교수 ( 과목, 교수 ) 릴레이션과과목교재 ( 과목, 교재 ) 릴레이션으로분해 분해원리 개설교과목릴리에션은모두키로구성되어있기때문에함수종속이없음 그러므로, 다치종속에의해분리
다치종속 MVD, Multi-Valued Dependency 정의 A, B, C 를릴레이션 R 의애트리뷰트의부분집합이라할때애트리뷰트쌍 (A, C)- 값에대응되는 B- 값의집합이 A- 값에만종속되고 C- 값에는독립이면 B 는 A 에다치종속이라함 표기 : A B 예 ) 개설교과목릴레이션 과목교수, 과목교재 MVD 를가진릴레이션의분해 (Fagin 의정리 ) R(A,B,C) 에서 MVD A B C 이면 R1(A,B) 와 R2(A,C) 로무손실분해가능
제 4 정규형정의 정의 릴레이션 R 에서 MVD A B 가존재할때 R 의모든애트리뷰트들이 A 에함수종속 (FD) ( 즉 R 의모든애트리뷰트 X 에대해 A X 이고 A 가후보키 ) 이면릴레이션 R 은제 4 정규형에속한다 BCNF 를이용한정의 의미 릴레이션 R 이 BCNF 에속하고모든 MVD 가 FD 이면 R 은 4NF 어떤릴레이션 R 이 4NF 이라면 MVD 가없거나, MVD A B C 가있을경우 A 에대응되는 B 와 C 의값은하나씩이어야하며이때 A 는후보키라는것을의미한다.
제 4 정규형예 개설교과목릴레이션에대한해결방안 교과목교수 개설교과목과목 (C) 화일처리화일처리화일처리화일처리데이타베이스데이타베이스데이타베이스 교수 (P) P2 P2 P3 P3 P3 교재 (T) T1 T2 T1 T2 T3 T4 T5 과목 (C) 화일처리화일처리데이타베이스 교과목교재 과목 (C) 화일처리화일처리데이타베이스데이타베이스데이타베이스 교수 (P) P2 P3 교재 (T) T1 T2 T3 T4 T5 4NF
조인종속 1/2 가정 릴레이션 R 에는 BCNF 까지의어떤정규형도위배하는함수적종속성이존재하지않음 또, 제 4 정규형을위배하는다치종속성도존재하지않음 R 을두개의스키마로무손실분해를할수없으나, 두개이상의릴레이션스키마로무손실분해할수있는경우 조인종속성이라는새로운종속성을사용 조인종속성이존재하는경우다중분해를통하여제 5 정규형을만듦 36
조인종속 2/2 릴레이션이그의어떤프로젝션들을조인한결과와똑같아야한다는제약조건 조인종속정의 어떤릴레이션 R 의애트리뷰트들에대한부분집합 A1, A2,An 이있다고하자. 이때만일릴레이션 R 이그의프로젝션 A1, A2,, An 을모두조인한결과와똑같이된다면 R 은조인종속 * (A1, A2,An) 을만족시킨다고한다. 즉, 릴레이션 R 이조인종속 * (A1, A2,An) 만족하면 n- 분해릴레이션이다.
조인종속으로인한이상현상들 1/2 예 ) SUPPLY 릴레이션 제약조건 공급자 s 가부품 p 를공급하고, 프로젝트 c 에서부품 p 가사용되고, 공급자 s 가적어도하나이상의부품을프로젝트 c 에사용할때마다 공급자 s 는부품 p 를프로젝트 c 에공급하는것을하나의릴레이션에표현 삽입이상현상 SUPPLY 릴레이션에서 (S2,,C1) 의삽입시 (S1,,C1) 의삽입 필요 SK PK CK S1 C2 S1 P2 C1 38
조인종속으로인한이상현상들 2/2 삭제이상현상 SUPPLY 릴레이션에서 (S1,,C1) 의삭제시다른투플들중어느하나를함께삭제하여야함 SK PK CK S1 C2 S1 P2 C1 S2 C1 S1 C1 이상현상의원인 3- 분해릴레이션이기때문 해결방안 : SUPPLY 릴레이션을 3- 분해함
해결방안과제 5 정규형정의 해결방안 : SUPPLY 릴레이션을 3- 분해함 제 5 정규형정의 릴레이션 R 에존재하는모든조인종속 (JD) 이릴레이션 R 의후보키를통해서만성립된다면릴레이션 R 은제 5 정규형또는 PJ/NF(Projection-Join Normal Form) 에속한다. 40
조인종속성을가진릴레이션의예 5NF 아님 : 조인종속이 (SK, PK, CK) 를통해서성립하는것이아니고, (SK, PK), (PK, CK), (CK, SK) 를통해조인종속이성립되기때문 SPC SK S1 S1 S2 S1 PK P2 CK C2 C1 C1 C1 프로젝션 5NF : 어떤조인종속이전혀없기때문 SP SK S1 S1 S2 PK P2 PC PK P2 CK C2 C1 C1 CS CK C2 C1 C1 SK S1 S1 S2 첫번째조인 프로젝션 조인 부당투플 SK S1 S1 S1 PK P2 CK C2 C1 C1 S2 C2 S2 C1 두번째조인
결론 : 정규화과정 비정규릴레이션 원자값이아닌도메인을분해 1NF 부분함수종속제거 2NF 이행함수종속제거 3NF 결정자가후보키가아닌함수종속 (FD) 제거 BCNF 함수종속이아닌다치종속 (MVD) 제거 4NF 후보키를통하지않은조인종속 (JD) 제거 5NF
반 ( 역 ) 정규화 (De-Normalization) Note 현실적으로모든릴레이션을반드시 5NF 에속하도록분해할필요는없음 학생주소 ( 학번, 이름, 주소, 전화번호 ) : BCNF 가아님 기본키 : 학번 FD : 전화번호 주소 학생전화 ( 학번, 이름, 전화번호 ) : 5NF 전화주소 ( 전화번호, 주소 ) : 5NF 이름, 전화번호, 주소는분리하지않고사용하는것이검색성능은더좋으므로위의 5NF 으로의분해는무의미함