張曉琳 郭丹丹 韓雨童 郝 琨 譚躍生

RLPI索引：一種處理連續(xù)不確定XML索引

張曉琳 郭丹丹 韓雨童 郝 琨 譚躍生

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

針對目前連續(xù)不確定XML數(shù)據的概率閾值范圍查詢，提出一種新的包含路徑索引和值索引的RLPI(Reverse Label Probabilistic Index)索引。RLPI路徑索引以逆序標簽路徑作為索引項，通過逆序標簽路徑可區(qū)分不同路徑上的同名節(jié)點，更具針對性地定位所需節(jié)點。RLPI值索引借鑒U樹的思想，通過提前計算并存儲葉子節(jié)點的相關信息，以減少查詢中需處理的元素數(shù)目，并且其對滿足任意連續(xù)pdf (probability density function)的不確定數(shù)據均適用。理論分析和實驗結果表明，RLPI索引技術有效地提高了查詢處理的性能。

連續(xù)不確定數(shù)據 XML 索引 概率閾值范圍查詢

0 引 言

隨著網絡技術的快速發(fā)展，XML類型的數(shù)據已成為當前一種主流的數(shù)據形式，并成為Internet中進行數(shù)據交換和表示事實上的標準。在實際生活中，數(shù)據的不確定性是普遍存在的，傳統(tǒng)的確定性數(shù)據已經不能準確描述現(xiàn)實世界。隨著人們對不確定性數(shù)據的認識研究和對數(shù)據采集和處理技術的深入理解，不確定性數(shù)據在物流、工業(yè)、金融、軍事等領域得到相當廣泛的應用?；旧希跀?shù)據庫中的不確定性是為了捕捉現(xiàn)實世界的狀態(tài)，如監(jiān)控的壓強、溫度、移動目標的位置都是在不斷改變的。數(shù)據的不確定性信息可以以概率值或概率分布的形式在XML文檔中表示。對于連續(xù)不確定的數(shù)據，存儲用概率密度函數(shù)pdf可能值的范圍來代替存儲數(shù)據單一的值。而相應的概率閾值范圍查詢，是通過給定概率閾值及范圍，來獲取超過概率閾值起點并滿足查詢范圍的結果。在概率閾值范圍查詢中，由于滿足查詢指定的概率值的出現(xiàn)，從而使得結果被擴大化。概率閾值范圍查詢比傳統(tǒng)查詢更精確及信息化。

目前，對概率閾值范圍查詢局限于只對滿足正態(tài)分布的連續(xù)不確定XML數(shù)據具有適用性。本文針對概率閾值范圍查詢,提出一種對任意連續(xù)不確定XML數(shù)據均適用的RLPI索引。在RLPI路徑索引中將具有相同逆序標簽路徑的索引項聚集存儲，節(jié)省了空間花銷；在RLPI值索引中，通過預處理任意連續(xù)不確定數(shù)據，并結合相應地過濾策略，過濾與查詢無關的節(jié)點，減少了pdf的計算，從而提高了查詢的速度。

1 相關研究

目前針對XML數(shù)據的小枝查詢，研究者們已經提出了一些有效而快速的索引結構。文獻[1]提出了一種素數(shù)序列標記法,這種標記法可快速地建立經典F&B索引,并給出了素數(shù)整除匹配算法。通過路徑匹配算法可預先排除部分無關節(jié)點,并利用節(jié)點標記值之間的整除關系來判斷子樹匹配,有效地加速了查詢處理過程。但此索引不能處理不確定XML數(shù)據。在文獻[2]中PATRICIA-TRIES路徑索引是基于關鍵字空間分解的樹結構，只在葉節(jié)點存儲數(shù)據記錄，內部節(jié)點作為占位符引導檢索過程。對路徑索引使用壓縮字符編碼建立路徑索引，壓縮了索引空間。但這些索引都不能處理不確定XML數(shù)據。

對不確定XML數(shù)據，在文獻[3]中提出將XML Schema路徑和數(shù)據值組合作為索引值，并利用idlists來確定分支點，可以支持一般關系查詢處理策略。文中還提出路徑索引和值索引的空間壓縮策略，可以很大程度節(jié)省建索引的空間花銷。文獻[4]針對目前大多數(shù)索引不支持小枝查詢及索引結構存儲花銷大的缺點提出了USIX算法。該算法僅使用了兩個關系表：一個是路徑的摘要表；另一個是包含值的葉子節(jié)點表。結構緊湊，可以有效地支持分枝查詢。

進一步地，文獻[5]提出了一個擴展的基于區(qū)間的編碼索引，并提供了有效的概率XML查詢處理。它只訪問查詢中指定的數(shù)據標簽，在數(shù)據匹配同時，評估結果的概率以消除不必要的數(shù)據匹配。該索引減少了數(shù)據的存取時間并改善了概率XML查詢處理的性能。

針對目前越來越多的連續(xù)不確定XML數(shù)據,文獻[6]擴展了經典的結構索引F-index，針對連續(xù)不確定XML數(shù)據的概率閾值查詢，提出CPTI索引。通過CPTI結構索引查詢小枝，并確定小枝的路徑概率；通過CPTI值索引過濾與查詢無關的元素以減少查詢中需要處理的元素數(shù)目。但該索引僅限于對滿足正態(tài)分布的連續(xù)不確定XML數(shù)據的研究。

對連續(xù)不確定數(shù)據的處理引起了廣泛地研究，文獻[7]介紹了兩個有效的索引。第一個索引是擴大基于R樹的不確定信息的存儲，使得I/O操作明顯減少。通過把一維的片段映射到二維空間，并由二維多邊形進行范圍查詢。第二個索引基于理論研究，提出基于方差的聚類索引。這個索引將具有相似的不定性的數(shù)據節(jié)點聚類在一起，可用于各種連續(xù)不確定密度函數(shù)(pdf)數(shù)據的查詢。文獻[8]針對不確定數(shù)據的范圍查詢提出了U-tree，通過存取方法的優(yōu)化設計減少I/O操作及CPU的處理時間，而且其中的過濾策略對任意連續(xù)不確定密度函數(shù)(pdf)數(shù)據的過濾均有效。但此索引主要應用在地理信息系統(tǒng)(GIS)。

2 基本概念

2.1 數(shù)據模型

目前，支持連續(xù)不確定數(shù)據的數(shù)據模型有概率樹模型和P-文檔模型?，F(xiàn)已有通過分析概率XML數(shù)據樹中的路徑類型從而對不確定XML文檔進行簡化的概率樹模型[9]。在概率樹模型中，可能節(jié)點會存在大量的冗余信息，給不確定數(shù)據管理造成一定的困難，使得效率下降。本文采用的是將概率信息附加在文檔樹邊上的P-文檔模型PrXML{mux,ind}[10]。為支持葉子上的連續(xù)分布，在葉子節(jié)點附加一個cont(連續(xù))類型的分布式節(jié)點。

2.2 PEDewey編碼

PEDewey編碼[11]是在Dewey編碼的基礎上，增加了對不確定XML中分布節(jié)點IND和MUX的處理一種前綴編碼。該編碼為不確定XML文檔樹中的每個節(jié)點都相應地分配了唯一的標識符。該編碼的優(yōu)點是根據節(jié)點對應的編碼值可以獲得從根節(jié)點到該節(jié)點的路徑標簽名序列。

如圖1所示是一棵帶有PEDewey編碼的不確定XML文檔樹。

圖1 不確定XML文檔

3 RLPI索引

3.1 RLPI路徑索引

RLPI路徑索引的基本思想：根據編碼后XML文檔樹及樹中的逆序標簽路徑，為XML文檔樹中的所有可能路徑建立索引。其中，逆序標簽路徑是由根節(jié)點到當前節(jié)點路徑的逆序表示。

路徑索引的構建采用如圖2(a)所示的鏈表方式進行存儲，以逆序路徑(ReversePath)即節(jié)點標簽路徑的逆序表示作為索引項，每個索引項存儲一個單鏈表首地址；將同一逆序路徑對應的路徑信息(PathInformation)依次存入相應單鏈表節(jié)點中。

