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



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

IIPHEÙP TAÙCH KEÁT NOÁI BAÛO TOAØN

1Pheùp taùch keát noái baûo toaøn thoâng tin (lossless-join decomposition)


Cho löôïc ñoà quan heä Q(TENNCC,DIACHI,SANPHAM,DONGIA) coù quan heä töông öùng laø r

Ñaët r1 laø quan heä coù ñöôïc baèng caùch chieáu r leân Q1(TENNCC,SANPHAM,DONGIA),

Ñaët r2 laø quan heä coù ñöôïc baèng caùch chieáu r leân Q2(TENNCC,DIACHI)

Ñaët r’laø quan heä coù ñöôïc baèng caùch keát töï nhieân giöõa r1 vaø r2 qua TENNCC.



chaúng haïn:

r










TENNCC

DIACHI

SANPHAM

DONGIA

Hung

12 Nguyeãn Kieäm

Gaïch oáng

200

Hung

12 Nguyeãn Kieäm

Gaïch theû

250

Hung

40 Nguyeãn Oanh

Gaïch oáng

200




r2 = r.Q2+




r1 = r.Q1+

TENNCC

DIACHI




TENNCC

SANPHAM

DONGIA

Hung

12 Nguyeãn Kieäm




Hung

Gaïch oáng

200

Hung

40 Nguyeãn Oanh




Hung

Gaïch theû

250




TENNCC

r’ = r1|><|r2

TENNCC

DIACHI

SANPHAM

DONGIA

Hung

12 Nguyeãn Kieäm

Gaïch oáng

200

Hung

12 Nguyeãn Kieäm

Gaïch theû

250

Hung

40 Nguyeãn Oanh

Gaïch oáng

200

Hung

40 Nguyeãn Oanh

Gaïch theû

250

Keát quaû laø r  r’ hay r  r.Q1|><|r.Q2.

Vôùi keát quaû treân, ta noùi pheùp taùch (Q1,Q2) taùch Q thaønh Q1, Q2 laø taùch-keát noái (phaân raõ) maát maùt thoâng tin.

Neáu r = r.Q1|><|r.Q2­­ ta noùi pheùp taùch (Q1,Q2) laø taùch-keát noái khoâng maát maùt thoâng tin (taùch keát noái baûo toaøn thoâng tin hay phaân raõ baûo toaøn thoâng tin).

Vaäy vôùi ñieàu kieän naøo thì pheùp taùch trôû thaønh taùch-keát noái khoâng maát maùt thoâng tin?


iÑònh nghóa pheùp taùch Q thaønh 2 löôïc ñoà con


Q laø löôïc ñoà quan heä, Q1, Q2 hai löôïc ñoà con coù:

Q1+ Q2+ = X

Q1+ Q2+ = Q+

Noùi raèng löôïc ñoà quan heä Q ñöôïc taùch thaønh hai löôïc ñoà con Q1, Q2 theo pheùp taùch (Q1,Q2) laø pheùp taùch keát noái khoâng maát (hay pheùp taùch baûo toaøn thoâng tin) neáu vôùi r laø quan heä baát kyø cuûa Q ta coù:

r = r.Q1r.Q2

Töùc laø r ñöôïc taïo neân töø pheùp keát noái töï nhieân cuûa caùc hình chieáu cuûa noù treân caùc Q1,Q2


iiTính chaát


Neáu Q laø moät löôïc ñoà quan heä, Q1,Q2­­­ laø hai löôïc ñoà quan heä con coù

Q1+  Q2+ = X

Q1+  Q2+ = Q+

X  Q+­

Thì r = r.Q1r.Q2

Chöùng minh:

t r t r.Q1r.Q2­­

t  r  t1r1 t1 = t.Q1 t2r2 t2 = t.Q2 t1.X = t2.X = t.X

 t  r.Q1r.Q2­­ (Theo ñònh nghóa)

