함수적 종속성과 정규화

(1)

1

 9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침

 9.2 함수적 종속성 (functional dependencies, FDs)

 9.3 기본 키를 기반으로 한 정규형

 9.4 제 s2 정규형과 제 3 정규형의 일반적인 정의

 9.5 BCNF (Boyce-Codd Normal Form)

9 장 . 관계 데이타베이스의 함수적 종속성과 정규화 9 장 . 관계 데이타베이스의

함수적 종속성과 정규화

(2)

 관계형 데이타베이스 설계란 무엇인가 ?

– “ 좋은” 릴레이션 스키마를 생성하기 위하여 애트리뷰트들을 그룹별로 모으는 과정

 릴레이션 스키마의 두 가지 수준

– 논리적인 “사용자 뷰 (user view)” 수준

– 저장이 되는 “기본 릴레이션 (base relation)” 수준

 설계는 주로 기본 릴레이션과 관련된다 .

 “ 좋은” 기본 릴레이션에 대한 기준은 ?

 먼저 좋은 릴레이션 설계에 관한 개괄적인 지침을 논한 후 , 함수적 종속 성과 정규형의 형식적인 개념에 관해 논한다 .

– 1NF ( 제 1 정규형 ) – 2NF ( 제 2 정규형 ) – 3NF ( 제 3 정규형 )

– BCNF (Boyce-Codd 정규형 )

9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침

9.1 릴레이션 스키마를 설계하는

몇 가지 개략적인 지침

(3)

3

 이외의 다른 종속성 , 정규형 , 릴레이션 설계 알고리즘은 제 10 장에서 논한다 .

 9.1.1 릴레이션 애트리뷰트들의 의미

 9.1.2 투플에서 중복된 정보와 이상 (anomaly)

 9.1.3 투플의 널값

 9.1.4 가짜 투플 (spurious tuples)

9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침 (cont.) 9.1 릴레이션 스키마를 설계하는

몇 가지 개략적인 지침 (cont.)

(4)

 비공식적으로 표현하자면 , 각 투플은 하나의 엔티티 또는 관계 인스턴스 를 표현해야 한다 .

 다른 엔티티들 (EMPLOYEE, DEPARTMENT, PROJECT) 의 애트리뷰트 들은 하나의 릴레이션에 혼합되면 안된다 .

 다른 엔티티를 참조하기 위해서는 외래키만을 사용하여야 한다 .

9.1.1 릴레이션 애트리뷰트들의 의미

(5)

5

 하나의 릴레이션에 하나 이상의 엔티티의 애트리뷰트들을 혼합하는 것은 여러 가지 문제를 야기시킨다 .

 정보가 중복 저장되고 , 저장 공간을 낭비하게 된다 .

 갱신 이상의 종류

– 삽입 이상 (insertion anomalies) – 삭제 이상 (deletion anomalies) – 수정 이상 (modification anomalies)

9.1.2 투플에서 중복된 정보와 이상 (anomaly)

(6)

[ 그림 9.1] COMPANY 관계 데이타베이스 스키마를 단순화시킨 버전

ENAME SSN BDATE ADDRESS DNUMBER

DNAME DNUMBER DMGRSSN DLOCATIONS

DNUMBER DLOCATIONS PNAME PNUMBER PLOCATIONS DNUM

SSN PNUMBER HOURS EMPLOYEE

DEPARTMENT

DEPT_LOCATIONS

PROJECT

WORKS_ON 기본키

기본키

외래키

기본키

외래키

외래키 외래키

기본키 기본키

(7)

7

[ 그림 9.2] 그림 9.1 의 스키마의 릴레이션들의 예

ENAME SSN BDATE ADDRESS DNUMBER

EMPLOYEE

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 5 4 4 5 5 4 1

DNAME DNUMBER DMGRSSN DEPARTMENT

Research Administration Headquarters

5 4 1

333445555 987654321 888665555

DNUMBER DLOCATIONS DEPT_LOCATIONS

1 4 5 5 5

Houston Stafford Bellaire Sugarland Houston

(8)

[ 그림 9.2] 그림 9.1 의 스키마의 릴레이션들의 예 (cont.)

PNAME PNUMBER PLOCATIONS DNUM SSN PNUMBER HOURS

PROJECT WORKS_ON

123456789 123456789 666884444 453453453 453453453 333445555 333445555 333445555 333445555 999887777 999887777 987987987 987987987 987654321 987654321 888665555

1 2 3 1 2 2 3 10 20 30 10 10 30 30 20 20

