DB08 - Normalization

Agenda

• 동기(Motivating) 를 부여하는 예시
• 정규형(Normal forms)
• 정규화 예시
• 부록 (Appendix): 정규화 이론

데이터가 뒤섞여 있을 때 (Jumbled)…

 

1. 강사(instructor)와 학과(department)를 결합한다고 가정해보자.

• (아래는 instructor와 department의 조인을 나타냄)

2. 주요 문제

• 데이터의 반복 → 데이터베이스의 크기를 증가시킴
• 데이터 일관성(Data consistency) 문제
  • 삽입 이상(Insertion anomaly): 새로운 레코드를 삽입할 때마다 중복된(redundant) 데이터를 넣어야 함
    • 예시 : 새로운 강사를 추가하려는데, 학과 정보도 함께 넣어야 함. 근데 그 학과가 아직 존재하지 않으면? → 넣기 곤란해짐.
    • 예시 : 새로운 교수 "Lee"를 추가하려는데, 소속 학과 "Comp. Sci."의 건물과 예산 정보도 함께 입력해야 한다. 학과가 아직 존재하지 않으면 삽입이 어렵다.
  • 삭제 이상(Deletion anomaly): 일부 데이터를 삭제하면 관련된 데이터도 함께 손실됨
    • 예시 : 강사 한 명을 삭제했더니, 그 학과에 대한 정보까지 같이 없어져버려! (row가 하나일 경우에는, 존재하지 않게 된다)
    • 예시 : 교수 "El Said"와 "Califieri"를 삭제하면, 해당 학과인 "History"에 대한 정보도 함께 사라진다.
  • 갱신 이상(Update anomaly): 특정 정보를 갱신(certain)할 때, 모든 레코드를 하나하나 다 수정해야 함
    • 예시 : "컴퓨터공학과의 건물이 바뀌었다!" → 100명 강사의 레코드를 하나하나 다 수정해야 해.
    • 예시 : "Comp. Sci." 학과의 건물이 변경되면, 해당 학과 교수들의 모든 레코드에서 건물 정보를 일일이 수정해야 한다.

 

해결책: 분해(Decomposition)!

Q. 정보의 반복 문제를 어떻게 피할 수 있을까?

• 답: 두 개의 스키마로 분해한다 (원래처럼)
  • 정규화(Normalization) = 관계형 스키마의 분해
  • 핵심 아이디어: 직접적으로 관련 있는 데이터만을 하나의 릴레이션으로 구성하도록 분할하는 것

분해(Decomposition)

0. 분해란?

: 하나의 테이블이 너무 복잡하거나 중복이 많을 때, 작은 테이블들로 나누는 것을 말한다.

 

1. 분해의 장점

: 중복(redundancy)이 줄어듦 → 더 적은 디스크 저장 공간 사용, 삽입/삭제/갱신 이상(anomalies) 현상이 줄어듦

 

2. 모든 분해가 좋은 것은 아님

[다음처럼 분해했다고 가정하자]

원본
employee(ID, name, street, city, salary)

분배
employee1 (ID, name)
employee2 (name, street, city, salary)

→ 문제: 이름이 같은 직원이 둘 이상 있을 경우 어떻게 할 것인가?

-> 즉, 그런데 같은 이름 "김민수"가 두 명이면? 👉 어떤 주소와 급여가 어떤 ID의 김민수인지 연결할 수 없다!

 

3. 손실 분해(Lossy decomposition): 원래의 릴레이션을 복원할 수 없는 분해

-> 즉, "원래 테이블로 다시 정확히 되돌릴 수 없는 나쁜 분해" 를 말한다. 그래서 절대 하면 안 되는 분해 방식이라고 볼 수 있다.

 

손실이 있는 분해(Lossy Decomposition)

1. R이 하나의 릴레이션 스키마이고, R1과 R2가 R의 분해라고 하자. 즉, R = R1 ∪ R2

 

2. 분해가 손실 없는 분해(lossless decomposition) 이려면, R을 R1과 R2로 대체해도 정보 손실이 없어야 한다.

• 공식적으로, ∏R1(r) ⋈ ∏R2(r) = r 이면 손실 없음
  • cf. 반대로(Conversely), 분해가 손실 있는 분해(lossy) 라면, 프로젝션의 조인 결과가 원래 릴레이션보다 더 많은 튜플을 반환함 즉, r ⊂ ∏R1(r) ⋈ ∏R2(r) 이 성립함

