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



tải về 1.89 Mb.
trang17/20
Chuyển đổi dữ liệu07.07.2016
Kích1.89 Mb.
1   ...   12   13   14   15   16   17   18   19   20

IIITHIEÁT KEÁ CSDL BAÈNG CAÙCH PHAÂN RAÕ

1Phaân raõ thaønh daïng chuaån BC (hay chuaån 3) baûo toaøn thoâng tin

iCaùch thoâng thöôøng


Thuaät toaùn phaân raõ Q,F thaønh daïng chuaån BC (hay chuaån 3) baûo toaøn thoâng tin

Böôùc 1:Tìm taát caû khoùa cuûa Q

Böôùc 2:Tìm phuï thuoäc haøm X  Y Î F coù X khoâng laø sieâu khoùa vaø Y khoâng chöùa thuoäc tính khoùa.

Neáu tìm thaáy thì taùch Q thaønh Q1 vaø Q2 theo quy taéc sau:

Q1=Q[XY]; F1Q1(F)tìm bao ñoùng cuûa taát caû taäp con cuûa XY ñeå suy ra Q1(F)F1

Q2=Q[Q+ -Y] F2Q2(F)tìm bao ñoùng cuûa taát caû taäp con cuûa Q+-Y ñeå suy ra Q2(F)F2

thöïc hieän thuaät toaùn phaân raõ (Q1,F1)

thöïc hieän thuaät toaùn phaân raõ (Q2,F2)

Ngöôïc laïi neáu khoâng tìm thaáy thì coù hai tröôøng hôïp:

Tröôøng hôïp 1: moïi phuï thuoäc haøm trong Fi ñeàu coùveá traùi laø sieâu khoùa thì Qi ñaït chuaån BC

Tröôøng hôïp 2: neáu coù phuï thuoäc haøm coù veá traùi khoâng laø sieâu khoùa vaø veá phaûi laø thuoäc tính khoùa thì Qi ñaït chuaån 3.

Ví duï 16: cho Q(S,D,I,M) F={SID;SDM} haõy phaân raõ Q thaønh caùc löôïc ñoà con ñaït chuaån BC baûo toaøn thoâng tin

Giaûi:

Böôùc 1: tìm taát caû khoùa cuûa Q

i

TNXi

(TNXi)+

Sieâu khoùa

Khoùa



SI

SDIM

SI

SI

D

SID

SDIM

SID




Böôùc 2: phuï thuoäc haøm SD  M Î F coù SD khoâng laø sieâu khoùa.



Chuù yù: ñeå tính ñöôïc F1,F2,K1,K2 nhö hình treân, ta phaûi tính bao ñoùng cuûa taát caû taäp con cuûa{SDM} vaø {SDI} F1,F2 roài tìm taát caû khoùa cuûa Q1 vaø Q2.




S+=S

D+

=D

M+

=M




S+=S

D+

=D

I+

=I










SD+

=SDM

SM+

=SM







SD+

=SDM

SI+

=SDIM
















DM+

=DM













DI+

=DI
















SDM+

=SDM













SDI+

=SDIM




F1+=Q1(F)={SDM,SDSM,SDDM,SDSDM}{SDM}= F1

F2+=Q2(F)={SID,SISD,SIDI,SISDI}{SID}= F2

Q1 vaø Q2 ñeàu ñaït daïng chuaån BC vì trong Qi chæ coù phuï thuoäc haøm coù veá traùi laø khoùa. F1 ñöôïc taïo thaønh baèng caùch laáy caùc phuï thuoäc haøm cuûa Q1(F)coù veá phaûi moät thuoäc tính. Töông töï cho F2

Ví duï 17: cho Q(CTHRSG), F={CT;HRC;HTR;CSG;HSR} haõy phaân raõ Q thaønh caùc löôïc ñoà con ñaït chuaån BC baûo toaøn thoâng tin. (giaûi nhö ví duï treân)



Tính chaát: Theo thuaät toaùn treân, khi phaân raõ Q thaønh Q1(XY)vôùi XY vaø Q2 thì taäp khoùa SQ cuûa Q luoân luoân baèng vôùi taäp khoùa SQ2 cuûa Q2.

Chöùng minh

