摘 要： 設計了一種新的基于XML的關系數據映射索引技術，利用域關系樹解決了DTD的不足，通過改進的XML Schema算法保持了關系數據間的語義約束，并在映射的XML標簽樹上建立了RPNL索引，實現了查詢代價的最小化O（n）。
關鍵詞： XML語言 關系數據 映射索引
1998年，XML被W3C推薦為Web數據交換的標準，標志著數據庫系統進入了XML網絡時代。但目前使用最廣泛的仍然是關系數據庫，因此，關系數據向XML文檔的異構映射及其優化索引就成為Internet數據集成技術的焦點之一。通過分析映射索引現狀，本文提出了一種新的基于XML的關系數據映射索引技術。針對DTD的不足，在域關系樹的基礎上設計了一套改進的XML Schema算法，并在映射的XML標簽樹上構造了RPNL索引，使基于RPNLTree的查詢代價降至O（n）。
1 基于XML的關系數據映射技術
目前，對關系模型向XML DTD文檔的轉換研究比較成熟。但DTD模式保守，數據類型有限，特別是異構過程中完全忽略了關系數據間語義約束的保持，沒有做到實體聯系的完整性映射。針對上述不足，本文在域關系樹的基礎上設計了一套改進的基于標準XML Schema的關系數據映射算法。
1.1 域關系樹
定義1 域D∷=L{e|D{e，|D}*}。其中，e表示結點；L表示路徑；{ }表示域空間。
第一層：域根層，有且僅有一個虛根結點Root。
第二層：域表層，由表Student、Course及箭頭Taking和Taken_by組成，反映了選課關系。其域關系表達式為：Student.taking
Course，Course.taken_byStudent，Student.taking→Course.taken_by。相應的語義解釋為：如果沿著Student邊到達結點α并且結點α有Taking邊通向結點β，則結點β一定有一條Taken_by邊通向結點α。
第三層：域屬性層，每個結點均標識其域表層直接父結點的一個屬性。
1.2 基于域關系樹的XML Schema映射算法
嚴格結構化的關系模型向具有明顯層次性的XML半結構化模型映射過程中，借助于域關系樹的“中間件”作用，極大地簡化了異構的處理。算法中XML術語的父/子關系是關系術語的子/父關系。
算法1：以Student為例的算法過程
(1)設置域屬性元素。依次為域屬性層結點創建域屬性元素Ri-AttType及其屬性類型。如果值可以取NULL，則令其標識nillable等于ture。
<complextype name=″Student-AttType″>
<sequence>
<ELEMENT name=″Sno″ type=″string″/>
<ELEMENT name=″Sname″ type=″string″ nillable=″ture″/>
</sequence>
</complextype>
(2)設置域表元素。分別為域表層實體創建域表元素Ri-TabType，并令其域空間內的域屬性元素類型為xsd：Ri-AttType。同時設置域表元素minOccurs屬性為0，maxOccurs屬性為unbounded。
<complextype name=″Student-TabType″>
<sequence>
<ELEMENT name=″Student″ type=″xsd：Student-
AttType″ minOccurs=″0″ maxOccurs=″unbounded″/>
</sequence>
</complextype>
(3)創建庫元素。首先在XML Schema文檔中設置庫元素Ri-DB，然后依次添加庫表元素Ri-Tab及其域空間內的元素類型xsd：Ri-TabType。
<ELEMENT name=″Student-DB″>
<complextype>
<sequence>
<ELEMENT name=″Student-Tab″ type=″xsd：Student-TabType″/>
</sequence>
</complextype>
(4)設置主/外鍵。如果域屬性層結點是主屬性，則要插入主鍵標識Ri-PriKey。對于域表層實體間的聯系則通過設置外鍵來完成，并指明其參照域xsd:Ri-ForKey。在域空間內，分別為主/外鍵添加selector xpath和field xpath。
<key name=″Student-PriKey″>
<selector xpath=″xsd：Student-Tab/xsd：Student″/>
<field xpath=″@Sno″/>
</key>
<keyref name=″Course-Cno″ refer=″xsd：Student-ForKey″>
<selector xpath=″xsd：Course-Tab/xsd：Course″/>
<field xpath=″@Cno″/>
</key>
此算法已經在一個網上選課系統中得到了驗證，該系統的后臺數據庫采用Oracle。
2 基于XML的關系數據RPNL索引技術
目前已經提出的XML數據庫索引機制有基于Trie樹的索引Index Fabric、Stanford大學Lore系統的DataGuides、XISS系統索引方案、基于DOM模型的索引、基于共享根結點的索引Rist、基于結構的Join索引和基于路徑的索引等。其中較具代表性的是基于結構的Join索引和基于路徑的索引。但這二種方法的不足之處是查詢處理代價高于O(n)。因此，本文在XML標簽樹的基礎上設計了RPNL(Reverse Polish Notation Link逆波蘭鏈)索引，將查詢代價控制在O（n）。
2.1 XML標簽樹
圖2所示的XML標簽樹是利用XML Schema的樹狀層次性，借鑒半結構化模型OEM的表示形式建立的。其構造方法如下：
(1)每一個域屬性元素分別對應于XML標簽樹上的一個結點，帶方框的$表示父結點，圓圈表示子結點。
(2)在XML標簽樹中，元素-元素、元素-屬性之間的父-子關系均用相應名字的邊來標識。
2.2 基于XML標簽樹的RPNL索引
定義3 形如(L1D1L2D2……LnDn)的字符串稱為數據路徑。(L1L2……Ln)稱為語義路徑，(D1D2……Dn)稱為數據值。其中Li和Di（i=1，2，……n）分別表示標簽樹的邊和結點。
分析圖2，結點1、結點2具有相同的語義路徑{Student.Sno}，結點5、結點6具有相同的語義路徑{Student.Course.Cname}……由此可知：XML標簽樹中存在若干具有不同值但具有相同語義路徑的結點，即同一語義路徑可對應多個不同的數據值。于是，將具有相同語義路徑不同數據值的結點聚合在同一結點中，并在盡可能少的步驟內快速定位到目的結點，便是索引優化的關鍵技術。本文提出的基于XML標簽樹的索引，在語義路徑上特別設置了結點的RPNL，同時利用Hash表保存索引結點的RPNL指針。實驗證明，此方法能夠將順序查找的代價由O(n2)降至加了RPNL索引的O(n)。
定義4 設XML標簽樹中結點A的數據路徑為αβ，其中α為基本單元。若存在結點B的數據路徑β，則有一指針自結點A指向結點B，該指針稱為結點A的RPNL。
定義5 RPNLTree（逆波蘭鏈索引樹）中，聚合在同一結點A內的具有相同語義路徑不同數據值的結點集，稱為結點A的擴展集。
根據定義4、定義5并結合圖3(a)，給出了在XML標簽樹上構造RPNL索引(圖3（b）)的算法，稱為算法2。
算法2：在XML標簽樹上構造RPNL索引
約定： （1）p[i]←Li1Li2……Lin表示結點i的語義路徑（i=1，2，……n）。
(2)一層虛根Root的RPNL為NULL，二層子結點的RPNL均指向Root。
Input： TAGTree Output： RPNLTree
算法步驟：
(1)初始化。RPNLTree中有且僅有一個根{$Root}，令指針p←RPNLTree.root。
(2)從Root開始前序遍歷TAGTree，首先得到邊Student及結點{$1}，在RPNLTree中創建結點{$1}，并使p所指結點Root有一條邊Student指向結點{$1}。由于{$1}是根結點的孩子，所以需創建一條由{$1}指向Root的RPNL，最后令指針p指向{$1}。
(3)繼續遍歷TAGTree，得邊Course及結點A（擴展集為{$3}），并使Course自{$1}(由p所指)指向A。
(4)判斷p所指結點是否存在RPNL。若存在，則訪問RPNL所指結點N(當前是Root)，并創建新邊Course和新結點B（擴展集為{$3}），使Course自N指向{$3}，然后令A的RPNL指向B。
(5)檢查N中是否有RPNL指向下一個結點。如果有，使N標記該新結點，依次重復(3)(4)，直到沒有可以創建RPNL的新結點并且N的RPNL指向根結點，中止遍歷所得邊和結點（當前是Course和{$3}）。
(6)令p指向結點B，即遍歷所得當前結點路徑(Student.Course)所對應RPNLTree結點。
圖4是依據算法2對圖2中XML標簽樹構造的RPNLTree，其中虛線表示當前結點的RPNL。
由定義4、定義5及RPNLTree的構造過程，可得以下引理：
引理1 利用RPNL索引查詢語義路徑為L1L2……Ln的結點，若存在，則其擴展集即為查詢結果。
引理2 從RPNLTree根結點出發，查詢長度為n的字符串p，其查詢代價為O(n)。
引入RPNL索引技術的關鍵是：當遍歷得到邊L及結點A時，只需從p所指的當前結點開始沿著RPNL進行新結點、邊的構造，無需進行全程重復查找（根除外），以此來提高查詢速度，降低處理代價。
2.3 實驗結果
這里選取應用廣泛的路徑索引[6]作為RPNL索引查詢性能的對比分析。實驗的硬件環境為：CPU選用Pentium4 2.4，RAM為256MB；軟件環境為：操作系統選用Windows XP，數據集為DBLP。圖5為實驗結果。從圖5的趨勢曲線可以看出，隨著測試數據量的增大，路徑索引的查詢時間呈指數增長，而RPNL索引的查詢時間則基本是線性增長。再由引理1、引理2可證，RPNLTree的查詢處理代價為O(n)，即在相同條件下，RPNL索引技術的查詢效率優于其他索引。限于篇幅，與其他索引實驗結果的對比分析省略。
3 總 結
本文設計了一種新的基于XML的關系數據映射索引技術。通過對DTD不足的分析，在保持關系數據語義約束的基礎上，提出了一套改進的XML Schema算法，并利用XML文檔的層次性，構造了XML標簽樹，設計了RPNL索引，實現了基于RPNLTree的查詢代價最小化O（n）。
參考文獻
1 Bourret R.Mapping DTDs to Databases.http：//www.xml.com/pub/a/2001/05/09/dtdtodbs.html
2 Goldman R，Widom J.DataGuides：Enabling query formulation and optimization in semistructured databases.In：The 23re VLDB Conf Athens，Greece，1997
3 賈福林，王國仁，于戈.基于DOM的XML數據庫的索引技術研究.計算機研究與發展，2004
4 Wang H X，Park S ，Fan W et al.ViST：A Dynamic Index Method for Querying XML Data by Tree Structures.In： proceedings of ACM SIGMOD Conference，San Diego，CA， 2003
5 Srivastava D，Al-Khalifa S，Jagadish H V et al.Structural joins：A primitive for efficient XML query pattern matching.In：Proc of the 18th Int′l Conf on Data Engineering (ICDE′02).San Jose：IEEE Computer Society Press，2002
6 Goldman R，Widom J.DataGuides：Enabling query formulation and optimization in semistructured datavases.In：Proc of the 23rd Int′l Conf on Very Large Databases(VLDB′97). San Francisco：Morgan Kaufmann，1997