제 10 장 관계 데이타베이스 설계 알고리즘과 추가적인 정규형 제 10 장 관계 데이타베이스 설계 알고리즘과 추가적인 정규형 Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe Copyright© 2004 황규영 홍의경 음두헌 박영철 김진호 조완섭

Fundamentals of Database Systems 목 차 10.1 관계형 데이타베이스 스키마 설계 알고리즘 10.1.1 릴레이션 분해와 정규형의 부족한 점 10.1.2 분해와 종속성 보존 10.1.3 분해와 무손실(비부가적) 조인 10.1.4 널 값과 허상 투플이 야기하는 문제점 10.2 다치 종속성과 제4정규형 10.2.1 다치 종속성의 정형적 정의 10.2.2 함수적 종속성 및 다치 종속성의 추론 규칙 10.2.3 제4정규형 (4NF) 10.2.4 제4정규형 릴레이션으로의 무손실 조인 분해 10.3 조인 종속성 과 제5정규형 10.4 포함 종속성 10.5 기타 종속성과 정규형 10.5.1 템플리트 종속성 10.5.2 도메인-키 정규형 Ch10 Fundamentals of Database Systems

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

Fundamentals of Database Systems 10.1.1 릴레이션 분해와 정규형의 부족한 점 전체 릴레이션 스키마(universal relation schema) R = {A1, A2, ..., An} 데이타베이스의 모든 애트리뷰트들을 포함하는 릴레이션이다. 분해는 전체 릴레이션 R로부터 시작한다. 설계목표 I: R을 m 개의 릴레이션 스키마의 집합인 분해집합 D = {R1, R2, ..., Rm}로 분해한다. 각 릴레이션 스키마 Ri는 R의 애트리뷰트들의 부분집합이다. 애트리뷰트 보존 조건: R의 모든 애트리뷰트들은 적어도 하나의 릴레이션 Ri에 나타나야 한다. 설계목표 II: D의 각 릴레이션 Ri는 BCNF 혹은 3NF에 속하도록 한다.  좋은 데이타베이스 설계는 이들 정규형만으로 부족하다. 예제: 애트리뷰트가 둘 뿐인 릴레이션은 자동적으로 BCNF에 속하게 된다. 이러한 애트리뷰트가 둘인 릴레이션과 BCNF가 아닌 릴레이션과 조인하게 되면 가짜 투플이 만들어질 수 있다. Ch10 Fundamentals of Database Systems

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

