9 장. 관계 데이타베이스의 함수적 종속성과 정규화 9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침 9.2 함수적 종속성 (functional dependencies, FDs) 9.3 기본 키를 기반으로 한 정규형 9.4 제 s2 정규형과 제 3 정규형의 일반적인 정의 9.5 BCNF (Boyce-Codd Normal Form)

9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침 관계형 데이타베이스 설계란 무엇인가? 릴레이션 스키마의 두 가지 수준 “좋은” 릴레이션 스키마를 생성하기 위하여 애트리뷰트들을 그룹별로 모으는 과정 릴레이션 스키마의 두 가지 수준 논리적인 “사용자 뷰(user view)” 수준 저장이 되는 “기본 릴레이션(base relation)” 수준 설계는 주로 기본 릴레이션과 관련된다. “좋은” 기본 릴레이션에 대한 기준은 ? 먼저 좋은 릴레이션 설계에 관한 개괄적인 지침을 논한 후, 함수적 종속성과 정규형의 형식적인 개념에 관해 논한다. 1NF (제 1 정규형) 2NF (제 2 정규형) 3NF (제 3 정규형) BCNF (Boyce-Codd 정규형)

9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침(cont.) 이외의 다른 종속성, 정규형, 릴레이션 설계 알고리즘은 제 10 장에서 논한다. 9.1.1 릴레이션 애트리뷰트들의 의미 9.1.2 투플에서 중복된 정보와 이상 (anomaly) 9.1.3 투플의 널값 9.1.4 가짜 투플 (spurious tuples)

9.1.1 릴레이션 애트리뷰트들의 의미 비공식적으로 표현하자면, 각 투플은 하나의 엔티티 또는 관계 인스턴스를 표현해야 한다. 다른 엔티티들(EMPLOYEE, DEPARTMENT, PROJECT)의 애트리뷰트들은 하나의 릴레이션에 혼합되면 안된다. 다른 엔티티를 참조하기 위해서는 외래키만을 사용하여야 한다.

9.1.2 투플에서 중복된 정보와 이상(anomaly) 하나의 릴레이션에 하나 이상의 엔티티의 애트리뷰트들을 혼합하는 것은 여러 가지 문제를 야기시킨다. 정보가 중복 저장되고, 저장 공간을 낭비하게 된다. 갱신 이상의 종류 삽입 이상 (insertion anomalies) 삭제 이상 (deletion anomalies) 수정 이상 (modification anomalies)

[그림 9.1] COMPANY 관계 데이타베이스 스키마를 단순화시킨 버전 EMPLOYEE ENAME SSN BDATE ADDRESS DNUMBER 기본키 DEPARTMENT 외래키 DNAME DNUMBER DMGRSSN DLOCATIONS 기본키 DEPT_LOCATIONS 외래키 PROJECT 외래키 DNUMBER DLOCATIONS PNAME PNUMBER PLOCATIONS DNUM 기본키 기본키 WORKS_ON 외래키 외래키 SSN PNUMBER HOURS 기본키 [그림 9.1] COMPANY 관계 데이타베이스 스키마를 단순화시킨 버전

[그림 9.2] 그림 9.1의 스키마의 릴레이션들의 예 EMPLOYEE ENAME SSN BDATE ADDRESS DNUMBER Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Bong, 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 DEPARTMENT DEPT_LOCATIONS DNAME DNUMBER DMGRSSN DNUMBER DLOCATIONS Research Administration Headquarters 5 4 1 333445555 987654321 888665555 1 4 5 Houston Stafford Bellaire Sugarland [그림 9.2] 그림 9.1의 스키마의 릴레이션들의 예

[그림 9.2] 그림 9.1의 스키마의 릴레이션들의 예 (cont.) WORKS_ON PROJECT SSN PNUMBER HOURS PNAME PNUMBER PLOCATIONS DNUM 123456789 666884444 453453453 333445555 999887777 987987987 987654321 888665555 1 2 3 10 20 30 32.5 7.5 40.0 20.0 10.0 30.0 35.0 5.0 15.0 null ProductX ProductY ProductZ Computerization Reorganization Newbenefits 1 2 3 10 20 30 Bellaire Sugarland Houston Stafford 5 4 1 [그림 9.2] 그림 9.1의 스키마의 릴레이션들의 예 (cont.)

