데이터베이스 : 7장 Normalization

1.Features of Good Relational Design

1) Features of Good Relational Designs

(1) 정보의 반복이 존재하는 결합된 스키마

• instructor와 department를 in_dep으로 결합한다고 가정
  → in_dep : instructor와 department relation을 natural join으로 표현

• in_dep relation에는 정보의 반복이 존재함
• 만약 instructor가 없는 새 department를 추가하는 경우 null값을 사용해야 함

(2) 정보의 반복이 없는 결합된 스키마

• 결합된 스키마 모두가 정보의 반복으로 이어지는 것은 아니다
  • 다음 student와 advisor relation을 하나의 relation으로 결합한다고 가정
    
    • student(ID, name, dept_name, tot_cred) / advisor(s_ID, i_ID)
      → student(ID, name, dept_name, tot_cred, advisor)
  • 이 경우 정보의 반복(repetition)이 없음

2) Decomposition(분해) <=> Composition(합성)

Decompositoin : relation에서 특정 속성의 값이 반복적으로 나타나는 경우(data redundancy)
                          → 해당 relation을 더 작은 schema로 쪼개는 것!!!

• in_dep 스키마에서 정보의 반복 문제를 방지하는 유일한 방법은 정보를 instructor와 department 스키마의 두 가지 스키마로 decompose(분해)하는 것!!!
• 모든 decompose가 좋은 것은 아니다!!!
  • employee(ID, name, street, city, salary)
    → employee1(ID, name) and employee2(name, street, city, salary)
  • 같은 이름의 직원이 두 명일 때 문제가 발생할 수 있다!!!
    → 기존 employee relation으로 reconstruct(재구성)할 수 없기 때문에 lossy decomposition이라 함

Lossy decompositoin : 나뉘어진 2개의 relation을 하나로 합칠 때 원래의 테이블에서 데이터 손실이 발생하는 것
                                     → 주로 나뉘어진 relation에서 functional dependency가 없기 때문에 발생!!!

(1) Lossy Decomposition

Loss Decomposition

Loss Decomposition 예시

(2) Lossless Decomposition

• R을 relation 스키마로 하고 R1과 R2가 R의 분해를 형성하도록 함
  → R = R1 ∪ R2
• 우리는 R을 두 relation 스키마 R1 ∪ R2으로 대체하여 정보 손실이 없다면 해당 decompositoin은 lossless decomposition이다!!!

Lossless Decomposition

Lossless Decomposition 예시

3) Normalization Theory

• 특정 relation R이 "good" 형태인지 여부를 결정!!!
• relation R이 "good" 형태가 아닌 경우, 다음과 같이 relation set {R1, R2, ..., Rn}으로 분해
  • 각 realtion은 good 형태로~
  • 분해는 무손실 분해로~
• 우리의 이론은 다음을 기반으로 함
  1. Functional dependencies (함수적 종속성)
  2. Multivalued dependencies (다중값 종속성)

Functional Dependecies(함수적 종속성)
- X와 Y를 임의의 속성 집합이라 할 때, X의 값이 Y의 값을 유일하게 결정할 경우
→ "X는 Y를 함수적으로 결정"하고, "Y는 X에 함수적으로 종속된다"라고 함

Multivalued Dependecies(다중값 종속성)
- 어떤 조건 하에 튜플이 존재할 것을 기대하는 종속성

 

2. Functional Dependencies

1) Functional Dependencies

• 일반적으로 실제 데이터에는 다양한 constraint(제약 조건)이 있음
• 예시) 대학교 데이터베이스에 유지될 것으로 예상되는 제약 조건 중 일부는 다음과 같음
  1. 학생들과 강사들은 그들의 ID에 의해 고유하게 식별됨
  2. 각 학생과 강사는 이름이 하나뿐임
  3. 각 강사와 학생은 (주로) 하나의 학과와만 연계되어 있음
  4. 각 부서에는 예산에 대한 가치가 하나만 있고 관련 건물은 하나만 존재
• 이러한 모든 실제 제약 조건을 만족시키는 relation의 예를 legal instance of relation라고 함
• 데이터베이스의 legal instance는 모든 realtion instance가 legal instance인 경우를 말함

(1) Functional Dependecies란

• legal reation의 집합에 대한 constraints
• 특정 속성 집합의 값이 다른 속성 집합의 값을 고유하게 결정하도록 요구
• functional dependency는 key의 개념을 일반화하는 것

(2) Functional Dependencies 정의

• R을 다음을 만족하는 relation schema라고 하자

