<4D F736F F F696E74202D E20B0FCB0E BCB3B0E820BECBB0EDB8AEC1F2B0FA20C3DFB0A1C0FB20C1A4B1D4C7FC>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D E20B0FCB0E BCB3B0E820BECBB0EDB8AEC1F2B0FA20C3DFB0A1C0FB20C1A4B1D4C7FC>"

서웅 필
7 years ago
Views:

1 데이터베이스 (Database) 문양세강원대학교 IT특성화대학컴퓨터과학전공

2 강의내용 관계형데이터베이스스키마설계알고리즘 릴레이션분해와정규형의부족한점 분해와종속성의보존 분해와무손실 ( 비부가적 ) 조인 널값과허상투플이야기하는문제점 다치종속성과제 4 정규형 (4NF) 조인종속성과제 5 정규형 (5NF) 포함종속성 기타종속성과정규화 Page 2

3 관계 DB 스키마설계알고리즘 좋은데이터베이스스키마설계를위해서는정규형만으로는불충분함 예제 : 두개애트리뷰트를갖는릴레이션은 BCNF 이다. 그러면, 모든릴레이션을두개 애트리뷰트로설계하면좋은설계인가? 좋은데이터베이스설계를보장하기위해서는다음의추가적인조건들이 필요함 종속성보존특성 (dependency preservation property) 무손실조인특성 (lossless l join property) Page 3

4 릴레이션분해와정규형의부족한점 (1/2) 전체릴레이션스키마 (universal relation schema) R = {A 1, A 2,..., A n } 데이터베이스의모든애트리뷰트들을포함하는릴레이션이다. 분해는전체릴레이션 R 로부터시작한다. 설계목표 I: R 을 m 개릴레이션스키마의집합인분해집합 D = {R 1, R 2,..., R m } 로분해한다. 각릴레이션스키마 R i 는 R 의애트리뷰트들의부분집합이다. 애트리뷰트보존조건 : R 의모든애트리뷰트들은적어도하나의릴레이션 R i 에나타나야 한다. Page 4

5 릴레이션분해와정규형의부족한점 (2/2) 설계목표 II: D 의각릴레이션 R i 는 BCNF 혹은 3NF 에속하도록한다. 좋은데이터베이스설계는이들정규형만으로부족하다. 예제 : 애트리뷰트가둘인릴레이션은자동적으로 BCNF 이다. 이러한애트리뷰트가둘인 릴레이션과 BCNF 가아닌릴레이션을조인하게되면가짜투플이만들어질수있다. 그림 9.5 와그림 9.6 참조 : EMP_LOCS 는 BCNF 이나 BCNF 가아닌 EMP_PROJ1 과조인시 가짜투플이생성되었음 그림 9.5(a) EMP_LOCS ENAME PLOCATIONS EMP_PROJ1 SSN PNUMBER HOURS PNAME PLOCATIONS 기본키 기본키 그림 SSN PNUMBER HOURS PNAME PLOCATIONS SSN PNUMBER HOURS PNAME PLOCATIONS ENAME * * * ProductX ProductX ProductY ProductY ProductY Bellaire Bellaire Sugarland Sugarland Sugarland Smith, John B. English, Joyce A. Smith, John B. English, Joyce A. Wong, Franklin T. Page 5

6 분해와종속성보존 (1/3) 데이터베이스설계자는 R 의애트리뷰트들에대해성립하는함수적종속 성의집합 F 를정의한다. 분해집합 D 는종속성을보존해야한다. 즉, 각릴레이션 R i 에서성립하는모든 FD 들의합집합이 F 와동등 (equivalent) 해야한다. 종속성보존은정형적으로다음과같이정의한다. R i 상으로 F 의프로젝션 (Π Ri (F)): F + 에속하는함수적종속성 X Y 들의집합이며 (X Y) R i 를만족한다. 만약 (Π R1 (F) Π R2 (F)... Π Rm (F)) + = F + 를만족하면, 분해집합 D= {R 1,R 2,...,R m } 은종속성을 보존한다고정의한다. 이런특성으로인해각릴레이션 R i 상의함수적종속성들이개별적으로성립함을보임으 로써, F 의함수적종속성들이성립함을보장할수있다 Page 6

