금오공대 컴퓨터공학전공 강의자료

Size: px

Start display at page:

Download "금오공대 컴퓨터공학전공 강의자료"

혜정 여
5 years ago
Views:

1 데이터베이스및설계 Chap 7. 데이터종속성과정규화 오병우 컴퓨터공학과

데이터베이스구축 데이터베이스구축 DB 설계필요 : 전체 attribute 를 relation 별로 grouping 필요 (Logical) database design DDL 을가지고 conceptual schema 정의 Given some body of data suitable logical structure (what relations & what

2 데이터베이스구축 데이터베이스구축 DB 설계필요 : 전체 attribute 를 relation 별로 grouping 필요 (Logical) database design DDL 을가지고 conceptual schema 정의 Given some body of data suitable logical structure (what relations & what attributes in Relational Database) Application independent design (what, not how) Conceptual schema design Physical database design Given logical structure suitable physical structure 관계형데이터베이스인경우에만해당 Department of Computer Engineering 2

3 데이터의논리적표현 관계형데이터베이스에서는관계스킴 (relational scheme) 의설계에해당함 관계모델을이용하여어떻게실세계를정확히표현할것인가? i. attribute, entity, relationship 파악필요 ⅱ. 관련된 attribute 들을 relation 으로묶음 데이터종속성 : attribute 들간의관계성 효율적인데이터처리 데이터의일관성유지 iii. 변칙적성질의예방 데이터의중복성배제 이상 (anomaly) Department of Computer Engineering 3

example : 수강 relation 이상 (anomaly) High degree of redundancy problems 수강 학번과목번호성적학년 100 C413 A 4 100 E412 A 4 200 C123 B 3 300 C312 A 1 300 C324 C 1 300

4 example : 수강 relation 이상 (anomaly) High degree of redundancy problems 수강 학번과목번호성적학년 100 C413 A E412 A C123 B C312 A C324 C C413 A C312 A C324 A C413 B E412 C C312 B 2 Primary key: 학번, 과목번호 일부러만든잘못된예제. 학년을수강에서만가지고있다고가정 Department of Computer Engineering 4

삭제이상 (deletion anomaly) 이상 (2) 200 번학생이 'C123' 의등록을취소 3 학년이라는정보도함께삭제됨 연쇄삭제 (triggered deletion) 에의한정보의손실 (loss of information) 삽입이상 (insertion anomaly) 600 번학생이 2 학년이라는사실을삽입

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

이상의원인과해결책 : Normalization 이상의원인 상이한종류의정보를하나의릴레이션으로표현하려하기때문 Attribute 들간에존재하는여러종속관계를하나의 relation 에표현 이상의해결 Attribute 들간의종속관계를분석하여여러개의 relation 으로분해 (decomposition) 하는과정필요 정규화

6 이상의원인과해결책 : Normalization 이상의원인 상이한종류의정보를하나의릴레이션으로표현하려하기때문 Attribute 들간에존재하는여러종속관계를하나의 relation 에표현 이상의해결 Attribute 들간의종속관계를분석하여여러개의 relation 으로분해 (decomposition) 하는과정필요 정규화 (normalization) Normalization theory Allow us to recognize certain undesirable properties and show how such relations can be converted to a more desirable form Department of Computer Engineering 6

7 스키마설계와변환 스키마설계 : 데이터베이스의논리적설계 1 attribute 들과이들의제약조건 ( 종속성 ) 들을수집 2 수집된결과를명시된제약조건에따라여러개의 relation 으로분할 스키마변환 (schema transformation) 스키마변환의원리 1 정보의무손실 2 데이터의중복성감소 3 분리의원칙 Normalization procedure 연속적인 The successive reduction of a given collection of relations to some more desirable form 1NF 2NF 3NF BCNF 4NF 5NF Department of Computer Engineering 7

8 정규형 (Normal Form) Normalization 어떤일련의제약조건을만족하는 relation 정규화 (Normalization) 의원칙 정규화 = 스키마변환 (S S') 1 무손실표현 같은의미의정보유지 그러나더바람직한구조 2 데이터의중복성감소 3 분리의원칙 독립적인관계는별개의 relation 으로표현 relation 각각에대해독립적처리가가능 Department of Computer Engineering 8

9 정규형들간의포함관계 Normal Form 정규또는비정규 relation 1NF 2NF 3NF BCNF 4NF 5NF (PJ/NF) Department of Computer Engineering 9

10 함수종속 (FD) Functional dependence (or functional dependency): FD R(U): a relation R X, Y U : attribute X, Y R.X R.Y: Y is functional dependent on X (or X functionally determines Y) Each X-value in R has associated with it precisely on Y-value in R (i.e., u, v R, u[x] = v[x] u[y] = v[y]) 어떤 relation R에서, attribute X의값각각에대해 attribute Y의값이하나만연관 attribute Y 는 attribute X 에함수종속 X Y attribute X 는 Y 를 ( 함수적으로 ) 결정 X를결정자 (determinant) Y를종속자 (dependent) X, Y 는복합 attribute 일수있음 R X Y u o ㅁ v o ㅁ Department of Computer Engineering 10

11 함수종속 (2) 후보키인경우정의와일치함 relation R 에서 attribute X 가후보키면, R 의모든 attribute Y 에대해 X Y 성립 후보키 (Candidate Key) 의정의 유일성 (Uniqueness): 모두상이하고유일함 최소성 (Minimality): 꼭필요한애트리뷰트들로만구성 FD 에서는후보키만을다루는것이아님 함수종속 X Y 의경우 attribute X가반드시키 ( 유일값 ) 라는것을요건으로하지않음 즉, attribute X값들이하나이상의투플에서같을수있음 다만, X의값이같다면 Y의값도같음을의미함 Department of Computer Engineering 11

12 FD Diagram 수강 relation (Primary key: 학번, 과목번호 ) 학년 학번 과목번호 성적 { 학번, 과목번호 } 성적 학번 학년 Department of Computer Engineering 12

13 Full Functional Dependency Full functional dependency(default) partial FD R.X R.Y: Y is fully functional dependent on X not Z X such that R.Z R.Y 복합 attribute X 에대하여 X Y 가성립할때 Z 가존재하지않음 부분함수종속 (partial functional dependency) Z 가존재함 예제 ( 수강 relation) 학번 학년 { 학번, 과목번호 } 성적 ( 학년 ) 은 ( 학번 ) 에완전함수종속 그러나 { 학번, 과목번호 } 에는부분함수종속 ( 성적 ) 은 { 학번, 과목번호 } 에완전함수종속 수강학번과목번호성적학년 100 C413 A E412 A C123 B C312 A C324 C C413 A C312 A C324 A C413 B E412 C C312 B 2 Department of Computer Engineering 13

추론규칙 함수종속에대해추론규칙이성립함 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이다.

14 추론규칙 함수종속에대해추론규칙이성립함 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이다. 함수종속은데이터의의미 (data semantics) 표현 데이터베이스가현실세계를표현할때적용해야할의미적제약조건 예 : 학번 학년 의의미는 학생은하나의학년에만속한다 학번이하나인데학년이두가지값이라면현실세계를잘못표현한것이됨 Department of Computer Engineering 14

15 1NF: First Normal Form A relation: first normal form (1NF) All underlying simple domains contain atomic values only, any normalized relation is in 1NF 모든도메인이원자값 (atomic value) 만으로된 relation 예 : 수강지도 relation 수강지도 ( 학번, 지도교수, 학과, 과목번호, 성적 ) Primary key: { 학번, 과목번호 } FD : { 학번, 과목번호 } 성적학번 지도교수학번 학과지도교수 학과 성적 학번 과목번호 2NF 를위해일부러잘못만든 1NF 예제 지도교수 학과 Department of Computer Engineering 15

16 1NF 예제 1NF 설명끝 수강지도학번지도교수 학과 과목번호성적 100 P1 컴퓨터 C413 A 100 P1 컴퓨터 E412 A 200 P2 전기 C123 B 300 P3 컴퓨터 C312 A 300 P3 컴퓨터 C324 C 300 P3 컴퓨터 C413 A 400 P1 컴퓨터 C312 A 400 P1 컴퓨터 C324 A 400 P1 컴퓨터 C413 B 400 P1 컴퓨터 E412 C Department of Computer Engineering 16

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

18 Solution by Suitable Projections 1NF 이상 (anomaly) 의원인 Primary key에 partial FD( 부분함수종속 ) 된 attribute가존재 Primary key로식별되는개체와무관한 attribute가존재 두가지상이한정보가포함 1NF 이상 (anomaly) 의해결 Projection 으로 relation 을 decomposition( 분해 ) 2NF Partial FD ( 부분함수종속 ) 제거 Department of Computer Engineering 18

19 2NF: Second Normal Form A relation: second normal form (2NF) 1) 1NF 2) Every non key attributes is fully dependent on the primary key Non key attribute: any attribute that does not participate in the (primary) key 1NF 이고, 키에속하지않는 attribute 들은모두 Primary key 에 full FD ( 완전함수종속 ) A relation: 1NF, not 2NF collection of 2NF relations (suitable projections) Nonloss decomposition ( 무손실분해 ) 1NF 프로젝션 조인 2NF Original relation: recovered by taking the natural join ( no information is lost) 프로젝션하여분해된 relation들은자연조인을통해원래의 relation으로복귀가능 원래의 relation에서얻을수있는정보는분해된 relation들로부터도얻을수있음그러나, 그역은성립하지않음 ( 삽입이상의예제에서 500번학생의지도교수가 P4라는정보는원래의 relation에서표현할수없음 ) cf.) loss decomposition: original relation natural join of those projections Department of Computer Engineering 19