• Functional dependency (α → β)는 어떤 legal reation r(R)에 대해서도 r의 튜플들인 t1과 t2가 속성 α에 동의할 때마다 속성 β에 동의하는 경우에만 R이 유지된다. 즉, 다음과 같다.

• 예시) r(A, B)를 다음의 r의 instance와 함께 고려해보자
  • 해당 instance에서, B → A는 holde / A → B는 NOT hold

2) Closure of a Set of Functional Dependencies

• Functional Dependencies의 집합 F가 주어지면, F에 의해 논리적으로 암시되는 특정한 다른 functional dependecies가 있다.
  • 예시) 만약 A → B 및 B → C라면, A → C라고 추론할 수 있음
• F에 의해 논리적으로 암시되는 all functional dependencies의 집합은 closure of F라고 함

closure of F의 표현법

3) Keys and Functional Dependencies

• K는 K → R인 경우에만 관계 스키마 R에 대한 superkey이다.
• K는 다음과 같은 경우에만 R의 후보키이다.
  • K → R and for no α ⊂ K, α ⊂ R
• Functional Dependencies는 superkey를 사용하여 표현할 수 없는 제약 조건을 표현할 수 있게 해준다.
  • 예시) in_dep(ID, name, salary, dept_name, building, budget)
    → 우리는 이러한 functional dependencies이 다음과 같이 유지 될 것으로 예상할 수 있음
          dept_name → building
          ID → building
    → 하지만!!! 다음 사항이 유지될 것으로 예상하지는 않음
          dept_name → salary

4) Use of Functional Dependencies

• Functional Dependencies를 사용하여 다음을 수행
  • relation을 test하여 주어진 functional dependencies 집합에서 legal인지 확인
    • 만약 relation r이 functional dependencies 집합 F에서 legal이라면, 우리는 "r sataisfies F"라 지칭
  • legal relation의 집합에서 제약조건을 지정하려면
    • 우리는 R에 대한 모든 legal reation이 functional dependencies 집합 F를 만족하는 경우 "F holds on R"이라고 지칭

Notation : 관계 스키마의 특정 instance는 functional dependencies이 모든 legal instance를 hold(유지)하지 않더라도 functional dependencies를 충족할 수 있음
예시) instructor의 특정 인스턴스는 우연히 name → ID를 만족할 수 있음

5) Trivial(자명한) Functional Dependencies

• functional dependencies는 모든 realtion의 인스턴스에 의해 만족되는 경우 trival이다.
• 예시) ID, name → ID / name → name
• 일반적으로, β ⊆ α라면 α → β는 trival이다.

 

3. Decomposition Using Functional Dependencies

1) Lossless Decomposition

• 우리는 functional dependencies를 사용하여 특정 decomposition이 lossless임을 보여줄 수 있다.
•  R = (R1, R2) 의 경우, 우리는 스키마 R의 가능한 모든 relation에 대해 다음을 요구한다.

• 다음의 dependencies 중 적어도 하나가 F+인 경우, R을 R1과 R2로 분해하는 것은 lossless decomposition이다.
  • R1 ∩ R2 → R1
    R1 ∩ R2 → R2
    (둘 중 하나만 trival하게 추론될 경우 무손실 분해를 위한 조건)

(1) 예시

• R = (A, B, C)
  F = {A → B, B → C}
• R1 = (A, B), R2 = (B, C)
  • Lossless decomposition
    R1 ∩ R2 → {B} and B → BC
• R1 = (A, B), R2 = (A, C)
  • Lossless decomposition
    R1 ∩ R2 → {A} and A → AC
• R1 = (A, C), R2 = (B, C)
  • Loss decomposition
    R1 ∩ R2 → {C} and C → X
    

Note : B → BC 는 B → {B, C}의 단축 표기법(shorthand notation)이다.

2) Dependency Preservation

• 데이터베이스가 업데이트될 때마다 functional dependencies constraint를 test하는 데 많은 비용이 소요될 수 있음
• 제약 조건을 효율적으로 테스트할 수 있는 방식으로 데이터베이스를 설계하는 것이 유용
• functional dependencies을 하나의 relation만 고려하여 테스트할 수 있는 경우, 이 제약 조건을 테스트하는 비용은 낮음
• relation을 분해할 때 Cartesian Product을 수행하지 않고는 더 이상 테스트를 수행할 수 없음
• functional dependencies을 강제하기 어렵게 만드는 분해를 dependency preserving이라고 하지 않음

(1) 예시

• R = (A, B, C)
  F = {A → B, B → C}
