吳潔明，萬 勵，莫智懿，陸科達(dá)

WU Jie-ming，WAN Li，MU Zhi-yi，LU Ke-da

（梧州學(xué)院 計算機(jī)科學(xué)系，梧州 543002）

0 引言

在信息技術(shù)與網(wǎng)絡(luò)技術(shù)高速發(fā)展的今天，網(wǎng)絡(luò)已經(jīng)成為新一代操作平臺。信息正全面地以互聯(lián)網(wǎng)方式展開，互聯(lián)網(wǎng)的信息傳播，極大地加速了人類發(fā)展的進(jìn)程。隨著WEB技術(shù)的日益發(fā)展，WEB已經(jīng)成為信息制造、發(fā)布、加工和處理的主要平臺。XML技術(shù)已日益受到更為廣泛的關(guān)注，已經(jīng)在電子商務(wù)、電子數(shù)據(jù)交換、科學(xué)數(shù)據(jù)表示、數(shù)據(jù)建模與分析和搜索引擎等領(lǐng)域有著廣泛的應(yīng)用。隨著XML應(yīng)用技術(shù)的深入，將會有大量的XML文檔出現(xiàn)，并且現(xiàn)在在網(wǎng)絡(luò)上已經(jīng)積累了大量的XML文檔[1,2]。將XML數(shù)據(jù)轉(zhuǎn)化為關(guān)系數(shù)據(jù)，存儲在關(guān)系數(shù)據(jù)庫系統(tǒng)中，利用己經(jīng)成熟的關(guān)系數(shù)據(jù)庫理論和技術(shù)，來實現(xiàn)對XML數(shù)據(jù)的存取和訪問，并盡量減少XML數(shù)據(jù)查詢時的中間操作，以減少響應(yīng)時間，提高查詢效率，是XML文檔當(dāng)前最有效的存儲和查詢方式[3,4]。本文主要就基于關(guān)系數(shù)據(jù)庫的XML存儲技術(shù)相關(guān)問題進(jìn)行探討。

1 XML與關(guān)系數(shù)據(jù)庫結(jié)構(gòu)上的差異

XML文檔是半結(jié)構(gòu)化的數(shù)據(jù)，是一個樹模型，如果考慮到XML元素次序，則是一棵有序樹模型，其數(shù)據(jù)結(jié)構(gòu)是非結(jié)構(gòu)化的，而關(guān)系數(shù)據(jù)庫管理系統(tǒng)是采用二維表格作為存儲數(shù)據(jù)的模型，表格由行和列組成，列被稱作“字段”用于表示組成數(shù)據(jù)有效信息的屬性，行則用于儲存一條完整的數(shù)據(jù)記錄。XML數(shù)據(jù)與關(guān)系表之間數(shù)據(jù)結(jié)構(gòu)有很大的差異，具體來說，XML數(shù)據(jù)是有序的，而關(guān)系數(shù)據(jù)是則無序的，另外XML數(shù)據(jù)的模式往往經(jīng)常變化，可是關(guān)系數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)是固定不變的，XML數(shù)據(jù)可以無限層次嵌套，而關(guān)系數(shù)據(jù)則不能。雖然XML放松的類型限制和自描述性有利于數(shù)據(jù)之間的交換，但是卻不利于數(shù)據(jù)存儲。因此，XML的數(shù)據(jù)模型的半結(jié)構(gòu)化、有序性與平坦、無序的關(guān)系模型之間存在固有的不匹配。另外遵循文檔類型定義（DTD）或文檔模式定義（XML SCHEMA）的XML文檔也與遵循關(guān)系存儲模式的關(guān)系數(shù)據(jù)在語法、．結(jié)構(gòu)以及約束等很多方面存在著固有的異構(gòu)性，因此很難直接由XML數(shù)據(jù)產(chǎn)生關(guān)系模式。甚至即使多個XML文檔實例都遵循同一個文檔模式定義，它們也可能有不同的結(jié)構(gòu)?？梢钥闯?，XML映射到關(guān)系數(shù)據(jù)庫中存在固有的困難。映射時主要存在以下需要解決的問題：1）如何利用可能有的XML文檔模式（或類型）信息來采取各種不同的存儲策略；2）如何將XML文檔無損地存入關(guān)系數(shù)據(jù)庫；3）如何從關(guān)系數(shù)據(jù)庫中查詢并重構(gòu)XML信息。

2 基于關(guān)系數(shù)據(jù)庫的存儲策略

當(dāng)前，在將XML數(shù)據(jù)存儲在關(guān)系數(shù)據(jù)庫的策略主要有兩大類映射策略：即結(jié)構(gòu)映射策略和模型映射策略。簡單地來說，結(jié)構(gòu)映射需要將XML模式（或DTD）映射為特定的關(guān)系模式，隨著XML文檔模式（或者為DTD）的不同，映射成的關(guān)系模式也不同。而模型映射則是將XML文檔映射為固定的關(guān)系模式，與XML文檔模式（或者為DTD）無關(guān)。

2.1 基于結(jié)構(gòu)映射的策略