[그림 9.3] 두 개의 릴레이션 스키마와 함수적 종속성 (a) EMP_DEPT 릴레이션 스키마 ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN (b) EMP_PROJ SSN PNUMBER HOURS ENAME PNAME PLOCATIONS fd1 fd2 fd3 [그림 9.3] 두 개의 릴레이션 스키마와 함수적 종속성 (a) EMP_DEPT 릴레이션 스키마 (b) EMP_PROJ 릴레이션 스키마

[그림 9.4] 그림 9.2의 릴레이션들을 자연조인한 결과인 그림 9.3의 스키마에 대한 릴레이션의 예 EMP_DEPT ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN Smith, John B. Wong, Franklin T. Zelaya, Alicia J. Wallace, Jennifer S. Narayan, Ramesh K. English, Joyce A. Jabbar, Ahmad V. Bong, 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 EMP_PROJ SSN PNUMBER HOURS ENAME PNAME PLOCATIONS 123456789 666884444 453453453 333445555 999887777 987987987 987654321 888665555 1 2 3 10 20 30 32.5 7.5 40.0 20.0 10.0 30.0 35.0 5.0 15.0 null Smith, John B. Narayan, Ramesh K. English, Joyce A. Wong, Franklin T. Zelaya, Alicia J. Jabbar, Ahmad V. Wallace, Jennifer S. Bong, James E. ProductX ProductY ProductZ Computerization Reorganization Newbenefits Bellaire Sugarland Houston Stafford [그림 9.4] 그림 9.2의 릴레이션들을 자연조인한 결과인 그림 9.3의 스키마에 대한 릴레이션의 예

9.1.3 투플의 널값 릴레이션은 가능하다면 투플이 널 값을 가지지 않도록 설계해야 한다. 자주 널 값을 갖는 애트리뷰트들은 별개의 릴레이션으로 만든다.

9.1.4. 가짜 투플 (spurious tuples) 잘못된 관계 데이타베이스 설계는 일부 조인 연산들이 틀린 결과를 생성하게 한다. 조인 연산의 결과가 의미있게 하기 위해서는 “무손실 조인(lossless join)” 특성이 필요하다. 릴레이션들은 무손실 조인 조건을 만족하도록 설계되어야 한다. 더 자세한 것은 제 10 장에서 논한다.

(a) 그림 9.3(b)의 EMP_PROJ를 두 개의 릴레이션 스키마 (EMP_PROJ1과 EMP_LOCS)로 표현 ENAME PLOCATIONS SSN PNUMBER HOURS PNAME PLOCATIONS 기본키 기본키 (b) EMP_LOCS EMP_PROJ1 ENAME PLOCATIONS SSN PNUMBER HOURS PNAME PLOCATIONS Smith, John B. Narayan, Ramesh K. English, Joyce A. Wong, Franklin T. Zelay, Alicia J. Jabbar, Ahmad V. Wallace, Jennifer S. Borg, James E. Bellaire Sugarland Houston Stafford 123456789 666884444 453453453 333445555 999887777 987987987 987654321 888665555 1 2 3 10 20 30 32.5 7.5 40.0 20.0 10.0 30.0 35.0 5.0 15.0 null ProductX ProductY ProductZ Computerization Reorganization Newbenefits Bellaire Sugarland Houston Stafford [ 그림 9.5] EMP_PROJ를 다르게 표현 (a) 그림 9.3(b)의 EMP_PROJ를 두 개의 릴레이션 스키마 (EMP_PROJ1과 EMP_LOCS)로 표현 (b) 그림 9.4의 EMP_PROJ 릴레이션을 EMP_PROJ1과 EMP_LOCS 릴레이션의 애트리뷰트들 상에 프로젝트 한 결과

[그림 9.6] EMP_PROJ1과 EMP_LOCS에 자연조인을 적용한 결과 (*는 가짜 투플을 나타냄) SSN PNUMBER HOURS PNAME PLOCATIONS ENAME 123456789 666884444 453453453 333445555 1 2 3 10 20 32.5 7.5 40.0 20.0 10.0 ProductX ProductY ProductZ Computerization Reorganization Bellaire Sugarland Houston Stafford Smith, John B. English, Joyce A. Wong, Franklin T. Narayan, Ramesh K. [그림 9.6] EMP_PROJ1과 EMP_LOCS에 자연조인을 적용한 결과 (*는 가짜 투플을 나타냄)

