zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài tập về khóa

Chia sẻ: Nguyen Ngoc Son Son | Ngày: | Loại File: DOC | Số trang:9

Báo xấu

133
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Định nghĩa: Cho lược đồ quan hệ a=(U,F) , KÍU n ếu K+= U, thì ta nói K là một siêu khoá. Chú ý: Điều kiện K+=U có thể thay bằng KU hoặc KU \ K...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập về khóa

NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm 3. BµI TËP VÒ kho¸ MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC Phân biệt các loại khoá  Các thuật toán tìm một khoá, nhiều khoá.  Ứng dụng giải quyết các bài toán về khoá.  A/ NHẮC LẠI LÝ THUYẾT CÁC ĐỊNH NGHĨA, TÍNH CHẤT, THUẬT TOÁN I. 1. Họ Sperner Nếu gọi Kα là tập tất c các khoá của lược đồ α=(U,F), như vậy mỗi phần tử của K α là một tập thuộc tính và các tập hợp đó là không bao nhau. Định nghĩa: Họ Sperner trên U là họ M={ X | X ⊆ U } sao cho hai phần tử của M là không bao nhau. Nhận xét: Tập hợp Kα tất cả các khoá của lược đồ là một họ Sperner trên U. 2. Siêu khoá và khoá Định nghĩa: Cho lược đồ quan hệ α=(U,F) , K⊆ U n ếu K+= U, thì ta nói K là một siêu khoá. Chú ý: Điều kiện K+=U có thể thay bằng KU hoặc KU \ K Định nghĩa: Cho lược đồ quan hệ α=(U,F) , K⊆ U n ếu K+= U, thì ta nói K là một siêu khoá. Chú ý: Điều kiện K+=U có thể thay bằng KU hoặc KU \ K Định nghĩa: Cho lược đồ quan hệ α=(U,F), tập K ⊆ U được gọi là khoá của lược đồ (nếu như nó thoả mãn: - K là một siêu khoá - ∀ K1 ⊂ K thì K1 Không là siêu khoá tức K+1 ≠ U Chú ý: định nghĩa này là tương đương với định nghĩa Cho lược đồ quan hệ α=(U,F), tập K ⊆ U được gọi là khoá của lược đồ ( nếu như nó thoả mãn: - K U ∈ F+ - ∀ K1 ⊂ K thì K1  U ∉ F+ (K+ ≠ U) Tập hợp Kα tất cả các khoá của lược đồ là một họ Sperner trên U. Bài toán: Cho M là một họ Sperner trên U thì có tồn tại hay không một l ược đ ồ quan hệ α=(U,F) sao cho Kα =M ( lược đồ có các khoá là các phần tử của họ M). Trả lời: Có tồn tại một lược đồ α=(U,F) được xây dựng như sau: Xây dựng F, giả sử M={X1, X2,..., Xn} ta xây dựng F nh ư sau: F={ Xi U\ Xi ∀ i=1, .., n } Khi đó lược đồ α=(U,F) có Kα =M 2. Một số vấn đề về khoá Cho α=(U,F) ta cần quan tâm một số vấn đề sau: Bài toán 1: Cho K ⊆ U hỏi rằng K có phải là khoá hay không? Cách làm: Tính K+, nếu K+ ≠ U thì K không là khoá của lược đồ Trang 1
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm nếu K+ = U chứng tỏ K là một siêu khoá, để kiểm tra K có ph ải là khoá không ta l ấy m ọi t ập con thực sự của K, nếu tất cả các tập con thực s ự của K đều không là siêu khoá thì ch ứng tỏ K là khoá, nếu tồn tai một tập con thực sự của K là siêu khoá thì ch ứng t ỏ K không là khoá Bài toán 2: Tìm một khoá của lược đồ Cho một lược đồ α = (U, F), hãy tìm một khoá K. Phương pháp: b1) Trước hết chọn một siêu khoá K b2) Từ siêu khoá đó kiểm tra xem nó có phải là khoá không b3) Nếu K là khoá thì dừng thuật toán, ngựơc lại chuyển bước tiếp theo. b3) Nếu K chưa phải là khoá thì có K1 là t ập con thực s ự của và l ớn nh ất c ủa K và K 1 là siêu khoá, thay K bằng K1 và quay trở lại bước b2. Mô tả thuật toán (bằng ngôn ngữ tựa Pascal): Begin K:= R; For each A in K do if (K-A)+ = R then K:= K- A; end; Nhận xét: Thuật toán này cho ta tìm được một khóa của l ược đồ quan h ệ α. 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 khóa. Bài toán 3: T ìm giao của tất cả các khoá Kí hiệu α =(U, F) với F={Li  Ri , i=1,..n } Là tập mà mỗi phần tử của nó tham gia vào t ất cả các khoá c ủa l ược đ ồ hay I α là giao của tất cả các khoá của lược đồ. Kí hiệu Nα là tập mà mỗi phần tử của nó không tham gia vào b ất c ứ m ột khoá nào c ủa l ược đồ n  (Ri – Li) | ∀ Li  Ri ∈ F } Kí hiệu Sα ={ U \ i =1 n  (Ri – Li) | ∀ Li  Ri ∈ F} Khi đ ó: Iα =Sα = { U \ i =1 Bài toán 4: Cho lược đồ quan hệ α= (U, F) Hỏi rằng lược đồ có bao nhiêu khoá Phương pháp kiểm tra một lược đồ đã cho có một hay nhiều khoá: - Tính Iα - Nếu (Iα)+ =U thì lược đồ đã cho có duy nhất một khoá - Nếu (Iα)+ ≠ U thì lược đồ có nhiều khoá Trong ví dụ trên ta có Iα =AH do vậy ( Iα )+ ≠ U do vậy lược đồ đã cho có nhiều khoá. Bài toán 5: Cho lược đồ α = (U, F) Hãy tìm các khoá của lược đồ. Trang 2
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm Thuật toán: - Xác định Iα - Xác định N={ ∪ ( Ri -Li ) sao cho Li ∈ Iα } - Đặt N’=(Iα N)+ \ Iα ( N’⊆ Nα ) - Đặt B=U \N’ \ I α , khi đó B ∪ Iα là một siêu khoá, từ tập này ta bỏ đi các ph ần t ử đ ể thu đựơc một khoá II. MỘT SỐ LƯU Ý  Cần phân biệt các loại khoá, xác định khoá của lược đồ quan hệ. Kiểm tra m ột l ược đ ồ đã cho có một hay nhiều khóa? B/ BÀI TẬP MẪU Bài số 1: Cho lược đồ quan hệ: α=(U,F) V ới U=ABCDEGH F={AB  CDE, AC  BCG, BDG, ACHHE, CG  BDE } và K = ACGH Hỏi rằng K có là khoá của lược đồ hay không? K+= ACGH ∪ BCG ∪ HE ∪ BDE = U suy ra K là siêu khoá Các tập con thực sự lớn nhất của U là ACG, CGH, ACH, AGH dễ dàng ki ểm tra các t ập ACG có (ACH)+ = U vậy K không là khoá. Bài số 2: Cho lược đồ quan hệ α=(U, F) với U=ABCDEGHK F={ ADH→BC, GH→BE, D→CG, CH→K} Hãy tìm một khoá của lược đồ - Chọn siêu khoá K=ACDGH - loại A ta có (K-A)+ = (CDGH)+ = BCDEGHK ≠ U nên A không thể loai đựơc - loại C ta có (K-C)+ = (ADGH)+ = ABCDEGHK=U nên gán K:=K – {C}= ADGH - loại D ta có (K-D)+ = (AGH)+ =ABEGH ≠ U nên không loại được D - loại G ta có (K-G)+ = (ADH)+ = ABCDEGHK=U nên gán K=K- {G} = ADH - loại H ta có (K-H)+=(AD)+ =ACDG≠ U nên không loại được D Vậy khoá K=ADH Bài số 3: Hãy tìm giao của tấp cả các khoá của lược đồ α=(U, F) Với U=ABCDEGH F={AB  CDE, AC  BCG, BDG, ACHHE, CG  BDE } Iα = U \ ((CDE – AB) ∪ (BCG – AC) ∪ (G – BD) ∪ (HE – ACH) ∪ (BDE – CG) ) =U \ ( CDE ∪ BG ∪ G ∪ E ∪ BDE ) =U \ BCDEG=AH Bài số 4: Cho lược đồ quan hệ α = (U, F) với U=ABCDEGH, F={ ABC→ADH, ABG→AEH, AE→DG} Trang 3
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm Hãy tìm tất cả các khoá của lược đồ Iα =U \ ∪ (Ri -Li )=ABC N=∪ (Ri -Li )=DH ( víi Li ⊆ Iα ) N’=(Iα N)+ \ Iα =(ABCDH)+ \ ABC = DH ⊆ Nα B=U \ N \ Iα = ABCDEGH \ ABC \ DH =EG Do (Iα )+ ≠ U nên lược đồ đã cho có nhiều khoá, do vậy lược đồ này có hai khoá là Iα ∪ E =ABCE và Iα ∪ G= ABCG C/ BÀI TẬP TỰ GIẢI Bài tập 1: Xây dựng lược đồ quan hệ có các khoá là ADE, BCH, CG, AHE Bài tập 2: Cho lược đồ quan hệ α=(U, F) với U=ABCDEGHK F={ ADH→BC, GH→BE, D→CG, CH→K} Hãy tìm a) Giao của tất của các khoá b) Lược đồ đã cho có một hay nhiều khoá c) Hãy tìm tất của các khoá của lược đồ d) Một số các phần tử không khoá Bài tập 3: Tìm các thuộc tính khoá của lược đồ α=(U, F)với U=ABCDE F={ AB→C, AD→B, B→D } Hãy tìm các phần tử khoá của lược đồ trên Bài tập 4 Các mệnh đề trên mệnh đề nào đúng/ sai a) K⊆ U là một khoá khi và chỉ khi K→U b) K⊆ U là một khoá thì K→U c) Hai khoá bất kỳ là không giao nhau d) Hai khoá bất kỳ là không bao nhau e) Mọi lược đồ quan hệ đều có ít nhất một khoá f) bản thân U cũng có thể là một khoá g) tồn tại một lược đồ quan hệ không có khoá nào h) U không thể là khoá của lược đồ i) Hợp của hai khoá phân biệt là một khoá j) Hợp của hai khoá là một siêu khoá Bài tập 5: Cho lược đồ quan hệ (=(U, F) với U=ABCDEGH F={ ABC→DE, BCD→G, ABH→EG, CE→GH}. Hãy tìm một khóa của lược đồ Bài tập 6: Cho lược đồ quan hệ α=(U, F) với U=ABCDEGH F={CD→H, E→B, D→G, BH→E, CH→DG, C→A } a) Tìm giao của tất của các khoá b) Lược đồ có một hay nhiều khoá Trang 4
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm c) Tập ABD có phải là khoá của α không? vì sao ? d) Tập CH có phải là khoá của α không? vì sao ? e) Tính Z=(X+Y)+ ∩ (K+ -Y) trong đó X=CD , Y=CH , K là một siêu khoá bất kỳ nào đó của α Bài tập 7: Cho lược đồ quan hệ (=(U, F) với U=ABCD, F={ AD→BC, B→A, D→C} a. Tìm các khoá của lược đồ b. Cho biết C có phải là thuộc tính khoá hay không? Bài tập 8: Cho lược đồ quan hệ α=(U, F) với U=ABCDEGH, F={ DE→G, H→C, E→A, CG→H, DG→AE, D→B} Tìm giao của tất của các khoá a) Lược đồ có một hay nhiều khoá b) Tìm một khoá của lược đồ c) Tập BCE có phải là khoá của α không? vì sao ? d) Hãy thêm hoặc bớt một phụ thộc hàm trong F để lược đồ có duy nhất một khoá Bài tập 9: Cho lược đồ quan hệ α=(U, F) với U=ABCDEH, F={ BC→E, D→A, C→A, AE→D, BE→CH} Tìm một khoá K của lược đồ a) Ngoài khoá K lược đồ α còn có khoá nào khác không? Vì sao? b) Tập BCH có phải là khoá của α không? vì sao ? c) Tập BD có phải là khoá của α không? vì sao ? Bài tập 10: Cho lược đồ quan hệ α=(U, F) với U=ABCDE , F={ DE→A, B→C, E→AD} a) Tìm một khoá của lược đồ b) Tập BCE có phải là khoá của α không? vì sao ? c) Tập AD có phải là khoá của α không? vì sao ? d) Tập BD có phải là khoá của α không? vì sao ? e) Lược đồ có còn khoá nào nữa không? Vì sao? f) Tính Z=(X+ ∪ Y)+ ∩ (K+ -Y) với X=DE, Y=AD, K là một siêu khoá bất kỳ nào đó của α. Bài tập 11: Cho lược đồ quan hệ α=(U, F) với U=ABCDE , F={ AE→ C→ A→ B, D, BE} Tìm một khoá của lược đồ a) Tập BDE có phải là khoá của α không? vì sao ? b) Tập AC có phải là khoá của α không? vì sao ? c) Lược đồ có còn khoá nào nữa không? Vì sao? d) Tính Z=(X+ ∪ Y)+ ∩ K+ với X=AB, Y=AC, K là một siêu khoá bất kỳ nào đó của α Bài tập 12: Trang 5
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm Cho lược đồ quan hệ α=(U,F) với U=ABCDEG và tập phụ thộc hàm F={A→ C, B→DE, D→E, A→ED, AB→G} Hãy tìm khoá của lược đồ quan hệ Bài tập 13: Xác định khoá cuả các lược đồ quan hệ α =(U, F) với a) U=ABCEDH và F={AB→C, CD→E, AH→B, B→D, A→D} b) U=ABCDMNPQ F={AM→NB, BN→CM, A→P, D→M, PC→A, DQ→A} c) U=ABCDEGHIJ F={A→J, AE→H, H→E, DE→H, A→I, AB→C, CB→D, J→E} Bài tập 14: Cho lược đồ quan hệ α =(U, F) với U=ABCDEGHI và tập phụ thộc hàm F={AE→G, A→HI, G→E, DE→G, AG→C, BC→D, HI→E} Hãy tìm khoá các lược đồ. Bài tập 15: Cho lược đồ α= (U, F) có U = ABCDE và F = { AB → C, BD → CE, D → AC, A → DC, CE → A } Lược đồ có một hay nhiều khoá ? Hãy tìm một khoá của l ược đồ α Bài tập 16: Cho lược đồ α= (U, F) có U = ABCDE và F = { AB → C, BD → CE, D → AC, A → DC, CE → A } a. Hỏi rằng tập BDE có là khoá của lược đồ hay không b. Lược đồ có một hay nhiều khoá ? Bài tập 17: Xây dựng lược đồ α = (U, F) với U = ABCDEGHIK . Sao cho l ược đ ồ có ít nh ất 3 khoá và các thuộc tính A,B,C không tham gia vào bất kỳ một khoá nào . Bài tập 18: Cho lược đồ quan hệ α = (U, F) có U = ABCDEG và F = { A → BD, BC → DE, D → B, CD → GE, BE → A, G → B } a. Hỏi rằng tập CGE có là khoá của lược đồ hay không b. Lược đồ có một hay nhiều khoá ? c. Hãy tìm một khoá và giải thích. Bài tập 19: Cho lược đồ α = (U, F) có U = ABCDEG và F = { BC → DE, A → CD, CE → A, G → C, D → C, BD → GE, } a. Hỏi rằng tập BDE có là khoá của lược đồ hay không b. Lược đồ có một hay nhiều khoá ? c. Hãy tìm một khoá và giải thích. Bài tập 20: Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { AB → CDE , BD → CGE , DG → ACE, AD → CDEH, BCG → AEH } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Hãy tìm một khoá của lược đồ trên. iii. Liệu có thuộc tính nào không tham gia vào bất kỳ m ột khoá nào không ? Vì sao ? Bài tập 21: Trang 6
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { BDG → AEH , BC → ADE , AC → CDEH , AG → CDE, CG → BDE } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Hãy tìm một khoá của lược đồ trên. iii. Liệu có thuộc tính nào không tham gia vào bất kỳ m ột khoá nào không ? Vì sao ? Bài tập 22: Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { AB → CDE , BD → CGE , DG → ACE, AD → CDEH, BCG → AEH } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không ? Vì sao ? Bài tập 23: Cho U = ABCDEGH. Hãy xây dựng một lược đồ quan hệ α trên U thoả mãn các điều kiện sau : - Lược đồ α có ít nhất 4 khoá - Có hai thuộc tính C, D không tham gia vào bất kỳ một khoá nào - Hợp tất cả các khoá của lược đồ là tập lớn nhất . Hãy giải thích điều đó. Bài tập 24: Xây dựng lược đồ quan hệ α = (U, F) với U = ABCDEGHIK sao cho lược đ ồ có 3 khoá và giao của các khoá là DG và hai thuộc tính E,H không tham gia vào b ất kỳ m ột khoá nào . Bài tập 25: Cho lược đồ quan hệ α = (U,F) với U = ABCDEGHIK và F = { AEK → BEH , EH → BD , DG → BCD, ABCE → DE} i. Tập DEGH có phải là khoá của lược đồ đã cho hay không ? ii. Hãy tìm một khoá của lược đồ trên. iii. Hãy tìm tất cả các thuộc tính không tham gia vào bất kỳ một khoá nào. Bài tập 26: Cho lược đồ quan hệ α= (U,F) với U = ABCDEGHIK và F = { ACK → BCH , CH → BD , DG → BDE, ABCE → CD} i. Hãy tìm một khoá của lược đồ trên. ii. Tập CDGH có phải là khoá của lược đồ đã cho hay không ? iii. Hãy tìm tất cả các khoá còn lại Bài tập 27: Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { AB → CE , BCD → CH , DG → ACE, AD → CDH, BC → AEG } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Hãy tìm một khoá của lược đồ trên. ii. Tập BCDG có phải là khoá của lược đồ α đã cho hay không ? Bài tập 28: Cho lược đồ quan hệ α= (U,F) với U = ABCDEGHIK và Trang 7
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm F = { AEK → BEH , EH → BD , DG → BCD, ABCE → DE} i. Hãy tìm một khoá của lược đồ trên. ii. Tập DEGH có phải là khoá của lược đồ đã cho hay không ? b. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không ? Bài tập 29: Xây dựng lược đồ quan hệ α = (U, F) với U = ABCDEGH sao cho lược đồ có 3 khoá và giao của các khoá là CDE. Bài tập 30: Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { AB → CDE , BD → CG , DG → ACE, AD → CDH, BCE → AEH } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Hãy tìm một khoá của lược đồ trên. iv. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không ? Bài tập 31: Xây dựng lược đồ quan hệ α = (U, F) với U = ABCDEGH sao cho l ược đ ồ có 3 khoá và t ập thuộc tính không khoá là DH. Bài tập 32: Cho lược đồ quan hệ α = (U,F) với U = ABCDEGHIK và F = { ACK → BCH , CH → BD , DG → BDE, ABCE → CD} i. Hãy tìm một khoá của lược đồ trên. ii. Tập CDGH có phải là khoá của lược đồ đã cho hay không ? iii. Hãy tìm tất cả các khoá còn lại iv. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không ? Bài tập 33: Cho lược đồ quan hệ α = (U, F) với U = ABCDEGH và F = { AB → CE , BCD → CH , DG → ACE, AD → CDH, BC → AEG } i. Lược đồ đã cho có một hay nhiều khoá ? ii. Hãy tìm một khoá của lược đồ trên. ii. Tập BCDG có phải là khoá của lược đồ α đã cho hay không ? iii. Liệu có thuộc tính nào không tham gia vào bất kỳ m ột khoá nào không ? Bài tập 34: Cho lược đồ α = (U, F) có U = ABCDEGH và F = { AB → CE, BCD → CH, DG → ACE, AD → DCH, BC → AEG } a. Hãy tìm một khoá của lược đồ. b. Xây dựng một lược đồ quan hệ α có tập thuộc tính U đã cho ở trên sao cho thoả mãn 3 điều sau : 1. Lược đồ có it nhất ba khoá. 2. Hai khoá bất kỳ có giao khác trống. 3. Các thuộc tính B và H là các thuộc tính không khoá Bài tập 35:. a. Cho lược đồ α = (U, F) có U = ABCDEGH và F = { AB → CE, BCD → CH, DG → ACE, AD → DCH, BC → AEG } a. Hãy tìm một khoá của lược đồ. Trang 8
NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm b. Xây dựng một lược đồ quan hệ α có tập thuộc tính U đã cho ở trên sao cho thoả mãn 3 điều sau : 1. Lược đồ có it nhất ba khoá. 2. Hai khoá bất kỳ có giao khác trống. 3. Các thuộc tính B và H là các thuộc tính không khoá Hãy giải thích. Trang 9

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.