（计算机应用技术专业论文）基于语义的xml模式到关系模式的转换.pdf

摘要 可扩展标记语言x m l 技术自出现以来，在许多领域内得到广泛 的支持并有着广阔的应用前景。x m l 的核心作用体现于数据的交换 与共享。利用l 的样式语言来实现数据间的转换和显示，可以满 足用户的多种需求。由于x m l 的诸多优势并没有表现在存储上，如 何更为有效地存储和管理x m l 数据已成为一个研究热点。 本文基于x m l 文档中的映射规则，从保持语义约束的角度考虑， 展开对l 模式规范化存储的研究，包括：对l 文档用映射语 言进行描述；基于映射规则对应的表树探讨一种生成键的方法；基于 x m l 键和函数依赖之间的关系讨论简化键和简化函数依赖的定义， 以及键向简化函数依赖的转换等；讨论l 模式到关系模式的转换， 给出一种基于x m l 键的转换算法，把泛关系模式保持函数依赖且无 损连接地分解为3 n f 模式集，使得到的关系模式合理化。 本文的主要研究成果如下： ( 1 ) 参考已有的l 映射规则定义，给出) a l 文档的泛关系 定义和相应的映射规则。 ( 2 ) 提出基于x m l 文档的有效生成键的智能拓展算法：事先 给出标识键文件，该文件存放可预知的能唯一标识其他数据的键字符 串，在算法运行过程中能动态更新，然后基于映射规则对应的表树， 得到完备的x m l 键集，并给出算法分析和证明。 ( 3 ) 提出一种新的l 模式到关系模式的转换方法，该方法 不需要给定文档类型定义( d o c u m e n t 聊ed e s c r i p t i o n ，d t d ) ，先将 x m l 键集转换为简化函数依赖集，减少属性结点的冗余，然后保持 函数依赖的把泛关系分解为关系范式，使得到的关系模式中的关系表 及其属性合理化。从理论和实验的角度，验证算法的有效性。 关键词：x m l ，关系数据库，转换方法，x m l 键，函数依赖 i a b st r a c t e x t e n s i b l em a r k u p1 a n g u a g ex m lt e c h n 0 1 0 9 yh a sb e e nw i d e l y s u p p o r t e di nm a n yd o m a i n sa n dh a sh a db r i g h tp r o s p e c to fb r o a d a p p l i c a t i o ns i n c ei t sa p p e a r a n c e t h ek e yr 0 1 eo fx m l1 i e si n t h ed a t ae x c h a n g ea n ds h a r i n g u s i n gt h ex m ls t y l e1 a n g u a g et o r e a li z e t h ed a t at r a n s l a t i o na n dm a n i f e s t a t i o nc a ns a t i s f y v a r i o u sk i n d so fu s e r s d e m a n d s s i n c e m a n y o fx m l s a d v a n t a g e sc o u l dn o tb ef o u n di nm e m o r y ，h o wt os t o r ea n dm a n a g e t h ex m ld a t ae f f e c ti v e l yh a sb e c o m eah o tr e s e a r c hs u b j e c t b a s e do nt h ex m ld o c u m e n t sm a p p i n gr u l e s ，t h i sp a p e rd i d r e s e a r c hi n t on o r m a liz e ds t o r a g eo f x m ls c h e m af r o mt h e p e r s p e c t i v eo fk e e p i n gs e m a n t i cc o n s t r a i n t s i ti n c l u d e s ： d e s c r i p t i o no ft h ex m ld o c u m e n ti nm a p p i n gr u l e s ： d i s c u s s i o n o fan e wm e t h o do fg e n e r a t i n gx m lk e yb a s e do nt a b l et r e ef r o m m a p p i n gr u l e s ：d i s c u s s i o no ft h ed e f i n i t i o no fb o t hs i m p li f i e d k e y sa n ds i m p l i f i e df u n c t i o n a ld e p e n d e n c i e sa n do ft h e t r a n s l a t i o nf r o mk e y st os i m p l i f i e df u n c t i o n a ld e p e n d e n c i e s b a s e do nt h ec o n n e c ti o nb e t w e e nx m lk e y sa n df u n c tio n a l d e p e n d e n c i e s ：d i s c u s s i o no ft h et r a n s l a t i o nf r o mx m ls c h e m at o r e l a t i o ns c h e m aa n dp r e s e n t a t i o no fan e wt r a n s l a t i o na l g o r i t h m b a s e do nx m lk e y t h i sa l g o r i t h mc a nk e e pf u n c t i o n a ld e p e n d e n c y a n d1 0 s s l e s sc o n n e c t i o nt od i v i d et h eu n i v e r s a lr e l a t i o ni n t o 3 r dn o r h l a lf o r ms c h e m as e t ，a n di tc a nm a k et h ed e r i v e dr e l a t i o n s c h e m ar e a s o n a b l e t h ec o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： ( 1 ) 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 lm a p p i n gr u l e s ， w e p r e s e n tt h ed e f i n i t i o no ft h eu n i v e r s a lr e l a t i o na n dt h e i i i c o r r e l a t i v em a p p i n gr u l e so nx m ld o c u m e n t ( 2 ) aa l g o r i t h mf o ri n t e l l i g e n te x t e n d i n gt oe f f i c i e n t l y d e r i v i n gx m lk e y sb a s e do nx m ld o c u m e n ti sp r o p o s e d f i r s t l y w ep r e s e n tl a b e lk e yf i1 ea b l et os t o r eal o to fk e yc h a r a c t e r s t r i n g sw h i c hc a nf o r e s e e a b l ya n de x c l u s i v e l ym a r kt h eo t h e r d a t a ，a n di t i sd y n a m i c a l l yu p d a t e di nt h ea l g o r i t h mr u n n i n g t h e nt h ea l g o r i t h md e r i v e st h ek e ys e tf r o mt h et a b l et r e eo f m a p p i n gr u l e s ， a n dp r e s e n tt h ea n a l y s i sa n dp r o o fo ft h i s a l g o r i t h m ( 3 ) an e wn o r m a l i z e dt r a n s l a t i o nm e t h o di sp r o p o s e df o r t r a n s l a t i n gx m ls c h e m at or e l a t i o n a ls c h e m a ， w i t h o u tt h ed t d ( d o c u m e n tt y p ed e s c r i p t i o n ) f i r s t l yx m lk e ys e ti st r a n s l a t e d i n t os i m p l i f i e df u n c t i o n a ld e p e n d e n c i e s ，w h i c hc a nr e d u c et h e r e d u n d a n c vo fa t t r i b u t en o d e s d i v i d et h eu n i v e r s a lr e l a t i o n i n t or e l a t i o n a ln o r m a l f o r mw h i l e k e e p i n g f u n c t i o n a l d e p e n d e n c y ，a n de n s u r et h er e l a t i o n a lt a b l ea n di t sa t t r i b u t e s o ft h ed e r i v e dr e l a t i o n a ls c h e m ar e a s o n a b l e t h em e t h o dh a s b e e np r o v e dt ob ev a li df r o mt h ev i e wo ft h e o r ya n de x p e r i m e n t k e yw o r d s ：x m l ， r e l a t i o n a ld a t a b a s e ，t r a n s l a t i o nm e t h o d ，x m l k e y ， f u n ctio n a l d e p e n d e n c 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：始 刁年月，r 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密嘭 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 翻要 u 酬嘭镩 |1 日期：劢多年石月，日 日期：伽每年6 月f r 日 6 1 基于语义的xml 模式到关系模式的转换 1 1 问题的提出 1 绪论 上世纪9 0 年代以来，随着计算机网络的发展，作为全球最大的 网络i n t 咖e t ，已经成为信息发布和获取的平台，任何人都可以在 i n t e m e t 上发布和获取数据。而在i n t e m e t 里，w r e b 又充当着主要的角 色，其丰富的信息资源给人们的学习和生活带来了极大的便利，特别 是超文本标记语言( h y p e n e x tm a r k u pl a n g u a g e ，h t m l ) 的出现， 它以简单易学、灵活通用的特性，使人们发布、检索、交流信息都变 得非常简单，从而使w - e b 成了最大的环球信息资源库。 然而，随着i n t e m e t 的迅速发展，网站和静态h t m l 页面也急剧 膨胀，信息的数量级从9 0 年代初的m b 过渡到g b 、现在己上升到 t b 【1 1 。 面对庞大的信息海洋，人们却遇到了w r e b 上的两大问题：一是 i n t e m e t 的速度问题，二是虽然可以在线获得各种信息，但是要找到 所需要的信息常常极为困难。其中虽然有硬件方面的原因，但是主要 是由目前的w 曲语言h t m l 所引起的。 w r e b 上数据的增多，h t m l 存在的缺点就变得不可忽略。万维 网联合组织( w o r l d 晰d ew r e bc o n s o r t i u m ，w 3 c ) 提供了h t m l 的 几个扩展来解决这些问题。最后，w 3 c 的成员认识到随着w r e b 的发 展，必须有一种方法能够把数据和它的显示分离开来，决定开发一个 新的标准通用化标记语言( s t a n d a r dg e n e r a l i z e dm a 曲pl a n g u a g e ， s g m l ) 的简化子集，称为可扩展标记语言【2 】( e x t e n s i b l em a r 】b p l a n g u a g e ，l ) ，这样就导致了l 的诞生。1 9 9 6 年，w 3 c 开 始对h t m l 的后续语言进行研究，并于1 9 9 8 年2 月正式完成了可扩 展标记语言( l ) 标准的制定。 x m l 作为i n t e m e t 上数据表示和交换的标准，与h t m l 不同， 它具有自描述、半结构的特点，更加适合机器理解；而h t m l 则注 硕士学位论文 重对数据外观的表示，更加适合人的理解。x m l 是对h t m l 的一个 有益的补充【3 】。x m l 作为一种半结构化数据的表示模型，从提出到 现在只不过几年的时间，但它作为一种跨产品、跨界面、跨平台的互 联网的标准语言，己经显现出其强大的应用前景，并受到了政府、企 业和各大软件厂商的广泛关注。随着x m l 数据的增多，相关行业标 准的制定，人们也开始越来越多地希望以对待数据库的方式来处置和 管理x m l 文档。 由于x l l 作为i m e m e t 上数据标准的出现，有关x m l 数据的研 究也逐渐成为热点。在l 键【4 】出现之前，因为缺乏对l 文档 约束关系的描述，大多数存储方法都是一个从w ，e b 世界到机器世界 直接的转换过程，仅仅考虑到如何完整的保留x m l 文档中的结构信 息，而忽略了它语义约束的保持。这样必将对后来的数据处理带来很 大的麻烦，因为这样生成的数据库可能存在着插入、删除和更新异常。 为了避免这些异常的出现，就必须使得到的数据库模式保持一定的语 义约束信息。随着x m l 语义约束的发展，在存储x m l 数据时考虑 x m l 的语义约束成为研究的重点。 本文的规范化存储模式研究就是在这一背景下，基于语义约束 l 键提出的。在数据库领域中，规范化是模式设计的基础，它是 评价一个模式好坏的主要依据。在研究l 到关系数据库的存储中， 希望将x m l 数据转换成某种关系范式以利用成熟的数据库技术。目 前x l l 己经成为i n t e m e t 上的数据表示和数据交换的标准，需要通 过i n t e m e t 交换和处理的x m l 数据会大大的增加。对于x m l 数据库 模式的深入研究将有力地促进企业的信息化、电子商务以及电子政务 的发展，因此具有巨大的应用前景和经济效益。 1 2 研究目的和意义 x m l 已逐步成为在w e b 上数据表示以及应用间数据交换的标 准，并成为多种数据和文档的理想格式。但是，现今许多数据仍然存 2 基于语义的xml 模式到关系模式的转换 储于关系数据库中。相对订l ，关系数据库的优势在于：技术成熟、 应用广泛；数据管理能力强( 包括存贮、检索、修改等) ；数据安全 程度高；稳定可靠的并发访问机制等。由于l 缺乏象关系数据库 这样的有效的数据管理手段，x m l 尚不能代替关系数据库。但是 v i l 在异构数据交换方面具有很大优势，因此，用关系数据库存储 x m l 数据是一种理想且经济的选择，这在数据库领域内得到广泛的 认同【5 。 根据这种需求，研究实现x m l 转换成关系模式的系统，是一个 应用方向十分重要，应用领域十分广阔的系统。实现从x m l 文档到 关系数据库数据的转换，可以更好的管理订l 数据。虽然x m l 文 档有很多优点，但是当文档很大时不但不好管理而且不易查询。所以 l 数据转化为关系数据库的数据后，就可以充分的利用关系数据 库的成熟技术进行各种处理【7 】。当得到的关系模式为某种关系范式 时，能优化关系数据库的存储和查询效率。 由于数据语义约束信息在提取、映射、转换等方面的困难，现有 的关于x m l 与关系数据库之间的转换研究大多是基于简单的映射方 法，这种映射仅保持了结构信息，只注重数据结构的正确转换，忽略 了语义上的约束保持，往往在转换过程中产生大量的冗余，或丢失了 语义，最终还要对得到的关系模式进行规范化，大大浪费了时间和资 源。同时在保持语义约束的转换方法中，往往是预先给定语义约束信 息，这样结果的好坏易受给定信息的影响。 本文提出一种新的x i l 模式到关系范式的转换方法，可以根据 给出的订l 数据生成完备的键集，并通过将键集转换为简化函数依 赖来建立关系表，最终得到的关系模式符合3 范式，保证了数据的完 整性和一致性。 1 3 国内外研究现状 近来，基于关系的l 数据处理技术受到了研究者和数据库厂 硕士学位论文 商的关注，在这方面已经有了许多工作和成果。在文献 8 】中，t i a n 等比较和分析了5 种x m l 的不同存储方式，包括文件系统，关系存 储和基于对象的存储系统等。他们的研究结果表明，在处理x m l 数 据的性能中，基于关系的存储方法具有最好的性能。 在国外，l 与r d b 的相关技术已经引起了从高校科研院所到 商业数据库公司，从政府部门到自由撰稿人的广泛关注，其中具有代 表的有美国s t a n f o r d 大学的l o r e 项目【9 】、威斯康星大学麦迪逊分 校的n i a g a r a 【10 1 ，法国国家信息与自动化研究所的a g o r a 项目【1 1 】，还 有加拿大多伦多大学的t o x 项目【1 2 】等等。相比之下，国内相关研究 则起始于新世纪之初，其中有复旦大学对基于关系的半结构化数据存 储与检索、半结构化数据模型的增量维护、查询语言及其s q l 转换、 基于关系数据库的x m l 文件系统进行了较为深入的研究【l3 】；国防科 技大学在l 的数据库存储【1 4 】、西安交通大学在用删l 表示关系 数据【15 】等技术分别进行了研究。 现有的x m l 与数据库技术结合的研究中，x m l 数据管理系统 大致分为三类：n a t i v e ( 原生) 方式、e n a b l e d ( 支持) 方式和m i x e d ( 混合) 方式。原生方式下，l 文档作为数据库的存储单元进行 操作和管理，己经有一些研究机构开发出此类原生x m l 数据管理系 统，如d b x m l 16 1 、t a m i n o 【1 7 1 和t i m b d l 8 】等。但是原生l 数据管 理系统至今还没有形成一个固定的模式规范，所以对原生x m l 数据 管理系统而言，当务之急是建立统一的标准，以便于未来发展的需要。 支持x m l 的数据管理系统凭借传统数据库系统的成熟技术，提供完 善的功能，结合x m l 数据的特点设计x m l 存储、查询功能。混合 方式是以上两种方法的结合，有利于操作的灵活性，但是增加了保持 一致性的难度。 当前对x m l 存储支持得较好的关系数据库主要有o r a c l e 【l 明、 m i c r o s o rs q ls e r v e 一2 0 1 和i b md b 2 【2 0 】，提供的解决方案有其各自的 优点和不足。也有一些第三方提供的中间件支持x m l 在关系数据库 中的存储，比较著名的有x m l d b m s 等。此外，用户也可以自己编 4 基丁语义的x m l 模式到关系模式的转换 写专用的应用程序处理x m l 和关系数据库之间的数据交换。但是这 些方案存在一些不足之处，表现在： 采用某种关系数据库提供的对x m l 的支持处理比较简单，最大 的缺陷在于其解决方案和具体关系数据库平台相关。不同数据库厂商 提供的解决方案无法运用到其它厂商的平台上，不太适用于集成了多 种操作系统和关系数据库平台的应用领域。采用中间件的方式，即在 各种已有关系数据库的平台上加挂一个中间层，处理) ( i l 和数据库 的数据交换，这是一种比较好的解决方案，但目前很多中间件的功能 并不完备j 对x m l 相关标准的支持不很理想。专用应用程序的转换 效果虽好，但处理过程复杂繁琐，与特定的l 文档结构相关，通 用性不好，而且程序界面不够友好，使用起来不方便。 用关系数据库存储x m l 数据存在多种不同的方法。目前大多数 x m l 模式到关系模式的转换基于d t d ，并希望保持一定的语义。文 献 5 提出了一个管理x m l 文档的x 2 r 系统，该系统在提供键约束 的同时通过对结点进行编号和分类将d t d 转换为关系模式。由于这 个系统必须要有d t d 的支持，当不能成功获得d t d 或相应的x m l 模式时，系统就变得不那么有效。文献 2 1 是先分析d t d 中存在的 部分函数依赖形式和传递函数依赖形式，分别利用提升规则和创建新 结点规则进行d t d 的规范化，再转换为满足b c n f 的关系模式，过 程烦琐且不能保证d t d 的规范性。文献【6 的映射转换算法是将关系 模式中的表分为对象表和关系表两种，首先对d t d 树模型按层次结 构划分转换得到对象表，再针对每一条函数依赖描述的关系生成关系 表，虽然该算法得到的关系模式满足b c n f ，但是表的数量和重复的 属性非常多，存在大量的冗余。文献 2 2 】首先把l 文档映射为泛 关系模式，再利用算法d e r i v e f d s 推导出) ( m l 键所蕴含的泛关系模 式上函数依赖集的规范覆盖，最后将泛关系模式保持函数依赖地分解 为3 n f 模式集。该方法是独立于d t d 的，但d e r i v e f d s 算法的时间 复杂度为指数级。文献 6 和文献 2 2 】得到的关系模式虽然满足了关系 模式的规范化，但是转换过程不满足无损分解，并且需事先给定x 1 l 硕+ 学位论文 键集。 国内外对于x m l 模式转换为关系模式的研究工作更多的侧重于 具体的转换实现，但是对于基于语义转换中的预备工作，l 键集 生成的研究甚少，基本上均是对给定的语义信息来进行相应的转换操 作。l 模式中的约束主要是通过语义约束来实现的，而关系中约 束的主要概念是键。x l 键作为x m l 模式中的语义约束，可以唯 一标识x m l 文档中的一些结点，而保持x m l 键约束的存储模式既 能保持l 文档内容和结构信息，又能保持l 上存在的语义约 束，并大大减少存储冗余。因此完备的x m l 键集对转换后得到规范 化的关系模式是非常重要的。文献 2 3 给出了寻找l 键算法 ( s e a r c h k e y a l g o r i t h m ，s k a ) ，它基于d t d ，通过扫描d t d 中的结 点，将该结点中子结点为叶子的结点存入一个数组中，判断其中的叶 结点是否唯一确定该结点从而得到键路径。该算法每次判断均需扫描 x i l 树，在x m l 文档数据较大时，生成键集的计算时间较高。 1 4 主要工作和成果 本文基于) ( 1 l 文档中的映射规则，从数据库设计的角度考虑， 展开对l 模式规范化存储的研究，包括：对x m l 文档用映射语 言进行描述；基于映射规则对应的表树探讨一种生成键的方法；基于 x m l 键和函数依赖之间的关系讨论简化键和简化函数依赖的定义， 以及键向简化函数依赖的转换等；讨论x m l 模式与关系模式的转 换，给出一种基于x m l 键的转换算法，把泛关系模式保持函数依赖 且无损连接的分解为3 n f 模式集，使得到的关系模式更加合理。 本文的主要研究成果如下： 参考已有的x 1 l 映射规则定义，给出x m l 文档的泛关系定义和 相应的映射规则。 提出基于x m l 文档的有效生成键的智能拓展算法：事先给出标 识键文件，该文件存放可预知的能唯一标识其他数据的键字符串， 6 基于语义的xml 模式到关系模式的转换 在算法运行过程中能动态更新，然后基于映射规则对应的表树， 得到完备的x m l 键集，最后给出算法分析和证明。 提出一种新的x m i 模式到关系模式的转换方法，该方法不需要 给定d t d ，基于本文生成的l 键集，通过将其转换为简化函 数依赖集，减少属性节点的冗余，使得到的关系模式中的关系表 及其属性合理化。 1 5 本文的结构 本文共分五章。 第一章是绪论，介绍了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 模式到关系范式的转换，本章是全文 的重点章节。在本章中，提出了一种新的转换方法，并对这种方法进 行了详细的分析和阐述，给出了相应的转换算法，从理论上论证了转 换的可行性，并通过仿真实验对其进行应用； 最后是结语，对本文的研究工作进行了总结，并指出了进一步的 研究方向。 7 基于语义的xml 模式到关系模式的转换 2 1 引言 2 x ，语言 本章从x m l 基础知识出发，形式化的描述了x m l 文档树、路 径表达式等基本定义，并进一步定义了x m l 键、函数依赖等概念， 为后面章节中的讨论作符号上的准备。为了便于x m l 数据库模式规 范化的研究，本章从文献中引用来的定义和符号做了形式化上的统一 描述。 2 2 x m l 特点与语法规则 l 是w 3 c 于1 9 9 8 年2 月发布的一种标准，是s g m l 的一个 简化集。它继承了s g m l 的强大功能，去除了繁琐的定义，弥补了 h t m l 作为网络标准语言的不足。 现在，) ( 】l 之所以深受软件开发商的支持和程序开发人员的厚 爱，主要具有以下特点： ( 1 ) l 是自描述的。有相应的模式如：x m ls c h e m a ，提供 对合法文档的内容模型、元素、属性等的完整描述，数据可以根据模 式导入文档处理器。允许根据各个领域不同需要，开发本领域特定的 标记语言，方便该领域内的工作人员共享数据和信息。 ( 2 ) x 】l 是半结构化的。x m l 没有固定的标签集合，而是提 供了一种通用灵活的语法机制，用文本格式文件记录数据和数据之间 的层次关系。同时它又具有规范和严格的文档语法，每个x m l 文档 有且仅有一个根元素，该元素下有文本数据或子元素，子元素可以有 自己的子元素或文本数据。 ( 3 ) 订l 是开放的。x m l 规范是由w 3 c 制定的，完全开放。 不同组织开发的v i l 文件格式对于其他人或应用程序都是可读的。 这使它成为在不同应用之间交换数据的理想格式。 ( 4 ) x m l 数据内容与显示方式分离。x m l 把显示格式从数据 9 硕士学位论文 内容中独立出来，保存在样式单文件( s t y l e s h e e t ) 中，如需改变文 档显示方式只需修改样式单文件即可，与文档本身无关。 ( 5 ) x m l 支持高级搜索。v i l 的自描述性能很好地表现复杂 的数据关系，能记录文档内容的结构和含义，因此基于l 的应用 程序可以在x m l 文件中准确高效地搜索相关数据内容，忽略不相关 的部分，形成较为精确的搜索机制。 l 文档需遵守l 语法的一般规则，比如： ( 1 ) x m l 文档包含一个或多个元素，必须有且只有一个根元素， 它不出现在其他任何元素的内容中。 ( 2 ) 每个元素必须有起始和结束标记。 ( 3 ) 正确地格式化空元素。 ( 4 ) 开始标记和结束标记可以大写或小写，但它们必须配对。 ( 5 ) 元素必须正确地嵌套，如果起始标签在另一个元素的内容 中，则其结束标签也在同一元素的内容中。 ( 6 ) 属性值必须用引号括起来。 以下给出一个具体的关于书信息的x m l 文档。 n e t w o r l ( s l a n yp e t e r s o n f o u n d a t i o n t c p i p a t m 1 0 基于语义的xml 模式到关系模式的转换 a p p l i c a t i o n s a p p l i c a t i o n s 2 3 x m l 树 x 1 l 文档是一种层次结构，它可以被看作是一棵树【2 4 】。由上一 节所给出的l 文档为例，其树模型如图2 1 所示。 从图2 1 可知，一棵x m l 树中有三类结点： 元素结点( e l e m e n tn o d e ，e 结点) ：每个元素结点有一个标签 ( t a g ) ，但没有文本值。比如，图中的根结点是一个元素结点，它有 一个标签d b 。在此把所有元素结点的标签组成一个集合，用e 表示。 在图2 一l 中e = d b ，b o o k ，t i t l e ，a u t h o r ，c h 印t e r ，s e c t i o n ，n a m e ； 属性结点( 甜r i b u t en o d e ，a 结点) ：每个属性结点有一个标签， 也有文本值。比如，图2 1 中的第一本书的i s b n 号所对应的结点n 3 就是一个属性结点，它有一个标签i s b n ，且它的值为“7 1 11 0 7 5 2 6 9 ”。 把所有属性结点的标签组成一个集合，用a 表示。在图2 1 中 硕士学位论文 a = i s b n ，n u m b e r ； 图2 一lx m l 树 文本结点( t e x tn o d e ，s 结点) ：每个文本结点没有标签，只有文 本值，其实它对应的是p c d a t a 。比如，图2 1 中第一本书的书名所 对应的结点n 5 就是一个文本结点，它没有标签，但它的值为 “n e t w o r k s 。由于文本结点没有标签，假设其标签为s ，并用集合 s 表示文本结点的标签集合。 定义2 1 ( x m l 树) ：一棵x m l 树t 可以定义成一个七元组 t = ( v l a b ，e l e ，a t t ，v a l ，i d ，r o o t ) ，其中： 串v 代表有限的结点集； 串l a b 是一个函数，它将返回一个结点v 的标签。如果l a b ( v ) e ， 则v 是元素结点；如果l a b ( v ) a ，则v 是属性结点；如果l a b ( v ) s ， 则v 是文本结点； 宰e l e 是一个偏函数。如果v 是元素结点，则e l e ( v ) 返回v 所有元 素和文本孩子组成的序列，即e l e ( v ) = e i ，e n 】，其中e l ，e n 都是元素 结点或是文本结点，且都是v 的孩子。由于元素结点和文本结点是考 虑次序的，所以e l e ( v ) 是有次序的；如果v 不是元素结点，则e l e 没 有定义； 毒a t t 是一个偏函数。如果v 是元素结点，则a t t ( v ) 返回v 所有属 1 2 基于语义的xml 模式到关系模式的转换 性孩子组成的集合，即a t t ( v ) = a l ，a m ) ，其中a l ，a m 都是属性结点， 且都是v 的孩子。由于属性结点不考虑次序，所以a t t ( v ) 是一个集合， 里面的元素没有先后次序；如果v 不是元素结点，则a t t 没有定义； 宰v a l 是一个偏函数。如果v 是元素结点，则v a l 没有定义；如果 v 是属性结点或是文本结点，则v a l ( v ) 返回它的文本值； 木i d 给树中的每个结点指定一个唯一的标识，类似i d 一样，i d 在整个x 1 l 文档中必须是唯一的； 木r o o t 代表树的根，且有r o o t v 。用r 来代表根结点的标签，即 l a b ( r o o t ) - r 。 例如，在图2 1 中，v = n 1 ，n 3 7 ，它是包括树中所有结点的集 合。对于图中对应第一本书的结点n 2 而言，有1 a b ( n 2 ) - b o o k e ， 此 时也说明n 2 是一个元素结点；对于n 3 ，有l a b ( n 3 ) = i s b n a ，说明n 3 是一个属性结点；对于n 5 ，由于有l a b ( n 5 ) = s ，故其是一个文本结点。 对于某个元素结点n 2 ，有e l e ( n 2 ) = h ，n 6 ，n 8 ，n 2 0 】，其中的结点是有 次序的，互相之间不能打乱；a t t ( n 2 ) ： n 3 。 对于某个属性结点n 3 ，有v a l ( n 3 ) = “7 1 11 0 7 5 2 6 9 ”；对于某个文 本结点n 5 ，有v a l ( n 5 ) = “n e t w o r k s ”；而对于元素结点，v a l 函数没有 定义。 对于函数i d ，可以人为地为每一个结点设置一个标识号，比如对 于结点n i ( i - 1 ，3 7 ) ，可以定义i d ( n 沪i 。 最后树的根为n l ，即r o o t n l ，且r = d b 。 定义2 2 ( 值相等) ：一棵x m l 树中两个结点v l 和v 2 是值相等 的，用v l = v v 2 来表示，当且仅当下列条件成立： ( 1 ) l a b ( v 1 ) = l a b ( v 2 ) ； ( 2 ) 如果v l 、v 2 是属性结点或者是文本结点，则要求 v a l ( v 1 ) = v a l ( v 2 ) ； ( 3 ) 如果v 1 、v 2 是元素结点，则对任何a i a t t ( v 1 ) ，要求存在 弛a t t ( v 2 ) ，使得a i = v a i ，反之亦然；对e l e ( v 1 ) = e l l ，e l n 】， e l e ( v 2 ) = 娩l ，e 2 n 】，要求有e l i - v e 2 i ，其中i - 1 ，n 。 硕士学位论文 例如，在图2 1 中的两个结点n 9 和n 3 l ，由于它们都是属性结点， 1 a b ( n 9 ) = l a b ( n 3 i ) = n u m b e r 而且v a l ( n 9 ) = v a l ( n 3 1 ) = “l ，因此有n 9 _ vn 3 l 。 同理，对两个文本结点n 5 和n 2 7 ，有n 5 - v n 2 7 。 与值相等的概念相对应地，如果有两个结点v 。和v 2 ，它们实际 上都是表示同一个结点，那么就说v l 和v 2 是相等的，记为v l _ v 2 。可 以这么说，在一棵x m l 树中如果v l = v 2 当且仅当i d ( v 1 ) = i d ( v 2 ) 。 2 4 路径语言 路径表达式语法 p l 。 p ：= 占l1 p p l p ：= 占i1lp pi 术 图2 2 路径表达式的语法 在文献 4 中定义了书写x m l 键中的路径表达式的路径语言，有 两种路径表达式：一种是简单路径表达式，用p l 。表示；另一种是正 则路径表达式，用p l 表示。它们的语法描述如图2 2 所示。其中， l e u a u s ，是一个结点的标签；占代表空路径；“ 是一个二元 操作符，它代表两个路径表达式的连接；“可以匹配任意标签；“秽 表示是e e n e 闭包，两者的组合“水 可以匹配任意路径。 一个简单路径表达式p l s 指用一些标签所组成的序列，其中不带 任何通配符和k l e e n e 闭包。由简单路径表达式定义的路径为简单路 径，比如在图2 1 中，d b b o o k c h a p t e r n a m e 就是一个简单路径。 一个正则路径表达式p 可能包含“妒，其中的“秽就可以匹 配任意路径。由正则路径表达式定义的路径为正则路径，比如在图 2 1 中，d b b o o k 宰n a m e 就是一个正则路径。特别地，一个简单路径 也可以被看作是一个正则路径。 如果p 是一个合法的简单路径，当且仅当对p 中的任意标签l ， 如果l a u s ，则l 必是p 的最后一个标签。类似地，可以定义合法 的正则路径。在以下的内容，仅考虑合法的路径。 1 4 基于语义的xml 模式到关系模式的转换 包含关系：实际上，一个正则路径表达式定义的是一个简单路径 的集合。用p p 表示p 属于由正则路径表达式p 定义的集合。例如， d b b 0 0 k c h a p t e r n 锄e d b b o o k 木n 锄e 。极端地， d b b o o k c h a p t e r n a m e d b b o o kc _ h a p t 既n 锄e 。 可达性：在一个x m l 树t 中一个结点v 2 可以由结点v l 经过简 单路径p 可达，用t i _ p ( v l ，v 2 ) ，当且仅当( 1 ) 如果p = g ，则v l 巩； ( 2 ) 如果夕= p 1 ，则在t 中存在一个结点v ，使得t i _ p ( v l ，v ) ，且 v 2 是v 的一个孩子，它的标签是l 。 举例而言，在图2 1 中，结点n 8 可以由结点n 1 经过简单路径 d b b o o k c h 印t e r 可达，而结点n 1 6 却不能由结点n l 经过简单路径 d b b o o k c h 印t e r 可达。 类似地，在一个x m l 树t 中一个结点v 2 可以由结点v 1 经过正 则路径p 可达，用t l = p ( v l ，v 2 ) ，当且仅当存在一个简单路径p p ， 使得t 1 p ( v l ，v 2 ) 。 比如，也可以说，结点n 8 可以由结点n l 经过正则路径木c h a p t e r 可达。 结点集：设v 是t 中的一个结点，用v ( p 】表示在树t 中，从v 开始，经过路径p 可达的所有结点的集合，即v p 】= y lt i - p “y ) ) 。 类似地，可以定义v p 】= it l = p ( v ，v ) ) 。 例如，假设p - b o o k c h a p t e r ，p = o n a m e ，那么n 2 【p 】= n 8 ，n 2 0 ， 而n 2 【 p 】= n l o ，n 1 4 ，n 1 8 ，n 2 2 。 值交集：设v 。【p 】，v 2 p 】为两个结点集，它们的值交集 v 1 p n v v 2 【p 定义为： h p 】n v1 ，2 【 尸】= ( z ，z ) i j p p ，z ，l p 】，z 7 屹【p 】，z = vz 。 实际上，它们的值交集是一个集合，里面的元素是一些结点对。 对一个结点对( z ，z 7 ) 来说，两个结点的值相等，而且它们是分别从v l 和v 2 开始，经过同一条简单路径p 可达，这里p p