32.5 7.5 40.0 20.0 20.0 10.0 10.0 10.0 10.0 30.0 10.0 35.0 5.0 20.0 15.0 null

ProductX ProductY ProductZ Computerization Reorganization Newbenefits

1 2 3 10 20 30

Bellaire Sugarland Houston Stafford Houston Stafford

5 5 5 4 1 4

(9)

9

[ 그림 9.3] 두 개의 릴레이션 스키마와 함수적 종속성 (a) EMP_DEPT 릴레이션 스키마

(b) EMP_PROJ 릴레이션 스키마

ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN EMP_DEPT

SSN PNUMBER HOURS ENAME PNAME PLOCATIONS EMP_PROJ

fd1 fd2 fd3

(a)

(b)

(10)

[ 그림 9.4] 그림 9.2 의 릴레이션들을 자연조인한 결과인 그림 9.3 의 스키마에 대한 릴레이션의 예

Smith, John B.

Wong, Franklin T.

Zelaya, Alicia J.

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 5 4 4 5 5 4 1

Research Research Administration Administration Research Research Administration Headquarters

333445555 333445555 987654321 987654321 333445555 333445555 987654321 888665555

SSN PNUMBER HOURS ENAME PNAME PLOCATIONS

EMP_PROJ

123456789 123456789 666884444 453453453 453453453 333445555 333445555 333445555 333445555 999887777 999887777 987987987 987987987 987654321 987654321 888665555

1 2 3 1 2 2 3 10 20 30 10 10 30 30 20 20

Smith, John B.

Narayan, Ramesh K.

English, Joyce A.

Wong, Franklin T.

Zelaya, Alicia J.

Jabbar, Ahmad V.

Bong, James E.

32.5 7.5 40.0 20.0 20.0 10.0 10.0 10.0 10.0 30.0 10.0 35.0 5.0 20.0 15.0 null

ProductX ProductY ProductZ ProductX ProductY ProductY ProductZ Computerization Reorganization Newbenefits Computerization Computerization Newbenefits Newbenefits Reorganization Reorganization

Bellaire Sugarland Houston Bellaire Sugarland Sugarland Houston Stafford Houston Stafford Stafford Stafford Stafford Stafford Houston Houston

(11)

11

 릴레이션은 가능하다면 투플이 널 값을 가지지 않도록 설계해야 한다 .

 자주 널 값을 갖는 애트리뷰트들은 별개의 릴레이션으로 만든다 .

9.1.3 투플의 널값

(12)

 잘못된 관계 데이타베이스 설계는 일부 조인 연산들이 틀린 결과를 생성 하게 한다 .

 조인 연산의 결과가 의미있게 하기 위해서는 “무손실 조인 (lossless join)”

특성이 필요하다 .

 릴레이션들은 무손실 조인 조건을 만족하도록 설계되어야 한다 .

 더 자세한 것은 제 10 장에서 논한다 .

9.1.4. 가짜 투플 (spurious tuples)

(13)

13

[ 그림 9.5] EMP_PROJ 를 다르게 표현

(a) 그림 9.3(b) 의 EMP_PROJ 를 두 개의 릴레이션 스키마 (EMP_PROJ1 과 EMP_LOCS) 로 표현

(b) 그림 9.4 의 EMP_PROJ 릴레이션을 EMP_PROJ1 과 EMP_LOCS 릴레이션의 애트리뷰트들 상에 프로젝트 한 결과

ENAME PLOCATIONS EMP_LOCS

기본키

SSN PNUMBER EMP_PROJ1

기본키

HOURS PNAME PLOCATIONS

ENAME PLOCATIONS EMP_LOCS

HOURS PNAME PLOCATIONS Smith, John B.

Smith, John B.

Narayan, Ramesh K.

English, Joyce A.

Wong, Franklin T.

Zelay, Alicia J.

Jabbar, Ahmad V.

Borg, James E.

Bellaire Sugarland Houston Bellaire Sugarland Sugarland Houston Stafford Stafford Stafford Stafford Houston Houston

123456789 123456789 666884444 453453453 453453453 333445555 333445555 333445555 333445555 999887777 999887777 987987987 987987987 987654321 987654321 888665555

1 2 3 1 2 2 3 10 20 30 10 10 30 30 20 20

32.5 7.5 40.0 20.0 20.0 10.0 10.0 10.0 10.0 30.0 10.0 35.0 5.0 20.0 15.0 null

ProductX ProductY ProductZ ProductX ProductY ProductY ProductZ Computerization Reorganization Newbenefits Computerization Computerization Newbenefits Newbenefits Reorganization Reorganization

