XML 文檔到關(guān)系型數(shù)據(jù)庫的模型映射方法

史 濤， 沈艷霞

(江南大學(xué) 電氣自動化研究所，江蘇 無錫214122)

XML 憑借其獨立于平臺、可擴(kuò)展性和自描述性等特性［1］廣泛應(yīng)用于異構(gòu)數(shù)據(jù)集成系統(tǒng)的設(shè)計中，實現(xiàn)不同數(shù)據(jù)源之間的信息交換和共享［2］。隨著XML 應(yīng)用的不斷深入，在諸多領(lǐng)域都產(chǎn)生了海量的XML 數(shù)據(jù)，如何高效地存儲這些XML 數(shù)據(jù)已成為值得研究的重要課題［3］。現(xiàn)階段，關(guān)系型數(shù)據(jù)庫仍然是企業(yè)應(yīng)用最廣泛的數(shù)據(jù)庫，基于此，實現(xiàn)XML與關(guān)系型數(shù)據(jù)庫的數(shù)據(jù)交換對企業(yè)數(shù)據(jù)集成平臺的設(shè)計具有現(xiàn)實意義。

將XML 文檔中的數(shù)據(jù)有效且精確地分解到關(guān)系型數(shù)據(jù)庫中，要求采用強(qiáng)健且無縫的映射方法。在映射過程中，XML 文檔中節(jié)點關(guān)系的完整保存更有利于精確地實現(xiàn)用戶檢索過程。用戶檢索可以分為兩種方式，即全文本檢索和結(jié)構(gòu)檢索［4］。全文本檢索只包含關(guān)鍵字檢索，沒有具體的限制條件，是使用最普遍的檢索方式，其特點是簡單方便，缺點是檢索結(jié)果不精確，效率較低。結(jié)構(gòu)檢索包含多個限制條件，能夠返回更精確的答案。顯然為了在關(guān)系型數(shù)據(jù)庫中得到更為精確的查詢結(jié)果，結(jié)構(gòu)檢索方式是不錯的選擇。

目前，國內(nèi)外學(xué)者對映射技術(shù)的研究已經(jīng)取得了一定進(jìn)展。文獻(xiàn)［5］提出的邊緣(Edge)方法是最簡單直接的方法，主要思路是使用整數(shù)標(biāo)記節(jié)點，使用XML 文檔中的元素名標(biāo)記邊緣這兩種形式將整個XML 文檔存儲在單個關(guān)系型表格中，這種方法只適用于簡單的XML 文檔，而針對復(fù)雜組合的XML 文檔可能出現(xiàn)“超出表格大小”的錯誤。與Edge 方法相比，屬性［5］(Attribute)方法根據(jù)XML文檔中的元素名稱創(chuàng)建足夠多的表格來進(jìn)行存儲。這種方法雖然適用于具有復(fù)雜結(jié)構(gòu)的XML 文檔，但是過多的表格會消耗資源和機(jī)器內(nèi)存。文獻(xiàn)［6］提出的DTD 方法在XML 文檔中元素出現(xiàn)頻率的基礎(chǔ)上映射XML 數(shù)據(jù)，允許更少的空間消耗、簡單的表格模式和有效的表格映射機(jī)制，但該方法只適用于XML 文檔模式由DTD 表示的情況，具有局限性。文獻(xiàn)［7］中用來存儲XML 文檔結(jié)構(gòu)的是編碼字符串的大文本字段，這種方法降低了維持XML 文檔結(jié)構(gòu)的代價，但卻提高了查詢XML 文檔的難度。文獻(xiàn)［8］提出一種新的基于模式的方案，其利用分離和連接的操作符來構(gòu)成模式及其相應(yīng)的數(shù)據(jù)元素，易于呈現(xiàn)復(fù)雜的映射請求。文獻(xiàn)［9］提出一種數(shù)據(jù)模型，通過同時表示數(shù)據(jù)視圖和結(jié)構(gòu)視圖的方式來改寫XML 文檔，進(jìn)而實現(xiàn)XML 文檔的映射過程。上述兩種映射方法的設(shè)計都基于XML 模式，無法支持動態(tài)的XML 數(shù)據(jù)存儲。

