Bài tâp lý thuyết CSDL quan hệ

Ệ

KHOA CÔNG NGH THÔNG TIN B MÔN CÔNG NGH PH N M M

Ộ

Ầ

Ệ

Ề

Biên so n : ạ

- Nguy n Minh Quý

ễ

Tài li u l u hành n i b

ệ ư

ộ ộ

Biên so n: B môn Công ngh ph n m m

ệ

ề

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

M C L C Ụ Ụ

ƯƠ CH TÌM BAO ĐÓNG C A T P THU C TÍNH Ủ Ậ 2. Thu t toán tìm bao đóng c a t p thu c tính ậ Ộ ủ ậ ậ ụ

Ể Ậ Ủ Ộ

ng:

ụ

C Đ QUAN H Ể ố ị i thi u: ể ố 3 NG I ........................................................................................................ 3 ........................................................ 3 ............................................. ộ 3 ....................................................................................................... Thu t toán 1 3 ............................................................................................. Bài t p áp d ng: ậ CH NG II 6 ....................................................................................................... ƯƠ 6 ......................................... TÌM PH T I THI U C A T P PH THU C HÀM Ủ Ố Ụ Đ nh nghĩa ph thu c hàm d th a: 6 .............................................................. ị ộ ụ ư ừ ng đ Đ nh nghĩa ph t 6 ....................................................................... ị ủ ươ ươ Đ nh nghĩa ph t i thi u: 6 ............................................................................... ể ủ ố ị Ph ng pháp tìm ph t 6 ..................................................................... i thi u: ủ ố ươ ể Bài t p áp d ng 8 .............................................................................................. ậ 12 .................................................................................................... NG III CH ƯƠ 12 TÌM KHOÁ T I THI U C A L ........................................ Ủ ƯỢ Ồ Ệ Ố 12 1. Đ nh nghĩa khoá t ....................................................................... i thi u: ể 12 ...................................................... 2. Phát bi u bài toán tìm khoá t ể 12 ............................................................................................ Bài t p áp d ng ụ ậ

2 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

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 ủ ồ + là t p t t h p c các thu c tính mà có : Cho l ượ U), ký hi u Xệ ệ ậ ấ ợ ả ộ X. 1. Đ nh nghĩa bao đóng t p thu c tính ậ ộ th suy di n logic t ễ ể X (X ˝ ừ

• Nh n xét: Bao đóng c a t p thu c tính X th c ch t là t p t ủ ậ ậ ấ ậ ấ ả ộ i” (hay suy ra) nó t tính mà ta có th “v i t t c các thu c ộ ầ ộ ể ớ ớ • 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 ơ ở ệ ự t p thu c tính X ban đ u. ừ ậ ể ậ m t ph thu c hàm nào đó có t n t ồ ạ ụ ộ i trong quan h hay không... ệ ệ ộ

ậ ủ ậ ộ

c đ quan h R=(U,F). ầ ộ ượ ệ ồ 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 ầ ầ ậ ộ

+ = Const.

+ Ph Ki m tra l n l ộ ể ả ứ b ) vào vào X+: X+ := X+ ¨ ph i (t c L p l ặ ạ

ng pháp: ươ a fi b t t ng ph thu c hàm fi = ˝ X+ thì k t n p v ầ ượ ừ ụ , n u ế a ế ạ ế b . i cho đ n khi nào X ế

Thu t toán 1

ậ

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

X+ := X+ ¨ b ; 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)+

3 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

i:ả Gi a) Tính (D)+

fi EG) fi 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) +

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

c) Tính (BE)+

ụ ụ ụ fi AG) fi D) fi H) (= Constant) X0 = BE fi 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)+

+ = ABCDEGH

ụ fi BD) fi H) fi EG) (= Constant) X0 = CG fi 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) ậ

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

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 +

+ = ABCDEG

fi AE) ụ ụ fi BC) fi CD) (= Constant) ụ X0 = C fi 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) ậ

b) Tính (B)+ X0 = B

4 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

+ = ABCDEG

fi CG) ụ fi CD) ụ fi AE) (= Constant) ụ 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)+

ụ fi BC) fi CD) (= Constant) X0 = AEG 1) X1 = AEGBC (áp d ng AEG 2) X2 = AEGBCD (áp d ng BG V y (AEG) ụ + = ABCDEG ậ

ng t nh bao đóng c a t p thu c tính, ng ư ươ ườ ậ ộ ự ủ ậ ụ ộ ộ ụ ữ ộ i ta cũng đ nh ** Chú ý: T ị ủ ủ nghĩa bao đóng c a 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ó. ạ ứ ạ ậ ậ c ng d ng do v y H n n a vi c tính bao đóng c a t p ph thu c hàm ít đ ụ ượ ứ ụ ủ ậ ơ xin không đ c p trong tài li u này. ệ ộ ệ ề ậ

ộ ộ ụ ề ớ ụ ủ ậ bài t p 2. ậ ở

ề ệ ả ậ

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 …..

5 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

NG II

CH

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

Ủ Ố

Ộ

Ụ

Ể

ộ ụ ụ ể ề ấ ộ ụ ể ẫ ộ ả ấ ộ ng đ 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 ụ ố ề ặ ọ ạ ng v i F. i thi u (g i là G) đ sao cho G v n t thu c hàm F thành t ớ ể ố ớ ư ừ ụ ộ ẫ ươ ươ ể ọ

ụ ụ ề đây ph thu c hàm A ư ừ ở ụ ộ ở

Ví d v ph thu c hàm d th a: ộ F = {A  B, B  C, A  C. có th d dàng có đ ụ Nh v y t p ph thu c hàm t c ph thu c hàm này thông qua A ng v i F là G = { A ộ ng đ  C là d th a b i vì ta ư ừ  B, B  C  B, B  C } ể ễ ư ậ ậ ượ ộ ươ ụ ươ ớ

ộ ụ

(F – {a

}) (cid:201)

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

ng đ

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

i thi u c a t p ph thu c hàm F là m t t p ph thu c hàm G, ộ ụ ị ộ ủ ố ể i thi u: ể ủ ậ ộ ậ ụ ộ

+ = F+)

ng đ ươ ớ ng v i F (t c là G ụ  A Trong đó A là m tộ ề ạ ộ

ỏ ơ ượ ứ ữ ể ể ấ ấ ộ ộ Đ nh nghĩa ph t M t ph t ủ ố Trong đó: + G t ươ ứ + T t c các ph thu c hàm trong G đ u có d ng X ấ ả thu c tính. ộ + 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 ộ ng đ ph i, phía trái c a m i ph thu c hàm mà G v n t ươ ng v i F). ớ ẫ ươ ụ ả ủ ụ ộ ỗ

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

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

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

X  A1 X  A2 ……… X  An

ạ ỏ ủ ụ ộ ỗ 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ì ệ ừ thì xoá đi. ướ ư ừ

6 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

L u ý: Trình t c 2 và 3 là KHÔNG TH thay đ i !!! ư b ự ướ ổ Ể

i thích rõ th nào thu c tính d th a, ph thu c hàm ư ừ ụ ộ ộ ầ ả ế

ộ ộ ớ . Ta nói A là thu c tính d th a n u có th suy d n ra ộ b t ư ừ ạ ế a A  b , v i A là m t thu c tính ộ ừ a , T c làứ ể ẫ đây ta c n gi Ở d th a ? ư ừ Đ nh nghĩa 1: M t ph thu c hàm có d ng ị ụ đ n l ộ ơ ẻ b . a +˚

Ví d : Cho F = {AC  B, C  B, ABDE  GH, A  E, A  D} ụ

+ = (CB) (cid:201)

+ 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 ộ

 B: ụ ộ  B là d th a vì C B. ư ừ

+ = 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 ỏ ụ ạ ộ ộ ượ

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

+ = ABDE (cid:201)

+ Các thu c tính trong các ph thu c hàm còn l

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

i đ u không d th a. ụ ộ ộ ạ ề ư ừ

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: ố ượ ậ ư ừ ụ ộ ồ ộ F = {C  B, AB  GH, A  E, A  D}

a fi b ụ ộ a ọ ạ c g i là d th a n u nh xoá b nó kh i t p F thì ta v n có : ( ỏ ộ ỏ ậ ư ẫ b a fi b t , ư ừ M t ph thu c hàm có d ng b )+ ˚ kh iỏ , m c dù đã xoá b ph thu c hàm ỏ ụ ư ừ ẫ ừ a ụ ặ ẫ ộ Đ nh nghĩa ph thu c hàm d th a: ị ộ đ ượ ế (t c là v n suy d n ra ứ F).

Ví d : Cho F = {A  B, B  C, A  C, B  DE, A  E, A  D} ụ

+ ˚

+, N u Aế

+ Ki m tra xem A hàm này kh i F sau đó tính A d th a. ư ừ

ể ư ừ ụ  B có d th a hay không b ng cách : Th lo i ph thu c ộ ằ i là không ử ạ B thì nó là d th a, trái l ỏ ư ừ ạ

ỏ  B là không d th a. ư ừ 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 ẫ

 C có d th a ? ể ư ừ

+ Ki m tra B 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 ư ừ ứ

7 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

F v n là: {A B, BC, AC, BDE, AE, AD} ẫ

+ Ki m tra 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

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

+ Ki m tra B - 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 ẫ

DE có d th a ? ể ư ừ ượ B ứ B, BC, AE, AD} ỏ DE không d th 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

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} ờ