• R1 = (A, B), R2 = (B, C)
  • Lossless-join decomposition
    R1 ∩ R2 → {B} and B → BC
  • Dependency preserving
• R1 = (A, B), R2 = (A, C)
  • Lossless decomposition
    R1 ∩ R2 → {A} and A → AC
  • Not dependency preserving
    → R1과 R2를 join을 하지 않고서는(R1 ⋈ R2) B → C를 확인할 수 없음

<Decomposition 조건>
1. Lossless
2. dependcy presrving

 

4. Normal Forms

1) First Normal Form

• Domain의 원소가 분리할 수 없는 단위로 간주되는 경우 Domain은 atomic이다.
  • non-atomic domain의 예 : Set of names, composite attributes(복합 속성)
• R의 모든 속성의 도메인이 atomic일 경우 relational schema R은 first normal form을 만족한다.
• non-atomic value로 인해 저장공간이 복잡해지고 데이터의 redundant(repeated) storage가 촉진됨
  • 예시) 각 고객과 함께 저장된 계좌 집합 및 각 계좌와 함께 저장된 소유자 집합
  • 우리는 모든 relation이 first normal form이라고 가정

2) Boyee-Codd Normal Form

• 관계 스키마 R은 형식의 F+에 있는 모든 functional dependencies에 대한 functional dependencies의 집합 F에 대해 BCNF에 있다.
  α → β
  α ⊆ R 및 β ⊆ R일 때, 적어도 다음 중 하나를 hold한다.
  
  1. α → β 는 trivial하다(즉, β ⊆ α)
  2. α는 R에 대해 superkey이다.
• 예시) BCNF를 만족하지 않는(not) 스키마
            in_dep(ID, name, salary, dept_name, building, building, budget)
             - ID → name, salary, dept_name
             - dept_name → building, budget
  
  • 이유
    • dept_name → buliding, budget
      • in_dep에서 hold
      • 하지만 dept_name은 superkey가 아님
• in_dept를 instructor와 department로 분해할 때
  • instructor는 BCNF 만족
  • department는 BCNF 만족

(1) Decomposing a Schema into BCNF

• R을 BCNF에 없는 스키마 R이라 하자. α → β가 BCNF 위반을 유발하는 FD라고 하자
• 우리는 R을 다음과 같이 분해할 수 있다.
  1. (α ∪β)
  2. (R - (β - α))
• in_dep의 예시를 통해 분해해보기
  • α : dept_name
  • β : building, budget
  • in_dep는 다음과 같이 분해할 수 있음
    • (α ∪β) = (dept_name, building, budget)
    • (R - (β - α)) = (ID, name, dept_name, salary)

<Example>

• R = (A, B, C)
  F = {A → B, B → C)
• Key?
  • A → B와 B → C를 통해 A → C를 추론할 수 있음
  • A는 A → ABC이므로 primary key이다.
• BCNF?
  • B는 B → C에서 supekey가 아니다
  • R은 BCNF가 아니다
• Decompose
  • R1 = (R - (β - α)) = (A, B) , R2 = (α ∪β) = (B, C)
  • R1과 R2는 모두 BCNF이다.
  • Lossless-join decomposition : R1 ∩ R2 = {B} and B → BC
  • Dependency preserving

(2) BCNF and Dependency Preservation

• BCNF와 dependency preservation을 모두 달성하는 것이 항상 가능한 것이 아님
• 다음 스키마를 고려해보자 : dept_advisor(s_ID, i_ID, dept_name)
  • function dependencies(과별로 지도교수가 있는 경우)
    i_ID → dept_name
    s_ID, dept_name → i_ID
  • dept_advisor가 BCNF에 있지 않다.
    • i_ID는 superkey가 아니다.
  • Decompose
    • R1 = (α ∪β) = (i_ID, dept_name), R2 = (R - (β - α)) = (s_ID, i_ID)
    • R1과 R2는 모두 BCNF에 있다.
    • Dependency는 보존되지 않음

3) Third Normal Form

• 관계 스키마가 R은 다음과 같은 경우 third normal form(3NF)이다.
  적어도 다음 중 하나 이상을 hold
  1. α → β 는 trivial하다(즉, β ⊆ α)
  2. α는 R에 대해 superkey이다
  3. β → α에서 각 속성 A는 R의 candidate key에 포함되어 있다.
     (참고 : 각 속성은 서로 다른 candidate key에 있을 수도 있음)

• 관계는 BCNF에 있으면 3NF에 있다.(BCNF에서 위의 두 조건 중 하나가 유지되어야 하기 때문)
• 세번째 조건은 dependency preservation을 보장하기 위해 BCNF를 최소한으로 완화(minimal relaxation)하는 것!!!

