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



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

IIHEÄ LUAÄT DAÃN ARMSTRONG (Armstrong inference rule)


Ngöôøi ta thöôøng duøng F ñeå chæ taäp caùc phuï thuoäc haøm cuûa löôïc ñoà quan heä Q. Ta coù theå ñaùnh soá caùc phuï thuoäc haøm cuûa F laø f1, f2, .., fm. Quy öôùc raèng chæ caàn moâ taû caùc phuï thuoäc haøm khoâng hieån nhieân trong taäp F (caùc phuï thuoäc haøm hieån nhieân ñöôïc ngaàm hieåu laø ñaõ coù trong F).

1Phuï thuoäc haøm ñöôïc suy dieãn logic töø F


Noùi raèng phuï thuoäc haøm X  Y ñöôïc suy dieãn logic töø F neáu moät quan heä r thoûa maõn taát caû caùc phuï thuoäc haøm cuûa F thì cuõng thoûa phuï thuoäc haøm X  Y. Kyù hieäu F|= X  Y.

Bao ñoùng cuûa F kyù hieäu F+ laø taäp taát caû caùc phuï thuoäc haøm ñöôïc suy dieãn logic töø F.

Caùc tính chaát cuûa taäp F+

1. Tính phaûn xaï: Vôùi moïi taäp phuï thuoäc haøm F+ ta luoân luoân coù F  F+

2. Tính ñôn ñieäu: Neáu F  G thì F+  G+

3. Tính luõy ñaúng: Vôùi moïi taäp phuï thuoäc haøm F ta luoân luoân coù (F+)+ = F+.

Goïi G laø taäp taát caû caùc phuï thuoäc haøm coù theå coù cuûa r, phaàn phuï cuûa F kyù hieäu F  = G - F+



Chöùng minh

  1. X  Y  F  r thoûa X  Y  X  Y  F+

  2. Neáu X  Y laø phuï thuoäc haøm thuoäc F+ ta phaûi chöùng minh X  Y thuoäc G+

Giaû söû r thoûa taát caû caùc phuï thuoäc haøm cuûa G (1)

 r thoûa taát caû phuï thuoäc haøm cuûa F vì F  G

 r thoûa phuï thuoäc haøm X  Y (2) vì X  YF+

(1) vaø (2)  X  Y  G+  F+  G+­­



  1. F  F+ (tính phaûn xaï)  F+  (F+)+ (1)

Neáu X  Y  (F+)+ (2) X  Y  F+ thaät vaäy: (3)

Giaû söû r thoûa taát caû caùc phuï thuoäc haøm cuûa F (4)

 r thoûa taát caû caùc phuï thuoäc haøm cuûa F+ (theo ñònh nghóa)

 r thoûa taát caû caùc phuï thuoäc haøm cuûa (F+)+ (theo ñònh nghóa)

 r thoûa X  Y (vì (2))  X  Y  F+­­

(1) vaø (3)  (F+)+ = F+


2Heä luaät daãn Armstrong


Heä luaät daãn laø moät phaùt bieåu cho bieát neáu moät quan heä r thoûa maõn moät vaøi phuï thuoäc haøm thì noù phaûi thoûa maõn phuï thuoäc haøm khaùc.

Vôùi X,Y,Z,W laø taäp con cuûa Q+. r laø quan heä baát kyø cuûa Q. Ta coù 6 luaät daãn sau:



  1. Luaät phaûn xaï (reflexive rule): X  X

  2. Luaät theâm vaøo (augmentation rule): Cho X  Y XZ Y

  3. Luaät hôïp (union rule): Cho X  Y, X  Z X YZ

  4. Luaät phaân raõ (decomposition rule): Cho X  YZ X Y

  5. Luaät baéc caàu (transitive rule): Cho X  Y, Y  Z X Z

  6. Luaät baéc caàu giaû (pseudo transitive rule): Cho X  Y, YZ  W XZ W

Heä tieân ñeà Armstrong (Armstrong’s Axioms) goàm 3 luaät: (1), (2) vaø (5)

Chöùng minh

Vôùi t1,t2 laø hai boä baát kyø cuûa quan heä r.

Luaät phaûn xaï: Ta coù (t1.X = t2.X  t1.X = t2.X) theo ñònh nghóa suy ra X  X

Luaät theâm vaøo: giaû söû coù t1.XZ = t2.XZ (1)

 t1.X = t2.X

 t1.Y = t2.Y (do X  Y) (2)

 XZ  Y (do (1)  (2))

Luaät hôïp: giaû söû coù t1.X = t2.X (1)

 t1.X = t2.X vaø t1.Z = t2.Z

 t1.XZ = t2.XZ (2)

 X  YZ (do (1)  (2))