t r.Q1r.Q2­­ t r­­

t  r.Q1r.Q2­­  t1r1 t1 = t.Q1 (1)

maø t1  r1=r.Q1 neân theo ñònh nghóa pheùp chieáu ta laïi coù t’r t1 = t’.Q1 (2)

(1) vaø (2)  t’.Q1 = t.Q1  t’.X = t.X  t’.Q2 = t.Q2­­ (do X  Q2­­)

 t’ = t  t  r

Ví duï 10: cho Q(SAIP), Q1 =(SA) , Q2 =(SIP) F={SA,SIP}. Hoûi vieäc taùch Q thaønh Q1 vaø Q2 coù gaây ra maát maùt thoâng tin khoâng?

AÙp duïng tính chaát treân, ta coù

Q1+  Q2+ = S

Q1+  Q2+ = SAIP = Q+

S  SA = Q1+ ­­

Theo tính chaát treân, vôùi moïi quan heä r cuûa Q ta luoân coù r = r.Q1r.Q2. Suy ra pheùp taùch treân laø pheùp taùch keát noái baûo toaøn thoâng tin.


iiiPheùp taùch Q thaønh n löôïc ñoà con


Q laø moät löôïc ñoà quan heä, F laø taäp phuï thuoäc haøm. Q ñöôïc taùch thaønh caùc löôïc ñoà con Q1, Q2, Q3...,Qn theo töøng böôùc maø ôû moãi böôùc moät löôïc ñoà ñöôïc taùch thaønh hai löôïc ñoà con vaø thoûa maõn ñieàu kieän cuûa tính chaát baûo toaøn thoâng tin thì vôùi r laø quan heä baát kyø cuûa Q ta luoân coù:

r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qn

Chöùng minh:

Ta chöùng minh baèng phöông phaùp qui naïp.

ÔÛ böôùc i = 1 thì r = r.Q1|><|r.Q1m ñuùng theo ñònh lyù baûo toaøn thoâng tin

Giaû söû bieåu thöùc treân ñuùng ôû böôùc i = k nghóa laø ta coù:

r = r.Q1|><|r.Q2|><|r.Q3..... |><|r.Qk |><|r.Qkm (1)

ta phaûi chöùng minh r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m

Vôùi Qkm ñöôïc taùch thaønh hai löôïc ñoà con Qk+1 vaø Qk+1m theo ñuùng ñieàu kieän cuûa tính chaát baûo toaøn thoâng tin nghóa neáu s laø quan heä cuûa Qkm thì s = s.Qk+1|><|s.Qk+1m

r.Qkm = (r.Qkm).Qk+1|><|(r.Qkm).Qk+1m = r.Qk+1|><|r.Qk+1m

r = r.Q1|><|r.Q2|><|r.Q3.....|><|r.Qk|><|r.Qk+1|><|r.Qk+1m

ivThuaät toaùn kieåm tra pheùp taùch keát noái baûo toaøn thoâng tin

(a)Thuaät toaùn

Döõ lieäu vaøo: löôïc ñoà quan heä Q(A1,A2,…An), taäp phuï thuoäc haøm F, pheùp taùch =(Q1,Q2,…,Qk).

