XML小枝模式查詢處理技術研究.pdf

1、隨著在電子商務、數(shù)字圖書館以及WEB服務等各領域大規(guī)模的應用和傳播，XML已經(jīng)成為數(shù)據(jù)表示和交換的新標準。全世界XML文檔的數(shù)量正在以驚人的速度增長。與此同時，如何有效的管理和檢索日益增長的XML數(shù)據(jù)，已成為數(shù)據(jù)庫領域的一個熱點問題并得到了廣泛關注和研究。
　　 本論文聚焦于XML小枝模式查詢處理技術研究。XML小枝模式查詢是眾多XML查詢語言的核心子集，其主旨是在XML文檔樹中搜索以得到所有匹配樹狀結(jié)構(gòu)查詢模式的結(jié)果。XML小

2、枝模式查詢處理被認為是XML數(shù)據(jù)查詢中的一個核心操作，在XML數(shù)據(jù)管理中占有非常重要的地位。由于XML半結(jié)構(gòu)化以及小枝模式查詢多樣性、復雜性等特點，傳統(tǒng)的數(shù)據(jù)庫技術已經(jīng)不能適應高效處理XML小枝模式查詢的需求，而現(xiàn)有研究在XML索引、小枝模式查詢匹配算法、查詢優(yōu)化等關鍵技術上都還存在缺陷，并且至今仍缺乏一個通用的模型可以描述各種類型XML小枝模式的查詢處理過程。因此，XML小枝模式查詢處理仍是XML數(shù)據(jù)檢索領域一個非常重要且極富挑戰(zhàn)性的

3、研究課題。
　　 本文著重解決XML小枝模式查詢處理中的核心問題，研究XML索引、小枝模式查詢重寫、小枝模式選擇度估計、代價估計模型、多種類型小枝模式查詢匹配算法等一系列關鍵技術，并綜合以上研究成果，提出了一個統(tǒng)一的XML小枝模式查詢處理框架。本文的主要貢獻和創(chuàng)新總結(jié)如下：
　　 統(tǒng)一的XML小枝模式查詢處理框架
　　 在分析XML數(shù)據(jù)模型、小枝模式查詢結(jié)構(gòu)特征的基礎上，本文提出了一個統(tǒng)一的XML小枝模式查詢處理

4、框架。該框架基于多層次的索引管理模型，集成多種小枝模式查詢匹配算法，并根據(jù)一系列啟發(fā)式優(yōu)化規(guī)則選擇最優(yōu)的算法，提供綜合、高效的小枝模式查詢處理服務。圍繞整個框架，本論文還就基于路徑連接的簡單小枝模式查詢匹配、復雜小枝模式查詢處理以及基于索引的空間跳躍等關鍵技術進行了深入研究，并分析了這些技術在框架中的具體應用：
　　 基于路徑連接的簡單小枝模式查詢處理技術研究
　　 在研究連接算法分解粒度的基礎上，提出了基于路徑連接的簡

5、單小枝模式查詢匹配算法TJFGeneric。該算法將小枝模式分解成多條查詢路徑，通過自低向上的路徑連接過程實現(xiàn)簡單小枝模式查詢的整體匹配，減少了連接操作的數(shù)目并且只訪問查詢?nèi)~節(jié)點對應的元素。在此基礎上，研究了路徑連接算法的節(jié)點編碼方案。為了能支持多種編碼方式，采用標準化的接口，提高了算法的通用性。
　　 有序小枝模式查詢的整體路徑連接技術研究
　　 分析有序小枝模式的結(jié)構(gòu)特征，提出自低向上的有序小枝模式整體路徑連接算法O

6、TJFast。算法引入一種新的數(shù)據(jù)結(jié)構(gòu)--子節(jié)點鏈接堆棧組(CLS)，通過構(gòu)建及檢查CLS的內(nèi)容，在路徑連接過程中判斷元素間的順序關系，實現(xiàn)有序小枝模式的高效查詢處理。實驗結(jié)果表明該算法具有I/O訪問少、查詢速度快等特點，并能有效處理包含各種順序軸的有序小枝模式查詢。
　　 帶邏輯或謂詞的小枝模式查詢整體路徑連接技術研究
　　 通過引入或分支擴展概念，提出了處理帶邏輯或謂詞小枝模式查詢的整體路徑連接算法ORTJFast。

7、算法自下而上遞歸的匹配以分支節(jié)點為根的查詢子樹，大大簡化了查詢處理過程，結(jié)合或分支擴展和路徑連接思想，實現(xiàn)帶邏輯或謂詞小枝模式查詢的整體處理。大量的實驗結(jié)果表明，ORTJFast算法在性能上要明顯優(yōu)于已有算法。
　　 基于空間跳躍的查詢加速技術研究
　　 結(jié)合空間跳躍技術，在上述研究的基礎上提出了相應的查詢加速算法。通過引入失配優(yōu)化、空數(shù)據(jù)流優(yōu)化和亂序優(yōu)化等優(yōu)化規(guī)則，加速類算法利用索引跳過那些明顯不參與最終結(jié)果的元素訪問