尹曉奇

關(guān)系數(shù)據(jù)庫(kù)中XML數(shù)據(jù)存儲(chǔ)的有效映射方案

尹曉奇

XML是萬(wàn)維網(wǎng)數(shù)據(jù)傳輸?shù)闹饕?，有關(guān)XML映射到關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)的研究已成為當(dāng)今最重要的話題之一。映射方案對(duì)XML的處理效率具有一定影響，表現(xiàn)在以下幾個(gè)方面：數(shù)據(jù)庫(kù)可擴(kuò)展性、數(shù)據(jù)在數(shù)據(jù)庫(kù)系統(tǒng)的存儲(chǔ)速率以及數(shù)據(jù)庫(kù)里的信息存儲(chǔ)模式。對(duì)一種高效的新型XML映射技術(shù)s-XML的性能展開(kāi)深入探討。研究結(jié)果表明,與現(xiàn)有相關(guān)方法如Edge和Attribute相比，s-XML的文檔存儲(chǔ)效果更理想。

可擴(kuò)展標(biāo)記語(yǔ)言；映射方法；動(dòng)態(tài)更新；結(jié)構(gòu)化關(guān)系；XML查詢

0 引言

XML對(duì)萬(wàn)維網(wǎng)的信息共享和交流具有很好的適應(yīng)性，成為數(shù)據(jù)表示和數(shù)據(jù)通信方面重要的互聯(lián)網(wǎng)標(biāo)準(zhǔn)[1]，以致不少研究人士積極開(kāi)展相關(guān)研究并基于關(guān)系型數(shù)據(jù)庫(kù)模式提出XML存儲(chǔ)和文檔查詢的有效、精確映射方案。

伴隨著XML的快速發(fā)展，需要確保存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)里的信息條理清晰、前后一致以維持原始文檔數(shù)據(jù)的完整性。目前主要要處理好各節(jié)點(diǎn)之間的關(guān)系，才可確保查詢處理和所生成的結(jié)果精準(zhǔn)無(wú)誤，并與原始XML文檔里的數(shù)據(jù)相一致。

一個(gè)好的映射方法需要滿足四個(gè)基本關(guān)系：祖先后代關(guān)系、父子關(guān)系、兄弟關(guān)系和層級(jí)關(guān)系。這些信息需儲(chǔ)存在關(guān)系表里用以鑒定XML文檔里節(jié)點(diǎn)之間的關(guān)聯(lián)性，如此便可確保用戶的查詢得到恰當(dāng)處理。

但一直讓人困擾的是如何提出一個(gè)可維持節(jié)點(diǎn)間的基本關(guān)系以實(shí)現(xiàn)XML的有效處理一種映射方案。通常存在全文本查詢和結(jié)構(gòu)化查詢這兩種查詢。目前許多方法支持全文本查詢，但對(duì)結(jié)構(gòu)化查詢尚無(wú)定論。由于多種標(biāo)準(zhǔn)綜合的緣故，結(jié)構(gòu)化查詢導(dǎo)致查詢檢索不連貫，無(wú)法完整地完成任何查詢。此外，有些方法可存儲(chǔ)這類信息但它們復(fù)雜的表模式也成為制約因素，妨礙查詢處理速度，因而延長(zhǎng)了查詢響應(yīng)。對(duì)此，需要提出可對(duì)XML數(shù)據(jù)進(jìn)行有效映射并連貫維持節(jié)點(diǎn)間關(guān)系的解決方案。

本文貢獻(xiàn)如下：概述目前映射方案的優(yōu)缺點(diǎn)，基于持久標(biāo)識(shí)方案介紹s-XML映射技術(shù)，s-XML與其它技術(shù)性能對(duì)比研究。

1 相關(guān)研究

有關(guān)XML數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫(kù)的研究已成為學(xué)者們關(guān)注的一個(gè)重要領(lǐng)域，這是因?yàn)檎业揭环N有助于實(shí)現(xiàn)XML高效處理的映射方案十分重要。此前提出的許多映射方案均無(wú)法處理好節(jié)點(diǎn)之間的關(guān)系，而這對(duì)判定根據(jù)用戶需求從數(shù)據(jù)里進(jìn)行信息檢索節(jié)點(diǎn)間的關(guān)聯(lián)起到重要作用[2]。

