Ch7_Relational_Database_Design

Chapter 7. Relational Database Design

핵심 요약: “좋은” 릴레이션 설계는 정보 중복과 null을 최소화한다. 나쁜 스키마는 **분해(decomposition)**로 개선하되, 원본을 복원할 수 있는 lossless decomposition이어야 한다. 좋음의 기준은 함수적 종속성(Functional Dependency, FD) 위에 정의된 **정규형(Normal Form)**으로 판단한다. BCNF는 모든 비자명 FD의 좌변이 superkey여야 하고, 3NF는 BCNF의 조건을 완화하여 dependency preservation을 항상 보장한다. Armstrong’s axioms와 attribute closure ${\alpha }^{+}$로 FD를 추론하고 BCNF/3NF 분해 알고리즘을 적용한다.

---

1. Features of Good Relational Designs

나쁜 설계의 증상을 in_dep(instructor와 department를 natural join한 결과)로 관찰한다:

ID	name	salary	dept_name	building	budget
22222	Einstein	95000	Physics	Watson	70000
12121	Wu	90000	Finance	Painter	120000
45565	Katz	75000	Comp. Sci.	Taylor	100000
10101	Srinivasan	65000	Comp. Sci.	Taylor	100000
76766	Crick	72000	Biology	Watson	90000
…	…	…	…	…	…

증상

• 정보 중복(Repetition of information): Comp. Sci. 학과의 building·budget이 여러 행에 반복.
• Null의 필요성: 교수가 없는 학과를 추가하려면 교수 속성에 null을 써야 함.

해결 — Decomposition

• in_dep을 instructor와 department 두 스키마로 분해해야만 중복을 제거할 수 있다.
• 그러나 모든 분해가 좋은 것은 아니다.

---

2. Decomposition — Lossless vs Lossy

2.1 Lossy Decomposition 예시

employee(ID, name, street, city, salary)를

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

로 분해하면, 같은 이름을 가진 두 직원(예: Kim)이 있을 때 natural join 결과에 원본에 없던 튜플이 생긴다:

ID	name	street	city	salary
57766	Kim	Main	Perryridge	75000
57766	Kim	North	Hampton	67000 ← 가짜
98776	Kim	Main	Perryridge	75000 ← 가짜
98776	Kim	North	Hampton	67000

원본을 복원할 수 없다 → lossy decomposition.

2.2 Lossless Decomposition 정의

$R=R_1\cup R_2$일 때, 모든 가능한 인스턴스 $r$에 대해
${\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)=r$
이 성립하면 lossless decomposition. 만약
$r⊊{\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)$
이면 lossy.

r 이라는 relation에서 any column R1, R2를 뽑아 projection하고
natural join 했을 때, 원본 복구가 돼냐?
→ “쪼갰다 붙이면 원본 복구됨?”

반대로 loosy를 생각해보면 아까 위에서 visual 적으로 불필요한게 늘어난 경우니까, 부등호 방향을 기억하기!

직관 — "lossless"는 사실 "가짜 튜플 무발생"

• 튜플은 절대 사라지지 않음: $r\subseteq {\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)$는 항상 성립. 원본의 어떤 튜플이든 쪼갰다 붙이면 반드시 돌아옴.
• 문제는 반대 방향: $\supseteq$가 깨질 수 있음 → join 결과에 원본에 없던 가짜 튜플(spurious tuple) 이 섞임 = lossy.
• 따라서 lossless = “쪼갰다 붙여도 가짜가 안 생김”. 이름은 “lossless”지만 실제로는 “spurious-free”가 더 정확한 표현.

기호 정의

• $R$: 릴레이션 스키마 (속성 이름들의 집합), 예: $R=\{A,B,C\}$
• $r$ (소문자): 스키마 $R$의 인스턴스 — 실제 튜플들이 담긴 테이블
• $R_1,R_2$: 분해로 생긴 부분 스키마. $R_1\cup R_2=R$, $R_1\cap R_2$는 공통 속성
• $t\in r$: $r$의 한 튜플(행)
• $t[R_1]$: 튜플 $t$에서 $R_1$ 속성만 뽑은 값 (한 행의 부분 투영)
• ${\Pi }_{R_1}(r)$: $r$ 전체를 $R_1$ 컬럼으로만 잘라낸 테이블 (중복 제거)
• $\bowtie$: natural join — 공통 속성 값이 같은 행끼리 붙임

왜 $\subseteq$ 방향(튜플 안 사라짐)은 항상 성립하는가
원본의 임의의 튜플 $t\in r$을 잡자. 그러면:

1. $t_1=t[R_1]$은 ${\Pi }_{R_1}(r)$ 안에 존재 ($t$를 $R_1$으로 자른 조각).
2. $t_2=t[R_2]$는 ${\Pi }_{R_2}(r)$ 안에 존재 ($t$를 $R_2$로 자른 조각).
3. $t_1$과 $t_2$는 같은 원본 튜플 $t$에서 잘린 조각이므로 공통 속성 $R_1\cap R_2$에서의 값이 자동으로 일치 → natural join 조건을 만족.
4. 따라서 $t_1\bowtie t_2=t$가 join 결과에 반드시 포함됨.

