基于扩展DOM树的XML SCHEMA文档转换为数据库模式算法

刘必广

（福建交通职业技术学院 福建 福州 350007）

基于扩展DOM树的XML SCHEMA文档转换为数据库模式算法

刘必广

（福建交通职业技术学院 福建 福州 350007）

通过分析XML文档转换成数据库文件存在的问题，提出基于扩展DOM树的XML Schema文档转换为数据库模式的算法。提出了扩展DOM树的概念。描述了由XMLSchema文档生成扩展DOM树算法。说明了路径键的概念及其作用。实现了将扩展DOM树转换成数据库模式的算法。实现过程使用了反向扫描优化和特殊元素处理规则。

XML Schema；扩展DOM树；路径键；数据库模式

1 引言

作为网络环境下数据传输的重要工具，XML文档得到越来越多的应用。在许多WEB应用中，应用程序将用户提交的数据以XML文档的形式传送到服务器。服务器在收到XML文档后，要根据事先约定的XML Schema模式进行分析，提取其中的用户数据保存在数据库中。服务器如何保存XML数据显得相当重要。

目前，传统方法中通过分析XML文档生成XML树。然后转换成一个对应的图模型[1]，再转换成数据库模式。这样转换过程复杂，而且不能保留元素间的包含关系信息。典型的算法是P_Schema算法[2]，该算法对XML Schema中包含子元素的元素进行单独求其模式，生成一个子模式，在求子模式过程时，没有处理元素间的包含关系[3]。另外，XML不同元素中可能存在同名子元素，在转换成数据库模式过程中[4]，这些元素可能存在冲突。在将XML文档信息存储到数据库中时，需要处理元素间的包含关系和元素间可能存在的冲突问题。

2 相关工作

将Schema文档转换为数据库模式时，要将Schema文档中的元素、属性、约束和元素间的包含关系对应成数据库模式中的字段和表间关系。

本文所采用的算法中，使用扩展DOM树表示Schema文档内容。在转换时，先将Schema文档用扩展DOM树表示，再通过遍历扩展DOM树生成Schema文档对应的数据库模式。为了解决转换时模式冲突问题，本文提出了基于路径键的处理方式，以处理元素和子元素之间的包含关系。在生成的模式中将父模式的键作为外键，以实现上下级的联系。在子模式中，根据函数依赖[5]关系使用上一级的键和本级的相关属性组成本级结点表的键。通过结点间键的逐层传递形成结点深度遍历的路径键。扩展DOM树每条深度遍历的路径[6]都有其相应的路径键。这样，就可以解决转换过程中元素之间的冲突问题。

通过转换DOM树各结点的子元素、属性、约束以及结点间的包含关系，能够完整存储XML Schema文档的信息；通过数据库的约束实现Schema文档中对数据的约束。

3 Schema文档

3.1 Schema文档定义

Schema用于定义XML文件[7]的逻辑结构。为了便于实现转换算法，本文将Schema文档定义为：Schema={Node，Attrib，Key，Path，Constraint，Funtion}。其中Node表示元素的集合，Attrib表示属性的集合，Key表示各元素键的集合，Path表示元素路径的集合，Constraint表示约束的集合，Function表示函数依赖的集合。

3.2 Schema文档实例

如XML Schema文档Purchase·xml所示。从文档结构和语义可知，其Schema文档可定义为：

PurchaseSchema={Node，Attrib，Key，Path，Constraint，Funtion}

其中：

4 产生扩展DOM树

为了准确完整地表示Schema文档信息，要有一个模型。这个模型除了能够表达元素数据，还要存储Schema文档元素间的层次关系、元素的属性、约束以及元素的包含关系。一般的DOM树能够表达Schema文档元素间的关系和元素属性。无法表示Schema文档元素间包含关系及元素的约束。本文使用扩展DOM树来表示Schema文档，以完整表达这些信息。

扩展DOM树使用结点表示Schema文档元素，结点还包含Schema元素的约束信息。使用结点间的联系表示Schema文档元素之间的关系。

4.1 扩展DOM树定义

为了便于将Schema文档转换为数据库模式，首先将Schema文档表示的XML文档模式转换为扩展DOM树表示。

扩展DOM树定义：用树的形式存储Schema文档信息，使用结点表示Schema文档普通元素、属性和约束，使用父子结点间的联系方式表示Schema文档中元素间的关系，叶子表示没有子元素的元素。使用联系表示元素间的包含关系。