Edge[3]是一種最簡(jiǎn)單的映射方案，將信息存儲(chǔ)到單個(gè)Edge表。因?yàn)檫@一特性，Edge方法會(huì)引發(fā)復(fù)雜查詢處理過(guò)程中信息檢索方面過(guò)多的自我連接問(wèn)題。鑒于大量數(shù)據(jù)存儲(chǔ)在超大XML文檔的單個(gè)表里，Edge表會(huì)遭遇“表大小過(guò)大出錯(cuò)”問(wèn)題。與Edge不同的是，Attribute[4]方法將相同元素名的所有元素儲(chǔ)存到單個(gè)表里，結(jié)果XML文檔里的表的數(shù)量有離散元素名之多，這將導(dǎo)致復(fù)雜查詢處理用的表之間存在許多連接。上述方法都是在邊緣標(biāo)記方法基礎(chǔ)上提出的，當(dāng)原始XML文檔存在動(dòng)態(tài)更新時(shí)，該方法要求對(duì)表里的現(xiàn)有數(shù)據(jù)進(jìn)行調(diào)整。

XRel[5]方法是基于節(jié)點(diǎn)標(biāo)記方法提出的。通過(guò)該法信息會(huì)映射到四個(gè)關(guān)系型表里。這些表是根據(jù)元素、屬性、文本和路徑這4個(gè)節(jié)點(diǎn)類型而設(shè)計(jì)的，路徑負(fù)責(zé)將根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行存儲(chǔ)。這是一種有效的方案，負(fù)責(zé)對(duì)文檔里的數(shù)據(jù)進(jìn)行維護(hù)。此外，XParent[6]將XML文檔表示為結(jié)構(gòu)樹(shù)，將相關(guān)信息映射到4個(gè)表即：1）LabelPath表：負(fù)責(zé)對(duì)該表里的離散標(biāo)記路徑進(jìn)行存儲(chǔ)；2）DataPath表：負(fù)責(zé)維護(hù)父子關(guān)系型的信息；3）元素表：負(fù)責(zé)維護(hù)元素信息；4）數(shù)據(jù)表：負(fù)責(zé)對(duì)文檔里的數(shù)據(jù)值進(jìn)行存儲(chǔ)以及祖先表負(fù)責(zé)對(duì)祖先后代信息進(jìn)行存儲(chǔ)。但是，這些方法的復(fù)雜性可能導(dǎo)致XML文檔的處理速度放緩，并影響查詢處理時(shí)間。

新映射方法s-XML是在持久標(biāo)識(shí)方案基礎(chǔ)上提出的。因此，不論何時(shí)已有XML文檔存在動(dòng)態(tài)更新，都不要求對(duì)表里存儲(chǔ)的已有數(shù)據(jù)進(jìn)行調(diào)整。再者，s-XML還可有效維持節(jié)點(diǎn)間的關(guān)系以確保這些節(jié)點(diǎn)間的關(guān)聯(lián)，如表1所示：

表1 Edge、Attribute與s-XM映射方案的優(yōu)缺點(diǎn)對(duì)比結(jié)果

除了提出適合的映射方案，還需確保標(biāo)識(shí)方案具有一定的持續(xù)性，以防一旦出現(xiàn)動(dòng)態(tài)更新，不需要對(duì)已有節(jié)點(diǎn)的標(biāo)記進(jìn)行變更或修改。所以，需要采用恰當(dāng)?shù)臉?biāo)識(shí)方案。本文提出的映射方法是智慧型方案，是XML高效處理的理想之選。當(dāng)每次插入新節(jié)點(diǎn)時(shí)，該標(biāo)記技術(shù)必須能夠生成唯一的標(biāo)記。當(dāng)對(duì)已有節(jié)點(diǎn)進(jìn)行刪除或調(diào)整時(shí)，需要確保已有節(jié)點(diǎn)的標(biāo)記原封不動(dòng)。持久標(biāo)識(shí)方案是支持對(duì)XML文檔的動(dòng)態(tài)更新并為新節(jié)點(diǎn)生成唯一標(biāo)識(shí)的方案之一。此基礎(chǔ)上提出了s-XML方案。

2 持久標(biāo)識(shí)方案及本文新方案S-XML

1）持久標(biāo)識(shí)方案

持久標(biāo)識(shí)方案[7-8]是最具有影響力的標(biāo)識(shí)方案之一，能夠有效地維持結(jié)構(gòu)關(guān)系并支持動(dòng)態(tài)更新，這歸咎于這一映射技術(shù)的能力問(wèn)題。每當(dāng)對(duì)文檔進(jìn)行插入、刪除或更新時(shí)，該技術(shù)不需要對(duì)XML文檔里的已有節(jié)點(diǎn)進(jìn)行重新標(biāo)記。持久標(biāo)識(shí)方案對(duì)XML圖做了標(biāo)識(shí)后的示例圖，如圖1所示：

圖1 基于持久標(biāo)識(shí)方案的新映射方案