路徑信息(PathInformation)結構如圖2(b)所示。其中，PEDewey是相應逆序路徑所對應節(jié)點的編碼；PathProbability是從根節(jié)點到該節(jié)點的路徑概率；Distribution是存放葉子節(jié)點服從的分布(如節(jié)點服從正態(tài)分布，則Distribution存放的是N；如服從均勻分布，則Distribution存放的是U)。圖1不確定XML文檔中逆序標簽路徑temperature. measurement.room.house.fact- ory的PathInformation信息結構如圖2(c)所示，編碼為0.0.0.0. -30.0的temperature節(jié)點路徑概率是0.3，服從正態(tài)分布N;編碼為0.0.0.0.-30.1的temperature節(jié)點路徑概率是0.7，服從正態(tài)分布N；編碼為0.0.1.0.0的temperature節(jié)點路徑概率是1，服從均勻分布U。

圖2 路徑索引鏈表結構

算法1 RLPI-path

輸入：編碼的XML文檔，其中有n個節(jié)點{v1,v2,…,vn}。

輸出：逆序路徑索引鏈表。

a) Vi=Travelsal(T);

//深度優(yōu)先遍歷樹，得到其節(jié)點序列

b) Lvi=RLPI_NXPath(Vi);

//根據節(jié)點的逆序路徑構建索引

c) return Lvi

//返回RLPI路徑索引

RLPI-path的核心操作是RLPI_NXPath(Vi)，以下為具體過程：

1 if(ReversePathList.isEmpty())

//逆序路徑信息鏈表為空

2 { ReversePathList.add(path)；

//將當前路徑添加到ReversePathList

3 RLPI_IndexConstructionList.addnodeRLPI_

IndexConstruction(Vi)；

//添加PathInformation

}

4 else

5 {if(Vi.ReversePath.equals(ReversePathList.get(i)))

//當前節(jié)點逆序路徑在逆序路徑信息鏈表中已存在

6 { k=i;

7 RLPI_IndexConstructionList.get(k).addnode

RLPI_IndexConstruction(Vi);

//在路徑相同的位置添加PathInformation

}

8 else

9 { ReversePathList.add(path)；

//將當前路徑添加到ReversePathList

10 RLPI_IndexConstructionList.addnodeRLPI_ IndexConstruction(Vi)；

//添加PathInformation

11 }

12 return RLPI_IndexConstructionList;

//返回RLPI路徑索引鏈表

13 }

3.2 RLPI值索引

RLPI值索引的基本思想：提前計算葉子節(jié)點的連續(xù)不確定數(shù)據的相關信息，并將這些信息存儲在對應的節(jié)點鏈表。查詢時，通過存儲的信息及相應的過濾規(guī)則進行過濾，以提高查詢效率。

定義1 節(jié)點o的概率約束區(qū)域PCR(Probabilistically Const- rained Regions)由線l1+、 l1-兩線分割得到的片段，記作o.pcr(p)。線l1+將不確定片段成兩部分(l1+的左、右片段)，其中點o出現(xiàn)在l1+右片段的概率為p；相似地，點o出現(xiàn)在線l1-左端的概率也為p，其中p取[0，0.5]。如圖3(a)所示。

根據上述定義可以得到節(jié)點針對不同p(p1，p2，…，pm)的PCR，再根據下面的公式計算在這m個PCR外側的線性函數(shù)o.cfbout及在這m個PCR內側的線性函數(shù)o.cfbin(如圖3(b)所示)：

o.cfbout(p)=αout-βout·p

(1)

o.cfbin(p)=αin-βin·p

(2)

圖3 葉子節(jié)點的PCR和o.cfbout及o.cfbin

圖4(a)為節(jié)點值索引組織結構，cont為相應節(jié)點的pdf,ur為當前節(jié)點的不確定范圍。如圖4(b)所示為服從均勻分布U(20,40)的葉子節(jié)點的值索引結構。如圖4(c)所示為服從正態(tài)分布N(52,5)的葉子節(jié)點的值索引結構。

圖4 葉子節(jié)點的值索引結構

值索引相應的過濾規(guī)則(對于給定概率pq的范圍查詢rq):

