基于擴展DOM樹的XML SCHEMA文檔轉(zhuǎn)換為數(shù)據(jù)庫模式算法

劉必廣

（福建交通職業(yè)技術(shù)學(xué)院 福建 福州 350007）

基于擴展DOM樹的XML SCHEMA文檔轉(zhuǎn)換為數(shù)據(jù)庫模式算法

劉必廣

（福建交通職業(yè)技術(shù)學(xué)院 福建 福州 350007）

通過分析XML文檔轉(zhuǎn)換成數(shù)據(jù)庫文件存在的問題，提出基于擴展DOM樹的XML Schema文檔轉(zhuǎn)換為數(shù)據(jù)庫模式的算法。提出了擴展DOM樹的概念。描述了由XMLSchema文檔生成擴展DOM樹算法。說明了路徑鍵的概念及其作用。實現(xiàn)了將擴展DOM樹轉(zhuǎn)換成數(shù)據(jù)庫模式的算法。實現(xiàn)過程使用了反向掃描優(yōu)化和特殊元素處理規(guī)則。

XML Schema；擴展DOM樹；路徑鍵；數(shù)據(jù)庫模式

1 引言

作為網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)傳輸?shù)闹匾ぞ撸琗ML文檔得到越來越多的應(yīng)用。在許多WEB應(yīng)用中，應(yīng)用程序?qū)⒂脩籼峤坏臄?shù)據(jù)以XML文檔的形式傳送到服務(wù)器。服務(wù)器在收到XML文檔后，要根據(jù)事先約定的XML Schema模式進行分析，提取其中的用戶數(shù)據(jù)保存在數(shù)據(jù)庫中。服務(wù)器如何保存XML數(shù)據(jù)顯得相當(dāng)重要。

目前，傳統(tǒng)方法中通過分析XML文檔生成XML樹。然后轉(zhuǎn)換成一個對應(yīng)的圖模型[1]，再轉(zhuǎn)換成數(shù)據(jù)庫模式。這樣轉(zhuǎn)換過程復(fù)雜，而且不能保留元素間的包含關(guān)系信息。典型的算法是P_Schema算法[2]，該算法對XML Schema中包含子元素的元素進行單獨求其模式，生成一個子模式，在求子模式過程時，沒有處理元素間的包含關(guān)系[3]。另外，XML不同元素中可能存在同名子元素，在轉(zhuǎn)換成數(shù)據(jù)庫模式過程中[4]，這些元素可能存在沖突。在將XML文檔信息存儲到數(shù)據(jù)庫中時，需要處理元素間的包含關(guān)系和元素間可能存在的沖突問題。

2 相關(guān)工作

將Schema文檔轉(zhuǎn)換為數(shù)據(jù)庫模式時，要將Schema文檔中的元素、屬性、約束和元素間的包含關(guān)系對應(yīng)成數(shù)據(jù)庫模式中的字段和表間關(guān)系。

本文所采用的算法中，使用擴展DOM樹表示Schema文檔內(nèi)容。在轉(zhuǎn)換時，先將Schema文檔用擴展DOM樹表示，再通過遍歷擴展DOM樹生成Schema文檔對應(yīng)的數(shù)據(jù)庫模式。為了解決轉(zhuǎn)換時模式?jīng)_突問題，本文提出了基于路徑鍵的處理方式，以處理元素和子元素之間的包含關(guān)系。在生成的模式中將父模式的鍵作為外鍵，以實現(xiàn)上下級的聯(lián)系。在子模式中，根據(jù)函數(shù)依賴[5]關(guān)系使用上一級的鍵和本級的相關(guān)屬性組成本級結(jié)點表的鍵。通過結(jié)點間鍵的逐層傳遞形成結(jié)點深度遍歷的路徑鍵。擴展DOM樹每條深度遍歷的路徑[6]都有其相應(yīng)的路徑鍵。這樣，就可以解決轉(zhuǎn)換過程中元素之間的沖突問題。

通過轉(zhuǎn)換DOM樹各結(jié)點的子元素、屬性、約束以及結(jié)點間的包含關(guān)系，能夠完整存儲XML Schema文檔的信息；通過數(shù)據(jù)庫的約束實現(xiàn)Schema文檔中對數(shù)據(jù)的約束。

3 Schema文檔

3.1 Schema文檔定義

Schema用于定義XML文件[7]的邏輯結(jié)構(gòu)。為了便于實現(xiàn)轉(zhuǎn)換算法，本文將Schema文檔定義為：Schema={Node，Attrib，Key，Path，Constraint，F(xiàn)untion}。其中Node表示元素的集合，Attrib表示屬性的集合，Key表示各元素鍵的集合，Path表示元素路徑的集合，Constraint表示約束的集合，F(xiàn)unction表示函數(shù)依賴的集合。

3.2 Schema文檔實例

如XML Schema文檔Purchase·xml所示。從文檔結(jié)構(gòu)和語義可知，其Schema文檔可定義為：

