陳子陽(yáng)，王璿，湯顯

（1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2. 河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3. 燕山大學(xué) 經(jīng)濟(jì)與管理學(xué)院，河北 秦皇島 066004）

1 引言

隨著XML（extensible markup language，可擴(kuò)展標(biāo)記語(yǔ)言）應(yīng)用領(lǐng)域的不斷擴(kuò)展，以XML格式表示和存儲(chǔ)的數(shù)據(jù)量不斷增大。作為一種簡(jiǎn)單易用的信息檢索機(jī)制，基于XML數(shù)據(jù)的關(guān)鍵字檢索技術(shù)得到了研究者的廣泛關(guān)注[1～16]，其中的核心問(wèn)題之一是如何高效返回滿足特定語(yǔ)義的查詢結(jié)果[3,5～11]。

通常情況下，把一個(gè)XML文檔看成一棵帶有節(jié)點(diǎn)標(biāo)注信息的文檔樹(shù)T。給定一個(gè)關(guān)鍵字查詢Q，每個(gè)查詢結(jié)果tv為T中滿足查詢條件的結(jié)果子樹(shù)，tv包含Q中的所有關(guān)鍵字且tv的根節(jié)點(diǎn)v滿足特定語(yǔ)義如 SLCA[6～10]，ELCA[3，10～11]等?，F(xiàn)有的子樹(shù)構(gòu)建方法[12～14]涉及3個(gè)步驟。步驟1：遍歷倒排表中所有節(jié)點(diǎn)，求解相應(yīng)的SLCA/ELCA節(jié)點(diǎn)集。步驟2：再次遍歷倒排表，求得與每個(gè) SLCA/ELCA節(jié)點(diǎn)v相關(guān)的關(guān)鍵字節(jié)點(diǎn)集Rv。步驟3：對(duì)于每一個(gè)Rv，構(gòu)建滿足特定約束條件的結(jié)果子樹(shù)[12～14]。目前，XML關(guān)鍵字查詢處理的研究主要集中在如何提高步驟1的處理效率[3,5～11]，實(shí)際上，步驟2和步驟3是影響系統(tǒng)整體性能的關(guān)鍵因素。

以 MaxMatch算法[12]為例，在582 MB的XMark注1http://monetdb.cwi.nl/xml。數(shù)據(jù)集上運(yùn)行96個(gè)查詢，這些查詢依據(jù)其結(jié)果選擇率注2選擇率定義為結(jié)果個(gè)數(shù)和最短倒排表的比值。分成6組。圖1給出基于不同算法[7～9]求解SLCA時(shí)，步驟1耗費(fèi)時(shí)間占總時(shí)間的百分比。圖2給出步驟2和步驟3所耗時(shí)間的比例關(guān)系。根據(jù)圖1和圖2，有如下觀察結(jié)果。

圖1 步驟1耗費(fèi)時(shí)間(t1)占總時(shí)間(t1+t2+t3)的百分比

圖2 步驟2和步驟3所耗時(shí)間的比例關(guān)系

觀察 1：相對(duì)于總時(shí)間(t1+t2+t3)而言，步驟1所耗時(shí)間(t1)幾乎可以忽略不計(jì)(小于10%)。

觀察2：當(dāng)結(jié)果選擇率較低時(shí)，步驟3耗費(fèi)時(shí)間(t3)較多，隨著結(jié)果選擇率的增加，步驟2耗費(fèi)時(shí)間(t2)所占比重逐漸增加。

通過(guò)上述的2個(gè)觀察不難發(fā)現(xiàn)，無(wú)論步驟1采用何種算法，系統(tǒng)整體性能始終受限于步驟2和步驟3。本文重點(diǎn)研究基于ELCA語(yǔ)義如何提高步驟2的處理效率。原因有2個(gè)方面：1)已有研究[17]表明，50%的關(guān)鍵字查詢是探索式查詢，即用戶不知其具體查詢目的。和SLCA相比，求解ELCA能夠返回更多有意義的結(jié)果[6,11,15]，有助于用戶發(fā)現(xiàn)所需信息。2)已有方法[13]的步驟2不能正確求解與每個(gè)ELCA節(jié)點(diǎn)相關(guān)的關(guān)鍵字節(jié)點(diǎn)集，導(dǎo)致結(jié)果子樹(shù)可能包含無(wú)用信息或丟失有用信息。當(dāng)然，本文方法適用于SLCA語(yǔ)義。