扩展DOM树表示schema文档的方法：

4.2 Schema文档产生扩展DOM树算法

通过扫描Schema文档对应Schema文档的元素、属性、约束以及元素之间的关系进行必要处理，生成满足定义要求的扩展DOM树。产生扩展DOM树算法为：

算法1:Schema文档产生扩展DOM树

输入：Schema文档

输出：扩展DOM树

扫描Schema文档

(1)Schema文档根元素作为扩展DOM树根结点，并设置根结点为当前结点；

(2)扫描Schema文档当前元素的各个子元素、属性，若子元素为简单类型且没有下一级元素，则作为DOM树的叶子结点；

(3)若Schema文档当前元素或属性的某一子元素有下一级元素，则该子元素作为DOM树的中间结点；

(4)对于Schema文档中复杂类型的元素，作为DOM树的中间结点，展开其复杂类型中包含的元素作为下一级元素，在DOM树中作为下一级结点处理；

(5)DOM树中当前结点到各子结点的连线上以形式标明对应子结点的最大元素数和最小元素数；作为结点间的联系。

(6)读取Schema文档中当前元素的限定设置，作为扩展DOM树结点的约束；

(7)依次设置Schema文档中当前元素中的包含下级元素的元素为当前元素为扩展DOM树的当前结点，转(2)。

如图1是Purchase.xml所对应的扩展DOM树。

图1.扩展DOM树

5 扩展DOM树生成数据库模式算法

通过遍历扩展DOM树，根据各个结点和上一级结点的关系生成相应的结点表。生成结点表过程中，将上级结点表的键加入到结点表中，做为结点表键的一部分。这样保留了扩展DOM树中结点之间的联系。对于联系中max>1的结点进行特殊处理，生成相应的结点表。

在生成结点表时，保留扩展DOM树中结点信息的同时保留结点的关系及约束信息。

5.1 算法

算法2:扩展DOM树生成数据库模式

输入：扩展DOM树

输出：优化数据模式

广度遍历扩展DOM树，先设置根结点为当前结点

(1)为当前结点创建一张结点表，广度遍历各子结点；

(2)若不是根结点，则根据函数依赖关系设置上一级结点的键和当前结点表的的相关属性组成键，形成本结点表的路径键；

若子结点为叶子结点且其max=min=1，则作为表的一个列，列名为叶子结点名。确定结点表的键及属性间的函数依赖；

(3)若子结点为叶子结点且其max>1，则构造一张对应的叶子表，包含的列有：叶子结点名，当前结点表的键做为叶子表的外键；

(4)对于约束结点，根据其内容对其对应的结点表或列进行约束设置；

(5)广度遍历当前结点的各子结点中非叶子结点，转 1；

(6)反向扫描优化

从最低层的叶子结点开始，反向扫描扩展DOM树。

若某一非叶子结点的max=1，且各子结点max=1、其结点表的键为上一级结点的键，则其对应的结点表合并到上一级结点表，上一级结点表的键做为合并后的键；

(7)特殊元素处理规则

结点中min=0的叶子结点，构造一张对应的表，表名为叶子结点名，包含的列有：结点名，上一级结点的键做为外键。

对于包含文本内容的普通结点，其对应结点表中增加列，列名为结点名。

5.2 扩展DOM树中约束结点的处理[8]

扩展DOM树转换为数据库模式时必须对约束结点进行处理。根据Schema文档转换来的约束结点对其上一级结点进行必要的约束。这些约束的进行如下处理：数据类型约束转换为数据库的相应数据类型；值域约束转换为结点表的对应列的取值范围；结点默认值约束用结点表的对应列的默认值实现；结点值长度约束通过结点表中列的长度约束实现；结点值的限定字符串通过正则表达式实现。

6 结束语

本文提出了由XML Schema文档产生扩展DOM树，进而生成对应数据库模式的方法。在转换中使用路径键保留了结点之间的关系。解决了传统转换方法中结点冲突、不能保留约束信息等问题。简化转换过程，代价较小，效率较高。

[1]袁文翠,左万利.基于模式图的规范化XML模式设计[J].计算机应用研究,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]宁静,刘杰,叶丹.一种基于内容模型图的XML Schema Definition的提取方法[J].计算机科学，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语义约束在关系数据库中的实现[J].计算机与现代化,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，Fuzhou，Fujian 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-)，男,汉族，讲师，硕士，主要研究方向:计算机应用。