[發(fā)明專(zhuān)利]XPath查詢(xún)優(yōu)化方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201210411505.8
• 申請(qǐng)日: 2012-10-24
• 公開(kāi)（公告）號(hào): CN102929996A
• 公開(kāi)（公告）日: 2013-02-13
• 發(fā)明（設(shè)計(jì)）人: 李東;梁曉翀
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華南理工大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 蔡茂略

1.一種XPath查詢(xún)優(yōu)化方法，其特征在于，包括下述步驟：

S101、初始化代價(jià)估算矩陣；

S102、處理單步路徑；

S103、判斷是否存在未估算路徑，如果是，則進(jìn)入步驟S104；如果否，則進(jìn)入步驟S115；

S104、判斷路徑類(lèi)型，若判斷得到當(dāng)前路徑為長(zhǎng)路徑，則進(jìn)入步驟105，若是謂詞路徑，則進(jìn)入步驟110；

S105、判斷是否存在下一種可能的連接；對(duì)于長(zhǎng)度大于1的長(zhǎng)路徑來(lái)說(shuō)，任意的路徑Stepi/…/Stepj，都能將其看成由兩個(gè)子路徑Stepi/…/Stepk和Stepk+1/…/Stepj連接而成，其中i<=k<j，因此該路徑共有j-i種連接，k初始為i，每循環(huán)一次加1，至j-1結(jié)束，若i<=k<j時(shí)下一步進(jìn)入步驟S106，估算該路徑在當(dāng)前連接下消耗的代價(jià)；當(dāng)k=j時(shí)表示已遍歷完該路徑所有可能的連接情況，進(jìn)入步驟S109估算該路徑的結(jié)果集和結(jié)果集規(guī)模；

S106、利用文檔統(tǒng)計(jì)信息估算長(zhǎng)路徑代價(jià)；

S107、判斷是否最優(yōu)連接；即判斷上一步驟計(jì)算所得的長(zhǎng)路徑執(zhí)行代價(jià)是否小于已記錄于代價(jià)估算矩陣中的最小執(zhí)行代價(jià)cost，若為真則進(jìn)入步驟108，記錄當(dāng)前連接的信息，否則無(wú)需記錄任何信息，返回步驟S105；

S108、用最優(yōu)連接和代價(jià)更新代價(jià)估算矩陣；進(jìn)入步驟S108則表示當(dāng)前路徑在k處的分割為代價(jià)最小的連接方式，因此在代價(jià)估算矩陣中更新最小執(zhí)行代價(jià)cost和最優(yōu)連接分割點(diǎn)splitIndex，其中splitIndex=k；

S109、利用文檔統(tǒng)計(jì)信息估算結(jié)果集，更新結(jié)果集矩陣；

S110、判斷是否存在下一種可能的排列；

S111、利用文檔統(tǒng)計(jì)信息估算謂詞路徑代價(jià)；

S112、判斷是否最優(yōu)排列；判斷步驟S111計(jì)算所得的謂詞路徑執(zhí)行代價(jià)是否小于已記錄于代價(jià)估算矩陣中的最小執(zhí)行代價(jià)cost，若為真則進(jìn)入步驟S113，記錄當(dāng)前謂詞排列順序的信息，否則無(wú)需記錄任何信息，返回步驟S110；

S113、更新代價(jià)矩陣和結(jié)果集矩陣，記錄最優(yōu)排列；進(jìn)入步驟S108則表示當(dāng)前謂詞排列順序?yàn)槟壳按鷥r(jià)最小的排列方式，因此在代價(jià)估算矩陣中更新最小執(zhí)行代價(jià)cost，并記錄下當(dāng)前的謂詞排列順序，以便后面的步驟按此順序重新排列謂詞；

S114：按步驟S113記錄的謂詞排列順序來(lái)重新排列謂詞；

S115：重構(gòu)查詢(xún)計(jì)劃。

2.根據(jù)權(quán)利要求1所述的XPath查詢(xún)優(yōu)化方法，其特征在于，步驟S101中，初始化的具體步驟為：使用查詢(xún)代價(jià)矩陣作為運(yùn)行時(shí)的數(shù)據(jù)結(jié)構(gòu)，在其中保存代價(jià)指標(biāo)、連接位置和中間結(jié)果集的信息；查詢(xún)代價(jià)矩陣中的每一個(gè)單元格s[i,j],1<=i<＝j(luò)<=N，分別記錄了其對(duì)應(yīng)的一個(gè)部分路徑SP=Stepi/.../Stepj的相關(guān)信息，用一個(gè)四元組<cost,splitIndex,hidList,rsCount>來(lái)表示，其中cost表示為完成該部分路徑的查詢(xún)處理，所消耗的總代價(jià)；rsCount表示該部分路徑的選擇度，即對(duì)該部分路徑執(zhí)行查詢(xún)處理后的中間結(jié)果集規(guī)模；splitIndex記錄該部分路徑的最佳分割位置，即在該點(diǎn)將路徑表達(dá)式分成兩部分分別查詢(xún)后再對(duì)兩部分的結(jié)果集進(jìn)行連接操作能獲得最快的處理速度；hidList是完成當(dāng)前子路徑的查詢(xún)處理后得到的結(jié)果集，即層次編碼五元組列表。

3.根據(jù)權(quán)利要求2所述的XPath查詢(xún)優(yōu)化方法，其特征在于，步驟S102中，處理單步路徑具體為：對(duì)于單步路徑，不需要進(jìn)行操作可直接獲得目標(biāo)結(jié)點(diǎn)集，所以將單步路徑的代價(jià)cost為零；單步路徑無(wú)需也無(wú)法進(jìn)行連接順序的選擇，所以分割位置splitIndex設(shè)為其自身；hidList即為該標(biāo)簽名對(duì)應(yīng)的層次編碼五元組列表，rsCount即為標(biāo)簽對(duì)應(yīng)的節(jié)點(diǎn)個(gè)數(shù)，通過(guò)對(duì)hidList中的nodeCount字段求和得到。

4.根據(jù)權(quán)利要求1所述的XPath查詢(xún)優(yōu)化方法，其特征在于，步驟S105中，判斷路徑類(lèi)型的步驟是：定義謂詞路徑為只包含謂詞過(guò)濾操作符，不包含其它類(lèi)型操作符的路徑表達(dá)式，遍歷當(dāng)前處理路徑的操作符集合，如果存在除謂詞操作符以外的其它類(lèi)型的操作符，則當(dāng)前處理路徑為長(zhǎng)路徑，如果不存在，當(dāng)前處理路徑為謂詞路徑。