基於關係型資料庫引擎的"XML"索引技術

xml(可擴展標記語言)已成為Web應用中資料表示和資料交換的標準,隨著Internet的快速發展,尤其是電子商務，Web服務等應用的廣泛使用,XML類型的資料成為當前主流的數據形式。因此XML資料的管理技術尤其是XML資料查詢技術成為當前的研究熱點。

比起關係型數據，XML有著各種不同的優點，但有個最大的缺陷就是它的效率。因為關係型資料檔案中，資料的欄位名稱只需出現一次即可，而XML資料檔案中，元素名稱會重複出現，這必須會影響到查詢的效率。為了盡可能的提高XML的查詢效率，需要為XML類型提供了索引功能。

萬維網聯盟於2007年1月23日將XPath2.0和XQuery1.0確定為建議標準，結束了先前各種查詢語言群雄逐鹿的局面。 基於此標準， 除傳統廠商外，各科研機構紛紛提出了對XPath和XQuery的實現(文獻中提及的有十數種)，其存儲模型不同，查詢算法各異，優化途徑也各有所長，在這樣的背景下，達夢資料庫公司根據自身發展策略，也提出了自己的XML查詢引擎模型，目前，達夢的XML查詢引擎正在緊張開發中，而對XML資料建立有效的索引是影響XML資料查詢效能的重要因素。在深入分析目前已有的資料庫產品的索引技術基礎上為達夢XML查詢引擎設計一種較為合理的索引結構，以使該引擎能發揮較優效能。

XML索引技術簡介

目前，人們對XML的研究主要分為兩個面向。一個是對XML這種半結構化資料的儲存、查詢和管理的的原生資料庫，其中的資料和元資料完全採用XML結構表示，與其底層的資料儲存格式(如物件模型、關聯模型等)無關。另一個是它與關聯式資料庫之間的相互轉換，利用關聯式資料庫的成熟技術對XML資料進行處理。由於後一個方向比較有現實意義，因此成了XML研究中的重點。

而除了儲存方案之外，索引技術也是決定一個資料庫系統最重要的因素之一。如果對XML文件不建構索引結構，那麼針對XML資料的任何查詢都很可能導致對整個文件樹的遍歷，隨著XML資料集的增大，這種開銷是不可忍受的。故此，對XML索引技術的研究具有較高的理論與實用價值。

雖然傳統的索引技術經過長期的積累已經相對成熟，但是，這類索引技術針對的主要是根據值(而不是具有某種關係的模式)定位數據記錄的功能，不太關注資料記錄間的邏輯關係;而XML 資料查詢的基本特徵就是根據模式特徵(正則路徑表達式形式描述的結構關係)的輸入提取符合該模式的數據，所以，XML 索引的主要內容就是設計適用於模式匹配的技術。

XML索引分類

基於路徑的XML索引

基於路徑的索引是以XML樹結構中節點的路徑資訊為基礎，採取某種約簡方式，使得約簡後的樹狀結構只維護不同的路徑訊息，而不會存在兩個具有相同路徑的節點。 已經提出的這類索引有：DataGuides索引、Index Fabric索引、XML資料的自適應路徑索引(Adaptive Path Index for XML Data， APEX )

Dataguides 索引是從根結點為起始的精練路徑的一種結構摘要。邊標籤串聯在一起形成的字串路徑在 Dataguides 中只描述一次。 Dataguides 減少了遍歷路徑查詢時所需的部分結點，它對從根部遍歷 XML文件是有效的。但對於含有通配符的路徑查詢或對帶有XPath標準中定義的descendant-or-self軸的路徑查詢要進行多次的連接操作，查詢效率較低，並且存在資料冗餘。

然後寫關於這2個大字段的java物件檔案TestLob.java，分別定義類型為CLOB和BLOB屬性欄位為String和byte[]類型，其中由於CLOB是處理大文字類型所以它對應了Java中的String類型，BLOB是處理一些以二進位流形勢儲存的沒有嚴格定義的大檔案所以讓它使用byte[]類型，然後分別定義這2個屬性的Getter和Setter方法，相關程式碼如下:

Dataguides 索引是從根結點為起始的精練路徑的一種結構摘要。邊標籤串聯在一起形成的字串路徑在 Dataguides 中只描述一次。 Dataguides 減少了遍歷路徑查詢時所需的部分結點，它對從根部遍歷 XML文件是有效的。但對於含有通配符的路徑查詢或對帶有XPath標準中定義的descendant-or-self軸的路徑查詢要進行多次的連接操作，查詢效率較低，並且存在資料冗餘。