Luaät phaân raõ: gæa söû coù: t1.X = t2.X (1)

 t1.YZ = t2.YZ (do X  YZ)

 t1.Y = t2.Y (2)

 X  Y (do (1)  (2))

Luaät baéc caàu: giaû söû coù t1.X = t2.X (1)

 t1.Y = t2.Y

 t1.Z = t2.Z (2)

 X  Z (do (1)  (2))

Luaät baéc caàu giaû: giaû söû coù: t1.XZ = t2.XZ (1)

 t1.X = t2.X vaø t1.Z = t2.Z (2)

 t1.Y = t2.Y (do X  Y) (3)

 t1.YZ = t2.YZ (Keát hôïp (2) vaø (3))

 t1.W = t2.W (do YZ  W) (4)

 XZ  W

Trong 6 luaät treân, chæ caàn 3 luaät 1, 2 vaø 6 laø ñuû, nghóa laø caùc luaät coøn laïi coù theå suy daãn töø ba luaät naøy.


iHeä luaät daãn Armstrong laø ñuùng


Noùi raèng X  Y laø phuï thuoäc haøm ñöôïc suy dieãn nhôø vaøo luaät daãn Armstrong neáu toàn taïi caùc taäp phuï thuoäc haøm F0  F1 ...  Fn sao cho X  Y  Fn vôùi F0,F1,...,Fn laàn löôït ñöôïc hình thaønh thoûa phöông phaùp sau:

Böôùc 1: F0 = F

Böôc 2:choïn moät soá phuï thuoäc haøm trong Fi aùp duïng heä luaät daãn Armstrong ñeå thu ñöôïc moät soá phuï thuoäc haøm môùi. Ñaët Fi+1= Fi  {caùc phuï thuoäc haøm môùi}

Ví duï: Cho F = {AB  C,C  B,BC  A} thì coù F0  F1  F2 sao cho C  A  F2

F0 = {AB  C,C B, BC  A} aùp duïng luaät hôïp cho C  B vaø C  C

F1 = {AB  C,C  B, BC A, C BC} aùp duïng luaät baéc caàu.

F2 = {AB  C,C  B, BC  A, C BC, C  A}


Heä quaû: Heä luaät daãn Armstrong laø ñuùng nghóa laø neáu F laø taäp caùc phuï thuoäc haøm ñuùng treân quan heä r vaø X  Y laø moät phuï thuoäc haøm ñöôïc suy dieãn töø F nhôø heä luaät daãn Armstrong thì X  Y ñuùng treân quan heä r. Vaäy X  Y laø phuï thuoäc haøm ñöôïc suy dieãn logic töø F
Phaàn tieáp theo chuùng ta seõ chöùng minh heä luaät daãn Armstrong laø ñaày ñuû, nghóa laø moïi phuï thuoäc haøm X  Y ñöôïc suy dieãn logic töø F seõ ñöôïc suy dieãn töø F nhôø heä luaät daãn Armstrong.

iiBao ñoùng cuûa taäp thuoäc tính X (closures of attribute sets)

(a)Ñònh nghóa

Q laø löôïc ñoà quan heä, r laø quan heä töông öùng, F laø taäp caùc phuï thuoäc haøm trong Q. X,Ai laø caùc taäp con cuûa Q+.

Bao ñoùng cuûa taäp thuoäc tính X ñoái vôùi F kyù hieäu laø X+ (hoaëc ) ñöôïc ñònh nghóa nhö sau:

X+ =  Ai vôùi X  Ai laø phuï thuoäc haøm ñöôïc suy dieãn töø F nhôø heä tieân ñeà Armstrong

Tính chaát:

  • bao ñoùng cuûa Q laø Q+
(b)Caùc tính chaát cuûa bao ñoùng

Neáu X,Y laø caùc taäp con cuûa taäp thuoäc tính Q+ thì ta coù caùc tính chaát sau ñaây:

1. Tính phaûn xaï: X  X+

2. Tính ñôn ñieäu: Neáu X  Y thì X+  Y+

3. Tính luõy ñaúng: X++ = X+

4. (XY)+  X+Y+

5. (X+Y)+ = (XY+)+ = (X+Y+)+

6. X  Y  Y+  X+

7. X  X+ vaø X+  X

8. X+ = Y+  X  Y vaø Y  X

Chöùng minh:

1. X  X  X+  X

2. A  X+  X  A  Y  A  A  Y+

3. A  X++  X+  A vaø X  X+ (aùp duïng 8)  X  A  AX+

 X++  X+. AÙp duïng 1  X++  X+

...............................................

7. X  A1 vaø X A2  X  A1A2 .... XAi = X+

X+  X  X+  X (Phuï thuoäc haøm hieån nhieân)

...............................................


(c)Thuaät toaùn tìm bao ñoùng

Tính lieân tieáp taäp caùc taäp thuoäc tính X0,X1,X2,... theo phöông phaùp sau:

