摘  要： 設(shè)計(jì)了一種新的基于XML的關(guān)系數(shù)據(jù)映射索引技術(shù),，利用域關(guān)系樹解決了DTD的不足,，通過改進(jìn)的XML Schema算法保持了關(guān)系數(shù)據(jù)間的語義約束，并在映射的XML標(biāo)簽樹上建立了RPNL索引,，實(shí)現(xiàn)了查詢代價(jià)的最小化O（n）,。
關(guān)鍵詞： XML語言  關(guān)系數(shù)據(jù)  映射索引

　　1998年，XML被W3C推薦為Web數(shù)據(jù)交換的標(biāo)準(zhǔn),，標(biāo)志著數(shù)據(jù)庫系統(tǒng)進(jìn)入了XML網(wǎng)絡(luò)時(shí)代,。但目前使用最廣泛的仍然是關(guān)系數(shù)據(jù)庫,，因此，關(guān)系數(shù)據(jù)向XML文檔的異構(gòu)映射及其優(yōu)化索引就成為Internet數(shù)據(jù)集成技術(shù)的焦點(diǎn)之一,。通過分析映射索引現(xiàn)狀,，本文提出了一種新的基于XML的關(guān)系數(shù)據(jù)映射索引技術(shù)。針對DTD的不足,，在域關(guān)系樹的基礎(chǔ)上設(shè)計(jì)了一套改進(jìn)的XML Schema算法,，并在映射的XML標(biāo)簽樹上構(gòu)造了RPNL索引，使基于RPNLTree的查詢代價(jià)降至O（n）,。
1  基于XML的關(guān)系數(shù)據(jù)映射技術(shù)
　　目前,，對關(guān)系模型向XML DTD文檔的轉(zhuǎn)換研究比較成熟。但DTD模式保守,，數(shù)據(jù)類型有限,，特別是異構(gòu)過程中完全忽略了關(guān)系數(shù)據(jù)間語義約束的保持，沒有做到實(shí)體聯(lián)系的完整性映射,。針對上述不足,，本文在域關(guān)系樹的基礎(chǔ)上設(shè)計(jì)了一套改進(jìn)的基于標(biāo)準(zhǔn)XML Schema的關(guān)系數(shù)據(jù)映射算法。
1.1 域關(guān)系樹
　　定義1 域D∷=L{e|D{e,，|D}*},。其中，e表示結(jié)點(diǎn),；L表示路徑,；{ }表示域空間。

　　第一層：域根層,，有且僅有一個(gè)虛根結(jié)點(diǎn)Root,。
　　第二層：域表層，由表Student,、Course及箭頭Taking和Taken_by組成,，反映了選課關(guān)系。其域關(guān)系表達(dá)式為：Student.takingCourse,，Course.taken_byStudent,，Student.taking→Course.taken_by。相應(yīng)的語義解釋為：如果沿著Student邊到達(dá)結(jié)點(diǎn)α并且結(jié)點(diǎn)α有Taking邊通向結(jié)點(diǎn)β,，則結(jié)點(diǎn)β一定有一條Taken_by邊通向結(jié)點(diǎn)α,。
　　第三層：域?qū)傩詫樱總€(gè)結(jié)點(diǎn)均標(biāo)識其域表層直接父結(jié)點(diǎn)的一個(gè)屬性,。
1.2 基于域關(guān)系樹的XML Schema映射算法
　　嚴(yán)格結(jié)構(gòu)化的關(guān)系模型向具有明顯層次性的XML半結(jié)構(gòu)化模型映射過程中,，借助于域關(guān)系樹的“中間件”作用，極大地簡化了異構(gòu)的處理,。算法中XML術(shù)語的父/子關(guān)系是關(guān)系術(shù)語的子/父關(guān)系,。
算法1：以Student為例的算法過程
　　(1)設(shè)置域?qū)傩栽?。依次為域?qū)傩詫咏Y(jié)點(diǎn)創(chuàng)建域?qū)傩栽豏i-AttType及其屬性類型。如果值可以取NULL,，則令其標(biāo)識nillable等于ture,。
　　<complextype name=″Student-AttType″>
 　　　<sequence>
    　　　　<ELEMENT name=″Sno″ type=″string″/>
    　　　　<ELEMENT name=″Sname″ type=″string″ nillable=″ture″/>
　    　</sequence>
　　</complextype>
　　(2)設(shè)置域表元素。分別為域表層實(shí)體創(chuàng)建域表元素Ri-TabType,，并令其域空間內(nèi)的域?qū)傩栽仡愋蜑閤sd：Ri-AttType,。同時(shí)設(shè)置域表元素minOccurs屬性為0，maxOccurs屬性為unbounded,。
　　<complextype name=″Student-TabType″>
　　　 <sequence>
　　　　    <ELEMENT name=″Student″ type=″xsd：Student-
　　　　　　AttType″ minOccurs=″0″ maxOccurs=″unbounded″/>
　　　</sequence>
　　</complextype>
　　(3)創(chuàng)建庫元素,。首先在XML Schema文檔中設(shè)置庫元素Ri-DB，然后依次添加庫表元素Ri-Tab及其域空間內(nèi)的元素類型xsd：Ri-TabType,。
　　<ELEMENT name=″Student-DB″>
 　　　　<complextype>
    　　　　　<sequence>
    　<ELEMENT name=″Student-Tab″ type=″xsd：Student-TabType″/>
