Bài giảng Cơ sở dữ liệu - Bài 8: Thiết kế SCDL mức quan niệm - Vũ Văn Định

Bài 8. THIẾT KẾ SCDL MỨC QUAN NIỆM  Trên thực tế, một ứng dụng có thể đựơc phân tích. thiết kế thành nhiều lược đồ CSDL khác nhau. Để đánh giá việc thiết kế một lược đồ CSDL, người ta dựa trên các tiêu chuẩn về sự trùng lặp thông tin, chi phí kiểm tra và các ràng buộc toàn vẹn...  Vậy để tránh sự dư thừa thông tin, ta cần chuẩn hoá tất cả các lược đồ trong quá trình thiết kế. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 1. Phép tách các lược đồ quan hệ - ĐN: Phép tách các lược đồ quan hệ R = { A1, A2, .. An} là việc thay thế lược đồ quan hệ R bằng tập các lược đồ { R1, R2, .., Rk}, trong đó Ri  R, i= 1,..,k và R = R1 R2  ...  Rk Không đòi hỏi các Ri phải là phân biệt - Mục đích : Loại bỏ các dị thường dữ liệu TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Cho lược đồ quan hệ người cung cấp : S(MCTY, ĐC, MH, GIA) với tập pth : MCTY  ĐC MCTY, MH  GIA Có thể được tách thành 2 lược đồ khác là : S1(MCTY, ĐC) và S2 ( MCTY, MH, GIA) như vậy sẽ không mất công lưu địa chỉ của một công ty nhiều lần TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Kết nối không mất mát thông tin - Nếu R là một lược đồ quan hệ được tách thành các lược đồ con R1, R2, .., Rk và D là một tập các phụ thuộc dữ liệu. Nói rằng phép tách là tách - kết nối không mất mát thông tin đối với D nếu với mỗi quan hệ r trên R thoả D: r = R1(r) *  R2 (r) * ... *  Rk(r) tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên các Ri, i= 1..,k TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Kiểm tra phép kết nối không mất mát thông tin Input: R ={ A1, A2, .., An} tập các phụ thuộc hàm và phép tách p =(R1, R2, .., Rk) Output: Phép tách có phải là không mất mát thông tin hay không ? Phương pháp : Thiết lập một bảng với n cột k hàng.; cột thứ j tương ứng với thuộc tính Aj; hàng thứ i tương ứng với lược đồ Ri. Tại ô (i,j) điền kí hiệu aj nếu Aj  Ri, nếu không điền kí hiệu bij TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí - Xét các pth: +Xét ( X Y )  F , xét các hàng và nếu có giá trị bằng nhau trên thuộc tính X thì làm bằng các giá trị của chúng trên Y. Khi làm bằng trên Y, nếu một trong hai giá trị là aj thì ưu tiên làm bằng aj, nếu không làm bằng một trong các kí hiệu bij. +Tiếp tục với các pth khác ( kể cả việc lặp lại các pth đã được áp dụng) cho đến khi không còn áp dụng được nữa. - Xem xét kq: Nếu xuất hiện một hàng gồm toàn kí hiệu a1, a2, .. , an thì phép kết nối là không mất mát thông tin, ngược lại là kết nối mất mát thông tin. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí VD1: Quan hÖ ng­êi cung cÊp: R(MCTY, ĐC, MH, GIA) ®­îc t¸ch thµnh 2 quan hÖ: R1(MCTY, ĐC) vµ R2(MCTY, MH,GIA) víi c¸c phô thuéc hµm: MCTY ĐC MCTY,MH GIA Kiểm tra xem phép tách trên có mất mát thông tin hay không ? TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí B¶ng ban ®Çu ®­îc thiÕt lËp nh­ sau: a1 a1 MCTY a3a3b22R2 b14b13a2R1 GIAMH§C 1 2 3 4 1 2 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí ¸p dông phô thuéc hµm MCTY ĐC cho 2 hµng cña b¶ng. Ta nhËn thÊy 2 hµng b»ng nhau trªn cét tªn (®Òu lµ a1) nªn ë cét §C chóng ®­îc lµm b»ng vµ b»ng a2. Khi ®ã ta thÊy b¶ng kÕt qu¶ lµ: Cã hµng thø 2 cã c¸c gi¸ trÞ toµn lµ a, do ®ã phÐp t¸ch lµ T¸ch - KÕt nèi kh«ng mÊt m¸t th«ng tin. a1 a1 Tªn a3a3a2R2 b14b13a2R1 Gi¸S¶n phÈmĐÞa chØ TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Bµi tËp: B1. Cho l­îc ®å quan hÖ R={A, B, C, D} vµ tËp phô thuéc hµm F={AB, AC D} PhÐp t¸ch quan hÖ R thµnh 2 quan hÖ R1={AB} vµ R2={ACD} cã tæn thÊt th«ng tin kh«ng? V× sao? B2. Cho lược đồ quan hệ với các thuộc tính A, B, C, D, E, F và tập phụ thuộc hàm F= { AB  C, C  D, ABD  E, F  A} Kiểm tra tính mất mát thông tin của phép tách R thành : (R) = ( BC, AC, ABDE, ABDF) B3. Dùng kĩ thuật bảng kiểm tra tính tổn thất của các phép tách sau : R= , U = ABCDE ; F = { A C, B C , CD , DE C , CEA} p = ( AD, AB, BE , CDE) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Một số khái niệm * Thuộc tính khoá và không khoá - Cho một lược đồ quan hệ R trên tập thuộc tính U ={ A1, .., An}. Thuộc tính A U được gọi là thuộc tính khoá ( nguyên thuỷ hay cơ bản) nếu A là một thành phần thuộc một khoá nào đó của R, ngược lại A được gọi là thuộc tính không khoá (phi nguyên thuỷ hoặc thứ cấp). -VD : Cho lược đồ R trên tập thuộc tính u= { A, B, C, D } với các pth AB C , B  D , BC A . Ta thấy AB và BC là khoá. Vậy A, B, C là thuộc tính khoá ( hay cơ bản) , còn D là thuộc tính không khoá hay thứ cấp. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí * Phụ thuộc hàm đầy đủ Cho lược đồ quan hệ R(U) trên tập thuộc tính U = { A1, ... ,Ak}. X và Y là hai tập thuộc tính khác nhau X  U và Y  U. Y là phụ thuộc hàm đầy đủ vào X nếu Y là pth vào X nhưng không pth vào bất kì tập con thực sự nào của X TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Phụ thuộc bắc cầu Cho một lược đồ quan hệ R(U); X là một tập con các thuộc tính X U, A là một thuộc tính thuộc U. A được gọi là phụ thuộc bắc cầu vào X trên R nếu tồn tại một tập con Y của R sao cho X  Y, Y A nhưng Y  X với A  XY. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3. Các dạng chuẩn của lược đồ quan hệ - Quan hệ được chuẩn hoá là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa các giá trị nguyên tố ( tức là không phân nhỏ được nữa) - Quan hệ có chứa các miền giá trị là không nguyên tố gọi là quan hệ không chuẩn hoá. - Mét quan hÖ ®­îc chuÈn ho¸ cã thÓ thµnh mét hoÆc nhiÒu quan hÖ chuÈn ho¸ kh¸c vµ kh«ng lµm mÊt m¸t th«ng tin. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí C¸c d¹ng chuÈn: - D¹ng kh«ng chuÈn - D¹ng chuÈn thø nhÊt (1NF: First Normal Form) - D¹ng chuÈn thø hai (2NF) - D¹ng chuÈn thø ba (3NF) - D¹ng chuÈn Boye – Codd (BCNF) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.1. D¹ng chuÈn thø nhÊt: Mét l­îc ®å quan hÖ R ®­îc gäi lµ ë d¹ng chuÈn mét (1NF) nÕu vµ chØ nÕu toµn bé c¸c miÒn cã mÆt trong R ®Òu chØ chøa c¸c gi¸ trÞ nguyªn tè. VD: Cho bảng quan hệ GD ( Ten_GV, MON_GD) C, VISUAL BASIC, TK WEPHà PASCAL, NM CSDNLan Mon_GDTen_GV Các giá trị ở thuộc tính Mon_GD chưa là giá trị nguyên tố nên bảng trên chưa ở dạng chuẩn 1. Để đưa lược đồ trên về dạng chuẩn 1 ta tách thuộc tính kép thành các thuộc tính đơn như sau : TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí TK WEPHà VISUAL BASICHà NM CSDNLan CHà PASCALLan Mon_GDTen_GV Bảng GD ở dạng chuẩn 1: TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.2. D¹ng chuÈn thø 2: L­îc ®å quan hÖ R ë d¹ng chuÈn 2 (2NF) nÕu:  R ë d¹ng chuÈn mét  Mọi thuéc tÝnh kh«ng kho¸ cña R lµ phô thuéc hµm ®Çy ®ñ vµo kho¸ chÝnh. VD:Cho quan hÖ: SVTHI ( MONTHI, MSSV, TEN, TUOI, DIACHI, DIEM ) 2HT22Tu135 7HN20Lan115 6HP21Ha124 7HN20Lan114 6HP21Ha123 8HN20Lan113 §iÓmĐÞa chØTuæiTªnMSSVM«n thi TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Khoá chính của quan hệ trên là (Monthi , MSSV).Ta thấy các thuộc tính không khoá: ten, tuoi , diachi không phụ thuộc đầy đủ vào khoá chính (chỉ phụ thuộc vào MSSV). Do đó, vi phạm 2NF. Để lược đồ ở dạng chuẩn 2, ta tách thành 2 quan hệ : SINHVIEN (MSSV, TEN, TUOI, DIACHI) vµ THIXONG (MONTHI, MSSV, DIEM) Hai quan hệ trên đã ở 2NF vì mọi thuộc tính không khoá đều đã phụ thuộc hàm đầy đủ vào khoá chính TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.3 Dạng chuẩn thứ 3 ( 3NF) Lược đồ quan hệ R ở dạng chuẩn thứ 3 ( 3NF) nếu :  R ở dạng chuẩn 2 Mỗi thuộc tính không khoá là không phụ thuộc hàm bắc cầu vào khoá chính. - VD1 : Cho lược đồ quan hệ R ( SAIP) với các phụ thuộc hàm : SI P và S  A. R không ở 3NF. Vì có A là một thuộc tính không khoá, phụ thuộc bắc cầu vào khoá chính: SI S , S A và S SI. - VD2: Lược đồ quan hệ R ( CSZ) với các phụ thuộc hàm: CS  Z, Z  C. Trong lược đồ này, mọi thuộc tính đều là thuộc tính khoá. Do vậy R ở 3 NF TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3.4 Dạng chuẩn Boye-Codd ( BCNF) Lược đồ quan hệ R ở dạng chuẩn Boye-Codd ( BCNF) nếu với mọi : X  A thoả trên R , A  X thì X là một khoá của R. - VD :Trong ví dụ R(CSZ) nêu trên, rõ ràng R không ở BCNF mà là ở 3NF vì rằng Z  C nhưng Z không phải là một khoá của R. - Định lý : Nếu một lược đồ quan hệ R với tập phụ thuộc hàm F là ở BCNF thì nó là ở 3NF. - Nhận xét : Trong CSDL, các lược đồ quan hệ ở dạng chuẩn 1, 2, 3 vẫn tồn tại sự dư thừa thông tin. Để tối thiểu sự dư thừa thông tin thì các bảng phải ở dạng chuẩn BCNF TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4. Chuẩn hoá bảng Chuẩn hoá bảng là cách đưa một bảng chưa chuẩn hoá về dạng chuẩn 3NF hoặc BCNF mà không làm mất mát thông tin. Có hai phương pháp để chuẩn hoá lược đồ quan hệ :  Phương pháp phân rã : Tách một lược đồ quan hệ thành nhiều quan hệ khác thỏa mãn các dạng chuẩn.  Phương pháp tổng hợp : Gom các thuộc tính thành từng nhóm tạo thành quan hệ thoả mãn các dạng chuẩn. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4.1. Đưa một bảng chưa chuẩn hoá về dạng chuẩn hoá  Tách các nhóm thuộc tính lặp thành một bảng, khoá của bảng là khoá của bảng ban đầu và thuộc tính định danh của nhóm lặp.  Những thuộc tính còn lại lập thành một bảng với khoá của bảng là khoá của bảng ban đầu.  Quá trình tách chỉ dừng lại khi ta đã nhận được các bảng đã chuẩn hoá ( không còn thuộc tính lặp)  VD : Quan hệ đơn hàng: DONHANG ( SoĐ,MaH , TenH, SL, MAK, TenK,Tel) DONHANG1 (SoĐ, MaH, TenH, SL) DONHANG2 (SoĐ, MaK, TenK, Tel) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4.2. Đưa bảng ở 1NF về 2NF  Tách các thuộc tính phụ thuộc vào một phần của khoá thành một bảng, bảng này có khoá là thuộc tính gây ra sự phụ thuộc.  Các thuộc tính còn lại là một bảng với khoá của bảng là khoá của bảng ban đầu.  VD : Quan hệ ; SVTHI ( MONTHI, MSSV, TEN, TUOI, DIACHI, DIEM ) ở 1NF nhưng chưa ở 2NF. Để quan hệ ở 2NF, ta tách thành 2 quan hệ : SINHVIEN (MSSV, TEN, TUOI, DIACHI) vµ THIXONG (MONTHI, MSSV, DIEM) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4.3. Phép tách một lược đồ quan hệ thành 3NF Phép tách một lược đồ quan hệ R với tập pth F tối thiểu , không làm mất mát thông tin trên R, bảo toàn các pth sao cho mỗi lược đồ con đều ở 3NF: - B1 : Gom tất cả các thuộc tính của R không liên quan đên một pth nào của F, hoặc vế trái, hoặc vế phải , cho vào một lược đồ. - B2 : Nếu có một phụ thuộc hàm nào của F mà liên quan tới tất cả các thuộc tính của R thì kết quả ra chính là R. - B3 : Ngoài ra, phép tách đưa ra các lược đồ gồm các thuộc tính XA cho pth X  A; nếu X A1, X A2, ... , X An thì thay thế tập thuộc tính XA1A2...An cho XAi ( 1<= i<= n). Quá trình tiếp tục đến khi tất cả các lược đồ đều đã ở 3NF TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Cho lược đồ quan hệ R ( CTHRSG) với tập pth tối thiểu : C  T , HR  C , HT  R , CS  G và HS  R. Thuật toán trên cho ta kết quả của phép tách là tập lược đồ gồm 5 lược đồ con ở 3NF là : R1 (CT) (ứng với pth C  T) R2 (HRC) (ứng với pth HR  C) R3 ( HTR) (ứng với pth HT  R) R4 ( CSG) (ứng với pth CS  G) R5 (HSR) (ứng với pth HS  R) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4.3. Phép tách một lược đồ quan hệ thành BCNF Phép tách một lược đồ quan hệ R với tập pth F, không làm mất mát thông tin sao cho mỗi lược đồ con đều ở BCNF. Phương pháp : Lặp liên tiếp. Tại mỗi bước phép tách p là bảo đảm không mất mát thông tin đối với F. -Bước đầu : p chỉ bao gồm R -Các bước tiếp : Nếu S là một lược đồ thuộc p, S chưa ở BCNF, chọn X  A là pth thoả trên S, trong đó X không chứa khoá của S, A X. Thay thế S trong p bởi S1 và S2 với : S1 = XA, S2 = S - A Quá trình tiếp tục cho tới khi tất cả các lược đồ đều ở dạng chuẩn BCNF. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí VD: Cho lược đồ R(CTHRSG) với tập pth : C  T, HR  C, HT  R, CS  G, HS  R Khoá của R là HS. Ta lần lượt xét các pth vi phạm điều kiện BCNF. - Xét C  T : vi phạm BCNF vì C không chứa khoá, dùng thuật toán trên để tách thành : R1 ( CT ) và R2( CHRSG). Sau đó cần tính F+ và chiếu xuống R1 và R2, kiểm tra ta thấy R1 đã ở BCNF, R2 thì chưa. Ta tách tiếp R2. Phép tách cuối cùng được : R1(CT), R2 ( CSG), R3 ( CHR), R4 ( HSR) Quá trình tách có thể được biểu diến qua sơ đồ : TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí R(CTHRSG) Khoá =HS R1(CT) Khoá =C R2(CHRSG) Khoá =HS R21(CSG) Khoá =CS R22(CHRS) Khoá =HS R221(HRC) Khoá =HR,HC R222(HSR) Khoá =HS C  T, HR  C, HT  R, CS  G, HS  R HRC, HT R, CS G, HS R HRC, HC R, HS R HRC, HC R HS R CS G C  T TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí BTVN: B1. Cho lược đồ quan hệ R= với tập thuộc tính U = ABCDEHG và tập phụ thuộc hàm F={DE G, E A, H C, CG H, DG EA, D B} a. Xác định khoá của lược đồ quan hệ trên. b. Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên. B2. Xác định dạng chuẩn cao nhất của lược đồ quan hệ với các thuộc tính ABCDEF và tập phụ thuộc hàm {ABC,CB,ABDE,FA} B3. Cho W= R = { A, B, C, D} F= { B  D, A  C, C  ABD}. Hỏi W có là 2NF, 3NF không ? TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí B4. Xác định dạng chuẩn cao nhất của lược đồ quan hệ sau: H=(U,F); U=ABCD; F={CDB,AC,BACD} B5. Cho lược đồ R=(BOISQD) và F={SD,IB, ISQ,BO} a. Chứng tỏ rằng phép tách: R=(SD,IB, ISQ,BO) Là phép tách không mất mát thông tin. b. Chứng tỏ phép tách trên là ở dạng 3NF. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí