Bài giảng Cơ sở dữ liệu - Chương 4: Thiết kế cơ sở dữ liệu quan hệ - Hồ Cẩm Hà

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 4: Thiết kế cơ sở dữ liệu quan hệ - Hồ Cẩm Hà

1. CHƯƠNG 4 THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ “Làm thế nào để có một cơ sở dữ liệu tốt?” Hồ Cẩm Hà- ĐHSP HN
2. Quá trình thiết kế CSDL Thế giới thực Tập hợp các yêu cầu và phân tích Các yêu cầu CSDL Thiết kế khái niệm Lược đồ logic Không phụ (trong một mô hình dữ liệu bậc cao) thuộc DBMS Ánh xạ mô hình dữ liệu DBMS cụ thể Lược đồ khái niệm (trong mô hình dữ liệu của một DBMS cụ thể ) Thiết kế vật lý Lược đồHồ trongCẩm Hà- ĐHSP HN (đối với cùng một DBMS cụ thể đó)
3. Cần loại bỏ dư thừa dữ liệu Khi dư thừa dữ liệu dẫn đến những khó khăn khi cập nhật dữ liệu Hồ Cẩm Hà- ĐHSP HN
4. Phụ thuộc hàm. Dạng dư thừa dữ liệu thường gặp Có X→Ytrên R(U): ∀r(R) ∀ t1, t2 ∈ r, t1[X] = t2[X] ⇒ t1[Y]=t2[Y]. Hồ Cẩm Hà- ĐHSP HN
5. Hệ qui tắc suy diễn Amstrong A1. Phản xạ (Reflexivity). Nếu Y ⊆ X thì X→Y A2. Tăng trưởng (Augmentation). Nếu X→Y thì mọi Z⊆U, XZ→YZ A3. Bắc cầu (Transitivity). Nếu X→Y và Y→Z thì X→Z Hồ Cẩm Hà- ĐHSP HN
6. Hệ tiên đề Armstrong là đúng và đủ Hồ Cẩm Hà- ĐHSP HN
7. Các qui tắc suy diễn bổ sung Quy tắc hợp (the union rule) Nếu {X→Y, X→Z} đúng thì X→YZ đúng Quy tắc giả bắc cầu (the pseudotransitivity rule) {X→Y, WY→Z} đúng thì WX→Z đúng Quy tắc tách (the decomposition rule) Nếu (X→Y) đúng và Z⊆Y thì X→Z đúng. Hồ Cẩm Hà- ĐHSP HN
8. Tập phụ thuộc hàm tối tiểu F và G là tương đương nếu F+=G+, ký hiệu F~G. Có thể kiểm tra được F và G, tập nào phủ tập nào và chúng có tương đương hay không (tính X+) Định lí 7.9: Cho tập phụ thuộc hàm F luôn tìm được phủ tối tiểu của F Hồ Cẩm Hà- ĐHSP HN
9. Tập phụ thuộc hàm tối tiểu Tập PTH F là tối tiểu nếu: 1. Vế phải của mỗi phụ thuộc trong F gồm đúng một thuộc tính. 2. Không thể bỏ đi một phụ thuộc nào trong F mà vẫn thu được một tập phụ thuộc tương đương với nó. 3. Không thể bỏ đi bất kỳ một thuộc tính nào ở vế trái của một phụ thuộc nào trong F mà vẫn thu được một tập phụ thuộc tương đương với nó. Hồ Cẩm Hà- ĐHSP HN
10. Tập phụ thuộc hàm tối tiểu Cho F = {A→B, B→A, A→C, C→A, B→C}. Có thể tìm được hai tập phụ thuộc tối tiểu tương đương với F F1 = {A→B, B→C, C→A} F2 = {A→B, B→A, A→C, C→A} Hồ Cẩm Hà- ĐHSP HN
11. Phép tách các lược đồ quan hệ Việc tách một lược đồ quan hệ trước hết là thay thế tập U các thuộc tính bằng những tập con U1, U2, , Uk của nó sao cho U = U1 ∪ U2 ∪ ∪ Uk. Chú ý rằng ở đây, ta không đòi hỏi U1, U2, , Uk phải rời nhau. Hồ Cẩm Hà- ĐHSP HN
12. Phép tách các lược đồ quan hệ Khi đó, việc thay thế lược đồ R = 〈U, F〉 bằng các lược đồ con R1 = 〈U1, F1〉, R2 = 〈U2, F2〉, , Rk = 〈Uk, Fk〉 được gọi là một phép tách lược đồ quan hệ đã cho 〈U, F〉. ký hiệu là ρ = (R1, R2, , Rk). Đôi khi, kí hiệu ρ = (U1, U2, , Uk). Hồ Cẩm Hà- ĐHSP HN
13. Phép tách các lược đồ quan hệ Ta sử dụng một số ký hiệu sau: Dấu hoa thị (*) ký hiệu phép kết nối tự nhiên trên giao của hai tập thuộc tính. ρ = (R1, R2, , Rk) hay ρ = (U1, U2, , Uk) là phép tách lược đồ quan hệ trên U thành các lược đồ con tương ứng với các tập con thuộc tính U1, U2, , Uk. ri = là hình chiếu của quan hệ r lên tập con thuộc tính Ui mρ(r) = r1 * r2 * * rk là kết quả của phép kết nối tự nhiên của các hình chiếu của r lên các tập con thuộc tính trong phép tách ρ. Hồ Cẩm Hà- ĐHSP HN
14. Phép tách các lược đồ quan hệ Phép tách U thành {U1, U2, , Uk} được gọi là kết nối không thất thoát (hay ngắn gọn là LJ) nếu với mỗi quan hệ r của lược đồ này, ta đều có r = r1 * r2 * * rk = mρ(r) Phép tách bảo toàn các phụ thuộc của F Hồ Cẩm Hà- ĐHSP HN
15. Tách kết nối không mất thông tin Kiểm tra được tính kết nối không thất thoát của một phép tách (thuật toán 3.2) Ví dụ ABCDE U = ABCDE, U1 = AD, U2 = AB, U3 = BE,U 1 a1 b12 b13 a4 b15 U a a b b b U4 = CDE, U5 = AE 2 1 2 23 24 25 U b a b b a Tập các phụ thuộc hàm là: A→C, B→C, 3 31 2 33 34 5 U b b a a a C→D, DE→C, CE→A. 4 41 42 3 4 5 U5 a1 b52 b53 b54 a5 Hồ Cẩm Hà- ĐHSP HN
16. Tách kết nối không mất thông tin Tập các phụ thuộc hàm là: A→C, B→C, C→D, DE→C, CE→A. ABCDE ABCDE U1 a1 b12 b13 a4 b15 U1 a1 b12 b13 a4 b15 U2 a1 a2 b13 b24 b25 U2 a1 a2 b23 b24 b25 U3 b31 a2 b13 b34 a5 U3 b31 a2 b33 b34 a5 U4 b41 b42 a3 a4 a5 U4 b41 b42 a3 a4 a5 U5 a1 b52 b13 b54 a5 U5 a1 b52 b53 b54 a5 Hồ Cẩm Hà- ĐHSP HN
17. Tách kết nối không mất thông tin Tập các phụ thuộc hàm là: A→C, B→C, C→D, DE→C, CE→A. ABCDE ABCDE U1 a1 b12 b13 a4 b15 U1 a1 b12 b13 a4 b15 U2 a1 a2 b13 b24 b25 U2 a1 a2 b23 a4 b25 U3 b31 a2 b13 b34 a5 U3 a1 a2 a3 a4 a5 U4 b41 b42 a3 a4 a5 U4 a1 b42 a3 a4 a5 U5 a1 b52 b13 b54 a5 U5 a1 b52 a3 a4 a5 Hồ Cẩm Hà- ĐHSP HN
18. Phép tách các lược đồ Mặc dù là những tính chất quan trọng của phép tách lược đồ quan hệ nhưng một phép tách có thể thoả mãn tính chất này nhưng lại không thoả mãn tính chất kia. Chẳng hạn, phép tách lược đồ quan hệ 〈ABCD, {A→B, C→D}〉 thành hai lược đồ 〈AB, {A→B}〉 và 〈CD, {C→D}〉 là phép tách bảo toàn phụ thuộc nhưng không phải là phép tách với kết nối không thất thoát. Hồ Cẩm Hà- ĐHSP HN
19. phép tách các lược đồ Ta xét lược đồ CSZ với ba thuộc tính C (City), S (Street) và Z (Zip code) và tập phụ thuộc hàm F = {CS→Z, Z→C}. Từ phụ thuộc hàm Z→C hay CS∩CZ→CS−CZ suy ra rằng phép tách CSZ thành hai lược đồ CS và CZ có tính chất kết nối không mất thông tin nhưng không có tính chất bảo toàn phụ thuộc. Hồ Cẩm Hà- ĐHSP HN
20. 1NF Hồ Cẩm Hà- ĐHSP HN
21. 2NF Cho lược đồ quan hệ R = 〈U, F〉 với khoá K. R được gọi là thuộc dạng chuẩn thứ hai (2NF) nếu nó thuộc dạng chuẩn thứ nhất và mọi thuộc tính A∉K đều phụ thuộc đầy đủ vào K. Hồ Cẩm Hà- ĐHSP HN
22. 3NF Lược đồ quan hệ R = 〈U, F〉 được gọi là thuộc dạng chuẩn thứ ba (3 NF) nếu không có thuộc tính không khóa phụ thuộc bắc cầu vào khóa Nghĩa là: nếu không tồn tại một khoá X, một tập thuộc tính Y⊆U và một thuộc tính A∉XY làm cho các điều kiện sau được thoả mãn: (X→Y), (Y→A), và không có (Y→X). Hồ Cẩm Hà- ĐHSP HN
23. BCNF Lược đồ quan hệ R = 〈U, F〉 được gọi là thuộc dạng chuẩn Boyce-Codd (BCNF) nếu từ (X→A) đúng trong R và A∉X kéo theo X là siêu khoá. Định lý 7.12 Nếu lược đồ quan hệ R = 〈U, F〉 thuộc dạng chuẩn Boyce-Codd (BCNF) thì nó thuộc dạng chuẩn thứ ba. Hồ Cẩm Hà- ĐHSP HN
24. Chuẩn hoá lược đồ quan hệ Bổ đề 7.7: Giả sử R = 〈U, F〉 là một lược đồ quan hệ và ρ = (R1, R2, Ri, Rk) là một phép tách của R, trong đó ∀i, Ri = 〈Ui, Fi〉. Giả sử ρ là kết nối không thất thoát. Khi đó, nếu thay thế lược đồ Ri trong ρ bởi S1, S2, , Sm, với σ = (S1, S2, , Sm) là phép tách kết nối không thất thoát của Ri thì phép tách τ = (R1, R2, , Ri-1, S1, S2, , Sm, Ri+1, , Rk) thu được cũng là kết nối không thất thoát. Giả sử ρ là kết nối không thất thoát. Nếu bổ sung vào ρ một số lược đồ quan hệ trên U (Rk+1, ,Rn) thì phép tách τ = (R1, R2, , Rk, Rk+1, ,Rn) thu được cũng là kết nối không thất thoát. Hồ Cẩm Hà- ĐHSP HN
25. Chuẩn hoá lược đồ quan hệ Ví dụ Tách để đưa lược đồ về chuẩn BCNF (trang 33) Hồ Cẩm Hà- ĐHSP HN
26. Ví dụ U = CTHRSG F = {C→T, HR→C, TH→R, CS→G, HS→R} Khãa HS U1 = CSG V1 = CTHRS F1 = {CS→G} FV1 = {C→T, TH→R, HR→C, HS→R} Kho¸ CS Khãa HS U2 = CT V2 = CHRS F2 = {C→T} FV2 = {CH→R, HR→C, HS→R} Kho¸ C Kho¸ HS U3 = CHR U4 = CHS F3 = {CH→R, HR→C} F4 = {HS→C} Khãa CH hoÆc HR Khãa HS Hồ Cẩm Hà- ĐHSP HN
27. Phép tách bảo toàn phụ thuộc thành 3NF Nếu có những thuộc tính không xuất hiện trong bất kỳ một phụ thuộc hàm nào của F, ở cả vế trái lẫn vế phải thì ta xác định một lược đồ quan hệ gồm những thuộc tính này rồi xoá chúng khỏi U. Nếu một trong các phụ thuộc hàm của F chứa toàn thể các thuộc tính của U thì phép tách cần tìm chỉ gồm R. Trường hợp còn lại, phép tách kết quả gồm các lược đồ ứng với các tập thuộc tính có dạng XA, trong đómỗi phụ thuộc hàm X→A là thuộc F. Tuy vậy, nếu xảy ra tình huống X→A1, X→A2, , X→Ak cùng thuộc F thì thay cho các lược đồ với tập thuộc tính dạng XAi, ta sử dụng lược đồ ứng với tập thuộc tính XA1A2 Ak vì rõ ràng sự thay thế này cho kết quả gọn hơn. Hồ Cẩm Hà- ĐHSP HN
28. Tách vừa là LJ vừa bảo toàn phụ thuộc §Þnh lý 7.14 Cho R(U) lµ mét l−îc ®å quan hÖ, trong ®ã tËp thuéc tÝnh U = {A1, A2, ,An} vµ F lµ tËp c¸c phô thuéc hµm x¸c ®Þnh trªn R. Kh«ng gi¶m tæng qu¸t, gi¶ sö F lµ mét phñ tèi tiÓu cã d¹ng: F = {Yj → Aij ⏐j=1, 2, , m}. Gäi X lµ mét kho¸ cña l−îc ®å R(U, F). Khi ®ã phÐp t¸ch: ρ = (Y1Ai1, Y2Ai2, , YmAim , X) lµ mét phÐp t¸ch cña R, tháa m·n ba tÝnh chÊt sau: z ρ lµ mét phÐp t¸ch b¶o toµn th«ng tin; z ρ lµ mét phÐp t¸ch b¶o toµn tËp F; z C¸c l−îc ®å con trong ρ ®Òu ë 3NF. Hồ Cẩm Hà- ĐHSP HN
29. Phụ thuộc đa trị Cho R(U); X vµ Y lµ hai tËp con cña U, Z = U \ XY. X→→Y Khi mäi quan hÖ r ∈ R(U) víi hai bé bÊt kú t1, t2 ∈ r: t1[X] = t2[X] ⇒ ∃ t3 ∈ r sao cho t3[X] = t1[X], t3[Y] = t1[Y] vµ t3[Z] = t2[Z]. (v× t1, t2 b×nh ®¼ng nªn ∃ t4 sao cho t4[X] = t1[X], t4[Y] = t2[Y] vµ t4[Z] = t1[Z] ). Chóng ta cã thÓ kÝ hiÖu X →→ Y | Z. Hồ Cẩm Hà- ĐHSP HN
30. Phụ thuộc đa trị NÕu X → Y tho¶ trªn r th× X →→ Y còng tho¶ trªn r. Do vËy mỗi phô thuéc hµm ®Òu lµ phô thuéc ®a trÞ. Hồ Cẩm Hà- ĐHSP HN
31. 4NF L−îc ®å quan hÖ R ®−îc gäi lµ thuéc d¹ng chuÈn thø bèn (4NF) nÕu cã phô thuéc ®a trÞ kh«ng tÇm th−êng X →→ Y ®óng trªn R th× X lµ siªu khãa. Nãi mét c¸ch kh¸c, R lµ 4NF nÕu cã phô thuéc ®a trÞ X →→ Y trªn R , trong ®ã Y ≠ ∅, Y ⊄ X vµ XY kh«ng chøa tÊt c¶ c¸c thuéc tÝnh cña R th× X lµ mét siªu kho¸* cña R Hồ Cẩm Hà- ĐHSP HN
32. Phụ thuộc đa trị và 4NF VÝ dô 7.20 XÐt l¹i l−îc ®å quan hÖ TBK(CTHRSG) cho ë vÝ dô 7.17 cïng víi tËp D c¸c phô thuéc hµm vµ phô thuéc ®a trÞ nh− sau: C→T Mçi líp häc phÇn do mét gi¶ng viªn chÞu tr¸ch nhiÖm. HR→C T¹i mçi phßng häc, trong mçi giê häc chØ cã mét líp häc phÇn. HT→R T¹i mçi giê häc, mçi gi¶ng viªn chØ cã thÓ d¹y ®−îc ë mét phßng häc. CS→G §èi víi mçi líp häc phÇn, mçi sinh viªn chØ cã mét ®iÓm ®¸nh gi¸. HS→R T¹i mçi giê häc, mçi sinh viªn chØ cã mÆt ë mét phßng häc. C→→HR TËp c¸c cÆp phßng-giê häc ®−îc x¸c ®Þnh theo mçi häc phÇn mµ kh«ng lÖ thuéc g× vµo bÊt cø thuéc tÝnh nµo kh¸c. Hồ Cẩm Hà- ĐHSP HN
33. VÝ dô t¸ch LJ ®−a vÒ 4NF z XÐt thÊy C →→ HR vi ph¹m 4NF, do vËy t¸ch TBK thµnh (CHR) vµ (CTSG). L−îc ®å con (CHR) cã khãa lµ HR ®· ë d¹ng chuÈn bèn. L−îc ®å (CTSG) cã khãa lµ CS ch−a ë d¹ng chuÈn bèn v× cã C →→ T (suy ratõ C → T) vi ph¹m chuÈn bèn. z T¸ch (CTSG) thµnh hai l−îc ®å con ®Òu ë d¹ng chuÈn bèn lµ (CT) vµ (CSG). z PhÐp t¸ch ρ = {CHR, CT, CSG} lµ phÐp t¸ch - kÕt nèi kh«ng tæn thÊt vµ mçi l−îc ®å trong nã ®Òu ë d¹ng chuÈn bèn. Hồ Cẩm Hà- ĐHSP HN