ࡱ> pro^bjbjUU A"??P 4;4;wHwHwHwHwHHHH8HHHoHHHHHHHHW0wHHHHHHwHwHHH)HHHHwHHwHHHHHHbw}HFLHHFz6?0o|zN)H)l}} )wH~(HHHHHHHHHHHHoHHHH)HHHHHHHHH4; =G:Resumo O processamento de consultas em grandes bases de dados XML ainda um problema desafiador, especialmente porque no existe um modelo e nem uma lgebra padro para o processamento eficiente de consultas a esse tipo de dados. Na literatura, autores sugerem fragmentar fisicamente e distribuir o banco de dados, para que as consultas possam ser executadas em paralelo. Entretanto, a fragmentao fsica projetada para beneficiar um conjunto de consultas frequentes. Dessa forma, aplicaes que requerem o processamento de consultas ad hoc sob bases de dados XML, tais como as OLAP, apresentam baixo desempenho ao utilizar esse tipo de fragmentao. Para resolver este problema, trabalhos anteriores propem o uso da fragmentao virtual, que consiste em replicar o banco de dados em vrios ns de processamento e definir a fragmentao dos dados em tempo de execuo da consulta. Porm, a Fragmentao Virtual Simples pode sofrer com desbalanceamento de carga na presena de distoro de dados, o que impacta negativamente no tempo de processamento da consulta. Para superar esta limitao e aumentar o desempenho do processamento de consultas, propomos nesta tese trs estratgias para o processamento paralelo de consultas XML ad hoc: Fragmentao Virtual Simples com balanceamento de carga Mestre-Escravo, Fragmentao Virtual Adaptativa e Fragmentao Virtual Adaptativa Dinmica. Alm disso, implementamos um prottipo de software para a arquitetura de um processador paralelo intraconsultas que utiliza as diferentes estratgias de fragmentao virtual em um cluster de banco de dados XML sem compartilhamento de recursos. Resultados de nossa avaliao experimental com o benchmark TPC-H XML mostraram acelerao sublinear na maioria das consultas executadas com estas estratgias de fragmentao virtual em um cluster de computadores. Em particular, a Fragmentao Virtual Adaptativa Dinmica se mostrou como a mais adequada para o processamento eficiente de consultas XML ad hoc de alto custo, acelerando o tempo de processamento dessas consultas em at 6,2 vezes no cenrio com 16 ns quando comparado ao ambiente centralizado. Palavras-chave: Balanceamento de carga; Fragmentao virtual; Processamento paralelo de consultas; XML; XQuery. Abstract Efficient query processing in large XML datasets is still a challenging problem, especially because there is no standard model and algebra to handle XML data and drive query optimization. In the literature, authors suggest to physically fragment and distribute the database, so that queries can be executed in parallel to increase performance. However, physical fragmentation is designed to benefit a set of frequent queries, and applications that require ad-hoc queries over XML datasets, such as OLAP, usually present poor performance in such settings. To solve this problem, previous work has proposed the use of virtual partitioning, which consists in replicating the dataset in several processing nodes and defining data partition at query runtime. However, Simple Virtual Partitioning may suffer from load imbalance in the presence of data skew, which negatively impacts the query processing time. To overcome this limitation and improve query processing performance, in this thesis, we contribute by proposing three skew-aware strategies for the parallel processing of ad-hoc XML queries: Master-Slave Simple XML Virtual Partitioning, Adaptive XML Virtual Partitioning and Dynamic Adaptive XML Virtual Partitioning. In addition, we implemented a prototype for an intra-query parallelism architecture that applies different strategies of virtual partitioning in a shared nothing XML database cluster. Experimental evaluation results with the TPC-H XML benchmark show sublinear speedup in most of the queries executed with these virtual partitioning strategies in a cluster. In particular, the Dynamic Adaptive XML Virtual Partitioning is the most adequate approach for heavyweight queries, speeding up the query processing time up to 6.2 times in a scenario with 16 processing nodes when compared to a single node. Keywords: Load balance; Parallel query processing; Virtual partitioning; XML; XQuery.     . 8FHIq]^_`pYZBNOPƿ嬡xxxc(hMhCJOJQJ^JaJmH sH hAhmH sH hxhmH sH hL<hmH sH hmH sH hmHhmH sH %h7Kh5;CJ\aJmH sH  hgz hhgz h5\ hG`h hLh hi{hh h?A;hhIh5;CJ\aJ#_`OPRSUVXY[\dgdWK d`gd0$d`a$gdzE`gdmH $da$`gdIgdgJ`gdA_ $h`a$gdIPQSTVWYZ]^(hMhCJOJQJ^JaJmH sH hjhU \]^$d`a$gdzE?0P1h:pzE. A!"n#$n% Dpj| 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJPJQJ_HmHnHsHtH``` \3Normal$dh`a$$CJOJPJQJ_HaJmHsHtH v v K'0 Heading 1,$$$ & Fh@&^`a$5;CJPJ\aJmHsHl l 0 Heading 2*$$ & FBx@&^B`5;PJ\mHsH\ \ K'0 Heading 3$$ & Fx@&5;PJ\mHsHl l K'0 Heading 4*$$ & F^x@&^^`5;PJ\mHsHl l K'0 Heading 5*$$ & Fx@&^`5;PJ\mHsHl l K'0 Heading 6*$$ & Fx@&^`5;PJ\mHsHl l K'0 Heading 7*$$ & Fx@&^`5;PJ\mHsH\ \ K'0 Heading 8$$ & Fx@&5;PJ\mHsHl l  K'0 Heading 9* $$ & F.x@&^.`5;PJ\mHsHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List Z/Z [IHeading 1 Char&5CJ KH OJPJQJ\^JaJ tH \/\ [IHeading 2 Char(56CJOJPJQJ\]^JaJtH V/V [IHeading 3 Char"5CJOJPJQJ\^JaJtH V/!V [IHeading 4 Char"5CJOJPJQJ\^JaJtH \/1\ [IHeading 5 Char(56CJOJPJQJ\]^JaJtH N/AN [IHeading 6 Char5OJPJQJ\^JtH P/QP [IHeading 7 CharCJOJPJQJ^JaJtH V/aV [IHeading 8 Char"6CJOJPJQJ]^JaJtH H/qH  [IHeading 9 CharOJPJQJ^JtH X/X K'0Heading 1 Char1!5;CJOJPJQJ\aJtH X/X 0Heading 2 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 3 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 4 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 5 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 6 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 7 Char1!5;CJOJPJQJ\aJtH X/X K'0Heading 8 Char1!5;CJOJPJQJ\aJtH X/X  K'0Heading 9 Char1!5;CJOJPJQJ\aJtH f/f "Ds0Ttulos!d7$8$H$'5B*CJPJ\aJmHphsHtHT/!T !Ds0 Ttulos Char#5B*CJOJQJ\^JaJph^/^ $g1H0 TextoSimples#dh#5B*CJOJQJ\_HaJph^/A^ #g1H0TextoSimples Char#5B*CJOJQJ\_HaJphf/1Rf &M0 FiguraEtabela%/5B*CJOJPJQJ\aJmHphsHtH`/a` %M0FiguraEtabela Char#5B*CJOJQJ\^JaJphD/qD jI0Ttulo do Livro 5:@\T/T jI0Texto do Espao Reservado B*phZ Z +jI0 Balloon Text)d CJOJPJQJaJmHsHtHR/R )[I0Balloon Text CharCJOJPJQJaJtH P/P )jI0Balloon Text Char1CJOJQJ^JaJH/H -k0Figuras,$a$CJPJaJmHsHtHT/T ,k0 Figuras Char#5B*CJOJQJ\^JaJph:: 0mB0Header. 8!dF/F .[I0 Header CharCJOJPJQJaJtH 00 .mB0 Header Char1: : 3WK0Footer1 8!dF/!F 1[I0 Footer CharCJOJPJQJaJtH 010 1WK0 Footer Char1R/BR 5g1H0Seo4$dha$;CJPJaJmHsHtHR/QR 4g1H0 Seo Char&5;B*CJOJQJ\^JaJphP/AbP 7Ds0 Sub-seo65CJPJ\aJmHsHtHZ/qZ 6Ds0Sub-seo Char&5;B*CJOJQJ\^JaJphB/B 9h0Tabela8(5PJ\mHsHtHR/R 8h0 Tabela Char#5B*CJOJQJ\^JaJph  h0 Table GridI:V:0ak :CJPJ^JaJ22 <a0Rodap1 ;^.2. ;a0 Rodap CharZY Z ?D0 Document Map=d CJOJPJQJaJmHsHtHR/R =[I0Document Map CharCJOJPJQJaJtH P/P =D0Document Map Char1CJOJQJ^JaJB'B _R0Comment ReferenceCJaJR R C_R0 Comment TextAdCJPJaJmHsHtHR/!R A[I0Comment Text CharCJOJPJQJaJtH P/1P A_R0Comment Text Char1CJOJQJ^JaJPj P F_R0Comment SubjectD5PJ\mHsHtHN/2QN D[I0Comment Subject Char5PJ\tH \/a\ D_R0Comment Subject Char15CJOJQJ\^JaJHrH p0Pargrafo da Lista G^/ p0Grade Mdia 3 - nfase 4>:VH0ajQ@ jQ jQ dj; djQ djQ dk 44HCJPJ^JaJ/ p0Grade Mdia 3 - nfase 2>:VI0ajQ@ ߧjQ ߧjQ PMj; PMjQ PMjQ PMk 44ICJPJ^JaJ@"@ \30CaptionJ$da$5\NN gJ0Cabealho do Sumrio K & F@& 22  0TOC 1L e# d:: w0TOC 2M e# d^22 B0TOC 3Nd^6U6 B0 Hyperlink >*B*ph<#<  0Table of FiguresP/ RO0Referncias Bibliogrficas(Qdx1$7$8$H$^`PJmHsHtHj/!j QO0Referncias Bibliogrficas CharCJOJQJ^JaJNN B0 BibliografiaS |d`\B B\ V#0 Body Text T$dx*$1$`a$KHmHsHtHL/QL T[I0Body Text CharCJOJPJQJaJtH R/aR T#0Body Text Char1CJKHOJPJQJ^JaJN rN Y#0 Footnote TextWCJPJaJmHsHtHT/T W[I0Footnote Text CharCJOJPJQJaJtH J/J W#0Footnote Text Char1 OJQJ^J@&@ #0Footnote ReferenceH*V/V );e0Tabela de Grade 1 Clara1 5:@\>/> );e0Grade Mdia 11 B*phXX );e0Lista Colorida - nfase 11 ]^/ );e0Sombreamento Mdio 2 - nfase 5>:V^0ajQ@ jQ jQ dj; djQ djQ dk 44^CJPJ^JaJ/ );e0Sombreamento Mdio 2 - nfase 3>:V_0ajQ@ ߧjQ ߧjQ PMj; PMjQ PMjQ PMk 44_CJPJ^JaJNN );e0Tabela de Grade 31 ` & F@& PJRR );e0Tabela de Grade 21ad`X/"X c);e0Quadrobd`5CJPJ\aJmHsHtHR/1R b);e0 Quadro Char#5B*CJOJQJ\^JaJph~/B~);e0Sombreamento Escuro - nfase 11d$CJOJPJQJ_HaJmHsHtH /S );e0Grade Colorida - nfase 5>:Ve0ajQ@ jQ jQ dj; djQ djQ dk 44eCJPJ^JaJ/c );e0Grade Colorida - nfase 3>:Vf0ajQ@ ߧjQ ߧjQ PMj; PMjQ PMjQ PMk 44fCJPJ^JaJ/q );e0ilB/B );e0apple-converted-spaceN/N);e0Revisoi$CJOJPJQJ_HaJmHsHtH  Nt0Initial Body Text Indentj d` (CJOJ PJ QJ ^J aJmH nHsH tH Nt0Algorithm Text2k h8d&dP`&5CJOJ PJ QJ \^J aJmH sH  Nt0 Algorithm6ld$d&dNP`)5;CJOJ PJ QJ \^J aJmH sH f/f Nt0Default m7$8$H$1B*CJOJ PJ QJ ^J _HaJmH phsH tH zAz Nt0Initial Body Textn$*$1$a$,CJKHOJ PJ QJ ^J aJmH nHsH tHT> T qK>0Titleod(@CJ8KHOJPJQJaJ8mHsHtHR/R o[I Title Char&5CJ KHOJPJQJ\^JaJ tH N/N oK>0 Title Char1 @CJ8KHOJPJQJ^JaJ8d"d K>0 Table bodyr$d`a$ CJOJ PJ QJ ^J aJmH sH 2 K>0 Table source&s$  dx<`a$(CJOJ PJ QJ ^J aJmH nHsH tH`C B` vK>0Body Text Indenttx^CJPJaJmHsHtHZ/QZ t[I0Body Text Indent CharCJOJPJQJaJtH X/aX tK>0Body Text Indent Char1CJOJQJ^JaJ:0 r: K>0 List Bullet w & F DD kf0Legenda-Figurax<`DD )0Legenda-Tabelay<`DD )0Legenda-Quadroz<`FVF  0FollowedHyperlink >*B* phPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] ^" P^ \^_`wX>Dk'z-L DFa4s$u).;W$rv;)xpL6Xq2(Lj&40*|C5vP5j4@I6 E!>6Hy_>z-L&?xQ-K%@ vP5 I6Wl %axI`F^`X|C5&?-K:g4;g4J]?Hng4V x}V<*g4(@Q        pDg4g4g4Ng4QcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcQcDQ*=B.Wn,4;/zEShQCHsF ] TFBQ$=>L^u^t ~ gz C| L O R h j $ 1 K V j G 1 ) - B wt Q [# * Q3LY*0,Vd&w)kiA!jA$5M\_c6  g?Kgkz# *gJ?Nc4347*uf.]MC[|06D\`Nx6v5w3^j^Vmt,hp#zH!PPD((#)%)`*r*{*M+ZD-H-R-d.QT.k./E#/)=08s0z0V12"2-242=24L2s2w23$3i44n45 5-555yH5|56G 6t6w6z6771H7M7W7j7s78w8B8#9:} :m;;; #;;;?A;h;Mr;x;U<1@<L<s<] ='=6=b=e >(><>?>K>Z>p>%?G?@5@8)@/J@S@AAANA/gAB| B9B{#BS(B.-Bo;B^BmB$C(C(C/C?C qC|C~CDDG+Db0D6DoGDAEDEjtE{E F-FHFhFY2GVGpdGoGH%Hg1HiIHmHIxIr:IjIrIxI rJ-K7K+L#CLlLDMM8M@:MLMOVMeM{iM'?N FN}NjOPNPePjPMtP~PUQrQRDYR_RylRSFS,T)Ts)TVlT:U'UH*U=UNU2 VVN;VEGVRVhV(qV-xVP WB`+cpX QM!?#7zN #()0EPvRlcP'&g5_KG_YRu` 3/OSi{#5p.>t.~ =%48nr+Deix/z|oO[6]&")P Q{. #${8k*q\3JPZ]fo')a?k,^\b(w 5#8KJ_lBRn+kt@@*L)SfY0L^X3C7D|",._3I6>b=CCKB3."0_GkloeUCZ~ vt<kbJgKiBu7(BFio"Z),[aoKN [[]; 43HLs[\n+ U[1cdk$<LRio4 &pHoGLCgwxOgpmM`\!w55=u3z ~ &666*g gh4SNDq-E//FmL JDB,Je*|&&|^td{) N_}"5cdLIW x,90<DTx8t#O,m"["=1:P\kf@<4@PEKz|, P E E]at4]8 !$/86[ xb17 Qr7VoA g!(@AEWT`,K\(t3U~g.WKEXAJG`uvvXyh#Bahq!)A8tzNXfOmzCw t&7gm C,QHORT\^gikl?57ONtLuyN_} _Fq _[4<HV849JO`y)~P]uC#%FtT AJWHfh l-LZ(w=SjK|+$~PR@^@@UnknownG*Ax Times New Roman5Symbol3. *Cx ArialE=Lucida Console7.@CalibriW=   jMS Gothic l r SVbN7@Cambria;. *Cx Helvetica5..[`)TahomaMCentury SchoolbookO=  jMS Mincho l r   U"NewCenturySchlbk-Roman?= *Cx Courier New;WingdingsACambria Math"XGXG0X !x0$PP*!xxOC:\Users\Docente\Dropbox\Doutorado\TESE\Tese-Luiz\versoes-texto\pgc-uff v3.dotx'Template de Dissertaes e Teses da UFFlzomatosHeliol                   Oh+'0 ,8 \ h t (Template de Dissertaes e Teses da UFF lzomatos pgc-uff v3Helio2Microsoft Office Outlook@@W@l&L@l&L ՜.+,D՜.+,T hp|   (Template de Dissertaes e Teses da UFF Title(X`hZOTERO_PREF_1ZOTERO_PREF_2