Thaät vaäy, K laø moät khoùa cuûa Q  K laø moät sieâu khoùa cuûa Q2. Giaû söû coù K’ K vaø K’ laø khoùa cuûa Q2  K’(Q+-Y) maø XY  K’Q+. Ñieàu naøy maâu thuaãn vôùi K laø khoùa cuûa Q  K laø khoùa cuûa Q2. Ngöôïc laïi cuõng ñuùng.

Döïa vaøo tính chaát treân, ta caûi tieán thuaät toaùn phaân raõ nhaèm giaûm bôùt khoái löôïng tính caùc phuï thuoäc haøm cuûa taäp F+

Thuaät toaùn phaân raõ Q,F thaønh daïng chuaån BC (hay chuaån 3) baûo toaøn thoâng tin

Böôùc 1: Tìm taäp taát caû khoùa SK cuûa Q

Böôùc 2: Tìm phuï thuoäc haøm X  Y Î F coù X khoâng laø sieâu khoùa vaø Y khoâng chöùa thuoäc tính khoùa. Neáu tìm thaáy thì taùch Q thaønh Q1 vaø Q2 theo quy taéc sau:

Q1=Q[XY]; Tính F1 baèng caùch tính bao ñoùng taát caû taäp con cuûa XY

Q2=Q[Q+ -Y] SK cuõng laø taäp khoùa cuûa Q2

thöïc hieän böôùc 1 cho Q1

thöïc hieän böôùc 2 cho Q2

Ngöôïc laïi neáu khoâng tìm thaáy thì coù hai tröôøng hôïp:

Tröôøng hôïp 1: moïi phuï thuoäc haøm trong Fi ñeàu coùveá traùi laø sieâu khoùa thì Qi ñaït chuaån BC

Tröôøng hôïp 2: neáu coù phuï thuoäc haøm coù veá traùi khoâng laø sieâu khoùa vaø veá phaûi laø thuoäc tính khoùa thì Qi ñaït chuaån 3.

Chuù yù: Thuaät toaùn naøy chæ tieän trong tröôøng hôïp khoái löôïng tính toaùn trong vieäc tìm taát caû khoùa cuûa löôïc ñoà quan heä Q khoâng lôùn. Noùi caùch khaùc taäp trung gian TG coù ít thuoäc tính. Ngöôïc laïi ta phaûi duøng thuaät toaùn cuûa phaàn tieáp theo.

Ví duï 18: phaân raõ löôïc ñoà ôû ví duï treân thaønh caùc löôïc ñoà con ôû daïng chuaån BC baûo toaøn thoâng tin.

Trong F coù 4 phuï thuoäc haøm CT,HRC,HTR,CSG laøm Q khoâng ñaït daïng chuaån 3 hay BC vaø pheùp phaân raõ treân ñaõ choïn ngaãu nhieân phuï thuoäc haøm CT ñeå phaân raõ thaønh Q1 vaø taäp thuoäc tính cuûa Q12 chính laø taäp thuoäc tính cuûa Q boû thuoäc tính T.Taäp phuï thuoäc haøm F12 seõ chöùa caùc phuï thuoäc haøm cuûa F boû ñi caùc phuï thuoäc haøm coù veá traùi hay veá phaûi chöùa thuoäc tính T. Nhö vaäy tuøy theo caùch choïn phuï thuoäc haøm ñeå phaân raõ thaønh Q1 maø soá löôïng phuï thuoäc haøm mang xuoáng Q12 khaùc nhau vaø chaát löôïng phaân raõ cuõng khaùc nhau. Keát quaû cuûa pheùp phaân raõ treân chính laø Q1, Q2, Q3 cuûa hình treân. Pheùp phaân raõ baûo toaøn thoâng tin, vaø caùc löôïc ñoà con ñaït chuaån BC nhöng pheùp phaân raõ khoâng baûo toaøn phuï thuoäc haøm vì G = F1  F2  F3 = {CT; HRC; CHR; HSRG} khoâng töông ñöông vôùi F (HTR  G+ vaø CSG  G+). Ta haõy xem pheùp phaân raõ sau seõ cho keát quaû toát hôn.



