Bài giảng Cơ sở dữ liệu ( Databases ) - Chương 5: Dạng chuẩn và Chuẩn hóa

Nội dung text: Bài giảng Cơ sở dữ liệu ( Databases ) - Chương 5: Dạng chuẩn và Chuẩn hóa

1. CƠ SỞ DỮ LIỆU ( Databases ) Ch ươ ng 5: D ạng chu ẩn và Chu ẩn hóa bangtqh@utc2.edu.vn Nội dung 1. Dạng chu ẩn 2. Chu ẩn hóa l ượ c đồ CSDL 3. Bài t ập bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 2
2. 5.1. Dạng chuẩn
   Chu ẩn hóa là gì? – Chu ẩn hóa là k ỹ thu ật dùng để t ạo ra m ột t ập các quan hệ có các đặ c điểm mong mu ốn d ựa vào các yêu c ầu về d ữ li ệu c ủa 1 enterprise – Chu ẩn hóa là 1 cách ti ếp cận từ dướ i lên (bottom-up approach) để thi ết kế CSDL, bắt đầ u từ các mối liên hệ gi ữa các thu ộc tính
   Mục đích c ủa chu ẩn hóa – Lo ại bỏ các b ất th ườ ng c ủa 1 quan h ệ để có đượ c các quan h ệ có c ấu trúc t ốt h ơn, nh ỏ hơn
   Quan h ệ có c ấu trúc t ốt (well-structured relation): – Là quan hệ có sự dư th ừa dữ li ệu là tối thi ểu và cho phép ng ườ i dùng thêm, sửa, xóa mà không gây ra mâu thu ẫn dữ li ệu bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 3 5.1.1.Sự dư thừa dữ li ệu
   Sự ph ụ thu ộc gi ữa các thu ộc tính gây ra s ự d ư th ừa – Ví d ụ: • Điểm các môn h ọc  Điểm trung bình  xếp lo ại • Đị a ch ỉ  zip code TENPHG MAPHG TRPHG NG_NHANCHUC MANV TENNV HONV Nghien cuu 5 333445555 05/22/1988 333445555 Tung Nguyen Dieu hanh 4 987987987 01/01/1995 987987987 Hung Nguyen Quan ly 1 888665555 06/19/1981 888665555 Vinh Pham bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 4
3. 5.1.1.Sự dư thừa dữ li ệu (tt)
   Thu ộc tính đa tr ị trong l ượ c đồ ER  nhi ều b ộ s ố li ệu trong l ượ c đồ quan h ệ
   Ví d ụ: NHANVIEN(TENNV, HONV, NS,DCHI,GT,LUONG, BANGCAP) TENNV HONV NS DCHI GT LUONG BANGCAP Tung Nguyen 12/08/1955 638 NVC Q5 Nam 40000 Trung học Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Trung học Nhu Le 06/20/1951 291 HVH QPN Nu 43000 Đại học Hung Nguyen 09/15/1962 Ba Ria VT Nam 38000 Thạc sỹ bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 5 5.1.1.Sự dư thừa dữ li ệu (tt)
   Sự d ư th ừa  sự d ị th ườ ng – Thao tác s ửa đổ i: c ập nh ật t ất c ả các giá tr ị liên quan – Thao tác xóa: ng ườ i cu ối cùng c ủa đơ n v ị  mất thông tin v ề đơ n v ị – Thao tác thêm: TENPHG MAPHG TRPHG NG_NHANCHUC MANV TENNV HONV Nghien cuu 5 333445555 05/22/1988 333445555 Tung Nguyen Dieu hanh 4 987987987 01/01/1995 987987987 Hung Nguyen Quan ly 1 888665555 06/19/1981 888665555 Vinh Pham bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 6
