Bài giảng Cơ sở dữ liệu - Bài 5: Chuẩn hóa

Sau khi học xong Bài giảng Cơ sở dữ liệu Bài 5 Chuẩn hóa giúp sinh viên nắm được kiến thức về tiếp cận phân rã, tiếp cận tổng hợp, phụ thuộc đa trị. Các kỹ năng cần có sau khi học là tìm phân rã thỏa các tiêu chuẩn thiết kế.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu - Bài 5: Chuẩn hóa CƠ SỞ DỮ LIỆU Bài 5: CHUẨN HOÁ13/08/2012 HVĐ – THQL 1 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→N13/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ống13/08/2012 HVĐ – THQL 4 TIẾP CẬN PHÂN RÕ Tiếp cận phân rã – Cơ sở lý thuyết – Thủ tục – Minh hoạ• Tiếp cận tổng hợp• Thảo luận tình huống13/08/2012 HVĐ – THQL 5 CƠ SỞ LÝ THUYẾT• Định lý: Với phân rã {(XY), (XZ)}, nếu có XY hoặc XZ thì phân rã là bảo toàn thông tin13/08/2012 HVĐ – THQL 6 THỦ TỤC• Mỗi khi tìm thấy một vi phạm dạng chuẩn, thực hiện phân rã theo định lý trên• Tiêu chuẩn đạt được (BTTT, dạng chuẩn cao)• Vấn đề: BTPT• Mong muốn – Bảo toàn thông tin – Bảo toàn phụ thuộc – Đạt tối thiểu chuẩn 313/08/2012 HVĐ – THQL 7 THUẬT TOÁN1. Phân rã chỉ gồm lược đồ gốc2. 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úc3. Chọn một lược đồ con nào có vi phạm sao cho khi tách vẫn BTPT4. Tách theo vi phạm này5. Quay về 213/08/2012 HVĐ – THQL 8 MINH HOẠR(KDHNMLG) (KDNHMLG)F={ K→D K -> D, (KD) (KNHMLG) H -> KN, M -> G, H→NK (HKN) (HMLG) HM -> L} M→G• Bảo toàn thông tin (MG) (HML)• Đặc trưng đầy đủ• Dạng chuẩn BC13/08/2012 HVĐ – THQL 9 THẢO LUẬN• Làm bài tập13/08/2012 HVĐ – THQL 10 TIẾP CẬN TỔNG HỢP• Tiếp cận phân rã• Tiếp cận tổng hợp – Cơ sở lý thuyết – Thủ tục – Minh hoạ• Thảo luận tình huống13/08/2012 HVĐ – THQL 11 CƠ SỞ LÝ THUYẾT• Định lý: Một phân rã đã bảo toàn phụ thuộc sẽ bảo toàn thông tin nếu có một lược đồ con chứa khoá của lược đồ gốc13/08/2012 HVĐ – THQL 12 THỦ TỤC• Mỗi PTH phát sinh một lược đồ con – Bảo toàn phụ thuộc (thật ra đặc trưng đầy đủ) – Chuẩn BC – Bổ sung lược đồ từ một khoá để BTTT• Vấn đề – Dư thừa lược đồ – Quá nhiều lược đồ con có khoá tương đương nhau• Giải quyết – Tìm phủ tối tiểu trước – Sát nhập lược đồ con có khoá tương đương nhau và xử lý dạng chuẩn13/08/2012 HVĐ – THQL 13 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)}13/08/2012 HVĐ – THQL 15 THẢO LUẬN• Lược đồ – R = (ABCDE) – F = {A  B, B  A, AC  D, BC  E}• Áp dụng thuật toán: – F đã tối tiểu – Phát sinh D = {(AB), (BA), (ACD), (BCE)} – Nhóm …và khử thuộc tính …, kết quả … – Kết luận: …13/08/2012 HVĐ – THQL 16 KẾT QUẢ• Bảo toàn thông tin• Đặc trưng đầy đủ F• Dạng chuẩn tối thiểu 3• Số lược đồ ít nhất13/08/2012 HVĐ – THQL 17 MINH HOẠ R(KDHNMLG) F={ {(KD), K -> D, (HKN), H -> KN, (MG), M -> G, (HML)} HM -> L } tối tiểu • ...