즉 project는 “세로로 자르기”일 뿐 행을 버리지 않고, natural join은 매칭되는 쌍을 반드시 복원하므로, 모든 원본 튜플은 복구 보장. 그래서 $\subseteq$는 수학적으로 항상 참인 부등식이고, 실제 lossless/lossy를 가르는 것은 오직 $\supseteq$ 방향뿐.

왜 가짜가 생기는가: 분해 시 “ID ↔ salary의 짝 정보”가 끊어지고, join은 공통값으로 모든 조합을 만들어버리기 때문. 공통 속성이 한쪽의 key이면 조합이 1:1이라 가짜 불가 → 그래서 §5의 lossless 조건이 “공통 속성 $\to$ 한쪽 전체”인 것.

2.3 Lossless 예시

$R=(A,B,C)$, $R_1=(A,B)$, $R_2=(B,C)$로 분해:

| A | B | C | → | A | B | | B | C |

|---|---|---| |---|---| |---|---|
| α | 1 | A | | α | 1 | | 1 | A |
| β | 2 | B | | β | 2 | | 2 | B |

natural join 결과가 원본과 일치 → lossless.
조건 : 공통 속성이 한 쪽의 superkey일 것.

---

3. Normalization Theory 개요

• 주어진 릴레이션 $R$이 “good” form인지 판단한다.
• good form이 아니면 $\{R_1,R_2,\dots ,R_n\}$로 분해하되 각 $R_i$가 good form이고, lossless여야 한다.
• 이론은 Functional dependencies와 Multivalued dependencies 위에 구축된다.

3.1 “Good form”의 의미 — 왜 분해하는가

분해의 궁극적 목표는 redundancy 제거를 통해 3가지 anomaly를 방지하는 것:

anomaly : 변칙, 예외, 이상치, 이상 징후

Anomaly	증상
Update anomaly	같은 사실이 여러 행에 반복되어, 일부만 갱신하면 불일치 발생
Insertion anomaly	특정 정보를 넣으려면 아직 모르는 값(NULL)까지 억지로 채워야 함
Deletion anomaly	한 튜플 삭제 시 무관한 다른 정보까지 함께 사라짐

예: inst_dept(ID, name, salary, dept_name, building, budget)에서 한 학과의 교수가 10명이면 building, budget이 10번 반복됨 → 건물 정보 변경 시 10줄 모두 갱신 필요(update), 교수 없는 신설 학과는 삽입 불가(insertion), 마지막 교수 퇴직 시 학과 정보까지 소실(deletion).

3.2 분해의 3가지 목표

“good form으로 분해”는 동시에 3가지 품질 기준을 만족해야 한다:

1. Lossless join (§2) — 반드시 만족. 원본 복원 가능해야 함.
2. Dependency preservation (§6) — 가능한 한 만족. 원래 FD들을 분해 후에도 각 $R_i$ 안에서 검사 가능해야 함.
3. 최소 redundancy — 가능한 한 높은 정규형(BCNF 이상)에 도달.

3.3 이론의 전체 지도

FD(+MVD) 주어짐
    │
    ├─ F⁺, α⁺ 계산 (§10)  ← 모든 후속 판정의 기초
    │
    ├─ Candidate key 도출
    │
    ├─ 정규형 판정
    │    ├─ BCNF? (§7)   ← 가장 엄격, redundancy 최소
    │    ├─ 3NF?  (§8)   ← 느슨, dep-preservation 보장
    │    └─ ... (4NF, 5NF는 MVD 기반)
    │
    └─ 위반 시 분해 알고리즘 적용 (§11)
         ├─ BCNF decomp: lossless ✓ / dep-preservation ✗ 가능
         └─ 3NF  decomp: lossless ✓ / dep-preservation ✓ 보장

3.4 BCNF vs 3NF — 왜 두 개가 필요한가

• 이상적: BCNF (redundancy 최소).
• 현실적 타협: 일부 스키마는 BCNF로 가면 dependency preservation이 깨져서 원래 제약을 여러 테이블 join으로만 검사 가능해짐 → 성능·일관성 비용.
• 그래서 3NF가 **“lossless + dep-preservation + 거의 BCNF 수준의 정규화”**라는 절충점으로 제공됨.

한 줄 요약

Normalization = “redundancy를 제거하되(높은 정규형), 정보와 제약은 잃지 않는(lossless + dep-preservation) 분해를 찾는 이론.” FD는 이 모든 판정·알고리즘의 입력 언어이다.

---

4. Functional Dependencies (FDs)

= 함수 : i.e. x 정해지면 y도 deterministic함?