　　　    </sequence>
　　</complextype>
　　(4)設(shè)置主/外鍵,。如果域?qū)傩詫咏Y(jié)點(diǎn)是主屬性，則要插入主鍵標(biāo)識Ri-PriKey,。對于域表層實(shí)體間的聯(lián)系則通過設(shè)置外鍵來完成,，并指明其參照域xsd:Ri-ForKey。在域空間內(nèi),，分別為主/外鍵添加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>
　　此算法已經(jīng)在一個(gè)網(wǎng)上選課系統(tǒng)中得到了驗(yàn)證，該系統(tǒng)的后臺數(shù)據(jù)庫采用Oracle,。
2   基于XML的關(guān)系數(shù)據(jù)RPNL索引技術(shù)
　　目前已經(jīng)提出的XML數(shù)據(jù)庫索引機(jī)制有基于Trie樹的索引Index Fabric,、Stanford大學(xué)Lore系統(tǒng)的DataGuides、XISS系統(tǒng)索引方案,、基于DOM模型的索引,、基于共享根結(jié)點(diǎn)的索引Rist、基于結(jié)構(gòu)的Join索引和基于路徑的索引等,。其中較具代表性的是基于結(jié)構(gòu)的Join索引和基于路徑的索引,。但這二種方法的不足之處是查詢處理代價(jià)高于O(n)。因此,，本文在XML標(biāo)簽樹的基礎(chǔ)上設(shè)計(jì)了RPNL(Reverse Polish Notation Link逆波蘭鏈)索引,，將查詢代價(jià)控制在O（n）,。
2.1 XML標(biāo)簽樹
　　圖2所示的XML標(biāo)簽樹是利用XML Schema的樹狀層次性,，借鑒半結(jié)構(gòu)化模型OEM的表示形式建立的。其構(gòu)造方法如下：

　　(1)每一個(gè)域?qū)傩栽胤謩e對應(yīng)于XML標(biāo)簽樹上的一個(gè)結(jié)點(diǎn),，帶方框的$表示父結(jié)點(diǎn),，圓圈表示子結(jié)點(diǎn)。
　　(2)在XML標(biāo)簽樹中,，元素-元素,、元素-屬性之間的父-子關(guān)系均用相應(yīng)名字的邊來標(biāo)識,。
2.2 基于XML標(biāo)簽樹的RPNL索引
　　定義3 形如(L1D1L2D2……LnDn)的字符串稱為數(shù)據(jù)路徑。(L1L2……Ln)稱為語義路徑,，(D1D2……Dn)稱為數(shù)據(jù)值,。其中Li和Di（i=1，2,，……n）分別表示標(biāo)簽樹的邊和結(jié)點(diǎn),。
　　分析圖2，結(jié)點(diǎn)1,、結(jié)點(diǎn)2具有相同的語義路徑{Student.Sno},，結(jié)點(diǎn)5、結(jié)點(diǎn)6具有相同的語義路徑{Student.Course.Cname}……由此可知：XML標(biāo)簽樹中存在若干具有不同值但具有相同語義路徑的結(jié)點(diǎn),，即同一語義路徑可對應(yīng)多個(gè)不同的數(shù)據(jù)值,。于是，將具有相同語義路徑不同數(shù)據(jù)值的結(jié)點(diǎn)聚合在同一結(jié)點(diǎn)中,，并在盡可能少的步驟內(nèi)快速定位到目的結(jié)點(diǎn),，便是索引優(yōu)化的關(guān)鍵技術(shù)。本文提出的基于XML標(biāo)簽樹的索引,，在語義路徑上特別設(shè)置了結(jié)點(diǎn)的RPNL,，同時(shí)利用Hash表保存索引結(jié)點(diǎn)的RPNL指針。實(shí)驗(yàn)證明,，此方法能夠?qū)㈨樞虿檎业拇鷥r(jià)由O(n²)降至加了RPNL索引的O(n),。
　　定義4 設(shè)XML標(biāo)簽樹中結(jié)點(diǎn)A的數(shù)據(jù)路徑為αβ，其中α為基本單元,。若存在結(jié)點(diǎn)B的數(shù)據(jù)路徑β,，則有一指針自結(jié)點(diǎn)A指向結(jié)點(diǎn)B，該指針稱為結(jié)點(diǎn)A的RPNL,。
　　定義5 RPNLTree（逆波蘭鏈索引樹）中,，聚合在同一結(jié)點(diǎn)A內(nèi)的具有相同語義路徑不同數(shù)據(jù)值的結(jié)點(diǎn)集，稱為結(jié)點(diǎn)A的擴(kuò)展集,。
　　根據(jù)定義4,、定義5并結(jié)合圖3(a)，給出了在XML標(biāo)簽樹上構(gòu)造RPNL索引(圖3（b）)的算法,，稱為算法2,。

