Bài giảng Phân tích thiết kế thống thông tin - Chương 7: Lý thuyết chuẩn hóa dữ liệu - Lê Nhị Lãm Thúy

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