Download miễn phí Bài tập về Khoá
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à K1 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):
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-02-11-bai_tap_ve_khoa.8aVCBNf0tD.swf /tai-lieu/de-tai-ung-dung-tren-liketly-58440/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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
1. Họ Sperner
Nếu gọi Ka là tập tất c các khoá của lược đồ a=(U,F), như vậy mỗi phần tử của Ka 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 Ka 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ệ 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 hay KàU \ K
Đị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 hay KàU \ K
Định nghĩa: Cho lược đồ quan hệ a=(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ệ a=(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 Ka 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ệ a=(U,F) sao cho Ka =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 đồ a=(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 đồ a=(U,F) có Ka =M
2. Một số vấn đề về khoá
Cho a=(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 đồ
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 đồ a = (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ệ a. 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 a =(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 Ia là giao của tất cả các khoá của lược đồ.
Kí hiệu Na 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 đồ
Kí hiệu Sa ={ U \ (Ri – Li) | " Li à Ri Î F }
Khi đ ó: Ia =Sa = { U \ (Ri – Li) | " Li à Ri Î F}
Bài toán 4:
Cho lược đồ quan hệ a= (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 Ia
- Nếu (Ia)+ =U thì lược đồ đã cho có duy nhất một khoá
- Nếu (Ia)+ ¹ U thì lược đồ có nhiều khoá
Trong ví dụ trên ta có Ia =AH do vậy ( Ia )+ ¹ U do vậy lược đồ đã cho có nhiều khoá.
Bài toán 5:
Cho lược đồ a = (U, F)
Hãy tìm các khoá của lược đồ.
Thuật toán:
- Xác định Ia
- Xác định N={ È ( Ri -Li ) sao cho Li Î Ia }
- Đặt N’=(Ia N)+ \ Ia ( N’ÍNa )
- Đặt B=U \N’ \ Ia , khi đó B È Ia 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ệ: a=(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ệ a=(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 đồ a=(U, F)
Với U=ABCDEGH
F={AB à CDE, AC à BCG, BDàG, ACHàHE, CG à BDE }
Ia = 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ệ a = (U, F) với
U=ABCDEGH, F={ ABC®ADH, ABG®AEH, AE®DG}
Hãy tìm tất cả các khoá của lược đồ
Ia =U \ È (Ri -Li )=ABC
N=È (Ri -Li )=DH ( víi Li ÍIa )
N’=(Ia N)+ \ Ia =(ABCDH)+ \ ABC = DH Í Na
B=U \ N \ Ia = ABCDEGH \ ABC \ DH =EG
Do (Ia )+ ¹ U nên lược đồ đã cho có nhiều khoá, do vậy lược đồ này có hai khoá là Ia È E =ABCE và Ia È 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ệ a=(U, F) với
U=ABCDEGHK
F={ ADH®BC, GH®BE, D®CG, CH®K}
Hãy tìm
Giao của tất của các khoá
Lược đồ đã cho có một hay nhiều khoá
Hãy tìm tất của các khoá của lược đồ
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 đồ a=(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ệ a=(U, F) với
U=ABCDEGH
F={CD®H, E®B, D®G, BH®E, CH®DG, C®A }
Tìm giao của tất của các khoá
Lược đồ có một hay nhiều khoá
Tập ABD có phải là khoá của a không? vì sao ?
Tập CH có phải là khoá của a không? vì sao ?
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 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ệ a=(U, F...
