摘 要:一种使各种关系模式生成技术都可以直接利用SilkRoute中的XQuery转换算法作为自己的查询处理器的方法,从而省去构造查询处理器的复杂工作,提高查询处理效率。

关键词:XML文档 SilkRoute框架 View Forest结构 共享内嵌

　　随着XML文档的大量涌现,如何有效地存储和查询这些文档中的数据已成为业界关注的问题。通常,将XML数据映射为关系数据,再利用经典的关系数据库系统来管理XML是一种有效的解决方法。该映射过程大致分为3步:(1)产生关系模式,创建存储XML数据的关系表;(2)将XML数据分片,存入相应的关系表中;(3)处理XML的查询,将其转化为等价的SQL语句。目前通用的XML查询语言是由W3C提出的XQuery,其描述功能强大,通常由多个子查询合成,且带有复杂的文档结构信息。然而将XQuery转换成一组等价的SQL语句是一项复杂的工作,而且这种转换和具体的关系模式生成技术密切相关。不同的生成技术需要开发相应的查询处理器。

　　本文提出了一种有效的方法,使不同的关系模式生成技术可共享通用查询处理器,且该查询处理器无需自己开发,可直接应用著名的SilkRoute[1]中转换Xquery的算法。这样就可以大大降低开发强度,提高工作效率。

1 构造View Forest

　　SilkRoute是一种发布关系数据的框架。它将关系数据映射为规定格式的XML数据,以便在网络上传输和交换。它提供了一个XQuery转换算法,可将基于XML数据的XQuery查询转化为基于关系数据的SQL查询,在数据库引擎上执行后,再把得到的结果按照XQuery中定义的结构组成XML文档。

　　SilkRoute可通过View Forest结构来进行XQuery查询到SQL语句的转换。View Forest是由若干棵树组成的森林,其每个结点都包含一个XML标签和一个SQL语句片断。从语义角度看,View Forest定义了从关系数据库到XML文档的一个映射。它的结点、边和结点的XML标签表示了XML文档的结构,而结点的SQL语句片断则表示了由关系数据产生XML文档内容的计算过程。其中,View Forest的内部结点(即非叶结点)表示XML文档中的元素或属性,它的XML标签即是相应的元素或属性的名称。其SQL片断只包含From子句和Where子句,指定该结点从数据库中选取数据的范围;边表示XML数据间的包含关系;叶结点表示其父结点的值,它的XML标签为值的类型,其SQL片断一般只包含select子句,表明具体选择关系表中与父结点值相对应的某列属性。

　　SilkRoute中转换XQuery的关键算法是VFCA(View Forest合成算法)。它将XQuery查询涉及到的所有XML数据对应的View Forest作为输入,通过递归调用VFCA,对XQuery表达式逐个转化,得到表示查询结果的View Forest;再根据所得View Forest中每个结点的SQL片断合成完整的SQL语句,从关系数据库中取得准确的数据,最终生成查询结果文档。

　　本文的研究对象是利用关系数据库来存储和管理XML的系统。它将XML数据映射为关系数据,与SilkRoute的工作过程正好相反。但这二个系统中都定义了关系数据和XML数据之间的映射关系,都需要完成转换XQuery的任务。因此,在本文研究的系统中,可以将View Forest作为桥梁,应用SilkRoute提供的算法。即在利用关系数据库存储和管理XML的系统中,可以先构造出与源XML数据对应的View Forest,然后以它作为输入参数,使用SilkRoute中的VFCA算法及其他辅助算法,将Xquery查询转化成SQL语句,再把查询结果按要求组成XML文档。这种查询转换方法能适用于多种关系模式生成技术。各种生成技术都可通过构造View Forest,将SilkRoute中转换XQuery的算法作为自己的查询处理器,省去自行编写查询处理器的复杂工作。

　　View Forest结构显示了XML文档和关系数据之间的映射关系。所以,根据XML数据的结构信息和在关系数据库中的存储模式,可轻松地构造View Forest。算法的基本思路如下:

　　(1)根据XML中的元素、属性及它们之间的包含关系生成View Forest中所有的内部结点和边。内部结点表示了XML的元素或属性,它的XML标签即为元素或属性的名称;边表示结点之间的包含关系。

　　(2)为View Forest中的每个属性结点和每个包含文本值的元素结点创建一个子结点,其XML标签为其父结点值的类型。该子结点即为View Forest中的叶结点。

　　(3)对于View Forest中的每个内部结点,根据其所有祖先元素的SQL片断以及该结点的数据在关系数据库中的存储情况构造它的SQL语句片断。对于每个叶结点,则根据其父结点值在关系表中对应的列名构造其SQL片断。

　　对于不同的关系模式生成技术,构造View Forest的具体算法也有所不同。下面介绍利用常见的关系模式生成技术——共享内嵌技术构造View Forest的方法。

2 共享内嵌关系模式下的View Forest构造算法

　　作为实例分析,本节将对使用共享内嵌(shared inline)技术生成的关系模式给出构造View Forest的具体算法。

