關(guān)系模式向DTD轉(zhuǎn)化方法研究

劉煒

摘要：XML已經(jīng)成為Web上數(shù)據(jù)交換的標(biāo)準(zhǔn)，然而絕大多數(shù)的商業(yè)數(shù)據(jù)仍然存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中。因此需要將關(guān)系數(shù)據(jù)發(fā)布XML文檔的形式。發(fā)布過程中一個(gè)最關(guān)鍵的就是進(jìn)行模式轉(zhuǎn)換。提出了一種算法來(lái)實(shí)現(xiàn)關(guān)系模式向DTD的轉(zhuǎn)化。最終通過SQL查詢將關(guān)系數(shù)據(jù)發(fā)布XML文檔的形式。最后通過一組關(guān)系表對(duì)該算法進(jìn)行了具體的實(shí)現(xiàn)。

關(guān)鍵詞：數(shù)據(jù)交換;關(guān)系模式;模式轉(zhuǎn)換;發(fā)布

1引言

隨著因特網(wǎng)的不斷發(fā)展，XML[1]作為Web上數(shù)據(jù)發(fā)布和交換的標(biāo)準(zhǔn)迅速地出現(xiàn)并且流行起來(lái)。XML具有層次性和自描述性，自然成為數(shù)據(jù)傳輸?shù)氖走x。然而，另一方面，絕大多數(shù)的商業(yè)數(shù)據(jù)仍然存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)（DBMS）中[2]。DBMS的可靠性和可擴(kuò)展性使得它將來(lái)仍然會(huì)扮演著數(shù)據(jù)存儲(chǔ)的角色。因此，迫切需要在關(guān)系數(shù)據(jù)和XML文檔之間進(jìn)行相互的轉(zhuǎn)換，如圖1所示。

在XML的發(fā)布過程中面臨著很多問題[3]，首先，數(shù)據(jù)庫(kù)中的關(guān)系表是平面的，而XML文檔則是樹形的標(biāo)記結(jié)構(gòu)。其次，在關(guān)系表中很多完整性約束在轉(zhuǎn)換過程中也不能被丟失[4]-[6]。整個(gè)映射過程可以分成兩部分，第一部分稱為模式映射，也叫結(jié)構(gòu)映射。是將關(guān)系模式轉(zhuǎn)化成XML的模式。XML的模式反映了XML文檔中標(biāo)簽的結(jié)構(gòu)。而標(biāo)簽中的內(nèi)容要由數(shù)據(jù)映射來(lái)解決。

本文提出了一種良好的算法將關(guān)系模式轉(zhuǎn)化成DTD。算法將現(xiàn)實(shí)世界中的關(guān)系分成了三類，運(yùn)用上面的算法對(duì)這三類關(guān)系模型分別進(jìn)行了轉(zhuǎn)化。利用這個(gè)算法可以以DTD為中介，并且實(shí)現(xiàn)了關(guān)系數(shù)據(jù)向XML數(shù)據(jù)唯一性的轉(zhuǎn)化。最后通過一組關(guān)系表對(duì)算法進(jìn)行了具體實(shí)現(xiàn)。

2關(guān)系模式分類的相關(guān)定義

下面給出相關(guān)的定義，并將關(guān)系模式分成三類。

定義1：對(duì)于一個(gè)關(guān)系中的所有關(guān)系表，如果能夠存在一個(gè)關(guān)系表，它其中所有的屬性分別存在于其他的關(guān)系表中，那么我們稱這個(gè)關(guān)系表為根關(guān)系表。

定義2：如果一個(gè)關(guān)系中存在一個(gè)關(guān)系表，它的一部分屬性分別存在于其他所有的關(guān)系表中，而另一部分屬性為自身獨(dú)有的屬性，那么我們稱這個(gè)關(guān)系表為擴(kuò)展的根關(guān)系表。

根關(guān)系表中的屬性都是連接屬性。而擴(kuò)展的根關(guān)系表中除了連接屬性以外還有其他的屬性。在具有根關(guān)系表或擴(kuò)展的根關(guān)系表的關(guān)系中，可以看出有一個(gè)“中心關(guān)系表”能夠連接所有其他的關(guān)系表。