Döõ lieäu ra: keát luaän pheùp taùch  coù phaûi laø pheùp taùch baûo toaøn thoâng tin ?


  1. Thieát laäp baûng vôùi k+1 doøng, n+1 coät . Coät j öùng vôùi thuoäc tính Aj (j=1...n), haøng i öùng vôùi löôïc ñoà quan heä Qi(i=1…k). Taïi ví trí haøng i, coät j ta ñieàn kyù hieäu Aj neáu Aj  Qi, neáu khoâng ta ñaët kyù hieäu bt vaøo vò trí ñoù. (vôùi t ñaàu tieân baèng 1) vaø sau ñoù taêng t leân moät ñôn vò.

  2. Xeùt laàn löôït caùc phuï thuoäc haøm trong F, aùp duïng cho baûng vöøa môùi thaønh laäp ôû treân. Giaû söû xeùt (X  Y)  F, chuùng ta tìm nhöõng haøng gioáng nhau ôû taát caû caùc thuoäc tính cuûa X, neáu thaáy nhöõng haøng nhö vaäy ta seõ laøm cho caùc kyù hieäu cuûa hai haøng naøy baèng nhau ôû taát caû caùc thuoäc tính cuûa Y. Khi laøm cho 2 kyù hieäu naøy baèng nhau, neáu moät trong hai kyù hieäu laø aj thì cho kyù hieäu kia trôû thaønh aj, neáu hai kyù hieäu laø bk hoaëc bl thì coù theå cho chuùng trôû thaønh bt hoaëc bt (vôùi t = min (k,l)). Böôùc naøy ñöôïc tieáp tuïc cho caùc phuï thuoäc haøm coøn laïi cuûa F cho ñeán khi khoâng coøn aùp duïng ñöôïc nöõa.

  3. Xeùt baûng keát quaû, neáu thaáy trong baûng naøy coù moät haøng chöùa toaøn aj (i=1..n) thì keát luaän ñoù laø pheùp keát noái baûo toaøn thoâng tin, ngöôïc laïi laø pheùp keát noái maát maùt thoâng tin.


Chuù yù: moät ñieàu quan troïng caàn phaûi nhôù laø khi cho hai kyù hieäu baèng nhau thì phaûi cho baèng nhau ôû taát caû caùc xuaát hieän cuûa chuùng trong baûng chöù khoâng phaûi chæ cho baèng nhau ôû nhöõng kyù hieäu trong phaïm vi caùc phuï thuoäc X  Y  F.
Ví duï 11: Vôùi Q(ABCDE)

Q1 = (AD),Q2 =(AB), Q3 =(BE), Q4 =(CDE), Q5 =(AE)

F = {AC,BC,AD,DEC,CEA}

Kieåm tra tính baûo toaøn thoâng tin cuûa pheùp phaân raõ Q thaønh Q1,Q2,Q3,Q4,Q5.




Böôùc 1:

a1

a2

a3

a4

a5




Böôùc 2:

Ñieàn b1,b2,b3, ...




A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1







a4







Q1(AD)

a1

b1

b2

a4

b3

Q2(AB)

a1

a2













Q2(AB)

a1

a2

b4

b5

b6

Q3(BE)




a2







a5




Q3(BE)

b7

a2

b8

b9

a5

Q4(CDE)







a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1










a5




Q5(AE)

a1

b12

b13

b14

a5




Söûa baûng giaù trò ñeå noù thoûa AC

Söûa b4,b13 thaønh b2






Söûa baûng giaù trò ñeå noù thoûa BC

Söûa b8 thaønh b2






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

b2

a4

b3




Q1(AD)

a1

b1

b2

a4

b3

Q2(AB)

a1

a2

b2

b5

b6




Q2(AB)

a1

a2

b2

b5

b6

Q3(BE)

b7

a2

b8

b9

a5




Q3(BE)

b7

a2

b2

b9

a5

Q4(CDE)

b10

b11

a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1

b12

b2

b14

a5




Q5(AE)

a1

b12

b2

b14

a5




Söûa baûng giaù trò ñeå noù thoûa AD

Söûa b5,b14 thaønh a4






Söûa baûng giaù trò ñeå noù thoûa DEC

söûa b2 thaønh a3  söûa taát caû b2 thaønh a3






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

b2

a4

b3




Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

b2

a4

b6




Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

b7

a2

b2

b9

a5




Q3(BE)

b7

a2

a3

b9

a5

Q4(CDE)

b10

b11

a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1

b12

b2

a4

a5




Q5(AE)

a1

b12

a3

a4

a5




