Tr c khi đi vào chi ti t chúng ta tìm hi u m t s khái ni m:ướ ế ể ộ ố ệ
- 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.ạ ậ ầ
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.ủ ượ ồ ệ
B c 1: ướ
- TN={S}, TG={CZ}
B c 2: ướ
- TG khác r ng nên qua b c 3ỗ ướ
B c 3: ướ
- t p con Xi c a t p trung gian X={0,C,Z,CZ} ghi chú 0: là r ngậ ủ ậ ỗ
B c 4: ướ
- S+=S Khác Q có nghĩa không có siêu khóa.
- SC+=CZS b ng v i Q nên siêu khóa SC.ằ ớ
- SZ+=CZ b ng v i Q nên Siêu khóa là CZằ ớ
- SCZ+= b ng v i Q nên Siêu khóa là CSZằ ớ
B c 5: ướ
- V y t p siêu khóa S={SC, CZ, CSZ} Vì SC ch a trong CSZ và CZ ch a trong CSZậ ậ ứ ứ
nên lo i b siêu khóa CSZ kh i t p siêu khóa.ạ ỏ ỏ ậ
- K t qu khóa c a l c đ quan h trên là SC và CZ. K={SC, CZ}ế ả ủ ượ ồ ệ
Thu t toán tìm m t khóa trên l c đ quan hậ ộ ượ ồ ệ
SUNDAY, 31. MAY 2009, 17:05:46
COSODULIEU
M c tiêu : cho m t l c đ U có các thu c tính {A1,A2,...An} và t p Ph thu c hàmụ ộ ượ ồ ộ ậ ụ ộ
F. hãy tìm m t khóa cho l c đ đó.ộ ượ ồ
Thu t toán:ậ
B c 1 :ướ
+ Gán K0=U+ (U+ là t p thu c tính c a U)ậ ộ ủ
B c 2 : ta có A là thu c tính c a U.ướ ộ ủ
+ Tính bao đóng c a (Ki-1\A)+ n u b ng U+ ((Ki-1\A)+ =U+) thì lo i b A ra kh i Kủ ế ằ ạ ỏ ỏ
t c là Ki =(Ki-1\A). n u (Ki-1\A)+ !=U+ thì Ki =Ki-1.ứ ế
L p l i b c trên n l n ặ ạ ướ ầ
B c n: k t qu K=Knướ ế ả
Ví d : cho U={A,B,C,D,E} và F={AB->C, AC->B, BC->DE} tìm m t khóa c a l cụ ộ ủ ượ
đ quan h r xác đ nh trên U và F ?ồ ệ ị
B c 1:ướ
+ K=U t c là K=ABCDEứ
B c 2:ướ
+ Tính Bao đóng c a (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta th y k t qu tính baoủ ấ ế ả
đóng không b ng U+ nên K=ABCDEằ
B c 3:ướ
+ Tính Bao đóng c a (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta th y k t qu tính baoủ ấ ế ả
đóng b ng U+ nên lo i B ra t p K ban đ u K=ACDEằ ạ ậ ầ
B c 4:ướ
+ Tính Bao đóng c a (K\C)+ nghĩa là tính (ADE)+ = ADE ta th y k t qu tính baoủ ấ ế ả
đóng Không b ng U+ nên không b C ra t p K ta có K=ACDEằ ỏ ậ
B c 5:ướ
+ Tính Bao đóng c a (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta th y k t qu tính baoủ ấ ế ả
đóng b ng U+ nên b D ra t p K ta có K=ACEằ ỏ ậ
B c 6:ướ
+ Tính Bao đóng c a (K\E)+ nghĩa là tính (AC)+ = ACBDE ta th y k t qu tính baoủ ấ ế ả
đóng b ng U+ nên b E ra t p K ta có K=AC ằ ỏ ậ
=>>K t qu Khóa là K=ACế ả
Thu t toán tìm ph t i thi u c a m t t p ph thu c hàmậ ủ ố ể ủ ộ ậ ụ ộ
1. Tách các ph thu c hàm sao cho v ph i ch còn m t thu c tính. (ví d : A->BCụ ộ ế ả ỉ ộ ộ ụ
thành A->B và A->C)
2. B các thu c tính d th a v trái. (ví d : cho F = {A → B, B → C, AB → D} cácỏ ộ ư ừ ở ế ụ
ph thu c hàm có v trái 1 thu c tính là đ y đ nên ta không xét, xét AB → D có B dụ ộ ế ộ ầ ủ ư
th a(b B) vì bao đóng c a A có ch a B. A+=ABC) (d hi u là chúng ta b thu c tínhừ ỏ ủ ứ ễ ể ỏ ộ
bên v trái, khi và ch khi bao đóng c a các thu c tính còn l i có ch a thu c tính đó)ế ỉ ủ ộ ạ ứ ộ
3. Lo i kh i F các ph thu c hàm d th a. (Các thu c tính v ph i c a PTH chạ ỏ ụ ộ ư ừ ộ ở ế ả ủ ỉ
xu t hi n di nh t 1 l n thì không th lo i b . Còn l i tính bao đóng c a t p thu c tínhấ ệ ấ ầ ể ạ ỏ ạ ủ ậ ộ
v trái n u có xu t hi n thu c tính v ph i thì có th lo i b thu c tính đó và đó làế ế ấ ệ ộ ế ả ể ạ ỏ ộ
PTH d th a.)ư ừ
Ví d : Cho l c đ quan h Q(A,B,C,D) và t p pth F={AB->CD, B->C, C->D} Tìmụ ượ ồ ệ ậ
ph t i thi u?ủ ố ể
1. Tách các ph thu c hàm sao cho v ph i ch còn m t thu c tính.ụ ộ ế ả ỉ ộ ộ
+ ta có F={AB->C, AB->D, B->C, C->D}
2. B các thu c tính d th a v trái. ỏ ộ ư ừ ở ế
+ B->C, C->D Không xét vì v trái ch có m t thu c tính.ế ỉ ộ ộ
+ xét AB->C : N u B A thì B+=BCD không ch a A nên không th B A. N u B Bế ỏ ứ ể ỏ ế ỏ
thì A+=A. không b đ c thu c tính nào. ỏ ượ ộ
+ xét AB->D : N u B A thì B+=BCD không ch a A nên không th B A. N u B Bế ỏ ứ ể ỏ ế ỏ
thì A+=A. không b đ c thu c tính nào.ỏ ượ ộ
3. Lo i kh i F các ph thu c hàm d th a.ạ ỏ ụ ộ ư ừ
+ xét AB->C : Tính AB+=ABCD = Q nên lo i b AB->Cạ ỏ
+ xét AB->D : tính AB+=ABCD = Q nên lo i b AB->Dạ ỏ
+ B->C : tính B+=B không th b .ể ỏ
+ C->D : tính C+=C không th b .ể ỏ
Ph t i thi u là Ftt = {B->C, C->D}ủ ố ể
Tìm bao đóng
Ví d : Cho l c đ quan h R(U, F)ụ ượ ồ ệ
V i U = ABCDE và F = { AB -->CD, E --> C, D -->CE, A -->E}. Tìm A+ớ
- Đ u tiên gán A+=Aầ
- Ti p theo xét xem có PTH nào A->X không? n u có b X vào A+, đây ta có A->Eế ế ỏ ở
nên A+=AE
- Ta th y E->C nên A+=ACEấ
- Cu i cùng ta có A+=ACEố