2.1 共享内嵌技术

　　共享内嵌技术根据XML的DTD(或Schema)创建适当的关系表。现以XML文档(程序1)和其DTD(程序2)中数据为例来演示创建过程。

(1)对DTD进行简化,得到对应的DTD图(见图1(a))。DTD图中包含2类结点:一类是表示XML元素或属性的结点(称为元素结点或属性结点);另一类是符号结点,即‘？’或‘*’,介于父元素结点和子元素结点之间,表示子元素在父元素中的出现次数。

(2)遍历DTD图。对于DTD图中入度为0或者入度大于1的元素结点(如图1(a)中的Dep和Name)创建独立的关系表存储。对入度为1的元素结点和属性结点(例如Intro),则内嵌到存储父元素的关系表中,作为某个字段存储。对‘*’下面的子元素结点(例如Stud和Tea),也要创建独立的关系表予以存储。

　　每个关系表都有id字段作为主键。除了根元素关系表外,其他关系表中都有parentid字段作为外键,引用其父元素所在关系表中的id,以提供该元素与其父元素之间的链接。而入度大于1的元素结点(例如Name),由于存在多个父元素结点,所以其对应的关系表中增加了parentCode字段,存储父表的编号。生成的关系表如图1(b)。

　　程序1:XML文档

Jack

Chris

Ada

Grace

　　程序2:DTD

2.2 View Forest构造算法

　　将图1(a)所示的DTD图进行简化,去掉所有的符号结点,可得简化后的DTD图(如图1(c))。以此为基础构造View Forest的算法详见算法1(该算法假设DTD中不存在循环结构)。

　　算法1:对应于共享内嵌关系模式生成技术的View Forest构造算法

　　Generate_node(DTDGraphNode Dnode,ViewForestNode VparentNode)

　　1.　　{ prefixName:=′′;/*先将prefixName(列名前缀)置空,

　　　　　列名前缀为若干层祖先的名字,用′.′隔开。例如Dep

　　　　　表中的Dep.Intro字段,“Dep.”就是列名前缀*/

　　2. 　 if ( Dnode is type Element ) then//若Dnode

　　　　　//是元素结点

　　3. 　　{ XMLLabel:=Dnode.Name;

　　4. 　　if ( Dnode is stored in a separate table from

　　　　　 parent ) then

　　5. 　　{ tName:=getTableName(Dnode);//取得存储

　　　　　//Dnode元素的关系表名

　　6. 　 alias:=GenAlias(tName);//运用某种规则为

　　　　　//该表产生一个别名,不得与已有别名重复

　　7. 　 SQLFragment:=′From′+tName+′as′+alias;

　　　　　//待生成的View Forest结点的SQL片断

　　8.　　if ( not Dnode.isRoot ) then　　//若Dnode不是

　　　　　//根元素结点,则需要找到parentid引用的父表

　　9. 　 { tempvfnode:=VparentNode;

　　　　　/*找到Form子句不为空的那个祖先,它的From子句

　 中的表的别名就是需要找的父表别名*/

　　10. 　while tempvfnode.SQLFragment.From=′′do

　　11. tempvfnode:=tempvfnode.parent;

　　12. ptName:=tempvfnode.SQLFragment.From.alias;

　　　　　//ptName为找到的父表的别名

　　13. SQLFragment:=SQLFragment+′where′+alias

　　　　　+′.parentid=′+ptName+′.id′;}

　　14. tName:=alias;//下面引用tName时,

　　　　　//都引用的是其别名

　　15.　　}

　　16. else//Dnode的数据和祖先元素的数据

　　　　　//存在一张关系表的情况,即Dnode是内嵌元素

　　17. { tempvfnode:=VparentNode;//寻找该Dnode

　　　　　//数据存放的表

　　18.　 while tempvfnode.SQLFragment.From=′′do

　　19. 　{ tempvfnode:=tempvfnode.parent;

　　20. prefixName:=tempvfnode.XMLLabel+′.′

　　　　　+prefixName;}

　　21. tName:=tempvfnode.SQLFragment.From.alias;

　　　　　//找到存放Dnode表的别名

　　22. prefixName:=tempvfnode.XMLLabel+′.′+

　　　　　prefixName;//获得正确的列名前缀

　　23. SQLFragment:=′From()′;//由于是内嵌元素,

//所以SQL片断为空

24. }

25. }

26. if ( Dnode is type Attribute ) then//如果Dnode

//是属性结点,则一定内嵌在元素表中

27. ... //与处理内嵌元素的方法相同,省略(惟一区别是

XMLLabel:=′@′+Dnode.Name)

28. newvfnode:=VF.new(XMLLabel,SQLFragment);

//构造View Forest中Dnode对应的结点

29. newvfnode.parent:=VparentNode;//把该新结点

//加入为VparentNode的一个子结点

30. if (Dnode is type element with text,or Dnode is

type attribute ) then //构造叶结点

