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

　　XML（Extensible Markup Language）即可擴(kuò)展標(biāo)記語(yǔ)言，它與HTML一樣，都是SGML（Standard Generalized Markup Language,標(biāo)準(zhǔn)通用標(biāo)記語(yǔ)言）。Xml是Internet環(huán)境中跨平臺(tái)的，依賴于內(nèi)容的技術(shù)，是當(dāng)前處理結(jié)構(gòu)化文檔信息的有力工具。擴(kuò)展標(biāo)記語(yǔ)言XML是一種簡(jiǎn)單的數(shù)據(jù)存儲(chǔ)語(yǔ)言，使用一系列簡(jiǎn)單的標(biāo)記描述數(shù)據(jù)，而這些標(biāo)記可以用方便的方式建立，雖然XML占用的空間比二進(jìn)制數(shù)據(jù)要占用更多的空間，但XML極其簡(jiǎn)單易于掌握和使用。

　　1998年，XML被W3C推薦為Web數(shù)據(jù)交換的標(biāo)準(zhǔn)，標(biāo)志著數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)入了XML網(wǎng)絡(luò)時(shí)代。但目前使用廣泛的仍然是關(guān)系數(shù)據(jù)庫(kù)，因此，關(guān)系數(shù)據(jù)向XML文檔的異構(gòu)映射及其優(yōu)化索引就成為Internet數(shù)據(jù)集成技術(shù)的焦點(diǎn)之一。通過(guò)分析映射索引現(xiàn)狀，本文提出了一種新的基于XML的關(guān)系數(shù)據(jù)映射索引技術(shù)。針對(duì)DTD的不足，在域關(guān)系樹(shù)的基礎(chǔ)上設(shè)計(jì)了一套改進(jìn)的XML Schema算法，并在映射的XML標(biāo)簽樹(shù)上構(gòu)造了RPNL索引，使基于RPNLTree的查詢代價(jià)降至O（n）。

　　1  基于XML的關(guān)系數(shù)據(jù)映射技術(shù)

　　XML 是SGML 的子集，它是一種標(biāo)記性語(yǔ)言，同時(shí)也可以作為派生其它置標(biāo)語(yǔ)言的元語(yǔ)言，允許使用者自己定義標(biāo)識(shí)。和HTML相比， XML是面向內(nèi)容的，它具有更多的結(jié)構(gòu)和更多的語(yǔ)義，具有形式與內(nèi)容分離的特點(diǎn)，同時(shí)， XML所擁有的良好的可擴(kuò)展性、自描述性、自相容性以及跨文種等優(yōu)點(diǎn)，又使得它非常適于web上的數(shù)據(jù)表示、交換與發(fā)布。

　　目前，對(duì)關(guān)系模型向XML DTD文檔的轉(zhuǎn)換研究比較成熟。但DTD模式保守，數(shù)據(jù)類型有限，特別是異構(gòu)過(guò)程中完全忽略了關(guān)系數(shù)據(jù)間語(yǔ)義約束的保持，沒(méi)有做到實(shí)體聯(lián)系的完整性映射。針對(duì)上述不足，本文在域關(guān)系樹(shù)的基礎(chǔ)上設(shè)計(jì)了一套改進(jìn)的基于標(biāo)準(zhǔn)XML Schema的關(guān)系數(shù)據(jù)映射算法。

　　1.1 域關(guān)系樹(shù)

　　定義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)的語(yǔ)義解釋為：如果沿著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)識(shí)其域表層直接父結(jié)點(diǎn)的一個(gè)屬性。

　　1.2 基于域關(guān)系樹(shù)的XML Schema映射算法

　　嚴(yán)格結(jié)構(gòu)化的關(guān)系模型向具有明顯層次性的XML半結(jié)構(gòu)化模型映射過(guò)程中，借助于域關(guān)系樹(shù)的“中間件”作用，極大地簡(jiǎn)化了異構(gòu)的處理。算法中XML術(shù)語(yǔ)的父/子關(guān)系是關(guān)系術(shù)語(yǔ)的子/父關(guān)系。

　　算法1：以Student為例的算法過(guò)程

　?。?）設(shè)置域?qū)傩栽?。依次為域?qū)傩詫咏Y(jié)點(diǎn)創(chuàng)建域?qū)傩栽豏i-AttType及其屬性類型。如果值可以取NULL，則令其標(biāo)識(shí)nillable等于ture。

