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

Chương 6 cung cấp cho người học những kiến thức về chuẩn hóa cơ sở dữ liệu. Các nội dung chính được trình bày trong chương này gồm có: Phép kết nối bảo toàn thông tin, phép tách bảo toàn phụ thuộc hàm, cách tiếp cận phân rã để thiết kế CSDL, cách tiếp cận tổng hợp để thiết kế CSDL.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu: Chương 6 - ThS. Hồ Đắc QuánMônCƠSỞDỮLIỆUChương6:Chuẩnhóa cơsởdữliệuNộidung 1.PHÉPKẾTNỐIBẢOTOÀNTHÔNGTIN  CơSởLýThuyết  ThuậtToánKiểmTraTínhKếtNốiBảoToàn ThôngTin 2.PHÉPTÁCHBẢOTOÀNPHỤTHUỘCHÀM  Cơsởlýthuyết  Thuậttoán 3.CÁCHTIẾPCẬNPHÂNRÃĐỂTHIẾTKẾCSDL 4.CÁCHTIẾPCẬNTỔNGHỢPĐỂTHIẾTKẾCSDL 21.PHÉPKẾTNỐIBẢOTOÀNT.TINCơSởLýThuyếtNếuQlàmộtlượcđồquanhệđượctáchthànhcác lượcđồconQ1,Q2,...,QkvàFlàtậpphụthuộc hàm,nóirằngphéptách(phânrã)làphéptáchcó bảotoànthôngtinđốivớiFnếuvớimỗiquanhệr trênQthỏaF:Q= Q1(r)* Q2(r)*..* Qk(r)Tứclàrđượctạonêntừphépkếtnốitựnhiêncủa cáchìnhchiếucủanótrênQi(i=1..k) 31.PHÉPKẾTNỐIBẢOTOÀNTT(tt)ThuậtToánKiểmTraTínhKếtNốiBảoToànThôngTin Dữliệuvào:LượcđồquanhệQ(A1,A2,…An)vàtậpcácphụ thuộchàmF,phéptách={Q,Q,…,Qk}. Dữliệura:Phéptáchcóbảotoànthôngtinhaykhông?(1)Thiếtlậpbảngvớik+1dòng,n+1cột.Cộtjứngvớithuộctính AJ(i=1...n),hàngiứngvớilượcđồquanhệQi(i=1…k).Tạivítrí hàngi,cộtjtađiềnkýhiệuAjnếuAJQi,Đầutiênđặtt=1vàđặtvàocácôcònlạicủabảngkýhiệubttheo chiềutừtráisangphảivàtừtrênxuốngdưới,sauđótăngtlênmột đơnvịvàlặplạithaotácđiềnbtnhưtrên.Chođếnkhimọiôcủa bảngđiềuđãcókýhiệu.(2)XétlầnlượtcácphụthuộchàmtrongF,ápdụngchobảngvừamới thànhlậpởtrên.Giảsửxét(XY)F,chúngtatìmnhữnghàng giốngnhauởtấtcảcácthuộctínhcủaX,nếuthấynhữnghàng nhưvậytasẽlàmchocáckýhiệucủahaihàngnàybằngnhauởtất cảcácthuộctínhcủaY. 41.PHÉPKẾTNỐIBẢOTOÀNTT(tt)ThuậtToánKiểmTraTínhKếtNốiBảoToànThôngTin(tt)Khilàmcho2kýhiệunàybằngnhau,tagặp3trườnghợpsauđây: nếumộttronghaikýhiệulàAJthìchokýhiệukiatrởthànhAJ, nếuhaikýhiệulàbkhoặcblthìcóthểchochúngtrởthànhbthoặc bt(vớit=min(k,l)), nếucảhaikýhiệulàajthìgiữnguyên(lúcđóchỉsốjcủacácký hiệunàyphảigiốngnhau)Chúýrằngbướcnàycóthểđượclặplại(chocácphụthuộchàm)cho đếnkhikhôngcònápdụngđượcnữa(nghĩalàchođếnkhinàoở mộtlầnduyệtquatấtcảcácphụthuộchàmtrongFmàbảngkhông cósựthayđổinào.(3)Xétbảngkếtquả,nếuthấytrongbảngnàycómộthàngchứatoàn aj(i=1..n)thìkếtluậnđólàphéptáchbảotoànthôngtin,ngượclại thìlàphéptáchm ấtmátthôngtin. 51.PHÉPKẾTNỐIBẢOTOÀNTT(tt) Vídụ: 62.PHÉPTÁCHBẢOTOÀNPTHCơsởlýthuyết Chophânrãp={Q1,Q2,…Qk}củamộtlượcđồquanhệ,vàtậpphụ thuộchàmF.HìnhchiếucủaFtrênmộttậpcácthuộctínhZký hiệu Z(Q)làtậpcácphụthuộchàmX Y F+saochoXY Z.TanóiphânrãpbảotoàntậpphụthuộchàmFnếuhợpcủatất cảcácphụthuộchàmtrongQi(F)vớii=1..ksuyrađượctấtcảcác phụthuộchàmtrongF. LýdopcầnbảotoàntậpFđólàvìcácphụthuộchàmtrongFcó thểđượcxemlàcácràngbuộctoànvẹnchoquanhệQ.Nếucác phụthuộchìnhchiếukhôngsuyrađượcFthìkhibiểudiễnQqua p,chúngtacóthểthấyrằnggiátrịhiệnhànhcủacácQibiểudiễn mộtquanhệQkhôngthỏaF,ngaycảnếuplàphéptáchkhôngmất thôngtinứngvớiF.KhiđómỗithaotáccặpnhậttrênmỗiRisẽ cầnphảithựchiệnmộtphépnốiđểkiểmtralạirằngcácràng buộckhôngbịviphạm. Dữliệuvào:Mộtphânrãp={Q1,Q2,…Qk}vàmộttậpcácphụthuộc hàmF(f1,f2,…,fm} Dữliệura:phéptáchpcób ảotoànphụthuộchàmhaykhông? 72.PHÉPTÁCHBẢOTOÀNPTH(tt)Phéptáchbảotoànphụthuộchàm Vềnguyêntắc,chúngtacóthểdễdàngkiểmtraxemmột phânrãp={Q1,Q2,…Qk}cóbảotoàntậpphụthuộcF haykhông.ChúngtachỉcầntínhF+rồichiếunótrêntất cảcácthànhphầnQi.Sauđólấyhợpcủacáctậpphụ thuộckếtquảrồikiểmraxemtậpnàycótươngđương vớiFhaykhông? Tuynhiêntrongthựctế,tínhF+làmộtcôngviệchếtsức khókhănvìsốlượngcácphụthuộcchứatrongnóthường làhàmmũtheokíchthướccủaF.Nhưngcómộtcáchđể kiểmtratínhbảotoànnàymàkhôngcầnphảitínhF+; phươngphápnàycóchiphíthờigiantỷlệvớihàmđa 82.PHÉPTÁCHBẢOTOÀNPTH(tt)Thuậttoán ChúngtagọiGlàhợpcủacácQi(F),đểtínhxemGcótương đươngvớiFhaykhôngchúng ...