31. { XMLLabel:=Type(Dnode.Value);//XML标签

//为值的类型

32. SQLFragment:=′SELECT′+tName+′.′+prefixName

+Dnode.Name;

33. newatomicnode:=VF.new(XMLLabel,SQLFragment);

34. newatomicnode.parent:=newvfnode;}//叶结点的

//父结点即为刚刚构造的newvfnode

35. for every ChildNode in Dnode.Children do

//对于Dnode的所有子结点,递归调用该函数

36. Generate_node(ChildNode,newvfnode);

算法1的核心是Generate_node函数,它以DTD图中的结点作为输入,创建与之相对应的View Forest结点。函数包含2个参数:Dnode和VparentNode。Dnode是DTD图中的某个结点,VparentNode是View Forest中与Dnode的父结点相对应的结点。Generate_node函数是递归函数,它先作用于DTD图的根结点(这里为Dep,此时VparentNode参数为空),创建View Forest的根结点;再按照深度优先顺序递归处理DTD图中其余结点,从而创建View Forest中相应的子孙结点。函数处理过程具体分为4个步骤:

(1)首先根据Dnode的信息,得到待创建的View Forest结点的XML标签和SQL片断。XML标签即为Dnode所表示的元素或属性的名称(行3)。SQL片断则要分3种情况处理:

①若Dnode为XML中根元素结点,则SQL片断形式为:From 根元素表 as 别名(行7)。其中根元素表即是数据库中存储根元素的关系表。

②若Dnode为XML中普通元素结点,且数据库中将该元素数据单独存为一张关系表,则SQL片断形式为:From 子表 as 子表别名 where 子表别名.parentid=父表别名.id(行13)。其中子表为存储该元素的关系表,父表为其外键parentid引用的关系表。从VparentNode或其祖先结点的SQL语句片断中可得父表的别名(因为VparentNode是待创建结点的父结点,行10～12)。若存储该元素的关系表中还存在parentCode字段(如图1中的Name表),则还需根据父表表名在Where子句中限定parentCode的值,算法中省略了这一点。

③若Dnode是内嵌元素或属性结点,则由于Dnode的数据内嵌于祖先元素表中,并未产生新的数据选取范围,所以SQL片断为空(即From(),行23)。

(2)根据XML标签和SQL片断创建新的View Forest结点newvfnode(行28),再把新结点作为VparentNode的子结点加入到View Forest中。

(3)若Dnode结点为属性结点或包含文本值的元素结点,则继续创建newvfnode的子结点newatomicnode(行31～35),即为View Forest中的叶结点。其XML标签为父结点值的类型,SQL片断形式为select表别名.字段名。其中表别名是存储Dnode的关系表的别名,可从newvfnode或其祖先结点的SQL片断中得到(行14,18～21);字段名是表中存储Dnode结点文本值(或属性值)的字段名称,根据其构成规则,可由newvfnode及其某些祖先结点的XML标签组合而得到。

(4)将新创建的结点vfnewnode作为VparentNode参数,对Dnode的所有的子结点递归调用Generate_node函数。重复上述步骤,继续创建View Forest结点(行35～36)。

　　以程序1、程序2中的XML数据为实例,应用该算法构造的View Forest如图2所示(图2(a)为View Forest的树型图,图2(b)为部分结点的SQL片断)。该算法对于存在循环的DTD图是无效的。因为View Forest本身不能出现环结构。

3 结束语

　　使用关系数据库存储和查询XML数据一直是研究者们关注的热点。根据XML数据的特性,有多种生成关系模式的技术。但对于每一种生成技术都需要开发复杂的查询处理器,将XQuery转换成SQL语句。本文提出的方法,使得绝大部分关系模式生成技术都可直接利用SilkRoute中转换及优化XQuery的算法作为自己的查询处理器,省去了大量的开发工作,提高了处理查询的效率。该方法的核心思想是根据XML数据的结构信息和存储模式来构造SilkRoute中的重要的数据结构View Forest,随后利用SilkRoute中的算法转换XQuery。作为分析实例,本文针对典型的关系模式生成技术——共享内嵌技术,给出了相应的构造View Forest的算法。以本文的方法为基础,可以很容易地推导出对应于其他关系模式生成技术的算法。

　　上述方法的缺陷是如果XML数据存在循环结构,则无法构造View Forest,因为View Forest中不能带有回路。因此今后将进一步研究如何对循环结构进行转化,从而构造相应的View Forest的方法。

参考文献

1 Fernández M,Kadiyska Y,Suciu D et al.SilkRoute:A framework for publishing relational data in XML.ACM

Transactions on Database Systems,2002;27(4)

2 Shanmugasundaram J.Relational Databases for Querying XML Documents:Limitations and opportunities.In:

VLDB Conference,Edinburgh Scotland,1999

3 World-WideWeb Consortium.XQuery 1.0:An XML Query Language.W3C Working Draft,2002,11.http://www.w3.org/TR/xquery/.

4 Florescu D,Kossmann D.Storing and Querying XML Data using an RDBMS.IEEE Data Engineering

Bulletin,1999,22(3)