7 분해와종속성보존 (2/3) Claim 1: 종속성들의집합 F 에대해서종속성을보존하면서각릴레이션 R i 가제 3 정규형인분해집합 D 를항상구할수있다. 제 3 정규형으로의관계합성 ( 알고리즘 10.2) 1. Find a minimal set of FDs G equivalent to F 2. For each X of an FD X A in G, Create a relation schema R i in D with the attributes {X {A 1 } {A 2 }... {A k }}, where X A 1, X A 2,, X A k are the only dependencies in G with X as left hand side; 3. Place any remaining attributes in a single relation schema to ensure the attribute preservation property. Claim 1A: 관계합성알고리즘에의해생성되는모든릴레이션스키마는 3NF 에속한다. Page 7

8 분해와종속성보존 (3/3) 문제점 : F 에대한최소덮개 (minimal cover) 를찾아야한다. 최소폐쇄를찾는효율적인알고리즘이존재하지않는다. F 에대한여러개의최소덮개가존재할수있다. 따라서, 알고리즘의결과는어떤함수적 종속성이선택되었는가에따라다르다. Page 8

9 분해와무손실 ( 비부가적 ) 조인개념 (1/2) 무손실조인의비정형적정의 : 분해집합의릴레이션들을조인했을때, 어떠한가짜투플도생성되지않음을보장하는특 징이다. 무손실조인의정형적정의 : 함수적종속성의집합 F 를만족하는모든릴레이션상태 r 에대해다음의성질이만족되면, R 의분해집합 D = {R 1, R 2,.., R m } 는 F 에대해서무손실조인특성을갖는다. ( 는 D 에포함 된모든릴레이션의자연조인이다.) (Π R1 (r),..., Π Rm (r) ) = r Page 9

10 분해와무손실 ( 비부가적 ) 조인개념 (2/2) 분해집합이위의성질을만족하면, 프로젝션과조인연산후에가짜투플이추가되 지않음이보장된다. 분해된릴레이션들은실제로는기본릴레이션으로저장하기때문에, 조인을수반 한질의가의미있는결과를생성하기위해서는위와같은조건이필요하다. 주어진분해집합 D 가함수적종속성집합 F 에대해서무손실조인특성을가지는 것을검사하는알고리즘이존재한다. Page 10

11 [ 그림 10.1] n 차분해에대한무손실조인검사 (1/2) (a) 경우 1: EMP_PROJ 를 EMP_PROJ1 과 EMP_LOCS 로분해하면검사를통과하지 못함 R = {SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS} D = {R1, R2} R1 = EMP_LOCS = {ENAME, PLOCATION} R2 = EMP_PROJ1 = {SSN, PNUMBER, HOURS, PNAME, PLOCATION} F = {SSN ENAME; PNUMBER {PNAME, PLOCATION}; {SSN, PNUMBER} HOURS} SSN ENAME PNUMBER PNAME PLOCATION HOURS R 1 b 11 a 2 b 13 b 14 a 5 b 16 R 2 a 1 b 22 a 3 a 4 a 5 a 6 ( 함수적종속성들을적용한후에행렬에어떤변화도생기지않음 ) (b) 무손실조인특성이있는 EMP_PROJPROJ 의분해 EMP PROJECT WORKS_ON SSN ENAME PNUMBER PNAME PLOCATION SSN PNUMBER HOURS Page 11

12 [ 그림 10.1] n 차분해에대한무손실조인검사 (2/2) (c) 경우 2: EMP_PROJ 를 EMP, PROJECT, WORKS_ON 으로분해하면검사를통과함 R = {SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS} D = {R1, R2, R3} R1 = EMP = {SSN, ENAME} R2 = PROJ = {PNUMBER, PNAME, PLOCATION} R3 = WORKS_ON ON = {SSN, PNUMBER, HOURS} F = {SSN ENAME; PNUMBER {PNAME, PLOCATION}; {SSN, PNUMBER} HOURS} SSN ENAME PNUMBER PNAME PLOCATION HOURS R a 1 a 2 b 13 b 14 b 15 b 16 R 1 R 2 b 21 b 22 a 3 a 4 a 5 a 26 a 1 b 32 a 3 b 34 b 35 a 6 ( 알고리즘을시작할때행렬 S 의초기내용 ) SSN ENAME PNUMBER PNAME PLOCATION HOURS R 1 a 1 a 2 b 13 b 14 b 15 b 16 b 21 b 22 a 3 a 4 a 5 a 26 R 2 a 1 b 32 a 3 b 34 b 35 a 6 ( 처음두개의함수적종속성을적용한후의행렬 S의내용. 마지막항의모든애트리뷰트가심볼 a 를가지므로알고리즘을종료한다.) Page 12

