Giaùo trình CÔ SÔÛ DÖÕ lieäu trang



tải về 1.89 Mb.
trang13/20
Chuyển đổi dữ liệu07.07.2016
Kích1.89 Mb.
1   ...   9   10   11   12   13   14   15   16   ...   20

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 XY cuûa F ta xaùc ñònh xem XY coù laø thaønh vieân cuûa G khoâng

Böôùc 2: Vôùi moãi phuï thuoäc haøm XY cuûa G ta xaùc ñònh xem XY 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={ABC,AD,CDE} vaø G = {ABCE,AABD,CDE}

a) F coù töông ñöông vôùi G khoâng?

b) F coù töông ñöông vôùi G’={ABCDE} khoâng?

Giaûi:

a) Ta coù =ABCDE  trong G+ coù ABC vaø AD  F  G+  F+  G+ (1). =ABCDE  trong F+ coù ABCE vaø AABD  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 CDE  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, ZYF. 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={ABC; BC}

F  F-{ABC}{(AB-A)C}={BC}

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 ABD 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 XY 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 ABD coù A+=ABCD  ADF+. Trong F ta thay ABD baèng AD  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:

  1. F laø taäp phuï thuoäc haøm coù veá traùi khoâng dö thöøa

  2. F laø taäp phuï thuoäc haøm coù veá phaûi moät thuoäc tính.

  3. 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å FFtt 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: ABCD 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}

1   ...   9   10   11   12   13   14   15   16   ...   20


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương