Bài giảng Cơ sở dữ liệu: Chương 5 - ThS. Hồ Đắc Quán

Bài giảng chương 5 trang bị cho người học những hiểu biết về phụ thuộc hàm và một số ứng dụng. Sau khi học xong chương này người học có thể nắm bắt được định nghĩa phụ thuộc hàm, một số tính chất của phụ thuộc hàm - hệ luật dẫn Armstrong, biết được bao đóng của tập phụ thuộc hàm F và của tập thuộc tính X,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu: Chương 5 - ThS. Hồ Đắc Quán MônCƠSỞDỮLIỆU Chương5:PhụthuộchàmvàmộtsốứngdụngNộidung 1.PHỤTHUỘCHÀM  ĐịnhNghĩaPhụThuộcHàm  Mộtsốtínhchấtcủaphụthuộchàmhệluậtdẫn armstrong 2.BAOĐÓNGCỦATẬPPHỤTHUỘCHÀMF&CỦA TẬPTHUỘCTÍNHX  BaođóngcủatậpphụthuộchàmF  BaođóngcủatậpthuộctínhX 3.THUẬTTOÁNTÌMBAOĐÓNGF+VÀX+,BÀI TOÁNTHÀNHVIÊN  Bàitoánthànhviên  ậttoántìmbaođóngcủamộttậpthuộctính(X) Thu 2Nộidung(tt) 4.PHỦTỐITHIỂUCỦAMỘTTẬPPHỤTHUỘCHÀM  TậpPhụThuộcHàmTốiThiểu  TậpPhụThuộcHàmTươngĐương  ThuậtToánTìmPhủTốiThiểuCủaMộtTậpPhụThuộcHàm 5.KHÓACỦALƯỢCĐỒQUANHỆMỘTSỐTHUẬTTOÁN TÌMKHÓA  ĐịnhNghĩa  ThuậttoántìmmộtkhóacủamộtlượcđồquanhệQ  ThuậtToánTìmTấtCảCácKhóaCủaMộtLượcĐồQuanHệ 6.DẠNGCHUẨNCỦALƯỢCĐỒQUANHỆ  Dạngchuẩn1,2,3  DạngchuẩnBoyceCodd 31.PHỤTHUỘCHÀM Phụthuộchàm(functionaldependancy)làmộtcôngcụdùngđể biểudiễnmộtcáchhìnhthứccácràngbuộctoànvẹn.ĐịnhNghĩaPhụThuộcHàm CholượcđồquanhệQvới{A1,A2,…,An}làtậpcácthuộctính.X, YlàhaitậpconkhácrỗngcủaQ. TanóiXxácđịnhY(hayYphụthuộchàmvàoX)nếuvớirlàmột quanhệtrênQvànếuhaibột1,t2bấtkỳthuộcrmàt1.X=t2.X==> t1.Y=t2.Y.KhiđótakýhiệulàX Y PhụthuộchàmX Xđượcgọilàphụthuộchàmhiểnnhiên. ngườitathườngdùngFđểchỉtậpcácphụthuộchàmđịnhnghĩa trênQ.VìQhữuhạnnênFcũnghữuhạn,tacóthểđánhsốcácphụ thuộchàmcủaFlàf1,f2,..,fm. Quyướcrằngchỉcầnmôtảcácphụthuộchàmkhônghiểnnhiên trongtậpF(cácphụthuộchàmhiểnnhiênđượcngầmhiểulàđãcó trongF}. 41.PHỤTHUỘCHÀM(tt)Mộtsốtínhchấtcủaphụthuộchàmhệluậtdẫnarmstrong Đểcóthểxácđịnhđượccácphụthuộchàmkháctừtậpphụthuộc hàmđãcó,tadùnghệtiênđềArmstrong(1974),gồmcácluậtsau:vớiX,Y,Z,W Q+1. Luậtphảnxạ: X X2. Luậtthêmvào: X Y ==>XZ YZ3. Luậtbắccầu: X Y,Y Z==>X Z4. Luậtbắccầugiả: ChoX Y,WY Z==>XW Z5. Luậthợp: ChoX Y,X Z==>XYZ6. Luậtphânrã: ChoX Y,Z Y==>X Z(cáchệtiênđề1,2,3đượcgọichunglàHệluậtdẫnArmstrong) 52.BAOĐÓNGBaođóngcủatậpphụthuộchàmF BaođóngcủatậpphụthuộchàmF(thườngkýhiệulàF+)làtập hợptấtcảcácphụthuộchàmcóthểsuyratừFdựatrêncáctiênđề Armstrong.Vídụ:ChorlàquanhệtrênlượcđồquanhệQ(A,B,C,D)vàtậpF đượcchonhưsau:F={A B;B C;A D;B D}khiđóF+={A B;B C;A D;B D;A BD;A BCD;A C;A CD;A BC;B CD;….}RõràngF F+ CáctínhchấtcủatậpF+ Tínhphảnxạ:VớimọitậpphụthuộchàmF+taluônluôncóF F+ Tínhđơnđiệu:NếuF GthìF+ G+ Tínhlũyđ ẳng:VớimọitậpphụthuộchàmFtaluônluôncóF++=F+. 62.BAOĐÓNG(tt)BaođóngcủatậpthuộctínhX ChorlàquanhệtrênlượcđồquanhệQ.giảsửF làtậpcácphụthuộchàmtrongQ,X Q+.BaođóngcủatậpthuộctínhXđốivớiFkýhiệulà X+(hoặcX+F)làtậptấtcảcácthuộctínhAcủaQ đượcsuyratừXdựavàohệtiênđềArmstrongvà cácphụthuộchàmtrongF.X+={A:A QvàX A F+} 72.BAOĐÓNG(tt)BaođóngcủatậpthuộctínhX–VídụQ(A,B,C,D,E,G);F={A C;A EG;B D;G E};X={A,B};Y={C,G,D}Thì X+={A,B,C,D,E,G}; Y+={C,G,D,E}TươngtựnhưtậpbaođóngcủatậpPTHF+,tậpbao đóngX+cũngchứacácphầntửcủaX+,tứclàX X+. 82.BAOĐÓNG(tt)BaođóngcủatậpthuộctínhX–VídụNếuX,YlàcáctậpconcủatậpthuộctínhQthìtacó cáctínhchấtsauđây: Tínhphảnxạ: X X+ Tínhđơnđiệu: NếuX YthìX+ Y+ Tínhlũyđẳng: X++=X+ (XY)+ X+Y+ (X+Y)+=(XY+)+=(X+Y+)+ X Y F+ Y X+ X Y Y+ X+ X X+vàX+ X X+=Y + X YvàY X 93.TTTÌMBAOĐÓNGF+VÀX+Bàitoánthànhviên TrênđâytanhậnthấyrằngX+đượcđịnhnghĩathôngqua F+.Mộtvấnđềquantrọngkhinghiêncứulýthuyết CSDLlà:ChotrướctậpcácPTHFvàmộtphụthuộchàm f,cóhaykhôngmộtkhẳngđịnhf F+?bàitoánnàyđược gọilàbàitoánthànhviên. Đểtrảlờicâuhỏinày(bà ...