XML文件樹(shù)狀路徑查詢優(yōu)化研究

1、XML文件樹(shù)狀途徑查詢優(yōu)化研究摘要XL查詢優(yōu)化成為XL數(shù)據(jù)庫(kù)研究熱門(mén)，此中的布局毗連是其重要操縱。毗連挨次的選擇是XL查詢的焦點(diǎn)題目。本文提出在片斷途徑樹(shù)的底子上，提出了一種毗連及組合途徑表達(dá)式的計(jì)謀，該計(jì)謀是起首得到最優(yōu)化途徑序列，末了將最優(yōu)化序列組合成完備的查詢效果。關(guān)鍵詞XL；查詢優(yōu)化；途徑表達(dá)XQuery是由3訂定的，其目的是提供一種查詢語(yǔ)言，讓利用者可以從XL文檔中尋出所必要的資料。XQuery根本上包羅三個(gè)子句，在Fr語(yǔ)句中，利用者可以利用XPath指定所要依序處置懲罰的元素并將其設(shè)置給一個(gè)變量，here語(yǔ)句那么是可以對(duì)每個(gè)變量舉行條件限定，而Return語(yǔ)句那么是可以指定所盼望返

2、回的元素及其格式。在XL查詢中，可以將XPath轉(zhuǎn)化為一棵樹(shù)，稱為查詢樹(shù)。從初始查詢樹(shù)開(kāi)始，選擇查詢樹(shù)中的某一條邊，對(duì)該邊上相毗連的兩個(gè)結(jié)點(diǎn)做毗連，毗連的效果用一個(gè)新的結(jié)點(diǎn)表現(xiàn)，并取代原樹(shù)中的兩個(gè)結(jié)點(diǎn)。每次毗連時(shí)都市使結(jié)點(diǎn)淘汰一個(gè)，同時(shí)產(chǎn)生一個(gè)新的樹(shù)。當(dāng)樹(shù)只包羅一個(gè)結(jié)點(diǎn)時(shí)，整個(gè)求解歷程便竣事。在查詢樹(shù)中，可以將樹(shù)中的結(jié)點(diǎn)分為五種范例，別離是：根節(jié)點(diǎn)(Rt)，葉節(jié)點(diǎn)(LN)，分支節(jié)點(diǎn)(GN)，孫子節(jié)點(diǎn)(DN)，孩子節(jié)點(diǎn)(N)。此中與通常環(huán)境差異的是，孫子節(jié)點(diǎn)是指在查詢樹(shù)中與其下一個(gè)節(jié)點(diǎn)為祖孫干系的節(jié)點(diǎn)。孩子節(jié)點(diǎn)是指在查詢樹(shù)中與下一個(gè)節(jié)點(diǎn)為父子干系的節(jié)點(diǎn)。將查詢中必要返回的結(jié)點(diǎn)，界說(shuō)為返回節(jié)點(diǎn)。界

3、說(shuō)1：給定一個(gè)查詢樹(shù)QT(N，E)，及節(jié)點(diǎn)NiN，假設(shè)Ni為GN或LN或DN，那么將此節(jié)點(diǎn)稱為GLDNde。界說(shuō)2：給定一個(gè)查詢樹(shù)QT(N，E)，及QT中的一條途徑P為EiNi.Ni+nEi+nNi+n+1，假設(shè)Ni與Ni+n+1為GLDNde或根節(jié)點(diǎn)，且對(duì)付全部的節(jié)點(diǎn)Nj屬于Ni+1到Ni+n皆不為GLDNde或根節(jié)點(diǎn)，那么我們稱EiNi.Ni+nEi+nNi+n+1為一個(gè)后置途徑SuffixPath。界說(shuō)3：給定一個(gè)查詢樹(shù)，由根節(jié)點(diǎn)開(kāi)始向下拜候，假設(shè)走訪的節(jié)點(diǎn)屬于GLDNde，那么將其創(chuàng)立在片斷途徑樹(shù)中，PT(N，E)，N是節(jié)點(diǎn)的聚集，E是邊的聚集。對(duì)付每個(gè)niN都有一個(gè)TagNae，且n

4、i的范例只屬于GN或LN或DN。對(duì)付每個(gè)eiE為“/，代表節(jié)點(diǎn)與節(jié)點(diǎn)之間的相鄰干系為父子干系。稱如許的樹(shù)為片斷途徑樹(shù)。界說(shuō)4：假設(shè)A為SuffixPath的末了一個(gè)節(jié)點(diǎn)，那么XL文檔中切合SuffixPath的文件所構(gòu)成的聚集，稱之為A的PartialData，記作Ap。界說(shuō)5：在片斷途徑樹(shù)FPT(FN，F(xiàn)E)中，假設(shè)NiFN且以Ni為起始點(diǎn)的途徑P為EiNiEi+1Ni+1Ei+2Ei+nNi+n，假設(shè)Ni為葉節(jié)點(diǎn)或分支節(jié)點(diǎn)，Ni+n為最靠近Ni的根節(jié)點(diǎn)或分支節(jié)點(diǎn)，那么稱途徑P為一個(gè)片斷途徑，并以“Ni-Ni+n表現(xiàn)。圖1所表現(xiàn)的是將XQueryTree拆分成SuffixPath，即“/a、