Problems in Relation DB Design (1) Careless Composition Repetition of Information space waste, complicates updating the database Insertion/deletion/update anomaly (1) Insertion Anomaly Null value is inserted Undefined primary key value indexing problems (2) Deletion Anomaly Triggered deletion of relations Desired deletion of a relation delete 할 때에 연관된 모든 것을 delete 해야 함. (3) Update Anomaly Partial update: inconsistent information 연관된 모든 tuple을 전부 update 해야 함.

Problems in Relation DB Design (2) Careless Decompostion Loss of information Goal of Decomposition Removal of anomaly No loss of Information Lossless Decomposion Need Normalization of relation schema

정규화 (Normalization)의 필요성 Normal Form A relation is said to be in a particular normal form if it satisfies a certain set of constraints Objectives No redundancy No Insertion/Deletion/Update Anomaly No loss of information Issues What attributes in each relation How do we decide that normal forms Categories universe of relations (normalized and unnormalized) 1NF relation (normalized relation) 2NF , 3NF, BCNF, 4NF, 5NF (PJ/NF) relations

9.2 함수적 종속성 함수적 종속성(FD)은 좋은 릴레이션 설계의 정형적 기준으로 사용된다. FD는 데이타 애트리뷰트들의 의미와 애트리뷰트들 간의 상호 관계로부터 유도되는 제약조건(constraints)의 일종이다. 9.2.1 함수의 종속성(functional dependency)의 정의 9.2.2 함수적 종속성의 추론 규칙 9.2.3 함수적 종속성 집합의 동등성 9.2.4 함수적 종속성의 최소집합

9.2.1 함수적 종속성의 정의 애트리뷰트들의 집합 X의 값이 애트리뷰트들의 집합 Y의 값을 유일하게(unique) 결정한다면 X는 Y를 함수적으로 결정한다(functionally determines)고 한다. X → Y로 표기; 그림 9.3의 릴레이션 스키마에서 처럼 그래픽하게도 표현할 수 있다. 모든 릴레이션 인스턴스 r(R)에 대하여 적용되는 제약조건이다. 임의의 릴레이션 인스턴스 r(R)에서의 임의의 두 투플 t1과 t2에 대해 t1[X] = t2[X]이면, t1[Y] = t2[Y]이다. 두 투플이 X에 대해 같은 값을 가질 때마다 Y에 대해서도 같은 값을 가져야 한다면 X → Y가 성립한다. FD는 애트리뷰트들에 대한 실세계 제약조건으로부터 유도된다.

9.2.1 함수적 종속성의 정의 (보충) Functional Dependency (FD) attribute X functionally determines attribute Y iff each X-value in R has associated with it precisely on Y-value in R any tuples t1, t2 in r(R) satisfy t1[Y] = t2[Y] if t1[X] = t2[X] => Denoted by X  Y

9.2.1 함수적 종속성의 정의 (cont.) FD 제약조건의 예제: FD는 스키마 R에 있는 애트리뷰트들의 특성이다. 주민등록번호는 사원의 이름을 결정한다. SSN → ENAME 프로젝트 번호는 프로젝트 이름과 위치를 결정한다. PNUMBER → {PNAME, PLOCATION} 사원의 주민등록번호와 프로젝트 번호는 그 사원이 일주일동안 그 프로젝트을 위해서 일하는 시간을 결정한다. {SSN, PNUMBER} → HOURS FD는 스키마 R에 있는 애트리뷰트들의 특성이다. FD는 모든 릴레이션 인스턴스 r(R)에서 성립해야 한다. K가 R의 키이면 K는 R의 모든 애트리뷰트들을 함수적으로 결정한다 (t1[K] = t2[K]인 서로 다른 두개의 투플이 존재하지 않기 때문).

9.2.1 함수적 종속성의 정의 (cont.) Normalization using Functional Dependency FD 관련 우선적으로 해야 할 내용 Need to determine all the Functional Dependencies (FDs) that hold in relation scheme Chosen a particular decomposition, need to determine those FDs that hold on the decomposed schemes Purpose of FD to test relations to see if they legal under a given set of FDs to specify constraints on the set of legal relations

