Cơ sở dữ liệu quan hệ - Chương V: Phụ thuộc hàm - Nguyễn Thị Tâm

CHƯƠNG V: PHỤ THUỘC HÀM 07/11/2012 11:02 AM 2 Nội dung chi tiết 1. Phụ thuộc hàm 2. Hệ tiên đề Amstrong 3. Bao đóng phụ thuộc hàm, tập thuộc tính 4. Bài toán thành viên 5. Tập PTH tương đương 6. Tập PTH tối thiểu – Phủ tối thiểu 7. Khóa của quan hệ 07/11/2012 11:02 AM 3 I. Phụ thuộc hàm Định nghĩa: Cho R(U), với R là quan hệ và U là tập thuộc tính. Cho X,Y ⊆U, phụ thuộc hàm X → Y (đọc là X xác định Y) được định nghĩa là: ∀ t, t’ ∈ R nếu t.X = t’.X thì t.Y = t’.Y (Có nghĩa là: Nếu hai bộ có cùng trị X thì có cùng trị Y Cách đọc: X xác định Y hay Y phụ thuộc hàm vào X -X gọi là vế trái của PTH, Y là vế phải của PTH Phụ thuộc hàm thường được ký hiệu là FD hay F (Functional Dependencies) 07/11/2012 11:02 AM 4 Ví dụ 1:  Trong quan hệ SV(MaSV,Ten,Diachi,Ngaysinh), mỗi thuộc tính Ten, Diachi, Ngaysinh đều phụ thuộc hàm (pth) vào thuộc tính MaSV.  Mỗi giá trị MaSV xác định duy nhất một giá trị tương ứng đối với từng thuộc tính đó. Khi đó, có thể viết : - MaSV DIACHI - MaSV TEN - MaSV NGAYSINH 07/11/2012 11:02 AM 5  Ví dụ 2: Cho quan hệ R(A,B,C,D) như sau:  Cho biết các phụ thuộc hàm nào liệt kê dưới đây được thoả trong quan hệ R ở trên? - f1: A A - f2: A B - f3: A C - f4: AC C - f5: A D - f6: D A R (A B C D) a 1 x 2 a 1 y 2 b 2 x 1 b 2 y 1 07/11/2012 11:02 AM 6 Nhận xét: - Phụ thuộc hàm là công cụ để biểu diễn một cách hình thức các ràng buộc. - PTH được ứng dụng giải quyết các bài toán tìm khoá, tìm phủ tối thiểu và chuẩn hoá các quan hệ trong cơ sở dữ liệu. - Nếu X Y thì không thể nói gì về Y X. - Ví dụ:  Có MSV Tên thì không thể khắng định Tên MSV vì có thể có nhiều sinh viên cùng tên  Có MSV Ngaysinh thì không thể khắng định Ngaysinh MSV vì có thể có nhiều sinh viên sinh cùng ngày 07/11/2012 11:02 AM 7  Biểu diễn phụ thuộc hàm: - Dùng đường nối mũi tên từ các thuộc tính vế trái đến các thuộc tính vế phải của tất cả các phụ thuộc hàm  Ví dụ: MƯỢN(Sốthẻ, Mãsốsách, Tênngườimượn, Tênsách, Ngàymượn) - Với các phụ thuộc hàm: FD1: Sốthẻ Tênngườimượn FD2: Mãsốsách Tênsách FD3: Sốthẻ, Mãsốsách Ngàymượn  Có sơ đồ phụ thuộc hàm như sau: MƯỢN Sốthẻ Mã số sách Tên người mượn Tên sách Ngàymượn FD3 FD1 FD2 07/11/2012 11:02 AM 8 II. Hệ tiên đề Amstrong  Năm 1974, Amstrong đưa ra hệ luật dẫn hay các tính chất của phụ thuộc hàm, gọi là hệ tiên đề Amstrong  các nguyên tắc biến đổi của pth  Định nghĩa: - F là tập pth trên quan hệ R(U) và A B là một pth với A, B U. Nói rằng, pth A B được suy diễn logic từ F nếu với mỗi quan hệ r xác định trên R thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A B.  Ví dụ: - Tập phụ thuộc hàm F = { A B, B C} - Ta có phụ thuộc hàm A C là phụ thuộc hàm được suy dẫn từ tập F 07/11/2012 11:02 AM 9 * Hệ tiên đề Amstrong:  Cho X, Y, Z, W U . Ký hiệu: XY = X Y. Ta có các luật sau : 1. Luật phản xạ: Nếu Y X thì X Y VD: ABC BC 2. Luật bổ sung - tăng trưởng: Nếu X Y thì XZ YZ VD: Nếu C D thì ABC ABD 3. Luật bắc cầu: Nếu X Y và Y Z thì X Z VD: Nếu có AB C, C EG thì AB EG 4. Luật hợp: Nếu X Y và X Z thì X YZ VD: Nếu AB CD và AB EF thì AB CDEF 5. Luật tách: Nếu X Y và Z Y thì X Z VD: Nếu AB CDEF thì AB CD và AB EF 6. Luật tựa bắc cầu: Nếu X Y và WY Z thì XW Z VD: Nếu AB EF và DEF G thì ABD G 07/11/2012 11:02 AM 10  Ví dụ 1: Cho R = ABC và tập F = { AB C , C A }. Áp dụng hệ tiên đề Amstrong CMR: BC ABC 07/11/2012 11:02 AM 11  Ví dụ 2: Cho lược đồ quan hệ R (A, B, C, D, E, G, H) và tập phụ thuộc hàm F = {BD, ABC, CDE, ECGH, GA}. Áp dụng hệ tiên đề Amstrong để tìm chuỗi suy diễn cho: AB  E và AB G Thực hiện: 1. AB C (gt) 2. AB  BC (tăng cường thêm B) 3. B  D (gt) 4. BC  DC (t/c thêm C) 5. CD  E (gt) 6. BC  E ( bắc cầu 4 và 5) 7. AB  E (bắc cầu 2 và 6) 8. AB  EC (hợp 1 và 7) 9. EC  GH (gt) 10. AB  GH ( bắc cầu 8 và 9) 11. AB  G (tách) 07/11/2012 11:02 AM 12  Ví dụ 3: Cho R= {A, B, C, E, F } Và F= { AB C, C B , ABC  E, F A}. Áp dụng hệ tiên đề Amstrong. CMR: FB  E Thực hiện: 1. F  A ( gt) 2. FB  AB ( tăng cường) 3. AB  C (gt) 4. ABC  C (tc) 5. ABC  E (gt) 6. ABC  EC ( hợp 4 và 5) 7. AB  E ( tách 6) 8. FB  E ( bắc cầu 2 và 7) 07/11/2012 11:02 AM 13  Ví dụ 4: - Hãy dùng hệ tiên đề Armstrong để chứng minh: - Nếu X Y và U V thì XU YV  Chứng Minh: 1. Từ X Y ( gt) 2. Có XU YU, (tăng trưởng U vào (1) ) 3. Từ U V (gt) 4. Có YU YV (tăng trưởng Y vào (3) 5. Có XU YV ( bắc cầu (2) và (4) ) 07/11/2012 11:02 AM 14 III. Bao đóng 1. Các khái niệm cơ bản  Gọi F là tập các pth trên tập thuộc tính U, X U .  Bao đóng của phụ thuộc hàm: là tập tất cả các PTH được suy diễn logic từ tập pth F, kí hiệu là F+ Nhận xét: Nếu F+ = F thì F là họ đầy đủ của các pth  Bao đóng của tập thuộc tính X: là tất cả các thuộc tính A mà phụ thuộc hàm X A có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. Kí hiệu: X+ X+ = { A U | X A F+ }  Nhận xét: - X X+ - X Y F+  Y X+ => Có nghĩa là: X Y được suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y X+ 07/11/2012 11:02 AM 15 07/11/2012 11:02 AM 16 2. Thuật toán tìm bao đóng của tập thuộc tính Cho X U là tập thuộc tính => Tìm X+ Thuật toán CLOSURE(X,F). -Input: Tập thuộc tính X và tập phụ thuộc hàm F -Output: Tìm bao đóng X+ của F -Thực hiện: Lần lượt tính các X0, X1, X2, , theo các bước sau:  Bước 1: Đặt X0 = X  Bước 2: Lần lượt xét các phụ thuộc hàm của F nếu tồn tại pth Y Z F mà Y Xi thì Xi+1 = Xi {Z}, ngược lại, đặt Xi+1 = Xi  Bước 3: Nếu ở bước 2 mà không tính được Xi+1 thì Xi chính là bao đóng của tập thuộc tính X, ngược lại lặp lại bước 2. 07/11/2012 11:02 AM 17 Ví dụ 1:  Cho R = (A, B, C, D, E, G) và pth F = {AB C, C A, BC D, ACD B, D EG, BE C, CG BD, CE AG}. Tính: (BD)+ 07/11/2012 11:02 AM 18 Ví dụ 2:  Cho R = (A,B,C,D,E,H) và  F = { AB → C, BC → AD, D → E, CE → B}  Tính (AB)+? 07/11/2012 11:02 AM 19  Ví dụ 3: U = (ABCDEGH) và tập pth F ={A  D, AB  DE, CE G, EH}. - Tính bao đóng X+ với X= (AB )  Ví dụ 4: Cho R = { A, B, C, D, E} Và F = {A  C, B C, CD, DE  C, CE A} - Tính bao đóng X+ với X = ( AE) 07/11/2012 11:02 AM 20 Bài tập áp dụng:  Cho LĐQH p = (U,F) với U = ABCDE,  F = { A C, BC D, D E, E A }. Tính: - (AB)+ - (BD)+ - (D)+ - Kiểm tra xem CE->A; DE->A có là thành viên của F 07/11/2012 11:02 AM 21 Ví dụ: VD: Cho R(ABCDEG) F = { AB C (f1) D EG (f2) C A (f3) BE C (f4) BC D (f5) CG BD (f6) ADC B (f7) CE AG (f8) } Cho X= BD. Tính ( BD)+F 07/11/2012 11:02 AM 22 3. Bài toán thành viên  Là bài toán để xác định một phụ thuộc hàm bất kỳ có là thành viên của tập phụ thuộc hàm F đã cho  Định nghĩa: X Y là thành viên của F nếu X Y F+  Thuật toán: - Bước 1: Tính X+ - Bước 2: So sánh X+ với Y nếu Y X+ thì khẳng định X Y là thành viên của tập phụ thuộc hàm F 07/11/2012 11:02 AM 23 Ví dụ 1:  Cho F = { AB E, BE I, E C, CI D } - Chứng minh AB CD suy được từ F.  Tính (AB)+ = ABEICD => (AB)+ chứa CD - Vậy AB CD được suy từ F 07/11/2012 11:02 AM 24  Ví dụ 2: Cho R= { A, B, E, I, G, H} và F= { AB  C, B D, CDE, CE  GH, G A} - Chứng minh rằng: AB  G  Ví dụ 3:Cho U= (ABEGHI) và pth F = {AB  E, AG I, BEI, E  G, GI H} - Chứng minh rằng nếu quan hệ r xác định trên W thoả F thì cũng thoả AB  GH 07/11/2012 11:02 AM 25 Ví dụ 4:  Cho R(ABCDE) và tập PTH F  F = { A CD; C E; D BC }  Yêu cầu: Xác định - A B có là thành viên của F - D E có là thành viên của F - B D có là thành viên của F 07/11/2012 11:02 AM 26  Chú ý: - có thể áp dụng hệ tiên đề Amstrong để kiểm tra một pth có là thành viên của F hay không bằng cách áp dụng lần lượt các luật để suy ra pth cần chứng minh 07/11/2012 11:02 AM 27  Ví dụ 1: Cho F = { AB E, BE I, E C, CI D } - Chứng minh AB CD suy được từ F bằng cách áp dụng các luật của hệ tiên đề Amstrong.  1. AB --> E, Giải thiết  2. E --> C, Giả thiết  3. AB --> C, Bắc cầu từ (1) và (2)  4. AB --> BE, Tăng cường (1) bởi B  5. BE --> I, Giả thiết  6. AB --> I, Bắc cầu (4) và (5)  7. ABC --> CI, Tăng cường (6) bởi C  8. AB --> ABC, Tăng cường (3) bởi AB 07/11/2012 11:02 AM 28  9. AB --> CI, bắc cầu (7) và (8)  10. CI --> D, Giả thiết  11. AB --> D, Bắc cầu (9) và (10)  12. ABC --> CD, Tăng cường (11) bởi C  13. AB --> CD, Bắc cầu (8) và (12) 07/11/2012 11:02 AM 29 IV. Tập phụ thuộc hàm tương đương  Hai tập pth F và G được gọi là tương đương nếu: - mọi pth của F đều có thể suy được từ G - mọi pth của G đều có thể suy được từ F có nghĩa là F+ = G+  Khi đó ta nói F phủ G (hay G phủ F). Kí hiệu : F G  Thuật toán kiểm tra sự tương đương của 2 tập PTH - F phủ G: X Y G, tính X+ từ F, sau đó kiểm tra xem Y X+ - G phủ F: X Y F, tính X+ từ G, sau đó kiểm tra xem Y X+ 07/11/2012 11:02 AM 30  Ví dụ 1: Xét hai tập phụ thuộc hàm F = { A C, AC D, E AD, E H } G = { A CD, E AH } CMR: F và G là tương đương với nhau  Chứng minh F phủ G: Tìm bao đóng các vế trái của các phụ thuộc hàm trong G, ta có: {A}+ = { A, C, D }; {E}+ = {E, A,D,H,C} - Các bao đóng này chứa các vế phải tương ứng. Suy ra F phủ G.  Chứng minh G phủ F: Tìm bao đóng của các vế trái của các phụ thuộc hàm trong F theo G. Ta có {A}+ ={A,C,D}, {AC}+ = { A,C,D}, {E}+ = {E,A,H,C,D}, - Các bao đóng này chứa các vế phải tương ứng. Suy ra G phủ F. Vậy: G tương đương với F. 07/11/2012 11:02 AM 31  Ví dụ 2: Cho lược đồ Q = ABCDE và hai tập PTH:  F={A BC, A D, CD E} và G={A BCE, A ABD, CD E}  Hỏi: - F có tương đương với G không - F có tương đương với G’ = { A BCDE } không 07/11/2012 11:02 AM 32 VI. Tập PTH tối thiểu - Phủ tối thiểu Định nghĩa: Ta nói tập pth F là tối thiểu nếu: -Vế phải của các pth trong F chỉ có 1 thuộc tính  không có thuộc tính ở vế phải dư thừa -Không tồn tại X A trong F và một tập con thực sự Z của X sao cho F\{X A} {Z A} tương đương với F  không có thuộc tính ở vế trái dư thừa -Không tồn tại X A trong F sao cho F\{X A} tương đương với F  không có phụ thuộc hàm dư thừa Nhận xét: -Tất cả các tập PTH đều có PTH tối thiểu tương đương với nó -Có thể có nhiều phủ tối thiểu 07/11/2012 11:02 AM 33 1. PTH có vế phải 1 thuộc tính  Mỗi tập PTH F luôn tương đương với tập PTH G trong đó các PTH của G đều có vế phải là một thuộc tính.  Ví dụ: 07/11/2012 11:02 AM 34 2. 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 các PTH có vế trái dư thừa  PTH có vế trái dư thừa:  Ví dụ: 07/11/2012 11:02 AM 35 * Thuật toán loại khỏi F các PTH có vế trái dư thừa  Input: Tập pth F  Output: Tập pth F không có pth có vế trái dư thừa  Thuật toán - Bước 1: Với mỗi pth X Y của F thì thực hiện bước 2 - Bước 2: Với mỗi A X  Nếu A Y F+ thì thay X Y bằng A Y  Lặp lại bước 2 đến khi vế trái X không dư thừa. 07/11/2012 11:02 AM 36 Ví dụ 1  Cho PTH  Xét PTH  Như vậy: - B là dư thừa trong PTH AB D - Trong F thay AB D bằng A D Kết quả: F={A BC, B C, A D} 07/11/2012 11:02 AM 37  Ví dụ 2: Cho F = { AB -> CD, B -> C, C -> D} - Kiểm tra xem F có chứa pth có vế trái dư thừa 07/11/2012 11:02 AM 38 3. Tập PTH không dư thừa  F là tập PTH không dư thừa nếu không tồn tại  Thuật toán loại khỏi F các PTH dư thừa - Input: Tập PTH F - Output: Tập F không có PTH dư thừa - Thuật toán:  Bước 1: Với mỗi PTH X Y trong F  Bước 2: Nếu X Y là thành viên của F – {X Y} thì loại X Y khỏi F  Bước 3: Lặp lại bước 2 cho đến khi hết các PTH cần xét 07/11/2012 11:02 AM 39 Ví dụ 1:  Cho F = {A BC, B D, AB D}. Tìm Tập pth không dư thừa 07/11/2012 11:02 AM 40 4. Thuật toán tìm phủ tối thiểu  Input: Tập PTH F  Output: Phủ tối thiểu của F  Thuật toán - Bước 1: Đưa tất cả các PTH trong F về dạng PTH vế phải chỉ có 1 thuộc tính - Bước 2: Loại khỏi F các PTH có vế trái dư thừa - Bước 3: Loại khỏi F các PTH dư thừa  Nhận xét: - Thuật toán luôn tìm được ít nhất 1 phủ tối thiểu. - Nếu trật tự loại các PTH trong F khác nhau có thể có các phủ tối thiểu khác nhau. 07/11/2012 11:02 AM 41 * Các bước thực hiện:  Bước 1: Đặt G:=F  Bước 2: Tách các pth có vế phải nhiều thuộc tính bằng các pth có vế phải chỉ có một thuộc tính - Thay thế tất cả các pth X {A1, A2, , An} trong G bằng n pth con: X A1, X A2, , X An  Bước 3: xóa lần lượt các thuộc tính trong vế trái của pth mà vế trái có nhiều thuộc tính  loại bỏ thuộc tính dư thừa ở vế trái - Với mỗi pth X A trong G, với mỗi thuộc tính B trong X nếu ((G-{X A}) {(A-{B}) A}) là tương đương với G, thì thay thế A A bằng (X-{B}) A trong G  Bước 4: loại bỏ pth dư thừa - Với mỗi pth X A trong G, nếu (G-{X A}) tương đương với G, thì loại bỏ pth X A ra khỏi G (loại bỏ phụ thuộc hàm dư thừa) 07/11/2012 11:02 AM 42 Ví dụ 1  Cho F={AB CD, B C, C D}. Tìm tập pth tối thiểu  Loại PTH có vế trái dư thừa: - Xét AB CD, giả sử dư A cần CM B CD là thành viên của F: B+={BCD} => đúng dư A. - Nên F = {B CD; B C; C D}  Đưa về dạng PTH có vế phải 1 thuộc tính F = {B C; B D; C D}  Loại khỏi F các PTH dư thừa - Dễ thấy B D là dư thừa Vậy phủ tối t hiểu của F = {B C; C D} 07/11/2012 11:02 AM 43 Ví dụ 2:  Cho tập thuộc tính R = {PCHART} và tập phụ thuộc hàm F như sau: - F = { P → CHART, CH → PART, C → T, A → R }  Tìm phủ tối thiểu của tập pth 07/11/2012 11:02 AM 44 Ví dụ 3  Tìm phủ tối thiểu cho tập phụ thuộc hàm: {A B, A C, B A, B C, C A, C B} Áp dụng thuật toán trên, chúng ta có thể tìm được các phủ tối thiểu sau: - Do A B và B C nên A C là thừa. - Do C B và B A nên C A là thừa.  Bỏ những phụ thuộc hàm thừa đi, ta có {A B, B A, B C, C B} là một phủ tối thiểu. - Do A B và B C nên A C là thừa. - Do có B C và C A nên B A là thừa. - Do có C A và A B nên C B là thừa.  Bỏ những phụ thuộc hàm thừa đi, ta nhận được một phủ tối thiểu khác là {A B, B C, C A} 07/11/2012 11:02 AM 45 Bài tập:  Bài 1: - Cho G = { AB C, A B, B A}. - F = {AB F; A CD; B E} - Tìm phủ tối thiểu của F,G.  Bài 2: - Cho F = { A C, BD E, B D, B E, C AD } - Tìm phủ tối thiểu của F 07/11/2012 11:02 AM 46 VII. Khóa của quan hệ 1. Định nghĩa: - Cho R(A1, ,An) là lược đồ quan hệ; - Tập các thuộc tính U = { A1, A2, .. , An} - Tập các pth F= { f1, f2, .. ,fn} xác định trên R. - K U là khoá của R nếu thoả mãn hai điều kiện sau : (1): K U (2): Không tồn tại K' K mà K' U 07/11/2012 11:02 AM 47  Thông thường có nhiều hơn một khóa tối thiểu trong một lược đồ quan hệ  Ví dụ: R = ABC, F = { AB C, C A }. - AB là một khóa tối thiểu vì: AB ABC thuộc F+ nhưng A ABC và B ABC không thuộc F+ - BC là một khóa tối thiểu vì: BC ABC thuộc F+ nhưng C ABC và B ABC không thuộc F+ 07/11/2012 11:02 AM 48  Thuật toán tìm siêu khóa: - Cho lược đồ quan hệ R = (U,F). Để kiểm tra X U là siêu khóa, thực hiện:  Tính X+  Kiểm tra nếu X+ = U (X+ chứa tất cả các thuộc tính của quan hệ) thì X là siêu khóa  ngược lại nếu X+ U thì X không là siêu khóa 07/11/2012 11:02 AM 49  Ví dụ 1: Cho quan hệ R = (A, B, C, G, H, I) và tập PTH F = {A B, A C, CG H, CG I, B H},  Kiểm tra AG là siêu khóa của R? - Dùng thuật toán tính bao đóng (AG)+. - Nếu (AG)+ chứa tất cả thuộc tính của R thì AG là siêu khóa của R. 07/11/2012 11:02 AM 50 2. Thuật toán tìm khóa  Input: - Lược đồ quan hệ R(A1,A2,An) - Tập thuộc tính U {A1,A2,An} - Tập PTH F  Output: Khóa của quan hệ R  Ý tưởng: Bắt đầu từ tập U vì U+ = U. Ta bớt dần các phần tử của U để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U.  Các bước: - Bước 1: Gán K = U - Bước 2: Loại khỏi K lần lượt từng thuộc tính A mà ( K\A)+ =U - Lặp lại bước 2 đến khi không loại khỏi K được nữa  Nhận xét: Thuật toán trên chỉ tìm được một khoá trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta thay đổi trật tự loại bỏ các phần tử của K. 07/11/2012 11:02 AM 51 Ví dụ 1:  cho R = { A,B,C,D,E,G,H,I} và  F= { AC → B, BI → ACD, ABC → D , H→ I , ACE → BCG , CG → AE }  Tìm khóa ? (1) 07/11/2012 11:02 AM 53 Ví dụ 2:  Cho LĐQH r( R) với R = ABCDEF và tập PTH - F = {AB C, C D , AD  E, F A} Tìm khóa của lược đồ quan hệ 07/11/2012 11:07 AM 54 3. Thuật toán tìm khóa cải tiến  Input: - Lược đồ quan hệ R(A1,A2,An) - Tập thuộc tính U {A1,A2,An} - Tập PTH F  Output: Khóa của quan hệ R  Ý tưởng: Bắt đầu từ tập Left(U) (tập các thuộc tính vế trái) và các thuộc tính không xuất hiện ở cả hai vế  Các bước: - Bước 1: Gán K = Left(U) U (U\(Left(U) U Right(U))) - Bước 2: Loại khỏi K phần tử A mà ( K\A)+ =U  Nhận xét: Thuật toán nhanh hơn do số phần tử cần xét ít hơn. 07/11/2012 11:02 AM 55 Ví dụ 1:  Cho LĐQH r( R) với R = ABCD và tập  PTH F = {AB → C, B → D, D → B}  Tìm khóa của lược đồ quan hệ 07/11/2012 11:02 AM 56 * Thuật toán tìm tất cả các khóa  Một số khái niệm cơ bản: - Tập thuộc tính nguồn (TN): bao gồm các thuộc tính chỉ xuất hiện ở vế trái, không xuất hiện ở vế phải của pth và các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth. - Tập thuộc tính đích (TĐ) : bao gồm các thuộc tính chỉ xuất hiện ở vế phải không xuất hiện ở vế trái của pth. - Tập thuộc tính trung gian (TG): Chứa thuộc tính ở vế trái lẫn vế phải của pth.  Thuật toán: - Bước 1 Tạo tập nguồn TN và tập trung gian TG - Bước 2: Nếu TG=0(rỗng) thì K=TN, kết thúc. ngược lại qua bước 3. - Bước 3: tìm tất cả tập con Xi của tập trung gian. - Bước 4: tìm siêu khóa Si bằng cách với mọi Xi, nếu (TN U Xi) +=Q+ thì Si = TN U {Xi} - Bước 5:  tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu  với mọi Si, Sj thuộc S nếu Si chứa trong Sj thì loại bỏ tập Sj ra khỏi siêu khóa (VD: Si=AB, Sj=ABC thì loại bỏ Sj ra khỏi tập siêu khóa) S còn lại chính là tập khóa cần tìm. 07/11/2012 11:02 AM 57 Ví dụ  Cho lược đồ quan hệ Q={CSZ} tập phụ thuộc hàm F={CS → Z; Z → C} tìm tất cả các khóa của lược đồ quan hệ trên. Câu 1: Cho lược đồ quan hệ: = U={A,B,C,D,E,G,H} F={BH->CA, H->BG, GH->AD, DH->CG } Tìm bao đóng H+ Loại bỏ các thuộc tính dư thừa ở vế trái Hãy tìm tất cả các khóa của lược đồ?  Câu 2: Cho các quan hệ:  SinhVien(MaSV, HotenSV, Ngaysinh, Gioitinh, Quequan)  DeTai(MaDT, TenDT, ChuNhiemDT, Kinhphi)  ThucTap(MaDT, MaSV, NoiThucTap, KetQua)  Hãy dùng các phép toán đại số quan hệ để thực hiện các yêu cầu sau:  Cho biết danh sách sinh viên làm đề tài có tên đề tài là X  Cho biết danh sách các chủ nhiệm đề tài có sinh viên đạt kết quả tốt (KetQua >=8)  Cho biết số đề tài của mỗi chủ nhiệm 07/11/2012 11:02 AM 58