Luận án Một số vấn đề tối ưu hóa truy vấn trong đa cơ sở dữ liệu

(;lihQcco nhi~uCSDL c1;1cbQ g6mcacphongban,van phongdangky, phongcongchuc,hi~phQisinhvien,... Dii' li~uIu'utrongcacCSDL nayg6msinhvienvagiaovien.Chungtasii'd1;1ng 40 DB.R.adtSchithuQctinha cuaquanh~R cuaCSDLDB.LuQcd6cuacacCSDL naynhusan: CSDL PhongDangKy -Registra'sOfficeDatabase(ROD) SV_Nu (#s,ten,dtb,duong,thanhpho,quan,#covan) SV_Nam (#s,ten,dtb,duong,thanhpho,quan,#covan) GV_nil (#g,ten,vanphong) GV_nam(#g,ten,vanphong) CSDL KhoaMayTinh-ComputerScienceDepartmentDatabase(CSD) Sinhvien(#s,ten,phai,diachi,#covan) Giaovien(#g,ten,phai,vanphong) Diachi(#g,duong,thanhpho,quan) CSDL Lien Ke't -AssociationDatabase(ASD) Sinhvien(#s,ten,sothich,#covan) Diachi (#s,duong,thanhpho,quan) Giaovien(#g,ten,naill,nil, vanphong) CSDL KhoaCongNgh~Di~n-ElectricalEngineeringDepartment Database(EED) Sinhvien(#s,ten,naill,nu , #covan) Giaovien(#g,ten, vanphong) CSDL Hi~pHQiSinhVien-StudentUnionDatabase(SUD) Sinhvien(#s,ten,phai,#covan) Diachi(#s,duong,thanhpho,quan) Giaovien(#g,ten,phai, vanphong) 41 MQthtgcd6TichHgp- An IntegratedSchema(IS) Sinhvien(#s,ten,phai,sothich,dtb,duong,thanhpho,quan,#covan) Giaovien(#g,ten,phai,vanphong,diachi) TrongcacCSDL tren,cos'!d\:tngdQv~luQcd6.Vi d\:t,CSDL phongdangky (ROD),sinhvien, giaoviennitvanamduQcluutrongcacquanh~khacnhau, trongkhiCSDL khacthichIluutrongthuQctinhphdi.HaydiachilamQtquanh~ trongASD vaSUD,trongkhitrongcacCSDL khacnolamQthuQctinhhaymQt t~pthuQctinh.Gia sii'tfttcacacsinhvien phaidangky dphongdangkyvacac sinhvienclingt,!dQngla thanhviencuahi~phQisinhvien.Tli do,nh~nthiy ROD.SV_Nuva ROD.SV_NamtuongduongcacbQtrongSUD.Sinhvien.Do do,. ne'uco truyvftntoanc\:tc:timten,diachIg6mtenduong,thanhph6,qu~ncua sinhvien,thith'!chi~ntrongSUD,cophepke't: SUD.Sinhvien.#s=SUD.Diachi.#s Ne'uth'!chi~nd ROD: ROD.SV_Nu(ten,duong,thanhpho,quan) U ROD.SV_Nam(ten,duong,thanhpho,quan) R6 rangCalltruyvftntrencoth€ duQctraWiquahaiCSDL khacnhau.Trong m6itruongt6ngquatconhi~ulo~id\:tngdQluQcd6,d€ sosanhdQphuct~pcua quatrinhth'!cthitruyvin trongcacCSDL khacnhaula mQttacv\:tkh6ngdon .? gmn. B€ giaiquye'tvftnd~tren,chungtaxemxetanhhuangcuatit cacaclo~i d\:tngdQluQcd6d6ivoi chiphixii'ly truyvftn.Cac lo~id\:tngdQnayduQcdo 42 b~ngcachgall tr<;mgs6chochung.Gia sO'c6 mQtlaqc d6 tichhqptrongMDBS. Ne'umQtmanhdii'li~utronglaqcd6 c~cbQdaqcmo taphlic t(;lphon tronghiqc d6tichhqp,trqngs6nhosedaqcgall.Ngaqcl(;li,thitrqngs6ldn . Khi truyva'n to~mc~cdaaratronglaqcd6tichhqp,cacthuQctinhvaquanh~daqctruyxua't daqcbie't.B~ngcachkiemITacaclo(;lid~ngdQlaqcd6trongcacCSDL vatinh trqngs6cuachung,seHmdaqctr(;lmt6tnha'tdexO'ly truyva'n. Phfintie'ptheo,chungtasedinhnghlacackhaini~mtaongdaongngii'nghla vaph(;lmvi cacm6ilienh~giii'acacquanh~tttongdaongv~m~tngii'nghla.D1!a vaoph(;lmvi m6ilienh~nay,cactruyva'nth1!chi~ntrencacquanh~sec6cung ke'tqua. 3.2.2Caekhainiem. Dungkhaini~mnaydetimcacCSDL ITav~ke'tquatruyva'nnhanhau.Hai quanh~la taongdaongngii'nghlane'ucacm6ilienh~giii'acaclo(;livav~tthe tttonglingcuachungla nhanhau.Vi d~,haiquanh~SinhvienvaSvienla taong daongngii'nghlavi cungamchithongtinv~sinhvien.Tuynhien,Sinhvienva Nhanvienthikhongtttongdaongngii'nghlavi cacm6ilienh~ giii'acaclo(;liva v~thecuachungkhacnhau. Hai quanh~taongdaongngii'nghlac6thekhongcungt~pthuQctinh.Vi d~, SinhvienvaSvientttongdaongngii'nghla,nhangt~pthuQctinhthikhongtttong daong.ThongtincuaSinhvienhaduong,thanhpho,quantrongkhicuaSvienla diachi. 43 Cacth'!cth~trongthe'gidith'!cdu'<Jcthamchie'ubdicacquanh~tu'dngdu'dng trongcacCSDL khacnhaucoth~lienquanvoi nhau,thongquacacrangbuQc toanVyn(RBTV).TrdI~ivi d~cuacacCSDLtren,tacocacRBTV: . Tilt casinhvienphaidangkydphongdangky. CSD.Sinhvien.#sc (ROD.SV_Nu.#su ROD.SV_Nam.#s) EED.Sinhvien.#sc (ROD.SV_Nu.#su ROD.SV_Nam.#s) . Tilt casinhviend~uIathanhviencuahi~phQisinhvien (ROD.SV_Nu.#su ROD.SV_Nam.#s)=SUD.Sinhvien.#s . M6i sinhvien chidu'<JcphephQcmQtkhoachinh. CSD.Sinhvien.#sn EED.Sinhvien.#s=0 . M6i sinhviendu'<Jctt!do thamgiahi~phQilien ke't. ASD.Sinhvien.#sn EED.Sinhvien.#s=0 ASD.Sinhvien.#sn SUD.Sinhvien.#s=0 Ngoaifa,concomQtph~thuQCgiii'akhoacuaquanh~SinhvientrongASD vakhoacuaquanh~SinhvientrongRODvaSUDnhu'sau: ASD.Sinhvien.#sc (ROD.SV_Nu.#su ROD.SV_Nam.#s) ASD.Sinhvien.#sc (SUD.Sinhvien.#s) D,!avaocacRBTV tren,chungtad~dangnh~nracacquanh~co cungdii' li~u,haycacdii'li~uchangcheo,cacdii' li~uriengbi~t.Chung tadinhnghia ph{lmvi cuaquanh~R, ky hi~uScope(R),Ia t~pcacth'!cth~the'gioi th'!c, Ia cacbQcuaquanh~R. Haiquanh~Rl vaRzgQiIatu'dngdu'dngv~m~tngii'nghia ne'ucom6ilienh~v~ph~mvi: 1) Tu'dngdu'dng: 44 Scope(R1)=Scope(Rz) 2) Chl1'atrong: Scope(R1)c Scope(Rz); Scope (R1) ::::>Scope (Rz) 3) Ch6ngcheo: Scope(R1)n Scope(Rz)* 0 /\ Scope(R1)~ Scope(Rz) /\ Scope(Rz)~ Scope(R1) 4) Rieng bi~t: Scope(R1)n Scope(Rz)=0 ? 3.2.3Anh hu'O'ngvaphanlo~idyngdQgiii'acacCSDLcycbQ Trongphannay,chungtakheiosatv~caclo~idQngdQgiuacacCSDL.Sau do,segalltrQngs6chocacthuQcHnh.CactrQngs6nayv~sausedungdc5xac dinhcacCSDL cothc5thl1Chi~ntruyva'nloancQcvdidQphl1'ct~pithall. 3.2.3.1Dilngd9gj{lacaeCSDL Ba thanhphanchinhcuaCSDL la:giatri,thuQcHnh,quaDh~.Tn do,chialam 6 lo~idQngdQ:gid trj - gid trj, gid trj - thuQctinh,gid trj- bang,thuQctinh- thuQc tinh,thuQctinh- bang,bang- bang. . BQngdQgid trj - gid trj (V-V): Lo~inayxua'thi~nkhiCSDL dungcacmotelkhacnhauchocunggiatr!dii' li~u.Co 3 tru'onghQpxua'thi~n:bic5uthl1'c,donvi vadQchinhxac.Vi d1;1 45 d~ngdQddnvi giuacacnguyent~nhU'USD,Yen;di~ms6to'0de'n100 thayvi A de'nE (d~ngdQvedQchinhxac). . B~ngdQgicitrj - thuQctfnh(V-A): Khi clingmQtthongtinnhU'ngbi~udic3nHimQtgia tri trongmQtCSDL, con CSDL khacthiIacacthuQcHnh.Vi d~,giatricuathuQcHnhphaicua CSD.SinhviendU'QcmotaHithuQctinhnamvanutrongEED.Sinhvien. . B~ngdQgicitrj - bang(V-T): Khi cacgia tri thuQctinhtrongmQtCSDL dU'Qcbi~udic3nthanhcacbang trongCSDL khac.Vi d~,SV_NuvaSV_NamIacacquaDh~cuaRODbi~u dic3ncacsinhVieDDamvasinhVieDnIT.TrongkhitrongCSD, thongtin phaidU'QcmotaIacacgiatri. . B~ngdQthuQCtfnh- thuQctfnh(A-A): B~ngdQnayxua'thi~ndovi~csitd~ngcacdinhnghlakhacnhauchocac thuQcHnhtU'dngdU'dngngunghlatrongcacCSDL khacnhau.Vi d~,diachi Ia mQthuQctinhtrongCSD.Sinhvien,trongkhinodU'Qcbi~udic3nthanh3 thUQctinhduong,thanhpho,quantrongIS.Sinhvien. . B~ngdQthuQctfnh-bang(A-T): Khi mQthuQctinhcuamQtCSDL dU'Qcbi~udic3nthanhmQtbangtrong CSDL khac.Vi d~,diachiIamQthuQctinhtrongCSD.SinhviennhU'ngdU'Qc bi~udic3nthanhquaDh~DiachitrongSUD. . B~ngdQbang-bang(T-T): Khi vi~cmotathongtintrongmQt~pcacbangngunghlatU'dngdU'dng 46 trongrnQtCSDL vdit~pcacbangkhactrongrnQtCSDL khac.Vi d~, IS.Sinhvienco d~ngdQbang- bangvdiASD.SinhvienvaASD.Diachi. 3.2.3.2 Gan trpng56" TrongrnoitruongMDBS co luQcd6tichhQp,st!biendichcuatroyvanloan c~cdt!avaoluQCd6tichhQp(IS)nay.MQttroyvanloanc~cthuongyellCallcac dii'li~utUnhi~utr(;lrn,nghiala troyvancoth~duQcthihanhbAngnhi~ucach,va taHrncachxii'ly t6iu'uhoat6tnhat.Co th~conhi~ucachtichhQpluQcd6vacac cachnaykhongbi anhhuangtrongvi~ct6iu'uboa.£)~ngdQluQcd6gayrast! khacnhautrongtht!cthithaolac loanc~ctrongCSDL c~cbQ,vaungvdirn6i d~ngdQ,rn6itrQngs6se duQcgall. XernxetDBMS xii' ly rnQtroyvan, c63thaolacdin ban:chQn,chie'u,ke't. VI v~y,d6ivdirn6ithaolacquaDh~optht!chi~ntrenthuQctinha cuaIS, taco th~dungrnQtrQngso'd~danhgiadQphuct(;lpkhi chuy~nthaolaccoth~tht!c hi~ntrenCSDL c~cbQdb.£)~dongian,tanoitrQngso'duQcgallcho[oF,a,db] vdiynghianhu tIeD.Co tru'onghQpkhichuy~nd6ithaolackhongcod~ngdQ giii'acacthuQctinhtrongcacbang.Khi d6,trQngso'khongduQcgallchothuQc tinhnao.Thayvi v~y,noduQcdungchogiaido(;lnsaukhitdngtrQngsoduQclien ke'tvdirnQtke'ho(;lchtht!cthiduQctinh.Phant6ngtrQngs6duQctrinhbaytrong phansau.Quy lu~tgall trQngs6t6ngquatnhusau: 1. Ne'uthuQctinhacuaIS vacacthanhphantu'ongduongtrongCSDLc~cbQ db(coth~lagiatri,t~pthuQctinhho~cquaDh~myIO(;lid~ngdQ)duQcmo tahoanloannhunhauthitrQngso'cua[oF,a,db]laO. 47 2. Ne'uthaotacth~chi~ntrenthuQctinha cuaIS vdidQph1i'ct(;lpthip honl thaotacduQcchuy~nd6itu'ong1i'ngtrenCSDL cvcbQthltrQngs6cua[op, a, db]<O. 3. NguQcI(;li,ne'uthaotacth~chi~ntrenthuQctinha cuaIS vdidQph1i'ct(;lp caohonthaotacduQcchuy~nd6itu'ong1i'ngtrenCSDL cvcbQthltrQngs6 cua [op,a, db]>O. 4. Ne'uCSDL cvcbQdbkhongco thuQctinhtu'ongdudngvdi thuQctinh a cuaIS,ho~cthaotacoptrena khongth~chuy~nd6ithanhbit ky thaotac tu'ongduongnaocuaa trongdb,trQngs6seduQcgallIaX. D~dongian,chungtachixemxet3thaotacchQn,chie'u,ke't. a)TrongslfIrongIrlll1nghdpdungdothuoctinh- thuoctinh Xemvi dVcuacacCSDL truongd(;lihQc.ThuQctinhdiachicuaCSD.Sinhvien co dvngdQthuQctinh- thuQctinhvdi duong,thanhpho,quancuaIS.Sinhvien. DvngdQnayco2 Io(;licon: . mQtthuQcfinkV(jimthuQcfink (1:m)va . mthuQCfinkvoin thuQcfink(n:m) TruonghQpdvngdQm:nIanhi~udvngdQ1:md 2quanh~.Dodo,tachidin xettruonghQp1:m.SaDdo,taxemxettruonghQpIS gill vai trc>mthuQctinh haynguQcI(;li. TruonghqpA: IS dongvaifro mthUQctinh 1Di;>phuct1).pcua mi;>tthaotacam chi chi phi tht,tchi~nthaotacoVi d\1di;>phlic t1).pcua phepke"tcaDhdnphepch9n. 48 PhepchQn Sii'd~ngCSD vaIS.Tacotruyva'n: sedU'CJcdichsangtruyva'ntrenCSDvdidi~uki~nchQndiachilike '%TPHCM%', TrongIDQts6trU'onghCJp,ne'uke'tqualakhacnhausegalltrQngs61ax, nghlala truyva'nkhongthc3th1!cthidU'CJctrongCSDL c~cbQ.Ne'uke'tquala nhU'nhau, chiphith1!cthi2 thaotacchQntren2CSDL lanhU'nhau,trQngs6th1!chi~nphep chQnthanhphocuaCSDlaO. Phepchie'u ] MQtphepchie'ukhongthc3xii'ly dU'CJctrongCSDL c~cbQne'uthuQctinhtruy va'ntrongIS cod~ngdQthuQctinh- thuQctinhvdiCSDL c~cbQ.Vi d~: select thanhpho from Sinhvien khongth1!cthidU'CJctrongCSD.Vi v~y,trQngs6th1!chi~nphepchie'utrenthuQc tinhthanhphod CSD(nghlala [chieu,thanhpho,CSD])dU'CJcgalllaX. Phepke't Sii'd~ngCSD vaIS.Tacotruyva'nke'ttrenthuQctinhthanhpho: select * from Sinhvien,Giaovien where Giaovien.thanhpho=Sinhvien.thanhpho 49 select ten from Sinhvien where thanhpho='TPHCM' khongthethl.l'chi~nduQctrenCSD.Dodo,[ktt,thanhpho,CSD]laX. TruonghqpB: IS dongvaifro mQtthuQctinh Khanangkhaccualo~idt;mgdQlamQthuQctinhcuaIS duQcbiendienthanh nhh~uthuQctinhtrongCSDL c~cbQ.Luc do,mQttruyva'nchQntrenthuQctinh doncuaIS thuongkhongthedichtrendi~uki~ncuanhi~uthuQctinhkhaca CSDL c~cbQ.Vi v~y,trQngs6cuaphepchQntrongtruonghQpnayla X. Tuy nhien,ne'uMDBS co theghepgiatri cacthUQCtinhtimkie'mtuCSDL c~cbQ thanhmQtchu6iva sosanh(nghlala phepchQnagiaido~nxii'ly san)thitruy va'ncothethl.l'cthiduQc.Lucdo,trQngs6<0dot6ngphicuavi~cthl.l'chi~nphep chQna giaido~nxii' ly san.TruonghQpchie'uvake't,vi~cbiendichtrathanh tamthuongvatacotheboqua.Xema [8]decothongtinchitie'thon. b) TTongs{f(TongtrIllInghdpdungdo(huoctinh-bang Tuongtl.l'a phantrudc,diachicuaCSD.Sinhvienco d~ngdQthuQctinh-bang vdibangSUD.Diachi. TruonghqpA: IS dongvaifro thuQctinh PhepchQn Giasii'CSD cocungluQcd6vdiIS.Tacotruyva'nchQn: 50 select #s from Sinhvien where diachi='22To RienThanh,QI0, TPRCM' khongth~duQcdichdtravaoduong,thanhphova quan.Do do, [chQn,diachi, SUD] la X. Tuynhien,nGuMDBS coth~xii'ly sailsailkhidiin6igiatriduong, thanhpho,quanvasosanh,troyva'ncoth~thtrcthiduQc.Nhungdophaitinht6ng phicuavi~cthtrchi~nphepchQntrongMDBS,trQngso'[chQn,diachi,SUD]<O. Ngoaifa, th~mchiMDBScoth~xii'ly sailtroyva'nnay,coth~cohonmQthuQc tinh trongbangcuad~ngdQthuQctinh- bang,lienquaDtrongtruyva'n.Trong truonghQpnay,troyva'nchQnduQcdichthanhtroyva'nkGt.Xemvi d~mQtroy va'nloanc~c: select #s from Sinhvien where diachi='22To HienThanh,QI0, TPHCM'andphai='nil' duQcdich thanh: select #s from Sinhvien,Diachi where duong='22To HienThanh'and thanhpho='TPHCM' and quaD=' QI0' and phai='nil' and Sinhvien.#s=Diachi.#s co th~thtrcthid SUD.Cacgiatriduong,thanhpho,quaDduQCghepvasosanh vdichu6i'22To HienThanh,Q10,TPHCM'.D6ngthoi,phepkGtduQcb6sung themvaophepchQnd~thtrcthitroyva'nd CSDL c~cbQ.PhepkGtb6sungnay khonggayfa ba'tky thuQCtinhd~cbi~tnao nhungdovi~cchiacacthuQctinh thanh2 bang,DentrQngso' sekhongduQcgalldGnba'tky thuQctinhnaocua CSDL loanc~c.Trongtru'onghQpnay,trQngso'chiduQctinhkhi t6ngtrQngso' cuamQtkGho~chthtrcthiduQctinh. Phep chiGu ] 51 GiAsii'IU'qcd6tichhqpISgio'ngCSD.Tacotroyvanchie'u: select from diachi Sinhvien dU'qcdichthanh select from duong,thanhpho,quan Diachi co thc3'thl}'cthid SUD.BQphuct~pcda2 truyvanla nhU'nhau.Do do, [chieu, diachi, SUD] =O. TU'dngtl}'phepchqn,ne'utroyvanchie'u: select from ten,diachi Sinhvien dU'dcdichthanh select from where ten,duong,thanhpho,quan Sinhvien,Diachi Sinhvien.#s=Diachi.#s cothc3'thl}'cthid SUD.Tuynhien,ngoaiphepchie'u, c6themphepke'tnentrqng so'« 0 ) dU'qctinhtronggiai do~nsankhi t6ngtrqngso'cdaCSDL dU'qctinh. Phepke't GiAsii'IU'qcd6tichhqpISgio'ngCSD.Tacotroyvanke't: select from where Sinhvien.#s,Giaovien.ten Sinhvien,Giaovien Sinhvien.Diachi=Giaovien.Diachi 52 dU'<;1Cdich thanh select from where and Sinhvien.#s,Giaovien.ten Diachi,Giaovien Diachi.duong=Giaovien.duongand Diachi.quan=Giaovien.quan Diachi.thanhpho=Giaovien.thanhpho M~cdli3di~uki~nke'tlienquand giaido~nsau,nhU'ngcacphepke'tnaytren cling quan h~.Trngso'cua [kft, diachi, SUD] =0 . TU'dngtVnhU'tren,giasacotruyva'n: select from where Sinhvien.ten,Giaovien.ten Sinhvien,Giaovien Sinhvien.Diachi=Giaovien.Diachi dU'<;1cdi h thanh select from where Sinhvien.ten,Giaovien.ten Sinhvien,Diachi,Giaovien Sinhvien.#s=Diachi.#sandDiachi.duong=Giaovien.duongand Diachi.quan=Giaovien.quanand Diachi.thanhpho=Giaovien.thanhpho co th~tht1cthi dU'<;1cd SUD, nhU'ngco themdi~uki~nke't(Sinhvien.#s= Diachi.#s)nentrngso'<O.Khi phepke'tphatsinhdocacthuQctinhn~md cac quanh~khac nhaucua CSDL c~cbQ,trngso'chi dU'ngso' dU'<;1Ctinh. TruonghqpB: IS dongvaifrobang Phep chn 53 Giasii'luQcd6tichhQpIS gio'ngSUD(trongdodiachiduQcmotalaquanh~- bang). Giasii'cotmyvanchQn: duQcdichthanhtruyvancodi~uki~nchQndiachilike '%TPHCM%'trongCSDL Cl;!CbQCSD.Tuongnr tru'onghQptht1chi~nphepchQntrongdl;!ngdQthuQctinh- thuQctinh,truyvanhQpl~haykhongphl;!thuQcvaoMDBS. Ne'uMDBS khong thexii'ly saD,trQngso'[chqn,thanhpho,CSD] la X. NguQcl~i,trQngso'<0 khi t6ngphixii' ly santrongMDBS. Giasii'cotruyvan: select * from Sinhvien,Diachi where Sinhvien.#s=Diachi.#sandthanhpho='TPHCM' and phai='fill' duQcdich thanh select * from Sinhvien where phai='fill'anddiachilike '%TPHCM' co thetht1cthiduQclIen CSD.Luc do,truyvantht1cthitrenCSDdongianhon trenIS dotranhduQcphepke'tm~cdil cophepchQnd giaido~nxii'ly saD,nen trQngso'>O.Tuongnrcactru'onghQptren,trQngso'nayseduQctinhkhi t6ng trQngso'duQctinh. Phep chie'u ] 54 select * from Diachi where thanhpho='TPHCM' Giasd'luqcd6tichhqpIS giO'ngSUD(trongd6diachiduqcmotalaquanhc$- bang). Giasd'c6truyvanchieu: select thanhpho from Diachi khongth€ th'!cthiduqctrongCSD.Dod6,trqngso'cua[chieu,thanhpho,CSD]la x. c) Trongsfffrontfrtidnghdpdungdoria tri-thuoclinh Nhudathaolu~ntrongphfin3.1,phaicuaIS.Sinhviend~ngdQgiatr!- thuQc tinhvoi thuQctinhnam,nucuaEED.Lo~id~ngdQitkhixayfa. TruonghqpA: IS dongvaifrogiatr! Phepchqn Giasd'c6truyvanchqntrenthuQctihhphaicuaIS.Sinhvien: duqcd!chthanh c6th€ th'!cthitrongEED voigiasd'cacgiatr!cuathuQctinhnuvanamlaYes hayNo.TIT truyvantren,trqngso'[chQn,phai,EED]=O. 55 select ten from Sinhvien where phai='nu' select ten from Sinhvien where nu=Yes Phepchie'u ] Giii sii'cotruyva'nchie'utrencacthuQctinhcuaIS.Sinhvien: select from ten,phai Sinhvien duQcdichthanh select from ten,nil, nam Sinhvien co th€ thl.l'CthitrongEED vdiphit6nxii' ly cua2 truyva'nlIen la nhunhaunen trQng s6 [chie'u,phai, EED] =O. Phepke't Giii sii'cotruyva'nke'tcuaIS.Sinhvien,va luQcd6cuaCSDL c~cbQdbnhu sail: Sinhvien(#s,ten,naill,nil,#covan) Giaovien (#g,ten,naill,nil, vanphong) Truyva'nloanc~csail: select from where * Sinhvien,Giaovien Sinhvien.phai=Giaovien.phai duQcdich thanhtruyva'ntrongCSDL c~cbQdb: select from where * Sinhvien,Giaovien Sinhvien.nu=YesandGiaovien.nu=Sinhvien.nu 56 union select * from Sinhvien,Giaovien where Sinhvien.nam=YesandGiaovien.nam=Sinhvien.narn Trongtruyva'nct;lcbQ,b6 sungphepke't,phephQiva2 pheptoanchQn.Phi t6nthlfChi~nphepke'tvaphephQixemlanhunhauvaIdnhonnhi~usovdiphep chQn.Vi v~y,trQngso'cda[kef,phai,db]nhohon0 nhi~u.MQtcachhlnhthlic, ne'umQtthuQctinhA d quanh~toanct;lcduQcmotathanhn thuQctinhd quanh~ ct;lcbQvacodt;lngdQgiatr!- thuQctinhvdiA, thltruyva'nke'ttrenA sethlfcthi (n-I) phepke'tva(n-1)phephQi,nghlaIaco2(n-1)pheptoan. TruonghqpB: IS d6ngvaifrothuQctinh Ne'uluQcd6tichhQpgi6ngIuQcd6EED (nghlaIanamvanu IathuQctinh)thl m6iphepchQn,chie'u,ke'ttrenIS coth€'duQcd!chthanhcactruyva'ntu'ongling trenEED vdicungdQphlict~p.Viv~y,trQngs6IuonIaO.Tru'onghQpnaykh6ng cogldc)cbi~t,nenboqua.Chungtacoth€'thallikhaochitie'td taili~u[8]. d) TrongsrItrongtrllilnghdpdungdoria tri -bang Xernvi dt;lcacCSDL nhusan: CSDL DI Cophan(ngay,congty,gia) Thongtin(#c,congty,diachi) CSDL Dz Cphanl (ngay,gia) 57 Cphan2(ngay,gia) Cphann (ngay,gia) Thongtin (#c,congty,diachi) TrongDj, quaDh~Cophanhill ghic6phfincuacongty trongcaengaykhac nhau. Trong Db m6i lo~i c6 phfin du'<;Icmo tatrongmQtquaDh~.Cho nell, Cophan.congtyd~ngdQgiatri- bangvdiquaDh~Cphann. TntiJnghqpA: IS dongvaifrogiatri PhepchQn Gia sa1u'<;Icd6tichh<;lpla Dj. Truy va'nchQnnhu'sau: du'<;IcdichtrenD2- CSDL c~cbQ: select ngay,gIa from Cphan1 Do truyva'ntrend CSDL loanc~ccochiphinhi~uhonsovditrenCSDLc~c bQ(honphepchQn)DentrQngs6[chQn,congty,D2]>o. Phep chie'u ] 58 select ngay,gla from Cophan where congty='Cphanl' Ghl sii'1u'<;fCd6 tichh<;fpla D]. va troyvffnchie'unhu'sau: select from congty,gia Cophan khongth~thl1chi~ndu'<;fCtrongD2vi Hmtencongty (Cphann)vacacgiatrong D2doihoi themcacpheptoaDkhacngoaipheptoaDquaDh~.Mi~ngiatrtcua Cophan.Congtyco th~khacvdi Thongtin.congty,Denkhongth~dtchtroyvffn. Tuynhien,ne'uMDBScoth~xii'ly saud~dtnhnghial~idiYli~utrongCSDLc~c bQthitrQngs6[chieu,congty,D2]<O.Khi quatrinhxii' ly saulienquaDcacxii'ly phuct~pg6msaochepten'Cphani'vaghep novdim6igiatIt giavdicacbQ mditrongcacbangCphaniDentagiasii'chiphithl1Chi~ntroyvffntrongCSDL c~cbQtu'dngdu'dngvdichiphithl1chi~npheptoaDt~ph<;fp. Phepke't Gia sii'lu'<;fcd6 tichh<;fpla D]. va troyvffnke'ttrenIS : select from where * Cophan,Thongtin Cophan.congty=Thongtin.congty vatroyvffntu'dngdu'dngtrongD2nhu'sau: select from where union select from * Cphan1,Thongtin Thongtin.congty='Cphanl' * Cphan2,Thongtin 59 where Thongtin.congty='Cphan2' union select * from Cphann,Thongtin where Thongtin.congty='Cphann' Truyva'ndu'QcdichhQicuanhi€u truyva'ncon.Trangm6itroyva'ncon,cohai quailh~,nhu'ngkhongcodi€u ki~nke'tgiua2 quailh~nay.Do do,ke'tquacua truyva'nconIa tfchcheogiua2 quailh~.Bi€u ki~nchQntrongm~nhd€ where dunggioih~ncacbQ. Giasaphit6ntht1chi~npheptichcheoIonhonphepke't.Trangtroyva'nbien dichlIen, co n pheptichcheova (n -1) phephQimatroyva'n0 IS chicomQt phepke't.Dodo,trQngso'[ket,congty,D2]nhohon0 nhi€u. (j day,ta khongchu trQngdokhongdangk~sovoiphephQivatichcheo. TruonghqpB: ISdongvaifrobang Ne'uIu'Qcd6cuaIS laDz,m6ipheploanchQn,chie'u,ke'ttrenIS sedu'Qcdich thanh troyva'ntu'ongdu'ongtrenCSDL c~cbQco Iu'Qcd6gio'ngDl. Voi phep chQnvaphepke't,phit6nlanhu'nhaunentrQngso'cua2pheploannaylaO.Voi phepchie'u,mQtroyva'nba'tkylIenquailh~CphaninaGsedu'Qcdichthanhtruy va'nvoidi€u ki~n"Cophan.congty='Cphani'."Vi v~y,trQngso'senhohonO.(do chiphi0 truyva'n0CSDL c~cbQto'nbon).Xemchitie'thontrongt~li~u[8]. 60 e)Trongsri'trongtrliunghdpdungdobang-bang Vi dl,lv€ Io<;1idl,lngdQnayxay ra gifi'aIS.Sinhvienva SUD.Diachi.TrangIo<;1i dl,lngdQnay,do cacthuQctinhthuQccacbangkhacnhaucuaCSDL Cl,lCbQ,nen cothemcacthaolac ba'tk<3'truyva'nIaphepchqn,chie'uhayke't.Vi v~y,trqng s6 du'<;icHnh khi t6ngtrqngs6cuaCSDL du'<;iCHnh.Dl,lngdQIO<;1inaytu'ongtl,l' IO<;1ithuQcHnh- bang,nenchitie'tphannayboqua. 0 Tomtilt cuaphepgantrongslf Trongcacungdl,lngthl,l'C,cacnhathie'tke'MDBS chilltrachnhi~mHnhloan du'aragiatri trqngs6.Giatri chinhxaccuatrqngs6naytilythuQcVaGnhftnt6 nhu'chie'nIu'<;icxii'Iy voim6ithaolacquailh~,th6ngke truyva'n,chie'nIu'<;ict6i u'uhoatruyva'ntrangCSDL cl,lcbQ,cfingnhu'ca'uhinhphancungcuacactr<;1m cl,lcbQ(t6cdQCPU, dai tanilia,...).Vi dl,l,chiphixii' Iy cuapheploanke'tsii' dl,lng idithWltsapxe'p- tr()ntheo[17],[18],[19],[20],[21]Ia: Chi phi kef =F *(IRI* log IRI)+F * (ISI* log ISI)+IRI +ISI2 2 +(JFS * IIRII*IISII)*tuple- size/page- size voiF Iah~s6(khoang1.2)chIkichthu'ocoth<3'vaphit6ns~pxe'pd [17],Ixlla kichthu'ocuas6trangcuaquailh~x, IIXIIIa s6bQcuaX, IFS du'<;iCdinhnghla Ia IIR t><JSII/(IIRII *IISII) , tuple_sizeIa kichthu'octrungbinhcuamQtbQtheo byteva page_sizeIa kichthu'octrangtheobyte.Chi phixii' Iy naycoth<3'trl,l'c tie'pdung trqngs6 nhu'tranghinh3.9.Trongh~th6ngdangthl,l'cthi,khibans6 61 vadi~uki~nchQnthayd6i,trQngs6nayseduQcdi~uchlnhd~coduQcgiaiphap thl1Cthit6iu'u. Dl1avaovi~cphftnlo:;ticacd~ngdQnhutren,chungtaduarabangtomt~tcho vi~cgalltrQngs6.BangnaygQila bangtrc;mgso'nhuhlnh3.9.V-A, V-T, A-A, A-T va T-T vie'tt~tcuad~ngdQgiatri - thuQctinh,giatri - bang,thuQctinh- thuQctinh,thuQctinh- bangvabang- bangtudngling.IS la luQcd6tichhQp.Gia trid cQtIS dongvaitrocuaIS.Vi d~,V cuadongV-T nghlala IS gillvaitrogia tri trongd~ngdQgiatri- bang.MQt6 trongbangtrQngs6 nghlala phit6nthl1c hi~npheptoantudngdudngvoithuQctinha trenCSDL c~cbQ. Cacthams6dungtrongbangtrQngs6: S- S+ p- p+ r J+ C- C+ SA- SA+ JA- JA+ Phai thl1chi~nmQtphepchQn Tie'tki~mduQcmQtphepchQn Phaithl1chi~nmQtphepchie'u Tie'tki~mduQcmQtphepchie'u Phai thl1Chi~nmQtphepke't(t~phQp) Tie'tki~mduQcmQtphepke't(t~phQp) Phai thl1Chi~nmQtpheptichcheo Tie'tki~mduQcmQtpheptichcheo Phai thl1Chi~nmQtphepchQnkhi di€u chlnh(nghlala tuykh6nggall trQngs6chobittky thuQctinhnaonhungchi phi duQctinhkhi phai tinht6ngtrQngs6cuaCSDL c~cbQ) Tie'tki~mduQcmQtphepchQnkhidi~uchlnh Phai thl1chi~nmQtphepke'ttrongdi~uchlnh Tie'tki~mduQcmQtphepke'ttrongdi~uchlnh 62 SM- JM- x n 0 Phai th\1Chi~nIDQtphepchQntrongMDBS Tie'tki~IDduQcIDQtphepke'ttrongMDBS Khongthe'th\1cthivi MDBSkhongthe'xii'ly sau,ho~cCSDL c~cbQ khongcodfi'li~utuongling. S6thuQctinh(bang)trongCSDL duQcIDOtanhughitricuaIDQthuQc tinhtrongIDQtCSDLkhacdd~ngdQgiatri- thuQctinh(haygiatri- bang). Khongcos\1khacnhaugifi'avi~cth\1chi~ntruyv~nd troyv~nloan c~cvatroyv~nc~cbQ. Hlnh3.9:BangtrQngso albicNghlala IDQtrongcacgiatria,bhaycduQcchQn.D\1avaoguylu~tsau: 2Xemphan lo~id\lngde>i'Jm\lc3.2.3.1 63 IS Phep chQn Phep chie'u Phep ke't d.;mg dO V-A V 0 0 2*(n-1)*r A 0 0 0 V-T V s+ JM-ho{tcX n*C+(n-2)*r T 0 SA- 0 A-A ill-A 0 (ho{tcX) X X I-A SM-(ho{tcX) 0 0 A-T A NA/ SM-/(SM-+(mf-l)*JA) hayX NA/O/(mf- 1)*JA- NA/O/(mf- 1)*JA- T NA/ SM-/(SM-+(mg-1)*JA+)hayX X X T-T m-T (mg-1)*JA+)/0/ NA (mg-1)*JM/O/NA (mg-1)* JM/O/NA. I-T NA/O/(mf-l)* JA- NA/O/(mf-l)* JA- NA/O/(mf-l)* JA- VOim6ithue)ctinhtruyva'ncuaIS co d~ngde)A-T ho~cT-T vdiCSDL c~cbe),giasacacthue)ctinhnayph~thue)cvaomgquanh~toanc~cvatu'dngung vdim,quanh~c~cbe),xemxet: . Ne'umg~2vam,=1,thla du'QchQn . Ne'umg=1vam,=1,thlb du'QCchQn . Ne'umg=1vam,~2,thlcdu'QchQn (NA trongalbiclakhongapd~ngdu'Qchaytru'onghQpkhongth~xayfa) Trd h:livi d~v~cacCSDL d tru'ongd~ihQc,taxemxetcaclo~id~ngde)va galltrqngso'tu'dngungtITbangtrQngso'dhlnh3.9. Tronghlnh3.10,labangtrQngso'cacthue)ctinhtrongh~MDBScuatru'ongd~i ? hQc.0 vi d~nay,giasatrQngso'phepchQndingnhu'phepchie'ula 1,trQngso' phepke'tclingnhu'phephe)ila5vatrQngso'pheptichcheola 10.Ne'uconthao tacclinglo~ithltrQngso'selan * w(vdiwla trQngso'cuathaotac). Tronghlnh3.10,vdita'tcaCSDL c~cbe)(CSD,ROD,ASD,EED, SUD)trQng so'cuathue)ctinh#5,tenva#covancuaquanh~IS Sinhvienvathue)ctinh#g,ten cuaquanh~IS Giaovienla 0 VIkhongcod~ngde)gifi'aCSDL c~cbe)vaCSDL tichhQp.KhongphaiCSDL c~cbe)naoclingco thue)ctinhdtbva sothich,nen CSDL c~cbe)naokhongco,trQngso'segallla x, ne'ucogallla O.Vdi CSDva SUD,thue)ctinhphaicuaSinhvienkhongd~ngde)vdi IS nentrQngso'1aO.Vdi ASD,quanh~Sinhvienkhongcothue)ctinhphai,trqngso'1aX. Vdi ROD,2quan h~SV_NamvaSV_Nud~ngde)giatri - bangvdi thue)ctinhphaicuaIS.Sinhvien (tu'dngtl1,trongROD, 2 quanh~GV_Namva GV_Nuclingd~ngde)nayvdi 64 IS.Giaovien).Do do,theobangtrQngso'dhinh3.9,trQngso'lingvoiphepchQn, chie'u,ke'tIa S+,JM-ho~cX van*C-+(n-2)*T . f)~dongianboa,tagiasii'trong vi d~nay,MDBS kh6ngth~xii'I)' sanvakh6ngphanbi~tdu'<;ICthuQctinhnhu' thanhphova duongtuchu6idiachi.Do do, trQngso'cuaphepchQnIa 1,phep chie'uIaX vaphepke'tIa2 * (-10)+(2-2)* (-5) =-20(tru'ongh<;lpnayn=2).Voi EED, thuQctinhnuvanamcod~ngdQgiaIT!- thuQctinhvoi IS.Sinhvien.phainen trQngso'Ia 0, 0 va 2*(n-l)T cho phepchQn,chie'uva ke'thay Ia 0, 0 va 2*(2 - 1)*(-5)=-10(don=2) (dayclingIa tru'ongh<;lpASD,thuQctinhnamvanu co d~ngdQIo~inayvoi IS.Giaovien.phai).ClingtrongEED, vi quanh~Sinhvien kh6ngcothuQctinhduong,thanhphovaquannentrQngso'cacthuQctinhnayIa X. Voi ROD,vi kh6ngcod~ngdQgiii'athuQctinhduong,thanhphovaquannen trQngso'cacthuQctinhnayIaO.Voi SUD,thuQctinhduong,thanhphovaquanco d~ngdQbang- bangvoi cacthuQctinhtu'ongdu'ongtrongIS. Tru'ongh<;lpnayIS dongvai tro Ia mQtbangnentrQngso'cacphepchQn,chie'u,ke'tIa NA/O/(m[-I)* JA- . dgiaido~nnay,dochu'abie'truyva'ntoanc~cnenm[IagiaIT!chu'abie't(m[ ph~thuQcvaosl1phanbo'cacthuQctinh du'<;Ictruyxua'tbditruyva'ntoanc~c). TrongbangtrQngso',tru'ongh<;lpnaytat~mghi Ia *. Voi CSD,vi thuQctinh Giaovien.diachico d~ngdQthuQctinh- bangvoi IS nentrQngso'lingvoiphep chQn,chie'uvake'tIaX, NA/O/(m[-I)JA-vaNA/O/(m[-I)JA-. 65 TrQngso' ROD CSD ASD EED SUD S P J S P J S P J S P J S P J Sinh #s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Vlen ten 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 phai 1 X -20 0 0 0 X X X 0 0 -10 0 0 0 sothich X X X X X X 0 0 0 X X X X X X Hlnh3.10:BangtrQngs6tuMOBS 3.2.3.3 ToluUh6atruyvand1/aVaGtangtn;ngSO~ Trongphfinnay,tatill CSDLxii'Iy truyva'nvoiphit6nnhonha't.Coth€ co nhi€u cach xii'Iy domQtthuQctinhduQcyell cfiutITtruyva'ntoaDc~cco th€ duQc till tha'ytrongnhi€u CSDL. M6i phuonganxii'Iy co th€ duQcmatelbAngmQtt~p cacquaDh~va thuQCtinh,trongdo m6iquaDh~chuait nha'tmQttrongso'cac thuQctinhmatruyva'ntoaDc~cyellcfiu.MQtcachhinhthuc,chungtakyhi~u: (dbil:Rjl.attrkl,dbi2:Rj2.attrk2,, dbih:Rjh.attrkh) voi m6idbigIa CSDL c~cbQ,m6iRjgla mQtquaDh~toaDc~cvam6iattrkgIa mQt thuQCtinhlienquaDtrongquaDh~toaDc~c(1~g~h).Ky hi~udb:R.anghlala dii'li~uR.a(duQcyellcfiutITtruyva'ntoaDc~c)duQCtruyxua'tITdii'li~utuong duongtrongCSDL db.Phfinnaykhangxet de'nthutt;1'tht;1'chi~ncacpheptoaD, xemla nhunhau.Trongkyhi~utren,dbilcoth€ bAngvoidbimvoi I ,L: mvaRjp co th€ bAngvoiRjqvoip ,L:q.Vi d~,truyva'ntill tencacsinhvieDcocungten 66 dtb 0 0 0 X X X X X X X X X X X X duong 0 0 0 X X X * * * X X X * * * thanhpho 0 0 0 X X X * * * X X X * * * quaD 0 0 0 X X X * * * X X X * * * #covan 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Giao #g 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 VIeD ten 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 phai 1 X -20 0 0 0 0 0 -10 X X X 0 0 0 diachi X X X X * * X X X X X X X X X voi giao vien, se co 2 phuongan thvc thi Ia (ROD: Sinhvien.ten,ROD: Giaovien.ten)va(SUD:Sinhvien.ten,SUD:Giaovien.ten). Gia sii'cophuonganthvcthiIaejvaej. Ta kyhi~ucacquailh~Cl;lCbQtu'ong lingvoicacquailh~toanCl;lCv€ m~tIy thuye'tnhusail: ej : Xj, X2,...,Xnjva ej : Yj, Y2,...,Ynj trongdo, m6iXhva Yk(1 ~h ~nj, 1 ~k ~nj) bi~udi~nmQtt~pcacquailh~Cl;lC bQtuongduongngii'nghla. Hai phuonganxii'Iy gQiIa tuongduongne'uchungchocungke'tqua.Xii' Iy tuongduongnayphaithoacacdi€u ki~n: 1) nj =nj, 2) Voi m6iXh(1 ~h ~nj)trongej, t6nt~ichinhxacmQt Yk (1 ~k ~nj) trong ejsaGchoXhva Yktuongduongngii'nghlavaScope(Xh)=Scope(Yk). Ml;lCdicht6iauhoacuachungtad dayIa timtucacphuonganxii'Iy tuong duongmQtphuonganco t6ngtrQngso'Ionnha't.MQtcachhinhthlic,taco th~ phatbi~ubai toan: MQtcachhinhthlic,tacoth~phatbi~ubaitoan: Cho iuqcdB cuacac CSDLva truyvanloanqtC,truyvannayco thi duqc thlfcthi bangnhi~uphuongan,m6iphuongan tra v~cungkefqua.Gia sa ~ ia ttlPhqpcacphuongan thlfCthiva (e E ~). TtlPcacCSDL lienquandene gQi ia DBe.Cac quanh~Rj, ...,Rr cuaIS ia cac quanh~duqctruyxuatcho truyvanloanqtc. Vai quanh~Rj, thuQctinhattrj, ...,attrajia cacthuQctinh duqctruyxuatbiJi truyvanloanc1:tc.Phep loanduqcthlfChi~ntrenRj.attrj 67 la °Pij. . Gid sa trQngso vi~cthlfChi~nCSDL k (la dbk), djchpheploan°Pij trenIS.Ri.attrj,la OJR dbk tt . ..' MlfC dich cua chungta la am eoE q saD cho:,.a rrOPy max dbk Weight(eo)=\-I j: L L L OJ R attrop VeEf::,'o'dbkEDBc'o'Rj 'o'attrj ,. r y vcJiweight(x)la t6ngtrQngsocuaphuonganx. Khi tinhroan,cactrQngs6duQcIa'ytubangtrQngs6.Tu thaoIu~nd f, tatha'y khi cac IuQcd6 va ca'uhinh h~th6ngbie'ttrudc,thi c6 th€ tinhduQctrQngs6, nghiaIa tinhbangtrQngs6trudckhi duara truyva'nroanC\!c.Do d6,xli'ly t6iu'u d daychi lien quailde'ncacgia IT!trQngs6duQcbie'ttrudcd phuongtrinhtrend€ timphuonganxli'Iy truyva'nvdi t6ngtrQngs6caonha't.Vi v~y,dQphilct~pcua xli'Iy rimt6ngtfQngs6caonha'tnaykh6ngdangk€ sovdi dQphilc t~pcuavi~c t6iu'uh6ad milcdQkhacnhu t6iu'uh6ab~ngcachhoanV! thikh6ngnhfi'ngtinh chi phi thvchi~nchom6ipheproanmacon timcayxli'Iy t6tnha't.Vi d\!saurim phuongant6iu'udungt6ngtrqngs6. Vi du3.3:Giasli'truyva'nroanC\!Cnhusau: select G.ten,G.diachi from SinhvienS, GiaovienG where S.phai=G.phaiandS.thanhpho="TPHCM" and S.sothich="bongda"and S.#covan=G.#g Trudc he't,BQPh<itSinhKe'Ho~chThvcThi (ExecutionPlanGenerator)se phat sinhta'tcacacphuonganthvcthi.SoIuQcv~cachlamvi~c uabQxli'Iynay nhusau:Bftutien,n6phatsinhtiltcacact6hQpc6th€ cuacacCSDL vacac 68 quailh~nghiaIacact6h<:JpnaychuaHitcacacthuQctinhyellcfiutruyxua'tcua truyva'nloancl;lC.Saudo, no gidi h~lncact6 h<:Jpnayb~ngcachgill I~icac phuonganke'tquala t~pconcuaphuonganke'tquakhac.Vi~cgiOih~nnayco th€ th1!chi~ndu<:Jcb~ngcachki€m ITaph~mvi cuacacquailh~.Cacke'ho~chxii' Iy tuongduongdu<:Jcphatsinh tuongt1!nhubQbie'nd6itruyva'ntrongbQphat sinhtruyva'ntruy~nth6ng.BQphatsinhxii'Iy naykhongdu<:Jcd~c~ptronglu~n van.Tacoth€ thamkhaorarangphfinnayd [19],[22]. Giasii'BQPhatSinhKe'Ho~chTh1!CThid!chradu<:Jcdanhsachcacphuongan th1!cthih<:JpI~nhusau: e]=(ROD: Sinhvien.#covan,ROD: Sinhvien.phai, ROD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) e2=(ROD: Sinhvien.#covan,ROD: Sinhvien.phai, ASD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) e3=(ASD: Sinhvien.#covan,ROD: Sinhvien.phai, ROD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) e4=(ASD: Sinhvien.#covan,ROD: Sinhvien.phai, ASD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, 69 CSD : Giaovien.diachi,CSD : Giaovien.phai) e5=(ASD: Sinhvien.#covan,SUD: Sinhvien.phai, ASD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD : Giaovien.diachi,CSD : Giaovien.phai) e6=(SUD ..Sinhvien.#covan,SUD : Sinhvien.phai, ASD:Sinhvien.thanhpho,ASD:Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) e7=(ASD: Sinhvien.#covan,SUD: Sinhvien.phai, SUD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) e8=(SUD: Sinhvien.#covan,SUD: Sinhvien.phai, SUD: Sinhvien.thanhpho,ASD: Sinhvien.sothich, CSD: Giaovien.#g,CSD: Giaovien.ten, CSD: Giaovien.diachi,CSD: Giaovien.phai) Cacphu'ongandu'QcphatsinhtrendvavaocacRBTV cuaCSDL dadu'arad phftn2. Tie'ptheo,ta xemxettruyvanloanc~c.ThuQctinhGiaovien.tenva Giaovien.diachitrongtruyvanloancl;!Clien quailde'nphepchieu,thuQctinh Sinhvien.thanhphova Sinhvien.sothichlien quailde'nphepchQn, va thuQctinh phai,#covan,#glienquailde'nphepkef.Tli bangtrQngso'tronghinh3.10,tatill cactrQngso'dethvchi~ncacthuQctinh.Vi dl;!,t6ngtrQngso'e}la0- 20+0 +0 + 0 +0 + (m,- 1) * (-5)+ O.Trongvi dl;!nay,m,la 2 vi cacthuQctinhcua IS.Giaovientu'onglingvoi 2 quailh~cl;!cbQGiaovienvaDiachicuaCSD.Ly 70 lu~ntuongW',ta'tca gia tri cuam[ trongcacei d€u b~ng2 VI e2,e4,es,e6, cac thuQctinhcuaIS.Sinhvienlingvoi2 quanh~SinhvienvaDiachitrongASD.Voi e7va eg,cacthuQctinhIS.Sinhviencfinglingvoi 2 quanh~SinhvienvaDiachi trongSUDnentrongmqcthlibacotrQngs6,m[cfingla 2.Tuongtv,ta'tcacac phuongantITel de'negcuamqcthli7 la ((m[- 1)*(-5))com[ la 2 VIcacthuQc tinhclInglienquande'n2 quanh~cqcbQla GiaovienvaDiachitrongCSD.V~y, tacotrQngs6cacthuQctinhtrongeinhusau: T6ngtrQngSa(el) =0 - 20+0+0+0+0+(m[-I)*(-5)+0=-25 T6ngtrQngSa(e2)=0 - 20+ (m[-I)*(-5)+0+0 +0+(m[-I)*(-5)+0=-30 T6ngtrQngso'(e3)=0 - 20+0 +0 +0 +0 +(m[-1)*(-5) +0 =-25 T6ngtrQngSa(e4)=0- 20+ (m[-I)*(-5)+0+0+0+(m[-1)*(-5)+0=-30 T6ngtrQngs6'(es)=0+0+(m[-I)*(-5)+0+0+0+(m[-I)*(-5)+0=-10 T6ngtrQngso'(e6)=0+0+(m[-I)*(-5)+0+0+0+(m[-1)*(-5)+0=-10 T6ngtrQngs6'(e7)=0+0+(m[-I)*(-5)+0+0+0+(m[-I)*(-5)+0=-10 T6ngtrQngsa(eg)=0+0+(m[-I)*(-5)+0+0+0+(m[-I)*(-5)+0=-10 Cu6icling,HmeicotrQngs6caonha'tlaes,e6,e7vaeg.V~y,coth€ chQnmQt trong4ke'ho<;1chthvcthivi~ct6iu'uhoadqngdQluQcd6. 71 3.3T6iduhoatruyva'ntrongMDBSdtrddnghQ'pbansaodii li~u vaphepke'tlientr~m 3.3.1TO'iu\Ihoavi~cs~px~ptruyv~ncontocIncl}ctrongtrltanghQ'p co bansaodl1li~u Trongph~nnay,taxemxetvand€ phantancuatruyvancontoaDc~cvdicac tr'.lmlienquaDtrongtnI'ongh<Jpco nhi€u tr'.lmco th~xii'ly truyvancon.Giai do'.ln aychidu'<Jcth1!Chi~nsaukhidaphanratruyvand ph~ntrudc. Khi codu li~uphantantrongh~MDBS,coth~cohelnm<?ttr'.lmcoth~xii'ly truyvancontOaDc~c.Cacph~ncuatruyvantOaDc~csaukhiphanfa,t'.lmgQila truyvdncontoimc~c.M<?tcachngAngQn,co th~gQitruyvdncontoimc~cla truy vdncon. Sauquatrlnhphanra Calltroyvan tOaDc~cdu'<JCphanchiathanhcac CalltruyvanconvacacCalltroyvanconnaydu'<Jcxii'ly tr1!ctie'pt'.licactr'.lm. Vand€ la Calltruyvanconnaodu'<Jcxii'ly t'.litr'.lmnao.Chungtamahinhbai tOaDnhu'sau:Giii sii'co n Calltruyvanconqi : i=Ln, m tr'.lmSj: j=Lm, chi phi th1!chi~nCalltroyvancontOaDc~cqit'.litr'.lmSj la trQngso'm(qi,sf) vachiphi chovi~ctiiiduli~ut'.litr'.lmSj Ia lj. TImhamphanph6iftli t~pcactroyvancon qivaot~pcactr'.lmSj saochochiphisaudayIat6ithi~u: max { If + LOJ(qi'S) }S)E{I,.,mJ q;:[f(qj)=S)] (1) E>~tc(Sj) =Ij+Sum(m(qi's)saochof(qi)=Sj)vdij =Lm 72 Ta nh~ntha'yr~ngc(Sj) chinhla chi phi thl;l'chi~nt~itr~mSj . Va'nd~cua chungta la timhamphanph6if saochochi phi Ion nha'tla nho nha't.Day la bai tmlnmax-mill ra'tkh6giai. C6 th~c6mQtuocluQngkhacchohamchiphila trungbinhcuac(Sj)thayvi la maxcuac(Sj).Theohamchiphinaykhongbaodamtinhd6ngd~utrongphuong phapphanph6ivi sec6tinhtr~ngchiphid mQtr~mnaod6la ra'tcaotrongkhi mQtr~mkhacl~ira'tha'p,m~cdlitheotie'pc~nnaythid~dangtimmillbon. Trd l~iva'nd~cuachungta,nhudad~c~pd trentimmillcua(1)labaitoan NP-kh6,tad~nghimQtthu~ttoanthayd6inh~mlamchochiphiit tangnha'tc6 th~duQctrongm6ibuocl~p.Trongthu~ttoannaysaukhikhdit~ocacgiatricho cac tr~m,cac Calltruyva'ncon, chi phi thl;l'Chi~nCalltruyva'ncon t~icactr~m duQctinh.Gia trichiphiduQcchepsangmatr~n0/ vachiphitaicactr~mcling duQcthemvao.T~i'm6ibuocl~ptrongyangwhile,cacCalltruyva'nconvoichi phi cl;l'cd~itrongw' duQcll;l'achQn.Ne'uc6 nhi~ubon mQtCalltruyva'nconc6 gia tri cl;l'cd~i,chQntrongd6 Calltruyva'nconva tr~msaochochi phi thl;l'chi~n w' la be nha't.Cu6i clingxoaCalltruyva'nconduQcchQntrenrakhoi t~pcacCall truyva'nva gia tri chi phi trongw' trongta'tcacacCalltruyva'nconcanl~itang themb~ngchiphiwcuatruyva'ncondax6a. Thuftttmin3.3:Tffiltu hoavi?csiipxtp truyvlfncon begin Q ={l,...,n}Zatqptruyvdncon; S ={I,...,m}Za ttl-P cac trqm Tfnh ta'tcd OJ(qi's), qi E Q va Sj E S; 73 Ta nh~nthiy ding c(Sj) chinh la chi phi th\;l'Chi~nt(;litr(;lmSj . Vin d€ cua chungtala timhamphanph6if saochochiphiIOnobit la nhoobit.Bay labai loanmax-mill fit kho giai. Co thtScomQtudcluQngkhacchohamchiphila trungblobcuac(Sj)thayVIla maxcuac(Sj).Theohamchiphinaykh6ngbaadamHnhd6ngd€u trongphuong phapphanph6iVIsecotinhtr(;lngchiphid mQtr(;lmnaodola fit caotrongkhi mQtr(;lmkhacl(;lifit thip,m~cdotheotie'pc~nnaythld~dangtimmillbon. Trd l(;livin d€ cuachungta,nhuda d€ c~pd tIeDtlmmill cua(1) la bai loan NP-kho, tad€ nghimQtthu~tloanthayd6i nhAmlam chochi phi it tangobit co thtSduQctrongm6ibudcl~p.Trongthu~tloannaysaukhikhdit(;locacgiatricho cac tr(;lm,cac Calltruyvin con, chi phi th\;l'chi~nCalltruyvin con t(;licactr(;lm duQctinh.Gia tri chi phi duQcchepsangmatr~n0)'va chi phi tai cactr(;lmding duQcthemvao.T(;li'm6ibudcl~ptrongvongwhile,cacCalltruyvin convdi chi phi c\;l'cd(;litrong0)' duQcl\;l'achQn.Ne'uco nhi€u hon mQtCalltruyvin conco gia tri c\;l'cd(;li,chQntrongdo Calltruyvin conva tr(;lmsaochochi phi th\;l'Chi~n 0)' la be obit. Cu6i congxoaCalltruyvin conduQcchQntrenrakhoi t~pcacCall truyvin va gia tri chi phi trong0)' trongtit cacacCalltruyvin conconl(;litang thembAngchiphi0)cuatruyvin condaxoa. Thuattmin3.3: Tifi liu hoavi?csiipx(ptruyvancon. begin Q ={l,...,n}latcJ-ptruyvancon; S = {I,...,m}la tcJ-pcae tr(lm Tfnhtatcd m(qpsj)' qi E Q vaSj E S; 73 (j yangl~pthanhat,giatri caonhatla OJ'(4,1)=15,nensubquery(troyvan con)la4.Ma minSjE{I,2,3}{oJ'(subquery,Sf)}=w'(4,2)=13 , trqmdu'<;jcchQnIa2, vi v~y,subquery4 sedu'<;jcthvchi~nd tr(;lm2 voi chiphi Ia 13.Sand6,x6a subquery4 vatatcaOJ'(i,2),i E ~ 1,2,3r du'<;jctangm(4,2)=13.Voi yangl~ptha 2,bittdfiuvoibang3. 3 Subquery 1 2 Bang3:GiatrjOJ'choyangI~pthu2. Trongyangl~p2, OJ'(2,2)=21Ia gia tri caonhat,nensubquery=2. Va minSjE{I,2,3}0' (subquery,sf)}=w'(2,1)=6 , tr{lmdu'<;jcchQnla 1, vi v~y, subquery2 sedu'<;jcthvchi~nd tr(;lID1voichiphila 6.Sand6,x6asubquery2 vatatca OJ'(i,I), i E ~ 1,3r du'<;jctang m(2,1)=6.Voi yangl~ptha3,bittdfiuvoi bang4. 75 Subquery Trm 1 Trm 2 Trm 3 1 OJ'(1,1) =5 OJ'(1,2) =7 OJ'(1,3)=9 2 OJ'(2,1) =6 OJ'(2,2) =8 OJ'(2,3) =8 3 OJ'(3,1) =6 OJ'(3,12 =7 OJ' (3,3) =6 4 OJ'(4,1) =15 OJ'(4,2) =13 OJ'(4,3) =14 Bang2:GiatriOJ'kh6itc;lo Trm 1 Trm 2 Trm 3 OJ'(1,1) =5 OJ'(1,2) =20 OJ'(1,3)=9 OJ'(2,1) =6 OJ'(2,2) =21 OJ'(2,3) =8 OJ'(3,1) =6 OJ'(3,2) =20 OJ'(3,3) =6 1Subquery 2 Bang4:Giatrj{lj'chovongI~ptht13. Trang vongI~p3, cii {lj'(1,2)va {lj'(3,2)=20Ia giatricaonha't,nensubquery c6 {lj'(qi,Sj) nhonha'tduQcchQntrongcactruyva'nconqi E i 1,3r. Vi {lj'(3,3) = 6 , subqueryduQcchQnIa 3 va trr;zmla 3,nghiala truyva'ncon3 seduQctht:I'c hi~nd tr~m3voichiphila 6.Saud6,x6asubquery3va (lj'(1,3),i E i 1,3r duQc ? tangw(3,3)=6.0 vongI~pcu6i,truyva'ncon1duQcgalltht:I'chi~nd tr~m1. 3.3.2 T6i u\I h6aphep ke'tlien trc.tmtrong Da CSDL Trangvi~cgiiimt6idat6ngthaigiantht:I'chi~ntruyva'n,xii'Iy trQngHimlaI~p Iichcacphepk€t lientr~m.Ngoaifa,so'Ianxua'thi~nvachiphitroy~nthongcua troyva'ncon toanCl;lCclingduQctinhd€n chiphi trongphepk€t. Do d6,giii sii's6 Ian xua'thi~ntruyva'nconc6 th~uocluQngduQc.Va'nd~con I~iphiiigiiii quy€t Iat6iu'uh6aphepk€t lientr~m,UOCluQngso'Ianxua'thi~ncuatroyva'ncon. Vi va'nd~thlltt:I'phepk€t kinhdi~nIabaitoanNP-Kh6 [23],va'nd~thllWk€t lien tr~mcuaMDBS clingIa mQtbai toanNP-Kh6.Trangt6i u'uh6ak€t lien tr~m,chungtad~xua'tmQthu~ttoanheuristic2buoc.Thu~toannaytangt6ida ? khiinangxii'Iy songsongcuacacphepk€t trongtroyva'ntoanCl;lC.0 buocthll nha't,tITd6thitroyva'ntoanCl;lC,sec6duQcmQthllWk€t tuy€ntinhd~ct:I'cti~u toanbQchi phi cho truyva'ntoanCl;lC.Buoc thll2 thu~toandungthll tt:I'nayd~ HmmQtI~pItch cho xii' Iy truyva'n,xem xet cd che'songsongh6a trongxii'Iy troyva'ncon.DBthitruyvantoemqlC lamQtbi~udi~ncuatruyva'nduQcduara 76 Ttm 1 Trm 2 Trm 3 (lj' (1,1) =11 (lj' (1,2) =20 (lj' (1,3) =9 {lj'(3,1) =12 {lj'(3,2) =20 {lj'(3,3) =6 trongh~MDBS trongdonutlake'tquacuatruyva'nconloanc~cvaq.nhla thao lac lien tr(;lm. 3.3.2.1Heuristicdl ph/Itsinhm(jtthytvtuyentfnhchotruyvan Ta segallc(;lnhcuad6th!truyva'nloanc~cvoihamtrQngs6. Tniockhitrinh baycacthu~tloan,tacomQtvaid!nhnghladuQcdungtrongcachamtrQngs6: Djnhnghla3.1TinhchQnIQckichthu'O'c(SizeSelectivity) Tinh chQnIQckich thuoccuathaolacke'tC =L 1><1R, ky hi~uO"size(L,R) duQc d!nhnghla: O"size(L,R) =nbpages(C) / (nbpages(L)+nbpages(R» voinbpages(C)la t6ngtrangnhouocluQngcuake'tquatrunggianC. Djnhnghla3.2Chi phitrenmQtddnvj Chi phi lIen mQtddnV!cuamQtpheploanC =L 1><1R voiL, R Iake'tqua trunggian, leastla chiphinhonha'tcothGcuaphepke't, kyhi~uPeast(L,R) nhu sau: Peast(L, R) =least(L, R) / ~LI+!R!)voi ILlla bans6cuaL. Djnhnghla3.3HamtrQngs6 La dQdouocluQngchiphixii'ly cuaphepke't.Ta d!nhnghla4 hamtrQngs6 \pI, \p2,\p3,\p4nhu sau: \P1(L, R) =Jeast(L,R) / (1 - O"size(L,R) 77 'P2(L,R) =Jeost(L,R) * (Ysize(L,R) 'P\L, R) =Peost(L,R) * (YsizJL,R) 'P4(L, R) =In Jeost(L,R) * e O"size(L.R) Trongdinhnghlatren,tatha'ychiphivaHnhchQnlQccuam6iphepke'trong daythaotacke'tanhhudngtrvctie'pde'nthutv ke't.Vi d~,xemA 1><3C voi chi phi Jeost(A,B), Jeost(B,C) va Hnh chQn lQc kich thuoc la (Ysize(A,B), (Ysize(B,C). Gia sa leost(A,B) > leost(B,C) va (Ysize(A,B) < (Ysize(B,C) . Ne'uxet trenchi phi, ta se thvchi~nBI><3Ctruoc,nhungdo (Ysize(A,B)< (Ysize(B,C)nen thvchi~nphepke'tIDeothutv AI><3C. Dodo,phaiHnhde'nchiphilfintinhchQnlQckichthuoc. Trongm6ihamtrQngsO'tren,to'P\L, R) de'n'P\L, R), anhhudngcuachiphi voi trQngsO'giamdfintrongkhiHnhchQnlQctangdfin. Thu~toan3.4tlmmQtthutVtuye'nHnhchod6thi truyva'ntoanc~c.Trong thu~toan,d6thitruyva'ntoanc~cQG\ k E {1,2,3,4voichiphicacc~nhduqc Hnhb~ngcongthuchamchiphi'Ilktren.Vi~crutgQncacnutduqcthvchi~nIDeo quylu~t3.1voimQtpheprutgQntrunggian,nhancuanuttuangungduqcmoc nO'ivaodi€u ki~nlanggi€ng. Quylu~tnayla mQtheuristicd~coth~tranhtich descartes. Lu~t 3.1 78 LffiR= RL RrL LRr LR ne'u LL ~ RR ne'u LL ~ RL ne'u LR ~ RR ngu'9cl~i voiL vaRIa nhancuanuttrongd6thitruyvannhU'hlnh2vaRrIa thiltvngU'<jc cuanhanR. LL ~RR nghlaIa nuttniinhattrongL (LL)vanutphainhatcuaR (RR) Ia Ianggi€ng trongd6thitruyvantoanCl;lC,tilc Ia phaico di€u ki~nke't gifi'achung. Thuattmin3.4(Xacdinkthuttjtuye'nlink) begin For k =1to4 do { cosl =o., Xayd1;lngdBthi truyvantoimClfCQOk; Tinh tpk(L,R) chom8ic~nh(L, R) E QOk; while(Co c~nhxilly dltqc){ ChQnc~nh(L, R) wJi trQngsf)nhonhat; cosl =cosl +lcoslL,R); Dungluqt3.1thunhonutL vaR thanh(D3JR); Tinh l~i tpk((LC3JR),17),V 17E QOk kg cqn wJi (LC3JR); } } ChQnthatif tuyentinhveJichiphi nhonhatminkE{l..4}cosl; end. 79 Trong thu~ttoaDnay, gia sli'vi~cphilo ra troyv~ntoaDcl;lcphai duQCthvc hi~ntruackhi xay dvngd6 thi troyv~ntoaDCl;lC.(j m6i vongI~p,tlmci:;lnhvai chi phi nha nh~t,ci:;lnhnay xoa di, va 2 nut lien quail duQcrut trichva chi phi ci:;lnhb~tngu6ntu nUt ruttrichseduQctinhIi:;liva vungnhaheapduQcdi~u chinh.VungnhaheapduQcxaydvngd6duytrl trQngsacacci:;lnhtrongd6thi truy v~n toaDcl;lc.DC)phllC ti:;lPthu~ttoaDnay Ia O(ne + n2 loge) (hay Ia 0 (n2loge)ne'udungmangdinhvi cho cacphantd'trongheap)vai e Ia saci:;lnh van Ia sanUttrongd6thitroyv~n. Vi du3.5Giasli'd6thitroyv~nbandaunhuhlnh3.11a.Nhancuaci:;lnhchinh Ia cactrQngsa,nghlaIa chiphidunghamtrQngsa\}fl.M6i buaccuathu~ttoaD nay nhuhlnh3.11b-f, cacnutcochiphici:;lnhnhanh~tduQcruttrichtheoIu~t 3.1.Xli'ly naytie'ptl;icduQcthvchi~ncho\}f2,\}f3,\}f4vathlltvtuye'ntinhvaichi phike'tnhanh~tduQcchQn. Q2 Q7 a)06 thi truyvanband~u Ql,Q4 8 °Q6 Q2 c) Bu'ac2 8 °Q6 Q7 b) Bu'ac1 Ql,Q4 V~8 ocf Q6 Q2,Q3,Q7 Q5 d) Bu'ac3 80 Q1,Q4,Q5o 5 c/ Q2,Q3,Q7 °Q6 Q5,Q4,Q1,Q2,Q3,Q7 o 4 °Q6 e)Bu'oc4 f) Bu'oc5 Q5,Q4,Q1,Q2,Q3,Q7,Q6 g)Thli tvtuyentfnhcuoicling Hlnh 3.11:Tim thutLjtuyentfnhtli Do Thi Truy Van Toan Cl,IC 3.3.2.2M(jtheuristicddxacdinhvitrfngo?cddnchothyt1/tuyen tfnh Tir thu~tloan 3.4,tadfi c6 thli W'tuye'ntinhcho troyvan loancl;lCQ. Van dc3 bay gia la cl;l'cti€u thai gian dapling b~ngcachgia tangsl;l'songsongh6acua phepke'tlientr~m. Trang congthlic3.1dU'oiday,giii sac6thlitl;l'tuye'ntinhQJi(1)QJi(2)...QJi(n)cua truyvan Q voi n(1)n(2)...1l"(n)Ia mQth6anvi cuasCSI::;i ::;n. Congthuc3.1 cost(i,i)=tJi(i), 1 ::;i ::;n 81 cost(i,i+1)=mill jC(Q"(i),Q"(i+1))site(Qn(i))+ { t"(i),ne"U t"(i+1)+com- coSt(Q"(i+1)):::;t"(i) t,,(i+1)+com- cast(Q,,(i+1))' nguQclc;ti' { t,,(i+1),ne"U t"(i) +com- coSt(Q"(i)):::;t"(i+l) t"(i)+com- cost(Q,,(i))' nguQclc;ti ' ,1:::;i :::;n cost(l, n)= jC(L"(i),R,,(i)Le(Ln(iJ) + { Cost(I,i),ne"Ucost(i+I,n) +com- coSt(R"(i)):::;cost(I,i) . . ~ cast(i +1,n)+com- cast(R7r(i))' nguQclc;ti ' mm1« {mill ( )_U . L RJC ,,(i)' ,,(i) site(Rn(i))+ { cost(i+I,n),ne"u cost(I,i)+com- cost(L,,(i)):::;cost(i+I,n) castel,i) +com- cast(L"(i))' nguQclc;ti trong d6, Ln(i)= Qn(l)1><1 Qn(n) Cong thuc3.1 gia sU's6 troyvan con loan cl;1cbAngvdi s6 trc;tID.TntonghQp t6ngquathon sen6i de'ntrongcongthuc3.3. Trongcongthuctren,cost(i,j) la chiphike'tlien trc;tIDgiii'atroyvanconQn(i) vaQn(j) vdi 1 :::;i :::;j :::;n trongthutl;1'tuye'ntinhtITthu~tloan 3.4.Khi khdi tc;tO, cost(i,i) bAngs6 Hinxuathi~ntn(i) cuatroyvanconQn(i) , i E {1, 2,...,n jc(L,R)s Ia chi phi thaolac ke'tgiii'aloanhc;tngL va loanhc;tngR thl1Chi~nbQxU' ly troyvan loan cl;1cuaLDAO d trc;tIDs,khi ca hai loan hc;tngthl1Chi~nduQcd trc;tIDnay. Ky hi~usite(L) nghlala tc;titrc;tIDCl;1CbQc6 th€ thl1Chi~nloanhc;tngL. Cu6i cung, chi phi truy~nthong cua loan hc;tngL de'n trc;tIDkhac ky hi~u com_cost(L). 82 Dinhnghia3.4cost(1,n)trongcongthuc3.1duQcvie'tl~inhusau: cost(l, n)=mill l~i~n{cost'(l,i,n) vdi cost'(l,i,n) Ia chiphi xii'ly thaolacke'tlien tr~mgiii'aloanh~ngL1(O)vaR1(O)' Chi phi nayIa chiphi nhonhattrongcacchiphi xii'ly thaolacke'tlien tr~m.Ne'u ca2 loanh~ngd~ucoth€ cungxii'ly duQcd 1tr~mthikhongcochiphitruy~n thong.TruonghQpconhi~uhdnm(}ttruyvanconloanc1;1cduQcgalldCSDLc1;1c b(}saukhiphanra truyvan,thisii'd1;1ngcongthuc3.3t6ngquathdnsovdicong thuc3.1. Trangthu~tloan3.5,matr~nvuongM cod~ngnxnvdiM(i,j) Iathoigiannho nhat d€ thvc hi~n vi~c ke'ttr~mgiii'a truy van con Q11(i)va Qn(j)vdi 1 :::;i :::;j :::;n trongthutv tuye'nHnhHmthaytuthu~tloan3.4.M~tkhac,M(i, j) =cost(i,i). Cu6i cung,0 M(1,n) chuachiphi xii'ly truyvanloanc1;1c.£)€ ddngianboa,vi~c l~plichkhonghi€n thi trongHnhloanmatr~nM duara tronggiai thu~t5.2. Trang[24],so'khanangd~tdaungo~cddncuam(}thutvtuye'ntinhvdin+1ke't quathanhphfin(nghlala matr~nn+1chi~u)va so'caynhi~ula vdinnUtb~ng C(2n,n)/(n+1), CIa hamke'thQp. Thuattmin3.5(Bijl d{fungoijctrenThuTlj TuytnTinh) begin for k =1ton doM(i,i) = t11(i),o for f = 1 ton-fdo /* tinhM(i,i+f) */ { M(i,i+f)=+If),o for i =1tof do /* wJi tatcdvi?cd{jtdaungo{jc*/ 83 {a=cost'(i,i+j-1, i+f);/* xemdjnhnghfa3.4chocost'*/ neua <M(i, i+f)thiM(i, i+f)=a; ] } end. BQphilct~pcuathu~ttmln3.5Hi: n-\ L i(n - i) =n * (n - 1)* (n +1)/ 6 i=\ nghiaHiO(n3)vdin la s6nuttrongd6thitroyva'ntoanc~c. Ne'utaboquachiphitruy~nthong,lucdo,congthilc3.1sedongianthanh congthilc3.2 Congthuc3.2 cost(i, i) = tn(i),1~i ~n,/* s61dnxuathi~n*/ cost(i, i+1)=rnax{t1l(i), t1l(i+l) + jC(Q1l(i), Q1l(i+1), 1~i ~n, cost(1,n)=rninl~i~{max{ cost(I,i), cost(i+l,n) + jC(L1l(i), R1l(i» trongdo, Ln(i)= Qn(l) £><1 Qn(n)vajc(L, R) lachiphithl1chi~nthaotacke'tgifi'a2toanhC;lngL vaRkhica2 toanh~ngcoth~thl1CthidcungrnQtr~rn. Vi du3.6Xern3CSDL sautrongrnoitntongkhongd6ngnha't: SV_dangky(masv,ten,diachi,tinhtrang)d tr~rn1 84 Thuvien(sv_no,sv_ten,muon_sack)d tr~m2 SV_Tinhoc(id, ten,man,xeploai)d tr~m3 Giasacotruyvansan:TImsinhviendangkYcodlachitc;ziTPHCMthuQckhoa TinHQcmuqnhan10cucfnsackvadc;ztloc;ziA trongmanCSDL. Truyvannaysankhiphftnranhu'sau: . QI d tr~m1:TimsinhviendangkycodiachIt~iTPHCM. Q2dtr~m2:Timsinhvienmu'Qnhan10cu6nsachtITthu'vi~n. Q3d tr~m3:TimsinhvienkhoaTin HQcd~tlo~iAmon CSDL. Giasake'tquacuathu~ttoan3.4laQ=QI Q2 Q3 vagiasaso'l~nxuathi~n cuake'tquathanhph~nd cactr~mtu'anglingnhu'bang5 san: Truy va'nconke'tqua 1 2 3 1 2 msecs cost(1,2) cost(1,3) cost(2,3)2 5 msecs 3 3 msecs Bang 5: s6 Ianxuathi~ncua ketqua thanhphan Ta c~ntinhcost(1,2),cost(2,3)vacost(I,3).Giasa jC(QI,Q2)=3, jC(Q2, Q3 ) =2 va jc(Q},Q2t><JQ3 ) =2 la thaigianke'ttinhb~ngmili gifty.Ap d\;1ngcongthlic3.2,taco: cost(1,2)=max{ cost(1, 1),cost(2,2) +jc(Q}, Q2)=5 +3=8 msecs. cost(2,3)=max{ cost(2,2),cost(3,3) +jC(Q2' Q3)=7 msecs. Cu6icling, 85 cost(1,3) =min{ (max{cost(I,2),cost(3,3)+jC(Ql [><JQ2,Q3», (max{cost(1,I),cost(2,3) +jC(Ql, Q2[><JQ3» =min{ (max{8, 3 +2), (max{2, 7 +2) =min(9, 10) =9 msecs. Vi v~y,thlitvthvchi~nchophepke'tlientr:;tmcuatruyvftnloanC\!CQ Ia Ql [><JQ3). 3.3.2.3Tangkhanangxuif truyvansongsongtrongJVJDBS Santhu~tloan3.3tadaxacdinhdu'<;ICdiu truyvftnnaodu'<;Icthvchi~nt:;titr:;tm nao,sando chungtaphaike'th<;lptilt ca cacdiu truyvftncon I:;tide co ke'tqua. Vftnd~Ia ke'th<;lpthe'naodevi~cthvchi~nco chiphibe nhftt. Djnhnghla3.5MQtdaybansaocuamQtd6thitruyvftnloanC\!CIamQthlitv tuye'ntinhcotheso:;tnthaodu'<;ICbiendichtheothu~tloan3.6.MQtdaybansao phuIenHitcacaccacc:;tnhtrongd6thitruyvftnloanC\!c.Ta t:;tmgQimQtchu6i concuadaybansaoIaphandOfln. Gia sathu~tgiai3.6du'aramQtthlitv tuye'ntinhtud6thitruyvftnloanC\!C mamQtnutIa mQttruyvftnconloanC\!Cvacothexuftthi~nnhi~uhonmQtHin trongday.Haidiu truyvftnconQl vaQ2cotheke'th<;lpdu'<;Icne'ucoitnhfttmQt di~uki~nke'tn6igifi'achung.Thu~tloannayseduy~tiltcacacc:;tnhcuad6thi truyvftncondi quacacnutHinc~nvaquayIuikhi tiltcacacc:;tnhcuanutdu'<;Ic duy~t. 86 ThuattmlD3.6(Thytt,tcothi so",nthilova;caebilnsao) Q2 Ql Q3 Q5 Hlnh3.12do thi truyvan toanCl)C begin START=Nut wJi bqcnhonhat; S = {tqp cac cqnh trang d6 thi truy van toemClfC }; FLAG =1; while(Skhongrbng){ while(FLAG) { xoa m()tcqnh (START,J) titS; cqpnhqtcacbqccua STARTvaJ trongS; inSTART; dllaSTARTvaostack; ntut6ntqim()tcQnh(X,J) hoiJc (J, X) trong S thiSTART=J; ntukhong{FLAG=0; in(J); } } ntu(Skhongrbng ) thi { layra STARTtitstack; while ((bqc cua STARTtrongS la 0) va(stackkhongrbng)){ in START; lay ra STARTtitstack; } 87 FlAG ==1; j J end. Trangthu~troan3.6,m6inutla mQtbansaotrongdaycuad6thitruyva'n.Vi v~y,khib~ccuamQtnUtladj, elaso'c~nhtrongd6thi,thlltVdQdaiIonnha'tcua mQtdaybansaochontruyva'nconla: n n(n-l) Ldi=2e~2 ~n(n-I)=O(n2). ;=1 2 V~y,dQphllCt~pcuathu~troan3.6cfingla O(n2). 88