Pheùp phaân raõ cuõng cho keát quaû pheùp phaân raõ baûo toaøn thoâng tin, caùc löôïc ñoà con Q1,Q2,Q3,Q4 ñaït chuaån BC vaø pheùp phaân raõ khoâng baûo toaøn phuï thuoäc haøm vì G = F1  F2  F3  F4 ={CSG;HRC;CHR;CT;HSC} khoâng töông ñöông vôùi F (HTR  G+).Pheùp phaân raõ naøy toát hôn vì chæ coù moät phuï thuoäc haøm HTR khoâng thuoäc G+ trong khi pheùp phaân raõ treân coù tôùi 2 phuï thuoäc haøm HTR vaø CSG khoâng thuoäc G+.Sôû dó pheùp phaân raõ thöù 2 toát hôn vì ôû böôùc choïn phuï thuoäc haøm ñeå phaân raõ thaønh Q1 pheùp phaân raõ ñaõ choïn phuï thuoäc haøm sao cho khi chieáu F xuoáng Q12 soá phuï thuoäc haøm mang xuoáng caøng nhieàu caøng toát.



Ví duï 19: cho Q(A,B,C,D,E,G), F={AEC;CGA;BDG;GAE} haõy phaân raõ Q thaønh caùc löôïc ñoà con ñaït chuaån BC baûo toaøn thoâng tin.

Neáu Q ñöôïc phaân raõ thaønh:

(Q1(BDG), Q2(A,B,C,D,E)) löôïc ñoà cô sôû döõ lieäu ñaït chuaån 3

(Q1(BDG), Q2(A,C,E), Q3(A,B,D,E)) löôïc ñoà cô sôû döõ lieäu ñaït chuaån BC


iiBoå ñeà:


Neáu Q khoâng ôû daïng chuaån BC thì coù thuoäc tính A,B thuoäc Q+ sao cho (Q+-AB)A

Chöùng minh:

Q khoâng ôû daïng chuaån BC  coù XA sao cho X khoâng laø sieâu khoùa  coù thuoäc tính B  XA (vì neáu khoâng coù B  XA thì X phaûi laø sieâu khoùa)  (Q+-AB)  X  (Q+-AB)A



Nhaän xeùt:

  • Moät löôïc ñoà Q ôû daïng chuaån BC vaãn coù theå coù AB sao cho (Q+-AB)A

  • Moät löôïc ñoà Q khoâng coù AB sao cho (Q+-AB)A thì Q ôû daïng chuaån BC

iiiThuaät toaùn


Thuaät toaùn phaân raõ sau khoâng caàn tìm taát caû khoùa cuûa löôïc ñoà quan heä Q

Thuaät Toaùn phaân raõ Q, F thaønh daïng chuaån BC baûo toaøn thoâng tin

Böôùc 1: Z’ = Q+

Böôùc 2: phaân raõ Z’ theo thuaät toaùn chi tieát ñeå ñöôïc 2 löôïc ñoà Z’-A vaø XA trong ñoù XA ôû daïng chuaån BC vaø X  A

Neáu thuaät toaùn chi tieát cho keát quaû thì qua böôùc 3

Ngöôïc laïi keát thuùc thuaät toaùn

Böôùc 3: nhaän XA laø moät löôïc ñoà con cuûa caùc löôïc ñoà keát quaû Q1,...,Qk

Böôùc 4: thöïc hieän phaân raõ Z’-A,F
Thuaät toaùn chi tieát

Böôùc 1: neáu Z’ khoâng chöùa AB sao cho (Z’-AB)A. thì

baùo khoâng phaân raõ ñöôïc.

Ngöôïc laïi qua böôùc 2

Böôùc 2: ñaët Y’ = Z’

Böôùc 3: neáu Y’ chöùa AB sao cho (Y’-AB)A. thì gaùn Y’ = Y’–B thöïc hieän laïi böôùc 2

Böôùc 4: böôùc 3 cho keát quaû Y’ = XA vôùi XA ôû daïng chuaån BC vaø X  A. Traû veà XA
Nhaän xeùt

ÔÛ moãi böôùc 2 cuûa thuaät toaùn phaân raõ Q,F ta thu ñöôïc 2 löôïc ñoà Qi+=Z’-A,Q1+=XA vôùi Qi+Q1+ = (Z’-A)XA = X vaø XQ1+ vaø Q1 laø löôïc ñoà ôû daïng chuaån BC. Thuaät toaùn laïi tieáp tuïc phaân raõ Qi theo ñuùng caùch ñaõ laøm  thuaät toaùn phaân raõ baûo toaøn thoâng tin vaø caùc löôïc ñoà con Qi ñaït daïng chuaån BC.



Thuaät toaùn chi tieát tìm Ql ñaït chuaån BC sao cho Ql+ chöùa nhieàu thuoäc tính nhaát. Ñeå tìm ñöôïc Ql nhö vaäy thuaät toaùn chi tieát tìm hai thuoäc tính ABQ+ sao cho (Q+-AB)A. Neáu tìm thaáy chöùng toû Q chöa ñaït chuaån BC vaø thuaät toaùn giaûm B trong Q vôùi hy voïng thu ñöôïc löôïc ñoà con Ql ñaït chuaån BC vaø thoûa phuï thuoäc haøm (Q+-AB)A. Thuaät toaùn chi tieát tieáp tuïc tìm vaø giaûm cho tôùi khi thu ñöôïc löôïc ñoà con khoâng coù hai thuoäc tính AB sao cho (Q+-AB)A  Ql laø löôïc ñoà con ñaït chuaån BC caàn tìm.

Ví duï 19: Cho quan heä Q(B,O,S,Q,I,D) vaø taäp phuï thuoäc haøm F

F = {S  D,

I  B

IS  Q


B  O}

Haõy phaân raõ Q thaønh caùc löôïc ñoà con ñaït daïng chuaån BC vaø baûo toaøn thoâng tin.



Giaûi

***Ñaët Z’= Q+= BOSQID

Thöïc hieän thuaät toaùn chi tieát

Y’= BOSQID

Choïn 2 thuoäc tính . Tìm bao ñoùng cuûa taäp hôïp thuoäc tính coøn laïi. Neáu bao ñoùng chöùa 1 trong 2 thuoäc tính choïn chaúng haïn A, nghóa laø ta ñaõ tìm ñöôïc 2 thuoäc tính AB sao cho (Y’-AB)A

Choïn BO:(SQID)+  B

Giaûm O trong Y’ ta ñöôïc Y’= BSQID

Choïn BS:(QID)+  B

Giaûm S trong Y’ ta ñöôïc Y’= BQID

Choïn BQ:(ID)+  B

Giaûm Q trong Y’ ta ñöôïc Y’= BID

Choïn BD: I+  B

Giaûm D trong Y’ ta ñöôïc Y’= BI  Q1=(BI) vaø F1={IB}

Ñeå tính F1 ta phaûi tính bao ñoùng cuûa taát caû taäp con cuûa {BI}F1

***Giaûm B trong Z’ ta ñöôïc Z’= OSQID

Ñaët Y’=OSQID

Choïn OD: (SQI)+  D;

Giaûm O trong Y’ ta ñöôïc Y’= SQID

choïn QD: (SI)+  D

giaûm Q trong Y’ ta ñöôïc Y’= SID

choïn ID: S+  D;

giaûm I trong Y’ ta ñöôïc Y’= SD  Q2=(SD) vaø F2={SD}

Ñeå tính F2 ta phaûi tính bao ñoùng cuûa taát caû taäp con cuûa {SD}  F2

*** Giaûm D trong Z’ ta ñöôïc Z’= OSQI

Ñaët Y’=OSQI

choïn OQ: (SI)+  Q

giaûm O trong Y’ ta ñöôïc Y’= SQI  Q3=(SQI) vaø F3={SIQ}

ÔÛ böôùc treân khoâng choïn AB ñeå bao ñoùng taäp hôïp thuoäc tính coøn laïi chöùa A hay B

Ñeå tính F3 ta phaûi tính bao ñoùng cuûa taát caû taäp con cuûa {SQI}  F3

*** Giaûm Q trong Z’ ta ñöôïc Z’= OSI

Ñaët Y’=OSI

Choïn OS: I+=IBO  O

giaûm S trong Y’ ta ñöôïc Y’= OI  Q4=(OI) vaø F4={IO}
*** Giaûm O trong Z’ ta ñöôïc Z’= SI  Q5=(SI)vaø F5={PTHHN}

Ta coù theå hieåu Q3(SQI)laø toå hôïp cuûa 2 löôïc ñoà con Q5(SI) vaø Q3(SQI)



Vaäy keát quaû phaân raõ laø:

1:Q1(BI) F1={IB}

2:Q2(SD) F2={SD}

3:Q3(SQI) F3={SIQ}

4:Q4(OI) F4={IO}

