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
-
X Y F r thoûa X Y X Y F+
-
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 YF+
(1) vaø (2) X Y G+ F+ G+
-
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:
-
Luaät phaûn xaï (reflexive rule): X X
-
Luaät theâm vaøo (augmentation rule): Cho X Y XZ Y
-
Luaät hôïp (union rule): Cho X Y, X Z X YZ
-
Luaät phaân raõ (decomposition rule): Cho X YZ X Y
-
Luaät baéc caàu (transitive rule): Cho X Y, Y Z X Z
-
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:
(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 AX+
X++ X+. AÙp duïng 1 X++ X+
...............................................
7. X A1 vaø X A2 X A1A2 .... XAi = 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 YZ 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û -
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
-
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
-
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
-
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 = XY 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.
Chia sẻ với bạn bè của bạn: |