基于父節(jié)點(diǎn)的XML查詢優(yōu)化算法?

宗傳霞

（煙臺(tái)南山學(xué)院，山東龍口 265713）

0 引言

XML 文檔中的關(guān)鍵詞檢索是以XML 元素為粒度來(lái)返回檢索結(jié)果的，即在返回檢索結(jié)果時(shí)，并不需要將整個(gè)文檔返回給用戶，而只需返回用戶感興趣且符合檢索條件的元素集即可，該集合可以看作是原文檔的一個(gè)片段。因此，XML文檔中的關(guān)鍵詞檢索不但可以使得檢索結(jié)果更為準(zhǔn)確，也使得傳輸?shù)臄?shù)據(jù)量大大減小。基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法的目的就是返回用戶在XML 文檔中的最小子樹(shù)根節(jié)點(diǎn)，從而查詢出對(duì)應(yīng)于最小子樹(shù)根節(jié)點(diǎn)的最緊致片段。

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

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

鑒于這種情況，改進(jìn)XML 信息查詢技術(shù)具有必要性和緊迫性，這是基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法研究的主要?jiǎng)恿Α１疚囊匀绾翁岣咂鋽?shù)據(jù)信息的查詢效率為目的，描述了一種既能夠在保證查全率的同時(shí)又對(duì)其查準(zhǔn)率有所提高的基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法。

1 查詢方案

基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法，首先根據(jù)關(guān)鍵詞的個(gè)數(shù)分別進(jìn)行標(biāo)記，以便區(qū)分不同的關(guān)鍵詞。然后，根據(jù)關(guān)鍵詞的順序，依次查找關(guān)鍵詞在XML 樹(shù)葉節(jié)點(diǎn)中出現(xiàn)的次數(shù)并且進(jìn)行標(biāo)記。這里分兩種情況：第一，如果關(guān)鍵詞在XML 樹(shù)葉節(jié)點(diǎn)中出現(xiàn)的次數(shù)不相同，那么關(guān)鍵詞出現(xiàn)的最小次數(shù)就是最小子樹(shù)根節(jié)點(diǎn)的個(gè)數(shù)；第二，如果關(guān)鍵詞在XML 樹(shù)葉節(jié)點(diǎn)中出現(xiàn)的次數(shù)相同，那么該次數(shù)就是最小子樹(shù)根節(jié)點(diǎn)的個(gè)數(shù)。

其次，按照關(guān)鍵詞順序依次查找它們對(duì)應(yīng)的父節(jié)點(diǎn)，如果父節(jié)點(diǎn)的標(biāo)記沒(méi)有包含所有關(guān)鍵詞的標(biāo)記，則繼續(xù)進(jìn)行查找，直到達(dá)到第二層，或者查找完最小子樹(shù)根節(jié)點(diǎn)為止。這里主要分為兩種情形：第一，如果關(guān)鍵詞在XML 樹(shù)中葉節(jié)點(diǎn)所在層數(shù)不一致，那么向上一層查找父節(jié)點(diǎn)時(shí)，就一定有關(guān)鍵詞查找的父節(jié)點(diǎn)先到達(dá)第二層，這時(shí)候，該關(guān)鍵詞不用再去查找它的祖先節(jié)點(diǎn)，它需要做的是等待其他關(guān)鍵詞繼續(xù)尋找其父節(jié)點(diǎn)。然后，驗(yàn)證自己已經(jīng)標(biāo)記過(guò)的節(jié)點(diǎn)和其他關(guān)鍵詞標(biāo)記過(guò)的節(jié)點(diǎn)標(biāo)記有沒(méi)有同時(shí)出現(xiàn)。如果查找的各個(gè)關(guān)鍵詞標(biāo)記在同一個(gè)父節(jié)點(diǎn)出現(xiàn)，那么該節(jié)點(diǎn)就是最小子樹(shù)根節(jié)點(diǎn)，從而根據(jù)最小子樹(shù)根節(jié)點(diǎn)得出對(duì)應(yīng)的最緊致片段；第二，如果關(guān)鍵詞在XML樹(shù)中葉節(jié)點(diǎn)所在層數(shù)一致，那么在向上一層查找父節(jié)點(diǎn)時(shí)，就僅僅需要按照關(guān)鍵詞的順序循環(huán)查找父節(jié)點(diǎn)并且進(jìn)行標(biāo)記，等出現(xiàn)包含所有關(guān)鍵詞標(biāo)記的父節(jié)點(diǎn)時(shí)，即為最小子樹(shù)根節(jié)點(diǎn)，從而根據(jù)最小子樹(shù)根節(jié)點(diǎn)得出對(duì)應(yīng)的最緊致片段。

此時(shí)，該關(guān)鍵詞組集合的最小子樹(shù)根節(jié)點(diǎn)求解完成，從而也得到了它們對(duì)應(yīng)的最緊致片段。

2 算法步驟及其流程圖

下面是基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法的算法步驟。

(1)為n個(gè)關(guān)鍵詞進(jìn)行標(biāo)示，標(biāo)記為k1，k2，…，kn以便區(qū)分不同的關(guān)鍵詞。

(2)依據(jù)k1，k2，…，kn的順序進(jìn)行循環(huán)查找父節(jié)點(diǎn)，并且父節(jié)點(diǎn)也按照關(guān)鍵詞的順序依次標(biāo)記，分別為k1，k2，…，kn。