圖3表示XML文檔D對(duì)應(yīng)的文檔樹(shù)T。假設(shè)要從T中查找Yanshan大學(xué)的Tom在Computer期刊上發(fā)表的有關(guān)XML的文章，可以使用關(guān)鍵字查詢Q=｛Yanshan，Tom，Computer，XML｝來(lái)完成該查詢?nèi)蝿?wù)。根據(jù)ELCA語(yǔ)義，滿足條件的子樹(shù)根節(jié)點(diǎn)為2和7。在判斷節(jié)點(diǎn)2是否為ELCA節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)6、18、20、21是被排除在外的，即對(duì)節(jié)點(diǎn)2來(lái)說(shuō)，節(jié)點(diǎn)6、18、20、21是無(wú)關(guān)節(jié)點(diǎn)，因此2的相關(guān)關(guān)鍵字節(jié)點(diǎn)集為R2={3，4，22，23}。然而文獻(xiàn)[13]得到節(jié)點(diǎn)2的相關(guān)節(jié)點(diǎn)集為R2={3，4，22，23，6，18，20，21}。如果用戶想要得到匹配子樹(shù)[14]，則用 R2={3，4，22，23，6，18，20，21}構(gòu)建以節(jié)點(diǎn) 2為根的子樹(shù)時(shí)，將包含無(wú)用信息(節(jié)點(diǎn) 5，6，16，18，19，20，21)，且丟失有用信息（節(jié)點(diǎn) 4和 23）。

本文的主要貢獻(xiàn)如下。

1)提出相關(guān)關(guān)鍵字節(jié)點(diǎn)（RKN，relevant keyword node）的形式化定義。

3)針對(duì) RKN-Base算法不能避免處理無(wú)用節(jié)點(diǎn)的問(wèn)題，提出優(yōu)化算法RKN-Optimized。該算法基于每個(gè)ELCA節(jié)點(diǎn)求其相關(guān)關(guān)鍵字節(jié)點(diǎn)，可以避免訪問(wèn)無(wú)用節(jié)點(diǎn)，將時(shí)間復(fù)雜度降為O(d m| E LCASet|·log|Lm|)，其中，Lm為最長(zhǎng)倒排表。

圖3 XML文檔D對(duì)應(yīng)的文檔樹(shù)T(每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是其ID編碼，該編碼是按照文檔順序排序的)

4)通過(guò)實(shí)驗(yàn)對(duì)算法的性能進(jìn)行了驗(yàn)證和分析。

2 背景知識(shí)及相關(guān)工作

2.1 數(shù)據(jù)模型

本文用帶有節(jié)點(diǎn)標(biāo)注信息的樹(shù)表示一個(gè) XML文檔，其中節(jié)點(diǎn)表示元素或者屬性，邊表示節(jié)點(diǎn)間的直接嵌套關(guān)系。給定查詢Q，若節(jié)點(diǎn)v的標(biāo)簽、屬性或者v的文本包含Q中的關(guān)鍵字k，則稱v直接包含k，v為關(guān)鍵字節(jié)點(diǎn)。

為了加速查詢處理，通常需要給XML文檔樹(shù)中的每個(gè)節(jié)點(diǎn)v指定一個(gè)可以唯一標(biāo)識(shí)的編碼，用于確定節(jié)點(diǎn)間的位置關(guān)系，已有方法通常使用Dewey[16]編碼來(lái)標(biāo)識(shí)節(jié)點(diǎn)。給定節(jié)點(diǎn) v，Dewey編碼由其父親節(jié)點(diǎn)的 Dewey編碼和其本身在兄弟節(jié)點(diǎn)中的順序值組成。如圖3所示，給每個(gè)節(jié)點(diǎn)一個(gè)ID值，該值等于以先序遍歷方式訪問(wèn)D時(shí)該節(jié)點(diǎn)的訪問(wèn)次序。相應(yīng)地，圖3中每個(gè)節(jié)點(diǎn)v的Dewey編碼由根節(jié)點(diǎn)到v的路徑上所有節(jié)點(diǎn)的ID構(gòu)成，稱這種由節(jié)點(diǎn)ID構(gòu)成的Dewey編碼為IDDewey編碼。

后續(xù)討論中，除非有歧義，本文不對(duì)一個(gè)節(jié)點(diǎn)的ID值及其編碼進(jìn)行區(qū)分。例如，圖4中的節(jié)點(diǎn)9，即為節(jié)點(diǎn) 1，2，5，7，9。對(duì)于給定的2個(gè)節(jié)點(diǎn) u和v，其位置關(guān)系包括：文檔順序(?d)，相等關(guān)系(=)，祖先后代關(guān)系(?a). u?dv表示在文檔中，u位于v的前面，即節(jié)點(diǎn)u的ID值小于節(jié)點(diǎn)v的ID值，稱u小于v，反之稱u大于v。u?av表示u是v的祖先節(jié)點(diǎn)。如果u和v表示同一個(gè)節(jié)點(diǎn)，則u=v，并且同時(shí)成立。

2.2 查詢語(yǔ)義及符號(hào)

給定查詢Q={k1，k2，…，km}，XML文檔D及ki的倒排表Li，Li中的編碼按照文檔順序升序有序。圖3中查詢Q={Yanshan，Tom，Computer，XML}的倒排表如圖4所示，圖4中的Pos表示倒排表中每個(gè)編碼的下標(biāo)位置。假設(shè)lca (v1，v2，…，vm)表示節(jié)點(diǎn) v1，v2，…，vm的最低公共祖先(LCA,lowest common ancestor)，則 Q在D上的 LCA集合定義為L(zhǎng)CASet=LCA(Q)={v| v=lca(v1,v2,…,vm),vi∈Li(1≤ i≤m)}。例如圖3中滿足Q={Yanshan，Tom，Computer，XML}的LCA節(jié)點(diǎn)為1，2，5，7。