예시: 손실 없는 분해(Lossless Decomposition)

R = (A, B, C) 를 다음과 같이 분해한다고 하자:

→ R1 = (A, B); R2 = (B, C)

Normalization (정규화)

1. 데이터베이스 정규화: 데이터 중복(redundancy)을 줄이고 데이터 무결성(integrity)을 향상시키기 위해 데이터베이스를 구조화하는 과정

• 정규형(normal forms)의 일련의 규칙에 따라 수행됨(In accordance with)
• 이 과정을 통해:
  • 관계를 분해하여 데이터 이상 현상을 억제할 수 있다(suppress)
  • 분해가 손실 없는 것인지 확인할 수 있다 (테이블을 나눴다가 나중에 다시 합쳤을 때, 원래 정보가 100% 되돌아오는지 확인)

 

 

 

 

Agenda (목차)

• 동기 부여 예시
• 정규형(Normal Forms)
• 정규화 예시
• 부록: 정규화 이론

Normal Forms (정규형)

1. 정규화 과정 

• 정규화는 관계형 데이터베이스 테이블을 더 높은 정규형까지 설계할 때 사용되는 데이터베이스 설계 기법이다.
  • 논리적으로 독립적이지만 관련된 데이터 엔터티를 여러 관계로 절차적으로 분리한다.
  • 키를 사용하여 이들 간의 연결을 유지한다.

2. 점진적인 과정(Progressive process)이다.

• 이전 수준의 정규형을 만족하지 않으면 더 높은 수준의 정규화를 달성할 수 없다.
  • UNF: 비정규형
  • 1NF: 제1정규형
  • 2NF: 제2정규형
  • 3NF: 제3정규형
  • BCNF: 보이스-코드 정규형 (3.5정규형)
  • 4NF: 제4정규형 ...

3. 정규형은 다음과 같은 이론들에 의해 뒷받침된다

• 함수(Functional) 종속성 : 어떤 속성 A를 보면, 다른 속성 B가 정해지는 관계
  • 부분(Partial) 종속성 : 복합 키의 일부만 보고 결정되는 속성이 있음
    -> 이걸 없애는 게 제2정규형 (2NF)의 목표!
  • 이행적(Transitive) 종속성 : A → B, B → C 이면 A → C 도 성립하는 관계
    -> 이걸 없애는 게 제3정규형 (3NF)의 목표!
    
• 다치(Multi-valued) 종속성 : 하나의 키가 여러 개의 독립된 값과 연결될 때
  -> 이런 걸 다루는 게 제4정규형 (4NF)!
  

4. 이러한 이론들은 특정 릴레이션 R이 '좋은 형식'인지 아닌지를 판단한다 

• 릴레이션 R이 '좋은 형식'이 아니라면, 이를 릴레이션들의 집합 {R1, R2, ..., Rn}으로 분해하여
  • 각 릴레이션은 좋은 형식이어야 하며
  • 분해는 손실이 없어야 한다

First Normal Form (1NF, 제1정규형)

1. 요구 사항 

• 릴레이션은 원자값(atomic values)으로 구성되어야 한다.
  • 원자값: 더 이상 나눌 수 없는 값 (≒ JAVA의 원시 데이터 타입과 유사)
    • 원자값 예시: INT, FLOAT, DOUBLE, DECIMAL(NUMERIC), CHAR, VARCHAR, BLOB, TEXT
    • 사용 불가 예시: 구조체(Structure), 리스트(List), 배열(Array)
  • 속성은 고유한 식별자(unique identifiers)를 가져야 한다.

2. 정규화 과정의 1단계

• "당신의 데이터베이스 테이블이 1NF를 따르지 않는다면, 데이터베이스 사용을 중단해야 한다."

3. 1NF 체크리스트

1) 각 열(column)은 원자값을 포함해야 한다.

• (x, y) 형태의 항목은 이 규칙을 위반함
• 즉, 각 셀에는 하나의 값만 있어야 한다.

2) 각 열은 동일한 데이터 도메인 내의 값을 포함해야 한다.

• 한 열에 서로 다른 타입의 값을 혼합하지 말 것
• 즉, 열 하나에는 같은 종류의 값만 있어야 한다.