4.1 직관

현실에는 다양한 제약(rule)이 있다. 예: 대학 DB에서

• 학생·교수는 ID로 유일 식별된다.
• 각 학생·교수는 이름을 하나만 가진다.
• 각 학생·교수는 기본적으로 하나의 학과에 소속된다.
• 각 학과는 하나의 building·budget 값을 가진다.

모든 실세계 제약을 만족하는 릴레이션 인스턴스를 legal instance라 한다.

4.2 FD의 형식적 정의

릴레이션 스키마 $R$에 대해 $\alpha \subseteq R$, $\beta \subseteq R$일 때,
$\alpha \to \beta$
가 $R$에 hold on한다는 것은: 임의의 legal instance $r(R)$에서 임의의 두 튜플 $t_1,t_2$가 $\alpha$에서 일치하면 $\beta$에서도 반드시 일치함. 즉,
$t_1[\alpha ]=t_2[\alpha ]⟹t_1[\beta ]=t_2[\beta ]$

예시 — 인스턴스 $r(A,B)$:

A	B
1	4
1	5
3	7

• $B\to A$는 hold (4→1, 5→1, 7→3 모두 일관) : 함수 관점.
• $A\to B$는 hold 하지 않음 (A=1인데 B가 4도 5도 됨)

4.3 FD와 Key의 관계

• $K$가 $R$의 superkey이다 ⇔ $K\to R$
• $K$가 $R$의 candidate key이다 ⇔ (1) $K\to R$, (2) $K$의 어떤 진부분집합도 $R$을 결정하지 않음 ($\forall \alpha ⊊K,\alpha \nrightarrow R$)
• FD는 superkey로 표현할 수 없는 제약도 표현한다.

예시 — in_dep(ID, name, salary, dept_name, building, budget)

• 성립: dept_name → building, ID → name
• 성립하지 않음: dept_name → salary (같은 학과라도 급여는 다름)

4.4 FD의 활용

두 가지 목적:

1. Legal 검사: 인스턴스가 주어진 FD 집합 $F$ 아래에서 legal한지 검사 → $r$이 satisfies $F$.
2. 제약 명시: legal 릴레이션 집합에 제약을 부과 → $F$가 $R$에 holds on.

주의: 특정 인스턴스가 우연히 어떤 FD를 만족한다고 해서 그 FD가 모든 legal 인스턴스에서 성립한다는 뜻은 아니다. 예: instructor 인스턴스에서 우연히 name → ID가 성립할 수 있지만, 일반적으로는 성립하지 않는다.

4.5 Trivial Functional Dependencies

모든 인스턴스에서 항상 성립하는 FD를 trivial이라 한다.

• 예: ID, name → ID, name → name
• 일반 규칙: $\alpha \to \beta$는 $\beta \subseteq \alpha$일 때 trivial.

4.6 Closure of a Set of FDs — $F^{+}$

• 주어진 FD 집합 $F$로부터 논리적으로 함의되는 추가 FD들이 있다. 예: $A\to B$, $B\to C$이면 $A\to C$.
• $F$가 논리적으로 함의하는 모든 FD의 집합을 $F$의 closure라 하며, $F^{+}$로 표기한다.

FD / $F$ / $F^{+}$ 세 층위 정리

층위	타입	예시
FD	화살표 식 하나 (한 개의 주장)	dept_name → building
$F$	FD들을 원소로 갖는 집합	$F=\{A\to B,B\to C,CG\to H\}$
$F^{+}$	$F$로부터 Armstrong’s axioms로 연역 가능한 모든 FD의 집합	$\{A\to C,AG\to H,B\to B,\dots \}$

Span 비유: 선형대수 $\text{span}(v_1,\dots ,v_n)$이 선형결합 규칙 아래 닫힌 최소 공간이듯, $F^{+}$는 Armstrong 규칙(reflexivity / augmentation / transitivity) 아래 닫힌 최소 FD 집합. 수학적으로는 closure operator — $F\subseteq F^{+}$ (extensive), monotone, idempotent $(F^{+}{)}^{+}=F^{+}$.

Sound + Complete (§10.1)의 역할: “모든 legal instance에서 성립” ⇔ “$F^{+}$에 속함”을 보장. 즉 **의미론(모든 테이블 조사)**을 **구문론(규칙 유도)**으로 환원 — 이게 없으면 FD 추론은 불가능한 무한 검사가 됨.

쌍둥이 주의 — $F^{+}$ vs ${\alpha }^{+}$ (§10.5)

기호	입력	출력	용도
$F^{+}$	FD 집합 $F$	FD들의 집합	개념적 존재 (보통 전체를 만들지 않음)
${\alpha }^{+}$	속성 집합 $\alpha$ (+ 고정된 $F$)	속성들의 집합	실무 계산 도구, 다항시간

