1、1998年2月萬(wàn)維網(wǎng)聯(lián)盟發(fā)布了一種名為XML(可擴(kuò)展標(biāo)記語(yǔ)言)的數(shù)據(jù)標(biāo)準(zhǔn)。由于它是標(biāo)準(zhǔn)通用標(biāo)記語(yǔ)言SGML的子集,又是由W3C組織發(fā)布的,因此XML正逐漸成為信息世界數(shù)據(jù)交換的標(biāo)準(zhǔn)。在Web應(yīng)用中的數(shù)據(jù)存儲(chǔ)、應(yīng)用程序的配置文件、應(yīng)用程序之間數(shù)據(jù)共享等凡是涉及數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)交換的領(lǐng)域都有XML的身影。面對(duì)多變的客觀世界,數(shù)據(jù)的不確定性在加工數(shù)據(jù)的同時(shí)也要被考慮到。由于XML技術(shù)的發(fā)展以及XML自身所具有的各種優(yōu)點(diǎn),使用XML來(lái)存儲(chǔ)不確定性

2、數(shù)據(jù)已經(jīng)成為當(dāng)前趨勢(shì)。利用XML文檔來(lái)保存數(shù)據(jù)及數(shù)據(jù)的概率,這種形式的XML叫做不確定XML,針對(duì)不確定XML的查詢已經(jīng)成為當(dāng)前研究熱點(diǎn)。
　　二元結(jié)構(gòu)連接和整體匹配是當(dāng)前小枝模式匹配領(lǐng)域中常使用的方法。但二元結(jié)構(gòu)連接過程中的部分結(jié)果是沒有意義的,這樣無(wú)意義的結(jié)果對(duì)查詢速度有著很大的約束?；谡w匹配的方法由于查詢過程過于集中,不方便進(jìn)行概率閾值過濾,無(wú)法高效地利用概率閾值過濾來(lái)提高查詢效率。由于當(dāng)前不確定XML小枝模式查詢處理方

3、法存在著缺陷,本文將基于序列匹配的方法應(yīng)用到不確定XML查詢。通過改進(jìn)LCS-TRIM算法提出了基于序列的不確定XML小枝模式匹配算法PrTRIM以及H-PrTRIM。
　　不確定XML文檔與普通XML文檔相比,具有額外概率信息,因此在查詢同時(shí)還需要正確地處理這些概率信息。本文中PSI索引由于存儲(chǔ)了結(jié)構(gòu)信息,因此可以對(duì)互斥分布節(jié)點(diǎn)來(lái)進(jìn)行識(shí)別。PSI索引中的內(nèi)容信息可以進(jìn)行實(shí)例樹概率的計(jì)算,這樣XML文檔中存儲(chǔ)數(shù)據(jù)的概率就可以被準(zhǔn)確

4、處理。PSI索引在查詢中也發(fā)揮著重要的作用。
　　不確定XML的查詢結(jié)果沒有必要全部保留,這是因?yàn)榈透怕式Y(jié)果對(duì)于一些實(shí)際應(yīng)用沒有意義。這樣就可以考慮在查詢中設(shè)置一個(gè)閾值來(lái)去掉部分不符合要求的結(jié)果。概率閾值是查詢時(shí)給出的一個(gè)概率值,意義是要求查詢結(jié)果的概率值都大于等于給出的概率閾值。本文在查詢同時(shí)加入三次概率閾值過濾策略,可以確保查詢結(jié)果符合概率閾值,同時(shí)又能提高查詢效率。
　　實(shí)驗(yàn)主要通過PrTRIM算法與H-PrTRIM算