Computer Science Basics/데이터베이스

DB - 5. Normalization

타자치는 문돌이

|  ID  |     Name       | dept_name | salary | building | budget |
|------|----------------|-----------|--------|----------|--------|
|  1   |   Jane Smith   |  Biology  | 50000  |   LSB    | 80000  |
|  2   |    John Doe    |  CS       | 60000  |   LSB    | 120000 |
|  3   |  Sarah Johnson |  Physics  | 55000  |   PSB    | 100000 |
|  4   |  Michael Brown |  Chemistry| 52000  |   CSB    | 90000  |
|  5   |  Emily Wilson  |  Math     | 62000  |   MSB    | 110000 |
|  6   |    David Lee   |  Economics| 65000  |   ESB    | 130000 |
|  7   |  Lisa Anderson |  History  | 58000  |   HSB    | 95000  |

이것은 in_dep Relation이다. (instructor와 department를 Natural Join 한 모양이다)
DB에 이렇게 저장하면

department의 정보가 반복되어 나타난다.
Instructor가 아직 없는 Department를 추가하면 NULL Value를 추가해야 한다.

는 문제점이 나타난다.

그렇다면 좋은 Relational Design이란 어떤 것일까?

Decomposition

in_dept의 중복 문제를 해결하기 위해서는 in_dept Schema를 instructor Schema와 department Schema로 나눠야 한다.

Schema를 쪼개는 작업을 Decomposition이라고 한다.

그러나 무작정 표를 쪼갠다고 다 좋은 것이 아니다.
Schema $employee(ID, name, street, city, salary)$ 가 있다고 하자.
이 Schema를 $employee1(ID, name)$ 와 $employee2(name, street, city, salary)$ 로 나눠보자.
이때 동명이인이 있다면 두 Schema를 합해 기존의 $employee$로 다시 합할 수 없다.
이렇게 Schema $R$을 Schema $R\_1$, Schema $R\_2$로 Decompose하면 데이터가 유실되는 경우를 Lossy Decomposition이라고 한다.

Decompose를 해도 데이터의 유실이 없는 바람직한 경우를 Lossless Decomposition이라고 한다.

Normalization Theory

Relation이 바람직하지 않은 모양이면 Decompose 해 좋은 모양으로 만들어야 한다.
Relation이 좋은 모양인지 아닌지 판단하기 위해 도입된 이론이 Normalization Theory이다.

Normalization Theory에 따르면 Relation $R$이 좋지 않은 형태이면,

바람직한 모양의 Relation으로 Decompose가 가능하고
그 Decomposition은 Lossless Decomposition이다.

이 이론은 Functional Dependency 개념과 Multivalued Dependency 개념을 바탕으로 한다.

Functional Dependency

실제 세상의 데이터는 다양한 제한과 규칙이 존재한다.
이러한 Real World Constraints를 모두 만족하는 Relation의 Instance를 Legal Instance라고 한다.

Table $R$의 속성 부분집합 $A$와 $B$에 대해, $A$의 한 값이 $B$에 속한 오직 하나의 값에만 매핑되는 경우에 $B$는 $A$에 Functionally Dependent하다고 한다.
다른 말로, $A$가 결정되면 $B$가 결정될 때, "Functional Dependency $A \rightarrow B$가 Legal Relationship $r(R)$ 에 대해 hold on 된다"고 할 수 있다.

$student(\underline{id}, name, age, dept)$ 를 예로 들면, $id$가 주어지면 $name$, $age$, $dept$가 결정된다.
이때 Functional Dependency $id \rightarrow name, age, dept$가 성립한다.

Keys

$K$가 Relation Schema $R$의 Superkey라면,

$K \rightarrow R$이다.

$K$가 Relation Schema $R$의 Candidate Key라면

$K \rightarrow R$이고,
$\alpha \subset K,, \alpha \rightarrow R$인 다른 $\alpha$는 없다.

Functional Dependency를 사용하면 Superkey로만은 표현하지 못한 관계를 표현할 수 있다.

$\alpha^{+}$를 구하는 알고리즘은 다음과 같다.

result := a;
while (changes to result) do
    for each b -> c in F do
        begin
            if (b is subset of result)
                result := union(result, c)
        end

$R = {A, B, C, G, H, I}$
$F = {A \rightarrow B, A \rightarrow C, CG \rightarrow H, CG \rightarrow I, B \rightarrow H }$
에 대해 $(AG)^{+}$는
result = $AG$
result = $ABCG$ ($A \rightarrow C$ and $A \rightarrow B$)
result = $ABCGH$ ($CG \rightarrow H$ and $CG \subseteq AGBC$)
result = $ABCGHI$ ($CG \rightarrow I$ and $CG \subseteq AGBCH$)