PurchaseSchema={Node，Attrib，Key，Path，Constraint，F(xiàn)untion}

其中：

4 產(chǎn)生擴展DOM樹

為了準(zhǔn)確完整地表示Schema文檔信息，要有一個模型。這個模型除了能夠表達元素數(shù)據(jù)，還要存儲Schema文檔元素間的層次關(guān)系、元素的屬性、約束以及元素的包含關(guān)系。一般的DOM樹能夠表達Schema文檔元素間的關(guān)系和元素屬性。無法表示Schema文檔元素間包含關(guān)系及元素的約束。本文使用擴展DOM樹來表示Schema文檔，以完整表達這些信息。

擴展DOM樹使用結(jié)點表示Schema文檔元素，結(jié)點還包含Schema元素的約束信息。使用結(jié)點間的聯(lián)系表示Schema文檔元素之間的關(guān)系。

4.1 擴展DOM樹定義

為了便于將Schema文檔轉(zhuǎn)換為數(shù)據(jù)庫模式，首先將Schema文檔表示的XML文檔模式轉(zhuǎn)換為擴展DOM樹表示。

擴展DOM樹定義：用樹的形式存儲Schema文檔信息，使用結(jié)點表示Schema文檔普通元素、屬性和約束，使用父子結(jié)點間的聯(lián)系方式表示Schema文檔中元素間的關(guān)系，葉子表示沒有子元素的元素。使用聯(lián)系表示元素間的包含關(guān)系。

擴展DOM樹表示schema文檔的方法：

4.2 Schema文檔產(chǎn)生擴展DOM樹算法

通過掃描Schema文檔對應(yīng)Schema文檔的元素、屬性、約束以及元素之間的關(guān)系進行必要處理，生成滿足定義要求的擴展DOM樹。產(chǎn)生擴展DOM樹算法為：

算法1:Schema文檔產(chǎn)生擴展DOM樹

輸入：Schema文檔

輸出：擴展DOM樹

掃描Schema文檔

(1)Schema文檔根元素作為擴展DOM樹根結(jié)點，并設(shè)置根結(jié)點為當(dāng)前結(jié)點；

(2)掃描Schema文檔當(dāng)前元素的各個子元素、屬性，若子元素為簡單類型且沒有下一級元素，則作為DOM樹的葉子結(jié)點；

(3)若Schema文檔當(dāng)前元素或?qū)傩缘哪骋蛔釉赜邢乱患壴兀瑒t該子元素作為DOM樹的中間結(jié)點；

(4)對于Schema文檔中復(fù)雜類型的元素，作為DOM樹的中間結(jié)點，展開其復(fù)雜類型中包含的元素作為下一級元素，在DOM樹中作為下一級結(jié)點處理；

(5)DOM樹中當(dāng)前結(jié)點到各子結(jié)點的連線上以形式標(biāo)明對應(yīng)子結(jié)點的最大元素數(shù)和最小元素數(shù)；作為結(jié)點間的聯(lián)系。

(6)讀取Schema文檔中當(dāng)前元素的限定設(shè)置，作為擴展DOM樹結(jié)點的約束；

(7)依次設(shè)置Schema文檔中當(dāng)前元素中的包含下級元素的元素為當(dāng)前元素為擴展DOM樹的當(dāng)前結(jié)點，轉(zhuǎn)(2)。

如圖1是Purchase.xml所對應(yīng)的擴展DOM樹。

圖1.擴展DOM樹

5 擴展DOM樹生成數(shù)據(jù)庫模式算法

通過遍歷擴展DOM樹，根據(jù)各個結(jié)點和上一級結(jié)點的關(guān)系生成相應(yīng)的結(jié)點表。生成結(jié)點表過程中，將上級結(jié)點表的鍵加入到結(jié)點表中，做為結(jié)點表鍵的一部分。這樣保留了擴展DOM樹中結(jié)點之間的聯(lián)系。對于聯(lián)系中max>1的結(jié)點進行特殊處理，生成相應(yīng)的結(jié)點表。

在生成結(jié)點表時，保留擴展DOM樹中結(jié)點信息的同時保留結(jié)點的關(guān)系及約束信息。

5.1 算法

算法2:擴展DOM樹生成數(shù)據(jù)庫模式

輸入：擴展DOM樹

輸出：優(yōu)化數(shù)據(jù)模式

廣度遍歷擴展DOM樹，先設(shè)置根結(jié)點為當(dāng)前結(jié)點

(1)為當(dāng)前結(jié)點創(chuàng)建一張結(jié)點表，廣度遍歷各子結(jié)點；

(2)若不是根結(jié)點，則根據(jù)函數(shù)依賴關(guān)系設(shè)置上一級結(jié)點的鍵和當(dāng)前結(jié)點表的的相關(guān)屬性組成鍵，形成本結(jié)點表的路徑鍵；

若子結(jié)點為葉子結(jié)點且其max=min=1，則作為表的一個列，列名為葉子結(jié)點名。確定結(jié)點表的鍵及屬性間的函數(shù)依賴；