3) 각 열은 고유한 이름을 가져야 한다.

• 중복된 열 이름은 데이터 접근 시 혼란을 야기함
• 즉, 각 열의 이름은 고유해야 한다.
  • 그래야, 데이터 조회 및 수정 때 헷갈리지 않는다.

4) 데이터 저장 순서는 중요하지 않다.

• SQL을 사용하면 어떤 순서로든 데이터를 쉽게 가져올 수 있음
• 즉, 행의 순서는 중요하지 않다.

5) 테이블에 중복된 행(row)은 없어야 한다.

• 기본키(PK)는 다음을 보장한다:
  • 기본키에 포함된 속성은 고유하다
  • 기본키에 포함된 속성은 null이 될 수 없다
• 즉, 중복된 행은 없어야 한다.
  • 이를 방지하기 위해 기본키를 설정한다.

Functional Dependencies (함수 종속성)

0. 의미

: 어떤 값을 알면, 다른 값이 자동으로 딱 하나로 결정되는 관계이다.

 

1. 현실 세계의 데이터에는 다양한 제약조건(규칙)이 존재한다.

• 예: 대학 데이터베이스에서 기대되는 제약 조건은 다음과 같다:
  • 학생과 교수는 ID로 고유하게 식별된다
  • 각 학생과 교수는 하나의 이름만을 가진다
  • 각 교수와 학생은 하나의 학과에만 소속된다
  • 각 학과는 예산에 대해 하나의 값과 하나의 건물만을 가진다
• 릴레이션은 어떤 속성 집합의 값이 다른 속성 집합의 값을 유일하게 결정해야 한다는 것을 요구한다.
  즉, 어떤 값을 보면, 다른 값이 "하나로만" 딱 정해져야 한다는 것이다.
  
  • 예 : 여기서 학번이 같으면, 이름과 학과도 항상 같아야 한다. 
  • 함수 종속성은 키의 개념을 일반화한 것이다 (= 자명한 종속성 포함).

2. 예시

: 릴레이션 스키마 R이 있고, a, b가 그 속성이라 하자 (a ⊆ R, b ⊆ R)

1) 함수 종속성 a → b는 다음 조건을 만족할 때 성립한다

: 릴레이션 r(R)에서 임의의 두 튜플 t1, t2가 a 속성들에 대해 같다면, 그들은 b 속성들에 대해서도 같아야 한다.

• 즉, t1[a] = t2[a] ⇒ t1[b] = t2[b]
• 예: r(A, B)의 인스턴스를 보자:

A | B
1 | 4
1 | 5
3 | 7

→ 이 경우 B → A는 성립하지만, A → B는 성립하지 않는다 (B 값만 유일하므로)

쉽게 말해, A가 1이면 B는 4, 5 여러 개 있을 수 있으므로 A->B는 성립 안되고,
B가 4이면 A는 1, B가 5이면 A는 1 이렇게 하나씩만 존재하므로 B->A는 성립이 된다.

 

 

Keys and Functional Dependencies (키와 함수 종속성)

0. 핵심 질문

:  "왜 함수 종속성이 키보다 더 넓은 개념일까?"

 

1. 함수 종속성(Functional dependencies)을 통해 슈퍼키로는 표현할 수 없는 제약을 표현할 수 있다.

• 예: in_dep (ID, name, salary, dept_name, building, budget)
  • ID = 교수의 ID (instructor ID)
  • dept_name = 교수가 소속된 학과
• 기대되는 함수 종속성:
  • dept_name → building
  • ID → building
  • ⇒ dept_name과 ID는 슈퍼키이며 후보키(candidate key)가 될 수 있다
  • * ID, dept_name, {ID, dept_name}
• 하지만 다음과 같은 종속성은 기대하지 않는다:
  
  • dept_name → salary
  • 이유 : "컴퓨터공학과" 교수는 여러 명이 있을 수 있고,  교수마다 급여는 다르기 때문이다.

Functional Dependencies 

0.

후보키(Candidate Key)란?

: 튜플(한 줄)을 유일하게 식별할 수 있는 속성(들)의 집합이다!

• 여러 개의 속성들이 함께 모여서 하나의 후보키가 될 수도 있다. 
• 예: {a1, a2, a3} → 이 3개가 같이 있을 때만 고유한 한 줄을 찾을 수 있다면, 이게 후보키야.