　　算法2：在XML標(biāo)簽樹上構(gòu)造RPNL索引
 　　約定： （1）p[i]←Li1Li2……Lin表示結(jié)點(diǎn)i的語義路徑（i=1，2,，……n）,。
　　(2)一層虛根Root的RPNL為NULL，二層子結(jié)點(diǎn)的RPNL均指向Root,。
　　Input： TAGTree   Output： RPNLTree
　　算法步驟：
　　(1)初始化,。RPNLTree中有且僅有一個(gè)根{$Root},，令指針p←RPNLTree.root。
　　(2)從Root開始前序遍歷TAGTree,，首先得到邊Student及結(jié)點(diǎn){$1},，在RPNLTree中創(chuàng)建結(jié)點(diǎn){$1}，并使p所指結(jié)點(diǎn)Root有一條邊Student指向結(jié)點(diǎn){$1},。由于{$1}是根結(jié)點(diǎn)的孩子,，所以需創(chuàng)建一條由{$1}指向Root的RPNL，最后令指針p指向{$1},。
　　(3)繼續(xù)遍歷TAGTree,，得邊Course及結(jié)點(diǎn)A（擴(kuò)展集為{$3}），并使Course自{$1}(由p所指)指向A,。
　　(4)判斷p所指結(jié)點(diǎn)是否存在RPNL,。若存在，則訪問RPNL所指結(jié)點(diǎn)N(當(dāng)前是Root),，并創(chuàng)建新邊Course和新結(jié)點(diǎn)B（擴(kuò)展集為{$3}）,，使Course自N指向{$3}，然后令A(yù)的RPNL指向B,。
　　(5)檢查N中是否有RPNL指向下一個(gè)結(jié)點(diǎn),。如果有，使N標(biāo)記該新結(jié)點(diǎn),，依次重復(fù)(3)(4),，直到?jīng)]有可以創(chuàng)建RPNL的新結(jié)點(diǎn)并且N的RPNL指向根結(jié)點(diǎn)，中止遍歷所得邊和結(jié)點(diǎn)（當(dāng)前是Course和{$3}）,。
　　(6)令p指向結(jié)點(diǎn)B,，即遍歷所得當(dāng)前結(jié)點(diǎn)路徑(Student.Course)所對應(yīng)RPNLTree結(jié)點(diǎn)。
　　圖4是依據(jù)算法2對圖2中XML標(biāo)簽樹構(gòu)造的RPNLTree,，其中虛線表示當(dāng)前結(jié)點(diǎn)的RPNL,。

　　由定義4、定義5及RPNLTree的構(gòu)造過程,，可得以下引理：
　　引理1 利用RPNL索引查詢語義路徑為L₁L₂……L_n的結(jié)點(diǎn),，若存在，則其擴(kuò)展集即為查詢結(jié)果,。
　　引理2 從RPNLTree根結(jié)點(diǎn)出發(fā),，查詢長度為n的字符串p，其查詢代價(jià)為O(n),。
　　引入RPNL索引技術(shù)的關(guān)鍵是：當(dāng)遍歷得到邊L及結(jié)點(diǎn)A時(shí),，只需從p所指的當(dāng)前結(jié)點(diǎn)開始沿著RPNL進(jìn)行新結(jié)點(diǎn),、邊的構(gòu)造,，無需進(jìn)行全程重復(fù)查找（根除外）,，以此來提高查詢速度，降低處理代價(jià),。
2.3 實(shí)驗(yàn)結(jié)果
　　這里選取應(yīng)用廣泛的路徑索引[6]作為RPNL索引查詢性能的對比分析,。實(shí)驗(yàn)的硬件環(huán)境為：CPU選用Pentium4 2.4，RAM為256MB,；軟件環(huán)境為：操作系統(tǒng)選用Windows XP,，數(shù)據(jù)集為DBLP。圖5為實(shí)驗(yàn)結(jié)果,。從圖5的趨勢曲線可以看出,，隨著測試數(shù)據(jù)量的增大，路徑索引的查詢時(shí)間呈指數(shù)增長,，而RPNL索引的查詢時(shí)間則基本是線性增長,。再由引理1、引理2可證,，RPNLTree的查詢處理代價(jià)為O(n),，即在相同條件下，RPNL索引技術(shù)的查詢效率優(yōu)于其他索引,。限于篇幅,，與其他索引實(shí)驗(yàn)結(jié)果的對比分析省略。

3  總  結(jié)
　　本文設(shè)計(jì)了一種新的基于XML的關(guān)系數(shù)據(jù)映射索引技術(shù),。通過對DTD不足的分析,，在保持關(guān)系數(shù)據(jù)語義約束的基礎(chǔ)上，提出了一套改進(jìn)的XML Schema算法,，并利用XML文檔的層次性,，構(gòu)造了XML標(biāo)簽樹，設(shè)計(jì)了RPNL索引,，實(shí)現(xiàn)了基于RPNLTree的查詢代價(jià)最小化O（n）,。
參考文獻(xià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數(shù)據(jù)庫的索引技術(shù)研究.計(jì)算機(jī)研究與發(fā)展,，2004
4   Wang H X，Park S ,，F(xiàn)an 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