13 무손실조인특성을갖는 BCNF 릴레이션들로분해 (1/3) 릴레이션 R 을분해한릴레이션들이 BCNF 정규형에속하며, 분해집합이 함수적종속성의집합 F 에대해무손실조인특성을갖게하는알고리즘이 존재한다 (Algorithm 10.3) 1. Set D {R} 2. While there is a relation schema Q in D that is not in BCNF do { }; Choose one Q in D that is not in BCNF; Find a FD X Y in Q that violates BCNF; Replace Q in D by two relation schemas (Q-Y) and (X Y); Page 13

14 무손실조인특성을갖는 BCNF 릴레이션들로분해 (2/3) 위알고리즘은다음두가지무손실조인분해특성에기반한다. (1) R 의분해집합 D = {R 1, R 2 } 가함수적종속성의집합 F 에대해무손실조인특성을가지 기위한필요충분조건은다음의두가지중반드시하나를만족하는것이다. 함수적종속성 ((R -R + 1 R 2 ) (R 1 R 2 )) 가 F 에속한다. 함수적종속성 ((R 1 R 2 ) (R 2 -R 1 )) 가 F + 에속한다. (2) R 의분해집합 D = {R 1 1, R 2 2,,...,, R m m} 이함수적종속성집합 F 에대해무손실조인특성을 가지고, R i 의분해집합 D 1 = {Q 1, Q 2,..., Q m } 가 F 의 R i 상에의프로젝션에대해무손실 조인특성을가진다면, R 의분해집합 D 2 = {R 1, R 2,.., R i 1, Q 1, Q 2,.., Q k, R i+1,.., R m } 또한 F 에대해무손실조인특성을가진다. Page 14

15 무손실조인특성을갖는 BCNF 릴레이션들로분해 (2/3) 분해집합이종속성을보존하며 BCNF 정규형에속하게하는알고리즘은존재하지 않는다. 다음의수정된합성알고리즘은 1) 무손실조인특성과 2) 종속성보존특성을만족 하며, 3) 제 3 정규형릴레이션으로분해하는것을보장한다. ( 주의 : BCNF 정규형으 로의분해는보장못함 ) 많은제 3 정규형릴레이션들은 BCNF 정규형에도속한다. Page 15

16 무손실조긴과종속성을보장하는분해알고리즘 무손실조인과종속성보존을보장하는제 3 정규형릴레이션으로분해하는 알고리즘 1. Find a minimal cover for F. 2. For each X of an FD X Y in G Create a relation schema R i in D with the attributes {X }{A 1 } {A 2 }... {A k }}, where X A 1, X A 2,, X A k are the only dependencies in G with X as left hand side; 3. If none of the relations schemas in D contains a key of R, then create one more relation schema that contains attributes that form a key for R. Page 16

17 널값이야기하는문제점 (1/4) 널값 (Null Values) 널값이조인애트리뷰트에존재할때문제가발생한다. 널값이존재하는경우질의를명기할때정규조인 (regular join) 과 OUTER 조인의결과 사이의차이가중요해진다. 어떤질의는정규조인을필요로하고어떤질의는 OUTER 조인을필요로한다. Page 17

18 널값이야기하는문제점 (2/4) [ 그림 10.2(a)] 조인애트리뷰트에널값이존재하는데이터베이스 EMPLOYEE ENAME SSN BDATE ADDRESS DNUM Smith, John B JAN Fondren, Houston, TX 5 Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A DEC JUL JUN SEP JUL Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX Jabbar, Ahmad V. Borg, James E. Berger, Anders C. Benitez, Carlos M MAR NOV APR JAN Dallas, Houston, TX 731 Stone, Houston, TX 6530 Braes, Bellaire, TX 7654 Beech, Houston, TX 4 1 null null DEPARTMENT DNAME DNUMBER DMGRSSN Research Administration Headquarters Page 18

