[데이터베이스] CH7. Relational Database Design(Normalization)

0. Intro

1. Features of Good Relational Design

• 우리가 instructor 과 department를 in_dep이라는 table로 합쳤다고 생각해보자.
  이러면 같은 dept 정보가 계속 반복해서 들어가고, 만약 학과가 새로 만들어 졌을 때 교수자가 아직 없다면 null값으로 넣어 추가해야 하는 문제도 발생한다. 심지어 id가 not null이면 이것도 불가능 하다.

• 즉, 무조건 table을 합친다고 좋은 것이 아니다.

  Combined schema without repetition

• 그러나 합친다고 또 무조건 중복이 생기는 건 아니다.
• sec_class와 section을 합칠 경우 중복되는 정보가 없게 된다.

2. Decomposition : table 쪼개기.

우리가 앞서 본 in_dep schema의 문제를 해결하려면 table을 두 개로 쪼개야 한다. (instructor과 department)
근데 또 모든 decomposition이 좋은 건 아니다.

employee(ID, name, street, city, salary) 를
employee1(ID, name)
employee2(name, street, city, salary)로 쪼개개 되면

만약 동명이인이 있을 경우 join할 때 문제가 발생한다.

동명이인있으면 정보 일부가 날라가 원래의 table로 복원이 불가하게 되는데 이를 lossy decomposition이라고 한다.

(데이터 양(tuple)은 증가하는데 information은 누락(less)된다)

Lossless Decomposition

-> Table을 다시 합쳤을 때 정보 누락이 없도록 하는 decomposition (<-> lossy)

3. Normalization Theory

: relation schema R이 지금 현재 'good' 한 형태인지 decide하는 이론.
만약 good form 이 아니라면, decompose해서 relation을 쪼개야 한다. (당연히 쪼갠 후에 relation은 good form이어야 하고, lossless decomposition이어야함)

크게 두 개로 나누어 살펴볼 것 !

1. Functional dependencies
2. Multivalued dependencies

1. Funtional dependency

• 우리가 살아가는 세상의 데이터에는 여러가지 제한 (constraints, rule)이 존재한다.

• 이러한 모든 real-world constraints를 만족하는 relation의 instance를 legal instance 라고 부른다.
  데이터베이스의 legal instance는 relation의 instance가 모두 legal instance일 때를 말한다.

• functional dependency : legal relations의 constraints로 인해 특정 attributes의 집합이 다른 set of attribute를 유일하게 결정하도록 해야한다.
  말이 어렵긴 한데, 그냥 key 개념을 일반화 한 것
  legal instance를 만들기 위해 조건을 추가함으로 인해 특정 attribute간의 종속성이 생성된다.

relation R에 a, b attribute가 있을 때,

functional dependency a -> b는 a가 결정됨에 따라 b가 결정될 때에 어떤 legal relations r(R)에 대해서 hold on R 된다.
즉 앞의 것이 UNIQUE 할 때 뒤의 것이 하나로 결정되는 경우를 functional dependency 가 HOLD 된다고 말한다.

Closure of a set of functional dependencies

만약 A->B, B->C라는 Functional dependency가 있다면 우린 A->C도 hold됨을 알 수 있다. 이런 식으로 funstional dependencies 의 집합 F가 주어졌을 때, F로 부터 추론해서 얻어 낼 수 있는 모든 functional dependency를 closure of F라고 부른다.

F+ 라고 표기한다.

Keys and Functional Dependency

• K가 relation schema R의 superkey라고 하면, K->R이다. (반대도 성립한다.)

• K가 candidate key라면

  1. K->R
  2. a ⊂ K, a->R 인 또다른 a 는 존재하지 않음

• fd는 우리가 superkey로는 표현하지 못했던 constraints를 표현할 수 있다.

Use of Functional Dependencies

1. 주어진 functional dependencies에서 relation이 legal한지 확인한다.

   • 만약 functional dependencies F 아래에서, relation instance r이 legal하다면 r satisfies F라고 말한다.

2. legal relations의 집합에 constraints를 지정하기 위해 사용한다.

   • 만약 R의 모든 legal relation이 funtional dependencies F를 만족한다면 F holds on R 라고 말한다.

   satisfy는 특정 instance가 fd를 만족하는 것, hold는 스키마 자체가 legal한 것.
   hold하지 않더라도 우연히 satisfy는 할 수 있음

Trivial Functional Dependencies

• 당연한 사실들 (자명한 것들)

  ex) ID , NAME -> ID
  NAME -> NAME

• 보통 a->b 에서 b⊆a 일 때 trivial 하다고 말함

Lossless Decomposition

