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

Presentation on theme: "9 장. 관계 데이터베이스의 함수적 종속성과 정규화"— Presentation transcript:

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

2 9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침
관계형 데이타베이스 설계란 무엇인가? 관계 데이터 베이스의 스키마를 결정하는 것 “좋은” 릴레이션 스키마를 생성하기 위하여 애트리뷰트들을 그룹별로 모으는 과정 함수적 종속성의 개념 정규형, 무손실 조인 특성, 종속성 보존 특성

3 9.1 릴레이션 스키마를 설계하는 몇 가지 개략적인 지침(cont.) 9.1.1 릴레이션 애트리뷰트들의 의미
9.1.2 투플에서 중복된 정보와 갱신 이상 9.1.3 투플의 널값 9.1.4 가짜 투플의 생성

4 9.1.1 릴레이션 애트리뷰트들의 의미 의미가 쉽게 전달되도록 릴레이션 스키마를 설계한다.
애트리뷰트들 사이에 어떤 의미적인 상호 관계가 있을 때 애트리뷰트들을 하나의 릴레이션 스키마로 묶는다. 각 투플은 하나의 엔티티 또는 관계 인스턴스를 표현해야 한다. 다른 엔티티들의 애트리뷰트들은 하나의 릴레이션에 혼합되면 안된다.

5 [그림 9.1] 단순화된 COMPANY 관계 데이타베이스 스키마

6 [그림 9.2] 그림 9.1의 관계 데이터베이스 스키마를 위한 데이터베이스 상태의 예
[그림 9.2] 그림 9.1의 관계 데이터베이스 스키마를 위한 데이터베이스 상태의 예

7 9.1.2 투플에서 중복된 정보와 갱신 이상 하나의 릴레이션에 하나 이상의 엔티티의 애트리뷰트들을 혼합하는 것은 여러 가지 문제를 야기시킨다. => 정보의 중복, 저장 공간의 낭비 및 이상(anomaly) 문제 등. 이상(anomaly)의 종류 삽입 이상 (insertion anomalies) 삭제 이상 (deletion anomalies) 갱신 이상 (modification anomalies) 릴레이션에서 삽입, 삭제, 또는 갱신 이상이 생기지 않도록 기본 릴레이션 스키마를 설계

8 [그림 9.3] 갱신 이상이 발생하는 두 릴레이션 스키마 (a) EMP_DEPT, (b) EMP_PROJ

9 [그림 9.4] 그림 9.2의 릴레이션들을 자연 조인한 결과인 EMP_DEPT와 EMP_PROJ에 대한 상태들의 예

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

11 9.1.4. 가짜 투플의 생성 잘못된 관계 데이타베이스 설계는 일부 조인 연산들이 틀린 결과를 생성하게 한다.
조인 연산의 결과가 의미있게 하기 위해서는 “무손실 조인(lossless join)” 특성이 필요하다.릴레이션들은 무손실 조인 조건을 만족하도록 설계되어야 한다. 기본키나 외래키 애트리뷰트를 가지고 동등 조건으로 조인할 수 있는 릴레이션 스키마를 설계한다 (다른 엔티티를 참조하기 위해서는 외래키만을 사용하여야 한다).

12 [ 그림 9.5] 그림 9.3(b)의 EMP_PROJ에 대한 나쁜 설계
(a) 두 개의 릴레이션 스키마 EMP_PROJ1과 EMP_LOCS (b) 그림 9.4의 EMP_PROJ의 외연을 릴레이션 EMP_LOCS와 EMP_PROJ1의 애트리뷰트들 상에 프로젝트 한 결과