19 널값이야기하는문제점 (3/4) [ 그림 10.2(b)] EMPLOYEE 와 DEPARTMENT 에자연조인을적용한결과 두개투플이사라짐 ENAME SSN BDATE ADDRESS DNUM DNAME DMGRSSN Smith, John B JAN Fondren, Houston, TX 5 Research Wong, Franklin T DEC Voss, Houston, TX 5 Research Zelaya, Alicia J JUL Castle, Spring, TX 4 Administration Wallace, Jennifer S JUN Berry. Bellaire, TX 4 Administration Narayan, Ramesh K SEP Fire Oak, Humble, TX 5 Research English, Joyce A JUL Rice, Houston, TX 5 Research Jabbar, Ahmad V MAR Dallas, Houston, TX 4 Administration Borg, James E NOV Stone, Houston, TX 1 Headquarters Page 19

20 널값이야기하는문제점 (4/4) [ 그림 10.2(c)] EMPLOYEE 를 DEPARTMENT 와외부조인한결과 투플이사라지지않음 ( 널값을갖는가상적인부서가생김 ) ENAME SSN BDATE ADDRESS DNUM DNAME DMGRSSN Smith, John B JAN Fondren, Houston, TX 5 Research Wong, Franklin T DEC Voss, Houston, TX 5 Research Zelaya, Alicia J JUL Castle, Spring, TX 4 Administration Wallace, Jennifer S JUN Berry. Bellaire, TX 4 Administration Narayan, Ramesh K SEP Fire Oak, Humble, TX 5 Research English, Joyce A JUL Rice, Houston, TX 5 Research Jabbar, Ahmad V MAR Dallas, Houston, TX 4 Administration Borg, James E NOV Stone, Houston, TX 1 Headquarters Berger, Anders C APR Braes, Bellaire, TX null null null Benitez, Carlos M JAN Beech, Houston, TX null null null Page 20

21 허상투플이야기하는문제점 (1/3) 허상투플 (Dangling Tuples) 정규화과정에서릴레이션을너무분해하면허상투플의문제가발생함 분해된릴레이션을조인하면사라지는투플을허상투플이라고함 Page 21

22 허상투플이야기하는문제점 (2/3) [ 그림 10.3(a)] EMPLOYEE 에서 DNUMBER 애트리뷰트를제외한모든애 트리뷰트를포함하는릴레이션 EMPLOYEE_1 EMPLOYEE_1 ENAME SSN BDATE ADDRESS Smith, John B. Wong, Franklin T. Zelaya, Alicia J JAN DEC JUL Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A JUN SEP JUL Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX Jabbar, Ahmad V. Borg, James E. Berger, Anders C. Benitez, Carlos M MAR NOV APR JAN Dallas, Houston, TX 731 Stone, Houston, TX 6530 Braes, Bellaire, TX 7654 Beech, Houston, TX Page 22

23 허상투플이야기하는문제점 (3/3) [ 그림 10.3(b)] 널값이존재하는 DNUMBER 애트리뷰트를포함하는 EMPLOYEE_2 에는문제가없음 [ 그림 10.3(c)] DNUMBER 에널값을갖는투플을포함하지않는 EMPLOYEE_3 를만들면, 조인시투플이사라짐 (b) EMPLOYEE_2 SSN DNUM null (c) EMPLOYEE_3 SSN DNUM null Page 23

24 강의내용 관계형데이터베이스스키마설계알고리즘 다치종속성과제 4 정규형 (4NF) 다치종속성의정형적정의 함수적종속성및다치종속성의추론규칙 제 4 정규형 (4NF) 제 4 정규형릴레이션으로의무손실조인분해 조인종속성과제 5 정규형 (5NF) 포함종속성 기타종속성과정규화 Page 24

25 다치종속성과제4정규형 함수적종속성은하나의공통된형태의제약조건을명기하기위해서사용 된다. 함수적종속성만에의해서명기될수없는다른형태의제약조건들이존 재한다. 추가적인종속성에는다치종속성 (multi valued dependency) 이있으며, 이에기반한정규형이제 4 정규형 (4NF) 이다 Page 25

