基于父節點的XML查詢優化算法?

宗傳霞

（煙臺南山學院，山東龍口 265713）

0 引言

XML 文檔中的關鍵詞檢索是以XML 元素為粒度來返回檢索結果的，即在返回檢索結果時，并不需要將整個文檔返回給用戶，而只需返回用戶感興趣且符合檢索條件的元素集即可，該集合可以看作是原文檔的一個片段。因此，XML文檔中的關鍵詞檢索不但可以使得檢索結果更為準確，也使得傳輸的數據量大大減小。基于父節點的XML 查詢優化算法的目的就是返回用戶在XML 文檔中的最小子樹根節點，從而查詢出對應于最小子樹根節點的最緊致片段。

在XML 查詢優化算法中，典型算法主要分為基于索引的搜索算法、基于堆棧的算法和基于掃描的算法。

基于索引的搜索算法基本思想是將XML 數據保存到B+樹結構，插入B+樹的數據形式為(key，dewey)，這相當于將XML中的數據按照關鍵詞(keyword)和關鍵詞在XML 樹中的節點Dewey碼進行排序[1]。之后，借助于B+樹結構以及Dewey 碼的基本運算（大于、小于、子孫碼、公共前綴等）計算最小子樹根節點。但是，這種算法必須修改B+樹結構來支持Dewey 碼操作，實現比較復雜。基于堆棧的算法主要是利用棧來進行存儲，操作起來相對簡單。但是，這種算法空間復雜度很高[2]。基于掃描的算法在時間復雜度和空間復雜度方面都不是很理想[3]。相對來說，在這3種算法中，基于索引的搜索算法應用比其他兩種算法廣泛。

鑒于這種情況，改進XML 信息查詢技術具有必要性和緊迫性，這是基于父節點的XML 查詢優化算法研究的主要動力。本文以如何提高其數據信息的查詢效率為目的，描述了一種既能夠在保證查全率的同時又對其查準率有所提高的基于父節點的XML 查詢優化算法。

1 查詢方案

基于父節點的XML 查詢優化算法，首先根據關鍵詞的個數分別進行標記，以便區分不同的關鍵詞。然后，根據關鍵詞的順序，依次查找關鍵詞在XML 樹葉節點中出現的次數并且進行標記。這里分兩種情況：第一，如果關鍵詞在XML 樹葉節點中出現的次數不相同，那么關鍵詞出現的最小次數就是最小子樹根節點的個數；第二，如果關鍵詞在XML 樹葉節點中出現的次數相同，那么該次數就是最小子樹根節點的個數。

其次，按照關鍵詞順序依次查找它們對應的父節點，如果父節點的標記沒有包含所有關鍵詞的標記，則繼續進行查找，直到達到第二層，或者查找完最小子樹根節點為止。這里主要分為兩種情形：第一，如果關鍵詞在XML 樹中葉節點所在層數不一致，那么向上一層查找父節點時，就一定有關鍵詞查找的父節點先到達第二層，這時候，該關鍵詞不用再去查找它的祖先節點，它需要做的是等待其他關鍵詞繼續尋找其父節點。然后，驗證自己已經標記過的節點和其他關鍵詞標記過的節點標記有沒有同時出現。如果查找的各個關鍵詞標記在同一個父節點出現，那么該節點就是最小子樹根節點，從而根據最小子樹根節點得出對應的最緊致片段；第二，如果關鍵詞在XML樹中葉節點所在層數一致，那么在向上一層查找父節點時，就僅僅需要按照關鍵詞的順序循環查找父節點并且進行標記，等出現包含所有關鍵詞標記的父節點時，即為最小子樹根節點，從而根據最小子樹根節點得出對應的最緊致片段。

此時，該關鍵詞組集合的最小子樹根節點求解完成，從而也得到了它們對應的最緊致片段。

2 算法步驟及其流程圖

下面是基于父節點的XML 查詢優化算法的算法步驟。

(1)為n個關鍵詞進行標示，標記為k1，k2，…，kn以便區分不同的關鍵詞。

(2)依據k1，k2，…，kn的順序進行循環查找父節點，并且父節點也按照關鍵詞的順序依次標記，分別為k1，k2，…，kn。

(3)查找出的父節點集合兩兩求交集。如果父節點集合交集為空，則繼續求查找出的父節點的父節點，也就是關鍵詞的祖先節點；如果父節點集合交集不為空，則記錄下來，然后再去求關鍵詞的祖先節點。當進行到第二層，或者父節點集合中任何一個集合為空集時，循環結束，計算終止。

(4)把求得父節點集合的交集組成一個集合，它就是所求的最小子樹根節點集合，進而根據所得的最小子樹根節點得出用戶所需的最緊致片段。

根據基于父節點的XML 查詢優化算法的算法步驟設計的詳細流程圖，如圖1所示。

3 實驗

為了驗證改進的效果，本文對基于索引的搜索算法、基于堆棧的算法、基于掃描的算法、基于父節點的XML 查詢優化算法進行了實驗對比和分析。

3.1 實驗結果

實驗平臺是Windows VistaTM Home Basic，Intel(R) Core(TM)2 Duo CPU T5800@2.00 GHz 2.00 GHz，內存(RAM)2.00GB，32位操作系統，160GB 硬盤。開發工具是在Microsoft Visual Studio.NET 2003（實現語言為vb.net），Microsoft SQL Server 2000環境下設計并實現的。

圖1 流程圖

INEX（Initiative for the Evaluation of XML Retrieval的縮寫）[4]是XML 信息檢索中具有代表性的文檔集，其資源的核心內容是從1995年到2000年出版的1.2萬篇期刊文章。本文選取INEX 2006上的Wikipedia XML 文集進行實驗的測試，整個文集是由八種不同語言部分組成。本文選擇以英語文集為主要的實驗對象。該實驗數據集共包含659388篇文章，約4600 MB 大小，文檔的平均大小約為7.1 M，平均深度為6.732層。

在進行的XML 查詢優化算法時，實驗數據的裝入是通過調用基于事件的XML parser 來實現的，它分析XML 文檔，實現對元素節點的編碼和元素索引記錄的插入[5-8]。表1是XML 查詢優化算法實驗對比結果。

表1 XML查詢優化算法實驗對比結果

最后，實驗得出，基于父節點的XML 查詢優化算法不論是從內存占有率、數據準備時間還是時間復雜度方面，都優于其他3種算法，是一種行之有效的算法。

3.2 實驗分析

本文提出的基于父節點的XML 查詢優化算法比基于索引的搜索算法具有更高的查準率。另外通過實驗也得出，只有用戶輸入的查詢關鍵詞大于等于五個時，這種查詢優化算法才能發揮出它的優勢。

下面是10組數據的查詢，查詢內容如表2所示。

表2 其它10組查詢內容

對實驗數據進行統計分析，虛線表示基于索引的搜索算法，實線表示基于父節點的XML 查詢優化算法。如圖2所示。

圖2 統計結果分析

4 結論

基于父節點的XML 查詢優化算法，主要是根據關鍵詞的順序依次求父節點，并且把求得的父節點進行標示，然后再根據關鍵詞的順序依次求父節點并且進行標示，持續循環，直到求得的父節點標示為所有關鍵詞的標示為止。這時，該父節點即為所求的最小子樹根節點，進而根據最小子樹根節點得出對應的最緊致片段。

通過實驗驗證，該算法在內存占有率、數據準備時間、時間復雜度方面都有一定程度地提高。與傳統的XML 查詢優化算法相比，它的查詢結果更為準確，更符合用戶的需要。

[1]王國仁，于戈，楊曉群，等.XML數據管理技術[M].北京：電子工業出版社，2007.

[2]基于堆棧的查詢算法，http：//bbs.pediy.com/archive/index.phy?t-52885.com.

[3]江騰蛟，萬常選.針對XML文檔集的關鍵詞檢索結果排序[J].軟件技術與數據庫，2007，33(2)：59-61.

[4]G.Gou，R.Chirkova.Efciently Querying LargeXml Data Repositories：ASurvey[J].IEEE Trans.Knowl.Data Eng，2007，19(10)：1381-1403.

[5]萬常選，魯遠.基于權重查詢詞的XML結構查詢擴展[J].軟件學報，2008，10(19)：2611-2619.

[6]沈劍滄，鮑培明.XML查詢方法的設計與研究[J].計算機工程，2007，21(33)：63-65.

[7]宗傳霞.基于編輯距離的XML查詢方法[J].電子測試，2011(3)：1-4.

[8]郭俊文，衡星辰，邵利平，等.一種基于XML文檔聚類的XML近似查詢算法[J].計算機工程，2006，32(15)：52-54.