Chương 6: Phụ Thuộc Hàm và Dạng Chuẩn

1. Các Vấn Đề Gặp Phải Khi Tổ Chức CSDL

Khi thiết kế CSDL không tốt, ta gặp phải vấn đề dư thừa dữ liệu, dẫn đến ba loại bất thường:

Ví dụ minh họa

Xét quan hệ SINHVIEN_DIEMTHI(MaSV, MaMH, HoTen, TenMH, Diem):

MaSV	MaMH	HoTen	TenMH	Diem
SV01	CSDL	Nguyễn Tuyết An	Cơ sở dữ liệu	10
SV01	NMLT	Nguyễn Tuyết An	Nhập môn lập trình	9.5
SV01	HDT	Nguyễn Tuyết An	Hướng đối tượng	8.5
SV02	CSDL	Trần Ngọc Minh	Cơ sở dữ liệu	8
SV02	CTRR	Trần Ngọc Minh	Cấu trúc rời rạc	5
SV03	NMLT	Phạm Tiến Dũng	Nhập môn lập trình	7
SV03	CTRR	Phạm Tiến Dũng	Cấu trúc rời rạc	7.5

Vấn đề: HoTen của SV01 lặp lại 3 lần, TenMH của CSDL lặp lại 2 lần → dư thừa dữ liệu.

Ba loại bất thường

Nếu đổi tên SV01 từ “Nguyễn Tuyết An” → “Nguyễn Tuyết Anh” nhưng chỉ sửa 1 dòng (dòng NMLT), các dòng còn lại vẫn là “Nguyễn Tuyết An” → mâu thuẫn dữ liệu.

Muốn thêm sinh viên SV04 (Phan Minh Đức) nhưng chưa đăng ký môn nào → phải để MaMH = NULL → vi phạm ràng buộc khóa chính, không thể thêm.

Nếu SV03 chỉ học 2 môn (NMLT, CTRR), xóa cả 2 dòng → mất luôn thông tin về SV03 (họ tên, ngày sinh,…).

Giải pháp: Tách quan hệ

Tách thành 3 quan hệ riêng biệt:

SINHVIEN(MaSV, HoTen)
MONHOC(MaMH, TenMH)
DIEMTHI(MaSV, MaMH, Diem)

→ Loại bỏ dư thừa, tránh cả 3 loại bất thường trên.

2. Phụ Thuộc Hàm (Functional Dependency)

2.1. Khái niệm cơ bản

X gọi là vế trái của phụ thuộc hàm (PTH).
Y gọi là vế phải của PTH.
X xác định Y, hoặc Y phụ thuộc (hàm) vào X.
Tập tất cả PTH trên quan hệ R ký hiệu là F.

Ví dụ thực tế:

MaNV → TenNV          -- Mã NV xác định tên NV
MaNV, MaDA → ThoiGian -- Cặp (MaNV, MaDA) xác định thời gian làm việc

2.2. Xác định PTH từ dữ liệu — Ví dụ

Xét CTHD(SoHD, MaSP, SL, DonGia, ThanhTien):

SoHD	MaSP	SL	DonGia	ThanhTien
HD01	SP01	5	2.000	10.000
HD01	SP03	2	10.000	20.000
HD02	SP01	5	2.000	10.000
HD02	SP04	2	3.000	6.000
HD03	SP02	4	10.000	40.000
HD03	SP03	4	12.500	50.000
HD03	SP04	8	2.500	20.000

Phân tích từng PTH được đề xuất

