[發(fā)明專利]基于粒子群優(yōu)化算法的XQuery查詢路徑優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210193940.8
• 申請(qǐng)日: 2012-06-13
• 公開(kāi)（公告）號(hào): CN102760167A
• 公開(kāi)（公告）日: 2012-10-31
• 發(fā)明（設(shè)計(jì)）人: 李浩;趙偉;鄭程光;孫偉豐;羅正海;李泉;李書淦;程仁波
• 申請(qǐng)（專利權(quán)）人: 上海方正數(shù)字出版技術(shù)有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06N3/12
• 代理公司: 上海漢聲知識(shí)產(chǎn)權(quán)代理有限公司 31236
• 代理人: 胡晶

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，特別涉及一種基于粒子群優(yōu)化算法的XQuery查詢路徑優(yōu)化方法。

背景技術(shù)

XQuery是用來(lái)從XML文檔查找和提取元素及屬性的一種語(yǔ)言，其業(yè)已被接納為W3的標(biāo)準(zhǔn)。XQuery被設(shè)計(jì)用來(lái)查詢XML文檔，但其不僅僅局限于對(duì)XML文檔的查詢，而且其還可以對(duì)任何以XML形式所呈現(xiàn)的數(shù)據(jù)，當(dāng)然也包括數(shù)據(jù)庫(kù)。XQuery之于XML，相當(dāng)于SQL之于關(guān)系型數(shù)據(jù)集。故而，XQuery被廣泛應(yīng)用于網(wǎng)絡(luò)服務(wù)中的信息提取；信息摘要的生成；將XML轉(zhuǎn)化為HTML；XML文檔的搜索等應(yīng)用場(chǎng)景下。

因此，當(dāng)需要對(duì)一XML文檔進(jìn)行查詢時(shí)，對(duì)于所給出的XQuery語(yǔ)句的選擇執(zhí)行什么樣的查詢路徑，直接影響查詢語(yǔ)句的響應(yīng)時(shí)間。現(xiàn)有技術(shù)中，對(duì)于查詢路徑的優(yōu)化一般或多或少都是基于查詢代價(jià)來(lái)完成查詢路徑的優(yōu)化。在用戶給出一條XQuery查詢語(yǔ)句時(shí)，系統(tǒng)會(huì)根據(jù)所給出的XQuery查詢語(yǔ)句，將該語(yǔ)句分解為數(shù)個(gè)不同的查詢子任務(wù)，并根據(jù)關(guān)系代數(shù)或布爾代數(shù)做一些基本的等價(jià)變化，例如利用De?Morgan定律對(duì)查詢條件進(jìn)行等價(jià)處理等。但當(dāng)執(zhí)行復(fù)雜查詢時(shí)，或者包含嵌套查詢時(shí)，現(xiàn)有技術(shù)對(duì)于此種類型的優(yōu)化則辦法不多。導(dǎo)致上述情形發(fā)生的因素包括：(1)對(duì)于XML節(jié)點(diǎn)掃描消耗過(guò)多的資源，導(dǎo)致對(duì)于查詢大文檔時(shí)，資源消耗過(guò)大，查詢時(shí)間相應(yīng)增加；(2)對(duì)于中間結(jié)果的處理不夠理想。例如在查詢語(yǔ)句中需要多次使用查詢的中間結(jié)果，而系統(tǒng)對(duì)于查詢結(jié)果要么沒(méi)有進(jìn)行緩存處理，要么進(jìn)行緩存處理時(shí)沒(méi)有對(duì)中間結(jié)果的內(nèi)容進(jìn)行處理，從而導(dǎo)致系統(tǒng)所消耗的資源在做查詢時(shí)增長(zhǎng)過(guò)快；(3)對(duì)于查詢路徑?jīng)]有進(jìn)行有效編碼和優(yōu)化。

發(fā)明內(nèi)容

本發(fā)明提供一種基于粒子群優(yōu)化算法的XQuery查詢路徑優(yōu)化方法，以解決是現(xiàn)有技術(shù)中查詢路徑消耗資源過(guò)大的問(wèn)題。

為解決上述問(wèn)題，本發(fā)明技術(shù)方案提供一種基于粒子群優(yōu)化算法的XQuery查詢路徑優(yōu)化方法，包括：

S1：讀取預(yù)查詢的XML文檔，并對(duì)所述XML文檔進(jìn)行預(yù)處理，以簡(jiǎn)化所述XML文檔；

S2：根據(jù)預(yù)處理后得到的所述XML文檔轉(zhuǎn)換XQuery查詢語(yǔ)句；

S3：根據(jù)所述轉(zhuǎn)換后得到的XQuery查詢語(yǔ)句構(gòu)造查詢代價(jià)矩陣；

S4：用粒子群優(yōu)化算法對(duì)所述查詢代價(jià)矩陣進(jìn)行計(jì)算，以得出最短的查詢代價(jià)路徑。可選地，所述步驟S1具體包括：

S11：對(duì)XML文檔的所有節(jié)點(diǎn)標(biāo)簽進(jìn)行預(yù)處理；

S12：對(duì)XML文檔中的冗余標(biāo)簽進(jìn)行處理。

可選地，所述步驟S11具體包括：

S111：尋找出所述XML文檔中所有節(jié)點(diǎn)標(biāo)簽信息，并將所述節(jié)點(diǎn)標(biāo)簽信息保存至一張節(jié)點(diǎn)數(shù)據(jù)表中，并對(duì)所述節(jié)點(diǎn)數(shù)據(jù)表中的每一項(xiàng)賦予唯一編號(hào)作為該項(xiàng)在表中的索引值；

S112：在所述節(jié)點(diǎn)數(shù)據(jù)表的建立完成后，使用各個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的索引號(hào)對(duì)所述XML文檔進(jìn)行相應(yīng)的處理，將所述節(jié)點(diǎn)在文檔中的出現(xiàn)的位置使用其對(duì)應(yīng)的節(jié)點(diǎn)索引號(hào)進(jìn)行代替。

可選地，所述步驟S12具體包括刪除所述XML文檔的所有節(jié)點(diǎn)的右標(biāo)簽。

可選地，所述步驟S2具體為：根據(jù)所述的預(yù)處理后得到的XML文檔轉(zhuǎn)換原有的XQuery查詢語(yǔ)句，也即使用所述XML文檔中的各個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)ID表示所述節(jié)點(diǎn)，從而將原XQuery語(yǔ)句進(jìn)行轉(zhuǎn)換；

可選地，所述步驟S3具體為：

S31：獲取轉(zhuǎn)換后得到的所述XQuery查詢語(yǔ)句中的節(jié)點(diǎn)編號(hào)：MAX_ID和MIN_ID，其中，所述MAX_ID、所述MIN_ID分別表示所述XQuery查詢語(yǔ)句中的節(jié)點(diǎn)編號(hào)的最大值和最小值；

S32：根據(jù)MAX_ID，MIN_ID的取值范圍建立一個(gè)(MAX_ID–MIN_ID)*(MAX_ID–MIN_ID)的查詢代價(jià)矩陣，并將所述查詢代價(jià)矩陣中的各個(gè)元素值設(shè)置為一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)所包含的節(jié)點(diǎn)數(shù)量，以表示所述兩個(gè)節(jié)點(diǎn)之間的查詢路徑的權(quán)值；

可選地，所述步驟S4具體為：

步驟S41:定義粒子群優(yōu)化算法的目標(biāo)函數(shù)為：min:f(x1,x2,…,xn);

步驟S42:隨機(jī)生成N個(gè)個(gè)體，以生成初始種群；

步驟S43:初始化N個(gè)個(gè)體的初始值，也即使用隨機(jī)數(shù)生成器對(duì)所述N個(gè)個(gè)體的初始速度及位置生成初始速度和初始位置；

步驟S44:計(jì)算所述各個(gè)個(gè)體的適應(yīng)度值；

步驟S45:若適應(yīng)度值小于給定的閾值d，則終止計(jì)算;

步驟S46:輸出最優(yōu)值，即該算法所尋找到的最優(yōu)路線，否則進(jìn)行步驟S47；