26 다치종속성의정형적정의 (1/3) 정형적정의 릴레이션스키마 R 에대해, X 와 Y 는 R 의애트리뷰트들의부분집합이다. 그리고, Z = R (X Y) ( 남은애트리뷰트들 ) 이다. 릴레이션스키마 R 에서성립하는다치종속성 X Y 는 R 의임의의인스턴스 r(r) 에대해, 만약 t 1 [X] = t 2 [Y] 를만족하는 r(r) 의두투플 t 1, t 2 가존재한다면, 다음의성질을만족하는 두개의투플 t 3 와 t 4 도반드시존재해야한다 : t 3 [X] = t 4 [X] = t 1 [X] = t 2 [X] t 3 [Y] = t 1 [Y] 이고 t 4 [Y] = t 2 [Y] t 3 [Z] = t 2 [Z] 이고 t 4 [Z] = t 1 [Z] MVD 제약조건은 Z 의값에관계없이 X 의값이 Y 의값들의집합을결정한 다라는것을암시한다. MVD의특성 : X Y가성립하면, X Z도성립한다. Page 26

27 다치종속성의정형적정의 (2/3) 애트리뷰트들의집합 X 의값이애트리뷰트들의집합 Y 의값을결정한다 면, X 는 Y 를다중결정한다 (multidetermine) 라고한다. MVD X Y가 (a) Y X 혹은 (b) (X Y) = R이면단순다치종속성 (trivial MVD) 이라부른다. 단순다치종속성은다치종속성의정의에따라항상성립한다. 주어진함수적종속성과다치종속성의집합 F 에대해추가적인함수적종 속성과다치종속성을추론할수있다. Page 27

28 다치종속성의정형적정의 (3/3) 제 4 정규형 (4NF) (a) 두다치종속성 ENAME PNAME과 ENAME DNAME을가진EMP 릴레이션 (b) (c) EMP 를제 4 정규형인두개의릴레이션으로분해 다치종속성을갖지않으며제 4 정규형인 SUPPLY 릴레이션 (a) EMP ENAME PNAME Smith X Smith Y Smith X Smith Y DNAME EMP_PROJECTS EMP_DEPENDENTS John Anna Anna John (b) ENAME PNAME ENAME DNAME Smith X Smith John Smith Y Smith Anna (c) SUPPLY SNAME PARTNAME PROJNAME Smith Smith Adamsky Walton Adamsky Adamsky Smith Bolt Nut Bolt Nut Nail Bolt Bolt ProjX ProjY ProjY ProjZ ProjX ProjX ProjY Page 28

29 FD와 MVD의추론규칙 추론규칙들의집합 IR1. (FD 의재귀성규칙 ): X Y 이면, X Y 이다 IR2. (FD 의부가성규칙 ): {X Y} = XZ YZ IR3. (FD 의이행성규칙 ): {X Y, Y Z} = X Z IR4. (MVD 의보완성규칙 ): {X >> Y} = {X >> (R-(X Y))} IR5. (MVD 의부가성규칙 ): X >> Y 이고 W Z 이면, WX >> YZ 이다 IR6. (MVD 의이행성규칙 ): {X >> Y, Y >> Z} = X >> (Z-Y) IR7. (FD 에서 MVD 로의모사규칙 ): {X Y} = X >> Y IR8. (FD 와 MVD 의합동규칙 ): X >> Y 이고, (a)w Y가공집합, (b) W Z, (c) Y Z인 W가존재하면, X Z이다 주의 규칙 IR7 에의해, 모든 FD 는 MVD 이다. 규칙 IR1 에서 IR8 를적용하면함수적종속성들의집합에대한폐쇄 F+ 를유도할수있다. Page 29

30 제4정규형 (4NF) 제 4 정규형의특성 3NF 와 BCNF 는다치종속성을다루지않는다. 비단순다치종속성을가지는릴레이션스키마는좋은디자인이아닐수있다. 제 4 정규형은위와같은문제를다루며, BCNF 정규형이된다. ( 제 4 정규형에속하는모든 릴레이션은 BCNF 정규형에속한다 ) 제 4 정규형의정형적정의 종속성들의집합 F 에대한 F + 의모든비단순다치종속성 X >> Y 에대하여, X 가 R 의수퍼 키이면릴레이션스키마 R 은 F 에대한제 4 정규형이다. Page 30