具體來說，基于結(jié)構(gòu)的映射方法可以分為兩個步驟來實現(xiàn)。

第一步：簡化DTD并生成DTD圖。因為XML DTD的元素是相當(dāng)復(fù)雜的，需要對復(fù)雜的DTD進(jìn)行簡化。DTD的簡化變換主要有以下三種方式。1）平面化變換：將DTD內(nèi)的層次嵌套關(guān)系打平，把嵌套的定義轉(zhuǎn)換為非嵌套的定義；2）簡化變換：將連續(xù)的多個一元操作轉(zhuǎn)換為一個一元操作；3）聚集變換：將多個具有相同名稱的子元素聚在一起，形成一個子元素。一個DTD圖表示的是一個DTD的結(jié)構(gòu)，圖的結(jié)點表示DTD中的元素、屬性或操作符，DTD中的元素在DTD圖中只出現(xiàn)一次，屬性和操作符在DTD圖中出現(xiàn)的次數(shù)則與它們在DTD中出現(xiàn)的次數(shù)相同。

第二步：DTD圖到關(guān)系模式的映射。從DTD圖到關(guān)系模式的映射方法主要有：基本內(nèi)聯(lián)法、共享內(nèi)聯(lián)法和綜合內(nèi)聯(lián)法。

1）基本內(nèi)聯(lián)法。基本內(nèi)聯(lián)法的原則是在存儲一個結(jié)點的時候，盡可能多地將這個元素的后代結(jié)點存儲在一個表中。例如，形如直線而無分支的數(shù)據(jù)路徑上的結(jié)點。這些后代結(jié)點作為祖先結(jié)點表中的屬性域而存儲。而結(jié)點之間的嵌套關(guān)系則用采用關(guān)系表之間的外鍵來解決?；緝?nèi)聯(lián)法將產(chǎn)生大量的關(guān)系，并且會產(chǎn)生大量的數(shù)據(jù)冗余，因此該方法基本上是不實用的。

2）共享內(nèi)聯(lián)法。共享內(nèi)聯(lián)法為以下三種DTD結(jié)點生成獨立的關(guān)系：（1）DTD圖中入度大于1或者等于0（根結(jié)點）的元素結(jié)點生成獨立的關(guān)系；（2）DTD圖中結(jié)點“幸”的孩子結(jié)點（將值集元素作為單獨的關(guān)系保存）；（3）互為遞歸的入度均為1的元素結(jié)點，其中之一生成獨立的關(guān)系。而其余的結(jié)點都生成關(guān)系屬性。共享內(nèi)聯(lián)法相對減少了XML查詢轉(zhuǎn)換為SQL語句的數(shù)目，但增加了每個SQL查詢中的連接運(yùn)算。

3）綜合內(nèi)聯(lián)法

綜合內(nèi)聯(lián)方法在處理入度大于l的結(jié)點上與共享內(nèi)聯(lián)方法不同，綜合內(nèi)聯(lián)法將所有入度大于1的元素結(jié)點也內(nèi)聯(lián)進(jìn)入父結(jié)點所生成的關(guān)系表中，但是帶回路的結(jié)點以及結(jié)點“}”或“+”的直接后繼結(jié)點除外，該方法減少了子結(jié)點與父結(jié)點的連接運(yùn)算。綜合內(nèi)聯(lián)法的出發(fā)點是充分吸取基本內(nèi)聯(lián)法和共享內(nèi)聯(lián)法的優(yōu)點，克服其缺點。與共享內(nèi)聯(lián)方法相比，綜合內(nèi)聯(lián)方法相對減少了每個SQL查詢中的連接運(yùn)算，但是增加了SQL語句的數(shù)目。

2.2 基于模型映射的策略

模型映射的方法是用一個固有的模式來存儲XML文檔。它用固定的關(guān)系模式來存放任何格式的XML數(shù)據(jù)，而不考慮XML文檔的模式（DTD或SCHEMA），其實質(zhì)是存儲XML文檔本身的結(jié)構(gòu)信息。目前，基于模型的映射方法主要有Edge方法、XRel方法和XParent方法。

1）Edge方法

Edge方法圓的存儲策略是把要存入的XML文檔看做圖形結(jié)構(gòu)，每個圖的邊界都表示為圖中的元組，把XML文檔圖中的所有邊都存入到關(guān)系表Edge中，用表Edge（source，ordinal，target，label，flag，value）存儲XML文檔圖中的邊，其中的source字段和target字段分別用來存儲邊的源結(jié)點和目標(biāo)結(jié)點的標(biāo)識符；label域為目標(biāo)結(jié)點的類型；flag用來區(qū)分目標(biāo)結(jié)點；target是一個元素結(jié)點還是一個文本結(jié)點，如果該目標(biāo)結(jié)點是文本結(jié)點，則文本值存儲于value域中；ordinal字段指出target結(jié)點在source結(jié)點的所有孩子中的位置。由于Edge方法將所有XML數(shù)據(jù)都用Edge表存放，操作方法簡單。但缺點是在Edge方法中每條邊都是單獨管理的，所以在用戶進(jìn)行查詢操作時就需在大量的表上進(jìn)行連接操作以形成路徑。如果要判斷祖先/后代關(guān)系就需要從祖先到后代（或與之相反）遍歷所有的邊，造成代價非常昂貴。