+ Ki m tra A - Lo i Aạ D kh i F, ta đ ỏ - A+ = {ABCDE} ch a D, ch ng t  F bây gi

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

ụ ụ ộ ộ ứ ụ ộ ố ị ạ Duy t l 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 = 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à: ư ừ ụ ạ ộ F = {A B, B  C, B  DE}

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

Bài t p áp d ng ụ ậ

i thi u c a t p ph thu c hàm T sau đây : ụ ủ ậ ủ ố ụ ộ ể Ví d 2: Tìm ph t T = {ABH  CK, A  D, C  E, BGH  F, F  AD, E  F, BH  E}

ả ủ ế ể ộ ộ ỗ ướ , ta đ • 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 ẻ ượ

c: – ABH  C – ABH  K – A  D – BGH  F – F  A – F  D – E  F – BH  E

8 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

ướ ủ ụ ỗ ộ • 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 ộ ư ừ ạ ỏ ng pháp lo i gi ng nh ví d 1). hàm (Sử d ng ph ố ươ ư ụ ụ ạ

+ = {BHEFDAKC} có 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)

C ụ ứ

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

ư ừ ư ừ

ế ứ ả ấ ầ  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 ự d th a trong BGH

ng t : A d th a trong ABH K vì (BH)+ = {BHCEFDAK} ch a K và G ư ừ ứ 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 đ c thu c tính nào n a. ể ạ ể ượ ữ ộ

ư ừ ạ ỏ ụ ộ i T = {BH C, BHK, AD, BHF, FA, FD, EF, BHE} • B c 3: Lo i b các ph thu c hàm d th a ướ Hi n t ệ ạ

+ Th lo i BH ử ạ

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

th a.ừ

+ Th lo i BH ử ạ

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

+ Th lo i A

th 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 c: T = {BH C, BHK, AD, FA, FD, ạ ra kh i T, ta đ ỏ ừ ượ

+ Th lo i F

EF, BHE}

+ Th lo i F

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

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

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

+ Th lo i E + Th lo i BH

ư ừ ứ ử ạ 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 đ . K t qu ử ượ ế ồ ộ ụ i thi u T = {BH ả C, BH K, AD, FA, EF, ế ố ủ ố t c các ph thu c hàm trong l ấ ả ể Đ n đây ta đã th xong t cu i cùng ta có ph t BHE}.

