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

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

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

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

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

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

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

0 引 言

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

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

1 相關(guān)研究

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

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

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

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

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

2 基本概念

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

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

2.2 PEDewey編碼

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

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

圖1 不確定XML文檔

3 RLPI索引

3.1 RLPI路徑索引

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

路徑索引的構(gòu)建采用如圖2(a)所示的鏈表方式進(jìn)行存儲(chǔ)，以逆序路徑(ReversePath)即節(jié)點(diǎn)標(biāo)簽路徑的逆序表示作為索引項(xiàng)，每個(gè)索引項(xiàng)存儲(chǔ)一個(gè)單鏈表首地址；將同一逆序路徑對(duì)應(yīng)的路徑信息(PathInformation)依次存入相應(yīng)單鏈表節(jié)點(diǎn)中。

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

圖2 路徑索引鏈表結(jié)構(gòu)

算法1 RLPI-path

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

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

a) Vi=Travelsal(T);

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

b) Lvi=RLPI_NXPath(Vi);

//根據(jù)節(jié)點(diǎn)的逆序路徑構(gòu)建索引

c) return Lvi

//返回RLPI路徑索引

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

1 if(ReversePathList.isEmpty())

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

2 { ReversePathList.add(path)；

//將當(dāng)前路徑添加到ReversePathList

3 RLPI_IndexConstructionList.addnodeRLPI_

IndexConstruction(Vi)；

//添加PathInformation

}

4 else

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

//當(dāng)前節(jié)點(diǎn)逆序路徑在逆序路徑信息鏈表中已存在

6 { k=i;

7 RLPI_IndexConstructionList.get(k).addnode

RLPI_IndexConstruction(Vi);

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

}

8 else

9 { ReversePathList.add(path)；

//將當(dāng)前路徑添加到ReversePathList

10 RLPI_IndexConstructionList.addnodeRLPI_ IndexConstruction(Vi)；

//添加PathInformation

11 }

12 return RLPI_IndexConstructionList;

//返回RLPI路徑索引鏈表

13 }

3.2 RLPI值索引

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

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

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

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

(1)

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

(2)

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

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

圖4 葉子節(jié)點(diǎn)的值索引結(jié)構(gòu)

值索引相應(yīng)的過(guò)濾規(guī)則(對(duì)于給定概率pq的范圍查詢r(jià)q):

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

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

算法2 RLPI-value

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

輸出：RLPI索引。

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

2 { cont=vi.getText()

//獲取其數(shù)據(jù)

3 valueResultlist=contvalueSolution(cont);

//cfbout,cfbin信息計(jì)算

4 RLPI_IndexConstructionList.addvalueResultlist

//將信息插入到對(duì)應(yīng)節(jié)點(diǎn)鏈表

5 return RLPI_IndexConstructionList}

3.3 算法復(fù)雜度分析

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

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

4 基于RLPI索引的查詢處理

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

(1) 根據(jù)RLPI路徑索引中的索引項(xiàng)查詢?nèi)~子節(jié)點(diǎn)所對(duì)應(yīng)的單枝路徑，通過(guò)有限自動(dòng)機(jī)進(jìn)行匹配，從而得到相應(yīng)的編碼。

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

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

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

算法3 ProTwig

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

輸出：滿足查詢模式Q的結(jié)果。

a) Vi=Travelsal(T);

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

b) Rvi=TwigSolution (Vi);

//判斷節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，并進(jìn)行相應(yīng)的處理

c) return Rvi

//返回查詢結(jié)果

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

算法4 TwigSolution

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

2 { leafResult= leafSolution(node);

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

3 filterSolution(leafResult);

//進(jìn)行過(guò)濾

4 return leafResult;}

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

5 else

6 { for(all children of node)

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

8 }

9 Result=QnodIntegration (ResultList);

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

10 filterSolution(Result);

11 return Result;

12 }

4.2 基于RLPI索引的查詢實(shí)例

圖5 查詢實(shí)例

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

例：查詢?nèi)鐖D5實(shí)例，先根據(jù)RLPI路徑索引的逆序標(biāo)簽路徑temperature.…h(huán)ouse.…factory和humidity.…h(huán)ouse.…factory，并分別通過(guò)有限自動(dòng)機(jī)進(jìn)行匹配，得到temperature.measurement.room.house.factory路徑相應(yīng)的temperature為0.0.0.0.-30.0，0.0.0.0.-30.1，0.0.1.0.0及temperature.measurement.house.factory路徑相應(yīng)的temperature為0.1.0.0，0.2.0.-20.0；路徑humidity.measurement.house.factory相應(yīng)的humidity為0.1.0.1，0.2.0.-20.1。經(jīng)過(guò)步驟(2)過(guò)濾后，保留的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根據(jù)過(guò)濾規(guī)則1被過(guò)濾掉；編碼為0.1.0.0的temperature根據(jù)過(guò)濾規(guī)則3，可得其滿足在(20，50)的范圍內(nèi)概率大于0.8。將此時(shí)留下的{0.1.0.0}的temperature和{0.1.0.1，0.2.0.-20.1}的humidity進(jìn)行匹配返回給上一層{(0.1.0.0，0.1.0.1)，0.1}；同理自底向上依次執(zhí)行，直到執(zhí)行到factory的位置，合并共同祖先f(wàn)actory的后代節(jié)點(diǎn)集合。因此，最終結(jié)果為{(0.1.0.0，0.1.0.1)，0.1，0}。

5 實(shí)驗(yàn)結(jié)果分析

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

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

5.2 測(cè)試和結(jié)果分析

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

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

表1 查詢用例

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

圖6 不同文檔的響應(yīng)時(shí)間對(duì)比

圖7 不同查詢用例的響應(yīng)時(shí)間對(duì)比

圖8 不同閾值的響應(yīng)時(shí)間對(duì)比

6 結(jié) 語(yǔ)

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

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

[2] 易平,胡運(yùn)安,陳福生,等.基于PATRICIA-TRIES的XML路徑索引設(shè)計(jì)[J].小型微型計(jì)算機(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ù)索引技術(shù)[J].計(jì)算機(jī)應(yīng)用與軟件,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ù)樹(shù)的化簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用研究,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。國(guó)家自然科學(xué)基金項(xiàng)目(61163015)；內(nèi)蒙古自然科學(xué)基金項(xiàng)目(2013MS0909)。張曉琳，教授，主研領(lǐng)域：數(shù)據(jù)庫(kù)理論與技術(shù)。郭丹丹，碩士生。韓雨童，碩士生。郝琨，碩士生。譚躍生，教授。

TP392

A

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