PTH	Đúng?	Giải thích
`SoHD → MaSP`	❌	HD01 có SP01 và SP03 → không duy nhất
`SoHD → SL`	❌	HD01 có SL=5 và SL=2 → không duy nhất
`MaSP → DonGia`	❌	SP03 xuất hiện ở 2 dòng: DonGia=10.000 và 12.500 → không duy nhất
`SoHD, MaSP → SL`	✅	Cặp (HD, SP) xác định duy nhất số lượng
`SoHD, MaSP → DonGia`	✅	Cặp (HD, SP) xác định duy nhất đơn giá
`SL → ThanhTien`	❌	HD01/SP03: SL=2, TT=20.000; HD03/SP04: SL=8, TT=20.000 — cùng TT khác SL; ngược lại HD03/SP02: SL=4, TT=40.000; HD03/SP03: SL=4, TT=50.000 → không duy nhất
`DonGia → ThanhTien`	❌	DonGia=10.000 có TT=20.000 và 40.000 → không duy nhất
`SL, DonGia → ThanhTien`	✅	ThanhTien = SL × DonGia → xác định duy nhất
`SoHD, MaSP → SL, DonGia, ThanhTien`	✅	Tổng hợp từ các PTH đúng trên

2.3. Hệ Luật Dẫn Armstrong

Ký hiệu: $F \models X \rightarrow Y$ — “X→Y được suy ra từ F”.

Ba luật cơ bản (Armstrong Axioms)

#	Tên	Phát biểu	Ví dụ
F1	Phản xạ (Reflexivity)	Nếu $Y \subseteq X$ thì $X \rightarrow Y$	`{MaSV, TenSV} → TenSV`
F2	Tăng trưởng (Augmentation)	Nếu $X \rightarrow Y$ thì $XZ \rightarrow YZ$	Từ `MaSV→TenSV` suy ra `MaSV,NgaySinh → TenSV,NgaySinh`
F3	Bắc cầu (Transitivity)	Nếu $X \rightarrow Y$ và $Y \rightarrow Z$ thì $X \rightarrow Z$	Từ `MaSV→MaLop`, `MaLop→TenLop` suy ra `MaSV→TenLop`

Ba luật bổ sung (dẫn xuất từ Armstrong)

#	Tên	Phát biểu	Ví dụ
F4	Kết hợp (Union)	Nếu $X \rightarrow Y$ và $X \rightarrow Z$ thì $X \rightarrow YZ$	`MaSV→TenSV` + `MaSV→GioiTinh` ⟹ `MaSV→TenSV,GioiTinh`
F5	Phân rã (Decomposition)	Nếu $X \rightarrow YZ$ thì $X \rightarrow Y$ và $X \rightarrow Z$	`MaSV→TenSV,GioiTinh` ⟹ `MaSV→TenSV` và `MaSV→GioiTinh`
F6	Tựa bắc cầu (Pseudotransitivity)	Nếu $X \rightarrow Y$ và $YZ \rightarrow W$ thì $XZ \rightarrow W$	`MaSV→MaLop`, `MaLop,MaMon→MaGV` ⟹ `MaSV,MaMon→MaGV`

Bài tập chứng minh

VD10: R(A,B,C,D), F={A→B, A→C, BC→D}. Chứng minh A→D

Bước	PTH	Lý do
1	A→B	Giả thiết
2	A→C	Giả thiết
3	A→BC	F4 (kết hợp 1 và 2)
4	BC→D	Giả thiết
5	A→D	F3 (bắc cầu 3 và 4) ✅

VD11: R(A,B,C,D,E), F={AB→D, C→A, B→E}. Chứng minh BC→DE

Bước	PTH	Lý do
1	C→A	Giả thiết
2	AB→D	Giả thiết
3	BC→D	F6 (tựa bắc cầu 1 và 2: C→A, AB→D ⟹ BC→D)
4	B→E	Giả thiết
5	BC→EC	F2 (tăng trưởng 4 với C)
6	BC→E	F5 (phân rã 5)
7	BC→DE	F4 (kết hợp 3 và 6) ✅

VD12: R(A,B,C,D,E,G,H), F={AB→C, B→D, CD→E, CE→GH, G→A}. Chứng minh AB→E

Bước	PTH	Lý do
1	AB→C	Giả thiết
2	AB→B	F1 (phản xạ, B⊆AB)
3	B→D	Giả thiết
4	AB→D	F3 (bắc cầu 2 và 3)
5	AB→CD	F4 (kết hợp 1 và 4)
6	CD→E	Giả thiết
7	AB→E	F3 (bắc cầu 5 và 6) ✅