綜上所述，很多現(xiàn)存的映射技術(shù)在實現(xiàn)結(jié)構(gòu)化檢索的前提下，往往會消耗更多的資源和內(nèi)存，如文獻(xiàn)［5，7］;還有一些映射方案，如文獻(xiàn)［6，8-9］，雖然能夠?qū)崿F(xiàn)高效的結(jié)構(gòu)化查詢，但需要考慮XML 文檔的模式，只支持靜態(tài)的XML 數(shù)據(jù)存儲，無法應(yīng)用在XML 模式不斷變化的情況。

文中提出一種從XML 文檔到關(guān)系型數(shù)據(jù)庫的高效映射方案，利用特殊的標(biāo)記節(jié)點方法，通過遍歷XML 文檔對節(jié)點進(jìn)行編碼，有效獲取節(jié)點關(guān)系，實現(xiàn)了高效的結(jié)構(gòu)化查詢。該映射方法不僅實現(xiàn)了高效的結(jié)構(gòu)化查詢檢索方式，同時不需要考慮XML文檔的具體模式，支持任何格式良好的XML 數(shù)據(jù)的動態(tài)存儲。文中將該方法與現(xiàn)有的3 種存儲XML 文檔方法，即Edge、Attribute 以及DTD，在存儲空間、映射時間和檢索時間3 個方面進(jìn)行比較。

1 理論概述

1.1 XML 數(shù)據(jù)模型

一個定義良好的數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)在于具有定義良好的數(shù)據(jù)模型。XML 數(shù)據(jù)模型一般被簡化為標(biāo)記樹或者直觀顯示的圖表，其中攜帶著表示結(jié)構(gòu)數(shù)據(jù)和屬性值的元素。XML 具有多種不同的數(shù)據(jù)模型，其中Xpath1.0 和DOM 模型都將XML 文檔轉(zhuǎn)換為樹結(jié)構(gòu)。Xquery 1.0 和Xpath 2.0 模型使用7 種節(jié)點將XML 文檔轉(zhuǎn)換成圖表［10］。文中采用DOM 模型，具體考慮XML 文檔中4 種類型的節(jié)點，分別為根節(jié)點、元素節(jié)點、文本節(jié)點和屬性節(jié)點［11］。圖1 是一個XML 文檔的具體實例和通過DOM 模型解析得到的XML 樹結(jié)構(gòu)，實例中包含上文提到的4 種節(jié)點類型。

圖1 XML 文檔實例Fig.1 XML documents instance

1.2 XML 節(jié)點關(guān)系

圖2 顯示的是在XML 文檔中節(jié)點的4 種主要關(guān)系類型，分別為:a:父-子關(guān)系;b:祖先-子代關(guān)系;c:同胞關(guān)系;d:層級信息［12］。這些信息在映射過程需要被保存下來，滿足檢索用戶的查詢需要。

文中在文獻(xiàn)［13］提出的連續(xù)性標(biāo)記模式方法的基礎(chǔ)上，提出一種標(biāo)記節(jié)點的方法。該方法能夠保存節(jié)點間的關(guān)系信息，有效支持結(jié)構(gòu)化的查詢檢索方式。也就是，每個節(jié)點將被標(biāo)記為形如(1，np，n)，其中:1.XML 樹種節(jié)點的層級;n.該節(jié)點相對于同胞的位置，稱為節(jié)點的區(qū)域標(biāo)記。np. 父節(jié)點的區(qū)域標(biāo)記;可以推斷，對于根節(jié)點nr，因為沒有父節(jié)點，可以被標(biāo)記為(0，NULL，1)，具體實例如圖3所示。

圖3 標(biāo)記解釋Fig.3 Expalanation of nodes

2 具體算法設(shè)計

文中提出的模式映射方法的主要思路是:首先利用特有的標(biāo)記形式，通過遍歷XML 文檔樹對所有節(jié)點進(jìn)行標(biāo)記編碼，有效獲取各節(jié)點間的關(guān)系信息;其次將XML 樹結(jié)構(gòu)中的節(jié)點分為葉節(jié)點和非葉節(jié)點，創(chuàng)建對應(yīng)的兩個表格將所有節(jié)點存儲到關(guān)系型數(shù)據(jù)庫中。具體流程如圖4 所示。其中標(biāo)記節(jié)點和表格映射兩個步驟作用于映射過程中，查詢檢索步驟用于對存儲在關(guān)系型數(shù)據(jù)庫中的XML 文檔進(jìn)行查詢檢索。算法的具體設(shè)計思路在下文詳細(xì)說明。