4. 5.1.1.Sự dư thừa dữ li ệu (tt)
   Các giá tr ị không xác đị nh – Đặ t thu ộc tính Tr ưở ng phòng vào quan h ệ NHANVIEN thay vì vào quan h ệ PHONGBAN
   Các b ộ gi ả – Khi s ử d ụng các phép n ối bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 7 5.1.1.Sự dư thừa dữ li ệu (tt)
   Một s ố quy t ắc khi thi ết k ế CSDL quan h ệ – NT1 : Rõ ràng v ề m ặt ng ữ ngh ĩa, tránh các s ự ph ụ thu ộc gi ữa các thu ộc tính v ới nhau – NT2 : Tránh s ự trùng l ặp v ề n ội dung đả m b ảo tránh đượ c các d ị th ườ ng khi thao tác c ập nh ật d ữ li ệu • Ph ải có một số thao tác khi thêm mới và cập nh ật vào lượ c đồ quan hệ, cũng nh ư có th ể gây sai hỏng trong tr ườ ng hợp xóa bỏ các bộ – NT3 : Tránh s ử d ụng các thu ộc tính có nhi ều giá tr ị Null • Khó th ực hi ện các phép n ối và k ết h ợp – NT4: Thi ết kế các lượ c đồ quan hệ sao cho chúng có th ể đượ c nối với điều ki ện bằng trên các thu ộc tính là khoá chính ho ặc khoá ngoài theo cách đả m bảo không sinh ra các bộ “gi ả” bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 8
5. 5.1.2. Các dạng chuẩn
   Mỗi một dạng chu ẩn là một tập các điều ki ện trên lượ c đồ nh ằm đả m bảo các tính ch ất của nó (liên quan tới dư th ừa và bất th ườ ng trong cập nh ật)
   Chu ẩn hóa dữ li ệu: quá trình phân tích lượ c đồ quan hệ dựa trên các FD và các khóa chính để đạ t đượ c –Cực ti ểu s ự d ư th ừa –Cực ti ểu các phép c ập nh ật b ất th ườ ng bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 9 5.1.2. Các dạng chuẩn (tt)
   Phân lo ại –Dạng chu ẩn 1 (1NF – first normal form) –Dạng chu ẩn 2 (2NF – second normal form) –Dạng chu ẩn 3 (3NF – third normal form) –Dạng chu ẩn BCNF (Boyce-Codd normal form) –Dạng chu ẩn 4NF bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 10
6. Dạng chuẩn 1
   Đị nh ngh ĩa: quan hệ R đượ c gọi là ở dạng 1NF nếu mi ền giá tr ị của một thu ộc tính ch ỉ ch ứa giá tr ị nguyên tố đơ n, ko phân chia đượ c) và giá tr ị của mỗi thu ộc tính cũng là một giá tr ị đơ n lấy từ mi ền giá tr ị của nó
   Ví d ụ PHONGBAN( MaPHG, TenPHG, DDIEM ) Thu ộc tính đa tr ị PHONGBAN(MaPHG, TenPHG) DDIEM_PHG(MaPHG, DDIEM ) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 11 Dạng chuẩn 1 (tt) Table (Key1, . . . (Key2, . . . (Key3, . . .) ) ) Table1(Key1, . . .) TableA (Key1,Key2 . . .(Key3, . . .) ) Table2 (Key1, Key2 . . .) Table3 (Key1, Key2, Key3, . . .)
   Lượ c đồ g ốc: Table (Key1, aaa. . . (Key2, bbb. . . (Key3, ccc. . .) ) )
   Để th ỏa mãn 1NF chúng ta th ực hi ện – Table1(Key1, aaa . . .) – Table2(Key1, Key2, bbb . .) – Table3(Key1, Key2, Key3, ccc. . .) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 12
7. Dạng chuẩn 1 (tt)
   Vấn đề còn t ồn t ại trong 1NF
   Xét l ượ c đồ DDIEM_PHG(MaPHG, DDIEM ) –Vẫn b ị l ặp l ại MAPHG DIADIEM 1 TP HCM 4 HA NOI – Ẩn ch ứa các ph ụ thu ộc hàm 5 VUNGTAU bộ ph ận 5 NHATRANG 5 TP HCM bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 13 Dạng chuẩn 2
   Ph ụ thu ộc hàm đầ y đủ : Một ph ụ thu ộc hàm X → Y là một ph ụ thu ộc hàm đầ y đủ nếu lo ại bỏ bất kỳ thu ộc tính A nào ra kh ỏi X thì ph ụ thu ộc hàm không còn đúng nữa. ∀ A, A ∈ X, (X – {A}) → Y : là sai.
   Ph ụ thu ộc hàm bộ ph ận:Một ph ụ thu ộc hàm X → Y là ph ụ thu ộc bộ ph ận nếu có th ể bỏ một thu ộc tính A∈ X, ra kh ỏi X ph ụ thu ộc hàm vẫn đúng, điều đó có ngh ĩa là với ∃A∈ X, (X – {A}) → Y bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 14