圖4 查詢關(guān)鍵字“Yanshan”(L1)，“Tom”(L2)，“Computer”(L3)，“XML”(L4)的倒排表

給定LCA節(jié)點(diǎn)v，若去掉以v的后代LCA節(jié)點(diǎn)為根的子樹(shù)后，以v為根的子樹(shù)仍然包含所有的關(guān)鍵字，則稱v為ELCA節(jié)點(diǎn)。其形式化定義為ELCASet=ELCA(Q)={v|?v1∈L1,…,vm∈Lm(v=lca(v1,v2,…,vm)∧?i∈[1,m],，其中child(v,vi)指從節(jié)點(diǎn)v到節(jié)點(diǎn)vi路徑上v的孩子節(jié)點(diǎn)。例如圖3中滿足Q={Yanshan,Tom,Computer,XML}的ELCA節(jié)點(diǎn)為2和7。

給定節(jié)點(diǎn)u和v，若u和v具有祖先后代關(guān)系，則函數(shù)desc(u,v)返回二者中的后代節(jié)點(diǎn)；若任一節(jié)點(diǎn)為空，則返回非空節(jié)點(diǎn)；若二者均空，則返回空值。假設(shè)S是有序節(jié)點(diǎn)集（按文檔順序升序有序），則lm(u，S)(rm(u，S))返回S中比u小（大）的最大（?。┕?jié)點(diǎn)；若不存在滿足條件的節(jié)點(diǎn)，則返回空值。

2.3 相關(guān)工作

現(xiàn)有方法構(gòu)建的結(jié)果子樹(shù)主要分為3類：1）受限結(jié)果子樹(shù)[12]；2）完全子樹(shù)[2,8]；3）路徑子樹(shù)[15]。其中完全子樹(shù)指以滿足特定語(yǔ)義節(jié)點(diǎn)v為根且未經(jīng)修剪的原始子樹(shù)；路徑子樹(shù)是指以v為根且由v到全部關(guān)鍵字節(jié)點(diǎn)的路徑組成的子樹(shù)；受限子樹(shù)是指以v為根且滿足相關(guān)特殊刪減條件的子樹(shù)。目前研究較多集中于受限結(jié)果子樹(shù)，代表性的算法有MaxMatch[12]、MergeMatching[14]以及 RTF[13]。

MaxMatch與MergeMatching算法只針對(duì)SLCA語(yǔ)義求解相關(guān)關(guān)鍵字節(jié)點(diǎn)并構(gòu)建結(jié)果子樹(shù)，不能適用于ELCA語(yǔ)義。RTF算法雖然基于ELCA語(yǔ)義，但是不能正確求解相關(guān)關(guān)鍵字節(jié)點(diǎn)，導(dǎo)致其結(jié)果子樹(shù)可能包含無(wú)用信息或者丟失有用信息。本文所提算法既能適用于 SLCA語(yǔ)義也能適用于 ELCA語(yǔ)義，并且能夠正確、高效求解相關(guān)關(guān)鍵字節(jié)點(diǎn)。

3 RKN及其性質(zhì)

針對(duì)已有方法[13]不能正確求解基于 ELCA語(yǔ)義的相關(guān)關(guān)鍵字節(jié)點(diǎn)集問(wèn)題，為了進(jìn)一步規(guī)范相關(guān)關(guān)鍵字節(jié)點(diǎn)，本文提出了相關(guān)關(guān)鍵字節(jié)點(diǎn)的形式化定義。

定義1 相關(guān)關(guān)鍵字節(jié)點(diǎn)：對(duì)于給定的查詢Q，假設(shè)v為Q的ELCA節(jié)點(diǎn)，若關(guān)鍵字節(jié)點(diǎn)u滿足以下條件：1)u不是LCA節(jié)點(diǎn)且u是v的后代節(jié)點(diǎn)；2)v到u的路徑上不存在其他LCA節(jié)點(diǎn)，則稱u為v的相關(guān)關(guān)鍵字節(jié)點(diǎn)。v的所有相關(guān)關(guān)鍵字節(jié)點(diǎn)組成的集合稱為v的相關(guān)關(guān)鍵字節(jié)點(diǎn)集(RKNS,relevant keyword node set)Rv。

例如，給定圖3中查詢Q，ELCASet={2,7}。依據(jù)定義1，節(jié)點(diǎn)4為節(jié)點(diǎn)2的包含關(guān)鍵字“XML”的后代節(jié)點(diǎn)，且從2到4的路徑上不存在LCA節(jié)點(diǎn)，故4是2的RKN。雖然節(jié)點(diǎn)6也為節(jié)點(diǎn)2的包含關(guān)鍵字“XML”的后代節(jié)點(diǎn)，但是從2到6的路徑上存在LCA節(jié)點(diǎn)5，根據(jù)定義1，節(jié)點(diǎn)6不是節(jié)點(diǎn)2的RKN。以此類推，節(jié)點(diǎn)2的RKNS為R2={3,4,22,23}，節(jié)點(diǎn)7的RKNS為R7={8,9,11,12,14}。