실무에선 $F^{+}$를 직접 생성하지 않고 $\beta \subseteq \alpha^+$? 꼴의 membership test로 대체. BCNF 판정(§11.1)에서 “$F^{+}$의 모든 FD 대신 $F$ 각 원소의 ${\alpha }^{+}$만 보면 충분”한 이유가 바로 이것.

---

5. Lossless Decomposition — FD 기반 판정

표기 해설 — $R=(R_1,R_2)$가 무슨 뜻?

괄호 (...)는 tuple 표기 — 순서대로 나열한 구성 요소. 괄호 안에 무엇이 들어가느냐에 따라 의미가 달라짐.

표기	괄호 안	의미
$R=(A,B,C)$	속성 이름들	”$R$은 속성 $A,B,C$로 이루어진 스키마” — 스키마 정의
$R=(R_1,R_2)$	부분 스키마들	”$R$을 $R_1,R_2$로 분해했다” — decomposition

각 기호 정리 (§2.2에서도 정의됨):

• $R$: 원본 릴레이션 스키마 (속성 이름들의 집합). 예: $R=\{ID,name,dept\_name,building,budget\}$
• $R_1,R_2$: $R$의 부분 스키마 — 각각 $R$ 속성들의 부분집합
  • 조건: $R_1\cup R_2=R$ (두 조각을 합치면 원본 전체 속성)
  • $R_1\cap R_2$: 공통 속성 (join의 연결 고리)
  • 예: $R=\{A,B,C\}$를 $R_1=\{A,B\}$, $R_2=\{B,C\}$로 분해 → 공통 속성은 $B$
• (참고) $r$: 스키마 $R$의 인스턴스 — 실제 튜플이 담긴 테이블. 스키마는 “설계도”, 인스턴스는 “그 설계대로 만든 실제 데이터”

$R=(R_1,R_2)$일 때, 다음 중 적어도 하나가 $F^{+}$에 있으면 lossless decomposition:
$R_1\cap R_2\to R_1\text{또는}{R}_1\cap R_2\to R_2$

직관: 공통 속성이 한쪽 전체를 결정하면, join이 원본 튜플만 복원.
아까 위에서 본 예제 그 상황? | join 시 한쪽이라도 primary.

예시

$R=(A,B,C)$, $F=\{A\to B,B\to C\}$

• $R_1=(A,B),R_2=(B,C)$ → $R_1\cap R_2=\{B\}$, $B\to BC$ 성립 → Lossless
• $R_1=(A,B),R_2=(A,C)$ → $R_1\cap R_2=\{A\}$, $A\to AB$ 성립 → Lossless

Notation: $B\to BC$는 $B\to \{B,C\}$의 축약.

대비 — lossless 비교

케이스	분해	판정
in_dep → instructor, department	공통 dept_name이 department 전체 결정	Lossless
employee → employee1, employee2	공통 name이 어느 쪽도 결정 못 함	Lossy

---

6. Dependency Preservation

6.1 맥락 — 왜 이걸 신경 쓰나

FD는 DBA가 “이 규칙은 항상 지켜져야 한다”고 선언한 법규야 (§4.4의 holds on). 법규는 매 INSERT/UPDATE마다 검사되어야 해. 문제는 검사 비용:

• 분해 전 ($R$ 한 덩어리): FD $\alpha \to \beta$의 모든 속성이 $R$ 안에 있음 → SELECT 한 번으로 검사 끝. 싸다.
• 분해 후 ($R_1,R_2,\dots$): 만약 FD 하나의 속성이 여러 $R_i$에 걸쳐 흩어지면 → 검사하려면 먼저 $R_i$들을 JOIN해서 원래 모양 복원해야 함. 매 연산마다 JOIN = 비용 폭발.

핵심 질문

“분해 후에도 원래 $F$의 모든 FD를 한 테이블 안에서 검사할 수 있나?”

• 예 → Dependency Preserving ✓
• 아니오 (JOIN 필요) → NOT Dependency Preserving ✗

6.2 정의 — 쉬운 말로

분해 $\{R_1,\dots ,R_n\}$이 dependency preserving이다 ⇔ $F$의 모든 FD를 각 $R_i$ 안에서만 검사하여 원래 $F$ 전체를 재구성할 수 있음.

엄밀히: 각 $R_i$에 투영된 FD 집합을
$F_i=\{\alpha \to \beta \in F^{+}\mid \alpha \beta \subseteq R_i\}$
로 정의할 때,
$(F_1\cup F_2\cup \cdots \cup F_n{)}^{+}=F^{+}$

말로: “각 조각에서 발견되는 FD들을 합치면 원본 FD 전체가 함의된다”. 즉 쪼개도 제약의 정보 손실이 없음.

6.3 성공 예시 (Dep Preserving ✓)

세팅: $R=(A,B,C)$, $F=\{A\to B,B\to C\}$.
분해: $R_1=(A,B)$, $R_2=(B,C)$.