8. Dạng chuẩn 2 (tt)
   2NF: – Th ỏa mãn 1NF – Ph ụ thu ộc hàm đầ y đủ vào khóa chính
   Với các quan hệ có thu ộc tính khóa đơ n thì ko ph ải xét
   Ch ỉ ki ểm tra các lượ c đồ có ch ứa ph ụ thu ộc hàm bộ ph ận bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 15 Dạng chuẩn 2 (tt)
   Ví d ụ Ph ụ thu ộc vào c ả 2 MaNV, MaDA NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA) Ch ỉ ph ụ thu ộc vào MaDA bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 16
9. Dạng chuẩn 2 (tt)
   Ví d ụ Ph ụ thu ộc vào c ả 2 MaNV, MaDA NV_DA(MaNV, MaDA, Sogio, TenDA, DDiemDA) Ch ỉ ph ụ thu ộc vào MaDA NV_DA(MaNV, MaDA, Sogio) DUAN(MaDA, TenDA) DUAN(MaDA, DDiemDA) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 17 Dạng chuẩn 3
   3NF dựa trên khái ni ệm ph ụ thu ộc bắc cầu.
   Đị nh ngh ĩa: Một lượ c đồ quan hệ R là ở 3NF nếu nó: – Th ỏa mãn 2NF – Không có thu ộc tính không khoá nào của R là ph ụ thu ộc bắc cầu vào khoá chính. bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 18
10. Dạng chuẩn 3 (tt) Ph ụ thu ộc vào MaNV NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG) Ph ụ thu ộc vào MaDV ° Tất cả các thu ộc tính ph ải ph ụ thu ộc vào thu ộc tính khóa - Một vài thu ộc tính ph ụ thu ộc vào thu ộc tính ko ph ải là khóa - Chu ẩn hóa  Tách nhóm các thu ộc tính đó thành quan hệ mới bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 19 Dạng chuẩn 3 (tt) Ph ụ thu ộc vào MaNV NV_DV(MaNV, TenNV, NS, DCHI, MaDV, TenDV, TruongPHG) Ph ụ thu ộc vào MaDV NHANVIEN(MaNV, TenNV, NS, DCHI, MaDV) DONVI(MaDV, TenDV, TruongPHG) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 20
11. Tóm t ắt 3 dạng chuẩn 1-3 NF Nh ận bi ết Cách chu ẩn hóa 1 Quan hệ ko có thu ộc tính đa Chuy ển tất cả quan hệ lặp tr ị và quan hệ lặp ho ặc đa tr ị thành 1 quan hệ mới 2 Ph ụ thu ộc 1 ph ần vào thu ộc Tách thu ộc tính ph ụ thu ộc 1 tính khóa ph ần thành lượ c đồ mới, đả m bảo quan hệ với lượ c đồ liên quan 3 Ph ụ thu ộc ẩn, tồn tại ph ụ Tách các thu ộc tính đó thành thu ộc hàm gi ữa các thu ộc lượ c đồ mới tính ko ph ải là khóa bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 21 Dạng chuẩn Boyce-Codd
    Một lượ c đồ quan hệ R đượ c gọi là ở dạng chu ẩn Boyce-Codd (BCNF) nếu nó – Th ỏa mãn d ạng chu ẩn 3NF – Không có thu ộc tính ph ụ thu ộc hàm vào thu ộc tính không khóa .
    Ví d ụ R A B C D FD1 FD2 FD5 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 22