9.2.2 함수적 종속성의 추론규칙 주어진 FD의 집합 F를 가지고, 성립하는 추가적인 FD를 추론할 수 있다. 암스트롱의 추론 규칙들: A1. (재귀성 규칙: Reflexivity) X → X이고 Y ⊆ X이면, X → Y이다. A2. (부가성 규칙: Augmentation) X → Y이면, XZ → YZ이다. (표기: XZ는 X∪Z를 의미) A3. (이행성 규칙: Transitivity) X → Y이고 Y → Z이면, X → Z이다. A1, A2, A3는 건전(sound)하고 완전한(complete) 추론 규칙 집합을 형성한다. 추가적인 유용한 추론 규칙들: (분해 규칙: Decomposition) X → YZ이면, X → Y이고 X → Z이다. (합집합 규칙: Union) X → Y이고 X → Z이면, X → YZ이다. (의사이행성 규칙: Pseudo-transitivity) X → Y이고 WY → Z이면, WX → Z이다. 위의 세 규칙 뿐만 아니라 다른 추론 규칙들도 A1, A2, A3로부터 추론 가능하다(완전성 특성).

9.2.2 함수적 종속성의 추론규칙 (cont.) F+ (F의 폐포 : Closure of F): Let F be a set of FDs, the set of all FD logically implied by F FD의 집합 F의 폐포는 F로부터 추론할 수 있는 모든 FD들의 집합 F+ 이다. A+ (A의 폐포: Closure of A) F에 대한 애트리뷰트들의 집합 A의 폐포는 A에 의해서 함수적으로 결정되는 모든 애트리뷰트들의 집합 A+ 이다. A+는 F에 포함된 FD들을 가지고 A1, A2, A3를 반복적으로 적용하여 구할 수 있다. Goal: Given a set of FDs, may find all implied FDs

9.2.2 함수적 종속성의 추론규칙 (cont.) Eg: input: R = (A, B, C, G, H, I) F = { A  B, A  C, CG  H, CG  I, B  H } Some members of F+ (1) A  H : (A  B and B  H (Transitivity)) (2) CG  HI : (CG  H and CG  I (Union)) (3) AG  I : ( A  C , CG  I (Pseudo-Transitivity)) 또는, (A  C: AG  CG (Augmentation), CG  I : AG  I (Transitivity))

9.2.2 함수적 종속성의 추론규칙 (cont.) Let A be a set of attributes. E.G. Closure of A, A+ Set of all attributes functionally determined by A. Algorithm result := X; while (change to result) do for each FD Y  Z in F do begin if result  Y then result := result  Z end; E.G. (AG)+ = ABCGHI A  B result = {A, G, B} A  C result = {A, G, B, C} CG  H result = {A, G, B, C, H} CG  I result = {A, G, B, C, H, I}

9.2.3 함수적 종속성 집합의 동등성 다음의 두 조건이 성립하면 FD의 두 집합 F와 G는 동등하다(equivalent)고 한다: F의 모든 FD가 G로부터 추론될 수 있고, G의 모든 FD가 F로 부터 추론될 수 있다. F+ = G+이면 F와 G는 동등하다. 정의: G의 모든 FD가 F로부터 추론될 수 있다면(즉, G+ Í F+), F가 G를 덮는다(cover). F가 G를 덮고 G가 F를 덮으면 F와 G는 동등하다. FD 집합의 동등성을 검사하는 알고리즘이 존재한다.

9.2.4 함수적 종속성의 최소집합 FD의 집합 F가 다음의 조건들을 만족하면, F는 최소집합(minimal set) 또는 최소 덮개(minimal cover)라고 한다: (1) F의 모든 종속성들이 오른쪽편에 하나의 애트리뷰트만을 가진다. (2) F로부터 어떠한 종속성을 제거하면, 나머지 FD의 집합은 F와 동등하지 않게된다. (3) F의 임의의 종속성 X → A를 Y → A (Y Ì X)로 대치하면, F와 동등하지 않게 된다. FD의 모든 집합은 동등한 최소집합(minimal set)을 가진다. 하나의 FD의 집합 F에 대하여 여러개의 동등한 최소집합이 존재한다. FD의 집합 F와 동등한 FD의 최소집합을 구하는 간단한(simple) 알고리즘은 없다. 최소집합의 개념은 릴레이션 설계 이론을 위해서 중요하다. (제 10 장 참조)

9.3 기본 키를 기반으로 한 정규형 9.3.1. 정규화 소개 9.3.2. 제1 정규형(First Normal Form ; 1NF) 9.3.3. 제2 정규형(Second Normal Form ; 2NF) 9.3.4. 제3 정규형(Third Normal Form ; 3NF)

9.3.1 정규화 소개 정규화(normalization): 불만족스러운 “나쁜” 릴레이션의 애트리뷰트들을 나누어서 더 작은 릴레이션으로 분해하는 과정 정규형(normal form): 특정 조건을 만족하는 릴레이션 스키마의 형태 제 1 정규형, 제 2 정규형, 제 3 정규형, BCNF는 릴레이션 스키마의 FD와 키에 기반하여 정의된다. 제 4 정규형은 키와 MVD에 기반하여 정의된다 (제 10 장 참조). 좋은 릴레이션 설계를 위해서는 정규형 이외에도 추가적인 특성이 필요 (즉, 무손실 조인과 종속성 보존; 제 10 장 참조)

Lossless Join Decomposition Let R1, … , Rn be a decomposition of R. If the join of r1(R1), … , rn(Rn) is equal to r(R), we call R1, … , Rn a lossless join decomposion of R. Otherwise, Lossy join. Eg: branch-scheme = (branch-name, loan-number, customer-name, amount) Lossy decomposition (branch-name, loan-number, amount) (amount, customer-name) Lossless decomposition (loan-number, customer-name, amount) (branch-name, loan-number ) Testing Lossless Join Decomposition Let R1 and R2 be a decomposition of R. This decomposition has a lossless join iff R1  R2  R1 - R2 or R1  R2  R2 - R1

Lossless Join Decomposition Theorem (Lossless Decomposition) Decomposition of R into R1 and R2 is lossless if at least one of the following FDs are in F+ R1  R2  R1 R1  R2  R2 Example: branch-scheme = (branch-name, loan-number, customer-name, amount) R1 = (branch-name, amount) R2 = (branch-name, loan-number, customer-name) R1  R2 = branch-name branch-name  branch-name, amount branch-name  R1  Lossless

Dependency Preserving Theorem (Dependency Preservation) F’ : union of all restrictions to Ri’s F1  F2  F3 …  Fn (Fi : restriction of F to Ri) Dependency Preserving Decomposition update 시 다른 릴레이션과의 join 없이, 자체의 FD 만 만족하면 correct 하도록 decompose 여러 relation에 걸쳐 functional dependency 정의될때 A decomposition is dependency preserving if F’+ = F+ Note that even if F’  F, it may be that F’+ = F+

Dependency Preserving Example: Decomposition of Branch-scheme into R1 thru R5 is dependency preserving R = (R1, … R5) Algorithm (testing dependency preserving) Compute F+; for each scheme R1 in R do begin Fi = Restriction of F+ to Ri; end; Computer F’+: if (F’+ = F+) then return (true) else return (false)

9.3.2 제 1 정규형(1NF) 제 1 정규형은 복합 애트리뷰트(composite attribute), 다치 애트리뷰트(multivalue attribute) 그리고 중첩 릴레이션(nested relation) 등 비원자적(non-atomic) 애트리뷰트들을 허용하지 않는다. 제 1 정규형은 릴레이션 정의의 일부분을 이룬다. First Normal Form (1NF) Relation all attributes have atomic values Problems of 1NF repetition of branch information and amount deletion/insertion/update anomaly occurs

{Bellaire, Sugarland, Houston} DEPARTMENT (a) DNAME DNUMBER DMGRSSN DLOCATIONS DEPARTMENT (b) DNAME DNUMBER DMGRSSN DLOCATIONS Research Administration Headquarters 4 5 1 333445555 987654321 888665555 {Bellaire, Sugarland, Houston} {Stafford} {Houston} DEPARTMENT (c) DNAME DNUMBER DMGRSSN DLOCATIONS Research Administration Headquarters 4 5 1 333445555 987654321 888665555 Bellaire Sugarland Houston Stafford [그림 9.8] 제 1 정규형으로 정규화 (a) 제 1 정규형이 아닌 릴레이션 스키마 (b) 릴레이션 인스턴스의 예 (c) 중복이 포함된 제 1 정규형 릴레이션

