Ch7_Relational_Database_Design

Chapter 7. Relational Database Design

한 줄 핵심: “좋은” 설계는 정보 중복과 null을 최소화하며, 나쁜 스키마는 원본 복원이 가능한(lossless) 분해로 고친다. 좋음의 기준은 함수 종속성(FD) 위에 정의된 **정규형(BCNF/3NF)**이고, BCNF는 모든 비자명 FD의 좌변이 superkey, 3NF는 이를 완화해 dependency preservation을 항상 보장한다.

이 챕터가 답하는 핵심 질문

• Q1. “좋은” 릴레이션 설계란? 나쁜 설계의 증상은?
• Q2. Lossless / Lossy decomposition의 차이는?
• Q3. Functional Dependency(FD)란 정확히 무엇인가?
• Q4. FD로 lossless 분해를 어떻게 판정하나?
• Q5. Dependency preservation이란? 왜 중요한가?
• Q6. BCNF란? 어떻게 판정·분해하나?
• Q7. 3NF란? BCNF와 무엇이 다른가?
• Q8. BCNF로도 부족한 경우(4NF 동기)는?
• Q9. $F^{+}$와 ${\alpha }^{+}$는 어떻게 계산하나? (FD 이론)
• Q10. BCNF / 3NF 분해 알고리즘은?
• Q11. 최종 설계 목표와 SQL과의 괴리는?

---

Q1. “좋은” 릴레이션 설계란 무엇이고, 나쁜 설계의 증상은?

A. 좋은 설계는 정보 중복과 null을 피하며, 나쁜 스키마는 분해(decomposition)로 고친다.

나쁜 설계의 증상을 in_dep(instructor ⋈ department)으로 관찰:

ID	name	salary	dept_name	building	budget
22222	Einstein	95000	Physics	Watson	70000
45565	Katz	75000	Comp. Sci.	Taylor	100000
10101	Srinivasan	65000	Comp. Sci.	Taylor	100000

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

이로 인한 3대 anomaly:

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

해결: in_dep을 instructor와 department로 분해해야 중복이 사라진다. 단, 모든 분해가 좋은 것은 아니다.

---

Q2. Lossless와 Lossy decomposition의 차이는?

A. 분해 후 다시 join하면 원본이 정확히 복원되면 lossless, 원본에 없던 가짜 튜플이 생기면 lossy다.

Lossy 예시: employee(ID, name, street, city, salary)를

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

로 분해 → 같은 이름의 두 직원이 있으면 natural join에 **원본에 없던 가짜 튜플(spurious tuple)**이 생겨 원본 복원 불가.

Lossless 정의: $R=R_1\cup R_2$일 때 모든 인스턴스 $r$에 대해
${\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)=r$
이면 lossless. 만약 $r⊊{\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)$이면 lossy.

직관 — lossless = "가짜 튜플 무발생"

$r\subseteq {\Pi }_{R_1}(r)\bowtie {\Pi }_{R_2}(r)$는 항상 성립(원본 튜플은 절대 사라지지 않음 — 같은 튜플에서 잘린 두 조각은 공통 속성 값이 자동 일치하여 반드시 다시 join됨). 따라서 lossy를 가르는 것은 오직 $\supseteq$ 방향 — join이 가짜 조합을 만드느냐다. 공통 속성이 한쪽의 key이면 조합이 1:1이라 가짜가 불가능.

기호 정리: $R$ = 스키마(속성 이름 집합), $r$ = 인스턴스(실제 테이블), $R_1\cap R_2$ = 공통 속성(join 연결 고리).

---

Q3. Functional Dependency(FD)란 정확히 무엇인가?

A. 좌변 속성 값이 같으면 우변 속성 값도 반드시 같다는 제약으로, key 개념의 일반화다.

현실 제약의 예(대학 DB): 학생·교수는 ID로 유일 식별, 각자 이름 하나, 학과 하나, 학과당 building·budget 하나. 이 모든 제약을 만족하는 인스턴스를 legal instance라 한다.

형식적 정의: $\alpha \subseteq R$, $\beta \subseteq R$일 때 $\alpha \to \beta$가 $R$에 hold on한다는 것은, 임의의 legal $r(R)$에서 두 튜플 $t_1,t_2$가 $\alpha$에서 일치하면 $\beta$에서도 일치함:
$t_1[\alpha ]=t_2[\alpha ]⟹t_1[\beta ]=t_2[\beta ]$

예시 — $r(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도)

FD와 Key

