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

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

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

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

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

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