20 2NF 예제 예 : 수강지도 지도, 수강 relation 지도 ( 학번, 지도교수, 학과 ) Primary key : { 학번 } 수강 ( 학번, 과목번호, 성적 ) Primary key : { 학번, 과목번호 } Foreign key : { 학번 } 참조 : 지도 지도 학번 지도교수 학과 3NF 를위해일부러잘못만든 2NF 예제 수강 학번 과목번호 성적 Department of Computer Engineering 20

21 2NF 예제 2NF 설명끝 지도 학번지도교수 학과 100 P1 컴퓨터 200 P2 전기 300 P3 컴퓨터 400 P1 컴퓨터 수강 학번 과목번호성적 C413 A E412 A C123 B C312 A C324 C C413 A C312 A C324 A C413 B E412 C Department of Computer Engineering 21

22 3NF 를위한 Anomalies in 2NF 2NF( 지도 relation) 에서의이상 (anomaly) 1 삽입이상 어떤지도교수가특정학과에속한다는사실의삽입불가능 예제 : 지도교수 P4 가수학과에속한다 2 삭제이상 300 번학생의투플을삭제하면지도교수 P3 가컴퓨터공학과에속한다는정보손실 3 갱신이상 지도교수 P1 의소속이컴퓨터공학과에서전자과로변경된다면학번이 100 과 400 번인두개의투플을모두변경하여야함 Department of Computer Engineering 22

