[데베시] 14강

Relation Decomposition

1) universal relation schema에서 시작 : relation schema R = {A1, ... An} 은 DB에 필요한 모든 attribute로 구성 -> attribute name은 unique

2) R을 relation schema D = {R1, R2 ... Rm}으로 분해

  - R의 subset이 아닌 Ri는 없음

  - R의 모든 attribute는 적어도 하나 이상의 Ri에 속해 있어야 한다

  - 각각의 Ri는 BCNF이거나 3NF이어야 한다.

  - 위의 조건을 만족할 때 D는 R의 decomposition이라고 한다.

 

Insufficiency of Normal Forms(노멀 폼의 불완전성)

- 노멀 폼으로 나타나기만 하면 되는 것이 아님

- 어떤 relation schema가 오직 2개의 attribute만 가지면 무조건 BCNF

-> 즉, 모든 relation schema가 오직 2개의 attribute만 가지게 한다면 D를 만들 수 있음 -> 그러나 그렇게 만들게 되면 가짜 튜플(spurious tuple)을 만드는 문제가 생김

-> 즉 좋은 relational databases의 추가적인 특성

    : (1) Lossless join property(튜플 누락/가짜 튜플 발생 x), (2) Dependency preservation property(함수 종속 보존)

 

Dependency preservation

- F : Relation schema R에 정의된 FD의 집합

- dependency preservation = Decomposition D는 종속을 보존해야 함.

- 독립적인 릴레이션 Ri가 가지고 있는 함수적 종속 Fi를 Union(합) 했을 때 F랑 동일(equivalent)해야 함

- 공식적인 정의

   - Projection of F on Ri, πRi(F) = F+에 있는 함수적 종속(X -> Y)의 set 중에서 Ri의 attribute에 X U Y가 포함된 것

   - Decomposition D가 dependency-preserving하다 = ((πR1(F) U πR2(F) ... πRm(F))+ = F+

- Dependency preservation은 D에 대한 제약조건이므로 반드시 지켜져야 함.

- 쪼갠 후에 이 조건을 체크하기 위해선 쪼개진 relation들을 JOIN해서 확인해야 함. -> 효율적이지 않음. -> 쪼개기 전부터 이 조건에 맞게 쪼개자.

ex)

3NF를 FD5을 분리하기 위해 BCNF Normalize를 하면 더 좋은 NF는 될 수 있지만 FD2의 Dependency-preservation을 만족하지 못하므로 확인하기 위해선 LOTS1AX와 LOTS1AY를 항상 JOIN해서 확인해봐야 함 -> 효율성이 떨어짐.

-> 선택 : 중복이 더 없는 BCNF를 사용할 것인가, 중복은 있더라도 Dependency Presevation이 만족된 3NF를 사용할 것인가 선택이 필요.

 

Minimal cover G of F

- F하고 G는 equivalent한 FD의 set, 즉, G의 어떠한 FD라도 제거하면 더이상 F랑 equivalent하지 않는다면 G는 F의 minimal cover.

- F에서 G를 찾는 방법

   - F의 모든 FD를 canonical form(우변에 하나의 attribute만 남기는 형태)으로 바꾼다. ex) {X,Y} -> {A, B} 일때 {X,Y} -> A, {X, Y} -> B로 나눔.

   - 좌변의 attribute 중에서 제거되더라도 FD를 만족하는 attribute가 있다면 그것은 제거한다. ex) XY -> A인데 X->A라면 Y는 제거

   - 중복된 FD를 F에서 제거

 

Relational Decomposition을 Dependency Preservation을 만족하는 3NF로 변환하기

(1) F의 minimal cover G를 찾는다.

(2) G에서 좌변에 있는 임의의 X에 대한 모든 X->Ai를 구해서 {X U {A1} U {A2} ... U {Ak}}를 하나의 relation schema로 -> X가 key이고 나머지 모든 변수는 X가 함수적으로 종속하는 relation  -> 3NF

(3) 2를 마치고 남아있는 Attribute(즉, 어떠한 FD에 속하지 않은 Attribute)가 있다면 해당하는 Attribute를 하나의 relation schema로

 

Lossless Join Property (= non-additive join property)

- 쪼개진 relation들을 JOIN의 결과로 어떠한 spurious tuple도 생성되지 않음을 보장하는 property

- Decomposition D = {R1, R2, ... Rm}이 losslesss join property를 만족한다면

  -> 모든 relation instance r에 대해 *(πR1(r), ... , πRm(r)) = r (r는 F를 만족하는 R의 인스턴스)

 

Relational Decomposition을 Lossless Join Property를 만족하는 BCNF로 변환하기

(1) Set D := {R};

(2) while(D에 BCNF를 만족하지 않는 relation schema Q가 있다면)

     do{

          D에서 BCNF가 아닌 Q를 고름

          Q에서 BCNF를 위반하는 X->Y를 찾는다.

          D에 있는 Q를 제거하고 (Q-Y)와 (X U Y)로 대체한다.

     }

-> 이렇게 하면 Lossless Join Property를 만족함.

- Decomposition D = {R1, R2}이 Lossless Join Property를 만족한다

  = FD((R1 ∩ R2)->(R1-R2)) is in F+ or FD((R1 ∩ R2)->(R2-R1)) is in F+

-> 의미 (R1 ∩ R2)는 최소 R1과 R2 둘 중 하나에서 기본키이다. (그럼 기본키가 아닌 쪽은 외래키)

-> (Q-Y)와 (X U Y)로 나누면 뒤쪽은 기본키, 앞쪽은 외래키를 갖는 table이 생긴다. => lossless join

-> Decomposition D를 lossless join property를 만족하는 Ri로 나눴을 때 Ri를 lossless join property를 만족하게 쪼갠 Di가 있으면 D2 = (D-Ri) U Di도 lossless join property를 만족.

 

ex) BCNF, Dependency-preserving, Lossless join을 모두 만족하지 못하는 경우도 있다.

그냥 두면 Dependency-preserving & Lossless Join은 만족 그러나 BCNF가 아님

BCNF를 만족하게 쪼개면 Lossless Join은 만족 그러나 Dependency-preserving은 아님.

-> 이러한 경우를 제외한 대부분의 경우는 3가지 조건을 다 만족할 수 있다.

 

Relational Decomposition을 Dependency Preservation + Lossless Join을 만족하는 3NF로 변환하기

(1) F의 minimal cover G를 찾는다.

(2) G에서 좌변에 있는 임의의 X에 대한 모든 X->Ai를 구해서 {X U {A1} U {A2} ... U {Ak}}를 하나의 relation schema로 -> X가 key이고 나머지 모든 변수는 X가 함수적으로 종속하는 relation  -> 3NF

(3) D에 속하는 어떤 relation schema도 R의 key를 포함하지 않는다면 D에 R의 key를 구성하는 attribute가 포함된 새로운 relation을 하나 더 추가하라

 

key를 찾는 알고리즘