Chöông 5. PHUÛ CUÛA TAÄP PHUÏ THUOÄC HAØM IÑÒNH NGHÓA
Noùi raèng hai taäp phuï thuoäc haøm F vaø G laø töông ñöông (Equivalent) neáu F+ = G+ kyù hieäu F G.
Ta noùi F phuû G neáu F+ G+
Thuaät toaùn xaùc ñònh F vaø G coù töông ñöông khoâng
Böôùc 1: Vôùi moãi phuï thuoäc haøm XY cuûa F ta xaùc ñònh xem XY coù laø thaønh vieân cuûa G khoâng
Böôùc 2: Vôùi moãi phuï thuoäc haøm XY cuûa G ta xaùc ñònh xem XY coù laø thaønh vieân cuûa F khoâng
Neáu caû hai böôùc treân ñeàu ñuùng thì F G
Ví duï 1: Cho löôïc ñoà quan heä Q(ABCDE) hai taäp phuï thuoäc haøm:
F={ABC,AD,CDE} vaø G = {ABCE,AABD,CDE}
a) F coù töông ñöông vôùi G khoâng?
b) F coù töông ñöông vôùi G’={ABCDE} khoâng?
Giaûi:
a) Ta coù =ABCDE trong G+ coù ABC vaø AD F G+ F+ G+ (1). =ABCDE trong F+ coù ABCE vaø AABD F+ G F+ G+ (2) (1) vaø(2) F+ = G+ F G.
b) Do = CD G’+ khoâng chöùa phuï thuoäc haøm CDE F khoâng töông ñöông vôùi G’
IIPHUÛ TOÁI THIEÅU CUÛA MOÄT TAÄP PHUÏ THUOÄC HAØM (minimal cover) 1Phuï thuoäc haøm coù veá traùi dö thöøa
F laø taäp caùc phuï thuoäc haøm treân löôïc ñoà quan heä Q, Z laø taäp thuoäc tính, ZYF. Noùi raèng phuï thuoäc haøm Z Y coù veá traùi dö thöøa (phuï thuoäc khoâng ñaày ñuû) neáu coù moät AZ sao cho:
F F-{Z Y}{(Z-A) Y}
Ngöôïc laïi Z Y laø phuï thuoäc haøm coù veá traùi khoâng dö thöøa hay Y phuï thuoäc haøm ñaày ñuû vaøo Z hay phuï thuoäc haøm ñaày ñuû.
Ví duï 2: Q(A,B,C) F={ABC; BC}
F F-{ABC}{(AB-A)C}={BC}
AB C laø phuï thuoäc haøm khoâng ñaày ñuû
B C laø phuï thuoäc haøm ñaày ñuû
Chuù yù: phuï thuoäc haøm coù veá traùi chöùa moät thuoäc tính laø phuï thuoäc haøm ñaày ñuû.
Ví duï 3: cho taäp phuï thuoäc haøm F = {A BC,B C,AB D} thì phuï thuoäc haøm ABD coù veá traùi dö thöøa B vì:
F F – {AB D}{A D}
{A BC,B C,A D}
Ta noùi F laø taäp phuï thuoäc haøm coù veá traùi khoâng dö thöøa neáu F khoâng chöùa phuï thuoäc haøm coù veá traùi dö thöøa.
Thuaät toaùn loaïi khoûi F caùc phuï thuoäc haøm coù veá traùi dö thöøa.
Böôùc 1: laàn löôït thöïc hieän böôùc 2 cho caùc phuï thuoäc haøm XY cuûa F
Böôùc 2:Vôùi moïi taäp con thaät söï X’ cuûa X.
Neáu X'Y F+ thì thay XY trong F baèng X'Y thöïc hieän laïi böôùc 2
Ví duï: ÔÛ ví duï 3 phuï thuoäc haøm ABD coù A+=ABCD ADF+. Trong F ta thay ABD baèng AD F {A BC,B C,A D}
2Taäp phuï thuoäc haøm coù veá phaûi moät thuoäc tính (the right sides of dependencies has a single attribute)
Moãi taäp phuï thuoäc haøm F ñeàu töông ñöông vôùi moät taäp phuï thuoäc haøm G maø veá phaûi cuûa caùc phuï thuoäc haøm trong G chæ goàm moät thuoäc tính.
Ví duï 4: cho F = {A BC,B C,AB D} ta suy ra
F {A B, A C ,B C,AB D} = G
G ñöôïc goïi laø taäp phuï thuoäc haøm coù veá phaûi moät thuoäc tính.
3Taäp phuï thuoäc haøm khoâng dö thöøa
Noùi raèng F laø taäp phuï thuoäc haøm khoâng dö thöøa neáu khoâng toàn taïi F’ F sao cho F’ F. Ngöôïc laïi F laø taäp phuï thuoäc haøm dö thöøa.
Ví duï: cho F = {A®BC, B®D, AB®D} thì F dö thöøa vì
F º F’= {A®BC, B®D}
Thuaät toaùn loaïi khoûi F caùc phuï thuoäc haøm dö thöøa:
Böôùc 1: Laàn löôït xeùt caùc phuï thuoäc haøm X Y cuûa F
Böôùc 2: neáu X Y laø thaønh vieân cuûa F - {X Y} thì loaïi X Y khoûi F
Böôùc 3: thöïc hieän böôùc 2 cho caùc phuï thuoäc haøm tieáp theo cuûa F
4Taäp phuï thuoäc haøm toái thieåu (minimal cover)
F ñöôïc goïi laø moät taäp phuï thuoäc haøm toái thieåu (hay phuû toái thieåu) neáu F thoûa ñoàng thôøi ba ñieàu kieän sau:
-
F laø taäp phuï thuoäc haøm coù veá traùi khoâng dö thöøa
-
F laø taäp phuï thuoäc haøm coù veá phaûi moät thuoäc tính.
-
F laø taäp phuï thuoäc haøm khoâng dö thöøa
Thuaät toaùn tìm phuû toái thieåu cuûa moät taäp phuï thuoäc haøm
Böôùc 1: loaïi khoûi F caùc phuï thuoäc haøm coù veá traùi dö thöøa.
Böôùc 2: Taùch caùc phuï thuoäc haøm coù veá phaûi treân moät thuoäc tính thaønh caùc phuï thuoäc haøm coù veá phaûi moät thuoäc tính.
Böôùc 3: loaïi khoûi F caùc phuï thuoäc haøm dö thöøa.
Chuù yù: Theo thuaät toaùn treân, töø moät taäp phuï thuoäc haøm F luoân tìm ñöôïc ít nhaát moät phuû toái thieåu Ftt ñeå FFtt vaø neáu thöù töï loaïi caùc phuï thuoäc haøm trong taäp F laø khaùc nhau thì coù theå seõ thu ñöôïc nhöõng phuû toái thieåu khaùc nhau.
Ví duï 5: Cho löôïc ñoà quan heä Q(A,B,C,D) vaø taäp phuï thuoäc F nhö sau:
F={AB CD,B C,C D}
Haõy tính phuû toái thieåu cuûa F.
Giaûi:
Böôùc 1: ABCD laø phuï thuoäc haøm coù veá traùi dö thöøa?
B CD F+? traû lôøi: B+=BCD B CD F+
Vaäy AB CD laø phuï thuoäc haøm coù veá traùi dö thöøa A keát quaû cuûa böôùc 1 laø:
F{B CD;B C;C D}
Böôùc 2: keát quaû cuûa böôùc 2 laø:
F{B D; B C;C D}=F1tt
Böôùc 3: trong F1tt, B C laø phuï thuoäc haøm dö thöøa?
B C G+? vôùi G = F1tt - {B C}={B D;C D}
BG+=BD B C G+ trong F1tt B C khoâng dö thöøa.
trong F1tt,B D laø phuï thuoäc haøm dö thöøa?
B D G+? vôùi G = F1tt - {B D}={B C;C D}
BG+=BCD B D G+ trong F1tt,B D dö thöøa.
keát quaû cuûa böôùc 3 cho phuû toái thieåu:
F{B C;C D}=Ftt
Ví duï 6: Cho löôïc ñoà quan heä Q(MSCD,MSSV,CD,HG) vaø taäp phuï thuoäc F nhö sau:
F = {MSCD CD;
CD MSCD;
CD,MSSV HG;
MSCD,HG MSSV;
CD,HG MSSV;
MSCD,MSSV HG}
Haõy tìm phuû toái thieåu cuûa F
keát quaû:
Ftt = {MSCD CD;
CD MSCD;
CD,HG MSSV;
MSCD,MSSV HG}
Chia sẻ với bạn bè của bạn: |