基于小枝模式匹配的XML數(shù)據(jù)查詢處理算法研究.pdf

1、隨著因特網(wǎng)的飛速發(fā)展,半結(jié)構(gòu)化式的Web數(shù)據(jù)大量涌現(xiàn),使得HTML標記語言已經(jīng)不能滿足用戶日益增長的需求,XML作為一種自描述的半結(jié)構(gòu)化數(shù)據(jù)為Web數(shù)據(jù)管理提供了新的數(shù)據(jù)模型,得到了廣泛的應用,并已發(fā)展成為Internet上數(shù)據(jù)表示和交換的事實上的標準。但由于XML本身是一種嵌套的樹型結(jié)構(gòu),如何從大量的XML數(shù)據(jù)源中查找感興趣的信息成為XML數(shù)據(jù)庫研究領(lǐng)域的一大熱點。小枝模式整體匹配是XML查詢處理方法中效率較高的一種,近年來相繼出現(xiàn)了

2、許多小枝模式整體匹配算法,例如TwigStack、TJFast、TwigList和TwigNM算法等。這些方法對于只包含祖先-后代關(guān)系的查詢效率很出色,但它們要按序遍歷輸入數(shù)據(jù)流中的每一個元素結(jié)點,對于那些很顯然不會構(gòu)成匹配的元素結(jié)點仍然在掃描和判斷范圍之內(nèi),當要掃描的標簽流較長時,需要花很長的時間,而且對于含有父子關(guān)系的查詢,它們的查詢效率并不高。另外,這些算法只能滿足無序查詢的需求,對于含有有序軸的Xpath表達式查詢無法實現(xiàn)。

3、r>　　 本文對XML路徑查詢處理中尚存在的問題進行了深入研究,在汲取了各種小枝模式匹配算法優(yōu)點的基礎(chǔ)上,針對目前算法存在的不足,研究了兩種有效的非歸并整體匹配算法TwigTL和OrderedTwigPM。主要內(nèi)容包括：⑴研究一種有效的小枝模式匹配算法TwigTL,該算法使用Tag+Level流模型,并在進行查詢處理之前先進行無用數(shù)據(jù)層的剪枝,以減少待處理結(jié)點的數(shù)目,縮短處理時間；⑵為了支持有序小枝模式查詢,研究一種新的整體匹配算法O