Index Fabric是一種在Patricia Trie樹上發展而來的索引結構，它把到每個元素節點的每條標記路徑都用一個字串編碼，再將這些編碼值插入到Patricia Trie樹中去，從而將按照路徑方式對XML資料的查詢轉換為對字串的查詢。在查詢時先將查詢路徑編碼成字串的形式，然後再在索引樹中進行尋找。 Index Fabric索引優點是儲存了XML資料的層次結構訊息，統一處理了有模式和無模式資訊情況下的XML資料的檢索，並且使對XML資料的查詢和更新所需的時間與層次相關而不是與索引關鍵字的長度相關。 Index Fabric索引的缺點在於遺失了元素節點間的結構關係，因為它只保留了有文字值的元素節點的資訊。因此，與DataGuides索引類似，Index Fabric索引處理帶有XPath標準中定義的descendant-or-self軸的部分匹配查詢表達式效率不高

為此，APEX[14]引入了依賴於XML資料查詢分佈的資訊:將經常出現的XML查詢語句對應的標籤節點預先保存在一個雜湊結構中。它的作用類似於Cache的功能:當有新的查詢要求處理時，首先在哈希表中搜尋是否有滿足的節點集合。但它對於帶有元素值或屬性值的查詢表達式的處理效率較低。

基於節點的索引

基於節點的索引本質上即是將XML資料分解為資料單元的記錄集合，同時在記錄中保存該單元在XML資料中的位置資訊。與基於路徑的索引不同，基於節點的索引打破了必須透過標籤路徑尋找節點此限制，將XML資料分解成規範形式的節點記錄。由於保存了節點的位置信息，並且能夠很好地結合到成熟的關係資料庫管理系統中，因此它是目前應用最廣泛的索引。

根據對位置資訊的編碼方式不同，基於節點的索引一般可以分為一下幾類：

1. 基於前綴的索引

基於前綴的索引主要是根據Dewey[12]編碼產生的索引，文獻[13]的ORDPATH 編碼採用的也是類似的方法,並給出了壓縮ORDPATH的方法，該方法已應用於SQL Server 2005的索引組織中。

前綴編碼的基本思想是直接將一個節點的雙親節點的編碼作為該節點編碼的前綴，對於前綴編碼，要判斷一個節點v是否另一個節點u的後裔，只要判斷u的編碼是否v的編碼的前綴。前綴編碼索引的一個重要性質是它們的字典有序：以節點r為根的子樹中的任一個節點u，它的前綴編碼c(u)大於（小於）它的左兄弟子樹（右兄弟子樹）中所有節點的前綴編碼。因此，基於前綴的索引不僅能夠有效地支援包含關係的運算，而且能夠有效地支援文件位置關係的計算。

2. 基於區間編碼的索引

對於區間編碼索引,樹T中的每一個結點被賦予一個區間編碼[begin,end],滿足:一個結點的區間編碼包含它的後裔結點的區間編碼.也就是說，樹T中的節點u是節點v的祖先，當且僅當start(u)

第一個區間編碼方案是Dietz編碼,樹T中的每一個結點被賦予一個具有先序遍歷序號和後序遍歷序號的二元組.由於樹T中的一個祖先結點u在先序遍歷(後序遍歷)中必然出現在它的後裔結點v之前(之後),因此, 節點u和v是祖先/後裔關係,當且僅當PRe(u)

#另一個區間編碼索引的典型例子是XISS索引，它為每個節點賦予一個數字對，其中order為擴展的前序編碼，size為節點的子孫的範圍。對一文檔樹中的任意節點X和Y，當且僅當order(x)

XISS索引透過將原始查詢語句分解為子表達式。然後分別針對這些子運算式實作查詢，最後對這些中間結果進行聯結以獲得查詢結果集。從而能較好地支援含通配符的查詢語句。不過，它是對每一個中間結果進行聯結後得到最終查詢結果。雖然這樣一種方法的確能夠解決所有的通配符問題，可是，這種中間結果的聯結很有可能是非常耗時的，特別是對於長路徑的簡單表達式。

兩種索引機制的比較

基於路徑的索引主要基於節點合併的策略，透過節點等價、路徑等價等技術，得到比原始文件小得多的索引結構，它的結構仍然是樹型的，所以在處理查詢時，基本上仍須遍歷整個索引樹才能得到結果。基於路徑的索引可以很好地支援簡單路徑表達式的查詢，但是對於正規路徑表達式，它效果不是很理想。

基於節點的索引透過編碼技術索引每一個節點，節點之間的結構關係透過編碼可以在常數時間內確定它可以很好地支援正則路徑表達式，但是對於長的路徑表達式，尤其是在查詢產生的中間結果很多的時候，節點索引的連接操作代價高昂。

基於路徑的索引和基於節點的索引各有優缺點，但可以優勢互補。目前在實際應用中，基於節點的索引應用更為廣泛，研究得也比較成熟，因此，達夢公司有關XML索引結構研究主要以基於節點的索引為主，並適當參考基於路徑的索引加以改進。

 以上就是基於關係型資料庫引擎的"XML"索引技術的內容，更多相關內容請關注PHP中文網（www.php.cn）！

#