FD	어디서 검사?
$A\to B$	$R_1$ 안에서 바로 ✓
$B\to C$	$R_2$ 안에서 바로 ✓

두 FD 모두 한 테이블 내에서 검사 가능 → Dependency Preserving.

6.4 실패 예시 (NOT Dep Preserving ✗) — 자세히

세팅: dept_advisor(s_ID, i_ID, dept_name)

실세계 의미:

• i_ID → dept_name: 한 교수는 한 학과에만 소속
• (s_ID, dept_name) → i_ID: 한 학생은 한 학과에서 한 명의 advisor만 가짐

원본 테이블 (분해 전):

s_ID	i_ID	dept_name
s1	i1	CS
s2	i1	CS
s3	i2	Physics

BCNF 위반 (i_ID는 superkey 아닌데 i_ID → dept_name 존재). 분해:

• $R_1=\{i\_ID,dept\_name\}$
• $R_2=\{s\_ID,i\_ID\}$

분해 후 테이블:

advisor_dept(i_ID, dept_name):

i_ID	dept_name
i1	CS
i2	Physics

student_advisor(s_ID, i_ID):

s_ID	i_ID
s1	i1
s2	i1
s3	i2

이제 FD 2 (s_ID, dept_name) → i_ID 검사를 해보자:

• 이 FD의 속성 s_ID, dept_name, i_ID → 세 속성이 세 군데에 흩어짐
  • s_ID: $R_2$에만
  • dept_name: $R_1$에만
  • i_ID: 양쪽 다
• 어느 테이블도 세 속성을 함께 갖지 않음

구체적 시나리오: INSERT 두 개를 동시에 추가한다고 해보자:

• student_advisor에 (s1, i3) 추가 (s1에게 advisor i3 지정)
• advisor_dept에 (i3, CS) 추가 (i3는 CS 소속)

원본 FD 2 관점에서: 이제 s1이 CS에서 advisor i1과 i3를 동시에 갖게 됨 → 위반. 그런데 이걸 탐지하려면:

1. student_advisor ⋈ advisor_dept JOIN → 원래 모양 복원
2. JOIN 결과에서 (s_ID, dept_name) 그룹별로 i_ID가 유일한지 검사

매 INSERT마다 JOIN — 비용 폭발. 어떻게 분해해도 세 속성을 한 테이블에 담을 수 없음 → NOT Dependency Preserving.

6.5 왜 이게 현실 문제인가

1. 제약 위반 탐지 불가능 or 극도로 느림 — 매 연산에 JOIN이 끼면 TPS 급감.
2. SQL의 표현력 한계 — 표준 PK/FK/UNIQUE로는 multi-table 제약을 선언 못 함. ASSERTION이 있지만 거의 구현되지 않음 (§13 SQL과의 괴리).
3. 일관성 보장 포기 — 실무에선 트리거나 애플리케이션 레벨 체크로 땜빵 → 코드 복잡도 ↑ + 버그 리스크 ↑.

6.6 BCNF와의 긴장 관계

이 예시가 보여주는 것:

• dept_advisor는 BCNF로 가려면 dep preservation을 포기해야 함.
• 반대로 dep preservation을 지키려면 BCNF를 포기하고 3NF에 머물러야 함 (§8에서 봄: 같은 스키마가 3NF에는 속함).

이게 BCNF vs 3NF 트레이드오프의 핵심 — BCNF는 중복 제거의 이상형이지만, 일부 스키마에서는 dep preservation과 양립 불가.

한 줄 요약

Dependency preservation = “쪼갠 뒤에도 원래 규칙들을 각 조각 안에서 검사 가능하게 남겨두는 속성”. 이게 깨지면 규칙 검사에 JOIN 필요 → 매 연산마다 비싸짐. BCNF와 항상 양립하진 않고, 3NF는 항상 양립.

---

7. Boyce-Codd Normal Form (BCNF)

7.1 정의

$R$이 FD 집합 $F$에 대해 BCNF에 있다 ⇔ $F^{+}$의 모든 FD $\alpha \to \beta$ (단, $\alpha \subseteq R$, $\beta \subseteq R$)에 대해 다음 중 적어도 하나가 성립:

1. $\alpha \to \beta$가 trivial ($\beta \subseteq \alpha$)
2. $\alpha$가 $R$의 superkey

7.2 위반 예시

in_dep(ID, name, salary, dept_name, building, budget)

• dept_name → building, budget — 성립
• 그러나 dept_name은 superkey 아님 → BCNF 위반

분해:

instructor(ID, name, salary, dept_name)  ← BCNF
department(dept_name, building, budget)  ← BCNF

7.3 BCNF 분해 규칙

BCNF를 위반하는 FD $\alpha \to \beta$에 대해 $R$을 두 스키마로 분해:

• $(\alpha \cup \beta )$
• $(R-(\beta -\alpha ))$

예시 — in_dep에서 $\alpha =dept\_name$, $\beta =\{building,budget\}$:

• $(\alpha \cup \beta )=(dept\_name,building,budget)$
• $(R-(\beta -\alpha ))=(ID,name,dept\_name,salary)$

7.4 BCNF와 Dependency Preservation

• BCNF와 dependency preservation을 동시에 달성하는 것이 항상 가능한 것은 아니다.
• 예: dept_advisor(s_ID, i_ID, dept_name), $F=\{i\_ID\to dept\_name,s\_ID,dept\_name\to i\_ID\}$
  • i_ID는 superkey 아님 → BCNF 위반.
  • 어떤 분해도 s_ID, dept_name → i_ID의 세 속성을 한 릴레이션에 두지 못함 → dependency preserving 아님.

---

8. Third Normal Form (3NF)

8.1 정의

$R$이 3NF에 있다 ⇔ $F^{+}$의 모든 FD $\alpha \to \beta$에 대해 다음 중 적어도 하나 성립:

1. $\alpha \to \beta$가 trivial ($\beta \subseteq \alpha$)
2. $\alpha$가 $R$의 superkey
3. $\beta -\alpha$의 각 속성 $A$가 $R$의 어떤 candidate key에 포함 (각 속성은 서로 다른 candidate key에 속해도 됨)

관찰:

• BCNF ⇒ 3NF (앞 두 조건이 BCNF와 동일).
• 3번째 조건은 BCNF의 최소한의 완화로, dependency preservation을 보장하기 위해 도입.

8.2 3NF 예시

dept_advisor(s_ID, i_ID, dept_name), $F=\{i\_ID\to dept\_name,s\_ID,dept\_name\to i\_ID\}$

• Candidate keys: $\{s\_ID,dept\_name\}$, $\{s\_ID,i\_ID\}$
• BCNF 위반 (i_ID가 superkey 아님).
• 그러나 3NF:
  • s_ID, dept_name → i_ID: 좌변이 superkey ✓
  • i_ID → dept_name: i_ID가 superkey는 아니지만, $\{dept\_name\}-\{i\_ID\}=\{dept\_name\}$이 candidate key의 일부 ✓

8.3 3NF의 Redundancy 잔존

R = (J, K, L), $F=\{JK\to L,L\to K\}$.
인스턴스:

J	L	K
$j_1$	$l_1$	$k_1$
$j_2$	$l_1$	$k_1$
$j_3$	$l_1$	$k_1$
null	$l_2$	$k_2$

• 정보 중복: $l_1\to k_1$이 반복.
• null 필요: $(l_2,k_2)$ 관계를 표현하려면 $J$에 null.

8.4 BCNF vs 3NF 비교

측면	BCNF	3NF
중복	없음 (이상적)	일부 허용
Dependency preservation	보장 안 됨	항상 달성 가능
Lossless	달성 가능	달성 가능
Null 값	일반적으로 불필요	필요할 수 있음

3NF의 장점: lossless + dependency preservation을 항상 동시에 달성 가능.

---

9. How Good is BCNF? — Multivalued 동기

inst_info(ID, child_name, phone) — instructor가 여러 자녀, 여러 전화번호를 가질 수 있음.

ID	child_name	phone
99999	David	512-555-1234
99999	David	512-555-4321
99999	William	512-555-1234
99999	William	512-555-4321

• non-trivial FD 없음 → 이미 BCNF.
• 그러나 명백한 insertion anomaly: 새 phone 981-992-3443을 추가하려면 자녀 David, William 각각에 대해 두 튜플을 삽입해야 함.

해결 — Higher Normal Forms

분해:

• inst_child(ID, child_name) = {(99999, David), (99999, William)}
• inst_phone(ID, phone) = {(99999, 512-555-1234), (99999, 512-555-4321)}

이는 Fourth Normal Form (4NF) — multivalued dependency 기반. (Chapter 7.6에서 다룸)

---

10. Functional-Dependency Theory

10.1 Closure $F^{+}$ 계산 — Armstrong’s Axioms

Armstrong’s Axioms(건전 + 완전)로 $F^{+}$를 계산:

규칙	내용
Reflexive rule	$\beta \subseteq \alpha$이면 $\alpha \to \beta$
Augmentation rule	$\alpha \to \beta$이면 $\gamma \alpha \to \gamma \beta$
Transitivity rule	$\alpha \to \beta$, $\beta \to \gamma$이면 $\alpha \to \gamma$

성질:

• Sound: 실제로 성립하는 FD만 생성.
• Complete: 성립하는 모든 FD를 생성.

10.2 추가 규칙 (axioms로부터 유도 가능)

규칙	내용
Union rule	$\alpha \to \beta$ 그리고 $\alpha \to \gamma$이면 $\alpha \to \beta \gamma$
Decomposition rule	$\alpha \to \beta \gamma$이면 $\alpha \to \beta$ 그리고 $\alpha \to \gamma$
Pseudotransitivity rule	$\alpha \to \beta$ 그리고 $\gamma \beta \to \delta$이면 $\alpha \gamma \to \delta$