圖4 算法流程Fig.4 Flowchart of the algorithm

2.1 步驟1:標(biāo)記節(jié)點

步驟1 的具體算法(標(biāo)記節(jié)點)實現(xiàn)如下所示。

步驟1)標(biāo)記節(jié)點:

1)輸入:XML 樹，Τ

2)輸出:標(biāo)記的XML 節(jié)點，η

3)int level = 0

4)function labelNode(document)

5)if(ηr= = root node in Τ)

6)then label forηr(level，NULL，sn = 1)

7)level ++

8)for each child node ofηr，ηc(i)do{

9)label for nodeηc(i)(level，np= 1，n = 1)

10)getCNodes(ηc(i)，n，level)

11)n ++

12)i ++

13)}//endfor

14)}//endfunction

15)

16)function getCNodes(ηc(i)，npc，levelchild)

17){levelchild ++

18)for each child node ofηc(i)，ηnextc(i)do{

19)label for nodeηnextc(i)(levelchild，np= npc，n =1)

20)getCNodes(ηnextc(i)，n，levelchild)

21)getValue(ηnextc(i)，n，levelchild)

22)n ++

23)i ++

24)}//endfor

25)}//endfunction

26)

27)function getValue(ηnextc(i)，npleaf，levelleaf){

28)levelleaf ++

29)for each child node ofηnextc(i)，ηleaf(i)do{

30)label for nodeηleaf(i)(levelleaf，np= npleaf，n =1)

31)}//endfor

32)}//endfunction

步驟1 中，每個節(jié)點都被特定的標(biāo)記模式所標(biāo)記，形 如(l，np，n)。XML 文 檔，即 步 驟1 中 的document 能夠被XML 解析器解析出所有節(jié)點，具體實現(xiàn)為步驟1 中的第4 行。函數(shù)labelNode()標(biāo)記出根節(jié)點ηr。因為根節(jié)點沒有父節(jié)點，所以如步驟1 中第6 行所示，np被標(biāo)記成NULL。根節(jié)點的子節(jié)點，即ηc(i)，通過函數(shù)getCNodes()標(biāo)記，具體實現(xiàn)如步驟1 的16 ～25 行。當(dāng)增加XML 節(jié)點的層級時，每一個子節(jié)點都被遞歸地送入函數(shù)getCNodes()生成隨后的子節(jié)點，遞歸函數(shù)的結(jié)束條件為levelchild 等于層數(shù)。葉節(jié)點的標(biāo)記由函數(shù)getValue()實現(xiàn)，即步驟1中的27 ～32 行。

2.2 步驟2:表格映射

步驟1 中輸出的信息將被映射到兩張表格，分別為內(nèi)部節(jié)點表格inNodeTable 和外部節(jié)點表格exNodeTable。內(nèi)部節(jié)點表格存儲的是非葉節(jié)點，即內(nèi)部節(jié)點;外部節(jié)點表格存儲的是葉節(jié)點，即外部節(jié)點。

下面介紹兩個表格的具體字段:

inNodeTable(nodeID，pName，cName，level，lParent，selfLabel):

(a)nodeID:存儲在內(nèi)部節(jié)點表格中的節(jié)點唯一識別編號

(b)pName:存儲父節(jié)點的元素名

(c)cName:節(jié)點名稱

(d)level:層級

(e)lParent:節(jié)點的父節(jié)點的nodeID

(f)selfLabel:節(jié)點所在層級的區(qū)域標(biāo)簽

exNodeTable(nodeID，level，pName，selfLabel，lParent，value):

(a)nodeID:存儲在外部節(jié)點表格中的節(jié)點唯一識別編號

(b)level:存儲節(jié)點在XML 文檔中的層級

(c)pName:存儲父節(jié)點的元素名

(d)selfLabel:節(jié)點所在層級的區(qū)域標(biāo)簽

(e)lParent:存儲在內(nèi)部表格中的父節(jié)點的nodeID

