Giaùo trình CÔ SÔÛ DÖÕ lieäu trang
IIIKHOÙA CUÛA LÖÔÏC ÑOÀ QUAN HEÄ (Key)
tải về 1.89 Mb.
|
- Điều hướng trang này:
- 2Thuaät toaùn tìm taát caû khoùa
IIIKHOÙA CUÛA LÖÔÏC ÑOÀ QUAN HEÄ (Key)1Ñònh NghóaQ(A1,A2,…,An)laø löôïc ñoà quan heä. Q+ laø taäp thuoäc tính cuûa Q. F laø taäp phuï thuoäc haøm treân Q. K laø taäp con cuûa Q+. Noùi raèng K laø moät khoùa cuûa Q neáu:
Taäp thuoäc tính S ñöôïc goïi laø sieâu khoùa neáu S K Thuoäc tính A ñöôïc goïi laø thuoäc tính khoùa neáu AK vôùi K laø khoùa baát kyø cuûa Q. Ngöôïc laïi A ñöôïc goïi laø thuoäc tính khoâng khoùa.
(Khi thieát keá moät heä thoáng thoâng tin, thì vieäc laäp löôïc ñoà cô sôû döõ lieäu ñaït ñeán moät tieâu chuaån naøo ñoù laø moät vieäc laøm quan troïng. Vieäc xaùc ñònh chuaån cho moät löôïc ñoà quan heä coù lieân quan maät thieát vôùi thuaät toaùn tìm khoùa). Thuaät toaùn tìm moät khoùa cuûa moät löôïc ñoà quan heä Q Böôùc 1: gaùn K = Q+ Böôùc 2: A laø moät thuoäc tính cuûa K, ñaët K’ = K A. Neáu K’+= Q+ thì gaùn K = K' thöïc hieän laïi böôùc 2 Neáu muoán tìm caùc khoùa khaùc (neáu coù) cuûa löôïc ñoà quan heä, ta coù theå thay ñoåi thöù töï loaïi boû caùc phaàn töû cuûa K. Ví duï 7: Q(A,B,C,D,E,G,H,I)F={AC B;BI ACD;ABCD;HI;ACEBCG;CGAE} Tìm K Laàn löôït loaïi caùc thuoäc tính trong K theo thöù töï sau: A, B, D, E, I Ta ñöôïc moät khoùa laø cuûa löôïc ñoà quan heä laø {C,G,H} (Löu yù laø thuaät toaùn naøy chæ neân söû duïng trong tröôøng hôïp chæ caàn tìm moät khoùa).
iThuaät toaùn cô baûnBöôùc 1: Xaùc ñònh taát caû caùc taäp con khaùc roãng cuûa Q+. Keát quaû tìm ñöôïc giaû söû laø caùc taäp thuoäc tính X1, X2, …,X2n-1 Böôùc 2: Tìm bao ñoùng cuûa caùc Xi Böôùc 3: Sieâu khoùa laø caùc Xi coù bao ñoùng ñuùng baèng Q+. Giaû söû ta ñaõ coù caùc sieâu khoùa laø S = {S1,S2,…,Sm} Böôùc 4: Xaây döïng taäp chöùa taát caû caùc khoùa cuûa Q töø taäp S baèng caùch xeùt moïi Si, Sj con cuûa S (i j), neáu Si Sj thì ta loaïi Sj (i,j=1..n), keát quaû coøn laïi cuûa S chính laø taäp taát caû caùc khoùa caàn tìm. Ví duï 8: Tìm taát caû caùc khoùa cuûa löôïc ñoà quan heä vaø taäp phuï thuoäc haøm nhö sau: Q(C,S,Z); F = {f1:CS Z; f2:Z C}
Vaäy löôïc ñoà quan heä Q coù hai khoùa laø: {C,S} vaø {S,Z} Thuaät toaùn treân thì deã hieåu, deã caøi ñaët, tuy nhieân neáu vôùi n khaù lôùn thì pheùp duyeät ñeå tìm ra taäp taát caû caùc taäp con cuûa taäp Q+ laø khoâng hieäu quaû. Do vaäy caàn thu heïp khoâng gian duyeät. Chuùng ta seõ nghieân cöùu thuaät toaùn caûi tieán theo höôùng giaûm soá thuoäc tính cuûa taäp caàn duyeät taát caû caùc taäp con. iiThuaät toaùn caûi tieánTröôùc khi ñi vaøo thuaät toaùn caûi tieán, ta caàn quan taâm moät soá khaùi nieäm sau:
Heä quaû: Neáu K laø khoùa cuûa Q thì TN K vaø TD K = Chöùng minh TN K Theo heä quaû 2 cuûa thuaät toaùn tìm bao ñoùng ta coù K+ KTDTG Ta chöùng minh A TN A K. Thaät vaäy: Neáu A K K+ KTDTG Q+-A K khoâng laø khoùa maâu thuaãn Chöùng minh TD K = Giaû söû coù thuoäc tính A TD K ta seõ daãn ñeán ñieàu maâu thuaãn. Thaät vaäy: Theo heä quaû 1 cuûa thuaät toaùn tìm bao ñoùng thì K+ = (K-A)+ A A TD coù X laø veá traùi cuûa moät phuï thuoäc haøm trong F sao cho X A (1) vaø A X X K+ = (K-A)+ A vì A X X (K-A)+ (K-A) X (2) (1) vaø (2) cho (K-A) A A(K-A)+ (K-A)+ A = (K-A)+ K+ = (K-A)+ maâu thuaãn vôùi ñieàu K laø khoùa. Döïa vaøo heä quaû treân ta coù thuaät toaùn tìm taát caû khoùa sau: Döõ lieäu vaøo: Löôïc ñoà quan heä Q vaø taäp phuï thuoäc haøm F Döõ lieäu ra: Taát caû caùc khoùa cuûa quan heä Thuaät toaùn tìm taát caû khoùa cuûa moät löôïc ñoà quan heä Böôùc 1: taïo taäp thuoäc tính nguoàn TN, taäp thuoäc tính trung gian TG Böôùc 2: if TG = then löôïc ñoà quan heä chæ coù moät khoùa K K TN keát thuùc Ngöôïc laïi Qua böôùc 3 Böôùc 3: tìm taát caû caùc taäp con Xi cuûa taäp trung gian TG Böôùc 4: tìm caùc sieâu khoùa Si baèng caùch Xi if (TN Xi)+ = Q+ then Si = TN Xi Böôùc 5: tìm khoùa baèng caùch loaïi boû caùc sieâu khoùa khoâng toái tieåu Si, Sj S if Si Sj then Loaïi Sj ra khoûi Taäp sieâu khoùa S S coøn laïi chính laø taäp khoùa caàn tìm. Ví duï 9: Giaûi laïi baøi taäp ví duï 8 Aùp duïng thuaät toaùn caûi tieán ta coù lôøi giaûi nhö sau: TN = {S}; TG = {C,Z} Goïi Xi laø caùc taäp con cuûa taäp TG:
Keát quaû quan heä treân coù hai khoùa laø : {S,C} vaø {S,Z} Каталог: 2015 2015 -> CHỦ TỊch nưỚC 2015 -> CHỦ TỊch nưỚC 2015 -> Qcvn 81: 2014/bgtvt 2015 -> Tác giả phạm hồng thái bài giảng ngôn ngữ LẬp trình c/C++ 2015 -> TRƯỜng đẠi học ngân hàng tp. Hcm markerting cơ BẢn lớP: mk001-1-111-T01 2015 -> Bch đOÀn tỉnh thanh hóa số: 381 bc/TĐtn-btg đOÀn tncs hồ chí minh 2015 -> Hãy là người đầu tiên biết 2015 -> Có chiến lược toàn diện về việc truyền phát tin tức 2015 -> Transformations 2015 -> SỞ gd&Đt bắc ninh trưỜng thpt hàn thuyêN tải về 1.89 Mb. Chia sẻ với bạn bè của bạn:
|