1. 예: R = a1, a2, a3, a4 -> 후보키(candidate key) = a1, a2, a3, {a1, a2}, {a2, a3}, {a1, a3}, {a1, a2, a3}

• a1은 키의 일부
  • 함수 종속성: a4는 키 a1a2a3에 종속되어야 한다
    • 예: b_id, b_name, bd_detail_attrib1, bd_detail_attrib2
      • 후보키: b_id, b_name, {b_id, b_name}
  • 그런데 a4가 a1에만 종속되고 전체 키(a1a2a3)에 종속되지 않는다면 이는 부분 종속성이다.
    즉, 이 후보키 안의 일부 속성만으로도 어떤 값을 알 수 있다면? 그게 바로 부분 종속성이다.

Trivial Functional Dependencies (자명한 함수 종속성)

1. 함수 종속성이 모든 릴레이션 인스턴스에서 항상 만족된다면 그것은 자명한 종속성이다.

• 예:
  • ID, name → ID
  • name → name
• 일반적으로 a → b가 자명하려면 b ⊆ a 이어야 한다.

Functional Dependencies (사진 예시)

1. 예시: student2(ID, name, tot_cred)

• 성립하는 함수 종속성:
  • ID → name : ID는 한 학생을 고유하게 식별하니까
  • ID → tot_cred : 마찬가지로 ID는 한 명의 학생을 의미하니까
• 성립하지 않는 함수 종속성:
  • tot_cred → name : 총 학점이 같다고 해서 이름이 같지는 않음!
  • name → tot_cred : 이름이 같다고 해서 총 학점이 같지는 않음!

 

 

 

 

 

 

2. 예시: score(score_id, student_id, subject_id, score)

• {student_id, subject_id} → score 성립

 

제1정규형 (1NF)

1. 예시

한 셀에 여러 개의 값이 들어 있음
→ course 컬럼에 "Algorithm, OS" 같은 식으로 여러 과목이 쉼표로 묶여 있음
→ 이건 제1정규형을 위반한 상태이다.

 

→ 학생 한 명당 한 줄, 중복 없음
→ 이건 괜찮다.

 

 

→ 한 줄에 하나의 과목만 들어있고
→ 과목이 여러 개일 경우 학생 ID를 반복하면서 표현

→ 이걸로 제1정규형(1NF)을 만족하는 테이블이 됨!

내용은 정규화된 형태로 잘 나뉘어 있다.

• 학생 테이블 (ID, name)
• 수강 테이블 (ID, course)

 

제2정규형 (2NF)

1. 요구 사항

• 릴레이션은 1NF에 있어야 한다 (정규형은 순서대로 적용해야 함)
• 릴레이션은 어떤 후보키의 부분집합에 함수적으로 종속된 비-기본키(non-PK) 속성을 가져서는 안 된다 = 부분 종속성 금지!
  • 기본키(PK)가 아닌 모든 속성은 PK 전체에 종속되어야 한다
  • 부분 종속성이 존재해서는 안 된다
  • PK(Primary Key):
    • 릴레이션의 각 튜플을 고유하게 식별하는 속성 또는 속성 집합
    • PK는 릴레이션 내의 특정 데이터를 가져올 수 있음
    • 예: student_ID = 21800999인 학생의 학과명을 조회하기

부분 종속성 (Partial Dependencies)

1. 릴레이션 R = a1, a2, a3, a4 → 기본키(복합 키)

• a1은 기본키의 일부
  • 부분 종속성: a4가 a1에는 종속되지만 전체 키(a1a2a3)에는 종속되지 않음
    • 키: a1a2a3
    • 종속: a1 ➝ a4

2부분 종속성 제거하기

1. 예시 : teaches2(ID, course_id, sec_id, semester, year, name)

• ID ➝ name

• 문제점 : ID → name → 교수 ID만 알면 이름이 정해짐
  → 그런데 ID는 전체 키의 일부만 사용되고 있어
  → 👉 부분 종속성 발생 → 2NF 위반

1) 정규화 결과

• teaches2a(ID, course_id, sec_id, semester, year)
• teaches2b(ID, name)

2. 또 다른 예시

• score(score_id, student_id, subject_id, score, instructor)
• subject_id ➝ instructor → 부분 종속성