依據(jù) RKN的定義可知，若要判斷一個(gè)節(jié)點(diǎn) u是否為節(jié)點(diǎn)v的RKN，則必須保證從v到u的路徑上不存在LCA節(jié)點(diǎn)。針對(duì)這個(gè)重要的條件，提出了最近LCA(CLCA，closest LCA)的概念。

定義2 最近 LCA：給定關(guān)鍵字節(jié)點(diǎn) u，ul=lm(u，ELCASet)(ur=rm(u，ELCASet))表示節(jié)點(diǎn)u在ELCASet中的左(右)匹配節(jié)點(diǎn)，為u與ul(ur)的 LCA節(jié)點(diǎn)，則 u的 CLCA節(jié)點(diǎn) c定義為c=

直觀上看，節(jié)點(diǎn)u的CLCA節(jié)點(diǎn)c是給定查詢Q的LCA節(jié)點(diǎn)，且從c到u的路徑上不存在其他LCA節(jié)點(diǎn)，即c為距離u最近的祖先LCA節(jié)點(diǎn)。以圖3中查詢Q為例，ELCASet=｛2，7｝，關(guān)鍵字節(jié)點(diǎn)6在ELCASet中的左匹配為節(jié)點(diǎn)2，右匹配為節(jié)點(diǎn)7，其為2，為5，故其CLCA節(jié)點(diǎn)為5。同理，關(guān)鍵字節(jié)點(diǎn)18在ELCASet中的左匹配為節(jié)點(diǎn)7，右匹配為空，其為5，為空，故其CLC A節(jié)點(diǎn)為5。基于定義2，用定理1來(lái)判斷給定關(guān)鍵字節(jié)點(diǎn)是否為某個(gè)ELCA節(jié)點(diǎn)的RKN。

定理1 設(shè)c為給定關(guān)鍵字節(jié)點(diǎn)u的CLCA節(jié)點(diǎn)，若c為ELCA節(jié)點(diǎn)，則u是c的RKN。

例如，關(guān)鍵字節(jié)點(diǎn)6的CLCA為5，但5不是ELCA節(jié)點(diǎn)，故6不是任一ELCA節(jié)點(diǎn)的RKN。又如，節(jié)點(diǎn)11的CLCA節(jié)點(diǎn)為7，且7是ELCA節(jié)點(diǎn)，故11是7的RKN。

4 RKN-Base算法

4.1 RKNS的表示

對(duì)于給定的查詢Q={k1,k2,…,km}，通常用集合Rv={u1,u2,…,un}表示并存儲(chǔ)節(jié)點(diǎn)v的全部RKN節(jié)點(diǎn)編碼。顯然，RKN節(jié)點(diǎn)編碼已經(jīng)存在于倒排表中，采用Rv={u1,u2,…,un}表示并存儲(chǔ)會(huì)產(chǎn)生節(jié)點(diǎn)編碼重復(fù)存儲(chǔ)問(wèn)題，造成內(nèi)存空間的極大浪費(fèi)。由于 v的 RKNS中許多節(jié)點(diǎn)都是連續(xù)分布在倒排表上，因此將v的RKN節(jié)點(diǎn)通過(guò)其在倒排表Li中的下標(biāo)位置表示：RvLi={[s1,e1],… [sj,ej]}(j≤n)，其中，s表示一組連續(xù)RKN節(jié)點(diǎn)在倒排表上的起始位置，e表示一組連續(xù)RKN節(jié)點(diǎn)在倒排表上的結(jié)束位置。

例如R7L4={[3,4]}，ELCA節(jié)點(diǎn)7在L4(如圖4所示)上第一個(gè)RKN的位置為3，最后一個(gè)RKN的位置為4。即通過(guò)[3,4]可知節(jié)點(diǎn)7的RKN的編碼是1,2,5,7,10,11和1,2,5,7,13,14。

4.2 算法描述

假設(shè)每個(gè)倒排表Li都有一個(gè)關(guān)聯(lián)的指針Ci，Ci指向Li中的某個(gè)節(jié)點(diǎn)。后續(xù)描述中，在不引起歧義的情況下，Ci可用于指代其所指節(jié)點(diǎn)。函數(shù)advance(Ci)的作用是讓Ci指向下一個(gè)節(jié)點(diǎn)。

算法1 getRKNS-B(ELCASet)

算法1中，第1行對(duì)ELCASet中所有節(jié)點(diǎn)按照文檔順序排序。假設(shè)查詢Q有m個(gè)關(guān)鍵字，在每次的循環(huán)過(guò)程中（第2）～7）行），算法1先從C1到Cm中選擇最小節(jié)點(diǎn)Ci（第3）行），然后在第4）行得到Ci的CLCA節(jié)點(diǎn)c，如果c是ELCA節(jié)點(diǎn)，那么根據(jù)定理1，Ci是c的RKN，更新Rc. Li（第5）行）。第6行讓Ci指向下一個(gè)節(jié)點(diǎn)。

