Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 7 - Lê Nhị Lãm Thúy

Chia sẻ: Tầm Y | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

44
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Phân tích thiết kế hệ thống thông tin - Chương 7: Lý thuyết chuẩn hóa dữ liệu" cung cấp cho người học các kiến thức: Phụ thuộc hàm, bao đóng, khóa của lược đồ quan hệ, phủ tối thiểu, dạng chuẩn, chuẩn hóa cơ sở dữ liệu,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích thiết kế hệ thống thông tin: Chương 7 - Lê Nhị Lãm Thúy

Chương 7 LÝ THUYẾT CHUẨN HÓA DỮ LIỆU PHÂN TÍCH THIẾT KẾ THỐNG THÔNG TIN Nội dung Xét hóa đơn bán hàng như sau  Phụ thuộc hàm.  Bao đóng.  Khóa của lược đồ quan hệ.  Phủ tối thiểu.  Dạng chuẩn.  Chuẩn hóa cơ sở dữ liệu.  Phép tách lược đồ quan hệ.  Bài tập 1
Ví dụ Số HD NgàyHD TênKH TênNV TênHH SL DG TT 001 01/02/19 Nuyễn Ngọc Nga Trần Thị Lan Coca 2 8.000 16.000 001 01/02/19 Nuyễn Ngọc Nga Trần Thị Lan Pepsi 1 7.000 7.000 001 01/02/19 Nuyễn Ngọc Nga Trần Thị Lan Ken 3 15.000 45.000 002 01/02/19 Nguyễn Thị An Linh Gạo 1 20.000 20.000 002 01/02/19 Nguyễn Thị An Linh Đường 2 21.000 42.000 003 01/02/19 Nguyễn Thị An Linh Sữa 1 25.000 25.000 Nếu thêm một hóa đơn mới ??? Nếu thêm một kết quả thi của sinh viên mới ??? 7.1 Phụ thuộc hàm (functional dependence-FD) 7.1 Phụ thuộc hàm (functional dependence-FD) Định nghĩa: Một thể hiện của R thỏa phụ thuộc hàm X  Ynếu Phụ thuộc hàm là ràng buộc giữa 2 tập thuộc tính của 01 lược t1, t2  R đồ quan hệ t1.X = t2.X  t1.Y = t2.Y R(A1, A2,…, An) là lược đồ quan hệ. X, Y là hai tập con của tập thuộc tính  ={A1, A2,…, An}. Nếu t1.X = t2.X  t1.Y  t2.Y thì lược đồ vi phạm phụ thuộc Ta nói Y phụ thuộc hàm vào X: X → Y hàm XY Với mỗi giá trị tại X trong R xác định duy nhất một giá trị của Y trong R 2
A B C D E Ví dụ 1 2 3 4 5 sai 1 4 3 4 5 1 2 4 4 1 Kí hiệu nào là phụ thuộc hàm MONHOC → DIEMTHI ??? I. AB → C HOTEN → DIEMTHI ??? II. B → D MASV → DIEMTHI ??? (T) III. DE → A (T) Phụ thuộc hàm hiển nhiên 7.2 Hệ luật dẫn Armstrong  Phụ thuộc hàm được suy diễn logic từ F Nếu X  Y thì X → Y .  Phụ thuộc hàm X  Y được suy diễn logic từ F nếu một quan hệ r  Với r là quan hệ bất kỳ, F là tập phụ thuộc hàm bất kỳ thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X  Y. thỏa trên r, ta luôn có  Ký hiệu F|= X  Y. F  {các phụ thuộc hàm hiển nhiên}  Bao đóng của F  Bao đóng của F là tập tất cả các phụ thuộc hàm được suy diễn logic từ F.  Ký hiệu: F+ Nếu F=F+ thì F là họ đầy đủ của các PTH 3
Thuật toán tìm bao đóng F+ 7.2 Hệ luật dẫn Armstrong  Các tính chất của tập F+ “Áp dụng hệ tiên đề Armstrong cho đến khi  Tính phản xạ: F  F+ không tìm ra thêm phụ thuộc hàm mới”  Tính đơn điệu: Nếu F  G thì F+  G+  Tính lũy đẳng: (F+)+ = F+.  Phần phụ của F: F- = G - F+ (G - tập tất cả các PTH có thể có của r) 7.2 Hệ luật dẫn Armstrong CM: Tiên đề tăng trưởng  Hệ luật dẫn Amstrong: Gọi R() là lược đồ quan hệ với  ={A1, A2,…, An} là tập thuộc tính và X,Y,Z,W là Giả sử quan hệ r thoả mãn X  Y. tập con của . (Kí hiệu: XY=XY) Tồn tại hai bộ t, u  r sao cho t[XZ] = u[XZ] mà t[YZ]  u[YZ]  Ba luật của tiên đề Amstrong: Vì t[Z] = u[Z] nên để có t[YZ]  u[YZ] thì t[Y]  u[Y] (1) 1. Luật phản xạ (reflexive rule): Mà ta có t[XZ] = u[XZ] nên t[X] = u[X] (2) Nếu Y  X thì X  Y 2. Luật tăng trưởng (augmentation rule): Từ (1) và (2) ta có t[X] = u[X] và t[Y]  u[Y] điều này là trái với Nếu X  Y, Z   thì XZ  YZ giả thiết quan hệ r thoả mãn X  Y. 3. Luật bắc cầu (Transivity Rule) Vậy t[YZ] = u[YZ] hay XZ  YZ là đúng trên quan hệ r. Nếu X  Y và Y  Z thì X  Z 4
7.3 Bao đóng của tập thuộc tính X 7.2 Hệ luật dẫn Armstrong (closures of attribute sets)  Định nghĩa  Ba hệ quả của tiên đề Amstrong: Gọi F là tập các phụ thuộc hàm trên tập thuộc tính  1. Luật hợp (Union Rule) Bao đóng của F là tất cả các phụ thuộc hàm có thể Nếu X  Y và X  Z thì X  YZ suy ra từ F dựa trên các tiên đề Armstrong 2. Luật bắc cầu giả (Pseudotransivity Rule) Nếu X  Y và WY  Z thì XW  Z 3. Luật phân rã (Decomposition Rule) Nếu X  Y và Z  Y thì X  Z 7.3 Bao đóng của tập thuộc tính X 7.3 Bao đóng của tập thuộc tính X (closures of attribute sets) (closures of attribute sets)  Thuật toán tìm bao đóng: Ví dụ 1: Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và  Tính liên tiếp tập các tập thuộc tính X0,X1,X2,... theo phương tập phụ thuộc hàm pháp sau: F={BA; DACE; DH; GH C; ACD}.  Bước 1: X0 = X Tìm bao đóng của X = {A,C} trên F? bao đóng  Bước 2: lần lượt xét các phụ thuộc hàm của F  Nếu YZ có Y  Xi thì Xi+1 = Xi Z Giải: X(0) = {A,C} , {A,C}{D}  X(1) = {A,C,D}, {A, D}{C,E}  Loại phụ thuộc hàm Y  Z khỏi F  X(2) = {A,C,D,E}, {D}{H}  Bước 3: Nếu ở bước 2 không tính được Xi+1 thì Xi chính là  X(3) = {A,C,D,E,H} bao đóng của X  X+= X(3)  Ngược lại lặp lại bước 2. Cho X = {B, D} ->X+? 5
7.3 Bao đóng của tập thuộc tính X (closures of attribute sets)  Ví dụ 2: cho lược đồ quan hệ: Q(A,B,C,D,E,G)  F = { f1: A → C; f2: A → EG; f3: B →D; f4: G →E} Tìm bao đóng: - X+ với X = {A,B}; Phủ tối thiểu - Y+ với Y = {C,G,D} 7.4 Phủ tối thiểu Tập phụ thuộc hàm tối thiểu (minimal cover) Một phủ tối thiểu của tập phụ thuộc hàm F là một tập phụ F là một tập phụ thuộc hàm tối thiểu nếu thỏa mãn 3 thuộc hàm G điều kiện sau: Trong đó:  F là tập phụ thuộc hàm có vế trái không dư thừa - G tương đương với F (tức G+ = F+)  F là tập phụ thuộc hàm có vế phải một thuộc tính. - Tất cả các phụ thuộc hàm trong G đều có dạng X  A  F là tập phụ thuộc hàm không dư thừa - Không thể làm G nhỏ hơn được nữa (nghĩa là không thể xóa đi bất kỳ PTH nào trong G, hay xóa đi bất kỳ thuộc tính nào bên phải, bên trái của mỗi phụ thuộc hàm mà G vẫn tương đương với F) 6
7.4 Phủ tối thiểu Ví dụ Thuật toán tìm phủ tối thiểu R(A, B, C, D, E, F, G, H) Bước 1: T = {ABH → CK, A → D, C → E, BGH → F, F → AD, E → F, BH → E} Tìm phủ tối thiểu - Tách vế phải mỗi PTH trong F sao cho các vế phải mỗi Bước 1: PTH chỉ chứa 1 thuộc tính Tách vế phải của các thuộc tính hàm thành các thuộc tính đơn lẻ: ABH → C Bước 2: ABH → K - Tìm các PTH đầy đủ bằng cách loại bỏ các PTH dư thừa A→D C→E ở vế trái của từng PTH BGH → F F→A Bước 3: F→D - Loại bỏ các PTH dư thừa trong F E→F BH → E T = {ABH → C, ABH → K, A → D, C → E, BGH → F, F → A, T = {ABH → C, ABH → K, A → D, C → E, BGH → F, F → A, Bước 2 F → D, E → F, BH → E} Bước 2 F → D, E → F, BH → E} Loại bỏ các thuộc tính dư thừa phía bên trái của mỗi 2.2. Xét ABH → K thuộc tính hàm: - Loại A trong ABH → K: T = {ABH → C, ABH → K, A → D, C → E, BGH → F, F → A, F → D, Ta có (BH)+ = (BHEFADK) chứa A, nên A dư thừa. E → F, BH → E} - Loại B trong ABH → K: 2.1. Xét ABH → C Ta có (AH)+ = (AHD) không chứa B, nên B không dư thừa. - Loại A trong ABH → C: - Loại H trong ABH → K: Ta có (BH)+ = (BHEFADK) chứa A, nên A dư thừa. Ta có (AB)+ = (ABD) không chứa H, nên H không dư thừa. - Loại B trong ABH → C: Ta có (AH)+ = (AHD) không chứa B, nên B không dư thừa.  Kết quả: T = {BH → C, BH → K, A → D, BGH → F, F → A, F → - Loại H trong ABH → C: D, E → F, BH → E} Ta có (AB)+ = (ABD) không chứa H, nên H không dư thừa.  Kết quả: T = {BH → C, ABH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E} 7
Bước 2 T = {ABH → C, ABH → K, A → D, C → E, BGH → F, F → A, Bước 3 T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, F → D, E → F, BH → E} E → F, BH → E} 2.3. Xét BGH → F Loại bỏ các phụ thuộc hàm dư thừa: - Loại B trong BGH → F: Ta có (GH)+ = (GH) không chứa B, nên T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E} B không dư thừa. - Loại G trong BGH → F: Ta có (BH)+ = (BHEFDACK) không chứa G, nên G không dư thừa. 3.1. Thử loại bỏ BH → C: - Loại H trong BGH → F: Ta có (BG)+ = (BG) không chứa H, nên Ta có: (BH)+ = (BHEFDAK) không chứa C, nên BH → C H không dư thừa. không dư thừa.  Kết quả: T = {BH → C, BH → K, A → D, BGH → F, F → A, F  Kết quả giữ nguyên. → D, E → F, BH → E} 3.2. Thử loại bỏ BH → K: 2.4. Xét BH → E Ta có: (BH)+ = (BHCEFDA) không chứa K, nên BH → K - Cả B và H đều không dư thừa. Kết quả: T = {BH → C, BH → K, A → D, BGH → F, F → A, F → không dư thừa. D, E → F, BH → E}  Kết quả giữ nguyên. Bước 3 T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, Bước 3 T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E} E → F, BH → E} 3.3. Thử loại bỏ A → D: 3.6. Thử loại bỏ F → D: Ta có: (A)+ = (A) không chứa D, nên A → D không dư thừa. Ta có: (F)+ = (FAD) chứa D, nên dư thừa.  Kết quả giữ nguyên.  Kết quả: T = {BH → C, BH → K, A → D, F → A, E → F, BH → E} 3.4. Thử loại bỏ BGH → F: Ta có: (BGH)+ = (BHEFDAKC) chứa F nên BGH → F dư 3.7. Thử loại bỏ E → F: thừa. Ta có: (E)+ = (E) không chứa F, nên không dư thừa.  Kết quả: T = {BH → C, BH → K, A → D, F → A, F → D, E  Kết quả giữ nguyên. → F, BH → E} 3.8. Thử loại bỏ BH → E: Ta có: (BH)+ = (BHCK) không chứa E, nên không dư thừa. 3.5. Thử loại bỏ F → A: Ta có: (F)+ = (FD) không chứa A, nên không dư thừa.  Kết quả giữ nguyên.  Kết quả giữ nguyên. 8
Kết quả Ví dụ T = {BH → C, BH → K, A → D, F → A, E → F, BH → E} Cho lược đồ quan hệ Q(A,B,C,D) và tập phụ thuộc F ={AB CD, B  C, C  D}. Tìm phủ tối thiểu của F. 1. BH → C 2. BH → K Bước 1: AB  CD là phụ thuộc hàm có vế trái 3. A → D dư thừa? 4. F → A Xét B  CDF+ ? 5. E → F 6. BH → E Tính B+ =BCD  B  CD F+ Vậy AB  CD là phụ thuộc hàm có vế trái dư thừa A  F={B  CD; B  C; C  D} Ví dụ Bài tập Bước 2: tách các phụ thuộc hàm có vế phải nhiều hơn 1 thuộc tính thành các phụ thuộc hàm có vế phải 1 thuộc tính Tìm phủ tối thiểu? F={B  CD; B  C; C  D} F={BD; B  C; C  D}=F1tt Bước 3: Ta có: B  D là PTH dư thừa do {B  C;C  D} Kết quả cho phủ tối thiểu: F={B  C;C  D}=Ftt 9
7.5 Phụ thuộc hàm tương đương 7.5 Phụ thuộc hàm tương đương  Định Nghĩa: Hai tập phụ thuộc hàm F và G là tương đương (Equivalent) nếu F+ = G+  Ví dụ: Cho lược đồ quan hệ R(ABCDE) hai tập  Ký hiệu: F  G (F ∼G). phụ thuộc hàm:  Thuật toán xác định F và G có tương đương không F = {ABC, AD, CE} Bước 1: Với mỗi phụ thuộc hàm XY của F ta xác định G = {ABCE, AABD, CE} xem XY có là thành viên của G không. Bước 2: Với mỗi phụ thuộc hàm XY của G ta xác định a) F có tương đương với G không? xem XY có là thành viên của F không. b) F có tương đương với G’={ABCE} không?  Nếu cả hai bước trên đều đúng thì F G 7.5 Phụ thuộc hàm tương đương Phụ thuộc hàm dư thừa Với mỗi phụ thuộc hàm YZ trong F Tính Y+ trên tập phụ thuộc hàm G  Tập các PTH có thể là dư thừa vì chúng có thể suy Nếu Z  Y+ thì YZ trong G+ và ngược lại diễn từ các PTH khác. F={ABC,AD,CE} Ví dụ: AC là dư thừa đối G = {ABCE,AABD,CE} với F= (AB, BC, A C) Giải:  Tính A+ , C+ dựa trên tập G  Một phần của phụ thuộc hàm cũng có thể dư thừa.  A+G=ABCED BC (xét A  BC)  Ví dụ:  C+G=CE  E (xét C  E) F=(A B, BC, AC,D) có thể được viết lại:  Các phụ thuộc hàm trong F đều được suy diễn từ G (1). + F=(A B, BC, AD) - Tính A+ , C+ dựa trên tậpF  A+ =ABCED  BCE (xét ABCE) F  C+F = CE  E (xét C  E)  Các phụ thuộc hàm trong G đều được suy diễn từ F (2) +  (1) và (2)  F+ = G+  F  G. 10
Cho F = { A→C, AC→D, E→AD, E→H} Cách 1 Y = {A→CD, E→AH} Cho F = { A→C, AC→D, E→AD, E→H} A→C  A → AC A→D Y = {A→CD, E→AH} AC → D A → CD A→C Kiểm tra F và E có tương đương Vậy F chứa A → CD Cách 1: Quy tắc suy diễn Cách 2: Dùng bổ đề và bao đóng E→AD  E → A E → AH E→H Vậy F chứa E → AH Cho F = { A→C, AC→D, E→AD, E→H} Cho F = { A→C, AC→D, E→AD, E→H} Cách 1 Y = {A→CD, E→AH} Cách 2 Y = {A→CD, E→AH} A→CD  A → C Xét Y trong F A→CD  A → D  AC → D (A)+F = {ACD} E → AH E → A E → AD (E)+F = {ADEH} A → D(do A → CD) Vậy F phủ Y E → AH E → H Xét F trong Y (A)+Y = {ACD} (AC)+Y = {ACD} (E)+Y = {ACDEH} Vậy Y phủ F 11
Bài tập: Bài tập: 1. Cho lược đồ quan hệ R và tập các phụ thuộc hàm: 4. Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc F như sau: F = {A  C; C  A; CB  D; AD  B; CD  B; AB  D} F={AB  C, B  D, CD  E, CE GH, G A} trên R. Hãy tìm phủ tối thiểu của F? Chứng minh AB  EG 2. Cho lược đồ quan hệ R(A,B, C, D, E, G, H) và tập phụ thuộc hàm F, 5. Cho G = {AB  C, A  B, B  C, A  C}và F = {B → A; DA→ CE; D → H; GH→ C; AC→ D} F ={AB  C, A  B, B  C}. Hãy tính: B+; H+;BC+ và tìm PTT Hai PTH trên có tương đương không? 3. Cho lược đồ quan hệ Q(ABC) hai tập phụ thuộc hàm: 6. Cho lược đồ quan hệ (A,B,C,D,E,G) và tập PTH: F = {ABC; C  A; CB  D; ACD  B; D  EG, BE  F={ A→B; A→C; B→A; C→A; B→C} C; CG BD; CE AG } G={ A→B; C→A; B→C} a/ X={B,D}, X+=? F có tương đương với G không? b/ Y={C,G}, Y+=? c/ Hãy tìm phủ tối thiểu của F Bài tập: Bài tập: 7. Cho lược đồ CSDL 8. Cho lược đồ CSDL KeHoach(NGAY, GIO, PHONG, MOMHOC, GIAOVIEN): Q(LENTAU, LOAITAU, MACHUYEN, LUONGHANG, BENCANG, NGAY} F = {NGAY, GIO, PHONG MONHOC; F = {TENTAU LOAITAU; MACHUYEN TENTAU, LUONGHANG; MONHOC, NGAY GIAOVIEN; TENTAU, NGAY  BENCANG, MACHUYEN} NGAY, GIO, PHONG  GIAOVIEN; a/ Hãy tìm tập phủ tối thiểu của F? MONHOC  GIAOVIEN} b/ Tìm tất cả các khóa của Q? a/ Tính {NGAY, GIO, PHONG}+; {MONHOC}+ b/ Tìm phủ tối thiểu của F. c/ Tìm tất cả các khóa của KeHoach? 12
Bài tập: Bài tập: 1.Cho lược đồ quan hệ R(C,T,H,R,S,G) và tập phụ thuộc F như sau: 7. Hãy tìm tất cả các khóa cho lược đồ CSDL F = {C T; HR  C; HT  R; CS  G; HS  R} Hãy tìm phủ tối thiểu của F? Q(BROKER, OFFICE, STOCK, QUANTITY, INVESTOR, DIVIDENT): 2.Cho lược đồ quan hệ R(A,B,C,D,E,H) và tập phụ thuộc F như sau: F = {A E; C  D; E  DH} F = {STOCK DIVIDENT; Chứng minh K={A,B,C} là khóa duy nhất của R? INVESTOR  BROKER; INVESTOR, STOCK  QUANTITY; 3.Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc F như sau: F = {AB C; D  B; C  ABD} BROKER  OFFICE} Hãy tìm tất cả các khóa của R? 4.Cho lược đồ quan hệ R(A,B,C,D,E,G) và tập phụ thuộc F như sau: F = {AB C; C  A; BC  D; ACD  B; D EG; BE  C; CG BD; CE G} Hãy tìm tất cả các khóa của R? KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)  Định Nghĩa: Cho lược đồ quan hệ R(A1,A2,…,An) U là tập thuộc tính của R. F là tập phụ thuộc hàm trên R. K là tập con của U Dạng chuẩn K là một khóa của R nếu thỏa 2 điều kiện sau:  K+ = U  Không tồn tại K'  K sao cho K’+= U 13
KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)  Ví dụ: cho lược đồ quan hệ R(U) với U={A,B,C,D,E} • Tập thuộc tính S được gọi là siêu khóa nếu S K và tập PTH: • Thuộc tính A được gọi là thuộc tính khóa nếu F={AB CE; B  D; BC  A} AK với K là khóa bất kỳ của R. Ngược lại A  Các khóa của R là K1=AB, K2=BC. được gọi là thuộc tính không khóa. Vậy: A,B,C là thuộc tính khóa còn Fn={D,E} • Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa cũng có thể bằng rỗng. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key) KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)  Thuật toán tìm một khóa của một lược đồ quan hệ R  Ví dụ 1: cho lược đồ quan hệ U = R(A,B,C,D,E) và tập phụ thuộc hàm F như sau: • Bước 1: gán K = U. F={ABC, AC  B, BC  DE} tìm khóa K? • Bước 2: A là một thuộc tính của K, đặt K’ = K - A. Giải:  Nếu K’+= U thì gán K = K' thực hiện lại bước 2. B1: K=U  K=ABCDE B2:(K\A)+ (BCDE)+=BCDE ≠ U  K=ABCDE  Nếu muốn tìm các khóa khác (nếu có) của lược đồ B3:(K\B)+ (ACDE)+= ABCDE = U  K=ACDE quan hệ, ta có thể thay đổi thứ tự loại bỏ các phần tử B4: (K\C)+ (ADE)+ = ADE ≠ U  K=ACDE của K. B5: (K\D)+  (ACE)+ = ACEBD=U  K=ACE B6: (K\E)+ (AC)+ = ACBDE =U  K=AC 14
KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key) KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)  Ví dụ 2: cho lược đồ quan hệ R(A,B,C,D,E,G,H,I) và  Thuật toán tìm tất cả khóa của lược đồ quan hệ: tập phụ thuộc hàm  Bước 1: Xác định tất cả các tập con khác rỗng của U={X1, F={ AC B; X2, …,Xn-1 } BI AC;  Bước 2: Tìm bao đóng của các Xi ABC D; H  I;  Bước 3: Siêu khóa là các Xi có Xi+= U ACEBCG;  Giả sử ta đã có các siêu khóa là S = {S1,S2,…,Sm} CG  AE}  Bước 4: xét mọi Si, Sj con của S (i ≠ j), nếu Si  Sj thì loại Sj  Tìm K? (i,j=1..n), kết quả còn lại của S chính là tập tất cả các khóa cần tìm. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key) KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)  Ví dụ: Tìm tất cả các khóa của lược đồ quan hệ  Thuật toán (cải tiến) tìm tất cả khóa của một với tập phụ thuộc hàm như sau: lược đồ quan hệ  Bước 1: tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG  Bước 2:  Nếu TG =  thì lược đồ quan hệ chỉ có một khóa K= TNkết thúc  Ngược lại Qua bước 3  Bước 3: tìm tất cả các tập con Xi của tập trung gian TG 15
KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key) Tập thuộc tính nguồn (TN) : bao gồm các thuộc tính chỉ xuất  Bước 4: tìm các siêu khóa Si bằng cách Xi hiện ở vế trái, không xuất hiện ở vế phải của F( tập phụ  if (TN  Xi)+ = U then Si = TN Xi thuộc hàm) và các thuộc tính không xuất hiện ở cả vế trái  Bước 5: tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu. và vế phải của F.   Si, Sj S Tập thuộc tính đích (TĐ) : Bao gồm các thuộc tính chỉ xuất if Si Sj then Loại Sj ra khỏi tập siêu khóa S, S hiện ở R, không xuất hiện ở L. còn lại chính là tập khóa cần tìm. Tập thuộc tính trung gian (TG) : Chứa các thuộc tính xuất hiện ở cả L và R Ví dụ : Cho một tập cơ sở dữ liệu R = Q = {ABC} F = {AB –> C, C -> A}. Với Q = {ABC} F = {AB –> C, C -> A}. Tìm tất cả các khóa TN = {B} TG = {0, A,C,AC} thuộc tập cơ sở dữ liệu trên. S1 = TN U 0 = B Ta có B+ = B # Q nên S1 = A không là siêu khóa Giải L = {ABC} R = {CA} S2 = TN U A = AB Ta có AB+ = ABC = Q nên S2 = AB là siêu khóa TN = {B} TG = {AC} # 0 nên ta làm tiếp bước 3 S3 = TN U C = BC Ta có BC+ = ABC = Q nên S3 = BC là siêu khóa Ta có tập con Xi của tập TG = {0, A,C,AC} S4 = TN U AC = ABC Ta có ABC+ = ABC = Q nên S4 = ABC là siêu khóa Ta lấy từng thuộc tính thuộc tập con Xi của tập TG hợp với TN Vậy ta có tập siêu khóa S = {AB,BC,ABC}. ta có các thuộc tính sau : Tuy nhiên, vì AB chứa trong ABC và BC chứa trong ABC nên loại bỏ siêu khóa ABC ra khỏi tập siêu khóa Vậy ta có, tập khóa K = {AB,BC} là khóa của lượt đồ quan hệ 16
KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key) 7.5 Dạng chuẩn Ví dụ: cho lược đồ quan hệ R(C,S,Z) và tập phụ thuộc hàm 1. Các loại PTH F={CS Z; Z  C}.  Phụ thuộc hàm riêng phần/bộ phận Áp dụng thuật toán cải tiến: X → A được gọi là phụ thuộc hàm riêng phần nếu N = {S}; TG ={C,Z} tồn tại Y ⊂X để cho Y → A. Gọi Xi là các tập con của tập TG:  Phụ thuộc hàm đầy đủ Xi TNXi (TNXi)+ Siêu khóa Khóa X → A được gọi là phụ thuộc hàm đầy đủ nếu TN = {S} =U không tồn tại Y ⊂X để cho Y → A.  S S C SC U SC SC  Ví dụ Z SZ U SZ SZ Cho lược đồ quan hệ R(A,B,C) và tập PTH CZ SCZ U SCZ F={A → B; A → C; AB → C} thì A → B; A → C là các PTH đầy đủ. AB → C không là PTH đầy đủ vì có A → C. 7.5 Dạng chuẩn 7.5 Dạng chuẩn 1. Các loại PTH 7.5.1 Qui trình chuẩn hóa  Phụ thuộc hàm bắc cầu X → A được gọi là phụ thuộc hàm bắc cầu nếu tồn  Khi thiết kế và cài đặt các hệ tại Y để cho X →Y, Y → A, Y −/→ X và A∉ XY. CSDL, chuẩn hoá là quá trình khảo sát danh sách các thuộc tính và áp dụng tập các quy tắc phân tích vào danh sách đó, biến  Ví dụ đổi chúng thành nhiều tập nhỏ Cho lược đồ quan hệ R(A,B,C,D,E) và tập PTH hơn sao cho: F={A → BCE; B → DC}  Tối thiểu việc lặp lại  Thuộc tính D,C là PTH bắc cầu vào A.  Tránh dị thường thông tin  Xác định và giải quyết được sự không rõ ràng, nhập nhằng trong suy diễn. 6 6 7 8 17
7.5.2 Các dạng chuẩn 7.5.2 Các dạng chuẩn Dạng chuẩn Một (1NF - first normal form) Dạng chuẩn Một (2NF - second normal form) Lược đồ quan hệ R ở dạng chuẩn 1 nếu và chỉ nếu Lược đồ quan hệ R ở dạng chuẩn 2 NF nếu R ở toàn bộ các miền có mặt trong R đều chỉ chứa các giá dạng chuẩn 1 và mọi thuộc tính không khóa đều trị nguyên tố (không phân chia được nữa). phụ thuộc hàm đầy đủ vào mọi thuộc tính khóa của R. Ví dụ: Cho lược đồ quan hệ R(ABCDEG) thỏa mãn phụ thuộc hàm: F={ A BC, C  DE, E G} Kiểm tra R có thỏa dạng chuẩn 2NF không ? Giải: Ta có: (A)+ =U K=A Các thuộc tính không khóa { B, C, D, E,G}  Đưa về dạng chuẩn 1: Do khóa chỉ có 1 thuộc tính nên R ở dạng 2NF Biến cột đa trị thành đơn trị 6 Điền đủ dữ liệu vào các cột khác 7 0 7.5.2 Các dạng chuẩn Ví dụ 2: Dạng chuẩn Một (3NF – third normal form) Xét quan hệ CNHAN như sau: Lược đồ quan hệ R ở dạng 3NF nếu có PTH X  A CNHAN(MACN, LOAINGHE, HESOTHUONG) thỏa trên R thì:  Khóa của quan hệ là MACN  X là siêu khóa của R, hay  Ta thấy có các PTH trong quan hệ:  A là thuộc tính khóa của R MACN → LOAINGHE MACN → Ví dụ: HESOTHUONG Cho lược đồ quan hệ R (A, B, C, D) thỏa mãn phụ thuộc hàm: LOAINGHE → HESOTHUONG F={ AB CD, D  A} Dạng chuẩn cao nhất của quan hệ này? Kiểm tra R có thỏa dạng chuẩn 3NF không ? Giải Giải: Khóa của lược đồ quan hệ R là: K={AB,BD} Xét Ta có: DA: A là thuộc tính khóa - Pth bắc cầu: MACN → LOAINGHE và Vậy R thỏa dạng chuẩn 3NF LOAINGHE → HESOTHUONG -Thuộc tính không khóa HESOTHUONG phụ thuộc bắc cầu Hệ quả: Một lược đồ quan hệ gọi là ở dạng chuẩn thứ 3 nếu vào thuộc tính khóa MACN nó ở dạng chuẩn thứ 2 và không có phụ thuộc hàm bắc cầu Do đó: CNHAN không phải là 3NF. 71 18
\ 7.5.2 Các dạng chuẩn Dạng chuẩn BCNF (Boyce - Codd) Lược đồ quan hệ R được gọi là BCNF nếu X  A Định lý: Các lớp dạng chuẩn của 1 lược đồ quan hệ trên R (A  X) thì: X là một siêu khóa của R. có quan hệ lồng nhau nghĩa là lớp sau nằm trọn trong lớp trước: BCNF3NF  2NF  1NF Ví dụ 1: Cho lược đồ quan hệ R(A, B, C) thỏa mãn phụ thuộc hàm F={AB  C, BC  A} VD: R là BCNF thì R là 3NF Kiểm tra R có thỏa dạng chuẩn BCNF không? Ví dụ: Giải: Khóa của R là : K={AB, BC} Cho lược đồ quan hệ R ( A, B, C, D) và Xét AB  C: Ta có AB là khóa, C  AB F = { AB  C, D B, C  ABD} Xét BC  A : Ta có BC là khóa, A BC Kiểm tra R có thuộc dạng chuẩn BCNF không? Giải thích? Vậy R thỏa dạng chuẩn BCNF Giải: Ví dụ 2: Cho lược đồ của quan hệ PROJ(PNO, PNAME, - Khóa của lược đồ quan hệ R là : K1=AB, K2=AD, K3=C BUDGET) thỏa mãn phụ thuộc hàm duy nhất PNO(PNAME, Nên R không có thuộc tính không khóa. Vậy R là dạng BUDGET), chuẩn 3NF nhưng không là BCNF. Kiểm tra PROJ có thỏa dạng chuẩn BCNF không? BTVN Chú ý:  Một quan hệ ở BCNF thì cũng đạt 3NF. 1/ Xét LĐQH R với U=ABCDE và tập PTH  Trong thực hành các quan hệ đạt chuẩn 3NF là đủ. F = {ABCE, E  AB, C  D} Tuy nhiên một quan hệ ở 3NF không đảm bảo đã loại bỏ được tất cả các lỗi khi thao tác dữ liệu. Dạng chuẩn cao nhất của quan hệ này là gì? Bài tập 1/ Cho lược đồ quan hệ R( A,B,C,D,E ) và tập phụ thuộc hàm F: F = { AB  C, AD  E, B  D} Kiểm tra R có thuộc dạng chuẩn 3NF không? Giải thích? 75 19
Bài tập 2/ Cho lược đồ quan hệ Q ( A, B, C, D, E ) và tập 1/ Cho lược đồ quan hệ HoaDon với HoaDon(SOHD, phụ thuộc hàm F như sau: KHACH, NGAYLAP, MATHANG, DONGIA, SOLUONG) và F = {AD  C, AB  E, D  B } tập các phụ thuộc hàm F như sau: a. Kiểm tra phụ thuộc hàm: AD  E có thuộc F+ ? F={SOHD →KHACH, NGAYLAP, SOHD,MATHANG b. Kiểm tra R có thuộc dạng chuẩn 2NF không? →DONGIA,SOLUONG} Hãy cho biết lược đồ quan hệ HoaDon có đạt dạng chuẩn Tìm phủ tối thiểu của tập phụ thuộc hàm: nào ? Tại sao? T = {ABH → CK, A → D, C → E, BGH → F, F → AD, E → F, BH → E} 2/ R = (A, B, C, D); F = {ABC→D, D→A} a. Xác định tất cả khóa của R b. Xác định dạng chuẩn cao nhất 77 78 Bài tập 3/ Cho lược đồ quan hệ HoaDon với HoaDon(SOHD, KHACH, NGAYLAP, MATHANG, DONGIA, SOLUONG) và tập các phụ thuộc hàm F như sau: F = { SOHD→KHACH, NGAYLAP, SOHD, MATHANG → DONGIA , SOLUONG } Hãy cho biết lược đồ quan hệ HoaDon có đạt dạng chuẩn nào ? Tại sao? 4/ Cho LĐQH r(R) với R=ABCD Thank you! F= {A → C, D → B, C → ABD} Xác định dạng chuẩn cao nhất? 5/Cho LĐQH r(R) với R={A, B, C, D} và tập PTH F={ABCD, B  C}. R có là 2 NF? 79 20