持久標(biāo)識(shí)的標(biāo)識(shí)公式如下：

(l,[np,dp],[n,d])，式中：

- l 指節(jié)點(diǎn)的層次

- [n,d] 指節(jié)點(diǎn)的自我標(biāo)識(shí)

- [np,dp] 指父代節(jié)點(diǎn)的標(biāo)識(shí)

單個(gè)或大批節(jié)點(diǎn)插入的情況有三種，具體如下：

（1）在標(biāo)識(shí)(j,k)之前立即插入一個(gè)新節(jié)點(diǎn)，且在(j,k)之前不存在其它節(jié)點(diǎn)

新節(jié)點(diǎn)(j-1,k)的自我標(biāo)識(shí)

（2）在標(biāo)識(shí)(j,k)之后立即插入一個(gè)新節(jié)點(diǎn)，且在(j,k)之后不存在其它節(jié)點(diǎn)

新節(jié)點(diǎn)(j+1,k)的自我標(biāo)識(shí)

（3）在標(biāo)識(shí)為(j,k)的節(jié)點(diǎn)A與標(biāo)識(shí)為(m,n)的節(jié)點(diǎn)B之間插入一個(gè)新節(jié)點(diǎn)

第一步：假設(shè)新節(jié)點(diǎn)的標(biāo)識(shí)是(a,b)

第二步：a = m.k + j.n / d

第三步：b = 2.k.n / d，其中d是(m.k + j.n)和(2.k.n)的最大公約數(shù)

基于上述公式，我們不需要對(duì)已有節(jié)點(diǎn)重新進(jìn)行標(biāo)記，因?yàn)槊看纬霈F(xiàn)動(dòng)態(tài)更新時(shí)都會(huì)生成新的標(biāo)識(shí)。所以，持久標(biāo)識(shí)方案是一種能改善XML處理性能的可靠、持久標(biāo)記技術(shù)。正是基于這一特點(diǎn)，我們?cè)诔志脴?biāo)識(shí)方案基礎(chǔ)上提出了s-XML，使得XML的映射能力大大增強(qiáng)。

2）s-XML

確保一種映射方案可維持節(jié)點(diǎn)之間的關(guān)聯(lián)這一點(diǎn)很重要，它關(guān)系到查詢處理和查詢檢索能否有效進(jìn)行。s- XML表方案的設(shè)計(jì)理念：便于維持結(jié)構(gòu)式關(guān)系，較好地支持動(dòng)態(tài)更新。

s- XML包含ParentTable和ChildTable這兩種表，分別負(fù)責(zé)對(duì)父節(jié)點(diǎn)和葉節(jié)點(diǎn)方面的信息進(jìn)行存儲(chǔ)。這些表方案的公式介紹如下。

ParentTable (IdNode, LParent, SelfLabel)，其中：

LParent -負(fù)責(zé)對(duì)層次方面的信息和父節(jié)點(diǎn)的標(biāo)識(shí)進(jìn)行維護(hù)

ChildTable (IdNode, Level, Child, LParent) where: 其中：

基于持久標(biāo)識(shí)方案的s-XML的信息存儲(chǔ)情況，如表2和表3所示：

表2 父節(jié)點(diǎn)中ParentTable存儲(chǔ)的信息

表3 葉節(jié)點(diǎn)中ChildTable存儲(chǔ)的信息

如在表2中,ChildTable里的IdNode4的父標(biāo)識(shí)存儲(chǔ)在&6，表明ChildTable里的IdNode 6位于第二級(jí)，得到節(jié)點(diǎn)的本地標(biāo)識(shí)是[4.1]。該方案便于我們很方便地通過(guò)減少一個(gè)級(jí)別來(lái)判定節(jié)點(diǎn)間的祖先后代關(guān)系，追蹤父標(biāo)識(shí)和自我標(biāo)識(shí)。

3 實(shí)驗(yàn)分析與結(jié)果

1）實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)設(shè)備是因特爾奔騰雙核處理器T2390，160GB HDD和1GB DDR2，采用JDK 1.5.0的IntelliJ IDEA Community Edition 9.0.1版本進(jìn)行實(shí)驗(yàn)操作，MySQL作為數(shù)據(jù)庫(kù)服務(wù)器，JAVA作為編程語(yǔ)言。XML文件的樣品取自華盛頓UW大學(xué)數(shù)據(jù)庫(kù)，大小不等，如表4所示：

表4 本次實(shí)驗(yàn)用到的數(shù)據(jù)資料和文件

實(shí)驗(yàn)的目的有兩個(gè)：（1）確定XML數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫(kù)的時(shí)間；（2）根據(jù)文件大小和信息類型對(duì)各方案所消耗的數(shù)據(jù)庫(kù)大小進(jìn)行判定。

