Bài giảng Thiết kế cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu

Chương 4:Lý Thuyết Thiết Ké Cơ Sở Dữ LiệuKhái Niệm Phụ thuộc HàmĐịnh Nghĩa: là khái niệm quan trọng nhất trong việc thiết kế cơ sở dữ liệu - cho quan hệ R trên tập thuộc tính U R(U) + với U={A1,A2,A3An} x,y,z là tập con của U x y nếu mọi t & t’ t.x=t’.x t.y=t’.yVí dụ: x={masv} y={hoten,ngaysinh}=>x y2. Hệ tiên đề Amstrongđ/n hệ tiên đề amstrongGọi R(U) là lược đồ quan hệ với U = {A­1,,An} là tập các thuộc tính. X, Y, Z, W  U. Hệ tiên đề Armstrong bao gồm:F1) Tính phản xạ:Y  X  X  YF2) Tính bắc cầu:X  Y, Y  Z  X  ZF3) Tính mở rộng hai vế(tăng trưởng)X  Y  (Z  U) XZ  YZb. bổ đề. Bổ đề 1:Hệ tiên đề Armstrong là đúng. Có nghĩa là F là tập các phụ thuộc hàm đúng trên quan hệ R. Nếu X  Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì X  Y là đúng trên quan hệ R.Bổ đề 2:F4) Cộng tính ở vế phảI( luật hợp)X  Y, X  Z  X  YZF5) Tính tựa bắc cầu(giả bắc cầu)X  Y, YZ  W  XZ  WF6) Luật tách:X  Y Z  X  Z và x  yVí dụ:Cho tập phụ thuộc hàm F = {A  B, B  CD} ta chứng minh phụ thuộc hàm AC  CD được suy diễn logic từ F.Thật vậy:F3: A  B  AC  BCF3: B  CD  BC  CD F3: AC  BC, BC  CD  AC  CD Ví dụ 2:cho R={A,B,C,D,E} F={A  BC,B  D,C  E} CMR:A  E,A  DVí dụ 3:cho R={ABCDEF} F={A  BC,AB  D,AC  E,DE  F,F  AD) CMR:A  E,F  DE3. Tính bao đóngBao đóng của phụ thuộc hàma. Định nghĩa:Cho tập phụ thuộc hàm F trên tập thuộc tính U. Bao đóng của F, ký hiệu là F+, là tập nhỏ nhất các phụ thuộc hàm trên U thoả:F+ = {X  Y | F |== X  Y}b. Định nghĩa khác cho bao đóng của tập phụ thuộc hàm:F+ là tập các phụ thuộc suy diễn từ F nhờ hệ tiên đề Armstrong. Tức nó phải thoả hai tính chất sau:F+  FKhi áp dụng các tính chất F1, F2, F3 cho F+ ta không thu được phụ thuộc hàm nào nằm ngoài F+.c. Tính chất:(1): Tính phản xạ: F+  F(2): Tính đơn điệu: F  G  F+  G+(3): Tính lũy đẳng: (F+)+ = F+(4): (FG)+  F+G+(5): (F+G)+ = (FG+)+ = (FG)+b. Bao đóng của tập thuộc tínha. Định nghĩa:Cho tập phụ thuộc hàm F trên tập thuộc tính U và X  U. Bao đóng của tập thuộc tính X (đối với F), ký hiệu X+, là tập sau:X+ = {A | X  A  F+}b. Định nghĩa khác cho bao đóng của tập thuộc tính:X+ là tập các thuộc tính A sao cho X  A có thể suy diễn được từ F bằng hệ tiên đề Armstrong.c. Tính chất:(1): Tính phản xạ: X+  X(2): Tính đơn điệu: X  Y  X+  Y+(3): Tính lũy đẳng: (X+)+ = X+(4): (XY)+  X+Y+(5): (X+Y)+ = (XY+)+ = (XY)+(6): X  Y  Y  X+(7): X  Y  Y+  X+(8): X  X+ và X+  X(9): X+ = Y+  X  Y, Y  X 4. phụ thuộc hàm tương đươngkhái niệmCho R={A1,A2.An}Cho lược đồ quan hệ R và các tập phụ thuộc hàm F và G trên R ta nói:F phủ phụ thuộc hàm G nếu G+  F+F tương đương phụ thuộc hàm G nếu G+ = F+Để xác định phụ thuộc hàm Y  Z  G+ hay không ta sử dụng thuật toán tính bao đóng tập thuộc tính để tính Y+ đối với G và kiểm tra xem Z  Y+ hay không.Mệnh đề: F  G+  F+  G+Mệnh đề: Mỗi tập phụ thuộc hàm F tương đương với tập phụ thuộc hàm G gồm các phụ thuộc hàm mà vế phải chỉ có 1 thuộc tính.b. Phủ tối tiêu:Để tối ưu hơn nữa việc thiết kế lược đồ CSDL quan hệ ta yêu cầu mạnh hơn đối với tập phụ thuộc hàm tương đương.Định nghĩa: Tập phụ thuộc hàm F gọi là phụ thuộc hàm tối thiểu nếu nó thoả mãn các điều kiện sau:(1): Vế phải của mỗi phụ thuộc hàm trong F chỉ có 1 thuộc tính.(2): Mọi phụ thuộc hàm X  A  F là quan trọng, tức là tập phụ thuộc hàm có từ F bằng sự loại bỏ phụ thuộc hàm X  A:F \ {X  A}không tương đương với F.(3): Với mỗi phụ thuộc hàm X  A  F, mọi thuộc tính B  X đều quan trọng, tức là tập phụ thuộc hàm có từ F bằng việc thay phụ thuộc hàm X  A bởi phụ thuộc hàm (X \{B})  A:(F \ {X  A})  {X \ {B}  A}không tương đương với F.Nhận xét: Điều kiện (2) đảm bảo không có phụ thuộc hàm dư thừa, điều kiện (3) đảm bảo không có thuộc tính ở vế trái dư thừa.Thuật toán tìm phủ tối thiểu:- Input: Tập phụ thuộc hàm F.- Output: Tập phụ thuộc hàm tối thiểu G tương đương với F.- Method:(1): Phân rã vế phải tất cả phụ thuộc hàm của F và gọi G là tập tất cả các phụ thuộc hàm thu được.(2): Loại các phụ thuộc hàm dư thừa trong G: Không tồn tại X  A nào trong F mà tập F - {X  A} tương đương với F.(3): Loại các thuộc tính dư thừa ở vế trái của các phụ thuộc hàm trong G: Không tồn tại X  A trong F mà Z  X để cho:(F - {X  A})  {Z  A}tương đương với F.Ví dụ:Cho lược đồ R = (A, B, C, D, E, G) và tập phụ thuộc hàm F gồm các phụ thuộc hàm sau: AB  C D  EGC  A BE  CBC  D CG  BDACD  B CE  AGTa áp dụng thuật toán tính phủ tối thiểu để tính phủ tối thiểu của F.(1): Phân rã vế phải các phụ thuộc hàm trong FTập G thu được gồm các phụ thuộc hàm:AB  C BE  CC  A CG  BBC  D CG  DACD  B CE  AD  E CE  GD  G(2): Loại các phụ thuộc hàm dư thừa và thuộc tính dư thừa* Loại các phụ thuộc hàm dư thừa:- Loại CG  B, vì nó suy ra từ C  A, ACD  B và CG  D bằng các phép kéo theo như sau: C  A  CG  AG (qui tắc mở rộng hai vế)  CG  A (qui tắc phân rã)CGA & CGD & CG  C  CG  ACD (qui tắc hợp)CG  ACD & ACD  B  CG  B (qui tắc bắc cầu)Như vậy ta loại ra khỏi G.- Loại CE  A, vì nó suy ra từ C  A.Kết thúc bước này các phụ thuộc hàm còn lại như sau:AB  C BE  CC  A BC  D CG  DACD  B D  E CE  GD  G*Loại thuộc tính dư thừa:Trong phụ thuộc hàm ACD  B, thuộc tính A dư thừa vì C  A. Như vậy ta thay ACD  B bởi CD  B.Cuối cùng ta nhận được phủ tối thiểu:AB  C BE  CC  A BC  D CG  DCD  B D  E CE  GD  G6.Khoá và giải thuật tìm khoáKhái niệm khoákhái niệm căn bảnCho R={A1,A2,A3An}Cho K là tập con của RCho r là quan hệ trên R t1,t2 là hai bộ bất kỳKhi đó K gọi là khoá nếu như t1 t2 thì t1[k] t2[k]Là siêu khoá khi: K’ K-khái niệm theo phụ thuộc hàm cho Cho R={A1,A2,A3An} cho k R cho F là f tập phụ thuộc hàmKhi đó : k la khoá nếu + k  R + K’ Kb. giải thuật tìm khoá*ứng dụng:cho phếp xác định được khoá của một quan hệ dựa trên tập phụ thuộc hàm*bài toán: cho R là quan hệ F là tập phụ thuộc hàm yêu cấu: tìm khoá của R dựa trên FCác bước: b1: liệt kê các phần tử vế trái của phụ thuộc hàm F: L liệt kê các phần tử vế phải của phụ thuộc hàm F:R1 b2: lấy R\R1=thuộc tính x // trong khoá phả chứa x L giao R1=y b3:tính bao đóng x+: x+=R thì kết luận x là khoá nếu x+ R chuyển sang bước 4 b4: ghép x với từng phần tử ySau đó thực hiên như bước 3Ví dụ: Cho lược đồ R = (A, B, C, D, E, G) và tập phụ thuộc hàm F gồm các phụ thuộc hàm sau: AB  C, D  EG,C  A,BE  C,BC  D,CG  BDACD  B,Tìm khoá?Vd2: cho Q=(A,B,C,D,E,G,H,I)F=(A  BC,D  EG,AE  H,BD  I)kiểm tra A  ITính bao đóng AETìm khoáVí dụ 3: cho R=(MNPQSU)F={M  NP,P  NQ,MN  S,NS  UQ}a.kiểm tra M  Q?b.tính bao đóng của Pc. Tìm khoáVí dụ 4: cho R=(ABCDEG)F={AB  C,AC  DE,C  BG,D  EG}a.kiểm tra AB  Eb.tính bao đóng của ACc.tìm khoáChương v: các dạng chuẩn của quan hệGiới thiệudạng chuẩn là gì?đ/n :là những quy ước phụ thuộc những ràng buộc áp dụng cho một quan hệTránh do bộ phát sinh khi cập nhật dữ liệuCác thao tác cập nhập : thêm,sửa, xoá, tìm kiếm, sắp xếp, lọcVd: cho 1 quan hệ sinh viênsv{hoten,masv,diem,mamh}// dạng chuẩn hay không chuẩn? vì sao?2.các loại dạng chuẩngồm 4 dạng:1NF: dạng chuẩn 12NF : dạng chuẩn 23NF: dạng chuẩn 3BCNF: dạng chuẩn 4II. Quy ước dạng chuẩn1.dạng chuẩn 1NF*quy ước: giá trị của các thuộc tính trong mỗI bộ phải đầy đủ*chú ý: hầu hết tất cả các bảng dl đều ở dạng 1NFVí dụ Hàng 1 Hàng 2(mah,ngayban,slban) mah ngayban slban M1 5 10 m1 5 10 M2 9 20 m1 8 35 M3 9 100 5 25 M1 4 10 m3 5 12M2 8 23 20 14 dạng 1NF ko phải ở dạng 1NF (thiếu thông tin)2. Dạng 2NFQuy ước một quan hệ ở dạng 2NF khi: - nó ở dạng 1NF -các thuộc tính không khoá phải phụ thuộc hàm đầy đủ vào thuộc tính khoáChuẩn hoá nếu một quan hệ ở dạng 1NF nhưng lại ở dạng 2 thì phải chuẩn hoá như sau -tách các thuộc tính phụ thuộc một phần vào khoá và thuộc tính khoá vào bảng - khoá của bảng tách là thuộc tính khoáVí dụ:Cho 1 quan hệ R={ABCD}F={AB  C,B  D} - Hỏi R đã ở dạng chuẩn 2 NF hay chưa? - tách bảng đã chuyển về 2NFtrả lời:-Khoá: ABR chưa phải ở dạng 2( vì D phụ thuộc 1 phần khoá)tách R(ABCD) R1(ABC), F={AB  C} Khoá AB R2(BD),F={B  D} Khoá Bkết luận: từ R tách 2 quan hệ R1,R2 đều ở dạng 2 NF3.Dạng chuẩn 3NF*quy ước: một quan hệ ở dạng 3NF khi: - ở dạng 2 NF -không tồn tại các thuộc tính không khoá phụ thuộc hàm bắc cầu vào khoá chínhphụ thuộc hàm bắc cầu:` -chặt: A B,B C Thì A C và C không thể xác định được A - không chặt: A B,B C ,C A*chuẩn hoá thành dạng 3NFnếu 1 quan hệ ở dạng 2NF nhưng chưa ở dạng 3NF thì phải tách - tách các thuộc tính phụ thuộc hàm bắc cầu và thuộc tính xác định hàm thành 1 bảng - khoá của bảng tách là thuộc tính xác định hàmVí dụ: cho R=(ABCD)F={AB  C,C  D)Tách R(ABCD)R1(CD);F={C  D}// Khoá là CR2(ABC); F={AB  C} Khoá ABChú ý: phụ thuộc hoàn toàn 1NF  2NF Phụ thuộc trực tiếp(không bắc cầu): 2NF  3NFBÀI TẬPCho R=(ABCDEGH)F={B  AC,AB  DE,A  G,C  H}-hỏi R ở dạng nào?chuyển về 2 NFchuyển về 3NFBài làmR =(ABCDEGH)R1=(AG); F={A  G} khoá là: AR2=(CH);F={C  H} khoá là :CR3=(ABCDE);F3=(B  AC,AB  DE}Tách R3thấy B  AC B  A(luật tách) B  AB(luật tăng trưởng) AB  DE B  DE(bắc cầu)R31=(BAC),F={B  AC} Khoá là: BR32=(BDE)4. Cách kiểm tra việc tách hợp lệR=R1 R2 .Rnhỏi tách R đúng hay không đúnggiả thiết: R={A1,A2,A3AN}N: thuộc tính - giả sử R=R1 R2 .Rn F={f1,f2fn}kiểm tra: b1:lập bảng có: n cột tương đương n thuộc tính nhãn của mỗi cột là tên thuộc tính xác định m dòng(các quan hệ được tách ra) đặt chỉ số: Stt cho cột và dòng ghi giá trị aij: j là chỉ số dòng i là chỉ số cột tại các quan hệ các quan hệ có thuộc tính được táchB2 cập nhật Từ F nếu có X  Y nếu X ở 2 ô có giá trị giống nhau thì Y cập nhật giá trị bằng nhau lặp lại nhiều lần cho đến khi nào 1 dòng xuất hiện toàn a thì quá trình tách là đúngVí dụ 1 cho R(ABCD)F={AB C,B D,BC A}Tách thành:ABC,DC,DBAHỏi phép tách này có mất thông tin hay không?Ví dụ 2:Cho R=(ABCDE) F={AB DE,E AD,D C}. Tách thánh BDC,AE,ABDPhép tách có bảo toàn hay không?5. chuẩn BCNF(boyed godd) chuẩn rất mạnh hoàn toàn dựa vào định nghĩa phụ thuộc hàm, trong thự tế sử dụng BCNF nhiều hơn 3NFQuy định: mọi thuộc tính không khoá phải phụ thuộc hàm vào khoá - không tồn tại 1 trường hợp ngược lại: khoá phụ thuộc hàm không khoáKhái niệm khoá theo quan điểm phụ thuộc hàm cho R={A1,A2,A3AN} K R, K gọi là khoá nếu: - k {A1,A2,A3AN} - không tồn tại k’ k, k’ {A1,A2,A3AN}Ví dụR={ABCD},F={AB C,C D} AB là khoá, và AB {A,B,C,D}Chú ý:tập thuộc tính xác định hàm tất cả các thuộc tính còn lại-khoá dự tuyển: giả sử R đều có K1,K2 là khoá, có tính chất của khoá. gọi K1,K2 là khoá dự tuyểnVí dụ R={ABCD},F={AB C,BC D,D AB}Tìm K=?K1={AB}K2={BC}K3={D}gọi K1 ,K2 ,K3 các khoá dự tuyển Ví dụ 2:R={ABCD},F={AB CD,D B} dạng chuẩn 3NF , không ở dạng chuẩn BCNF vì khoá AB CD không là khoáQuy tắc táchnếu quan hệ không ở dạng chuẩn BCNF thì chuyển về BCNF như sau(trong quan hệ vẫn có thuộc tính khoá phụ thuộc hàm vào không khoá)-tách thuộc tính không khoá và thuộc tính khoá thuộc phụ thuộc hàm vào không khoá thành 1 bảngkhoá của bảng tách là thuộc tính không khoáVí dụ 2 táchR1:={B,D}R2:={A,B,C}R2={A,C,D} BÀI TẬP Bài 1: cho R=(A,B,C,D,E,G)F={AB CD,BC E,D GB}Yêu cầu:- tìm khoá -xác định dạng chuẩn R - tách R thanh BCNFBài 2:R=(A,B,C,D,E)F={AB ED,E A,A C}Yêu cầu:- tìm khoá -xác định dạng chuẩn R - tách R thanh BCNF6. Cách kiểm traR được tách R1, R2cho R la tập thuộc tính,F là tập phụ thuộc hàmnếu R tách ra R1,R2 thì trong F có 1 phụ thuộc hàm có dạng R1