IIIKHOÙA CUÛA LÖÔÏC ÑOÀ QUAN HEÄ (Key) 1Ñònh Nghóa
Q(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:
-
K+ = Q+ vaø
-
Khoâng toàn taïi K' K sao cho K’+= Q+
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.
Moät löôïc ñoà quan heä coù theå coù nhieàu khoùa vaø taäp thuoäc tính khoâng khoùa cuõng coù theå baèng roãng.
(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).
2Thuaät toaùn tìm taát caû khoùa iThuaät toaùn cô baûn
Böôù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}
Xi
|
|
Sieâu khoùa
|
khoùa
|
C
|
C
|
|
|
S
|
S
|
|
|
CS
|
CSZ
|
CS
|
CS
|
Z
|
ZC
|
|
|
CZ
|
CZ
|
|
|
SZ
|
SZC
|
SZ
|
SZ
|
CSZ
|
CSZ
|
CSZ
|
|
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án
Tröôù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:
-
Taäp thuoäc tính nguoàn (TN) chöùa taát caû caùc thuoäc tính coù xuaát hieän ôû veá traùi vaø khoâng xuaát hieän ôû veá phaûi cuûa caùc phuï thuoäc haøm vaø caùc thuoäc tính khoâng xuaát hieän ôû caû veá traùi laãn veá phaûi cuûa caùc phuï thuoäc haøm.
-
Taäp thuoäc tính ñích (TD) chöùa taát caû caùc thuoäc tính coù xuaát hieän ôû veá phaûi vaø khoâng xuaát hieän ôû veá traùi cuûa caùc phuï thuoäc haøm.
-
Taäp thuoäc tính trung gian (TG) chöùa taát caû caùc thuoäc tính xuaát hieän ôû caû veá traùi laãn veá phaûi cuûa caùc phuï thuoäc haøm.
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:
Xi
|
(TN Xi)
|
(TN Xi)+
|
Sieâu khoùa
|
khoùa
|
|
S
|
S
|
|
|
C
|
SC
|
Q+
|
SC
|
SC
|
Z
|
SZ
|
Q+
|
SZ
|
SZ
|
CZ
|
SCZ
|
Q+
|
SCZ
|
|
Keát quaû quan heä treân coù hai khoùa laø : {S,C} vaø {S,Z}
Chia sẻ với bạn bè của bạn: |