Attribute Closure의 용도는 다음과 같다.

Superkey Test : $\alpha^{+}$가 $R$의 모든 Attribute를 가지고 있으면 Superkey이다.
Functional Dependency Test : $\beta \subseteq \alpha^{+}$면 $\alpha \rightarrow \beta$이다.
Closure of $F$ 계산 : 각각의 $\gamma \subseteq R$에 대해 $\gamma^{+}$를 찾고, $\gamma \rightarrow S$를 도출한다.

Canonical Cover

Relation Schema의 Functional Dependency $F$가 있다고 가정하자.
Relation을 Update할 때마다 데이터베이스 시스템은 Update가 Functional Dependency를 훼손하지는 않는지 검사해야 한다. Functional Dependency를 훼손한다면 롤백을 통해 Update를 취소해야 한다.
이때 이 Violation 검사의 비용을 줄이기 위해 주어진 집합과 같은 Closure의 단순화된 Functional Dependency 집합을 사용할 수 있다.
이때 사용할 수 있는 단순화된 집합을 Canonical Cover라고 한다.

Canonical Cover를 찾기 위해선 먼저 Extraneous Attribute를 찾아야 한다.

Extraneous Attribute

Functional Dependency $F$에서 $F^{+}$를 변경하지 않고 Attribute를 삭제할 수 있다면, 그 Attribute를 "Extraneous 하다"라고 한다.

$F$의 원소 $\alpha \rightarrow \beta$에 대해

좌측 Attribute 제거 : $\alpha$의 $A$는
- $A \in \alpha$이고,
- $F$가 $(F - {\alpha \rightarrow \beta }) \cup { (\alpha - A) \rightarrow \beta}$를 논리적으로 암시할 때,
  Extraneous 하다.

Functional Dependency에서 좌측의 Attribute를 제거하면 더 강한 Constraints가 만들어진다.

$F = {AB \rightarrow C, A \rightarrow D, D \rightarrow C }$에서 $A \rightarrow D \rightarrow C$가 유도된다.
$AB \rightarrow C$에서 $B$를 없애면,
더 강한 Constraint $A \rightarrow C$를 얻을 수 있다.
$A \rightarrow C$는 $AB \rightarrow C$ 를 암시하지만,
$AB \rightarrow C$는 $A \rightarrow B$를 암시하지는 못하므로 $A \rightarrow B$가 더 강한 Constraints라고 할 수 있다.
여기서 우리는 $B$가 $AB \rightarrow C$에서 Extraneous 한 Attribute라고 한다.

우측 Attribute 제거 : $\beta$의 $A$는
- $A \in \beta$이고,
- $F$가 $(F - {\alpha \rightarrow \beta }) \cup { \alpha \rightarrow (\beta - A) }$를 논리적으로 암시할 때,
  Extraneous하다.

우측의 Attribute를 제거하면 더 약한 Constraints가 만들어진다.

$F = {AB \rightarrow CD, A \rightarrow C}$의
$AB \rightarrow CD$에서 $C$를 없애면,
더 약한 Constraint $AB \rightarrow D$를 얻을 수 있다.
$AB \rightarrow D$는 더이상 $AB \rightarrow C$를 암시하지는 못하므로 더 약한 Constraints라고 할 수 있다.
여기서 우리는 $C$가 $AB \rightarrow CD$에서 Extraneous 한 Attribute라고 한다.

다시 Canonical Cover로 돌아와서,
$F$의 Canonical Cover $F\_c$는

$F$가 논리적으로 $F\_c$의 모든 Dependency를 암시하고,
$F\_c$가 논리적으로 $F$의 모든 Dependency를 암시하고,
$F\_c$의 모든 Dependency가 Extraneous가 없고,
$F\_c$의 모든 좌변이 서로 중복되지 않은 (ex: $A \rightarrow B$,$A \rightarrow C$는 좌변이 $A$로 중복)
Dependency의 집합이다.

Canonical Cover를 찾는 알고리즘은 다음과 같다.

F:
Fc = F
repeat
    Union rule로 a->b, a->c 형태의 Depedency를 a->bc로 대체
    Fc에서 Extraneous Attribute를 가지고 있는 a->b를 찾는다
    찾으면 a->b에서 지운다
until Fc가 바뀌지 않을 때까지

* 지운 다음 Union Rule을 다시 적용해야 한다.

Dependency Preservation