12. Dạng chuẩn Boyce-Codd(tt)
    Ví d ụ: R (A1,A2,A3,A4,A5) Với các ph ụ thu ộc hàm: A1,A2 → A3,A4,A5 A4 → A2 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 23 Dạng chuẩn Boyce-Codd(tt)
    Nếu m ột l ượ c đồ quan h ệ không tho ả mãn điều ki ện BCNF, th ủ t ục chu ẩn hóa bao g ồm: – Lo ại b ỏ các thu ộc tính khóa ph ụ thu ộc hàm vào thu ộc tính không khóa ra kh ỏi quan h ệ – tách chúng thành m ột quan h ệ riêng có khoá chính là thu ộc tính không khóa gây ra ph ụ thu ộc.
    Ví d ụ trên: R (A1,A2,A3,A4,A5) Với các ph ụ thu ộc hàm: – A1,A2 → A3,A4,A5 – A4 → A2
    lượ c đồ đượ c tách ra nh ư sau: – R1( A4, A2) – R2(A1, A4, A3, A5) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 24
13. Dạng chuẩn Boyce-Codd(tt) ° Ví dụ Ph ụ thu ộc vào c ả 2 MaSV, MaMH SV_MH_GV(MaSV, MONHOC, GIANGVIEN) Ph ụ thu ộc vào MONHOC bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 25 Dạng chuẩn Boyce-Codd(tt) ° Ví dụ Ph ụ thu ộc vào c ả 2 MaSV, MaMH SV_MH_GV(MaSV, MaMH, MaGV) Ph ụ thu ộc vào MONHOC SV_MH(MaSV, MaMH) MH_GV(MaGV, MaMH) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 26
14. 5.1.3. Phân rã l ược đồ quan hệ
    Lượ c đồ quan h ệ chung R(A 1, , A n) –Tập h ợp t ất c ả các thu ộc tính c ủa các th ực th ể.
    Xác đị nh t ập ph ụ thu ộc hàm F trên R.
    Phân rã –Sử d ụng các thu ật toán chu ẩn hóa để tách R thành t ập các l ượ c đồ D = {R 1, , R m}.
    Yêu c ầu –Bảo toàn thông tin – Các l ượ c đồ R i ph ải ở d ạng chu ẩn 3 ho ặc BCNF. bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 27 Phân rã bảo toàn thông tin
    Sau phân rã, CSDL không còn lưu tr ữ quan hệ R nữa mà ch ỉ lưu lại các quan hệ chi ếu của nó R1, R2, ,R n. CSDL ph ải có kh ả năng khôi ph ục lại quan hệ gốc R từ các quan hệ chi ếu này.
    Nếu không khôi ph ục lại đượ c quan hệ R thì vi ệc phân rã không bi ểu di ễn cùng 1 thông tin với CSDL gốc → Phân rã mất mát (lossy decomposition ) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 28
15. Phân rã bảo toàn thông tin (tt)
    Phân rã l ượ c đồ R = (U,F) thành 1 t ập h ợp các l ượ c đồ : R1 = (U 1,F 1) R 2= (U 2, F 2) . R n = (U n,F n)
    Phân rã không m ất mát thông tin n ếu v ới m ỗi th ể hi ện r hợp l ệ c ủa R thì: r = r 1 r2 r n Với r 1 = πU1 (r) r2 = πU2 (r), . rn = πUn (r) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 29 Phân rã bảo toàn thông tin (tt)
    Th ực t ế s ẽ nh ận đượ c nhi ều b ộ ( tuple ) t ừ phép k ết các r 1, r 2, ,r n hơn là các b ộ g ốc ban đầ u  Vậy t ại sao l ại g ọi là m ất mát (lossy ) ??
    Tuy nhi ều bộ hơn nh ưng lại thi ếu thông tin và không có cách nào bi ết đượ c bộ nào là đúng, bộ nào là không đúng với bộ gốc.
    Nhi ều b ộ h ơn nh ưng không đúng ≡ mất mát thông tin bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 30