ivChuù yù


  • Neân traùnh phaân raõ neáu löôïc ñoà ñaõ ôû daïng chuaån mong muoán.

  • Neân xem xeùt toå hôïp caùc löôïc ñoà quan heä con thaønh löôïc ñoà lôùn hôn neáu löôïc ñoà lôùn hôn vaãn ñaït daïng chuaån mong muoán.

  • Moät keát quaû phaân raõ baûo toaøn phuï thuoäc haøm seõ coù giaù trò hôn keát quaû phaân raõ khoâng baûo toaøn phuï thuoäc haøm. Giöõa hai keát quaû phaân raõ ñeàu khoâng baûo toaøn phuï thuoäc haøm thì keát quaû phaân raõ thoûa nhieàu phuï thuoäc haøm trong F seõ coù giaù trò hôn .

  • Khoâng coù thuaät toaùn phaân raõ löôïc ñoà Q thaønh caùc löôïc ñoà con ôû daïng chuaån BC vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm.

  • Vaãn coù löôïc ñoà Q ñöôïc phaân raõ thaønh caùc löôïc ñoà con ôû daïng chuaån BC vöøa baûo toaøn thoâng tin vöa baûo toaøn phuï thuoäc haøm.


Ví duï 20: cho löôïc ñoà Q(CSZ) coù F={CS®Z,Z®C}. Q khoâng theå phaân raõ thaønh caùc löôïc ñoà con ôû daïng chuaån BC vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm. Thaät vaäy:

TN={S} TG={CZ}



Taát caû khoùa cuûa Q laø:

Xi

TNXi

(TNXi)+

sieâu khoùa

khoùa



S

S







Z

SZ

SZC

SZ

SZ

C

SC

SZC

SC

SC

ZC

SZC

SZC

SZC




Vaäy Q ñaït daïng chuaån 3 nhöng khoâng ôû daïng chuaån BC vì coù Z®C coù veá traùi khoâng laø sieâu khoùa. Nhöng neáu ta phaân raõ Q thaønh caùc löôïc ñoà con coù ít hôn 3 thuoäc tính thì phuï thuoäc CS®Z khoâng suy ra ñöôïc töø caùc phuï thuoäc hình chieáu.

2Phaân raõ thaønh daïng chuaån 3 vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm


Thuaät Toaùn phaân raõ Q, F thaønh daïng chuaån 3, baûo toaøn thoâng tin, baûo toaøn phuï thuoäc haøm

Döõ lieäu vaøo: löôïc ñoà quan heä Q vaø taäp phuï thuoäc haøm F.

Döõ lieäu ra: moät phaân raõ sao cho moãi löôïc ñoà quan heä con ñeàu ñaït chuaån 3 vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm.
Tìm phuû toái thieåu Ftt cuûa F
Neáu coù moät phuï thuoäc haøm naøo cuûa Ftt maø lieân quan ñeán taát caû caùc thuoäc tính cuûa Q thì keát quaû phaân raõ chính laø Q ( Q khoâng theå phaân raõ)
Neáu coù nhöõng thuoäc tính cuûa Q khoâng naèm trong moät phuï thuoäc naøo cuûa Ftt - duø ôû veá phaûi hay veá traùi cuûa F thì chuùng taïo thaønh moät löôïc ñoà caàn tìm.
Cöù moãi phuï thuoäc haøm X  A  Ftt thì XA laø moät löôïc ñoà caàn tìm
Neáu coù moät löôïc ñoà con chöùa khoùa K cuûa Q thì keát thuùc thuaät toaùn

Ngöôïc laïi taïo moät löôïc ñoà con K
Ví duï 21: cho löôïc ñoà Q(CTHRSG),F={C®T,HR®C,TH®R,CS®G,HS®R}.Haõy phaân raõ Q thaønh caùc löôïc ñoà con ñaït daïng chuaån 3 vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm.

Gæai:

  • F=Ftt={C®T,HR®C,TH®R,CS®G,HS®R} laø phuû toái thieåu.

  • AÙp duïng thuaät toaùn treân Q ñöôïc phaân raõ thaønh caùc löôïc ñoà con

Q1(CT),Q2(HRC),Q3(THR),Q4(CSG),Q5(HSR)

  • Khoùa cuûa Q

    Xi

    TNXi

    (TNXi)+

    sieâu khoùa

    khoùa



    HS

    CTHRSG

    HS

    HS

    C

    HSC

    CTHRSG

    HSC




    T

    HST

    CTHRSG

    HST




    CT

    HSCT

    CTHRSG

    HSCT




    R

    HSR

    CTHRSG

    HSR




    CR

    HSCR

    CTHRSG

    HSCR




    TR

    HSTR

    CTHRSG

    HSTR




    CTR

    HSCTR

    CTHRSG

    HSCTR




  • Q5 chöùa khoùa cuûa Q neân Q1,Q2,Q3,Q4,Q5 laø keát quaû cuûa phaân raõ.

Ñònh lyù: Thuaät toaùn treân taïo ra moät phaân raõ ôû daïng chuaån 3 vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc haøm

Chöùng minh:

  1. Neáu Ftt coù phuï thuoäc haøm fi lieân quan ñeán taát caû thuoäc tính thì Q ñaït chuaån 3. Thaät vaäy:

fiFtt  fi laø phuï thuoäc haøm coù veá phaûi 1 thuoäc tính  fi coù daïng KA  K laø sieâu khoùa. Neáu khoùa cuûa Q laø K’ K thì ta coù K’A  KA laø phuï thuoäc haøm coù veá traùi dö thöøa ñieàu naøy maâu thuaãn vôùi fiFtt. Vaäy K laø khoùa cuûa Q  neáu Q coù thuoäc tính khoâng khoùa thì A laø thuoäc tính khoâng khoùa duy nhaát cuûa Q vaø moïi phuï thuoäc haøm coù veá phaûi laø A phaûi coù veá traùi laø K  löôïc ñoà quan heä Q khoâng coù phuï thuoäc haøm coù veá traùi khoâng laø sieâu khoùa vaø veá phaûi khoâng laø thuoäc tính khoùa  Q ñaït chuaån 3.

  1. Neáu löôïc ñoà Q(W) goàm caùc thuoäc tính khoâng xuaát hieän trong Ftt thì Q ñaït chuaån 3. Thaät vaäy:

V laø taäp con baát kyø cuûa W ta coù V+=V  F’ cuûa Q’ chæ goàm caùc phuï thuoäc haøm hieån nhieân  trong F’ khoâng coù phuï thuoäc haøm coù veá traùi khoâng laø sieâu khoùa vaø veá phaûi laø thuoäc tính khoâng khoùa Q’ ñaït chuaån 3.

  1. Ta chöùng minh moãi löôïc ñoà con ôû daïng chuaån 3. Thaät vaäy:

Theo thuaät toaùn thì moãi löôïc ñoà con Qi coù daïng YB vôùi YB  Y laø sieâu khoùa. Giaû söû trong Qi coù phuï thuoäc haøm XA coù veá traùi khoâng laø sieâu khoùa vaø veá phaûi khoâng laø thuoäc tính khoùa. Ta phaân laøm hai tröôøng hôïp:

Tröôøng hôïp 1: A=B  XB  X  Y  YB laø phuï thuoäc coù veá traùi dö thöøa, ñieàu naøy traùi vôùi YB laø phuï thuoäc haøm trong phuû toái thieåu.

Tröôøng hôïp 2: AB  AY (1). Goïi K laø khoùa cuûa Qi  K  Y (2). A laø thuoäc tính khoâng khoùa neân A  K (3).(1)(2)(3) K  Y (4).K laø khoùa neân K®B  Y®B laø phuï thuoäc haøm coù veá traùi dö thöøa. Ñieàu naøy traùi vôùi ñieàu phuï thuoäc haøm Y®B laø phuï thuoäc haøm cuûa phuû toái thieåu Ftt

  1. Ta chöùng minh pheùp phaân raõ baûo toaøn phuï thuoäc haøm. Thaät vaäy:

Hieån nhieân Ftt  G = Qi(Ftt) Ftt+  G+ (1)

Hôn nöõa Ftt+  G = Qi(Ftt) Ftt++  G+  Ftt+  G+ (2)



(1)vaø (2)  Ftt+ = G+

  1. Ta chöùng minh pheùp phaân raõ baûo toaøn thoâng tin. Thaät vaäy:

Laäp baûng kieåm tra baûo toaøn thoâng tin. Ta laàn löôït ñoàng nhaát caùc giaù trò cuûa baûng treân theo caùc phuï thuoäc haøm ñöôïc phaùt hieän ôû moãi böôùc cuûa thuaät toaùn tìm bao ñoùng cuûa taäp thuoäc tính Qi+ vôùi Qi+ chöùa khoùa K cuûa löôïc ñoà Q. Phuï thuoäc haøm ñaàu tieân ñöôïc phaùt hieän laø YAjFtt sao cho Qi+Y vaø AjQi+.ÔÛ doøng cuûa löôïc ñoà Ql(YAj) coù giaù trò aj ôû coät Aj neân khi laøm baèng giaù trò keát quaû laø ôû coät Aj cuûa doøng coù löôïc Qi coù theâm giaù trò aj. Tieáp tuïc cho caùc phuï thuoäc haøm phaùt hieän tieáp theo ta seõ coù theâm caùc giaù trò a ôû caùc coät khaùc cuûa doøng Qi. Do Qi chöùa khoùa neân caùc giaù trò a môùi theâm vaøo cuûa doøng Qi seõ xuaát hieän ôû taát caû caùc thuoäc tính cuûa löôïc ñoà Q. Suy ra haøng cuûa löôïc ñoà Qi seõ chöùa toaøn a laø ñieàu phaûi chöùng minh. Ñeå laøm saùng toû yù töôûng cuûa phaàn chöùng minh naøy ta xeùt tröôøng hôïp cuï theå cuûa ví duï 21 :

Böôùc 1: ta laäp baûng kieåm tra baûo toaøn thoâng tin:




C

T

H

R

S

G

Q1(CT)

a1

a2













Q2(HRC)

a1




a3

a4







Q3(THR)




a2

a3

a4







Q4(CSG)

a1










a5

a6

Q5(HSR)







a3

a4

a5




Böôùc 2:Ta chöùng minh doøng Q5 cuûa baûng treân seõ chöùa toaøn giaù trò a. Thaät vaäy: ta laàn löôït ñoàng nhaát caùc giaù trò cuûa baûng treân theo caùc phuï thuoäc haøm ñöôïc phaùt hieän theo thuaät toaùn tìm bao ñoùng cuûa X={HSR}  K; F={C®T,HR®C,TH®R,CS®G,HS®R}

X0=HSR

X1=HSRC do HR®C. Ñoàng nhaát caùc giaù trò theo phuï thuoäc haøm naøy. Treân doøng Q2 ôû coät C chöùa giaù trò a neân treân doøng Q5 seõ coù theâm giaù trò a ôû coät C

X2=HSRCT do C®T. Ñoàng nhaát caùc giaù trò theo phuï thuoäc haøm naøy.

X3=HSRCTG do CS®G ñoàng nhaát caùc giaù trò theo phuï thuoäc haøm naøy.





C

T

H

R

S

G

Q1(CT)

a1

a2













Q2(HRC)

a1

a2

a3

a4







Q3(THR)

a1

a2

a3

a4







Q4(CSG)

a1

a2







a5

a6

Q5(HSR)

a1

a2

a3

a4

a5

a6

Do X+=Q+ neân doøng Q5 chöùa toaøn giaù trò a

Ví duï 22: Cho Q(ABCDEGH), F={ABD; EHG; GC; DC} haõy phaân raõ Q thaønh caùc löôïc ñoà con ôû daïng chuaån 3 vöøa baûo toaøn thoâng tin vöøa baûo toaøn phuï thuoäc.

Giaûi:

Tìm phuû toái thieåu Ftt cuûa F

Ftt=F={ABD; EHG; GC; DC}

AÙp duïng thuaät toaùn, Q ñöôïc phaân raõ thaønh löôïc ñoà CSDL sau:

Q1{ABD), Q2(EHG), Q3(GC), Q4(DC)

Tìm khoùa cuûa Q

TN={ABEH} TG={GD}


Xi

TN Xi

(TN Xi)+

Sieâu khoùa

Khoùa



ABEH

ABCDEGH

ABEH

ABEH

G

ABEHG

ABCDEGH

ABEHG




D

ABEHD

ABCDEGH

ABEHD




GD

ABEHGD

ABCDEGH

ABEHGD




Q1,Q2,Q3,Q4 khoâng chöùa khoùa  ñeå baûo toaøn thoâng tin ta caàn coù Q5(A,B,E,H).Vaäy keát quaû cuûa phaân raõ laø Q1,Q2,Q3,Q4,Q5

1   ...   12   13   14   15   16   17   18   19   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