　　<complextype name=″Student-AttType″>

　　<sequence>

　　<ELEMENT name=″Sno″ type=″string″/>

　　<ELEMENT name=″Sname″ type=″string″ nillable=″ture″/>

　　</sequence>

　　</complextype>

　?。?）設(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)建庫(kù)元素。首先在XML Schema文檔中設(shè)置庫(kù)元素Ri-DB，然后依次添加庫(kù)表元素Ri-Tab及其域空間內(nèi)的元素類型xsd：Ri-TabType。

　　<ELEMENT name=″Student-DB″>

　　<complextype>

　　<sequence>

　　<ELEMENT name=″Student-Tab″ type=″xsd：Student-TabType″/>

　　</sequence>

　　</complextype>

　?。?）設(shè)置主/外鍵。如果域?qū)傩詫咏Y(jié)點(diǎn)是主屬性，則要插入主鍵標(biāo)識(shí)Ri-PriKey。對(duì)于域表層實(shí)體間的聯(lián)系則通過(guò)設(shè)置外鍵來(lái)完成，并指明其參照域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)的后臺(tái)數(shù)據(jù)庫(kù)采用Oracle。

　　2   基于XML的關(guān)系數(shù)據(jù)RPNL索引技術(shù)

　　目前已經(jīng)提出的XML數(shù)據(jù)庫(kù)索引機(jī)制有基于Trie樹(shù)的索引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)簽樹(shù)的基礎(chǔ)上設(shè)計(jì)了RPNL索引，將查詢代價(jià)控制在O（n）。

　　2.1 XML標(biāo)簽樹(shù)

　　圖2所示的XML標(biāo)簽樹(shù)是利用XML Schema的樹(shù)狀層次性，借鑒半結(jié)構(gòu)化模型OEM的表示形式建立的。其構(gòu)造方法如下：

　?。?）每一個(gè)域?qū)傩栽胤謩e對(duì)應(yīng)于XML標(biāo)簽樹(shù)上的一個(gè)結(jié)點(diǎn)，帶方框的$表示父結(jié)點(diǎn)，圓圈表示子結(jié)點(diǎn)。

　?。?）在XML標(biāo)簽樹(shù)中，元素-元素、元素-屬性之間的父-子關(guān)系均用相應(yīng)名字的邊來(lái)標(biāo)識(shí)。

　　2.2 基于XML標(biāo)簽樹(shù)的RPNL索引

　　定義3 形如（L1D1L2D2……LnDn）的字符串稱為數(shù)據(jù)路徑。（L1L2……Ln）稱為語(yǔ)義路徑，（D1D2……Dn）稱為數(shù)據(jù)值。其中Li和Di（i=1，2，……n）分別表示標(biāo)簽樹(shù)的邊和結(jié)點(diǎn)。

　　分析圖2，結(jié)點(diǎn)1、結(jié)點(diǎn)2具有相同的語(yǔ)義路徑{Student.Sno}，結(jié)點(diǎn)5、結(jié)點(diǎn)6具有相同的語(yǔ)義路徑{Student.Course.Cname}……由此可知：XML標(biāo)簽樹(shù)中存在若干具有不同值但具有相同語(yǔ)義路徑的結(jié)點(diǎn)，即同一語(yǔ)義路徑可對(duì)應(yīng)多個(gè)不同的數(shù)據(jù)值。于是，將具有相同語(yǔ)義路徑不同數(shù)據(jù)值的結(jié)點(diǎn)聚合在同一結(jié)點(diǎn)中，并在盡可能少的步驟內(nèi)快速定位到目的結(jié)點(diǎn)，便是索引優(yōu)化的關(guān)鍵技術(shù)。本文提出的基于XML標(biāo)簽樹(shù)的索引，在語(yǔ)義路徑上特別設(shè)置了結(jié)點(diǎn)的RPNL，同時(shí)利用Hash表保存索引結(jié)點(diǎn)的RPNL指針。實(shí)驗(yàn)證明，此方法能夠?qū)㈨樞虿檎业拇鷥r(jià)由O（n2）降至加了RPNL索引的O（n）。

　　定義4 設(shè)XML標(biāo)簽樹(shù)中結(jié)點(diǎn)A的數(shù)據(jù)路徑為αβ，其中α為基本單元。若存在結(jié)點(diǎn)B的數(shù)據(jù)路徑β，則有一指針自結(jié)點(diǎn)A指向結(jié)點(diǎn)B，該指針?lè)Q為結(jié)點(diǎn)A的RPNL。

