CHƯƠNG I TÌM BAO ĐÓNG CỦA TẬP THUỘC TÍNH

CH

NG I ƯƠ TÌM BAO ĐÓNG C A T P THU C TÍNH Ủ Ậ

Ộ

c đ quan h R=(U, F). Bao đóng c a t p thu c tính X ộ ồ ệ X. ễ ộ 1. Đ nh nghĩa bao đóng ị (X ˝ U), ký hi u Xệ ể • Nh n xét: Bao đóng c a t p thu c tính X th c ch t là t p t ủ ậ ừ t c các thu c tính mà ta có t h p c các thu c tính mà có th suy di n logic t ộ ấ : Cho l + là t p t ậ ấ ợ ủ ậ ậ ấ ả ự i” (hay suy ra) nó t ầ ộ t p thu c tính X ban đ u. • Vi c tính toán bao đóng là c s cho vi c tìm khoá, tìm t p khoá, ki m tra m t ph thu c ộ ụ ệ ể ậ ộ ậ th “v i t ể ớ ớ ệ ượ ả ộ ừ ậ ơ ở hàm nào đó có t n t ồ ạ i trong quan h hay không... ệ

ậ ộ ủ ậ

c đ quan h R=(U,F). ượ ệ ồ ộ ầ ậ ươ a ﬁ b ˝ X+ thì k t n p v ph i (t c t t ng ph thu c hàm fi = , n u ế a ế ạ ả ứ b ) vào vào ế ầ ượ ừ ụ ộ b

+ = Const.

ế

2. Thu t toán tìm bao đóng c a t p thu c tính Đ u vào: T p thu c tính X c n tính bao đóng trên l ầ ậ + Đ u ra: T p thu c tính X ộ ầ + Ph ng pháp: Ki m tra l n l ể X+: X+ := X+ ¨ . i cho đ n khi nào X L p l ặ ạ Thu t toán 1 ậ

CònThayĐ i := True; ổ X+ := X; While Còn_Thay_Đ i Doổ Begin ổ a ﬁ b Do Còn_Thay_Đ i := False; For m i fi = ỗ Begin X+ Then If a ˝ Begin

b ; X+ := X+ ¨ Còn_Thay_Đ i := True; ổ End; End;

End; *** L u ý: Vi c cài đ t chi ti ệ ư ặ ế t thu t toán xin xem trong ph l c ụ ụ ậ

ụ

c đ quan h R = (U, F) ệ ồ

Bài t p áp d ng: ậ Bài t p 1: ậ Cho l ượ U= {A,B,C,D,E,G,H} F= {ABC, DEG, ACDB, CA, BEC, CEAG, BCD, CGBD, G H}

a) Tính (D)+ b) Tính (DE)+ c) Tính (BE)+ d) Tính (CG)+ i:ả Gi a) Tính (D)+

ﬁ EG) ﬁ H) (= Constant) ậ X0 = D 1) X1 = DEG (áp d ng Dụ 2) X2 = DEGH (áp d ng Gụ + = DEGH V y (D) b) Tính (DE) +

ﬁ EG) ﬁ H) (= Constant) X0 = DE 1) X1 = DEG (áp d ng Dụ 2) X2 = DEGH (áp d ng Gụ

1 PHẠM THỊ THỦY

V y (DE)

+ = DEGH

ậ c) Tính (BE)+

ụ ụ ụ ﬁ AG) ﬁ D) ﬁ H) (= Constant) X0 = BE ﬁ C) 1) X1 = BEC (áp d ng BE 2) X2 = BECAG (áp d ng CE 3) X3 = BECAGD (áp d ng BC 4) X4 = BECAGDH (áp d ng Gụ + = ABCDEGH V y (BE) ậ d) Tính (CG)+

ụ ﬁ BD) ﬁ H) ﬁ EG) (= Constant)

c đ quan h R = (U, F)

+ = ABCDEGH ồ ượ

ệ ậ

X0 = CG ﬁ A) 1) X1 = CGA (áp d ng Cụ 2) X2 = CGABD (áp d ng CG 3) X3 = CGABDH (áp d ng Gụ 4) X4 = CGABDHE (áp d ng Dụ V y (CG) ậ Bài t p 2: Cho l U = {A,B,C,D,E,G} F = {CG, BG  CD, AEG  BC, CG  AE, B  CG }

a) Tính C+ b) Tính (B)+ c) Tính (AEG)+ i:ả Gi a) Tính C +

