（计算机应用技术专业论文）基于xml的关系数据库优化方法研究.pdf

摘要 基于x m l 的关系数据库优化方法研究 摘要 x m l 自1 9 9 8 年由w 3 c 提出之后，已经成为数据表示和数据交 换的新标准，各行各业都在使用x m l 用来描述本领域信息，随着 x m l 文档的增加，如何有效存储、管理和查询这些数据成为当前 x m l 领域的一个研究热点，也是数据库领域的一个新的研究方向。 本文主要讨论基于x m l 的关系数据库存储和查询技术。 ( 1 ) 本文首先讨论基于x m l 的关系数据库存储技术，在介绍 完典型的x m l 。r d b 映射方法之后，对几种改进的存储方法进行了深 入分析。典型的映射方法包括边模型映射、结点模型映射、结构映射 以及约束映射。改进的存储方法中重点讨论了x r e s t o r e 方法、基 于es c h e m a 的映射方法以及基于扩展哈夫曼编码的x m l 存储模型。 基于以上的研究，结合线索二叉树的思想，本文提出了线索多叉树 ( t h r e a d i n g n u m e r o u s - t r e e ) 的概念，运用线索多叉树的原理，本文 提出了基于t h r e a d i n g n u m e r o u s t r e e 的x m l 存储模型。该模型能有 效解决基于哈夫曼编码的x m l 存储模型中，随着x m l 树的深度增 加，编码实现困难的问题。 ( 2 ) 在介绍完存储技术后本文探讨了x m l 索引和查询若干技 术。根据响应查询和处理查询的方式将索引分为结构概要索引、结点 编码索引和整体索引，并分别对它们进行研究。在此之后，对x m l i 北京化工大学硕士学位论文 查询关键技术：x p a t h 查询处理技术、x q u e r y 查询处理技术、以及 x m l t o s q l 查询转化技术进行了深入分析。因为结构连接算法在 x m l 查询中的重要性，本文对其中的父子关系以及兄弟关系进行了 研究与改进，改进的算法基于本文提出的b r e a d t h d e p t h 存储模型， 采用深度查询和广度查询相结合的搜索策略。为了解决f l m l 中用户 书写表达式困难的问题，本文提出了利用本体模式表示x m l 查询条 件的思路。 ( 3 ) 最后将x m l 存储和查询运用到古代建筑领域，提出了x m l 存储和查询实现的系统架构，并对主要的实现过程进行详细而深入的 分析。并且基于古代建筑领域数据的特点提出了基于全路径搜索的和 基于领域本体的查询优化方案。 关键词：关系数据库，x m l ，存储查询 摘要 r e s e a r c h o no p t i m i z a t i o no fr e l a t i o n a l d a t a b a s eb a s e do nx m l a b s t r a c t a f t e rp r o p o s e db yt h ew 3 ci n19 9 8 ，x m lh a sb e c o m ean e w s 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 dd a t ae x c h a n g eo nt h ei n t e r n e t a l l t r a d e sa n d p r o f e s s i o n s a r e u s i n g x m lt od e s c r i b et h ed o m a i n i n f o r m a t i o n a l o n g w i t hx m ld o c u m e n t s s h a r pg r o w t h ，h o w t o e f f e c t i v e l ys t o r a g e ，m a n a g ea n di n q u i r et h e s ex m ld a t ab e c o m ea r e s e a r c h h o t s p o t i nx m ld o m a i na n dan e wr e s e a r c hd i r e c t i o ni n d a t a b a s ed o m a i n t h i s p a p e r f o c u s e so nx m ls t o r a g ea n d q u e r y t e c h n o l o g yb a s e do nr e l a t i o n a ld a t a b a s e i nt h i sp a p e r , w ef i r s td i s c u s sx m ls t o r a g et e c h n o l o g yb a s e do n r e l a t i o n a ld a t a b a s e a f t e rs e v e r a lt y p i c a lx m l - r d bm a p p i n gm e t h o d sa r e i n t r o d u c e d ，i n d e p t ha n a l y s i sa r ec a r r i e do ns e v e r a li m p r o v e ds t o r a g e m e t h o d s t h e s et y p i c a lx m l r d bm a p p i n gm e t h o d si n c l u d em a p p i n g m e t h o do fe d g em o d e l ，m a p p i n gm e t h o do fn o d em o d e l ，s t r u c t u r em a p p i n g m e t h o da n dc o n s t r a i n tm a p p i n gm e t h o d a m o n gt h ei m p r o v e ds t o r a g e m e t h o d sw ef o c u so nx r e s t o r em e t h o d ，m a p p i n gs c h e m af r o m x m lt or e l a t i o nb a s e do ne s c h e m aa n dt h ex m l s t o r a g em o d e lb a s e d 北京化工大学硕士学位论交 o ne x t e n d e dh u f f m a nc o d i n g t h e nf r o ma b o v er e s e a r c ha n dt h e o r yo f t h r e a d i n g - n u m e r o u s - t r e e b a s e do nt h r e a d i n g - b i n a r y - t r e ew ep u t f o r w a r dax m l s t o r a g em o d e lb a s e do i lt h r e a d i n g n u m e r o u s t r e e t h e n e w s t o r a g em o d e lc a l le f f e c t i v e l ys o l v et h ep r o b l e mt h a ti ti sd i f f i c u l 锣t o r e a l i z ec o d e i n gi fx m lt r e e sd e p t hi n c r e a s e si nx m ls t o r a g em o d e l b a s e do ne x t e n d e dh u f f m a nc o d i n g 。 a f t e ri n t r o d u c t i o no fx m l s t o r a g et e c h n o l o g y , t h e nt h i sp a p e rf o c u s o nt e c h n o l o g i e si nx m lq u e r y ，a n dw er e s e a r c ho nx m lq u e r y t e c h n o l o g i e si n c l u d i n gx p a t hq u e r yp r o c e s s i n gt e c h n i q u e s ，x q u e r yq u e r y p r o c e s s i n gt e c h n i q u e s a n d x m l - t o - s q lq u e r y c o n v e r s i o n t e c h n i q u e s b e c a u s e o ft h e i m p o r t a n c e o ft h es t r u c t u r ec o n n e c t i o n a l g o r i t h mi nt h ex m lq u e r y , w er e s e a r c ha n di m p r o v ep a r e n t c h i l da n d p r e c e d i n g - s i b l i n g f o l l o w i n g s i b l i n gs t r u c t u r a lj o i na l g o r i t h mt h a tb a s e d o nb r e a d t h d e p t hs t o r a g em o d e lp r o p o s e di nt h i sp a p e r i no r d e rt os o l v e t h ep r o b l e mt h a ti t sd i f f i c u l tf o ru s e r st ow r i t ei n q u i r ye x p r e s s i o n ，w e p r o p o s et h ev i e w p o i n tt h a tc o n s t r u c t i o no fx m lq u e r ye x p r e s s i o nu s i n g o n t o l o g ym o d e l 。 a tl a s t ，w ea p p l yt h ex m ls t o r a g ea n dq u e r yt e c h n i q u e st oa n c i e n t a r c h it e c t u r ed o m a i n as t o r a g ea n dq u e r yf r a m e w o r kb a s e do nr e l a t i o n a l d a t a b a s ei sc o n s t r u c t e da n dd e t a i l e da n di n - d e p t ha n a l y s i sa r ec a r r i e do n t h e i m p l e m e n t a t i o np r o c e d u r e t h e n ，b a s e d o nf e a t u r e so fa n c i e n t a r c h i t e c t u r e ，w ep u tf o r w a r dx m lq u e r yo p t i m i z a t i o nb a s e do ne n t i r e i v 摘要 p a t ha n dx m lq u e r yo p t i m i z a t i o nb a s e do nd o m a i no n t o l o g y k e yw o r d s ：r e l a t i o n a ld a t a b a s e ，x m l ，s t o r a g ea n dq u e r y v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：乏勉日期：2 2 2 竺垒：竺笸 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在一年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：兰垒盘 导师签名：璺罂绁 第一章绪论 第一章绪论 1 1 课题研究的背景和意义 随着i n t r a n e t 技术的迅速发展和网络计算模式的广泛应用，各个应用领域建 立了不同规模的信息系统。各信息系统大都自成体系，具有不同的数据格式，数 据库的结构各不相同。因此各个系统间的交流阻抗很大，需要人工对信息进行转 换和和输入。随着x m l 技术应用的普及，x m l 成为信息交换和编码的主流格 式和事实标准。目前很多研究尝试在同一领域应用x m l 制定相应的数据描述规 范，参与者按照这个规范描述数据，就可以有效地进行数据交换。 但随着x m l 数据发布的指数式增长，管理现有的x m l 文档已变得越来越 困难，因此对x m l 文档的有效存储和查询成为近几年的研究热点。由于关系数 据库在管理数据方面的高效性，加之过去几十年里关系数据库技术已经发展地相 当成熟，因此利用关系数据库来存储和查询x m l 数据是处理x m l 文档的一种 有效手段。 相对于关系数据库，v d d l 在数据应用方面有很多优点：跨平台性，x m l 文 件为纯文本文件，不受操作系统、软件平台的限制；具有基于d t d s c h e m a 自描 述语义的功能；x m l 不仅可以描述结构化数据，更可以有效描述半结构化甚至 非结构化数据。相对于x m l ，关系数据库的优势在于：技术成熟、应用广泛、 数据管理能力强、数据安全程度高、具有稳定可靠的并发访问机制等。研究的目 的就是把两者的优点结合起来，研究x m l 数据和关系数据的映射策略，从而达 到“以关系数据库为存储手段，以x m l 格式数据为交换载体”的数据管理方式。 1 2 本课题相关领域的历史、现状和前沿发展情况 早期的x m l 数据以文档方式存储，以关键字查询等信息检索手段查询，这 种方法简单、易用，但查询的效率非常低。目前，在存储和查询x m l 数据领域 主要有两种方法：原生x m l 数据库和使能x m l 数据库。 原生x m l 数据库分为两类：基于文本和基于模型。基于文本的原生x m l 数 据库将x m l 作为文本存储，它可以是文件系统中的文件，关系数据库中的b l o b 或特定的文件格式。目前已经有很多研究机构开发了纯x m l 数据库，国外有 l o r e t 、t a m i n o 【2 j 、t i m b e 一3 】等，国内主要是人民大学的o r i e n t x t 4 1 。目前，大部 分原生数据库采用深度优先的方法存储记录，这是因为深度优先实现起来简单， 北京化工大学硕士学位论文 同时存储顺序与x m l 文档的原始顺序一致。广度优先的顺序还没有被采用，聚 集存储的方法在o r i e n t x 中实现过。与其它存储方式相比，原生x m l 数据库可以 完整地保留x m l 文档的信息，存储映射时不需要d t d 结构，同时原生的x m l 数 据库采用基于x m l 的查询界面，例如：x p a t h 或d o m ，适合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 查询语言转换为s q l 或o q l ，查询结果转换为y 2 v l l 文档等。目前许多研究者正在从事基于关系数据库系统处理x m l 数据的研究。 国内有复旦大学的v x m l “习系统，国外有c o n t 吼t 溺m l 【6 】系统、m a r k q a v e s 【刀 系统。 当今，包括甲骨文、微软在内的数据库厂商都在走从传统关系数据库中支持 x m l 的路线，并且在其成熟的关系数据库产品中提供了对x m l 的支持。毫无疑 问，在接下来的几年里，所有的数据库产品都需要能够快速地用x m l 格式语言 进行数据的校验、存储和恢复。 1 3 课题的难点 ( 1 ) 信息无损性。要实现结构化查询，设计的x l v l l 数据存储模型要有足 够的信息以保证查询结果是无损的。 ( 2 ) 在查询的过程中如何通过建立索引和改进结构连接算法提高查询效率。 ( 3 ) x m l 查询表达式的构建。 1 4 课题的主要创新点 ( 1 ) 提出了新的存储模型t h r e a d i n g - n u m e r o u s - t r e e 和b r e a d t h - d e p t h 。其中 t h r e a d i n g - n u m e r o u s t r e e 模型源于线索- - y 树的思想；b r e a d t h d e p t h 模型基于 x r e l 模式和x p a r e n t 模式构建，增加了广度优先遍历序和深度优先遍历序的信 息，运用该存储模型有利于提高父子关系、兄弟关系的结构查询。 2 第一章绪论 ( 2 ) 基于b r e a d t h d e p t h 存储模型提出了新的父子关系和兄弟关系结构连接 算法。 ( 3 ) 鉴于x q u e , y 、x p a t h 和x m l - q l 等x m l 查询语言的复杂性以及本体 和x m l 在概念层次上的一致性研究一种基于本体的查询条件表示方法。 ( 4 ) 将所研究的理论应用到古代建筑领域，提出了一种基于领域本体的查 询优化策略。 1 5 论文的研究内容和组织结构 1 5 1 论文的主要研究内容 本论文主要研究基于x m l 的关系数据库存储方法和查询方法，以便充分利 用数据库的高效、安全等性能实现对x m l 数据的存储和管理，主要研究内容包 括： ( 1 ) 基于x m l 的关系数据库存储模型研究。 ( 2 ) 研究y 3 v i l 数据库索引技术和x m l 查询处理技术。 ( 3 ) 设计简单的查询语言。 现今对x m l 查询语言的研究已经非常成熟，但这些语言过于复杂，普通用 户不容易完全掌握，因此有必要设计一种查询语言变体，在保证查询准确率的前 提下，方便用户使用。 ( 4 ) x m l 存储和查询在古代建筑领域的应用 1 5 2 论文的组织 本论文内容共分为五章： 第一章论述了本论文的研究背景和意义、研究历史和现状、课题的难点和 创新点。 第二章研究基于x m l 的关系数据库存储技术，对典型的x m l r d b 映射 方法进行了深入分析，并提出改进的存储方法。 第三章研究x m l 索引和查询技术，对常用的索引策略、查询处理技术进 行了深入探讨，对父子关系、兄弟关系的结构连接算法进行研究和改进，最后提 出了一种基于本体的x m l 查询条件表示方法。 第四章面向古代建筑信息数据的x m l 存储和查询研究，对基于x m l 的关 系数据库存储和查询的框架以及具体的实现过程进行了深入探讨，并针对古代建 筑数据的特点提出查询优化方案。 北京化工大学硕士学位论文 第五章对本论文的主要工作做了总结，同时也提出了今后需要进一步做的研 究和工作。 4 第二章基于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 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 模式相关的。 2 1 典型的x m l - r d b 映射方法 利用关系数据库存储x m l 数据有如下的方法和策略： ( 1 ) 边模型映射方法：x m l 文档用一个有向标记图表示，称为x m i ，文档， 设计一个或若干个关系存储x m l 图的边信息和结点值； ( 2 ) 结点模型映射方法：用若干个关系来存储x m l 文档树的结点信息、结 点值和结构信息，通过区间编码来译码结构信息，或直接存储双亲孩子结点对 或祖先后裔结点对； ( 3 ) 结构映射方法：简化d t d 产生d t d 图及元素图，根据d t d 图或元素图 生成关系模式，最后将符合该d t d 的x m l 文档数据载入关系数据库中； ( 4 ) 约束映射方法：从保持信息的角度出发，利用x m l 文档中语义约束 ( 键、函数依赖) 来产生关系模式。 2 1 1 边模型映射方法 对于边模型映射方法，每个x m l 文档用有序有向边标记图( 即x m l 图) 来表示【8 1 。在x m l 图中，元素用结点表示，结点标上x m l 对象的o i d ；元素 与子元素( 或属性) 之间的关系用图中的边表示，并在边上标上子元素名；为了 表示x m l 元素中各子元素的顺序，可以对图中从某结点引出的所有边进行排序； x m l 文档的值作为图中的页结点。图2 2 表示的是图2 一l 所示x m l 文档实例的 北京化工大学硕士学位论文 x m l 图。图中标有数字的圆圈为非叶结点，数字为结点序号o l d ：标有以v 开头 数字的圆圈为叶结点；每条边名称后面的数字为边的序号。 有了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 方法，该方法采用一个边表来存储图中所有路径的边信息。 7 x m iv e r s l o n 已 1 0 7 p u b 古建筑博物馆 h t t p ：# 2 0 2 4 15 5 19 1 b u c t pm p i 1 j p g 2 0 0 8 0 5 0 5 l u l d o a d t i m e d y n a s t y 洛j 咀，d y n a s t y ：- 该值梁是浯朝修缮= 仙庙时加入 a u i h o ri d = ”102 n a m e ) g a o l e i a u t h o rl d = 。10 了 n a m e ) 匿名 a u t h o r ) ，e o l l e c t i o n c o l l e c t i o ns o r t l d = l 。 n a m e ) 飞来石，n a m e ) p i c t u r e p a t h ，h t t p ：# 2 0 2 4 15 5 19 1 ，b u c t pm ，p i ，3 j p g u p l o a c l t i m e ) 2 0 0 8 - 0 争12 l u p l o a d t i m e 唐喜日 一d i s c r 的t i o n 唐童耳修建 ，d i s c r i 洲o n c o l l e c t i o n 宗教建筑, i s o r t c o m m e n t 你的博物馆内容很丰富，c o n t e n t e ，c 0 m m e n t ) ，d u b ) 图2 - 1 一个x m l 文档实例 f i g 2 - la l lx _ m ld o c u m e n ti n s t a n c e 1 图2 - 2x m l 图实例 f i g 2 - 2a l lx m lf i g u r ei n s t a n c 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 域用来反映该边在 6 第二章基于x m l 的关系数据库存储技术研究 兄弟边中的位置序号，l a b e l 域用来存储边标记，f l a g 属性反映该边所指向的结点 类型。表2 l 所示为图2 - 2 所示x m l 图对应的e d g e 方法的边表。 表2 - 1e d g e 方法的边表 t a b l e 2 - 1t h es i d et a b l eo fe d g e b i n a r y 边表与e d g e 边表的原理相同，只是将所有具有相同边标记的边存放 在一个单独的边表中，概念上讲，b i n a r y 方法的边表是e d g e 方法中使用的边表 的水平分割。b i n a r y 边表的关系模式为： b i n a r y m , e j ( s o u r c e ，o r d i n a l ，f l a g , t a r g e t ) 用来存储x m l 文档值的值表有两种设计方案：第一种是内联法，该方法不 单独设计值表，将值和边存储在同一个表中，在边表中直接增加一个属性v a l u e ， 用来存储叶结点的值；另一种方法是分离值表，该方法为每一种可能的取值类型 设计一个值表，分离值表的关系模式为v a l u e t y p e ( v i d ，v a l u e ) ，其中v i d 属性用来存 储叶结点的o i d 值，v a l u e 属性用来存储叶结点的值。 三种边表设计方案和两种值表设计方案组合共有六种存储模式。d f l o r e s c u 和d k o s s m a n n 对这六种基本的存储模式得到的关系数据库大小、执行不同类型 的x m l 查询的时间，从关系数据库重构x m l 文档的时间等三个性能参数进行 了量化分析，结论是：b i n a r y 边表方法优于e d g e 边表方法，e d g e 边表方法又优 于u n i v e r s a l 边表方法；内联值表方法优于分离值表方法；b i n a r y 边表和内联值 表相结合的存储模式能获得最好的综合性能。 7 北京化工大学硕士学位论文 2 1 2 结点模型映射方法 结点模型映射和边模型映射的基本思想相似，但其保留了x m l 中所有结点 的信息。较有代表性的有x r e l 9 】模式和x p a r e n t t l o 】模式。x r e l 模式是由 m y o s h i k a w a 、t a m a g a r a 等提出。香港科技大学j i a n gh a i f e n g 、l uh o n g j u n 和 w a n gw e i 等基于结点模型映射方法提出了另一个x m l 数据的关系存储模式，称 为x p a r e n t 。 ( 1 ) x r e l 模式 x r e l 是通过区间编码 s t a r t ，e n d 来反映x m l 文档的模型结构，并根据内容 来划分边、属性边和文本边，同时将所有路径进行存储。x r e l 模型将一篇x m l 文档映射到四个关系表中，分别为e l e m e n t 、a t t r i b u t e 、t e x t 、p a t h 。其中e l e m e n t 、 t e x t 和a t t r i b u t e 表分别用来描述x m l 文档中元素、属性和数据信息，p a t h 表描 述路径信息。四个关系表的结构分别为： e l e m e n t ( p a t h l d ，d o c l 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 l d ，d o c l d ，s t a r t , e n d ，v a l u e ) t e r t ( p a t b _ d ，d o c l d ，s t a r t ，e n d ，v a l u e ) p a t h ( p a t h l d ，p a t h e x p ) 这种模型在建e l e n i e n t t e x t 和a t t r i b u t e 表的过程中直接视x m l 文档为一个 字符流文件并进行相应的操作。为此引入r e g i o n 概念，将r e g i o n 指定为一个节点 在x m l 文档中对应的起点和终点之间的区域，其中，s t a r t 和e n d 界定r e g i o n 的 范围。 ( 2 ) x p a r e n t 模式 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 l 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 ) 这四个表分别用来存储边路径、双亲孩子关系、x m l 文档中的元素和数据。 x p a r e n t 模式分别通过l a b e l p a t h 表和p a r e n t 表来支持标记路径和数据路径，因此， x p a r e n t 模式既具有基于结点的模型映射的特点，又具有基于边的模型映射的特 点。 ，p a r e n t 表基于双亲孩子关系来反映x m l 文档的核心内容，它能够进一步物 8 第二章基于x m l 的关系数据库存储技术研究 化为a n c e s t o r 表来支持祖先后裔关系。 在结点模型映射的两种方法中，x r e l 通过区间编码来译码x m l 文档的模型 结构，它的优点是通过非等值连接。可以很容易判别两个结点之间的包含关系， 但因为在关系数据库中没有特殊的索引机制支持它，o 连接的代价比等值连接要 高得多。x p a r e n t 模式在结构上类似于x r e l 模式，只是用d i d 替代t s t a r t , e n d 。 然而这种变化使得x p a r c n t 模式仅仅需要等值连接，因此，x p a r c n t 模式能够基 于传统的索引机制( 如b 树索引) 得到有效实现。 2 1 3 结构映射方法 结构映射方法也称为有模式映射方法，即在进行关系数据库的x m l 存储时， 先根据x m l 模式生成相应的关系模式，然后再根据生成的关系模式对x m l 文 档进行解析分解并将它存于相应的数据表中。结构映射的特点是以x m l 文档模 式为输入，产生的关系为输出。x m l 文档模式主要由d t d 和x m ls c h e m a 来定 义。 ( 1 ) d t d 数据模型及其映射方法 j s h a n m u g a s u n d a r a m 等提出了根据d t d 映射关系模式的存储策略【1 1 1 。 该方法首先需要对d t d 进行简化，然后产生d i d 图及元素图，再根据d t d 图 及元素图生成关系模式，最后将符合该d t d 的x m l 数据载入关系数据库中。 简化d t d 生成d t d 图 在将d t d 映射为关系模式前，需要对复杂的d t d 进行必要的简化变换。 d t d 的简化变化包括三种类型： a ) f 变换，即将嵌套定义转换为非嵌套的平坦化的表示，使二元操作“， 和“l ”不出现在任何操作内。其变换规则如下： ( e l ，e 2 ) 木一e l 幸，e 2 幸 ( e l ，e 2 ) ? 一e l ? ，e 2 7 ( e d e 2 ) 一e l ? ，e 2 7 b ) s 变换，即将多个一元操作简化为一个一元操作，其规则如下： e 宰 啼e 幸 e 宰? 一e 宰 e ? 簟一e 枣 e ? ? 一e ? c ) g 变换，即将多个具有相同名字的子元素进行聚合，从而形成一个子元 素，其变换规则如下： ，e 木，e 牟，一e 枣， 9 北京化工大学硕士学位论文 ，e 车，e ? ，。e 宰， ， e ? ， e 宰，呻e 幸， ，e ? ，e ? ，一e 幸， ”，e ，e ，4 e ， 另外，所有的“+ 操作都被转化为“木”操作，所有的“? ”操作都被去掉。 一个d t d 图表示一个d t d 的结构，图的结点是d i d 中的元素、属性以及 正则路径运算符，每一个元素在图中出现仅出现一次，属性和操作符在d t d 图 中出现的次数则与它们在d t d 中出现的次数相同；图的边则反映d t d 中元素之 间的嵌套关系；图中的环表示回路的出现。 根据d t d 图生成关系模式 依据一个d t d 图生成的关系是该d t d 图中每个元素所生成的关系的集合。 在说明生成一个元素的关系模式前，需要引入元素图的概念。简单地说，一个元 素的元素图就是从该元素出发以深度优先遍历d t d 图的过程中生成的一棵树， 其构造方法有： a ) 从待创建关系的元素结点开始对d t d 图作深度优先遍历，当首次访问某 个结点时则标记为“已访问”，而该元素结点的所有孩子结点均被遍历后则取消 它的标记。 b ) 若在遍历的过程中，d t d 图中一个未被标记的结点被访问，则在元素图 中创建一个同名的新结点，并创建一条从最近生成的结点到这个新创建的结点的 一条边。 c ) 若在遍历过程中到达一个已被标记的结点，则在元素图中创建一条逆向 边，从元素图中最近生成的结点到与已经标记了的d t d 结点同名的元素图中最 近生成的结点。 根据d t d 图生成关系模式的方法有：基本内联法、共享内联法和混合内联 法。 a ) 基本内联法 基本内联法是将元素图中的每个元素，根据它的元素图生成一个同名关系， 该元素的所有后继都作为同名关系的属性。但有两种情况除外：一是对于结点“幸 或“+ ”的直接孩子结点不包括在该关系中，即对于集合值孩子将另外生成一个 新的关系；二是遇到环的结点需要生成一个新的关系。 b ) 共享内联法 共享内联法确保一个元素结点出现且仅，出现在一个关系中，它按照如下的原 则来判断哪些元素可生成独立的关系模式：d t d 图中入度大于l 或等于0 的元 素结点；d t d 图中结点“宰”或者“+ 的直接后续元素结点；环结点且入度均 l o 第二章基于x m l 的关系数据库存储技术研究 为l 的元素结点；其余的结点均生成关系属性 c ) 混合内联法 混合内联法充分吸收基本内联法和共享内联法的优点，将所有入度大于l 的 元素结点也内联进父结点所生成的关系中，但是带回路的结点以及结点 或+ 的直 接后继结点除外。 ( 2 ) s c h e m a 数据模型及其映射方法【1 2 】 由于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 中的嵌套元素映射为关系模式。e b o h a n n o n 提出了p - s c h m a a 的概念。p s c h e m a 将原始x m ls c h e m a 中的值集合元素单独进 行处理。它的过程如下： 生成p - s c h e m a 。在p - s c h e m a 中用同名的复杂数据类型替换掉原始) 洲l s c h e m a 中的多值元素，即将x m ls c h e m a 中的所有多值元素抽取出来生成同名 的复杂类型。在其父元素类型定义中保留对新增类型的引用，这样p - s c h e m a 中 就不存在多值元素。 生成关系模式。根据p - s c h e m a 生成关系模式的规则如下：对于每个复杂 类型t 生成一个独立的关系r t ，同时为增加主键p k m - 保存结点i d ；再增加一 个外键t o p t - k e y 表示与关系r e r 的引用关系( p t 是t 的父类型) ；简单数据类 型定义的元素直接映射为对应关系的属性。 2 1 4 约束映射方法 结构映射算法从x m l 模式中的结构约束出发来推导关系模式，这种映射方 法保持了x m l 文档中的结构约束信息。在考虑结构约束信息的基础上进一步