10.3 $F^{+}$ 예시

$R=(A,B,C,G,H,I)$, $F=\{A\to B,A\to C,CG\to H,CG\to I,B\to H\}$

$F^{+}$의 원소들:

• $A\to H$ — transitivity ($A\to B$, $B\to H$)
• $AG\to I$ — $A\to C$ augment with $G$ → $AG\to CG$, 그리고 $CG\to I$와 transitivity
• $CG\to HI$ — $CG\to I$ augment → $CG\to CGI$; $CG\to H$ augment → $CGI\to HI$; transitivity

10.4 $F^{+}$ 계산 절차

F⁺ := F
repeat
    for each f in F⁺
        apply reflexivity and augmentation to f, add results to F⁺
    for each pair f₁, f₂ in F⁺
        if combinable by transitivity
            add result to F⁺
until F⁺ does not change

10.5 Attribute Set Closure ${\alpha }^{+}$

속성 집합 $\alpha$에 대해 $F$ 하에서 $\alpha$로부터 함수적으로 결정되는 모든 속성의 집합을 closure ${\alpha }^{+}$라 한다.

알고리즘:

result := α
while (changes to result) do
    for each β → γ in F do
        if β ⊆ result then
            result := result ∪ γ

10.6 ${\alpha }^{+}$ 예시 — $(AG{)}^{+}$

$F=\{A\to B,A\to C,CG\to H,CG\to I,B\to H\}$

1. result = AG
2. $A\to B,A\to C$ 적용 → result = ABCG
3. $CG\to H$ 적용 (CG ⊆ ABCG) → result = ABCGH
4. $CG\to I$ 적용 → result = ABCGHI

AG가 candidate key인지 판정:

1. Superkey 여부: $AG\to R$? — $A{G}^{+}=ABCGHI=R$ ✓
2. 어떤 부분집합이 superkey 인지: $A\to R$?, $G\to R$?
   • 각 크기 $n-1$ 부분집합을 검사.

---

11. Algorithms for Decomposition

11.1 Testing for BCNF

비자명 FD $\alpha \to \beta$가 BCNF를 위반하는지:

1. ${\alpha }^{+}$를 계산.
2. ${\alpha }^{+}$가 $R$의 모든 속성을 포함하는지 (즉 superkey인지) 확인.

Simplified test: $F^{+}$의 모든 FD를 검사할 필요 없이 $F$의 FD만 검사하면 충분 — $F$의 FD가 모두 BCNF를 준수하면 $F^{+}$의 FD도 준수.

주의: simplified test는 $R$ 자체를 검사할 때만 유효. 분해 후의 $R_i$를 검사할 때는 $F$만으로는 부정확.

• 예: $R=(A,B,C,D,E)$, $F=\{A\to B,BC\to D\}$. $R_2=(A,C,D,E)$ 검사 시 $F$의 어느 FD도 $R_2$의 속성만을 포함하지 않아 BCNF 같아 보이지만, $F^{+}$에 있는 $AC\to D$로 인해 $R_2$는 BCNF 위반.

11.2 BCNF Decomposition Algorithm

result := {R}
done := false
compute F⁺
while (not done) do
    if (there is a schema Rᵢ in result that is not in BCNF)
    then begin
        let α → β be a non-trivial FD holding on Rᵢ
            such that α → Rᵢ is not in F⁺, and α ∩ β = ∅
        result := (result − Rᵢ) ∪ (Rᵢ − β) ∪ (α, β)
    end
    else done := true

각 $R_i$는 BCNF이며, 분해는 lossless-join.

11.3 BCNF Decomposition — 예시

class(course_id, title, dept_name, credits, sec_id,
      semester, year, building, room_number, capacity, time_slot_id)

FDs:

• $course\_id\to title,dept\_name,credits$
• $building,room\_number\to capacity$
• $course\_id,sec\_id,semester,year\to building,room\_number,time\_slot\_id$

Candidate key: $\{course\_id,sec\_id,semester,year\}$.

Step 1: $course\_id\to title,dept\_name,credits$가 성립하지만 $course\_id$는 superkey 아님 → 분해

• course(course_id, title, dept_name, credits) ← BCNF
• class-1(course_id, sec_id, semester, year, building, room_number, capacity, time_slot_id)

Step 2: class-1에서 $building,room\_number\to capacity$ 성립하지만 $\{building,room\_number\}$는 superkey 아님 → 분해

• classroom(building, room_number, capacity) ← BCNF
• section(course_id, sec_id, semester, year, building, room_number, time_slot_id) ← BCNF

11.4 Testing for 3NF

