(计算机应用技术专业论文)xml数据的规范化存储.pdf_第1页
(计算机应用技术专业论文)xml数据的规范化存储.pdf_第2页
(计算机应用技术专业论文)xml数据的规范化存储.pdf_第3页
(计算机应用技术专业论文)xml数据的规范化存储.pdf_第4页
(计算机应用技术专业论文)xml数据的规范化存储.pdf_第5页
已阅读5页,还剩60页未读, 继续免费阅读

(计算机应用技术专业论文)xml数据的规范化存储.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 作为一种i n t e m e t 上的主要的数据表示和 交换标准,应用范围非常广,这就对x m l 数据库的模式提出了更高的要求。和 关系数据库类似,如果x m l 数据模式设计的不好,就会引起插入、删除和更新 等异常,由于w e b 的歼放性,x m l 数据异常的危害性往往远大于关系数据库异 常的危害性。 x m l 数据已经成为i n t e r n e t 上的主流数据,虽然现有的研究在存储与发布、 查询与优化等技术方面已取得一定的成果,特别是与关系数据的转换技术己相对 成熟,但大部分理论仅仅考虑将x m l 文档数据转换到关系数据,且这种转换只 是保持了结构信息,而没有从数据库设计的角度来评价x m l 数据库模式;另外, 部分已有的研究虽然提出了相关的x m l 范式,但定义的理论仍然存在不完善和 欠缺,这必将对今后的w e b 数据处理带来很大的麻烦,势必造成网络数据大量 冗余和不一致的现象。 本文从数据库的角度出发,以x m l 键为中心结合函数依赖f d 和多值依赖 m v d 描述x m l 数据间的约束;基于主键、副键分析不同情况下的数据冗余, 给出相应的规范化规则;并由此定义不同的范式和规范化算法;最后提出一种新 的基于键的x m l 模式到关系模式的转换算法。主要的研究成果如下: 对x m l 函数依赖约束进一步研究:基于本文的符号理论体系给出 x m l 函数依赖、部分函数依赖、传递函数依赖的概念;定义了x m l 函数依 赖的逻辑蕴涵与覆盖,并给出相应的推理规则和消解规则,得到无冗余的极 小函数依赖集;最后给出有效性证明; 参考已有的x m l 多值依赖定义和x m l 多值依赖推理规则,给出基 于本文符号理论体系的m v d 相关的形式化定义; 讨论x m l 中的键约束,仿照关系数据库中键的概念,以集合的形式 给出x m l 主键和副键的定义,基于键讨论了x m l 数据冗余,分别定义为 “主键无关的冗余”和“副键无关的冗余”; 针对数据冗余的不同情况定义不同的x m l 范式,并给出消除数据冗 余的相应规则:在范式定义和规范化规则的基础上给出x m l 文档的规范化 算法,并给出算法分析和证明; 提出一种新的x m l 模式到关系模式的规范化转换算法,该算法基于 本文所定义的x m l 键,包括主键、副键及隐键,结合函数依赖的约束,尽 量减少属性节点的冗余,使得到的关系模式中的关系表及其属性更加合理。 关键词:x m l 模式、约束、x m l 键、函数依赖、规范化、推理规则 a b s t r a c t a st h em a i ns t a n d a r df o rd a t ar e p r e s e n t a t i o na n de x c h a n g eo nt h ei n t e m e t ,西e r a n g eo f x m u sa p p l i c a t i o ni sv e r yl a r g e ,w h i c hr e q u e s t sm o r et ox m ld a t a b a s e s c h e m a s i m i l a rt or e l a t i o n a ld a t a b a s e ,i f x m ls c h e m ad e s i g n i n gi sn o tg o o d ,i tw i l l c a u s ea b n o r m i t yf o ri n s e r t i n g ,d e l e t i n ga n du p d a t i n gd a t at o o ,a n dt h eh a r mo fx m l d a t aa b n o r m i t yi sf i l r t h e rh i g h e rt h a nr e l a t i o n a ld a t aa sw e bi so p e n x m ld a t ah a sb e c o m em a i n s t e a md a t ao ni n t e m e t t h e r eh a sa l r e a d ys o m e a c h i e v e m e n to nc o r r e l a t i o nx m l r e s e a r c h ,f o re x a m p l e ,t h et e c h n o l o g yf o rs t o r i n g , p u b l i s h i n g ,q u e r y i n ga n do p t i m i z i n go nx m ld a t a ,a n ds oo n ,e s p e c i a l l y ,i ti s f u r t h e rm a t u r eb e t w e e nx m la n dr e l a t i o nd a t at r a n s f o r m i n g ,b a tm o s to ft h e s e t h e o r i e so n l yc o n s i d e rh o wt ot r a n s f o r mx m ld a t ai n t or e l a t i o n a ld a t a ,w h i c ho n l y h o l d ss t r u c t u r ei n f o r m a t i o n ,w h e r e a sn o tc o n s i d e r i n gx m ld a t a b a s es c h e m af r o mt h e p o i n to fd e s i g n i n gd a t a b a s e b e s i d e s ,a l t h o u g hs o m er e s e a r c hh a v ea d v a n c e dt h e f o r mo fx m l ,t h et h e o r yo fd e f i n i t i o ni sn o tc o n s u m m a t e ,w h i c hw i l lb r i n gm u c h t r o u b l eo nw e bd a t ap r o c e s s i n gl a t e r ,a n dm a k e sm a n yr e d u n d a n ta n di n c o n s i s t e n t d a t a i nt h i sp a p e r ,w ec o n s i d e rf r o mt h ep o i n to fd a t a b a s ed e s i g n i n ga n ds t u d yf u r t h e r o nc o n s t r a i n t sa n ds t o r a g eo fx m ld a t a b a s e ,m a k ed i r e c tn o r m a t i v ep r o c e s s i n go n x m ld a t a ,g i v et h ed e f i n i t i o no fr e d u n d a n c ya n da l g o r i t h mb a s e do nx m lk e y w h i c hc a nr e d u c et h ed a t ar e d u n d a n c ya n dk e e pt h ec o n s i s t e n c yo fx m ld a t a t h e c o n t r i b u t i o n so f t h i sp a p e ra r ea sf o l l o w s : x m lf u n c t i o n a l d e p e n d e n c y ,p a r t i a l f u n c t i o n a l d e p e n d e n c y a n d t r a n s i t i v ef u n c t i o n a ld e p e n d e n c yb a s e do nt h es y m b o ls y s t e mo ft h i sp a p e ra r e p r e s e n t e d w e d e f i n e l o g i c a li m p l i c a t i o n a n dc o v e rf o rx m lf u n c t i o n a l d e p e n d e n c y t h e nw eg i v eas e to fi n f e r e n c er u l e sa n das e to fc l e a rr u l e so f x m lf u n c t i o nd e p e n d e n c yw h i c ha l es o u n d a tl a s tw eg i v et h ec o r r e l a t i v ep r o v e o f r u l e s ; r e f e r e n c i n gt ot h ed e f i n i t i o no fx m l m u l t i v a l u e dd e p e n d e n c ya n das e t o f i n f e r e n c er u l e s ,w ep r e s e n tt h ed e f i n i t i o no f m v db a s e do nt h es y m b o ls y s t e m o f t h i sp a p e r ; 1 1 1 n l ex m lk e yc o n s t r a i n si sd i s c u s s e db a s e do nt h ek e yc o n c e p ti nt h e r e l a t i o n a ld a t a b a s e a n dt h ed e f i n i t i o no fx m lm a i n - k e ya n dx m l d e p u t y - k e y a r e 西v e ni nt h ef o r mo fa g g r e g a t e b a s e do i lt h ek e y ,w ed i s c u s st h ed a t a r e d u n d a n c y ; n o r m a l i z a t i o nr u l e sa n da l g o r i t h mf o rx m ld o c u m e n t sa l ep r e s e n t e d b a s e do nt h ed e f i n i t i o no fn o r m a lf o r m sf o rx m lo fd i f f e r e n tk i n d so fd a t a r e d u n d a n c y ; an e wn o r m a l i z e dt r a n s l a t i o na l g o r i t h mi sp r o p s e df o rt r a n s l a t i n gx m l s c h e m at or e l a t i o n a ls c h e m ab a s e do nx m l k e y ,w h i c ht a c k l e st h er e d u n d a n c y a n du n s t a n d a r de x p r e s s i o ni nt h et r a n s l a t i o n a c c o r d i n gt oag r o u po fd e d u c e r u l e sa n dc l e a rr u l e sa b o u tx m lf u n c t i o n a ld e p e n d e n c y , w et a k et h ex m lk e ya s t h ec e n t e rt od i v i d et h er e l m i o na t t r i b u t e s ,o b t a i nt h er e l a t i o nt a b l e b e s i d e sw e c a l lg u a r a n t e et h el a s tr e l a t i o ns c h e m am o r er e a s o n a b l e k e y w o r d s :x m ls c h e m a ,c o n s t r a i n t ,x m lk e y ,f t m c t i o n a ld e p e n d e n c y n o r m a l i z a t i o n ,i n f e r e n c er u l e s i v 学位论文独创性声明 本人郑重声明: i 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外,所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外,不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名: 日期: 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定,学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版;有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅;有权将学位论文的内容编入有关数据库进 行检索;有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名: 日 期: x m l 数据的规范化存储第1 章引言 1 1 问题的提出 第1 章引言 经过十几年的发展,互联网( i n t e r n e t ) 己经成为新经济时代的标志,它极大地 影响了人类的生活方式、商业模式,并将在新世纪继续对人类社会的进步起着巨 大的推动作用。作为互联网最主要应用的w e b 正成为整个世界的窗口,它实现 了全球用户和机构信息的共享,可以预计,w e b 将成为人类社会的主要信息源、 媒体和商务的门户,而互联网将成为信息传播的介质和商务运作的基础平台。 随着互联网时代的到来,数据越来越多地开始以网络在线的方式进行发布、 交换和集成。1 9 9 8 年2 月,万维网协会w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 推出 了可扩展的标记语言x m u e x t e n s i b l em a r k u pl a n g u a g e ) ,将它作为一种互联网进 行数据表示和交换的标准 2 1 。x m l 作为一种半结构化数据的表示模型,从提出 到现在只不过几年的时间,但它作为一种跨产品、跨界面、跨平台的互联网的标 准语言,已经显现出其强大的应用前景,并受到了政府、企业和各大软件厂商的 广泛关注。各个行业如金融机构、海关、媒体产业正制定各自行业的x m l 文档 类型定义d t d ( d o c u m e n t t y p ed e f i n i t i o n ) 2 1 1 ,以利于数据以公认的格式进行交换 与集成。随着x m l 数据的增多,相关行业标准d t d 的制定,人们也开始越来 越多地希望以对待数据库的方式来处置和管理x m l 文档。 由于x m l 作为i n t e r n e t 上数据标准的出现,) 。儿数据的相关研究也逐渐成 为热点。现有的x m l 存储方法,都是一个从w 曲世界到机器世界直接的转换过 程,仅仅考虑到如何完整的保留x m l 文档中的结构信息,而没有从数据库设计 角度来评价所得到的数据库模式,这样必将对后来的数据处理带来很大的麻烦, 因为这样的数据库可能存在着插入、删除和更新异常。为了避免这些异常的出现, 就必须对得到的数据库模式按照数据库设计中的要求进行改进。也就是说,现有 的方法看起来简单,实际上想要真正得到一个优秀的数据库却非常的复杂。 x m l 是半结构化数据的特例,目前有很多研究采用x m l l 0 标准提出了更 适合表达x m l 数据模式的方法,如x m l d a t a l 3 1 。x m l s c h e m a t 4 】1 5 1 ,d t d 【6 1 等, 它们的共同点是:( 1 ) 要与x m ld t d 兼容并提供更丰富的描述能力;( 2 ) 使用x m l 1 0 的语法规范定义自身。文献【7 修f 对6 种x m l 模式语言进行了分析比较,但 是这些规范的研究还未成熟,在很多方面还未达成共识。相比之下,基于d t d x m l 数据的规范化存储 第l 章引言 规范己被广泛接受。 本文的规范化模式研究就是在这背景下,基于d t d 约束提出的。在数据 库领域中,规范化是模式设计的基础,它是评价一个模式好坏的主要依据。对于 x m l 领域,也要讨论相应的问题。目前x m l 已经成为i n t e r n e t 上的数据表示和 数据交换的标准,需要通过i n t e r n e t 交换和处理的x m l 数据会大大的增加。对 于x m l 数据库模式的深入研究将有力地促进企业的信息化、电子商务以及电子 政务的发展,因此具有巨大的应用前景和经济效益。 1 2 国内外研究现状 数据依赖及规范化理论源于数据库领域,在关系数据库里,键和外键是数据 库概念设计的基础,提供了如何唯一识别一个元组和如何引用另一个元组的方 法i 而函数依赖理论是关系模式设计的核心部分,也是范式研究的基础。基于范 式的关系模式,可以消除插入、修改和删除等异常现象,保证数据的完整性和一 致性。但是这些研究仅局限于传统的数据库范畴,在半结构化数据领域中,键的 约束表述能力仍然非常的缺乏。 x m l 数据约束对于研究x m l 数据的查询优化、数据集成以及x m l 数据与 其他形式数据库的转换都极为重要,作为一种半结构化数据的表示模型,已有的 x m l 文档规范化问题的研究大多集中在路径约束上进行讨论,并从关系数据库 的规范化理论中得到了一定有益的启示。 与x m l 文档的数据依赖问题相关的研究工作包括:文献 1 3 1 提出了x m l 文档的函数依赖的一种定义,但是这种函数依赖的定义没有区别x m l 文档中的 相对函数依赖和绝对函数依赖的不同,而且也没有给出关于函数依赖的推理规 则。文献 2 4 】用x p a t h 和属性的混合表达式给出了x m l 文档的函数依赖的另外 一种定义。在函数依赖关系中,这种定义只考虑了元素属性和元素的值,没有考 虑元素的节点,而且也没有讨论函数依赖的蕴含问题。x m l 的键和函数依赖有 密切的关系,文献 3 5 1 提出了x m l 的键的概念,同时讨论了x m l 键的蕴含问 题,并给出了关于x m l 键的完备的推理规则集。 与x m l 文档的规范化相关的研究工作包括:文献 1 3 】提出了x m l 文档的 一种范式x n f 。当采取一种合适的编码方法把关系模式和嵌套模式分别表示成 x m l 文档时,这种范式分别是对关系数据库中b c 范式( b c n f ) 和嵌套关系中嵌 套范式( n n f ) 的一种泛化。范式x n f 虽然可以消除数据之间的异常函数依赖所 引起的数据冗余和操作异常,但是却不能解决本文所提到的x m l 文档中数据之 x m l 数据的规范化存储 第1 章引言 问的多值依赖所引起的数据冗余和操作异常;另外,在x m l 的实际应用中,不 同的应用需求要求有不同级别的x m l 文档的范式,这就非常有必要引入其它的 x m l 文档的范式,这也是对x m l 文档规范化问题进行系统研究的必然要求, 这些问题都将在本文中进行讨论。文献【2 5 】提出了半结构化模式的一种范式 n f s s ,它主要是从现实世界实体的语义联系上来消除数据冗余。文献【8 】为半结 构化数据定义了种叫s 3 一g r a p h 的模式,但是这种模式也只是能部分地消除数 据的传递依赖。另外,对于x m l 文档的完整性约束或一致性问题可参见文献 3 7 , 3 8 】,x m l 以及其它半结构化数据的约束模型在文献 2 3 ,2 6 1 中有论述。 1 3 研究内容及意义 1 3 1 本文研究的内容及成果 本文基于x m l 文档层次结构中的路径表达式,从数据库设计的角度考虑, 展开对x m l 模式规范化的研究,包括:对d t d 模式及x m l 文档进行规范的形 式化描述;基于x m l 一对一的约束关系讨论x m l 函数依赖的形式化定义、逻 辑蕴涵和最小覆盖等,包括x m l 函数依赖推理规则和消解规则;基于x m l 一 对多的约束关系讨论x m l 多值依赖的形式化定义、逻辑蕴涵和覆盖等;讨论 x m l 模式中的范式定义,根据不同的冗余讨论不同的规范化规则,和相应的规 范化算法;讨论x m l 模式与关系模式的转换,探索一种基于x m l 键的转换算 法,使得到的关系模式更加合理。 本文的主要研究成果如下: 对x m l 函数依赖约束进一步研究:基于本文的符号理论体系给出 x m l 函数依赖、部分函数依赖、传递函数依赖的概念;定义了x m l 函数依 赖的逻辑蕴涵与覆盖,并给出相应的推理规则和消解规则,得到无冗余的极 小函数依赖集;最后给出有效性证明: 参考已有的x m l 多值依赖定义和x m l 多值依赖推理规则,给出基 于本文符号理论体系的m v d 相关的形式化定义; 讨论x m l 中的键约束,仿照关系数据库中键的概念,以集合的形式 给出x m l 主键和副键的定义,基于键讨论了x m l 数据冗余,分别定义为 “主键无关的冗余”和“副键无关的冗余”: 针对数据冗余的不同情况定义不同的x m l 范式,并给出消除数据冗 余的相应规则;在范式定义和规范化规则的基础上给出x m l 文档的规范化 x m l 数据的姚范化存储第1 章g f 言 算法,并给出算法分析和证明; 提出种新的x m l 模式到关系模式的规范化转换算法,该算法基于 本文所定义的x m l 键,包括主键、副键及隐键,结合函数依赖的约束,尽 量减少属性节点的冗余,使得到的关系模式中的关系表及其属性更加合理; 1 3 2 研究的理论和实际意义 “l 比h 刑l 具有更加灵活、可跨平台、简单易用等特性,在很短时间内 就得到广泛认同。并在众多领域都有应用,是种广泛通用的数据格式。 x m l 文档作为半结构化数据的特例,虽然可以很容易表达来自不同源的数 据,但是其所能表达的语法和语义信息却非常有限,由于x m l 的层次性和复杂 性,本文给出一组推理规则和一组消解规则,得到相对比较完整的数据依赖推理 规则集,以扩充已有的约束能力。除此以外,本文通过给出x m l 键的定义增强 了x m l 数据的语义表现力,使x m l 上约束的定义完整。 由于w e b 的开放性,x m l 数掘操作异常的危害性远远大于关系数据操作异 常的危窖性,因此,对x m l 数据异常原因的研究和消除异常方法的探索具有十 分重要的意义,已有的规范化规则不能消除所有的数据冗余,本文在“l 键的 基础上定义了两种不同情况的冗余,并给出相应的消除规则,可以消除对应的数 据冗余和操作异常。针对不同原因产生的冗余,本文将x m l 范式定义为三种, 最后利用定义的规则给出范式规范化转换的算法,由此得到消除冗余的规范化范 式,消除x m l 的数据冗余和操作异常。 另外,现有的关于x m l 与关系数据库之间的转换研究都是基于简单的映射 方法,这种映射仅保持了结构信息,忽略了语义上的约束保持,往往在转换过程 中产生大量的冗余,或丢失了语义,最终还要对得到关系模式进行规范化,大大 浪费了时间和资源。本文提出的一种新的基于“x m l 键”的x m l 模式到关系 模式的规范化转换算法,可以在转换过程中对约束进行分类,以键为中心得到更 加合理的关系表,同时保证了数据的完整性和致性。 1 4 本文结构 本文共分六章,文章结构和各章主要内容组织如下: 第l 章介绍了x m l 模式规范化的研究背景和研究意义,分析国内外的研究 现状,介绍了本文主要的研究工作和取得的成果,最后给出本文的整体组织结构: x m l 数据的规范化存储 第l 章引言 第2 章介绍了本文中涉及的规则和算法所使用到的形式化定义,包括d t d 、 x m l 文档、路径表达式、树元组等符号概念,并结合实例对定义和符号进行说 明,为后面章节的讨论做好准备: 第3 章讨论了x m l 模式中的语义约束,给出了x m l 函数依赖、x m l 多值 依赖的形式化定义,提出了x m l 键的概念;并给出其对应的逻辑规则及相关约 束的蕴涵和覆盖; 第4 章在键的基础上分析产生冗余和异常的不同原因,给出由键描述的两种 冗余的定义;在此基础上给出消除规则;并按照不同情况的冗余划分不同的范式, 根据提出的规则给出规范化转换算法;最后对算法进行证明和分析; 第5 章分析了现有的x m l 模式到关系模式的转换算法存在的弊端,提出了 一种新的基于“x m l 键”的转换算法,使满足任一范式的x m l 模式都可以一 步转换为规范化的关系模式; 第6 章总结了本文的工作,并对今后的研究做出了展望。 x m l 数摧的规范化存储第2 章摹本定义及符号 第2 章基本定义及符号 本章在已有的x m l 基本知识的基础上,形式化的描述了d t d 、x m l 文档 和路径表达式等基本定义,并进一步定义了x m l 文档树、节点值相等和树元组 等概念,为后面章节中的讨论作符号上的准备。为了便于x m l 数据库模式规范 化的研究,本章从文献中引用来的定义和符号做了形式化上的统一描述。 2 1d t d 定义2 1 ( 文档类型定义,d t d ) ”1d t d 定义为一个六元组d = ( e ,a ,p ,r ,r ) , 其中: d 为文档类型定义名。它是符号化的元组语义; e 表示元素类型( e l e m e n tt y p e s ) 的有限集合; a 表示属性( a t t r i b u t e s ) 的有限集合; p 表示从e 到元素类型定义的映射:对于每_ 个t e ,p ( 0 = s 或p 是如下定义的正则表达式口: c t := s l 占阳口i 口l 口,口l 口幸 其中,s 表示字符串类型( 元素类型声明中的# p c d a t a ) ,占是空序列 ( 元素类型声明中的e m p t y ) ,t e e ,“i ”,“,”和“t ”分别表示并、连接 和k l e e n e 闭包; r 表示从e 到a 的幂集p ( a ) 的映射,对于任意t e ,如果 l e r ( 0 , 称属性 i 是t 的定义; r e e ,是根元素类型,不失一般性,对于任意- e e ,假定r 不出现 在p ( ,) 中。 这里用e 描述元素名集合,a 描述属性名集合,s 描述字符串属性值集合, 所有的属性名均以符号 开头。 例2 1 :d t d d l ( e l ,a 1 ,p 1 ,r 1 ,r 1 ) 描述的是一个学校( s c h 0 0 1 ) 的信息,包 括课程( c o u r s e ) 、学 牛( s t u d e n t ) 、监护人( g u a r d i a n ) 实体之间的关系。d 1 定义如下: x m l 数据的规范化存储第2 章基本定义及符号 上课课时 实验谋时 图2 1 是一个符合d t dd 1 的d t d 示意图,并为了区分元素和属性,在属 性前加上 。 s c h o o l l 幸 c o b r s e ( 歹7 c n o c n a m eh o u rs t u d e n t c ,磊翟哪 h o u rh o u r ,| 套藩g r a d b g u a r d i a l l 3 n a n l e e s n o c r e d i t 图2 - 1 :符合d 1 的d t d 示意图 e 1 = s c h o o l ,c o u r s e ,c n a m e ,h o u r ,s t u d e n t ,c l a s s h o u r ,e x p e r i m e n t h o u r ,s n a n l e , c r e d i t ,g r a d e ,g u a r d i a n a i = c n o , s n o ) p 1 ( s c h 0 0 1 ) = c o u r s e + p l ( c o u r s e ) = c n a m e ,h o u r ,s t u d e n t p 1 ( h o u r ) = c l a s s h o u r ,e x p e r i m e n t h o u r p 1 ( s t u d e n t ) = s n a m e ,c r e d i t ,g r a d e ,g u a r d i a n 。 p 1 ( e n a m e ) = p 1 ( c l a s s h o u r ) = p 1 ( e x p e r i m e n t h o u r 、= p l ( s n a m e ) = p 1 ( c r e d i t ) = p i ( g r a d e ) = s r 1 ( c o u r s e ) = c n o ) r 1 ( s t u d e n t ) = s n o r 1 ( s c h 0 0 1 ) = r 1 ( c n a m e ) = r 1 ( h o u r ) = r 1 ( c l a s s h o u r ) 2 r i ( e x p e r i m e n t h o u r ) = r l ( s n a m e ) 。 r 1 ( c r e d i t ) = r l ( g r a d e ) = r 1 ( g u a r d i a n ) = 西 r l = s c h o o l - 7 x m l 数据的j 甏范化存储第2 章摹本定义及符号 从d t d 的定义可知,d t d 中元素类型和属性组成一个树形结构,为了描述 d t d 结构上的特点,引入文献【1 3 】中路径的概念: 定义2 2 ( d t d 路径) 【1 3 1 给定一个d t d d = ( e ,a ,p ,r ,r ) ,d 中的路径定义 为p = w 1 w n ,其中w l 可;w i e p ( w i - t ) ,i 【2 p 1 】;w e p ( w 1 ) 或w n 1 , 1 e r ( w n 1 ) 。 令p a t h s ( d 户 p i p 是d 中的路径 ,表示d 中所有路径构成的集合; e p a t h s ( d ) = p i p a p a t h s ( d ) 且l a s t ( p ) e e ,表示以元素类型结尾的路径构成的集合; a p a t h s ( d ) = p p e p a t h s ( d ) l 寻l 雒t q ) a ,表示以属性结尾的路径构成的集合。如 果p a t h s ( d ) 是无穷的,那么称d 为递归的,否则称为非递归的,本文仅考虑非递 归的d t d 。 l e n g t h ( p ) = - n 代表路径p 的长度;l a s t ( p ) - - w 表示路径p 的最后一个节点映射 的字符串,且p l a s t ( p ) 表示路径p 除去最后一个节点路径后表示的路径。如果 l a s t ( p ) = 占,那么p - - l a s t ( p ) ,所以为了便于叙述,本文仅考虑路径最后一个元 素不为空的情况,即l a s t ( p ) 占。 例2 2 在例2 1 中给出的d t d d l 定义中: s c h 0 0 1 c o u r s e s t u d e n t s n o 和s c h 0 0 1 o a 3 u r s e h o u r c l a s s h o u r 都是该d t d 上的路 径,前者属于a p a t h s ( d ) ,后者属于e p a :c h s ( d ) 。 2 2 x m l 树 给定d t d d ,符合d 的x m l 文档实际上就是d 的一个映像,在此给出x m l 文档的树形结构 2 0 】表示: 定义2 3 ( x m l 树) 给定d t d d = ( e ,a ,p ,r ,r ) ,称七元组t = ( v ,l a b ,e l e , a t t ,v a l ,r o o t ) 为满足( 或符合) d 的x m l 树,记作t 卜d ,其中: t 为x m l 树名,它是符号化的元组语义: v 是节点的有限集合 l a b 是从v 到e u a u s 的映射,对于任意节点v v :若l a b ( v ) 鼍且 t e ,则v 称为元素节点:若l a b ( v ) e a ,则v 称为属性节点;若i a b ( v ) 气,t e e 且p ( t ) = s ,则v 称为文本节点; e l e 是从v 到v 的部分映射,满足对任意v e v ,都有e l e ( v ) = v 1 ,v n 】 且l a b ( v t ) p ( t ) ,te e ,i e 【l ,n 】; a t t 是从v 到a 的部分映射,满足对任意v e v 和 l e a ,a r t ( v , 1 ) 有定义,当且仅当l a b ( v ) = t ,te e , 1 er ( ) ; x m l 数据的规范化存储 第2 章基奉定义及符号 , 7 赢c m m 。钐b o u t 手形歹、li 歹每 窄。d 鬯b , 哩,顾f 沁、| 、,霖、荟;,r 、 1 筘事觚、笤姜誊“可髫饕 图2 - 2 :符合d l 的一个x m l 文档实例 对于这样一棵树,我们可以前序遍历对其节点进行编号,记为n i ,i e 1 ,3 2 , 则可以得到如图2 - 3 的一棵x m l 实例树: n “0 l ”“j a c k w 3 ”。9 6 d。m ” 图2 - 3 :实例树t 1 通过例子可以看出,上述定义的直观解释是;v 是) m l 树t 中节点的有限 集合。映射l a b 用e u a u s 中的一个符号给v 中的每一个节点作标记。用元素 类型集合e 中的元素类型名称作标记的节点是元素类型的节点,并且映射e l e 和 a r t 分别定义了该元素类型节点的子元素类型和属性( 分别对应d t d d 中的映射p 和r ) ;用s 或者属性集合a 中的属性名称作标记的节点是树t 中的叶子节点, 映射v a l 给这些节点赋予一个字符串值。最后,用r o o t 表示该x m l 树的唯一根 h r 、氽一 貂一 彰 f 掣、善 如矿 x m l 数据的碰拖化存储 第2 章摹奉定义及符号 节点。相应的,我们也可以定义x m l 树中的路径: 定义2 4 ( x m l 路径) 【1 3 l 给定d t dd = ( e ,a ,p ,r ,r ) 和满足d 的x m l 树 t = ( v ,l a b ,e l e ,a r t ,v a l ,r o o t ) ,t 中的路径定义为p = v 1 “v n ,其中v l = r o o t ,y i e l e ( v i ,i ) i e 【2 ,n 1 b 如果t a b ( v ) e ,v n e d e ( v 1 ) ,且p ( 1 a b ( v 。) 降s ,称路径p 为 元素节点类型路径;如果l a b ( v ) e a ,v n a t t ( v 1 ) 或者l a b ( v ) e e ,v e l e ( v n 1 ) , 且p ( 1 a b ( v 。) p s ,那么,称路径p 为值类型路径。 令l a s t ( p ) - - - v 。,表示路径p 中最后一个节点:p a t h s ( t ) = p p 是t 中的路径 , 表示t 中所有路径的集合;e p a t h s ( t ) = p l p e p a t h s ( t ) 且l a b ( 1 a s t ( p ) ) e e ,表示元素 节点类型路径的集合;a p a t h s ( t ) = p l p e p a t h s ( t ) 且l a b ( 1 a s t ( p ) ) e a 表示属性值类 型路径的集合;v p a t h s ( t ) = p i p e p a t h s ( t ) j j 1 a s t ( p ) e e ,p ( 1 a b ( 1 a s t ( p ) ) ) _ s ) ,表示文 本值类型路径的集合。事实上,x m l 树t - d ,t 中的路径也是d 中相应路径 的映射。 例2 3 :在圈2 3 中给出的x m l 实例t 1 中: n o 。n 1 队n o n l 。n 2 和n o n 1 n 7 n 9 都是该x m l 树t l 的路径,第一个属于e p a t h s ( t ) , 第二个属于a p a t h s ( t ) ,第三个属于v p a t h s ( t ) 。 2 3 节点值相等 关系数据库中的元组相等是严格意义上的值相等。由x m l 树的定义可以看 到一个x m l 文档是典型的节点标签树,据此,节点值相等也对应的定义在树元 组上。接下来给出x m l 文档树中树元组和值相等的定义。 定义2 。5 ( 树元组) 给定d t d d = ( e ,a ,p ,r ,f ) 和满足d 的x m l 树t = ,l a b , e l e ,a r t ,v a l ,r o o t ) ,树元组t 定义为p a t h s ( d ) 至0v u s u 上 的映射,满足: 如果p e e p a t h s ( d ) ,那么t p 】v u f 上 ,且t 嘲上;否则t p e s u 上 : 如果t p d - - t p : gt p l 】v ,那么p l = p 2 ; 如果t p d = _ l 且p l 是p 2 的前缀,那么t p 2 】= 上; ( p e p a t h s ( d ) l t p 】上 是有限的。 其中s 和j - 分别表示字符串值( 文本) 和空值。令t 【日= t n t 表示树元组的 集合,树元组t 【p 】可记作t p 。 , 例2 4 图2 2 文档树中的部分树元组为: t l 【s c h 0 0 1 c o u r s e = n 2 ,t 2 s c h 0 0 1 c o u r s e = n 2 1 元素节点类型 t l s c h 0 0 1 c o u r s e s t u d e n t s n o 】一0 1 , t 2 s c h 0 0 1 c 0 1 1 r s e s t u d e n t s n o 2 0 2 x m l 数据的碰扭化每储第2 章摹奉定义及符号 属性值类型 t l s c h 0 0 1 c o u r s e e n a m e l = d b ”,t 2 s c h 0 0 1 c o u r s e c n a m e = “o s ” 文本值类型 定义2 6 ( 节点值相等) 给定d t d d = ( e ,a ,p ,r ,r ) 和满足d 的x m l 文档树 t = ( v ,l a b ,e l e ,a r t ,v a l ,r o o t ) ,1 1 1 和n 2 是v 中的节点,两个节点1 1 1 和n 2 是值相 等记为n l = 。n 2 ,当且仅当下列条件是满足的: l a b ( n 1 ) - j a b ( n 2 ) ; 如果n l 和n 2 是a 或s 节点,那么v a l ( n 1 ) :v a l ( n 2 ) ; 如果i l l 和n 2 是e 节点,那么( 1 ) v a l e a t t ( n o ,j a u e a u ( n 2 ) ,满足a j = v a 2 , 反之亦然;( 2 ) 如果e l e ( n 1 ) 叫l ,- - , v k ,e l e ( n 2 ) - - - v l , - - , v k ,那么对于所有i e 1 ,k 】, v i = v v i 。 从x m l 文档中来看,对节点n l 和n 2 ,若节点n l 和n 2 表示的是x m l 文档 树上的同一个节点,则称n l 和m 相等,记为l l l 瑚2 ;若l a b ( n 1 ) - l a b ( n 2 ) ,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论