Söûa baûng giaù trò ñeå noù thoûa CEA

Söûa b7,b10 thaønh a1.






Laàn löôït xeùt laïi caùc phuï thuoäc haøm trong F, neáu baûng giaù trò chöa thoûa phuï thuoäc haøm naøo thì tieáp tuïc laøm cho noù thoûa.

Söûa baûng giaù trò ñeå noù thoûa AD






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

a3

a4

b3




Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

a3

a4

b6




Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

a1

a2

a3

b9

a5




Q3(BE)

a1

a2

a3

a4

a5

Q4(CDE)

a1

b11

a3

a4

a5




Q4(CDE)

a1

b11

a3

a4

a5

Q5(AE)

a1

b12

a3

a4

a5




Q5(AE)

a1

b12

a3

a4

a5

Doøng thöù Q3(BE) cuûa baûng chöùa toaøn giaù trò aj (j=1..n) neân pheùp phaân raõ treân laø baûo toaøn thoâng tin.


(b)Ñònh lyù

Baûng keát quaû cuûa thuaät toaùn treân cho pheùp ta keát luaän ñöôïc tính baûo toaøn hay khoâng baûo toaøn thoâng tin cuûa pheùp taùch.

Chöùng minh:

Ta chöùng minh neáu baûng keát quaû thuaät toaùn khoâng coù haøng chæ chöùa toaøn giaù trò a thì pheùp taùch khoâng baûo toaøn thoâng tin. Thaät vaäy:

Ta xaây döïng moät quan heä r coù caùc giaù trò nhö baûng keát quaû cuûa thuaät toaùn, caùc haøng laø caùc boä. Quan heä r thoûa taäp phuï thuoäc F vì thuaät toaùn ñaõ söûa caùc giaù trò cuûa r ñeå noù khoûi vi phaïm caùc phuï thuoäc haøm trong F  r laø moät quan heä cuûa löôïc ñoà Q. Ta taùch quan heä r thaønh caùc quan heä ri vôùi ri = r.Qi vaø duøng pheùp keát töï nhieân ñeå keát chuùng laïi. Neáu:



  • k Qk+Qi+ =  i  r1|><|r2....|><|rk khoâng toàn taïi  pheùp taùch khoâng baûo toaøn thoâng tin.

  • i,k Qi+Qk+ = Xik   maø moãi ri ñeàu coù moät boä ti chöùa toaøn a  caùc ti noái ñöôïc vôùi nhau vì coù cuøng giaù trò treân Xik  coù moät boä tr1|><|r2....|><|rk coù toaøn giaù trò a, boä naøy laïi khoâng coù trong r  r  r1|><|r2....|><|rk  pheùp taùch khoâng baûo toaøn thoâng tin.

Ta chöùng minh neáu baûng keát quaû thuaät toaùn coù haøng chæ chöùa toaøn giaù trò a thì pheùp taùch baûo toaøn thoâng tin. Ta chöùng minh ñieàu naøy qua 2 böôùc:

  • Böôùc 1: chöùng minh neáu tr tr1|><|r2....|><|rk. Suy ra rr1|><|r2....|><|rk.

Giaû söû t=(a1,...,an) r . Ta taùch quan heä r thaønh caùc ri = r.Qi vôùi ti = t.Qi. Coù hai tröôøng hôïp:

    • i,k Qi+Qk+ = Xik    caùc ti noái ñöôïc vôùi nhau vì coù cuøng giaù trò treân Xik  boä tr1|><|r2....|><|rk  r  r1|><|r2....|><|rk.

    • k Qk+Qi+ =  i. Suy ra baûng kieåm tra baûo toaøn thoâng tin ôû giai ñoaïn chöa thoûa caùc phuï thuoäc haøm, coù daïng:




A1

A2

...

AK

AK+1

...

Q1










bk1

bk2

b..

Q2










b..

...

...

...










b..

...

...

QK(AK,AK+1,..)

b..

b..

b..

ak

ak+1

...

Vôùi moïi XQ+ tk.X  ti.X vôùi ik neân khi laøm baèng caùc giaù trò theo caùc phuï thuoäc haøm XY thì caùc giaù trò b ôû doøng Qk khoâng thay ñoåi coøn caùc giaù trò b ôû caùc coät Ak,Ak+1,... khoâng ñoåi thaønh a ñöôïc. Suy ra baûng keát quaû cuûa thuaät toaùn khoâng bao giôø chöùa doøng coù toaøn giaù trò a. Vaäy tröôøng hôïp k Qk+Qi+ =  i khoâng xaûy ra khi baûng kieåm tra baûo toaøn thoâng tin coù moät doøng toaøn a.

  • Böôùc 2: chöùng minh neáu tr1|><|r2....|><|rk tr. Suy ra r1|><|r2....|><|rkr.

Giaû söû t=(a1,...,an) r1|><|r2....|><|rk theo ñònh nghóa suy ra i tiri sao cho t.Qi+ = ti. Nhöng ri=r.Qi+  ti’r sao cho ti’.Qi+=ti=t.Qi+i . Tröôøng hôïp xaáu nhaát laø caùc ti’laø caùc doøng khaùc nhau. Trong tröôøng hôïp naøy, ta coù theå xem ti’laø doøng Qi cuûa baûng kieåm tra baûo toaøn thoâng tin vôùi caùc giaù trò b xem nhö chöa bieát. Nhöng caùc doøng Qi phaûi thoûa caùc phuï thuoäc haøm trong F, pheùp laøm baèng caùc giaù trò theo caùc phuï thuoäc haøm ñaõ daàn daàn xaùc ñònh ñöôïc taát caû caùc giaù trò b cuûa moät doøng ti’naøo ño,ù laø doøng coù toaøn giaù trò a. Vaäy coù moät i’ ñeå ti’= t  tr  r  r1|><|r2....|><|rn (2)

(1) vaø (2)  r = r1|><|r2....|><|rn. Noùi caùch khaùc pheùp taùch baûo toaøn thoâng tin.


2Pheùp taùch baûo toaøn phuï thuoäc haøm (decompositions that preserve dependencies)

iTaäp phuï thuoäc haøm Fi cuûa Qi


Phaàn treân chæ ñeà caáp vaán ñeà taùch moät löôïc ñoà quan heä Q(A1,A2,…An)thaønh caùc löôïc ñoà con Q1,Q2,…,Qk coøn khoâng ñeà caäp ñeán taäp phuï thuoäc haøm cuûa caùc löôïc ñoà con naøy. Neáu Q(A1,A2,…An) laø löôïc ñoà quan heä, F phuï thuoäc haøm, =(Q1,Q2,…,Qk)laø pheùp phaân raõ baûo toaøn thoâng tin, ri laø quan heä cuûa Qi thì tính chaát sau thoûa:

  • ri chæ thoûa caùc phuï thuoäc haøm XYF+ vôùi XYQi+

Noùi caùch khaùc, taäp phuï thuoäc haøm cuûa Qi chính laø Fi coù Fi+={XYF+| XYQi+}. Ta coù theå hieåu F ñöôïc phaân raõ thaønh caùc F1,...,Fk

Chöùng minh tính chaát treân:

Do ri ñöôïc taùch töø r maø r thoûa F+  ri thoûa caùc phuï thuoäc haøm XYF+ vôùi XYQi+.Theo ñònh nghóa phuï thuoäc haøm, ñöông nhieân ri khoâng thoûa caùc phuï thuoäc haøm XYF+ vôùi XYQi+. Ngoaøi ra ri khoâng thoûa baát kyø moät phuï thuoäc haøm naøo XYF+ . Thaät vaäy neáu coù XY nhö vaäy thì r = r1|><|r2....|><|rn cuõng phaûi thoûa XYF+. Ñieàu naøy maâu thuaãn vôùi ñònh nghóa cuûa taäp F+ .