2.4. Bao Đóng (Closure)

Bao đóng của tập PTH F

Bao đóng của tập thuộc tính X

Thuật toán tính $X^+_F$

Input:  (R, F), X ⊆ R*
Output: X⁺_F

Bước 1: Khởi tạo X₀ = X
Bước 2: Lặp:
    X_{i+1} = X_i ∪ Z, với mọi Y→Z ∈ F mà Y ⊆ X_i
    (Loại Y→Z khỏi F sau khi dùng)
    Dừng khi X_{i+1} = X_i  hoặc  X_i = R*
Bước 3: Kết luận X⁺_F = X_i cuối cùng

Bài toán thành viên

2.5. Phủ Tối Thiểu (Minimal Cover)

Các khái niệm liên quan

Hai tập PTH tương đương: F ≡ G nếu $F^+ = G^+$ (suy ra được lẫn nhau).

PTH có vế trái dư thừa: $X \rightarrow Y$ có thuộc tính $A \in X$ dư thừa nếu bỏ A đi mà PTH vẫn đúng trong F, tức là $(X - A) \rightarrow Y \in (F - {X\rightarrow Y})^+$.

PTH dư thừa: $X \rightarrow Y \in F$ là dư thừa nếu $X \rightarrow Y \in (F - {X\rightarrow Y})^+$.

Thuật toán tìm Phủ Tối Thiểu

Bước 1: Phân rã vế phải
    Thay mỗi X→Y₁Y₂...Yₙ thành X→Y₁, X→Y₂, ..., X→Yₙ

Bước 2: Loại bỏ thuộc tính vế trái dư thừa
    Với mỗi X→Y có |X| ≥ 2:
        Với mỗi A ∈ X:
            Tính (X-A)⁺ trong F - {X→Y}
            Nếu Y ∈ (X-A)⁺ → A dư thừa, thay X→Y bằng (X-A)→Y

Bước 3: Loại bỏ PTH dư thừa
    Với mỗi X→Y ∈ F:
        Tính X⁺ trong F - {X→Y}
        Nếu Y ∈ X⁺ → X→Y dư thừa, loại khỏi F

VD17: R(A,B,C,D), F={AB→CD, B→C, C→D}. Tìm phủ tối thiểu

Bước 1: Phân rã vế phải

F = {f1: AB→C, f2: AB→D, f3: B→C, f4: C→D}

Bước 2: Loại thuộc tính vế trái dư thừa

Xét f1: AB→C (bỏ f1 khỏi F khi xét):

Bỏ A: $B^+_{{f2,f3,f4}} = B \cup C \cup D = BCD$ → C ∈ BCD ✅ → bỏ A
Bỏ B: $A^+_{{f2,f3,f4}} = A$ → C ∉ A → giữ B
→ f1 viết lại thành B→C (trùng f3, giữ 1 cái)

Xét f2: AB→D (bỏ f2 khỏi F khi xét):

Bỏ A: $B^+_{{f1,f3,f4}} = BCD$ → D ∈ BCD ✅ → bỏ A
Bỏ B: $A^+_{{f1,f3,f4}} = A$ → D ∉ A → giữ B
→ f2 viết lại thành B→D

F = {B→C, B→D, C→D}  (f1 và f3 hợp nhất thành B→C)

(Thực ra slide gộp f1 mới = f3, nên F = {B→C, C→D} sau bước 2 — xem bước 3)

Bước 3: Loại PTH dư thừa

Xét B→C: $B^+{F-{B\rightarrow C}} = B^+{{C\rightarrow D}} = B$ → C ∉ B → không dư thừa
Xét C→D: $C^+{F-{C\rightarrow D}} = C^+{{B\rightarrow C}} = C$ → D ∉ C → không dư thừa

$$\boxed{\text{Phủ tối thiểu: } F = {B \rightarrow C,\ C \rightarrow D}}$$

2.6. Khóa (Key)

