Bài giảng Chương 4: Lý thuyết thiết kế cơ sở dữ liệu

Bài giảng cung cấp cho người học các kiến thức: Lý thuyết thiết kế cơ sở dữ liệu, khái niệm phụ thuộc hàm, tính bao đóng, bao đóng của tập thuộc tính, phụ thuộc hàm tương đương,... Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. Mời các bạn cùng tham khảo chi tiết nội dung bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 4: Lý thuyết thiết kế cơ sở dữ liệuChương4:LýThuyếtThiếtKéCơSởDữ LiệuI. KháiNiệmPhụthuộcHàm1. ĐịnhNghĩa:làkháiniệmquantrọngnhấttrongviệc thiếtkếcơsởdữliệu choquanhệRtrêntậpthuộctínhU R(U) +vớiU={A1,A2,A3…An} x,y,zlàtậpconcủaU xynếumọit&t’ t.x=t’.xt.y=t’.y • Vídụ: x={masv} y={hoten,ngaysinh}=>xy2.HệtiênđềAmstronga. đ/nhệtiênđềamstrongGọiR(U)làlượcđồquanhệvớiU={A1,…,An}làtậpcácthuộctính. X,Y,Z,W U.HệtiênđềArmstrongbaogồm:F1)Tínhphảnxạ:Y X XYF2)Tínhbắccầu:XY,YZ XZF3)Tínhmởrộnghaivế(tăngtrưởng)XY (Z U)XZYZ • b.bổđề.Bổđề1:HệtiênđềArmstronglàđúng.CónghĩalàFlàtậpcácphụ thuộchàmđúngtrênquanhệR.NếuX Ylàmộtphụ thuộchàmđượcsuydẫntừFnhờhệtiênđềArmstrong thìXYlàđúngtrênquanhệR.Bổđề2:F4)CộngtínhởvếphảI(luậthợp)XY,XZ XYZF5)Tínhtựabắccầu(giảbắccầu)XY,YZW XZWF6)Luậttách:X  Y Z X  Z và x  y Vídụ:Cho tập phụ thuộc hàm F = {A  B, B  CD} ta chứng minhphụthuộchàmACCDđượcsuydiễnlogictừF.Thậtvậy:F3:AB ACBCF3:BCD BCCD F3:ACBC,BCCD ACCDVídụ2:choR={A,B,C,D,E} F={ABC,BD,CE} CMR:AE,ADVídụ3:choR={ABCDEF} F={ABC,ABD,ACE,DEF,FAD) CMR:AE,FDE 3.Tínhbaođónga. Baođóngcủaphụthuộchàma.Địnhnghĩa:ChotậpphụthuộchàmFtrêntậpthuộctínhU.BaođóngcủaF,kýhiệulàF+, làtậpnhỏnhấtcácphụthuộchàmtrênUthoả: F+={XY|F|==XY}b.Địnhnghĩakhácchobaođóngcủatậpphụthuộchàm:F+ làtậpcácphụthuộcsuydiễntừFnhờhệtiênđềArmstrong.Tứcnóphải thoảhaitínhchấtsau:F+ FKhiápdụngcáctínhchấtF1,F2,F3choF+ takhôngthuđượcphụthuộchàm nàonằmngoàiF+.c.Tínhchất:(1):Tínhphảnxạ:F+ F(2):Tínhđơnđiệu:F G F+ G+(3):Tínhlũyđẳng:(F+)+=F+(4):(FG)+ F+G+(5):(F+G)+=(FG+)+=(FG)+ b.Baođóngcủatậpthuộctínha.Địnhnghĩa:ChotậpphụthuộchàmFtrêntậpthuộctínhUvàX U.Baođóngcủatập thuộctínhX(đốivớiF),kýhiệuX+,làtậpsau: X+={A|XA F+}b.Địnhnghĩakhácchobaođóngcủatậpthuộctính:X+làtậpcácthuộctínhAsaochoXAcóthểsuydiễnđượctừFbằnghệ tiênđềArmstrong.c.Tínhchất:(1):Tínhphảnxạ:X+ X(2):Tínhđơnđiệu:X Y X+ Y+(3):Tínhlũyđẳng:(X+)+=X+(4):(XY)+ X+Y+(5):(X+Y)+=(XY+)+=(XY)+(6):XY Y X+(7):XY Y+ X+(8):XX+vàX+X(9):X+=Y+ XY,YX 4.phụthuộchàmtươngđương kháiniệmChoR={A1,A2….An}CholượcđồquanhệRvàcáctậpphụthuộchàmFvàGtrênRtanói:FphủphụthuộchàmGnếuG+ F+FtươngđươngphụthuộchàmGnếuG+=F+ĐểxácđịnhphụthuộchàmY Z G+ haykhôngtasửdụngthuậttoántính baođóngtậpthuộctínhđểtínhY+ đốivớiGvàkiểmtraxemZ Y+ hay không.Mệnhđề:F G+ F+ G+Mệnhđề: MỗitậpphụthuộchàmFtươngđươngvớitậpphụthuộchàmG gồmcácphụthuộchàmmàvếphảichỉcó1thuộctính. b.Phủtốitiêu:ĐểtốiưuhơnnữaviệcthiếtkếlượcđồCSDLquanhệtayêucầumạnhhơnđốivớitập phụthuộchàmtươngđương.Địnhnghĩa: TậpphụthuộchàmFgọilà phụthuộchàm tốithiểu nếu nóthoảmãncác điềukiệnsau:(1):VếphảicủamỗiphụthuộchàmtrongFchỉcó1thuộctính.(2):MọiphụthuộchàmX A Flàquantrọng,tứclàtậpphụthuộchàmcótừFbằng sựloạibỏphụthuộchàmXA: F{XA}khôngtươngđươngvớiF.(3):VớimỗiphụthuộchàmX A F,mọithuộctínhB Xđềuquantrọng,tứclàtập phụthuộchàmcótừFbằngviệcthayphụthuộchàmX Abởiphụthuộchàm(X {B})A: (F{XA}) {X{B}A}khôngtươngđươngvớiF.Nhận xét: Điều kiện (2) đảm bảo không có phụ thuộc hàm dư thừa, điều kiện (3) đảm bảokhôngcóthuộctínhởvếtráidưthừa. Thuậttoántìmphủtốithiểu:Input:TậpphụthuộchàmF.Output:TậpphụthuộchàmtốithiểuGtươngđươngvớiF.Method:(1):PhânrãvếphảitấtcảphụthuộchàmcủaFvàgọiGlàtậptấtcảcácphụthuộc hàmthuđược.(2):LoạicácphụthuộchàmdưthừatrongG:KhôngtồntạiXAnàotrongFmàtập F{XA}tươngđươngvớiF.(3):Loạicácthuộctínhdưthừa ởvếtráicủacácphụthuộchàmtrongG:Khôn ...