XML数据已经成为Internet上的主流数据，但目前大部分XML规范化理论局限在层次的冗余上，从数据库的角度出发，以XML键为中心结合函数依赖FD和多值依赖MVD描述XML数据间的约束；基于主键、副键分析不同情况下的数据冗余，给出相应的规范化规则，得到消除数据冗余的XML模式。王梅娟,庞引明,谈子敬,等:消除XML键数据冗余的相关规贝2010,46(26127叶节点,对应 leaves数组为空,故不为其建立XML键上仅由e决定而与e的语义相关无任何现实意义,且e≠,则(3)对于“*”对应的 course节点,与之对应的 leaves数组中该节点为“副键无关冗余”的叶节点集合是{@cno, cname, classhour, experimenthour},由在上述描述中,特别注意的两点是:FD1可以知道@cno是 course节点的XML键;同理可知asno(1)定义中的相关约束是在一定范围内讨论,这样的限定是 student节点的XML键。条件是由副键本身的性质所决定。由副键的定义可知,在最终的K1={@cno,asno}。棵XMI文档树?(T-D)中,节点e唯一决定e当且仪当节点3.12副键e;对应的节点确定时才能成立,因此e为根的子树中节点可能副键的定义是在主键定义的集合范围内给出的。通过推导规则与e或者e,存在结构上的约束关系,而这种结构定义2[副键]给定DTDD=(E,A,P,R,r),一棵XML文上的关联没有现实意义档树T}D,D上存在元素节点e、e的主键KEY分别对应x:e(2)如果e,=r,则对应的副键无关约束不形成冗余。这是和κ':e’,e在以e为根的子树下,若在对应的T中,主键κ:e当由XML层次结构的特点决定的,因为并不是所有的多值依赖且仅当节点e!对应的节点确定时才能成立,则称节点e!是节都存在冗余。点e的副键。对应于副键,函数依赖集Σ中一定存在函数依赖FD:g1:([SnSe:'}→S,S′.e");q2:(Sn.S,e',[Scel]→S,e,)4基于XML键的消除冗余规则副键的示意图如图3所示。已有文献[1-3,9中定义的PFD和TFD是基于树元组进行定义的,从而局限在层次导致的冗余上;文献[8]是基于ⅹMLlast(s,键将XML模式转换成消除冗余的关系模式。本义研究的是消除ⅹML模式的数据冗余,因此本节用键的思想,给出消除数据冗余的规则。41消除“主键无关冗余”的规则last(S)lasI(s,由定义3可知,给定DTDD如果存在主键无关的节点,则last(S)对应于主键无关冗余的函数依赖为g:(S.e;,[Se]→S.v),且在根部路径S约束范围內(S,[S,e]-S.v),此时由其副键约图3副键示意图束的函数依赖为g’:(S,[S'.e!]→S.v),满足[S.e]一[S!!]和副键集合是在主键集合中定义的,某节点的副键一定是Se5.e1,其中 S:pAths, 'paths=:。在例1中, credit节点该节点某祖先节点的主键,由此替代该祖先节点与该节点为存在“主键无关”的冗余,因此对于同一门课程下的不同学生同样的 credit值需要重复存储,这就形成了由“ credit节点是主根的子树间存在的约束关系,以此来弥补DTD模式的不足。键无关冗余”引起的数据冗余。例3由图1的DTDD1得:在整个文档树中,当节点@cno这种数据冗余现象是由于层次的嵌套导致的,本文提升确定时,以 course为根的子树也随之确定,即 course节点的子存在冗余的元素节点为其副键所约東节点的子节点,避免其节点@cno可以唯一地确定它及以它为根的子树,根据定义出现在主键无关的子树中;并充分考虑依赖关系,给出函数依节点@c是节点 course的主键;在以 course为根的子树下,如赖集相应的变换规则,下面是该规则的具体定义和形式化描述:果@sno确定,则以 student为根的子树也随之确定, student节规则1(消除¨主键无关冗余”)为了消除存在主键无关冗点的子节点@在cno确定的情况下可以唯一地确定余的节点r,通过构造一个新的DTDD=(E",A,P’,R’,),使dn以它为根的子树,根据定义2,节点@s0o是节点 student得1bS)成为e的子节点,即提升该元素节点至其语义相的主键,@acno是节点 student的副键。关的副键约東的子树中,成为该子树根的儿子节点。如图432基于XML键的数据冗余所示。研究XML键的目的是为了减少冗余,如何判断冗余是规范化研究的重要基础。根据3.1节中ⅹML键的相关定义,分析可以得出,当某一元素节点e存在主键κ:e和副键κ':e:'时,last(S,)last(s以e所决定的元素节点e为根的子树与以e为根的子树形成las(s)last(s)嵌套包含的关系,同时在以e为根的子树中,所有节点都应与e和e有语义上的约束关系,否则就会出现数据单元重复的存储。将引起这种数据冗余的原因定义为基于键的数据冗余last(s)last(s, last(s) last(s)定义3给定DTDD和D上的主键集合K,:e、x:e'∈K分别唯一决定元素节点e和e,且e'是元素节点e,的副键,则last(s) last(s_)last(s) last(Slast(S))以节点e为根的子树中包含以节点e为根的子树。在以e为根的子树中图4规则1的变换示意图(1)如果存在某一节点在根部路径S约束范围内的语义形式地,D=(E',A,P,R,r),其中上仅由e决定而与e的语义相关无任何现实意义,则称该节点(1)E′=E为“主键无关冗余”;(2)A′=A;(2)如果存在某一节点在根部路径S约束范围内的语义(3)若last(S)∈E,则P(e")={P(e"),last(S)}:P"(last(S1282010,46(26)Computer Engineering and Applications计算机工程与应用last(S)))=((last(S:-last(S)))-dlast(S:))(4)若S:=Se,且v∈A,则R(e")={R(e),av};R'(e){R(e")}-{@av};@表示取相应的属性值;last(S,)las(S”(5)P和P的其他定义分别同D中P和R的定义;同吋,在D上成立的FD集合∑对应于∑中所有的FD,仅对last(s) last(,) last(s)部分路径有所改动的F进行转换(即路径表达式具有形如Svlast(slast(s)last(S,, last(S)的,都将转换成形如Se′S!v,其中S′=S:-Se),其他不变(6)删除Σ中“主键无关的约束”,即删除g:(S:e",[S,elast(s,)last(Sk)las (S )last(.) lasi(S )last(Sk -last( S: -las: (S,)st(S)last(S))(7)对于Σ屮“副键约束”的函数依赖φ:(S,[S:e!]→S图5规则2的变换小意图V:),转换成相应的“主键约束”的函数依赖:(S,[S:e!]→S(5)若S=S-S=Se,且v、v∈A,则R(Vm)={@v,@v,e,S2v2)。av};R(last(Se,)=P(lat(Se))-{@v,@w};@表示取相42消除“副键无关冗余”的规则应的属性值;给定DTDD=(E,A,P,R,r),如果存在副键无关的节点,6)P和R的其他定义分别同D中P和R的定义则存在对应于副键无关函数依赖ρ:(S,[S,e]→S,v)或者多值同时,在D'上成立的FD集合∑对应于∑中所有的FD依赖r:(S,Se」→→Sv),且在根部路径S范闱内(S.S:e!MVD集合9对应于中听有的MVD仅对部分路径有所改动的Sn),(S,[S:e!Sn)。对于9,存在造成其冗余的函FD和MVD进行转换(即路径表达式具有形如S或S的,数依赖0:(S,[S.c]-s1)、0":(s,5.e]→s1v),满足se]都将转换成形如SvmS"或SmS"),具体变化如下:ASe]和[S,v[Se],其中 S,CPa s,pAths≤mhS;对于a,存(7)删除Σ中的函数依赖:(S,[S.el→S.v);删除Ω中的在造成冗余的多值依赖7:(S5S']→→Se)。由例1中的分多值依赖:(S:e,[S.el→→Sw)析可知, sname节点和 guardian节点存在“副键无关”的冗余,(8)将∑中形如φ':(S,[Se]→Skv)的函数依赖转换成了因此对于选修不同课程的同一个学生,其 sname值和 guardian new:(S,Sm"→Mms")值需要重复存储,这就形成了由“ shame节点和 guardian节点(9)将Ω中形如a:(S,[S.c-]→→Sv)的函数依赖转换成是副键无关冗余”引起的数据冗余。了σnn:(S,[SVS"v]→→S针对这种数据冗余现象,从键的角度出发,采用创建新节4.3数据冗余消解实例点并提升存在冗余的元素节点和其主键为新节点的子节点的由规则1和规则2可以分别消除“主键无关冗余和“副方法,避免其出现在副键无关的子树中;并充分考虑依赖关无关冗余”,从而消除使得到的DTD更加规范,更加合理。图系,给出函数依赖集相应的变换规则,下面是该规则的具体定6是例1中的D1经过规则消解后得到的一个XML实例。义和形式化描述:规则2(消除“副键无关冗余”的规则)为了消除XM文5结论与展望档中副键无关冗余的节点,通过创建一个新的元素类型T来从数据库规范化的角度出发,在现有的XML范式理论基构造新的DTDD′=(E,A',P,R',r),使last(S,v)或last(S.v)础上,通过例子描述现有键约束存在的不足,通过集合的思想直接包含在根部路径约束下新建节点为根旳子树内。如图5给岀ⅹML键及主键、副键的概念,避免了树结构的嵌套带来所的复杂问题,并以“XML键”为中心结合函数依赖FD和多值依形式地,D′=(E’,A',P′,R',r),其中:赖MVD描述ⅹML数据问的约束,最后基于主键、副键分析不(1)E′=EU{lb(Vme)};同的数据冗余,给出相应的规范化消解规则。(2)A′=A;将来的上作还可以改进的地方:进一步扩允XML键的(3)P ( last( Sh))=(P(last( S:)), lab( Vnew)*3概念,对XML键的定义和寻找做进一步的延仲,对于某些无法(4)若lasr(S)、lasr(S)、last(S)∈E,则P(Vm)={last(S),标记XML主键,但在实际问题中又存在冗余的节点给出相应last( Ss),last(S: P(last( Sx-last( Sk)))=P(last( Sx-last( S)))的规范化规则;将ⅹML键的概念引入到XML文档的查询索{las(S)};Pla(S-lus(S))=P(las(S-las(S)-{las(S)};引中,以键为中心,建立·种新的索引机制,可以优化查询等kshani =n EreEr lanet tdif witkin an siiihie miininwiinaii lin sime finlin"∠k bi sTa soHcpmm解n"Nn2要mg图6消除数据冗余的XML文档实例(下转240页)