2）研究結(jié)果

首先確定XML數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)的用時(shí)，然后將s-XML方案與Edge、Attribute方案所得結(jié)果進(jìn)行比較。文件大小從KB到MB不等，如99KB、1MB和82MB。連續(xù)5個(gè)周期后各方案的平均用時(shí)結(jié)果，如表5所示：

表5 各方案下XML數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫(kù)平均用時(shí)（分鐘）結(jié)果對(duì)比

各方案下XML數(shù)據(jù)映射到關(guān)系型數(shù)據(jù)庫(kù)的用時(shí)數(shù)據(jù)，如圖2所示：

圖2 各方案用時(shí)結(jié)果對(duì)比

由表5和圖2可知Edge方案用時(shí)最少，這是因?yàn)镋dge是最簡(jiǎn)單的方案，只有一個(gè)表。Attribute用時(shí)最長(zhǎng)，這是因?yàn)樗谱鞯谋碛蠿ML文檔里出現(xiàn)的離散元素名之多。s-XML用時(shí)比Attribute的要少，這是因?yàn)樵摲桨钢挥袃蓚€(gè)表，通過(guò)直接的映射設(shè)計(jì)模式對(duì)XML數(shù)據(jù)進(jìn)行映射。

通過(guò)以上3種方案對(duì)文件進(jìn)行加載時(shí)我們測(cè)得了數(shù)據(jù)庫(kù)的大小。結(jié)果表明Edge和Attribute比s-XML要占用更大空間，這是因?yàn)榍皟烧叽鎯?chǔ)的數(shù)據(jù)較多，而s-XML對(duì)它們進(jìn)行了簡(jiǎn)化。Attribute方案占用空間最大，這是因?yàn)橹谱髁嗽S多表來(lái)滿足XML文檔里的不同元命名的需求。上述3種方案所消耗的數(shù)據(jù)庫(kù)大小結(jié)果，如表6和圖3所示：

表6 在KB和MB中不同文件大小數(shù)據(jù)庫(kù)大小的比較

圖3 三種方案所消耗的數(shù)據(jù)庫(kù)大小結(jié)果

根據(jù)所加載XML文檔的大小不同，XML數(shù)據(jù)映射到關(guān)系型表所需的表大小和時(shí)間也會(huì)變得越來(lái)越大。因此，映射方案必須足夠簡(jiǎn)單、具有一定持續(xù)性方可有效地進(jìn)行規(guī)模加載。映射方案的復(fù)雜性體現(xiàn)在數(shù)據(jù)加載所用時(shí)間、信息檢索和數(shù)據(jù)庫(kù)存儲(chǔ)大小3方面。必須將那些指標(biāo)降低才可滿足同時(shí)進(jìn)行多個(gè)查詢的要求，進(jìn)行全文本查詢和結(jié)構(gòu)化查詢。映射方案還必須存儲(chǔ)充足的數(shù)據(jù)，如層次、父子、祖先后代和兄弟關(guān)系以支持結(jié)構(gòu)化查詢。

除此之外，映射方案的進(jìn)步還必須考慮是否支持動(dòng)態(tài)更新，如對(duì)已有XML文檔進(jìn)行語(yǔ)句插入、刪除和更改。更改應(yīng)當(dāng)不影響表里的已有數(shù)據(jù)和表的結(jié)構(gòu)。Edge和Attribute這兩方案要求對(duì)表里存儲(chǔ)的已有數(shù)據(jù)進(jìn)行調(diào)整。這會(huì)影響查詢處理用時(shí)并延誤信息檢索。s-XML方案不要求對(duì)表里存儲(chǔ)的已有數(shù)據(jù)進(jìn)行更改，這是因?yàn)樵摲桨甘窃诔志脴?biāo)識(shí)方案基礎(chǔ)上提出的，持久標(biāo)識(shí)方案可生成插入已有文檔的新節(jié)點(diǎn)的唯一一組標(biāo)識(shí)。這是一種有效的查詢處理方法，信息檢索效果也理想。