iiÑònh nghóa:


Cho phaân raõ  =(Q1,Q2,…,Qk) cuûa moät löôïc ñoà quan heä, vaø moät taäp phuï thuoäc haøm F. Hình chieáu cuûa F treân moät taäp caùc thuoäc tính Qi+ kyù hieäu Qi(F) laø taäp caùc phuï thuoäc haøm X  Y  F+ sao cho XY  Z.

Qi(F)=Fi+={ X  Y| X  Y  F+ vaø XY  Qi}

Ta noùi phaân raõ  baûo toaøn taäp phuï thuoäc haøm F neáu

F   Qi(F)  F+ = ( Qi(F))+ vôùi i=1..k


Heä quaû: F+  ( Qi(F))+ vôùi i=1..k

Nhaän xeùt: töø heä quaû treân ta suy ra: ñeå xaùc ñònh pheùp phaân raõ  =(Q1,Q2,…,Qk) coù baûo toaøn phuï thuoäc haøm hay khoâng, vôùi moãi phuï thuoäc haøm XYF ta xaùc ñònh xem noù coù laø thaønh vieân cuûa taäp phuï thuoäc haøm G =  Qi(F) hay khoâng. Ta khoâng caàn xaùc ñònh chieàu ngöôïc laïi.
Ví duï12: Cho löôïc ñoà quan heä Q(A,B,C) vaø F={AB,BC,CA}. Pheùp phaân raõ =(Q1,Q2) taùch Q thaønh hai löôïc ñoà quan heä Q1(A,B) vaø Q2(B,C). Haõy tính hình chieáu cuûa F treân Q1+ vaø Q2+­­.Pheùp phaân raõ coù baûo toaøn phuï thuoäc haøm F khoâng?

Giaûi: veà nguyeân taéc ta coù theå giaûi baøi toaùn theo caùc böôùc döôùi ñaây

Böôùc 1: Keâ taát caû taäp con cuûa Q+




A

B

C






A

B

C










AB

AC










BC













ABC





Böôùc 2: Tính bao ñoùng cuûa caùc taäp con cuûa Q+­­

=

A+=ABC

B+

=ABC

C+

=ABC







AB+

=ABC

AC+

=ABC
















BC+

=ABC
















ABC+

=ABC




Böôùc 3: Tính F+

AB

BA

CA

ABABC

ACB

BCA

AAB

BAB

CB

ABC

ACAB

BCAB

AC

BC

CAB

ABBC

ACBC

BCAC

AAC

BAC

CAC

ABABC

ACABC

BCABC

ABC

BBC

CBC










AABC

BABC

CABC










Böôùc 4: Tính Q1(F), Q2(F)

Q1(F)= F1+ ={AB,AAB,BA,BAB}{AB,BA} (chæ laáy pth coù veá phaûi 1 tt)

Q2(F)= F2+ ={BC,BBC,CB,CBC}{BC,CB}(chæ laáy pth coù veá phaûi 1 tt)

Böôùc 5:

G = Q1(F)Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}

F={AB,BC,CA} coù AB, BC ñeàu laø thaønh vieân cuûa G, coøn CA coù laø thaønh vieân cuûa G hay khoâng ta tính CG+. CG+=ABC  CA cuõng laø thaønh vieân cuûa G. Vaäy pheùp phaân raõ treân baûo toaøn phuï thuoäc haøm.
Baøi toaùn treân coù theå ñöôïc giaûi theo caùc böôùc ñôn giaûn sau cho töøng löôïc ñoà quan heä con:

Ví duï12: Cho löôïc ñoà quan heä Q(A,B,C) vaø F={AB,BC,CA}. Pheùp phaân raõ =(Q1,Q2) taùch Q thaønh hai löôïc ñoà quan heä Q1(A,B) vaø Q2(B,C). Haõy tính hình chieáu cuûa F treân Q1+ vaø Q2+­­.Pheùp phaân raõ coù baûo toaøn phuï thuoäc haøm F khoâng?

Tính cho Q1



Böôùc 1: Keâ taát caû taäp con cuûa Q1+




A

B



A

B







AB

Böôùc 2: Tính bao ñoùng cuûa caùc taäp con cuûa Q1+­­

=

A+=ABC

B+

=ABC







AB+

=ABC

Böôùc 3: Tính F1+=Q1(F)

AB

BA

AAB

BAB

Tính cho Q2

Böôùc 4: Keâ taát caû taäp con cuûa Q2+




B

C



B

C







BC

Böôùc 5: Tính bao ñoùng cuûa caùc taäp con cuûa Q2+­­

=

B+=ABC

C+

=ABC







BC+

=ABC

Böôùc 6: Tính F2+=Q2(F)

BC

CB

BBC

CBC

Böôùc 7:

G=Q1(F)Q2(F)={AB,AAB,BA,BAB,BC,BBC,CB,CBC}

F={AB,BC,CA} coù AB, BC ñeàu laø thaønh vieân cuûa G coøn CA coù laø thaønh vieân cuûa G hay khoâng ta tính CG+. CG+=ABC  CA cuõng laø thaønh vieân cuûa G. Vaäy pheùp phaân raõ treân baûo toaøn phuï thuoäc haøm.

iiiYÙ nghóa cuûa phaân raõ coù baûo toaøn phuï thuoäc haøm


Ví duï 13: Cho löôïc ñoà quan heä Q(C,S,Z) vaø F={CSZ,ZC}. Pheùp taùch =(Q1,Q2) taùch Q thaønh hai löôïc ñoà Q1(S,Z) vaø Q2(C,Z). Hoûi pheùp taùch coù baûo toaøn phuï thuoäc haøm khoâng?

Giaûi:

Q1 coù caùc taäp thuoäc tính con:






S

Z



S

Z







SZ

Bao ñoùng cuûa caùc taäp thuoäc tính con Q1+

=

S+=S

Z+

=ZC







SZ+

=CSZ

F1+ chæ goàm caùc phuï thuoäc haøm hieån nhieân vì taát caû caùc phuï thuoäc haøm sau ñeàu khoâng thoûa:

ZC

SZC

ZZC

SZCS




SZCZ




SZCSZ

Q2 coù caùc taäp thuoäc tính con:




C

Z



C

Z







CZ

Bao ñoùng cuûa caùc taäp thuoäc tính con Q2+

=

C+=C

Z+

=ZC







CZ+

=CZ

F2+ goàm caùc phuï thuoäc:

ZC

ZZC

Q1(F)Q2(F)={ZC,ZZC}{ZC} khoâng töông ñöông vôùi F = {CSZ,ZC}



Vaäy pheùp phaân raõ treân khoâng baûo toaøn phuï thuoäc haøm, ñieàu naøy coù nghóa khi ta ñöa döõ lieäu vaøo Q1 vaø Q2 sao cho khoâng vi phaïm phuï thuoäc haøm hình chieáu cuûa noù, nhöng khi keát noái chuùng laïi thì döõ lieäu keát quaû cuûa löôïc ñoà quan heä Q laïi vi phaïm phuï thuoäc haøm CSZ

Q1(F)={PTHHN}

Q2(F)={ZC, ZZC}

F={CSZ,ZC}

Q1

(S

Z)

Q2

(C

Z)

Q

(C

S

Z)




s1

z1




c1

z1




c1

s1

z1




s1

z2




c1

z2




c1

s1

z2

ivThuaät toaùn kieåm tra baûo toaøn phuï thuoäc haøm


Thuaät toaùn tìm bao ñoùng cuûa taäp thuoäc tính X ñoái vôùi G =  Qi(F)