16. Phân rã bảo toàn thông tin (tt)
    Đị nh lý 5.1 – Phân rã D = {R1(U1), R2(U2)} c ủa R(U) không m ất thông tin đố i v ới t ập PTH F n ếu và ch ỉ n ếu: + • (U 1 ∩ U2) → (U 1) ∈ F , ho ặc + • (U 1 ∩ U2) → (U 2) ∈ F .
    Đị nh lý 5.3 –Nếu phân rã D = {R 1, , R m} c ủa R không m ất thông tin đố i v ới F và phân rã D i = {Q 1, , Q k} c ủa R i không mất thông tin đố i v ới πRi (F) thì D’ = {R 1, , R i-1, Q 1, , Qk, R i+1 , , R m} c ủa R c ũng không m ất thông tin. bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 31 Ví dụ
    Xét l ượ c đồ quan h ệ PERSON(SSN, Name, Address,Hobby) SSN Name Address Hobby 1111111 John 123 Main St. Stamps 1111111 John 123 Main St. Coins 5556667 Mary 7 Lake Dr. Hiking 5556667 Mary 7 Lake Dr. Skating 9876543 Simpson Fox 5 TV Acting
    Nếu phân rã l ượ c đồ trên thành 2 l ượ c đồ : PERSON1(SSN, Name, Address) HOBBY(SSN, Hobby) Vi ệc phân rã này có m ất thông tin không? bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 32
17. Ví dụ
    Ta có: PERSON1 ∩ HOBBY = {SSN} mà SSN là khóa chính c ủa PERSON1 , do đó PERSON1 ∩ HOBBY  PERSON1
    Vậy: Phân rã này không m ất thông tin 33 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa Phân rã bảo toàn phụ thuộc hàm
    Xét l ượ c đồ quan h ệ sau: HASACCOUNT(ClientId, OfficeId, AccountNumber) Với các PTH sau: ClientId, OfficeId  AcountNumber AccountNumber  OfficeId
    Nếu phân rã l ượ c đồ trên thành 2 l ượ c đồ sau: ACCTOFFICE (AccountNumber, OfficeId) ACCTCLIENT (AccountNumber, ClientId) Phân rã trên có m ất mát thông tin không??? bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 34
18. Phân rã bảo toàn PTH (tt)
    Phân rã trên không m ất mát thông tin vì: ACCTOFFICE ∩ ACCTCLIENT ={AccountNumber}
    Do AccountNumber là Primary Key của CCTOFFICE nên: ACCTOFFICE ∩ ACCTCLIENT  ACCTOFFICE
    Nh ưng phân rã này không b ảo toàn ph ụ thu ộc hàm bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 35 Phân rã bảo toàn PTH (tt)
    Ph ụ thu ộc hàm gốc: ClientId, OfficeId  AcountNumber không tồn t ại trong các ph ụ thu ộc hàm c ủa các lượ c đồ phân rã vì: –Cả hai ph ụ thu ộc hàm phân rã đề u không ch ứa đủ các thu ộc tính c ủa ph ụ thu ộc hàm g ốc (1) nên không th ể suy di ễn l ại đượ c ph ụ thu ộc hàm này bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 36
19. Phân rã bảo toàn PTH (tt)
    Cho lượ c đồ R = (U,F)
    D = {R 1(U 1,F 1),R2(U 2,F2), , R (Un,Fn) } là phân rã của R. Phân rã này đượ c gọi là bảo toàn ph ụ thu ộc hàm nếu và ch ỉ nếu F và ∪ Fi là tươ ng đươ ng nhau.
    Nếu 1 ph ụ thu ộc hàm f ∈ F nh ưng không thu ộc bất kỳ Fi nào không có ngh ĩa là phân rã không bảo toàn ph ụ thu ộc hàm nếu f có th ể đượ c suy di ễn từ ∪ Fi – Ch ỉ khi nào f không th ể suy di ễn từ ∪ Fi thì phân rã đó mới không bảo toàn PTH bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 37 Ví dụ
    Phân rã quan h ệ HASACCOUNT AccountNumber ClientId OfficeId B123 111111 SB01 A908 123456 MN08 AccountNumber OfficeId Account Number ClientId B123 SB01 B123 111111 A908 MN08 A908 123456 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 38