31 4NF 릴레이션으로의무손실조인분해 (1/2)_ 모든 MVD 는 FD 이므로, 제 4 정규형은 BCNF 를포함한다. F 의모든종속성이함수적종속성이면, 4NF 의정의는자동적으로 BCNF 정의가된다. 릴레이션 R 상의종속성의집합 F 에대해 R 을제 4 정규형릴레이션으로 무손실조인분해하는알고리즘이존재한다. 특성 LJ1 : R 의분해집합 D = {R 1, R 2 } 가종속성의집합 F 에대해무손실 조인특성을가질필요충분조건은다음의둘중하나를만족하는것이다 : (a) 종속성 ((R 1 R 2 ) >> (R 1 -R 2 )) 가 F + 에속한다. (b) 종속성 ((R >> -R + 1 R 2 ) (R 2 R 1 )) 가 F 에속한다. Page 31

32 4NF 릴레이션으로의무손실조인분해 (2/2)_ 4NF 릴레이션으로의분해알고리즘 1. Set D {R} 2. While there is a relation schema Q in D that is not in 4NF do { }; Choose one Q in D that is not in 4NF; Find a nontrivial MVD X Y in Q that violates 4NF; Replace Q in D by two relation schemas (Q-Y) and (X Y); Page 32

33 [ 그림 10.5] 4NF 의이점 (a) 여러투플을추가한 EMP 릴레이션 (Brown) (b) EMP 를 EMP_PROJECTSPROJECTS 와 EMP_DEPENDENTS 로분해 (a) EMP ENAME PNAME Smith Smith Smith Smith Brown Brown Brown Brown Brown Brown Brown Brown Brown Brown Brown Brown X Y X Y W X Y Z W X Y Z W X Y Z DNAME John Anna Anna John Jim Jim Jim Jim Joan Joan Joan Joan Bob Bob Bob Bob (b) EMP_PROJECTSPROJECTS ENAME Smith Smith Brown Brown Brown Brown ENAME PNAME X Y W X Y Z EMP_DEPENDENTS Smith Smith Brown Brown Brown DNAME Anna John Jim Joan Bob Page 33

34 강의내용 관계형데이터베이스스키마설계알고리즘 다치종속성과제 4 정규형 (4NF) 조인종속성과제 5 정규형 (5NF) 포함종속성 기타종속성과정규화 Page 34

35 조인종속성과제5정규형 (5NF) 조인종속성 R 에지정된조인종속성은 JD(R 1, R 2,, R n ) 으로표기하며, R 의상태 r 에대하여 RR 의모든 합법적상태 r 이 R 1, R 2,, R n 으로의무손실조인분해를가져야한다 는점이다. 다치종속성은 n 이 2 인특별한경우이다. R i = R 이면, JD(R 1, R 2,, R n ) 를단순다치종속성이라부른다. 제 5 정규형 (5NF) R 이함수적종속성, 다치종속성, 그리고조인종속성들의집합인 F 에대해모든비단순조 인종속성 FD(R 1, R 2,, R n ) 이 F + 에속하고, R i 가 R 의수퍼키라면, R 은제 5 정규형에속한다. 프로젝트 조인정규형 (Project Join NF: PJNF) 이라고도한다. 로젝인정규형 ( j J J ) 이라한다 조인종속성을발견하는것은매우어려운일로, 실제로제 5 정규형은거의쓰이지않는다. Page 35

