Giaùo trình CÔ SÔÛ DÖÕ lieäu trang
IIHEÄ LUAÄT DAÃN ARMSTRONG (Armstrong inference rule)
tải về 1.89 Mb.
|
- Điều hướng trang này:
- 1Phuï thuoäc haøm ñöôïc suy dieãn logic töø F
- 2Heä luaät daãn Armstrong
- (b)Caùc tính chaát cuûa bao ñoùng
- (c)Thuaät toaùn tìm bao ñoùng
- (d)Ñònh lyù
- 3Heä luaät daãn Armstrong laø ñaày ñuû
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öø FNoù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+
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
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+
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 ArmstrongHeä 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:
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ùngNoù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óaQ 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ùngNeá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+
............................................... (c)Thuaät toaùn tìm bao ñoùngTí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}
X+ = {ABCDEG} Y+ = {CGDE}
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+
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+
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û
Chöùng minh
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 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
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
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.
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. Каталог: 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:
|