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

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

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

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