（计算机软件与理论专业论文）基于dtd的xml环的研究.pdf

摘要 摘要 在关系数据库中，无环数据库模式设计是数据库理论与图论相结合而 产生的一个新的研究领域。无环数据库有许多优良特性，无环成为判断数 据库模式优劣的又一重要标准。这里的环指的是在关系数据库中由于某些 属性存在二义性，使得在查询这些属性的时候存在两条或两条以上的路径， 这就形成了环。同样的，在沮，文档中也存在着环。在) 。沮，文档中，某 些元素的定义不能准确的表示元素的语义，使得在查询特定内容，而又缺 少上下文语义关系的情况下，不能准确得到查询结果，这就是查询二义性 问题。本文从一个全新的角度对x m l 数据的规范化进行了研究，定义了基 于d t d 的x m l 环，并设计了d t d 中x m l 环的判定算法和重新定义元素 的d t d 中舭环的消除算法。 本文从研究帆文档的查询二义性出发，首先，分析多种存在环结构 的d t d ，总结其结构特点，据此定义了基于d t d 的x m l 环，并根据环结 构特点的不同进行了分类。根据x m l 环的定义，进一步分析存在环的d t d ， 发现某些元素存在多个父元素或者根元素也成为其他元素的子元素这个特 点，根据这个特点设计d t d 中x m l 环的判定算法。其次，分析在) m l 文档中如何消除查询二义性，并设计x m l 文档中消除二义性的方法。根据 存在环的d t d 的特点和d t d 中x m l 环的判定算法的结果，设计基于重新 定义元素的d t d 中x m l 环的消除算法，使d t d 满足x l n f ，并指出使用 该算法消除x m l 环以后还存在的一些问题。最后结合其他文献提出的使 d t d 满足) ( 2 n f 和) 【3 n f 的算法，设计d t d 满足) 。虾的算法。 本文设计的x m l 的判定算法和x m l 环的消除算法能嵌入到一些d t d 和x m l 的编辑器的功能模块中，具有实用意义。 关键词环；二义性；x m l ；d t d ；规范化 燕山大学工学硕士学位论文 a b s t r a c t a e y c l i cd a t a b a s es c h e m ed e s i g n i n gi s an e wr e s e a r c hf i e l di nr e l a t i o n a l d a t a b a s e ；i tc o m b i n e sd a t a b a s et h e o r yw i t hg r a p ht h e o r y a e y c l i cd a t a b a s eh a s m a n yg o o dc h a r a c t e r i s t i cp r o p e r t y s i tb e c o m e sa n o t h e ri m p o r t a n ts t a n d a r dt 0 e v a l u a t et h ed a t a b a s ep a t t e r ni ss u p e r i o ro ri n f e r i o r n ec y c l eh e r em c a n st h a t s o m ea t t r i b u t e sa r ea m b i g u o u si nr e l a t i o n a ld a t a b a s e t h e r et i t l et w oo rl l l o r e p a t h sw h e nq u e r ya b o u tt h e s ea t t r i b u t e s ，s ot h ec y c l eh a sf o r m e d c y c l ee x i s ti n t h ex m ld o c u m e n ti nt h es a m e i fd e f i n i t i o no fs o m ee l e m e n t sc a n n o td i s p l a y t h em e a n i n go fe l e m e n ti nx m ld o c u m e n tp r o p e r l y ，t h e r ew i l lb e 如z z yr e s u l t w h e nq u e r ys o m ee l e m e n tw i t h o u tc o n t e x ti n f o r m a t i o n , t h e nw ec a n n o td e c l a r e t h em e a n i n go fq u e r i e dr e s u l t , i ti s q u e r ya m b i g i i i t y t h i sp a p e rs t u d y n o r m a l i z a t i o no f 也d o c u m e n tf r o man e wp o i n to fv i e w , d e f i n ex m l - c y c l e b a s e do nd t d ，p r o p o s ead e t e r m i n a n ta r i t h m e t i ci ft h e r ei sa n yc y c l ei nd t d ， p r o p o s eaa r i t h m e t i co f d e f i n en e w e l e m e n tt oe l i m i n a t ec y c l i ci nd t d b e g i nw i t hs t u d y i n gt h eq u e r ya m b i g u i t yo fx m l d o c u m e n t ，t h ew o r k so f t h i sp a p e ri s ：f i r s t , a n a l y z ev a r i o u sd t dw i t hc y c l e - s t r u c t u r ei ni t , g e n e r a l i z e t h es t r u c t u r ee h a r a e t e r i s t i e a n da c c o r d i n g l yd e f i n ex m l c y c l eb a s e d0 1 1d 1 d a c c o r d i n gt ot h ed e f i n i t i o no f x m l c y c l e a n a l y zd t d w i t hx m l - e y d ef l l l t h e l , d i s c o v e rt h ec h a r a c t e r i s t i co fd t dw i t hx m l - c y c l et h a ti ss o m ee l e m e n t sh a v e m o l et h a no n ef a t h e re l e m e n to rt h er o o te l e m e n th a v ef a t h e re l e m e n t a n d p r o p o sa d e t e r m i n a n ta r i t h m e t i ct oc h e c kt h a ti f t h e r ei sa n yx m l - c y c l ei nd t d s e c o n d , p u tf o r w a r dam e t h o do fe l i m i n a t et h eq u e r ya m b i g u i t y o i lt h eb a s i so f a n a l y z i n g p r o p o s ea l la l g o r i t h mo fd e f i n en e we l e m e n tt oe f i m i n a t ee y e l i ei n d t do nt h eb a s i so f t h ec h a r a c t e r i s t i co f d t dw i t hx m l c y c l ea n dt h er e s u l to f d e t e r m i n a n ta r i t h m e t i c ，n 3 a k ed t ds a t i s f yx 1 n f a n dp o i n to u tt h ep r o b l e m so f d t da f t e rx m l e y c l ei se l i m i n a t e d c o m b i n i n gw i t ht h ea l g o r i t h mo fm a k e a b s t r a c t d t ds a t i s f yx 2 n fa n dx 3 n f ，p r o p o s ea l la l g o r i t h mt h a tm a k ed t ds a t i s f y x n f a t l a s t t h ea r i t h m e t i c sp r o p o s e di nt h i sa r t i c l ec a l lb ee m b e d d e di ns o i n ef u n c t i o n m o d u l eo f x m le d i t o ro rd t de d i t o r , i ti st h em e a n i n go f p r a c t i c a l i t y k e y w o r d sc y c l e ；a m b i g u i t y ；d t d ；x m l ；n o r m a l i z a t i o n 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于d t d 的皿。环的研究， 是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所 取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰 写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在 文中以明确方式注明。本声明的法律结果将完全由本人承担。 毛 作者签字墨佛向)日期：。7 年；月巧日 燕山大学硕士学位论文使用授权书 基于d t d 的) 。m ，环的研究系本人在燕山大学攻读硕士学位期间 在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有， 本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解 燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密吼 ( 请在以上相应方框内打。”) 作者签名：莓伟序)日期：。7 年；月玷日 导师签名：囱良选 日期：0 7 年3 月2 拍 第1 章绪论 1 1 研究背景 第1 章绪论 在关系数据库中，无环数据库有许多优良特性，无环成为判断数据库 模式优劣的又一重要标准。这里的环指的是在关系数据库中由于某些属性 存在二义性，使得在查询这些属性的时候存在两条或两条以上的路径，也 就是从一个属性到另一个属性存在着多条通路，这就形成了环。在对无环 数据库的研究过程中，发现数据库模式存在着不同级别的无环性，r f a g i n 描述t - - 种重要的无环类型【l 】，无i f , 环，无p 环，无t 环，且无t 环j 无 b 环，无p 环j 无o f , 环。无y 环数据库模式消除了查询二义性，而且有许 多优良特性，在文献【1 】中给出了相关的证明。 随着网络的发展，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 ) 文档被广泛应用， x m l 已成为事实上的网络传输标准。大量的关系数据表示为x m l 文档在 网络中传输和交换，从而使关系数据中的某些问题不可避免的出现在了 x m l 文档中，如插入、删除和查询错误、数据冗余等。在关系数据库中， 解决这些问题的方法是对关系模式进行规范化处理。同样的，对x m l 模式 进行规范化处理也能解决x m l 文档中的这些问题。帆数据可以表示为 树型结构，x m l 数据的查询以路径为基础，如果从某一节点出发，通过不 同的路径，到达了相同的节点，就会产生查询二义性。x m l 文档也有自己 的模式，如x m l d a t a 、x m l s c h e m a 和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 ) 等。而在实际应用中，d t d 是x m l 文档使用最多也是应用 最成熟的一种模式。 有的关系数据库模式中存在环，存在环的数据库模式有很多缺点，如 查寻二义性等。同样，有的) m 几模式中也存在环，在存在环的x m l 模式 中，有的虽然语法上完全正确却不存在任何“有效的”x m l 文档遵循这个 x m l 模式；有的虽然存在x m l 文档，但不能有效查询存在二义性的元素。 燕山大学工学硕士学位论文 ) ( 1 帆模式中的环研究得还比较少，处于起步阶段。 本课题结合关系数据库中无环数据库的研究方法，从研究x m l 文档的 查询二义性出发，分析了存在环结构的d 1 d ，根据存在环结构的d t d 的结 构特点定义了讧l 环，并根据特点的不同进行了分类，给出了d t d 中x m l 环的判定算法和d t d 中x m l 环的消除算法。 1 2 无环数据库和x m l 文档规范化研究现状 无环成为判断数据库模式优劣的一个重要特性，许多学者对它进行了 深入地研究，取得不少成果。对无a 环环数据库的研究已经比较成熟，郝 忠孝等人在研究了数据库模式分解为满足p 3 ( 无损连接，保持依赖和3 n r ) 及无o c 环的条件 2 1 ，万静等人分析了在属于f d ( f u n e t i o n a ld e p e n d e n c y ) 集f 的任意最小归并依赖集d 存在弱左部或弱右部时所具有的性质和特征，在 此基础上讨论了它的模式分解问题，给出了d 有弱冲突时，满足p b c 是有 a 环的结论【3 】。郝忠孝在前期讨论基础上讨论了数据库模式无内部冲突，但 在最小归并依赖集d 中存在弱右部或弱左部冲突时分解的性质和理论【l 。 为无内部冲突的满足p 3 的无o 环的数据库模式分解算法设计提供了基础； 给出了数据库无内部冲突时满足p 3 且为无a 环的数据库模式分解算法、正 确性证明及分析。 由于无p 环具有子图无环性和比无丫环的限制条件宽松等优势，很多 学者都把无环数据库研究的重点放在了无1 3 环上，刘文远等人提出了严格 无冲突的概念 6 1 ，以线图为工具，证明了应用分解树算法对一个严格无冲突 的m v d ( m u l t i v a l u e dd e p e n d e n c y ) 集分解得到的数据库模式对应的线图及等 权化筒子图都是三角化的，而且线图中每个三角形都是相容的。最后得出 无冲突条件下无d 环且满足保持数据依赖、无损联接和4 n f 的数据库模式 分解的充要条件是给定的m v d 集存在一个严格无冲突的覆盖；给出了基于 线图的无1 3 环混合依赖分解条件及算法【”，对无p 环进行了比较全面深入的 研究i s 。 虽然无t 环的限制条件比较苛刻，但因其满足了查询无二义性的要求， 2 第1 章绪论 也有不少学者把研究精力放在了这上面。无y 环的研究基本上还处于研究 无7 环的存在条件上，如姚春龙等人研究了在m v d 下，无1 r 环数据库模式 的存在条件【9 j 。 对无环数据库的研究目前还处于理论研究阶段，实际应用还比较少。 周国亮将无环理论用于x m l 文档【1 0 1 ，在研究x m l 文档规范化的同时用无 环理论去解决x m l 文档中的查询二义性问题。 目前，许多主流的数据库厂商都把x m l 支持结合到其产品中，或者提 供可在其数据库中使用x m l 的工具。m m 提供了x m le x t e n d e rf o rd b 2 ， 以允许用户在d b 2 中存储x m l 文档，并提供一些新功能协助用户处理 x m l 文档；m i c r o s o f t 的s q ls e r v e r6 5 和7 0 也进行了x m l 扩充，在s q l s e r v e r 2 0 0 0 中己加入了) 。m 。输出选项，用以向其他系统传送信息。o r a c l e 也拥有功能强大的x m l 索引引擎。 当前，已经出现了很多存储x m l 的方法，大多数方法都是直接将x m l 文档转换成其他的数据形式来存储在数据库中，而不是从数据库设计的角 度进行x m l 数据的存储。基于数据库设计，将x m l 看作网络世界中的数 据模型，d t d 看作是x m l 数据的模式。在此基础上，提出了d t d e r ( 实 体联系模型) 方法( 也就是一种d t d 到e r l l l 】模型的转换方法) 以及基于 d t d e r 方法的x m l 数据存储技术。 2 0 0 1 年m a r e n a s 和l l i b k i n 提出了x n f ( x m ln o r m a lf o r m ) ”】的概念 和任一文档转化为x n f 的算法，其中x n f 基本上与在关系数据库规范化 中讨论的b c n f ( b o y c e c o d dn o r m a lf o r m ) 相一致，并且系统的给出了x m l 文档、d t d 、x m l 文档中的f d 的表示方法和它们之间的关系，最后又提 出当在文档中存在m v d 的情况下还需要进一步探讨。2 0 0 2 年，m o n g l i l e e ， t o kw a n gl i n g 和w a il u pl o w 等提出了良好结构的x m l 文档 ( w e l l - s 仇l c t l 】r e d ) 的概念 1 3 1 ，给出了相关定义，提出了估算在x m l 中的数 据可能的最大上下文集势c o n t e x tc a r d i n a l i t y 的公式，用来预测数据的重复 次数，以此来判断数据冗余的程度，最后又给出了一个基于f d 的解析器， 用来检测x m l 文档中由于数据依赖而引起的错误。一些相关文献为x m l 文档的规范化提出了数据模型，如s i ny e u n gl e e ，m o n g l il e e 等提出的 燕山大学工学硕士学位论文 s 3 g r a p h ( s e m i - s t r u c t u r e d s c h e m ag r a p h ) 1 4 1 ，n f s s ( n o r m a lf o r m s e m i s t r u c t u r e d ) 0 5 】，以及比较熟悉的o e m ( o b j e c te x c h a n g e dm o d e l ) 【1 6 l 等，这些 数据模型为x m l 文档的规范化带来了很大方便。2 0 0 3 年复旦大学的谈子 敬，庞引明，施伯乐等人提出了x m l 函数依赖推理规则【1 7 1 ，为x m l 规范 化进一步提供了理论基础。吕腾等人研究了x m l 的范式【1 8 1 ，给出了x m l 函数依赖、部分函数依赖和传递函数依赖的概念，然后据此提出了三种x m l 范式：x 1 n f 、2 x n f 和3 x n f 。提出了d t d 无损联接分解的概念，给出了 两个把d t d 无损联接地分解成2 x n f 和3 x n f 的算法。张忠平和吕腾对 x m l 文档规范化作了比较全面深入的研础1 9 捌。有的学者研究了关系模式 到x m l 模式之间的互相转换问题，王庆等人提出了既能保持x m l 文档的 内容和结构信息，又能保持函数依赖信息的映射方法【2 ”。刘云生和吴文辉 分别提出了从关系模式到x m l 文档的转换算法1 2 2 ，2 3 】。m u s t a f a a m y 等人提 出了从d t d 到关系模式的得到有效模式的算法脚】。游中胜提出了ss c h e m a 到关系模式的转换和加载算法【2 5 】。曾字昆等人提出了满足关系模式规范化 约束的从x m l 到关系模式的映射方法1 2 6 1 。何盈捷等人提出了一种保持依赖 的从d t d 到关系模式的映射方法p d d 2 ”。 对x m l 文档进行查询时，文献 2 8 ，2 9 提出了d a t a g u i d e 的概念，文献 【3 0 】以d a t a g u i d e 为评估路径研究了数据库的检索效能。其对于提高查询效 率有很大帮助，但在构建d a t a g u i d e 时，如果文档中存在环结构，构建的模 式可能非常庞大，最坏情况下生成d a t a g u i d e 算法的复杂度是指数级的，文 献 3 l 】给出了具体的说明。在无环的文档中，由于消除了文档中的环结构， 从而构建d a t a g u i d e 就相对容易，而且比较简单。这样就提高了x m l 文档 的查询效率。 关于帆文档中存在的环只有较少的一些文献有所涉及，并没有给出 详细的定义和系统的分析。s h i y o n g l u 等人提出了d t d 一致性的概念【3 2 捌， 指出语法上完全正确的d t d 可能是不一致的，即不存在任何“有效的” 沮，文档遵循这个d t d ，并d t d 给出了d t d 一致性的充要条件，路燕 等人在此基础上提出了d t d s 完全一致性的概念，并给出了线性时间复 杂性d t d s 完全一致的判断算法，并对算法的正确性进行了证明。他们所 4 第l 章绪论 提到的不一致的d t d 中都存在着环结构，由d t d 中的元素循环调用构成。 文献【1 0 】根据关系数据库中的超图理论，提出了x m l 超图，并根据关系数 据库中丫环的定义方法，在x m l 超图中定义了x m l7 环和一些相关的概 念，并给出了判定算法。基于x m l 超图判定x m ly 环需要先将d t d 映 射为关系模式，再根据关系模式给出超图，过程比较繁琐，而且在映射成 关系模式时，有些元素的语义可能会发生变化。本文将基于d t d 定义x m l 环，就能省去了d t d 映射为关系模式和超图这一环节，并且使x m l 环的 定义更加直观和利于理解，环的判定和消除也会比较简单。这些功能也能 比较方便地嵌入到一些d t d 和m ，编辑器中。 1 3 本文主要工作和论文结构 通过以上的分析可以看出，目前x m l 文档的规范化是重要的研究方 向，本文在他人研究的基础上重点研究以下问题。 ( 1 ) 分析二义性的性质和存在二义性的d t d 的结构特点。并指出存在二 义性的d t d 中存在环结构：分析各种存在二义性的d t d 中的环结构的特 点，并进行分析、总结、提取，在此基础上定义基于d t d 的x m l 环；在 咀。环定义的基础上，提出d t d 中x m l 环的判定算法。 ( 2 ) 分析克服x m l 文档查询二义性的方法，并具体分析存在环的d t d 中，存在二义性的元素的和其父元素、子元素和函数依赖间的各种关系， 并根据分析结果提出基于重新定义元素的消除x m l 环的算法。分析d t d 中消除x m l 环之后还存在的问题，并使用现行的x m l 文档的规范方法来 解决该问题，最后提出使d t d 满足x n f 的算法。 本课题的意义在于，随着大量x m l 文档的使用，对x m l 文档的操作 也在相应的增加。如果文档没有进行规范化，当对文档进行查询或者其他 操作时就会出现各种异常。然而通过规范化以后x m l 文档在一定程度上克 服了这些异常和查询二义性，并具有某些优良特性。当前数据库理论研究 与实际应用已经出现了脱节，x m l 的出现给数据库领域注入了新鲜血液。 数据库理论的研究人员开始考虑将原有数据库理论应用到x m l 的研究中， 燕山大学工学硕士学位论文 推动理论与实际相结合从而产生巨大的社会效益和经济效益。 本文共分为4 章，内容包括： 第1 章为绪论，从无环数据库和沮。文档规范化现状分析引出课题研 究工作的出发点，指出了存在的问题以及急待解决和完善的问题，对本文 的研究内容进行了概述，最后给出论文的结构。 第2 章对) 。沮，文档深入剖析，研究咀，文档和d t d 的基本知识和 无环数据库理论，为后面的研究做了必须的准备。 第3 章分析) 叫l 文档中的查询二义性；分析存在环结构的d t d 的特 点，并根据特点基于d t d 定义m ，环，并根据特点的不同进行分类，最 后给出d t d 中x m l 环的判定算法。 第4 章分析沮。文档中消除查询二义性的方法，设计基于重新定义元 素来消除d t d 中x m l 环的算法。结合其他文献提出的d t d 满足x 2 n f 和x 3 n f 的算法，给出d t d 文档满足盯的算法。 最后，在结论中对本文的工作进行总结，并对进一步的研究进行分析 和展望。 6 第2 章x m l 文档和无环数据库 第2 章x m l 文档和无环数据库 2 1 x m l 简介 x m l 是一种界定文本数据的简便而标准的方法。它曾经被人们称作 “w e b 上的a s c n 码”。就好像程序员可以用自己喜欢的编程语言来创建 任何一种数据结构，然后同其他人在其他计算平台上使用的其他语言来共 享一样。x m l 的标记用来说明所描述的概念，而属性则用来控制它们的结 构，因此人们可以定义自己所设计出的语法与他人共享。x m l 数据描述机 制意味着它将成为一种在i n t e m e t 上共享信息的强大途径，必将成为网络传 输的数据标准，这主要有以下三条原因。 ( i ) 它是开放的，x m l 能够在不同的用户和程序之间交换数据，而不考 虑其平台如何； ( 2 ) 它自描述的特性使其对于b 2 b ( b u s i n e s st ob u s i n e s s ) 和企业内部网的 解决方案来说是一种有效地选择； ( 3 ) 它无需事先协调就可以在程序之间共享数据。 x m l 具有以下一些特性：x m l 具有自描述性( 元素的标记描述了信息) 、 可扩展性、可分析性、可重用性、自解释性、简单性和开放性。 2 1 1 ) 见基本语法 首先x m l 是基于标签的，与h t m l 的标签不同，x m l 的标签不需要 预先指定含义，相反，它只是用来标记数据。所谓的“x m l 基本语法”， 依据x m l 规格，大致可以整理如下。 ( 1 ) x m l 声明必须以小写“x m l ”声明，并设置v e r s i o n 属性而且是出现 在第一行； ( 2 ) 一定要有一个根( r o o t ) 节点，而且只能有一个根节点； ( 3 ) 所有标记必须以树状排列； 7 燕山大学工学硕士学位论文 ( 4 ) 除了内容为空的标记外，所有的标记都必须以开始标记、结束标记 成对出现； ( 5 ) 内容为空的标记结尾必须加上“”，这种标记称为“空标记”； ( 6 ) 标记名称与属性必须合法，且大小写被视为不同； ( 7 ) 属性值的指定前后必须被双引号所包含； ( 8 ) 特殊字符必须依照规定编写。 符合上述8 个条件的x m l 文件称为w e l l - f o r m e dx m l 文件。 2 1 2 验证规则( d ) 与x m ls c h e m a ) 文件需要验证的理由有很多种，针对b 2 b ( b u s i n e s st ob u s i n e s s ) 或 b 2 c ( b u s i n e s s t oc o n s u m e o 电子商务网站而言，每一个订单都需要做正确性 的检查，以保障网站的安全。而验证规则可带来一个好处，当您将订单规 范成一个x m l 文件或x m l 数据包时，接收端只需要简单的几条命令，分 析器就会帮您做订单的基本格式确认，而不需要编写复杂的程序来做文件 正确性确认。确认包括四点。 ( 1 ) 确认元素( 标记) 与属性都是使用规范中的名称以及内容： ( 2 ) 确认属性是否可属于或应属于某一个元素( 标记) ； ( 3 ) 确认子元素( 标记) 的顺序与个数是否合法； ( 4 ) 确认元素( 标记) 与属性的数据类型是否合法。 帆的验证规则又可以分为d t d 和x m ls c h e m a 两种；d t d 是) a 证l 标准中所制定的验证规则语法，d t d 源自s g m l ( s t a n d a r df o rg e n e r a l m a r k u pl a n g u a g e ) ，因此，无法完全适用于x m l 的应用。于是，另一个较 新的x m l s e l a e m a 开始被开发，x m l s c h e m a 也是一个) m 也的应用，意即 x m ls c h e m a 文件也是x m l 文件，并且提供了更多数据类型的支持【3 5 】。 2 1 3x m l 模式d t d 定义2 1 ：d t d ( 文档类型定义) 定义成d = ( e4 ，p 皿，力3 6 1 , 其中： ( 1 话表示元素类型的有限集合； ( 2 m 表示属性的有限集合； 8 第2 苹x m l 文档和无环数据库 ( 3 炉是从e 到元素类型定义的映射：对于每一个f e ，p ( 订爷或只f ) 是正规表达式a ：c t ；：= 翻s i a c t l a * ，其中s 表示字符类型( 元素类型声明中 的# p c d a t a ) ，s 是空序列( 元素类型声明的e m p l y ) ，f e e ，“- ”和“” 表示连接和k l e e n e 闭包； ( 4 皿是从e 到4 的幂集p 0 ) 的映射，对于任意t e e ，如果 ，r ( r ) ， 称属性w 是f 的定义； ( 5 ) ，e ，是树根的元素类型。在这里假定对于任何的f e ，r 不出现 在p ( 力中。 为了描述d t d 结构上的特点，引入文献【1 2 】中路径的概念：给定d t d d = ( e4 ，p 疋力。d 中的路径p 定义为旷硼1 。，栉小于等于元素和属性的 个数之和，其中c 0 1 - - r ，珊f e p ( t o 1 ) ，j 2 ，3 ，西1 ) ；如果t o e a ，那么 c o h r ( + 1 ) ；否则，p ( + 1 ) 。 令p a t h s ( d ) = 仞p 是d 中的路径 。如果p a t h s ( d ) 是无穷的，那么d 叫 做递归的，否则称为非递归的。本文仅考虑非递归的d t d 。用l a s t ( p ) 表示 路径p 的最后一个符号，用f l a s t ( p ) 表示路径p 除去最后一个符号后所表示 的路径。显然，如果l a s t ( p ) = e ，那么p = p - l a s t ( p ) 。所以为叙述方便，下文只 考虑路径的最后一个元素不为空的情况，即l a s t ( p ) ：e 。 d t d 中描述的基本部件是元素和属性，它们负责确定x m l 文档的逻 辑结构。元素表示一个信息对象，而属性表示这个对象的性质。d t d 有两 种基本的元素类型，一种称为简单类型，另一种称为复合类型。简单类型 具有文本数据，即可析字符数据，该类型也称为上下文中的卯c d a l l a 或 p c d a t a ；复合类型可以包含其他元素和文本数据。所有的元素中有且只 有一个根元素，其他的元素都是它的子元素，除根元素外，每个元素都被 其他元素包含，一个元素可以有几个不同类型的子元素。 在有效的x m l 文档中使用的每项标记都要在d t d 中的元素声明中进 行声明，声明必须以子符串 ! e l e m e m t 开始，随后描述的是元素名称和 元素的内容规范。元素的声明格式如下所示。 其中，e l e m e n t n a m e 是元素名，它决定了在x m l 文档中所使用的标记。 9 燕山大学工学硕士学位论文 这个名称在单个d t d 中必须是唯一的。t y p e 是元素的类型，也就是元素的 内容范围。虽然按规定元素名在单个d t d 中必须是唯一的，在一些不太严 格的x m l 解析器中，部分存在同名元素的d t d ，甚至存在元素重复定义 的d t d ，也可以被使用，调用这种d t d 的x m l 文档，在i e 浏览器中也 可以被显示，并可以做一些查询。 x m l 中支持下列4 种元素类型。 ( 1 ) e m p t y 不包含数据内容，但可以有属性； ( 2 ) m q y 包括任何x m l 允许的内容； ( 3 ) e l e m e n t 只包含子元素； ( 4 ) m i x e d 允许元素包含于元素和数据内容。 为了描述元素出现的状态，可以用“一、“l ”、“? ”和“+ ”等来 修饰，这些符号的含义和用法将在后面详细讨论。 由于多数元素都有子元素，因此给出子元素的描述是不可缺少的，d t d 中描述具有子元素的一般语法格式为 ，其中，c o n t r o l m o d e l 是子元素的控制模式，它由圆括号、子元素名、 逗号、加号、问号和竖线组合而成，现分述如下。 圆括号表示将圆括号中的子元素合并成为一个整体，而逗号则表示子 元素必须按照次序出现；在子元素中，如果没有增加加号、问号等修饰符 号，则表示该子元素必须出现，且只能出现一次；在d t d 的元素声明中， 用逗号隔开的一系列子元素称为序列；用加号修饰的子元素表示该子元素 必须出现1 次以上；用星号修饰的子元素表示该子元素可以出现任意次； 用问号修饰的元素表示该元素可以出现0 次或1 次：用竖线描述的内容规 范称为选择，表示在多个被选元素中进行选择，且被选的元素只能出现一 个和出现一次。 在d t d 中，由于每个元素只能在 中声明一次，那么是否 需要严格安排元素的声明次序，以保持元素声明的条理性呢? d t d 中这是 不必要的，因为x m l 允许对元素的声明提前引用。 从d t d 的定义可知，d t d 中的元素类型和属性组织成一个树型结构， 下面给出树型结构的d t d 图的定义。 1 0 第2 罩x m l 文档和无环数据厍 定义2 2 ：d t d 图g = ( m 三) 。其中n 是节点集，工是有向边集。 图的节点集e u 爿) ，e 是d t d 中出现的元素( e l e m e n t ) 的集合，4 是 d t d 中出现的属性( a t t r i b u t e ) 的集合。其中，每个元素和属性在图中只能出 现一次，边是由相应操作符号表示的操作。l 到2 的有向边。其中，l ， n 2 n ，n 2 是1 的子元素或者属性。 d t d 图中的边包括一，一? ，一，一+ 和一i ，表示在引用该d t d 的 x m l 文档中子元素出现的次数，因为d t d 图的边的类型并不影响环的结 构特点，所在定义x m l 环的时候只考虑“一”边。但不同类型的边对x m l 是有影响的，本文将在消除x m l 环的方法中具体说明这一点。 2 1 4x m l 函数依赖 相对于关系模式中的函数依赖，d t d 上的函数依赖是基于路径的，下 面给出它的定义【3 刀。 定义2 , 3 ：给定d t d d ，在d 上的函数依赖妒具有如下形式。 ( s h ，阪l ，s 柚】一晦l ，一与d ) ，其中 ( 1 ) s h p a t h s ( d ) n q 做函数依赖妒的头部路径，定义了9 在d 上成立的范 围。该路径的最后一个符号是一个元素类型的名称，即l a s t ( s h ) e e 。如果 s h - ：o 且r ，那么妒叫做相对函数依赖，表示妒只有在以l a s t ( s h ) 为根的子 树范围内才成立；否则，矿叫做绝对函数依赖，表示9 在整个d 上均成立； ( 2 ) 阵l ，蹦叫做妒的左部路径，对每一个f l 2 朋- l ，都有 鼠p a t h s ( d ) ，s x i o 且l a s t ( s “) e e u a u s ； ( 3 ) s y l 焉嗣叫做妒的右部路径，对每一个_ ， 1 , 2 ，胁1 ，都有 p a t h s ( d ) ，m 且l a s t ( s 打) e e u a u s ； 这里所定义的函数依赖，在比较两个元组在值类型的路径上是否相等 的时候，比较的是这两个元组在该路径的最后一个符号所表示的属性或者 元素的取值是否相等；但是在比较两个元组在节点类型的路径上是否相等 的时候，比较的是该路径在x m l 文档中所对应的节点是否相同。 在d 上的函数妒：( s ，【氏】寸陋。s 。】) ，总是可以把它的右部 路径分开，从而可以写成如下所示的m 个函数依赖： 燕山大学工学硕士学位论文 妒：( ， & i 氏】寸) ，j 【1 ，研】 所以不失一般性，在下文中，如无特别说明，只考虑函数依赖的右部 路径是单路径的情况，即具有如下的形式： 9 ：( 瓯，【墨1 】一q ) 2 2x m l 查询 x m l 模糊了数据库、文档、和消息之间的界线，但是，要充分发挥 x m l 的所有潜能，还必须要有强大的、优雅的查询语言。 2 2 1 x m l 查询语言综述 随着互联网的飞速发展，x m l 以其强大的数据表达能力及其简单、跨 平台的优点逐渐成为信息存储、交换和表示的事实标准，因此如何有效的 查询x m l 信息这个问题也变得日益重要。在这种背景下，研究人员提出了 很多种x m l 查询原型语言，其中比较著名的有x m l q l 3 8 1 ，x s l ，x q l 3 9 1 ， x m l g l t 4 0 l ，q u i l t | 4 1 】等。 ( 1 ) x m l q l 由a t & t 实验室的数据库研究人员设计。x m l q l 通过 加入明确的构造语句c o n s t r u c t 扩展s q l ，使用元素模式匹配进行查询 处理。 ( 2 ) x m l g l 意大利p o l i t e c n i od im i l a n o 大学所设计的一种图形化查 询语言，它利用边标记图来图形化表达x m l 数据和d t d 。在x m l g l 中 所有元素都是可视的，适于作为友好的人机界面( 类似q b e ) 。 ( 3 ) x s l 由w 3 c 的x s tt 作组设计。一段x s l 程序包含一组模板规 贝l j ( t e m p l a t er u l e ) ，每个模板规则由两部分组成：与数据源中某节点匹配的 模式和一个示例模板构成输出树。x s l 利用x p a t h 定义的语言处理选择、 条件和文本产生。 ( 4 ) x q l 由微软公司设计的。它的作用是选择和过滤x m l 文档的元 素和文本。x q l 可以看成是x s l 模式语法的自然扩展，它的设计目标是简 单、紧凑，可以作为u r i 的一部分，所以降低了部分表达能力。 第2 章x m l 文档和无环数据库 ( 5 ) q u i l t 综合很多语言的优点：它的路径表达式参考了x p a n l ，变量 绑定借鉴了x m l - g l ，f l w r ( f o r ，l e t , w h e r ea n dr e t u r n ) 表达式类似于s q l ， 而且它还支持用户自己定义函数。q u i l t 不仅可以查询x m l 数据，也可以 方便地查询关系数据，因此它的表达能力是很强的。 2 2 2 x q u e r y l 0 简介 x q u e r y l 0 是一个功能性语言，它的各种表达式之间可以相互嵌套；它 又是一个强类型化的语言，所有的操作、表达式和函数都必须有一定的类 型；和x m l 一样，它也是大小写敏感的，所有的关键字都必须小写。 x m l 数据具有树状结构，因此在x q u e r y l 0 查询中，路径表达式起着 非常关键的作用。x q u e r y l 0 的路径表达式的表达能力非常强。 x q u e r y l 0 提供f l w r ( 发音同f l o w e r ) 表达式用于迭代运算和将变量绑 定到中间结果上。这个表达式也经常用于实现多个文档之间的联接操作和 查询结果重构。f l w r 代表关键字f o r ，l e t ，w h e r e 和r e t u r n ，即表达式中的 四个子句，它们的含义如下。 ( 1 ) f o r 子句将一个或多个交量关联到表达式( 通常是路径表达式) 上； ( 2 ) l e t 子句将变量直接绑定到整个表达式上； o ) w h e r e 子句用作缸子句和l e t 子句创建的变量绑定元组的过滤器； ( 4 ) r e t u r n 子句包含用于构造f l w r 表达式结果的表达式。 x q u e r y l 0 是在综合先前多种查询语言优点的基础上提出的，它在表达 能力、灵活性和易用性等方面具有显著的优势，已被越来越多的研究人员 所接受，因此很可能成为w 3 c 的正式标准。目前，w 3 c 仍在不断的完善 该语言，一方面提供更强大的表达能力，另一方面进一步精确语义，使之 能够更全面的满足用户的需求。 2 3 无环数据库模式 无环数据库模式设计是数据库理论与图论相结合而产生的一个新的研 究领域，是数据依赖与数据规范化理论研究中由于数据语义的多样性而产 燕山大学工学硕士学位论文 生的一个复杂的数据库设计问题。这一研究不仅具有理论价值，而且能够 指导数据设计的实践，是