(1) 3NF 예시

• 다음 스키마를 고려해보자 : dept_advisor(s_ID, i_ID, dept_name)
• function dependencies
  i_ID → dept_name
  s_ID, dept_anme → i_ID
• 두 개의 candidate key = {s_ID, dept_name}, {s_ID, i_ID}
• 우리는 이전에 dept_advisor가 BCNF에 없다는 것을 보았다.
• 하지만 R은 3NF에 있다.
  • s_ID, dept_name은 superkey이다.
  • i_ID → dept_name 과 i_ID는 superkey가 아니다 하지만
    
    • {dept_name} - {i_ID} = {dept_name} 그리고
    • dept_name은 candidate key에 포함된다.

(2) Redundancy in 3NF

• 3NF를 만족하는 아래 스키마 R을 고려해보자
  - R = (J, L, K)
  - F = {JK → L, L → K}
  그리고 instance table

• 위의 테이블에서 잘못된 것은?
  • 정보의 반복
  • Null 값을 사용해야 함(예: J에 해당하는 값이 없는 관계 l2, k2를 나타내려면)

<정규화 순서>

(3) 3NF Decomposition Algorithm

i := 0;
for each functional dependency α → β in F do
	if none of the schemas Rj, 1 ≤ j ≤ i contains α β
		then begin
			i := i + 1;
			Ri := α β
		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 
/* 다른 테이블에 속하는 candidate key가 있다면 제외하는 코드 */
repeat
if any schema Rj is contained in another schema Rk 
	then /* delete Rj */
 		Rj= Ri;
		i=i-1;
return (R1, R2, ..., Ri)

(4) 3NF Decomposition 예시

• Relation Schema
  cust_banker_branch = (customer_id, employee_id, branch_name, salary, type)
• 이 관계 스키마의 functional dependencies는 다음과 같다
  • customer_id, employee_id → type
  • employee_id → branch_name, salary 
  • customer_id, branch_name → employee_id
• for 루프는 다음 3NF 스키마를 생성
   (customer_id, employee_id, type )
   (employee_id, branch_name, salary)
   (customer_id, branch_name, employee_id)
  • (customer_id, employee_id, type)에 원래 스키마의 후보키가 포함되어 있으므로 관계 스키마를 추가할 필요가 없음
• 루프가 종료되면 다른 스키마의 하위 집합인 스키마를 탐색하고 삭제
  • 삭제된 스키마가 없음
  • 결과는 FD가 고려되는 순서에 따라 달라지지 않음
• 단순화된 3NF 스키마는 다음과 같음
   (customer_id, employee_id, type )
   (employee_id, branch_name, salary)
   (customer_id, branch_name, employee_id)

<과정>

1. BCNF

• candidate key를 먼저 찾기
  
  • {customer_id, employee_id}
  • {customer_id, branch_name} 
    → 연쇄적으로 모든 속성값을 찾을 수 있음
• super key인지 확인
  • {employee}는 superkey가 아님
    ⇒ R1 = (employee_id, branch_name, salary)
         R2 = (customer_id, employee_id, type)
    → BCNF는 불가능
• dependence로 R3 생성
   R1 = (employee_id, branch_name, salary)
   R2 = (customer_id, employee_id, type)

(5) Comparision of BCNF and 3NF

• BCNF에 비해 3NF의 장점
  • Losslessness 또는 dependency preservation을 희생하지 않고 항상 3NF 설계를 얻을 수 있음
• 3NF의 단점
  • 정보의 반복이라는 문제가 있음
  • 데이터 항목 간에 가능한 의미 있는 관계 중 일부를 나타내기 위해 Null값을 사용해야 할 수도 있음

4) Goals of Normalization

• R이 functional dependencies의 집합 F를 갖는 관계 스키마라고 하자
• 관계 스키마 R이 "good" 형태인지 여부를 결정
• 관계 스키마 R이 "good 형태가 아닌 경우, 다음과 같이 관계 스키마 {R1, R2, ..., Rn} 집합으로 분해해야 함
  1. 각 관계 스키마는 good form이다.
  2. decomposition은 lossless decomposition이다.
  3. 가급적이면, decomposition은 dependency preserving(보존)해야 한다.

5) How good is BCNF?

• BCNF에 충분히 정규화 되지 않은 데이터 스키마가 있다.
• 다음 relation을 고려해보자 : inst_info(ID, child_name, phone)
  → child와 phone이 여러 개가 존재할 수 잇음
  
  • inst_info의 인스턴스

• non-trivial functional dependencies는 없으므로 위의 relation은 BCNF에 있다.
• Insertion anomalies(삽입 이상)
  예시) 981-992-3443 전화기를 99999에 추가하면 튜플 두 개를 추가해야 함
            + (99999, David, 981-992-3443), (99999, William, 981-992-3443)

6) Multivalued Dependencies

• R이 관계 스키마이고 α ⊆ R이고 β ⊆ R이라고 하자.
• multivalued dependencyα →→ β 는 어떤 legal relation r(R)에서 t1[α] = t2[α]와 같은 r의 튜플들 t1과 t2에 대한 모든 쌍에 대해 다음과 같은 튜플 t3와 t4가 존재한다.

• 예시

7) Fourth Normal Form

• inst_info를 다음과 같이 분해하는 것이 좋다.

• relation R은 다음과 같은 경우 4NF에 있다.
  1. It is in BCNF
  2. No two or more attributes are multivalued in R

8) Further Normal Forms

• Join dependencies는 multivalued dependencies를 일반화한다.
  • project-join normal from(PJNF)로 이어진다.(또는 fifth normal form이라고 불림)
• 훨씬 더 일반적인 제약 조건의 클래스는 domain-key normal form이라고 불리는 normal form으로 이어진다.
• 이러한 일반화된 제약 조건의 문제는 추론하기 어렵고, 건전하고 완전한 inference rule(추론 규칙) 집합이 존재하지 않음
• 따라서 거의 사용되지 않음
• 모든 3NF 스키마는 2NF에 있다.

 

5. Overall Database Design Process

• 주어진 스키마를 R이라고 하자
  • R은 E-R 다이어그램을 테이블 집합으로 변환할 때 생성될 수 있다.
  • R은 관심있는 모든 속성을 포함하는 single relation일 수 있다.(universal relation이라고 불림)
  • R은 우리가 테스트하고 normal form으로 변환하는 어떤 ad hoc(특별한) design of relations의 결과일 수 있다.
  • Normalization은 R을 더 작은 relation으로 나눈다.

6. ER Model and Normalization

• E-R 다이어그램을 신중하게 설계하여 모든 엔티티를 정확하게 식별할 때, E-R 다이어그램에서 생성된 표는 추가 정규화가 필요하지 않아야 함!!!
• 하지만 실제 설계에서는 엔티티의 non-key 속성에서 엔티티의 다른 속성에 대한 functional dependencies가 있을 수 있음
  • 예시) 다음과 같은 employee 엔티티
    • attributes : department_name 와 building
    • functional dependency : department_name → building
    • 좋은 디자인은 department를 하나의 엔티티로 만들었음
• 관계 집합의 key가 아닌 속성으로부터의 Functional dependencies이 가능하지만 희귀
  → 대부분의 relationship은 binary이다.

7. Denormalization for Performance

• performance(성능)을 위해 non-normalized schema를 사용할 수 있음
• 예를 들어, prereeqs를 course_id 및 title과 함께 표시하려면 prereq와 course를 join해야 한다.
• 대안 1 : 위의 모든 속성과 함께 prereq뿐만 아니라 course 속성을 포함하는 denormalized relation을 사용
  • faster lookup(더 빠른 탐색)
  • 업데이트를 위한 추가 공간 및 추가 실행 시간
  • 프로그래머를 위한 추가 코딩 작업 및 추가 오류 가능성
• 대안 2 : course ⋈ prereq를 정의하는 materialized view를 사용
  • 프로그래머를 위한 추가 코딩 작업이 없고 가능한 오류를 피하는 것을 제외하면 위와 같은 장점과 단점이 있다.

8. Other Design Issues

• 데이터베이스 설계의 일부 측면은 정규화에 의해 파악되지 않음
• 피해야 할 잘못된 데이터베이스 설계의 예 : earnings(company_id, year, amount) 대신에
  1.  (company_id, earnings)를 가지는 earnings_2004, earnings_2005 등으로 사용
     • 위의 것들은 BCNF에 있지만, 수년에 걸치 쿼리를 어렵게 만들고 매년 새로운 테이블이 필요함
  2. company_year(company_id, earnings_2004, earnings_2005, earnings_2006)으로 사용
     1. BCNF에 있지만, 수년에 걸친 쿼리를 어렵게 만들고 매년 새로운 속성을 요구함
     2. 한 속성에 대한 값이 열 이름이 되는 crosstab의 예이다.
     3. 스프레드시트 및 데이터 분석 도구에 사용됨