Bellaire Sugarland Houston Bellaire Sugarland Sugarland Houston Stafford Houston Stafford Stafford Stafford Stafford Stafford Houston Houston

(a)

(b)

(14)

[ 그림 9.6] EMP_PROJ1 과 EMP_LOCS 에 자연조인을 적용한 결과 (* 는 가짜 투플을 나타냄 )

SSN PNUMBER HOURS PNAME PLOCATIONS

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 32.5 7.5 7.5 7.5 40.0 40.0 20.0 20.0 20.0 20.0 20.0 10.0 10.0 10.0 10.0 10.0 10.0 10.0 10.0

ProductX ProductX ProductY ProductY ProductY ProductZ ProductZ ProductX ProductX ProductY ProductY ProductY ProductY ProductY ProductY ProductZ ProductZ Computerization Computerization Reorganization

Bellaire Bellaire Sugarland Sugarland Sugarland Houston Houston Bellaire Bellaire Sugarland Sugarland Sugarland Sugarland Sugarland Sugarland Houston Houston Stafford Houston Houston

ENAME

Smith, John B.

English, Joyce A.

Smith, John B.

English, Joyce A.

Wong, Franklin T.

Narayan, Ramesh K.

Wong, Franklin T.

Smith, John B.

English, Joyce A.

Smith, John B.

English, Joyce A.

Wong, Franklin T.

Smith, John B.

English, Joyce A.

Wong, Franklin T.

Narayan, Ramesh K.

Wong, Franklin T.

Narayan, Ramesh K.

(15)

15

 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 (1)

(16)

 Careless Decompostion – Loss of information

– Goal of Decomposition

• Removal of anomaly

• No loss of Information

– Lossless Decomposion

• Need Normalization of relation schema

Problems in Relation DB Design (2)

(17)

17

 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

정규화 (Normalization) 의 필요성

(18)

 함수적 종속성 (FD) 은 좋은 릴레이션 설계의 정형적 기준으로 사용된다 .

 FD 와 키는 릴레이션의 정규형을 정의하기 위해 사용된다 .

 FD 는 데이타 애트리뷰트들의 의미와 애트리뷰트들 간의 상호 관계로부 터 유도되는 제약조건 (constraints) 의 일종이다 .

 9.2.1 함수의 종속성 (functional dependency) 의 정의

 9.2.2 함수적 종속성의 추론 규칙

 9.2.3 함수적 종속성 집합의 동등성

 9.2.4 함수적 종속성의 최소집합

9.2 함수적 종속성

(19)

19

 애트리뷰트들의 집합 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 함수적 종속성의 정의

(20)

 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 함수적 종속성의 정의 ( 보충 )

(21)

21

 FD 제약조건의 예제 :

– 주민등록번호는 사원의 이름을 결정한다 . SSN → ENAME

– 프로젝트 번호는 프로젝트 이름과 위치를 결정한다 . PNUMBER → {PNAME, PLOCATION}

– 사원의 주민등록번호와 프로젝트 번호는 그 사원이 일주일동안 그 프로젝트을 위해서 일하는 시간을 결정한다 .

{SSN, PNUMBER} → HOURS

 FD 는 스키마 R 에 있는 애트리뷰트들의 특성이다 .

 FD 는 모든 릴레이션 인스턴스 r(R) 에서 성립해야 한다 .

 K 가 R 의 키이면 K 는 R 의 모든 애트리뷰트들을 함수적으로 결정한다 (t₁[K] = t₂[K] 인 서로 다른 두개의 투플이 존재하지 않기 때문 ).

9.2.1 함수적 종속성의 정의 (cont.)

(22)

 Normalization using Functional Dependency

 FD 관련 우선적으로 해야 할 내용

– Need to determine all the Functional Dependencies (FDs) that hold in r elation scheme

– Chosen a particular decomposition, need to determine those FDs that h old 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.1 함수적 종속성의 정의 (cont.)

(23)

23

 주어진 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 함수적 종속성의 추론규칙

(24)

 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.)

(25)

25

 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.)

(26)

 Let A be a set of attributes.

– 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.2 함수적 종속성의 추론규칙 (cont.)

(27)

27

 다음의 두 조건이 성립하면 FD 의 두 집합 F 와 G 는 동등하다 (equivale nt) 고 한다 :

– 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.3 함수적 종속성 집합의 동등성

(28)

 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.2.4 함수적 종속성의 최소집합

(29)

29

 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 기본 키를 기반으로 한 정규형

