面向XML關(guān)鍵字查詢的高效RKN求解策略

陳子陽，王璿，湯顯

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

1 引言

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

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

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

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

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

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

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

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

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

本文的主要貢獻如下。

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

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

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

4)通過實驗對算法的性能進行了驗證和分析。

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

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

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

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

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

2.2 查詢語義及符號

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

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

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

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

2.3 相關(guān)工作

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

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

3 RKN及其性質(zhì)

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

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

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

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

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

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

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

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

4 RKN-Base算法

4.1 RKNS的表示

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

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

4.2 算法描述

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

算法1 getRKNS-B(ELCASet)

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

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

4.3 算法分析

5 RKN-Optimized算法

5.1 主要思想

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

5.2 算法描述

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

算法2 getRKNS-O(ELCASet)

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

5.3 算法分析

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

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

圖5 例2的運行圖

6 實驗

6.1 實驗環(huán)境

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

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

從 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個查詢，按照關(guān)鍵字個數(shù)分成 4組(Group1：2個關(guān)鍵字；Group2：3個關(guān)鍵字；Group3：4個關(guān)鍵字；Group4：5個關(guān)鍵字)，如表1所示。表示所有關(guān)鍵字倒排表的長度之和，|Lmax|(|Lmin|)表示最長(最短)倒排表的長度，NE表示滿足條件的ELCA節(jié)點個數(shù)，RE=NE/|Lmin|表示結(jié)果選擇率。DBLP數(shù)據(jù)集上的查詢也用類似的方式生成，由于XMark數(shù)據(jù)集包含較復(fù)雜的文檔結(jié)構(gòu)，且數(shù)據(jù)集大小可以按比例調(diào)整以便進行擴展性測試，本文中主要展示基于XMark數(shù)據(jù)集的實驗結(jié)果。所有算法均用Visual C++ 語言實現(xiàn)，運行時間為算法執(zhí)行100次的平均值。

6.2 性能比較和分析

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

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

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

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

表2 RKN-Base與RKN-Optimized運行12個查詢的運行時間

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

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

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

圖6 運行時間比較

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

圖7 Q8在不同大小XML文檔上的運行時間

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

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

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

7 結(jié)束語

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

本文的后續(xù)工作將針對生成結(jié)果子樹的第3步（構(gòu)建結(jié)果子樹）展開研究，進而設(shè)計并實現(xiàn)一個完整、高效的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.