[그림 9.9] 중첩된 릴레이션을 제 1 정규형으로 정규화 (a) (b) EMP_PROJ EMP_PROJ SSN ENAME PROJS SSN ENAME PROJS PNUMBERS HOURS PNUMBERS HOURS 123456789 666884444 453453453 333445555 999887777 987987987 987654321 888665555 Smith, John B. Narayan, Joyce K. English, Joyce A. Wong, Franklin T. Zelaya, Alicia J. Jabbar, Ahmad V. Wallace, Jennifer S. Bong, James E. 1 2 3 10 20 30 32.5 7.5 40.0 20.0 10.0 30.0 35.0 5.0 15.0 null (c) EMP_PROJ1 SSN ENAME EMP_PROJ2 SSN PNUMBER HOURS [그림 9.9] 중첩된 릴레이션을 제 1 정규형으로 정규화 (a) 중첩 릴레이션 PROJS를 포함하는 릴레이션 EMP_PROJ의 스키마 (b) 각 튜플 안에 중첩 릴레이션을 포함하고 있는 릴레이션 EMP_PROJ 의 외연의 예 (c) 기본키를 복사함으로써 EMP_PROJ를 제 1 정규형 릴레이션들로 분해

9.3.3 제 2 정규형(2NF) 제 2 정규형은 완전 함수적 종속성 개념을 이용한다. 정의: 예제: (그림 9.3(b)) 완전 함수적 종속성(full functional dependency): FD Y → Z에서 Y의 어떤 애트리뷰트라도 제거하면 더이상 성립하지 않는 경우 예제: (그림 9.3(b)) {SSN, PNUMBER} → HOURS는 SSN → HOURS와 PNUMBER → HOURS가 성립하지 않기 때문에 완전 함수적 종속성이다. {SSN, PNUMBER} → ENAME은 SSN → ENAME이 성립하기 때문에 완전 함수적 종속성이 아니다 (이는 부분 함수 종속성(partial function dependency)이라고 부름).

Trivial Dependency X  Y is trivial if Y is a subset of X Partial Dependency Y is partially dependent on X if X  Y and there exist Z  X such that Z  Y. Eg: (branch-name, branch-address)  zip-code branch-address  zip-code

9.3.3 제 2 정규형(2NF) (cont.) Second Normal Form (2NF) Relation 릴레이션 스키마 R의 모든 비주요(non-prime) 애트리뷰트들이 기본키에 대해서 완전 함수적 종속이면 R은 제 2 정규형(2NF)을 갖는다고 한다. every nonprime attribute is fully dependent on a key each functional dependency X  Y holds at least one of the followings: it is a trivial dependency X is a superkey for R X is not contained in a candidate key R은 제 2 정규형 정규화 과정에 의해서 항상 제 2 정규형 릴레이션으로 분해될 수 있다.

[그림 9.10] 정규화 과정 (a) (a) EMP_PROJ를 제 2 정규형으로 정규화 2NF 정규화 EMP_PROJ SSN PNUMBER HOURS ENAME PNAME PLOCATIONS fd1 fd2 fd3 2NF 정규화 EP1 EP2 EP3 SSN PNUMBER HOURS SSN ENAME PNUMBER PNAME PLOCATIONS fd1 fd2 fd3 [그림 9.10] 정규화 과정 (a) EMP_PROJ를 제 2 정규형으로 정규화

9.3.4 제 3 정규형(3NF) 정의: 이행적 함수적 종속성(transitive functional dependency): 두 FD X → Z와 Z → Y에 의해서 추론될 수 있는 FD X → Y 예제: SSN → DMGRSSN은 SSN → DNUMBER과 DNUMBER → DMGRSSN이 성립하기 때문에 이행적 함수적 종속성이다. SSN → ENAME는 SSN → X이고 X → ENAME인 애트리뷰트 집합 X가 존재하지 않기 때문에 이행적 종속성이 아니다. 릴레이션 스키마 R이 제 2 정규형을 갖고 R의 어떤 비기본 애트리뷰트도 기본키에 대해서 이행적으로 종속되지 않으면 R은 제 3 정규형을 갖는다고 한다. R은 제 3 정규형 정규화 과정에 의해서 항상 제 3 정규형 릴레이션으로 분해될 수 있다.

[그림 9.10] 정규화 과정 (cont.) (b) (b) EMP_DEPT를 제 3 정규형으로 정규화 3NF 정규화 ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN 3NF 정규화 ED1 ED2 ENAME SSN BDATE ADDRESS DNUMBER DNUMBER DNAME DMGRSSN [그림 9.10] 정규화 과정 (cont.) (b) EMP_DEPT를 제 3 정규형으로 정규화

