Thuật toán tìm chuỗi suy diễn

Trước tiên mời các bạn cùng mình thống nhất vấn đề sau :Nếu ta có : B Í A và B C thì A A,CTa có điều trên là vì : B Í A = A B (luật phản xạ)mà : B C (giả thiết)suy ra : A C (luật bắc cầu)suy ra : A A,C (luật tăng trưởng)Bài toán tìm chuỗi suy diễn :Cho tập phụ thuộc hàm (PTH) F={f1,f2,...,fm}.Tìm chuỗi suy diễn X Y nào đó.Để thực hiện thuật toán này ta cần một mảng mà mỗi phần tử của mảng có cấutrúc như sau :{tập thuộc tính...
Nội dung trích xuất từ tài liệu:
Thuật toán tìm chuỗi suy diễn ThuậttoántìmchuỗisuydiễnTrướctiênmờicácbạncùngmìnhthốngnhấtvấnđềsau:Nếutacó:B⊆ AvàB>CthìA>A,CTacóđiềutrênlàvì:B⊆A=>A>B(luậtphảnxạ) mà:B>C(giảthiết) suyra:A>C(luậtbắccầu) suyra:A>A,C(luậttăngtrưởng)Bàitoántìmchuỗisuydiễn:Chotậpphụthuộchàm(PTH)F={f1,f2,...,fm}.TìmchuỗisuydiễnX>Ynàođó.Đểthựchiệnthuậttoánnàytacầnmộtmảngmàmỗiphầntửcủamảngcócấutrúcnhưsau:{tậpthuộctính1;tậpcácphụthuộchàm;tậpthuộctính2}Đểđơngiản,đầutiêncácbạnhãytìmbaođóngcủaXtrênF,kýhiệulà(X)+F.NếuY⊄(X)+FthìthuậttoánkếtthúcvàthôngbáorằngkhôngcóchuỗisuydiễnX>YNếungượclạicácbạnthựchiệnnhưsau:TapTT_dangxet=X {TapTT_dangxetsẽlưutrữtậpthuộctínhđangxétởmỗibước }WhileY⊄TapTT_dangxet B1:TìmcácPTHtrongFcóvếtráichứatrongTapTT_dangxet B2:TapTT_suyra=TapTT_dangxet∪{Tậpcácthuộctínhcó trongvếphảicủacácPTHtìmđượcởbướctrên} B3:Lưutrữvàomảngnhưsau{TapTT_dangxet;chỉsốcácPTH tìmđượcởbước1trongF;TapTT_suyra} B4:LoạibỏrakhỏiFcácPTHtìmđượcởbước1 B5:TapTT_dangxet=TapTT_suyraEndWhileXincácbạnngừngthuậttoánởđâymộtchútđểmìnhcómộtvàighichú:ThựcchấttoànbộvònglặpWhileởtrênchínhlàđitìmbaođóngcủaXtrongFTạimỗibướclặpthìTapTT_suyrachínhlàbaođóngcủaTapTT_dangxetởbướclặpđó,hayrõhơnđóchínhlàcácthuộctínhcóthểsuyrađượctừTapTT_dangxetởmỗibướclặp.Tacóđượcđiềunàychínhlànhờvàovấnđềđãbànởđầu(B⊆ 1AvàB>CthìA>A,C)vàluậthợpcủatiênđềArmstrong(nếutìmđượcnhiềuhơn1PTHởbước1).Đếnđâythìphầnchínhcủathuậttoánxemnhưđãxong,chúngtasẽquaphầntrìnhbày:DuyệttoànbộmảngtừphầntửđầuđếnphầntửcuốiTạimỗiphầntửtasẽtrìnhbàyđượcmộtPTHlà:Tập_thuộc_tính_1>Tập_thuộc_tính_2,kèmtheolờigiảithíchlàtađãsửdụngnhữngPTHnàotrongF(thôngquachỉsốcácPTHtrongFđãđượcchuẩnbịtrước)kếthợpvớilờigiảithíchB⊆ AvàB>CthìA>A,CvàluậthợpcủaArmstrong(nếusốlượngPTHsửdụng>1)CácbạnđểýrằngtạibướcsauthìTậpthuộctính1chínhlàTậpthuộctính2củabướctrước.Nênđếnsaubướccuốicùng,tadựavàoluậtbắccầuvàphânrãđểđưarakếtluậnX>Y.Vídụcụthể:ChotậpPTHF={X>Y(f1);Y>W(f2);W,Y>Z(f3)}TìmchuỗisuydiễnX>ZChạytaynhưsau:Lầnlặp1:{X;f1;XY},F={Y>W(f2);W,Y>Z(f3)}Lầnlặp2:{XY;f2;XYW},F={W,Y>Z(f3)}Lầnlặp3:{XYW;f3;XYWZ},F=∅Trìnhbày:X>X,YdoX⊆ XvàX>Y(f1)thìX>X,YX,Y>X,Y,WdoY⊆ X,YvàY>W(f2)thìX,Y>X,Y,WX,Y,W>X,Y,W,ZdoW,Y⊆ X,Y,WvàW,Y>Z(f3)thìX,Y,W>X,Y,W,ZCuốicùngdựatrênluậtbắccầu,tacó: X>X,Y,W,ZDựatrênluậtphânrãtacó: X>ZMộtvídụkhác:ChotậpPTHF={X>Y(f1);Y>W(f2);W,Y>Z(f3);X>K(f4)}TìmchuỗisuydiễnX>Z 2Chạytaynhưsau:Lầnlặp1:{X;f1f4;XYK},F={Y>W(f2);W,Y>Z(f3)}Lầnlặp2:{XYK;f2;XYKW},F={W,Y>Z(f3)}Lầnlặp3:{XYKW;f3;XYKWZ},F=∅Trìnhbày:X>X,Y,KdoX⊆ XvàX>Y(f1)thìX>X,Y doX⊆ XvàX>K(f4)thìX>X,K doluậthợp:X>X,Y,KX,Y,K>X,Y,K,WdoY⊆ X,Y,KvàY>W(f2)thìX,Y,K>X,Y,K,WX,Y,K,W>X,Y,K,W,ZdoW,Y⊆ X,Y,K,WvàW,Y>Z(f3)thìX,Y,K,W>X,Y,K,W,ZCuốicùngdựatrênluậtbắccầu,tacó: X>X,Y,K,W,ZDựatrênluậtphânrãtacó: X>ZCuốicùng,xinthầyvàcácbạngópý,chỉnhsửađểchúngtacóthểgiảiquyếtbàitoánnàymộtcáchhoànthiện. ThuậttoánchiếuF+xuốngcáclượcđồconThuậttoánnàyhoàntoànkhôngbịphụthuộcvàobấtkỳthuậttoántáchmộtlượcđồquanhệthànhcáclượcđồconnào.Cũngnhưtrêntrướctiênmìnhphảicùngvớicácbạnthốngnhấtmộtvấnđề(đểchứngminhvấnđềnàytachủyếusửdụngcáctiênđềArmstrong)ChoR(A1,A2,...,An),F={f1,f2,...,fm}GiảsửbaođóngcủaA1trênF,kýhiệu:(A1)+F={Ai1,Ai2,...,Aik}Vậytacóđược2k1phụthuộchàmcótínhchấtsau: - VếtráilàA1 - Vếphảilầnlượtlàcáctậphợpconcácthuộctínhcủa(A1)+F(trừtậprỗng)vàcácphụthuộchàmnàyđềunằmtrongF+. 3Saukhiđãthốngnhấtvấnđềtrên,xinmờicácbạnxemquathuậttoán:ChoR(A1,A2,...,An),F={f1,f2,...,fm}GiảsửtađãtáchđượcRthà ...