(f)value:存儲節(jié)點的值

步驟2 實現(xiàn)的是節(jié)點到表格的映射過程。下文采用和步驟1 同樣的方法對XML 文檔進(jìn)行遞歸遍歷。從步驟1 推導(dǎo)出的節(jié)點標(biāo)簽，即層級(1)，區(qū)域標(biāo)簽(n)，父標(biāo)簽(np)將被分別映射到level，selfLabel 和lParent 三列當(dāng)中。具體算法實現(xiàn)步驟如下所示。

步驟2:映射XML 節(jié)點到關(guān)系型數(shù)據(jù)庫:

1)function createTable(){

2)long timeBefore = System.currentTimeMillis();

3)connect to the database

4)}

5)

6)// 插入根節(jié)點

7)function rootN(Doucument doc){

8)insert into inNodeTable(pName，cName，level，selflabel，lParent)values(NULL，root.getNode Name()，level，n，’NULL’)

9)// 插入第1 層的節(jié)點

10)insert into inNodeTable (pName，cName，level，selflabel，lParent)values(cNode.getParentNode( ).getNodeName( )，cNode.getNodeName()，level，n，nodeID)

11)}

12)

13)// 插入其他非葉節(jié)點

14)function child(ηnextc(i)){

15)insert into inNodeTable (pName，cName，level， selflabel，lParent)values(cN.getParentNode( ). getNodeName( )，cN.getNodeName()，level，n，nodeID)

16)child(ηnextc(i))

17)// 插入葉節(jié)點

18)leafNode(ηnextc(i))

19)}

20)

21)function leafNode(ηnextc(i)){

22)insert into exNodeTable (level，selfLabel，lParent，value)values(level，n，nodeID，cData.getNodeValue())

23)}

24)long timeAfter = System.currentTimeMillis();

25)Time taken to map = timeAfter-timeBefore

2.3 步驟3:查詢檢索

步驟3 描述的是查詢檢索過程。如果查詢條件包括一個關(guān)鍵詞以及節(jié)點間關(guān)系的組合，在外部節(jié)點表格中檢索lParent 字段，該字段決定了內(nèi)部節(jié)點表格中父-子關(guān)系或者祖先-子代關(guān)系，如步驟3 中5 ～7 行所示;如果是結(jié)構(gòu)查詢，那么將在內(nèi)部節(jié)點表格中使用lParent 字段值進(jìn)行搜索查詢?nèi)绮襟E3中8 ～11 行所示。

步驟3:在關(guān)系型數(shù)據(jù)庫中進(jìn)行查詢檢索過程:

1)輸入:查詢條件，例如元素名，值或者節(jié)點間各種關(guān)系的組合

2)輸出:從數(shù)據(jù)庫返回的結(jié)果集

3)v:= 節(jié)點文本值

4)e:= 節(jié)點間關(guān)系組合的元素名

5)if(input = = v)

6)then criteria of the query is value = v from exNodeTable

7)endif

8)if(input = = e)

9)if(e = = parent-child relationship)＆＆

(e = = ancestor-descendant relationship)＆＆

(e = = leaf node)

10)then trace the node from exNodeTable to inNo deTable by matching lParent from exNodeTable to nodeID in inNodeTable

11)endif

12)if((e = = parent-child relationship)＆＆

(e = = ancestor-descendant relationship)＆＆

(e!= leaf node))

13)then trace the node in inNodeTable

14) only match lParent and nodeID in inNode Table

15)endif

16)endif

圖5 描述了利用步驟3 對于文中之前提到的節(jié)點間4 種主要關(guān)系的檢索過程。由此可以在關(guān)系數(shù)據(jù)庫中實現(xiàn)對XML 文檔中各節(jié)點的檢索。

圖5 4 種節(jié)點關(guān)系的檢索過程Fig.5 Search of four node relations

3 實驗評估

為了驗證提出的模式映射方法的有效性，將文中所提方法與現(xiàn)有的3 種映射方法，即基于邊緣、基于屬性和關(guān)系型DTD 3 種方法進(jìn)行比較。評價指標(biāo)分別為:將XML 文檔映射到關(guān)系型數(shù)據(jù)庫的時間;映射過程完成后的存儲時間;從關(guān)系型數(shù)據(jù)表中執(zhí)行查詢的時間。