9.4 제 2 정규형과 제 3 정규형의 일반적인 정의 앞의 정의들은 기본키만을 고려하여 정규형을 정의하였다. 다음의 더 일반적인 정의는 여러개의 후보 키를 가진 릴레이션들을 고려한다. 릴레이션 스키마 R의 모든 비기본 애트리뷰트 A가 R의 모든 후보키에 완전 함수적 종속이면 R은 제 2 정규형(2NF)을 갖는다고 한다. 정의: 기본 애트리뷰트(prime attribute): 임의의 후보키 K의 멤버인 애트리뷰트 릴레이션 스키마 R의 수퍼키(superkey): R의 후보키를 포함한 R의 애트리뷰트들의 집합 S 릴레이션 스키마 R의 FD X → A가 성립할 때마다 (a) X 가 R의 수퍼키이거나 (b) A가 R의 기본 애트리뷰트이면 R은 제 3 정규형(3NF)을 갖는다고 한다. Boyce-Codd 정규형은 위의 조건중 (b)의 경우를 허락하지 않는 정규형을 의미한다.

(a) LOTS 릴레이션 스키마와 함수적 종속성 fd1부터 fd4 PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE TAX_RATE fd1 fd2 fd3 fd4 (b) LOTS1 PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE fd1 fd2 LOTS2 fd4 COUNTY_NAME TAX_RATE fd3 [그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화 (a) LOTS 릴레이션 스키마와 함수적 종속성 fd1부터 fd4 (b) LOTS를 제 2 정규형 릴레이션 LOTS1과 LOTS2로 분해

[그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화(cont.) (a) LOTS1A LOTS1B PROPERTY_ID# COUNTY_NAME LOT# AREA AREA PRICE fd1 fd4 fd2 (b) LOTS 1NF LOTS1 LOTS2 2NF LOTS1A LOTS1B LOTS 3NF [그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화(cont.) (c) LOTS1를 제 3 정규형 릴레이션 LOTS1A과 LOTS1B로 분해 (d) LOTS의 정규화 요약

9.5 BCNF (Boyce-Codd Normal Form) 릴레이션 스키마 R에서 성립하는 임의의 FD X → A에서 X가 R의 수퍼키이면 R은 Boyce-Codd 정규형(BCNF)을 갖는다고 한다. 각 정규형은 그의 선행 정규형보다 더 엄격한 조건을 갖는다. 즉, 모든 제 2 정규형 릴레이션은 제 1 정규형을 갖는다. 모든 제 3 정규형 릴레이션은 제 2 정규형을 갖는다. 모든 BCNF 릴레이션은 제 3 정규형을 갖는다. 제 3 정규형에는 속하나 BCNF에는 속하지 않는 릴레이션이 존재한다. 관계 데이타베이스 설계의 목표는 각 릴레이션이 BCNF(또는 제 3 정규형)를 갖게 하는 것이다. “좋은” 관계형 데이타베이스의 릴레이션을 설계하기 위해서는 추가적인 특성이 만족되어야 한다. 무손실 조인(lossless join) 특성 종속성 보존(dependency preservation) 특성

(a) BCNF로 정규화하는 과정에서 종속성 fd2가 없어지는 경우 LOTS1A PROPERTY_ID# COUNTY_NAME LOT# AREA fd1 fd2 fd5 BCNF 정규화 LOTS1AX LOTS1AY PROPERTY_ID# AREA LOT# AREA COUNTY_NAME (b) R A B C fd1 fd1 [그림 9.12] BCNF (a) BCNF로 정규화하는 과정에서 종속성 fd2가 없어지는 경우 (b) 제 3 정규형이지만 BCNF가 아닌 릴레이션 R

Boyce-Codd Normal Form (BCNF) One of the most desirable normal form Each functional dependency X  Y holds at least one of the followings: it is a trivial dependency X is a superkey for R Problems there is redundancy in BCNF relation dependency preserving이 보장되지 않음 Fouth Normal Form (4NF) Each multi-valued functional dependency X  Y in F holds at least one of the followings: it is a trivial multi-valued dependency 5th Normal Form (5NF) Each join dependencies in D of the form *(R1,R2, …, Rn) holds at least one of the followings: *(R1,R2, …, Rn) is a trivial join dependency Every Ri is a superkey for R