• 문제점: subject_id → instructor
  → 즉, 과목 ID만 알면 담당 교수가 정해짐
  → 그런데 subject_id는 후보키가 아니고, 전체 키(score_id)의 일부 속성만으로 instructor를 결정하고 있어!

 

1) 정규화 결과

• score_a(score_id, student_id, subject_id, score)
• score_b(subject_id, instructor)

제3정규형 (3NF)

1. 요구 사항

• 릴레이션은 2NF에 있어야 함
• 릴레이션은 이행적 종속성(transitive dependency) 을 가져서는 안 됨
  • 이행적 종속성: 비-PK 속성이 다른 비-PK 속성이나 그 집합에 종속되는 경우

이행적 종속성 (Transitive Dependencies)

1. 릴레이션 R = a1, a2, a3, a4 → 후보키 = a1, a2, {a1, a2}

• a1은 R의 기본키
  • a3는 a1에 종속됨 (a1 ➝ a3) → OK
  • a4는 a3에 종속됨 (a1 ➝ a3 ➝ a4) → 비-PK ➝ 비-PK → 이행적 종속성

이행적 종속성 제거하기

1. 예시 - (1)

• PK: BookNo
• Patron ➝ Address 관계가 존재한다. 즉, 이 사람의 이름으로 주소를 알 수 있다.
• 한마디로, BookNo -> Parton -> Address라는 이행적 종속성이 생기게 된다.
• 문제점 : J.Fisher의 Address가 바뀌면, 그 사람이 빌린 책이 여러 개면, 모든 레코드의 주소를 다 바꿔야 한다. (갱인 이상 발생)

-> 따라서 대출 정보와 이용자 정보로 분리한다.

 

1. 예시 - (2)

• PK: {Tournament, Year}
• Winner ➝ DOB

2. 예시 : score2(id, student_id, subject_id, exam_name, exam_score)

• {student_id, subject_id} ➝ FINAL or MIDTERM
• {student_id, subject_id} ➝ 77 43 … 어디서 온 값인가?
• {student_id, subject_id} ➝ exam_name ➝ exam_score → 이행적 종속성
• 문제인 이유 :
  시험 이름(exam_name)을 잘못 쓰거나 바꾸면,
  → 그에 따른 점수(exam_score)가 여러 군데에서 바뀌어야 할 수도 있음

1) 정규화 결과

• score2a(id, student_id, subject_id, exam_id, exam_name)
• score2b(student_id, subject_id, exam_id, exam_score)

보이스-코드 정규형 (BCNF, Boyce-Codd Normal Form = 3.5NF)

1. 요구 사항

• 릴레이션은 3NF에 있어야 한다
• 어떤 종속성 A ➝ B에 대해, A는 슈퍼키여야 한다
  • A ➝ B에서 A가 비-PK이면, BCNF에 해당하지 않음

BCNF 예시

1. 예시 : takes2(student_id, subject, instructor)

• (student_id, subject) ➝ instructor
• instructor ➝ subject → 비-PK가 PK의 구성원을 결정 → BCNF 아님

1) 정규화 결과

• takes2a(student_id, section_id)
• takes2b(section_id, subject, instructor)

제4정규형 (4NF)

1. 요구 사항

• 릴레이션은 BCNF에 있어야 함
• 릴레이션은 다치 종속성(Multi-valued Dependency) 을 가지면 안 됨
  • 다치 종속성은 잘못된 DB 스키마로 인해 발생함
  • 다치 종속성은 릴레이션이 3개 이상의 속성을 가질 때 발생할 수 있음
  • 예: 릴레이션 (A, B, C)에서
    • A ➝ B 이고
    • B와 C가 서로 독립적일 때 → 다치 종속성이 발생할 수 있음

다치 종속성 예시 (Multi-valued Dependencies)

1. 예시

• student_id ➝ course
• student_id ➝ activity
• course ⊥ activity (서로 독립)

요약: 정규형 (Normal Forms)

1. 이론 – 정규형 (사진)

•  

전체 데이터베이스 설계 과정

1. 스키마 R이 주어졌다고 가정하자
: R이라는 테이블 구조(스키마) 가 하나 있다고 가정하자.

• (E-R 모델)
  • R은 E-R 다이어그램을 테이블 집합으로 변환하면서 생성되었을 수 있다
    : "처음엔 그림으로 설계하고, 그걸 테이블로 바꾼 것"이라는 말이다.
