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

劉必廣

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

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

劉必廣

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

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

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

1 引言

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

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

2 相關(guān)工作

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

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

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

3 Schema文檔

3.1 Schema文檔定義

Schema用于定義XML文件[7]的邏輯結(jié)構(gòu)。為了便于實(shí)現(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ù)依賴(lài)的集合。

3.2 Schema文檔實(shí)例

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

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

其中：

4 產(chǎn)生擴(kuò)展DOM樹(shù)

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

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

4.1 擴(kuò)展DOM樹(shù)定義

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

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

擴(kuò)展DOM樹(shù)表示schema文檔的方法：

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

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

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

輸入：Schema文檔

輸出：擴(kuò)展DOM樹(shù)

掃描Schema文檔

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

(2)掃描Schema文檔當(dāng)前元素的各個(gè)子元素、屬性，若子元素為簡(jiǎn)單類(lèi)型且沒(méi)有下一級(jí)元素，則作為DOM樹(shù)的葉子結(jié)點(diǎn)；

(3)若Schema文檔當(dāng)前元素或?qū)傩缘哪骋蛔釉赜邢乱患?jí)元素，則該子元素作為DOM樹(shù)的中間結(jié)點(diǎn)；

(4)對(duì)于Schema文檔中復(fù)雜類(lèi)型的元素，作為DOM樹(shù)的中間結(jié)點(diǎn)，展開(kāi)其復(fù)雜類(lèi)型中包含的元素作為下一級(jí)元素，在DOM樹(shù)中作為下一級(jí)結(jié)點(diǎn)處理；

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

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

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

如圖1是Purchase.xml所對(duì)應(yīng)的擴(kuò)展DOM樹(shù)。

圖1.擴(kuò)展DOM樹(shù)

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

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

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

5.1 算法

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

輸入：擴(kuò)展DOM樹(shù)

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

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

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

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

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

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

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

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

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

從最低層的葉子結(jié)點(diǎn)開(kāi)始，反向掃描擴(kuò)展DOM樹(shù)。

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

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

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

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

5.2 擴(kuò)展DOM樹(shù)中約束結(jié)點(diǎn)的處理[8]

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

6 結(jié)束語(yǔ)

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

[1]袁文翠,左萬(wàn)利.基于模式圖的規(guī)范化XML模式設(shè)計(jì)[J].計(jì)算機(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]寧?kù)o,劉杰,葉丹.一種基于內(nèi)容模型圖的XML Schema Definition的提取方法[J].計(jì)算機(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語(yǔ)義約束在關(guān)系數(shù)據(jù)庫(kù)中的實(shí)現(xiàn)[J].計(jì)算機(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

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

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