2）XRel方法

XRel方法為了存儲XML文檔的所有信息，將XML文檔樹分解為一個個路徑表達(dá)式，對于樹中每一個結(jié)點，都將從根結(jié)點到其自身的路徑存儲。而在樹中有可能有多個結(jié)點的路徑是一樣的，所以單個的簡單路徑表達(dá)式并不能夠存儲整棵XML文檔樹的信息。XRel模式是通過區(qū)間編碼[start，end]來反映XML文檔的模型結(jié)構(gòu)，并根據(jù)結(jié)點類型來劃分，分為元素結(jié)點表、屬性結(jié)點表和文本結(jié)點表，同時將所有路徑進(jìn)行存儲。因此，XRel模式由四個關(guān)系表組成如圖1所示。

圖1 XRel存儲模式

在Path表中，存儲所有的不重復(fù)的路徑，其中，PathID為標(biāo)記路徑的標(biāo)識，pathexp域存儲標(biāo)記路徑。為了實現(xiàn)路徑表達(dá)式的字符串匹配操作，防止意外的結(jié)果出現(xiàn)，將標(biāo)記路徑中的“/”替換為“#/”進(jìn)行存儲。對于Element表、Attribute表和Text表，Attribute表和Text表中的value字段存儲的分別是屬性結(jié)點的值和文本結(jié)點的值。對于每一個路徑表達(dá)式，查詢過程都可以分為兩部：第一步，利用字符串的匹配操作，能夠快速的查找出與路徑表達(dá)式相匹配的所有標(biāo)記路徑的標(biāo)識；第二步，利用這些路徑標(biāo)識，能夠快速的查找出隸屬于這些路徑終端的值。

XRel存儲模式的特點可以總結(jié)如下：1）用簡單路徑表達(dá)式和結(jié)點的區(qū)間編碼（start，end）存儲XML文檔的所有信息。2）分別為每一種結(jié)點類型創(chuàng)建一個對應(yīng)的關(guān)系表。3）用一個Path表把文檔中所有不重復(fù)的路徑都提取出來，有效地降低了數(shù)據(jù)庫的存儲容量。

3）XParent方法

XParent模式和XRel模式一樣，將文本數(shù)據(jù)路徑獨立出來，共包含四個關(guān)系表，如圖2所示。

圖2 XParent存儲模式

其中，表LabelPath中的pathexp字段用來存儲所有不重復(fù)的標(biāo)簽路徑，即模式路徑。每一個標(biāo)簽路徑被賦予一個標(biāo)識符pathID，length為標(biāo)記路徑的長度。Parent表存儲的是雙親/孩子關(guān)系，pid和cid分別表示一個邊的起始結(jié)點與結(jié)尾結(jié)點。did為XML文檔中元素結(jié)點的標(biāo)識，它也可以作為以該結(jié)點為終端點的數(shù)據(jù)路徑的標(biāo)識。

Parem表存儲的是雙親/孩子關(guān)系，因此，為了檢查數(shù)據(jù)路徑需要進(jìn)行連接操作。為了提高這種處理的效率，可以改用Ancestor表來存儲祖先/后裔關(guān)系。Ancestor（did，ancestor，level），利用Ancestor表能夠快速的檢測結(jié)點之間的祖先/后裔關(guān)系，但是它比Parent表需要更多的空間，而且由于存在冗余信息，修改代價也更高。XParent模式分別通過LabelPath表和Parent表來支持標(biāo)記路徑和數(shù)據(jù)路徑。因此，XParent模式既具有基于結(jié)點的模型映射的特點，又具有基于邊的模型映射的特點。

3 結(jié)束語

主要討論了基于關(guān)系數(shù)據(jù)庫的XML存儲方式的兩大類映射方法：模型映射和結(jié)構(gòu)映射。并且分別對三種具體的映射方法：基于邊的映射方法、基于結(jié)點的映射方法和基于結(jié)構(gòu)的映射方法進(jìn)行了探討，并說明了各自的原理與優(yōu)缺點，對于今后XML數(shù)據(jù)庫設(shè)計具有一定幫助。

[1]周勇，韓潔，史忠植.XML數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫協(xié)作研究[J].計算機(jī)工程與應(yīng)用，2002，38（13）.

[2]曹亮，王茜，盧菁.XML數(shù)據(jù)在關(guān)系數(shù)據(jù)庫中存儲和檢索的研究和實現(xiàn)[J].東南大學(xué)學(xué)報（自然科學(xué)版），2002，32（1）.

[3]路燕，郝忠孝，張亮.基于編碼的XML關(guān)系數(shù)據(jù)庫存儲[J].計算機(jī)研究與發(fā)展，2005，42（11）.

[4]許卓明，劉琴，董逸生.基于關(guān)系數(shù)據(jù)庫的XML存儲技術(shù)評述[J].計算機(jī)工程與應(yīng)用，2003，39（21）.