Vaøo:  =(Q1,Q2,…,Qk),F,X

Ra: XG+

Böôùc 1: Vôùi moãi phuï thuoäc haøm XYF ta thöïc hieän töø böôùc 2 ñeán böôùc 4

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

Böôùc 3: theá Z’ = Z’((Z’)+)

Böôùc 4: neáu ôû Qi, Z’thay ñoåi thì thöïc hieän laïi böôùc 3 cho Qñaàu tieân

Ngöôïc laïi keát thuùc thuaät toaùn vaø traû veà Z’(laø bao ñoùng XG+)
Thuaät toaùn kieåm tra baûo toaøn phuï thuoäc haøm

Vaøo:  =(Q1,Q2,…,Qk),F

Ra: keát luaän pheùp taùch  baûo toaøn hay khoâng baûo toaøn phuï thuoäc haøm

Böôùc 1: Vôùi moãi phuï thuoäc haøm XYF ta thöïc hieän töø böôùc 2 ñeán böôùc 3:

Böôùc 2: Tìm bao ñoùng XG+ vôùi G =  Qi(F)

Böôùc 3: Neáu Y  XG+ thì XY Qi(F)+

Böôùc 4: Neáu taát caû phuï thuoäc XYF ñeàu thuoäc Qi(F)+ thì ta keát luaän phaân raõ  baûo toaøn phuï thuoäc haøm ngöôïc laïi  khoâng baûo toaøn phuï haøm
Ví duï 14: thöïc hieän laïi ví duï 13, nghóa laø kieåm tra pheùp taùch coù baûo toaøn phuï thuoäc haøm khoâng?
Vaøo: Q(C,S,Z),F={CSZ,ZC},Q1(S,Z) vaø Q2(C,Z)

Ñöông nhieân ZCG = Q1(F)Q2(F) ZC  (Q1(F)Q2(F))+



  1. Z’=CS

  2. gaùn Z’= Z’((Z’)+ ): Z’ = CS(SSZ)=CS

Böôùc 1 vaø 2 coù Z’ khoâng thay ñoåi, ta sang löôïc ñoà Q2 vaø tính tieáp Z’

  1. gaùn Z’= Z’((Z’)+ ): Z’ = CS(CCZ)=CS

Z’khoâng thay ñoåi vaø heát löôïc ñoà quan heä  ngöng khoâng tính tieáp Z’

  1. Vaäy =CS CSZ  (Q1(F)  Q2(F))+ pheùp phaân raõ khoâng baûo toaøn phuï thuoäc haøm.

Ví duï 15: thöïc hieän laïi ví duï 12 vôùi noäi dung keát luaän pheùp taùch  coù baûo toaøn phuï thuoäc haøm khoâng (khoâng tính F+)

Vaøo: Q(A,B,C),F={AB,BC,CA},Q1(A,B) vaø Q2(B,C)

Hieån nhieân G = Q1(F)  Q2(F)  {AB,BC}



Ta xaùc ñònh CA coù thuoäc (Q1(F)  Q2(F))+

  1. Z’=C

  2. gaùn Z’= Z’((Z’)+ ): Z’ = C(AB)=C

Böôùc 1 vaø 2 coù Z’ khoâng thay ñoåi, ta sang löôïc ñoà Q2 vaø tính tieáp Z’

  1. gaùn Z’= Z’((Z’)+ ): Z’ = C(ABCBC)=BC

Z’thay ñoåi  tính tieáp Z’baét ñaàu töø löôïc ñoà Q1

  1. gaùn Z’= Z’((Z’)+ ): Z’ = BC(ABCAB)=ABC

do Z’=Q+  Z’ seõ khoâng bao giôø thay ñoåi.

  1. vaäy =ABC  CA(Q1(F)  Q2(F))+ pheùp phaân raõ baûo toaøn phuï thuoäc haøm.
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