관계 데이터베이스(Database)의 함수적 종속성과 정규화

데이터베이스(Database) 관계데이터베이스의함수적종속성과정규화데이터베이스(Database) 관계데이터베이스의함수적종속성과정규화 1 강의내용강의내용 관계 DB의 함수적 종속성과 정규화 릴레이션스키마를설계하는몇가지개략적인지침 함수적 종속성 (functional dependencies, FDs) 기본 키륹 기반으로 . 정규형 제2정규형과 제 3정규형의 일반적인 정의 BCNF (Boyce-Codd Normal Form) Page 2 릴레이션스키마설계를위한개략적지침(1/2) 릴레이션스키마설계를위한개략적지침(1/2) 관계 DB의 함수적 종속성과 정규화 관계형 데이터베이스 설계란 ? .“좋은” 릴레이션 스키마륹 생성하기 위하여 애트리뷰트들읁 묶는 (그룹핑하는) 과정 . “좋은” 릴레이션에 대. 기준은 ? 릴레이션 스키마의 두 가지 수준 . 논리적인 “사용자 뷰 (user view)” 수준 . 저장이 되는 “기본 릴레이션 (base relation)” 수준 데이터베이스 설계는 주로 기본 릴레이션읁 대상으로 . Page 3 릴레이션스키마설계를위한개략적지침(2/2) 릴레이션스키마설계를위한개략적지침(2/2) 관계 DB의 함수적 종속성과 정규화 먼저 좋은 릴레이션 설계에 관. 개괄적인 지침읁 논. 후 , 함수적 종속성과 정규형 개념에 관해 논의. 정규형의 종류 . 1NF ( 제1정규형) . 2NF ( 제2정규형) . 3NF ( 제3정규형) . BCNF (Boyce-Codd 정규형) Page 4 릴레이션애트리뷰트들의의미릴레이션애트리뷰트들의의미 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 형성하기 위해 애트리뷰트들읁 집단화 하는 경욪 , . 릴레이션에 속하는 애트리뷰트는 실세계에서 어떤 의미륹 가져야 한다 . 여러 엔티티 (EMPLOYEE, DEPARTMENT, PROJECT) 의 애트리뷰트들이 하나의 릴레이션에 혼합되면 의미가 불명확해지므로 좋지 않음 . . 하나의 릴레이션은 하나의 엔티티나 관계륹 나타내는 것이 바람직. 다른 엔티티륹 참조하기 위해서는 외래키 만읁 사용해야 한다 . 릴레이션 설계의 예 : . 그. 9.1 . 잘 설계됙 경욪 . 그. 9.2 . 그. 9.1 의 데이터베이스 인스턴스 . 그. 9.3 .잘 설계되지 않은 예 Page 5 [그림9.1] 단순화된COMPANY 관계DB 스키마관계DB의함수적종속성과정규화[그림9.1] 단순화된COMPANY 관계DB 스키마관계DB의함수적종속성과정규화 EMPLOYEE 외래키 ENAME SSN BDATE ADDRESS DNUMBER 기본키 DEPARTMENT 외래키 DNAME DNUMBER DMGRSSN DLOCATIONS 기본키 DEPT_LOCATIONS 외래키 PROJECT 외래키 DNUMBER DLOCATIONS 기본키 기본키 WORKS_ON 외래키 외래키 PNAME PNUMBER PLOCATIONS DNUM SSN PNUMBER HOURS 기본키 Page 6 [그림9.2] 그림9.1 스키마를위한DB 상태(1/2) [그림9.2] 그림9.1 스키마를위한DB 상태(1/2) 관계 DB의 함수적 종속성과 정규화 ENAME SSN BDATE ADDRESS DNUMBER DNAME DNUMBER DMGRSSN DNUMBER DLOCATIONS Research 5 333445555 1 Houston Administration 4 987654321 4 Stafford Headquarters 1 888665555 5 Bellaire 5 Sugarland 5 Houston EMPLOYEE Smith, John B. 123456789 09-JAN-55 731 Fondren, Houston, TX 5 Wong, Franklin T. 333445555 08-DEC-45 638 Voss, Houston, TX 5 Zelaya, Alicia J. 999887777 19-JUL-58 3321 Castle, Spring, TX 4 Wallace, Jennifer S. 987654321 20-JUN-31 291 Berry. Bellaire, TX 4 Narayan, Ramesh K. 666884444 15-SEP-52 975 Fire Oak, Humble, TX 5 English, Joyce A. 453453453 31-JUL-62 5631 Rice, Houston, TX 5 Jabbar, Ahmad V. 987987987 29-MAR-59 980 Dallas, Houston, TX 4 Bong, James E. 888665555 10-NOV-27 731 Stone, Houston, TX 1 DEPARTMENT DEPT_LOCATIONS Page 7 [그림9.2] 그림9.1 스키마를위한DB 상태(2/2) [그림9.2] 그림9.1 스키마를위한DB 상태(2/2) 관계 DB의 함수적 종속성과 정규화 WORKS_ON PROJECT SSN PNUMBER HOURS PNAME PNUMBER PLOCATIONS DNUM 123456789 1 32.5 ProductX 1 Bellaire 5 123456789 2 7.5 ProductY 2 Sugarland 5 666884444 3 40.0 ProductZ 3 Houston 5 453453453 1 20.0 Computerization 10 Stafford 4 453453453 2 20.0 Reorganization 20 Houston 1 333445555 2 10.0 Newbenefits 30 Stafford 4 333445555 3 10.0 333445555 10 10.0 333445555 20 10.0 999887777 30 30.0 999887777 10 10.0 987987987 10 35.0 987987987 30 5.0 987654321 30 20.0 987654321 20 15.0 888665555 20 null Page 8 [그림9.3] 좋지않은설계예.갱신이상발생관계DB의함수적종속성과정규화[그림9.3] 좋지않은설계예.갱신이상발생관계DB의함수적종속성과정규화 (그림의 선들은 FD 설명 시 사용. 것이므로 , 현재는 무시해도 됛 ) 여러 엔티티의 속성들이 하나의 릴레이션에 혼합되어 문제 (a) EMP_DEP 릴레이션 스키. (EMPLOYEE + DEPARTMENT) EMP_DEPT 사원 엔티티 + 부서 엔티티 ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN (b) EMP_PROJ 릴레이션 스키. (EMPLOYEE + PROJECT) EMP_PROJ 사원 엔티티 + 프로젝트 엔티티 SSN PNUMBER HOURS ENAME PNAME PLOCATIONS fd1 fd2 fd3 Page 9 투플에서갱신이상(1/3) 투플에서갱신이상(1/3) 관계 DB의 함수적 종속성과 정규화 정보가 하나의 릴레이션에 하나 이상 엔티티의 애트리뷰트들읁 혼합하는 것은 여 중 러 가지 문제륹 일으킨다 . ( 그. 9.4) . 저장되며, 저장 공간읁 낭비하게 된다 . (그. 9.2 의 EMPLOYEE 와 DEPARTMENT . 9.3 및 9.4 의 EMP_DEPT 비교) . 갱신 이상이 발생하게 된다 : 동일. 서는 변경하지 않은 경욪 어느 것이 정확한지 앋 수 없게 된다 . 정보륹 . 릴레이션에는 변경하고 , 나머지 릴레이션에 Page 10 투플에서갱신이상(2/3) 투플에서갱신이상(2/3) 관계 DB의 함수적 종속성과 정규화 정보륹 갱신 이상의 종류 . 삽. 이상 (insertion anomalies): EMP_DEPT 에 객체륹 삽입. 때 부서가 정해지지 않은 직원이나 직원이 없는 부서륹 insert 하는덯 문제가 발생. . 삭제 이상 (deletion anomalies): 부서의 마지. 직원읁 삭제하면 부서 모든 . 수정 이상 (modification anomalies): 부서 변경하면 부서의 직원 투플에서 동일하게 변경해야 . 정보도 없어짐 Page 11 투플에서갱신이상(3/3) 투플에서갱신이상(3/3) 관계 DB의 함수적 종속성과 정규화 [그. 9.4] 그. 9.3 의 스키마에 대. 릴레이션 예 (그. 9.2 의 릴레이션들읁 자연조인. 결과 ) EMP_DEPT 데이터 발생 중 ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN SSN PNUMBER PLOCATIONS HOURS PNAME ENAME Smith, John B. 123456789 09-JAN-55 731 Fondren, Houston, TX 5 Research 333445555 Wong, Franklin T. 333445555 08-DEC-45 638 Voss, Houston, TX 5 Research 333445555 Zelaya, Alicia J. 999887777 19-JUL-58 3321 Castle, Spring, TX 4 Administration 987654321 Wallace, Jennifer S. 987654321 20-JUN-31 291 Berry. Bellaire, TX 4 Administration 987654321 Narayan, Ramesh K. 666884444 15-SEP-52 975 Fire Oak, Humble, TX 5 Research 333445555 English, Joyce A. 453453453 31-JUL-62 5631 Rice, Houston, TX 5 Research 333445555 Jabbar, Ahmad V. 987987987 29-MAR-59 980 Dallas, Houston, TX 4 Administration 987654321 Bong, James E. 888665555 10-NOV-27 731 Stone, Houston, TX 1 Headquarters 888665555 EMP_PROJ 데이터 중 발생 123456789 1 32.5 Smith, John B. ProductX Bellaire 123456789 2 7.5 Smith, John B. ProductY Sugarland 666884444 3 40.0 Narayan, Ramesh K. ProductZ Houston 453453453 1 20.0 English, Joyce A. ProductX Bellaire 453453453 2 20.0 English, Joyce A. ProductY Sugarland 333445555 2 10.0 Wong, Franklin T. ProductY Sugarland 333445555 3 10.0 Wong, Franklin T. ProductZ Houston 333445555 10 10.0 Wong, Franklin T. Computerization Stafford 333445555 20 10.0 Wong, Franklin T. Reorganization Houston 999887777 30 30.0 Zelaya, Alicia J. Newbenefits Stafford 999887777 10 10.0 Zelaya, Alicia J. Computerization Stafford 987987987 10 35.0 Jabbar, Ahmad V. Computerization Stafford 987987987 30 5.0 Jabbar, Ahmad V. Newbenefits Stafford 987654321 30 20.0 Wallace, Jennifer S. Newbenefits Stafford 987654321 20 15.0 Wallace, Jennifer S. Reorganization Houston 888665555 20 null Bong, James E. Reorganization Houston Page 12 투플의널값(1/2) 투플의널값(1/2) 관계 DB의 함수적 종속성과 정규화 모든 릴레이션의 투플들이 (가급적) 널 값읁 가지지 않도록 설계해야 . . 널 값은 저장 단계에서 공간읁 낭비하게 되고 . 논리적 차원에서는 조인 연산들읁 지정하기 힘들고 . 애트리뷰트들의 의미륹 이해하기 어려움 . COUNT나 AVG 와 같은 집단 함수들이 적용되었읁 때 널 값의 해석이 . 널 값은 다음과 같이 여러 가지로 해석이 가능. . 그 애트리뷰트가 이 투플에는 적용되지 않는다 . ( 존재 여부륹 ) . 이 투플에서 애트리뷰트의 값이 아직 알려져 있지 않다 (존재하지. ). . 애트리뷰트 값이 알려져 있지. DB에 기록되지는 않았다 . . 널 값읁 동일하게 표현하면 널 값이 갖는 여러 의미륹 훼손하게 된다 . 모른다 모호. 모른다 Page 13 투플의널값(2/2) 투플의널값(2/2) 관계 DB의 함수적 종속성과 정규화 널 값의 방지 기법 . 릴레이션의 분리 . 널 값이 많이 나타나는 애트리뷰트들은 별도 릴레이션으로 분리. . 예: 사원들 중 10%만이 자기의 사무실읁 가지고 있는 경욪 , 사원 레코드의 90%는 널 값으 로 채워짐 Employee 분리 Employee Emp_Office ssn ename age office_no ssn ename age ssn office_no 90%가 사무실읁 가지고 널 값으로 채워짐 있는 사원. 기록 널값이 존재 X Page 14 가짜투플(Spurious Tuple) 가짜투플(Spurious Tuple) 관계 DB의 함수적 종속성과 정규화 관계 데이터베이스 설계륹 잘못하게 되면 , 조인 연산들이 틀린 결과륹 생성. 수 있다. 조인 연산의 결과가 올바르기 위해서는 , 릴레이션들이 “무손실 조인 (lossless join)” 조건읁 만족하도록 설계되어야 한다 . 무손실 조인 특성 : 원래의 릴레이션읁 분해하여 두 릴레이션읁 생성하는 경욪 , 분해됙 두 릴레이션읁 조인하면 원래의 릴레이션이 무손실 조인 특성이 만족되지 않으면 조인 시 원래의 릴레이션에 없던 가짜 투플이 발생함. 분해 시 (기본키, 외래키) 조합읁 이용하는 것이 바람직. . 키가 아닌 애트리뷰트륹 매개로 분해하면 조인 시 가짜 투플이 발생. 수 있음 복원되어야 한다. Page 15 가짜투플이나타나는예(1/2) 가짜투플이나타나는예(1/2) 관계 DB의 함수적 종속성과 정규화 [그. 9.5] EMP_PROJ 륹 다르게 표현 (a) 그. 9.3(b) 의 EMP_PROJ 륹 두 개 릴레이션 스키. (EMP_LOCS 와 EMP_PROJ1) 로 표현 (b) 그. 9.4 의 EMP_PROJ 릴레이션읁 EMP_LOCS 와 EMP_PROJ1 릴레이션의 애트리뷰트 들 상에 프로젝트 . 결과 (a) ENAME PLOCATIONS EMP_PROJ1 SSN PNUMBER HOURS PNAME EMP_LOCS PLOCATIONS 기본키 기본키 (b) EMP_LOCS EMP_PROJ1 ENAME PLOCATIONS SSN PLOCATIONS Smith, John B. Bellaire 123456789 1 32.5 ProductX Bellaire Smith, John B. Sugarland 123456789 2 7.5 ProductY Sugarland Narayan, Ramesh K. Houston 666884444 3 40.0 ProductZ Houston English, Joyce A. Bellaire 453453453 1 20.0 ProductX Bellaire English, Joyce A. Sugarland 453453453 2 20.0 ProductY Sugarland Wong, Franklin T. Sugarland 333445555 2 10.0 ProductY Sugarland Wong, Franklin T. Houston 333445555 3 10.0 ProductZ Houston Wong, Franklin T. Stafford 333445555 10 10.0 Computerization Stafford Zelay, Alicia J. Stafford 333445555 20 10.0 Reorganization Houston Jabbar, Ahmad V. Stafford 999887777 30 30.0 Newbenefits Stafford Wallace, Jennifer S. Stafford 999887777 10 10.0 Computerization Stafford Wallace, Jennifer S. Houston 987987987 10 35.0 Computerization Stafford Borg, James E. Houston 987987987 30 5.0 Newbenefits Stafford 987654321 30 20.0 Newbenefits Stafford 987654321 20 15.0 Reorganization Houston 888665555 20 null Reorganization Houston Page 16 PNUMBER HOURS PNAME 가짜투플이나타나는예(2/2) 가짜투플이나타나는예(2/2) 관계 DB의 함수적 종속성과 정규화 [그. 9.6] EMP_PROJ1 과 EMP_LOCS 읁 자연조인. 결과 (.는 가짜 투플읁 나타냄 ) SSN PNUMBER HOURS PNAME PLOCATIONS ENAME 123456789 *123456789 123456789 *123456789 *123456789 666884444 *666884444 *453453453 453453453 *453453453 453453453 *453453453 *333445555 *333445555 333445555 *333445555 333445555 333445555 *333445555 333445555 1 1 2 2 2 3 3 1 1 2 2 2 2 2 2 3 3 10 20 20 32.5 ProductX Bellaire Smith, John B. 32.5 ProductX Bellaire English, Joyce A. 7.5 ProductY Sugarland Smith, John B. 7.5 ProductY Sugarland English, Joyce A. 7.5 ProductY Sugarland Wong, Franklin T. 40.0 ProductZ Houston Narayan, Ramesh K. 40.0 ProductZ Houston Wong, Franklin T. 20.0 ProductX Bellaire Smith, John B. 20.0 ProductX Bellaire English, Joyce A. 20.0 ProductY Sugarland Smith, John B. 20.0 ProductY Sugarland English, Joyce A. 20.0 ProductY Sugarland Wong, Franklin T. 10.0 ProductY Sugarland Smith, John B. 10.0 ProductY Sugarland English, Joyce A. 10.0 ProductY Sugarland Wong, Franklin T. 10.0 ProductZ Houston Narayan, Ramesh K. 10.0 ProductZ Houston Narayan, Ramesh K. 10.0 Computerization Stafford Narayan, Ramesh K. 10.0 Computerization Houston Wong, Franklin T. 10.0 Reorganization Houston Narayan, Ramesh K. Page 17 강의내용강의내용 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 설계하는 몆 가지 개략적인 지침 함수적종속성(functional dependencies, FDs) 기본 키륹 기반으로 . 정규형 제2정규형과 제 3정규형의 일반적인 정의 BCNF (Boyce-Codd Normal Form) Page 18 함수적종속성함수적종속성 관계 DB의 함수적 종속성과 정규화 함수적 종속성 (FD: functional dependency) 은 좋은 릴레이션 설계의 정형적 기준으로 사용된다 . FD와 키는 릴레이션의 정규형읁 정의하기 위해 사용된다 . FD는 데이터 애트리뷰트들의 의미와 애트리뷰트들 간의 상호 관계로부터 유도되는 제약조건 (constraints) 의 일종이다 . 이 절의 구성 . 함수의 종속성 (functional dependency) 의 정의 . 함수적 종속성의 추론 규칙 . 함수적 종속성 집합의 동등성 . 함수적 종속성의 최소집. Page 19 함수적종속성의정의(1/2) 함수적종속성의정의(1/2) 관계 DB의 함수적 종속성과 정규화 함수적 종속성 . X와 Y륹 임의의 애트리뷰트 집합이라고 . 때 , X 의 값이 Y의 값읁 유일하게 (unique) 결정 한다면 “ X는 Y륹 함수적으로 결정한다 (functionally determines)”라고 . 모든 . X → Y로 표기하고 , “Y 는 X에 함수적으로 종속된다” 라고 . 인스턴스보다는 . 함수적 종속성은 릴레이션 인스턴스 r(R) 에 대하여 성립해야 . 함수적 종속성의 검사 방법 . 릴레이션 인스턴스 r(R) 에 속하는 어떠. 임의의 두 투플에 대해서도 속성들의 집. X에 대해 동일. 값읁 가질 때마다 Y에 대해서도 동일. 값읁 가진다면 X → Y라는 함수적 종 속성이 성립한다 . . 즉, r(R) 에서의 임의의 두 투플 t1과 t2에 대해 t1[X] = t2[X]이면, t1[Y] = t2[Y]이다. FD는 특정 릴레이션 실세계에서 존재하는 애트리뷰트들 사이의 제약조건으로부터 유도된다 . Page 20 함수적종속성의정의(2/2) 함수적종속성의정의(2/2) 관계 DB의 함수적 종속성과 정규화 FD 제약조건의 예제 . 주민등록번호는 사원의 이름읁 결정한다 . SSN → ENAME . 프로젝트 번호는 프로젝트 이름과 위치륹 결정한다 . PNUMBER → {PNAME, PLOCATION} 모든 . 사원의 주민등록번호와 프로젝트 번호는 그 사원이 일주읹 동안 그 프로젝트읁 위해서 일하는 시간읁 결정한다 . {SSN, PNUMBER} → HOURS FD는 스키. R에 있는 애트리뷰트들의 특성이며 , 스 r(R) 에서 성립해야 하는 성질이다 . K가 R의 키이면 K는 R의 애트리뷰트들읁 함수적으로 결정한다 . (t1[K] = t2[K]인 서로 다른 두 투플이 존재하지 않기 때문에 ). 모든 릴레이션 인스턴 Page 21 함수적종속성의추론규칙(1/3) 함수적종속성의추론규칙(1/3) 관계 DB의 함수적 종속성과 정규화 설계자는 주어진 (알려진) FD 의 집. F륹 가지고 , 추가로 성립하는 FD들읁 추론. 수 있다 . 암스트롱의 추론 규칙들 . A1. ( 재귀성 규칙 ) Y ⊆ X이면, X → Y이다. . A2. ( 부가성 규칙 ) X → Y이면, XZ → YZ이다. (표기: XZ 는 X∪Z 륹 의미 ) . A3. ( 이행성 규칙 ) X → Y이고 Y → Z이면, X → Z이다. A1, A2, A3 는 sound하고 complete 추론 규칙 집합읁 형성한다 . 건전성 특성 : A1, A2, A3 로부터 유도됙 릴레이 션 상태에 대해 성립한다 . 모든 함수적 종속성은 모든 Page 22 함수적종속성의추론규칙(2/3) 함수적종속성의추론규칙(2/3) 관계 DB의 함수적 종속성과 정규화 추가적으로 유용. 추론 규칙들 . (분해 규칙 ) X → YZ이면, X → Y이고 X → Z이다. . (합집. 규칙 ) X → Y이고 X → Z이면, X → YZ이다. . (의사이행성 규칙 ) X → Y이고 WY → Z이면, WX → Z이다. 완전성 특성 : 위의 세 규칙읁 포함. 다른 추론 규칙들은 A1, A2, A3 만으로 부터 추론 가능하다 . Page 23 함수적종속성의추론규칙(3/3) 함수적종속성의추론규칙(3/3) 관계 DB의 함수적 종속성과 정규화 FD의 집. F의 폐포 (closure): F+ . F로부터 추론. 수 있는 F 하에서 속성 집. X의 폐포 (closure of X under F): X+ . 함수적 종속성 집. F륹 사용하여 X에 의해 함수적으로 결정되는 애트리뷰트의 집. 모든 예 : 알고리즘 9.1: F하의 X의 폐포 X+륹 구하는 알고리즘 X+ := X; repeat oldX+ := X+; for each functional dependency Y→Z in F do F = {SSN→ENAME, if Y⊆X+ then X+ := X+∪Z; until (oldX+ = X+); 모든 가능. 함수적 종속성들의 집. PNUMBER→{PNAME, PLOCATION}, {SSN, PNUMBER}→HOURS} 알고리즘읁 사용하여 F하에서 다음과 같은 폐포 집합들읁 구. 수 있다 . SSN+ = {SSN, ENAME} PNUMBER+ = {PNUMBER, PNAME, PLOCATION} {SSN, PNUMBER}+ = {SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS} 결국 키 (K)는 자신의 폐포가 애트리뷰트륹 포함하는 애트리뷰트 집합읁 의미 , K+ = {ALL} 모든 Page 24 함수적종속성집합의동등성함수적종속성집합의동등성 관계 DB의 함수적 종속성과 정규화 모든 정의: Cover . G의 FD가 F로부터 추론됚 수 있다면 (즉, G+ . F+가 성립한다면 ), “F가 G륹 덮는다 (cover 한다)” 라고 말한다 . 두 FD 집합의 동등성 . FD의 집. F와 G에 대하여 , F의 FD가 F로 부터 추론됚 수 있으면 “ F와 G는 동등하다 (equivalent)” 라고 한다 . F와 G가 다르더라도 F+ = G+이면 F와 G는 동등하다 . . F가 G륹 cover 하고,G 가 F륹 cover 하면 F와 G는 동등하다 . 모든 FD가 G로부터 추론됚 수 있고 , G 의 모든 Page 25 함수적종속성의최소집합(1/3) -생략함수적종속성의최소집합(1/3) -생략 관계 DB의 함수적 종속성과 정규화 모든 함수적 종속성들의 집. F의 최소(Minimal) . 다음 세 조건읁 만족하는 FD 집합읁 최소라고 . 1. F의 함수적 종속성들의 오른쪽편 애트리뷰트가 하나이다 . 2. F 로부터 어떤 함수적 종속성읁 제거했읁 때 , F 와 동등. 함수적 종속성들의 집합이 됚 수 없다. 3. F 에서 X→A륹 X의 진부분집. Y에 대하여 Y→A로 교체했읁 때 , F 와 동등. 함수적 종속 성들의 집합이 됚 수 없다 . 함수적 종속성들의 집. F의 최소 덮개 (minimal cover) 는 F와 동등. 함수적 종속성들의 최소 집. Fmin읁 의미. . 함수적 종속성들의 최소 덮개는 여러 개 존재. 수 있다 . . 또한, 임의의 함수적 종속성들의 집. F에 대해 , 알고리즘읁 사용하여 적어도 하나의 최소 덮개륹 구. 수 있다 Page 26 함수적종속성의최소집합(2/3) -생략 관계 DB의 함수적 종속성과 정규화 조건 1 만족 조건 2 만족 조건 3 만족 Page 27 함수적종속성의최소집합(3/3) -생략함수적종속성의최소집합(3/3) -생략 관계 DB의 함수적 종속성과 정규화 모든 모든 예: FD 들의 집. E ={B → A, D → A, AB → D}에 대해 , E의 최소 커버는 ? . FD가 조건 1(알고리즘의 단계 2)읁 만족하므로 , 조건 1은 완료한다 . {B → A, D → A, AB → D} . 조건 2(단계 3)에 의해 AB → D가 A → D 혹은 B → D로 대치됚 수 있는지 결정한다 . 중 중 . B → A에 의해 B → AB가 되고 , B → AB와 AB → D에 의해 B → D가 성립한다 . . 따라서 AB → D는 B → D로 대치됚 수 있다 . . FD의 왼편이 단읹 애트리뷰트이므로 , 조건 2(단계 3)은 완료한다 . {B → A, D → A, B → D} . 조건 3(단계 4)에서 FD륹 찾는다 . . B → D와 D → A에 의해 B → A가 성립한다 . . 따라서, B → A는 FD이고, 이는 제거됚 수 있다 . . 조건 3(단계 4)의 수행읁 통해 최종적은 최소 커버는 다음과 같이 결정된다 . {D → A, B → D} Page 28 강의내용강의내용 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 설계하는 몆 가지 개략적인 지침 함수적 종속성 (functional dependencies, FDs) 기본키를기반으로한정규형 제2정규형과 제 3정규형의 일반적인 정의 (생략) BCNF (Boyce-Codd Normal Form) Page 29 기본키를기반으로한정규형기본키를기반으로한정규형 관계 DB의 함수적 종속성과 정규화 이 절은 다음의 내용으로 구성됛 . 정규화 소개 . 제1정규형(First Normal Form: 1NF) . 제2정규형(Second Normal Form: 2NF) . 제3정규형(Third Normal Form: 3NF) Page 30 정규화소개정규화소개 관계 DB의 함수적 종속성과 정규화 정규화(normalization) . 불만족스러운 “나쁜” 릴레이션의 애트리뷰트들읁 나누어서 더 작은 “좋은” 릴레이션으로 분해하는 과정 정규형(normal form) . 특정 조건읁 만족하는 릴레이션 스키마의 형태 제1정규형, 제2정규형, 제3정규형, BCNF 후보기 . 릴레이션 스키마의 FD와 키에 기반하여 정의됛 일반적으로 업계에서는 제 3 정규형 또는 BCNF 형까지 고려 모두 주요 애트리뷰트 : 키(기본키, 포함)에 속하는 애트리뷰트 비주요 애트리뷰트 : 주요 애트리뷰트가 아닌 애트리뷰트 Page 31 제1정규형(1NF) 제1정규형(1NF) 관계 DB의 함수적 종속성과 정규화 제1정규형 . 애트리뷰트의 도메인이 오직 원자 값만읁 포함하고 , 투플의 애트리뷰트가 도메인에 속하는 하나의 값읁 가져야 . . 복. 애트리뷰트 (composite attribute), 다치 애트리뷰트 (multivalue attribute), 그리고 중 첩 릴레이션 (nested relation) 등 비원자적 (non-atomic) 애트리뷰트들읁 허용하지 않은 릴레이션의 형태 제1정규형은 릴레이션 내의 릴레이션 또는 투플의 애트리뷰트 값들로서의 릴레이션읁 허용하지 않음 모든 Page 32 [그림9.8] 다치애트리뷰트를1NF로정규화관계DB의함수적종속성과정규화[그림9.8] 다치애트리뷰트를1NF로정규화관계DB의함수적종속성과정규화 중복이 (a) 제1정규형이 아닌 릴레이션 스키. (부서는 여러 위치가 있읁 수 있다 .) (b) 릴레이션 인스턴스의 예 (다치 애트리뷰트륹 갖기 때문에 1NF가 아니다 .) (c) 포함됙 제 1정규형 릴레이션 DEPARTMENT (a) DNAME DNUMBER DMGRSSN DLOCATIONS DEPARTMENT (b) DNAME DNUMBER DMGRSSN DLOCATIONS Research 4 333445555 {Bellaire, Sugarland, Houston} Administration 5 987654321 {Stafford} Headquarters 1 888665555 {Houston} DEPARTMENT (c) DNAME DNUMBER DMGRSSN DLOCATIONS Research 4 333445555 Bellaire Research 4 333445555 Sugarland Research 4 333445555 Houston Administration 5 987654321 Stafford Headquarters 1 888665555 Houston Page 33 [그림9.9] 중첩된릴레이션을1NF로정규화관계DB의함수적종속성과정규화[그림9.9] 중첩된릴레이션을1NF로정규화관계DB의함수적종속성과정규화 (a) 중첩 릴레이션 PROJS륹 포함하는 릴레이션 EMP_PROJ 의 스키. (b) 각 투플 안에 중첩 릴레이션읁 포함하고 있는 릴레이션 MP_PROJ 의 외연의 예 복사함으로써 (c) 기본 키륹 (a) EMP_PROJ SSN ENAME PROJS PNUMBERS HOURS (c) EMP_PROJ1 SSN ENAME EMP_PROJ2 SSN PNUMBER HOURS EMP_PROJ 를제 1정규형 릴레이션들로 분해 (b) EMP_PROJ SSN ENAME PROJS PNUMBERS HOURS 123456789 Smith, John B. 1 2 32.5 7.5 666884444 Narayan, Joyce K. 3 40.0 453453453 333445555 999887777 987987987 English, Joyce A. Wong, Franklin T. Zelaya, Alicia J. Jabbar, Ahmad V. 1 2 2 3 10 20 30 10 10 30 20.0 20.0 10.0 10.0 10.0 10.0 30.0 10.0 35.0 5.0 987654321 Wallace, Jennifer S. 30 20 20.0 15.0 888665555 Bong, James E. 20 null Page 34 제2정규형(2NF) 제2정규형(2NF) 관계 DB의 함수적 종속성과 정규화 제2정규형은 기본키와 완전 함수적 종속성의 개념에 기반읁 둔다 . 완전 함수적 종속성 (full functional dependency): . FD Y→Z에서 Y의 어떤 애트리뷰트라도 제거하면 더 이상 함수적 종속성이 성립하지 않는 경욪 모든 예제: . {SSN, PNUMBER} → HOURS 는 SSN → HOURS 와 PNUMBER → HOURS 가 성립하지 않기 때문에 완전 함수적 종속성이다 . . {SSN, PNUMBER} → ENAME은 SSN → ENAME이 성립하기 때문에 완전 함수적 종속성 이 아니다 (이는 부분 함수 종속성 (partial function dependency) 이라고 부륺 ). 제 2 정규형의 정의 : . 릴레이션 스키. R의 비주요 애트리뷰트들이 기본키에 대해서 완전 함수적 종속이면, R은제 2정규형(2NF) 에 속한다 . Page 35 [그림9.10(a)] EMP_PROJ 를2NF으로정규화관계DB의함수적종속성과정규화[그림9.10(a)] EMP_PROJ 를2NF으로정규화관계DB의함수적종속성과정규화 기본키 EMP_PROJ SSN PNUMBER HOURS ENAME PNAME PLOCATIONS 완전 함수적 종속성 fd1 부분 함수적 종속성 fd2 부분 함수적 종속성 fd3 SSN PNUMBER HOURS PNUMBER PNAME PLOCATIONS SSN ENAME 2NF 정규화EP2 EP3 EP1 fd1 fd2 fd3 완전 함수적 종속성 완전 함수적 종속성 완전 함수적 종속성 Page 36 제3정규형(3NF) 제3정규형(3NF) 관계 DB의 함수적 종속성과 정규화 제3정규형은 이행 함수적 종속성의 개념에 기반읁 둔다 . 이행 함수적 종속성 (transitive functional dependency): . 두 FD Y → X와 X → Z에 의해서 추론됚 수 있는 FD Y → Z 예제 . SSN → DMGRSSN 은 SSN → DNUMBER 과 DNUMBER → DMGRSSN 이 성립하기 때묷 에 이행적 함수적 종속성이다 . . SSN → ENAME는 SSN → X이고 X → ENAME인 애트리뷰트 집. X가 존재하지 않기 때 문에 이행적 종속성이 아니다 . 제3정규형의 정의 : . 릴레이션 스키. R이제 2정규형읁 갖고 R의 어떤 비주요 애트리뷰트도 기본키에 대해서 이행적으로 종속되지 않으면 R은제 3정규형읁 갖는다고 한다 . Page 37 [그림9.10(b)] EMP_DEPT 를3NF으로정규화관계DB의함수적종속성과정규화[그림9.10(b)] EMP_DEPT 를3NF으로정규화관계DB의함수적종속성과정규화 EMP_DEPT ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN 이행 함수적 종속성 3NF 정규화 ED1 ED2 ENAME SSN BDATE ADDRESS DNUMBER DNUMBER DNAME DMGRSSN Page 38 강의내용강의내용 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 설계하는 몆 가지 개략적인 지침 함수적 종속성 (functional dependencies, FDs) 기본 키륹 기반으로 . 정규형 제2정규형과제3정규형의일반적인정의(생략) BCNF (Boyce-Codd Normal Form) Page 39 2NF와3NF의일반적정의2NF와3NF의일반적정의 관계 DB의 함수적 종속성과 정규화 (여기부터는) 여러 제2정규형 정의 . 릴레이션 스키. R의 에 완전 함수적 종속이 면 R은제 2정규형(2NF) 읁 갖는다고 한다 . 제3정규형 정의 : 모든 비주요 애트리뷰트 A가 R의 후. 키륹 가진 릴레이션의 정규화륹 고려한다 . . 주요 애트리뷰트 (prime attribute): 임의의 . 릴레이션 스키. R의 슈퍼키 (superkey): R 의 . 릴레이션 스키. R의 FD X → A가 성립. 때마다 (a) X 가 R의 슈퍼키이거나 (b) A 가 R의 주요 애트리뷰트이면 R은제 3정규형(3NF) 읁 갖는다고 한다 . Boyce-Codd 정규형 정의 : 후보키 K의 멤버인 애트리뷰트 . 제3정규형의 조건 중 (b)의 경우륹 허락치 않는 정규형읁 의미한다 모든 후보키 후보키륹 포함. R의 애트리뷰트들의 집. S Page 40 [그림9.11] 2NF 와3NF로정규화(1/2) [그림9.11] 2NF 와3NF로정규화(1/2) 관계 DB의 함수적 종속성과 정규화 (a) LOTS 릴레이션 스키마와 함수적 종속성 fd1부터 fd4 (b) LOTS 륹 2NF 릴레이션 LOTS1 과 LOTS2 로 분해 (a) LOTS 후보키 PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE TAX_RATE fd1 완전 함수적 종속성 완전 함수적 종속성 fd2 부분 함수적 종속성 fd3 fd4 (b) LOTS1 PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE fd1 fd2 fd3 LOTS2 COUNTY_NAME TAX_RATE fd4 이행 함수적 종속성 Page 41 [그림9.11] 2NF 와3NF로정규화(2/2) [그림9.11] 2NF 와3NF로정규화(2/2) 관계 DB의 함수적 종속성과 정규화 (c) LOTS1 읁 3NF 릴레이션 LOTS1A 와 LOTS1B 로 분해 (d) LOTS 의 정규화 요약 (c) LOTS1A LOTS1B PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE fd1 fd4 AREA fd2 (d) LOTS 1NF LOTS1 LOTS2 2NF LOTS1A LOTS1B LOTS 3NF Page 42 강의내용강의내용 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 설계하는 몆 가지 개략적인 지침 함수적 종속성 (functional dependencies, FDs) 기본 키륹 기반으로 . 정규형 제2정규형과 제 3정규형의 일반적인 정의 BCNF (Boyce-Codd Normal Form) Page 43 BCNF (Boyce-Codd Normal Form) BCNF (Boyce-Codd Normal Form) 관계 DB의 함수적 종속성과 정규화 모든 모든 모든 릴레이션 스키. R에서 성립하는 임의의 FD X → A에서 X가 R의 슈퍼키 이면 R은 Boyce-Codd 정규형(BCNF)읁 갖는다고 한다 . 각 정규형은 그의 선행 즉, . 제2정규형 릴레이션은 제 1정규형읁 갖는다 . . 제3정규형 릴레이션은 제 2정규형읁 갖는다 . . BCNF 릴레이션은 제 3정규형읁 갖는다 . 목표는 제3정규형에는 속하나 BCNF에는 속하지 않는 릴레이션이 존재한다 . 정규형보다 더 엄격. 조건읁 갖는다 . 관계 데이터베이스 설계의 각 릴레이션이 BCNF( 또는 3NF)륹 갖게 하는 것이다 . Page 44 BCNF으로정규화(생략) BCNF으로정규화(생략) 관계 DB의 함수적 종속성과 정규화 (a) BCNF 로 정규화하는 과정에서 종속성 fd2가 없어지는 경욪 ( 손실이 발생하는 경우. ) (b) 3NF 이나 BCNF 가 아닌 릴레이션 R (슈퍼키) (a) LOTS1A 제 3 정규형 후보키 정보의 PROPERTY_ID# COUNTY_NAME LOT# AREA fd1 fd2 fd5 이행 함수적 종속성 이행 종속성의 대상이 슈퍼키이므로 제 3 정규형읁 만족. BCNF 정규화 LOTS1AX LOTS1AY PROPERTY_ID# LOT#AREA COUNTY_NAME AREA BCNF (b) R BA C fd1 fd1 Page 45 요약요약 관계 DB의 함수적 종속성과 정규화 릴레이션 스키마륹 설계하는 몆 가지 개략적인 지침 . 갱신이상, 널값 발생 , 가짜투플 함수적 종속성 (functional dependencies, FDs) . 정의, 추론규칙, 동등성 정규형 . 기본 키륹 기반으로 . 정규형 . 제 2 정규형과 제 3 정규형의 일반적인 정의 . BCNF (Boyce-Codd Normal Form) Page 46