1) 當pq>1-pm，如果rq沒有完全包括o.cfbin(pj)，節(jié)點o可以刪除。其中pj(1≤j≤m)是U-catalog中不小于1-pq的最小值。

2) 當pq≤1-pm，如果rq和o.cfbout(pj)不相交，節(jié)點o可以刪除。其中pj是在U-catalog中不大于pq的最大值。

算法2 RLPI-value

輸入：編碼的XML文檔，其中有n個節(jié)點{v1,v2,…,vn}，RLPI-path索引。

輸出：RLPI索引。

1 while(vi是葉子節(jié)點)

2 { cont=vi.getText()

//獲取其數(shù)據

3 valueResultlist=contvalueSolution(cont);

//cfbout,cfbin信息計算

4 RLPI_IndexConstructionList.addvalueResultlist

//將信息插入到對應節(jié)點鏈表

5 return RLPI_IndexConstructionList}

3.3 算法復雜度分析

時間復雜度為：RLPI路徑索引，最壞的情況掃描所有節(jié)點，為每個節(jié)點都構建逆序路徑時間復雜度為O(n)。若這n條逆序路徑都不同，則其時間復雜度為O(1+2+…+(n-1)),即O((n2-n)/2),其中n表示節(jié)點數(shù)。所以RLPI路徑索引的時間復雜度為O(n+(n2-n)/2),即O((n2+n)/2)；RLPI值索引中，葉子節(jié)點個數(shù)為1,則時間復雜度為O(1)。因此RLPI索引在最壞情況下的時間復雜度為O((n2+n)/2+l)。

空間復雜度：RLPI路徑索引，最壞情況下的時間復雜度是O((n2+n)/2)，將這n個節(jié)點的路徑最后都存入鏈表中。在RLPI值索引構建階段的空間復雜度仍為O((n2+n)/2)，所以RLPI索引的空間復雜度為O((n2+n)/2)。

4 基于RLPI索引的查詢處理

4.1 基于RLPI索引的ProTwig查詢算法描述

(1) 根據RLPI路徑索引中的索引項查詢葉子節(jié)點所對應的單枝路徑，通過有限自動機進行匹配，從而得到相應的編碼。

(2) 根據鏈表中PathProbability確定概率閾值查詢的路徑概率。如果temperature的路徑概率小于查詢概率閾值將被過濾掉，否則保留。

(3) 根據RLPI值索引中o.cfbout和o.cfbin及下面的過濾規(guī)則判斷在給定范圍的溫度概率是否大于給定概率值。

(4) 將得到的底層葉子節(jié)點集合返回給上一層；再經過步驟(2)過濾并計算小枝的條件概率值，將結果集返回給上一層；同理自底向上依次執(zhí)行，直到查詢到根節(jié)點，合并根節(jié)點的后代節(jié)點集合并計算小枝的條件概率值。

算法3 ProTwig

輸入：查詢模式Q，其中有n個節(jié)點{v1,v2,…,vn}；RLPI索引鏈表。

輸出：滿足查詢模式Q的結果。

a) Vi=Travelsal(T);

//深度優(yōu)先遍歷樹，得到其節(jié)點序列

b) Rvi=TwigSolution (Vi);

//判斷節(jié)點是否為葉子節(jié)點，并進行相應的處理

c) return Rvi

//返回查詢結果

ProTwig查詢算法主函數(shù)TwigSolution的遞歸調用實現(xiàn)過程如下：

算法4 TwigSolution

1 if(node是葉子節(jié)點)

2 { leafResult= leafSolution(node);

//葉子節(jié)點查詢處理算法

3 filterSolution(leafResult);

//進行過濾

4 return leafResult;}

//將滿足條件的葉子節(jié)點集合返回給上層查詢節(jié)點

5 else

6 { for(all children of node)

7 { ResultList[]=TwigSolution(node.children(i));

8 }

9 Result=QnodIntegration (ResultList);

//合并共同祖先的后代節(jié)點集合

10 filterSolution(Result);

11 return Result;

12 }

4.2 基于RLPI索引的查詢實例

圖5 查詢實例