Fundamentals of Database Systems Claim 1: 종속성들의 집합 F에 대해서 종속성을 보존하면서 각 릴레이션 Ri가 제 3 정규형인 한 분해집합 D를 항상 구할 수 있다. 관계 합성(relational synthesis) 알고리즘 (알고리즘 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 Ri in D with the attributes {X∪}{A1}∪{A2}∪ ... ∪{Ak}}, where X→A1, X→A2, …, X→Ak 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에 속한다. 문제점: F에 대한 최소 폐쇄(minimal cover)를 찾아야 한다. 최소 폐쇄를 찾는 효율적인 알고리즘이 존재하지 않는다. F에 대한 여러 개의 최소 폐쇄가 존재할 수 있다. 따라서, 알고리즘의 결과는 어떤 함수적 종속성이 선택되었는가에 따라 다르다. Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.1.3 분해와 무손실 (비부가적) 조인 무손실 조인의 비정형적 정의: 분해집합의 릴레이션들을 조인했을 때 어떠한 가짜 투플도 생성되지 않음을 보장하는 특징이다. 무손실 조인의 정형적 정의: 함수적 종속성의 집합 F를 만족하는 모든 릴레이션 상태 r에 대해 다음의 성질이 만족되면, R의 분해집합 D = {R1, R2, .., Rm}는 F에 대해서 무손실 조인 특성을 갖는다. (*는 D에 포함된 모든 릴레이션의 자연조인이다.) *(ΠR1(r) , ..., ΠRm (r) ) = r 분해집합이 위의 성질을 만족하면, 프로젝션과 조인 연산 후에 가짜 투플이 추가되지 않음이 보장된다. 분해된 릴레이션들은 실제로는 기본 릴레이션으로 저장하기 때문에, 조인을 수반한 질의가 의미있는 결과를 생성하기 위해서는 위와 같은 조건이 필요하다. 주어진 분해집합 D가 함수적 종속성 집합 F에 대해서 무손실 조인 특성을 가지는 것을 검사하는 알고리즘이 존재한다(알고리즘 10.2). Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems SKIP 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} b11 a2 b13 b14 a5 b16 a1 b22 a3 a4 a5 a6 SSN ENAME PNUMBER PNAME PLOCATION HOURS R1 R2 (함수적 종속성들을 적용한 후에 행렬에 어떤 변화도 생기지 않음) SSN ENAME EMP PNUMBER PNAME PROJECT PLOCATION WORKS_ON HOURS (a) (b) [그림 10.1] 무손실 조인 검사 알고리즘 (a) EMP_PROJ를 EMP_PROJ1과 EMP_LOCS로 분해한 결과가 무손실조인 특성을 갖는지 검사하기 위하여 알고리즘을 적용함 (b) EMP_PROJ의 또 다른 분해집합 Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems SKIP (c) R = {SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS} D = {R1, R2, R3} R1 = EMP = {SSN, ENAME} R2 = PROJ = {PNUMBER, PNAME, PLOCATION} R3 = WORKS_ON = {SSN, PNUMBER, HOURS} F = {SSN ® ENAME; PNUMBER ® {PNAME, PLOCATION}; {SSN, PNUMBER} ® HOURS} SSN ENAME PNUMBER PNAME PLOCATION HOURS a1 a2 b13 b14 b15 b16 b21 b22 a3 a4 a5 a26 a1 b32 a3 b34 b35 a6 R1 R2 (알고리즘을 시작할 때 행렬 S의 초기 내용) SSN ENAME PNUMBER PNAME PLOCATION HOURS a1 a2 b13 b14 b15 b16 b21 b22 a3 a4 a5 a26 a1 b32 a3 b34 b35 a6 R1 R2 (처음 두개의 함수적 종속성을 적용한 후의 행렬 S의 내용. 마지막 항의 모든 애트리뷰트가 심볼 “a”를 가지므로 알고리즘을 종료한다.) [그림 10.1] 무손실 조인 검사 알고리즘 (cont.) (c) 그림 10.1(b)의 분해집합이 무손실 조인 특성을 갖는지 검사하기 위하여 알고리즘을 적용함 Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.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); }; Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 위 알고리즘은 다음 두 가지 무손실 조인 분해 특성에 기반한다: (1) R의 분해집합 D = {R1, R2}가 함수적 종속성의 집합 F에 대해 무손실 조인 특성을 가지기 위한 필요충분조건은 다음의 두 가지 중 반드시 하나를 만족하는 것이다. 함수적 종속성 ((R1∩R2) → (R1－R2))가 F+에 속한다. 함수적 종속성 ((R1∩R2) → (R2－R1))가 F+에 속한다. (2) R의 분해집합 D = {R1, R2,..., Rm}이 함수적 종속성 집합 F에 대해 무손실 조인 특성을 가지고, Ri의 분해집합 D1 = {Q1, Q2,..., Qm}가 F의 Ri 상에의 프로젝션에 대해 무손실 조인 특성을 가진다면, R의 분해집합 D2 = {R1, R2, .., Ri-1, Q1, Q2, .., Qk, Ri+1, .., Rm} 또한 F에 대해 무손실 조인 특성을 가진다. 분해집합이 종속성을 보존하며 BCNF 정규형에 속하게 하는 알고리즘은 존재하지 않는다. 다음의 수정된 합성 알고리즘은 1) 무손실 조인 특성과 2) 종속성 보존 특성을 만족하며, 3) 제 3 정규형 릴레이션으로 분해하는 것을 보장한다. (주의: BCNF 정규형으로의 분해는 보장 못함) 많은 제 3 정규형 릴레이션들은 BCNF 정규형에도 속한다. Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 무손실 조인과 종속성 보존을 보장하는 제 3 정규형 릴레이션으로 분해 Algorithm 1. Find a minimal cover for F. 2. For each X of an FD X→Y in G create a relation schema Ri in D with the attributes {X∪}{A1}∪{A2}∪ ... ∪{Ak}}, where X→A1, X→A2, …, X→Ak 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. Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.1.4 널값과 허상 투플이 야기하는 문제점 널값(null values): 널값이 조인 애트리뷰트에 존재할 때 문제가 발생한다. 널 값이 존재하는 경우 질의를 명기할 때 정규 조인(regular join)과 OUTER 조인의 결과 사이의 차이가 중요해진다. 어떤 질의는 정규 조인을 필요로 하고 어떤 질의는 OUTER 조인을 필요로 한다. 그림 10.2 참고 (the next slides) Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems EMPLOYEE ENAME SSN BDATE ADDRESS DNUM Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Borg, James E. Berger, Anders C. Benitez, Carlos M. 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 999775555 888664444 09-JAN-55 08-DEC-45 19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27 26-APR-55 09-JAN-53 731 Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 731 Stone, Houston, TX 6530 Braes, Bellaire, TX 7654 Beech, Houston, TX 5 4 1 null DEPARTMENT DNAME DNUMBER DMGRSSN Research Administration Headquarters 5 4 1 333445555 987654321 888665555 [그림 10.2] 널값 조인의 문제점 (a) 조인 애트리뷰트에 널값이 존재하는 데이타베이스 Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems ENAME SSN BDATE ADDRESS DNUM DNAME DMGRSSN Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Borg, James E. 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 09-JAN-55 08-DEC-45 19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27 731 Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 731 Stone, Houston, TX 5 4 1 Research Administration Headquarters 333445555 987654321 888665555 [그림 10.2] 널값 조인의 문제점 (cont.) (b) EMPLOYEE와 DEPARTMENT 릴레이션에 자연조인 연산을 적용한 결과 (두 개 tuple이 사라짐) Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems (c) ENAME SSN BDATE ADDRESS DNUM DNAME DMGRSSN Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Borg, James E. Berger, Anders C. Benitez, Carlos M. 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 999775555 888664444 09-JAN-55 08-DEC-45 19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27 26-APR-55 09-JAN-53 731 Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 731 Stone, Houston, TX 6530 Braes, Bellaire, TX 7654 Beech, Houston, TX 5 4 1 null Research Administration Headquarters null 333445555 987654321 888665555 null [그림 10.2] 널값 조인의 문제점 (cont.) (c) EMPLOYEE 릴레이션을 DEPARTMENT 릴레이션과 외부조인한 결과 Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.1.4 널값과 허상 투플이 야기하는 문제점 허상 투플(dangling tuples): 정규화 과정에서 릴레이션을 너무 분해하면 허상 투플의 문제가 발생함 분해된 릴레이션을 조인하면 사라지는 투플을 허상투플이라고 함 그림 10.3 참고 (the next slides) Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems (a) EMPLOYEE(그림 10.2(a))가 EMPLOYEE_1과 EMPLOYEE_2로 분해되었다 하자 EMPLOYEE_1 ENAME SSN BDATE ADDRESS Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Borg, James E. Berger, Anders C. Benitez, Carlos M. 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 999775555 888664444 09-JAN-55 08-DEC-45 19-JUL-58 20-JUN-31 15-SEP-52 31-JUL-62 29-MAR-59 10-NOV-27 26-APR-55 09-JAN-53 731 Fondren, Houston, TX 638 Voss, Houston, TX 3321 Castle, Spring, TX 291 Berry. Bellaire, TX 975 Fire Oak, Humble, TX 5631 Rice, Houston, TX 980 Dallas, Houston, TX 731 Stone, Houston, TX 6530 Braes, Bellaire, TX 7654 Beech, Houston, TX [그림 10.3] ‘허상 투플’의 문제점 (a) EMPLOYEE 릴레이션에서 DNUMBER 애트리뷰트를 제외한 모든 애트리뷰트를 포함하는 릴레이션 EMPLOYEE_1 Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems (c) EMPLOYEE_2 SSN DNUM EMPLOYEE_3 SSN DNUM 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 999775555 888664444 5 4 1 null 123456789 333445555 999887777 987654321 666884444 453453453 987987987 888665555 5 4 1 [그림 10.3] ‘허상 투플’의 문제점 (cont.) (b) 널값이 존재하는 DNUMBER 애트리뷰트를 포함하는 릴레이션 EMPLOYEE_2에서는 문제가 없으나, (c) DNUMBER에 널값을 갖는 투플을 포함하지 않는 릴레이션 EMPLOYEE_3를 만들면 Join시 튜플이 사라진다. Ch10 Fundamentals of Database Systems

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