ﬁ AE) ụ ụ ﬁ BC) ﬁ CD) (= Constant) ụ X0 = C ﬁ G) 1) X1 = CG (áp d ng Cụ 2) X2 = CGAE (áp d ng CG 3) X3 = CGAEB (áp d ng AEG 4) X4 = CGAEBD (áp d ng BG V y (C)

+ = ABCDEG

ậ b) Tính (B)+

ﬁ CG) ụ ﬁ CD) ụ ﬁ AE) (= Constant) ụ

+ = ABCDEG

ậ X0 = B 1) X1 = BCG (áp d ng B 2) X2 = BCGD (áp d ng BG 3) X3 = BCGDAE (áp d ng CG V y (B) c) Tính (AEG)+

ụ ﬁ BC) ﬁ CD) (= Constant) ậ i ta cũng đ nh nghĩa bao ụ + = ABCDEG ư ự ị ườ nh bao đóng c a t p thu c tính, ng ủ ậ ệ ụ ụ ủ ậ ộ ơ ạ ữ ủ ậ ụ ộ ậ X0 = AEG 1) X1 = AEGBC (áp d ng AEG 2) X2 = AEGBCD (áp d ng BG V y (AEG) ng t ươ ộ ộ ụ ụ ề ộ c ng d ng do v y xin không đ c p trong tài li u này. ề ậ ủ ậ ụ bài t p 2. ậ ở ớ

ệ ề ậ ả

đóng c aủ ** Chú ý: T ộ ứ t p ph thu c hàm. Tuy nhiên vi c tính bao đóng c a t p ph thu c hàm nói chung là ph c ậ t p, nó thu c lo i bài toán NP – Khó. H n n a vi c tính bao đóng c a t p ph thu c hàm ít ệ ạ đ ượ ứ ệ M t ví d v tính bao đóng c a t p ph thu c hàm. ộ Tính (BG  CD)+ v i R cho X0 = BG  CD X1 = (BGC, BG  D) (Theo lu t tách trong h tiên đ Amstrong) ậ X2 = (BG  C, BG  D, BG  B, BG  G) (Theo lu t ph n x ) ạ X3 = (BG  B, BG  G, BG  C, BG  D, BG  CG) (Lu t h p) ậ ợ  AE) X4 = (BG  B, BG  G, BG  C, BG  D, BG  CG, CG …..

2 PHẠM THỊ THỦY

NG II

CH

ƯƠ TÌM PH T I THI U C A T P PH THU C HÀM Ủ Ậ

Ủ Ố

Ộ

Ụ

Ể

ộ ớ ụ ẫ ụ ề ậ ộ ộ ụ ể ể ố ộ ố ọ ả ng v i F. ớ ng đ ươ ụ  C là d th a b i vì ta có th d dàng đây ph thu c hàm A ư ừ ở ư ừ ể ễ ụ ộ ở c ph thu c hàm này thông qua A ượ ụ V i m i t p ph thu c hàm F đã cho, r t có th có nhi u ph thu c hàm là d th a, t c là ta ỗ ậ ư ừ ụ ứ ể ấ ấ có th suy d n ra các ph thu c hàm này thông qua t p ph thu c hàm còn l i trong F. V n ộ ể ạ ụ đ đ t ra là ph i làm sao thu g n s ph thu c hàm F thành t i thi u (g i là G) đ sao cho G ọ ề ặ v n t ẫ ươ Ví d v ph thu c hàm d th a: ộ ụ ề F = {A  B, B  C, A  C. có đ Nh v y t p ph thu c hàm t  B, B  C ng v i F là G = { A  B, B  C } ng đ ư ậ ậ ộ ụ ươ ươ ộ ớ

ụ ộ

a ﬁ b đ ượ ồ ạ a ﬁ b ﬁ b

(F – {a

c đ R = {U, F}, m t ph thu c hàm trong F có d ng trong t p ph thu c hàm F – { c g i là d th a n u ế b . ư ừ }) (cid:201) a )+ Đ nh nghĩa ph thu c hàm d th a: ị Cho l ủ a nh bao đóng c a ư ư ừ ụ ụ ộ ộ ộ ậ ọ } có ch a ứ b . T c là : ( ượ ứ

ng đ

ng đ ng: ượ c g i là t ọ ươ ớ ậ ụ ộ ủ ượ ồ c đ R Đ nh nghĩa ph t ươ ủ ươ M t t p ph thu c hàm G đ ộ ụ + = G+. Khi đó ta nói F ph G hay G ph F. n u nh : F ị ộ ậ ế ư ủ ng v i t p ph thu c hàm F c a l ươ ủ

ụ ộ ậ ụ ộ ộ + = F+) i thi u: ể ủ ậ ớ 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 đó: ươ  A Trong đó A là m t thu c tính. ề ộ ộ ộ ấ ượ ữ ể ể ộ ụ ụ ỗ ủ ả ộ Đ nh nghĩa ph t ủ ố ị M t ph t ể ủ ố ộ + G t ng v i F (t c là G ng đ ươ ứ + T t c các ph thu c hàm trong G đ u có d ng X ạ ụ ấ ả + Không th làm cho G nh h n đ c n a. (T c là không th xoá thêm b t kỳ ph thu c hàm ứ nào trong G hay xoá đi b t kỳ m t thu c tính nào bên phía ph i, phía trái c a m i ph thu c ộ ộ hàm mà G v n t ng đ ỏ ơ ấ ng v i F). ớ ươ ẫ ươ

ượ ẫ ộ ả b o Gả ng đ L u ý : Các ph thu c hàm hay các thu c tính xoá đ ư t ọ ươ ộ ng v i F thì ta g i đó là ph thu c hàm hay thu c tính d th a. ộ c theo cách trên mà v n đ m ộ ư ừ ụ ớ ươ ụ

ng pháp tìm ph t ươ i thi u: ể

ủ ố ụ ướ ỗ ạ  A1A2A3…An thành các phụ thu c hàm ộ Ph B c 1: Tách m i ph thu c hàm trong F có d ng X ộ mà v ph i (RH – Right Hand) ch có m t thu c tính: ế ả ộ ộ ỉ

X  A1 X  A2 ……… X  An ộ ụ ủ ạ ỏ ư ừ thì ộ ể ộ ụ ệ ừ ỗ ư ừ ư ừ ế

c 2 và 3 là KHÔNG TH thay đ i !!! Ể ầ ộ ế nói A là ư ừ ơ ẻ ộ ộ ạ ộ ẫ ổ i thích rõ th nào thu c tính d th a, ph thu c hàm d th a ? ư ừ . Ta ớ a +˚ ừ a , T c là ứ  E, A ộ ụ  B, C  B: ụ ộ  B là d th a vì C

+ = (CB) (cid:201)

B. ư ừ B c 2: Lo i b các thu c tính d th a bên phía trái c a m i ph thu c hàm. ướ B c 3: Duy t t ng ph thu c hàm và ki m tra xem có d th a không, n u d th a thì ướ xoá đi. b L u ý: Trình t ự ướ ư đây ta c n gi ả Ở ụ a A  b , v i A là m t thu c tính đ n l Đ nh nghĩa 1: M t ph thu c hàm có d ng ộ ụ ị ộ b . b t thu c tính d th a n u có th suy d n ra ể ế ư ừ  D}  GH, A  B, ABDE Ví d : Cho F = {AC + Xét ph thu c hàm AC Rõ ràng thu c tính A trong AC ộ + Xét ph thu c hàm ABDE ộ ụ

+ = BDE không ch a GH + = ADE không ch a GH

 GH ư ừ ư ừ ứ ứ + = ABDE có ch a ABDE - Thu c tính A : Không d th a vì (BDE) - Thu c tính B : Không d th a vì (ADE) - Thu c tính D: D th a vì (ABE) ư ừ ộ ộ ộ ứ

 GH ta đ c ABE  GH ( Lo i thu c tính D kh i ph thu c hàm ABDE ỏ ụ ạ ộ ộ ượ

3 PHẠM THỊ THỦY

 GH

+ Xét ph thu c hàm ABE ộ

ụ ộ ư ừ - Thu c tính E: D th a vì (AB) ộ ụ ộ ư ừ

+ = ABDE (cid:201) + Các thu c tính trong các ph thu c hàm còn l Cu i cùng ta đ

c t p ph thu c hàm không có thu c tính d th a g m: ượ ậ ố ABE i đ u không d th a. ồ ạ ề ộ ụ ộ ư ừ F = {C  B, AB  GH, A  E, A  D}

a ﬁ b ộ ộ ư ừ M t ph thu c hàm có d ng a b b ụ )+ ˚ , đ ạ (t c là v n suy d n ra ư ừ c g i là d th a ọ ượ ừ a , m c dù đã t ặ ẫ ẫ ứ ư ị ế ỏ ậ a ﬁ b ỏ ụ ỏ ộ  E, A  C, B  DE, A  B có d th a hay không b ng cách : Th lo i ph thu c hàm này kh i Fỏ ộ ụ ụ ể  D} ử ạ kh i F). ỏ  C, A ư ừ

+ ˚

ằ B thì nó là d th a, trái l ạ ư ừ ư ừ

ư ừ ỏ  B là không d th a. ậ ụ A ỏ

ẫ ể ư ừ

B ứ ư ừ

ẫ ể ư ừ ượ ỏ A B, BC, BDE, AE, AD} ư ừ ỏ C là d th a c F = {A ứ

ể B, BC, BDE, AE, AD} ư ừ ượ B B, BC, AE, AD} ỏ DE không d th a ư ừ ứ

