（计算机应用技术专业论文）关系数据库中存储和查询xml文档的设计与实现.pdf

天津师范大学硕士学位论文 摘要 x m l 迅速的成为i n t e r n e t 上用于数据表示和数据交换的标准。x m l 文档大量 涌现，x m l 的有效管理受到广泛关注。为了结合数据库发展的需要，我们研究了 在关系数据库中存储和查询x m l 文档的技术。 根据x m l 查询以路径表达式为主体的特点，我们提出了一种在关系数据库 中存储x m l 文档的方法，这种方法是基于x p a t h 数据模型的，并对x m l 文档的元 素进行d i e t z 编码来标识元素，同时在数据库中存储每个元素及其父元素的 d i e t z 编码来保持元素之阃的父子关系以及用于将关系数据转化为) 强也文档或文 档片段。使用该方法我们开发出了一个中问件，将其命名为x r - s y s t e m 。 x r - s y s t e m 将x m l 文档分为三个关系表进行存储，这些表是e l e m e n t 、a t t r i b u t e 、 t e x t ，分别用来存储x m l 文档的元素、属性和文本。 基于这种存储方法，我们研究了如何实现将x m l 查询转化为s o l 的查询转换 问题，转换分为三个步骤：首先根据x p a t h 表达式产生x m l 查询图；然后，将这 个查询图根据定位步分解为若干个子图，通过使用基于d i e t z 编码的x p a t h 快速 定位方法得到这些子图所代表的定位步测试结点所对应的元素d i e t z 编码集合； 最后，再根据d i e t z 编码的x p a t h 快速定位方法由上一步骤得到的d i e t z 编码集 合产生s o l 。 整个中间件的设计分为三个组成部分，分别是x m l 存储模块，查询转换模块 和数据格式转换模块。在中间件的实现上采取分层的策略，分为基本组件层，用 户界面层，业务逻辑层和数据访问层。我们利用j d 伽作为x m l 解析器使用j a v a 实现了该中间件。 关键字：x m lx p a t h 关系数据库中问件d i e t z 编码 天津师范大学硬士学位论文 a b s t r a c t x m li sq u i c h y b e c o m i n gt h es t a n d a r df o rd a t ap r e s e n t a t i o na n dd a t ae x c h a n g e o v e rt h ei n t e m e t t h i si sc r e a t i n gan o ws e to fd a t am a n a g e m e n tr e q u i r e m e n t s i n v o l v i n gx m l c o m b i n i n gw i t hd a t a b a s ed e v e l o p m e n td e m a n d , w es t u d yt h ex m l s t o r i n ga n dq u e r y i n gt e c h n o l o g yi nr e l a t i o n a ld a t a b a s e a c c o r d i n gt oc o r eo fx m lq u e r yi sp a t he x p r e s s i o n w es u g g e s tax m ls t o r i n g m e t h o di nt d a t i o n a ld a t a b a s e t h i sm e t h o di sb a s eo l lx p a t hd a t am o d e l ，a n d e n c o d e se l e m e n t sb yu s i n gd i e t zm e t h o di no r d e rt oi d e n t i f yd e m e n t s w ea l s on e e d s t o r ed i e t zc o d eo fe v e r yd e m e n ta n di t sp a r e n ti no r d e rt op r e s e r v ep a r e n t - c h i l d r e l a t i o n s h i pb e h 嗍d e m e n t sa n di t 啪b eu s e df o rt r a n s f o r m a t i o nf r o mr e l a t i o n a l d a t ai n t ox m ld o c u m e n to rd o c u m e n tf r a g m e n t b yu s i n gt h i sm e t h o dw ed e v e l o pa m i d d l e w a r eb c t w c e i ix m la n dr e l a t i o n a ld a t a b a s en a m e dx r - s y s t e m x r - s y s t e m s t o r e sx m ld o c t m a e n ti n t ot h r e et a b l e s , t h e y 撇e l e m e n t , a t t r i b u t e 吩a n dt e x lt h e e l e m e n tt a b l es t o l e si n f o r m a t i o na b o u ta nd e m e n t so f ax m ld o c u m e n t , a t t i b u t ea n d t e x t t a b l es t o r e a t t r i b u t e a n d t e x t o f a ) 叫l d o c m n e n t b a s e0 1 1t h i ss t o r i n gm e t h o d , w cd i s c u s sh o wt oi m p l e m e n tq u e r yt r a n s f o r m a t i o n f t o mx m l q u e r y t os q lq u e r y , w h i c hj sc o m p o s e do f t h r s t e p s ：f i r s t , w oc o n s t r u c t x m lq u e r yg r a p ha c c 删i n gt ox p a t he x p r e s s i o n ；s e c o n d , s p l i tx m lq u e r yg r a p h i n t os e v e r a ls u b - q u e r yg r a p h sa c c o r d i n gt ol o c a t i n gs t e p b yu s i n ga c c e l e r a t i n gx p a t h l o c a t i n gs t e pb a s e do nd i e t ze n c o d em e t h o d , w ec 缸g e td i e t zc o d es e t sw h i c ha g o r e l a t e dt ot e s t i n gn o d e si nl o c a t i n gs t e p s t h e s en o d e sa r or e p r e s e n t e db ys u b - q u e r y g r a p h s ；a tl a s t , w eg e n e r a t es q lf r o md i e t zc o d e s e t sb yu s i n ga c c e l e r a t i n gx p a t h l o c a t i n gs t e pb a s e do nd i e 乜e n c o d em e t h o da g a i 几 t h i sm i d d l 创v a r ei sd e s i g n e di n t ot h r e em o d u l e s w h i c h 躺x m ls t o r i n gm o d u l e , q u e r yt r a n s f o r m a t i o nm o d u l e a n dd a t af o r m a tt r a n s f o r m a t i o nm o d u l e i n h n p l e m e n t a t i o nm e t h o d , t h ep r o g r a mi ss p i r e di n t of o u rl a y e r s , t h e ya r c ：b a s i cu t i l i t y l a y e r , u s e ri n t e r f a c el a y e r , b u s i n e 器l o g i cl a y e ra n dd a t aa c c e s sl a y e r w e i m p l e m e n tt h em i d d l e w a r eb yu s i n gj a v a , t a k ea d v a n t a g eo f j d o m a sx m l p a r s e r k e yw o r d s ：x m lx p 舳r d b m sm i d d l e w a r e d i e t ze n c o d em e t h o d n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得鑫鲞塑塾盘堂或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 签名： 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印，缩印或扫描等复制手段保存、汇 编以供查阅和借阅同意学校向国家有关部门或机构送交论文的复印件和磁盘 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 天津师范大学硕士学位论文 第一章引言 1 1 引言 近几年，x m l ( e x t e n s i b l e m a r k u p l 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 查询有效的转化为关系模式下一组等价的s q l 查询，并获得尽可能高的执行效率。 x m l 查询语言有多种，如l o r e l 、x m l - q l ，x s l 、x q l 等。在此基础 上，w 3 c 推出并逐步完善了标准的x m l 查询语言：x p a t h 。x p a t h 的查询体由 一系列定位步构成。这一特性使x p a t h 能灵活检索各种x m l 信息源，但却给 关系模式下x p a t h 的转换造成了困难，因为s q l 无法直接表示x p a t h 的查询结 果。x m l 存储领域中，x p a t h 查询转换是一个相对薄弱的环节，目前尚无很完 善的转换方法。对此，我们进行了深入研究。综合现有的多种x p a t h 转换方法， 我们设计并实践了一个x m l 存储领域里普遍适用的查询转换方案。其关键思 路是通过构造桥梁，将x m l 发布领域中较为成熟的x l a t h 转换方法应用于 x m l 存储领域中本文余下部分将详细阐述该方案。 1 2 国内外相关研究及本文贡献 基于关系数据库存储x m l 文档这个研究领域存在多种技术，基本上可以分 为两大类l q ：一是基于x m l 结构映射的方法；二是基于x m l 模型映射的方法。 对于发布x m l 文档的策略，比较成熟的是x p e r a n t o n 町和s i l k r o u t e n 帕嘲 中闻件 o r a c l e 、m m 和微软等公司也积极的对各自数据库产品进行了扩展以支持 x i i l 存储和发布，分别推出了o r a c l el o g 、m i c r o s o f ts q l s e r v a 2 0 0 5 、d b 29 这些数据库都将x g l 作为内置数据类型，这样x m l 文档就可以直接的存储到关 系表的属性中。 天津师范大学硬士学位论文 本文主要贡献在于：归纳了x m l 存储技术领域和x m l 发布技术领域中已 有的查询转换方法，在此基础上，设计了一套可以广泛适用于x m l 存储领域的 查询转换方案。该方案能够正确高效的转化大部分x p a t h ，但仍存在着一些不足 本文对方案中的不足之处进行了剖析和部分改进，并提出了可能的发展及优化方 向。 1 3 本文主要内容及结构 本文对于如何基于关系型数据库存储x m l 文档和如何将x p a t h 查询转化为 $ q l 这两个研究领域进行了深入的研究，并且提出了一套解决方案。本文的后 序内容组织如下：第二章介绍x m l 的基本概念以及已有的基于关系数据库存储 x m l 文档的方法；第三章详细的介绍了本文所提出的基于d i e t z 编码如何在关 系数据库中存储x m l 文档；第四章介绍了在这种存储方法基础上如何将x p a l h 转化为s q l 的方法；第五章介绍了以u m l 形式对整个系统结构的分析与设计； 第六章介绍了整个系统各个功能模块的实现算法：最后一章介绍的是对本系统的 总结以及未来的研究方向。 2 天津师范大学硕士学位论文 第二章研究背景 2 1x m l 及其相关技术 x m l 是c x t e n s i b l em a r k u pl a n g u a g e ( 可扩展标记语言) 的缩写，它是由 w 3 c 组织于1 9 9 8 年2 月创建的一组规范“1 。与h 蹦l 一样，x g l 也源自s g m l ( s t a n d a r dg e n e r a l i z em a r k u pl a n g u a g e 通用标记语言) ，但x m l 却有着h t m l 语言历欠缺的巨大伸缩性与灵活性。它不再像h t m l 样有着一成不变的格式 x m l 实际上是一种定义语言，即使用者可以定义无穷无尽的标记来描述文件中 的任何数据元素，从而突破了h t m l 固定标记集合的约束，使文件的内容更丰 富更复杂，并组成一个完整的信息体系。 x m l 主要有两类作用：一是作为元标记语言，定义各种实例标记语言的标 准；二是作为标准交换语言，担负起描述交换数据的作用。在信息世界中，x m l 扮演着“国际语言”的重要角色是互联网上和企业内交换数据和发布数据的主 要互操作标准 2 1 。1x m l 文档结构 x m l 文档是基于文本格式的，x m l 文档的最基本构成包括x m l 声明，处 理指令和x m l 元素三部分。另外还可以有注解，元素中还可以包含属性或者子 元素等。x m l 声明一般出现在文档开头部分，确认书写文档的语言，并且提供 版本号。元素是文档的主要逻辑部件，它是由开始标签和结束标签界定。属性是 元素的性质，属性表述了元素的开始标签内的信息，在结构上构成了“名一值” 对。处理指令是根据信息给软件应用程序使用的标记，由 字符组界定。 x m l 中的注释以“ ”结束，注释可以出现在文档的任何位 置【1 1 。 另外，一个x m l 文档必须满足两点：良好结构和有效。遵循x m l 语法的 文档叫做良好结构的文档，可以表达一定的语义信息。而一份附带有外部或内部 d t d 或者x m l s c h e m a 的良好结构的x m l 文档，并且x m l 文档本体符合d t d 或者x m ls c h e m a 所声明的文件格式的x m l 文档称为有效的x m l 文档。关于 d t d 和x m ls c h e m a 的内容，在后面的章节中叙述。一个良好结构的x m l 文 档，需要满足以下几项基本原s t i r l 】； 3 天津师范大学硕士学位论文 ( 1 ) 文档以x m l 声明四x m l 啪i o n - ”1 0 ”? 开始； ( 2 ) 有一个包含所有其它内容的根元素； ( 3 ) 所有元素必须合理的嵌套； ( 4 ) 起始标签和结束标签应当匹配：结束标签必不可少，不能像h t m l 里面那 样随便； ( 5 ) 大小写应该一致：x m l 对字母的大小写是敏感的，同时，x m l 不忽略空 格： ( 6 ) 属性必须在单引号或双引号中，在结构上构成了“名值_ 对； ( 7 ) 标签和属性的命名必须是合法的，元素中的属性是不允许重复的： x m l 语言的优秀特点主要体现在以下四个方面： ( 1 ) 简洁性 x m l 文档语法包含一个非常小的规则集，使开发者能立刻开始工作。x m l 严格的定义和规则使得人类和机器都能更容易地阅读文档。x m l 文档建立在基 本嵌套结构的一个核心集的基础之上当一层又一层增加的细节，使结构变得越 来越复杂时，作者或开发者只需要为内部结构的复杂化付出非常少的努力。这些 基本结构可以被用来代表复杂的信息集合，而不需要改变结构自身。x m l 的语 法解析器也非常容易创建。 ( 2 ) 可扩展性和开放性 x m l 可以进行扩展，有一些附加标准可用以向核心的x m l 功能集增加样 式、链接、和参照能力作为一个核心标准，x m l 为可能产生的别的标准提供 了一个坚实的基础。x m l 的标准完全开放的，可以免费获得。x m l 使用的是公 开、非专有格式，允许不同专业开发与自己特定领域有关的标记语言，不受版权、 专利、商业秘密等知识产权的限制。x m l 的开放性决定了它可成为异质系统之 间进行交流的媒介，各系统只要装有x m l 解析工具，便可理解以x m l 为中介 由其它系统传送的信息并加以利用，而不用考虑对方的信息格式或使用特殊的软 件而完成跨平台的交流，这有力地促进了电子商务和w a p 的发展。 ( 3 ) 数据的结构性 x m l 是可扩展的标记语言，这种格式不仅仅能够以统一的格式定义数据， 甚至能够封装与表示数据。这一特点，使x m l 能够在i n t e r n e t 行走，成为数据 4 天津师范大学硕士学位论文 交换的中介者，作为一种中介数据库语言开发数据库，在异种数据之间，异种数 据库之间，提供交换信息的平台。 ( 4 ) 互操作性 x m l 可以在多种平台上使用，而且可以用多种工具进行解释，并且能够与 多种开发语言一起打造不同需求的应用。例如：它能够进行数据的多样化显示， 服务器用同样的x m l 文件来保存数据，但能够针对每个客户端不同的样式表将 x m l 中的数据，各取所需，显示到不同的客户端。因此可以说，x m l 是一种很 好的多层应用的粘合剂。图2 1 是一个x m l 文档的示倒 图2 i 皿。文档示例 5 天津师范大学硕士学位论文 2 1 2 文档类型定义( d t d ) 和x m ls c h e m a 1 、d t d 简介 订l 作为一门标记语言，它就需要一种文档( 即文档类型定义d t d ) 来定 义，d t d 可以看作是一类x m l 文档的模板。它定义了文档的逻辑结构，规定了 x m l 文档中所使用的元素，实体，元素的属性，元素与实体之间的关系。它使 得数据交流与共享得以正常进行，验证了数据的有效性。d t d 可以是一个完全 独立的文件，也可以在) 函几文件中直接设定所以，d t d 分为外部d t d ( 在 订l 文件中调用另外已经编辑好的翻田) 和内部d t d ( 在咀，文件中直接设 定d t d ) 两种田。d t d 具有如下优点：d q d 使得x m l 文档保持一致；d t d 可 以共享；d t d 提供了对沮。语汇的形式化和完整的定义；每个v i l 文档有单 个的d t d 来限制。 ! e l e m e n tp l | b ( k 魄( b o o k i a n i d 球矮t o i p ! a 皿i s ta r t i c l ec d i t o r l d 存d d p l ! d ! e l e m e n ta l l t h o r ( n a l l l e 。e m a i l + p ! e l e m e n t e m a i l ( # p c d a t a 图2 2 图2 1 所示的x m l 文档对应的d t d 2 、x m l s c h e m a 简介 z m ls c h e m a 与d t d 一样，也是对一类x m l 文档进行约束、确定其结构， 元素、属性、及数据类型。及x m l 文档中所使用的元素，实体，元素的属性， 元素与实体之间的关系的约束。x m l s c h e m a 首先由微软提出，已经被、帕c 接 受成为一个标准与d t d 不同的是，x m ls c h e m a 文件使用x m l 语法，它的 设计目的很多跟d t d 相似之处，但在功能、扩展性方面超越了d t d 。以下是它 6 天津师范大学硕士学位论文 们之间的一些区别：x m ls c h e m a 是x m l 文档，不像d t d 有其特有的语法。 对开发人员来说，不需要懂这两种语法就能编写一个格式良好的x m l 文档。对 开发x m l 分析器来说，x m ls c h e m a 由于也是x m l 语法，实现及支持起来就 更方便了。同时x m ls c h e m a 继承了x m l 可扩展的优点。定义数据类型。在一 个d t d 文件中只能把数据声明为字符串类型或字符串类型的子元素，如 p c d a t a 、c d 闻队、i d 等。而在x m ls c h e m a 中，可以定义跟编程语言同样丰 富的数据类型，如整型，浮点型，布尔型，日期型等。这样的好处是显而易见的， 在你编写程序使用一个整型数据时，如用d t d 定义的，就必须将它从字符型转 化为整型，而x m ls c h e m a 贝q 可以直接定义为整型一个x m l 文档只能由一个 d t d 文档来描述，而可以由多个x m ls c h e m a 文档来描述。后者完全支持命名 空间。 2 2 基于关系数据库的x m l 存储技术 x m l 数据模型与传统的关系模型之间存在着较大的区别：( 1 ) 提供数据存 储。关系数据以数据库系统为手段，x m l 以文件系统为手段；( 2 ) 提供对数据 的直接存取访问。两者都不需要用户关心数据的物理结构；( 3 ) 提供数据的模式 描述。x m l 采用d t d ( d o c m n e n t t y p e i ) e f m i t i o n ，文档类型定义) 或x m l s c h e m a ( x m l 规范) 来描述数据的逻辑结构：关系数据通过关系模式来描述数据的逻 辑结构；( 4 ) 提供应用逻辑接1 3 。x m l 采用s a x ( s i m p l e a p i f o r x m l ) 和d o m ( d o c u m e n to b j e c tm o d e l ) 定义应用编程接1 3 ，使应用程序能够访问和更新x m l 文档的样式、结构和内容；关系数据采用o d b c 、j d b c 、o l ed b 等 x m l 数据库在技术成熟度上还无法与关系数据库抗衡，关系数据库具有数 据结构化、最低冗余度、较高的程序与数据独立性、易于扩充、易于编蒂4 应用程 序等优点；x m l 数据库缺乏多重管理、协同工作的能力，规划能力不强、易用 性不好，这些大型关系数据库所拥有的种种优点在x m l 数据库技术上难以展现 此外，x m l 技术采用的是基于文件的管理机制，文件管理存在着容量大、 管理困难的缺点；x m l 的检索是基于结点的检索，存放大量甚至海量数据的 x m l 文件造成检索速度极低；解析手段有缺陷。x m l 具有两种解析机制，s a x 方式是基于文件的解析，速度慢，d o m 方式是基于内存的方式，资源消耗极大； 修改效率低，目前x m l 的修改是基于结点的；x m l 的安全性及并发操作机制 7 天津师范大学硕士学位论文 也是需要解决的问题之一。 将x m l 文档映射为关系模式进行存储，有两大类映射方法【l ：模型映射 ( m o d e lm a p p i n g ) 和结构映射( s t r u c t u r em a p p i n g ) 。对于模型映射，需要将x m l 文档模型( 即文档树结构) 映射为关系模式，关系模式表示x m l 文档模型的组 成部分，这种存储方法对于所有的x m l 文档都有固定的关系模式。因此，它是 与x m l 模式( 或啪) 无关的。对于结构映射，需要将x m l 模式( 或肼田) 映射为关系模式，关系模式表示所存储的x m l 文档的逻辑结构( 即x m l 模式 或啪) ，这种方法是与x m l 模式( 或i y i d ) 相关的。具体说来，利用关系数 据库系统存储x m l 文档有如下的方法： ( 1 ) 将一个x m l 文档看成是一个有向边标记图，称为x m l 图。设计一个( 或 多个) 关系模式存储x m l 图中的边信息和结点值 7 1 。该策略是基于边的模型映 射方法，称为边模型映射方法 ( 2 ) 设计若干个关系来存储x m l 文档树的结点信息、结点值和结构信息( 遁 过区间编码来表示结构信息，或直接存储双亲，孩子结点对或祖先后裔结点对) ， 该策略基于结点的模型映射方法【1 1 1 2 x 2 2 1 1 2 3 1 ，称为结点模型映射方法。 ( 3 ) 从x m l 文档的d t d 或s c h e m a 推断x m l 元素应该怎样映射到关系模式 【7 】f 8 ( g x 2 s l ，再将x m l 文档存储到相应的关系模式中，该策略属于结构映射方法 2 2 1 模型映射方法 1 、边模型映射方法 一个x m l 文档能够用一个有序有向边标记图( 称为x m l 图) 来表示【刀 在这种图中，每一个x m l 元素用一个结点表示，结点被标记上x m l 对象的o i d ； 元素和子元素( 或属性) 的关系用图中的边来表示，并在边上标上子元素( 或属 性) 名；为了表示x m l 元素中各子元素的顺序，可以对图中从某结点引出的所 有边进行摔序；x m l 文档中的值作为图中叶结点( 即属性或最底层子元素结点) 表示。图2 3 就是根据图2 1 所示的x m l 文档所作的x m l 图，其中，标有数字 的圆圈为非叶结点，数字为结点o i d ；标有以“v ，牙头数字的圆圈为叶结点( 即值 结点) ，圈中编号为结点o i d ( 称为v i d ) ；每条边的名称后面的数字为边的序号； 4 号结点的e d i t o r i d 属性为i d r e f 类型，它直接指向5 号结点。 8 天津师范大学硕士学位论文 ： 图2 3 图2 1 所示x m l 对应的文档图 有了x m l 图以后，就可以分别设计关系表来存储x m l 文挡的边信息和值。 对于用来存储边信息的边表有三种设计方案：第一种是用一个表来存储图的所有 边信息，这种方案称为e d g e 方案；第二种是所有具有相同名称的边存放在一个 边表中，这种方案称为b i n a r y 方案；第三种是采用一个边表来存储图中所有路 径的边信息，该方案称为u n i v e r s a l 方案。 e d g e 边表的关系模式为：e d g e ( s o u r c e ，o r d i n a l ，l a b e l ，f l a g ，t a r g e t ) 其中 s o u r c e 域和t a r g e t 域分别用来存储边的引出结点和引入结点对象的o i d ，o r d i n a l 域用来反映该边在兄弟边中的位置编号，l a b e l 域用来存储边标记( e d g e - l a b e l ， 即该边所指向结点的标记名) ，f l a g 属性用来反映该边所指向结点的类型 结点的类型分为两类：时结点和非叶结点。时结点的类型分为n t e g e r 、s i r i n g 等，分别表示叶结点的值为整型和字符串类型等；非叶结点的类型均为r e f 9 天津师范大学硕士学位论文 表2 1 图2 3 所示x m l 图所对应的e d g e 方法的边表。 雕戮獭鬻麟麟a 磷蘸攒黼嘲霪囊戮缫麓濑麟缫畿戮黼瀚 2 l y e a ri n t e g e r v 2 2 2t i t l e s t r i n g v 3 23 p n c e d e c i m a lv 4 24a u t h o rr e f6 2 5a u t h o rr e f 7 4 2t i t l e s t r i n g v 1 5 b i n a r y 边表与e d g e 边表的原理相同，只是将所有具有相同边标记的边存储 在一个单独的边表中，b i n a r y 边表的关系模式为b i n 灯y l a b e l ( s o u r c e ，o r d i n a l ， f l a g ，t a r g e t ) 。从概念上说，b i n a r y 方法的边表是e d g e 方法中使用的边表的水平 分割。 表2 2 存储t i t l e 元素的b i n a r y 边表 对于用来存储x m l 文档值的值表有两种设计方案：第一种是不单独设计值 表，将值和边同时存储在一个关系表中，在边表中直接增加一个属性v a l u e ，用 于存储叶结点的值，这种方法称为内联方法；第二种是为每一种可能的取值类型 设计一个值表，该方法称为分离值表。分离值表的关系模式为u c i y 弦( v i d ， v a l u e ) ，其中，v i d 属性用来存储叶结点的o i d 值，v a l u e 属性用来存储叶结点的 值 边模型映射方法仅仅维护x m l 文档树的边信息，因此，为了处理用户的查 询，需要连接边表形成一个路径单一边表方法( e d g e 边表方法) 非常简单， 因为它仅需要维护边标记，但是为了实现路径表达式的计算就需要大量的连接操 作 2 、结点模型映射方法 q n 和b m o o n 首先对利用区间编码方案来有效的处理x m l 的正则路径表 达式( r e g u l a rp a t he x p r e s s i o n ) 查询进行研究 6 1 ，以实现快速地确定在x m l 数 据层次结构中任意结点对之间的包含关系。 l o 天津师范大学硕士学位论文 ( 1 ) x r e l 模式l l i 】 m y o s h i k a w a 、t a m a g a r a 等基于结点模型映射方法提出了一个x m l 数据的 关系存储模式，称为x r e l 。x r e l 是通过区间编码 s t a r t ，e n d 来表示x m l 文档 的模型结构，并根据内容来划分边，分为元素边、属性边和文本边，同时将所有 路径进行存储因此，x r e l 方法由四个关系表组成： e l e m e n t ( p a t h l d ，d o c i d ，s t a r t ，e n d ，o r d i n a l ) a t t r i b u t e ( p a t h i d ，d o c l d ，s t a r t ，e n d ，v a l u e ) t e x t ( p a t h i d ，d o d d ，s t a r t ，e n d ，v a l u e ) p a t h ( p a t h i d ，p a t h e x p ) 其中，在p a t h 表中，p a t h i d 是标记路径的标识，p a t b e x p 存储标记路径，为 了实现路径表达式中的字符串比配操作，将标记路径中的“”替换为“彬”进行 存储，对于e l e m e n t 、a t t r i b u t e 和t e x t 表，主键为( d o d d ，s t a r t ) ，p a t h i d 是外 键。 ( 2 ) x p a r e n t 模式【1 2 】 x p a r e n t 是通过一个单独的p a r e n t ( p a r e n t - i d ，c h i l d - i d ) 来反映x m l 文档 的模型结构，并根据内容和“结构与非结构”来划分边，同时将所有路径进行存 储，因此x p a r e n t 也是由四个关系表组成： l a b e l p a t h ( p a t h i d ，l e n g t h ，p a t h e x p ) p a r e n t ( p i d ，c i d ) e l e m e n t ( p a t h l d ，d i d ，o r d i n a l ) d a t a ( p a t h l d ，d i d ，o r d i n a l ，v a l u e ) 其中，l e n g t h 为标记路径的长度( 1 a b e l - p a t h ) 的长度，即标记路径中边标记 的个数；p a t h e x p 域存储标记路径，与x r e l 相似，这里将标记路径中的“”替 换为“，”进行存储；d i d 为x m l 文档中元素结点的标识，它也可以作为以该结 点为终端点的数据路径( d a t a - p a t h ) 的标识；li d 、c i d 分别为沮。文档中的数 据路径中的双亲结点、孩子结点的标识。这里，没有考虑文档标识d o c i d 。 p a r e n t 表存储的是双亲，孩子关系，因此，为了检查数据路径需要进行连接操作 为了加速这种处理，可以不用p a r e n t 表，而改用a n c e s t o r 表来存储祖先循裔关 系。关系模式为：a n c e s t o r ( d i d ，a n c e s t o r ，l e v e l ) ，利用a n c e s t o r 表能够快速的 天津师范大学硕士学位论文 检测结点之间的祖先后裔关系，但是比p a r e n t 需要更多的空间，而且由于存在 冗余信息，修改起来代价也很高。 x p 缸e n t 模式分别通过l a b e l p a t h 表和p a r e n t 表来支持标记路径和数据路径， 因此x p 觚e n t 模式既具有结点的模型映射特点，又具有基于边的模型映射特点。 p a r e n t 表基于双亲孩子关系来反映x m l 文档的核心结构，它也能够被迸一步物 化为a n c e s t o r 表来支持祖先后裔关系。由于x m l 文档中的结点也可以用来标 识以该结点为终端结点的数据路径，因此，元素和数据( 文本或属性) 隶属于数 据路径 结点模型映射方法需要维护的是x m l 文档树的结点信息，而不是边的信息。 x r e l 模式通过区间编码来译码x m l 文档的模型结构( 即包含关系) 它的优点 是通过非等值连接能够判断两个结点之间的包含关系。x p a x e n t 模式在结构上类 似于x r e l 模式，只是用d i d 替代了【s t a d 】。然而，这种变化使得x p m n t 模 式仅需要等值连接，因此x p a r e l l t 模式能够基于传统的索引机制，从而得到有效 的实现 2 2 2 结构映射方法 j s l m m n u 粥m d a r a m 等提出了根据d t d 映射关系模式的存储策略嘲。首先 要对明【d 进行适当的简化，然后产生d t d 图以及元素图，再根据明m 图或元 素图生成关系模式，最后将符合该关系模式的订l 文档数据装入到关系数据库 中 1 、简化d t d 并生成d t d 图 x m ld t d 的元素可以是任意复杂的，如“ ”( d t d - i ) 。因此，在将d t d 映射为关系模式之前必 须要对复杂的d t d 进行必要的简化变换d t d 的简化包括三种类型。 f l a t t e n i n g 变换：变换每一个嵌套定义到平坦的表示，使二元操作。，”和“l ” 不出现在任何操作之内，例如( c l ，c 2 ) 一e 1 ，e 2 * ( e l s e 2 ) 7 - , - e l ? ，e 2 7 ( c l i e 2 ) e l ，e 2 s i m p l i f i c a t i o n 变换：将连续的多个一元操作简化为一个一元操作，例如e l - - - e i *e l ? 一e l e l ? 一e l g r o u p i n g 变换：将多个具有相同名称的子元素进行聚合，形成一个子元素， 天津师范大学硬士学位论文 例如： 一矿一a 一一矿一 一a ? 一a 一一a 一 一a 一一a 一a 一 一a 一一a ? 一a 一a ? a ? 一a 根据上面所介绍的简化方法，( d t d - 1 ) 简化为“ ”。 根据前文给出的简化规则可以将图2 2 所示i y r d 进行简化。 ! 肖t i l i s ta r t i c l eo d i t o r i d 撑b d p l 皿 ! e l e m e n ta u t h o r ( n a m e 】a i l p ! e l e m e n te d i t o r ( n a m e e m a i l * p fe l e m e n ti i b r a r y ( # p c d a t a 图2 a 对图2 2 所示d t d 简化后的d t d 一个d t d 图表示一个d t d 的结构，图的结点是d t d 中的元素、属性和正 则路径运算符，每一个元素在图中出现且仅出现一次，属性和操作符在d t d 图 中出现的次数则与它们在d t d 中出现的次数相同；图的边则反映d t d 图中元 素之间的嵌套关系；图中的环路表示回路的出现，即在d t d 中元素之间出现了 递归的情形 天津师范大学硬士学位论文 图2 5 简化后的d t d 图 2 、根据d t d 图生成关系模式 根据一个d t d 图生成的关系模式是该d t d 图中每一个元素所生成的关系 模式的并集为了说明如何生成一个元素的关系模式，需要引入元素图的概念。 简单的说，一个元素的元素图就是从该元素出发以深度优先遍历d t d 的过程所 生成的一棵树。如果遍历过程中达到了一个已经遍历过的结点，则表示出现了回 路，回路可以看成是逆向边，它以虚线边来表示，且该条路线不必再去重复遍历。 根据d t d 图生成关系模式的方法有； ( 1 ) 基本内联法：对于每一个名为c 的元素，根据它的元素图生成一个同名的 关系模式e ，元素图中的根结点e 的所有后裔结点均内联到该关系中来作为一个 属性，但下列两种情况例外：一个或+ 结点的直接孩子结点不包括在该关系中， 即对于集合值孩子将另外生成一个新的关系：产生逆向边的结点不包括在该关 系中，即另外生成一个新的关系来处理回路。 在生成的关系模式中，关系的属性是以从结点c 到内联结点的路径来命名； 每一个关系需要有一个d 域来作为该关系的主键；对于或+ 结点的直接孩子结 点以及带回路的结点，它们所生成的关系模式还需要有一个p a r e n t i d 域来作为该 关系的外键。基本内联法将产生大量的关系，并且会产生大量的数据冗余，因此 天津师范大学硕士学位论文 该方法基本上不实用。 ( 2 ) 共享内联法：这个方法使每一个结点出现且仅出现在一个关系中按如下 规则来判断哪些元素可以生成独立的关系模式： d t d 图中入度大于l 或等于0 的元素结点生成独立的关系模式； d t d 图中结点或+ 的直接后继元素结点生成独立的关系模式； 互为递归的入度为l 的元素结点，其中之一生成独立的关系模式； 其余的结点均生成关系属性 共享内联法比基本内联法减少了数据冗余，但在查询时增加了许多连接操 将元素x 内联到元素y 所产生的关系模式中，如果有一个x m l 文档是以x 元素为根。则在查询时将会出现问题。为了解决这种元素的查询，在关系中引入 一个x i s r o o t 域。如b o o k 关系中的b o o k p r i i s r o o t 域 在m ，文档中，有些元素的双亲并不是唯一的，如，对于a u t h o r 元素，它 的双亲可能是b o o k 元素，也可能是a r t i c l e 元素。因此，在非根元素所生成的关 系中还需要增加一个p a r e n t c o d e 域，以指示双亲的类型，以便查询时进行正确 的连接。 ( 3 ) 综合内联法：在共享内联法的基础上，将所有入度大于l 的元素结点也内 联进入到所生成的关系模式中，但是带回路的结点以及结点或+ 的直接后继元素 除外。综合内联法充分吸取了基本内联法和共享内联法的优点采用综合内联法 根据d t d 映射成