例如查詢圖1中溫度在(20,50)范圍內的概率大于0.8,如圖5所示的小枝。利用RLPI路徑索引查詢圖5中的Twig，首先查詢到葉子節(jié)點temperature和humidity。再通過相應的過濾策略過濾掉不滿足(20,50)范圍內的概率大于0.8的溫度，根據編碼將具有相同祖先的節(jié)點由底層向上遞歸合并從而得到滿足條件的結果。

例：查詢如圖5實例，先根據RLPI路徑索引的逆序標簽路徑temperature.…h(huán)ouse.…factory和humidity.…h(huán)ouse.…factory，并分別通過有限自動機進行匹配，得到temperature.measurement.room.house.factory路徑相應的temperature為0.0.0.0.-30.0，0.0.0.0.-30.1，0.0.1.0.0及temperature.measurement.house.factory路徑相應的temperature為0.1.0.0，0.2.0.-20.0；路徑humidity.measurement.house.factory相應的humidity為0.1.0.1，0.2.0.-20.1。經過步驟(2)過濾后，保留的temperature為0.0.1.0.0，0.1.0.0，0.2.0.-20.0。其中p1，p2，…，pm分別選取0，1/16，2/16，…，8/16。編碼為0.0.1.0.0和0.2.0.-20.0的temperature根據過濾規(guī)則1被過濾掉；編碼為0.1.0.0的temperature根據過濾規(guī)則3，可得其滿足在(20，50)的范圍內概率大于0.8。將此時留下的{0.1.0.0}的temperature和{0.1.0.1，0.2.0.-20.1}的humidity進行匹配返回給上一層{(0.1.0.0，0.1.0.1)，0.1}；同理自底向上依次執(zhí)行，直到執(zhí)行到factory的位置，合并共同祖先factory的后代節(jié)點集合。因此，最終結果為{(0.1.0.0，0.1.0.1)，0.1，0}。

5 實驗結果分析

5.1 實驗環(huán)境和數(shù)據集

實驗的硬件環(huán)境為：CPU Inter(R) Core i5(3.2 GHz)，RAM為8 GB，操作系統(tǒng)為64位的Windows 7，實驗工具為MyEclipse 6.5，JDK 6.0。實驗測試所用數(shù)據集是通過XMark生成合成數(shù)據集，然后利用一個隨機化的算法隨機加入一些分布節(jié)點，其中包括滿足正態(tài)分布和均勻分布的連續(xù)不確定數(shù)據,合成具有連續(xù)不確定性節(jié)點的XML數(shù)據集。

5.2 測試和結果分析

實驗采用Java實現(xiàn)提出的RLPI索引算法，并將該算法與只針對數(shù)據滿足正態(tài)分布的連續(xù)不確定XML的CPTI索引算法以及在經典F-index算法上集成連續(xù)節(jié)點處理的CF-index算法進行對比。

實驗部分共有三組測試條件來對比兩種算法。第一組測試條件是不同文檔、相同查詢用例，相同概率閾值；第二組測試條件是相同文檔、不同查詢用例，相同概率閾值；第三組測試條件是相同文檔、相同查詢用例，不同概率閾值。每組實驗均重復十次，得到的實驗數(shù)據采用去掉最大值和最小值，取平均值的方法記錄整理。查詢用例如表1所示。

表1 查詢用例

第一組測試使用的查詢用例為Q3，查詢在(20，50)范圍內且概率閾值Pq=0.8的temperature，選取6個大小不同文檔測試，查詢結果如圖6所示；第二組測試文檔大小為56.4 MB，查詢在(20，50)范圍內且概率閾值Pq=0.8的temperature，分別執(zhí)行表1的3個查詢用例，查詢結果如圖7所示；第三組測試選取文檔大小為56.4 MB，查詢用例為Q3，改變在(20，50)范圍內查詢temperature的概率閾值Pq值，查詢結果如圖8所示；明顯看出這三種情況下算法RLPI性能均優(yōu)于算法CPTI與CF-index。原因是算法RLPI中相較CPTI算法與CF-index，不僅能過濾掉滿足正態(tài)分布的節(jié)點而且可過濾掉滿足均勻分布的節(jié)點，從而減少了大量無用中間結果的生成。