E có d th a ? ể ư ừ ượ  B, BC, BDE, AD} ph thu c hàm này d th a c F = {A ứ ư ừ ụ ỏ ộ ứ B, BC, BDE, AD}

ể ư ừ ượ D là d th a. B, BC, BDE} ph thu c hàm A ộ ư ừ ờ ữ i các ph thu c hàm ta th y không có ph thu c hàm nào b lo i thêm n a (T c là F ụ ứ ấ ộ ộ Đ nh nghĩa ph thu c hàm d th a: ộ n u nh xoá b nó kh i t p F thì ta v n có : ( ẫ xoá b ph thu c hàm ụ  B, B Ví d : Cho F = {A + Ki m tra xem A sau đó tính A+, N u Aế i là không d th a. Sau khi lo i A ạ  B ta có F = {B  C, A  C, B  DE, A  E, A  D} Rõ ràng A+ = {AED} nên B ˇ A+, ch ng t ứ V y ph thu c hàm này không th lo i kh i F. ộ ể ạ  B, B  C, A  C, B  DE, A  E, A  D} F v n là: {A + Ki m tra B  C có d th a ? B, AC, BDE, AE, AD} - Lo i Bạ C kh i F, ta có F = {A ỏ - B+ = {BDE} không ch a C, ch ng t ỏ C là không d th a. ứ B, BC, AC, BDE, AE, AD} F v n là: {A + Ki m tra A C có d th a ? - Lo i Aạ C kh i F ta đ - A+ = {ABCDE} có ch a C, ch ng t ứ  F bây gi là: F = {A ờ + Ki m tra B DE có d th a ? - Lo i Bạ DE kh i F, ta đ c F = {A ỏ - B+ = {BC} không ch a DE, ch ng t ứ B, BC, BDE, AE, AD}  F v n là {A ẫ + Ki m tra A - Lo i Aạ E kh i F, ta đ ỏ - A+ = {ABCDE} ch a E, ch ng t  F bây gi là: {A ờ + Ki m tra A D có d th a ? - Lo i Aạ D kh i F, ta đ ỏ - A+ = {ABCDE} ch a D, ch ng t  F bây gi Duy t l ệ ạ = Const). Do v y t p ph thu c hàm cu i cùng sau khi lo i các ph thu c d th a là: c F = {A ứ ụ ỏ ứ B, BC, BDE}. là {A ụ ậ ậ ị ạ ộ ư ừ ụ ụ ạ ộ ố

trên, sau đây ta ề ậ ở ộ i thi u c a t p ph thu c hàm F. V i ph ớ l y ví d th c hi n vi c tìm ph t ệ ấ ng pháp lo i b thu c tính và ph thu c hàm d th a đã đ c p ụ ủ ậ F = {A B, B  C, B  DE} ư ừ ộ ươ ụ ự ạ ỏ ệ ộ ủ ố ụ ể

ụ

i thi u c a t p ph thu c hàm T sau đây : ậ ụ ủ ậ ủ ố ụ ộ ể

, ta đ c: Bài t p áp d ng Ví d 2: Tìm ph t T = {ABH  CK, A  D, C  E, BGH  F, F  AD, E  F, BH  E} • B c 1: Chuy n v ph i c a m i ph thu c hàm thành các thu c tính đ n l ụ ả ủ ế ộ ỗ ộ ơ ẻ ượ

ướ ể – ABH  C – ABH  K – A  D – BGH  F – F  A – F  D

4 PHẠM THỊ THỦY

– E  F – BH  E

ư ừ ủ ụ ỗ ộ ử d ngụ • B c 2: Lo i b các thu c tính d th a bên phía trái c a m i ph thu c hàm (S ph ng pháp lo i gi ng nh ví d 1). ố ạ ỏ ạ ướ ươ ộ ư ụ

C ụ

+ = {BHEFDAKC} có ch a C.

ứ

+ = {AHD} không ch a Cứ + = {ABD} không ch a Cứ

+ Xét ph thu c hàm ABH ộ - A d th a vì (BH) ư ừ - B Không d th a vì (AH) ư ừ - H không d th a vì (AB) ư ừ ứ ầ ế

ả ấ

K vì (BH)+ = {BHCEFDAK} ch a K và G d th a trong ng t : A d th a trong ABH ư ừ ứ ự ươ ư ừ ứ ế ố

c thu c tính nào n a. ượ ữ ể ộ ư ừ ạ ỏ ộ C, BHK, AD, BHF, FA, FD, EF, BHE} i T = {BH  K t qu sau l n th nh t: T = {BH  C, ABH  K, A  D, BGH  F, F  A, F  D, E  F, BH  E} + T BGHF vì (BH)+ = {BHEFDAKC} có ch a F.  K t qu cu i cùng: ả T = {BH  C, BH  K, A  D, BH  F, F  A, F  D, E  F, BH  E} Đ n đây ta không th lo i thêm đ ể ạ • B c 3: Lo i b các ph thu c hàm d th a ụ ướ Hi n t ệ ạ

 C, Ta có (BH)+ = {BHFADEK} không ch a C => không d th a.

+ Th lo i BH ử ạ

ư ừ ứ

+ Th lo i BH

ử ạ K, Ta có (BH)+ = {BHCFADE} không ch a K => không d th a. ư ừ ứ

+ Th lo i A

ử ạ  D, Ta có (A)+ = {A} không ch a D => không d th a. ư ừ ứ

+ Th lo i BH

ử ạ  F, Ta có (BH)+ = {BHCKEFAD} có ch a F => lu t này d th a, lo i ư ừ ứ ậ ạ ra kh i T,ỏ

ta đ c: T = {BH C, BHK, AD, FA, FD, EF, BHE} ượ

+ Th lo i F

ử ạ  A, Ta có F+ = {FD} không ch a A => không d th a ư ừ ứ

+ Th lo i F

đ c : T = ử ạ  D, ta có F+ = {FAD} có ch a D nên lu t này d th a. Lo i kh i T ta ư ừ ứ ậ ạ ỏ ượ

{BHC, BHK, AD, FA, EF, BHE}

ư ừ ứ ứ t c các ph thu c hàm trong l ư ừ ế ấ ả ộ ồ c đ . K t qu cu i cùng ta có ph ố ủ ể

+ Th lo i E + Th lo i BH Đ n đây ta đã th xong t ế t i thi u T = {BH ố Ví d 2: Tìm ph t

i thi u c a l c đ cho d i đây: ử ạ F, ta có E+ = {E} không ch a F => Không d th a. ử ạ E, ta có (BH)+ = {BHCK} không ch a E nên không d th a. ả ượ ụ ử C, BH K, AD, FA, EF, BHE}. ủ ố ủ ượ ướ ụ ồ ể

R = , V i: ớ U = {ABCDEGH} F = {A BC, BE  G, E  D, D  G, A  B, AG  BC} B c 1 Tách v ph i thành 1 thu c tính: ả ướ ộ ế

 AB  AC  BEﬁ G  Eﬁ D  Dﬁ G  Aﬁ B  AGﬁ B  AGﬁ C ướ

B c 2 Xoá thu c tính d th a ộ B d th a trong BE G d th a trong AG ư ừ ﬁ G. Vì (E)+ = {DEG} ch a Gứ ﬁ B. Vì (A)+ = {ABC} ch a Bứ ư ừ ư ừ

5 PHẠM THỊ THỦY

ư ừ ﬁ C. Vì (A)+ = {ABC} ch a Cứ B c 3 Xoá ph thu c hàm d th a: ộ ướ ư ừ

ế ế ế ế ẫ ẫ ẫ ẫ ỏ ỏ ỏ ỏ

+ = {ABC} Ch a Bứ + = {ABC} Ch a Cứ + = {ABC} Ch a Bứ + = {DEG} Ch a Gứ

Ph t ủ ố

G d th a trong AG ụ Aﬁ B d th a. Vì n u xoá kh i F, ta v n có (A) ư ừ Aﬁ C d th a. Vì n u xoá kh i F, ta v n có (A) ư ừ Aﬁ B d th a. Vì n u xoá kh i F, ta v n có (A) ư ừ Eﬁ G d th a. Vì n u xoá kh i F, ta v n có (E) ư ừ i thi u c a F là : ủ ể 1) Aﬁ B 2) Aﬁ C 3) Dﬁ G 4) Eﬁ D Ví d 3: Tìm ph t i thi u c a l c đ cho d i đây: ủ ượ ủ ố ướ ụ ồ ể

R = U = (ABCDEGHIJ) F = {A  BDE, DE  G, H  J, J  HI, E  DG, BC GH, HGJ, EG} B c 1 Tách v phi thành 1 thu c tính: ướ ộ ế

 Aﬁ B  Aﬁ D  Aﬁ E  DEﬁ G  Hﬁ J Jﬁ H  Jﬁ  I  Eﬁ D  Eﬁ G  BCﬁ G  BCﬁ H  HGﬁ J  Eﬁ G ướ

ư ừ ư ừ ư ừ ﬁ G. Vì (E)+ = {DEG} ch a Gứ ﬁ J. Vì (H)+ = {HIJ} ch a Jứ B c 3 Xoá ph thu c hàm d th a: ộ ướ

ẫ ẫ ẫ ẫ ế ế ế ế ư ừ ỏ ỏ ỏ ỏ

+ = {ABDEG} Ch a Dứ + = {DEG} Ch a Gứ + = {HIJ} Ch a Jứ + = {DEG} Ch a Gứ

Ph t ủ ố

B c 2 Xoá thu c tính d th a ộ D d th a trong DE G d th a trong HG ụ Aﬁ D d th a. Vì n u xoá kh i F, ta v n có (A) ư ừ Eﬁ G d th a. Vì n u xoá kh i F, ta v n có (E) ư ừ Hﬁ J d th a. Vì n u xoá kh i F, ta v n có (H) ư ừ Eﬁ G d th a. Vì n u xoá kh i F, ta v n có (E) ư ừ i thi u c a F là : ủ ể  Aﬁ B  BCﬁ H  Aﬁ E  BCﬁ G  Hﬁ J Jﬁ H  Jﬁ  I  Eﬁ D  Eﬁ G

6 PHẠM THỊ THỦY

ƯƠ

TÌM KHOÁ T I THI U C A L

C Đ QUAN H

Ố

Ệ

CH Ể

NG III Ủ ƯỢ Ồ

ố i thi u: ể

ụ ậ ậ ộ ộ c g i là ọ c đ R = , trong đó U là t p thu c tính, F là t p ph thu c hàm. K đ i thi u c a R n u nh s thu c tính trong K là ít nh t nh ng v n tho mãn K ượ + =U . 1. Đ nh nghĩa khoá t ị Cho l ồ khoá t ể ượ ố ư ố ư ủ ế ấ ả ẫ ộ

ố i thi u: ể

ượ

t khoá i thi u) c a quan h R. ệ i thi u (L u ý, t nay n u không có s nh m l n thì ta g i t ự ọ ắ ế ẫ ầ ủ ể ể ố ư ừ i thi u là Khoá). 2. Phát bi u bài toán tìm khoá t ể c đ quan h R = Cho l ồ ệ Hãy tìm m t khoá (t ố ộ 3. Thu t toán tìm khoá t t ố ậ ể

*** Chi ti t cài đ t xin xem trong ph n ph l c. ế ụ ụ ầ ặ

Bài t p áp d ng ụ ậ

c đ R = :

i thi u K c a l ể ố c đ R ? ồ Ví d 1:ụ Cho l ồ ượ U = {ABCDE} F = {Aﬁ B, Bﬁ C, Bﬁ DE, Aﬁ E, Aﬁ D} Hãy tìm m t khoá t ủ ượ ộ H ng d n: ẫ ướ

B c 1: Đ t ướ ặ ấ ậ ậ ệ ấ ệ ả ộ

ướ

T = {AB} (T là t p các thu c tính xu t hi n phía trái) ộ P = {BCDE} (P là t p các thu c tính xu t hi n phía ph i) K = U\P = {A} ử + B c 2: Tính th K Ta có K+ = {ABCDE} ộ ủ c đ quan h R = , Trong đó : Vì K+ = U, nên K = {A} là m t khoá c a R. Ví d 2: Cho l ồ ượ ụ ệ

U = {ABCDE} F = {ABﬁ DE, Eﬁ AD, Dﬁ C} i thi u K c a l ố ể ủ ưượ c đ R ồ

Hãy tìm m t khoá t ộ H ng d n : ẫ B c 1: Đ t ặ ướ ướ

T = {ABED} P = {DEAC} K = U\P = {B} ử + B c 2: Tính th K ướ c 3 Ta có K+ = {B} ≠ U, nên ti p t c b ế ụ ướ B c 3 : Tính K = K ¨ (T ˙ P) ướ Ta có K = K ¨ (T ˙ P) = {ABDE}

˙ P= {AED} kh i Kỏ ộ ử ừ ỏ ướ ử ạ ỏ c A ạ ượ ằ ẫ ỏ ử ạ ỏ

c {E}. K v n là {BDE} ẫ ử ạ ỏ ỏ

i thi u tìm đ c là : K = {BE} ử ế ượ ố ể ế ậ

c đ quan h R = , Trong đó : B c 4 : Th xoá t ng thu c tính trong T Th lo i b {A} kh i K, Ta có: K = {BED} và K+ = {BEDAC} v n b ng U, nên ta lo i đ Th lo i b {E} kh i K, Ta có: K = {BD} và K+ = {BDC} Do K+ ≠ U nên không lo i đ ạ ượ Th lo i b {D} kh i K, Ta có: K = {BE} và K+ = {BEADC} = U. Đ n đây ta đã th h t. V y khoá t Ví d 3 ụ Cho l ượ ệ ồ

7 PHẠM THỊ THỦY

i thi u K c a l ố ể ủ ượ U = {ABCDEG} F = {ABﬁ C, Cﬁ A, BCﬁ D, ACDﬁ B, Dﬁ EG, BEﬁ C, CGﬁ BD, CEﬁ AG} c đ R. ồ

ướ ướ

ệ ậ ả ấ ộ

Hãy tìm m t khoá t ộ H ng d n : ẫ B c 1: Đ t ặ  T = {ABCDEG}  P = {ABCDEG} (P là t p các thu c tính xu t hi n phía ph i)  K = U\P = {} ử + B c 2: Tính th K ướ c 3 Ta có K+ = { } ≠ U, nên ti p t c b ế ụ ướ B c 3 : Tính K = K ướ ¨ (T ˙ P) Ta có K = K ¨ (T ˙ P) = {ABCDEG}

˙ P = {ABCDEG} kh i Kỏ ộ ử ướ ử ạ ỏ c A ạ ượ ẫ ằ ỏ ử ạ ỏ c B ạ ượ ằ ẫ ỏ ử ạ ỏ

c {C}. K v n là {DEGC} ẫ ỏ ử ạ ỏ c D ằ ẫ ạ ượ ỏ ử ạ ỏ c E ằ ẫ ạ ượ ử ạ ỏ

 Đã th h t ! ử ế c là : K = {CG} i thi u tìm đ ế ố ượ ử ế ạ ượ ậ c {G}. K v n là {CG} ẫ ể

c đ quan h R = , Trong đó : ồ ệ

c đ R ồ ủ ượ ể ố

ướ ướ

ướ c 3 ế ụ ướ ¨ (T ˙ P) ướ

ử ộ ˙ P= {ABCDE} kh i Kỏ ướ ử ạ ỏ

c {A}. K v n là {HBCDEA} ẫ ử ạ ỏ ỏ

c {B}. K v n là {HCDEAB} ẫ ử ạ ỏ

c {C}. K v n là {HDEABC} ẫ ử ạ ỏ B c 4 : Th xoá t ng thu c tính trong T ừ Th lo i b {A} kh i K, Ta có: ỏ K = {BCDEG} và K+ = {BCDEGA} v n b ng U, nên ta lo i đ Th lo i b {B} kh i K, Ta có: K = {CDEG} và K+ = {CDEGAB} v n b ng U, nên ta lo i đ Th lo i b {C} kh i K, Ta có: K = {DEG} và K+ = {DEG} Do K+ ≠ U nên không lo i đ ạ ượ Th lo i b {D} kh i K, Ta có: K = {EGC} và K+ = {EGCABD} v n b ng U, nên ta lo i đ Th lo i b {E} kh i K, Ta có: K = {GC} và K+ = {GCABDE} v n b ng U, nên ta lo i đ Th lo i b {G} kh i K, Ta có: ỏ K = {C} và K+ = {CA} Do K+ = ≠ U nên không lo i đ Đ n đây ta đã th h t. V y khoá t Ví d 4ụ Cho l ượ U = {ABCDEGH} F = {Aﬁ C, ABﬁ C, Cﬁ DG, CDﬁ G, ECﬁ ABEG,C, Hﬁ C} Hãy tìm m t khoá t i thi u K c a l ộ H ng d n : ẫ B c 1: Đ t ặ T = {ABCDEH} P = {ABCDEG} K = U\P = {H} ử + B c 2: Tính th K Ta có K+ = {HCDG} ≠ U, nên ti p t c b B c 3 : Tính K = K Ta có K = K¨ (T ˙ P) = {HABCDE} B c 4 : Th xoá t ng thu c tính trong T ừ Th lo i b {A} kh i K, Ta có: ỏ K = {HBCDE} và K+ = {HBCDEGA} Do K+ „ U nên không lo i đ ạ ượ Th lo i b {B} kh i K, Ta có: K = {HCDEA} và K+ = {HCDEAGB} Do K+ „ U nên không lo i đ ạ ượ Th lo i b {C} kh i K, Ta có: ỏ K = {HDEAB} và K+ = {HDEABCG} Do K+ „ U nên không lo i đ ạ ượ Th lo i b {D} kh i K, Ta có: ỏ K = {HEABC} và K+ = {HEABCDG}

8 PHẠM THỊ THỦY

c {D}. K v n là {HEABCD} ẫ ử ạ ỏ U nên không lo i đ ỏ

ẫ c là : K = {HABCDE} ử ế c {E}. K v n là {HABCDE}. i thi u tìm đ ể ượ ố

c đ quan h R = , Trong đó : Do K+ „ ạ ượ Th lo i b {E} kh i K, Ta có: K = {HABCD} và K+ = {HABCDG} Do K+ „ U nên không lo i đ ạ ượ Đ n đây ta đã th h t. V y khoá t ậ ế Ví d 5:ụ Cho l ượ ệ

ồ U = {ABC} F = {Aﬁ B, Bﬁ A, Cﬁ B} i thi u K c a l ủ ượ c đ R ồ ố ể

ướ ướ

ướ Hãy tìm m t khoá t ộ H ng d n : ẫ B c 1: Đ t ặ T = {ABC} P = {AB} K = U\P = {C} ử + B c 2: Tính th K Ta có K+ = {CBA} = U

Vì K+ = U, nên K = {C} là m t khoá c a R. ủ ộ

9 PHẠM THỊ THỦY