Fundamentals of Database Systems 10.2.1 다치 종속성의 정형적 정의 정형적 정의 릴레이션 스키마 R에 대해, X와 Y는 R의 애트리뷰트들의 부분집합이다. 그리고, Z = R－(X ∪ Y) (남은 애트리뷰트들)이다. 릴레이션 스키마 R에서 성립하는 다치 종속성 X Y는 R의 임의의 인스턴스 r(R)에 대해, 만약 t1[X] = t2[Y]를 만족하는 r(R)의 두 투플 t1, t2가 존재한다면, 다음의 성질을 만족하는 두 개의 투플 t3와 t4도 반드시 존재해야 한다: t3[X] = t4[X] = t1[X] = t2[X] t3[Y] = t1[Y]이고 t4[Y] = t2[Y] t3[Z] = t2[Z]이고 t4[Z] = t1[Z] MVD 제약조건은 Z의 값에 관계없이 X의 값이 Y의 값들의 집합을 결정한다라는 것을 암시한다. MVD의 특성: X Y가 성립하면, X Z도 성립한다. 애트리뷰트들의 집합 X의 값이 애트리뷰트들의 집합 Y의 값을 결정한다면, X는 Y를 다중결정한다(multidetermine)라고 한다. → Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.2.1 다치 종속성의 정형적 정의 MVD X Y가 (a) Y⊆X 혹은 (b) (X∪Y) = R이면 단순 다치 종속성(trivial MVD)이라 부른다. 단순 다치 종속성은 다치 종속성의 정의에 따라 항상 성립한다. 주어진 함수적 종속성과 다치 종속성의 집합 F에 대해 추가적인 함수적 종속성과 다치 종속성을 추론할 수 있다. → Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems EMP ENAME PNAME DNAME EMP_PROJECTS EMP_DEPENDENTS ENAME PNAME ENAME DNAME Smith X Y John Anna Smith X Y Smith John Anna (c) SUPPLY SNAME PARTNAME PROJNAME Smith Adamsky Walton Bolt Nut Nail ProjX ProjY ProjZ [그림 10.4] 제 4 정규형 (a) 두 개의 다치 종속성 ENAME PNAME과 ENAME DNAME을 가진 EMP 릴레이션 (b) EMP를 제 4 정규형인 두 개의 릴레이션으로 분해 (c) 다치 종속성을 갖지 않으며 제 4 정규형인 SUPPLY 릴레이션 → → Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.2.2 함수적 종속성 및 다치 종속성의 추론 규칙 함수적 종속성과 다치 종속성을 위한 건전(sound)하고 완전(complete)한 추론 규칙들의 집합 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+를 유도할 수 있다. Ch10 Fundamentals of Database Systems

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

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