圖6 不同文檔的響應時間對比

圖7 不同查詢用例的響應時間對比

圖8 不同閾值的響應時間對比

6 結 語

本文提出一種針對連續(xù)不確定XML數(shù)據概率閾值查詢的索引算法：RLPI算法通過其路徑索引加速了Twig查詢；使用其值索引過濾連續(xù)不確定XML數(shù)據，過濾掉不滿足條件的節(jié)點，減少了中間結果的連接，在一定程度上提高了查詢的效率。

[1] 王洪強,李建中,王宏志.基于F&B索引的XML查詢處理算法[J].計算機研究與發(fā)展,2010,47(5):866-877.

[2] 易平,胡運安,陳福生,等.基于PATRICIA-TRIES的XML路徑索引設計[J].小型微型計算機系統(tǒng),2006,27(3):475-480.

[3] Chen Z,Gehrke J,Korn F,et al.Index structures for matching XML twigs using relational query processors[J].Data & Knowledge Engineering,2007,60(2):283-302.

[4] Mohammad S,Martin P,Powley W.Relational universal index structure for evaluating XML twig queries[C]//Proceedings of Communications and Information Technology (ICCIT).Aqaba:IEEE,2011:116-120.

[5] Yun J H,Chung C W.Efficient probabilistic XML query processing using an extended labeling scheme and a lightweight index[J].Information Processing & Management,2012,48(6):1181-1202.

[6] 張換香,張曉琳,劉立新.連續(xù)不確定XML數(shù)據索引技術[J].計算機應用與軟件,2013,30(8):51-53.

[7] Cheng R,Xia Y,Prabhakar S,et al.Efficient indexing methods for probabilistic threshold queries over uncertain data[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30.Hong Kong:VLDB Endowment,2004:876-887.

[8] Tao Y,Cheng R,Xiao X,et al.Indexing multi-dimensional uncertain data with arbitrary probability density functions[C]//Proceedings of the 31st international conference on Very large data bases.Hong Kong:VLDB Endowment,2005:922-933.

[9] 王建衛(wèi),郝忠孝.一種概率XML數(shù)據樹的化簡算法[J].計算機應用研究,2010,27(12):4541-4543.

[10] Abiteboul S,Chan T H,Kharlamov E.Aggregate queries for discrete and continuous probabilistic XML[C]//Proceedings of the 13th International Conference on Database Theory.Lausanne:ACM Press,2010:50-61.

[11] Ning B,Liu C,Yu J X,et al.Matching top-k answers of twig patterns in probabilistic XML[J].Lecture Notes in Computer Science,2010,5981:125-139.

RLPI INDEX:AN INDEX PROCESSING CONTINUOUS UNCERTAIN XML DATA

Zhang Xiaolin Guo Dandan Han Yutong Hao Kun Tan Yuesheng

(SchoolofInformationEngineering,InnerMongoliaUniversityofScienceandTechnology,Baotou014010,InnerMongolia,China)

Aiming at current probability threshold range query on continuous uncertain XML data, we put forward a new RLPI index (reverse label probabilistic index). RLPI index contains RLPI path index and RLPI value index. RLPI path index takes reverse label path as the index item, through reverse label path it can distinguish tag nodes with same name on different paths, and is more targeted to locate the desired nodes. RLPI value index gets reference from the idea of U Tree. It calculates in advance and stores some related information of leaf nodes in order to reduce the number of elements to be processed in a query. RLPI value index is applicable to uncertain data satisfied with any continuous pdf (probability density function). Theoretical analysis and experimental results show that this index technique greatly improves query processing performance.

Continuous uncertain data XML Index Probability threshold range query

2014-09-24。國家自然科學基金項目(61163015)；內蒙古自然科學基金項目(2013MS0909)。張曉琳，教授，主研領域：數(shù)據庫理論與技術。郭丹丹，碩士生。韓雨童，碩士生。郝琨，碩士生。譚躍生，教授。

TP392

A

10.3969/j.issn.1000-386x.2016.04.007