23 TD: Transitive (Functional) Dependence 2NF 이상 (anomaly) 의원인 Transitive FD (TD) 가존재 R(U): a relation A, B, C U R.A R.B, R.B R.C R.A R.C 이행적함수종속 (TD, Transitive Dependency) A B 이고 B C A C ( 즉, attribute C 는 attribute A 에이행적함수종속 ) 2NF 이상 (anomaly) 의해결 Projection 으로 relation 을 decomposition TD 제거 3NF Department of Computer Engineering 23

24 3NF: Third Normal Form A relation: third normal form(3nf) 2NF Every nonkey attribute is nontransitively dependent on the primary key The non key attributes (if any) are (ⅰ) mutually independent, (ⅱ) fully dependent on the primary key (not FD each other) 2NF 이고, 키가아닌모든 attribute 들은 Primary key 에 transitive FD( 이행적함수종속 ) 되지않음 Nonloss decomposition ( 무손실분해 ) 2NF 프로젝션 3NF 조인 원래의 relation 에서얻을수있는정보는분해된 relation 들로부터도얻을수있으나그역은성립하지않음 ( 삽입이상예제에서지도교수 P4 가수학과에속한다는정보표현 ) Department of Computer Engineering 24

25 3NF 예제 3NF 설명끝 예 : 지도 학생지도, 지도교수학과 relation 학생지도 ( 학번, 지도교수 ) Primary key : { 학번 } Foreign key : { 지도교수 } 참조 : 지도교수학과 지도교수학과 ( 지도교수, 학과 ) Primary key : { 지도교수 } 학번 지도교수 지도교수 학과 학생지도 지도교수학과 학번 지도교수 P1 P2 P3 P1 지도교수 P1 P2 P3 학과컴퓨터전기컴퓨터 Department of Computer Engineering 25