• $K$가 superkey ⇔ $K\to R$
• $K$가 candidate key ⇔ (1) $K\to R$, (2) $K$의 어떤 진부분집합도 $R$을 결정 못 함($\forall \alpha ⊊K,\alpha \nrightarrow R$)
• FD는 superkey로 표현 못 하는 제약도 표현. 예: in_dep에서 dept_name → building, ID → name은 성립하지만 dept_name → salary는 성립 안 함.

활용 두 목적: ① 인스턴스가 $F$ 아래 legal한지 검사(satisfies) ② legal 집합에 제약 부과(holds on).
주의: 특정 인스턴스가 우연히 어떤 FD를 만족해도 모든 legal 인스턴스에서 성립하는 것은 아니다(예: 우연히 name → ID).

Trivial FD: 모든 인스턴스에서 항상 성립. $\alpha \to \beta$는 $\beta \subseteq \alpha$일 때 trivial. 예: ID, name → ID.

Closure $F^{+}$: $F$가 논리적으로 함의하는 모든 FD의 집합. 예: $A\to B,B\to C$이면 $A\to C$도 $F^{+}$에 속함.

---

Q4. FD로 lossless 분해를 어떻게 판정하나?

A. 공통 속성이 한쪽 스키마 전체를 결정하면 lossless다.

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

직관: 공통 속성이 한쪽 전체를 결정하면 join이 원본 튜플만 1:1 복원한다.

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

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

($B\to BC$는 $B\to \{B,C\}$의 축약)

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

가짜 튜플(spurious tuple)이 실제로 생기는 걸 눈으로 보기

원본 employee(name, salary) 두 행 — 동명이인 Kim:

name	salary
Kim	50000
Kim	90000

공통 속성을 name으로 잡고 둘로 쪼개면((name)과 (name, salary)는 의미 없으니, 가짜 발생이 보이는 (name, dept), (name, salary) 식 분해로 생각하자). 핵심은 공통 속성 name이 양쪽 어느 테이블의 키도 아니라는 점이다. 이때 Kim끼리 무차별로 짝지어지면서:

name	dept	salary
Kim	CS	50000
Kim	CS	90000 ← 가짜
Kim	EE	50000 ← 가짜
Kim	EE	90000

원본에 없던 조합(50000-CS가 아닌데 90000-CS 등)이 생긴다. 이것이 lossy. 만약 공통 속성이 한쪽의 키였다면 Kim이 유일해 가짜가 불가능했을 것 → 이래서 “공통 속성 → 한쪽 전체” 조건이 lossless를 보장한다.

---

Q5. Dependency preservation이란? 왜 중요한가?

A. 분해 후에도 원래 모든 FD를 각 테이블 안에서만 검사할 수 있는 성질로, 깨지면 매 갱신마다 join이 필요해 비싸진다.

• 분해 전: FD의 모든 속성이 한 릴레이션에 있어 SELECT 한 번으로 검사 — 싸다.
• 분해 후: FD 속성이 여러 $R_i$에 흩어지면, 검사하려면 먼저 JOIN으로 복원해야 함 — 매 연산마다 JOIN = 비용 폭발.

핵심 질문

“분해 후에도 원래 $F$의 모든 FD를 한 테이블 안에서 검사 가능한가?” → 예면 Dependency Preserving, 아니오(JOIN 필요)면 NOT Dependency Preserving.

엄밀히: 각 $R_i$에 투영된 FD를 $F_i=\{\alpha \to \beta \in F^{+}\mid \alpha \beta \subseteq R_i\}$라 할 때,
$(F_1\cup \cdots \cup F_n{)}^{+}=F^{+}$

실패 예시: dept_advisor(s_ID, i_ID, dept_name), $F=\{i\_ID\to dept\_name,(s\_ID,dept\_name)\to i\_ID\}$.
BCNF 위반(i_ID가 superkey 아님)으로 분해하면 (i_ID, dept_name)과 (s_ID, i_ID)가 된다. 그러면 FD (s_ID, dept_name) → i_ID의 세 속성이 세 군데로 흩어져 어느 테이블도 함께 갖지 못함 → 검사하려면 JOIN 필요 → NOT dependency preserving. 이게 BCNF vs 3NF 트레이드오프의 핵심(dept_advisor는 3NF에는 속함, Q7).

---

Q6. BCNF란? 어떻게 판정하고 분해하나?

A. 모든 비자명 FD의 좌변이 superkey여야 BCNF이며, 위반 FD $\alpha \to \beta$를 기준으로 두 스키마로 쪼갠다.

정의: $R$이 $F$에 대해 BCNF ⇔ $F^{+}$의 모든 FD $\alpha \to \beta$에 대해 다음 중 하나:

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

위반 예시: in_dep(ID, name, salary, dept_name, building, budget) — dept_name → building, budget은 성립하나 dept_name은 superkey 아님 → 위반.

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