(30)

 정규화 (normalization): 불만족스러운 “나쁜” 릴레이션의 애트리뷰트들을 나누어서 더 작은 릴레이션으로 분해하는 과정

 정규형 (normal form): 특정 조건을 만족하는 릴레이션 스키마의 형태

 제 1 정규형 , 제 2 정규형 , 제 3 정규형 , BCNF 는 릴레이션 스키마의 FD 와 키에 기반하여 정의된다 .

 제 4 정규형은 키와 MVD 에 기반하여 정의된다 ( 제 10 장 참조 ).

 좋은 릴레이션 설계를 위해서는 정규형 이외에도 추가적인 특성이 필요 ( 즉 , 무손실 조인과 종속성 보존 ; 제 10 장 참조 )

9.3.1 정규화 소개

(31)

31

 Let R¹, … , Rⁿ be a decomposition of R.

If the join of r

¹

(R

¹

), … , r

ⁿ

(R

ⁿ

) is equal to r(R),

we call R

¹

, … , R

ⁿ

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 R

¹

and R

2

be a decomposition of R.

– This decomposition has a lossless join

iff R

1

 R

²

 R

¹

- R

2

or R

1

 R

²

 R

²

- R

1

Lossless Join Decomposition

(32)

 Theorem (Lossless Decomposition)

– Decomposition of R into R1 and R2 is lossless if at least one of the following F Ds are in F+

• R¹  R²  R¹

• R¹  R²  R²

– Example: branch-scheme = (branch-name,

loan-number, customer-name, amount)

R¹ = (branch-name, amount)

R² = (branch-name, loan-number, customer-name)

R¹  R² = branch-name

branch-name  branch-name, amount branch-name  R¹

 Lossless

Lossless Join Decomposition

(33)

33



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

(34)



Example: Decomposition of Branch-scheme into R1 thru R5 is dep endency 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)

Dependency Preserving

(35)

35

 제 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

9.3.2 제 1 정규형 (1NF)

(36)

[ 그림 9.8] 제 1 정규형으로 정규화

(a) 제 1 정규형이 아닌 릴레이션 스키마 (b) 릴레이션 인스턴스의 예

(c) 중복이 포함된 제 1 정규형 릴레이션

DNAME DNUMBER DMGRSSN DLOCATIONS

DNAME DNUMBER DEPARTMENT

Research Administration Headquarters

4 5 1

333445555 987654321 888665555

{Bellaire, Sugarland, Houston}

{Stafford}

{Houston}

DMGRSSN DLOCATIONS

DNAME DNUMBER DEPARTMENT

Research Research Research Administration Headquarters

4 4 4 5 1

333445555 333445555 333445555 987654321 888665555

Bellaire Sugarland

Houston Stafford Houston DMGRSSN DLOCATIONS

(a)

(b)

(c)

(37)

37

[ 그림 9.9] 중첩된 릴레이션을 제 1 정규형으로 정규화

(a) 중첩 릴레이션 PROJS 를 포함하는 릴레이션 EMP_PROJ 의 스키마 (b) 각 튜플 안에 중첩 릴레이션을 포함하고 있는 릴레이션 EMP_PROJ 의 외연의 예

(c) 기본키를 복사함으로써 EMP_PROJ 를 제 1 정규형 릴레이션들로 분해

SSN ENAME PROJS

PNUMBERS HOURS

EMP_PROJ

SSN ENAME PROJS

PNUMBERS HOURS

EMP_PROJ

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.

Bong, James E.

1 2 3 1 2 2 3 10 20 30 10 10 30 30 20 20

32.5 7.5 40.0 20.0 20.0 10.0 10.0 10.0 10.0 30.0 10.0 35.0 5.0 20.0 15.0 null

SSN ENAME EMP_PROJ1

HOURS

(a) (b)

(c)

(38)

 제 2 정규형은 완전 함수적 종속성 개념을 이용한다 .

 정의 :

– 완전 함수적 종속성 (full functional dependency): FD Y → Z 에서 Y 의 어떤 애 트리뷰트라도 제거하면 더이상 성립하지 않는 경우

 예제 : ( 그림 9.3(b))

– {SSN, PNUMBER} → HOURS 는 SSN → HOURS 와 PNUMBER → HOUR S 가 성립하지 않기 때문에 완전 함수적 종속성이다 .

– {SSN, PNUMBER} → ENAME 은 SSN → ENAME 이 성립하기 때문에 완전 함수적 종속성이 아니다 ( 이는 부분 함수 종속성 (partial function dependency) 이라고 부름 ).

9.3.3 제 2 정규형 (2NF)

(39)

39



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 s uch that Z  Y.

– Eg: (branch-name, branch-address)  zip-code