26 BCNF: Boyce/Codd Normal Form 3NF 의약점 i. 복수의후보키를가지고있고 ii. 후보키들이복합 attribute들로구성되고 iii. 후보키들이서로중첩되는경우 적용불가능 보다일반적인 Boyce/Codd Normal Form(BCNF) 을제안 Department of Computer Engineering 26

BCNF A relation: Boyce/Codd normal form (BCNF) Every determinant is a candidate key Determinant Any attribute on which some other attribute is (fully) functional dependent Relation R 의모든 determinant(

27 BCNF A relation: Boyce/Codd normal form (BCNF) Every determinant is a candidate key Determinant Any attribute on which some other attribute is (fully) functional dependent Relation R 의모든 determinant( 결정자 ) 가후보키이면 relation R 은 BCNF 에속한다. Relation R 이 BCNF 에속하면 R 은 1NF, 2NF, 3NF 에속함 강한제 3 정규형 (strong 3NF) 이라고도함 앞의예제 Relation 은 BCNF 인가? 각 Relation 의기본키가모두유일한결정자인가? YES: 수강, 학생지도, 지도교수학과 NO (3NF 도아님 ) : 수강지도, 지도 3NF 이고.. 처럼 3NF 에대한직접적인언급은없음 Department of Computer Engineering 27

28 BCNF 를위한 3NF 예제 예 (3NF) : 수강과목 relation 제약조건 각과목에대한한학생은오직한교수의강의만수강 각교수는한과목만담당 한과목은여러교수가담당할수있음 수강과목 ( 학번, 과목, 교수 ) 후보키 : { 학번, 과목 }, { 학번, 교수 } Primary key : { 학번, 과목 } 함수종속 : { 학번, 과목 } 교수교수 과목 학번 과목 교수 수강과목 학번과목 100 프로그래밍 100 자료구조 200 프로그래밍 200 자료구조 300 자료구조 300 프로그래밍 BCNF 를위해일부러잘못만든 3NF 예제 교수 P1 P2 P1 P3 P3 P4 Department of Computer Engineering 28

29 BCNF 를위한 Anomalies in 3NF 3NF( 수강과목 relation) 에서의이상 1 삽입이상 교수 P5 가자료구조를담당한다는사실의삽입은학번 ( 수강학생 ) 이있어야가능 2 삭제이상 100 번학생이자료구조를취소하여투플을삭제하면 P2 가담당교수라는정보도삭제됨 3 갱신이상 P1 이프로그래밍과목대신자료구조를담당하게되면 P1 이나타난모든투플을변경하여야함 원인 : 교수가결정자이지만후보키가아님 Department of Computer Engineering 29

30 BCNF 예제 예 (BCNF) : 수강과목 수강교수, 과목교수 수강교수 ( 학번, 교수 ) Primary key : { 학번, 교수 } Foreign key : { 교수 } 참조 : 과목교수과목교수 ( 교수, 과목 ) Primary key : { 교수 } 수강교수 학번 교수 P1 P2 P1 P3 P3 P4 과목교수 교수 P1 P2 P3 P4 과목프로그래밍자료구조자료구조프로그래밍 학번 교수 교수 과목 Department of Computer Engineering 30

31 BCNF 예제 S(S#, SNAME, STATUS, CITY) S#, SNAME: two disjoint (nonoverlapping) candidate keys Primary key: S# Alternate key: SNAME BCNF S# STATUS SNAME CITY Department of Computer Engineering 31

32 Not BCNF 예제 BCNF 설명끝 SSP(S#, SNAME, P#, QTY) (S#, P#), (SNAME, P#): two overlapping candidate keys 3NF, but not BCNF ( S#, SNAME: determinants) S# Nonkey attribute P# QTY BCNF SNAME S(S#, SNAME), SP(S#, P#, QTY) or SP(P#, SNAME, QTY) 앞의예제를고려하면 S(S#, SNAME, STATUS, CITY), SP(S#, P#, QTY) or SP(P#, SNAME, QTY) Department of Computer Engineering 32

T5 교재 (T) T1 T2 T1 T2 T3 T4 T5 비정규형 Cartesian product BCNF Primary key 에속하지않는

33 Multi-valued Fact 과목목록 (UCPT) 과목 (C) 화일구조 데이터베이스 교수 (P) P1 P2 P3 개설과목 (CPT) 과목 (C) 교수 (P) 화일구조 P1 화일구조 P1 화일구조 P2 화일구조 P2 데이터베이스 P3 데이터베이스 P3 데이터베이스 P3 교재 (T) T1 T2 T3 T4 T5 교재 (T) T1 T2 T1 T2 T3 T4 T5 비정규형 Cartesian product BCNF Primary key 에속하지않는 determinant attribute 가없음 Primary key: ( 과목, 교수, 교재 ) X Y Department of Computer Engineering 33

4NF 를위한 Anomalies in BCNF 개설과목에서의변경이상 P4 가데이터베이스를담당한다는정보삽입시 3 개의교재에대한투플을삽입해야함 Primary key 에 null 을넣을수없으므로 Cartesian product 이므로 모두 primary key 로하지않고 null 을넣는방법도있으나교재에선 Cartesian

34 4NF 를위한 Anomalies in BCNF 개설과목에서의변경이상 P4 가데이터베이스를담당한다는정보삽입시 3 개의교재에대한투플을삽입해야함 Primary key 에 null 을넣을수없으므로 Cartesian product 이므로 모두 primary key 로하지않고 null 을넣는방법도있으나교재에선 Cartesian product 방법사용 BCNF 이상의원인 즉, 과목은교수나교재의값하나를결정하는것이아니라몇개의값, 즉 multi-value(set of values) 를결정 과목 교수 교재 (or 과목 교수 교재 ) ( 화일구조 ) { P1, P2 } ( 화일구조 ) { T1, T2 } Department of Computer Engineering 34

35 MVD: Multi-valued Dependency 다치 ( 다중값 ) 종속 (MVD, Multi-Valued Dependency) Relation 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 이나, 역은성립하지않음 MVD: A generalization of the functional dependence 즉, A B 이면 A B 가성립 (MVD 는여러개, FD 는딱한개만 ) MVD 를가진 relation 의분해 (Fagin 의정리, 1977 년 ) R(A,B,C) 에서 MVD A B C 이면 R1(A,B) 와 R2(A,C) 로 nonloss decomposition ( 무손실분해 ) 가능 언어 학번언어취미 C++, PHP Java, C# 학번 애트리뷰트가적어도 3 개이상 게임, 사진 사진, 트위터 취미 Department of Computer Engineering 35

36 4NF: Fourth Normal Form A relation : fourth normal form (4NF) ⅰ) BCNF ⅱ) All MVDs in R are in fact FDs Relation R 이 BCNF 에속하고모든 MVD 가 FD 이면 R 은 4NF MVD 가없으면 4NF Relation R 에서 MVD A B 가존재할때 R 의모든 attribute 들이 A 에함수종속 (FD) 이면 R 은 4NF 즉 R 의모든 attribute X 에대해 A X 이고 A 가후보키 의미 어떤 relation R 이 4NF 이라면 MVD 가없거나, MVD A B C 가있을경우 A 에대응되는 B 와 C 의값은하나씩이어야하며 이때 A 는후보키라는것을의미한다. 언어 학번, 언어 학번 학번, 취미 취미 Department of Computer Engineering 36

37 예제 개설교과목 과목 (C) 화일구조화일구조화일구조화일구조데이터베이스데이터베이스데이터베이스 4NF 예제 교수 (P) P1 P1 P2 P2 P3 P3 P3 교재 (T) T1 T2 T1 T2 T3 T4 T5 BCNF (key 에속하지않는 determinant attribute 가없음 ) Primary key: ( 과목, 교수, 교재 ) MVD 과목 교수 교재 과목교재 과목교수과목 (C) 교재 (T) 화일구조 T1 과목 (C) 교수 (P) 화일구조 T2 화일구조 P1 데이터베이스 T3 화일구조 P2 데이터베이스 T4 데이터베이스 P3 데이터베이스 T5 4NF Department of Computer Engineering 37

38 참고 4NF 설명끝 Rissanen's work R( A, B, C ) : a relation A B, B C (or A B, B C ) R1( A, B ), R2( B, C ) : independent ( R1( A, B ), R2( A, C ) : not independent ) (A, B)(A, C) 보다 (A, B)(B, C) 로 projection 함이바람직하다. Department of Computer Engineering 38

n decomposable (n- 분해 ) Relation Nonloss decomposition A relation two projections (1NF 4NF) 4NF 까지는 2 개의 relation 으로 decomposition( 분해 ) 하면문제해결 2-decomposable relation 이라고함 three or more projections

39 n decomposable (n- 분해 ) Relation Nonloss decomposition A relation two projections (1NF 4NF) 4NF 까지는 2 개의 relation 으로 decomposition( 분해 ) 하면문제해결 2-decomposable relation 이라고함 three or more projections (4NF 5NF) 5NF 는 n 개로 decomposition 필요 A relation: n decomposable ( n > 2 ) The relation can be nonloss-decomposed into n projections but not into m projections for any m < n n 개의 projection 으로만 nonloss decomposition ( 무손실분해 ) 될수있으며 m (m<n) 개의 projection 으로는 nonloss decomposition 이불가능한 relation Department of Computer Engineering 39

40 프로젝션과조인 예제 : Relation SPC 4NF SP 모든 attribute가 primary key에속함 FD나 MVD 없음 SPC를프로젝션하여세개의 SP,PC,CS를생성 세개의 relation SP,PC,CS 를조인해서는 SPC의재생성이가능하나그어느두개의조인만으로는재생성불가능 (Spurious tuple 발생 ) 프로젝션 조인 SK S1 S1 S2 프로젝션 PK P1 P2 P1 SPC PC 첫번째조인 SK PK CK S1 S1 S2 S1 PK P1 P2 P1 SK PK CK S1 S1 S1 P1 P1 P2 C2 C1 C1 S2 P1 C2 S2 P1 C1 P1 P2 P1 P1 CK C2 C1 C1 C2 C1 C1 C1 잘못된 (spurious) 투플 원래 SPC Relation CS CK C2 C1 C1 3- decompo sable SK S1 S1 S2 두번째조인 Department of Computer Engineering 40

41 3 decomposable Relation 예제 3-decomposable relation Relation SPC 가세개의프로젝션 SP,PC,CS 의조인과동등하다는것은다음을의미 (S1,P1) SP (P1,C1) PC (S1,P1,C1) SPC (C1,S1) CS 즉다음의순환적제약조건 (3D: 3-decomposable) 을만족 (S1,P1,C2) SPC (S2,P1,C1) SPC (S1,P1,C1) SPC (S1,P2,C1) SPC SPC : 3-decomposable relation : 3D 제약조건을만족 3D 제약조건을만족하는것을 JD 라고함 Department of Computer Engineering 41

42 JD: Join Dependency 조인종속 (JD, Join Dependency) R(U) : a relation X, Y, Z U (X, Y,, Z 는 R 의 attribute 들에대한 subset) *(X, Y,, Z): R satisfies the join dependence (JD) R = (natural) join of its projections on X, Y,, Z relation R 이그의프로젝션 X, Y,, Z 의 join 과동일하면 R 은 JD*(X, Y,, Z) 만족 A generalization of FD and MVD (JD 는 MVD 의일반형 ) MVD 는 JD 의특별한경우 (2- 분해 ) R(A,B,C) 가 JD *(AB,AC) 을만족하면, 한쌍의 MVD A B C 도성립 R(A, B, C) satisfies the JD*(AB,AC) R(A, B, C) satisfies the MVDs A B C ( R(A, B, C) = R1(A, B) JOIN R2(A, C)) JD 를만족하는 n-decomposable relation 은 n 개의 projection 으로분해해야함 SPC relation 은 JD *(SP, PC, CS) 를만족 3-decomposable relation 그러므로 5NF 아님 (3 개로분해해야함 ) Department of Computer Engineering 42

43 relation 에서의갱신이상 1 삽입이상 Anomalies relation SPC 에서 (S2,P1,C1) 의삽입시 (S1,P1,C1) 의삽입필요 역은성립않음 SPC SK PK CK S1 P1 C2 S1 P2 C1 Department of Computer Engineering 43

PK CK S1 P1 C2 S1 P2 C1 S2 P1 C1 S1 P1 C1 이상의원인 : SPC 는 3- 분해

44 Anomalies relation 의갱신이상 (con t) 2 삭제이상 relation SPC 에서 (S1,P1,C1) 의삭제시다른투플중어느하나를함께삭제하여야함 (S2,P1,C1) 의삭제는이상없이가능 SPC SK PK CK S1 P1 C2 S1 P2 C1 S2 P1 C1 S1 P1 C1 이상의원인 : SPC 는 3- 분해 relation 이상의해결 : relation SPC 를 3- 분해함 Department of Computer Engineering 44

45 5NF: Fifth Normal Form PJ/NF: Projection-Join Normal Form A relation: fifth normal form (5NF) or projection-join normal form(pj/nf) Every join dependency in R is a consequence of the candidate keys of R Relation R 에존재하는모든조인종속이 R 의후보키를통해성립되면, R 은 5NF 예제 SPC : 5NF 아님 JD 를가지고있고, JD *(SP,PC,CS) 는후보키 (SK,PK,CK) 를통하지않고후보키가아닌 (SK, PK), (PK, CK), (CK, SK) 를통해서 JD 성립하므로 5NF 아님 SP,PC, CS 각각은 5NF ( no JDs) 과목 과목, 교수 과목 교수, 교재 교수 교재 교수 교수, 교재 교재 Department of Computer Engineering 45

46 조인종속이 R 의후보키를통해성립된다는의미 예제 학생 ( 학번, 이름, 학과, 학년 ) relation 의후보키가학번과이름일경우 5NF 설명끝 JD *(( 학번, 이름, 학과 ), ( 학번, 학년 )) JD *(( 학번, 이름 ), ( 학번, 학년 ), ( 이름, 학과 )) 위의 JD 는모두후보키를통해성립됨 (JD 가 2 개밖에없다면 5NF) 문제는 JD 를모두찾아내는것이어려움 분리하는것이유익한것인지분명치않음 Department of Computer Engineering 46

47 정규화과정 ( 무손실분해 ) Normalization Process 실제정규화과정은정규형의순서와다를수있음 비정규 relation Atomic value( 원자값 ) 가아닌도메인을분해 1NF Partial FD ( 부분함수종속 ) 제거 2NF TD ( 이행함수종속 ) 제거 Determinant가 candidate key가아닌 FD ( 함수종속 ) 제거 BCNF FD( 함수종속 ) 가아닌 MVD ( 다치종속 ) 제거 4NF Candidate key를통하지않은 JD ( 조인종속 ) 제거 MVD attribute 분리 JD 인경우두개이상 n 개로분리 3NF 5NF Department of Computer Engineering 47

48 실제문제의예제 일반적으로 3NF, BCNF 정도까지고려 Anomaly 에의한 inconsistency 를방지할수있으면됨 현실적으로모든 relation 을반드시 5NF 에속하도록분해할필요는없음 NADDR( NAME, STREET, CITY, STATE, ZIP) : 2NF NSZ ( NAME, STREET, ZIP ) ZCS ( ZIP, CITY, STATE) not desirable ( STREET, CITY, STATE are almost required together and ZIP dose not change very often) Department of Computer Engineering 48

49 Concluding Remarks A relation : BCNF (4NF, 5NF ) every FD (MVD, JD) is a consequence of the candidate keys of R anomalies: caused by FDs or MVDs or JDs that are not consequence of the candidate keys Normalization Relation scheme 을분석하여바람직한구조로재구축 대충정의한 relation 을잘 ~ 정리하는과정 필요한 attribute 들을단순히한개의 relation 으로만들어놓았다면중복을피하고 inconsistency 를방지할수있도록 normalization 을통해정리해야함 FD, MVD, JD 를가지고 Entity 및 relationship 추출필요 E-R diagram 을그려서설계한후에 relation 으로만드는것이좋음 Objectives of normalization process 1. to eliminate certain kinds of redundancy 2. to avoid certain update anomalies 3. to produce a good representation of the real world 4. to simply the enforcement of certain integrity constraints Department of Computer Engineering 49

50 Concluding Remarks Dependency, normalization: data semantics Relational algebra, relational calculus, data language: data value relation 의정규화는실제데이터값이아니라개념적인측면에서다루어져야함 Decomposition operator projection restriction Beyond the 5NF 6NF Optimal Normal Form Domain-key Normal Form Etc. Recomposition operator natural join union Department of Computer Engineering 50

PowerPoint Presentation

PowerPoint Presentation 데이터종속성과정규화 이장의주요내용 데이터의잘못된논리적표현으로인해발생하는이상현 상들 함수종속성 정규화 제 1 정규형, 제 2 정규형, 제 3 정규형, BCNF 제 4 정규형, 제 5 정규형 참고문헌 데이타베이스시스템, 이석호저, 정익사 (chapter 11 장 ), 2005 년 2 데이타의논리적표현 조직체가가지고있는대량의운용데이터를어떻게조직해야효율적으로관리할수있는가?