Thuộc tính khóa: thuộc tính xuất hiện trong ít nhất một khóa.
Thuộc tính không khóa: không xuất hiện trong bất kỳ khóa nào.
Siêu khóa: tập K’’ mà $K \subseteq K’’$ với K là khóa (siêu khóa không cần tối tiểu).

Thuật toán tìm tất cả Khóa

Bước 1: Xác định tập NGUỒN (N)
    N = {thuộc tính chỉ xuất hiện ở VẾ TRÁI của các PTH}
    Tính N⁺:
    - Nếu N⁺ = R* → Khóa duy nhất là N. DỪNG.
    - Ngược lại → Bước 2.

Bước 2: Xác định tập TRUNG GIAN (TG)
    TG = {thuộc tính xuất hiện ở CẢ vế trái lẫn vế phải}
    Liệt kê tất cả tập con khác rỗng Xᵢ ⊆ TG.

Bước 3: Kiểm tra từng tập
    ∀Xᵢ ⊆ TG:
        Nếu (N ∪ Xᵢ)⁺ = R* 
        → Sᵢ = N ∪ Xᵢ là khóa ứng viên
        → Loại bỏ mọi Xⱼ ⊋ Xᵢ (không cần kiểm tra nữa)

Bước 4: Tập khóa K = {Sᵢ}

VD19: R(A,B,C,D,E,G,H), F={B→A, DA→CE, D→H, GH→C, AC→D}. Tìm tất cả khóa

Bước 1:

Vế trái: B, DA, D, GH, AC → N = {B, G} (chỉ xuất hiện vế trái, không bao giờ ở vế phải)
$BG^+ = BGA \neq R^*$ → tiếp tục

Bước 2:

TG = {A, C, D, H} (xuất hiện cả 2 vế)
Các tập con: {A},{C},{D},{H},{AC},{AD},{AH},{CD},{CH},{DH},{ACD},{ACH},{ADH},{CDH},{ACDH}

Bước 3:

N∪Xᵢ	$(N \cup X_i)^+$	= R*?	Kết luận
BGA	BGA	❌
BGC	BGCADEH	✅	BGC là khóa → loại AC,CD,CH,ACD,ACH,CDH,ACDH
BGD	BGDACEH	✅	BGD là khóa → loại AD,DH,ADH
BGH	BGHACDE	✅	BGH là khóa → loại AH

$$\boxed{\text{Các khóa: } {BGC,\ BGD,\ BGH}}$$

3. Dạng Chuẩn (Normal Forms)

graph LR DC1["1NF\n(Dạng chuẩn 1)"] --> DC2["2NF\n(Dạng chuẩn 2)"] DC2 --> DC3["3NF\n(Dạng chuẩn 3)"] DC3 --> DCBC["BCNF\n(Boyce-Codd)"]

Mỗi dạng chuẩn cao hơn bao hàm dạng chuẩn thấp hơn: BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF.

3.1. Dạng Chuẩn 1 (1NF)

Các loại thuộc tính vi phạm 1NF:

Thuộc tính đa trị (multi-valued): một ô chứa nhiều giá trị (VD: danh sách môn học)
Thuộc tính tổ hợp (composite): một ô gồm nhiều thành phần (VD: địa chỉ = số nhà + đường + phường + quận)

Ví dụ vi phạm 1NF:

DiaChi: "Số 175 Đường 3/2 Phường 10 Quận 5"
→ Không nguyên tố vì có thể tách thành: SoNha, TenDuong, Phuong, Quan

Quan hệ THAMGIA(MaNV, HoTen, NgSinh, MaDA, TenDA, ThoiGian) với một ô MaDA chứa nhiều mã dự án → vi phạm 1NF.

Sau khi chuẩn hóa 1NF (mỗi dòng = 1 dự án), dữ liệu hết đa trị nhưng vẫn trùng lặp HoTen, NgSinh → cần lên 2NF.

3.2. Dạng Chuẩn 2 (2NF)

Thuật toán kiểm tra 2NF