• (정규화)
  • R은 관심 있는 모든 속성을 포함한 단일 릴레이션(보편 릴레이션, universal relation)일 수 있다
    : 가끔은 관심 있는 정보를 전부 다 하나의 테이블에 몰아넣는 경우도 있다.
  • 그래서 정규화는 R을 더 작은 릴레이션으로 나눈다
• (혼합 방식)
  • R은 임의적인 릴레이션 설계 결과일 수 있으며, 이를 테스트하거나 정규형으로 변환한다
    : 누군가 그냥 아무 생각 없이 만든 테이블이 있다면?
    → 우리는 그 테이블이 잘 만들어졌는지 테스트하거나,
    → 정규화 과정을 거쳐서 더 나은 형태로 바꿀 수 있어!
    

E-R 모델과 정규화

1. E-R 다이어그램이 신중하게 설계되어 모든 엔터티를 정확히 식별했다면, 이로부터 생성된 테이블은 추가적인 정규화를 필요로 하지 않는다

2. 그러나 현실의 불완전한 설계에서는, 엔터티의 non-key 속성에서 다른 속성으로의 함수 종속성이 존재할 수 있다

• 예: employee 엔터티
  • 속성: department_name, building
  • 함수 종속성: department_name → building
  • 좋은 설계라면 department를 별도의 엔터티로 만들었어야 한다

3. 관계 집합의 비-키 속성으로부터의 함수 종속성도 존재 가능하지만, 대부분의 관계는 이항 관계라 드물다

 

성능을 위한 비정규화

1. 성능상의 이유로 비정규화된 스키마를 사용할 수 있다

• 예: course_id와 title과 함께 prereqs를 보여주려면 course와 prereq를 조인해야 함

2. 대안 1: course와 prereq의 속성을 모두 포함하는 비정규화된 릴레이션 사용

• 빠른 조회 가능
• 업데이트 시 더 많은 저장 공간과 실행 시간 필요
• 프로그래머가 추가 코딩 필요 + 오류 가능성 존재

3. 대안 2: course ⋈ prereq로 정의된 물리적 뷰(materialized view) 사용

• 위와 동일한 장단점, 단 코딩 필요 없음 → 오류 방지 가능

남은 문제들

1. 정규화로도 포착되지 않는 설계 문제들이 존재

2. 예 (피해야 할 설계):

• earnings_2004, earnings_2005, earnings_2006 등으로 설계된 경우, 스키마: (company_id, earnings)
  • 위 설계는 BCNF 정규형을 만족하지만, 연도 간 쿼리가 어렵고 매년 새 테이블이 필요
• company_year(company_id, earnings_2004, earnings_2005, earnings_2006)도 마찬가지 문제
  • 위 설계는 BCNF 정규형을 만족하지만, 연도 간 쿼리가 어렵고 매년 새 속성 필요
• 이는 크로스탭(crosstab)의 예시: 하나의 속성 값이 열 이름이 됨
• → 더 나은 스키마: earnings(company_id, year, amount)

 

 

 

목차

• 동기 부여 예시
• 정규형
• 정규화 예시
• 부록: 정규화 이론

예시 (위키백과에서 가져온 사례)

1. 주어진 릴레이션

2. 1NF 만족

 

3. 1NF 만족 (계속, 개선된 버전)

4. 주어진 릴레이션

• 복합 키 {Title, Format}
  • 부분 종속성: Title → Author, Author Nationality, Pages, Thickness, Genre ID, Genre Name, Publisher ID

5. 2NF 만족

6. 3NF 만족

• 이행 종속성: Genre ID → Genre Name 

 

7. BCNF 만족

• 비-PK → 비-PK: Author → Author Nationality

 

8. 주어진 릴레이션

• 이 데이터베이스는 여러 지역에 점포를 소유한 서점 프랜차이즈가 보유한 것으로 가정

 

9. 4NF 만족

• 모든 책이 모든 지역에서 제공된다고 가정하면, Title이 특정 지역에 명확하게 귀속되지 않음 → 4NF 만족하지 않음

목차

• 동기 부여 예시
• 정규형
• 정규화 예시
• 부록: 정규화 이론

정규화 이론

