Chương 4: PTH - Cô Nguyễn Thị Thu Hiếu

Môn học Cơ sở dữ liệu GV: Nguyễn Thị Thu Hiếu LOGO Chương 4: Ràng buộc toàn vẹn & Phụ thuộc hàm Chương 4: Ràng buộc toàn vẹn & Phụ thuộc hàm 1. Ràng buộc toàn vẹn 2. Phụ thuộc hàm 2. Phụ thuộc hàm (PTH)  2.1.  2.2.  2.3.  2.4.  2.5.  2.6.  2.7.  2.8. Định nghĩa và biểu diễn PTH Suy diễn logic các PTH Bao đóng của tập PTH Hệ luật dẫn Armstrong Bao đóng của tập thuộc tính Phủ và phủ tương đương Phủ tối thiểu Thuật toán xác định khóa của lược đồ quan hệ 2. Phụ thuộc hàm (PTH)  2.1. Định nghĩa và biểu diễn PTH  2.2. Suy diễn logic các PTH  2.3. Bao đóng của tập PTH  2.4. Hệ luật dẫn Armstrong  2.5. Bao đóng của tập thuộc tính  2.6. Phủ và phủ tương đương  2.7. Phủ tối thiểu  2.8. Thuật toán xác định khóa của lược đồ quan hệ 2.1. Định nghĩa và biểu diễn PTH Định nghĩa: Phụ thuộc hàm - Functional Dependencies  Là sự biểu diễn RBTV dưới hình thức toán học  Bảo đảm thông tin không bị tổn thất khi phân rã hoặc kết nối giữa các quan hệ. 2.1. Định nghĩa và biểu diễn PTH (tt) Sử dụng PTH để:  Kiểm tra các quan hệ để xem chúng có thỏa mãn tập các PTH đã cho không. • Nếu quan hệ r đúng trên tập PTH F, ta nói r thỏa F.  Xác định các ràng buộc trên tập các quan hệ được cho phép. Chú ý:  Một thể hiện (quan hệ) của lược đồ quan hệ có thể thỏa mãn 1 PTH cho dù PTH đó không đảm bảo tính hợp lệ của tất cả các quan hệ. 2.1. Định nghĩa và biểu diễn PTH (tt) Biểu diễn PTH: Cho R(U) là một lược đồ quan hệ với U = {A1, A2,..., An} là tập thuộc tính. PTH giữa hai tập thuộc tính X, Y ⊆ U • Ký hiệu: X → Y ( đọc là X xác định hàm Y hoặc Y phụ thuộc hàm vào X ) • ∀r ∈ R, ∀ t1, t2 ∈ r nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. 2.1. Định nghĩa và biểu diễn PTH (tt)  Các PTH xuất phát từ các ràng buộc trong thế giới thực.  Phụ thuộc hàm cơ bản nhất là những phụ thuộc hàm khẳng định rằng một khoá xác định được tất cả các thuộc tính của lược đồ quan hệ. VD1:  Quan hệ HOCVIEN (MaHV, Ho, Ten, NgaySinh, GioiTinh, NoiSinh, MaLop) • Có các PTH sau: MaHV → Ho, MaHV → Ten, MaHV → NgaySinh, MaHV → GioiTinh, NoiSinh, MaLop. • Không có PTH: Ho, Ten → NgaySinh, NoiSinh. 2.1. Định nghĩa và biểu diễn PTH (tt) VD2:  Quan hệ KETQUATHI(MaHV, MaMH, LanThi,NgayThi,Diem) • Có các PTH sau: MaHV, MaMH, LanThi → NgayThi MaHV, MaMH, LanThi → Diem • Không có PTH sau: MaHV → Diem  PTH X → Y là tầm thường (trivial)  Y = X VD: Ho → Ho, Ten → Ten, NgaySinh → NgaySinh…  Một số phụ thuộc hàm khác: VD: MaHV, Ho, Ten → NgaySinh, NoiSinh 2.1. Định nghĩa và biểu diễn PTH (tt) Chú ý:  Vì thực thể được nhận dạng bằng giá trị của các thuộc tính khóa nên nếu một thực thể có • Các thuộc tính A1, A2,..., An • X là tập các thuộc tính khóa của tập thực thể • Y là mọi tập con thuộc tính Thì ta có thể khẳng định: X → Y  Quan hệ r biểu diễn mối liên hệ n-1 từ tập thực thể E1 đến tập thực thể E2 • X là khóa của E1; Y là khóa của E2 Thì ta có thể khẳng định: X → Y 2.2. Suy diễn logic các PTH  Cho lược đồ quan hệ R với tập thuộc tính U và tập các PTH F.  X → Y là 1 PTH; X,Y ⊆ U.  Ta nói rằng X → Y được suy diễn logic từ F (hay F khẳng định logic X → Y):  ∀r ∈R, nếu r thỏa tất cả các PTH trong F thì r cũng thỏa X → Y  Ký hiệu là: F X → Y.  VD:  Nếu F chứa A → B và B → C thì A → C được khẳng định logic từ F.  Ký hiệu: {A → B, B → C} A → C 2.3. Bao đóng của tập PTH Với F là tập các PTH, khi đó  Bao đóng (Closure) của F là tập các PTH được suy diễn lôgic từ F.  Ký hiệu: F+ = {X → Y | F X → Y} Nếu F = F+ thì ta nói F là họ đầy đủ (full family) của các PTH. Bao đóng của tập PTH được dùng để xác định khóa dự tuyển của quan hệ, nhưng chi phí tính toán lớn. 2.4. Hệ luật dẫn Armstrong  Để có thể xác định khoá của một lược đồ quan hệ  Để hiểu được các phép suy diễn logic cho các phụ thuộc hàm, cần tính được F+ từ F  Để khẳng định được X → Y có thuộc F hay không nếu biết phụ thuộc hàm X → Y và tập phụ thuộc hàm F.  Đòi hỏi phải có những qui tắc suy diễn cho biết làm sao có thể suy ra một hay nhiều phụ thuộc hàm từ các phụ thuộc hàm khác. Tập các qui tắc này được Armstrong đưa ra năm 1974 và được gọi là hệ luật dẫn Armstrong. 2.4. Hệ luật dẫn Armstrong (tt) Cho R là lược đồ quan hệ với U= {A1,..,An} là tập các thuộc tính của nó và X, Y, Z, W ⊆ U. Hệ luật dẫn Armstrong:  Phản xạ: Y ⊆ X ⇒ X → Y.  Tăng trưởng: X → Y ⇒ XZ → YZ, với XZ = X∪Z.  Bắc cầu: X → Y, Y → Z ⇒ X → Z. Các luật bổ sung (chứng minh dựa vào Hệ luật dẫn Armstrong)  Phân rã: X → YZ ⇒ X → Y, X → Z.  Hợp: X → Y, X → Z ⇒ X → YZ.  Giả bắc cầu: X → Y, WY → Z ⇒ WX → Z. 2.4. Hệ luật dẫn Armstrong (tt)  Chứng minh các luật suy dẫn bổ sung:  Phân rã: X → YZ ⇒ X → Y, X → Z Vì Z YZ nên YZZ (theo luật phản xạ). Dùng luật bắc cầu cho XYZ và YZZ có XZ. Tương tự có X → Y  Hợp: X → Y, X → Z ⇒ X → YZ Từ XY dùng luật tăng trưởng, thêm X có XXY Từ XZ dùng luật tăng trưởng thêm Y có XYYZ và cuối cùng dùng luật bắc cầu suy ra vì XXy và XYXZ nên XYZ.  Giả bắc cầu: X → Y, WY → Z ⇒ WX → Z Từ XY, dùng luật tăng trưởng, thêm W có WX WY. Dùng luật bắc cầu cho WX  WY và WYZ suy ra WXZ.  Một hệ quả quan trọng của luật tách và luật hợp là nếu X Y suy ra XAi với mọi AiY 2.4. Hệ luật dẫn Armstrong (tt) VD: Cho F = {AB → C, C → A }. CMR: BC → ABC Ta có:  (1) C → A (giả thiết)  (2) BC → AB (tăng trưởng 1)  (3) AB → C (giả thiết)  (4) AB → ABC (tăng trưởng 3)  (5) BC → ABC (bắc cầu 2 & 4) 2.5. Bao đóng của tập thuộc tính Làm thế nào để biết một PTH X → Y được suy diễn từ tập PTH F cho trước? 2.5. Bao đóng của tập thuộc tính Định nghĩa:  F là tập PTH 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 tập các PTH F (ký hiệu: X+) là tập tất cả các thuộc tính A có thể suy dẫn từ X nhờ tập bao đóng của F (F+)  X+ = {A ∈ U | X → A ∈ F+} Nhận xét:  X ⊆ X+.  X → Y ∈ F+ ⇔ Y ⊆ X+.  Nếu K là khóa của R thì K+ = U. 2.5. Bao đóng của tập thuộc tính (tt) Sử dụng X+ để:  Kiểm tra siêu khóa: • Để kiểm tra K là siêu khóa, tính K+, kiểm tra K+ có chứa mọi thuộc tính của R?  Kiểm tra các PTH: • Để kiểm tra phụ thuộc hàm X → Y có thuộc F+ không thì kiểm tra Y ⊆ X+  Tính bao đóng của tập PTH F: • Với mỗi r ⊆ R, tìm r+ • Với mỗi S ⊆ r+, đưa ra PTH r → S 2.5. Bao đóng của tập thuộc tính (tt) Thuật toán tính bao đóng của tập các thuộc tính Input: U, F và X ⊆ U Output: X+ Thuật toán:  B1: X0 = X;  B2: Nếu tồn tại Y → Z ∈ F với Y ⊆ Xi, Z  Xi thì Xi+1 = Xi ∪ Z; Tiếp tục B2 Ngược lại B3  B3: output X+ = Xi 2.5. Bao đóng của tập thuộc tính (tt) VD: Cho R(U) với U=ABCDEG F = {AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG} Tính X+, với: X=D  X = BD 2.5. Bao đóng của tập thuộc tính (tt) Xi Tập PTH D → EG X0 = D Xi+1 DEG X1= DEG Vậy D+ = DEG Xi Tập PTH Xi+1 X0= BD D → EG BDEG X1= BDEG BE → C BCDEG X2= BCDEG C→A X3= ABCDEG Vậy BD+ = ABCDEG ABCDEG 2.6. Phủ và phủ tương đương Cho F và G là hai tập PTH trên tập thuộc tính U, ta nói rằng tập PTH F tương đương với tập phụ thuộc hàm G (ký hiệu: F  G) nếu và chỉ nếu F+ = G+ Nếu F+ = G+ thì ta nói rằng F là phủ của G và ngược lại G là phủ của F. 2.6. Phủ và phủ tương đương (tt) Thuật toán xác định F và G có tương đương không? B1: Với mỗi PTH X → Y của F ta xác định xem X → Y có được suy diễn logic từ G không B2: Với mỗi PTH X → Y của G ta xác định xem X → Y có được suy diễn logic từ F không Nếu cả 2 bước trên đều đúng thì F  G 2.6. Phủ và phủ tương đương (tt)  VD: Cho lược đồ quan hệ R(ABCDE), 2 PTH: F={A → BC, A → D, CD → E} và G={A → BCE, A → ABD, CD → E} a. F có tương đương với G không? b. F có tương đương với G’={A → BCDE} không? Giải: a. Ta có AG+ = ABCDE  trong G+ có A → BC và A → D  F ⊆ G+ F+ ⊆ G+ (1) Lại có AF+ = ABCDE  trong F+ có A → BCE và A → ABD  F+  G  F+  G+ (2) Từ (1) và (2)  F+ = G+  F  G b. Do (CD)+ = CD  G’+ không chứa PTH CD → E  F không tương đương G’ 2.7. Phủ tối thiểu  2.7. Phủ tối thiểu (tt) Tìm phủ tối thiểu của F:  B1: Tách các PTH có vế phải nhiều hơn 1 thuộc tính thành PTH có vế phải chỉ có 1 thuộc tính độc nhất  B2: Loại bỏ thuộc tính dư thừa ở vế trái  X → A, Y ⊆ X, Y dư thừa  A  (X-{Y})F+  Nếu XY → Z và X → Z thì Y dư thừa ở vế trái của PTH XY → Z. Vậy còn PTH X → Z  Nếu XY → Z và X → Y thì Y dư thừa ở vế trái của PTH XY → Z. Vậy còn PTH X → Z, X → Y  B3: Loại bỏ các PTH dư thừa  Áp dụng Hệ luật dẫn Armstrong  X → A dư thừa  A  (X)+F-{XA}  F X → Y  Y ⊆ X+ 2.7. Phủ tối thiểu (tt)  VD: Cho R(U), U={A,B,C} F = {A → BC, B → C, A → B, AB → C} Tìm phủ tối thiểu F’ của F  Tách các PTH có vế phải nhiều hơn 1 thuộc tính. F trở thành: {A → B, A → C, B → C, AB → C}  Loại bỏ thuộc tính dư thừa ở vế trái Có AB → C mà A → C nên B dư thừa ở vế trái của PTH AB → C. Còn A → C. Tập F mới là {A → B, A → C, B → C}  Loại bỏ các PTH dư thừa Có A → B và B → C, theo luật bắc cầu của Hệ luật dẫn Armstrong  A → C Như vậy PTH A → C trong tập F mới ở B2 là dư thừa Tập F mới {A → B, B → C}  Vậy F’ = {A → B, B → C} 2.8. Thuật toán xác định khóa của lược đồ quan hệ  2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt) Input: R(U), F Output: Tập K là khóa của R Thuật toán:  B1: Đặt K = U = {A1, …, An} i = 1;  B2: Loại bỏ thuộc tính khỏi K • Nếu U = (K – {Ai})F+ thì K = K - {Ai}. • i = i + 1; • Nếu i > n thì sang B3. Ngược lại, tiếp tục B2.  B3: output K  Chú ý: Khi thay đổi thứ tự loại bỏ các thuộc tính trong K, ta có thể tìm được các khóa khác 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  VD 2.8.1: Cho R(U), U = {A, B, C, D, E, F, G} F = {B → A, D → C, D → BE, DF → G} Tìm khóa của R. Giải:  B1:  K = ABCDEFG.  B2:  Loại bỏ A: (BCDEFG)F+ = ABCDEFG ⇒ K = BCDEFG.  Loại bỏ B: (CDEFG)F+ = ABCDEFG ⇒ K = CDEFG.  Loại bỏ C: (DEFG)F+ = ABCDEFG ⇒ K = DEFG.  Loại bỏ D: (EFG)F+ = EFG.  Loại bỏ E: (DFG)F+ = ABCDEFG ⇒ K = DFG.  Loại bỏ F: (DG)F+ = ABCDEG.  Loại bỏ G: (DF)F+ = ABCDEFG ⇒ K = DF.  B3:  Khóa là K = DF. 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  VD 2.8.2: Cho R(U), U = {C, S, Z} F = {CS → Z, Z → C} Tìm khóa của R  B1: K = CSZ.  B2:  Loại bỏ C: (SZ)F+ = CSZ ⇒ K = SZ. • Loại bỏ S: (Z)F+ = CZ. • Loại bỏ Z: (S)F+ = S. K1 = SZ  Loại bỏ S: (CZ)F+ = CZ. • Loại bỏ C: (Z)F+ = CZ. • Loại bỏ Z: (C)F+ = C.  Loại bỏ Z: (CS)F+ = CSZ ⇒ K = CS. • Loại bỏ C: (S)F+ = S. • Loại bỏ S: (C)F+ = C. K2 = CS  B3: LĐQH R có 2 khóa là K1 = SZ và K2 = CS. 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt) Thuật toán cơ bản tìm tất cả các khóa:  B1: Xác định tất cả các tập con khác rỗng của U. Kết quả tìm được giả sử là các tập thuộc tính X1, X2,… …,X2n-1  B2: Tìm bao đóng của Xi  B3: Siêu khóa là các Xi có bao đóng đúng bằng U. Giả sử ta đã tìm được các siêu khóa là S = {S1, S2,… …,Sm}  B4: Xây dựng tập chứa tất cả các khóa của R từ tập S bằng cách xét mọi Si, Sj con của S (i  j), nếu Si ⊆ Sj thì ta loại Sj. 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. 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  VD 2.8.2: Cho R(U), U = {C, S, Z} F = {CS → Z, Z → C} Tìm khóa của R Xi Xi+ C C S S Z CZ CS CSZ CZ CZ SZ CSZ Siêu khóa Khóa CS CS CSZ SZ SZ CSZ CSZ Vậy LĐQH R có 2 khóa là K1 = SZ và K2 = CS 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  Một số khái niệm:  Tập thuộc tính nguồn (TN): chứa tất cả các thuộc tính xuất hiện ở vế trái và không xuất hiện ở vế phải của các PTH; đồng thời chứa các thuộc tính không xuất hiện ở cả vế trái lẫn vế phải của các PTH.  Tập thuộc tính đích (TD): chứa tất cả các thuộc tính xuất hiện ở vế phải và không xuất hiện ở vế trái của các PTH  Tập thuộc tính trung gian (TG): chứa các thuộc tính xuất hiện ở cả vế trái lẫn vế phải của các PTH.  Hệ quả:  Nếu K là khóa của R thì TN ⊆ K và TD  K =  2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  Thuật toán cải tiến bản tìm tất cả các khóa:  B1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG  B2: Nếu TG =  thì LĐQH R chỉ có một khóa K = TN Ngược lại, thực hiện B3  B3: Tìm tất cả các tập con Xi của tập thuộc tính trung gian TG  B4: Tìm các siêu khóa Si Nếu (TN  Xi)+ = U thì Si = TN  Xi  B5: 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 (i  j), nếu Si ⊆ Sj thì ta loại Sj khỏi tập siêu khóa S. 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. 2.8. Thuật toán xác định khóa của lược đồ quan hệ (tt)  VD 2.8.2: Cho R(U), U = {C, S, Z} F = {CS → Z, Z → C} Tìm khóa của R Giải: TN = {S}; TG = {C,Z} Gọi Xi là các tập con của tập TG Xi TN  Xi (TN  Xi) + Siêu khóa Khóa  S S C CS CSZ CS CS Z SZ CSZ SZ SZ CZ CSZ CSZ CSZ Vậy LĐQH R có 2 khóa là K1 = SZ và K2 = CS LOGO