[發明專利]基于粒子群優化算法的XQuery查詢路徑優化方法

有效

• 申請號: 201210193940.8
• 申請日: 2012-06-13
• 公開（公告）號: CN102760167A
• 公開（公告）日: 2012-10-31
• 發明（設計）人: 李浩;趙偉;鄭程光;孫偉豐;羅正海;李泉;李書淦;程仁波
• 申請（專利權）人: 上海方正數字出版技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 上海漢聲知識產權代理有限公司 31236
• 代理人: 胡晶

1.一種基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，包括：

S1：讀取預查詢的XML文檔，并對所述XML文檔進行預處理，以簡化所述XML文檔；

S2：根據預處理后得到的所述XML文檔轉換XQuery查詢語句；

S3：根據所述轉換后得到的XQuery查詢語句構造查詢代價矩陣；

S4：用粒子群優化算法對所述查詢代價矩陣進行計算，以得出最短的查詢代價路徑。

2.如權利要求1所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S1具體包括：對XML文檔的所有節點標簽進行預處理。

3.如權利要求1所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S1具體包括：對XML文檔中的冗余標簽進行處理。

4.如權利要求2所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S11具體包括：

S111：尋找出所述XML文檔中所有節點標簽信息，并將所述節點標簽信息保存至一張節點數據表中，并對所述節點數據表中的每一項賦予唯一編號作為該項在表中的索引值；

S112：在所述節點數據表的建立完成后，將所述節點在文檔中的出現的位置使用其對應的節點索引號進行代替。

5.如權利要求3所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S12具體包括刪除所述XML文檔的所有節點的右標簽。

6.如權利要求1所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S2具體為：根據所述的預處理后得到的XML文檔轉換?原有的XQuery查詢語句，也即使用所述XML文檔中的各個節點的節點ID表示所述節點，從而將原XQuery語句進行轉換。

7.如權利要求1所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S3具體為：

S31：獲取轉換后得到的所述XQuery查詢語句中的節點編號：MAX_ID和MIN_ID，其中，所述MAX_ID、所述MIN_ID分別表示所述XQuery查詢語句中的節點編號的最大值和最小值；

S32：根據MAX_ID，MIN_ID的取值范圍建立一個(MAX_ID-MIN_ID)*(MAX_ID-MIN_ID)的查詢代價矩陣，并將所述查詢代價矩陣中的各個元素值設置為一個節點到另一個節點所包含的節點數量，以表示所述兩個節點之間的查詢路徑的權值。

8.如權利要求1所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，所述步驟S4具體為：

步驟S41：定義粒子群優化算法的目標函數為：min：f(x1，x2，...，xn)；

步驟S42：隨機生成N個個體，以生成初始種群；

步驟S43：初始化N個個體的初始值，也即使用隨機數生成器對所述N個個體的初始速度及位置生成初始速度和初始位置；

步驟S44：計算所述各個個體的適應度值；

步驟S45：若適應度值小于給定的閾值d，則終止計算；

步驟S46：輸出最優值，即該算法所尋找到的最優路線，否則進行步驟S47；

步驟S47：對粒子個體進行更新。

其中，其中，f(x1，x2，...，xn)為x1，x2，...，xn路徑上的查詢代價，min為去所述目標函數的最小值；?

d為用戶給點的閾值，由用戶進行指定；

適應度值，用以表明個體的優秀度，其越小則表明所述個體越優秀。

9.如權利要求7所述的基于粒子群優化算法的XQuery查詢路徑優化方法，其特征在于，在所述步驟S47中，具體按照下述的公式更新所述粒子個體：

v_i^k+1＝w?_vi^k+c₁?rand(?)(l_i^k-x_i^k)+c₂Rand()(g^k-x_i^k)?(1)

x_i^k+1＝x_i^k+v_i^k+1????(2)

其中，v_i^k+1中的x_i^k+1等參數為所述的各個種群的所在搜索空間中第k+1次迭代后的位置和速度；g^k為在搜索空間中的優值，l_i^k為第i個粒子在第k次迭代過程中所經歷的最優位置；w為算法慣性權值，此數值為經驗值，通常在[1，1.3]；c₁、c₂為加速常數，通常取值為2；rand()、Rand()為兩個在[0，1]范圍內變化的均勻分布函數。?