文中數(shù)據(jù)源來自于 Washington UW Repository［14］下 載 所 得 的Digital Bibliography ＆Library Project(DBLP)數(shù)據(jù)集大小為0.67G。實驗的測試平臺是Altova Spy 和Microsoft Visual Studio 2010 標(biāo)準(zhǔn)環(huán)境，采用文檔對象模型DOM 對XML 進(jìn)行解析處理，將Microsoft SQL server2008 作為關(guān)系型數(shù)據(jù)庫服務(wù)器，C#作為算法編程語言。其中記錄的時間由5 組連續(xù)執(zhí)行的平均值確定，以求數(shù)據(jù)更為準(zhǔn)確。

3.1 XML 數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫

第1 個實驗用于測量將XML 數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫的時間，其結(jié)果如圖6 所示。在映射過程中一共包含3 個步驟，分別為數(shù)據(jù)庫創(chuàng)建、表格創(chuàng)建以及加載XML 數(shù)據(jù)。

圖6 映射時間Fig.6 Time of mapping

由圖6 可知，通過文中方法得到的映射時間為37 254 ms，而關(guān)系型DTD 和基于屬性的方法映射時間分別為62 150 ms 和49 987 ms，后兩者時間明顯大于文中方法。其主要原因是關(guān)系型DTD 和屬性兩種方法分別根據(jù)元素重復(fù)出現(xiàn)的頻率和獨立元素的個數(shù)生成相應(yīng)數(shù)量的表格，導(dǎo)致創(chuàng)建表格和數(shù)據(jù)加載這兩個環(huán)節(jié)的時間過長。相比之下，文中的方法只包含兩個表格來有效地存儲XML 數(shù)據(jù)，表現(xiàn)最好。

3.2 關(guān)系型數(shù)據(jù)庫存儲容量

第2 個實驗評估通過邊緣、屬性、DTD 和文中所提方法將XML 數(shù)據(jù)映射到數(shù)據(jù)庫之后，存儲數(shù)據(jù)的容量大小比較。圖7 顯示了評估結(jié)果。

圖7 存儲空間Fig.7 Space of storage

由圖7 可知，基于屬性和關(guān)系型DTD 方法所消耗的存儲容量分別為698 MB 和608 MB，利用的空間較高，原因是基于屬性方法根據(jù)XML 文檔中獨立元素的個數(shù)創(chuàng)建相應(yīng)多的表格，而關(guān)系型DTD 方法根據(jù)文檔中元素重復(fù)出現(xiàn)的頻率同樣創(chuàng)建相應(yīng)多的表格，兩者創(chuàng)建更多的表格數(shù)，導(dǎo)致空間占有更大。基于邊緣的映射方法存儲容量為585 MB，相比前兩種方法占有的空間更少，原因是該方法將整個XML 文檔都存儲在一個表格中。同理，文中方法創(chuàng)建兩個表格來存儲XML 文檔，消耗的存儲空間較少。

3.3 查詢過程

第3 個實驗對數(shù)據(jù)庫中存儲的數(shù)據(jù)集的查詢時間進(jìn)行評估。實驗分別選用不同存儲容量的源數(shù)據(jù)，采用目前較為復(fù)雜的查詢方法——twig 對數(shù)據(jù)集進(jìn)行查詢。具體實驗結(jié)果如表1 所示。

表1 查詢檢索時間對比Tab.1 Time comparison in terms of query

由表1 得出，針對4 種存儲容量不同的元數(shù)據(jù)，基于邊緣和屬性兩種方法在進(jìn)行twig 查詢時都耗費更多的時間。相對而言，關(guān)系型DTD 方法是一種更好的方法，因為其在處理簡單的結(jié)構(gòu)化XML 樹時具有優(yōu)勢，但是在處理結(jié)構(gòu)不完整的XML 數(shù)據(jù)時其表現(xiàn)差于文中所提出的方法。造成這種差異的主要原因是DTD 映射模式創(chuàng)建了大量表格，導(dǎo)致節(jié)點關(guān)系之間出現(xiàn)大量連接。顯然，文中所提出的映射方法不存在上述情況，相比較其他方法，其在查詢過程中表現(xiàn)出了更高的效率。

