Luận văn Một số vấn đề về chuẩn hóa cơ sở dữ liệu quan hệ

PHAN I[ : l Y THUVET vE THIET KE cosaDOU~UQUANH~ 1.Yeuc~uthietkecosachIii~u: Taxettill d~sau: NHA_CUNG_CAP( TEN_CONG_TY, D!A_CHI, MAT_HANG, DON GIA ) la 1 lLiQ'cd6 qaun h~ 1u'Utn}thong tin v~ nha cung cap g6m co ten cong ty (TEN_CONG- TY), diachi cuacongty ( D!A_CHI ), nl?t hang( MAT_HANG) W nhacungcap,vadon gia( DON_GIA ) cuanl?thangdo . 1.1.Caedithuang:. (I) Slf du thua: Thongtin 1u'UI?p l<;1inhi~uIan,thl d~dia chi cuanhacungcap duQ'cI?p i<;1inhi~uIanungv6i nhi~um?thangkhacnhau. (ii) Slfkhongb~nvung(ti~mtang) : xayrakhiC?Pnh?tdO'li~u. - Khi thaydoi djachi cuanhacungcapmachidoi0 1 m§.utin va khongthaydoi 0 m§.utin khaccocungnhacungcapsed§.nden1 nhacungcapco nhi~udiachI. - Khithem1 m§.utin m6icocungnhacungcapnhUngkhacdiachi cOngd§.nden 1nhacungcapconhi~udiachi. (iii) Thieu thongtin: - Khi them1 nhacungcap(ten vadjachi) thlkhongthedUavaoduQ'cneukhong com?thangvademgia. (iv)Ma'tthongtin: - Khi xoacac m?thangcUanhacungcapdandenxoamatthongtin v~ten nha cungcapvadjachi. 1.2.Slfpill!thuQcvadi thuang: - Sl/ ph~thuQcva sl/ du thuaco moi quaIlh~ratkha:ngkhlt.Sl/ ph~thuQcla 1 kh~ngdjnh( m~nhd~) chi co 1t?P concuaquaIlh~la II hQ'pI~", phananhdung thegi6i till/CoDo sl/ phananh bj rangbuQctrongqui lu?tdo nen danden hang 10<;1tcac duthuatrongquaIl h~II hQ'pI~". 29 V6i 1 quaIlh~thoamQtsophl)thuQc,v6i mQtsothongtin chotn.i6cchungta co th~SUI'deanmQtsothongtincon I<;\.idlja tren giatri hi~nhanh va slj phl) thuQc. - Thf dv 11.1: NHA CUNG CAP- - TEN_CONG _TY CtyA 8!A_CHI MAT_HANG I 8dN_GIA 15 LythaiT6 001 3.49 CtyA ??? 002 4.19 Ta co th~suydean,qm~utin thCthai, gia tri cua 8!A_CHI la " 15 Ly thai T6 ". 8~tranhcacslj dli th'U'a,tacoth~phanra IliQcdbthanh2 IliQCdbcon: N_CUNG_CAP (TEN_CONG_TY, 8(A_CHI) HANG_CUNG_CAP (TEN_CONG_TY, MAT_HANG, 8dN_GIA) 8~tranhcac di thliangti~mtang,khithayd6itlnhtr<;\.ngquaIlh~taphai ki~mtra th~hi~nquaIlh~d~ dambaacacphl)thuQcdliQcthoa. Do slj phan ra d~tranhdli thLta,call hei d~tra la thongtin chCtatrongIliQcdb phanra co th~phl)chbidliQcdungnhlitlnhtr<;\.ngdliQcIliUnhlitrongIliQcdb ban d~u. Yeuc~uthietkecosadali~ud.n phai: (I) Lo<;\.i be slj dli thLta. (ii)Ki~mtratoithi~unha'td~dambaakhongcodj thliang. (iii) Kh6ngma'tthongtin: thongtin co th~dliQctai t<;\.oW nhCIngthongtin chCta trongIliQcdbcon. Tinhcha't(I)la veuc~ucoban I Tinhcha't(ij) la yellc~ucuaslj phanra IliQcdbbaaloanphl)thuQC Tinhcha't(iii) la yellc~ucuaslj phanrakhongma'thongtin. 30 2.Philnrakhongma'tthongtin ( Lossiess-joindecomposition) 2.1Philnra : Djnh nghia: Cho1u'Q'cdeSquanh~Q(Al,"', Am),Q+={AJ,...,Aml MQtrheinrap cuaQ IiI t~phQp p ={Ql,"', Qk I - Qi la cacquanh~,Qi ~ Q, 1 ::; I::;m ma - Qi kh6ngnhatthietphairoi nhau - Q+lU ...u Q\, =Q+ ThfdV/1.2: Q(A,B,C,D,E) Ta c6 : Ql (A, B,C ) Q2 ( B, C, D ) Q3 (D, E) p={Ql , Q2,Q3 I la1pheinracuaQ. 2.2.Philnrakhongma'thongtin: Djnhnghia( philnreikhongma'thongtin) : Cho1u'Q'cdeSquanh~Q ( Al,..,Am), F IiI t~ppill)thuQchamxacdinhtrenQ, p =I Ql,.." Qk Iia 1 pheinracuaQ. Ta n6i p la 1 pheinreikhongmatthongtincuaQ ( Ongva;F ) neu: V6i mQith~hi~nTQ cuaQ, TQ thoaF ma : TQ =IlQl( TQ ) Ixl ...Ixl IlC?t(TQ ) 23. Anh X<;lchieu kef : 2.3.1. Djnh nghia : ChoIu'QcdeSquanh~Q (Al,..,Aln),va p =I Ql,..., QkIia 1 pheinracuaQ. AnhX<;lchieuketlingv6ipheinrap la : 31 m,,(TQ)=ITQ1(TQ ) Ixl ...Ixl ITQm(TQ ),TQ la th~hi~ncuaQ H~qua: ChoILlQcdaquaIlh~Q (Al,..,Arn),F lat~pphl,)thuQchamxacd[nhtrenQ va p =I Ql,"., Qk}la1phanracuaQ. Ta noi p la 1 phanrakhongmatthongtin cuaQ ( Ctngvai F ) neu: TQ =mp(TQ), TQ lath~hi~ncuaQ, TQ thoaF 2.3.2.Tinh chatcua<iohx~chi~uk~t: Cho ILlQcdaquaIlh~Q ( Al,..,Am),va p ={Ql,..., Qk}Ia 1phanracuaQ. TQ la 1th§ hi~ncuaQ, d~tTQj =TIQitaco : (j) TQ c mp(TQ) (ij) Neu S=mp(TQ)thl TQj =TIQi( S ), (iii) mp( mp(TQ) ) =mp(TQ) Chung minh : ( [ 2 ) trang393 - 394 ) 2.4Ki~mchung1phanrakhongmatthongtin: 2.4.1.Thu~tgiai11.1( Ki~mchungphanrakhongmatthongtin) Input: - LLlQcdaquaIlh~Q( Al,...,Am) - T~pphl,)thuQchamF xacd[nhtrenQ - p={Ql,..., Qk} la1phanracuaQ. Output:- DUNG:neuplaphanrakhongmathongtin - SAI : neup laphanramatthongtin P/nlCfngphap: 1.Xay dljng1 bangM co n cQt,k hangnhLlsau: - CQtj Ctngvai cacthuQctfnhAi 32 - Hang i ling v6icacquan h~Qi 2. Ph§.ntv Mij ( hangi, cQtj ) du'Qcxacoinhnhu'sau: 3. Ap dl;Jng '§.n Iu'Qtcac ph!) thuQc ham X -> Y EOF VaGbang M nhu'sau : v6i 2 hang i1va i2cua M neu : iJ-f X] = i2.[X ] thllam i,.[ Y ] = i2.[Y ] theonguyentac sau: + Neu 1 tri la aj th)tri con lC;liphai d6i thanhaj + Neu 2 tri la bid Va bi2jthl bien thanh 1 tr!bij co gia trj i nho ban. 4. Saukhi apd!)ng bet cac ph!)thuQcham cua F, neut6n tC;li1 hangchlia toan gia tri a thl phan ra la khong ma'ttho~ tin; ngu'QclC;liphan ra la ma'tthongtin. Thf dV 1/.3: Q(S/A,I/P)/F={S->A, S/I->P} p={Ql(S/A)/Q2(S,I,P)} 1. Thiet I~pbang M 2. L§.nIu'Qtap d!)ngcac ph!)thuQchamtrongF 2.1. V6i 5 ->A 2.2. V6i 5/1-> P 33 Mij= ' Ai E Qiaj neu bij ' Aj Qineu 5 A I P Ql al a2 b13 b14 Q2 al bn a3 a4 5 A I P Ql al a2 b13 b14 Q2 al a2 a3 a4 Thu?t toan dung Ta co hang Q2 g6m nhO'nggia tri a. Ket lu?n phan ra p la 1 phan ra khongmatthongtin cua Q ( ling v6i F ) 2.4.2. Dinh Iy : Thu?f giai 11.1th?t slj kigm chung 1 phan ra la matthongtin hay khongmat thong tin. ChOngminh : ( [ 2 ] trang395 - 397 ) 34 5 .A I P Ql al a2 b13 b1 Q2 al a2 a] a 3.Phanrabaoto~mpill;!thuQcham: 3.1.f)!nhnghia( Phanra baoloan phl;lthuQcham) : Cho IvQcdb quan h$ Q ( Al,..,Am),F lat~pphl)thuQchamxac dinh tren Q va p =I Ql"", Qk Iia 1 phanracuaQ. Ky hi$u : Fi = ITQi( F ) = {x -> Y E F+j x U Y ~ Qi 1 Ta noi p la 1 phan ra bao loan phl)thuQCcua Q ( ling v6iF ) neu: F,u ...u Fk1=F 3.2.Ki~mchungphanrabaoloanphl;lthuQcham. 3.2.1Thu~tloan11.2. Input:- LLfQcdbquanh~Q( Al,...,Am) - T~p phl) thuQc ham F xac dinh tren Q - p ={Ql,"', Qk Iia 1 phanracuaQ. Output:- f)UNG : neup la phanrabaaloanphl)thuQcham. - SAI : neup la phan ra kh6ngbaa loan phl)thuQcham. Phuangphap : f)e kiem tra ( u Fi ) 1=F, ta kiem tra v6i m6i X -> Y E F, Y E X+(c' Fi). GQi phep loan Qi la Z u ( ( Z (\ Qi tF (\ Qi ) Thu~tloan tfnh X+(u Fi). 1. Z :=X ; 2. While Z co thay d6i danh sach for i :=1 to k do Z :=Z u ( ( Z (\ Qi )+F(\ Qi ) ; III baa dong Iftydo; va; F Illthu?t roan dung kh; co 7vong lijp for kh6ng lam cho Z thaydo; Thi dv 11.3: 35 Q( A, B,C, D), F =( A-> B,B ->C, C ->0, 0 ->A I p={Ql(A,B),Q2(B,C),Q3(C,0)1 Kiem chungp la 1 phanrabaataanphl)thuQccuaQ (ungvai F ) F1=D()l (F) =( A->B, B->A I F2=DQ2(F) =( B->C,C->B I F:;=DQ3(F) ={C->O, O->C I G =F1uF2uF3={A->B,B->A,B->C,C->B,C ->0, 0 ->CI Ta chi kiemchung0 ->A E F ?. Ap dl.mgthu~tloan -> 1.Z:={0 I 2.1.- Ap dl)ngpheptaanAB Z :=Z u ( (Z n AB tF n AB ) : ={O I - Ap dl)ngpheptaanBC Z :=Z u ( (Z n BC )+Fn BC ) :={O I - Ap dl)ngpheptoanCO Z :=Z u ( ( Z n CD )\ n CD ) :={C, 0 I IIII Z cothaydo;danhsckh 2.2.-Apdl)ngpheptoanAB Z :=Z u ( ( Z n AB t Fn AB ) :={COI - Ap dl)ngpheptoanBC Z: =Z u ( (Z n BCtF n BC ) : = {B, C, 0 I 36 III Z co thaydo;danhsach - Apdvngpheptoanco Z:= Z u (( Z n co tF n CO) : = {BI CI 0 I 2.3. - Ap dvng phep toanAB Z :=Z u ( ( Z n AB t F n AB ) :={A/B/C/O} Thu?t toan dung VI Q+= {AI BI CI 0 } V?y A E (0 t(uFi) =) AI BI CI 0 } Do d6 0 -> A E ( u Fi )+ Ke't/u~n: Phan ra baatoan phv thuQcham. 37 4.Cacdf;1ngchu~n: 4.1.Df;1ngchu~nBoyce-Codd( Boyce-CoddNormalForm- BCNF ) 4.1.1.Sieukhoa: Cho ILiQcd6 quanh$Q. T?p thuQctfnhX la 1 sieukhoacuaQ neuva chi neuno chua1 khoacuaQ 4.1.2.Dinhnghia BCNF: LLiQcd6 quanh$ Q (j BCNF neumQipill)thuQchamX ->A xacdinhtrenQ va A ~X thlX la 1sieukhoacuaQ.. Thf dV 11.4 Q( C, S, Z ), F={C,S->Z, Z ->C I . Khoa: C,S vaZ,S XetpIll)thuQchamZ -> C thl C \l {Z I, Z kh6ngla sieukhoa.V?y Q kh6ng(j BCNF 4.1.3.Dinh nghia : MQtphanrap={Q"..., Qk I (j dC;lngchu~nBCNF neumQiILiQcd6 Qi, 1 s;i s;k d&u(j dC;lngchu~nBCNF 4.2. Df;1ngchu~n3 ( 3NF ) 4.2.1.ThuQctinh khoa ( prime attribute), thuQctinh khongkhoa ( nonprime attribute) Dinhnghia: - ThuQctfnhA lathuQctfnhkhoacuaquanh$ Q neunotham giaVaG1 khoacua Q. - ThuQcthuQctfnhA la thuQctfnhkh6ngkhoacuaquanh$Q neuno kh6ngtham giaVaGbatkykhoanaGcuaQ. 38 4.2.2Dinh nghia1 3NF : Lu'ocd6quaIlh~Q a dC;lngchu~n3NF lieuvoimQiphl,]thuQchamX ->A xacdinb tn§nQ, A (l X thlX lasieukhoaho~cA lathuQctfnhkhoa. 4.2.3.ThuQctinhphI}thuQcb~cc~u: MQtthuQctfnh phl,]thuQcbac cgu vaGt?P thuQctfnh X lieu t6n tC;licac phu thu6c hamX ->Y vaY ->A maY I->X,A (l XY 4.2.4.Dinhnghia2 3NF : MQtIu'Qcd6quaIlh~9d?ngchu~n3NF lieumQithuQctfnhkh6ngkhoakh6ngphl,] thuQcbac cgu vaGkhda. 86 d~11.1: Hai dinh nghTatren la tu'ongdu'ong ChOngminh: ===>) A la thuQctfnhkh6ngkhoa.Cia su A phl,]thuQcbac cguvaG1 khoaK, nghTala c6 t6ntC;liphl,]thuQchamY ->A saDchoY I->A, A (l KY. TheodinhnghTalieuY ->A, A la thuQCtinhkh6ngkhoalienY lasieukhoa.V?y Y ->K ( mauthuan) <====) Chophl,]thuQchamX->A maX kh6nglasieukhoa,A lathuQctfnhkh6ngkhoa. Dod6voi khoaKtac6: K ->X, X/-> K, A (l KX. NghTala A phl,]thuQcbac du vaGkhoa K ( mauthuan ) V?y ho~cX la sieukhoa ho~cA la 1 thuQctfnh khoa. 4.2.5.Tinhchat: MQtIu'Qcd6 quaIl h~Q lieu thuQcd?ng chu~nBCNF thl n6 thuQcdC;lngchu~n3NF ChOngminh : ap dl:Jngdinh nghTa 39 5. Thu~tmlnphanra : 5.1.Dinh Iy phanra (Risanen- 1977) Cho II1'Qcdbquanh~Q vat~ppill)thuQchamFxacdinhtrenQ. p =!Ql, Q2 } la 1 phanracuaQ. p la 1 phan ra khongmatthongtin cua Q ( ling voi F ) neu va chi neuta co : .j. ~ -t 1- ( Ql n Q2) -> (Ql - Q2 ) - f 1 ~ t hOC;lC( Ql n Q2) -> (Q2 - Ql ) thuQcF+ Chungminh: XaydLjngbangki~mtrakhongmatth6ngtin: (j)===» Ap dl)ngpill)thuQchamtrongF+ - NeuQl n Q2->Ql - Q2till hangQ2laa, a2a3 - Neu Ql n Q2->Q2- Ql till hangQl la al a2 a3 Ket lu~n: p la phan ra khongmatthongtin. OJ)<====) Neu p la phanra khongmatthongtin,sauquatrlnhapdl)ngcac pill)thuQcham cua F,taco : - hangQl laal a2 a3 - ho~changQ2 la al a2 a3 * NeuhangQl laal a2 a3,nghTala cQt Q2 - Ql chuy~ntV b13thanh a:\. 40 Qln Q2 Ql- Q2 Q2 - Ql Ql al a2. b13 Q2 al b22 a3 Ta c6 phv thuQcham X -> Y E F saD cho X ~ Q1nQ2, va Yn( Ql - Q2 ) :;::0 hoac Yn( Q2 - Q1 ):;t:0. Ta c6 gia tri thuQctfnh Y bien thanh a khi va chi khi Y ~ x\. CQi (xt( Q1,Q2)={Y/ X-> Y E F va X ~ ( Ql nQ2) J 5auqua trlnh ap dvng cac phv thuQcham F I cac cQt cua Q2 - Ql bien thanh a nett ( Q2 - Ql ) ~ ( X t( Q1,-,Q2)C ( Ql nQ2 t Do d6 ( Ql nQ2) -> ( Q2 - Ql ) 5.2.Dinh Iy : ChoItJQcd6quarth~Q vat~pphvthuQchamFxacdinhtrenQ. p = {Q11Q21"., Qm J la 1 phanrakhongmatthongtincuacuaQ. Neu { 511 52 J la 1 phan ra khongmatthongtin cua Q1 ling v6i I1Q1( F) thl {5" 52,Q21."1Qm}la 1 phan ra khongmatthongtin cua Q ling v6iF. ChOngminh: ( [ 2 ] trang403 ) 5.3. B5 d~ 11.2 (i) MQi Iu'Qcd6 quart h~ c6 2 thuQc tfnh d~ua dC;lngchua"'nBCNF (ii) Neu Q khonga dC;lngchua"'nBCNF thl ta lucrI lucrItlm du'Qc2 thuQctfnh A va B ma( Q - AB ) ->A (thuQCF+) ChOngminh : (j) Cia su Q ( A, B ). Ta c6 2 phv thuQc ham khong tam thu'ang la A -> B va B -> A * Neu khong c6 phv thuQckhongtam thu'angham xac dinh tren Q, thl Q a dC;lng chua"'nBCNF * Neu chi c6 1 phv thuQcham khongtam thu'ang,gia su A -> B thl khoa la ,,\ va thoatieu chua"'nBCNF JI ,~ * Neu c6 d. hai pill) thuQc ham kh6ng t~m thu'dng la A -> B va B -> A thl khoa 13 A ho~c B, va thoa tieu chuan BCNF. Oi) Cia su Q kh6ng thoa tieu chuan BCNF, Q phai c6 nhi§u ban 2 thuQc tinh. Ta c6 pill) thuQc ham X -> A ma A ~ X va X kh6ng la sieu khoa. Do d6 t6n t9 i B EOXA ma B 13 thuQc tfnh khoa. Thllc v~y neu Q + = XA thl X la sieu khoa ( v6 Iy ). Neu v6i nlQi B E XA, B kh6ng la thuQc tfnh khoa thl chI c6 XA la thuQc tfnh khoa, ma X -> A nen X la sieu khoa ( v6 Iy ). V6i B nhu' tren, ta c6 X ~ ( Q - AB ) nen : ( Q - AB ) -> X ( tu~t phan X9 ) X -> A (gia thiet ) Dod6 ( Q - AB ) -> A ( bJ:c c~u ) 5.4 B6 d~ 11.3 : ClIo Iu'Qc d6 quan h$ Q va t~p pill) thuQc ham F xac d[nh tren Qo Ql 13 Iu'Qc d6 con cua Q, Q2 la Iu'Qc d6 can cua Q,o GQi F, = TIQ' ( F ), F2 = TIQ2 ( F, ) thl Chung minh : ( Ullman trang 405) F~ = TIQ2 ( F, ) 5.5. Thu~tloanphanra 1 : 5.5.1. Thu~t loan : Input: Lu'Qc d6 quan h$ Q va t~p pill) thuQc ham F xac d[nh tren Q Output: p = { Q"oo, Qm } la 1 phan ra kh6ng mat th6ng tin cua Qo Cac Qi a d9ng chu~n BCNF ling v6i IlQi( F ) Phuongphap: 1.Voi X -> A la 1 pill) thuQc ham cua F vi ph9m tieu chu~n BCNF, phan ra Q thanh hai Iu'Qc d6 : ~2 -Ql(XA),F1=TIQ1(F) - Q.2( Q-A), F2= TIQ2(F ) 2. Vdi tUngC?P nhu'tren,ki~mtratUngphl)thuQchamcua Fj co thoa. tieuchuanBCNF.Neukhongtier tl)Cphandoinhu'bu'dc1. 3. Neu thoatieu chuan BCNF, du'avao phan ra.. Thu?ttoandungkhikhongphanfa.du'QCnO'a. Thl dl) 11.3.. Q( A, B,C, 0) , F={A ->B,B ->A, BC->0, AC .:>0 } 1. CI1QnA ->B ( A )\ =( AB ), V?y A khong la sieukhoa,vi ph;;lmtieuchuan BCNF Phanrathanh: - Ql(AB) vdi F1=TIQ1(F) ={A-> B,B ->A} - Q2(ACO) vdi F2=TIQ2(F ) ={AC -> 0 } 2. Phanra Iu'Qcd6canQl, Q2 2.1.Ki~mtra0 d~ngchuanBCNFnendu'avaophanra.. 2.2.Ki~mtrao'd~ngchuanBCNFnendu'a vaophanfa. Ke't lufin .. Ql(AB) , {A-> B, B ->A } Q2(ACO ) {AC -> 0 } la1phanracua khongmatthongtin lingvdiF0 d~ngchuanBCNF 5.5.2.Dinh Ii' : Phanraketquacuathu?toanphanra1thl/csl/khongmatthong tinva0 BCNF. Chungminh: - D~ngchuanBCNF: doki~mtratrongtUngbu'dcthl/chi~ntru(kkhiphanfa. - KhongmatthongtinVIthl/chi~ntheodinh IyRisanen. 43 Nh?nxet : - Uudiem: +Ketquala 1 phanrakhongmatthongtinCiBCNF - Khuyet diem: + Ket qua khongbao loan pill) thuQcham. +Vi$ctfnhTIQi(F ) ratphlict<:lP + De kiemtralieu chua"nBCNF, phai tfnhtatca cac khoacua Iu'Qcd6 con. + Thai gian thu~t loan la O(n2m2),la ham mu thee sothuQctfnh n va so plw thuQcham m. 5.6.Thu~tloanphanra2 : De kiemtrad<:lngchua"nBCNF,taapdl)ngb6d~5.3thaychovi$ctfnhtatca cac khoacua Iu'Qcd6 con. 5.6.1 Thu~tloan ( [ 2 ] trang406 ) Input:Lu'Qcd6quanh$Q vat~ppill)thuQcham F xac dinh tren Q Output:p = {Ql,.., Qm }la 1 phan ra k,hongmatthongtin cua Q. Cac Qi Cid<:lng chua"nBCNFlingvaiTIQi(F+) PhUongphap: A. Chu'angtrlnh chfnh 1. Z:= Q 2. Thljc hi$nchodenkhikhongphanradu'Qc repeat begin 2.1. Phan ra Z bangcach gQithutl)Cdecompose. + Ket qua Z du'QcphanrathanhZ - A va XA vai X ->A, XA Cid<:lngchua"n BCNF. 44 2.2. E)u'aXA VaGIu'QcdE>phan ra end untilZ kh6ngth§phanra naatheebe>d~5.3 E)u'aZ VaG Iu'QcdE>phan ra Ketthuc B. Thu tl)Cdecompose If Z kh6ngchuaA va B naGthoaA E ( Z - AB )+11Baadong Iffy tUangLingv6'iF returntri trav~laZ 0 dC}.ngchu~nBCNFvaketthucphanrei. else begin Tim 1 c~pA vaBthoaA E (Z -AB t ; y :=Z - B ; While Y chuaA va BmaA E ( Z - AB )+ Y :=Y - B ; returntritrav~laphanraZ- A vaY IllY (j day 161XA end Thrdv 11.4 Q( C, T, H, R,S,G), F={C ->T , H/R->C, H,T ->R,C,S->G, H,S ->R } ThLjchi~nphanreiQ 1.Z:= Q 2. ThLjc hi~nthutl)Cdecomposevdi Z 2.1. ChQnA :=C, B :=T (Z- CT)+=(H,R,S/Gt :3C Ta laC).i B =T ra kh6i Z Y:=Z-B 45 = (H,R,S,G,C) 2.2.CllQnA :=R, B :=C (Y - RCt =(H,S,Gt :;)R Ta lo<;iiB =C rakhoiY Y : =(H,R,S,G) 2.3.CllQnA :=R, B :=G (Y - RG)+=(H,St :;)R Ta lo<;ii8 =G rakhoiY Y : =(H,R,S) 2.4.V6i Y nhLitren,kh6ngcoA va Brhoatieuchua'n(Y - AB )->A KetthdcthutL,JC Ta co H,S ->R lien tri tra v€= X:=HS,A:=R; ( Z - A ) :=(C,T,H,R,S,G) - R =(C,T,H,S,G) E)LiaILiQcd6R» vaoILiQcdeSphanra 3.Thljchi~nthutL,JCdecomposev6iZ :=Z - A =(C,T,H,S,G) 3.1.CllQnA :=T, B :=H (Z- HTt =(C,S,G)+:;)T Ta lo<;iiB=H rakhoiZ Y:=Z-B = (C,T,S,G) 3.2.ChQnA :=T, B :=S (Y - STt =(C,G)+:;)T Ta lo<;iiB=S rakhoiY Y :=(C,T,S) 46 3.3. Chon A :=T, B :=G (Y - TG)+ =(ct 3 T Ta 10<;1iB = G ra khoi Y Y : = (c,T) 3.4. V6i Y nhu'tren,kh6ngco A va B thoatieuchu&n( Y - AB ) ->A Ket thdc thu tl,)c. Ta co C ->T nen trj tra v§ X '- C A '- T '.- I . - '. ( Z - A ) := (C/T/H/S/G) - T = (C/H/S/G) f)u'a Iu'Qcd6 T }>vaoIu'Qcd6phanra 4. Thl/C hi~nthu tl,)Cdecomposev6i Z :=Z - A = (C/H/S/G) 4.1. ChQn A :=G, B :=H (Z - GHt = (C/S)+3 G Ta 10<;1i B = H ra khoi Z Y:=Z-B = (C/S/G) 4.2. V6i Y nhu'tren,kh6ngco A va B thoatieuchu&n( Y - AB ) ->A Ket thdc thutl,)c. Ta co C,S ->G nen tri tra v§ X:=CS/A:=G; ( Z - A ) :=(C/H/S/G) - G = (C/H/S) f)u'aIu'Qcd6 G }>vao Iu'Qcd6 phan ra 5. Thl/c hi~nthu tl,)Cdecomposev6i Z :=Z - A = (C/H/S) V6i Z nhu'tren,kh6ngco A va B thoatieu chu&n( Y - AB ) ->A 47 Ketthucthutl,]C:kh6ngphanradL1Qcm]a Taco H,S->C DL1aIL1Qcd6 C J>vao IL1Qcd6 phan ra Ke'tlu;tn: Phan rap khongmatthongtin,a d<;lngchua":nBCNFcua Q(C,T,H,R,S,G), F={C ->T, H,R ->C, H,T ->R,C,S->G, H,S->R J la: +Ql(H,R,S), Fl ={H,S ->RJ. +Q2(C,T),F2= {C :> T } +Q3(C,S,G),F3= {C,S ->G } -4 4 +Q (C,S,G), F ={H,S -> C } 5.7Thu~tgiai phanra 3 : D~ki~mtrada d<;lngchua":nBCNF khi : F=0;F={X->Y J ;F={Y->XJ;F={X->Y, Y->XJ Tieuchua":nIL1Qcd6chi co2 thuQctfnhtheeb6d@5.3 5.7.1.Thu~tgiai: Input:LL1Qcd6quanh~Q vat~pphI,]thuQchamFxacdinhtrenQ Output: p ={Ql,u, QrnJ la 1 phanrakhongmatthongtincuaQ. CacQi a d<;lng chua":nBCNF ungvai IIQi( F+) Phuongphap: A.ChL1angtrlnhchfnh 1.Z: =Q; 2.PTH(F):=F ; 3.p= 0; 48 4. GQi thu tl)CDecompose(Z, PTH(F)) III Phan ra QI F B. Thu tl)CDecompose(Q,F) Begin 1. V6i m6i X-> Y E F NeuXY =Q+ thl F :=F- {X ->Y } 2. Neu F=0 till p :=pu{Q}. 3. Neukh6ng V6i X ->Y E FvaXY :;::Q+ 3.1. Q, :=XY;F,=Project(F,Ql)Illchieu cuaP+xuongQl 3.2.Q2 :=Q- {Y};F2=Project(F,Q2)III chieucuaP+xuongQ2 3.3. Decompose(Q"F,) I/Iphan ra Qll F1 3.4. Decompose(Q2,F2)III phanraQ2,F2 end Project(F,Q)={X ->Y E F+I XY c Q } Thfdv 11.4 Q( C, T, H, R, S, G), F ={C ->T , H,R ->C, H,T ->R,C,S->G, H,S->R } Thl/chi$n phan raQ p=0; 1.Phan ra 2.V6i C ->T, taco : CT:;i:Q+ 2.1. Q, : ={C,T};F, :={C ->T } 2.2.Q2:={C,H,R,S,G};F2:={H,R->C,C,S->G, H,S->R} 3.Phanra 49 3.1.V6i C ->T thoaCT =Ql Fl :=F1-{C->TI= 0; p :=PUQl =Ql; 3.2. Ket thuc phan ra Ql 4. Phan ra 4.1.V6i X ->Y E F2,takhongcoXY =Q+ 4.2. V6i H,R ->C E F2, HRC:;t:Q+2 - Q2l ={H,R,CI;F21={HR ->C } - Q22={H,R,S,G};F22={H,S->R } 5. Phanra 5.1.V6i H,R ->C thoaHRC =Q2l F21:=F21- {HR ->C }=0; p :=p U Q2l ={Ql,Q2,}; 5.2.Ket thucphanra Q21 6. Phanra 6.1.V6i X ->Y E F22,ta khongco XY =Q+22 6.2. V6i H,S -> R E F22, "HSR:;t:Q+22 - Q221= {H,S,RI; F221= {H,S -> R } - Q222={H,S,G};F222=0 7. Phanra 7.1.V6i H,S->RthoaHSR=Q22l F221:=F221- {HS -> R }=0; p :=p U Q22l ={Ql, Q2l,Q22,}; 7.2. Ket thuc phan ra Q::21 8. Phanra 8.1.F222= 0; 50 p :=p u Q222 ={Qlt Q21! Q221! Q222! ; 8.2.Ketthucphanra Q222 51 6. Thu~t tmln tc5ngh<Jp 6.1 BaD loan phl;!thuQc ham: 6.1.1.Djnh nghia: ChoIu'Qcd6quanh~Q vat?P phl)thuQchamFxacdinhtrenQ, kyhi$u MQtphanrap={{Ql,Fl>, ,}labaatoanphl,JthuQchamcuaneu p la1phanracuaQ, vaH =(uFi)tu'eingdu'eingv6iF. 6.1.2.DjnhIy : Cho Iu'Qcd6quanh$,p={Qi} i =1,..,mla1phanracuaQ Neup la phanra khongt6ntha'thlt6nt<;lik : 1 :::;k :::;mma: Qk ->Q E F+ ChOngminh: dungbangki§mtrakhongt6ntha't.Chuyv6i hangQi, cQtA co tri tV b chuy§n sanga thl Qi ->A E F+ 6.1.3.Djnh Iy : Cho Iu'Qcd6quanh~,p ={Qi }i =1,..,mla 1 phanracuaQ. H la 1 phucuaF ( H+=F+) ma v6i X ->Y E H thl :3Qi E P thoa XY ~ Qi Neu :3Qi E P ma Qi ->Q E F+thl P la 1 phan ra khongt6ntha'tling v6i F 6.2.Thu~tgiaitc5ngh<Jp1 : 6.2.1.Thu~ttmln tc5ngh<Jp1: Phanra.theo16pcacphl)thuQcham cocungvetrai Input:Lu'Qcd6quanh~Q vat?P phl)thuQchamFxacdinhtrenQ Output:Phanra p={}i =1,..,mv6i(; d<;lngchu{ln3NF, phan rabaatoanphl)thuQcham,khongma'thongtin. 52 PhuCingphap : 1. Xay dljng G la 1 phu toi thi&ucua F 2. Phanhaq.chG thanhcac nhom{Gi },i =1,..,n,m6inhomGj g6mta'tca.phl,! thuQchamclingvetrai.TacoGinGj=0. 3. Dljatrencac Gi, xaydljngQi g6mtatd. thuQCtfnhco trangGi. Ta co a dq.ngchu~n3NF. p ={,...,}la 1 phanrabaataanphl,!thuQchama dq.ngchu~n 3NF cua 4. Tim1 khaacuaq.,laK 5. f)lia K vaGphanrap Phanra{Ql,...,Qn,K }la1phanrabaataanphl,!thuQchama dq.ngchu~n3NFva khongmatthongtin. 6.2.2.Dinh Iy : Thu?ttaant6nghQp1 th?t slj cha 1 phanra baataanphl,!thuQcham,a dang chu~n3NF vakhongmatthongtin. Chungminh: 1.Baataanphl,!thuQcham: Chungminh theeketqua.nhomphutoithi&u,tacoG =(uGj) tu'dngou'dngvai F. 2. Lu'Qc06a 3NF ([ 2] I trang470..): Chungminh : Vai Qi =(YB),Y ->BEG, Gi lat?P phl,!thuQcham trongphanraungvaiQi. GiasU't6ntq.iX ->A E Gi vi phq.mtieuchu~ndq.ngchu~n3NF thlAE X, X khong lasieukhaacuaQivaA lathuQCtfnhkhongkhaa - NeuA=B.VI AE X,nenXc Y maXkhonglasieukhaanenX~Y. TacoX ->A (theegiathiet) nghTalaX-> B 53 Nhu v~yX -> B phai duQcthay cho Y -> B trongquatrlnhxay dljng phutoi thieu ( Mau thu~nvoi tfnh phutoi thieu cua G ) - Neu A =t:B. Do do A E Y, ma A la thuQctinh khongkhoanen ta phai co Z ~ Y, Z :;t:Y, va Z la khoacua Qi. Do do ta co Z -> B, va pill) thuQcham nay duQcdung de thaycho Y -> B trongqua trlnh xay dljng phu toi thieu G. ( Mau thu~nvoi tfnh phu toi thieu cua G ) 3. Khongma'tthongtin: Chungminh: h~qua cua dinh 19 6.1.2, 6.1.3.. Thf dv 11.5 Cho luQc d6 quan h~ : Q(A,B,C,D,G,H) F ={f1: G,H ->A; f2: G,H -> D; h : A,G -> B; f4: C,D -> G; fs: C,D -> H; f6: C ->A; f;: B,H -> C } Phan ra IL1Qcd6 d~ngchu&n3NF, baotoan pill) thuQcham, khongmatthongtin. 7.Timphu toi thieu cua F 1.1F thoa tieu chugn phutoi thieu - Ve phai pill) thuQcham chi co 1 thuQctinh - Khongduthua - Pill) thuQcham vettrai d~Y du 1.2.Phutoi thieu : G:= F 1. Phflll ho?ch G blingcachnh6mcacphVthuQcham co clingvf!/tra; Taco: G1={f1: G,H ->A; f2: G,H -> D; }, G2={f:1 : A,G -> B; }, vetrai : Xl = {G,H } ve trai : X2={A,G } G3={f4: C,D ->G; fS : C,D ->H;}, vetrai : X3= {C, D } 54 G4 =!ff,: C ->A; }, vetrai : X4=!C I G:;=! f7: B,H ->C I, ve trai : Xs=!B,HI 3. Tim 7khoacuaQ : (CO)\ =!C, 0, G, H,A, B } V?y !COlla 1 khoacuaQ. 4.Xay dljngphanra : 4.1.Tu G1={f1: G,H ->A; f2: G,H -> 0; },taxay dljng Q1(G,H,A,O) a d<;ingchu~n3NF 4.2.TuG2={f3: A,G ->B;},taxaydljngQ2(A,G,B) a d<;ingchu~n3NF 4.3.TiJ G3={f4: C,O ->G; fs: C,O ->H;J, taxaydljngQ3(C,O,G,H) a d<;ingchu~n3NF 4.4.Tu G4 ={ f6: C ->A; },ta xay dljng Q4(A,C) a d<;ingchu~n3NF 4.5.TuGs={f7: B,H -> C },ta xay dljng Qs(B,H,C) a d<;ingchu~n3NF TacoG=G1uG2uG3uG4uGS G la 1 phutoithigucuaF nenG+=F+ 5. Xay dljng phan ra khong ma'tthongtin: p={,,,,} Khoa: K ={CD} XaydljngIu'Qcd6Qa(C,D), Fa=0 du'aVaGtrongphanrap. Tuynhienta co Q3(C,O,G,H) da:chuacacthuQctfnhC,O nenta lo<;iiQa ra khoi phanra. 55 KE:'rJuan: Phan rap = ( ,,,,I laphanra khongmatthongtin, baatoanplw thuQchamvaa d<;lngchuin 3NF 6.3.Thu~tgiait6nghqp2 : PhanratheelopG1.Cphl)thuQchamc6vetraitLiongdLiong 6.3.1.ThuQctinhtu'dngdu'dng: Djnhnghia: Hai nh6m thuQctfnh,X va Y gQi la tLiongdLiong( ling voi t?P phl) thuQcham F ) neuta c6 : x ->Y E F+va Y -> X E F+ Kyhi~u: X Y Tachuy trongquatrlnhphanho<;lchG thanhcacGi,g6mphl)thuQchamc6 cung nh6mthuQc!fnh ve trai Xi. C6 nh6m Gi va Gj c6 cac nh6mthuQc!fnh ve trai la Xi va Xi tLiongdLiongnhau, nghTala Xi Xi' Chungta c6 th§ gQPcac phan ho<;lch naythanh 1 nh6md§ giam bot 56ILiQcd6 ketquacua phan ra. Tren co sa nay hlnh thanh thu?t giai t6nghQp2 6.1..2.Thu~tloant6nghqp2 : Input:LLiQcd6quaIlh~Q vat?Pphl)thuQchamFxacd!nhtrenQ Output:Phan ra p = {}i = 1,u,mvoi ad<;lngchuin 3NF, phan I ra baa toan phl) thuQcham, khong matthongtin. Phuongphilp: 1.Xaydl/ngG la 1 phu t6i thi§u cua F 2. Phan ho<;lchG thanh cac nh6m {Gi }, i =1,..,n,m6i nh6m Gi g6mtat ca phl) thuQcham cungve trai. Ta c6 GinGj = 0. 3.GQPcac phan ho<;lchGi va Gj c6 thuQc!fnhvetrai Xi va Xi tu'ongdLiongnhau, Xi Xj 56 D~thanhphanhaC:lch{Fi }i =1,..,m 4. DLJatrencacFi,xaydLJngQi g6mtatcathuQctfnhcotrongGj.Tacod dC:lllgchu§:n3NF. p = kQ"F,>,...,}la 1 phanra baataanphL)thuQchama dC:lngchu§:n 3NFcua 5.Tim1 khaacuaQ la K 6.DLiaK VaGphanrap Phanra {Q"...,Qm,1\}la 1 phanra baataanphL)thuQcham a dC:lngchu§:n3NF vakhongmatthongtin. Tuynhien,trong1sotrLianghc;lPkhigQPphanhaC:lchGjvaGjthanh1phanhaach Fk,tada dLiathemthuQctfnhbac du VaGtrongphanhaC:lchFk,nenILiQcd6 quaIl h~dLic;lCxaydLJngtVphanhaC:lchnaykhongthaatieuchu§:ndC:lngchu§:n3 NF. Thf dL) 11.6 ClioiLiQcd6quaIlh~: Q(A,B,C,D,G,H) F={f1: G,H ->A; f4: C,D ->G; f2 : G,H ->D; f3':A,G-> B; f5 : C,D ->H; f6: C ->A; f7: B,H ->C } Phanra ILiQcd6dC:lngchu~n3, baataanphL)thuQcham,khongmatthongtin. 1.TImphu to; th;eu cua F 1.1Fthaatieuchu§:nphutoithi~u -V~phaiphL)thuQchamchi co 1thuQctfnh -KhongdLithua -PhL)thuQchamv~traidclydu 1.2.Phutoithi~u: G:= F 2. Phanho<;1chC biingeachnh6mcaepIlL)thuQchamc6 cungve'trai 57 Tac6 : Gl ={f1: G,H ->A; f2: G,H -> D; }, G2= {f3: A,G -> B; }, vetrai: Xl ={G,H } vetrai : X2={A,G } G3 ={f4: C,D ->G; fs: C,D ->H;J, G4={fl>:C ->A; }, ve trai : X3={C, D } ve trai : X4={C } Gs={f;: B,H ->C }, vetrai: Xs={B,H } 3. Tim 7khoaeuaQ : (CDtF={C, D, G, H, A, B }. V~y{CD}la 1 khoacUaQ. 4.XaedjnhvagQPcaenh6me6thuQI:tfnhve traitUcJngducJng: 4.1.Xacdjnhcacnh6mc6thuQctfnhvetraitlielngduelng: - (X1)\ =(GH)\ ={A,B,C,D,G,H} - (X2)\ =(AG)\ ={A,G,B} - (X3tF=(CD)\ ={A,B,C,D,G,H} - (X4)\=(C)\ ={C,A} - (Xs)\ =(BH)\ ={B,H,C,A} V~ytachic62 nh6mthuQctfnhvetraitlielngdlielgnla : Xl X3(GH)(CD) 4.2.GQPcacnh6mc6thuQctfnhvetraitlielngdlielngdlielng: Chi c6 nh6mGl vaG3dliQcgQPIq.i Fl =GluG3 ={fl : G,H ->A; f2: G,H -> D; f4: C,D ->G; fs: C,D ->H; }vetrai: Y1={(G,H),(C,D)} F2= G2= {f3: A,G -> B; }, F3= G4= {f&: C ->A; J, ve trai : Y2={A,G } F4=Gs={f7: B,H -> C }, ve trai : Y3= {C } ve trai : Y4= {B,H } 58 5. Xay dL/ngphan ra : 5.1. Tli Fl = {f,:G,H ->A; h:G,H ->D; f4:C,D->G; f5:C,D -> H; I, taxay dljng Q,(G,H,A,C,D). khongo'd~ngchucln3NF Chungminh: TacothuQctfnhkhoaC,D ThuQctfnhkhongkhoaA maG,H ->A, thuQctfnhG,H khonglasieukhoa. 5.2.Tli F2={f3: A,G ->B; },taxaydljngQl(A,G,B) (Jd~ngchucln3NF .5.3.Tli F3={f6: C ->A; },taxaydljngQ3(A,C) (Jd~ngchucln3NF 5.4.Tli F4 ={6: B,H ->C },taxaydljngQ4(B,H,C) (J d~ngchucln3NF TacoG =F,uF1UF3UF4 G la 1 phutoithi§ucuaF nenG+=F+, 6.XaydL/ngphanrakh6ngt6ntha't: p={,,,,} Khoa: K = {CD} XaydljngILiQcd6Qa(C,D), Fa=0 dLiavaotrongphanrap. TuynhientacoQ,(C,D,A,G,H) dachuacacthuQctfnhC,D nenta lo~iQa rakhoi phanrei. Ketlu[ln: Phanrap ={,,,} la1phanracuaQ baatoanphl)thuQchamvakhongmatthongtin 59 6.3.3.Thu~tgiaitanghqp2 ( b6sung) : Ta chu ytrongqua trlnh nh6m phan ho<:ichGi va Gj c6 cac nh6m thuQctfnh v{L trai la Xi va Xi tuangauangnhau,nghia la Xi Xi, chungta c6 th~gQPcac phan hoach nay thanh 1 nh6m a6ng thai cOngaua VaGthuQctfnh b~c cclutrung gian VaGtrong luQc06 ket qua. Do 06 chung ta tien hanh thl/c hi~n lo<:iibo cac thuQc tfnhb~cccluxay ra khi gQPcac phan ho<:ich. Tren co sa nay hlnh thanhthu~tgiai t6nghelP2 ( b6 sung) Thu~t toan t6ng helP ~( b6 sung) : Input: LuQc06 quail h-$Q va t~pphl,!thuQcham F xac ainh tren Q Output:Phanra p = {}i = f,..,m vai a d<;ingchu~n3NF, phan rabaatoanphl,!thuQcham, khongma'tthongtin. Phuongphilp: 1.Xaydl/ngG la 1 phu toi thi~ucua F 2. Phan ho<:ichG thanh cac nh6m {Gi }, i =1,..,n,moi nh6m G g6m ta'tca pill,! thuQchamcLIngvetrai.Tac6 GjI'\Gj = 0. 3.Xac a!nhcac cac phan ho<;ichGi va Gi c6 thuQctfnh ve trai Xi va Xi tuangauang nhau, Xi Xj 4. Lo<:iibothuQc tfnh b~c cclu trong tUng c~p Gi , Gj, i, j = l,..,m; i =Fj £)~tPTT(F) := G ; 4.1.Vai moi c~pXi cua Gi va Xj cua Gj, XiXj , a~tJij= {Xi ->Xi; Xi ->Xi} - Vai m6i AE Xj : +Neu Xi ->A E PTT(F)till : . Gi :=Gi - {Xi ->A }; II LOA ra khoi Gi ; . PTT(F) :=PTT(F) - {Xi -> A} II LO A ra khoi PTT(F) ; - Vai m6i BE Xi : 60 + Neu Xj -> B E PTT(F)thl : .Gj:=Gj-{Xj->BJII LO B ra khoiGj ; . PTT(F) :=PTT(F) - {Xj -> B J II Lo B rakhoi PTT(F) 4.2. O~tJ = Jij = {Xi -> Xj ; Xj -> Xi J PTT(F) auQcxac ainh (j buck tren Gij =GiuGj v6i Gi va Gj aa auQcxaydljng (j bu6c tren. 4.3. Tim t~pPTT ~ PTT(F)thoa : ( PTTuJ ) tuangauongv6i ( PTT(F)uJ ) bang cach : - PTT := PTT(F) - V6i m6i f E Gij : + PTT:= PTT(F)- {fJ + Ki&mtra (PTTuJ) wang auangvai ( PTT(F)uJ ) Neu dung : . PTT(F) := PTT(F) - {fJ ; . Gij := Gij - {f J ; Sau buac nay ta xac ainh auQc PTT 4.4. Ova Xi -> Xj va Xj -> Xi VaGGij . 5. Xay dljng cac Fi theo slj phan ho<;lchGi vai Gij la nh6m phan ho<;lchc6 thuQc tfnhve trai tuangauangauQcxay dljng nhutrongbu6c4. 6. Dlja tren cac Fi,xay dljng Qi g6mtatc3.thuQCtfnh c6 trongGj. Ta c6 (j dq.ngchu~n3NF. p={,...,Jla1phan ra baatoanphI)thuQcham (j dq.ngchu~n3NF cua 7.Tim 1 khoacua Q la K 8. Ova K VaGphan ra p 61 Phan ra {Ql,...,Qm,K Iia 1 phanra baataanpill)thuQcham Cid?ngchua"n3NF vakh6ngmatth6~ngtin. Thidv 11.7 ChailiQ'Cd6quanh~: Q(A,B,C,D,G,H) F={fl : G,H ->A; fl : G,H ->D; h : A,G ->B; f4: C,D -> G; f,:;: C,D -> H; f6: C ->A; h: B,H->C } Phanra 1u'Q'cd6d?ng"chua"n3, baataanpill)thuQcham,kh6ngmatth6ngtin. 7.TImphu to;th;e'ucuaF 1.1Fthaatieuchua"n phut6ithi@u - Ve phaipill)thuQchamchi co 1thu6ctfnh - Kh6ngdu'thLta - Pill)thuQchamvettrai d§.y du 1.2.Phut6ithi@u: G:= F 1.Phan ho(jJch G bangcachnh6mcacphVthuQchamc6 cLingvetra; Taco: G1={fl : G,H ->A; f2: G,H -> D; }, G2={fj : A,G ->B; I, vetrai: Xl ={G,H } vetrai : Xl ={A,G } G~={f4: C,D ->G; fs: C,D ->H;}, vetrai: X3={C, D } vetrai : X4={C IG4=lfc,: C->A; I, Gs=I f;: B,H ->C }, ve trai : Xs={B,H } 3.TIm7khoacuaQ : (CO)\ ={C, D, G, H, A, B I 62 V~y{COlla 1 khoacuaQ. 4.Xacd;nhvagC)pcac nh6rnc6 thuC)ctfnhvetraitLlCingduCing: 4.1. Xacdinhcac nh6mc6thuQctfnhvetrai tu'ongdu'ong: - (Xl tr =(GHtr ={A,B,C,D,G,H} - (X2)\ = (AG)+r= {A,G,BI - (X3)\ =(CDtr ={A,B,C,D,G,H} - (X4)\ =(C)\ ={C,A} - (X5)\ =(BH)+F =;{B,H,C,A} V~ytachic62 nh6mthuQctfnhvetraitu'ongdu'ongla: Xl X3(GH) (CD)" 4.2.GQPcac nh6mc6thuQctfnhvetraitu'ongdu'ongdu'ong: Chi c6 nh6mGl va G3du'QcgQPI?i Fl =G,UG3 ={f, : G,H ->A; f2: G,H ->D; f4: C,D->G; fs: C,D->H;}vetrai:Yl={(G,H),(C,D)} F.2=G:2={f3:A,G->B;}, F3=G4={f6: C ->A; }, ve trai : Y:2={A,G I F4=Gs={f7: B,H ->C }, ve trai : Y3= {C } ve trai : Y4= {B,H } 4.3.Lo?ibothuQctfnhb~kcgu chonh6mFl D~tPTT(F):=G X, =(GH),Gl ={fl: G,H ->A; h : G,H ->D} X3=(CD),G3={f4: C,D ->G; fs: C,D ->H} 4.3.1.Tlmphl,!thuQchamb~ccgu: Vai Xl ------------------------------- - V6i G E (GH), ta c6 f4 : C,D -> G E PTT(F): + PTT(F) :=PTT(F) - {f41; 63 = {f" f2,f3,f5,fb!f; } + G3 :=G3 -{f4}; = {f5 }; - V6i H E (GH), ta co fs : C,D -> H E PTT(F): + PTT(F):=PTT(F) - {is}; ={f"h,h,f6,f;} + G3 :=G3 -{is}; =0;. xong v6i X, --------------------------------- v6i )(3------------------------------- - V6i C E (CD), ta kh6ngco G,H ->C E PTT(F); - V6i D E (CD), ta co h : G,H -> D E PTT(F) : + PTT(F) :=PTT(F) - {h}; ={f"h, f6,f7} + G, :=G, -{hI; = {f1}; xong v6i )(3 ------------------------- 4.3.2. Ta co : PTT(F)= {f"h,f6,f7 } J = {C,D -> G,H ; G,H ->C,D ;} G3 =0 vaG, ={f, } f)~tG13= G,UG3 = {f, } TIm PTT thoa ( PTTuJ ) Wangduagnv6i ( PTT(F)u J ) - PTT := PTT(F) V6i f, : G,H ->A E G13 - PTT := PTT(F) - {f1} = {h, f6,f; } 64 - KiE~mtra PTTu J tu'ongdu'ongvaiG ? Taco * PTTuJ =!f3: A,G ->B ; f6: C ->A; f7: B,H->C ; G,H ->C,O ; C,O ->G,H 1 "'G =!f, :G,H ->A; f2:G,H ->0; f3:A,G->B;f4:C,O ->G; fs:C,O ->H; f,,:C->A; f7: B,H ->C } Nh?n xet : PTTuJ c G+,ta chi ki§m traG ~ (PTTuJt Ta co : f3,f6,f; hi§n nhien thuQcPTTuJ f4,f5thuQc(PTTuJt (ap dvngIu~tphanXG,H , Chi ki§mtrachof, : G,H ->A. Tfnh(GHt trongPTTuJ G,H ->C,O ===>G,H ->C (ILI~tphanX<,l) C ->A (f6E PTTu J ) V?y G,H ->A ( Iu~tba:ccgu) Ap dvnglu~tAmstrongtrent?P PTTuJ. V?y G,H ->A E WTTuJt Ket lu~n: PTTuJ tu'ongdu'angv6i G PTT(F) :=PTT ; Go :=Gn - ! f11 :=0; KetthuctlmPTTVIG'3chi cof, 4.3.3. Xay dl,ingphan ho<,lchG13 Gn :=G13U{X, -> X3; X3-> X, } ={C,O ->G,H ; G,H ->C,O } 4.4.Taco phanho<,lch: G :=PTTuJ =!f) : A,G ->B ; f(): C ->A; f7: B,H ->C ; G,H ->C,O ; C,O ->G,H 1 Fl =Gn =!G,H -> C,O; C,O ->G,H } vetrai: Y, ={(G,H),(C,O)} 65 F2 =G2 ={h : A,G ->B; }, F\ = G4 = {f6: C ->A; I, vetrai : Y2 ={A,G I F4= G:; = {f;: B,H -> C },, ve trai : Y3= {C I ve trai : Y4 ={B,H I 5. Xay dl.jngphan ra : 5.1.TCtFI ={G,H ->C,D; C,D -> G,H },ta xay dljng Q,(G,H,C,D) a d,;mgchucln3NF 5.2. TCtF2= {f3: A,G -> B; },ta xay dljng Q2(A,G,B) (j dC;lngchucln3NF. 5.3.TCtF3= {f6: C ->.A; },ta xay dljng Q3(A,C) adC;lngchucln3NF 5.4.TCtF4 = {f7: B,H -> C },ta xay dljng Q4(B,H,C) adC;lngchucln 3NF Ta co PTTuJ = F,uF2UF3UF4tu'angdu'agv6i G ma G la 1 phutoi thi§u cua F nen G+= F+hay (PTTuJt = F+ 6. Xay dljng phan ra khong ma'tthongtin: p= {,,,) Khoa : K = {CDI Xaydljng Iu'Qcd6 Qa(C, D), Fa= 0 du'aVaGtrongphan ra p. Tuy nhien ta co Q,(C,D,G,H) da chua cac thuQctfnh C,D nen ta IOC;liQa ra khoi phanrei. Ket lu?n : Phanra p = {,,,1 la1 phanracuaQ a dC;lngchucln3NF baaloanphvthuQcham,kh6ngma'th6ng tin. 66 7. Lilach~mPhl}thuQchamd~phan lap( quanh~) : Hc;lnche'cuathu~tloant6nghQ'pla cungca'pIWc deSke'tquamav~ngG'nghTakhongthkh h<;ip D~coth~apdl)ngthu~tloantrongthl,lcti~n,chungtadinhnghTaphl)thuQchamphuh<;ip-voi . nghTathl,lcte'. Saudayla mQtlingdl)ngchomohinhngunghTadl,latrenmohinhquanh~. TrongmohinhngG'nghTa,taxemxetcaclienh~giuacaclopnhLisau: +M6i lienh~thamchie'u +Ki~udG'li~uke't~p +Ki~uda li~uchuyenbi~t(Isa relationship) V~ndl)ngxacdinh phl)thuQchamnhLisau: 7.1Lienh? thamchie'u: . Quanh~CU_TRU I HQ_TEN I ~_NHA I#B~NG IT~N_B~NG #DVTEN DUONG HO_TEN ->SO_NHA,#DU<JNG,TEN_DUONG - Ke'tqua: Quanh~CU-TRU I HQ_T~N ~_NHA Quanh~DUONG( Oanh muc D" I #E>UONGI ) I #tJUONG I T~N_m.KJNG"I £)fnhnghfaph~thuQchamnhunQidungthongthuang 7.2.Kie'udali?u keft~p: +Nh6m: Quanh~CCVC I #PB E_PB #CCVC->HQ_TEN #PB->TEN_PB #CBVCthanhviencua#PB: #CBVC->#PB I #ccvc HQ_TEN Ke'tqua: Quanh~PHONG_BAN( Oanh ml)CPhong Ban) I #PB I T~N~PB I 66-1.. Quanh~CCVC I #Ccvc I HQ_T~N IIIPB EJfnhnghTaphl) thuQcham nhunQidungthongthuang +Thanhphjn: Quanh~CONG VAN #CV -> NQI_DUNG #NGUOI_NHAN ->"'CHUC-VV NGUOI_GUI->CQ_GUI . #CVcothanhph~nla#NGVC1l_NH~N: #CV ->#NGVC1I_NH~N #CVcothanhph~nla NGVC1I_GLn: #CV->NGVC1I_GLn Ke'tqua: Quanh~CONG_VAN E-:=:I NOI_DUNG Quanh~NGVOI_GUI I NGVrJI_GUI I CQ_GUI Quanh~NGUOI_NHAN I #NGUOI_NH,;,N I CHUCYl) EJfnhnghTapIll)thuQchamnhunQidungthongthuang I #NGLlOCNHAN NGLiOI_GUI 7.3.Ki€u dali~uhipchuyenbi~t: Quanh~eeve I #CCVC I HQ_TEN I D_V I #DV I NGAY_KN 0- V =1 Neu Ic'l8ang vi€!n, co cac thuQctfnh #DV, NGA Y_KN 0- V =0 NeukhongIc'l8angvien,khongcocacthuQctfnhtren #CCVC->HQ_TEN, D_V #DV ->NGAY_KN (eachchQnph'.lthuQchammota lopchuyenbi~t) #DVlachuyenbi~tcUa#CCVC: #DV->#CCVC Thongthuong:#CCVC->#DV,takhongphanraduqclopchuyenbi~t. 66-.2.. - #CV NQI_DUNG #NGUOI_N CHUC- CQ_GUI NGLiOI- HAN VV GUI Ke'tqua: Quanh~CCVC I#ccvc I HO_T~N ~ Quan h~DANG- VIEN I #CCVC~v I NGA Y _KN 8inh nghia phlJthuQcham khongnhu'nQidungthongthuang {;6-?>