下面我們將關(guān)系模式分成三類：分別是星形關(guān)系、直線型關(guān)系和樹狀關(guān)系。

定義3：對(duì)于一個(gè)關(guān)系中的若干關(guān)系表，如果其中有根關(guān)系表或擴(kuò)展的根關(guān)系表，那么我們稱這些關(guān)系表為星形關(guān)系。如圖1所示

星形關(guān)系的特點(diǎn)是以一個(gè)關(guān)系表為中心，其他的關(guān)系表都與這個(gè)關(guān)系表連接。

定義4：對(duì)于一個(gè)關(guān)系中的若干關(guān)系表，如果表的數(shù)目大于或者等于4，而且不存在一個(gè)表為根關(guān)系表或擴(kuò)展的根關(guān)系表，并且任何一個(gè)表只與不超過2個(gè)表相連接，那么我們成這樣的關(guān)系模式為直線型關(guān)系。如圖2所示

說明，在判斷直線型關(guān)系的時(shí)候必須考慮數(shù)目，如果小于或等于3個(gè)的話，那么即使符合上面的條件，也不是直線關(guān)系，而是星形關(guān)系。

定義5：對(duì)于若干個(gè)關(guān)系表，如果找不到一個(gè)表是根關(guān)系表或擴(kuò)展的根關(guān)系表，并且其中至少有一個(gè)表與三個(gè)或三個(gè)以上的表相連接，那么我們稱這個(gè)關(guān)系為樹狀關(guān)系。如圖3所示

現(xiàn)實(shí)世界的關(guān)系類型中只有這三類關(guān)系模型，即使有看似復(fù)雜的關(guān)系模型，總能夠歸納為上面三種類型之一。因此我們對(duì)這三類關(guān)系模型分別進(jìn)行轉(zhuǎn)化，就代表對(duì)整個(gè)關(guān)系模型進(jìn)行了轉(zhuǎn)化。

3關(guān)系數(shù)據(jù)庫(kù)模式向XML轉(zhuǎn)化方法

下面我們分別就三類關(guān)系模式給出相應(yīng)的轉(zhuǎn)化方法和具體的實(shí)現(xiàn)，然后總結(jié)出一套普遍適用的關(guān)系模式向XML模式轉(zhuǎn)化的算法。

3.1星形關(guān)系的轉(zhuǎn)化

這種類型的轉(zhuǎn)化方法很簡(jiǎn)單，從上面我們定義來(lái)看，凡是小于或等于3個(gè)表的關(guān)系都是星形關(guān)系，而4個(gè)表以上則必須根據(jù)定義進(jìn)行判斷。

3.1.1 轉(zhuǎn)化方法

第一步：把根關(guān)系表或擴(kuò)展的根關(guān)系表的名稱作為XML文檔的根元素。

第二步：把根關(guān)系表中的屬性作為第1層子節(jié)點(diǎn)。寫出DTD為<！ELEMENT 根節(jié)點(diǎn)（子元素，子元素…….）>

第三步：將第一層子元素名分別作為下一層的根節(jié)點(diǎn)。然后進(jìn)行DTD的書寫。一般格式為：

<！ELEMENT 子元素 （下一級(jí)子元素，下一級(jí)子元素）>。

這里的子元素都是連接元素，因此在書寫DTD時(shí)要將第三層葉子節(jié)點(diǎn)相應(yīng)的連接屬性刪除。否則就會(huì)產(chǎn)生錯(cuò)誤?？梢钥闯鲂切侮P(guān)系由于其特殊的結(jié)構(gòu)使得轉(zhuǎn)化后的XML樹也只有3層。

3.1.2具體轉(zhuǎn)化過程

這里列舉一個(gè)關(guān)系數(shù)據(jù)轉(zhuǎn)化XML的例子，這里我們不考慮關(guān)系的規(guī)范化的問題，也不考慮關(guān)系表實(shí)際含義的問題。