(3)查找出的父節(jié)點(diǎn)集合兩兩求交集。如果父節(jié)點(diǎn)集合交集為空，則繼續(xù)求查找出的父節(jié)點(diǎn)的父節(jié)點(diǎn)，也就是關(guān)鍵詞的祖先節(jié)點(diǎn)；如果父節(jié)點(diǎn)集合交集不為空，則記錄下來(lái)，然后再去求關(guān)鍵詞的祖先節(jié)點(diǎn)。當(dāng)進(jìn)行到第二層，或者父節(jié)點(diǎn)集合中任何一個(gè)集合為空集時(shí)，循環(huán)結(jié)束，計(jì)算終止。

(4)把求得父節(jié)點(diǎn)集合的交集組成一個(gè)集合，它就是所求的最小子樹(shù)根節(jié)點(diǎn)集合，進(jìn)而根據(jù)所得的最小子樹(shù)根節(jié)點(diǎn)得出用戶所需的最緊致片段。

根據(jù)基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法的算法步驟設(shè)計(jì)的詳細(xì)流程圖，如圖1所示。

3 實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)的效果，本文對(duì)基于索引的搜索算法、基于堆棧的算法、基于掃描的算法、基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法進(jìn)行了實(shí)驗(yàn)對(duì)比和分析。

3.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)平臺(tái)是Windows VistaTM Home Basic，Intel(R) Core(TM)2 Duo CPU T5800@2.00 GHz 2.00 GHz，內(nèi)存(RAM)2.00GB，32位操作系統(tǒng)，160GB 硬盤(pán)。開(kāi)發(fā)工具是在Microsoft Visual Studio.NET 2003（實(shí)現(xiàn)語(yǔ)言為vb.net），Microsoft SQL Server 2000環(huán)境下設(shè)計(jì)并實(shí)現(xiàn)的。

圖1 流程圖

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

在進(jìn)行的XML 查詢優(yōu)化算法時(shí)，實(shí)驗(yàn)數(shù)據(jù)的裝入是通過(guò)調(diào)用基于事件的XML parser 來(lái)實(shí)現(xiàn)的，它分析XML 文檔，實(shí)現(xiàn)對(duì)元素節(jié)點(diǎn)的編碼和元素索引記錄的插入[5-8]。表1是XML 查詢優(yōu)化算法實(shí)驗(yàn)對(duì)比結(jié)果。

表1 XML查詢優(yōu)化算法實(shí)驗(yàn)對(duì)比結(jié)果

最后，實(shí)驗(yàn)得出，基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法不論是從內(nèi)存占有率、數(shù)據(jù)準(zhǔn)備時(shí)間還是時(shí)間復(fù)雜度方面，都優(yōu)于其他3種算法，是一種行之有效的算法。

3.2 實(shí)驗(yàn)分析

本文提出的基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法比基于索引的搜索算法具有更高的查準(zhǔn)率。另外通過(guò)實(shí)驗(yàn)也得出，只有用戶輸入的查詢關(guān)鍵詞大于等于五個(gè)時(shí)，這種查詢優(yōu)化算法才能發(fā)揮出它的優(yōu)勢(shì)。

下面是10組數(shù)據(jù)的查詢，查詢內(nèi)容如表2所示。

表2 其它10組查詢內(nèi)容

對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，虛線表示基于索引的搜索算法，實(shí)線表示基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法。如圖2所示。

圖2 統(tǒng)計(jì)結(jié)果分析

4 結(jié)論

基于父節(jié)點(diǎn)的XML 查詢優(yōu)化算法，主要是根據(jù)關(guān)鍵詞的順序依次求父節(jié)點(diǎn)，并且把求得的父節(jié)點(diǎn)進(jìn)行標(biāo)示，然后再根據(jù)關(guān)鍵詞的順序依次求父節(jié)點(diǎn)并且進(jìn)行標(biāo)示，持續(xù)循環(huán)，直到求得的父節(jié)點(diǎn)標(biāo)示為所有關(guān)鍵詞的標(biāo)示為止。這時(shí)，該父節(jié)點(diǎn)即為所求的最小子樹(shù)根節(jié)點(diǎn)，進(jìn)而根據(jù)最小子樹(shù)根節(jié)點(diǎn)得出對(duì)應(yīng)的最緊致片段。

通過(guò)實(shí)驗(yàn)驗(yàn)證，該算法在內(nèi)存占有率、數(shù)據(jù)準(zhǔn)備時(shí)間、時(shí)間復(fù)雜度方面都有一定程度地提高。與傳統(tǒng)的XML 查詢優(yōu)化算法相比，它的查詢結(jié)果更為準(zhǔn)確，更符合用戶的需要。

[1]王國(guó)仁，于戈，楊曉群，等.XML數(shù)據(jù)管理技術(shù)[M].北京：電子工業(yè)出版社，2007.

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

[3]江騰蛟，萬(wàn)常選.針對(duì)XML文檔集的關(guān)鍵詞檢索結(jié)果排序[J].軟件技術(shù)與數(shù)據(jù)庫(kù)，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]萬(wàn)常選，魯遠(yuǎn).基于權(quán)重查詢?cè)~的XML結(jié)構(gòu)查詢擴(kuò)展[J].軟件學(xué)報(bào)，2008，10(19)：2611-2619.

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

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

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