36 포함종속성 포함종속성은릴레이션들사이의제한조건을나타낸다. 정형적으로 : 릴레이션 R 의애트리뷰트집합 X 와릴레이션 S 의애트리뷰트집합 Y 사이의포함 종속성 RX R.X < SY S.Y 는 R 의릴레이션상태 r 과 S 의릴레이션상태 s 에대해다음과같 은조건을만족해야한다. (Π X ((R)) (r(r)) Π Y ((S)) (s(s)) 포함종속성에대한세가지추론규칙 : IDIR1( 재귀성규칙 ): R.X < R.X IDIR2( 애트리뷰트대응규칙 ): X={A 1, A 2,, A n } 이고 Y={B 1, B 2,, B n } 일때, R.X < S.Y 이고 A i 가 B i 에대응한다면 R.A i < S. B i 이다. IDIR3( 이행성규칙 ): R.X < S.Y 이고 S.Y < T.Z 이면, R.X < T.Z 이다. Page 36

37 강의내용 관계형데이터베이스스키마설계알고리즘 다치종속성과제 4 정규형 (4NF) 조인종속성과제 5 정규형 (5NF) 포함종속성 기타종속성과정규화 템플리트종속성 도메인 키정규형 (DKNF) Page 37

38 템플리트종속성 (1/3) 아무리많은종속성을개발하더라도, 이들로표현할수없는특별한제약 조건이나올수있다. 템플리트종속성 : 각제약조건과함수적종속성을템플리트혹은예제를 사용하여지정하는방법이다. 템플리트의종류 : 투플 생성템플리트, 제약조건 생성템플리트 템플리트는많은수의가상투플 (hypothesis tuple) 로구성되며, 템플리트 의나머지부분은템플리트결론 (templete conclusion) 이라한다. 투플 생성템플리트결론 : 가상투플에있다면릴레이션에반드시나타나야하는 투플들의집합 제약조건 생성템플리트결론 : 가상투플들에대해서반드시지켜져야하는조건 Page 38

39 템플리트종속성 (2/3) [ 그림 10.6] 일반적형태의종속성에대한템플리트 (a) 함수적종속성 X Y 에대한템플리트 (b) 다치종속성 X >> Y 에대한템플리트 (c) 포함종속성 R.X < S.Y 에대한템플리트 (a) R={A, B, C, D} Hypothesisa1 b1 c1 d1 X={A, B} Conclusion c1=c2 and d1=d2 a1 b1 c2 d2 Y={C {C,D} (b) R={A, B, C, D} Hypothesisa1 b1 c1 d1 X={A, B} a1 b1 c2 d2 Y={C} Conclusion a1 b1 c2 d1 a1 b1 c1 d2 ( c) R={A {A, B, C, D} S={E, F, G} X={C,D} Hypothesisa1 b1 c1 d1 Y={E,F} Conclusion c1 d1 g Page 39

40 템플리트종속성 (3/3) [ 그림 10.7] 고용자월급이직속상급자월급보다많을수없다는 제약조건에대한템플리트 EMPLOYEE = {NAME, SSN,, SALARY, A SUPERVISORSSN SSN } a b c d Hypothesis e d f g Conclusion c < f Page 40

41 도메인-키정규형 (DKNF) DKNF: Domain Key Normalization Form 도메인 키정규형의아이디어는가능한종류의종속성과제약조건을적어 도이론적으로는모두고려하는 궁극적정규형 을명기하는것이다. DKNF 에속하는릴레이션은모든제약조건과종속성들을단지도메인제 약조건과키제약조건만으로나타낼수있어야한다. DKNF 릴레이션내에복잡한제약조건을포함시키는것은어렵기때문에, 실제적인유용성은매우제약적이다. Page 41

42 요약 관계형데이터베이스스키마설계알고리즘에서문제점들 릴레이션분해와정규형의부족한점 종속성보존과무손실 ( 비부가적 ) 조인 널값과허상투플이야기하는문제점 다치종속성의정의와제 4 정규형 조인종속성의정의와제 5 정규형 포함종속성 기타종속성과정규형 템플리트종속성 도메인 키정규형 Page 42

Microsoft PowerPoint - 13(FD1) [호환 모드]

Microsoft PowerPoint - 13(FD1) [호환 모드] 제 13 장 관계데이타베이스의함수적종속성과정규화기본이론 목차 13.1 릴레이션스키마를설계하는몇가지개략적인지침 13. 함수적종속성 (functional dependencies, FDs) 13.3 기본키를기반으로한정규형 13.4 제 정규형과제 3 정규형의일반적인정의 13.5 BCNF (Boyce-Codd Normal Form) 13.6 다치종속성과제4정규형 13.7