Ví d 2: Tìm ph t i thi u c a l c đ cho d i đây: ủ ố ụ ủ ượ ể ồ ướ

9 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

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  BEfi G  Efi D  Dfi G  Afi B  AGfi B  AGfi 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 d th a trong AG ư ừ fi G. Vì (E)+ = {DEG} ch a Gứ fi B. Vì (A)+ = {ABC} ch a Bứ fi 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ứ

Afi B d th a. Vì n u xoá kh i F, ta v n có (A) Afi C d th a. Vì n u xoá kh i F, ta v n có (A) Afi B d th a. Vì n u xoá kh i F, ta v n có (A) Efi G d th a. Vì n u xoá kh i F, ta v n có (E) ụ ư ừ ư ừ ư ừ ư ừ ế ế ế ế ẫ ẫ ẫ ẫ ỏ ỏ ỏ ỏ

Ph t ủ ố

i thi u c a F là : ủ ể 1) Afi B 2) Afi C 3) Dfi G 4) Efi 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: ướ ộ ế

 Afi B  Afi D  Afi E  DEfi G  Hfi J Jfi H  Jfi  I  Efi D  Efi G  BCfi G

10 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

 BCfi H  HGfi J  Efi G

ướ

B c 2 Xoá thu c tính d th a ộ D d th a trong DE G d th a trong HG ư ừ fi G. Vì (E)+ = {DEG} ch a Gứ fi 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ứ

Afi D d th a. Vì n u xoá kh i F, ta v n có (A) Efi G d th a. Vì n u xoá kh i F, ta v n có (E) Hfi J d th a. Vì n u xoá kh i F, ta v n có (H) Efi G d th a. Vì n u xoá kh i F, ta v n có (E) ế ế ế ế ẫ ẫ ẫ ẫ ư ừ ỏ ỏ ỏ ỏ ụ ư ừ ư ừ ư ừ ư ừ

Ph t ủ ố

i thi u c a F là : ủ ể  Afi B  BCfi H  Afi E  BCfi G  Hfi J Jfi H  Jfi  I  Efi D  Efi G

11 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ạ

ầ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

ƯƠ

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

C Đ QUAN H

Ố

Ệ

CH Ể

NG III Ủ ƯỢ Ồ

i thi u: ể ố

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

ố i thi u: ể

ượ i thi u) c a quan h R. 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 ố ộ ủ ể ệ

i thi u (L u ý, t nay n u không có s nh m l n thì ể ư ừ ự ế ầ ẫ ố i thi u là Khoá). 3. Thu t toán tìm khoá t ậ t khoá t ta g i t ọ ắ ể ố

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

Bài t p áp d ng ụ ậ

c đ R = :

Ví d 1:ụ Cho l ồ ượ U = {ABCDE} F = {Afi B, Bfi C, Bfi DE, Afi E, Afi D}

Hãy tìm m t khoá t i thi u K c a l ộ ố ủ ượ ể c đ R ? ồ

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}

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

Ví d 2: Cho l c đ quan h R = , Trong đó : ụ ượ ồ ệ

U = {ABCDE} F = {ABfi DE, Efi AD, Dfi C}

Hãy tìm m t khoá t i thi u K c a l ộ ố ủ ưượ ể c đ R ồ

H ng d n : ướ ẫ

B c 1: Đ t ặ ướ

T = {ABED} P = {DEAC}

12 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

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}

B c 4 : Th xoá t ng thu c tính trong T ướ ử ừ ộ ˙ P= {AED} kh i Kỏ

ử ạ ỏ ỏ 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 đ c A ẫ ằ ạ ượ

ử ạ ỏ ỏ

Th lo i b {E} kh i K, Ta có: K = {BD} và K+ = {BDC} Do K+ ≠ U nên không lo i đ ạ ượ c {E}. K v n là {BDE} ẫ

ử ạ ỏ ỏ 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 i thi u tìm đ c là : K = {BE} ử ế ế ậ ố ể ượ

c đ quan h R = , Trong đó : Ví d 3 ụ Cho l ượ ồ

