一種基于Dewey編碼的XML小枝模式匹配方法.pdf

1、近幾年來，隨著數據庫和網絡技術的迅速發(fā)展，XML（可擴展標記語言）已成為Web上數據表示、集成和交換的標準。相比其它的標記語言，XML的格式簡單、自我描述能力強，實現了內容、結構和表現三者的分離，更適合于數據表示和交換，因此XML在科學研究、電子商務等各個領域得到了廣泛的使用。今天Web上已經涌現了大量的XML數據，所以如何對XML文檔進行有效地查詢已成為當今數據庫領域的一個重要的研究課題。
　　查詢XML文檔，目前國內外提出的算

2、法主要是基于以下兩種思想:第一種是路徑分解法，它把將要查詢的路徑表達式分解成多個簡單路徑表達式，然后再進行匹配，最后將中間結果連接起來。這種方法不可避免地要產生許多無用的中間結果。另一種是小枝模式匹配方法，它將查詢表達式用樹的形式建模，稱為“小枝模式”(twigpattern)，再將小枝模式到XML文檔樹中進行匹配，通過掃描一遍輸入結點列表就可得到所有的輸出結果。這種方法使得算法的I/O代價、CPU時間復雜度和空間復雜度都大大降低，從而

3、提高了查詢的效率。目前具有代表性的小枝模式匹配算法有TwigStack和TJfast等。但是，對于包含較多父子邊的查詢語句這些算法并不是最優(yōu)的，同時這些算法的一個共同點就是它們并沒有利用XML文檔的路徑索引。
　　為了進一步提高小枝模式匹配算法的效率，本文利用了XML文檔的路徑索引JoinGuide，提出了一種新的基于Dewey編碼的小枝模式匹配方法TwigJoin，主要工作如下:
　　(1)綜合區(qū)域編碼和前綴編碼的優(yōu)點對X

4、ML文檔進行了編碼，對于文檔中的實例結點我們使用了前綴編碼方案，而對XML文檔的路徑索引JoinGuide使用了區(qū)域編碼的方案。
　　(2)對小枝模式匹配算法TwigStack進行了改進，先使用TwigStack算法在XML文檔的索引圖JoinGuide上得到預匹配結果，然后再掃描預匹配結果中的葉子實例結點序列得到所需的查詢結果。
　　(3)在理論上和TwigStack和(Ⅰ)-XISS系統(tǒng)進行了詳細的對比分析，說明了Twi

5、gJoin小枝模式匹配方法的優(yōu)點。
　　(4)最后構建了一個實驗系統(tǒng)，實現了提出的小枝模式匹配方法，然后通過實驗把TwigJoin同TwigStack和(Ⅰ)-XISS進行了對比，結果表明本文提出的小枝模式匹配方法的效率有了較大的提高。
　　今后的工作是，首先要提高TwigJoin系統(tǒng)中解析和建立路徑索引的效率，然后再完善TwigJoin系統(tǒng)中的查詢算法，增加TwigJoin系統(tǒng)中對XPath查詢語言中各種軸的查詢能力，以使