從數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）的角度來(lái)說(shuō)，要實(shí)現(xiàn)更理想的數(shù)據(jù)存儲(chǔ)和表現(xiàn)目標(biāo)，需要考慮幾個(gè)方面。關(guān)于這一點(diǎn)，從數(shù)據(jù)存儲(chǔ)和檢索角度而言，表現(xiàn)簡(jiǎn)明是一個(gè)值得關(guān)注的重要標(biāo)準(zhǔn)。表現(xiàn)簡(jiǎn)明指的是數(shù)據(jù)表現(xiàn)緊湊但不累贅的程度。由于DBMS采納關(guān)系型模式將數(shù)據(jù)組織到關(guān)系中，我們需要利用一定的靈活性盡可能靈活、有效地對(duì)XML數(shù)據(jù)進(jìn)行存儲(chǔ)，因?yàn)檫@也是對(duì)數(shù)據(jù)建模的一種直觀做法。Edge方案將單個(gè)Edge表里的數(shù)據(jù)進(jìn)行收集，這將影響到數(shù)據(jù)的表現(xiàn)過(guò)程。同時(shí)，Attribute方案由于信息融合較多以致顯得過(guò)于復(fù)雜，這會(huì)導(dǎo)致數(shù)據(jù)表現(xiàn)不連貫，延時(shí)和響應(yīng)用時(shí)增長(zhǎng)。s-XML比較合理，利用DBMS的靈活性對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，因?yàn)樵摲桨钢徊捎脙蓚€(gè)表來(lái)存儲(chǔ)數(shù)據(jù)，而且數(shù)據(jù)表現(xiàn)程度增強(qiáng)，準(zhǔn)確性提高。

4 總結(jié)

本文將新映射技術(shù)s-XML與Edge和Attribute這兩種已有方法進(jìn)行了研究對(duì)比，重點(diǎn)考察了這3種方案將XML數(shù)據(jù)映射到關(guān)系型表所耗費(fèi)的時(shí)間、數(shù)據(jù)庫(kù)大小和所支持的信息類型。結(jié)果表明無(wú)論在映射速率還是數(shù)據(jù)庫(kù)規(guī)模方面，s-XML方案都要優(yōu)于既有方案。s-XML方案是良好映射方案的一個(gè)例證，能有效地維護(hù)結(jié)構(gòu)化關(guān)系并對(duì)XML文檔里出現(xiàn)的動(dòng)態(tài)更新提供支持。

[1] Haifeng Jiang, Hongjun Lu, Wei Wang and Jeffrey Xu Yu, “Path Materialization Revisited: An Efficient Storage Model for XML Data,” [J]. In Proc. Of ADC, 2001, 85-94

[2] Samini Subramaniam, Su-Cheng Haw and Poo Kuan Hoong, “Mapping and Labeling XML Data For Dynamic Update,” [J]. In Proc. Of ICECT, 2010：3-4

[3] Masatoshi Yoshikawa and Toshiyuki Amagasa, “XRel: A Path-Based Approach to Storage and Retrieval of XML Documents using Relational Databases”, [J].In ACM Transactions on Internet Technology (TOIT), 2001：9-25

[4] Haifeng Jiang, Hongjun Lu, Wei Wang and Jeffrey Xu Yu, “XParent: An Efficient RDBMS-Based XML Database System”, [J]. In Proc. Of ICDE, 2002：56-60

[5] Su-Cheng Haw, Chien-Sing Lee, “Node Labeling Schemes in XML Query Optimization: A Survey and Trends”, [J].IETE Technical Review, 2009：88-99

[6] Jun-Ki Min, Jihyun Lee, Chin-Wan Chung, “An Efficient XML Encoding and Labeling Method for Query Processing and Updating on Dynamic XML Data” , [M].DASFAA, 2007：112-119

[7] Alban Gabillon and Majirus Fansi, “A Persistrent Labeling Scheme for XML and tree Database”, [M].ACI 2006：110-115

[8] Felix Naumann and Mary Roth, “Information Quality: How Good Are the Off-The-Shelf DBMS?”, [J].In Proc. Of the International Conference on Information Quality (ICIQ), 2004：34-40

Effective Mapping Scheme of XML Data Stored in Relational Database

Yin Xiaoqi
(Department of Computer Science and Technology, Cheng Dong College of Northeast Agricultural University, Harbin150025, China)

XML is the main channel of the web of data transmission, research on mapping XML to relational database system has become one of the most important topics in the current era. Mapping scheme has certain influence on treatment efficiency of XML. It is shown in the following aspects: database expandability, the data storage rate and information storing mode in the database system. An effective and new XML mapping scheme technology, the s-XML is discussed in this paper. The results show that compared with the existing methods such as Edge and Attribute, document storage effect of s-XML is more ideal.

XML; Mapping Approach; Dynamic Updates; Structural Relationship; XML Queries

TP391

A

2014.11.11）

1007-757X(2014)12-0061-04

尹曉奇（1980-），男，東北農(nóng)業(yè)大學(xué)成棟學(xué)院，計(jì)算機(jī)科學(xué)與技術(shù)系，講師，碩士，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)，信息安全，哈爾濱，150025