ệ U = {ABCDEG} F = {ABfi C, Cfi A, BCfi D, ACDfi B, Dfi EG, BEfi C, CGfi BD, CEfi AG}

Hãy tìm m t khoá t i thi u K c a l ộ ố ủ ượ ể c đ R. ồ

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}

B c 4 : Th xoá t ng thu c tính trong T ừ ướ ử ộ ˙ P = {ABCDEG} kh i Kỏ

ử ạ ỏ ỏ 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 đ c A ằ ẫ ạ ượ

ử ạ ỏ ỏ 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 đ c B ằ ẫ ạ ượ

13 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ề

ệ

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

ử ạ ỏ ỏ

c {C}. K v n là {DEGC} 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 đ c D ẫ ằ ạ ượ

ử ạ ỏ ỏ 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 đ c E ẫ ằ ạ ượ

ử ạ ỏ

 Đã th h t ! Th lo i b {G} kh i K, Ta có: ỏ K = {C} và K+ = {CA} Do K+ = ≠ U nên không lo i đ ạ ượ c {G}. K v n là {CG} ẫ ử ế

Đ n đây ta đã th h t. V y khoá t i thi u tìm đ c là : K = {CG} ử ế ế ậ ố ể ượ

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

Ví d 4ụ Cho l ượ U = {ABCDEGH} F = {Afi C, ABfi C, Cfi DG, CDfi G, ECfi ABEG,C, Hfi C}

Hãy tìm m t khoá t i thi u K c a l ộ ố ủ ượ ể c đ R ồ

H ng d n : ướ ẫ

ướ

B c 1: Đ t ặ T = {ABCDEH} P = {ABCDEG} K = U\P = {H}

ướ c 3 ử + B c 2: Tính th K Ta có K+ = {HCDG} ≠ U, nên ti p t c b ế ụ ướ

¨ (T ˙ P) ướ 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 ừ ướ ử ộ ˙ P= {ABCDE} kh i Kỏ

ử ạ ỏ ỏ

Th lo i b {A} kh i K, Ta có: K = {HBCDE} và K+ = {HBCDEGA} Do K+ „ U nên không lo i đ c {A}. K v n là {HBCDEA} ạ ượ ẫ

ử ạ ỏ ỏ

Th lo i b {B} kh i K, Ta có: K = {HCDEA} và K+ = {HCDEAGB} Do K+ „ U nên không lo i đ c {B}. K v n là {HCDEAB} ạ ượ ẫ

Th lo i b {C} kh i K, Ta có: ử ạ ỏ ỏ

14 Version 1.0 – 10/2005 UTE H ng Yên ư

Biên so n: B môn Công ngh ph n m m

ệ

ề

ầ

ạ

ộ

ậ Bài t p Lý thuy t CSDL quan ế hệ

K = {HDEAB} và K+ = {HDEABCG} Do K+ „ U nên không lo i đ c {C}. K v n là {HDEABC} ạ ượ ẫ

ử ạ ỏ ỏ

Th lo i b {D} kh i K, Ta có: K = {HEABC} và K+ = {HEABCDG} Do K+ „ U nên không lo i đ c {D}. K v n là {HEABCD} ạ ượ ẫ

ử ạ ỏ ỏ

Th lo i b {E} kh i K, Ta có: K = {HABCD} và K+ = {HABCDG} Do K+ „ U nên không lo i đ c {E}. K v n là {HABCDE}. ạ ượ ẫ

Đ n đây ta đã th h t. V y khoá t i thi u tìm đ c là : K = {HABCDE} ử ế ế ậ ố ể ượ

c đ quan h R = , Trong đó : Ví d 5:ụ Cho l ượ ệ

ồ U = {ABC} F = {Afi B, Bfi A, Cfi B}

Hãy tìm m t khoá t i thi u K c a l ộ ố ủ ượ ể c đ R ồ

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. ủ ộ

15 Version 1.0 – 10/2005 UTE H ng Yên ư