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

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)

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

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

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

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

Neáu r = r.Q₁|><|r.Q_2­­ ta noùi pheùp taùch (Q₁,Q₂) 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₁⁺ Q₂⁺ = X

Q₁⁺ Q₂⁺ = Q⁺

Noùi raèng löôïc ñoà quan heä Q ñöôïc taùch thaønh hai löôïc ñoà con Q₁, Q₂ theo pheùp taùch (Q₁,Q₂) 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.Q₁r.Q₂

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 Q₁,Q₂

iiTính chaát

Thì r = r.Q₁r.Q₂

t  r  t₁r₁ t₁ = t.Q₁ t₂r₂ t₂ = t.Q₂ t₁.X = t₂.X = t.X

 t  r.Q₁r.Q_2­­ (Theo ñònh nghóa)

t  r.Q₁r.Q_2­­  t  r_­­

t  r.Q₁r.Q_2­­  t₁r₁ t₁ = t.Q₁ (1)

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

(1) vaø (2)  t’.Q₁ = t.Q₁  t’.X = t.X  t’.Q₂ = t.Q_2­­ (do X  Q_2­­)

 t’ = t  t  r

Ví duï 10: cho Q(SAIP), Q₁ =(SA) , Q₂ =(SIP) F={SA,SIP}. Hoûi vieäc taùch Q thaønh Q₁ vaø Q₂ 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ù

Q₁⁺  Q₂⁺ = S

Q₁⁺  Q₂⁺ = SAIP = Q⁺

S  SA = Q₁⁺ _­­

Theo tính chaát treân, vôùi moïi quan heä r cuûa Q ta luoân coù r = r.Q₁r.Q₂. 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 Q₁, Q₂, Q₃...,Q_n 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.Q₁|><|r.Q₂|><|r.Q₃..... |><|r.Q_n

Chöùng minh:

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

ÔÛ böôùc i = 1 thì r = r.Q₁|><|r.Q_1m ñ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.Q₁|><|r.Q₂|><|r.Q₃..... |><|r.Q_k |><|r.Q_km (1)

ta phaûi chöùng minh r = r.Q₁|><|r.Q₂|><|r.Q₃.....|><|r.Q_k|><|r.Q_k+1|><|r.Q_k+1m

Vôùi Q_km ñöôïc taùch thaønh hai löôïc ñoà con Q_k+1 vaø Q_k+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 Q_km thì s = s.Q_k+1|><|s.Q_k+1m 

r.Q_km = (r.Q_km).Q_k+1|><|(r.Q_km).Q_k+1m = r.Q_k+1|><|r.Q_k+1m 