BCNF 분해 규칙: 위반 FD $\alpha \to \beta$에 대해 $R$을 분해:

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

예(in_dep, $\alpha =dept\_name$, $\beta =\{building,budget\}$): $(dept\_name,building,budget)$와 $(ID,name,dept\_name,salary)$.

직관 — BCNF 판정과 분해를 한눈에

판정: “모든 화살표(FD)의 꼬리(좌변)가 superkey냐?”만 본다. 좌변이 superkey가 아닌데 우변에 새 정보를 주는 화살표가 하나라도 있으면 → 위반. 그 화살표가 바로 중복의 원인이다(dept_name → building이 있으면 같은 학과가 나올 때마다 building이 반복되니까).

분해: 위반 화살표 $\alpha \to \beta$를 골라 “화살표만 따로 떼어 새 테이블로” 만든다.

• 새 테이블 1 = (좌변 + 우변) = $\alpha \cup \beta$ → 여기서는 $\alpha$가 키가 되어 더는 중복 없음.

• 새 테이블 2 = 원본 - (우변에서 좌변을 뺀 것) → 우변($\beta$의 잉여 부분)을 원본에서 제거. 좌변 $\alpha$는 연결고리(공통 속성)로 남겨둔다 → 그래서 다시 join하면 lossless.

한 스텝씩 — in_dep을 BCNF로 위반: dept_name → building, budget ($\alpha =\{dept\_name\}$, $\beta =\{building,budget\}$, dept_name은 superkey 아님)

• 테이블 1 = $\alpha \cup \beta$ = (dept_name, building, budget) → 여기서 dept_name이 키 ✓
• 테이블 2 = 원본 $-(\beta -\alpha )$ = 원본에서 building, budget 제거 = (ID, name, salary, dept_name) → ID가 키 ✓
• 공통 속성 dept_name이 테이블 1의 키 → join 시 1:1 복원 → lossless ✓
• 두 테이블 모두 모든 FD의 좌변이 키 → BCNF 완성.

BCNF와 dependency preservation: 둘을 동시에 달성하는 것이 항상 가능한 것은 아니다(Q5의 dept_advisor가 반례).

---

Q7. 3NF란? BCNF와 무엇이 다른가?

A. BCNF 조건에 **“우변 잉여 속성이 어떤 candidate key에 포함되면 허용”**이라는 3번째 조건을 추가한 완화형으로, dependency preservation을 항상 달성한다.

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

1. $\alpha \to \beta$가 trivial
2. $\alpha$가 superkey
3. $\beta -\alpha$의 각 속성이 $R$의 어떤 candidate key에 포함(속성마다 다른 candidate key여도 됨)

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

직관 — 3NF의 3번 조건은 "면죄부"

BCNF는 “좌변이 superkey가 아닌 화살표는 전부 위반”이라 엄격하다. 그런데 이 엄격함 때문에 어쩔 수 없이 FD를 두 테이블로 찢어야 하는(= dependency preservation을 깨는) 경우가 생긴다.
3NF는 여기에 **면죄부(3번 조건)**를 준다: “위반처럼 보여도, 우변의 잉여 속성이 어떤 후보키의 일부라면 봐준다.” 왜 봐주나? 우변이 후보키의 일부라는 건 그 속성이 이미 “키 멤버”라 시스템이 어차피 관리하는 핵심 속성이고, 이걸 살려두면 FD를 한 테이블에 보존할 수 있기 때문이다.
요약: BCNF = 무관용, 3NF = “우변이 키의 부품이면 한 번 봐준다” → 그 대가로 약간의 중복은 남지만 FD는 모두 보존된다.

3NF 예시: dept_advisor(s_ID, i_ID, dept_name), $F=\{(s\_ID,dept\_name)\to i\_ID,i\_ID\to dept\_name\}$

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

3NF의 잔존 중복: R=(J,K,L), $F=\{JK\to L,L\to K\}$ (3NF임)에서 $L\to K$ 사실이 반복되고, 일부 관계 표현에 null이 필요할 수 있다.

측면	BCNF	3NF
중복 제거	완전 (이상적)	부분 허용
Lossless	항상 가능	항상 가능
Dependency preservation	항상은 아님	항상 가능
Null 값	일반적으로 불필요	필요할 수 있음

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

---

Q8. BCNF로도 충분치 않은 경우는? (4NF 동기)

A. 서로 독립적인 두 multivalued 속성이 한 테이블에 있으면 BCNF여도 insertion anomaly가 남는다.

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.
• 그러나 새 phone 하나 추가 시 자녀 수만큼 튜플을 넣어야 함 → insertion anomaly.