1. 특정 릴레이션 R이 ‘좋은 형식’인지 판단

• R이 좋은 형식이 아니라면, 이를 릴레이션들의 집합 {R1, R2, ..., Rn}으로 분해해야 한다
  • 각 릴레이션은 좋은 형식이어야 한다
  • 분해는 손실 없는 분해여야 한다 

2. 정규화는 다음과 같은 이론들을 기반으로 한다:

• 함수 종속성
• 부분 종속성
• 이행 종속성
• 다치 종속성

함수 종속성

1. 현실 세계의 데이터에는 다양한 제약(규칙)이 존재

• 예: 대학 데이터베이스에서 기대되는 제약
  • 학생과 교수는 ID로 고유하게 식별
  • 각 학생과 교수는 하나의 이름만 가짐
  • 각 교수와 학생은 하나의 학과에만 (주로) 소속됨
  • 각 학과는 하나의 예산과 하나의 건물을 가짐
• 릴레이션은 어떤 속성 집합의 값이 다른 속성 집합의 값을 유일하게 결정해야 함
  • 함수 종속성은 키의 개념을 일반화한 것 (자명한 종속성 포함)

 

2. 릴레이션 스키마 R이 있고, a, b가 그 속성일 때 (a ⊆ R, b ⊆ R)

 

3. 함수 종속성 a → b는, 릴레이션 r(R)의 두 튜플 t1과 t2가 a 속성 값이 같으면 b 값도 같을 때 성립

• 즉, t1[a] = t2[a] → t1[b] = t2[b]
• 예: r(A, B)의 다음 인스턴스를 보자
  • A | B
    1 | 4
    1 | 5
    3 | 7
  • 이 경우 B → A는 성립하지만, A → B는 성립하지 않음 (B 값만 유일)

키와 함수 종속성

1. 함수 종속성은 슈퍼키만으로 표현할 수 없는 제약을 표현 가능

• 예: 스키마 : in_dep (ID, name, salary, dept_name, building, budget)
  - ID = 교수 ID
  - dept_name = 교수의 학과
  • 다음 종속성이 성립한다고 기대됨:
    • dept_name → building
    • ID → building
    • → dept_name, ID는 슈퍼키 = 후보키
      * ID, dept_name, {ID, dept_name}
  •  다음 종속성은 기대되지 않음:
    • dept_name → salary

함수 종속성

1. 릴레이션 R = a1, a2, a3, a4 -> 후보키: a1, a2, a3, {a1, a2}, {a2, a3}, {a1, a3}, {a1, a2, a3}

• a1은 키의 일부
  • a4는 키 a1a2a3에 종속되어야 함
    • 예: b_id, b_name, bd_detail_attrib1, bd_detail_attrib2
      • 후보키: b_id, b_name, {b_id, b_name}
  •  a4가 a1에만 종속되고 전체 키에는 종속되지 않는다면 a1a2a3 (a1 ➝ a4) → 부분 종속성

자명한 함수 종속성

1. 릴레이션의 모든 인스턴스에서 항상 만족되는 함수 종속성

• 예시:
  • ID, name → ID
  • name → name
• 일반적으로 a → b가 자명하려면 b ⊆ a여야 함

함수 종속성

1. student2(ID, name, tot_cred)

• ID → name
• ID → tot_cred
• tot_cred → name (X)

2. SCORE(score_id, student_id, subject_id, score)

• {student_id, subject_id} → score

 

부분 종속성

1. 릴레이션 R = a1, a2, a3, a4 → 복합 기본키

• a1은 기본키의 일부
  • a4는 a1에만 종속, 전체 키 a1a2a3에는 종속되지 않음 (a1 ➝ a4)
    • 키: a1a2a3
    • 종속성: a1 ➝ a4

2. teaches2(ID, course_id, sec_id, semester, year, name)

• ID → name
• {course_id, sec_id, semester, year} → name

 

3. SCORE(score_id, student_id, subject_id, score, instructor)

• subject_id → instructor (부분 종속성) → 이런 건 원하지 않음

이행 종속성

1. 릴레이션 R = a1, a2, a3, a4 -> 후보키 = a1, a2, {a1, a2}

• a1은 R의 기본키
  • a3는 a1에 종속됨 (a1 ➝ a3) → OK
  • a4는 a3에 종속됨 (a1 ➝ a3 ➝ a4) → 비-PK ➝ 비-PK

