论文研究-XML多值依赖及其消除冗余模式的算法.pdf

所需积分/C币:10 2019-07-22 22:13:38 119KB .PDF
收藏 收藏
举报

从消除XML文档内数据冗余的角度出发研究了文档的规范化问题。首先引入XML上的数据冗余及其消除处理示例,同时基于函数依赖,提出了规范化的DTD概念和XML DTD 规范化处理规则;其次通过XML多值依赖的定义,给出用于消除冗余模式的算法;最后给出用于XML模式及其消除冗余模式的算法。该算法相应于其他XML模式的研究,在算法产生的层次模式中,完全MVD和嵌入MVD的集合由给出的MVD集合导出;并且产生的XML模式具有消除冗余模式和满足无损连接的特性。
第6期 丘威等:XML多值依赖及其消除冗余模式的算法 63· 1.2ⅫML消除冗余的处理的 FD:(H[D、0姓/卩σ如→P4.0a…Bn、)和 更新异常现象是由于DTDD1在设计上存在的问题。为 :(H,[A.a…;mom→P.σy),HHσ是属性或 了避免这种异常现象,需要对DTD模式进行规范化处理。处具有形式(τ足元素类型)。通过创建元素类型Ww并移 理规则如 动具有传递依赖的节点来构造一个新的如图4所示的DTDD (1)是升规则 (E’A,P,R,广),消除传递函数依赖,以减少由传递函数依 给定DTDD(EAPR),D上的PFDL:(H[P 赖引起的数据冗余现象 ox…Bm,omn→,oy]),在(D,∑)中一定存在另一个 last(H') last(H') FDxM:(H,[H.p.o…,H,pmoa→p.o小)。其中,H last(H C Paths H PAths Py Paths By1≤/≤冂是属性或具有形式τ.S(τ (px)(pm)(pa)(pm)(py)(p)(D)(p2x)(pm)(p;) 是元素类型)。提升l(P)节点,使其成为la(H)的子节 O oz 点。构造一个新的如图2所示的DTDD(E,A,P,R,f, 图4创建移动规则示意图 消除部分函效依赖,以减少由部分函数依赖引起的数据冗余现 形式上为DTDD(EA,P,R,()。其中,E=EU 象 tlab( Vnew:a =A;P(last(h))=P(last(H)),lab (ve)};P(la(Ve))=[σa,…,σmo小;P(las(p) P(last(卩)[a;R(la(v))=@oa…@σm@σ} H st last jast tast ta R(。(p以)=R(lat())-{@aM;P和R的其他定义同D (H.p2)(Hpx)(p)(pA)(pa)(Hpz)(Hpm)(px)(px)(pa)(p,) 中P和R的定义。在∑中形如卩,y形式的函数依赖在 ∑中不冉成立,但增加新的函数依赖9new 图2提升规则示意堅 (H,[H".Ves.n…H.ew.om]→H.aw.y) 形式上为DTDD(E,A,P,R,)。其中E=E;A 例3图3经创建移动规则可转换为图5所示,其DTD为 AP(a(1)=p((H)),as(p)};R=RP的其他定D3 义同D中P的定义。在∑中形如p.oy形式的函数依赖 ELEMENT courses( course*, teacherinfo*) 在∑中被转換成H.风,σy形式。例如(H,[H.Pn.a…H A ELEMENT course(tite, takenby, teacher ATTLIST course cno CDATA #REQUIRED Pm,0a→P小)转换成(H,[HP4.0A…,H.pma→H. 4 ELEMENT title( #PCDATA) P°) ELEMENT takenby(student*) 例2DTDD1经提升规则可以转换为DTDD2图1可转 A ELEMENT student( sname)> 换为图3。 ATTLIST student sno CDATA #REQUIRED A ELEMENT name( #PCDATA) 4 ELEMENT courses( course*) ELEMENT teache empty> d element course(title, takenby, teacher) A ATTLIST teacher tno CDATA #REQUIRED> 4 ATTLIST urse cno CDATA #REQUIRED> EL EMENT teacherinfo( tname d element tite( #PCDATA) 4 ATTLIST teacherinfo tno CDATA #REQUIRED ELEMENT takenby( student ! EL EMENT如am(# CDATA) d eLemeNt student( sname) A ATTLIST Student sno CDATA #REQUIRED> @cno "c01 d elemeNt sname( PCDATA) tite“DB student. shame“]e @snc¨s01” 1 ELEMENT teacher( name)> course student sname“smth d aTTLiSt teacher tno CDATA #REQUIRED teacher tnc“t01 sno“s02 @cno c02 d ELEMENT tname(#PCDATA)> tite“DM” student shame“Smt” -takenby student sname"Jane teache @tnc“t01 @snc“st03” uite"DB” student takenO 一回sno“st0 cno“c03 course student sname“ Smith tite"KD” student tname"]chnC sno“st0 takenby @snc“s:01 teacher student sname“ane mct01” otnc“t02 @snc"‘St03 ute“DM student Shame“smth takenby sno"st02” teacherinfc-@tno“to” ame“]ane tname“]chn” @snost03 teacherinfo teacher ame“Jchr tname"Mary gtct1” @cno“c course ute“KD student 图5符合D3的一个XML文档 takenby asno“st01 student sname“]an teacher cname"Mary @sno"st03 tcto2” 2消除冗余模式的算法 图3符合D2的一个XML文档 2.1XML多值依赖 (2)移动规则 定义4XML文档中的数据兀余。给定DD上成立的函 给定DTDD(EAPR7,D⊥的TDxL:([Pa.数依赖集∑,符合D的文档X和非平凡的函数依赖R,R2 r…Pm,x→P.]),在(D∑)中一定存在芮个(Q,Q,…,Qn→P,P2…,P)∑+。设S为Q,…,Qn 计算机应用研究 2007年 P…;P的最大公共前缀,令Q=5/2,P=S/P,(i∈[1常。这一点止如例1所指出的那样,因此有必要像关系数据库 ,j∈[1,)。若vV∈R1,彐M,∈wR2},∈那样,引入一种规范 XML DTD的范式,以避免这种数据允余 {S,3U2w{S(u≠U2),有U1{Q}=u{Q}对jf∈和操作异常。给定DTDD和D上成立的多值依赖集合MVD [1,都成立,则根据函数依赖的定义,此时必有U1{P=(D),如果对在MD(D)中的每一个非平凡的MNDX→→Y P}对于j∈[1,都成立。这就是文档X巾的冗余。若非平都满足X可以唯一法定Pahs(tre(X),那么D是ⅩML范式 凡两数依赖在文档中导致了数据冗余,则称其为异常函数(简记为XNF)1。 依赖勹5。 如果在给出的MVD集合M中存在这样的两个MVD:X→ 定义5给定D和D上成的函数依赖集∑,称D是规→y和z→→Wz相应于X→→y是可分解的(即Xc乙z∩ 范化的,当且仅当对任给的非平凡函数依赖R,R2(Q,Q y≠0,2-X-y≠),并且WcY。相应于2→→W的分解会 Q→P,P2…P)∈∑,设S为Q1…QP1…P的最产生两个包含Z的简单类型元素和属性集合,而后相应于X→ 大公共前缀,令Q=5/Q,P1=5/P(∈[1,,j∈[1肉), y进行分解,在产牛的集合族中会有一个集合是另一个集合 则R1,R2/SQ,Q2…Q2)是D上的键。 的子集。因此,如果按 Provost的思想进行层次模式设计会 由此,规范化的DTD消除了文档中的元余。 产牛冗余模式;而产生汇余模式的原因是,在给出的MVD集 文档中冗余的存在是导致对其操作异常的原因,规范化的合中,存在这样两个MVD:X→→y和乙>→WZ相应于Ⅹ→ DTD,也就是消除文档中冗余的DTD。给定DD上成立的Y是可分解的,并且WcY。 两数依赖集Σ,符合D的文档和平凡的两数依赖(R1R2.2算法设计 Q,…Q,→P1…,Pn)(∑+。设S为Q,…QnP1…P 算法1消除冗余模式的分解构算法 的最大公共前级,令Q=5/Q=5/P。若存在vR1,存 输入:筍单尖型元素和属性的集合O和O上的MVD集合M 在,V(WR2},存在14{S》存在2"{S(U1≠ (1)产生与M等价的MVD集合M1:对于在M1中的任何X→→Y u),有u1{Q}=u2{Q}对于/∈[1,川都成立。根据函数依Y∈DEP(X) 赖的定义,此时必有a{P}=2只}对于子∈[1都成沉 设M1为{g19…9k,队列Q为 这就是文档X中的冗余。若非平凡函数依赖在文档中导致效 for i: =1 tok do for j:=1 to k do 据冗余,则称其为异常函数依赖9 if TEst(i,j)Then将(i,j加入到Q中 定义6给定 DTD D XUyCPat(tme(X),z=Pas tre(Ⅹ))-X∪y。Xyz分别表示元组在路径xYz上的 {将Q的队头(i,j移出冫 值。对于任意的XML树TFD如果在T中只要存在元组七 在M14用LHS(9)U(RHS(9)nLHS(g)→→RHS(9)取代 和t,)且满足如下关系:(=t(x)=X比1(Y)=,t(2=9HS和RS分别表示MYD的左式和式 z,t(Y)=y2和t2(2)=乙,那么在T中也存在元组t和t,并 fif TEST(l,j)then将(l,j邡入到Q中; 且满足如下关系:t(X)=t4(X)=xt(Y)=y1t(2)=zx if TEST(j,l)ten将(j,)加入到Q中} t(Y)=y2和t4(z)=乙就称多值依赖(简记为MVD)X→→y } 在D上成立。D上所有的多值依赖的集合表示成MVD(D)。 untQ为 假定∑CMVD(D,TFD表示如果对每一个MVDφ∈∑,都 (2)划分和排序 有T卡。TF(D∑)当H仅当7∑和TFD。(D∑)9 产生M1的划分{G1,G2,…,Gmn},使得在每个G1中的MVD有相 同的LHs,设x为G中MD的LHs,1sim并上如果×≤×3,则 9表示(D∑)隐含MDφ。山(D∑)隐含的所有MVD的集1≤i<j≤m 合表示为(D∑) (3)基于MVD集合M1产生分解树 定义7给定DTDD和Pahs(tree(X))上成立的一个多 设DT(O,M)在初始时是一个标号为集合O的节点; for i:=1 to m do 值依赖X→→Y。其中XY∈Pahs(tee(刈))。如果YAX或 r每个在DT(O,M)中出度为0的节点ndo 者ⅩJy=Pahs(te(刈)则称多值依赖X→→y为平凡的多 if label(n)相应丁M1中的G1是可分解的then 值依赖。实际上,所有的平凡多值依赖都可以根据定义8直接 tY:=label(n) 推岀。如果无特别说明,这里所说的多值依赖均指非平凡的多 label(n)←X 值依赖 设z是G1屮的所有RHS的并集 for每个在{X;(Y∩W)|Y∩W≠并HX→→W在G1中}U 定义8对于给定的XML树7=(vab,de,,v,Y-2}中的元素Xdo ro)。令Ⅵ1=ele(lat(ro)是根节点的了元素集合,称为第 在DT(O,M)中加入一个新节点n和弧,n>,|abel(n)←X";} 层元素节点;v是叶」节点的集合,也就是如果vv那么 输出:DT(O,M) ee(=①或v是属性。给定非递归的DTDD和XML树T 山算法1可知,产生的分解树DT(OM)是一棵有根树。 D如果对每一个v∈Vv的值都是不可分的原子值,那么称D算法1产生的DT(OM)消除了冗余模式但所有的元素和属 是规范化的XML模式 性都包含在一棵有根树中,结构比较复杂,需要作进一步处理。 例1屮的DTD都是规范化的XML模式,这种类型的DTD消除冗余模式具有无损连接特性的算法设计为:在算法1的 也是实际中使用最多的一种ⅩML的模式。这是对DTD进行础上产生层次模式,如算法2所示。 规范化的最基本的要求,因此本文只讨论这种类型的DTD 算法2消除冗余模式并具有元损连接特性的算法设计 但是仅仅符合这种条件的DTD往往存在着数据冗余和操作异 输入:算法1产牛的DT(O,M); 第6期 丘威等:XML多值依赖及其消除冗余模式的算法 (1)初始化 因而不可能解决所有数据冗余问题。通过引入函数依赖和多 少设「是DT(O,M)的根, CHILDREN(n)表示DTO,N)中内节点n值依赖的概念,本义给出了一种处理DTD规范化的准则,闸述 「孩子集合 LEAVES{mm是在DT(O,M)中的叶节点}; 了将DTD转换为规范化形式的处理过程。本义基」XML文 H(O)←{H(mm在 LEAVES中,设此时H(m)是一个标号为la-档的基本概念给出了ⅩML函数依赖、XML范式和ⅩML多值 be(m)的节点} 依赖等相关定义;提岀ⅩML模式规范化转换规则。产生的层 (2)产生层次模式 次模式具有消除冗佘模式和淸足无损迕接的特性。山此产生 {从DT(oM)中选择一个内节点n使得α HILDREN〔n)ALEA-的层次模式能更好地保持数据依赖关系,并且消除了冗余模 VES,令H(n)是一个标号为labe(n)的节点; 式。不文的工作对于某于Web的信息系统开发有一定意义 将H(n)加入到H(O)中; 在以后的工作中,将对ⅩML模式的冗余及其导致的异常进行 LEAVES+LEAVES-CHILDREN(n for每个在 CHILDREN(n)中的mdo 更深入的分析,并以此定义范式,完蓍规范化设计算法。这将 ifH(m)中有标号为X的节点,使得X=labd(n)then 对未来的ⅩML函数依赖保持、ML关键子及其求解、XML完 {以H(m)中灣足X= label(n)的最小X对应的顶点为终点,以标 整性约朿、函数依赖推理规则、ⅩML多值依赖以及ⅩML模式 号为labe(n)的顶点为起点做弧,以此将H(m合并到H(n)中; H(O)←H(O)-{H(m 的进一步规范化研究奠定理论基础。 g else 参考文献 在H(n)中构造标号为L(m的新节点并以V为终点,标号为la be(n)的顶点为起点做弧 [1] orld Wide Web Consortium. Extensible Markup Language( XML) LEAVES← LEAVESU{n}; OlEb/oL].(1998-02).http://ww.w3.org/tr/1998/reC 3 until LEavES=trfi XML-19980210 输出:层次模式H(O) [2 VIANU V. A Web odyssey: from Codd to XML: proc. a ACM PODS 由算法2产生的层次模式H(O)表示为一个弱连通有 [C]. Santa barbara:[s.n.],2001:148-160 向无环图,且H(O表示的数据依赖由给出的MVD集合M导[3]谈子敬,施伯乐.DTD的规范化[.计算机研究与发展,200441 出。因为嵌套关系可以通过非嵌套化操作转换为INF关系,所 以每个XML模式或DTD相应的XML文档可以通过非嵌套化[4PROVOSTW.NormalizingXML[EB/OL].h://WwW.xm.com 操作转换为一个关系实例。要证明算法2产生的层次模式满 pub/a/2002 /11/13/normalizing. html 是无损连接的特性,就要证明相应的关系模式具有无损连接的5] ARENAS M, LEONID L. A nomal form for XML documents[ C]∥ 特性。算法2产尘的层次模式中的数据依赖山给出的简单类 LUCIAN P. Proc. a the 21 st ACM SIGACT-SIGMOD-SIGART Symr posium on Principles of Database Systems. Madison: ACM Press 现元素和属性集合上的MVD集合M导出,并具有消除冗余模 2002:85-96 式和保持无损连接的特性。 [6张忠平;王超,朱扬勇.基于约束的ⅩML文档规范化算法[].计 算法1和2的忖间复杂性主要是由F循环体和合并消 算机研究与发展,2005,42(5):755-764 除几余两步骤决定。For循环体每执行一步,取∑中一个[刀] BUNEMAN P, DAVIDSON S B, FAN W F,aa, Reasoning about PFDXMI或 TFDXML。设最坏情况下∑中所有FD×ML都是 PFDXML keys for XML[ C]/ GHELLI G, GRAHNE G. The 8th IntI Work- 或TD×M,令∑中函数依赖数日n=|∑l,所以整个For循坏 shop on Database Programming Languages. Frascati: Springer-Ver- 体要执行∩步。算法中的合并和消除冗余元素类型是检查节 lag,2001:133-148. 的冗余情况。令D中节点数目m=|DL检查节点的冗余[8]FANW, LIBKIN L. On XML integerity constraints in the presence of 每次取两个元素,要执行Cn2步(Cn2=m(m-1)=mn2 DTDS: proc. of A CM Symposium on Principles of Database Systems m2)。所以合并和消除冗余元素类型的时间复尔性最坏情形 PODS[C]. Santa Barbara: [S.n., 2001: 114-125 下为Cm),整个算法的时间复杂性生为cm+n) [9]谈子敬,施伯乐,函数依赖和规范化在关系和XML间的传播[]] 软件学报,2005,16(4):533-539 3结束语 [10]王庆,周俊梅,吴红伟,等.XML文档及其函数依赖到关系的映射 [J].软件学报,2003,14(7):1275-1281 №L的规范化理论还没有成熟和完普。正如关系数据库[1]1吴永辉;周做英相应于无冲突依赖的规范化对象模式森林[] 中的模式一样,每一种范式都有它的应用范围、特点和局限性, 软件学报,2002,13(8):1488-1493 (上接第60页) 275 [6] ALTE NIS S, JENSEN C S. Indexing of moving objects for location- [10] sUn Ji reng, PAPA DIAS D, tao Yufe, et al. querying about the based servces: proc. ICDE[C][SL]: [SnI, 2002: 463-472 past, the present and the future in spatio-temporal databases: proc. [7] PATEL JM, CHEN Y, CHAKKA V P. STRIPES: an efficient index o f icde[C].[sl.]:[s.n.],2004:202-213. for predicted trajectories: proc. of ACM SIGMOD[ C][s..]: [S. [11] BECKMANN N, KRIE GEL H, SCHNEIDER R, Et al. The R n.],2004:637-646 tree: an efficient and robust access method for points and rectangl [8] KOLLIOS G, GUNOPULOS D, TSOTRAS V J. On indexing mobile poc. ACM SIGMODLC].[S.l.]:[s.n.],1990:322-331 objects: proc. of PODS[ C][SL]: [Sn.], 1999: 261-272 [12]cⅣ正lA,正 NSEN C S, NENORTAITE],a/. Efficient tracking [9] BECKER B, GSCH WIND S, OHLER T, et al. An asymptotically op of moving objects with precision guarantees: proc. of Mobi Quitous tima multiversion b-tree[]]. VLDB Journal 1996, 5 (4): 264 C].[S.1.]:[sn.],2004:164-173

...展开详情
试读 5P 论文研究-XML多值依赖及其消除冗余模式的算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-XML多值依赖及其消除冗余模式的算法.pdf 10积分/C币 立即下载
    1/5
    论文研究-XML多值依赖及其消除冗余模式的算法.pdf第1页
    论文研究-XML多值依赖及其消除冗余模式的算法.pdf第2页

    试读已结束,剩余3页未读...

    10积分/C币 立即下载 >