해결 — Higher Normal Form: 분해

inst_child(ID, child_name)
inst_phone(ID, phone)

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

---

Q9. $F^{+}$와 ${\alpha }^{+}$는 어떻게 계산하나? (FD 이론)

A. $F^{+}$는 Armstrong’s Axioms로, ${\alpha }^{+}$는 속성 집합 closure 알고리즘으로 계산하며, 실무 판정은 주로 ${\alpha }^{+}$를 쓴다.

Armstrong’s Axioms (sound + complete):

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

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

유도 규칙 (axioms로부터 도출): Union ($\alpha \to \beta ,\alpha \to \gamma \Rightarrow \alpha \to \beta \gamma$), Decomposition ($\alpha \to \beta \gamma \Rightarrow \alpha \to \beta ,\alpha \to \gamma$), Pseudotransitivity ($\alpha \to \beta ,\gamma \beta \to \delta \Rightarrow \alpha \gamma \to \delta$).

$F^{+}$ 예시 — $R=(A,B,C,G,H,I)$, $F=\{A\to B,A\to C,CG\to H,CG\to I,B\to H\}$:

• $A\to H$ (transitivity: $A\to B,B\to H$)
• $AG\to I$ ($A\to C$ augment with $G$ → $AG\to CG$, then $CG\to I$)
• $CG\to HI$ ($CG\to I$ augment → $CG\to CGI$; $CG\to H$ augment → $CGI\to HI$; transitivity)

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

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

Attribute Set Closure ${\alpha }^{+}$: $F$ 하에서 $\alpha$로부터 함수적으로 결정되는 모든 속성의 집합.

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

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

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

직관 — closure는 "눈덩이 굴리기"

${\alpha }^{+}$ 계산은 눈덩이 굴리기다. 처음엔 손에 든 속성($\alpha$)만 있다. FD 목록을 훑으며 “좌변이 지금 내 손 안에 다 들어있는” FD를 찾으면, 그 우변을 손에 추가한다(눈덩이가 커짐). 더 이상 추가할 게 없을 때까지 반복. 위 예시에서 AG로 출발 → $A$를 가졌으니 $A\to B,A\to C$ 적용 가능 → ABCG → 이제 $C,G$를 모두 가졌으니 $CG\to H,CG\to I$ 적용 → ABCGHI. 손에 든 게 $R$ 전체가 되면 그게 곧 superkey라는 뜻이다.

Candidate key 판정: ① $A{G}^{+}=R$이면 superkey ✓ ② $A^{+},G^{+}$ 등 모든 크기 $n-1$ 부분집합이 $R$을 결정 못 하면 → AG가 candidate key.

후보키를 직접 구해 보자 — $R=(A,B,C,D)$, $F=\{A\to B,B\to C,C\to D\}$

전략: 어떤 FD의 우변에도 안 나오는 속성은 반드시 모든 후보키에 포함된다(다른 걸로 결정될 방법이 없으니까). 여기서 $A$는 어떤 FD 우변에도 없다 → $A$는 후보키에 필수.

1. $A$부터 시작: $A^{+}=?$
   • A → $A\to B$로 AB → $B\to C$로 ABC → $C\to D$로 ABCD = $R$ ✓
2. $A^{+}=R$ 이므로 $A$가 superkey. 그리고 $A$는 속성 하나뿐이라 더 줄일 수 없음 → $\{A\}$가 유일한 candidate key.
3. 확인: $B^{+}=BCD$ (A 없음 → R 아님), $C^{+}=CD$, $D^{+}=D$ → 모두 superkey 아님. 따라서 후보키는 $\{A\}$ 하나뿐.

체크리스트: ① FD 우변에 한 번도 안 나오는 속성 모으기(필수 키 후보) → ② 그 집합의 closure 계산 → ③ $R$ 전체면 후보키 완성, 부족하면 다른 속성을 하나씩 추가하며 closure가 $R$이 되는 최소 조합 찾기.

$F^{+}$ vs ${\alpha }^{+}$: $F^{+}$는 FD들의 집합(개념적, 보통 전체 생성 안 함), ${\alpha }^{+}$는 속성들의 집합(실무 도구, 다항시간). BCNF/3NF 판정 시 $F^{+}$ 전체 대신 $F$ 각 원소의 ${\alpha }^{+}$만 보면 충분.

---

Q10. BCNF / 3NF 분해 알고리즘은?

A. BCNF는 위반 FD로 반복 분해(lossless 보장, dep-preservation 미보장), 3NF는 canonical cover 기반으로 분해(lossless + dep-preservation 보장)한다.