(3)若子結(jié)點為葉子結(jié)點且其max>1，則構(gòu)造一張對應(yīng)的葉子表，包含的列有：葉子結(jié)點名，當(dāng)前結(jié)點表的鍵做為葉子表的外鍵；

(4)對于約束結(jié)點，根據(jù)其內(nèi)容對其對應(yīng)的結(jié)點表或列進行約束設(shè)置；

(5)廣度遍歷當(dāng)前結(jié)點的各子結(jié)點中非葉子結(jié)點，轉(zhuǎn) 1；

(6)反向掃描優(yōu)化

從最低層的葉子結(jié)點開始，反向掃描擴展DOM樹。

若某一非葉子結(jié)點的max=1，且各子結(jié)點max=1、其結(jié)點表的鍵為上一級結(jié)點的鍵，則其對應(yīng)的結(jié)點表合并到上一級結(jié)點表，上一級結(jié)點表的鍵做為合并后的鍵；

(7)特殊元素處理規(guī)則

結(jié)點中min=0的葉子結(jié)點，構(gòu)造一張對應(yīng)的表，表名為葉子結(jié)點名，包含的列有：結(jié)點名，上一級結(jié)點的鍵做為外鍵。

對于包含文本內(nèi)容的普通結(jié)點，其對應(yīng)結(jié)點表中增加列，列名為結(jié)點名。

5.2 擴展DOM樹中約束結(jié)點的處理[8]

擴展DOM樹轉(zhuǎn)換為數(shù)據(jù)庫模式時必須對約束結(jié)點進行處理。根據(jù)Schema文檔轉(zhuǎn)換來的約束結(jié)點對其上一級結(jié)點進行必要的約束。這些約束的進行如下處理：數(shù)據(jù)類型約束轉(zhuǎn)換為數(shù)據(jù)庫的相應(yīng)數(shù)據(jù)類型；值域約束轉(zhuǎn)換為結(jié)點表的對應(yīng)列的取值范圍；結(jié)點默認(rèn)值約束用結(jié)點表的對應(yīng)列的默認(rèn)值實現(xiàn)；結(jié)點值長度約束通過結(jié)點表中列的長度約束實現(xiàn)；結(jié)點值的限定字符串通過正則表達式實現(xiàn)。

6 結(jié)束語

本文提出了由XML Schema文檔產(chǎn)生擴展DOM樹，進而生成對應(yīng)數(shù)據(jù)庫模式的方法。在轉(zhuǎn)換中使用路徑鍵保留了結(jié)點之間的關(guān)系。解決了傳統(tǒng)轉(zhuǎn)換方法中結(jié)點沖突、不能保留約束信息等問題。簡化轉(zhuǎn)換過程，代價較小，效率較高。

[1]袁文翠,左萬利.基于模式圖的規(guī)范化XML模式設(shè)計[J].計算機應(yīng)用研究,2006,(4),204-207.

[2]BOHANNON P,FREIRE J,ROY P,et al.From XML schema to relations:A cost2based approach to XML storage[M]//Proceedings of the 18th International Conf erence on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2002:64-75.

[3]寧靜,劉杰,葉丹.一種基于內(nèi)容模型圖的XML Schema Definition的提取方法[J].計算機科學(xué)，2010,(6):179-185.

[4]WANG G R.Extending XML schema with object-oriented features[J].Information Technology Journal,2005,4(1):44-54.

[5]E CC Tsang,D SYeung,X ZWang.OFFSS:Optimal Fuzzyvalued Feature Subset Selection[J].IEEE Transactions on Fuzzy Systems,2003,11(2).

[6]MartensW,Neven F,Sch wen tick T.Simple off the shelf abstractions for XML Schem a[J].ACM SIGM OD Record,2007,36(3):15-22.

[7]http://www.w3.org.

[8]李志輝.XMLSchema語義約束在關(guān)系數(shù)據(jù)庫中的實現(xiàn)[J].計算機與現(xiàn)代化,2009,(10),33-37.

The Algorithm for Convert XM L SCHEMA Document into Database Schema Based on Extended DOM Tree

LIU Biguang

（Fujian Communications Technology College，F(xiàn)uzhou，F(xiàn)ujian 350007）

By Analyze the problems of convert XML file document into Database,Proposed the algorithm of convert XML SCHEMA document into Database schema.Put forward the concept of extended DOM tree.Describes the algorithm of the expansion of DOM tree generated by XML Schema document.Illustrates the concept and the role of Path Key.Achieved the algorithm of convert Extended DOM tree into Database schema.In the implementation process,use the optimization of the reverse scan and the processing rules of special elements.

XML Schema；Extended DOM tree；Path Key；Database schema

TP311.13

A

1674－2109(2011)02－0056－05

2011-03-01

福建省教育廳科技項目(JA10284)。

劉必廣(1969-)，男,漢族，講師，碩士，主要研究方向:計算機應(yīng)用。