4 結(jié) 語

XML 文檔要求強(qiáng)健無縫的映射方法來實現(xiàn)將數(shù)據(jù)有效且精確地存儲到關(guān)系型數(shù)據(jù)庫中。一種好的映射方法應(yīng)該保存XML 樹結(jié)構(gòu)中的4 種主要關(guān)系，分別為父-子，祖先-子代，同胞以及XML 的層級，有效支持結(jié)構(gòu)化的查詢檢索。文中提出的映射方案利用特殊的標(biāo)記節(jié)點方法，在映射過程中保存節(jié)點之間的關(guān)系，高效實現(xiàn)了結(jié)構(gòu)化檢索。實驗結(jié)果表明，文中所提出的方法具有以下幾個特點:(1)在數(shù)據(jù)庫存儲和數(shù)據(jù)加載方面表現(xiàn)堅固;(2)支持結(jié)構(gòu)化檢索;(3)不受模式限制，支持任何格式良好的XML 文檔;(4)相比較基于邊緣、屬性和關(guān)系型DTD 等現(xiàn)有方法，映射效果更理想。

［1］Femau H.Learning XML grammars［C］//7th International Conference，MLDM 2011.New York:［s.n.］，2001，1:73-87.

［2］袁景凌，徐麗麗，苗連超.基于XML 的虛擬法異構(gòu)數(shù)據(jù)集成方法研究［J］.計算機(jī)應(yīng)用研究，2009，26(1):172-174.

YUAN Jingling，XU Lili，MIAO Lianchao.Research on virtual approach about heterogeneous data integration based on XML［J］.Application Research of Computers，2009，26(1):172-174.(in Chinese)

［3］Haw S C，Lee C S，Node labeling schemes in XML query optimization:a survey and trends［J］.IETE Technical Review，2009，26(2):88-99.

［4］曹蘭英，嚴(yán)義，鄔惠峰.基于模式匹配的XML 自動轉(zhuǎn)換技術(shù)［J］.計算機(jī)工程與應(yīng)用，2012，48(25):72-76.

CAO Lanying，YAN Yi，WU Huifeng. Automating XML document transformations based on schema matching［J］. Computer Engineering and Applications，2012，48(25):72-76.(in Chinese)

［5］Florescu D，Kossmann D.Storing and querying XML data using an RDBMS［J］.IEEE Data Engineering Bulletin，1999，22(3):27-34.

［6］Shanmugasundaram J，Shekita E，Kiernan J，et al.A general technique for querying XML documents using a relational database systems［EB/OL］.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.6801.

［7］耿飚，宋余慶，粱成全，等.XML 文檔到關(guān)系數(shù)據(jù)庫映射方法的研［J］.計算機(jī)應(yīng)用研究，2010，27(3):951-954.

［8］LI Xuhui，ZHU Shanfeng，LIU Mengchi，et al.Presenting XML schema mapping with conjunctive-disjunctive views［J］.Web-Age Information Management Lecture Notes in Computer Science，2013，7923:105-110.

［9］Eun-Young Kim，Se-Hak Chun.New database mapping schema for XML document in electronic commerce［J］. Multimedia and Ubiquitous Engineering，2013，240:353-358.

［10］Clark J，Derose S. XML path language(Xpath)version 1. 0［EB/OL］. W3C Recommendation. http://www. w3. org/TR/xpath，1999.

［11］QIN Jie，ZHAO Shumei，YANG Shuqiang，et al.Efficient storing well-formed XML documents using RDBMS［C］//International Conference on Services Systems and Services Management.Chongqing:IEEE，2005，2:1075-1080.

［12］Edith Cohen，Haim Kaplan，Tova Milo.Labeling dynamic XML trees［J］.Siam Journal on Computing，2002，39(5):271-281.

［13］Gabillon A，F(xiàn)ansi M.A persistent Labeling scheme for XML and tree database［C］//Signal-Image Technology and Internet-Based Systems，2005，1:110-115.

［14］Dan Sucin. XML data repository［EB/OL］. (2001-11-09)［2014-01-20］. http://www. cs. washington. edu/research/xmldatasets/www/repository.html.