Bài giảng Cơ sở dữ liệu - Chương 5: Phụ thuộc hàm - Nguyễn Việt Cường

1CHƯƠNG 5 PHỤ THUỘC HÀM Functional dependency 2NỘI DUNG • PHỤ THUỘC HÀM • BÀI TOÁN TÌM PHỦ TỐI THIỂU • BÀI TOÁN TÌM KHÓA
Pth là mt công c biu din mt cách hình thc mt dng ràng buc tòan vn
Pth ñc ng dng trong vi c gi!i quy$t bài tóan tìm khóa, tìm ph* t+i thiu và chu,n hóa c- s/ d0 li u 3PHỤ THUỘC HÀM • Khái niệm phụ thuộc hàm • Bao ñóng của một tập phụ thuộc hàm F • Bộ luật dẫn AMSTRONG • Bao ñóng của tập thuộc tính X • Thuật toán tìm F+ 4Xét ví dụ (sgk) : Cho quan hệ Phân công 1:25p15/8412Copely 5:50a13/8281Copely 5:50a9/8281Copely 1:25p12/8116Chin 10:15a13/883Chin 10:15a11/883Clark 6:35p12/8301Clark 5:50a8/8281Clark 1:25p10/8116Cushing 10:15a9/883Cushing GIOKH)NGAYKH,MAYBAY,(PHICONG,phanCong 1. KHÁI NIỆM 5Trong thế giới thực luôn có những qui tắc hoạt ñộng : - Mỗi máy bay có một giờ khởi hành duy nhất - Nếu biết phi công, Ngày và giờ khởi hành thì biết ñược máy bay do phi công này lái - Nếu biết máy bay, ngày khởi hành thì biết phi công lái chuyến bay ñó Những qui tắc hoạt ñộng trên là một loại ràng buộc , ñược gọi là phụ thuộc hàm , và có thể phát biểu lại như sau : MAYBAY xác ñịnh GIOKH Hay GIOKH phụ thuộc hàm vào MAYBAY ðược ký hiệu f1: {MAYBAY}→ GIOKH f2: {PHICONG,NGAYKH,GIOKH}→ MAYBAY f3: {MAYBAY,NGAYKH}→ PHICONG 6 ðịnh nghĩa phụ thuộc hàm Cho lược ñồ quan hệ Q(A1,A2,,An) X, Y là hai tập con của Q+ = {A1,A2,,An} r là quan hệ trên Q t1, t2 là hai bộ bất kỳ trên r X → Y ⇔ ( t1.X = t2.X ⇒ t1.Y= t2.Y ) - N$u ∃ t1,t2 ∈ r , sao cho t1.X = t2.X và t1.Y ≠ t2.Y ta nói : pth X → Y không th=a trên r - N$u v?i m@i quan h r ñAu th=a mãn pth X → Y , ta nói pth X → Y ñc ñCnh nghĩa trên lc ñE quan h Q 7e1d1c5b2a3 e1d3c4b1a2 e1d3c3b1a2 d1d1c2b2a1 e1d1c1b1a1 Phụ thuộc hàm nào sau ñây thỏa r (A , B , C , D , E) A →D , AB→D AB→C e1d3c1b1a5 e2d2c2b2a4 e1d1c1b1a3 e2d2c2b2a2 e1d1c1b1a1 Phụ thuộc hàm nào sau ñây thỏa q BC→E , DE→C , A → BCDE 8Ví duïï: phanCong(PC, MB, N, G) , F ={(1),(2),(3)} Ñònh nghóa: Phụ thuộc hàm X → Y ñược suy diễn logic từ F nếu một lược ñồ quan hệ Q 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 (Gọi F |= X → Y là phụ thuộc hàm hệ quả) NX : Neááu (1) thoûûa maõnõ thì (4) cuõngõ ñöôïïc thoûûa maõnõ ⇒ chæ caààn kieååm tra (1) 1. MB → G 2. MB,N → PC 3. PC,N,G → MB 4. MB,N → G 5. MB,N,G → PC 6. PC, N, G → PC ⇒ F F+ 2. Phụ thuộc hàm ñược suy diễn logic từ F Bao ñóng của một tập phụ thuộc hàm F 9 Bao ñoùùng F+ cuûûa F : là tập tất cả các phụ thuộc hàm ñược suy diễn logic từ F  Luaäät daãnã ñeåå suy ra phuïï thuoääc haøøm heää quaûû töøø F : f’ laøø phuïï thuoääc haøøm suy töøø F qua luaäät daãnã (kyùù hieääu F  f’ ) neááu ∃ f1, f2,, fn sao cho fn=f’ vaøø (fi ∈ F) ∨ (fi ñöôïïc suy dieãnã töøø fj vôùùi j=1,,i-1) Kyùù hieääu F ’={f’ | F  f’} ⇒ caààn tìm luaäät daãnã sao cho F ’= F+ ; nghóa laøø ∀f, F= f ⇒ F f vaøø F f ⇒ F = f 10 Cho quan hệ Q(Q+) . X,Y,Z,W là các tập thuộc tính của Q+ Hệ tiên ñề Amstrong gồm các luật sau (F1) LuIt ph!n x (reflexive rule): N$u Y ⊆ X thì X → Y (F2) LuIt thêm vào (augmentation rule): N$u X → Y thì XZ → Y trong ñó ký hi u XZ thay cho X∪ Z (F3) LuIt bPc cQu (transitive rule): N$u X → Y và Y → Z thì X → Z Các luật dẫn khác suy từ (F1), (F2), (F3) (F4) BPc cQu gi! : n$u X → Y và YW → Z thì XW → Z. (F5) LuIt hi : n$u X → Y và X → Z thì X → YZ (F6) LuIt phân rã : n$u X → Y và Z⊆Y thì X → Z 3. Bộ Luật Dẫn AMSTRONG (Hệ tiên ñề Amstrong) Cần chứng minh Hệ tiên ñề Armstrong là ñúng và ñầy ñủ (xem sgk) Tính ñúng : F f ⇒ F = f Tính ñầy ñủ : ∀ F = f ⇒ F  f 11 A → D , A → EA → DELuật phân rã A → DEBA → DE A → B Luật hội AB → CA → DE DEB → C Luật bắc cầu giả A → CA → DE DE → C Luật bắc cầu AB → DE AB → DEB ABC → DEB A → DELuật thêm vào AB → BB ⊆ ABLuật phản xạ Ví dụ : 12 Chứng minh Luật thêm vào: giả sử có t1.XZ = t2.XZ (1) ⇒ t1.X = t2.X ⇒ t1.Y = t2.Y (do X → Y) (2) ⇒ XZ → Y (do (1) ⇒ (2)) Luật hợp: giả sử có t1.X = t2.X (1) ⇒ t1.Y = t2.Y và t1.Z = t2.Z ⇒ t1.YZ = t2.YZ (2) ⇒ X → YZ (do (1) ⇒ (2)) Luật phân rã: gỉa sử có t1.X = t2.X (1) ⇒ t1.YZ = t2.YZ (do X → YZ) ⇒ t1.Y = t2.Y (2) ⇒ X → Y (do (1) ⇒ (2)) Luật bắc cầu: giả sử có t1.X= t2.X (1) ⇒ t1.Y = t2.Y ⇒ t1.Z = t2.Z (2) ⇒ X → Z (do (1) ⇒ (2)) Luật bắc cầu giả: giả sử có t1.XZ = t2.XZ (1) ⇒ t1.X = t2.X và t1.Z = t2.Z (2) ⇒ t1.Y = t2.Y (do X → Y) (3) ⇒ t1.YZ = t2.YZ (Kết hợp (2) và (3)) ⇒ t1.W = t2.W (do YZ →W) (4) ⇒ XZ →W 13 Bài tIp 1 : Chng t= các pth sau ñc suy din tY F nhZ b luIt d[n Amstrong ? F = { B → A , DA→ CE , D → H , AC → D } AC → DA AC → DH AC → EH ? F = { B → A , BD→ CE , A → CB , C → G , GE → H } ? BD → EH B → CG 14 Ta có f4 : AC → D và AC → A (theo luật phản xạ) => Suy ra AC → DA (theo luật hội) F = { B → A , DA→ CE , D → H , AC → D } Ví dụ Chứng minh AC → DA ? 15 Cho Q là lược ñồ quan hệ Q( Q+), F là tập các phụ thuộc hàm ñịnh nghĩa trên Q , gọi X, Ai ⊆Q +. Bao ñóng c*a tIp thuc tính X dba trên F ký hi u là X+ (hodc X+F ) X+F = ∪ Ai v?i X → Ai là ph thuc hàm ñc suy din tY F nhZ h tiên ñA Armstrong  Nhận xét : X ⊆ X+ , X+ ⊆ Q+ ⇒Bổ ñề : X → Y ∈ F+ ⇔ Y ⊆ X+ Chứng minh : (1) X → Y ⇒ tồn tại k sao cho Y = Ak ⊆ ∪ Ai = X+ theo ñịnh nghĩa của X + (2) Y ⊆ X+⇒ X+ = Y ∪ (X+ - Y) ⇒ X → Y ∪ (X+ - Y)⇒ X → Y theo luật phân rã 4.Bao ñóng của tập thuộc tính X (closures of attribute sets) 16 Thuật toán tìm bao ñóng X+: 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: lQn lt xét các ph thuc hàm c*a F N$u Y→ Z có Y ⊆ Xi thì Xi+1 = Xi ∪ Z Loi ph thuc 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 Ngc li ldp li b?c 2 17 Ví d 1: Cho lc ñE quan h Q(ABCDE) và tIp ph thuc hàm F F = { f1: A → B f2: B → C f3: C → D f4: D → E } Tìm bao ñóng c*a tIp X = {AB} dba trên F Gi!i: B?c 1:X0 = AB B?c 2: xét f1 vì A ⊆ X0  X1 = AB ∪ B = AB , loi f1 xét f2 vì B ⊆ X1  X2 = AB ∪ C = ABC , l@ai f2 xét f3 vì C ⊆ X2  X3 = ABC ∪ D = ABCD , loi f3 xét f4 vì D ⊆ X3  X4 = ABCD ∪ E = ABCDE , loi f4 B?c 3 : X+ = X4 = {ABCDE} là bao ñóng c*a X 18 Ví d 2: (sgk ) Cho lc ñE quan h Q(ABCDEGH) và tIp ph thuc hàm F F = { f1: B → A f2: DA → CE f3: D → H f4: GH → C f5: AC → D } Chng minh f= {AC → EH } ñc suy d[n tY F ? Gi!i: B?c 1: X0 = AC B?c 2: xét f5 vì AC ⊆ X0  X1 = AC ∪ D = ACD xét f2 vì AD ⊆ X1  X2 = ACD ∪ CE = ACDE xét f3 vì D ⊆ X2  X3 = ACDE ∪ H = ACDEH Xét f1, f4 :không th=a vì có v$ trái không nlm trong X3 VIy X3 không thay ñmi  X+=X3={ACDEH} là bao ñóng c*a X  AC → EH ∈ F+ 19 Bài tIp 2: Cho Q(ABCDEGH) và tIp pth F th=a trên Q. Tìm bao ñóng c*a AC ? F = { B → A , DA→ CE , D → H , AC → D } F = { B → A , BD→ CE , A → CB , C → G , GE → H } AC + = ? B + = ? 20 5. Thuật toán tìm F+ Thuật toán cơ bản ðể tính bao ñóng F+ của tập các phụ thuộc hàm F ta thực hiện các bước sau: • Bước 1: Tìm tất cả tập con của Q+ • Bước 2: Tìm tất cả các phụ thuộc hàm có thể có của Q. • Bước 3: Tìm bao ñóng của tất cả tập con của Q. • Bước 4: Dựa vào bao ñóng của tất cả các tập con ñã tìm ñể xác ñịnh phụ thuộc hàm nào thuộc F+ Thuật toán cải tiến Dựa vào thuật toán cơ bản trên, ta nhận thấy có thể tính F+ theo các bước sau: Bước 1: Tìm tất cả tập con của Q+ Bước 2: Tìm bao ñóng của tất cả tập con của Q+. Bước 4: Dựa vào bao ñóng của các tập con ñã tìm ñể suy ra các phụ thuộc hàm thuộc F+. 21 Phủ và Phủ tối thiểu Các khái niệm : • Tập phụ thuộc hàm tương ñương với F • Phủ của F • Phủ tối thiểu của F 22 1. Hai tập phụ thuộc hàm tương ñương Bổ ñề : F ≡ G nếu và chỉ nếu F |= G và G |= F  Nếu F ≡ G ⇒ F = G và G = F ∀g∈ G +, g: X → Y⇒ g∈ F + ⇒ F = g Do ñó ∀g∈ G thì F= g hay F = G Tương tự ∀f∈ F thì G = f hay G = F  Nếu F = G và G = F ⇒ F ≡ G F = G ⇒ G ⊆ F + ⇒ G +⊆ (F +)+= F + G = F ⇒ F ⊆ G + ⇒ F +⊆ (G +)+= G + Tập phụ thuộc hàm F và G tương ñương nếu F+ = G+ ký hiệu F ≡ G 23 Thuật tóan xác ñịnh F và G có tương ñương không ? B1 :với mỗi X → Y của F xác ñịnh xem X → Y có ñược suy dẫn từ G không B2 :với mỗi X → Y của G xác ñịnh xem X → Y có ñược suy dẫn từ F không Nếu cả 2 bước trên ñều ñúng thì F ≡ G 24 Ví dụ 1: Cho lược ñồ quan hệ Q (ABCDE) và 2 tập pth F ={A→BC, A→D, CD→E } và G ={A→BCE, A→ABD, CD→E } 1. F có tương ñương với G không ? 2. F có tương ñương với G’ = { A→BCDE } 1. Nhận xét : F ñược suy diễn từ G (1) Ta Kiểm tra G có ñược suy diễn từ F không ? Tính AF+ = {ABCDE} => trong F+ có A→BCE và A→ABD (2) Từ (1) (2) : kết luận F ≡ G 2. Ta kiểm tra F có ñược suy diễn từ G’ không ? Tính CDG+ = {CD} => G’+ không chứa pth CD → E Kết luận : F không tương ñương G’ 25 Ví dụ 1: Cho lược ñồ quan hệ Q (ABCDE) và 2 tập pth F ={A→BC, A→D, CD→E } và G ={A→BCE, A→ABD, CD→E } 1. F có tương ñương với G không ? 2. F có tương ñương với G’ = { A→BCDE } 26 Bài tập : xem xét các cặp pth sau có tương ñương không? Cho lược ñồ quan hệ Q (ABCDE) và 2 tập pth F ={A→BC, A→D, CD→E } và G ={A→DE , A→BCE, CD→E } F ={A→B, B→C, C→D } và G ={A→BCD , B→CD, C→D } F ={A→B, B→C, C→D } và G ={A→CD , C→D } F ={AB→C, B→C, CD→E ,D→E } và G ={B→C , D→E } F ={AB→C, B→C, CD→E ,D→E } và G ={AB→C, B→C, C→B, BD→E } 27 2. Phủ của F 3. Phủ tối thiểu G là phủ của F nếu G ≡ F Một số phủ của F : G1 = { A→BCE, A→ABD, CD→E } G2 = { A→E, A→ABCD, CD→E } G3 = { A→BCD, CD→E } . Trong các phủ của F ta quan tâm tới một nhóm phủ gọi là phủ tối thiểu G là phủ tối thiểu của F nếu G là phủ của F ñồng thời thỏa 3 ñiều kiện sau : - G là tập phụ thuộc hàm có vế trái không dư thừa (G chỉ chứa những pth ñầy ñủ) - G là tập phụ thuộc hàm có vế phải một thuộc tính (G chỉ chứa những pth có vế phải một thuộc tính) - G là tập phụ thuộc hàm không dư thừa 28 3.a. Phụ thuộc hàm có vế trái không dư thừa : Cho F , f: X→Y∈F. Nói rlng ph thuc hàm f: X→Y có v$ trái d thYa (ph thuc hàm không ñQy ñ*) n$u tEn ti mt Z∈ X sao cho : F ≡ F - {X → Y} ∪ {Z → Y} Ví d 1: cho Q(A,B,C) và F= {AB→C; B→C} AB → C là ph thuc hàm có v$ trái d thYa vì F ≡ F- {AB→C}∪ {B→C}= {B→C} 29 Thuật tóan ñể lọai khỏi F các pth có vế trái dư thừa : Bước 1: LQn lt thbc hi n b?c 2 cho các pth X→Y c*a F Bước 2: V?i m@i tIp con X’≠ ∅ c*a X. N$u X'→Y∈ F+ thì thay X→Y trong F blng X'→Y Nhận xét : Pth có vế trái một thuộc tính là pth có vế trái không dư thừa F là Tập pth có vế trái không dư thừa nếu F không chứa những pth có vế trái dư thừa. 30 Ví d 2: lọai khỏi F các pth có vế trái dư thừa cho tIp ph thuc hàm F = {A → BC, B → C, AB → D} - xét pth AB → D : A → D ∈ F+ ? tính AF + = ABCD => A → D ∈ F+ B → D ∈ F+ ? tính BF + = BC => B → D ∉ F+ Trong F ta thay AB → D blng A → D VIy F ≡ F’ = {A → BC, B → C, A → D} - Các pth còn li có v$ trái 1 thuc tính _ là pth ñQy ñ* K$t luIn : F ≡ F’ là tIp pth có v$ trái không d thYa 31 3.b. Tập phụ thuộc hàm có vế phải một thuộc tính Mỗi tập phụ thuộc hàm F ñều tương ñương với một tập phụ thuộc hàm G mà vế phải của các pth trong G chỉ gồm một thuộc tính. Ví dụ 3: cho F = {A → BC , B → C , A → D} ta suy ra F ≡ {A → B, A → C , B → C , A → D} = G G ñược gọi là tIp ph thuc hàm có v$ ph!i mt thuc tính. 32 3.c. Tập phụ thuộc hàm không dư thừa Nói rlng F là tIp ph thuc hàm không d thYa n$u không tEn ti X→ Y ∈ F sao cho F ≡ F – {X→ Y}. Ngc li F là tIp ph thuc hàm d thYa. Ví dụ 4: cho F = {A→BC, B→D, AB→D} thì F dư thừa vì tồn tại AB→D ∈ F mà F ≡ F – {AB→D} = {A→BC, B→D} Thuật tóan lọai khỏi F các pth dư thừa: Bước 1: lần lượt lọai từng pth X → Y trong F , ta có G Bước 2: kiểm tra X → Y có ñược suy dẫn từ G không ? Bước 3: nếu có thì pth X → Y là dư thừa và lọai khỏi F quay lại bước 1 33 Giải theo thuật toán : cho F = {A→BC, B→D, AB→D} - Thử loại A→BC , có G = { B→D, AB→D} => A→BC không ñược suy dẫn từ G - Thử loai B→D , có G = {A→BC, AB→D} => B→D không ñược suy dẫn từ G - Thử loại AB→D, có G = {A→BC, B→D } => AB→D ñược suy dẫn từ G , => F dư thừa AB→D 34 Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm * Từ tập phụ thuộc hàm F cho trước , câu hỏi là tìm phủ tối thiểu của F ? B?c 1: loi kh=i F các ph thuc hàm có v$ trái d thYa. B?c 2: Tách các ph thuc hàm có v$ ph!i trên mt thuc tính thành các ph thuc hàm có v$ ph!i mt thuc tính. B?c 3: loi kh=i F các ph thuc hàm d thYa Nhận xét : Từ một tập pth F luôn tìm ñược ít nhất một phủ tối thiểu F’ Nếu tập pth F có nhiều phủ tối thiểu thì các phủ tối thiểu tương ñương với nhau F’ ≡ F’’ ≡ F * Bài tóan trọng tâm 35 Ví dụ 1: Cho lược ñồ quan hệ Q(A,B,C,D) và tập pth F như sau: F = {AB → CD,B → C,C → D} Hãy 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+ ? trả lời: BF+ = BCD ⇒ B → CD ∈ F+ Xét A → CD ∈ F+ ? trả lời: AF+ = A ⇒ A → CD ∉ F+ Vậy AB → CD là phụ thuộc hàm có vế trái dư thừa A ⇒ kết quả của bước 1 là: F ≡ {B → CD ; B → C ; C → D} = F1 Bước 2: kết quả của bước 2 là: F ≡ {B → D; B → C;C → D} = F1 Bước 3: trong F1 , B → C là phụ thuộc hàm dư thừa? xét B → C ∈ G+ ? với G = F1 - {B → C} = {B → D;C → D} Trả lời : BG+ = BD ⇒ B → C ∉ G+ ⇒ B → C không dư thừa trong F1 36 trong F1 , B → D là phụ thuộc hàm dư thừa? xét B → D ∈ G+ ? với G = F1 - {B → D} = {B → C;C → D} trả lời : BG+ = BCD ⇒ B → D ∈ G + ⇒ B → D dư thừa trong F1 trong F1 , C → D là phụ thuộc hàm dư thừa? xét C → D ∈ G+ ? với G = F1 - {C → D} = {B → D;B → C} trả lời :CG+ = C ⇒ C → D ∉ G + ⇒ C→ D không dư thừa trong F1 Kết quả của bước 3 : cho phủ tối thiểu F ≡ F1 - {B → D} F ≡ {B → C;C → D} = Ftt 37 Ví dụ 2: Cho lược ñồ quan hệ Q(A,B,C,D) và tập phụ thuộc F như sau: F= {AB → C , B → A , A → B} Hãy tính phủ tối thiểu của F? Bước 1 : AB → C có là pth có vế trái dư thừa ? B → C ∈ F+ ? trả lời: B+ = ABC ⇒ B → C ∈ F+ A → C ∈ F+ ? trả lời: A+ = ABC ⇒ A → C ∈ F+ Kết quả có 2 tập F’ và F” có vế trái không dư thừa : F ≡ F’ = {B → C;B → A;A → B} F ≡ F” = {A → C;B → A;A → B} Bước 2 : F’ và F” là các tập phụ thuộc hàm có vế phải một thuộc tính Bước 3 : Xét F’ = {B → C;B → A;A → B} thì thấy F’ không phải là tập pth dư thừa. Xét F” = {A → C;B → A;A → B} thì thấy F” không phải là tập pth dư thừa Kết luận : F có 2 tập phủ tối thiểu F’ và F” 38 Ví dụ 3: Cho lược ñồ quan hệ Q(MSCD,MSSV,CD,HG) và tập phụ thuộc F như sau: F = {MSCD→ CD; CD → MSCD; CD,MSSV → HG; MSCD,HG → MSSV; CD,HG → MSSV; MSCD,MSSV → HG} Hãy tìm phủ tối thiểu của F ? Ví dụ 4: Cho lược ñồ quan hệ Q(ABC) ,tìm các phủ tối thiểu của tâp phụ thuộc hàm F F = { A→ B ; A→ C; B → A; C → A;B → C } 39 KHÓA CỦA LƯỢC ðỒ QUAN HỆ • Khái niệm • Thuật toán tìm một khóa • Thuật toán tìm tất cả các khóa 40 Cho Q(Q+) và F là tập pth ñịnh nghĩa trên Q. Cho K⊆ Q+ K là một khóa của Q nếu thỏa 2 ñiều kiện: (1) K → Q+ ∈ F+ (hay KF + = Q+) (2) ∃ K’ ⊂ K , K’ → Q+ ∈ F+ - Tập thuộc tính S là siêu khóa nếu S ⊇ K - Thuộc tính A là thuc tính khóa nếu A ∈ K - Thuộc tính B là thuc tính không khóa nếu B ∉ K - Tập thuộc tính không khóa có thể bằng ∅ - Một lươc ñồ quan hệ có thể có nhiAu khóa K 41  Thuật tóan tìm một khóa của lược ñồ quan hệ Q : B1 : Gán K = Q+ B2 : Lần lượt thử lọai từng thuộc tính A ∈ K,có K’ = K – A nếu k’+ = Q+ thì gán K = K’ Thực hiện lại bước 2 42 Ví dụ_sgk : Cho Q(ABCDEGHI) và F = {AC→ B, BI → ACD, ABC → D, H → I, ACE → BCG, CG → AE} Gán K = Q+ = {A,B,C,D,E,G,H,I} Xét K’= K - {A} = {BCDEGHI} , tính K’+ = BCDEGHIA = Q+ ⇒gán K = K’ Xét K’= K - {B} = {CDEGHI} , tính K’+ = CDEGHIAB = Q+ ⇒Gán K= K’ Xét K’= K – {C} = {DEGHI} , tính K’+ = DEGHI ≠ Q+ Xét K’= K – {D} = {CEGHI} , tính K’+ = CEGHIABD = Q+ ⇒Gán K = k’ Tiếp tục tương tự kết quả thu ñược khóa K = {C,G,H} 43 • Cho Q(ABCDEGHI) và F = {AC→ B, BI → ACD, ABC → D, H → I, ACE → BCG, CG → AE} K’= {DEGHI} K’+= ? 44  Thuật tóan tìm tất cả các khóa của lược ñồ quan hệ Q Thuật tóan căn bản: B1: Xây dựng các tập con Xi có thể có của Q+ B2: Tìm bao ñóng của các Xi B3: Xác ñịnh các siêu khóa Si chính là các Xi có Xi+ = Q+ B4: Xác ñịnh các khóa từ tập siêu khóa S ∀ Si, Sj ∈ S, nếu ∃ Sj ⊂ Si thì S’ = S – Si Cuối cùng tập S’ là tIp tvt c! các khóa cQn tìm Ví dụ -sgk Nhận xét : Kết quả của B1 có thể là một tập rất lớn của các tập con của Q+ (2n) 45  Thuật tóan tìm tất cả các khóa của lược ñồ quan hệ Q Thuật tóan cải tiến : Các khái niệm -Tập thuộc tính nguồn (TN) gồm tất cả • Các thuộc tính chỉ xuất hiện ở vế trái và không xuất hiện ở vế phải của các pth • Các thuộc tính không xuất hiện ở cả vế trái và vế phải của các pth -Tập thuộc tính ñích (TD) gồm tất cả -Các thuộc tính chỉ xuất hiện ở vế phải của các pth -Tập thuộc tính trung gian (TG) : gồm tất cả •Các thuộc tính xuất hiện ở cả vế trái và vế phải của các pth Hệ quả : Nếu K là khóa của A thì K ⊇ TN và K ∩ TD = ∅ 46 Thuật tóan cải tiến : Dữ liệu vào : lược ñồ quan hệ Q , tập phụ thuộc hàm F Dữ liệu ra: tất cả các khóa của quan hệ Q B1: Xác ñịnh tập thụôc tính nguồn TN, tập thuộc tính trung gian TG B2: Nếu TG = ∅ thì Q chỉ có một khóa K = TN kết thúc Ngược lại : Qua bước 3 B3: tìm tất cả các tập con Xi của tập trung gian TG B4: tìm các siêu khóa Si : ∀ Xi , nếu (TN ∪ Xi)+ = Q+ thì Si = TN ∪ Xi B5: tìm các khóa từ tập siêu khóa S: ∀ Si, Sj ∈ S, nếu ∃ Sj ⊂ Si thì S’ = S – Si cuối cùng , tập S’ chính là tập khóa cần tìm 47 Ví dụ 1: cho Q(CSZ) , F= {CS → Z , Z → C} B5B4B3 SZCSZCSCZCZ SZSZSZCSZZ SCSCSCZSCC SS∅ KhóaSiêukhóa( TN∪TG)+TN∪TGTG B1: TN = {S} , TG = {C,Z} B2 ñến B5 : 48 Ví dụ 2: cho Q(A,B,C,D) và tập F={ AB→C, D→B, C→ABD }. Tìm tất cả các khóa ? Giải: B1: TN={∅} , TG={A,B,C,D } B2: 49 F={ AB→C, D→B, C→ABD } ADADADBCADAD ACACACBDACAC ABABABCDABAB DBDD CCCABDCC BBB AAA ∅∅ KhóaSiêukhóa( TN∪TG)+TN∪TGTG {ABCD} 50 F={ AB→C, D→B, C→ABD } ABCDCDABABCDABCD BCDCDABBCDBCD ACDCDABACDACD ABDCDABABDABD ABCCDABABCABC CDCDCDABCDCD BDBDBD BCBCBCADBCBC KhóaSiêukhóa( TN∪TG)+TN∪TGTG {ABCD} 51 Ví dụ 3: cho Q(A,B,C,D,E,H) và tập F= {A → E; C → D; E → DH} CM: K={A,B,C} là khóa duy nhất của Q ? B1: TN= {A,B,C} , TG = { E } B2 52 F= {A → E; C → D; E → DH} B5B4B3 A,B,C,EABCEDH = Q+ A,B,C,EE ABCABCABCEDH = Q+ A,B,C∅ KhóaSiêukhóa( TN∪TG)+TN∪TGTG