例1 給定圖 3中查詢 Q=｛Yanshan,Tom,Computer,XML｝，ELCASet={2,7}，根據(jù)算法1，由圖4倒排表可知其關(guān)鍵字節(jié)點(diǎn)處理順序?yàn)椋?,4,6,8,9,11,12,14,18,20,21,22,23,31。首先處理節(jié)點(diǎn)3，其CLCA節(jié)點(diǎn)為2，因?yàn)?為ELCA節(jié)點(diǎn)，則節(jié)點(diǎn)3是2的RKN，于是得到R2L2={[1,1]}(1,2,3節(jié)點(diǎn)屬于L2)。其次，處理節(jié)點(diǎn)4，其CLCA節(jié)點(diǎn)為2，則節(jié)點(diǎn)4是2的RKN，于是有R2L4={[1,1]}。再次，處理節(jié)點(diǎn)6，其CLCA節(jié)點(diǎn)為5，由于5不是ELCA節(jié)點(diǎn)，故節(jié)點(diǎn)6不是任一ELCA節(jié)點(diǎn)的RKN，直接略過(guò)。后續(xù)的處理過(guò)程與前述相似，在處理完14個(gè)關(guān)鍵字節(jié)點(diǎn)后，ELCA節(jié)點(diǎn)2的RKNS為：R2L1={[3,3]}，R2L2={[1,1]，[3,3]}，R2L3={[3,3]}，R2L4={[1,1]}; ELCA節(jié)點(diǎn) 7的 RKNS 為:R7L1={[1,1]}，R7L2={[2,2]}，R7L3={[1,1]}，R7L4={[3,4]}。

4.3 算法分析

5 RKN-Optimized算法

5.1 主要思想

不同于算法 1遍歷處理倒排表上的每一個(gè)節(jié)點(diǎn)，本文設(shè)計(jì)了一種優(yōu)化算法，通過(guò)遍歷處理每一個(gè)ELCA節(jié)點(diǎn)，利用ELCA節(jié)點(diǎn)去相應(yīng)的倒排表查找其RKNS來(lái)提高算法效率。算法的主要思想為：對(duì)于每一個(gè)ELCA節(jié)點(diǎn)v，首先計(jì)算其后代節(jié)點(diǎn)在每個(gè)倒排表上的區(qū)間范圍，用vLi=[s,e ]表示。其次尋找v的每個(gè)后代LCA節(jié)點(diǎn)u，并計(jì)算u的后代節(jié)點(diǎn)在每個(gè)倒排表上的區(qū)間范圍，以u(píng).Li=[s,e]表示。最后，依據(jù)RKN定義，vLi減去uLi即為節(jié)點(diǎn)v在第i個(gè)倒排表上RKNS的區(qū)間范圍。

5.2 算法描述

算法 2采用棧 S存儲(chǔ)每個(gè) ELCA節(jié)點(diǎn)的IDDewey編碼中的數(shù)字，這更加容易發(fā)現(xiàn)ELCA后代節(jié)點(diǎn)中的LCA節(jié)點(diǎn)。如圖5(a)所示，當(dāng)棧中存儲(chǔ)節(jié)點(diǎn)1,2,5,7的編碼時(shí)，節(jié)點(diǎn)5即為ELCA節(jié)點(diǎn)2的后代LCA節(jié)點(diǎn)。算法2首先將所有ELCA節(jié)點(diǎn)按文檔順序排序（第1)行），然后依次處理每一個(gè)ELCA節(jié)點(diǎn)（第2)～26)行）。具體來(lái)說(shuō)，對(duì)于待入棧的ELCA節(jié)點(diǎn)v，將棧S中不是v祖先的節(jié)點(diǎn)全部出棧（第3)～6)行），對(duì)于每一個(gè)出棧的節(jié)點(diǎn)u，若u是ELCA節(jié)點(diǎn)，則直接得到其RKNS（第5)行）。然后，將v尚未入棧的祖先節(jié)點(diǎn)依次入棧（第 7)～25)行）。入棧過(guò)程中，對(duì)于v的每個(gè)祖先節(jié)點(diǎn)u(u≠v)，則首先將u標(biāo)記為非ELCA節(jié)點(diǎn)（第9)行），然后檢測(cè)當(dāng)前棧頂元素top(S)是否為ELCA節(jié)點(diǎn)，如果top(S)是ELCA節(jié)點(diǎn)（第10)行將返回TRUE），則在第11)行調(diào)用locateRange得到u的后代節(jié)點(diǎn)在各個(gè)倒排表中的范圍uLi，在第13)行將uLi從top(S)Li中去除。當(dāng)v的所有祖先節(jié)點(diǎn)入棧后，在第17)～22)行處理v。如果top(S)為ELCA（第17)行），則將u標(biāo)記為ELCA節(jié)點(diǎn)（算法 2第 17)～22)行 u=v），然后調(diào)用locateRange求出節(jié)點(diǎn)u的后代節(jié)點(diǎn)在各個(gè)倒排表中的范圍uLi（第18)行），然后將u的RKNS從top(S)的RKNS中移除（第19)～21)行）。在24)行將u入棧。最后，在處理完所有的ELCA節(jié)點(diǎn)后，將棧中剩余節(jié)點(diǎn)全部出棧，求出棧中ELCA節(jié)點(diǎn)相應(yīng)的RKNS（27)～30)行）。