• functional dependency를 이용해 decomposition이 lossless 한지 아닌지를 확인할 수 있다.

  R = (R1, R2)가 있을 때, R을 R1과 R2로 decomposition할 때, 다음과 같은 종속성을 적어도 하나 F+가 가지고 있어야 lossless decomposition이라고 할 수 있다.

1. R1 ∩ R2 -> R1
2. R1 ∩ R2 -> R2

위 functional dependency는 loseless join decomposition을 위해 필요한 조건이다.
위 dependency는 모든 constraints가 functional dependencies인 경우에만 필요한 조건이다.

예를 보자.

R=(A, B, C)
F = {A->B, B->C}

R1 = (A, B), R2= (B, C)
R1 ∩ R2 = {B} AND B->BC

R1 = (A,B) , R2 = (A, C)
R1 ∩ R2 = {A} AND A -> AB

참고로, AB = {A, B}라고 보면 됨

위 조건을 만족하니까 둘 다 올바른 Decomposition!

Dependency Preservation

: dependency constraints가 지켜졌는지 아닌지를 매번 join을 해봐야 아는지, 아니면 바로 알 수 있는지 여부가 이것!

• 디비가 업데이트 될 때 마다 fd constraints를 테스트하려면 비용이 많이 들 수 있다.
  • 따라서 제약 조건을 효율적으로 테스트 할 수 있게 디비를 설계하는 것이 좋다
  • 하나의 relation만 고려해 fd constraint를 테스트할 수 있다면 비용이 적게 든다.
  • 그러나 decomposing 과정에서 카르테지안 곱을 사용하지 않으면 테스트를 할 수 없게 되기도 함

functional dependency를 확인하기 위해 join을 해야 하는 등, 어렵게 만드는 decomposition의 경우, NOT dependency preserving 이라고 부른다.

예를 들어서 dept_advisor(s_ID, i_ID, department_name) 이 있다고 치자.
여기에 fd는
i_id -> dept_name
s_id, dept_name -> i_id

이 경우 instructor가 dept_advisor relation에 참여할 때마다 department_name을 계속 반복해서 적어줘야 한다.
이 중복성 문제를 해결하려면 decomposing을 해줘야 하는데, 이 경우 어떻게 나눠도 s_id, dept_name -> i_id를 포함할 수 없으므로 이 decomposition은 not dependency preserving 하다고 말할 수 있다.

1. Normal Forms

1. BCNF (Boyce-Codd Normal Form)

a -> b 일 때

1. a -> b가 trivial 하다
2. a가 R의 superkey이다.

F+의 모든 functional dependencies가 다음과 같은 조건을 만족하는 경우 relation schema R이 BCNF를 만족한다고 할 수 있다.

예를 들어 in_dep(ID, name, salary, dept_name, building, budget)
이 있고
dept_name -> building , budget 이라는 fd가 있을 경우
hold를 하긴 하는데, dept_name이 superkey는 아니므로 BCNF 가 아니다.

만약 Violation of BCNF가 일어날 경우, Decompose를 해줘야 한다. 어떻게?

1. a ∪ B
2. R - (b-a)

이렇게.

위의 예로 다시 해보면

a = dept_name
b= building, budget

이니까

a ∪ B = (dept_name, building, budget)
R - (b-a) = (ID, name, dept_name, salary)

가 된다.

BCNF and Dependency Preservation

-> BCNF와 dependency preserving decomposition을 언제나 동시에 만족 시킬 수는 없다

dept_advisor(s_ID, i_ID, department_name)
i_id -> dept_name
s_id, dept_name -> i_id

가 있을 때,
i_id가 superkey가 아니므로 decomposition을 해야한다.

근데 이 아이들은 3개가 다 쓰였으므로 어떻게 쪼개도 dependency 유지가 불가능하다.
따라서 이 decomposition 은 not be dependency preserving 이다.

2. 3NF (Third Normal Form)

• 3NF는 조금 더 완화된 형태의 normal form이다.

1. a -> b가 trivial 하다
2. a가 R의 superkey이다.
3. b-a 에 있는 attribute가 R의 candidate key에 포함이 된다.

이 셋 중 하나 만족시키면 3NF!

dept_advisor(s_ID, i_ID, department_name)
i_id -> dept_name
s_id, dept_name -> i_id

다시 이걸 보자.
s_id, dept_name은 superkey이다.
i_id는 superkey는 아니지만,
{dept_name} - {i_id} = {dept_name} 이고 dept_name은 candidate key에 포함되므로
3NF는 만족하게 된다.

Redundancy in 3NF

• repetition of information
• need to use null values

Comparison of BCNF and 3NF

• 3NF는 언제나 lossless 하고 dependency preserving한 3NF design을 얻을 수 있다.
• 그러나 데이터 간의 의미있는 관계 중 일부를 나타내려면 null 값을 사용해야 할 수도 있고, 정보의 repetition이 일어나기도 한다.