因?yàn)殛P(guān)系中表的數(shù)目是3個(gè)，因此判斷一定是星形關(guān)系。通過觀察可以看出表3是一個(gè)擴(kuò)展的根關(guān)系表?？梢园凑招切侮P(guān)系轉(zhuǎn)化的方法進(jìn)行轉(zhuǎn)化。首先確定XML文檔根元素為SC，也就是表3的名稱。因此可以寫出第一句<！ELEMENT SC（學(xué)號(hào)，課程號(hào)，成績(jī)）>。然后我們可以看出表3中的屬性學(xué)號(hào)和課程號(hào)分別連接著表1和表2。因此可以將學(xué)號(hào)和課程號(hào)做為第二層子節(jié)點(diǎn)。同時(shí)作為最下面一層葉子節(jié)點(diǎn)的父節(jié)點(diǎn)。另外，在書寫的時(shí)候要將表1和表2中的連接屬性刪去。完整的DTD如下：

3.2 直線型關(guān)系的轉(zhuǎn)化

定義6：將關(guān)系中每個(gè)關(guān)系表的一個(gè)屬性提取出來(lái)重新建立一個(gè)關(guān)系表稱為構(gòu)造根關(guān)系表。

直線型關(guān)系轉(zhuǎn)化XML時(shí)需要構(gòu)造根系表，否則任何一個(gè)關(guān)系表都能作為根元素，我們將構(gòu)造的關(guān)系表的名稱作為XML的根元素，而構(gòu)造根關(guān)系表中的屬性應(yīng)當(dāng)是第一層子節(jié)點(diǎn)。這些子節(jié)點(diǎn)再去連接相應(yīng)的下一層葉子節(jié)點(diǎn)?？梢灶A(yù)見。這種類型轉(zhuǎn)化后的XML文檔必定為3層樹型結(jié)構(gòu)。

3.2.1轉(zhuǎn)化方法

第一步：將關(guān)系中每個(gè)關(guān)系表的主屬性提取出來(lái)重新建立一個(gè)新的根關(guān)系表，然后給這個(gè)新的關(guān)系表命名，以這個(gè)關(guān)系表的名字作為根元素，其屬性作為第一層次子元素。

第二步：因?yàn)檫@個(gè)構(gòu)造的根關(guān)系表中的屬性都是連接屬性，因此可以根據(jù)連接屬性進(jìn)行對(duì)應(yīng)尋找下一層的節(jié)點(diǎn)。依次寫出DTD的內(nèi)容。

3.2.2具體轉(zhuǎn)化過程

在上面表1，表2，表3的基礎(chǔ)上，我們?cè)黾恿吮?。

首先我們要構(gòu)造出一個(gè)根關(guān)系表，令表名為學(xué)校信息，新的根關(guān)系表可以表示為：

學(xué)校信息（學(xué)號(hào)，課程號(hào)，成績(jī)，系），這是一個(gè)虛的關(guān)系表。然后可以寫出DTD的第一行定義為：<！ELEMENT 學(xué)校信息（學(xué)號(hào)，課程號(hào)，成績(jī)，系）>。限于篇幅，具體的DTD文檔我們就不再去書寫了。

3.3 樹型關(guān)系的轉(zhuǎn)化

樹型關(guān)系的轉(zhuǎn)化比較復(fù)雜。主要復(fù)雜在根節(jié)點(diǎn)的選擇上面。如果不加限制，那么任何一個(gè)表都可以作為根節(jié)點(diǎn)。

3.3.1轉(zhuǎn)化方法

第一步：分別計(jì)算出每個(gè)關(guān)系表能連接其他關(guān)系表的數(shù)目，將能連接數(shù)目最多的那個(gè)關(guān)系表的表名作為根元素。并且根據(jù)這種結(jié)構(gòu)畫出相應(yīng)的樹型結(jié)構(gòu)。

第二步：以這個(gè)表為中心，寫出根元素和第一層的子元素。然后根據(jù)連接屬性依次向下書寫。方法和前面的一樣。

可以看出，這種轉(zhuǎn)化方法對(duì)XML樹狀結(jié)構(gòu)的層數(shù)沒有限制。

3.3.2具體轉(zhuǎn)化過程

可以在上面4個(gè)表的基礎(chǔ)上增加一個(gè)表