算法2 getRKNS-O(ELCASet)

例 2 給定圖 3中查詢 Q=｛Yanshan,Tom,Computer,XML｝及其ELCASet={2,7}，算法2首先處理節(jié)點(diǎn) 2，將編碼 1.2直接入棧并初始化，如圖5(b)所示。其次處理節(jié)點(diǎn)7，因?yàn)闂ｍ敼?jié)點(diǎn)2為ELCA節(jié)點(diǎn)，5為L(zhǎng)CA節(jié)點(diǎn)，故需求出節(jié)點(diǎn)5的后代節(jié)點(diǎn)在倒排表中的范圍并將節(jié)點(diǎn)5入棧。入棧的同時(shí)，將棧頂節(jié)點(diǎn)2的后代范圍減去節(jié)點(diǎn)5的后代節(jié)點(diǎn)范圍，如圖5(c)所示。然后將節(jié)點(diǎn)7入棧，求出其后代節(jié)點(diǎn)范圍。由于此時(shí)ELCASet中再無(wú)其他節(jié)點(diǎn)，故ELCA節(jié)點(diǎn)處理完畢，如圖5(d)所示。最后將棧中節(jié)點(diǎn)全部出棧，最終得到ELCA節(jié)點(diǎn)2和7的RKNS。

5.3 算法分析

直觀上看，算法2依次處理ELCASet中每一個(gè)ELCA節(jié)點(diǎn)，從而得到其RKNS。由于每一個(gè)ELCA節(jié)點(diǎn)最多調(diào)用2次locateRange函數(shù)，而locateRange函數(shù)的代價(jià)為O(d m log|Lm|)，因此算法 2的時(shí)間復(fù)雜度為O(| E LCASet| d m log|Lm|)。顯然，和算法1相比，算法2可以避免處理無(wú)用節(jié)點(diǎn)。

由于不同SLCA節(jié)點(diǎn)之間沒(méi)有祖先后代關(guān)系，其 RKN集合的求解非常簡(jiǎn)單，只需要順序訪問(wèn)每個(gè)SLCA節(jié)點(diǎn)，在倒排表上調(diào)用locateRange函數(shù)，即可求出該SLCA節(jié)點(diǎn)的RKN區(qū)間范圍，具體過(guò)程不再贅述。

圖5 例2的運(yùn)行圖

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

6.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)所用機(jī)器的基本配置為AMD AthonⅡX2270 Professor 3.4 GHz CPU，2 GB內(nèi)存，500 GB硬盤，操作系統(tǒng)為Windows XP。

為了進(jìn)行公平比較，只比較基于內(nèi)存數(shù)據(jù)的算法性能。實(shí)驗(yàn)所采用的數(shù)據(jù)集為XMark (582 MB)與DBLP注3http://www.informatik.uni-trier.de/～ley/db/。(876 MB)。在解析 2個(gè)數(shù)據(jù)集之后，基于Oracle Berkeley DB4，使用一個(gè)散列文件來(lái)存儲(chǔ)所有的關(guān)鍵字倒排表，其中散列文件的每個(gè)key是一個(gè)關(guān)鍵字k，value是k對(duì)應(yīng)的存儲(chǔ)Dewey編碼的倒排表。當(dāng)處理給定查詢Q時(shí)，Q對(duì)應(yīng)的倒排表首先被讀入到內(nèi)存，所有實(shí)驗(yàn)結(jié)果均不考慮I/O代價(jià)的影響。

從 XMark數(shù)據(jù)集中選取了一組關(guān)鍵字，這些關(guān)鍵字根據(jù)其在數(shù)據(jù)集中出現(xiàn)的次數(shù)分為3類：1)低頻關(guān)鍵字(100～1000); 2)中頻關(guān)鍵字(10000～40000);3)高頻關(guān)鍵字(300000～600000)?；谶@些關(guān)鍵字，生成了 12個(gè)查詢，按照關(guān)鍵字個(gè)數(shù)分成 4組(Group1：2個(gè)關(guān)鍵字；Group2：3個(gè)關(guān)鍵字；Group3：4個(gè)關(guān)鍵字；Group4：5個(gè)關(guān)鍵字)，如表1所示。表示所有關(guān)鍵字倒排表的長(zhǎng)度之和，|Lmax|(|Lmin|)表示最長(zhǎng)(最短)倒排表的長(zhǎng)度，NE表示滿足條件的ELCA節(jié)點(diǎn)個(gè)數(shù)，RE=NE/|Lmin|表示結(jié)果選擇率。DBLP數(shù)據(jù)集上的查詢也用類似的方式生成，由于XMark數(shù)據(jù)集包含較復(fù)雜的文檔結(jié)構(gòu)，且數(shù)據(jù)集大小可以按比例調(diào)整以便進(jìn)行擴(kuò)展性測(cè)試，本文中主要展示基于XMark數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。所有算法均用Visual C++ 語(yǔ)言實(shí)現(xiàn)，運(yùn)行時(shí)間為算法執(zhí)行100次的平均值。

