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

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

F₂⁺=_Q2(F)={SID,SISD,SIDI,SISDI}{SID}= F₂

Q₁ vaø Q₂ ñeàu ñaït daïng chuaån BC vì trong Q_i chæ coù phuï thuoäc haøm coù veá traùi laø khoùa. F₁ ñöôï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 F₂

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 Q₁(XY)vôùi XY vaø Q₂ thì taäp khoùa S_Q cuûa Q luoân luoân baèng vôùi taäp khoùa S_Q2 cuûa Q₂.

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 Q₂. Giaû söû coù K’ K vaø K’ laø khoùa cuûa Q₂  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 Q₂. 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 S_K 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 Q₁ vaø Q₂ theo quy taéc sau:

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

Q₂=Q[Q⁺ -Y] S_K cuõng laø taäp khoùa cuûa Q₂

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

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

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 F_i ñeàu coùveá traùi laø sieâu khoùa thì Q_i ñ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ì Q_i ñ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 Q₁ vaø taäp thuoäc tính cuûa Q₁₂ 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 F₁₂ 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 Q₁ maø soá löôïng phuï thuoäc haøm mang xuoáng Q₁₂ 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ø Q₁, Q₂, Q₃ 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 = F₁  F₂  F₃ = {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 Q₁,Q₂,Q₃,Q₄ ñaït chuaån BC vaø pheùp phaân raõ khoâng baûo toaøn phuï thuoäc haøm vì G = F₁  F₂  F₃  F₄ ={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 Q₁ pheùp phaân raõ ñaõ choïn phuï thuoäc haøm sao cho khi chieáu F xuoáng Q₁₂ soá phuï thuoäc haøm mang xuoáng caøng nhieàu caøng toát.

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

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

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

iiBoå ñeà:

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

• 
  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

ÔÛ moãi böôùc 2 cuûa thuaät toaùn phaân raõ Q,F ta thu ñöôïc 2 löôïc ñoà Q_i⁺=Z’-A,Q₁⁺=XA vôùi Q_i⁺Q₁⁺ = (Z’-A)XA = X vaø XQ₁⁺ vaø Q₁ laø löôïc ñoà ôû daïng chuaån BC. Thuaät toaùn laïi tieáp tuïc phaân raõ Q_i 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 Q_i ñaït daïng chuaån BC.

F = {S  D,

I  B

IS  Q

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.

***Ñ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  Q₁=(BI) vaø F₁={IB}

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

***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  Q₂=(SD) vaø F₂={SD}

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

*** 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  Q₃=(SQI) vaø F₃={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 F₃ ta phaûi tính bao ñoùng cuûa taát caû taäp con cuûa {SQI}  F₃

*** 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  Q₄=(OI) vaø F₄={IO}
*** Giaûm O trong Z’ ta ñöôïc Z’= SI  Q₅=(SI)vaø F₅={PTHHN}

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

1:Q₁(BI) F₁={IB}

2:Q₂(SD) F₂={SD}

3:Q₃(SQI) F₃={SIQ}

4:Q₄(OI) F₄={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.
  

TN={S} TG={CZ}

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 F_tt cuûa F
Neáu coù moät phuï thuoäc haøm naøo cuûa F_tt 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 F_tt - 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  F_tt 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=F_tt={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
  

Q₁(CT),Q₂(HRC),Q₃(THR),Q₄(CSG),Q₅(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

• 
  Q₅ chöùa khoùa cuûa Q neân Q₁,Q₂,Q₃,Q₄,Q₅ 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 F_tt coù phuï thuoäc haøm f_i lieân quan ñeán taát caû thuoäc tính thì Q ñaït chuaån 3. Thaät vaäy:
   

f_iF_tt  f_i laø phuï thuoäc haøm coù veá phaûi 1 thuoäc tính  f_i 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 f_iF_tt. 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.

2. 
   Neáu löôïc ñoà Q’(W) goàm caùc thuoäc tính khoâng xuaát hieän trong F_tt 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.

3. 
   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 Q_i coù daïng YB vôùi YB  Y laø sieâu khoùa. Giaû söû trong Q_i 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 Q_i  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 F_tt

4. 
   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 F_tt  G = _Qi(F_tt) F_tt⁺  G⁺ (1)

Hôn nöõa F_tt⁺  G = _Qi(F_tt) F_tt⁺⁺  G⁺  F_tt⁺  G⁺ (2)

(1)vaø (2)  F_tt⁺ = G⁺

5. 
   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 Q_i⁺ vôùi Q_i⁺ 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A_jF_tt sao cho Q_i⁺Y vaø A_jQ_i⁺.ÔÛ doøng cuûa löôïc ñoà Q_l(YA_j) coù giaù trò a_j ôû coät A_j neân khi laøm baèng giaù trò keát quaû laø ôû coät A_j cuûa doøng coù löôïc Q_i coù theâm giaù trò a_j. 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 Q_i. Do Q_i chöùa khoùa neân caùc giaù trò a môùi theâm vaøo cuûa doøng Q_i 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à Q_i 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 Q₅ 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}

X₀=HSR

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

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

X₃=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 Q₅ 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 F_tt cuûa F

F_tt=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:

Q₁{ABD), Q₂(EHG), Q₃(GC), Q₄(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

Q₁,Q₂,Q₃,Q₄ khoâng chöùa khoùa  ñeå baûo toaøn thoâng tin ta caàn coù Q₅(A,B,E,H).Vaäy keát quaû cuûa phaân raõ laø Q₁,Q₂,Q₃,Q_4,Q₅

Каталог: 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: