Chương 9: Chuẩn hóa CSDL- Phép phân rã

Chương 9Chuẩn hóa CSDL- Phép phân rã1Các vấn đề gặp phải khi tổ chức CSDLDư thừa dữ liệu:Ví dụ: cho lược đồ quan hệ sauThi(MASV,HOTEN,MONHỌC,DIEMTHI) và một thể hiện trên lược đồ quan hệ Thi:2Các vấn đề gặp phải khi tổ chức CSDLBất thường khi cập nhật: Do dư thừa nên khi cập nhật họ tên của một sinh viên trong một bộ nào đó nhưng vẫn để lại họ tên cũ trong những bộ khác. Bất thường khi chèn (insertion anomaly)Không thể biết họ tên của một sinh viên nếu hiện tại sinh viên đó không dự thi môn nào.Bất thường khi xoá (deletion anomaly). Ngược lại, khi xoá tất cả các môn thi của một sinh viên, vô ý làm mất dấu vết để tìm ra họ tên của sinh viên này. 3Chuẩn hóa cơ sở dữ liệuChuẩn hóa: Là quá trình phân rã những quan hệ chưa đạt bằng cách chia nhỏ những thuộc tính của nó ra thành những quan hệ nhỏ hơnVí dụ: Phân rã lược đồ quan hệ Thi thành ba lược đồ quan hệ:Sinhvien(MASV,HOTEN)MonHoc(MAMH, TENMON)Ketqua(MASV,MAMH,DIEMTHI)4Chuẩn hóa cơ sở dữ liệu5MASVHOTEN00CDTH189Nguyễn Văn Thành00CDTH211Trần Thu HàMASVMAMHDIEMTHI00CDTH189M2700CDTH189M2900CDTH211M3500CDTH189M38MAMHTENMONM1Cơ sở dữ liệuM2Cấu trúc dữ liệuM3Kỹ thuật lập trìnhCác khái niệm liên quan đến dạng chuẩnThuộc tính khoá/không khoáA là một thuộc tính khoá nếu A có tham gia vào bất kỳ một khoá nào của quan hệ, ngược lại A gọi là thuộc tính không khoá.Ví dụ:Cho lược đồ quan hệ Q(ABC) và tập phụ thuộc hàm F={ A→ B; A → C; B → A}Có hai khóa là A và B. khi đó thuộc tính khoá là A, B; thuộc tính không khóa là: C 6Thuộc tính phụ thuộc đầy đủ-phụ thuộc hàm đầy đủA là một thuộc tính phụ thuộc đầy đủ vào tập thuộc tính X nếu X →A là một phụ thuộc hàm đầy đủ Phụ thuộc hàm X →A gọi là đầy đủ là không tồn tại X' X sao cho X' → A F+Ví dụ: Cho Q(ABC) và F={ A → B; A→ C; AB → C}A →B: A → C là các phụ thuộc hàm đầy đủ. AB → C không là phụ thuộc hàm đầy đủ vì có A → C.Chú ý rằng, một phụ thuộc hàm mà vế trái chỉ có một thuộc tính là phụ thuộc hàm đầy đủ.7Thuộc tính phụ thuộc trực tiếp-phụ thuộc hàm trực tiếpA là một thuộc tính phụ thuộc trực tiếp vào tập thuộc tính X nếu X →A , không tồn tại Z  U, X Z, ZA thì XA là phụ thuộc trực tiếp. Nếu ngược lại thì được gọi là phụ thuộc hàm bắc cầu.Ví dụ: Cho Q(ABC) F={ A → B; A→ C; C → B}C →B; A → C là các phụ thuộc hàm trực tiếp. A → B là phụ thuộc hàm bắc cầu vì tồn tại CQ A → C, C → B 8Dạng chuẩn 1 (1NF)Lược đồ quan hệ Q được gọi là đạt dạng chuẩn1 (1NF) nếu và chỉ nếu toàn bộ các thuộc tính của Q đều mang giá trị đơn.Ví dụ: xét quan hệ -không đạt chuẩn 1 (?)9Dạng chuẩn 1 (1NF)Đưa quan hệ trên về dạng chuẩn 1 như sau10Dạng chuẩn 2 (2NF)Một lược đồ quan hệ Q đạt dạng chuẩn 2 nếu Q đạt dạng chuẩn 1 và tất cả các thuộc tính không khoá của Q đều phụ thuộc đầy đủ vào khoá.Nếu một lược đồ quan hệ không đạt chuẩn 2 thì ta nói nó đạt dạng chuẩn 1.Ví dụ: Cho Q(A,B,C,D) và F={ AB → CD; B → D; C→ A}Khoá là {A,B} và {B,C}. D là thuộc tính không khoá; AB → D không là phụ thuộc hàm đầy đủ vì có B → D. Vậy Q đạt chuẩn 1.11Dạng chuẩn 2 (2NF)Ví dụ: Xác định dạng chuẩn của lược đồ quan hệ sau. Q(GMVNHP) với F={G→N;G→H; G→P; M→V; NHP→M}Khoá của Q là G.Thuộc tính không khoá là M,V,N,H,P.Do các phụ thuộc hàm G → M; G → V; G → N; G → H; G → P là các phụ thuộc hàm đầy đủ, nên lược đồ quan hệ Q đạt dạng chuẩn 212Dạng chuẩn 2 (2NF)Giải thuật kiểm tra lược đồ quan hệ đạt 2NFCho lược đồ quan hệ Q, tập phụ thuộc hàm F B1: Tìm tất cả khóa K của Q B2: Với mỗi khóa K, tìm bao đóng của tất cả tập con thực sự S của K.B3: Nếu có S+ chứa thuộc tính không khóa thì Q không đạt 2NF, ngược lại thì Q đạt 2NF13Dạng chuẩn 2 (2NF)Ví dụ: Q(A,B,C,D) F={AB→C; B→D; BC→A}. Q có đạt 2 NF khôngD là thuộc tính không khóa Q không đạt 2NF14Dạng chuẩn 2 (2NF)Hệ quả:Q đạt 2NF nếu Q đạt 1NF và tập thuộc tính không khoá của Q bằng rỗng.Nếu khoá của quan hệ có một thuộc tính thì quan hệ đó ít nhất đạt chuẩn 2.Ví dụ: Q(ABCDEH) F={A → E; C → D; E → DH}Khoá của Q là K={ABC}D là thuộc tính không khoá và C →D , vì C là tập con thực sự của khoá nên Q không đạt 2NF15Dạng chuẩn 3 (3NF)Định nghĩa 1: Một lược đồ quan hệ Q đạt dạng chuẩn 3 nếu mọi phụ thuộc hàm X→AF+ ( F là tập phụ thuộc không hiển nhiên định nghĩa trên Q, A là thuộc tính đơn, X là tập thuộc tính con của tập Q), thì một trong hai điều kiện sau được thoả:Hoặc X là một siêu khoá của QHoặc A là một thuộc tính khoáNhận xét: Nếu Q đạt chuẩn 3 thì Q đạt chuẩn 216Dạng chuẩn 3 (3NF)Ví dụ: cho R(C,S,Z), F = {CS →Z, Z →C}Khóa dự tuyển: CS và SZ Tất cả các thuộc tính đều là thuộc tính khóaR đạt 3NFVí dụ: R(A,S,I,P), F={SI →P, S →A},Khóa: SIS →A nhưng S là tập con của khóa và A là thuộc tính không khóa R không đạt 2NF  R không đạt 3NF17Dạng chuẩn 3 (3NF)Định nghĩa 2: Một lược đồ quan hệ R đạt dạng chuẩn 3 (3NF) nếu nó đạt dạng chuẩn 2 và không có thuộc tính không khóa phụ thuộc bắc cầu vào khóa chính.Ví dụ: R (Cust_ID, Name, Salesperson, Region)F = { Cust_ID → {Name, Salesperson, Region}, Salesperson → Region }Khóa K = Cust_IDPhụ thuộc hàm bắc cầu:Cust_ID →Salesperson → Region không đạt 3NF18Dạng chuẩn 3 (3NF)Giải thuật kiểm tra lược đồ quan hệ đạt 3NFCho lược đồ quan hệ Q, tập phụ thuộc hàm F B1: Tìm tất cả khóa của Q B2: Tạo một tập phụ thuộc hàm tương đương (F1tt) với vế phải của các phụ thuộc hàm chỉ chứa một thuộc tính.B3: Nếu mọi phụ thuộc hàm XA ∈ F1tt với A∉ X, X là siêu khóa hoặc A là thuộc tính khóa thì Q đạt 3NF, ngược lại thì Q không đạt 3NF19Dạng chuẩn 3 (3NF)Ví dụ: Cho Q(ABCD) và tập phụ thuộc hàm F=(AB → C ; D → B; C → ABD)K1=[AB]; K2=[AD]; K3=[C] là các khoá, vậy Q không có thuộc tính không khoá nên Q đạt chuẩn 3Hệ quả: Nếu lược đồ quan hệ Q, F mà Q không có thuộc tính không khoá thì Q đạt chuẩn 3.20Dạng chuẩn 3 (3NF)Ví dụ: Xác định dạng chuẩn của lược đồ quan hệ Q(NGPM), tập phụ thuộc hàm F={NGP→M; M→P}Khoá của Q là {NGP}, {NGM} NGP → M có vế trái là siêu khoáM → P có vế phải là thuộc tính khoá.Q đạt chuẩn 3.21Dạng chuẩn 3 (3NF)Ví dụ: cho Q(A,B,C,D) F={AB →C; D→B; C→ABD}, Q đạt 3NF?, TN= ∅ TG={ABCD}22Dạng chuẩn 3 (3NF)K1 = {AB}; K2 = {AD}; K3 ={C} , mọi phụ thuộc hàm XAF với A là thuộc tính khóa Q đạt 3NF 23Dạng chuẩn BCNF(Boyce-Codd)Một lược đồ quan hệ Q ở dạng chuẩn BCNF nếu với mỗi phụ thuộc hàm không hiển nhiên X → A  F thì X là một siêu khoá của Q.Nhận xét: Nếu Q đạt BCNF thì Q đạt 3NFVí dụ: Xác định dạng chuẩn của lược đồ quan hệ sau. Q(ACDEIB) F={ACD→EBI;CE→AD}Q có hai khoá là: ACD và CE. Các phụ thuộc hàm của F đều có vế trái là siêu khoá, nên Q đạt dạng chuẩn BC.24Dạng chuẩn BCNF(Boyce-Codd)Giải thuật kiểm tra BCNFB1: Tìm tất cả khóa của Q B2: Tạo tập phụ thuộc hàm tương đương (F1tt) mà vế phải của các phụ thuộc hàm chỉ chứa một thuộc tính.B3: Nếu mọi phụ thuộc hàm XA ∈ F1tt với A∉ X, X là siêu khóa, thì Q đạt chuẩn BCNF, ngược lại thì không đạt25Dạng chuẩn BCNF(Boyce-Codd)VD: Cho Q(A,B,C,D,E,I) F={ACD→EBI;CE→AD}. Q đạt chuẩn BCNF?F ≡ Ftt={ACD→E,ACD→B,ACD→I,CE→A,CE→D}Vế trái của Ftt đều là siêu khóa  Q đạt BCNF26Bài tập1.Cho biết dạng chuẩn cao nhất của các LDQH sau:a) Q(ABCDEG) F = {A ->BC, C->DE, E->G}b) Q(ABCDEGH) F = {C->AB, D->E, B->G}c) Q(ABCDEGH) F = {A->BC, D->E, H->G}d) Q(ABCDEG) F = {AB->C, C->B, ABD->E, G->A}e) Q(ABCDEGHI) F = {AC->B, BI->ACD, ABC->DH->I , ACE->BCG, CG->A}2.Cho Q(CDEGHK) và F = {CK->H, C->D,E->C, E->G, CK->E}a) Chứng minh EK->DHb) Tìm tất cả các khóa của Qc) Xác định dạng chuẩn cao nhất của Q27Phân rã (Decompositions)Phân rã một lược đồ quan hệ R: là thay thế lược đồ quan hệ R bằng các lược đồ quan hệ R1, R2, Rn, mà mỗi lược đồ quan hệ này chứa tập con thuộc tính của R, sao cho:R=R1R2 RnMỗi Ri là tập con của R ( với i = 1,2,n)Ví dụ: Lược đồ quan hệ R(x, y, z) có thể có 2 tập con: R1(x, z) và R2(y, z), nếu hội R1 và R2, ta được R = R1  R2 28Phân rã (Decompositions)Mục đích của việc phân rã:Giảm sự dư thừa bằng cách phân rã một quan hệ thành nhiều quan hệ ở dạng chuẩn cao hơn.Vấn đề với việc phân rã:Nếu RR1R2 Rn thì phép phân rã là mất mát thông tin29Phân rã (Decompositions)Ví dụ: 30Phân rã (Decompositions)Phép phân rã không bảo toàn thông tin31Phân rã (Decompositions)Sự phân rã mất thông tin:32Phân rã (Decompositions)Sự phân rã mất thông tin:33Phân rã (Decompositions)Sự phân rã mất thông tin:34Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Phép phân rã bảo toàn thông tin: Cho lược đồ quan hệ R và tập phụ thuộc hàm F. Phép phân rã R thành hai lược đồ với tập thuộc tính X và Y được gọi là phép phân rã bảo toàn thông tin đối với F nếu mọi thể hiện r của R thỏa mãn F ta luôn có:35 Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Ví dụ:36Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Thuật toán kiểm tra phân rã bảo toàn thông tinCho lược đồ quan hệ R, tập phụ thuộc hàm F và phép phân rã của R: D={R1, R2, , Rm} Bước 1: Lập ma trận m hàng ứng với m lược đồ con Ri và n cột ứng với n thuộc tính của R. Phần tử (i,j)của ma trận được xác định như sau:(i,j) = aj nếu Aj∈ Ri(i,j)=bij nếu Aj∉Ri trong đó, aj, bij∈ Dom(Aj)37Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Bước 2: Biến đổi bảngVới mỗi FD XY nếu có hai hàng giống nhau trên X và khác nhau trên Y thì làm cho hai hàng đó cũng giống nhau trên Y. (ưu tiên làm bằng ký hiệu là aj).Tiếp tục với các phụ thuộc hàm trong bảng (kể cả việc lập lại các phụ thuộc hàm đã áp dụng) cho đến khi không còn áp dụng được nữa.Mục đích của việc biến đổi bảng là để thu được bảng cuối cùng, xem như một quan hệ thỏa tập F.38Phép phân rã bảo toàn thông tin (LossLess-join decomposition) Bước 3: Xem bảng kết quảNếu trong bảng cuối cùng có chứa hàng gồm toàn ký hiệu a thì kết luận phép phân rã D= (R1,R2,Rm) là bảo toàn thông tin, ngược lại thì D là phân rã mất thông tin39Phép phân rã bảo toàn thông tin (LossLess-join decomposition)VD: Phân rã lược đồ quan hệ Q(ABCDE) thành Q1(AD), Q2(AB), Q3(BE), Q4(CDE), Q5(AE) và tập F={A→C, B→C, A→D, DE→C, CE→A}Phép phân rã trên có bảo toàn thông tin không?40Phép phân rã bảo toàn thông tin (LossLess-join decomposition)ABCDEQ1(AD)a1b1b2a4b3Q2(AB)a1a2b4b5b6Q3(BE)b7a2b8b9a5Q4(CDE)b10b11a3a4a5Q5(AE)a1b12b13b14a541ACABCDEQ1(AD)a1b1b2a4b3Q2(AB)a1a2b4 b2b5b6Q3(BE)b7a2b8b9a5Q4(CDE)b10b11a3a4a5Q5(AE)a1b12b13 b2b14a5Phép phân rã bảo toàn thông tin (LossLess-join decomposition)42BCABCDEQ1(AD)a1b1b2a4b3Q2(AB)a1a2b4 b2b5b6Q3(BE)b7a2b8 b2b9a5Q4(CDE)b10b11a3a4a5Q5(AE)a1b12b4 b2b14a5ADABCDEQ1(AD)a1b1b2a4b3Q2(AB)a1a2b4 b2b5 a4b6Q3(BE)b7a2b8 b2b9a5Q4(CDE)b10b11a3a4a5Q5(AE)a1b12b4 b2b14 a4a5Phép phân rã bảo toàn thông tin (LossLess-join decomposition)43DECABCDEQ1(AD)a1b1b2 a3a4b3Q2(AB)a1a2b4 b2 a3b5 a4b6Q3(BE)b7a2b8 b2 a3b9a5Q4(CDE)b10b11a3a4a5Q5(AE)a1B12b4 b2 a3b14 a4a5CEAABCDEQ1(AD)a1b1b2 a3a4b3Q2(AB)a1a2b4 b2 a3b5 a4b6Q3(BE)b7 a1a2b8 b2 a3b9a5Q4(CDE)b10 a1b11a3a4a5Q5(AE)a1b12b4 b2 a3b14 a4a5Phép phân rã bảo toàn thông tin (LossLess-join decomposition)44ADABCDEQ1(AD)a1b1b2 a3a4b3Q2(AB)a1a2b4 b2 a3b5 a4b6Q3(BE)b7 a1a2b8 b2 a3b9 a4a5Q4(CDE)b10 a1b11a3a4a5Q5(AE)a1b12b4 b2 a3b14 a4a5Dòng Q3(BE) chứa toàn giá trị aj  Phép phân rã trên là bảo toàn thông tinPhép phân rã bảo toàn thông tin (LossLess-join decomposition)Ví dụ 1: Cho lược đồ quan hệ R(A,B,C,D,E) và tập phụ thuộc hàm F={AC,E; EA,D; C,DB}. Phép phân rã thành: R1(A,B,C,E), R2(A,C,D), R3(D,E). Kiểm tra phép tách có bảo toàn thông tin không?45Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Ví dụ 2: Cho lược đồ quan hệ R(A,B,C,D), tập phụ thuộc hàm F={A →B, B→C, A→D, D→C}.Phép tách lược đồ thành các lược đồ con: R1(A,B),R2(A,C),R3(B,D). Kiểm tra phép tách có bảo toàn thông tin không?46Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Định lý: (Q1, Q2) là phép phân rã của lược đồ quan hệ Q và F là tập phụ thuộc hàm  là phép phân rã không mất mát thông tin nếu và chỉ nếu Q1 ∩ Q2  Q1-Q2 hoặc Q1 ∩ Q2  Q2-Q147Phép phân rã bảo toàn thông tin (LossLess-join decomposition)Ví dụ: Q(SAIP), Q1(SA) , Q2(SIP), F={S→A, SI→P}Q1Q2= SAIP = Q+Q1Q2= S → Q1-Q2= A=> Phép phân rã bào toàn thông tin48Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Tập phụ thuộc hàm Fi của QiNếu Q(A1,A2,An) là lược đồ quan hệ, F tập phụ thuộc hàm, ρ(Q1,Q2,,Qk) là phép phân rã bảo toàn thông tin, ri là quan hệ của Qi thì tính chất sau thỏa: ri chỉ thỏa các phụ thuộc hàm X→Y∈F+ với XY ⊆QiTập phụ thuộc hàm của Qi chính là Fi với Fi+={X→Y ∈ F+: XY ⊆ Qi}. Nghĩa là F được phân rã thành các F1,...,Fk49Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Địnhnghĩa: Gọi ρ=(Q1,Q2,,Qk) là phép phân rã của lược đồ quan hệ Q, và tập phụ thuộc hàm F.Hình chiếu của F trên một tập các thuộc tính của Qi ký hiệu ΠQi(F) là tập các phụ thuộc hàm X→Y ∈F+ sao cho XY ⊆QiΠQi(F) = Fi+ = {X→Y ∈F+| XY ⊆Qi}Ta nói phân rã ρ bảo toàn tập phụ thuộc hàm F nếu: F ≡ ∪ΠQi(F) ⇔F+= (∪ΠQi(F))+ với i=1..kHệquả: F+⊇(∪ΠQi(F))+với i=1..k50Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Nhận xét:Từ hệ quả trên ta suy ra: để xác định phép phân rã  ρ=( Q1 ,Q2 ,,Qk) có bảo toàn phụ thuộc hàm hay không, với mỗi phụ thuộc hàm X→Y ∈F ta xác định nếu nó thành viên của tập phụ thuộc hàm G=∪ΠQi(F) thì phép phân rã là bảo toàn phụ thuộc hàm.51Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition ) 52Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bước 3: Tính F+:A→B, A→C, A→AB, A→BC, A→AC, A→ABC, B→A, B→C, B→AB, B→BC, B→AC, B→ABC, C→A, C→B, C→AB, C→AC, C→BC, C→ABC, AB→C, AB→BC, AB→AC, AB→ABC, AC→B, AC→AB, AC→BC, AC→ABC, BC→A, BC→AB, BC→AC, BC→ABCBước 4: Tính ΠQ1(F), ΠQ2(F), ΠQ1(F)=F1+={A→B, A→AB, B→A, B→AB}ΠQ2(F)=F2+={B→C,B→BC,C→B,C→BC}53Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bước 5: G = ΠQ1(F)∪ΠQ2(F) = {A→B, A→AB, B→A, B→AB, B→C, B→BC, C→B, C→BC}F={A→B,B→C,C→A} có A→B, B→C đều là thành viên của G.Để kiểm tra C→A có là thành viên của G hay không ta tính CG+. CG+=ABC ⇒C→A cũng là thành viên của G. Vậy phép phân rã trên bảo toàn phụ thuộc hàm.54Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bài toán trên có thể được giải theo các bước đơn giản sau cho từng lược đồ quan hệ con: Q1(A,B)Bước 1: liệt kê tất cả tập con của Q1: ∅, A, B, ABBước 2: Tính bao đóng theo F của các tập con của Q1: ∅+=∅, A+=ABC, B+=ABC, AB+=ABCBước 3: Tính F1+=ΠQ1(F)={A→B, B→A, A→AB, B→AB}55Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Q2(B,C)Bước 4: Kê tất cả tập con của U2: ∅, B, C, BCBước 5: Tính bao đóng theo F của các tập con Của U2: ∅+=∅, B+=ABC, C+=BC, BC+=ABCBước 6: Tính F2+=ΠQ2(F)={B→C, C→B, B→BC, C→BC}Bước 7:G=ΠQ1(F)∪ΠQ2(F)={A→B,A→AB,B→A,B→AB,B→C,B→BC,C→B,C→BC}56Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )F={A→B,B→C,C→A} có A→B, B→C đều là thành viên của G. Kiểm tra C→A có là thành viên của G hay không ta tính CG+=ABC ⇒C→A cũng là thành viên của G. Vậy phép phân rã trên bảo toàn phụ thuộc hàm.57Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Ví dụ: Cho lược đồ quan hệ Q(C,S,Z) và F={CS→Z,Z→C}. Phép tách ρ(Q1,Q2) tách Q thành Q1(S,Z) và Q2(C,Z). Phép tách có bảo toàn phụ thuộc hàm không?Tập con của Q1: ∅, S, Z, SZ Bao đóng của các tập thuộc tính con Q1+: ∅+=∅, S+=S, Z+=ZC, SZ+=CSZF1+chỉ gồm các phụ thuộc hàm hiển nhiênTập con của Q2: ∅, C, Z, CZBao đóng của các tập thuộc tính con Q2+: ∅+=∅, C+=C, Z+=ZC, CZ+=CZ F2+gồm các phụ thuộc: Z→C, Z→ZC58Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )G=ΠQ1(F)∪ΠQ2(F)={Z→C,Z→ZC}≡{Z→C}F = {CS→Z,Z→C}F và G không tương đương. Vậy phép phân rã trên không bảo toàn phụ thuộc hàm.Một phép phân rã có thể bảo toàn thông tin nhưng không bảo toàn phụ thuộc hàm. Ngược lại có thể bảo toàn phụ thuộc hàm nhưng không bảo toàn thông tin.59Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition ) 60 Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Ví dụ: Cho R(ABCD), F={A →B, C →D}, phân rã R thành hai lược đồ R1(AB), R2(CD)Xét ρ(R1, R2), ρ là bảo toàn phụ thuộc hàm vì: F1= {A →B } F2= {C →D } Nhưng không bảo toàn thông tin61Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Thuật toán tìm bao đóng của tập thuộc tính X đối với G=∪ΠQi(F)Vào: phép phân rã ρ(Q1,Q2,,Qk), tập phụ thuộc hàm F, và thuộc tính XRa: XG+Bước 1: Với mỗi phụ thuộc hàm X→Y∈F ta thực hiện từ bước 2 đến bước 4Bước 2: Đặt Z’ = X62Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bước 3: Thế Z’ = Z’∪((Z’∩ Qi+)+∩ Qi+)Bước 4: Nếu ở Qi, Z’ thay đổi thì thực hiện lại bước 3 cho Q đầu tiên, ngược lại kết thúc thuật toán và trả về Z’ chính là bao đóng XG+63Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Thuật toán kiểm tra bảo toàn phụ thuộc hàmVào: ρ=(Q1,Q2,,Qk), FRa: kết luận phép tách ρ bảo toàn hay không bảo toàn phụ thuộc hàmBước 1: Với mỗi phụ thuộc hàm X→Y∈F ta thực hiện từ bước 2 đến bước 3:Bước 2: Tìm bao đóng XG+với G = ∪ΠQi(F)Bước 3: Nếu Y ⊆XG+thì X→Y∈∪ΠQi(F)+Bước 4: Nếu tất cả phụ thuộc X→Y∈F đều thuộc ∪ΠQi(F)+thì ta kết luận phân rã ρbảo toànphụ thuộc hàm ngược lại ρ không bảo toàn phụ hàm647.3.2. Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Ví dụ: cho Q(C,S,Z), F={CS→Z;Z→C}, phân rã Q thành hai lược đồ Q1(S,Z) và Q2(C,Z). Kiểm tra phép tách có bảo toàn phụ thuộc hàm không?Z→C∈ΠQ2(F)⇒Z→C∈G=(ΠQ1(F)∪ΠQ2(F))+Bước1: Z’=CSBước2: Gán Z’=Z’∪((Z’∩Q1+)+∩Q1+) = CS∪(S∩SZ)=CSBước 2 có Z’ không thay đổi, ta sang lược đồ Q2 và tính tiếp Z’657.3.2. Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bước 3: GánZ’=Z’∪((Z’∩Q2+)+∩Q2+)=CS∪(C∩CZ)=CSZ’ không thay đổi và hết lược đồ quan hệ ⇒ngưng không tính tiếp Z’Vậy CSG+= CS⇒CS→Z∉(ΠQ1(F) ∪ΠQ2(F))+phép phân rã không bảo toàn phụ thuộc hàm.667.3.2. Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Ví dụ: Cho Q(A,B,C), F={A→B,B→C,C→A}, Q1(A,B) và Q2(B,C). Phép tách có bảo toàn FD?G = ΠQ1(F) ∪ΠQ2(F) ⊇{A→B,B→C}Ta xác định C→A có thuộc G+Bước 1: Z’=CBước 2: Z’=Z’∪((Z’∩Q1+)+∩Q1+)= C∪(∅∩AB)=CBước 1 và 2 có Z’ không thay đổi, ta sang lược đồ Q2 và tính tiếp Z’677.3.2. Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bước 3: Z’=Z’∪((Z’∩Q2+)+∩Q2+) = C∪((C∩BC)+∩BC)=BCZ’ thay đổi ⇒tính tiếp Z’ bắt đầu từ lược đồ Q1Bước 4:Z’=Z’∪((Z’∩Q1+)+∩Q1+)= BC∪(ABC∩AB)=ABCDo Z’=Q⇒Z’ sẽ không bao giờ thay đổi.Bước 5:CG+=ABC  C→A ∈ (ΠQ1(F)∪ΠQ2(F))+Phép phân rã bảo toàn phụ thuộc hàm.687.3.2. Phân rã bảo toàn phụ thuộc hàm(Dependency-Preserving Decomposition )Bài tập: Kiểm tra các phép tách sau đây có bảo toàn phụ thuộc hàm hay không?Cho Q(A,B,C), tập phụ thuộc hàm F={AB→C, C→A} và phép tách (BC, AC).Cho Q(S,I,D,M) và tập phụ thuộc hàm F = {SI →DM; SD→M; D→M} và (SID, SIM) Cho Q(A,B,C,D), F = {A→B; B→C; A→D;D→C} và phép tách (AB, AC, BD) 697.4 Thiết kế CSDL bằng cách phân rã Phân rã thành dạng chuẩn BC (hoặc dạng chuẩn 3) bảo toàn thông tin.Phân rã thành dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm .707.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinPhép tách thành dạng chuẩn BCNF bảo toàn thông tin Thuật toán tách thành dạng chuẩn BCNF/3NF bảo toàn thông tinBước 1: Tìm tất cả khóa của QBước 2: Tìm phụ thuộc hàm X → A∈F có X không là siêu khóa và AX (vi phạm BCNF). Nếu tìm thấy thì tách Q thành Q1và Q2 theo quy tắc sau:717.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinQ1(XA). Tìm bao đóng của tất cả tập con của XY để suy ra F1=ΠQ1(F)Q2(Q+-A). Tìm bao đóng của tất cả tập con của Q+-A để suy ra F2=ΠQ2(F)Thực hiện thuật toán phân rã (Q1, F1) và (Q2, F2)727.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinNếu không tìm thấy thì xét dạng chuẩn Qi: Nếu mọi phụ thuộc hàm trong Fi đều có vế trái là siêu khóa thì Qi đạt dạng chuẩn BC Nếu có phụ thuộc hàm trong Fi có vế trái là siêu khóa hoặc vế phải là thuộc tính khóa thì Qi đạt dạng chuẩn 3 737.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinVí dụ: Cho Q(S,D,I,M) F={SI→D; SD→M} hãy phân rã thành các lược đồ con đạt chuẩn BCNF.Bước 1: Tìm tất cả khóa của QBước 2: SD→M có SD không là siêu khóa  tách Q thành Q1(SDM) và Q2(SDI).747.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinTính F1=ΠQ1(F) của Q1(SDM) dựa trên FTa được: F1={SDM}757.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinTính F2=ΠQ2(F) của Q2(SID) dựa trên FTa được:F2={SID}767.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinKết quả:777.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinVí dụ: Cho R(S,T,G,P,H,L) và {ST, G,PS, G,TP, S,HL, G,HP}787.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinVí dụ 1: Cho Q (SDIM), F={SI->D, SD->M}Bước 1: Q có một khóa là {SI} Bước 2: Phụ thuộc hàm SD->M có SD không là siêu khóa nên tách: Q1 = (SDM); F1 = {SD->M} Q2 = (SDI); F2 = {SI->D} Để tìm tập phụ thuộc hàm F1, F2 cần tính bao đóng của mọi tập con. Tìm F1: với Q1 = (SDM): bao đóng của mọi tập con ⇒ F1 = {SD->M} Tìm F2: với Q2= (SDI): bao đóng của mọi tập con ⇒ F2 = {SI->D} Bước 3: Mọi phụ thuộc hàm trong F1và F2 đều có vế trái là một siêu khóa nên Q1 và Q2 đạt dạng chuẩn BC. 797.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinVí dụ2: Cho Q(ABCDE), F = {BC->A, C->D, AE->B, B->D, B->E} Bước 1: 2 khóa là {CB, CAE} Bước 2: Từ C->D tách thành: Q1(CD), F1= {C->D}, Khóa C. Đạt dạng chuẩn BC. Q2(CABE), F2= {B->E, CB->A, AE->B} , Khoá Q2: {CB, CAE}. Vậy Q2 đã đạt dạng chuẩn 3. 807.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinVí dụ 3: Cho Q(ABCDEG), F={AE C, CG A, BD G, GA E} Khóa là BDA, BCD =>Q không đạt 2NF vì BD  G.Q phân rã thành Q1(BDG), Q2(ABCDE)Q2 gồm những thuộc tính của Q, trừ thuộc tính trong vế phải của BD->G.Trong Q1 gồm những PTT trong F mà vế trái và vế phải của nó tồn tại trong tập thuộc tính của Q1. F1={BD->G}817.4.1 Phân rã thành dạng BCNF/3NF bảo toàn thông tinBài tập:Phân rã lược đồ thành dạng BC a) Q(S,D,I,M) F={S,I→D;S,D→M} b) Q(A,B,C,D) F={A→B;B→C;D→B} c) Q(C,S,Z) F={C,S→Z; Z→C} 827.4.2 Phân rã thành dạng 3NF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm Phép tách 3NF bảo toàn thông tin và bảo toàn FD;Vào: R = Ra: (R0, R1, R2, , Rk) với các Ri đạt 3NF và  bảo toàn thông tin và bảo toàn phụ thuộc hàmPhương pháp: Bước 1: Xác định phủ tối thiểu của F:F’ = {Xi Ai| i = 1..n}Bước 2: Tìm 1 khoá K bất kì của R.837.4.2 Phân rã thành dạng 3NF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm Bước 3: Xác định lược đồ con R0= với U0= KBước 4: Lần lượt xác định các lượt đồ con Ri= với Ui= Xi, Ai (i=1,..,k) Bước 5: Nếu ij mà QiQj thì loại bỏ Ri. Quá trình này sẽ tiếp tục cho đến khi không thể loại bỏ được một Ri nào nữa.847.4.2 Phân rã thành dạng 3NF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm Ví dụ: Cho R = với U = ABCD, F = {AB, BC, CDA, ACD}Bước 1: Ta có một phủ tối thiểu của F là:F = {AB, BC, CDA, AD}Bước 2: Ta có A là một khoá của R.Bước 3: R0= với F0= Bước 4: R1= R2= R3= R4= Bước 5: Loại R0và R4 Kết luận: = (AB, BC, ACD)857.4.2 Phân rã thành dạng 3NF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm Cho Q(CTHRSG), F={CT, HRC, THR, CSG, HSR}. Hãy phân rã Q thành các lược đồ con đạt 3NF vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.Giải: F=Ftt={CT,HRC,THR,CSG,HSR} là phủ tối thiểu.Áp dụng thuật toán trên Q được phân rã thành các lược đồ con: Q1(CT); Q2(HRC); Q3(THR); Q4(CSG); Q5(HSR) Khóa của Q là HS.Vậy: Q1,Q2,Q3,Q4,Q5 chính là kết quả phân rã86Bài tậpKiểm tra phân rã có bảo toàn thông tin, bảo toàn phụ thuộc hàm hay không?R(CSZ), F={CS → Z, Z → C} có ρ(SZ,CZ) là phép tách của lược đồ quan hệ R.R(ABCD), F={A → B, C → D} có ρ(AB,CD) là phép tách của lược đồ quan hệ R.87Bài tậpCho R(ABCDEFG), F={B->A, D->C, D->EB, DF->G}, phân rã về dạng chuẩn BC bảo toàn thông tin.Cho Q(ABCDEG), F={AE  C, CG  A, BD  G, GA  E}. Tìm tất cả các khóa của Q.Xác định dạng chuẩn của Q.Nếu Q chưa đạt chuẩn 3. Hãy phân rã Q thành các quan hệ đạt chuẩn và bảo toàn thông tin.88Bài tậpCho R(A,B,C,D,E) và F={CDE ->B, AE->BD, DE->C, CE->D, B->CD}Hãy phân rã R thành lược đồ quan hệ đạt tối thiểu dạng chuẩn 3 vừa bảo toàn thông tin vừa bảo toàn phụ thuộc hàm.89Bài tậpCho lược đồ quan hệ R(U, F) với U = ABCDEHIKJ  F = { C -> EHI, HI -> ABC, AC -> DJ, EC -> AB  }Tìm tất cả các khóa của lược đồ quan hệ trênLược đồ quan hệ trên đã thỏa 2NF chưa? Tại sao?Dùng phép tách bảo tồn phụ thuộc hàm để tách R thành các LĐQH thỏa dạng chuẩn 3NFDùng phép tách có nối kết không mất thông tin để tách R thành các LĐQH thỏa 3NF hoặc BCNF90Bài tậpCho Q(SDIBQO) với các phụ thuộc hàm:F={ SD, IB, IS Q, BO}.Lược đồ trên đang tồn tại ở dạng chuẩn cao nhất là bao nhiêu?Hãy tách lược đồ trên thành dạng chuẩn 3NF có nối không mất thông tin và bảo toàn tập phụ thuộc hàm.91Bài tậpCho Q(ABCD) và F={A->B, B->C, A->D, DC}. Tách Q thành Q1(AB), Q2(AC), Q3(BD)a) Có bảo toàn thông tinb) Có bảo toàn phụ thuộc hàm92Dạng chuẩn 2 (2NF)Ví dụ: Cho lược đồ quan hệ và tập phụ thuộc hàm FCungCap(maNCC, tenNCC, diaChi, sanPham, gia)F = { MaNCCTenNCC, DiaChi;MaNCC, SanPhamGia }Khóa: K = {MaNCC, SanPham}Tậpthuộc tính không khóa: {TenNCC, DiaChi, Gia}Ta thấy với pth: MaNCC TenNCC, DiaChi, trong đó tenNCC, diaChi là thuộc tính không khóa, phụ thuộc vào MaNCC là tập con thực sự của khóa K = {maNCC,sanPham} không đạt 2NF93Dạng chuẩn 2 (2NF)Đưa về dạng chuẩn294