6.2 性能比較和分析

表2為12個(gè)查詢的運(yùn)行時(shí)間比較，其中，TB表示RKN-Base運(yùn)行時(shí)間，TO表示RKN-Optimized運(yùn)行時(shí)間，Re=TO/TB表示2個(gè)算法運(yùn)行時(shí)間的比率，由實(shí)驗(yàn)結(jié)果可知。

1)對(duì)RKN-Base而言，由于其需要處理所有的關(guān)鍵字節(jié)點(diǎn)(表1第3列，因此當(dāng)關(guān)鍵字節(jié)點(diǎn)個(gè)數(shù)較多時(shí)，性能較差，例如Q10。同時(shí)，其性能也受ELCA節(jié)點(diǎn)個(gè)數(shù)(表1第6列NE)的影響，當(dāng)ELCA節(jié)點(diǎn)個(gè)數(shù)變多時(shí)，所需時(shí)間明顯增大，這是由其時(shí)間復(fù)雜度中的log|ELCASet|決定的，例如Q2和Q3。

2)對(duì)RKN-Optimized而言，由于其循環(huán)次數(shù)由ELCA節(jié)點(diǎn)個(gè)數(shù)決定，因此當(dāng)ELCA節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，性能較好，如 Q1，Q4，Q7，Q8，Q9，Q10，Q11等，甚至在某些情況下優(yōu)于RKN-Base 4個(gè)數(shù)量級(jí)，例如Q1，Q4，Q7，Q10。隨著結(jié)果選擇率的增加，RKN-Optimized的性能優(yōu)勢(shì)逐漸下降，個(gè)別情況下甚至比RKN-Base差，這是因?yàn)镽KN-Optimized需要處理大量的ELCA節(jié)點(diǎn)，例如Q3。

表1 基于XMark數(shù)據(jù)集的查詢

表2 RKN-Base與RKN-Optimized運(yùn)行12個(gè)查詢的運(yùn)行時(shí)間

以上觀察及表2的實(shí)驗(yàn)結(jié)果可進(jìn)一步由表3的數(shù)據(jù)來(lái)解釋。表3為2種算法中執(zhí)行基本操作(編碼比較操作)的次數(shù)，該數(shù)據(jù)可以客觀反映不同算法運(yùn)行時(shí)間的差異。其中，NB表示RKN-Base編碼比較次數(shù)，NO表示RKN- Optimized編碼比較次數(shù)，Re=NO/NB表示2個(gè)算法編碼比較次數(shù)的比率，如表 3所示，對(duì)Q1，Q4，Q7，Q10而言，RKN-Optimized的編碼比較次數(shù)遠(yuǎn)少于RKN-Base，因此其所需運(yùn)行時(shí)間遠(yuǎn)小于 RKN-Base。對(duì) Q3而言，RKNOptimized的編碼比較次數(shù)接近RKN-Base，因此其所需運(yùn)行時(shí)間與RKN-Base也相差不大。

表3 RKN-Base與RKN-Optimized運(yùn)行12個(gè)查詢的編碼比較次數(shù)

除了表1的12個(gè)查詢，本文還隨機(jī)生成了17萬(wàn)查詢，算法運(yùn)行時(shí)間按照查詢關(guān)鍵字個(gè)數(shù)及結(jié)果選擇率分類，如圖6所示。該實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了：1)關(guān)鍵字個(gè)數(shù)較少，結(jié)果選擇率較高時(shí)，RKN-Optimized性能最差。例如圖 6(a)中結(jié)果選擇率為[40,100]時(shí)，RKN-Optimized與RKN-Base運(yùn)行時(shí)間基本相同。2)關(guān)鍵字個(gè)數(shù)較多，結(jié)果選擇率較低時(shí)，RKN-Optimized性能最好。如圖 6(d)中結(jié)果選擇率為(0,1)時(shí)，RKN-Optimized運(yùn)行時(shí)間優(yōu)于RKN-Base近100倍。3)考慮單個(gè)因素時(shí)，隨著關(guān)鍵字個(gè)數(shù)的增加，RKN-Optimized性能優(yōu)勢(shì)逐漸上升。例如圖6中隨著關(guān)鍵字個(gè)數(shù)增加，圖6(c)和圖6(d)中RKN-Optimized的整體性能優(yōu)于圖6(a)和圖6(b)。另外，隨著結(jié)果選擇率的升高，RKN-Optimized的優(yōu)勢(shì)逐漸下降。

圖6 運(yùn)行時(shí)間比較

圖7給出在不同大小的XML文檔上執(zhí)行查詢Q8的運(yùn)行時(shí)間。從圖中可以看出本文方法有非常好的擴(kuò)展性，對(duì)于其他的查詢，有類似的結(jié)果，因此不再贅述。

圖7 Q8在不同大小XML文檔上的運(yùn)行時(shí)間

表4為DBLP數(shù)據(jù)集上的10個(gè)查詢，其中，NE為ELCA個(gè)數(shù)，算法運(yùn)行時(shí)間如圖8所示。通過(guò)實(shí)驗(yàn)可知，RKN-Optimized在大多數(shù)情況下優(yōu)于RKN-Base，原因同樣是因?yàn)镽KN-Optimized避免了處理大量無(wú)用節(jié)點(diǎn)。

表4 基于DBLP數(shù)據(jù)集的查詢

圖8 DBLP數(shù)據(jù)集上運(yùn)行時(shí)間

7 結(jié)束語(yǔ)

構(gòu)建結(jié)果子樹(shù)是XML關(guān)鍵字查詢處理的核心問(wèn)題，其中求解與每個(gè)子樹(shù)根節(jié)點(diǎn)相關(guān)的關(guān)鍵字節(jié)點(diǎn)集是影響結(jié)果子樹(shù)構(gòu)建效率的重要步驟。針對(duì)已有方法不能正確求解基于ELCA語(yǔ)義的相關(guān)關(guān)鍵字節(jié)點(diǎn)集的問(wèn)題，本文提出了相關(guān)關(guān)鍵字節(jié)點(diǎn)的形式化定義RKN。依據(jù)該定義提出了基本算法RKN-Base，該算法通過(guò)順序掃描每個(gè)關(guān)鍵字節(jié)點(diǎn)一次即可判斷其是否為某個(gè)ELCA節(jié)點(diǎn)的相關(guān)關(guān)鍵字節(jié)點(diǎn)。針對(duì)RKN-Base算法不能避免處理無(wú)用節(jié)點(diǎn)的問(wèn)題，提出了優(yōu)化算法RKN- Optimized。該算法基于每個(gè)ELCA節(jié)點(diǎn)求其相關(guān)關(guān)鍵字節(jié)點(diǎn)，可避免處理無(wú)用關(guān)鍵字節(jié)點(diǎn)，降低時(shí)間復(fù)雜度。最后通過(guò)實(shí)驗(yàn)對(duì)所提算法的性能進(jìn)行了驗(yàn)證和分析。

本文的后續(xù)工作將針對(duì)生成結(jié)果子樹(shù)的第3步（構(gòu)建結(jié)果子樹(shù)）展開(kāi)研究，進(jìn)而設(shè)計(jì)并實(shí)現(xiàn)一個(gè)完整、高效的XML關(guān)鍵字查詢處理系統(tǒng)。

[1]TATARINOV I,VIGLAS S,BEYER K S,et al. Storing and querying ordered XML using a relational database system[A]. SIGMOD Conference[C]. 2002. 204-215.

[2]GUO L,SHAO F,BOTEV C,et al. Xrank: ranked keyword search over XML documents[A]. SIGMOD Conference[C]. 2003.16-27.

[3]ZHOU RUI,LIU CHENGFEI,LI JIANXIN. Fast elca computation for keyword queries on XML data[A]. International Conference on Extending DB Technology[C]. Lausanne,Switzerland,2010.549-560.

[4]COHEN S,MAMOU J,KANZA Y,et al. Xsearch: a semantic search engine for XML[A]. VLDB[C]. 2010. 45-56.

[5]LI G,FENG J,WANG J,et al. Effective keyword search for valuable lcas over XML documents[A]. CIKM[C]. 2007.31-40

[6]ZHOU J,BAO Z,CHEN Z,et al. Top-down SLCA computation based on list partition[A]. DASFAA[C]. 2012.

[7]WANG W Y,WANG X L,ZHOU A Y. Hash-search: an efficient slca-based keyword search algorithm on XML documents[A]. LNCS 5463[C]. 2009. 496-510.

[8]XU Y,PAPAKONSTANTINOU Y. Efficient keyword search for smallest lcas in XML databases[A]. SIGMOD Conference[C]. 2005.

[9]SUN C,CHAN C Y,GOENKA A K. Multiway slca-based keyword search in XML data[A]. WWW[C]. 2007.1043-1052.

[10]ZHOU J,BAO Z,WANG W,et al. Fast SLCA and ELCA computation for XML keyword queries based on set intersection[A]. ICDE[C].2012.

[11]XU Y,PAPAKONSTANTINOU Y. Efficient lca based keyword search in XML data[A]. EDBT[C]. 2008.

[12]LIU Z,CHEN Y Reasoning and identifying relevant matches for XML keyword search[J]. PVLDB,2008. 1(1): 921-932.

[13]KONG L,GILLERON R,LEMAY A. Retrieving meaningful relaxed tightest fragments for XML keyword search[A]. EDBT[C]. 2009.815-826.

[14]ZHOU J,BAO Z,CHEN Z,et al. Fast result enumeration for keyword queries on XML data[A]. DASFAA[C].2012.95-109.

[15]HRISTIDIS V,KOUDAS N,PAPAKONSTANTINOU Y,et al. Keyword proximity search in XML trees[J]. IEEE Trans Knowl Data Eng,2006,18(4):525-539.

[16]TATARINOV I,VIGLAS S,et al. Storing and querying ordered XML using a relational database system[A]. Special Interest Group on Management of Data Conference[C]. Madison,USA,2002. 204-215.

[17]BRODER A Z. A taxonomy of Web search[J]. SIGIR Forum,2002,36(2):3-10.