Böôùc 1: X0 = X

Böôùc 2: laàn löôït xeùt caùc phuï thuoäc haøm cuûa F

Neáu YZ coù Y  Xi thì Xi+1 = Xi  Z

Loaïi phuï thuoäc haøm Y  Z khoûi F

Böôùc 3: Neáu ôû böôùc 2 khoâng tính ñöôïc Xi+1 thì Xi chính laø bao ñoùng cuûa X

Ngöôïc laïi laëp laïi böôùc 2

Ví duï 1:

Cho löôïc ñoà quan heä Q(ABCDEGH) vaø taäp phuï thuoäc haøm F

F = { f1: B  A

f2: DA  CE

f3: D  H

f4: GH  C

f5: AC  D }

Tìm bao ñoùng cuûa caùc taäp X = {AC} döïa treân F.



Giaûi:

Böôùc 1: X0 = AC

Böôùc 2: Do f1, f2, f3, f4 khoâng thoûa. f5 thoûa vì X+  AC

X1 = AC  D = ACD

Laäp laïi böôùc 2: f1 khoâng thoûa, f2 thoûa vì X1  AD:

X2 = ACD  CE = ACDE

f3 thoûa vì X2  D

X3 = ACDE  H = ACDEH

f4 khoâng thoûa, f5 khoâng xeùt vì ñaõ thoûa

Laäp laïi böôùc 2: f2,f3 khoâng xeùt vì ñaõ thoûa, f1,f4 khoâng thoûa,f5 khoâng xeùt vì ñaõ thoûa.Trong böôùc naøy X3 khoâng thay ñoåi => X+=X3={ACDEH} laø bao ñoùng cuûa X



Ví du 2ï:

Q(A,B,C,D,E,G)

F = {f1: A  C;

f2: A  EG;

f3: B  D;

f4: G  E}

X = {A,B}; Y = {C,G,D}

Keát quaû:

X+ = {ABCDEG}

Y+ = {CGDE}

(d)Ñònh lyù

Thuaät toaùn tìm bao ñoùng cho keát quaû Xi = X+

Chöùng minh

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

Böôùc cô sôû chöùng minh X  X0

Theo tính phaûn xaï cuûa heä luaät daãn thì X  X theo thuaät toaùn thì X0 = X  X  X0

Vaäy X0  X+

Böôùc qui naïp giaû söû coù X  Xi-1 ­ (1) ta phaûi chöùng minh X  Xi

Theo thuaät toaùn tìm bao ñoùng thì coù fj = Xj  Yj ñeå Xi-1  Xj vaø Xi = Xi-1  Yj

 Xi-1  Yj (2).(1)vaø (2)  X  Yj (3)

(1) vaø (3)  X Xi-1Yj = Xi  X  Xi

Vaäy Xi  X+­­

2. Ta chöùng minh A  X+  A  Xi ñeå keát luaän Xi  X+

A  X+ neân coù moät phuï thuoäc haøm X  A. Theo thuaät toaùn tìm bao ñoùng thì X  Xi  A Xi


(e)Heä quaû

  1. Q laø löôïc ñoà quan heä. F laø taäp phuï thuoäc haøm, A laø thuoäc tính chæ xuaát hieän ôû veá phaûi cuûa caùc phuï thuoäc haøm trong F thì X+ = (X – A)+  A

  2. Q laø löôïc ñoà quan heä. F laø taäp phuï thuoäc haøm, X laø taäp con cuûa Q+ vaø Y = {caùc thuoäc tính xuaát hieän ôû veá phaûi cuûa caùc phuï thuoäc haøm trong F} thì X+  X  Y.

Chöùng minh

  1. Theo thuaät toaùn tìm bao ñoùng thì bao ñoùng X+ hay (X-A)+ ñöôïc hình thaønh qua moät soá böôùc. Ta chöùng minh bieåu thöùc X+ = (X – A)+  A theo qui naïp.

Böôùc cô sôû: X0 = X, (X-A)0 = X - A  X0 =(X - A)0  A ñuùng

Böôùc qui naïp: giaû söû ta coù Xi-1 =(X - A)i-1  A. Bao ñoùng Xi ñöôïc hình thaønh do coù fj = Xj  Yj ñeå:

Xi-1  Xj vaø Xi = Xi-1  Yj = (X - A)i-1  A  Yj (1).

Söï hình thaønh Xi luoân keùo theo söï hình thaønh (X-A)i vì:

Xi-1 = (X - A)i-1 ­­­ A  Xj do Xj khoâng chöùa A neân:

(X - A)i-1  Xj vaäy (X - A)i = (X - A)i-1  Yj (2)

(1) vaø (2) cho:

Xi = (X - A)i  A laø ñieàu phaûi chöùng minh


  1. Böôùc cô sôû: X0 = X  X0  X  Y

Böôùc qui naïp: giaû söû coù Xi-1  X  Y ta chöùng minh Xi  X  Y.

Bao ñoùng Xi ñöôïc hình thaønh do coù fj = Xj  Yj ñeå:

Xi-1  Xj vaø Xi = Xi-1  Yj  X  Y  Yj­­ do Yj laø veá phaûi cuûa phuï thuoäc haøm neân Y  Yj = Y vaäy Xi  X  Y

3Heä luaät daãn Armstrong laø ñaày ñuû

iÑònh lyù


Heä luaät daãn Armstrong laø ñaày ñuû nghóa laø moïi phuï thuoäc haøm X Y ñöôïc suy dieãn logic töø F seõ ñöôïc suy dieãn töø F nhôø heä luaät daãn Armstrong.

Chöùng minh:

Ñeå chöùng minh X  Y ñöôïc suy dieãn töø F nhôø heä luaät daãn Armstrong ta chöùng minh baèng phöông phaùp phaûn chöùng nghóa laø neáu X  Y khoâng suy dieãn ñöôïc töø heä luaät daãn Armstrong thì coù quan heä r thoûa caùc phuï thuoäc haøm F nhöng khoâng thoûa phuï thuoäc haøm X  Y (ñieàu naøy nghòch lyù vôùi giaû thuyeát laø moïi quan heä r thoûa caùc phuï thuoäc haøm trong F thì r cuõng thoûa phuï thuoäc haøm X  Y).

Thaät vaäy giaû söû Q(A1,A2,...,An) laø löôïc ñoà quan heä, ai,bi laø caùc giaù trò khaùc nhau treân mieàn giaù trò Ai. r laø quan heä treân Q coù hai boä t vaø t’ñöôïc xaùc ñònh nhö sau:

t=(a1,a2,...,an)



Vaäy quan heä r coù t.X = t’.X nhöng t.Y  t’.Y (t.Y goàm caùc giaù trò ai coøn t’.Y phaûi coù ít nhaát moät bi neáu khoâng Y  X+  X  Y ñöôïc suy daãn töø heä luaät daãn Armstrong ). Nhö vaäy r khoâng thoûa phuï thuoäc haøm X  Y.

Baây giôø ta chöùng minh quan heä r thoûa moïi phuï thuoäc haøm trong F. Goïi W  Z laø phuï thuoäc haøm trong F.

Neáu W  X+  t.W  t’.W  meänh ñeà (t.W = t’.W  t.Z = t’.Z)ñuùng

Neáu W  X+  t.Z = t’.Z = boä caùc ai

 meänh ñeà (t.W = t’.W  t.Z = t’.Z)ñuùng


iiHeä quaû:


Bao ñoùng cuûa taäp thuoäc tính X ñoái vôùi F laø:

X+ =  Ai vôùi X  Ai laø phuï thuoäc haøm ñöôïc suy dieãn logic töø F

Tính chaát

X Y F+ Y X+

Chöùng minh

X  Y  coù k sao cho Y = Ak   Ai = X+

Y  X+  X+ = Y  (X+ - Y)  X  Y  (X+ - Y)  X  Y

Baøi toaùn thaønh vieân

Noùi raèng X  Y laø thaønh vieân cuûa F neáu X  Y  F+

Moät vaán ñeà quan troïng khi nghieân cöùu lyù thuyeát CSDL laø khi cho tröôùc taäp caùc phuï thuoäc haøm F vaø moät phuï thuoäc haøm X  Y, laøm theá naøo ñeå bieát X  Y coù thuoäc F+ hay khoâng baøi toaùn naøy ñöôïc goïi laøø baøi toaùn thaønh vieân. Ñeå traû lôøi caâu hoûi naøy ta coù theå tính F+ roài xaùc ñònh xem X  Y coù thuoäc F+ hay khoâng. Vieäc tính F+ laø moät coâng vieäc ñoøi hoûi thôøi gian vaø coâng söùc. Tuy nhieân, thay vì tính F+ chuùng ta coù theå duøng thuaät toaùn sau ñeå xaùc ñònh X  Y coù laø thaønh vieân cuûa F hay khoâng. Thuaät toaùn naøy söû duïng tính chaát vöøa chöùng minh treân.

Thuaät toaùn xaùc ñònh f = XY coù laø thaønh vieân cuûa F hay khoâng

Böôùc 1: tính X+

Böôùc 2: so saùnh X+ vôùi Y neáu X+­­­  Y thì ta khaúng ñònh X  Y laø thaønh vieân cuûa F

Baïn ñoïc haõy naém thaät kyõ thuaät toaùn naøy – noù môû ñaàu cho moät loaït öùng duïng veà sau.


1   ...   7   8   9   10   11   12   13   14   ...   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