Testing for BCNF: 비자명 FD $\alpha \to \beta$에 대해 ① ${\alpha }^{+}$ 계산 ② ${\alpha }^{+}$가 $R$ 전체를 포함(superkey)하는지 확인.

• Simplified test: $F^{+}$ 전체 대신 $F$의 FD만 검사하면 충분(원본 $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를 안 담아 BCNF처럼 보이지만 $F^{+}$의 $AC\to D$로 위반.

BCNF Decomposition Algorithm:

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

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

BCNF 분해 예시 — class(course_id, title, dept_name, credits, sec_id, semester, year, building, room_number, capacity, time_slot_id)
FDs: course_id → title, dept_name, credits / building, room_number → capacity / course_id, sec_id, semester, year → building, room_number, time_slot_id. Candidate key = {course_id, sec_id, semester, year}.

• Step 1: course_id → ... 성립하나 superkey 아님 → course(course_id, title, dept_name, credits) + class-1(...)
• Step 2: building, room_number → capacity 성립하나 superkey 아님 → classroom(building, room_number, capacity) + section(course_id, sec_id, semester, year, building, room_number, time_slot_id)

Testing for 3NF: $F$의 FD만 검사. 각 $\alpha \to \beta$에서 $\alpha$가 superkey인지(closure로), 아니면 $\beta$의 각 속성이 어떤 candidate key에 포함되는지. 3NF 검사는 NP-hard, 그러나 3NF 분해는 polynomial time.

3NF Decomposition Algorithm:

Let Fc be a canonical cover for F;  i := 0
for each α → β in Fc do
    if none of Rⱼ (1≤j≤i) contains αβ then
        i := i + 1;  Rᵢ := αβ
if none of Rⱼ contains a candidate key for R then
    i := i + 1;  Rᵢ := any candidate key for R
/* remove redundant relations: if Rⱼ ⊆ Rₖ, delete Rⱼ */
return (R₁, ..., Rᵢ)

→ 각 $R_i$는 3NF, 분해는 dependency preserving + lossless-join.

직관 — Canonical cover는 "FD 집합의 군살 빼기"

Canonical cover $F_c$ = 원래 $F$와 똑같은 것을 함의하면서 가장 군살이 없는 FD 집합. 두 종류의 군살을 뺀다.

• Extraneous(잉여) 속성: FD 좌변/우변에서 빼도 의미가 안 변하는 속성. 예: AB → C인데 사실 A → C만으로 충분하면 좌변의 $B$가 잉여. 판정법: 그 속성을 뺀 closure가 여전히 같은 결과를 주는지 계산해 본다.
• 중복 FD: 다른 FD들로부터 유도 가능한 FD는 통째로 제거.
  또한 좌변이 같은 FD들은 union으로 묶는다(A→B, A→C ⇒ A→BC). 3NF 분해 전에 $F_c$를 구하는 이유: 군살을 빼두면 불필요하게 많은 테이블이 생기는 걸 막아 더 깔끔한 분해가 나오기 때문이다.

3NF 분해 예시 — cust_banker_branch(customer_id, employee_id, branch_name, type)
FDs: customer_id, employee_id → branch_name, type / employee_id → branch_name / customer_id, branch_name → employee_id.

• Canonical cover: 1번 FD의 branch_name이 extraneous(2번 FD가 결정) → 제거.
• For loop 생성: (customer_id, employee_id, type), (employee_id, branch_name), (customer_id, branch_name, employee_id).
• (customer_id, employee_id, type)가 candidate key 포함 → 추가 불필요.
• Redundancy 제거: (employee_id, branch_name)이 다른 스키마의 부분집합 → 삭제.
• 최종: (customer_id, employee_id, type), (customer_id, branch_name, employee_id). FD 고려 순서와 무관하게 동일한 결과.

---

Q11. 최종 설계 목표와 SQL과의 괴리는?

A. 목표는 BCNF + lossless + dependency preservation이며, 셋을 다 못 얻으면 dep-preservation을 포기(BCNF 유지)하거나 3NF로 완화한다.

설계 목표: ① BCNF ② Lossless join ③ Dependency preservation.

• 셋 다 불가하면: dependency preservation 포기(BCNF 유지) 또는 3NF로 완화(중복 허용) 중 하나 수용.

SQL과의 괴리:

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

---

부록. 정규형 요약

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

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

문제 풀이 흐름: 스키마 + $F$ 주어짐 → candidate key 찾기(${\alpha }^{+}$ 이용) → 정규형 판정 → 위반 시 분해(BCNF는 lossless만, 3NF는 lossless + dep-preservation) → 검증.

---

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