CƠ SỞ DỮ LIỆU
Bài 5:
CHUẨN HOÁ
13/08/2012 1 HVĐ – THQL
BÀI TOÁN THỰC TẾ
• Xử lý trường hợp phát hiện các phụ thuộc hàm
không tầm thường trong một lược đồ quan hệ
• Ví dụ:
– ThoiKhoaBieu(Lớp, Môn, Gviên, Phòng, Buổi), lược
đồ có tập khoá là {L, GB, PB}. Giả sử tìm thấy phụ
thuộc hàm L→M
– HoaDonBH(Hdsố, Nlập, Mhang, Sluong, Dgia),
lược đồ có khoá duy nhất là HM. Giả sử tìm thấy phụ
thuộc hàm H→N

13/08/2012 HVĐ – THQL 2
MỤC TIÊU
• Kiến thức
– Tiếp cận phân rã
– Tiếp cận tổng hợp
– Phụ thuộc đa trị
• Kỹ năng
– Tìm phân rã thoả các tiêu chuẩn thiết kế
– Xử lý tình huống phát sinh PTH mới
– Xử lý tình huống gặp phụ thuộc đa trị
• Yêu cầu: áp dụng thực tế
13/08/2012 HVĐ – THQL 3
NỘI DUNG
• Tiếp cận phân rã
• Tiếp cận tổng hợp
• Thảo luận tình huống

2. Nếu tất cả các lược đồ con không vi phạm,
hoặc có vi phạm nhưng kết quả tách không
BTPT thì kết thúc
3. Chọn một lược đồ con nào có vi phạm sao
cho khi tách vẫn BTPT
4. Tách theo vi phạm này
5. Quay về 2

13/08/2012 HVĐ – THQL 8
MINH HOẠ
• Bảo toàn thông tin
• Đặc trưng đầy đủ
• Dạng chuẩn BC
13/08/2012 HVĐ – THQL 9
R(KDHNMLG)
F={
K -> D,
H -> KN,
M -> G,
HM -> L}
H→NK
(KDNHMLG)
(HKN)
(HMLG)
K→D
(KD)
(KNHMLG)
M→G
(MG)
(HML)

THUẬT TOÁN
• Thay F bởi một phủ tối tiểu
• Phát sinh các lược đồ con, với các khoá thiết kế
• Với các lược đồ con có khoá tương đương
– Sát nhập
– Khử phụ thuộc bắt cầu
• Nếu chưa BTTT, bổ sung lược đồ con tạo bởi
các thuộc tính của một khoá bất kỳ

13/08/2012 HVĐ – THQL 14
KHỬ PHỤ THUỘC BẮC CẦU
• Lược đồ
– R = (GHCDAB)
– F = {GH

AD, AG

B, CD

GH, C

A, BH

C}
• Áp dụng thuật toán:
– F đã tối tiểu
– Phát sinh D = {(GHAD), (AGB), (CDGH), (CA), (BHC)}
– Nhóm (GHAD) và (CDGH) được (GHACD)
khử thuộc tính bắc cầu A, kết quả (GH CD)
– Không bổ sung: D = {(GH CD), (AGB), (CA), (BHC)}

• BCNF
• Tối thiểu lược đồ con
13/08/2012 HVĐ – THQL 18
R(KDHNMLG)
F={
K -> D,
H -> KN,
M -> G,
HM -> L
} tối tiểu
{(KD),
(HKN),
(MG),
(HML)}
MINH HOẠ

13/08/2012 HVĐ – THQL 19
• Nhớ bổ sung 2 ràng buộc tồn tại
R(GLMPB)
F={
L -> P,
LM -> G,
BL -> M,
BG -> L
BP -> G
} tối thiểu
{(GLMPB),BL,BP,BG}
{ (LP),
(LMG),
(BLMGP,{BL,BG,BP}) }

• Tiếp cận phân rã
• Tiếp cận tổng hợp
• Thảo luận tình huống
– Tĩnh
– Động
– Phụ thuộc đa trị
13/08/2012 HVĐ – THQL 23
HỆ THỐNG BÁN HÀNG
• Xét lược đồ <R, F>
– R = (HKDNMGL)
– F ={HKN, KD, MG, HML}.
• Thực hiện
– Xác định dạng chuẩn
– Phân rã theo tiếp tập phân rã
– Phân rã theo tiếp cận tổng hợp
• Bỏ M

G, thêm NM

G
13/08/2012 HVĐ – THQL 24
HỆ THỐNG ĐÀO TẠO
• Xét lược đồ <R, F>
– R = (GLMPB)
– F ={LP, LMG, BLM, BGL, BPG}
• Thực hiện
– Xác định dạng chuẩn
– Phân rã theo tiếp tập phân rã
– Phân rã theo tiếp cận tổng hợp
• Bổ sung phụ thuộc hàm L → M