• $F$의 FD만 검사해도 됨.
• 각 FD $\alpha \to \beta$에 대해:
  • $\alpha$가 superkey인지 (attribute closure로 검사) → OK
  • 아니면 $\beta$의 각 속성이 어떤 candidate key에 포함되는지 검사.
• candidate key 찾기는 expensive.
• 3NF 검사는 NP-hard, 그러나 3NF 분해는 polynomial time에 가능.

11.5 3NF Decomposition Algorithm

Let Fc be a canonical cover for F
i := 0
for each functional dependency α → β in Fc do
    if none of the schemas Rⱼ (1 ≤ j ≤ i) contains αβ then
        i := i + 1
        Rᵢ := αβ
if none of the schemas Rⱼ contains a candidate key for R then
    i := i + 1
    Rᵢ := any candidate key for R
/* Optionally, remove redundant relations */
repeat
    if any schema Rⱼ is contained in another schema Rₖ
    then /* delete Rⱼ */
        Rⱼ = Rᵢ
        i = i − 1
return (R₁, R₂, ..., Rᵢ)

결과: 각 $R_i$는 3NF이고, 분해는 dependency preserving + lossless-join.

11.6 3NF Decomposition — 예시

cust_banker_branch(customer_id, employee_id, branch_name, type)

FDs:

• $customer\_id,employee\_id\to branch\_name,type$
• $employee\_id\to branch\_name$
• $customer\_id,branch\_name\to employee\_id$

Canonical cover 계산: 첫 번째 FD에서 branch_name이 extraneous (두 번째 FD에 의해 이미 결정됨). → $F_c$:

• $customer\_id,employee\_id\to type$
• $employee\_id\to branch\_name$
• $customer\_id,branch\_name\to employee\_id$

For loop으로 각 FD에 대해 스키마 생성:

• $(customer\_id,employee\_id,type)$
• $(employee\_id,branch\_name)$
• $(customer\_id,branch\_name,employee\_id)$

Candidate key 포함 확인: $(customer\_id,employee\_id,type)$가 원 스키마의 candidate key $\{customer\_id,employee\_id\}$를 포함 → 추가 스키마 불필요.

Redundancy 제거: $(employee\_id,branch\_name)$은 $(customer\_id,branch\_name,employee\_id)$의 부분집합 → 삭제.

최종 3NF 스키마:

• $(customer\_id,employee\_id,type)$
• $(customer\_id,branch\_name,employee\_id)$

FD 고려 순서에 결과가 의존하지 않는다.

---

12. Comparison of BCNF and 3NF — 정리

속성	BCNF	3NF
중복 제거	완전	부분
Lossless	항상 가능	항상 가능
Dependency preserving	항상은 아님	항상 가능
Null 값	불필요	필요할 수 있음

---

13. Design Goals

관계형 DB 설계의 목표:

1. BCNF
2. Lossless join
3. Dependency preservation

이 셋을 모두 달성할 수 없으면 다음 중 하나를 수용:

• Dependency preservation 포기 (BCNF 유지)
• 3NF로 완화 (중복 허용)

SQL과의 괴리

• SQL은 superkey 외의 FD를 직접 명시하는 방법이 없다.
• Assertions로 표현 가능하지만 비용이 크고 (거의) 구현되지 않음.
• Dependency preserving 분해라도, 좌변이 key가 아닌 FD를 효율적으로 검사할 SQL 수단이 없다.

---

14. 정규형 요약 테이블

Normal Form	요구 조건 (각 비자명 $\alpha \to \beta$에 대해)
1NF	모든 속성이 atomic
2NF	비주요 속성이 candidate key의 부분집합에 부분 의존하지 않음
3NF	(1) $\alpha$가 superkey, 또는 (2) $\beta -\alpha$의 각 속성이 candidate key에 포함
BCNF	$\alpha$가 superkey
4NF	multivalued dependency 기반 (Chapter 7.6)

포함 관계: $\text{BCNF}\subset \text{3NF}\subset \text{2NF}\subset \text{1NF}$.

---

15. 학습 포인트 — 알고리즘 흐름 정리

1. 스키마와 FD 집합 $F$가 주어진다.
2. Candidate key를 찾는다 — 각 속성 부분집합의 closure를 계산하여 $R$ 전체를 함의하는 최소 집합.
3. Normal form 판정:
   • 각 FD $\alpha \to \beta$에 대해 BCNF/3NF 조건 확인.
4. 좋은 form이 아니면 분해:
   • BCNF 분해 알고리즘 — lossless 보장, dependency preservation은 보장 안 됨.
   • 3NF 분해 알고리즘 — lossless + dependency preservation 보장.
5. 검증: 분해 스키마들의 공통 속성이 한쪽을 결정하는지 확인 (lossless), 모든 FD가 한 릴레이션 안에서 검사 가능한지 확인 (dependency preservation).

---

출처: Database System Concepts, 7th Edition (Silberschatz, Korth, Sudarshan)