Functional Dependency Constraints를 데이터베이스가 업데이트될 때마다 검사하는 것은 비용이 많이 든다.
따라서 Constraints를 효과적으로 검사하도록 DB를 디자인해야 한다.
하나의 Relation만 고려해 검사하면 비용이 적게 든다. 그러나 Cartesian Produce를 사용하지 않고는 Decompose 할 수 없는 경우도 존재한다.

Functional Dependency를 Join과 같은 복잡한 연산 없이 검사할 수 있다면 Dependency가 Preserved 됐다고 한다.

Schema $dept\_advisor( s\_ID, i\_ID, dept\_name)$와
Functional Dependency
$i\_ID \rightarrow dept\_name$
$s\_ID,,dept\_name \rightarrow i\_ID$
가 있다고 하자.
이 경우, $dept\_advisor$에 $instructor$가 참여할 때마다를 할 수 있다.

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

Use

그래서 Functional Dependency는 언제 쓸까?

Relation이 주어진 Functional Dependency에서 Legal 한 지 확인하기 위해:
- Relation $r$이 Functional Dependency $F$ 아래서 Legal 하다면, $r$ satisfies $F$라고 한다.
Legal Relation의 제약(Constraints)을 지정하기 위해
- Relation $r$의 모든 Legal Relation이 Functional Dependency $F$를 만족한다면, $F$ holds on $r$이라고 한다.
Decomposition이 Lossless한 지 확인하기 위해

Lossless Decomposition

$R$을 $R\_1$과 $R\_2$로 Decompose 할 때, $R$은 $R\_1$과 $R\_2$를 Join한 결과여야 한다.

$R$을 $R\_1$과 $R\_2$로 Decompose 할 때,
최소 하나의 $F^+$가

$R\_1 \cap R\_2 \rightarrow R\_1$이거나
$R\_1 \cap R\_2 \rightarrow R\_2$이면
Lossless Decomposition이라고 할 수 있다.

이 Functional Dependency는 Lossless Join Decomposition을 위한 충분조건이며,
Dependency는 모든 제약조건이 Functional Dependency인 경우에만 필요조건이다.

Relation $R,=,(A,,B,,C)$과
Functional Dependency $F = {A \rightarrow B,, B \rightarrow C}$가 있다.
$R\_1,=,(A,,B)$, $R\_2,=,(B,,C)$로 나누면,
$R\_1 \cap R\_2 , = {B}, , B \rightarrow BC$로 Lossless Decomposition이다.

$R\_1,=,(A,,B)$, $R\_2,=,(A,,C)$로 나누면,
$R\_1 \cap R\_2 , = {A}, , A \rightarrow AB$로 Lossless Decomposition이다.

Normal Form

Normalization은 Relation $R$이 "좋은" 디자인인지 평가하는 척도이다.
$R$이 좋은 디자인이 아니라면 Decompose를 통해 Relation을 나눠야 하는데,

각 Relation이 좋은 디자인이어야 하고,
Decomposition이 Lossless Decomposition이어야 하며,
되도록 Decomposition이 Dependency Preserving 해야 한다.

Boyce-Codd Normal Form

Relation Schema $R$의 모든 Functional Dependency $F^{+}$가 아래 조건을 만족할 때 BCNF를 만족한다고 한다.

$\alpha \subseteq R$이고 $\beta \subseteq R$인 $\alpha \rightarrow \beta$가

$\alpha \rightarrow \beta$가 Trivial 하거나,
$\alpha$가 $R$의 Superkey이다.

