DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> XML學習教程 >> XML詳解
基於關系型數據庫引擎的 XML 索引技術探析
編輯:XML詳解     

XML(可擴展標記語言)已成為 Web 應用中數據表示與交換的事實標準。隨著網際網路快速發展,加上電子商務、Web 服務等應用普及,XML 資料已成為當前主流的數據形式,XML 數據的管理與查詢技術也因此成為研究熱點。

XML 的優勢與它的痛處

與關系型數據相比,XML 有各式各樣的優點,但有一個最大的缺陷:效率。關系型數據文件中,欄位名只需出現一次;而 XML 文件中元素名會反覆出現,冗餘直接拖累了查詢效率。因此,為 XML 數據提供合適的索引,是提升查詢效能的關鍵手段。

萬維網聯盟於 2007 年 1 月 23 日將 XPath 2.0 與 XQuery 1.0 確定為推薦標準,結束了此前各種查詢語言群雄逐鹿的局面。基於該標準,除傳統廠商外,各科研機構紛紛提出對 XPath 與 XQuery 的實現方案——存儲模型各異、查詢算法不同、優化途徑各有所長。在這樣的背景下,達夢數據庫公司也依自身發展戰略提出了自己的 XML 查詢引擎模型。而對 XML 數據建立有效索引,正是影響該引擎查詢性能的關鍵因素之一。

XML 索引技術簡介

目前對 XML 的研究大致分為兩個方向。一是面向這種半結構化數據的原生數據庫,數據與元數據完全以 XML 結構表示,與底層存儲格式(物件模型、關系模型等)無關。二是它與關系數據庫之間的相互轉換,借用關系數據庫的成熟技術來處理 XML。由於後者更具現實意義,遂成為研究重點。

除了存儲方案,索引技術也是決定資料庫系統好壞的核心因素之一。若完全不為 XML 文檔建立索引,任何查詢都可能導致對整棵文檔樹的遍歷;隨著數據集增大,這種開銷無法忍受。

值得注意的是,傳統索引技術雖已相當成熟,但它們主要解決的是「按值定位數據記錄」,不太關注記錄之間的邏輯關係。而 XML 查詢的特徵恰恰是「按模式特徵(以正則路徑表達式描述的結構關係)提取符合條件的數據」。所以 XML 索引的核心課題,是設計適用於模式匹配的技術。

XML 索引的兩大分類

基於路徑的索引

以 XML 樹結構中節點的路徑資訊為基礎,透過某種約簡方式,讓約簡後的樹只保留不同的路徑,不再出現兩個路徑相同的節點。已提出的方案包括 DataGuides、Index Fabric、APEX 等。

DataGuides 是一種從根節點起始的精簡路徑結構摘要,把邊標籤串接而成的字串路徑只描述一次。它減少了遍歷路徑查詢時需要訪問的部分節點,對「從根部遍歷」的查詢很有效。但遇到含通配符的路徑查詢,或帶 XPath 標準中 descendant-or-self 軸的查詢時,需要多次連接操作,效率偏低,且存在數據冗餘。

Index Fabric 由 Patricia Trie 發展而來。它把到每個元素節點的每條標記路徑都編成一個字串碼,再插入 Patricia Trie,於是「按路徑查詢 XML」就轉化為「查詢字串」。查詢時先把路徑編成字串,再到索引樹中查找。它的優點是存下了 XML 的層次結構資訊,統一處理了有模式與無模式兩種情況,且查詢與更新所需時間與層次相關,而非與索引關鍵字的長度相關。缺點則是丟失了元素節點之間的結構關係——它只保留了有文本值的元素節點。因此與 DataGuides 類似,處理帶 descendant-or-self 軸的部分匹配表達式時效率不佳。

APEX 引入了「依賴 XML 數據查詢分布」的資訊:把經常出現的查詢語句對應的標籤節點預先存進一個雜湊結構,作用類似 Cache——新查詢進來時先在雜湊表中搜尋是否有現成的節點集合。但它對帶元素值或屬性值的查詢表達式處理效率較低。

基於節點的索引

本質上是把 XML 數據分解為數據單元的記錄集合,同時在記錄中保存該單元在 XML 中的位置資訊。與路徑索引不同,它打破了「必須透過標籤路徑才能找到節點」的限制,把數據分解成規範形式的節點記錄。由於保留了位置資訊,又能與成熟的關系數據庫管理系統良好結合,這是目前應用最廣的一類索引。

依位置資訊的編碼方式不同,可分為兩類:

1. 基於前綴的索引

主要依據 Dewey 編碼生成,文獻中的 ORDPATH 編碼也採用類似方法並給出了壓縮方案,該方案已應用於 SQL Server 2005 的索引組織中。前綴編碼的思路是:直接把雙親節點的編碼作為該節點編碼的前綴。要判斷節點 v 是否為節點 u 的後裔,只需判斷 u 的編碼是否為 v 的編碼前綴。這類索引有一個重要性質——字典有序:以節點 r 為根的子樹中任一節點 u,其前綴編碼必定大於(小於)左兄弟子樹(右兄弟子樹)中所有節點的前綴編碼。因此它不僅能有效支持包含關係運算,也能有效支持文檔位置關係的計算。

2. 基於區間編碼的索引

為樹 T 中每個節點賦予一個區間編碼 [begin, end],並滿足:一個節點的區間編碼包含其所有後裔節點的區間編碼。也就是說,節點 u 是節點 v 的祖先,若且唯若 start(u) < start(v) 且 end(u) > end(v)。

最早的區間編碼方案是 Dietz 編碼,為每個節點賦予一個由先序遍歷序號與後序遍歷序號構成的二元組。由於祖先節點 u 在先序遍歷中必出現於後裔 v 之前、在後序遍歷中必出現於 v 之後,因此 u 與 v 為祖先/後裔關係,若且唯若 pre(u) < pre(v) 且 post(u) > post(v)。

另一個典型是 XISS 索引,為每個節點賦予一組數字:order 為擴展的前序編碼,size 為該節點子孫的範圍。對文檔樹中任意兩個節點 X 與 Y,X 是 Y 的祖先若且唯若 order(x) < order(y) 且 order(x) + size(x) > order(y) + size(y)。XISS 的做法是把原始查詢分解為子表達式,分別求值後再把中間結果連接起來,因此能較好地支持含通配符的查詢。但缺點也很明顯:所有中間結果都要做連接,對長路徑的簡單表達式而言,這種連接可能非常耗時。

兩種機制的取捨

基於路徑的索引主要採用節點合併策略,透過節點等價、路徑等價等技術,得到遠小於原始文檔的索引結構;其結構仍是樹形,查詢時基本上仍須遍歷整棵索引樹。它對簡單路徑表達式支持良好,但對正則路徑表達式效果並不理想。

基於節點的索引則為每個節點編碼,節點間的結構關係可在常數時間內判定,因此能很好地支持正則路徑表達式;但面對長路徑表達式、尤其是中間結果很多時,節點索引的連接代價相當高昂。

兩者各有優缺點,但可以優勢互補。目前實際應用中,基於節點的索引更為廣泛、研究也更成熟,因此達夢的 XML 索引結構研究以基於節點的索引為主,並適度參考基於路徑的索引加以改進。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved