以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的xml路徑查詢(xún)處理(編輯修改稿)
2025-07-22 17:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 對(duì)集合.文獻(xiàn)[11]中詳細(xì)論述了利用SUPEX索引實(shí)現(xiàn)上述操作的方法. 選擇性結(jié)構(gòu)連接操作結(jié)構(gòu)連接是XML查詢(xún)處理中的核心操作,目前所考慮的結(jié)構(gòu)連接操作是一種完全結(jié)構(gòu)連接操作,查詢(xún)樹(shù)的計(jì)算是以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的,對(duì)無(wú)用查詢(xún)結(jié)果的剔除可以盡早進(jìn)行,其定義如下:定義10. 給定兩個(gè)輸入集合A={(a1,a2,…,am)}和D={(d1,d2,…,dn)},A和D分別是m維和n維元組的集合,對(duì)指定的潛在祖先ai,潛在后代dj以及輸出結(jié)果定義,選擇性結(jié)構(gòu)連接操作產(chǎn)生的結(jié)果集合為{(x1,x2,…,xp)|ai是dj的祖先。xk206。{a1,…,am}或者xk206。{d1,…,dn},且xk在輸出結(jié)果定義中,k=1,…,p}. 選擇性結(jié)構(gòu)連接算法實(shí)現(xiàn)本節(jié)給出了兩類(lèi)選擇性結(jié)構(gòu)連接算法:排序合并和基于區(qū)域劃分. 選擇性排序合并結(jié)構(gòu)連接算法dn+1a2and1d2d2nd2n1dn…(a) XML tree(a) XML樹(shù)…a2a1and1d2d2nd2n1dndn+1…(b) Sort merge join by ancestor nodes(b) 按祖先節(jié)點(diǎn)排序合并結(jié)構(gòu)連接(c) SSMJAnc(c) SSMJAnca2a1and1d2dndn+1…… A case for SSMJAnc algorithm圖4 SSMJAnc算法的例子a1根據(jù)輸出結(jié)果是A或D中的元素,選擇性排序合并結(jié)構(gòu)連接(selective sort merge join,簡(jiǎn)稱(chēng)SSMJ)算法有兩個(gè):,避免了對(duì)某些元素的處理,(a)所描述的數(shù)據(jù)分布情況下,圖4(b)描述了按祖先排序合并算法進(jìn)行完全結(jié)構(gòu)連接的對(duì)D的多遍掃描,而圖4(c),SSMJAnc和SSMJDes只適用于祖先后代關(guān)系的計(jì)算.d2n1d2na0a1ana2d1d2d3dn…a3…a0a2ana1d1dn…d2(a) XML tree(a) XML樹(shù)(b) Sort merge join by descendant nodes(b) 按后代節(jié)點(diǎn)排序合并結(jié)構(gòu)連接(c) SSMJDes(c) SSMJDesa1ana2d1d2d3dn…a3… A case for SSMJDes algorithm圖5 SSMJDes算法的例子a0 基于區(qū)域劃分的選擇性結(jié)構(gòu)連接算法針對(duì)輸入數(shù)據(jù)集合無(wú)序的情況,我們已經(jīng)提出了基于區(qū)域劃分的結(jié)構(gòu)連接算法(range partitioning join,簡(jiǎn)稱(chēng)RPJ)[12],針對(duì)選擇性結(jié)構(gòu)連接操作,我們提出了基于區(qū)域劃分的選擇性結(jié)構(gòu)連接算法(selective range partitioning join,簡(jiǎn)稱(chēng)SRPJ).該類(lèi)算法包括兩個(gè):輸出結(jié)果限定在A上的SRPJAnc和輸出結(jié)果限定在D上的SRPJDes. SRPJAnc算法SRPJAnc充分利用元素編碼的特點(diǎn),盡早地對(duì)A中節(jié)點(diǎn)進(jìn)行判斷,:(1) ,只要Ri對(duì)應(yīng)的子集合Di中的元素節(jié)點(diǎn)數(shù)目不為0,我們?cè)趯?duì)A中的節(jié)點(diǎn)進(jìn)行劃分時(shí)就可以判斷一些節(jié)點(diǎn)是否有后代節(jié)點(diǎn),具體的判斷規(guī)則為:假設(shè)A中的一個(gè)節(jié)點(diǎn)a的區(qū)域編碼完全覆蓋了n個(gè)子區(qū)間,如果這些子區(qū)間所對(duì)應(yīng)的D的子集合中至少存在一個(gè)不為空,那么在D中一定存在a的后代節(jié)點(diǎn),就不再劃分到子集合中進(jìn)行處理。對(duì)于那些不能確定為結(jié)果的A中節(jié)點(diǎn),只需將其劃分到與區(qū)域編碼部分相交的子區(qū)間所對(duì)應(yīng)的子集合中,這樣的子集合的最大數(shù)目為2.(2) ,所以它可能在結(jié)果中出現(xiàn)兩次,即連接階段產(chǎn)生的結(jié)果集中可能出現(xiàn)重復(fù)元素.(3) ,去掉重復(fù)值. SRPJDes算法SRPJDes的基本思想與SRPJAnc類(lèi)似,:(1) ,所采用的劃分方法與RPJ相同,在對(duì)后代節(jié)點(diǎn)集合D進(jìn)行劃分時(shí)可以判斷一些節(jié)點(diǎn)是否有祖先節(jié)點(diǎn),判斷規(guī)則為:假設(shè)D中的一個(gè)節(jié)點(diǎn)d應(yīng)當(dāng)劃分到Di,如果對(duì)應(yīng)的Ai的Vi值不為0,則Ai中一定存在d的祖先節(jié)點(diǎn),就不再劃分到子集合中進(jìn)行處理。對(duì)于那些不能確定為結(jié)果的D中節(jié)點(diǎn),仍按照RPJ算法中的劃分方法劃分到子集合中,進(jìn)行進(jìn)一步的處理.(2) ,.5 實(shí)驗(yàn)結(jié)果和分析為了對(duì)本文中所提出方法的有效性進(jìn)行驗(yàn)證,分析. 實(shí)驗(yàn)設(shè)置我們的實(shí)驗(yàn)在Native XML數(shù)據(jù)管理系統(tǒng)OrientX的基礎(chǔ)上進(jìn)行,所有的算法都用C++ ,256M RAM,40G硬盤(pán)的PC上運(yùn)行,底層操作系統(tǒng)是Windows XP.,去掉最高和最低值后得到的平均執(zhí)行時(shí)間. 選擇性結(jié)構(gòu)連接的有效性選擇性結(jié)構(gòu)連接操作在我們的路徑查詢(xún)框架中具有重要的作用,本節(jié)我們結(jié)合所提出的多種實(shí)現(xiàn)算法對(duì)其進(jìn)行性能上的分析.我們采用IBM XML Generator生成了大小為113M的實(shí)驗(yàn)文檔,所用的DTD如圖6所示,它們可以分為兩類(lèi):Q1到Q4是簡(jiǎn)單結(jié)構(gòu)關(guān)系查詢(xún)。Q5和Q6是復(fù)雜查詢(xún),我們也在真實(shí)的數(shù)據(jù)集DBLP和XMark上進(jìn)行了實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果類(lèi)似.225。!ELEMENT manager (name, (manager | department | employee)+)241。225。!ELEMENT department (name, ?, employee+, department*)241。225。!ELEMENT employee (name+, ?)241。225。!ELEMENT name (PCDATA)241。225。!ELEMENT (PCDATA)241。 The DTD of synthetic data set圖6 人工數(shù)據(jù)集的DTDTable 1 Description of synthetic data set表1 人工數(shù)據(jù)集的描述ElementNumberManager38Department286 459Employee543 685Name1 111 390Email59 946Table 2 Description of queries of synthetic data set表2 人工數(shù)據(jù)集的查詢(xún)描述QueryPath expressionResult (Ancestor)Result (Descendant)Q1manager//employee38543 685Q2department//employee286 459543 631Q3department//34 22359 929Q4employee//31 39131 391Q5department//employee//10 47731 37
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1