五個(gè)表的關(guān)系如圖4所示

通過定義可以判斷是樹型結(jié)構(gòu)，其中表1為根元素，然后根據(jù)連接屬性寫出整個(gè)DTD。第一行為：<！ELEMENT Student（學(xué)號(hào)，姓名，性別，年齡，系） >

3.4 具體的算法（包含三類關(guān)系類型）

這里我們用自然語(yǔ)言描述：（2，3，4步是并列的，不能同時(shí)執(zhí)行，需要第1步進(jìn)行判斷后執(zhí)行）

第一步：判斷關(guān)系的類型

If （關(guān)系表的數(shù)目<4）：為星形關(guān)系，直接轉(zhuǎn)向第四步

Else：判斷這一組關(guān)系表的類型（判斷方法見上面的講述）

if（星形關(guān)系），直接轉(zhuǎn)向第四步

else if（直線型關(guān)系），則直接轉(zhuǎn)向第三步

else（樹狀關(guān)系）.則繼續(xù)執(zhí)行（即執(zhí)行第二步）

第二步：分別計(jì)算出每個(gè)關(guān)系表能連接其他關(guān)系表的數(shù)目，將能連接數(shù)目最多的那個(gè)關(guān)系表的表名作為根元素。并且根據(jù)這種結(jié)構(gòu)畫出相應(yīng)的樹型結(jié)構(gòu)。

第三步：將關(guān)系中每個(gè)關(guān)系表的主屬性提取出來(lái)重新建立一個(gè)新的根關(guān)系表，然后給這個(gè)新的關(guān)系表命名，以這個(gè)關(guān)系表的名字作為根元素，其屬性作為第一層次子元素。

第四步：把根關(guān)系表或擴(kuò)展的根關(guān)系表的名稱作為XML文檔的根元素。

第五步：在選定根元素之后，寫出第一DTD即<！ELEMENT 根元素（子元素，子元素…）>

第六步：根據(jù)每個(gè)表的連接屬性進(jìn)行書寫。要注意連接屬性作為下面一層的表名，在寫屬性的時(shí)候要把這個(gè)連接屬性刪去，這樣可以寫出整個(gè)DTD。

第七步：根據(jù)DTD寫出XML的基本結(jié)構(gòu)，然后依照關(guān)系表將標(biāo)簽中的內(nèi)容依次填上。

4 總結(jié)

這種方法的關(guān)鍵是如何確定每種關(guān)系類型的根元素。確定根元素之后就可以不同表之間的連接屬性進(jìn)行轉(zhuǎn)化了。將現(xiàn)實(shí)世界的關(guān)系模型分成了3類。對(duì)其分別進(jìn)行了討論，最后給出了一個(gè)算法。這種方法最大的優(yōu)點(diǎn)就是能夠唯一地將關(guān)系模式轉(zhuǎn)化成XML數(shù)據(jù)模式。并且可以實(shí)現(xiàn)一切關(guān)系模式的轉(zhuǎn)化。保證了轉(zhuǎn)化的全體性，唯一性。

參考文獻(xiàn)：

[1]T. Bray et al.，“Extensible Markup Language （XML） third edition，” http：//www.w3.org/TR/REC-xml.

[2]邱洋，岳昆，等. 利用緩存優(yōu)化關(guān)系數(shù)據(jù)的XML發(fā)布[J]. 計(jì)算機(jī)研究與發(fā)展，2004，41（10）：1082-1088.

[3]萬(wàn)常選. 以XML文檔發(fā)布關(guān)系數(shù)據(jù)[J]. 計(jì)算機(jī)應(yīng)用與軟件，2002，19（8）：30-33

[4]Shanmugasundaram J，Shekita E，Barr R. Efficiently publishing relational data as XML documents[C]. Egypt：Proceeding of the26th International Conference on Very Large Databases，2000.

[5]Fernandez M，Tan W. Silk route：A framewok for publishing relational data in XML[J]. ACM Transactions on Database Systems，2002，27（4）：438-493.

[6]Eisenberg A，Melton J. SQL/XML is making good progress[J].ACM SIGMOD Record，2002，31（2）：101 - 108.