XML文檔小枝模式匹配查詢算法研究.pdf

1、由于XML具有自描述性和可擴(kuò)展性等特點(diǎn)，能夠滿足WEB上對(duì)數(shù)據(jù)描述和存儲(chǔ)的需求，因而使得XML正在成為Web上數(shù)據(jù)表示和交換的事實(shí)上的標(biāo)準(zhǔn)。隨著XML格式數(shù)據(jù)的快速增長和廣泛應(yīng)用，對(duì)XML數(shù)據(jù)的查詢、轉(zhuǎn)換和存儲(chǔ)的研究受到了廣泛關(guān)注。在XML文檔的查詢技術(shù)研究中，基于小枝模式匹配的結(jié)構(gòu)連接查詢是關(guān)鍵的核心內(nèi)容。對(duì)于XML結(jié)構(gòu)查詢，可以對(duì)XML文檔樹中的結(jié)點(diǎn)或邊進(jìn)行編碼，通過編碼直接判斷結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系，而無需對(duì)原XML文檔樹進(jìn)行遍歷，從

2、而將XML結(jié)構(gòu)查詢的計(jì)算轉(zhuǎn)化為結(jié)構(gòu)連接的計(jì)算。目前對(duì)XML文檔的編碼方法有區(qū)間編碼、路徑編碼、前綴編碼等。因此，隨著不同編碼方案的研究，各種相應(yīng)的結(jié)構(gòu)查詢算法也提了出來。對(duì)于XML文檔基于結(jié)構(gòu)連接的小枝模式匹配查詢，是從文檔樹中查找與查詢模式匹配的結(jié)點(diǎn)，然后將查找到的匹配結(jié)果再組裝成最終符合查詢表達(dá)式的完整樹結(jié)構(gòu)。
　　TwigStack是一個(gè)典型的關(guān)于小枝模式匹配的結(jié)構(gòu)連接查詢算法。它采用鏈棧的數(shù)據(jù)結(jié)構(gòu)作為緩存，對(duì)查詢節(jié)點(diǎn)流進(jìn)行

3、整枝計(jì)算，從而避免了無用中間結(jié)果的產(chǎn)生?；诖怂惴?，又提出了一系列改進(jìn)的算法。其中Twig2Stack和TwigList算法分別采用層次關(guān)系的堆棧結(jié)構(gòu)和列表結(jié)構(gòu)，避免了復(fù)雜的歸并過程，進(jìn)一步提高了查詢效率。在我們對(duì)小枝模式匹配查詢的研究中，發(fā)現(xiàn)TwigStack算法對(duì)查詢節(jié)點(diǎn)流在結(jié)束時(shí)的處理上存在著不足;在對(duì)TwigList算法的分析中，發(fā)現(xiàn)可以將XML文檔的SAX解析應(yīng)用于查詢過程，從而避免了對(duì)XML文檔進(jìn)行編碼，能進(jìn)一步提高查詢效率

4、。
　　本文的主要工作是:
　　(1)提出了BSTwigStack小枝模式匹配查詢算法。該算法增強(qiáng)了原有的TwigStack算法，給出了XML文檔在查詢節(jié)點(diǎn)流結(jié)束時(shí)的查詢匹配處理策略。
　　(2)提出了BSTwigList小枝模式匹配查詢算法。針對(duì)XML文檔的結(jié)構(gòu)特點(diǎn)，在結(jié)合XML文檔的基于事件的SAX解析方式的基礎(chǔ)上，改進(jìn)了TwigList算法。BSTwigList算法能夠應(yīng)用于節(jié)點(diǎn)流模式的小枝查詢，在文檔解析的同時(shí)

5、可以進(jìn)行模式匹配查詢，避免了以往查詢算法需要先對(duì)文檔節(jié)點(diǎn)進(jìn)行編碼索引的步驟，使得XML文檔在更新時(shí)，無需對(duì)編碼文件進(jìn)行重新編碼和維護(hù)，從而減少了查詢所需的存儲(chǔ)空間，提高了查詢效率。
　　(3)最后通過對(duì)算法進(jìn)行的實(shí)驗(yàn)和數(shù)據(jù)測試，給出了算法查詢時(shí)間響應(yīng)及性能分析圖表，進(jìn)一步驗(yàn)證了改進(jìn)的查詢算法的有效性。
　　在對(duì)以上算法的研究和實(shí)現(xiàn)當(dāng)中，本文所研究的只是XPath查詢的一個(gè)片段，對(duì)于其他形式的XPath查詢，仍然有待于進(jìn)一步的