5、“/b、“/、“/d。圖1環(huán)境1：假設(shè)我們“/b/、“/b/d、“/a/b組合文件，那么/b/的效果有(b1，1)、(b2，2)、(b3，3)共三種選擇，其次切合“/b/d的有(b1，d1)一種選擇，以是，沒(méi)有對(duì)應(yīng)文件的b2，b3會(huì)從b中刪除。/a/b有一種選擇。在此挨次下必要五次選擇毗連。末了將其組合成末了效果，顯然只有一種選擇。以是根據(jù)如上方法一共做了六次選擇毗連。環(huán)境2：假設(shè)創(chuàng)立的挨次為“/b/d、“/b/、“/a/b，根據(jù)環(huán)境1的闡發(fā)方法，得到3種選擇，末了根據(jù)“/a/b、“/b/、“/b/d的方法組合只有一種選擇。顯然通過(guò)四次選擇毗連就得到了末了效果。通過(guò)上例，可以看到差異的創(chuàng)立及組

6、合挨次對(duì)查詢效果確有影響。這正是本文所研究的內(nèi)容。本文所研究的要領(lǐng)是基于片斷途徑樹(shù)的。根本框架為：起首尋到最優(yōu)化的片斷途徑序列，然后根據(jù)PartialData創(chuàng)立切合片斷途徑布局的文檔，末了得到具有完備布局的查詢效果。本文根據(jù)文獻(xiàn)1的要領(lǐng)得到片斷途徑樹(shù)及樹(shù)中每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的PartialData。起首根據(jù)途徑樹(shù)及對(duì)應(yīng)的PartialData舉行最正確化處置懲罰。根本頭腦是：根據(jù)起始點(diǎn)和中心點(diǎn)兩種差異的范例節(jié)點(diǎn)舉行拜候。PartialData大的先拜候大概小的先拜候。算法的終極目的是輸出最正確片斷途徑序列。算法3.1funtin()輸入：帶有PartialData的片斷途徑樹(shù)PT_TREE；st

7、artNde(PT_TREE)；/從根節(jié)點(diǎn)大概葉節(jié)點(diǎn)開(kāi)始拜候set(PatatialData)；/設(shè)置拜候計(jì)謀，選擇PartialData大的先拜候或小的先拜候startNde.ark()；/將起始點(diǎn)為標(biāo)識(shí)下一個(gè)要拜候的節(jié)點(diǎn)fpList.reate()；/創(chuàng)立一個(gè)表用來(lái)存放已拜候結(jié)點(diǎn)fpSequene(ptiizatin(startNde，fpList，set)；/舉行最優(yōu)化處置懲罰輸出：fpSequene；通過(guò)算法3.1可以得到最優(yōu)化片斷途徑序列。那么此中的ptiizatin算法是怎樣實(shí)現(xiàn)的呢，我們將在算法3.2給出詳細(xì)求解歷程。在樹(shù)拜候歷程中，會(huì)有遺漏的結(jié)點(diǎn)臨時(shí)未被拜候，用單向鏈表link

8、List來(lái)存儲(chǔ)這些節(jié)點(diǎn)。鏈表中每個(gè)節(jié)點(diǎn)的內(nèi)容是兩個(gè)指向途徑樹(shù)的指針，別離為urrentGTNde、PGNde，urrentGTNde指向當(dāng)前節(jié)點(diǎn)，PGNde指向一個(gè)相鄰的范例為GN的節(jié)點(diǎn)。算法3.2ptiizatin(startNde，fpList，set)輸入：startNde，fpList，set；fpList.add(urrentNde)；/將當(dāng)前節(jié)點(diǎn)放入fpList表中，并斷定當(dāng)前節(jié)點(diǎn)的環(huán)境if(父親節(jié)點(diǎn)兒子節(jié)點(diǎn)都已拜候過(guò))if(fpList.size()0)調(diào)解fpList，將fpList放入fpSequene中；if(linkList為空)輸出fpSequene；else/將PGN

9、de放入表中，由于linkList中的節(jié)點(diǎn)是由于該節(jié)點(diǎn)而遺漏的，將PGNde/放入表中，表現(xiàn)是從該P(yáng)GNde節(jié)點(diǎn)走向linkList中的節(jié)點(diǎn)的ptiizatin(urrentGTNde，fpList，set)；if(節(jié)點(diǎn)范例為DN)探求下一節(jié)點(diǎn)，遞歸ptiizatin(nextNde，fpList，set)；繼承拜候下一節(jié)點(diǎn)nextNde；elsenextNde.set()；/設(shè)置下一節(jié)點(diǎn)拜候計(jì)謀探求鄰近當(dāng)前節(jié)點(diǎn)，且被遺漏拜候的節(jié)點(diǎn)；將臨時(shí)遺漏節(jié)點(diǎn)安排在linkList中；/linkList的元素根據(jù)PartialData舉行擺列ptiizatin(nextNde，fpList，set)；接下

10、來(lái)對(duì)得到的最優(yōu)化片斷途徑序列舉行處置懲罰，重要是對(duì)每一個(gè)節(jié)點(diǎn)的PartialData舉行組合，創(chuàng)立切合片斷途徑布局的文檔。假設(shè)有些片斷無(wú)法匹配，將其刪除。并將匹配效果存到FP_TABLE表中。創(chuàng)立片斷途徑的詳細(xì)要領(lǐng)拜見(jiàn)參考文獻(xiàn)1。下面根據(jù)FP_TABLE組合出完備的效果。在題目的提出那一節(jié)，我們清楚的看到，差異的組合效果，所必要的代價(jià)是差異的。因此，本文接納組合挨次方法為由數(shù)目小的FP_TABLE到數(shù)目大的FP_TABLE。如容許以最大程度上淘汰組合代價(jià)。因此必要將得到的FP_TABLE舉行由小到大的擺列。下面通過(guò)算法3.3探究詳細(xì)組合歷程。算法3.3輸入：片斷序列中第一個(gè)節(jié)點(diǎn)所構(gòu)成的聚集FN

11、de；/緣故原由在于這些節(jié)點(diǎn)與FP_TABLE對(duì)應(yīng)FNde.getIndex(0)；/獲得第一個(gè)節(jié)點(diǎn)fr(該節(jié)點(diǎn)的FP_TABLE中每一筆切合的片斷GT)FNde.urrentGT=GT；/保存第一筆GT記載，以便在遞歸調(diào)用時(shí)得到前次處置懲罰的記載假設(shè)必要返回效果，那么將效果放到效果表中；if(Fnde的比來(lái)的鄰節(jié)點(diǎn)為根節(jié)點(diǎn))Result=Rebine(Fnde，index，Result)；/index為節(jié)點(diǎn)編號(hào)，Result需返回的節(jié)點(diǎn)尋到一組切合的答案，將其參加到ResultTable中；/鄰近的節(jié)點(diǎn)為GNelse獲得上方鄰近的GN獲得在該節(jié)點(diǎn)的FP_TABLE中和urrentGT可以或許

12、組合的記載GTTable；對(duì)GTTable中的每一筆GT舉行遞歸處置懲罰Result=Rebine(Fnde，index，Result)；繼承探求下一節(jié)點(diǎn)，并針對(duì)FP_TABLE舉行組合；/endfrRebine算法為組合片斷途徑，算法歷程如下：算法：3.4輸入：片斷序列中第一個(gè)節(jié)點(diǎn)所構(gòu)成的聚集FNde；假設(shè)全部途徑都已處置懲罰完，那么返回處置懲罰效果；獲得下一個(gè)需處置懲罰節(jié)點(diǎn)及與該節(jié)點(diǎn)在布局上比來(lái)的GN節(jié)點(diǎn)lastNde。if(lastNde為空)Rebine(Fnde，index，Result)；/對(duì)根節(jié)點(diǎn)遞歸處置懲罰Reset(FNde.urrentGT)；if(存在GN且GN.urre

13、ntGT尚未被拜候)獲得GN節(jié)點(diǎn)FP_TABLE中和urrentGT可以或許組合的序列；針對(duì)這些記載舉行遞歸處置懲罰；if(GN存在，但urrentGT已被拜候)獲得該節(jié)點(diǎn)的FP_TABLE中和其上GN節(jié)點(diǎn)的urrentGT可以或許組合的序列；遞歸處置懲罰這些記載，并探求下一組合節(jié)點(diǎn)；小我私家盤(pán)算機(jī)作為實(shí)行的平臺(tái)，其PU為Pentiu42.40GHz，內(nèi)存為512B，接納的操縱體系為irsftinds2000，接納V+編程，對(duì)本文所接納的最正確化計(jì)謀與文獻(xiàn)1及窮舉法舉行比力。得到的實(shí)行效果是本文所接納的計(jì)謀要快于文獻(xiàn)1及窮舉法。本文探究了最優(yōu)化的組合計(jì)謀，包羅最正確化算法處置懲罰片斷途徑樹(shù)及將所得到的途徑序列舉行最優(yōu)化組合。進(jìn)步了查詢的服從，到達(dá)了查詢優(yōu)化的目的。將來(lái)可以對(duì)查詢語(yǔ)句舉行更準(zhǔn)確的闡發(fā)，可以在無(wú)文檔布局下快速尋到最正確處置懲罰計(jì)謀。2NingZhang，VarunKahlia，.Taerzsu，“ASuintPh