论文部分内容阅读
【摘要】为解决数据库关系模式与XML模式间的转换问题,在分析XML Schema复杂类型模式信息和元素定义机制的基础上,构造了XML Schema抽象模型(AXSM),依据AXSM,提出一种把数据库的关系模式转换为XML模式的方法,利用元素模式的定义函数和基本约束条件转换函数可以基本保存关系模式中的结构和语义信息。
【关键词】XML Schema 关系模式 转换
【中图分类号】TP331 【文献标识码】A 【文章编号】1009-9646(2008)10(b)-0150-02
1 引言
20世纪70年代,随着数据库技术的迅猛发展,相继产生了关系型数据库和分布式数据,带来了数据库系统的繁荣以及数据库应用的普及,然而由此也带来了新问题——不同发展阶段、不同应用目的而产生的不同数据库系统无法结合在一起共同使用。
为解决上述问题,人们提出了基于XML文档的数据交换技术。该技术首先要解决数据库关系模式与XML模式之间的映射问题[1]。而一个XML模式能否精确描述被转换关系模式的结构和语义,对生成XML文档是非常重要的。目前已有一些方法实现关系模式与XML模式间的映射,但都存在一些不足,如:平面转化算法[2]无法实现运算符 +、?和*的转化;NET算法[3]不能从一个具有很多表的关系模式向XML模式转化。本文针对关系模式,在分析XML Schema复杂类型模式信息和元素定义机制[4]的基础上,构造了XML Schema抽象模型(Abstract XML Schema Model,简称 AXSM),依据AXSM,提出一种从数据库的关系模式到XML模式间的映射方法。该方法基本可以保存关系模式中的结构和语义信息。
2 关系模式模型
在关系数据库中,数据的逻辑结构是由关系模式(Relation Schema Model,简称RSM)决定的。 RSM反映如下信息:规定数据库中表与列、列与其数据类型的映射关系;提供表间的完整约束关系。
定义1数据库的关系模型为六元组{T,C,P,fieldt,typec,G},其中:
(1)T为有限表。名集;
(2)C为有限字段集,当不同的表有相同的字段名时,加上表名区分字段名;
(3)P为有限类型集;
(4)函数fieldt:T→C:t∈T ,Ct∈C,指定表t的字段子集Ct;
(5)函数typec:C→α:c c∈E∈P,而c∈E∈P表示一个三元组{p,u,n},其中:
①p表示某一类型,p∈E;
②u表示值是否唯一;
③n表示值是否为空;
(6)G为约束图,定义表间的完整性约束关系。
3 基本约束条件
在RSM中,通过约束图G来描述该模型所包含表的依赖关系,最常见的关系为主外键约束。
定义2约束图G为三元组{V,E,top},其中:
(1)V为有限节点集;
(2)E为有向边集;
(3)top表示图G的顶点。
对于数据库关系模式中的每一张表t,在图G中都有一个节点v与之对应。假设表t1的字段a是外键,指向表t2的字段b,b是t2的主键。对于每一个主外键约束条件,t1(a)t2(b),在图G中都有一条有向边e与之对应,起点是表t2的节点b,终点为表t1的节点。不被其他节点指向的节点称为顶点,用top表示。
4 XML Schema抽象模型
XML Schema作为XML文档的模式语言,将元素的模式分为简单类型和复杂类型[5]。简单类型元素是指不嵌套任何子元素的元素,反之则称为复杂类型元素。复杂类型元素在XML Schema中子元素的模式定义为复杂类型的模式信息。XML Schema元素的定义机制规定,所有简单类型元素都必须定义为某个简单类型(内建数据类型,或在此基础上自定义的数据类型),所有复杂类型元素都可以通过它的下一级子元素来确定,并用min Occurs和max Occurs表示该子元素出现的次数。
依据XML Schema中复杂类型模式信息和元素定義机制,用一个抽象模型来表示XML Schema,称该模型为XML Schema抽象模型(AXSM)。AXSM反映如下信息:规定XML文档实例中根节点元素的类型唯一;用正则表达式[6]及其对应的有限自动机来描述原XML Schema中复杂类型的模式信息,正则表达式同时明确了嵌套在元素中的子元素可以被实例化的数量范围,“+”表示一次或多次,“?”表示零次或一次,“*”表示零次或多次;每个复杂类型对应一个映射关系表,给出嵌套在复杂类型元素中子元素的类型。
定义3一个XML Schema的AXSM为四元组{∑,Γ,ρ,typeroot},其中:
(1)∑为有限元素集;
(2)Γ为有限类型集;
(3)ρ为复杂类型声明集,对于每个复杂类型f∈Γ,其声明都用唯一的(regexpf,typesf)序对来表示,其中:
①正则表达式regexpf表示了f的模式信息,即允许嵌套在复杂类型元素中的子元素序列; regexpf中的元素属于∑的某个子集,记为∑f∑; L(regexpf)表示符合正则表达式regexpf的元素序列集合;
②函数typesf:∑f→Γ,tag∈∑t,f∈Γ,指定∑f中元素的类型。
(4)typeroo,为根节点元素类型。
5 从AXSM模式生成XML模式的方法
从数据库的关系模式生成XML Schema模式,必须(1)确定原关系模型中的哪些信息映射成 XML Schema文档中的何种元素,并明确其元素类型。(2)完成数据库约束条件的转换。
在具体实现时,我们设计了两个子函数:元素定义模式函数X Schema (R)和基本约束条件转换函数 ADDREF(R,S)。X Schema (R)将关系模型中的表和列按照——映射的方法转换成XML Schema中的复杂类型,并根据RSM中对于字段的定义,明确了复杂类型中的子元素的相关信息。ADDREF(R,S)利用广度优先遍历算法[7]遍历约束图G中的所有的节点和边,来构造一个带有原关系模式的约束条件．通过调用上述两个函数,可完成关系模式到XML Schema的映射,其工作流程为:
(1)生成一个带名字空间的Schema标志。
(2)利用元素定义模式函数X Schema (R)为每个关系表生成一个元素的复杂类型,关系表中的每一个字段作为XML Schema中复杂类型的子元素,并添加对应类型和出现次数。
(3)利用基本约束条件转换函数ADDREF(R,S),给出所有复杂类型的嵌套关系。
(4) 添加一个复杂类型元素,指定约束图G中的top顶点为它的唯一元素,并将TOP顶点对应的复杂类型定义为子元素类型,其给表示该元素出现最小次数的min Occurse赋0值,给表示最大次数的max Occurs赋unbounded值。
(5)为XML Schema文档添加一个根元素,并将第四步中给出的复杂类型定义为根元素类型。
5.1 元素模式的定义函数X Schema(R)
元素模式的定义主要完成:把关系模式中的表t转换为AXSM中的复杂类型f;将关系模式中的各个表t所对应的字段Ct作为该表映射的复杂类型的模式信息;根据各个字段c对应的α来明确运算符+,?或*;规定表映射为AXSM中复杂类型名。
构造XML Schema中元素模式定义的算法框架如下:
输入:R为数据库的关系模式模型
输出:该关系模式模型对应的XML Schema抽象模型S
(1)设置一个数据结构Ct,用于表示当前表t的字段集;
(2)For表集T中的每张表t
(3)为表t新建一个复杂类型f,S←f;
(4)Ct→field t(t);
(5)For字段集Ct中的每个字段c;
(6)为复杂类型f新建一个子元素e,e＝c;
(7)获取type e(c)→p定义的类型来设置f→type c(e)的值;
(8) If(type c(c)→u的值为唯一);
(9) 子元素e的min Occurs置1;
(10)Else
(11)子元素e的min Occurs置0;
(12)If (type c(c)→n的值为空)
(13)子元素e的min Occurs置0;
(14)Else
(15)子元素e的min Occurs置1;
(16)maxOccurs置1;
(17)if(e的min Occurs为1)
(18)(f→regexpf)←e;
(19)返回S
5.2 基本约束条件转换函数ADDREF(R,S)
基本约束条件转换函数ADDREF (R,S)通过广度遍历约束图G向XML Schema中添加约束条件。其算法框架如下:输入:R为数据库的某个关系模式模型
S为XML Schema抽象模型
输出:该关系模式模型对应的XML Schema抽象模型S
(1)设置一个队列T,用v表示队中元素,v→e list表示子节点;
(2)将R→G→top节点人队;
(3)从R→G→E中获取以v作为起点的有向边,并将终点加入v的子节点;
(4)While队中元素不为空
(5)For v→e list中的每一个子节点w
(6)获取从v到w的有向边,
(7)在S中获取v对应的复杂类型fv,w对应的复杂类型fw;
(8)fv→regex pf,w,其中:w的min occurs为0;max occurs为unbounded,表示无穷多;
(9) 设置fv→type sf(w)的值为fw;
(10)w节点人队;
(11)v节点出队
(12)返回S
6 小结
基于XML Schema的关系模式到XML模式的映射方法,可将若干相互关联的表的逻辑结构转换成一个完整的XML Schema文档,同时保留原关系模式中相应的结构和语义信息。从而保证了XML文档的有效性,提高了XML文档的质量。因此该映射方法具有一定的实用意义。
参考文献
[1] D.Lee, W. W. Chu, Constraints-Preserving Inlining Algorithm for Mapping XML DTD to Relation Schema,Journal of Data Knowledge Engineering,2002 39:3-25.
[2] Ashvin Radiya,Vibba Dixit.The Basks of using XML Schema to defineelement,http://www2128,ibm.com.developer-works,xml.library,xml2sehema,2001.8.1.
[3] L.segoufin,V.Vianu, Validation streaming XML documents. PODS2002,2002,53-64.
[4] Beatric Bouehou,Mirian Halfeld FerrariAlves,Extending Tree Automa2ta to Model XML Validation Under Element and Attribute Constraints.ICEIS(1),2003,184-190.
[5] Henry S Thomp son et al, XML Schema Part 1:Structures.http://www. w3. org. TR. xmlschema-1,2004. 10. 28.
[6] Bruggemann2Klein A. Wood D,One2unambiguous regular languages.Information and Computation,1998,140 (2),229-255.
[7] [美] Kenneth C. Louden, Compiler Construction Prineip les and Prac2tice.北京:中國机械出版社. 2002.8,64-74.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
【关键词】XML Schema 关系模式 转换
【中图分类号】TP331 【文献标识码】A 【文章编号】1009-9646(2008)10(b)-0150-02
1 引言
20世纪70年代,随着数据库技术的迅猛发展,相继产生了关系型数据库和分布式数据,带来了数据库系统的繁荣以及数据库应用的普及,然而由此也带来了新问题——不同发展阶段、不同应用目的而产生的不同数据库系统无法结合在一起共同使用。
为解决上述问题,人们提出了基于XML文档的数据交换技术。该技术首先要解决数据库关系模式与XML模式之间的映射问题[1]。而一个XML模式能否精确描述被转换关系模式的结构和语义,对生成XML文档是非常重要的。目前已有一些方法实现关系模式与XML模式间的映射,但都存在一些不足,如:平面转化算法[2]无法实现运算符 +、?和*的转化;NET算法[3]不能从一个具有很多表的关系模式向XML模式转化。本文针对关系模式,在分析XML Schema复杂类型模式信息和元素定义机制[4]的基础上,构造了XML Schema抽象模型(Abstract XML Schema Model,简称 AXSM),依据AXSM,提出一种从数据库的关系模式到XML模式间的映射方法。该方法基本可以保存关系模式中的结构和语义信息。
2 关系模式模型
在关系数据库中,数据的逻辑结构是由关系模式(Relation Schema Model,简称RSM)决定的。 RSM反映如下信息:规定数据库中表与列、列与其数据类型的映射关系;提供表间的完整约束关系。
定义1数据库的关系模型为六元组{T,C,P,fieldt,typec,G},其中:
(1)T为有限表。名集;
(2)C为有限字段集,当不同的表有相同的字段名时,加上表名区分字段名;
(3)P为有限类型集;
(4)函数fieldt:T→C:t∈T ,Ct∈C,指定表t的字段子集Ct;
(5)函数typec:C→α:c c∈E∈P,而c∈E∈P表示一个三元组{p,u,n},其中:
①p表示某一类型,p∈E;
②u表示值是否唯一;
③n表示值是否为空;
(6)G为约束图,定义表间的完整性约束关系。
3 基本约束条件
在RSM中,通过约束图G来描述该模型所包含表的依赖关系,最常见的关系为主外键约束。
定义2约束图G为三元组{V,E,top},其中:
(1)V为有限节点集;
(2)E为有向边集;
(3)top表示图G的顶点。
对于数据库关系模式中的每一张表t,在图G中都有一个节点v与之对应。假设表t1的字段a是外键,指向表t2的字段b,b是t2的主键。对于每一个主外键约束条件,t1(a)t2(b),在图G中都有一条有向边e与之对应,起点是表t2的节点b,终点为表t1的节点。不被其他节点指向的节点称为顶点,用top表示。
4 XML Schema抽象模型
XML Schema作为XML文档的模式语言,将元素的模式分为简单类型和复杂类型[5]。简单类型元素是指不嵌套任何子元素的元素,反之则称为复杂类型元素。复杂类型元素在XML Schema中子元素的模式定义为复杂类型的模式信息。XML Schema元素的定义机制规定,所有简单类型元素都必须定义为某个简单类型(内建数据类型,或在此基础上自定义的数据类型),所有复杂类型元素都可以通过它的下一级子元素来确定,并用min Occurs和max Occurs表示该子元素出现的次数。
依据XML Schema中复杂类型模式信息和元素定義机制,用一个抽象模型来表示XML Schema,称该模型为XML Schema抽象模型(AXSM)。AXSM反映如下信息:规定XML文档实例中根节点元素的类型唯一;用正则表达式[6]及其对应的有限自动机来描述原XML Schema中复杂类型的模式信息,正则表达式同时明确了嵌套在元素中的子元素可以被实例化的数量范围,“+”表示一次或多次,“?”表示零次或一次,“*”表示零次或多次;每个复杂类型对应一个映射关系表,给出嵌套在复杂类型元素中子元素的类型。
定义3一个XML Schema的AXSM为四元组{∑,Γ,ρ,typeroot},其中:
(1)∑为有限元素集;
(2)Γ为有限类型集;
(3)ρ为复杂类型声明集,对于每个复杂类型f∈Γ,其声明都用唯一的(regexpf,typesf)序对来表示,其中:
①正则表达式regexpf表示了f的模式信息,即允许嵌套在复杂类型元素中的子元素序列; regexpf中的元素属于∑的某个子集,记为∑f∑; L(regexpf)表示符合正则表达式regexpf的元素序列集合;
②函数typesf:∑f→Γ,tag∈∑t,f∈Γ,指定∑f中元素的类型。
(4)typeroo,为根节点元素类型。
5 从AXSM模式生成XML模式的方法
从数据库的关系模式生成XML Schema模式,必须(1)确定原关系模型中的哪些信息映射成 XML Schema文档中的何种元素,并明确其元素类型。(2)完成数据库约束条件的转换。
在具体实现时,我们设计了两个子函数:元素定义模式函数X Schema (R)和基本约束条件转换函数 ADDREF(R,S)。X Schema (R)将关系模型中的表和列按照——映射的方法转换成XML Schema中的复杂类型,并根据RSM中对于字段的定义,明确了复杂类型中的子元素的相关信息。ADDREF(R,S)利用广度优先遍历算法[7]遍历约束图G中的所有的节点和边,来构造一个带有原关系模式的约束条件．通过调用上述两个函数,可完成关系模式到XML Schema的映射,其工作流程为:
(1)生成一个带名字空间的Schema标志。
(2)利用元素定义模式函数X Schema (R)为每个关系表生成一个元素的复杂类型,关系表中的每一个字段作为XML Schema中复杂类型的子元素,并添加对应类型和出现次数。
(3)利用基本约束条件转换函数ADDREF(R,S),给出所有复杂类型的嵌套关系。
(4) 添加一个复杂类型元素,指定约束图G中的top顶点为它的唯一元素,并将TOP顶点对应的复杂类型定义为子元素类型,其给表示该元素出现最小次数的min Occurse赋0值,给表示最大次数的max Occurs赋unbounded值。
(5)为XML Schema文档添加一个根元素,并将第四步中给出的复杂类型定义为根元素类型。
5.1 元素模式的定义函数X Schema(R)
元素模式的定义主要完成:把关系模式中的表t转换为AXSM中的复杂类型f;将关系模式中的各个表t所对应的字段Ct作为该表映射的复杂类型的模式信息;根据各个字段c对应的α来明确运算符+,?或*;规定表映射为AXSM中复杂类型名。
构造XML Schema中元素模式定义的算法框架如下:
输入:R为数据库的关系模式模型
输出:该关系模式模型对应的XML Schema抽象模型S
(1)设置一个数据结构Ct,用于表示当前表t的字段集;
(2)For表集T中的每张表t
(3)为表t新建一个复杂类型f,S←f;
(4)Ct→field t(t);
(5)For字段集Ct中的每个字段c;
(6)为复杂类型f新建一个子元素e,e＝c;
(7)获取type e(c)→p定义的类型来设置f→type c(e)的值;
(8) If(type c(c)→u的值为唯一);
(9) 子元素e的min Occurs置1;
(10)Else
(11)子元素e的min Occurs置0;
(12)If (type c(c)→n的值为空)
(13)子元素e的min Occurs置0;
(14)Else
(15)子元素e的min Occurs置1;
(16)maxOccurs置1;
(17)if(e的min Occurs为1)
(18)(f→regexpf)←e;
(19)返回S
5.2 基本约束条件转换函数ADDREF(R,S)
基本约束条件转换函数ADDREF (R,S)通过广度遍历约束图G向XML Schema中添加约束条件。其算法框架如下:输入:R为数据库的某个关系模式模型
S为XML Schema抽象模型
输出:该关系模式模型对应的XML Schema抽象模型S
(1)设置一个队列T,用v表示队中元素,v→e list表示子节点;
(2)将R→G→top节点人队;
(3)从R→G→E中获取以v作为起点的有向边,并将终点加入v的子节点;
(4)While队中元素不为空
(5)For v→e list中的每一个子节点w
(6)获取从v到w的有向边,
(7)在S中获取v对应的复杂类型fv,w对应的复杂类型fw;
(8)fv→regex pf,w,其中:w的min occurs为0;max occurs为unbounded,表示无穷多;
(9) 设置fv→type sf(w)的值为fw;
(10)w节点人队;
(11)v节点出队
(12)返回S
6 小结
基于XML Schema的关系模式到XML模式的映射方法,可将若干相互关联的表的逻辑结构转换成一个完整的XML Schema文档,同时保留原关系模式中相应的结构和语义信息。从而保证了XML文档的有效性,提高了XML文档的质量。因此该映射方法具有一定的实用意义。
参考文献
[1] D.Lee, W. W. Chu, Constraints-Preserving Inlining Algorithm for Mapping XML DTD to Relation Schema,Journal of Data Knowledge Engineering,2002 39:3-25.
[2] Ashvin Radiya,Vibba Dixit.The Basks of using XML Schema to defineelement,http://www2128,ibm.com.developer-works,xml.library,xml2sehema,2001.8.1.
[3] L.segoufin,V.Vianu, Validation streaming XML documents. PODS2002,2002,53-64.
[4] Beatric Bouehou,Mirian Halfeld FerrariAlves,Extending Tree Automa2ta to Model XML Validation Under Element and Attribute Constraints.ICEIS(1),2003,184-190.
[5] Henry S Thomp son et al, XML Schema Part 1:Structures.http://www. w3. org. TR. xmlschema-1,2004. 10. 28.
[6] Bruggemann2Klein A. Wood D,One2unambiguous regular languages.Information and Computation,1998,140 (2),229-255.
[7] [美] Kenneth C. Louden, Compiler Construction Prineip les and Prac2tice.北京:中國机械出版社. 2002.8,64-74.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”