1. Tìm tất cả khóa của R
2. Với mỗi khóa K:
   - Liệt kê tất cả tập con thực sự S ⊂ K (S ≠ K)
   - Tính S⁺
   - Nếu S⁺ chứa thuộc tính KHÔNG KHÓA → R KHÔNG đạt 2NF
3. Nếu không tìm thấy vi phạm → R đạt 2NF

VD26: SINHVIEN(MSSV, MaMH, TenSV, DiaChi, Diem), F={MSSV,MaMH→Diem; MSSV→TenSV,DiaChi}

Khóa: {MSSV, MaMH}
Tập con: {MSSV}, {MaMH}
Xét {MSSV}: $MSSV^+ = {MSSV, TenSV, DiaChi}$
TenSV, DiaChi là thuộc tính không khóa → SINHVIEN không đạt 2NF

Tách thành 2 lược đồ đạt 2NF:

DANGKY(MSSV, MaMH, Diem)    -- F1: {MSSV,MaMH → Diem}
SINHVIEN(MSSV, TenSV, DiaChi) -- F2: {MSSV → TenSV, DiaChi}

3.3. Dạng Chuẩn 3 (3NF)

Phụ thuộc bắc cầu: Thuộc tính $A$ phụ thuộc bắc cầu vào X nếu tồn tại Y sao cho:

$X \rightarrow Y \in F^+$ và $Y \rightarrow A \in F^+$
$Y \not\rightarrow X \in F^+$ (Y không xác định ngược lại X)
$A \notin (X \cup Y)$

Thuật toán kiểm tra 3NF

1. Tìm tất cả khóa → xác định thuộc tính khóa / không khóa
2. Phân rã vế phải: X→Y₁Y₂ thành X→Y₁, X→Y₂,...
3. Với mỗi X→Y (Y∉X):
   - Nếu X là siêu khóa → OK ✅
   - Nếu Y là thuộc tính khóa → OK ✅
   - Nếu cả hai đều không → R KHÔNG đạt 3NF ❌

3.4. Dạng Chuẩn Boyce-Codd (BCNF)

Thuật toán kiểm tra BCNF

1. Tìm tất cả khóa của R
2. Phân rã vế phải thành PTH 1 thuộc tính
3. Với mỗi X→Y (Y∉X):
   - Nếu X là siêu khóa → OK ✅
   - Nếu X không phải siêu khóa → R KHÔNG đạt BCNF ❌

3.5. Dạng Chuẩn của Lược Đồ Quan Hệ và Lược Đồ CSDL

Thuật toán xác định dạng chuẩn của R

1. Tìm mọi khóa của R
2. Kiểm tra BCNF:
   - Đúng → R đạt BCNF. DỪNG.
   - Sai → Bước 3
3. Kiểm tra 3NF:
   - Đúng → R đạt 3NF. DỪNG.
   - Sai → Bước 4
4. Kiểm tra 2NF:
   - Đúng → R đạt 2NF. DỪNG.
   - Sai → R chỉ đạt 1NF (hoặc thấp hơn).

Tổng Kết

graph TD A["Dư thừa dữ liệu\n→ 3 bất thường: Sửa/Thêm/Xóa"] --> B["Phụ thuộc hàm X→Y\n(X xác định duy nhất Y)"] B --> C["Hệ luật Armstrong\nF1 Phản xạ · F2 Tăng trưởng · F3 Bắc cầu\nF4 Kết hợp · F5 Phân rã · F6 Tựa bắc cầu"] C --> D["Bao đóng X⁺\n→ Bài toán thành viên"] D --> E["Phủ tối thiểu\n(tối giản F)"] E --> F["Khóa K\n(K⁺=R*, tối tiểu)"] F --> G["Dạng chuẩn\n1NF → 2NF → 3NF → BCNF"]

Dạng chuẩn	Yêu cầu thêm so với cấp trước
1NF	Mọi thuộc tính có giá trị nguyên tố
2NF	Không có phụ thuộc bộ phận vào khóa
3NF	Không có phụ thuộc bắc cầu vào khóa
BCNF	Mọi vế trái của PTH phải là siêu khóa