$in\_dept(\underline{ID}, name, salary, dept\_name, building, bu
$dept\_name \rightarrow building, budget$이
Trivial하지도, $dept\_name$이 Superkey도 아니다.
따라서 BCNF가 아니다.

$R$이 BCNF가 아니라면 BCNF가 되도록 Decompose 해야 한다.
$\alpha \rightarrow \beta$가 BCNF 위반을 일으킬 때, $R$을

$(\alpha \cup \beta)$와
$(R-(\beta - \alpha))$로 나눈다.

$in\_dept(\underline{ID}, name, salary, dept\_name, building, bu
$\alpha = dept\_name$
$\beta = building, budget$으로
$(\alpha \cup \beta) = (dept\_name, building, budget)$과
$(R-(\beta - \alpha)) = (ID, name, dept\_name, salary)$로 나누면 된다.

그러나 항상 BCNF를 사용할 수 있지는 않다. 어떤 경우는 Dependency Preservation이 깨지기도 한다.

$dept\_advisor(s\_ID, i\_ID, dept\_name)$가
$i\_ID \rightarrow dept\_name$
$s\_ID, dept\_name \rightarrow i\_ID$일 때,
$dept\_advisor$는 BCNF가 아니지만,
그 어떤 Decomposition도 $s\_ID, dept\_name \rightarrow i\_ID$의 모든 속성을 포함하지는 못한다.

BCNF Decomposition Algorithm

result := {R}; 
done := fasle; 
compute F+; 
while(not done) do 
    if (BCNF가 아닌 schema Ri가 result에 있을 경우) 
        then begin 
            a+가 Ri를 포함하지 않고, a ∩ b가 공집합인
            Nontrivial Functional Dependency a->b에 대해
            result := (result - Ri) ∪ (Ri - b) ∪ (a,b);
        end 
    else done := true;

Third Normal Form

3NF를 만족하는지 확인하기 위해서는 $F$의 Functional Dependency만 확인하면 된다.
$\alpha$가 Superkey라면 Attribute Closure로 확인할 수 있다.
$\alpha$가 Superkey가 아니라면 $\beta$의 각 Attribute가 $R$의 Candidate Key에 포함되어 있는지 검사해야 한다.

이 테스트는 매우 비싼 NP-Hard Test이다.
대신 Decomposition은 Polynomial Time이 걸린다.

Third Normal Form Decomposition Algorithm

Let Fc be a canonical cover for F; 
i := 0; 
for each functional dependency a -> b in Fc do
    begin 
        i := i + 1;
        Ri := ab 
    end

if none of the schemas Rj, 1 <= j <= i contains a candidate key for R 
    then begin 
        i := i + 1; 
        Ri := any candidate key for R; 
    end 

repeat
if any schema Rj is contained in another schema Rk 
    then /* delete Rj */ 
        Rj = Ri; 
        i = i - 1; 

return (R1, R2, ..., Ri)

Design Goal

그래서 데이터베이스를 어떻게 디자인하라는 것일까?
Relational Database Design의 목표는

BCNF
Lossless Join
Dependency Preservation
이다.
이 조건을 만족하지 못할 때는

Dependency Preservation에서 타협하거나
3NF의 중복을 타협한다.

SQL은 이러한 사항을 고려하지 않기 때문에 디자인 설계에서 고려해야 한다.

Multivalued Dependencies

ER Design에서 몇몇 값은 값을 여러 개 가지는 경우가 있었다.
이러한 값을 Multivalue라고 한다.

Relation Schema $R$에 대해
$\alpha \subseteq R$이고 $\beta \subseteq R$ 이면
Multivalued Dependency $\alpha \rightarrow \rightarrow \beta$가 성립한다.
이 경우 $\alpha$에 따라 $\beta$가 결정되지만, $\beta$는 Multivalue이다.

4NF

다음 조건을 만족하면 4NF를 만족한다.

$\alpha \rightarrow \rightarrow \beta$가 trivial하고,
$\alpha$가 $R$의 Superkey이다.

4NF이면 BCNF도 만족한다.

4NF로 Decompose하는 알고리즘은 다음과 같다.

result: = {R}; 
done := false; 
compute D+; 
Let Di denote the restriction of D+ to Ri 
while (not done) 
    if (there is a schema Ri in result that is not in 4NF) then 
        begin 
            let a->->b be a nontrivial multivalued dependency 
            that holds on Ri such that a->Ri is not in Di, and a ∩ b = null; 
            result := (result - Ri) ∪ (Ri - b) È (a, b); 
        end 
    else done:= true

DB - 0. Index

저작자표시 비영리 변경금지

현재글DB - 5. Normalization

Code in Coffee

DB - 5. Normalization

Decomposition

Normalization Theory

Functional Dependency

Keys

Canonical Cover

Extraneous Attribute

Dependency Preservation

Use

Lossless Decomposition

Normal Form

Boyce-Codd Normal Form

BCNF Decomposition Algorithm

Third Normal Form

Third Normal Form Decomposition Algorithm

Design Goal

Multivalued Dependencies

4NF

'Computer Science Basics/데이터베이스'의 다른글

티스토리툴바

DB - 5. Normalization

Decomposition

Normalization Theory

Functional Dependency

Keys

Canonical Cover

Extraneous Attribute

Dependency Preservation

Use

Lossless Decomposition

Normal Form

Boyce-Codd Normal Form

BCNF Decomposition Algorithm

Third Normal Form

Third Normal Form Decomposition Algorithm

Design Goal

Multivalued Dependencies

4NF

'Computer Science Basics/데이터베이스'의 다른글

관련글

티스토리툴바