2. EXAM_SCORE(id, student_id, subject_id, exam_name, exam_score)

• {student_id, subject_id} → FINAL 또는 MIDTERM
• {student_id, subject_id} → 77, 43 … 어디서 나온 값인가?
• {student_id, subject_id} → exam_name → exam_score → 이행 종속성

 

다치 종속성 (MVDs)

1. 교수의 자녀 이름과 전화번호를 기록한다고 가정

• inst_child(ID, child_name)
• inst_phone(ID, phone_number)
• → 이 둘을 결합하면: : inst_info(ID, child_name, phone_number)
  • → 하나의 테이블에 서로 독립된 다중 값을 포함하게 되어 중복 발생
  • 예: ID=999999 → {David, William} & {x-x-1234, x-x-4321}
    • (99999, David, 512-555-1234)
    • (99999, David, 512-555-4321)
    • (99999, William, 512-555-1234)
    • (99999, William, 512-555-4321)
    • → 문제 발생 가능

2. R이 하나의 릴레이션 스키마라고 하고, a ⊆ R이고 b ⊆ R이라고 하자.  

• 3. 다치 종속성 a ->-> b가 R에서 성립한다는 것은 다음과 같은 조건을 만족하는 경우이다:  
  릴레이션 r(R)에 있는 모든 튜플 쌍 t1과 t2에 대해 t1[a] = t2[a] 라면,   다음 조건을 만족하는 튜플 t3과 t4가 r에 존재해야 한다:  
• t1[a] = t2[a] = t3[a] = t4[a] 
  • t3[b] = t1[b] 
  • t3[R – b] = t2[R – b] 
  • t4[b] = t2[b] 
  • t4[R – b] = t1[R – b]  

3. 릴레이션 스키마 R이 있고, 이 R의 속성들이 Y, Z, W라는 3개의 비어 있지 않은 부분 집합으로 나누어진다고 하자.

4. Y ->-> Z (Y가 Z를 다치 결정한다) 라고 말하는 것은, 모든 가능한 릴레이션 r(R)에 대해 다음을 만족할 때이다:

• < y1, z1, w1 > ∈ r 이고 < y1, z2, w2 > ∈ r 이면,
• < y1, z1, w2 > ∈ r 이고 < y1, z2, w1 > ∈ r 여야 한다.

5. 주의할 점은, Z와 W의 동작이 동일하기 때문에, Y ->-> Z 이면 Y ->-> W 도 성립한다는 것이다.

 

6. 다치 종속성의 표 형태 표현

 

7. 예: FAV(student_id, course, activity)

• 예시 데이터: 21800999 → {statistics, Linear algebra} & {Soccer, basketball}
• → 선호 과목과 선호 활동은 독립적(orthogonal)이다

함수 종속성의 활용

1. 함수 종속성은 다음과 같은 목적으로 사용된다:

• 주어진 함수 종속성 집합 하에서 릴레이션이 유효한지 테스트하기
  • r이 F를 만족한다고 말하는 것은, 릴레이션 r이 함수 종속성 집합 F 하에서 유효하다는 뜻
• 유효한 릴레이션들의 집합에 제약을 명시하기
  • F가 R에서 성립한다고 말하는 것은, R에 대한 모든 유효한 릴레이션들이 함수 종속성 집합 F를 만족한다는 의미

2. 주의: 특정 릴레이션 인스턴스는 모든 인스턴스에서 해당 함수 종속성이 항상 성립하지 않더라도, 우연히 그 종속성을 만족할 수 있다

• 예: instructor 릴레이션의 특정 인스턴스가 우연히 name -> ID를 만족할 수 있다

다치 종속성의 활용

1. 다치 종속성은 다음 두 가지 방법으로 사용된다:

• 릴레이션이 주어진 함수 및 다치 종속성 집합 하에서 유효한지 확인하기 위해
• 유효한 릴레이션 집합에 제약을 명시하기 위해 (우리는 주어진 함수 및 다치 종속성 집합을 만족하는 릴레이션만을 고려함)

2. 릴레이션 r이 주어진 다치 종속성을 만족하지 않는다면, 해당 종속성을 만족하는 튜플들을 r에 추가함으로써 새로운 릴레이션 r′을 구성할 수 있다