Goals of Normalization

• R 이라는 relation schema와 F 라는 Functional dependencies가 있을 때, 이 R이 "good" form인지 판별하고, 아니라면 relation을 decompose한다.
• 이 때 각 relation schema는 good form이어야 하며, lossless decomposition이어야 하고, dependency preserving 해야 한다.

3. Higher Normal Form

4NF(Fourth Normal Form)

2. Funtional Dependency Theory

1. Closure of a set of functional dependency

• F로부터 추론될 수 있는 모든 functional dependencies를 closure라고 한다.

Armstrong's Axioms

1. Reflexive rule : b ⊆ a 이면 a->b
2. Augmentation rule : a->b이면 ra -> rb
3. Transitivity rule : a->b이고 b->c이면 a->c

Sound : 도출해낸 문장이 전부 true인 경우(반례X 전부다 찾은 건 아닐 수 있음)

Complete : true인 문장은 전부 도출할 수 있는 경우 (전부다 찾았지만 아닌 것도 섞여있을 수 있음)

Addition rules

1. Union Rule : a->b , a->r 이면 a->br
2. Decomposition rule : a->br 이면 a->b 그리고 a->r
3. Pseudotransitivity rule : a->b이고 rb->q 이면 ar -> q 이다.
   얘네는 암스트롱 어쩌구에서 추론할 수 있음

F+ 를 구하는 방법

F에서 시작해서 reflexivity, augmentation rules, combined using transitivy 과정을 거쳐 F+에 추가해나간다.

2. Closure of Attribute Sets

Attribute sets의 closure 구하기

result := a;
while (changes to result) do
    for each b->r in F do
      begin
           if b ⊆ result then result := result ∪ r
      end

Usees of Attribute Closure

1. Testing for superkey
   -> a가 superkey라면 a+는 R 의 모든 attributes를 가지고 있어야 한다.
2. Testing functional dependencies
   -> fd a->b가 hold한지 보려면 b ⊆ a+를 만족하는지 확인해보면 된다.
   -> 매우 쉽고 빠르고 유용한 방법.
3. computing closure of F
   -> r⊆R이 있을 때 closure r+를 찾고 S ⊆ r+에 대해 r->S를 output으로 내보낸다.

3. Canonical Cover

• relation schema에 functional dependency F가 있다고 하자. 사용자가 relation 을 업데이트 할 때마다 디비 시스템은 이 사항이 F의 모든 dependency를 충족하는지 확인해야 한다.
• 만약 violate한다면 update는 roll back되어야 한다.
• 우리는 주어진 set와 같은 closure를 가진, 더 단순화 된 functional dependency를 검사함으로서 드는 비용을 줄일 수 있다.
• 이 단순화 된 functional dependency 를 canonical cover라고 부른다

Extraneous Attributes

: 없어도 무방한 functional dependency의 attribute
-> 이걸 다 없애야 canonical cover를 찾을 수 있음

1. remove left side -> stronger
   AB -> C에서 A->C로 줄이면 좀 더 강력해짐. A만 있어도 C를 알 수 있음

• A ∈ a 이고 F 가 논리적으로 (F - {a-b}) ∪ {(a - A)->b}를 추론할 수 있을 경우 A는 extraneous 하다.

2. remove right side -> weaker

