基于序列的不確定XML索引和查詢處理技術(shù)研究.pdf

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

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

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

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