Fundamentals of Database Systems 알고리즘 10.5: 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); }; → Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems EMP EMP_PROJECTS ENAME PNAME DNAME ENAME PNAME Smith Brown X Y W Z John Anna Jim Joan Bob Smith Brown X Y W Z EMP_DEPENDENTS ENAME DNAME Smith Brown Anna John Jim Joan Bob [그림 10.5] 제 4 정규형의 이점 (a) 여러 개의 튜플을 추가한 EMP 릴레이션 (Brown) (b) EMP를 EMP_PROJECTS와 EMP_DEPENDENTS로 분해 Ch10 Fundamentals of Database Systems

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

Fundamentals of Database Systems 10.4 포함 종속성 포함 종속성은 릴레이션들 사이의 제한조건을 나타낸다. 정형적으로: 릴레이션 R의 애트리뷰트 집합 X와 릴레이션 S의 애트리뷰트 집합 Y사이의 포함 종속성 R.X < S.Y는 R의 릴레이션 상태 r과 S의 릴레이션 상태 s에 대해 다음과 같은 조건을 만족해야 한다. *(ΠX(r(R))  ΠY (s(S)) 포함 종속성에 대한 세 가지 추론 규칙: IDIR1(재귀성 규칙): R.X < R.X IDIR2(애트리뷰트 대응 규칙): X={A1, A2,…, An}이고 Y={B1, B2,…, Bn}일 때, R.X < S.Y이고 Ai가 Bi에 대응한다면 R.Ai < S. Bi이다. IDIR3(이행성 규칙): R.X < S.Y이고 S.Y < T.Z이면, R.X < T.Z이다. Ch10 Fundamentals of Database Systems

Fundamentals of Database Systems 10.5 기타 종속성과 정규형 템플리트 종속성 도메인-키 정규형(DKNF) Ch10 Fundamentals of Database Systems

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

그림 10.6: 일반적인 형태의 종속성에 대한 템플리트 함수적 종속성 X→Y에 대한 템플리트 (a) R={A, B, C, D} Hypothesis a1 b1 c1 d1 X={A, B} a1 b1 c2 d2 Y={C,D} ------------------- Conclusion c1=c2 and d1=d2 (b) R={A, B, C, D} a1 b1 c2 d2 Y={C} Conclusion a1 b1 c2 d1 a1 b1 c1 d2 ( c) R={A, B, C, D} S={E, F, G} X={C,D} Hypothesis a1 b1 c1 d1 Y={E,F} -------------------------------------- Conclusion c1 d1 g 그림 10.6: 일반적인 형태의 종속성에 대한 템플리트 함수적 종속성 X→Y에 대한 템플리트 (b) 다치 종속성 X ->> Y에 대한 템플리트 (c) 포함 종속성 R.X < S.Y에 대한 템플리트 Ch10 Fundamentals of Database Systems

그림 10.7: 고용자의 월급이 직속 상급자의 월급보다 많을 수 없다는 제약조건에 대한 템플리트 EMPLOYEE = {NAME, SSN, …, SALARY, SUPERVISORSSN } a b c d Hypothesis e d f g -------------------------------------- Conclusion c < f 그림 10.7: 고용자의 월급이 직속 상급자의 월급보다 많을 수 없다는 제약조건에 대한 템플리트 Ch10 Fundamentals of Database Systems

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

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