• A ∈ b 이고 F 가 논리적으로 (F - {a-b}) ∪ {(a->(b-A)}를 추론할 수 있을 경우 B는 extraneous 하다.
  AB -> CD에서 AB->C로 줄이면 약해짐. AB가 있어도 D를 알 수 없음

Testing Extraneous

1. A ∈ b 일 때 extraneous 인가

   • F'= (F - {a-b}) ∪ {(a - A)->b}
   • F' 안의 a+가 A를 포함하는지 확인해보고 그렇다면 A 는 extraneous 하다.

2. A ∈ a 일 때 extraneous 인가

   • r = a - {A} 라고 하자. r->B가 F로부터 추론 가능한지 체크한다.
   • r+ 를 계산해서 이게 b의 모든 attribute를 포함한다면 A는 extraneous 하다.

   예를 들어보자

   F={AB->CD, A->E, E->C}
   C를 Check 해봅시다.

   F' = {AB->D, A->E, E->C}
   이고 이 CLOUSER는 ABCDE이므로 CD를 포함한다.
   따라서 C는 EXTRANEOUS 하다.

   즉, C가 없어도 다 유추가 가능해서 필요 없는 것.

Canonical Cover

F의 canonical cover는 Fc이다.

• F는 Fc에 있는 모든 dependency를 추론해낼 수 있다
• Fc는 F에 있는 모든 dependency를 추론해 낼 수 있따.
• Fc에는 extraneous attribute가 있으면 안된다.
• Fc의 functional dependency의 왼쪽 side는 unique해야 한다.
  a1-> b1 , a2->b2 일 때 a1 = a2 이면 안됨.

canonical cover를 구해보자

1. F에 있는 dependency를 union rule을 활용해 a1->b1, a1->b2 를 a1->b1b2 꼴로 바꿔준다.
2. a->b 에 있는 extraneous attribute를 찾아 없애준다.
3. 반복한다.

4. Dependency Preservation

• 하나의 relation 안에서 FD가 확인 가능하면 DEPENDENCY Preserving 한 것.

• *(F1 U F2 U F3 ...U Fn) + = F+

• 위의 정의대로 dp를 테스트 하려면 지수함수적 시간이 소요된다.
  (만약 preserve하지 않는다면 violation of functional dependency 를 확인하기 위해 join을 계속 해야함)

• 그러나 restrinction의 모든 functional dependency는 오직 하나의 relation schema의 attribute를 포함하고 있으므로 하나의 relation을 확인함으로서 dependency check를 할 수 있다. (다항시간에 가능)

Testing for Dependency Preservation

result = a
repeat 
    for each Ri in the decomposition
        t = (result ∩ Ri)+ ∩ Ri
        result = result U t
until (result does not change)

만약 result가 b의 모든 attribute를 가지고 ㅣㅇㅆ다면 functional dependency a->b는 preserved한 것.

3. Algorithm for Decomposition Using Functional Dependencies

2. Testing for BCNF

a->b가 violation of BCNF를 야기하는지 확인하기 위해서는

1. a+ 계산
2. 이 a+가 R의 모든 attribute를 포함하는지, 즉 R의 superkey인지 확인

superkey라면 BCNF를 만족하는 것이다.

Testing decomposition for BCNF

1. 각각의 relation에 대해서 fd를 찾아봄
2. 각 leftside의 attribute의 closure가 decomposition relation의 모든 attribute를 갖고 있는지 확인.

result := {R};
done := fasle;
compute F+;
while(not done) do
    if(BCNF가 아닌 schema Ri가 result에 있을 경우)
        then begin
            nontribial functional dependency, Ri를 hold, F+에 속하지 않은 a->b, a ∩ b = ∮일 때
            result := (result - Ri) ∪ (Ri - b) ∪ (a,b);
        end
    end done := true;

4. Third Normal Form

• BCNF는 dependency preserving을 유지하지 못한다.

• efficient checking for FD violation on updates is important

  따라서 weaker normal form 인 3NF 사용

  • 조금의 중복 허용

  • join 없이 fd 확인 가능

  • 항상 lossless-join,, dependency-preserving decomposition

  • 대충 NP hard 문제임.

5. Design Goal

목표는 BCNF, Lossless join, Dependency preservation
만족 못한다면 둘 중 하나 포기
dependency preservation , BCNF
대신 3NF 쓴다.

sql에서는 고려하지 않기 때문에 설계할 때 고려해야 함.

4. Multivalued Dependencies

-> a 에 따라 b의 값이 정해지긴 하는데, b가 multivalue인 경우를 multivalued dependency라고 함
이를

a->->b

로 표기함.

Use of Multivalued Dependency

multialed dependency는 두가지 방법으로 쓴다.

1. relation에서 주어진 fdp, mdp 하에 legal한지 결정한다
2. legal relation 하에서 constraints를 지정한다.

mdp 의 정의에 따르면 우리는
a->b이면 a->->b
라는 규칙을 도출할 수 있다. 즉 모든 fdp는 mdp이다.

4NF

다음과 같은 조건 중 하나 이상을 만족하면 됨

• a->->b is trivial
• a is superke for schema R

4NF이면 BCNF이기도 함.

First Normal Form

• 모든 attributes의 domain 이 atomic해야 함.

Overall DB Design Process

1. ER Diagram을 table로 변환할 때 schema R이 생성될 수 있다.
2. R은 모든 attribute를 포함하는 single relation의 nomalization의 결과일 수 있따.
3. R는 우리가 test/conver normalform하는 ad hoc design의 relation의 결과일 수 ㅣㅇㅆ따

뭐라는거ㅑㅇ

ER model and Normalization

Denormalization for Performance

performance 때문에 non-normalized schema를 사용하고 싶을 수 있음.

대안 1. 걍 deormalized relation 사용

1. faster lookup 가능
2. extra space and execution time for updates 필요
3. extra coding work for programmer and possibility of error in extra code

대안 2. view 사용

-> 장점과 단점 위와 같음. 그러나 추가 코딩 작업과 에러 발생은 피할 수 있음