Luận án Cơ sở dữ liệu với thông tin chưa đầy đủ

t trongs b~ngcac gicitri duli~uxacdinh. Trong(14]Maier dfi dinhnghiacachamkha Dangdvatrencackhai nit$mmd rQngvamdrQngd~yduo Dinhnghia1.7 (POSSo)Cho mQtquailht$r, POSSo(r)={sIs Ia mQtmdrQngcuar} 18 Lu'u_Li sO' N gay_Dn Ngay_Di Phong S6_NgU'oi Tin- Tra 1 1/6 15/6 205 1 10000 - 2 1/8 @ 310 2 3000 3 1/6 ' @ 401 4 12000 4 1/6 @ 402 4 12000 Dinh Nghia 1.8(POSSe)Cho mQtquailh~r, POSSc(r)={sI s Ia mQtmarQngd~ydu cuar} Dinh Nghia1.9(POSSCE)ChomQtquailh~r, POSSCE(r)={sIsla mQtmarQng d6ng cLlar] 2.1.1.2.Cachtitpcq,ncuaImieliniskivaLipski Cachtie'pc~nnayd1;1'atrennhungquailh~mQtph~nc6chu'acacgiatri null du'<;1Cdanhda'u[20].M6i giatrinullxua'thi~ntrongquailh~nhu'mQtbie'n(variable) dod6c6tengQiv - table.BangIlIa ffiQtvi dl,lv6V-table Bang11.V - table Ky hi~ux vay chirahaigiatrinullkhacnhau.Vi~cs\i'dl,lngyhail~nngl,ly1a ngu'aikhachso3sethuehaiphong401va402trongclingthaigian. E>~caitie'nV-table,mQtcQtthuQctinhdiiu ki~ndu'<;1Cthemvao.CacbangV- tablekernthemcQtthuQctinhdi6uki~ndu'<;1cgQila cacbangC-table(bangdi6u ki~n) Bang12bi~uthis1;1'ki~nla ngu'aikhachso3 ses\i'dl,lngphong401ne'ungu'oi khachso2 roi khoiphongd6tntocngay1/8 vasestrdl:mgphong402ne'ungu'<;1cl<;li. 19 Lu'u_L<;li So Ngay_de'n Ngay_di Phong So_N gu'ai Ti6n 1 1/6 15/6 205 1 10000 2 1/8 x 401 2 3000 3 1/6 I Y 401 4 12000I i I I 3 L 1/6 Y 402 4 12000 Bang12.C-Table 2.1.2Ghi tri nullkhongt6nt~i Gia trinullkhongt6nt~iduQcnghienCUlltrong[18,21,22].Ngunghiacua nullkhongt6nt~iduQcbi~uthilakhongcogiatrithvcnaocoth~t6nt~idvi tITnull do.Vi d1;ld6ivoi nguoichuaco giadlnhthl tenvQ(ch6ng)khongt6nt~i.Trang bangnhan-VieDduoiday,MinhkhongcosO'di~ntho~inaoca. Bang13. Quanh~chuanullkhongt6nt~i Voi ngunghiaduQcneutrenthlgia11inullkhongt6n~i (ki hi~udne)giO'ng nhuffiQtgiatrixacdinhbonla ffiQtgiatri chuaxacdinh.Do donullkhongt6nt~i khongduQc oila d~bi~uthithongtinkhongd~ydu'. 2.1.3Ghitri nullkhongcothongtin Thu~tngugiatrinullkhongcothongtindoZaniolo[23]duafa . TheoZaniol0 caedi€ngiaichuabie'tvakhongt6nt~ichuaphaila nhungdi€n giaicosdnh!tcho 20 Lttu_li sO' N gay_De'n Ngay_di Phong sO' Tin DK Nglioi 1 1/6 15/6 205 1 10000 2 1/8 x 401 2 3000 3 1/6 Y 401 4 12000 x<I/8 3 1/6 Y 402 4 12000 xz1/8 Nhan-VieD Ten Phong Chuc-V1;l Din- Thoi MAL MT TK 9241320 ? 7652320HAL MT TP HVNG MT GVC 5568321 MINH MT GVC due giatqnull.C6mQtcachdi~ngi,iinguyenthuyhdnhaidi~ngi,Hn6itren,d6Ia di~n giii nullkhongc6thongtin.B~minhhQachoy tU'dngcuaminh,Zanioloda:dU'ara vi dl;lv~CSDL g6mmQtquanht$Nhan-Vien(S6_Hit$u,Ten,Gidi_Tinh,S6_nql) trongbing 14. Bang14.Quanh~nhanvien Zaniolo dil gii sa ngU'diquill tti CSDL mu6nthayd6i lU'Qcd6 CSDL b~ngcach dU'athemvaocQtthuQctinhBit$n-Tho'.lid~IU'ul'.lis6dit$ntho'.linhariengcuatung nhanvien.S11thayd6icuaIU'Qcd6khongc6nghiala m6inhanvienphii clingca'p s6dit$ntho'.licuahQngayl~ptacoThlfcte-thongtinnaysedU'QcdU'avaoCSDL khi naoda:sansang.NhU'v~yngU'diqUilltqCSDLphiig~phiiva'nd~thaotacdfi'lit$u , lamthe-naod~mdrQngIU'Qcd6makhonglamthayd6iv~nQidungthongtincua CSDL.Giii phaprarangnha'tIa:Beluvaot'.licQtthuQctinhBit$n-Tho'.liduQcdi~n bdiki hit$u"-" maZaniologQila giattinullkhongc6thongtin.<1daykyhit$u"-" khongbi~uthir~ngs6dit$ntho'.licuamQtnhanviennaod6la khongt6nt'.lihayc6 t6nt'.linhungmachU'abie-t. N6chIdongiin la bi~uthichU'ac6thongtinnaochoso' dit$ntho'.licuacacnhanvien.NhU'v~ygiatti null "-" c6th€ dU'QcxemnhU'Ia mQt ndichuachomQtgiatrikhongt6nt'.liho~cgiatqchU'ahie-toVa dod6n6la nguyen thuyhonhaidi~ngiii trU'dcday. 21 Nhan-Vien S6_Hit$u Ten GiOi-Tinh S6_nql 1120 SMITH M 2235 4335 BROWN F 2235 8799 GREEN M 1255 I Dttdidi€n giaikhongcothongtinthlbang14vabang15latUdngdttongv€ nQi dungthongtin. Bang15Quanh~nhanviensaukhithemcQtthuQctinhDi~n_Tho~i 2.2NUll NCO'CANHvA ca sa DO'lI~UNUll NCO'CANH Khi nghiencUuv€ ghltrinulltrongmohlnhqua~h<$,d6ivdim6iki€u nullh~u h€t cacnhanghiencUud€u dungduynha'tmQtkyhi<$ud€ bi€u di€n chomQithong tinbi thi€u.Chungtatha'ycachti€p c~nnaychttath~thoadang,bdigiatrinullt~i m6inoithi€u coth€ khacnhau. Vi<$cbi€t themcacthuQctinhcuamQtd6i ttt<;1ngsegiupchochungtaphong doanthemdtt<;1cnhungthuQctinhchttabi€t cuad6ittt<;1ngdo.Nghlala,nhungthuQc tinhchttabi€t cuad6i ttt<;1ngco th€ dtt<;1cxacdinhquanhungthuQctinhda:bi€t (t~p h<;1pnhungthuQctinhda:bi€t nay co th€ gQiIa ngucanhcuad6i tu'<;1ng)Vi dl,l:ne'u ChIbi€t tencuamN ngttaiIa A thlkhocoth€ noiba'tky di€u gl v€ Ittongcuangttai do.Nhttngn€u bie'themdingngttaiA IaKy stt,IamQtrttdngphong,thaigiantham niencongtacla 10nitro,chungtacoth€ doandtt<;1Cvaidi€u v€ Ittongcuangttainay. Nhttv~y,mQtgiatri chttabi€t trongmQtquailh<$co chili giatri nullcoth€ dtt<;1cxac dinhbdi nhunggia tri da:bi€t trongquanh<$do.N6i cachkhac,Nhunggia tri null chomQtthuQctinhla khacnhaun€u t~ph<;1pnhungthuQctinhda:bi€t co lien quaild€n giatridoIii khacnhau.hayngucanhcuachungIii khacnhau.Do m6igia 22 Nhan-Vien S6_Hi<$u ten GiOi-Tfnh S6_nqI Di<$n.;..Thoi 1120 SMITH M 2235 - - 4335 BROWN F 2235 - 8799 GREEN M 1255 - trinulldi~ug:invoingucanhcuano.VI v~ynguaitadii tangngunghiacuagiatri null b~ngcach bi~udi~nnhunggiatrinullco ngucanhkhacnhaubdinhungky hi~unullkhacnhauthayVId6ngnhfftchungbdiduynhfftmQtkyhi~u. XufftphattU y tudngtren, [24],[2]diiduaramQtdi~ngiaimoichonullvagQichunglanullngu canh. TruockhiduaraBinhnghiahlnhthucchonullngucanhchungtaxetmQtvi d\l sail: Vi du2.1: ChohailuQcd6quanh~R1(Ten,Tu6i,Man)vaRz(Ten,Tu6i,SV) voi haith~hi~ntuongungla rl, r2.Trongdo,Man la mand~ymamQtnguainaodoco m~trongquanh~rl d~y,SV la tensinhvienduQcnguaidohuangdftn,xetcosddu li~ug6mhaiquanh~rl var2: Giasat~ithaidi~mtl vat2(tl<t2),h~thongnh~nduQcmQteachdQcl~pnhung thongtinsail: tj: va t2: Trong truanghQpnayph~nduli~umah~thongco t~ithaidi~mt2sekhangduQC auathemvaovi nokhangcogi moi.VI v~yduli~utrongquanh~r[ var2seg6m cacbQtrongbang1vabang2: Bang1 Bang2 Saildo t~ithaidi~mt3h~thongnh~nduQcthongtin t3: 23 r[ ten Tu6i Man A 81 B A 81 C r2 Ten Tu6i SV A 81 82 DobQmoithemvaovahaibQbandffuIakhacnhautt;tinhunggiatridiibie'tv~ mandt;tynennhunggiatrinulltt;tibQmoithemclingnenkhacsovoihaibQtntoc. (Voi giathie'ta daytachuaquantamtoicacph\!thuQcdii'li<%unhuph\!thuQcham, ph\!thuQcdatri...) Bang3 Bang4 Tt;ti thai di€m tie'pthea, gia sa thong tin sail dU<;1cdua them vao h<%th6ng 4: Do thongtintt;tithaidi€m t4baag6mluoncathongtintt;tithaidi€m t3nenchi phffnthongtinmoilaM moicffndU<;1cduavaocosadii'li<%u. Nhuv~yfl vaf2 sela cacquanh<%tfongbang3vabang5. Bang5 V~m~ttn,tcgiac,chungtadii th1ydu<;1Csl,l'so sanhb~ngvasl,l'khacnhaugiii'a caegiatrinullthongquanhunggiatridiibie'trongcosadii'li<%u.Nhilnggidtrtdii 24 fl Ten Tu6i Mon A 01 B A 01 C A 03 D f2 Ten Tu6i SV A 01 02 A 01 N f2 Ten Tu6i SV A 01 02 A 03 N A 03 M bitt trongC(Jsadilli?u colienquandtnm6igill trjnulldLtqcg9ifangilcanhcuagill trjnulldo.Saildaychungtasedihlnhthucboakhainit$mcuanullngi1canh. Xet ffiQt~pph6quatcaethuQctinhU ={Aj: 1~i ~n }.Voi m6ithuQctinhAi tagalltl1ongungvoi ffiQt~pAiU LlitrongdoDj la mi~ngiatri cuaAj vaLlila ffiQt t~phcruh<;lnnhii'ngky tl,l'Hy L<;lp{Oij}d~bi~udi~ncac null ngi1canh cua Ai . G9iD =U {Di: 1~i ~n}vaLl =U{Lli1~i ~ n }tacoD n Ll =0. Voi X cU. MQtanhX(;I.t : X ~ D ULl saochot(AD E Dj U ~ivoi m9iAi E X dl1<;$cg9i la ffiQtbQtrenX vaki hi~ut[X]. Voi m9iX c U t~ptatcacacbQt[X] dl1<;$c ky hi~ula 3. Cho t la mQtbQtrenX; A E X n€u t(A);:null ky hi~ula t(A)!. N€u '7A EX, t(A)!tavi€t t!nghlala t chIchl1anhi1ngiatridii'li~uxacdinh.Voi y c X khidotakyhi~ut[Y]={t(A):A E Y} vag9ila phepchi€u cuat lenY .T(;I.p reX)nhii'ngbQcochl1anullngii'canhtrenX dl1<;$cg9ila quailh~voinullngii'canh trenX . N€u Y eX, thl{t[Y]:t E reX)}dl1<;$cg9ilaphepchi€u cuareX)trenY va dl1<;$cki hi~ur[Y]. Xuatphattuquaildi~m . Cosadii'li~ulatrongsu6td6ivoingl1oisli'dl,mg . Doconhi~ungl1oisli'dl,mgnenconhi~ukhungnhln(views). Lu~nvanse xemxetmQtco sa di1li~u(CSDL) nhl1ffiQtt~pcacquailh~ {rj(Xj):1~ i ~m}trongdoU {Xi1~i ~m}=U vam6iriCXi)dl1<;$cg9ila mQtquail h~trongCSDL . 25 DinhNghia2.4Chot vat' lahaibQbeltkytrong:J du'<JcxacdinhtrenmQtt~pchu'a X. (i) t vat' du'<JcgQila tu'ongdu'ongtrent~pX(vi6tla t ~ t' ho~ct[X] ~ t'[X])n6uva.t chi n6u\;jA E X, teA)!ho~ct'(A)! thiteA)=t'(A) . Ne'ur lamQtquanh~trenX, t vat' lanhii'ngbQtrongr chungtakihi~u~ bdi ~ .t r (ii) tdu'<JcgQilait thongtinhont' hayt' nhi~uthongtinhontvavi6tt~t' hay t' 2 t n6u\;jA E X, t(A)! keorheateA)=t'(A) Vi du 2.2 : Vdi bQtl = . (z=, t3= thi tl ~ tz; tb tz 9:;t3va t1,tz ~ t3 '1 '1 Dinh nghia2.5 (Dinhnghlav~caecaul~nhthaolac dii'li~u).ChoffiQtquanh~ CSDLcochtianullngii'canh, trongh~CSDLtaquy tide: (i) MQtCalil~nhinsertlacaul~nhcod~ng: insert( rib riZ,..., rip; Context(Ajl =Cjb Aj2 =Cj2,", Ajk =Cjk) ) (ii) MQtdiu l~nhupdatelacaul~nhcod~ng: update( rib riZ,...,rip; ; ContexteAjl =Cjb AjZ =CjZ"'" Ajk =Cjk) ) (iii) MQt Cali l~nhdelete la Cali l~nhco d~ng delete( ril, riZ,...,rip; ContexteAjl =Cjl, AjZ =CjZ"'" Ajk =Cjk) ) Trongdo : . rit. riZ,.. ., rip la caequanh~matrendo caephepinsert,update'vadeletedti<Jc thvchi~n. . Vdi ( e =j, va1~f ~k ) ho~c( e=hva1~f ~q) thi: 26 -Ad Ii ten cac thuQctinh tren cac quail ht$rib riZ, ri3'"" rip - Cd c Dom(Ad),Defc Dom(Aef)la t~pcacia tri thuQcmi~ntritu'angungcua thUQctinhAd . . F =Ii daycacgiatrimoichocacthuQctinhc~n update ContexteAjl =Cjl, Ajz =CjZ,...,Ajk=Cjk) ={ t[Ajl, Ajz,..., Ajk] : 'ifAji (1 :s;i :s;k) , t[Aji] E Cji } du'<;5CgQi Ii di~u kit$nd~ xac dinh cac bQ cho insert, update ho~c delete. Trang chuangnay, thu~tngu Cali lt$nhdu'<;5cdungd~chi ho~cmQtCali lt$nh insertho~cmQtCalilt$nhupdateho~cmQtCalilt$nhdelete. Cho Q Ii mQtCali It$nh,ne'uki hit$u::5(Q)la t~pcacbQdu Iit$utrang::5thoa mandi~ukit$nContext(Aji=Cji,...,Ajk=Cjk) cuaCalilt$nhQ, thl: ::5(Q)={t[Ajb AjZ,...,Ajk ]:'\7'Ajl (1 :s;I :s;k), t[Ajd E Cjl }. Vi du 2.3:Xet hai Iu'<;5Cd6 quailht$R1(Ten,Tu6i, Mon) vi Rz (Ten,Tu6i, SV) trong vi dl,l2.1; r" rz Ii hai th~hit$ntu'angungcua Rl vi Rz . Gia saht$th6ngnh~ndu'<;5c caliIt$nh: insert(rl,r2;ContexteTen =A, Mon=D, SV ={M,N} ). Khido:::5(Q)={,} Voi mQt Call It$nhQ tren quail ht$ril[Xil], riZ[XiZ],"',rip[Xip],ta ki hit$u p XQ= U Xi) . Do coth~b6sungvio m6ibQcuat~p::5(Q)cacnullngucanhd~noco j=l th~Ii bQtrenthuQctinhXQvi quyt~cb6sungcacnullngucanhchocacbQcua 3(Q)sedu'<;5cthl!Chit$n husau: GidsittrangCSDLdficomr;itcaenullngilcdnh5), 27 bz,..., 8k' k la chi sffngrlcdnhcudCSDL, khido caenull ngrlcdnhdU:(Jcb6sungvao trong cae bQcua .3(Q) se dU:(Jcdanhchi s6la'n lu:(1tit:k+1, k+2... Voi m6i t~p3(Q) chungta dinh nghla: . T~p3rij(~) =3(Q)[Xij] p . T~p3rj\, riZ,...,rip(Q)=U 3rij (Q) )=1 p Trong do U Ia ph6p h<;1pthongthu'ong,khong ph,Hla phep h<;1pquan h~ )=1 D€ thc1y,cac b<)trong t~p 3riQ) chinh la cac b<)se du'<;1Cchen vao ho~csti'ad6i trongho~cxoa kh6i quan h~ rij Vi du.2.4: Xet Cali l~nhQ cuavi d\l 2.3 inserter\,rz;ContexteTen =A, Mon =D, SV ={M,N} » Khi do,neuchI s6 ngil'canhcuaCSDL co chu'arl va rz la k thl t~p3(Q), 3r1(Q), ~rZ(Q)va 3rl,rz(Q)cuaCalil~nhinsertla: ~(Q)={,<Ten=A , Tu6i=Ok+\'Mon =D, SV =M > } ~r1(Q)={}va ~dQ)={,<Ten=A,Tu6i=~+l,Mon=D, SV = M> } ~rl.rZ(Q)= {,, } 28 Nhuv~yvoidiu It$nhinserttrenht$th6ngc~nphaiinsert<Ten=A, Tu6i =~+1 , Man=D >vaoquailht$rl va haibQ,<Ten=A, Tu6i=Ok+l , SV =M >vaoquailht$r2 Dinh nghla2.6: (i) ChomQtcos0du lit$uDB cochuanullngucanh,Oila mQtnullngucanhxua't hit$ntrencQthuQctinhA . M6ibQt trongmQtquailht$mathoamanerA]=OidU<;1c gQila mQtngucanhCl;1CbQcuaOJ. T~pta'tcacacngucanhCl;1CbQcuaOJ trenDB au<;1cgQila ngucanhcuaOJ (Ky hit$ula ContextDB(oi)). (ii) Cho Q la mQtdiu It$nhtrencacquailht$ril[Xid , r12[Xi2],...,rip[Xjp];8t la null ngu canhxua'thit$ntrangcQtthuQctinhA . M6i bQt trangt~p:3rit.ri2,...,rip(Q)mathoa manerA]=OJdU<;1CgQila Q ngucanhCl;1CbQcua Oi.T~pta'tcacacQ ngucanhCl;1C bQcua OJau<;1cgQi la Q - ngucanhcuaOJ( Ky hit$ulaContex~(oj)). (iii) Cho OJva OJla hai null ngucanhxua'thit$ntrenclingmQtcQtthuQctinh,OJaU<;1C gQila coM ngucanhh~pbonOJhayOJaU<;1CgQila co N ngucanhrQngbon OJ(voi M, N la DB ho~cQ) neuvachineu : 'Iftk[X]E ContextM(Oj)luon :J tk'[X] E ContextN(Oj)saochotk ~ tk"Khi d6 taky.r hi~ulaContextM(oi)~ ContextN(oj)hayContextN(Oj)~ ContextM(Oj). Ne'uContextM(Oj)C ContextN(Oj)vaContextM(Oj)S ContextN(Oj)chungtavietla ContextM(Oi)==ContextN(Oj). Ne'u ContextM(Oj)C ContextN(Oj)va ContextM(Oj);z: ContextN(Oj)ta ki hit$ula ContextM(Oj)C ContextN(Oj)hayContextN(Oj)S ContextM(oi). Ne'ucoContextM(oi)C ContextN(Oj)taseki hit$ut~pContextN(Oj)- ContextM(Oj)= {t[X]E ContextN(Oj): iJ t'[X] E ContextM(Oj)ma t ~ t'}.x 29 Vi dl,l2.5:X6tCSDL g6mhaiquanh!$fl vafztrongbang6 va7 : Bang6 Giasah!$th6ngnh~ndu<;cCalil!$nh: Bang7 insert(rl,rz;Context(Ten=A ,Mon={B,C},SV ={M,N})) Khi d6 : :5 (Q) ={St, Sz, S3, S4}voi Sl =, tg= . Nhttv~yContex~(03)={ ts,t6,t7,tg},ContextoB(ol)={t[,tz},ContextoB(oZ)={t3, td f)~tX ={Ten,Tu6i, Mon} vaY ={Ten, Tu6i, SV}, rheadinhnghIa2.6,vi tl ~ts ;tz,t3 ~ ~; t4 ~ t7nenContextoB(ol)C Contex~(03),ContextoB(8z)C Contex~(03)x y vaContex~(03)-ContextoB(ol)={t7,tg}. 30 Ten ,;>. manf[ tum t[ A 8[ B tz A o[ C t3 A Oz C Ten ,;>. SVfz tum 4. A Oz N Sz = , S3 = , S4 = 3r[,rz(Q)=.{ts, , t7,tg}voi ts = ,, = , , , t7 = va M~nhd~2.1. (i)Quanh<$~ IaphanX<;lvab~ccfiu. (ii) Quan h<$==Ia quail h<$tl1ongdl1ong chungminh : Suy tI1;1'ctie'ptu dinh nghla quail h<$==va quail h<$C . M~nh d~2.2.Ne'uQ Ia mQtdiu -I<$nhtren cac quail h<$ril[Xil], rdXiz],...,rip[Xip]; bjJ,...,bjkIa tfftcacacnullngii'canhxu1thi<$ntrongt~p:5ril,riZ...rip(Q),thl : k :3ril,fiZ,...ripCQ)= UContextQ(bjh)U T h=1 trangd6 T ={t E 3 ril,fiZ,...rip(Q):t! }. Chungminh:suytn,I'ctie'ptu(ii) cuadinhnghla2.6. Djnhnghia2.7.rho bivabjIahainullngii'canhxu1thi<$ntrenclingmQthuQctinh trongCSDL . Ta vie'tbi ~ bj ne'uva chine'uContextDBCbi)~ ContextoB(bj)ho~cDB CantextDB(bj)~ CantextDB(bi). Djnhnghia2.8.MQtCSDL dl1<jcgQiIaCSDL nullngii'canhne'unhl1cacgiatrinull trangCSDL Iacacnullngii'canhvabi ~ bj thlb i =bj .DB Be'ndaychungtac6vainh~nxetv6nullngii'canh.Donullngii'canhIaph1;lthuQc VaGnhii'ngiatIi dffbie'trangCSDL nengiatIi cuachungphaic6ynghlatrenroan bQCSDL , tucIa m~cdlingl1oisii'd\mglamvi<$ctrentungquailh<$mQtnhl1ngcac thut\ICchen,sii'ad6ivax6adii'Ii<$utrentungquailh<$d6phainh1tqUailtrongroan bQCSDL. VI v~y,caikh6hancuanullngii'canhsovdicacki€u nullkhac la vi<$c xacdinhchungphuct<;lPhannhl1ngbli I<;lithongtinmachungcungcffpchoh<$th6ng IC;linhi6uhanrfftnhi6u.Tie'prheachungtatImhi€u cacquit~cchothut\ICchen, x6avasii'ad6idii'Ii<$u. 31 2.3.CACPHEPC~PNH~TTRONGCSDl NULL NGU Cr\NH Trong phftntntoc dii gioi thi~ukhai ni~mv€ t~p3 ril,fiZ,...fip(Q).Nhung bQ trongt~p3 ribr12,...fip(Q)cuacaul~nhQ chinhla nhii'ngbQsedu<;1Cchenvao , sii'a d6i trongho<)cx6akh6i cacquailh~rib ri2,",rip.Trang3 rihfiZ,...rip(Q)c6 thet6nt~i nhungbQkhongchuagiatri null ~ B6i voi nhungbQd6cacthaotacchen,sii'ad6i ho<)cx6adu<;1Cth1,fchi~nhoanroanbinhthudng. B~ngcachlo~ib6nhungbQkhong chuanullkh6it~p~ril,riZ,...rip(Q), cacqui tAcdU<;1Cxetduoidaychidanhchonhii'ng truongh<;5pmacacbQthamgiachen,sii'ad6iho~cx6ala nhii'ngbQkhongdftydu thongtin. Nho m~nhd€ 2.1,neutalo~ib6nhii'ngbQkhongchuanullkh6i t~p~rihriZ,...rip(Q), hayn6icachkhacneucoi J fil,riZ,...rip(Q)chig6mnhii'ngbQc6chuagiatrinullthl k tac6 ~ ril,riZ,...rip(Q)= UContextQ(8jh)voi8jh,...,8jkla tit cacacnullngii'cantxuit h=l hi~ntrongt~pJ ril, riZ,...rip(Q). 2.3.1.Qui tAc2.3.1( Cho thaotacchendii'li~u) Q la mQtCalll~nhinserttrencacquailh~rileri2,...,rip.Khi th1,fChi~nthaotac chendu li~u, neutrongt~p3 rihriZ,...rip(Q)cuacaul~nhinsertc6 chuamQts6 null ngii'canhthld6ivoim6inullngii'canh8jxuit hi~ntrong3 ril,fiZ,...rip(Q),h~th6ng seIdemITa: (i) NeutrongCSDL t6nt~inullngii'canh8ixuit hi~ntrenclingcQtthuQctinhvoi 8jmaContex~(8j)C ContextoB(8i)thlh~th6ngsekhongth1,fchi~nthaotacinsert. (ii) Neukhongxayra(i) vatrongCSDLt6nt~i8il,8iz,...,8ik(k~1)la t~ptit cacac null ngu canhxuit hi~ntrenclingmQtthuQctinhvoi 8j ma ContextoB(8il)C Contex~(8j)voi(1::;1::;k).Khi d6h~th6ngse: 32 . Ki~mITa,n€u k >1thltlmnullngucanhcochis6benha"ttrongdayOil,~Z,...,Oik ( giasala Oil)thaymQixua"thi~ncuaOil(2:::;1:::;k) trongCSDLbdiOil. N€u vi~c thaycac null ngucanhOil( 2:::; 1:::;k) bdi Oillam xua"thi~nmQtsO'nhungbQgi6ng nhautrongCSDL thlht%th6ngchi gill l<;timQtbQ. . Ki~m ITa n€u C ={Contexto~(oil)u ContextoB(oiZ)u ,...U ContextoB(oik)}1: Contex~(oj)thl thaymQi xua"thi~ncua OJtrongContex~(oj)bdi Oilr6i ti€n hanh insertcacbQthuQct;%pContextQ(oil)- C . (iii) N€u cahai truonghQp(i) va ( ii) d~ukhongxayra,h~th6ngse ti€n hanh insertcaebQthuQct;%pContex~(o). Vi dl;l2.6.Xet CSDL g6mhai quailht%rl(T~n,Tu6i , Mon), r2(Ten,Tu6i, SV), gia sah~th6ngl~nlUQtnh;%nduQccacCalil~nh: L1:insert(rl,r2; ContexteTen=A ,Mon={B,C},SV=M ) ). L2:insert(rl,r2;ContexteTen=A ,Mon=C,SV=N ) ). L3: insert(r!,r2; ContexteTen =A , Mon={B,C},SV ={l'vl,N} ) ). Khi do:T;%p3 (Q)va3 rl,f2(Q)cuaCalil~nhL1la : 3(Q)={Sh S2}, vdi Sl =, S2=. 3rl, r2(Q) ={tbtz,t3}vdi tl =, tz=, t3=. Nhuv;%y:ContextQ(ol)={thtz,t3}.Theoquititc2.1cacbQtJ, tzvat3seduQcchen VflOtrongquail h~rl va r2 : 33 Bang8 Bang9 Voi calil~nhL2taco: :J (Q)={s} , s =. .:JfJ, fZ (Q) ={t4,ts}voi 4 =,vats=<Ten=A, tu6i =oz , Sv =N > . Khi doContex~(02)={t4,ts}. Do ContextoB(ol)={tJ, tz, t3} g; Contex~(82)va Contex~(02)g ContextoB(ol)nen caebQtrongContex~(02)sedu'<;1edu'aVaGtrongquanh~fl va f2, dli 1i~utrongquan h~fl va fZse1a: Bang10 Bang11 34 Ten Tu6i Mon 01 Btl A tz IA 01 C fZ Ten Tu6i Mon t3 A 01 M fl Ten Tu6i Mon tl A 01 B tz A 01 C 4 A 02 C fl Ten Tu6i SV A 01 M A 02 N Vai Calllt$nhL3: :5(Q) ={Sl>S2,S3,S4}vai SI=, S2=, S3=<Ten=A ,Tu6i =03, Mon =B , SV=N>, S4= . 3rl,r2(Q) ={4J,t7,tg,tg}vait6=,t7= <Ten=A, Tu6i=03,Mon =C >,tg= , t9= . Nhuv~yContextQ(03)={t6,t7, tg,tg}. Trang truonghQpnay ContextoB(ol)u ContextoB(02)C: ContextQ(03)vi tl ~ t6 ,x tz,t4 ~ t7, t3~ tg,ts ~ tgvaiX ={Ten,tu6i,Mon }vaY ={Ten,Tu6i,SV }.Theox y Y - quita:c2.1ffiQixu:1thit$ncua02trongCSDL phaiduQcthayb~ng°1.M~tkhac ContextQ(03)- ContextoB(°z) =0 nenkhongcodulit$umaiduQcthemVaGCSDL Bang12 2.3.2.Quitile2.2( Chothaotacsti'ad6idulit$u) Bang13 rho Q Ia mOtCallIt$nhupdatetrencaequailht$rib ri2,...rip' Khi thvchit$nthaotac sttad6i dli lit$u,ne'utrongt~p3ril,ri2,...rip(Q)cua diu lt$nhupdateco chuamOts6 nullngli canhthi d6ivdi t:1tca caenull ngucanhOjl ,...,Ojkxu:1thit$ntrongt~p 3ril,riZ,...rip(Q), ht$th6ngseki6mITa: -Trang 35- rl ten Tu6i Mon tl A 01 B tz A 01 C r2 Ten Tu6i SV t3 A 01 N t4 A 01 M (i) Ne'utrongCSDL t6nt'.licacnullngucanhOhl,...,Ohkma~vxu!thil$ntrencling CQtthuQctinhvoi Ojv(1 ~v ~k) va Contex~(ojv)C: ContextoB(~v)thl hl$th6ngse k tht,tchil$nthaotacupdatecac bQdti lil$utrong UContextQ(Ojv)r6i tie'nhfmhinsert v=\ cacdtilil$uke'tquavaotrongCSDL. (ii) Ne'utrongCSDL t6nt'.licacnullngucanhOhl,...,Ohkma~vxu!thil$ntrencling cQtthuQctinhvoi Ojv(1~v ~ k )vaContex~(ojv)==ContextoB(~,)thlhl$-th6ngse : k * Tht,tchil$nthaotacupdatecacbQtrongUContextDB(Ohv) rheaeach: v=! Ne'ugiatritntockhiupdatelanullngucanhthlthaymQixuathil$ncuanullngti canhd6trongCSDL thanhgiatIi moi. * Ki€m ITane'uthaytrongCSDL saukhi updatec6xu!t hil$nbatkY hainullngti canh0,~oJ voi i ::j; j maContextoB(Oj)C:ContextoB(Oj)thlhl$th6ngsex6anhung bQtrongContextoB(Oj)vagill l'.linhungbQtrongContextoB(Oj). (iii) Ne'udi~ukil$n(i) ho~c(ii) khongdU<;1cthoaman,hl$th6ngsekhongth\ichil$n thaotacupdate. Vi du2.7:Xethaith€ hil$nrl varztrongbang14vabang15 Bang14 Bang15 -Trang 36- rl Ten Tu6i Man tl A 01 B t2 A 01 C t3 A 02 C fZ Ten Tu6i SV tl' A 01 M tz' A Oz N Giasa, ngu'oisadl,mgmu6nupdatedl1li~utrongquanh~rl bdiCalil~nh: update(rl;Mon=D, ContexteTen =A, Mon=C)) Ta co : Contex~U)3)={sd, Sl =.Nhu'v?y Contex~(83)C: ContextoB(82)={t3, t2'}' Theo qui dc 2.2 h~th6ngse th1!chi~nupdatebQ Sl trongContex~(83)voi ( Mon=D ) r6i insertbQs[ vaotrongquanh~rl . Nhu'v?y tadu'<;5Cquanh~rl va r2 nhu'trongbang16va 17: Bang16 Bang17 Tie'pthea,giasli'ngu'oisli'dl,mgmu6nupdatedl1li~ubdi Calil~nh: update(rl;Mon =D ,Context(HQten=A, Mon={B,C}, SV =M)) Khido:Contex~(84)={Sl, sz, S3},SI =, 8Z =va S3=. Nhu'V?yContextQ(84)==ContextoB(81). Theoquitilc2.2tadu'<;5Cquanh~rl varz nhu'sau: Bang18 Bang19 37 rl Ten Tu6i Mon tl A 81 B tz A 81 C t3 A 82 C t4 A 83 D rz Ten Tu6i SV tl' A 81 M tz' A 82 N rl Ten Tu6i Mon tl A 81 D tz A 8z C t3 A 83 D rz Ten Tu6i SV tl' A 81 M tz' A 8z N Saudo,giasanguoisad\mgl~iffiuo'nupdatedll1it$ubdicaul~nh: update(f[,fZ;Tu6i ='50',ContexteTen=A,Mon=C,SV=N) ) Khi do : contex~(b4)={4, ts}, vdi 4 =, ts=.NhUV?YContextoB(bz)==Contex~(b4). Theoquitilc2.2ffiQixua'thi~ncua-b2trongCSDL d~udu<Jcthayd6ibdigiat:ri50vi V?yquailh~fl va f2sedu<Jcthayd6inhutrongbang20va21: Bang20 Bang21 2.3.3.Qui tiic2.3 (chothaotic xoadll1i~u) Cho Q Ia ffiQt cau l~nh delete tren cac quail ht$fib fI2,...rip . Ne'u trong t?P 3 IiI,f12,...fip(Q) cuacaul~nhdeletecochuaffiQtso'null ngll canhva bjl, ,bjkla ta't cacacnullngllcanhxua'thi~ntrong3 fil,r12,...rip(Q).Thi h~tho'ngchith1,1'chit$nthao tacxoane'unhutrongCSDL t6nt~icacnullngllcanhbhI. . .,~ ffia bhvxua'thi~n trenclingcQtthuQctinhvdi bjv(1 :::;v :::;k ) va Contex~(bjv)==ContextoB(bhv)'Khi k d6h~tho'ngsexoata'tcacacbQtrongUContextDB(bhv) v=\ Vi du2.8. Xethaith€ hi~nfl vaf2nhutrongbang22va23: -Trang 38- Ten Tu6i . Mon bl Dtl A tz A 50 C t3 A b2 D I fZ Ten Tu6i SV tl A bl M . tz. A 50 N Bang22 Gic:ls11, ngu'dis11d~ngmu6nx6adl1li~ub~ngCalll~nh: Bang23 Delete(r]; ContexteTen =A , Mon =C ) ). I Ta c6 ContextQ(03)={t}voit =. Nhu v~y I i ContextQ(o3)C:ContextoB(ol) ={tt.tz},theoqui ta:c2.3h~th6ngkhongth\lchi~n I thaotacx6a. Gias11l~nhx6ati€p rhealaDelete(rl;ContexteTen=A, Mon =C , SV =N)) Khid6caebQ,va sebi x6akh6iquanh~rl. Djnhnghia2.9rho DB1vaDBzlahaiCSDL.Ta vi€t DBl C DBzn€u 'if t E DBl ~ luon3 t'E DBz saocho t ~ t. Djnhnghia2.10 (i)MQtCSDL nullngl1canhdU<;1CgQilakhongbi t6nthaithongtinkhi apd~ngqui ta:c2.1n€u CSDLcli c CSDLmdi. ~ (ii)MQtCSDL nullngl1canhdu'<;1CgQila khongbi t6nth:1tthongtinkhiapd~ngqui ta:c2.2va quita:c2.3n€u khongxayra trudngh<;1pc6haibQt va t' cuaclingffiQt quanh~rimat =1=t' Va t ~ t' l~iclingdu<;1Cupdateho~cdelete. rl -Trang 39- rl Ten Tu6i Mon tl A 01 B tz A 01 C t3 A Oz C- rz Ten Tu6i SV tl' A 01 M tz' A Oz N Y nghlacua(ii) la : ne'utrongCSDL c6 t6nt(;lihai bQt, t' yoi t -:t:.t' va t ~ t' 'i thlhainullngucanhtrenclingmOthuQctinhcuacuat vat' phaiphananhhaid6i tuQngkhacnhau, tucla, thongtinv~haid6ituQngkhacnhaud6c6th~la dohai nguoisadl;1ngkhacnhaucungca'p,VIv~yne'utrongWonghQpupdatevadeleteca 2bQt va t' clingbi thayd6iho~cclingbi xoasegayra t6ntha'thongtinchoh~ th6ng. DinhIy 2.1 MQtCSDL thuduQctitCSDL nullnguca.nhsaukhiapdl;1ngcacquita:c 2.1,Quita:c2.2vaQuita:c2.3v~nlaCSDL nullngucanh. Chungminh:D~chungminhdinh19,taphaichiravi~capdl;1ngcacquita:c2.1,2.2 va2.3luondambaatrongCSDL khongt6nt(;liba'tkI haigiatribjvaOJvoi i -:t:.j ma 8. ~ o. (*). 1 DB J TruonghQpquidc 2.1duQcapdl;1ng: Theoquita:c2.1,khiinsertduli~u,ne'utrongCSDL t6nt(;limOtgiatrinullc6DB- ngucanhh~phanho~crQnghanQ-ngucanhcuamOtgia tri null trongcaul~nh inserthlh~th6ngchiluugiatrinullnaoc6ngucanhrQnghall.Do d6phepinsert duli~urheaquita:c2.1khonglamxua'thi~nba'tkyhaigiatrinullOJvaOJvoii -:t:.j ma 8.~ 0.. 1 DB J TruonghQpquyta:c2.2duQcapdl;1ng: Ne'uxayra truonghQp(i), thayVIupdate,h~th6ngseth'!chi~nthaotacinsert. Theotrenvuachungminhquita:c2.1khonglamxua'thi~n(*). TruonghQp(ii) lahi~nnhien. Nhu'v~yquita:c2.2luondambaatrongCSDL khongt6nt';liba'tky haigiatri nu1l8jva OJvoi i -:t:.j ma°i~ OJ'DB -Trang 40- Truongh<;1pqui t~c2.3du<;1Capd\lng: Do tru'ockhi th1,fchi~nthaotacxoa,CSDL Ia CSDL null ngii'canh,Wc la trong CSDL khongt5nt(;libeltki hai,giatri OJva OJvoi i 1=j maOJ ~OJ' Khi qui t~c2.3 du<;1C apd\lng,dil'li~utrongCSDL khongbi sti'ad6i,VIv~ynokhongth~lamxuelthi~nOJ vaOJvdi i 1=j ma OJ~ OJ'DB Djnhly 2.2.CSDL sekhongbi t6ntha'thongtinkhiapd\lngquit~c2.1,quit~c2.2 vaquit~c2.3. Chungminh: Truongh<;1pquit~c2.1dU<;1capd\lng: Theoquit~c2.1,voi truongh<;1p(i) va(iii) tad~ucoCSDLclic CSDLmoj.Nhuv~y s; chiphaixettruongh<;1p(ii) cuaquit~c2.1: Xett la mQtbQbeltki trenquailh~rj thuQcvaoCSDLcli,ra rang: . Neu tit:C={ContextDR(8;1)u ContextDR(8;z)u... U ContextDR(8" )}thl t E CSDLmdi v~y3t'=tE CSDLmdid~t'~t. . Neu tEe thl qua trinhthaymQixuelthi~ncua 8j (2'5:P '5:k) trongCSDL bdi p Oilv~ndam baa 3t'~tco m~t trong CSDLmdi.Do t'~tnen 1'~t. V~y v~n ri ? :3t'E CSDLmdi de t' ~ t . Nhuv~y'it E CSDLculuon 3t'E CSDLmdima l'~t. TheodinhnghIa2.10tasuy raCSDL lakhongt6ntheftthongtinkhiapd\lngquit~c2.1. (ii)Truongh<;1pqui t~c2.2vaqui t~c2.3dU<;1Capd\lng: Giasti'co xayra truongh<;1phaibQt va t' cuamQtquailh~rj clingdU<;1cupdateho~c deletekhimat 1=t' val' ~ t . Khi dotheoquit~c2.2vdimQtnullngii'canhOJnaodo ri -Trang 41- com~trongcaul~nhQ thlluon 3c\ trent va Oiztrent' la hainullngucanhtrong clingmQtcQtthuQctinhvoi null ngucanhOJsaGcho ContextDB(8il)==ContextQ(81')(*) va ContextDB(8iz) ==ContextQ(OJ) (**). Tu (*) va (**) ta suy ra ContextDB(0, ) ==ContextDB(0, ), Wc Ia OJ ~ Oidi6unaykhongth€ xay ra trongmotz z I DB z . CSDLngucanh. Nhu'v~yCSDL lakhongbi t6nthttthongtinkhiapdt,mgquiHic2.2va2.3. 2.3.4.Nh~nxet Trangph~nnaychungtadffdi sauvaocachti€p c?nv~nhunggiatrinullngucanh. MQtnull ngucanhxutt hi~ntrongCSDL co ynghiadQngva dlt<;fcxacdinhbdi nhung iatridffbiertrongngucanhhi~nt~icuachung. f)i~uquailtrQngla vi~cxacdinhnhunggiatri nulltheocachnaycoth€ du'<;fCt nh roanbdih~thongvaVIv~yh~thongcoth6ki6msoatdu'<;fCchungtrongCSDL. 42 A '" " .. - - - ... 2.4. PHAN CAP CAC CIA TRI NUll VA NCO'NCHIA DO'lIl.=U Phftnnaychungtaxemxetcaetlnhhu6ngd:1nde'ns1Icftnthie'tphaiphan cc1pcaegiatrinull.Tren cdsddochungtaseurnhi~uv€ ngl1nghladuli~ucua nullngucanh,ngunghladuli~udochophepmdrQngcaepheptoandq.is6se xemxettrongphftn2.5. 2.4.1PHAN CAP GIA TRf NULL 2.4.1.1Null ngilcanhchliabittvanullngilcanhmd Th1!chc1tcuanullngucanhIa d~bi~udi€n nhunggiatri chu'abie'tvapht;l thuQcVaGngucanh.D6i voim6inullngucanh,ngu'oitaxemxetcacd~ctru'ng ngucanhcuachung,kyhi~uchungbdicacki t1l81,82, 83,... D~nghiencUungunghladuli~ucuanullngucanh,tru'oche'thayxetunh hu6ngsail: Choquanh~Gido-Vien(ten,tu6i,man)1u'Uthongtinv€ hQten,tu6ivaman d?ycuacacgiaovienthuQcmQtkhoacuamQttru'ongdq.ihQc,giasah~th6ng nh?ndu'QCcacthongtin: (i) ComQtgiaovientenlaA, 45tu6i. (ii) ComQtgiaovientenIaB hi~nkhongdq.ymanhQcnaco (iii) ComQtgiaovientenlaC dangdq.ymQtmanhQc. Thongtin (i) mah~th6ngnh?ndu'Qcla thongtin"md"v€ mandq.y.Theo thongtinnay,giaovientenIa A coth~dq.ymQtmanhQc,coth~dq.ynhi€u man hQc,ho~cclingco th~khongdq.ymanhQcnacoD~bi~udi€n thongtin v€ man d?y,ne'uh~th6ngsadl,mgki hi~u8 thlcomQtvilnd€ d~trakhixetngunghla duli~ucuanullngucanhngu'oitad€u phaigallchonocactlnhhu6ngd~coth~ d?idi~nchomQtgiatri xacdinh,ho~cvaigiatri xacdinh,ho~cchomQtgiatri 43 khongt6nt~i.Do doquatrlnhxemxetngunghiadulit%ucuacacquanht%chua giattinullsephuct~plenra'tnhi~u. Thongtin (ii) maht%th6ngnh~ndttCJc,chobie"tgia tti t~ithuQctinhman<4y cuagiaovien B 1.1khongt6nt~i.TrongtrttdnghCJpnay,ngttdita co th€ sa d\;mg nullkhongt6nt~idnethaychomQtnullngilcanho.Vi giatti cIne1.1giatti xac dinhnennennomangnhi~uthongtinhongiattikhongxacdinho. Thongtin (iii) chobiergiaovienC dangd~ymQtmanhQcnengiatti null t~ivi trimanhQcsebi€u thi1.1cot6nt~imQtgiattinhttngchttabiet. Tu tlnhhu6ngtrenchotha'yvi~cphanlo~inullngilcanhchophilhCJpvoi tungtrttdnghCJpthieuthongtin1.1vi~clamc~nthiet. TrttdnghCJp(i)[3]diisad\lngytttongnull "mo"cuaGottlobvaZicari[12]: Chot 1.1mQtbQdil lit%u,A 1.1mQthuQctfnh,neut[A]dttCJcganla nullmo (viet t[A] =open)thl thuQctinhA sedttCJcxemxetdttoigia thietthegioi md (OWA) vaVIthet[A]coth€ bi€u thichomQtgiattikhongt6n't~i,coth€ bi€u thi chomQtgiatti xacdinhhoijccoth€ bi€u thivai giatti xacdinh(noicachkhac mQithuv~nconlamdd6ivoit[AD Y nghiacuanullmdg~ngi6ngnhttynghiacuanullkhongcothongtindttCJc nullmd A TA1tn , Khon.gco (unk l null) Nhi~u11i tl1 G"'" h,:! 1trila tqc~t e (unknull) Hinh1 1 Giatqc~th€ 1tri 1tri (unknull) (unknull) 1 1 Gia 11ic th Gia 11ic th 44 trinhbaytrongph~n2.1.Tuynhiendaivdinullma,ng1.toitamuonnh!nm~nh khiac<;lnh"ma" cuachung. Giangnhu'nullkhongcothongtin,nullmala nguyenthuyhonnullkhong t6nt<;livanullchu'abitt. IDnh1la cayphanc!pcacgiahi null,nochoth!ys1,1'thactri~ncuanullma thongquanullkhongt6nt<;livanullchu'abitt. Khaini~mnullngucanhmacoth~du'<JcmafQngnhu'sail:mOtnullngucanh maIamOtnullmavagiatrinulldoph1,1thuQcVaGngucanhcuanotrongCSDL. Nhu'v~yvdi tfu'ongh<Jp(i) co th~sad1,1ngmQtnullngucanhd~bi~udi€n thongtinbi thitu. Tru'ongh<;5p(iii) coth~sad1,1ngullngG'canhchu'abittd6bi~uthimOtgiatq t6nt<;linhu'ngchu'abie!vaph1,1thuQcVaGngucanh. Nhu'v~yntuchungtacoimOtCSDLnullngucanhg6mconullnguca.nhchu'a bitt,nullngG'canhmavanullkhongt6nt<;lithlkhongcotlnhhuangthituthong tinnaGla khongbi~udi€n du'<;5Cbai s1,1'ktt h<;5pgiuabaki~unull tren. Ntu ki hi~ucacnullngG'canhchu'abitt bai01.02,... thlcacnullngucanhma se du'<;5Cki hi~ubai cac ki t1,1'nhu'Pl, P2,... Vi du2.9: xetba th~hi~nfa,fb,fckhacnhaucuaR Bang! Bang2 Bang3 45 fa Ten Khoa f)i<$n_thoi NAM LY 8543647 HUNG LY 81 KIEN LY dne rb Ten Khoa f)i<$n_thoi KIEN LY 854647 KIEN LY Bl rc Ten Khoa f)i<$n_thoi KIEN LY 8543647 BI B2 B3 Trongth~hi~nfa,khongthUQCtinhnelocogiatrimd. ydi th~hi~nrb,coth~suyranhungs1!ki~nsau: . Kienleinhanvienduynhit . KhoaLy leikhoaduynhit . KiencomOts6di~nthoC;li:8543647 . Kiencoth~khangcoho~c oncothemmOtvelis6di~nthoC;linua Ngoelifa,khangmOts1!ki~nnelokhacIadung! Gia trimd~1trongrbkhangconghiathuOctfnh£)i~n_tho<:iicomi~ngiatri leicact~ph<jp.Ntu Kien co themvelis6di~nthoC;lithlnhungs6di~ntho<:iinelyse du<jcbi€u di~nbdi mOtt~pnhungbO, vdi cling gia tri ten velKhoa con s6 f)i~n_thoC;lithlkhacnhau. Th€ hi~nrcma tamOtCSDL dudigiathitttht gidimd.Dotit canhunggia t:IithuOctinhcuabOthlihaileimdnenchinoidu<jcKienIa vi~ctC;likhoaLy, co s6di~nthoC;lilei8453647.Ngoeliracoth~connhungnhanvienkhacchuadu<jc bitt. 2.4.2.T~pkhanangcuaquanh~nullngutanh: [3] ChoR(AI. ...,An)leimOtlu<jcddquanh~du<jcxacdiMtrenmOt~pthuOc tinhAI, ...,An. Y di m6i thuOctfnhAi, ta kf hi~umi~ngia tri tu'dngU'nglelDom(AJ. Mi~n cuaR leitfchf)~cacDom(AI) XDom(A2)X ...XDom(An)velkf hi~uleiDom(R). ChungtamdrOngm6i mi~nDom(Aj) thelnhDom*(Aj)b~ngcachthemvelo mOtt~phUllhC;lncackf hi~unull:Dom*(Ai)=Dom(Aj)u A il U Aj2U {dne}trong do: . Aillelt~pcacnullngucanhchuabittveldu<jckfhi~ubdi81.82,... AiZlelt~pcacnullngucanhmdveldu<jckfhi~ubdi~h~2,.... . doeleikf hi~uchonullkhangt6ntC;li . Dom(AJ,Ail,Ai2,{dne}leicact~pkhanggiaonhau 46 Tuongtv mQtsv mdrQngcuaDom(R)1aDom*(R)=Dom * (AI) X ... X Dom*(An). MQtquailh<$null ngii'canhcuamQt1u<;jcd6 Ria mQtt~pconcuaDom*(R). Nhii'ngquailh<$nhuv~ydu<;jcki hi<$ub~ngcacki tv thuongnhur, rr, ... va dtt<;jc gQila cac quailh<$mQtph£1n.T~ptit ca cac quailh<$mQtph£1ntren1tt<;jcd6 R du<;jcki hi<$u1are1t(R). Cac quailh<$khongchuanull du<;jcgQila quailh<$loanph£1n,t~ptit ca cac quailh<$loanph£1ntren1u<;jcd6R du<;jcki hi<$u1are1(R). Cho t 1abQcuamQtquailh<$null ngii'canhr, ne'ut[Ai] khacnull tavie't t[Ai]1. Ki hi<$uopend~chImQtnullngii'canhmdvaunkd~chIIDQtnullngii'canh chuabie't.T~ptiltcacaenullngii'canhchuabie'tho~cnullngii'canhmddtt<;jcgQi chung1acacgia tIi chuaxacdinhconnhii'nggia tri khacnull ho~cdnedtt<;jcgQi 1acacgia trtxacdinh. Cho tl va tz1ahaibQco th~chuanull tren1tt<;jed6R. Ala IDQtthuQctinh,ta ki hi<$utl[A]==tz[A]ne'u 1. tl[A]!,tz[A]!vatI[A]=tz[A],ho~e 2. tl[A] =8j , tz[A] =8j"vai =j, ho~c 3. tI[A] =~j, tz[A]=~jvai =j, ho~c 4. t[[A]=dnevatz[A]=dne. Ta vie't[[X]==tz[X]ne'uVA EX: tl[A]==tz[A]. Ynghlaeuaphepsosanh==la ki~mITaSvtrlingnhauv~ki hi<$ucuacae gia tri trongCSDL. Vi d\l 3 ==3; 8j ==8j;~j==~jvadne==dne. Ngu<!cl(;livoi phepsosanh==la phepsosanh=/=.Vi d\l3=/=4;8i=/=8j; 8i=/=~i; -Trang:47- Binh nghiafilachungtasephatbi~usaildayd~C?PWi t?pkhiinangcua mQtluQcd6quailht$.M6i khiinangcuarnQtquailht$r sechtYat?Pta'tcii cacbQ thuQcr saukhidiithaythe'cacgiatIi nullbdicacgiatIi xacdinh.Vi d\l,xetmQt quailht$r: {}vdirni~ntIi cuathuQctinhgifi'ala {I,2,3}.Khi domQt khanangcuar la'varnQtkhiinangkhacsela. Khi thaythe'nhfi'ngiatri null,dotinhcha'tcuacacnullkhongt6nt~inen chungta se duara rnQtki hit$u.1 d~bi~udi~nchodnetrongt~pkhii nang. Vi d\l:xetrnQtquailht$r : ,khidovdi rni~ntIi cuathuQctinhcu6ila {c,d}thlcohaikhanangchor lava.Nhuv~ytacoth~coi.1 latricuadne.Tie'ptheochungtadinhnghiav~t~pkhanang. Dinhnghia2.11ChoR(Al, ...,An)la rnQtluQcd6quailht$.MQtkhiinangcuaR la rnQt~pcon cuaDomJ.(R)=DornJ.(Al)x ...x DomJ.(An)tro-ngdoDom\Aj) = Dorn(Aj)u {1.}vaI ~i~ n. T~pta'tcacackhanangcuaR duQcki hit$ub~ngR. Dinhnghla2.12.Chor la rnQtquailht$,a Ia rnQtnullngfi'canh(a E L1ilU L1iZU {dne}) xua'thit$nt~icQtthuQctinhA, (i) MQtgiatriho~crnQt~pgiatriV duQcgQilamQtphepthe'coth~cuaane'u: . V =0 ho~c . V:t=0 va: Ne'ua E L1ilthlV E Dom(A) Ne'ua =dnethlV =.1 Ne'ua E L1iZthl:ho~claV =.1ho~claV =={bt.bz,...,bm},trongdo:m~1 vavdi 1~i ~rn: bi E Dorn(A). 48 (ii) Ne'uv lamQtphepthe'coth€ cuaa,taki hi~u r' =S;(r) lamQtquail h<$co du<;1ctti'r b~ngcach: . Ne'uV= 0 thlkh6ngth\fchi~nthaythe'a,Wcla r' =r. . Ne'uV :1=0 thlthaymQixuc1thi~ncui atrongr bdiV. (iii) Cho ai, az,... ,akla cacnull ngucanhxuc1thi~ntrongr; VI>Vz, ...,Vk tu'dng ling la Cae phep the' co th€ ?cua aJ, az, ..., ak. Khi do r' =Sv,V2"..YK(r) la quailh~codU<;1Ctti'rb~ngcach: Voi 1~i::; k:ala2..ak' . Ne'uVi * 0 thlthaymQixuc1thi~ncuaaitrongr bdiVi . Ne'uV =0 thlkh6ngth\fchi~nthaythe'ai. Vi du2.10:Xetr: {,}voimi€n thuQctinhd~ula {l, 2,3}, khi do r1 =S~I(r)la quail h~ : {,} fz =S{1,3}(f)la quailh~:{,,,}va ~l r3=s.l (f) la chinhquailh~r.Odne M~nhd~2.3 [3]Ne'uf[, rz,...,rmlamquailh~trenclingmQtlU<;1Cd6; ai, az,..., aklacacnullngucanh;Vi laphepthe'coth€ cuaai(1::;i::;k).Thl taco: . ) vv v ) -SVIV2 VK () S VlV2"",VK (1 S 12"'" K (flU fZ U...U fm - GIG2..Gk' fl U...U G,a,..ak" fm).GtG2..Gk' - ii) SV,V2"",VK (f\i1fZi1...i1fm)= S V1V2"'" VK(fdi1...i1SVIV2"",VK (rm). GIG2..Gk' ala2..ak' ala2..ak' 2.4.3.Ngfinghiadfi li~uvamohinhcuaquaDh~nullngllcanh[3] Cho r la mQtquailh~trenlu<;1cd6quailh~R(AJ, ...,An); r E R lamQtkha nangcuar. Djnhnghia2.13Chot lamQtbQcuaquailh~r ; tria mQtbQcuar .Tanoit suy fa tr (ki hi~ut t>tr ) ne'uvachine'uvoi 1::;i::; n it nhc1tmQttrongb6ndi€u ki~nsauphaidU<;1Cthai man. 1. t[AJ ==tP [Ai] ho~c 49 2. t[AiJ ==openho~c 3. (t[AiJ ==linkva tr [Ai]=/=.1)ho~c 4. (t[Aj]==dneva t~ [Ai] ==.1)r Vidu2.11 : t=(l, open,unk,dne,5) I>(l,2,4,.1,5);tl> (1,.1,1,.1,5). Dfnh nghia 2.14.MQt kha nang} cuar dU<;5CgQila mQtmohinhcuaquailh~f n€u va chIn€u no thoamanbadi€u ki~nsail: 1. Voi mQinull ngucanhat. az,...,amxuc1thi~ntrongf,:1 VI>V2, ...,Vmsaccho , v v 'r - S I ",.,. ~- m a I a 1" a fII 2. '\j L E r , khan!!t6n tai L 'E rr ~. r : ( t ~ +=t ~ ') \'a voi 1 s; i S;nr r (t ~ [AiJ +=.1 =>t, [AiJ=t ~'[Ai]r r r 3.E r => r =0. Truoc h€t, chungtaduafa nhunggi,aithichng~ngQn chotUngdi€u ki~ncua ainhnghla. Ddu hen 1 auafarangbuQcla m6inullngucanhchuabi€t chIdu<;5cthay th€ bdiduynhc1tmQtgiatrixacdinhchl.i'khangdu<1cthayth€ bdimQt~pgiatrio Hannua,noyetic11ubdimQtbQtr trongr phaidu<1csuyfa it nhc1tumQtbQ cuar. V€ m~tn!cgiac,di~unayconghla,f phaidu<1cdi~ngiaiduoigiathuy€t th€ gioidongtrukhinocoxuc1thi~nnhunggiatrinullnguciinhmdnaodo.E>i~u ki~nnayclingkh~ngdinh,m6ibQcuar (trufa haibQ, <dne,dne,...,dne» phaisuyra it nhc1tmQtbQtrongr . C1,1th{ - NhungbQmachIchl.i'aduli~uxacdinhcuar (khangconull)d€u phaixuc1t hi~ntrongmahlnhr . 50 -NhungbQc6 chuamQtho~cnhi€u nullngucanhchuabie'tphMguyra it nh<ltmQtbQtrong r trongd6 m6i null ngu canhchuabie'tdU<;1cthaythe'bdi nhunggiatriduli<$uxacdinh. - NhungbQc6chuamQtho~cnhi€u nullngucanhmd phaiguyramQtho~c nhi€ubQtrongr , trongd6 m6inull ngucanhmdho~cdU<;fCthaythe'bdi mQtgia tri 1.,ho~cdU<;fCthaythe'bdi mQtgia tri xac dinh , ho~cclingc6 th~thaythe'bdi mQt~pgiatrixacdinh. - Cu6iclingthlm6inullngucanhkhongt6nt~imaxu<lthi<$ntrongmQtbQ naGd6cuar sedU<;fCthaythe'bdigiatri1.trongmQtbQtudngungcua r Ddu kien2:bi~udi~nngunghIam~nhcuanullngii'canhkhongt6nt~i.N6 kh~ngdinhne'ut6nt~imQtbQt;: trongr mac6vaigiatri 1.thlkhongth~t6n t~ib<ltkymQtbQnaGtrongr makhacvditr chibdithaythe'mQtvaigiatri1. vdi nhunggia tri xacdinh.Vi d\!,xetquailh.Khi d6,di€u ki<$n1 cho dng ;: phai chuabQ , con di€u ki<$n2 l~i kh6ng cho phep bQ xu<lthi<$ntrong r , trongd6x 1amQtgiatridii'1i<$uxacdinh. Cu6icling,Di~ukien3 kh~ngdinh,ne'uc6bQtrongr thl r bit buQcphaila t~pr6ng.E>i€uki<$nnayxacdinhthemngii'nghIachodne. E>~cbi}vaquailh<$r6ng0 d€u c6chungduynh<ltmQtmohlnh,d61a0. Neu r chithoamanDi~ukifn1thi r du(fcgqilamohinhyeucuar. Dfnh nghia2.15Cho r 1affiQtquailh<$c6 th~chuanull.Ta n6i ngunghIacuar 1a t~pt<ltcacacmohlnhcuar (ki hi<$u: MODELS(r)). Dfnh nghia2.16.Cho r va r' 1ahai quailh<$trenclingmQt1U<;fCd6, r va r' du<;fc gQi1atuangduangngilnghiane'"uvachi ne'uMODELS(r) =MODELS(r'). 51 Vi du 2.12:Voi quailht$r va s nhutrongbang4 va bang5 thlMODELS(r)= MODELS( s ). ~ ~ ~ ~ Bang4 Bang5 Dinh nghla2.17.Choa,bE Dom* (A), vdi A 1amQtthuQctinh.Ta noi, b xdcdfnh hana (vie"tb ~a) hay a it xdcdfnhhanb (vie"ta ~b) ne"uva chi ne"umQttrong flamdi~ukit$nsailduQcthai!man: 1. a==b. 2. a==open. 3. a==link,vabL 4. a==link,vab==link. 5. a==dne,vab==1. Nhuv~ygidtrfopenLaitxdcdfnhhanmQtgiat:rilinkvagidtrj unk itxdc djnhhanmQtgid trfxdcdfnh. Tti dinhnghla2.17,taco th~md rQngkhai nit$mxac dinhhan ho?c it xac dinhhanchohaibQcuamQt1uQcd6quailht$. Dinh nghla 2.18.Cho r va r' la hai quail ht$trenclingmQt1uQcd6; t la mQtbQ cuaquailht$r; t' 1amQtbQcuaquailht$r'. Ta noi t' xdcdfnhhant ( ki hit$ut' ~t) ho~ct it xdc dfnh han t' (ki hit$ut ~ t') ne"uva chi ne"uvdi 1 ~ i ~ n thi t[Ai] ~ t'[Ai]. Vi du2.13:t=~ ; t~;t~ ;t~;t 1:,. M~nhd~2.4 (i) Ne"ut[ I>tzthi t[ ~tz. 52 Vi du 2.12:Vd'iquanh~r va s nhutrongbang4 vabang5 thlMODELS(r)= MODELS( s ). ~ ~ ~ ~ Bang4 Bang5 Binh nghia2.17.Choa,bE Dom*(A),vd'iA la mQthuQctinh.Tan6i,bxdcdtnh hona (vietb ~a)haya it xdcdtnhhonb (vieta ~b)neuvachineumQttrong namdi~uki<$nsaudu<;1Cthoaman: 1. a==b. 2. a==open. 3. a==link,vab!. 4. a==link,vab==link. 5. a==cine,vab ==1. Nhuv~ygidtrtopenfa itxdcdtnhhonmQtgiatri linkvagidtrtunk itxdc dfnhhonmQtgid trtxdcdtnh. Ta dinhnghla2.17,ta c6 th~ma rQngkhai ni~mxac dinhhonho?c it xac dinhhonchohaibQcuamQtlU<;1cd<3quanh<$. Binh nghia 2.18.Cho r va r' la hai quanh~trenclingmQtIU<;1cd<3;t la mQtbQ cuaquailh<$r; t' la mQtbQcuaquailh<$r'. Ta n6i t' xdcdtnhhont ( ki hi<$ut' ~t) ho?c t it xdc dtnh hon t' (ki hi<$ut ~ t') neu va chi neu vd'i 1 ~ i ~ n thi t[AiJ :5;t'[AiJ. Vi du2.13: t=~ ; t~;t ~;t:5;;t ~. M~nhd~2 .4 (i) Neu t1[>t2thi tl ~t2. 52 (ii) Neu tl :::;tzva tz!Thl tj I>tz. (iii) Neu tl :::;tzva tz:::;t3thl tl:::;t3. (iv) Neu tl :::;tzva tzl>t3thltll>t3. Dinh nghia 2.19.Cho r va s la hai quailh<$trenclingmQthl'<;1Cd6,r du<;1CgQila xacdinhbons ( ki hi<$ur ~s) hays du<;1cgQila it xac dinhbonr ( ki hi<$us :::;r) neuvoi mQibQtsE Sluant6nt<:libQtrE r saGchotr ~ ts. Neur ~ svas ~ r chungtavietr ==s. D~tha'yquailh<$:::;la phanX<:lvab~Cc~u.Quanh<$==la quailh<$tu'ongduong. Be)d~2.1 Cho r va s la hai quail h<$tren cling mQtlu<;1cd6, neu yIODELS(r):;:: 0 val'vl0DELS(r)c MODELS(s)thl: (i) r~s (ii) 'v"trE r, :3ts E S : ts:::;tr Vi du 2.14 : Voi quan h<$r trong Bang 6 va quail h<$strong Bang 7 thl MODELS(r)c MODELS(s) . Dinhly 2.3.Neur vas la tltongdltongngunghlathlr ==s. Chungminh.Suytrt,{ctieptuB6d~2.3. Dinh ly 2.4.Chor va s la haiquailh<$trenclingmQtlu<;1cd6.Neu t6nt<:licacnull ngucanhaI, a2, ...,ak trongs va t6nt<:licacpheptheco thSVi cuaai (1 :::;i:::;k) VIV2..Yk saGchor =S (s) MODELS(r) c MODELS(s). ala2..£lk .. 53 81 8z 1 1 83 1 81 82 2 1 83 2 I I2 2 34 5 6 4 5 6 Bang6 Bang7 2.3.1.4.Ml}tvai vi dT!- Xet lU<;1Cd6quanh~R =(X,Y, Z) vdiDorn(X)={a,b};Dorn(Y) ={I, 2} vaDorn(Z)={c,d}.Chungtaseduafa nhii'ngth~hi~nkhacnhaucuaR vaban lu~nv~figii'nghlacuachung. R6 fang,quanh~chichuanhii'ng ia hi dii'li~uxacdinhseco duynha't rnQtrnohlnh,mohlnhdochinhl~quanh~f. Vi dl,l,xetth€ hi~nfl cualU<;1Cd6R trongBang8 Bang8 Hi€n nhien,f I coduynha'trnQtmohlnh~trongBang9 Bang9 Bang10 Do tinhcha'tcuanullngii'canhIDanenf2se co 8 rnohlnhkhacMall. " ra " rb 54 " rc rl X Y Z A 1 C A 2 D " X Y Zrl A 1 C A ') D Xet ffiQtth hin f2khac (Bang 10)cua R: [2] X Y Z A 1 C A 1 D A 2 C A 2 D A 1 C A 1 D A 2 C A 2 D B 1 C A 1 C A 1 D A 2 C A 2 D B 2 C A 1 C A 1 D A 2 C A 2 D B 1 D " rd " re " rf " " rg rh D~tha'yconhungkhaniingcuaf2khanglamahlnh.Vi dlf: Titp thea,xetquailh<$f3cochuanullngucanhchU'abitt: Bang11 55 A 1 C A 1 D A 2 C A 2 D B 2 D A 1 C A 1 D A 2 C A 2 D B .1 C A 1 C A 1 D A 2 C A 2 D B 1 .1 A 1 C A 1 D A 2 C A 2 D B .1 D A 1 C A 1 D A 2 C A 2 D B 2 1. A 1 C A 1 D A 2 C A 2 D .1 .1 .1 A 1 C A 1 D A 2 C A 2 D A .1 C '3 X Y Z A or C A or D B 02 C r) cob6nmohlnhsau: 56 UjJ A 1 C AID A 1 D B 1 C B 2 C " " ra rb A 2 C - A 2 C A 2 D A 2 D B 1 C B 2 C " " rc rd V oi quan ht$ r) ne'u chi dung null chu'abie'td biu din thongtin khong dy duthls6mohlnhtanglenra'tnhiu r) X Y Z A link C A link D B link C Bang12 A 1 C A 1 C A 1 C A 1 D A 1 D A 2 D B 1 C B 2 C B 1 C A 1 A 2 C A 2 C A 2 D I A 1 D A 1 D B 2 C B 1 C B 2 C A 2 C A 2 C A 2 D A 2 D B 1 C B 2 C cotammohlnh Nhl1v~y,trongmQtquailh~nullng11canhne"unhus6giatrinullcocling ng11canhcangnhi~uthlm6irangbuQcgi11achungsecangcaovadodos6mo hlnhmachungxacdinhseit honnhi~uso voi nh11ngtrl1C1ngh<;1pthongthl1C1ng khac. Cu6icling,chungtahayxetquailh~r4 cochuabaki4unullkhacnhau Bang13 Do trongr4cobQnengia tri ~1cuabQkhongth4dl1<;1C thaythe"b~nggiatfi.l trongP(dodi~uki~n2).VI v~y,trongquailh~nay~1chI coth4dl1<;1cthaythe"boigiatri 1ho~cgiatri2. Nhl1v~yr4cob6nmohlnhsauday: A B -L 1 C D 57 r4 X Y Z A dne C B 81 D B 1 D " ra [I C B 2 D " rc A 1. C B 1 D B 2 D " rb A -L C B 2 D B 1 D " rd , "" ,,? " 2.5. CAC PHEP TOAN QUAN HI; MO RQNG Trangphgnnaychungtaseapd~ngcacke'tquav~ngunghladuli~ud~md rQngcacpheproanquailh~chonullngucanh. 2.5.1.Quanh~IDQtph~nd1iqcphanho~ch Khi nghienCUllv~thongtinkhongdgydu,ngu'aitathU'angd~tradiuhGi: The'naola giatri chanly cuabi6uthucx =y khimax ho~cy ho~cax vay la null? Theoquaildi~mcuaCodd[13],bi~uthucx=y dtrensechoke'tqualamQt giatri chanly chu:abitt.Do v~yCoddgioithi~umQtlogicbatri (0,0),1)thay chologichaitri(0,1)thongthU'ang.Voi logicbatrinay,mQigiatrichanly chU'a bie'td~udU'<;1Ckyhi~ubdi0)vadodocacgiatrichanly d~ucoth~du'<;1ehilltrong CSDL. Khi tht,tehi~nmQtvaipheproand~isotrencaequailh~mQtphgn,ngU'aita thU'ang~pphainhungbi~uthucsosanhd~ngx=ydtren.Bi~unayselamxua"t hi~nmQtsogiatri ehanly 0)trongnhungquailh~ke'tqua.Voi cacquailh~ke't qua,mQtbQduli~ukhongxua"thi~n(j)chinhla bQthGamanpheproand~iso, ngU'<;1Cl~inhungbQcoxua"thi~n(j)chi la nhlingbQcokhdndngthGamanphep roand~iso.BiskupgQinhungbQkhongchua0)la nhungbQchilechilnvanhung bQchua0)lanhungbQcothi.Dov~y,ongnhlnnh~nm6iquailh~mQtphgng6m haiphgn,thanhphgnthunha"tbaag6mnhungbQch~ch~nvathanhphgnthuhai baog6mnhungbQcoth~.Nhungquailh~du'<;1Cxemxettheoki~unaycondu'<;1C Maier [14]gQila nhungquailh~dU'<;1Cphanho~ch.MQtquailh~du'<;1cphanho~ch coth~dU'<;1CxemnhU'mQtc~pdU'<;1Cs~pcuahaiquailh~mQtphgn. SR Dfnh nghia 2.20.Cho rl va r2 lahaiquailh~trencling ffiQtIU<;1cd6 R. Chungta gQic~pdU<;1cs<1p(rl' r2)Ia ffiQtquailh~dU<;1cphanho~chr n€u rl!1 r2= 0 va SURE (r)=rl, MAYBE (r)=r2' SURE(r)du(/cgQifatq,pcacbQchilcchilncuar vaMAYBE(r) fatq,pcacbQ cothi cuaT. Dfnhnghia2.21.Chor laquailh~du<;1cphanho~chtrenlu<;1Cd6R, s laquailh~ ffiQtphfintrenR. Chungtan6is xffpxi r, kyhi~us [>r n€u vachin€u SURE (r ) u MAYBE (r) :) s :) SURE(r). Khi bi~udi~nffiQtquail h~du<;1Cphanho~ch,nhungbQch<1cch<1nse n~m dU<;1Cnganeachvoi nhungbQc6th~bdi ffiQtduangaUtnet. Vi d1,l2.15Choria quailh~trongBang 14,slva S2lacacquailh~t5~gBang15 vaBang16.Khi d6Sll>r vaS21>r. Bang14 Bang15 Bang16 sC) r A B C 1 81 4 PI 5 6 ...................................................................................... 2 dne 4 1 3 6 51 A B C 1 81 4 PI 5 6 1 3 6 52 A B C 1 81 4 PI 5 6 2.5.2.Ham kha DangPOSSNC[4] Trongph§nnaychungtaxemxetquanh<$chuanullngucanhdU'oidlJ.ng du<;cphanho~chthanhcacbQchilcchilnva cacbQco thl Ta diM nghiaham khanang:POSSNc(r)={s / s lamohlnhye'ucuasnaGdomas[>r}. M~nhd~ 2.5 Voi quan h<$du<;cphan ho~ch r va ham kha nang POSSNC (r) ={s / s lamohlnhye'ucuas naGdomast>r} thlPOSSNc(r) la xac dinhduynhfft. M~nhd~2.6Chor vaslacacphanho~chtrenlu<;cd6R vahamkhanang POSSNc,ne'ut6nt~inulngucanhal,az,...,aktrongsvat6nt~icacphepthe'co th~Vi cuaaj (1~i ~k ) saGcho i) s =S VI,V: , ...Vk (s) QI ,Q2, ..£lk ii) 'if t- E SURE(s) :J tr E SURE(r) : tr=t-s s iii) 'iftr E r :J t- E S : t r =t-s s thlr ~s. Vi du2.16Voi haiquanh<$r vasnhutrongBang17vaBang18thl r ~ s Trangvi dl,lnay, S = S78 (s) 81131 Bang17 Bang18 nO s A B C 81 1 82 81 2 3 .........................................-...........-...- 3 1 4 2 1 5 4 5 83 1 2 3 r A B C 7 1 82 7 2 3 3 8 4 ...................................................................... 2 8 5 4 5 83 M~nhd~2.7Chor vas la cacquanht$duQcphanho?-chtrenluQcd6R vaham khaDangPOSSNC,n€u POSSNC(r)c POSSNC(s)thl i) 'If tsE SURE (s)3 trE SURE (r) : ts::;tr ii) 'If tr E r 3 ts E S : ts::;tr Vi du217:Vdihaiquailht$r vasnhutrongBang19vaBang20thl POSSNC (r) <;fPOSSNC (s) . Bang19 Bang20 Trongvi d1,lnay,bQ 1;... 2.5.3.Md rQngcaepheptoaDquailh~[4] a) MlJ ri)ngpheploanch{Jn PheptoaDchQnduQcapd1,lngtrenmQtquailht$.K€t quacuapheptoaDchQn chomQtquailht$mata"tcacacbQcuaquailht$d6phaithoamanmQtdi~ukit$n . xacdinh.Trangph~n aychungtasexethaid?-ngcuaphepchQn: "A =a" ho~c "A =B ", trongd6A vaB latencacthuQctinhvaa lamQtgiat:rixacdinh.Chor lamQtquailht$duQcphanho?-chtrenluQcd6R ;A ER.ChungtadinhnghTa: crNC (r) =s(R)A=a Trangd6 SURE (s) ={tIt E SURE(r)vat [A]=a} 01 r A B C 7 1 81 7 2 3 3 8 4 """"""""""""""""""""""""""""""""""""""""". 2 8 5 s A B C 81 1 dne 81 2 3 """"""""""""""""""""""""-"-"-"'-"""'" 3 1 4 2 1 5 MAYBE(s)={tIt E MAYBE (r)vat[A]=a}u {t'l 3tErma t[A] E ~i1U ~hvat'[A]=a;t'[B]=t[B]VdimQiB*A} a NCA=B (r) =s(R) Trongdo SURE(s)={tIt E SURE(r)vat [A]=t[B]} MAYBE(s)={tIt E MAYBE (r)vat[A]=t[B]}u {t'l :3tErma t[A] E ~i1u ~i2vat'[B]!; t'[A]=t [B];t'[C]=t [C]vdi mQiC:;i:A}u {t'I 3tErma t [B] E ~ilu ~i2vat'[A]! ; t'[B]=t [A];t'[C]=t [C] vdi mQiC:;i:B}. Vi dl,l2.18Vdi quanh~r (A, B, C) cuavi dl,l2.15taco~~~ (r) la quanh<$ trongBang21vaa NC (r) 1aquanh<$trongBang22A=B Bang21 Bang21 M~nhd~2.8. a NC lamQtmdfQngthoadangcuaa tl1dngungvdihamA=a A=a khanangPOSSNC M~nhd~2.9.Ne"u11 t, t' E SURE(r) saDchot[A] E ~ilu ~i2vat[A] =t'[A] thl crNC lamQtmdfQngchinhxaccuacrA=atudngungvdihamkhanangPOSSNc. A=a M~nhd~2.10.crNC lamQtmdrQngthoadangcuacrA=Btl1dngungvdiham A=B khanangPOSSNc. n2 51 A B C 1 °1 4 """""..............................................,.......................... 1 5 6 1 3 6 52 A B C .........................................-..-.................... 1 1 4 5 5 6 M~nh d~2.11.Ne'u 3 t, t' E SURBer) saGcho t[A] E LlilU Lli2; t[A] =t'[A] va t[B] E Llil U Lli2t[B] =t'[B] thl crNC lamQtmdrQngchfnhxaccuacrA=BtltdngA=B . lingvdihamkhanangPOSSNc. b)MlJ rQngphepklt . Chor(R)vas(S)la cacquanh~du'<;1cphanho~ch,trongdoR n S =x. BQtr E r va tsE s du'<;5CgQila tu'ongh<;1ptrenX ne'uV A E X ho~ctrCA)!va trCA)=ts(A) ho~c trCA) E Llil U Lli2ho~c ts(A) E Llil U Lli2. Chungtadinhnghlar t><JNCS =q(RS) Trongdo SURE(q) ={t(RS)I 3 tr E SURBer), 3 tsE SURE(s) saGchot(R)=trvareS)=td va MA YBE(q) = {t(RS)I t6nt~icaebe>tu'ongh<;5ptr E r"vatsE SsaGcho: t(R-S)=tr(R-X),t(S-X)=ts(S-X)vaV AEX, ne'utr(A)!thlteA)=tr(A) ngu'<;1cl~i teA) =ts(A)}. Vi d1,l2.19:Giasar vas la haiquanh~trongBang23vaBang24thlr t><JNCSla quanh~trongBang25 Bang23 Bang24 01 r A B 81 1 3 82 ----------------------------- 4 2 s B C 1 2 82 4 83 6 Bang25 Dfnh nghla 2.22.Cho r va s la haiquailh~null ngucanhdU<;1Cphanho~ch, r la mahlnhye'ucuar' voir'r>r, slama hinhye'ucuas' vois'r>s.Khido r vas dU<;1cgQila tuongh<;1pne'unhutrongquatrinhthaythe'cacnullngucanhtU'r' thanhr vas' thanhs cacgiatrinullclingxua"thi~ntrongr' vas' d~udl1<;1Cthay the'nhanhau. Dfnh nghla2.23.Cho r va s la hai quailh~null ngucanhdU<;1Cphanho~ch. Chung ta dinh nghla : POSS(r)r><Jsir ePOSSNcCr),s ePOSS NcCS) va r, s la tl1ongh<;1p}. M~nhd~2.12.Phepke'tn6i r><Jtl1ongdng voihamkhaDangPOSSNc. 2.5.4.Nh~nxet Trongmahlnhdii'li~uquailh~Ii cosdtrungtamcuacaengan,ngutruy .. va"nVI v~yvi~cmdrQngd~isO'quailh~chocaegiatri null Ii vi~elamquail trQng,m~cdli da:khangdl1ara mQtd~isO'quailh~mdrQngdftydu,nhl1ngda: trlnhbay dU<;1cphuongphapgiai quye'tva"nd~khi cO'giingmdrQngmQtvai phep 114 rr><1NCs A B C 8, 1 2 3 82 4 _. 81 1 4 81 1 6 - 3 1 2 3 83 6 4 2 4 4 2 6 tmin ehQnlQe.CaeM<$nhd~tIt2.8- 2.12ehotha'ythongtinkhongbi ma'tmat khitht,tehi<$ncaepheptoand~i86trendl1'li<$ueuaCSDL nullngfi'eanh. (1:)