• branch-address  zip-code

(40)

 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 follo wings:

• it is a trivial dependency

• X is a superkey for R

• X is not contained in a candidate key

 R 은 제 2 정규형 정규화 과정에 의해서 항상 제 2 정규형 릴레이션으로 분해될 수 있다 .

9.3.3 제 2 정규형 (2NF) (cont.)

(41)

41

[ 그림 9.10] 정규화 과정

(a) EMP_PROJ 를 제 2 정규형으로 정규화

SSN PNUMBER HOURS ENAME PNAME PLOCATIONS EMP_PROJ

fd1 fd2 fd3

2NF 정규화

SSN PNUMBER HOURS SSN ENAME PNUMBER PNAME PLOCATIONS

fd1 fd2 fd3

EP1 EP2 EP3

(a)

(42)

 정의 :

– 이행적 함수적 종속성 (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.3.4 제 3 정규형 (3NF)

(43)

43

[ 그림 9.10] 정규화 과정 (cont.)

(b) EMP_DEPT를 제 3 정규형으로 정규화

3NF 정규화

ENAME SSN BDATE ADDRESS DNUMBER DNAME DMGRSSN EMP_DEPT

ENAME SSN BDATE ADDRESS DNUMBER ED1

DNUMBER DNAME DMGRSSN ED2

(b)

(44)

 앞의 정의들은 기본키만을 고려하여 정규형을 정의하였다 .

 다음의 더 일반적인 정의는 여러개의 후보 키를 가진 릴레이션들을 고려 한다 .

 릴레이션 스키마 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) 의 경우를 허락하지 않는 정규형을 의 미한다 .

9.4 제 2 정규형과 제 3 정규형의 일반적인 정의

일반적인 정의

(45)

45

[ 그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화

(a) LOTS 릴레이션 스키마와 함수적 종속성 fd1 부터 fd4

(b) LOTS 를 제 2 정규형 릴레이션 LOTS1 과 LOTS2 로 분해

PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE TAX_RATE LOTS

fd1 fd2

fd3

fd4

PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE fd1

fd2

fd4 COUNTY_NAME TAX_RATE

fd3

LOTS1

LOTS2

(a)

(b)

(46)

PROPERTY_ID# COUNTY_NAME LOT# AREA PRICE fd1

fd2

fd4 AREA

[ 그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화 (cont.)

(c) LOTS1 를 제 3 정규형 릴레이션 LOTS1A 과 LOTS1B 로 분해 (d) LOTS 의 정규화 요약

LOTS

LOTS1 LOTS2

LOTS LOTS1A LOTS1B

1NF

2NF

3NF

(b)

(47)

47

 릴레이션 스키마 R 에서 성립하는 임의의 FD X → A 에서 X 가 R 의 수퍼키이면 R 은 Boyce-Codd 정규형 (BCNF) 을 갖는다고 한다 .

 각 정규형은 그의 선행 정규형보다 더 엄격한 조건을 갖는다 . 즉 ,

– 모든 제 2 정규형 릴레이션은 제 1 정규형을 갖는다 . – 모든 제 3 정규형 릴레이션은 제 2 정규형을 갖는다 . – 모든 BCNF 릴레이션은 제 3 정규형을 갖는다 .

 제 3 정규형에는 속하나 BCNF 에는 속하지 않는 릴레이션이 존재한다 .

 관계 데이타베이스 설계의 목표는 각 릴레이션이 BCNF( 또는 제 3 정 규형 ) 를 갖게 하는 것이다 .

 “ 좋은” 관계형 데이타베이스의 릴레이션을 설계하기 위해서는 추가적인 특성이 만족되어야 한다 .

– 무손실 조인 (lossless join) 특성

– 종속성 보존 (dependency preservation) 특성

9.5 BCNF (Boyce-Codd Normal Form)

(48)

[ 그림 9.12] BCNF

(a) BCNF로 정규화하는 과정에서 종속성 fd2 가 없어지는 경우 (b) 제 3 정규형이지만 BCNF 가 아닌 릴레이션 R

fd1 fd2

fd5

BCNF 정규화

PROPERTY_ID# AREA LOT# AREA COUNTY_NAME

LOTS1AX LOTS1AY

C R

B A

fd1

(b)

(49)

 Boyce-Codd Normal Form (BCNF) 49

– One of the most desirable normal form

– Each functional dependency X  Y holds at least one of the followings:

• it is a trivial dependency

– 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 f ollowings:

• 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 th e followings:

• *(R1,R2, …, Rn) is a trivial join dependency

• Every Ri is a superkey for R