Luận văn Một số thuật toán lập chỉ mục cho cơ sở dữ liệu bán cấu trúc

-21- Chtidng2. Phtidng phap l~p chim\lC Table P- 2.1. Caedjnhnghia Dinh_nghla2-1: Gidsa D Ia m(Jttai li~uXML. M(Jtd6thiXML XD= (N, Va,E, A, \V,L:,A, <) Ia m(JtdB thico tr(ittl;Cvai : . N Ia t(ipcaenut;dur;cdungdi biiu di~ncaephtlntaha(ic thu(Jctfnh. . vaENIam(Jtnutphanbi~tdur;cgQiIanutgrIc. . E Ia t(ipcaeCf,mh;dur;cdungdi biiu diln quanh~chacangiila caephtln taha(icgiila phtln tava thu(Jctfnh. . A Ia t(ipcaecqnhchidungchacaethu(Jctfnh,AcE. . \V Ia m(Jt anhxq ticE VaGNxN, tuangungm6icqnhvahaidinh cuano. . L:Ia t(iphiluhqncaetenphtlntavathu(JctfnhcuaD. . AIam(Jtanhxqgannhiin,ticE VaGL:. . <Ia quanh~tr(ittl;CbanphtlntrenE. nffi vaimQic(ipcqnhe] vae2macungxua'tphatticm(Jtnutn, e1<e2,nfuvachinfu phtlntatuangungvaie]ndmtruacphtlntatuangungvaie2 trangD. MQt d<3thi XML choad li~uXML trongMinh hQa1-1duQctrlnhbay trongMinh hQa2-1.T~pN g<3mcacnut: Yo,VI, .. V23,voi nutg6cYo.T~pcac c(;lnhE ={eo,el,.",e22}'T~pcac c(;lnhA ={ell, e12,e14,e15,e17,elS, e20,e21}. Hamtoi \V : {(eo,(vO,VI)),(el,(vI,V2)),...} T~pL: g<3mcacten : {"DS_C~u_thu", "C~u_thu","Ten", "s6_ao", "Tu6i", "DS_DQi" , "DQi" }. Ham gannhan A . {(eo,"DS_DQi"), (er," DQi"),...}.Ta clingco mQtquanh~banph~n< : el <e2, e3<e4. -22- /3 Ten C:) f"' e4: Ds_ciu_thd A e7: CilUhli eS: Ciu_thd ~ CO~Qi ~e2:£>l)i Doi 3 France e9: Ciu_thd Italy £;'" ~&.,~O~. .~ .,,~ ~,. .~'~,. ~""~ ~ Toti 26 10 Toldo 33 12 Bathez 32 Zidan 29 10 Minh hQa2-11)6thiXML cuatiti li~uXML trongMinhhQa1-1 -23- Ma hlnhhoatai lit%uXML theodinhnghiad6thiXML trenla mQtcaiti€n cua mahlnhOEM, vadadu<jcsud\lngtrongmQts6tailit%uv~DataGuide,Toxin. Dinh_nghla2-2: GidsaXD=(N,Va,E,A, \jJ,~,'A,<)la mQtdBthiXML Vap =(VI, ej, V2, ..., em Vn+I)trong doVi EN, 0::;;i::;;n+l va ej E E, O::;;j::;;n la mf)tduilngd6n trongXD.ChungtagQichulJi l='A(eI)/ 'A(e2)/.../'A(en)la mQtduilng d6n nhiin,ky hi?u'A(p).MQtduiJngddnnhiinl co thi co nhduduiJngddnp tuClnglingsaDchol='A(p).MQtduiJngddnp nhutht du(lcgQila mQtthi hi?n (instance)cual. Ntu chi co nhdunhatmQtthi hi?ncuabatcli mQtduiJngddn nhiinnaotrongmQtdBthi,thldBthidodu(lcgQiladdndjnh. Dinh_nghla2-3: GidsaXD=(N,Va,E,A, \jJ,~,'A,<)la mQtdBthiXML, mQtduiJngddnp =(vj, ej, V2,...,emVn+I)du(lc gQi la tuy?tdelintu VI ==Va,ngu(lc l(,Iip du(lcgQila duiJngddntuClngdffi. MQts6vi d\l : . Duongd§.n: (vo,DS_DQi,VI,DQi,V2,Ten, V4) . Duong d§.n nhan : DS_DQi/DQi/Ten,DS_DQi /DQi /DS_C~u_thu, C~u_thu/Ten. Dinh_nghla2-4: Gid saXD= (N, Va,E, A, \jJ,~, 'A,<) la mQtdBthiXML, l lamQtduiJngddnnhiin,mQtqpdichcualla tqpcacnutcothiduhanhdtnbiJi ltrongXD, T(l) = {v l:3p =(xa,...,v), 'A(p)=lj. D€ ltiutrll cacnuttai lit%u,hamltiutrll du<jcdinhnghlanhusau: Dinh_nghla 2-5 : MQthamluu tril is cuacuacayXML XD = ( N, Va,E, A, ~, ~, 'A, <) la mQtanh X(l is..N -7 Z. Trongdo Z la tqpcac danhdinh luu tril (storageindentify- sid) .Hamis phdi la songanh.. . V6'imlJi ZE Z, :3nE N saDchois(n) = z. -24- . MJi Z E Z co chimQtn E N tuangling. M6i danhdinhlliutrfi'dungd€ xaedinhvi trieuanUttu'onglingtrenthi€t bi hill tIll, clingnhu'd€ phanbi~tcaenutvoi nhau. ; 2.2. Caethaotaeduli~u Trang qua trlnhth1!ethi caetruy va'n,caebQxU'ly truy va'nt~omQtk€ ho~ehthi h~mh(queryplan)baag6mcaethaotaedfi'li~u,la caechilenangxU'ly dfi'li~u0 miledongiannha't.Caeh~qUailly CSDL thu'ongto'iliu hoaxU'ly truy va'nbangeacht~omQt k€ ho~ehthih~mhto'iliu d1!atrencaechimvehi~ncova caethongsO'thO'ngke. Y tu'ongeualu~nvannayla clingea'pcaeea'utruechimveh6tn;5vi~eto'i u'uhoamQtsO'thaotaedfi'li~uquailtrQngsail: 1. Nav(lo,v, l) . TImt~pcaenUtdichU sailkhidi tuv theodu'ongdin I, 10ladu'ongdin d€n nutv. 2. Inv_Nav(lo,v, D). TIm nutdichu la ehaea'pn euanutv, 10la du'ong din d€n nutv. 3. Giiii thu{HSearch(l,a,b).TImt~pcaenutU la nutdicheuadu'ong din1,saoehogiatrieua'ill EU namtrongdo~n[a,b]. 4. Descendant(10,v ,I).TImt~pcaenutconehauconhffn1euanutv , 10 la du'ongdin d€n nUtv. Cae thaotae dfi'li~unay dff du'<;5eehQnl1!ad1!atheovi~ephantich eu phapeua bi€u thile du'ongdin XPath[28](Phvlve B cling ea'pgioi thi~ud€n XPath).MQt Call truy va'n XPath: Ql =/DS_DQiffiQi[Ten="Italy"]/DS_C~u_thu coth€ du'<;5exU'ly boi caethaotaedfi'li~usail : Rll =Search("/DS_DQi/ DQi/ Ten","Italy","Italy"). -25- R12=Inv_Nav("/DS_DQi / DQi / Ten", R11,1). R13=Nav("/DS_DQi/ DQi", R12,"DS_C~u_thu"). MQts6vi dl,lkhac: Vi dt;ll: Q2=II Ten duQcphantichthanh: R21=Descendant("/",vo,"Ten"). Vi dQ2: Q3=/ DS_DQi/ DQi[Ten="Ita1y"]//Tu6i duQcphantichthanh R31=Search("/DS_DQi / DQi / Ten","Italy","Italy"). R32=Inv_Nav("/DS_DQi/ DQi/ Ten",R31,1). R33=Descendant("/DS_DQi/ DQi" , R32, " Tu6i"). 2.3. Cae ea'utrue chi IDl}e PhuongphapP-Tablecobac1utrucchiffil,lC. . BangchImQcdu'ongdftnp.Table (Pathtableindex)dungd~h6trQ chocacthaotacdii'li~uDescendantvaNav trongtruonghQpx la nut g6c. . BangchImQcghitrf (Valueindex-Vlndex)dungd~h6trQchothao tacSearch. . Bang duy~tcity (Treetraverseindex-Tlndex)dungd~h6 trQcho thaotacNavvaIlly_Nay. Bang2-1Bangchiml.lCddongddn ? ? ,- lBangChImQcduongdaD(p.TableIndex) Ten thuQcHnh Yngh'ia Duong dftncha Duongdfindennutchao Nhan Nhancuanut. Nut Id Danhdinhlliutrii'cuanut. -26- Dinh_nghia 2-6: Gid sa Xv =(N, va,E, A, \jf,L, A, <) Ia mQtdb thiXML, is Ia hamIuutril.MQthamchi ml.lcd1idngdOnP-TablefPt ..N -7PT , trangd6 PT =NNx LX PP.. . NI t~pdanhdinhIuutril. . PP Ia t~pduiJngdt1n. Gid sa v c N, fPt(v) = (ni, I, pp) dU(lcxclcdinh nhusau .. . ni =flv). . I c L , Ia nhancuac{;mhdi tJi v Gid sap = (vo,eo...,emv) thil =A(en). . pp Ia duiJngdt1nnhancuanutchacuav. Gid sap = (vo,eo...,emv) thipp = A(eo)/..f'A(en-]). MQtbangchi ml.lcd1idngdOnP-Table Ia range(fplN)). Bang2-2Bangchim1,lcghitrio Bang2-3Bangduyt;tcity. BangchI m\lc duy~tdlY (Tindex&ITIndex) I TenthuQc tinh Dti(ing_d~n NuCp_Id NuCc_Id Y nghia Duongd~ntunutg6cd€n nUtcon. Danhdinhcuanutchao Giatricuanutcon. MQt bangchi mvc gia trioban'gduyl%tdiy donthu~nla cac bangtra CUll thuQclo<;tichi mvc ph~nttl'nhudffnoi ()ph~n1.3. Bang chi mvc duyl%tdty co thSduQcl~pchimvcdSh6trQhaithaotacnguQcnhau.ThaotactlmnUtcon Bang chi m\lc ghi tri (Vindex) I , Ten thuQc Y nghia tinh Duongdftn Duongdn dn nut. Nut id DanhdinhhilltIll cuanut. Gia tri Giatricuanut. -27- cuamQtnUtduQch6 trQboi chImvcduy~tdiy thu~n, gQila TIndex.Thaolac till nut chacua mQtnUtduQch6 trQboi chI mvcduy~tdiy nghich,gQi la ITIndex.Giii thu~t~ocacbangchI mvcgia tri va duy~tdiy ddngiannen <I khangmata0 day.Giai thu~t~obangchImvcP-TableduQctrinhbaytrong Minh hQa2-2 GildthuqiBuild_PTABLE( XD). DftuV~lO Xo : D6thiXML, Xo =(N, Yo,E, A, \jf,~,A,<). Dftura ? l'; tra ve : BangchImvcduongd~nPTable . Phu'ongphap PT~0 for eachv E N do sid ~ danhdinhhilltrucuav. 1 ~ nhanc~nhWi v. pp ~ duongd~ndennutchacuav. ThemvaoPT mQtbQ (pp,1, sid) od return PT MinhhQa2-2 GhHthu~tt~obangchimt;lcddo-ngdfinp.Table. Minh hQa2-4 , Minh hQa2-5 , Minh hQa2-6 trinhbay ba bangchI mvc cuad6thiXML trongMinh hQa2-1voi hamlu'utrunhutrongMinh hQa2-3. MinhhQa2-3 Hamldutru. Nut Vo VI V2 V3 V4 Vs NuCID 0 1 2 3 4 5 -28- Minh hQa2-4Bangchim1,1cdu<tngd~nchode)thiXML trongMinh hQa2-1. MinhhQa2-5Bangchim1,1cgill tri chode)thi XML trongMinh hQa2-1. MinhhQa2-6Bangchim1,1cduy~tcay chode)thiXML trongMinh hQa2-1. Caecfiutruedfi'lit%unaykh6ngphaila hoantoanmoimath~tra la co tu'ongd6ngvoicaecfiutruedffdu'cjcnghienCUlltru'ocday.Bangchimvcgiatri tu'ongtlfnhu'chimvcgiatricuacaephu'ongphaphit%nco : Toxin,SphinX.Bang duyt%tcay tu'ongttf nhu'caebangth€ hit%n(instancetable)cuaphu'ongphap Toxin. Bangchi mvcdu'ongd~nchinhla mQtbi€n th€ cuacfiutruechimvc d.~lllgcayDataGuide,I-Index... Vi~c chQnItfacfiutrued(;lngbangthaychod(;lngcay co mfiy ly do chinh sau: l Duong dftn cha Nhan Nut Id "I" "DS DQi" 2 "I pS DQi" "DQi" 3 "I DS DQi" "DQi" 4 "I DS DQiI DQi" "Ten" 5 "I DS DQiI DQi" "DS ch thU" 6 Duong dftn Nut id Ghi tri "I DS DQiI DQilTen" 5 Italy "I DS DQiI DQilTen" 7 France "I DS DQiI DQilDS cu thUI ch thUlTen" 13 Toti "I DS DQiI DQilDS ch thUI ch thUlTen" 16 Toldo Duongdftn Nut p Id Nut c Id "IDS DQi" 1 2 "IDS DQi/DQi" 2 3 "IDS DQi/DQi" 2 4 "IDS DQi/DQiITen" 3 5 "IDS DQi/DQiTen" 4 7 -29- . D,~lllgbangd€ qUailly vffnd~hill tru hdnd,;lllgdiy nhfftla cac thaolac them,xoatrencayrfftkh6qUailly. Day clingla ly domQts6 cffutruchill truhi~nthaithi€u khananghill tru. . Hi~usufftcuacffutruccayph\lthuQCnhi~uvaodQsaucuacayvadQcan bang,trongkhid6caccaychim\lcthu'angrfftkhongcanbang.Hi~usufft cuad~ngbangchiph\lthuQcvaos61u'Qngduli~u. . D~ngbangc6 the lu'utru du'oid~ngcay B+Tree. Di~ud6 deml~inhi~u IQith€ : t6cdQtlmki€m, truyvffnkhoang,baaloantr~ttv,phantrang. Bang2-4Giaodit;nchim\lcciiaphtidngphapp.Table. Giaodi~nchim\lccuaP-Tabledu'Qct6mHittrongBang2-4va du'QCmo tachiti€t trongmffyhamsau. a. Ham searchPT(PT,path,label) : TImki€m cacnUtc6du'angdftn d€n nutchapathva nhffnlabel.Hamsu d\lngtinhnangtlmki€m trenB+TreecuaPTablePT. b. Ham searchT(T,parent,path): TIm ki€m cacnutc6 nutchala parent,voipath la du'angdftnd€n nutcon.Hamsud\lngtinhnang tlmkie-mtrenB+TreecuaTlndexT. Chi m\lcP-Table Du:angddnd(/f1->NutID Nhiin ->NutID Chi m\lcgia tri Mfnh d ->NutID Chi m\lcduyt caythun NutID cha, Du:angddn->NutIDcon Chi m\lcduyt cayngu'Qc NutID con, Du:angddn->NutIDcha -30- c. Ham searchIT(IT,path,children): TIm kie'mnutco nutconla children,yoi path la du'ongd~nde'nnutcon.Hamsa dvngtlnh nangtimkie'mlIenB+TreecuaITlndexIT. Ham searchV(V,path, a, b) : TIm kie'mcacnutco du'ongd~nd. path,yoi giatrin~mtrongdo<;ln[a,b] . Hamsadvngtlnhnangtim kie'mlIenB+TreecuaVlndexV. 2.3.1.Lu'utru chi ID\lC BangchImvc du'ongd~nP-Tablecoth€ du'<;jchilldu'oid<;lngdiy B+Tree hailOpnhu'trongMinhhQa2-7.Bangchimvcdu'ongd~ntru'oche'tdu'<;jcl~pchi mvctheokhoaNhan,sand61~pchimvctie'ptheoDu'ong_ddn_cha. Chi fiVC theaNhan ~ Chi fillC theo dUong dh cha Chi fillC theo ~ "',,'"",,.. Chi fillC theo ~."'"' "",', MinhhQa2-7Ltiu tru chiIDQCdu'ongdftndu'oid;;.ngdiy B+Treehailop. Bang chi mvc gia tri clingco th€ du'<;jchill du'oid<;lngB+Tree hai cfipnhu' Minh hQa2-8.BangchI mvcgia tri du'<;jcl~pchimvctheokhoaDu'ong_ddn,san d6theokhoaGhi_tri. -31- Chi fillC thea gia rri Chi ill\1Crhea Quang ctdn ~ Chi fillC rhea gia ih "j ~ Chi fillC rhea gia rri MinhhQa2-8Lliu tru bangchi mt;lcghitrf du'oid~ngcayB+Treehailop. Bangduy~tdiy thu~ncoth€ lu'utrfi'duOid.;mgB+Tree voikhoakepnut cha (Nut_p_Id) va nhan.Bang duy~tcay ngu<;Jcdungkhoa la nut con (NuCc_id). 2.4. Caegiaithu~tehocaethaotaedii'li~u Sandayla giaithu~tchocacthaolac dfi'li~umadlfalIen mQts6ham du<;Jccoi la co san.MQts6hamsedu<;Jcgiaithich0 ph~nghichucuam6igiai thu~t.MQts6khacla cactinhnangcuachimvcduongdftn(PTable),chimvc giatri (Vlndex),chimvcduy~tcaythu~n(Tindex),vachimvcduy~tcaynghich (ITlndex). -32- Gidi thuq,tNav(lo, v, I) .TIm t~pcaenutd:ichU saukhi di tirv theodu'ongd~nI, 10la du'ongd~nde'nnutv. D~uvito v 1 10 p T D~ura travi: Phu'dngphap : nutb~tdeiuduh~lllh. : du'ongd~ndu'ongd~ntir nutb~tdeiude'nnut ceint1m. : la du'ongd~ntirnutg6cVode'nnutv. : chimvcdu'ongd~n. : chimvcduy~tdiy. : t~pnutd:ichU = '"C(1). if 10="/" then parentPath+--rheindu'ongd~nde'nnUtchacua1. nodeLabel+--rheinnhancu6iclingcua 1. u=searchPT(P,parentPath,nodeLabel) else path +--10 nodeLabel+--rheinnhandeiutiencua1. u +--v; whilenodeLabel0 do path+--path+nodeLabel; u +--searchT(T,u,path) 1+--rheindu'ongd~nconI~isaukhibonhandeiu. nodeLabel+--rheinnhandeiutiencua1. od fi returnu MinhhQa2-9Gia thu~tNay. -33- Giiii thui)tInv_Nav(lo,v,D). TIm nutdichu Ia chacip n cuanut v,10la duongd~nde'nnutv. Dftuv~lO v n :nutb~td~uduhanh. :cip cuanutchasovainutb~td~u. :chim\lcduy~tdiy theohuangnguQc.IT D~ura tnlv~ :nutchaune'u3p=(u,eI, ...,en,v). Phtidngphap u~ v path~ 10 while n > 0 do u ~ searchIT(IT,path,u) n~n-l path~ ph~nduongd~ndabo nhancu6icling. od returnu MinhhQa2-10Giiii thu~tInv_Nav -34- Giiii thuljtSearch(l,a, b). TIm t~pcaenutU la nutdichcua du'ongd~n1,saGchogiatricua'v'uE U n~mtrongdo~n[a,b]. J Dftuvito a,b :du'ongd~ncuacaenutc~ntim. : caegiOih~ndu'oiva trencuakhoang tric~ntim. :chImvcgiatrio gia 1 v Dftura travi: : t~pnutdich U c 't(l),'v'uE U, a<=u <=b. Phuo'ngphap return searchV(V,1, a , b) MinhhQa2-11Gh'ithu~tSearch. -35- Giiii thuljt Descendant(10, v , I). TIm t~pcacnutconchauco nhan1cuanUtv , 10la du'ongd~nd€n nutv. Dftuvito v 10 1 PT : nutchao : du'ongd~ntITnutg6cVod€n V. : 1E ~nhancuanUtconchau. : chim\lcdu'ongd~nPTable. D~ura trav€ : t~pnutconchauU={u13p=(v,eo,...,e, u),A(e)=l}. Phuongphap if 10="j" then PP xU =searchPT(PT,0,1) returnU else result+-0 PP xU+- searchPT(PT,0,1) for (parentPath,u) E PP XY do c ~ dOdaidu'ongd~ntITnutv d€n u if (N€u 10la ph~nti€n t6 cua parentPath) v ==Inv_Nav(u,1,c)) then result+-resultu u va fi od returnresult fi Minh hQa2-12Ghii thuilltDescendant. -36- 2.5. Bi!o trl Calltruc chi m\lC Ben c~nhvi~cxay dljng, tra CUllcua cac ca'utruc chi ml,lc,vi~cbaa trl cling la mQt va'nd€ c~nquailtam.BO'ivoi mQtsO'phuongphapchi ml,lckhi co & themduli~umoiho~cphaixoabotduli~ucli thicacca'utrucchiml,lcc~nphai xaydljngl~itli d~u.Bi€u dolamgiamhi~usua'th~thO'ngdi ra'tnhi€u dO'ivoi cacco saduli~uIOn.B€ tranhva'nd€ do , phuongphapP-Tablesu'dl,lngmQt phuongphapc~pnh~tangd~ntrong baatrl cacca'utrucchiml,lc.Cacph~n sansedi vaochiti€t trongcactruonghQpCl,lth€ : themduli~umoi,xoa, sua chU'aduli~usanco. 2.5.1.Themnutdii'li~umoi L~p chi ml,lcb~ngphuongphapP-Table khongdoi hoi phai l~pchi ml,lc l~ikhi cob6 sungdu li~umoi.Vi~csU'dl,lngB+Tree d€ lu'utrucacbangchiml,lc nay chophepb6sungthemcacthongtinchiml,lccuacacnUtmoiduQcthem vaomakhonganhhuangd€n cacnUtsanco.MinhhQa2-14,MinhhQa2-15mo ta slj thayd6ibangchiml,lcP- Tablesankhi co slj thayd6idu li~unhutrong MinhhQa2-13.BO'ivoi bangchiml,lcgia tri haychiml,lcduy~tcay(thu~nva nghich)slj thayd6i clingtuongtlj. -37- § C? 9 J 6T'" °'6" cp ~ ,,~B" 6 Du'b Italy France Italy (a) DO'li~u XML ban dJu "O\~ Ten 6 France (b) DO'li~u XML sau khi them nut mdi Minh hQa2-13. Tili li~uXML trdoc va sankhi them nut moi. Minh hQa2.14Bang P-Table ban ddu ung voi Minh hQa2-13(a). I Minh hQa2-15Bang poTablesankhi them dO'li~umoi. Duongdftncha Nhan Nut Id I DS DQi 1 IDS DQi DQi 2 IDS DQi/DQi Ten 3 IDS DQi/DQi DS ch thii 4 Duong dftn cha Nhan Nut Id I DS DQi 1 IDS DQi DQi 2 IDS DQi/DQi Ten 3 IDS DQi/DQi DS Cu thU 4 IDS Di)i Di)i 5 IDS Di)i/Di)i Ten 6 -38- Gild thuij,tAddNode_PTABLE(PT, v) .ThemthongtinchImvc cuamQtnUtdfi'li~uvaobangPTablePT. Dftuv~lO XD PT Dftu ra : B6 thiXML, XD =(N, Yo,E, A, \jJ,~,A,<). : Bang chI mvc du'ongd~nPTable . Phlidngphap sid ~ danhdinhhilltrfi'cuav. 1 ~ nhanc~nhtoi v. pp ~ du'ongd~nd€n nutchacuav. Them vaoPT mQtbQ(pp,1,sid). 2.5.2.XoanutdiI Ii~u KhixoamQtnutdfi'li~uXML, c~ncosv'thayd6id6ivOicab6nc1utruc chImvc.Khongnhfi'ngmQtnUtbi xoamat1tcacacnutconcuanoc~ndu'Qcxoa khoicacc1utrucchImvc.Khi c~nxacdinhcacnutconcuanutc~nxoachung taphai stl'dvngchI mvcduy~tdiy thu~n,cholien chungtalien co danhsachcac nUtc~nxoa va du'ongd~nd€n cac nutdo tru'ockhi chungta xoa chungra khoi chImvcduy~tdiy thu~n.TrongMinhhQa2-16,nut2bi xoakeotheocacnut4, 5 clingbi xoakhoitai li~uXML. MinhhQa2-18motasv'thayd6icuachImvc P-TablesovoiMinhhQa2-17saukhixoanut2.Giai thu~tc~pnh~tchoP-Table du'QcmotatrongMinhhQa2-19,congiaithu~tchocacc1utruckhactu'dngtv' nenkhongdu'Qcmota(jday. -39- (a)Tiii lieu XML ban d~u (b) Tiii lieu XML saukhi XG;!nut 2. MinhhQa2-16Tai li~nXML tru'O'cvasankhixoanut. MinhhQa2-17BangpoTableband~nungvO'iMinh hQa2-16(a). MinhhQa2-18BangpoTablesankhixoanut. DS_D6i DS_DQi J 9 D6i D6i DQi ,,?{ 9 6"'°'6 Ten cb Italy France France Duong dftn cha Nhan Nut Id I DS DQi 1 IDS DQi DQi 2 IDS DQi/DQi Ten 4 IDS DQi/DQi DS ch thU 5 IDS DQi DQi 3 IDS DQi/DQi Ten 6 Duong dftn cha Nhan Nut Id I DS DQi 1 IDSDQi DQi 3 IDS DQi/DQi Ten 6 -40- Giiii thuijtDeleteNode_PTABLE( PT, V). Dftu V~lO ~ PT : Bangchi fiVC du'ongd~nPTable . : NUtc~nxoa.v Dftu ra ? }!; trave : Bangchi fiVC du'ongd~nPTable . Phuongphap v ~ Xacdinhtit cacacnutconcuav for eachv E V do sid ~ danhdinhhilltrucuav. I ~ nhanc(;lnhtoiv. pp ~ du'ongd~ndennutchacuav. Xoa khoiPT bQ(pp,I , sid) MinhhQa2-19Ghli thul,itxoanutdfi'li~ukhoiP-Table 2.5.3.Sll'achiIatiti li~u C6haitru'onghQpsuachuaadli~uXML c6th€ xayra : suachti'anhanva suachti'agia tri cuanut.Hai tru'onghQpc6 anhhu'angkhacnhaudencacciu trucchifiVC. Trongtru'onghQpsti'achti'agia tri cua nut,chi c6 chi fiVC gia tri c~nphai c~pnh~t.TrongMinh hQa2-20, nUt6 du'Qcthayd6i gia tri tu "France" thanh "Phap".Di6ud6 du'Qcphananhthanhthayd6i gia tri cuahangthlihai trong MinhhQa2-23 sovoi MinhhQa2-22.Trongkhi d6MinhhQa2-21hoantoan khongc6 thay d6i tu'dngling. Neu nhu'bangchi fiVC gia tri du'Qchill tru du'oi -41- d~ngB+Treethic~ncosljc~pnh~tb~nghaithaotac: xoanutB+Treechuagia triCllvathemmQtnutvoigiatrimaio j cp ~ ~ ~ 0';9 9f';-'""' do~ J; 6"'" D'~ J; d ,~"'; 6"'"'-5 Italy France Italy Phap (a) Hi li~u XML ban dJu (b) Hi li~u XML saukhi sita nut MinhhQa2-20Tai li~nXML truckvasankhistYachiia. TrangtnionghQpstrachuanhancuanut,cabac:1utrucchimvcd~uphai c~pnh~theo. Nhancuanut2 trongminhhoaMinhhQa2-20du'Qcthayd6itu "DQi"thanh"DQLbong".Slj thayd6idodu'ad€n slj thayd6itrangP-Tablenhu' MinhhQa2-21sovoi MinhhQa2-17, trongchi mvc gia tfi nhu'Minh hQa2-23 sovoi MinhhQa2-22. Voi B+Treedu'Qcstrdvngnhu'c:1utruchilltru, nhi~uslj thayd6ic~ndu'Qcthljchi~nchocabac:1utrucchimvc.Voi P-Table, c~nxoa nutconhanthayd6ivat:1tcacacnutconcuanorakhoiB+Tree, saudothem VaGvoi giatrinhanvadu'ongd~nmoi.Voi chimvcgiatri,nUtconhanthayd6i vat:1tcacacnUtconcuanotrongchimvcgiatric~ndu'Qcxoava saudothem VaGvoigiatridu'ongd~nmaioTu'dngtljchochimvcduy~tcay. -42- Minh hQa2-21Bangchim~cdu'(tngd~nsankhisuachua. MinhhQa2-22Bangchim~cghitrt tru'8ckhisuachua. MinhhQa2-23Bangchim~cgill trt sankhisuachua. MinhhQa2-24Bangchim~cduy~tcaythu~nband~u. MinhhQa2-25Bangchim~cduy~tcitythu~nsankhisttachtta. Duong_ddn_cha Nhan Nut_Id I DS B(>i I IDS_B(>i DQi bon 2 IDS B(>i/DQibong Ten 4 IDS B(>i/DQibong DS C u thd 5 IDS_B(>i B(>i 3 IDS B(>iIB(>i Ten 6 Duongddn Gia_tri Nut_Id IDS B(>iIB(>iITen Italy 4 IDS B(>iIB(>iITen France 6 Du'£ingddn Ghi tri Nut Id IDS_B(>i/DQCbonglTen Italy 4 IDS B(>iIB(>iITen Phap 6 Du'ong ddn Nut -p-Id Nut c Id "IDS_B(>i" 0 I "IDS B(>ilB(>i" I 2 "/DS_B(>ilB(>i" I 3 "IDS B(>i/B(>ilTen" 2 4 "IDS_B(>ilB(>ilDs_ch_thd" 2 5 "IDS B(>ilB(>ilTen" 3 6 Du'£ing_ddn Nut_p- Id Nut c Id "IDS B(>i" 0 I "IDS B(>i/DQi Bong" I 2 "IDS_B(>ilB(>i" I 3 "IDS B(>ilDQi BongI Ten" 2 4 "IDS_B(>ilDQCBong/ Ds_ch thd" 2 5 "IDS B(>i/B(>i/Ten" 3 6