r = r.Q₁|><|r.Q₂|><|r.Q₃.....|><|r.Q_k|><|r.Q_k+1|><|r.Q_k+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

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 A_j (j=1...n), haøng i öùng vôùi löôïc ñoà quan heä Q_i(i=1…k). Taïi ví trí haøng i, coät j ta ñieàn kyù hieäu A_j neáu A_j  Q_i, neáu khoâng ta ñaët kyù hieäu b_t 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ø a_j thì cho kyù hieäu kia trôû thaønh a_j, neáu hai kyù hieäu laø b_k hoaëc b_l thì coù theå cho chuùng trôû thaønh b_t hoaëc b_t (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 a_j (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.
   

Q₁ = (AD),Q₂ =(AB), Q₃ =(BE), Q₄ =(CDE), Q₅ =(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 Q₁,Q₂,Q₃,Q₄,Q₅.

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öù Q₃(BE) cuûa baûng chöùa toaøn giaù trò a_j (j=1..n) neân pheùp phaân raõ treân laø baûo toaøn thoâng tin.

(b)Ñònh lyù

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ä r_i vôùi r_i = r.Q_i vaø duøng pheùp keát töï nhieân ñeå keát chuùng laïi. Neáu:

• 
  k Q_k⁺Q_i⁺ =  i  r₁|><|r₂....|><|r_k khoâng toàn taïi  pheùp taùch khoâng baûo toaøn thoâng tin.
  
• 
  i,k Q_i⁺Q_k⁺ = X_ik   maø moãi r_i ñeàu coù moät boä t_i chöùa toaøn a  caùc t_i noái ñöôïc vôùi nhau vì coù cuøng giaù trò treân X_ik  coù moät boä tr₁|><|r₂....|><|r_k coù toaøn giaù trò a, boä naøy laïi khoâng coù trong r  r  r₁|><|r₂....|><|r_k  pheùp taùch khoâng baûo toaøn thoâng tin.
  

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

• 
  i,k Q_i⁺Q_k⁺ = X_ik    caùc t_i noái ñöôïc vôùi nhau vì coù cuøng giaù trò treân X_ik  boä tr₁|><|r₂....|><|r_k  r  r₁|><|r₂....|><|r_k.
  
• 
  k Q_k⁺Q_i⁺ =  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:
  

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

(1) vaø (2)  r = r₁|><|r₂....|><|r_n. 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 F_i cuûa Q_i

Phaàn treân chæ ñeà caáp vaán ñeà taùch moät löôïc ñoà quan heä Q(A₁,A₂,…A_n)thaønh caùc löôïc ñoà con Q₁,Q₂,…,Q_k 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(A₁,A₂,…A_n) laø löôïc ñoà quan heä, F phuï thuoäc haøm, =(Q₁,Q₂,…,Q_k)laø pheùp phaân raõ baûo toaøn thoâng tin, r_i laø quan heä cuûa Q_i thì tính chaát sau thoûa:

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

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

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

Do r_i ñöôïc taùch töø r maø r thoûa F⁺  r_i thoûa caùc phuï thuoäc haøm XYF⁺ vôùi XYQ_i⁺.Theo ñònh nghóa phuï thuoäc haøm, ñöông nhieân r_i khoâng thoûa caùc phuï thuoäc haøm XYF⁺ vôùi XYQ_i⁺. Ngoaøi ra r_i 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 = r₁|><|r₂....|><|r_n 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õ  =(Q₁,Q₂,…,Q_k) 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 Q_i⁺ kyù hieäu _Qi(F) laø taäp caùc phuï thuoäc haøm X  Y  F⁺ sao cho XY  Z.

_Qi(F)=F_i⁺={ X  Y| X  Y  F⁺ vaø XY  Q_i}

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õ  =(Q₁,Q₂,…,Q_k) 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õ =(Q₁,Q₂) taùch Q thaønh hai löôïc ñoà quan heä Q₁(A,B) vaø Q₂(B,C). Haõy tính hình chieáu cuûa F treân Q₁⁺ vaø Q₂^+­­.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)= F₁⁺ ={AB,AAB,BA,BAB}{AB,BA} (chæ laáy pth coù veá phaûi 1 tt)

_Q2(F)= F₂⁺ ={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 C_G⁺. C_G⁺=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õ =(Q₁,Q₂) taùch Q thaønh hai löôïc ñoà quan heä Q₁(A,B) vaø Q₂(B,C). Haõy tính hình chieáu cuûa F treân Q₁⁺ vaø Q₂^+­­.Pheùp phaân raõ coù baûo toaøn phuï thuoäc haøm F khoâng?

Tính cho Q₁

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

	A	B
	A	B
		AB

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

+­=	A+=ABC	B+	=ABC
		AB+	=ABC

Böôùc 3: Tính F₁⁺=_Q1(F)

AB	BA
AAB	BAB

Tính cho Q₂

Böôùc 4: Keâ taát caû taäp con cuûa Q₂⁺

	B	C
	B	C
		BC

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

+­=	B+=ABC	C+	=ABC
		BC+	=ABC

Böôùc 6: Tính F₂⁺=_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 C_G⁺. C_G⁺=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 =(Q₁,Q₂) taùch Q thaønh hai löôïc ñoà Q₁(S,Z) vaø Q₂(C,Z). Hoûi pheùp taùch coù baûo toaøn phuï thuoäc haøm khoâng?

Giaûi:

Q₁ 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 Q₁⁺

+­=	S+=S	Z+	=ZC
		SZ+	=CSZ

F₁⁺ 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

Q₂ 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 Q₂⁺

+­=	C+=C	Z+	=ZC
		CZ+	=CZ

F₂⁺ 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 Q₁ vaø Q₂ 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:  =(Q₁,Q₂,…,Q_k),F,X

Ra: X_G⁺

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 ôû Q_i, 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 X_G⁺)
Thuaät toaùn kieåm tra baûo toaøn phuï thuoäc haøm

Vaøo:  =(Q₁,Q₂,…,Q_k),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 X_G⁺ vôùi G =  _Qi(F)

Böôùc 3: Neáu Y  X_G⁺ 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},Q₁(S,Z) vaø Q₂(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à Q₂ vaø tính tieáp Z’

3. 
   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’

4. 
   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},Q₁(A,B) vaø Q₂(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à Q₂ vaø tính tieáp Z’

3. 
   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à Q₁

4. 
   gaùn Z’= Z’((Z’)⁺  ): Z’ = BC(ABCAB)=ABC
   

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

5. 
   vaäy =ABC  CA(_Q1(F)  _Q2(F))⁺ pheùp phaân raõ baûo toaøn phuï thuoäc haøm.
   

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