20. Ví dụ
    HASACCOUNT và phân rã c ủa nó sau khi chèn thêm 1 hàng AccountNumber ClientId OfficeId Sau khi join 2 lược đồ phân rã lại, phụ thuộc hàm B123 111111 SB01 ClientId,B567 OfficeId  AcountNumber111111 SB01 bị vi phạm A908 123456 MN08 AccountNumber OfficeId Account Number ClientId B123 SB01 B123 111111 B567 SB01 B567 111111 A908 MN08 A908 123456 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 39 Phép chi ếu c ủa t ập ph ụ thu ộc hàm
    Xét l ượ c đồ quan h ệ R =(U,F) và t ập S ⊆ U
    Phép chi ếu c ủa F lên t ập các thu ộc tính S đượ c đị nh ngh ĩa nh ư sau: πS(F) = {X Y|X Y ∈F+ và X ∪ Y⊆ S} bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 40
21. Gi ải thuật phân rã thành BCNF
    R=(U,F) là 1 l ượ c đồ quan h ệ không ở chu ẩn BCNF.
    Gi ải thu ật: Th ực hi ện lặp l ại vi ệc phân chia R thành nh ững l ượ c đồ nh ỏ h ơn sao cho các l ượ c đồ m ới có ít PTH vi ph ạm BCNF h ơn. Gi ải thu ật k ết thúc khi t ất c ả l ượ c đồ k ết qu ả đề u ở d ạng BCNF bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 41 Gi ải thuật phân rã thành BCNF Input R = (U,F) Decom = R While có l ượ c đồ S=(V, F’) trong Decom không ph ải BCNF /*N ếu có X Y ∈F sao cho X ∪ Y ⊆ S và vi ph ạm BCNF, dùng FD này để phân rã*/ – Thay S trong Decom với S1 = (XY, F1) – S2=( (S-Y) ∪ X, F2) v ới F1,F2 là t ất c ả các FD c ủa F’ End Return Decom bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 42
22. Ví dụ
    Cho R= (U,F) U={ABCDEFGH}, F= {ABH  C, A DE, BGH  F, F  ADH, BH  GE}
    Tìm FD vi ph ạm BCNF – (ABH)+ = U , ABH là siêu khóa, ABH  C không vi ph ạm BCNF – A+ ≠ U, A DE vi ph ạm BCNF
    Chia R thành – R1 =(ADE, {A DE}) – R2 = (ABCFGH, {ABH C, BGH F, F  AH, BH G}) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 43 Ví dụ (tt)
    Sau khi phân rã, chú ý đế n 2 ph ụ thu ộc hàm g ốc F  ADH, BH  GE – Chia F ADH thành {F AH, F D} – Chia BH GE thành {BH G, BH E}
    FD, BH E không có ch ỗ trong các phân rã mới (vì không có ràng bu ộc nào có đủ thu ộc tính cho các FD này)
    Nh ưng –FD có th ể suy di ễn t ừ F AH ∈ R2 và ADE ∈ R1 – BH  E có th ể suy di ễn đượ c d ựa vào (BH)+ t ừ R1,R2  Phân rã R1,R2 b ảo toàn ph ụ thu ộc hàm bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 44
23. Ví dụ (tt)
    R1 là BCNF
    Với R2 (ABCFGH, {ABH C, BGH F, F  AH, BH G}) – ABH  C, BGH  F không vi ph ạm BCNF (ABH, BGH đề u là siêu khóa) –F AH vi ph ạm BCNF Vậy Phân rã R2 thành – R21=(FAH, {F AH}) – R22= (FBCG, {} ) R21, R22 đề u là BCNF nh ưng khi đó các Ph ụ thu ộc hàm ABH  C, BGH  F và BH G không có m ặt n ữa và cùng không th ể suy d ẫn đượ c t ừ các PTH c ủa R21, R22 và R1 Phân rã R2 không b ảo toàn ph ụ thu ộc hàm bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 45 Nhận xét
    Vi ệc phân rã R thành R1, R21, R22 không ph ải là duy nh ất.
    Nếu b ắt đầ u t ừ FD F  ADH thì s ẽ có R1= (FADH; {F  ADH}) R2 = (FBCEG,{}) R1,R2 c ũng ở chu ẩn BCNF và 1 s ố FD g ốc c ũng b ị m ất, không th ể suy di ễn đượ c bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 46
24. Tính ch ất c ủa gi ải thu ật phân rã BCNF
    Không m ất mát thông tin
    Nh ưng có th ể không b ảo toàn ph ụ thu ộc hàm
    Là gi ải thu ật không xác đị nh ( nondeterministic ), ph ụ thu ộc vào th ứ t ự các PTH đượ c ch ọn để xét phân rã 47 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa Gi ải thuật phân rã thành 3NF Cho l ượ c đồ R(U,F)
    Bướ c 1: Tìm ph ủ t ối thi ểu G c ủa F
    Bướ c 2: Phân ho ạch G thành các tập ph ụ thu ộc hàm G1, ,G n sao cho mỗi Gi ch ứa các PTH có cùng vế trái
    Bướ c 3: với mỗi Gi, tạo 1 lượ c đồ (Ri, Gi) với Ri ch ứa tất cả thu ộc tính có trong Gi +
    Bướ c 4: Nếu một trong các Ri th ỏa (R i) F = R thì kết thúc, ng ượ c lại đặ t Ro=(R, {}) là 1 lượ c đồ mới. Khi đó R0,R1, , Rn là kết qu ả phân rã. bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 48
25. Tính ch ất c ủa gi ải thu ật phân rã thành 3NF
    Bảo toàn ph ụ thu ộc hàm
    Không m ất thông tin bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 49 Ví dụ
    Cho R= (U,F) v ới U={ABCDEFGH}, F= {ABH  C, A DE, BGH  F, F ADH, BH  GE}
    Ph ủ t ối thi ểu c ủa F là: G={BH C,A D,C E,F A,E F}
    Phân rã thành 5 l ượ c đồ : – R1 (BHC; {BH C}) – R2 (AD; {A D}) – R3 (CE; {C E}) – R4 (FA; {F A}) – R5 (EF; {E F}) +
    Không có l ượ c đồ phân rã nào có (Ri) F = siêu khóa BCGH c ủa R, nên bổ sung thêm l ượ c đồ th ứ 6 – R6 (BCGH;{}) 50 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa
26. Phân rã BCNF thông qua phân rã 3NF
    Vì gi ải thu ật phân rã BCNF có th ể không bảo toàn ph ụ thu ộc hàm  nên phân rã BCNF thông qua phân rã 3NF. Nếu lượ c đồ sau phân rã là BCNF thì dừng, nếu không thì dùng lúc đó mới dùng gi ải thu ật BCNF để phân rã ti ếp 51 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa Ví dụ
    Xét tập thu ộc tính sau: St (Student), C (course), Sem (semester), P (Professor), T (time) và R(room) và tập PTH nh ư sau: St C Sem  P P Sem  C C Sem T  P P Sem T  C R P Sem C T  R P Sem T  C 52 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa
27. Phân rã 3NF bảo toàn FD
    Phân rã thành 4 l ượ c đồ nh ư sau: R1 (St C Sem P; {St C Sem  P}) R2 (P Sem C; {P Sem  C}) R3 (C Sem T P; {C Sem T  P}) R4 (P Sem T R; {P Sem T  R})
    Vì không có phân rã nào hình thành siêu khóa cho lượ c đồ gốc, nên bổ sung thêm lượ c đồ mới (b ướ c 4) R5 ( St T Sem P; {}) 53 bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa Phân rã thành BCNF
    Các phân rã 1 và 3 không ph ải là BCNF vì P Sem  C n ằm trong phân rã 2
    Phân rã 1 đượ c tách thành 2 l ượ c đồ m ới – (P Sem C; {P Sem  C}) – (St Sem P; {})  Phân rã tuy không m ất mát thông tin nh ưng không bảo toàn PTH St C Sem  P bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 54
28. Phân rã thành BCNF
    Phân rã l ượ c đồ 3 thành – (P Sem C; {P Sem  C}) – (P Sem T; {})  Không m ất mát thông tin nh ưng c ũng không b ảo toàn PTH C Sem T  P bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 55 Phân rã thành BCNF
    Kết qu ả cu ối cùng: (P Sem C; {P Sem  C}) (P Sem St) (P Sem T) (P Sem T R; {P Sem T  R}) (St T Sem P) bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 56
29. Bài t ập bangtqh@utc2.edu.vn Ch ươ ng 5 - Dạng chu ẩn và chu ẩn hóa 57