　　定義5 RPNLTree中，聚合在同一結(jié)點(diǎn)A內(nèi)的具有相同語(yǔ)義路徑不同數(shù)據(jù)值的結(jié)點(diǎn)集，稱為結(jié)點(diǎn)A的擴(kuò)展集。

　　根據(jù)定義4、定義5并結(jié)合圖3（a），給出了在XML標(biāo)簽樹(shù)上構(gòu)造RPNL索引（圖3（b））的算法，稱為算法2。

　　算法2：在XML標(biāo)簽樹(shù)上構(gòu)造RPNL索引

　　約定： （1）p[i]←Li1Li2……Lin表示結(jié)點(diǎn)i的語(yǔ)義路徑（i=1，2，……n）。

　?。?）一層虛根Root的RPNL為NULL，二層子結(jié)點(diǎn)的RPNL均指向Root。

　　Input： TAGTree   Output： RPNLTree

　　算法步驟：

　?。?）初始化。RPNLTree中有且僅有一個(gè)根{$Root}，令指針p←RPNLTree.root。

　?。?）從Root開(kāi)始前序遍歷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}。

　?。?）繼續(xù)遍歷TAGTree，得邊Course及結(jié)點(diǎn)A（擴(kuò)展集為{$3}），并使Course自{$1}（由p所指）指向A。

　?。?）判斷p所指結(jié)點(diǎn)是否存在RPNL。若存在，則訪問(wèn)RPNL所指結(jié)點(diǎn)N（當(dāng)前是Root），并創(chuàng)建新邊Course和新結(jié)點(diǎn)B（擴(kuò)展集為{$3}），使Course自N指向{$3}，然后令A(yù)的RPNL指向B。

　?。?）檢查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）所對(duì)應(yīng)RPNLTree結(jié)點(diǎn)。

　　圖4是依據(jù)算法2對(duì)圖2中XML標(biāo)簽樹(shù)構(gòu)造的RPNLTree，其中虛線表示當(dāng)前結(jié)點(diǎn)的RPNL。

　　由定義4、定義5及RPNLTree的構(gòu)造過(guò)程，可得以下引理：

　　引理1 利用RPNL索引查詢語(yǔ)義路徑為L(zhǎng)1L2……Ln的結(jié)點(diǎn)，若存在，則其擴(kuò)展集即為查詢結(jié)果。

　　引理2 從RPNLTree根結(jié)點(diǎn)出發(fā)，查詢長(zhǎng)度為n的字符串p，其查詢代價(jià)為O（n）。

　　引入RPNL索引技術(shù)的關(guān)鍵是：當(dāng)遍歷得到邊L及結(jié)點(diǎn)A時(shí)，只需從p所指的當(dāng)前結(jié)點(diǎn)開(kāi)始沿著RPNL進(jìn)行新結(jié)點(diǎn)、邊的構(gòu)造，無(wú)需進(jìn)行全程重復(fù)查找（根除外），以此來(lái)提高查詢速度，降低處理代價(jià)。

　　2.3 實(shí)驗(yàn)結(jié)果

　　這里選取應(yīng)用廣泛的路徑索引[6]作為RPNL索引查詢性能的對(duì)比分析。實(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ì)曲線可以看出，隨著測(cè)試數(shù)據(jù)量的增大，路徑索引的查詢時(shí)間呈指數(shù)增長(zhǎng)，而RPNL索引的查詢時(shí)間則基本是線性增長(zhǎng)。再由引理1、引理2可證，RPNLTree的查詢處理代價(jià)為O（n），即在相同條件下，RPNL索引技術(shù)的查詢效率優(yōu)于其他索引。限于篇幅，與其他索引實(shí)驗(yàn)結(jié)果的對(duì)比分析省略。

　　3  總  結(jié)

　　本文設(shè)計(jì)了一種新的基于XML的關(guān)系數(shù)據(jù)映射索引技術(shù)。通過(guò)對(duì)DTD不足的分析，在保持關(guān)系數(shù)據(jù)語(yǔ)義約束的基礎(chǔ)上，提出了一套改進(jìn)的XML Schema算法，并利用XML文檔的層次性，構(gòu)造了XML標(biāo)簽樹(shù)，設(shè)計(jì)了RPNL索引，實(shí)現(xiàn)了基于RPNLTree的查詢代價(jià)化O（n）。