13 [그림 9. 6] 그림 9. 5의 EMP_PROJ1과 EMP_LOCS에서 점선 위의 투플들에 대해 자연 조인을 적용한 결과 (

14 9.2 함수적 종속성 9.2.1 함수적 종속성(functional dependency)의 정의
9.2.2 함수적 종속성의 추론 규칙 9.2.3 함수적 종속성 집합의 동등성 9.2.4 함수적 종속성의 최소집합

15 9.2.1 함수적 종속성의 정의 릴레이션 스키마 R = {A1, A2, …, An}의 애트리뷰트들의 부분 집합인 X 와 Y 사이의 함수적 종속성 (X → Y로 표기): 임의의 릴레이션 인스턴스 r(R)에서의 임의의 두 투플 t1과 t2에 대해 t1[X] = t2[X]이면, t1[Y] = t2[Y]. 즉,애트리뷰트들의 집합 X의 값이 애트리뷰트들의 집합 Y의 값을 유일하게(unique) 결정 => 두 투플이 X에 대해 같은 값을 가지면 Y에 대해서도 같은 값을 가짐 이때 Y가 X에 함수적으로 종속된다고 함

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

17 9.2.2 함수적 종속성의 추론규칙 주어진 FD의 집합 F를 가지고, 성립하는 추가적인 FD를 추론할 수 있다.
암스트롱의 추론 규칙들: A1. (재귀성 규칙) Y ⊆ X이면, X → Y이다. A2. (부가성 규칙) X → Y이면, XZ → YZ이다. A3. (이행성 규칙) X → Y이고 Y → Z이면, X → Z이다. 추가적인 유용한 추론 규칙들: (분해 규칙) X → YZ이면, X → Y이고 X → Z이다. (합집합 규칙) X → Y이고 X → Z이면, X → YZ이다. (의사이행성 규칙) X → Y이고 WY → Z이면, WX → Z이다.

18 9.2.2 함수적 종속성의 추론규칙 (cont.) A1, A2, A3는 건전(sound)하고 완전한(complete) 추론 규칙 집합을 형성한다. 위의 세 규칙 뿐만 아니라 다른 추론 규칙들도 A1, A2, A3로부터 추론 가능하다(완전성 특성). FD의 집합 F의 폐포(closure)는 F로부터 추론할 수 있는 모든 FD들의 집합 F+ 이다. F에 대한 애트리뷰트들의 집합 X의 폐포는 X에 의해서 함수적으로 결정되는 모든 애트리뷰트들의 집합 X+ 이다. X+는 F에 포함된 FD들을 가지고 A1, A2, A3를 반복적으로 적용하여 구할 수 있다.

19 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 집합의 동등성을 검사하는 알고리즘이 존재한다.

20 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와 동등하지 않게 된다.

21 FD의 모든 집합은 동등한 최소집합(minimal set)을 가진다.
하나의 FD의 집합 F에 대하여 여러개의 동등한 최소집합이 존재한다. FD의 집합 F와 동등한 FD의 최소집합을 구하는 간단한(simple) 알고리즘은 없다. 최소집합의 개념은 릴레이션 설계 이론을 위해서 중요하다. (제 10 장 참조)

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

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

24 9.3.2 제 1 정규형(1NF) 제 1 정규형은 복합 애트리뷰트(composite attribute), 다치 애트리뷰트(multivalue attribute) 그리고 중첩 릴레이션(nested relation) 등 비원자적(non-atomic) 애트리뷰트들을 허용하지 않는다. 다치 애트리뷰트 및 다치의 복합 애트리뷰트 (중첩 릴레이션)의 제거 제 1 정규형은 릴레이션 정의의 일부분을 이룬다.

25 [그림 9.8] 제 1 정규형으로 정규화 (a) 제 1 정규형이 아닌 릴레이션 스키마
[그림 9.8] 제 1 정규형으로 정규화 (a) 제 1 정규형이 아닌 릴레이션 스키마 (b) 릴레이션 DEPARTMENT 외연의 예 (c) 중복이 포함된 동일 릴레이션의 제 1 정규형 버전

26 [그림 9.9] 중첩된 릴레이션을 제 1 정규형으로 정규화
[그림 9.9] 중첩된 릴레이션을 제 1 정규형으로 정규화 (a) 중첩 릴레이션 PROJS를 포함하는 릴레이션 EMP_PROJ의 스키마 (b) 각 투플 안에 중첩 릴레이션을 포함하고 있는 릴레이션 EMP_PROJ의 외연의 예 (c) 기본키를 복사함으로써 EMP_PROJ를 EMP_PROJ1과 EMP_PROJ2 릴레이션들로 분해

27 9.3.3 제 2 정규형(2NF) 제 2 정규형은 FD와 기본키 개념을 이용한다.
주요 애트리뷰트(prime attribute): 기본키 K의 멤버인 애트리뷰트 완전 함수적 종속성(full functional dependency): FD X → Y에서 X의 어떤 애트리뷰트라도 제거하면 더 이상 함수적 종속성이 성립하지 않는 경우 예제 (p334 그림 9.3(b)): {SSN, PNUMBER} → HOURS는 SSN → HOURS와 PNUMBER → HOURS가 성립하지 않기 때문에 완전 함수적 종속성이다.

28 9.3.3 제 2 정규형(2NF) (cont.) {SSN, PNUMBER} → ENAME은 SSN → ENAME이 성립하기 때문에 완전 함수적 종속성이 아니다 (이는 부분 함수 종속성(partial function dependency)이라고 부름). 릴레이션 스키마 R의 모든 비주요 애트리뷰트(즉, 키에 속하지 않는 애트리뷰트)들이 기본키에 대해서 완전 함수적 종속이면 R은 제 2 정규형(2NF)을 갖는다고 한다. R은 제 2 정규형 정규화 과정에 의해서 항상 제 2 정규형 릴레이션으로 분해될 수 있다.

29 [그림 9.10] 제 2 정규형과 제 3 정규형으로 정규화 EMP_PROJ를 제 2 정규형으로 정규화
[그림 9.10] 제 2 정규형과 제 3 정규형으로 정규화 EMP_PROJ를 제 2 정규형으로 정규화 EMP_DEPT를 제 3 정규형으로 정규화

30 9.3.4 제 3 정규형(3NF) 이행적 함수적 종속성(transitive functional dependency): 두 FD Y → X와 X → Z에 의해서 추론 될 수 있는 FD Y → Z. 여기서 X는 키의 부분 집합이 아니어야 함. 예제: SSN → DMGRSSN은 SSN → DNUMBER와 DNUMBER → DMGRSSN이 성립하기 때문에 이행적 함수적 종속성이다. SSN → ENAME는 SSN → X이고 X → ENAME인 애트리뷰트 집합 X가 존재하지 않기 때문에 이행적 종속성이 아니다.

31 릴레이션 스키마 R이 제 2 정규형을 갖고 R의 어떤 비주요 애트리뷰트도 기본키에 대해서 이행적으로 종속되지 않으면 R은 제 3 정규형을 갖는다고 한다.

32 9.4 제 2 정규형과 제 3 정규형의 일반적인 정의 앞의 정의들은 기본키만을 고려하여 정규형을 정의하였다.
다음의 더 일반적인 정의는 여러개의 후보 키를 가진 릴레이션들을 고려한다. 릴레이션 스키마 R의 모든 비주요 애트리뷰트 A가 R의 모든 후보키에 완전 함수적 종속이면 R은 제 2 정규형(2NF)을 갖는다고 한다.

33 정의: 주요 애트리뷰트(prime attribute): 임의의 후보키 K의 멤버인 애트리뷰트 릴레이션 스키마 R의 수퍼키(superkey): R의 후보키를 포함한 R의 애트리뷰트들의 집합 S 릴레이션 스키마 R의 FD X → A가 성립할 때마다 (a) X 가 R의 수퍼키이거나 (b) A가 R의 주요 애트리뷰트이면 R은 제 3 정규형(3NF)을 갖는다고 한다. Boyce-Codd 정규형은 위의 조건중 (b)의 경우를 허락하지 않는 정규형을 의미한다.

34 [그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화 (a) LOTS 릴레이션 스키마와 함수적 종속성 FD1부터 FD4
[그림 9.11] 제 2 정규형과 제 3 정규형으로 정규화 (a) LOTS 릴레이션 스키마와 함수적 종속성 FD1부터 FD4 (b) LOTS를 제 2 정규형 릴레이션 LOTS1과 LOTS2로 분해 (c) LOTS1을 제 3 정규형 릴레이션 LOTS1A와 LOTS1B로 분해 (d) LOTS의 정규화 요약

35 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에는 속하지 않는 릴레이션이 존재한다.

36 관계 데이타베이스 설계의 목표는 각 릴레이션이 BCNF(또는 제 3 정규형)를 갖게 하는 것이다.
“좋은” 관계형 데이타베이스의 릴레이션을 설계하기 위해서는 추가적인 특성이 만족되어야 한다(제 10 장 참조). 무손실 조인(lossless join) 특성 종속성 보존(dependency preservation) 특성 제 10 장에서 논할 다른 정규형은 다음과 같다: 제 4 정규형 (다중치 종속성에 기반)

37 (a) LOTS1A의 BCNF로 정규화하는 과정에서 종속성
FD2가 없어지는 경우 (b) 함수적 종속성과 관련된 의미; 제 3 정규형이지만 BCNF가 아니다