（计算机系统结构专业论文）基于关系数据库的xml存储、查询与重构.pdf

i 、1 、。 j - 二i 独创性声明 舢ii|ii|iiiiii|川川if|fif10 y 18 0 2 6 8 8 本人声明所呈交的学位论文是本入在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：! 虽兰堡坠日期：2 。i 。年歹月2 2 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：世 导师签名： 支耄 日期：矿卜年孓月之乙日 摘要 摘要 x m u e x t e n s i b l em a r k u pi 肌g u a g e ，可扩展标记语言) 为网络传输提供了一种 便捷有效的数据格式，它是一种自描述的标记语言，能提供统一的数据说明方式， 可以描述任意数据逻辑关系。x l l 很快成为了i i l t e m e t 上数据表示、集成和交换 的标准，同时也促进了下一代网络的发展。如今，互联网上急剧膨胀的x m l 数据 带来了一个全新的研究领域x m l 数据管理。而借助关系数据库来管理x m l 数据是其中一个热门研究方向，这种方法可以利用关系数据库成熟的技术，例如 内存管理、查询服务、并发控制、数据恢复、访问控制及安全性等。然而具有层 次和嵌套的x m l 数据模型比二维平面式的关系模型复杂得多，要使用关系数据库 无损地存储和管理x m l 数据是一项十分困难的任务。 论文的目的是设计并实现一种通用的基于关系数据库的x m l 数据管理系统， 使之能有效应用于电子商务等领域。使用关系数据库管理x m l 的方法一般需要完 成三个步骤，论文分别针对这三个阶段作了一系列工作： ( 1 ) 模式映射利用x m l 模式信息生成关系模式以存储遵从该模式定义的 所有x m l 文档。论文首先提出一种改进的共享内联技术，它增加了d t d 简化规 则，并定义新的d t d 图模型和内联d t d 图模型。基于这些模型，模式映射算法 d t d 2 r s c h e m a 将d t d 转换成对应的关系模式和。映射。 ( 2 ) 文档映射将订l 文档存储到关系数据库中。为表示x m l 文档，首 先定义一种x m l 树模型，文档映射算法s a 胁0 c m a p 自顶向下遍历x m l 树为每 一个结点编码，同时利用。映射将结点信息映射到关系元组中。 ( 3 ) 查询映射将x m l 查询转换为关系查询，并在需要时将关系查询结果 重构成x m l 子树。在路径匹配阶段，定义一种断环d t d 图来管理d t d 中存在的 递归环路，利用这种断环d t d 图，路径匹配算法p a t h m a t c h i n g 可有效地找出递归 查询的所有匹配路径；在查询转换阶段，转换算法c o n v e n 2 s q l 以匹配路径为输 入并生成等价的s q l 查询；在x m l 重构阶段，首先通过算法s e s g e n 生成结构 编码序列，再由重构算法r e c o n x m l 将结构编码序列还原成x m l 文档。 所有算法都已在x m l 存取原型系统x 2 r 中实现。论文最后以m v s q l 作为后 台数据库从不同角度对x 2 r 进行测试和验证。实验证明，x 2 r 能够无损地存储 x m l 数据，且具有良好的可扩展性和高效的查询性能。 塑墨 一 一一一 关键词：x m l 关系数据库；映射；存储；查询 a b s t r a c t a b s t r a c t 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 ) p m v i d e sac o n v e n i e n t 锄de 骶c t i v ed a t a f b 册a tf o rd a t at m s m i s s i o no nt h ei l l t e m e t i ti sas e l f - d e s c r i b i n gm a r k u pl 觚g u a g e ， w h i c hp r 0 v i d e sau i l i f o m lw a yt 0d e s c r i b ed a t a 弱w e l l 鹤i t sl o 舀cr e l a t i o n x m li ss o p o p u l 盯t h a ti t i sc o n s i d e r c d 弱s t 锄d a r df b fd a t ar e p r e s e n t a t i o n ，i i l t e 伊a t i o n 觚d e x c h 卸g e t h ei i l t e m e t n o w a d a y s ，r a p i de x p 觚s i o no fx m ld o c l l m e n t s0 nt h c i i l t e m e tb r i n g san e wr e s e a r c hc h a l l e n g e ：x m ld a t am 卸a g e m e n t u s i n gr d b m s st 0 m 锄a g e 讧li so n eo ft o pr c s e a r c h 髂d u et 0r d b m s s m a t l l r et e c l i i l o l o 西e ss u c h 弱 m e m o r ym 柚a g c m e n t ，i i l q u i r ys e r v i c e s ，c 0 n c i l r r e n c yc 0 n t i o l ，d a t ar e c 0 v e 吼a c c c s s c o n 仃0 l 姐ds e c u r i t y h o w e v e r x 1 ld a t ai sn a t u r a l l yf a rm o r cc 0 啦p l e xt h 勰f l 鸸 嘶0 一d i m e n s i o n a lr c l a t i o n a ld a t a ni sd i f ! f i c i i l tt o 血da1 0 s s l e s sw a yt 0s t o r cx m l d o 伽m e n t st 0r d b m s s t h ep u 驴o ft h i st h e s i si st 0 d e s i 印觚di l i l p l e m 铋tac 0 删m o nx m l d a t a m 柚a g c m e n ts y s t e mb a s c d0 nr d b m s s ，t h a ti t 啪b ee 蠡f c c t i v e l ya p p l i c dt 0 e c 0 m m e r c c 锄d0 t h e re r e 勰t 1 l er d b m s b 弱e dm e t h o d sc a i lg e n e r a l l yb ed i v i d e di n t 0 t h r e ep h 弱e s ，0 u rw o r ki s 弱f o l l o w sa o c o r d i i l 百y ： s c h e m am a p p i n g ，ad a t a b 弱es c h e m ai sg e n e r a t e d 仃o mad t d t h es h a r e di n l i n i n g t e c l m i q u ei sf i r s t l yi m p r o v e db yi n c r e 嬲i n gt h ed t ds i m p l i f ! i c a t i o nm l e s t h 明，an e w d t d g r a p ha n di n l i n ed t dg r a p hm o d e li sd e f i n e d t h es c h e m am a p p i n ga l g o r i t h m ， d t d 2 r s c h e m a t a l 【e st h e s cm o d e l s 弱i n p u t ，锄d0 u t p u tt h er e l a t i o n a ls c h e m a 锄d s - m a p p i n gc o 盯e s p o n d i n gt 0d t d d o c l l m e n tm a p p i n 如x m ld o c i l m e n ti ss h r e d d e di i l t 0r e l a t i o n a l t u p l e sw h i c hi s t h e ni n s e n e di n t 0t h er e l a t i o n a ld a t a b 鹤ew h o s es c h e m ai sg e n e r a t e di nt h es c h e m a m a p p i n gp h a s e ak i n do fx m l t r e em o d e li sf i r s t l yd e f i n e dt op r e s e n tx m l d o c u m e n t ， t h e nt h ed o c i l m e n tm a p p i n ga 1 9 0 r i t h mw h i c hi sc a l l e ds a x d o c m a pu s e s 姐e 伍c i e n t t o p - d o w nt r e ct r a v e r s a la p p r o a c h f o re n c o d i n gn o d e s0 ft h ex m lt r e ea sw e n 弱 s h r e d d i n gt h e mi n t or e l a t i o n a lt u p l e s q u e r ) rm a p p i n g ，w h i c ht l a n s l a t e s 柚x m lq u e r yi n t oi t sr e l a t i o n a le q u i v a l e n t 如d r e c 0 n s t l l j c tx m ls u b t r e e sr o o t e da tm a t c h i n gn o d e si fn e e d e d i np a t hm a t c h i n gp h r a s e ， i i i 广_ t h ea 1 9 0 r i t h mp a t h m a t c l l i i l gt a k c st h eu n f o l d e dd t d 卿h w h i c hm 蛆a g e sa 1 1d t d c i r c l e s 弱i n p u ta n dg e n e r a t e ss i 】唧l ep a t hc x p r e s s e sw h e n t h e r ei sr c c u r s i o nb o t hm a n x m lq u e r y 卸di ni t su n d e d y i n gd 田d t l h e n ，a ns i m p l ep a t he x p r e s s e sg e n e r a t e dm p a t hm a t c h i n gp h r a s ea r e 仃a i l s l a t e d i n 幻r e l a t i o n a le q u i v a l e n tb yq u e r yt r a i l s l a t l o n a l g o r i t h mc o n v e r t 2 s q l w h e n i tc o m 髓t or e c o n s t n l c t i o n o fx m ls u b t r e e s ，t h e a l g o r i t h m r e c o n x m li s u s e d t or o c o n s t m c tt h ex m ls u b t r e e 丘o m t h e s t n l c t u r e e n c o d e ds e q u e n c cw h i c hi s al i s t0 f ) ( m lt r e en o d e sg e n e r a t e db y t n e a l g o r i t h ms e s g e n 触la l g o r i t h m sa b o v eh a v ei m p l e m e n t e di n 肌x m ls t o m g e & q u e r yp r o t o t y p e s v s t e mn a m e dx 2 r a tt h ee n do f t h i st h e s i sav 撕e t yo fe x p e r i i n e n t sb a s e do nm y s q l a r ed i s p l a y e d r e s u l t ss h o wt h a tx 2 r 咖s t o r ex m l d o c i l m e n t sw i t h o u ta n yl o s s ，锄d h a s9 0 0 ds c a l a b i l i t ya sw e l la se f f i c i e n tq u e r yp e r l b 锄a n c e k 0 y w o r d s ：x m l ；r d b m s ；m a p p i n g ；s t o r a g e ；q u e r y 目录 第一章绪论。 目录 1 1 1 研究背景和意义1 1 2 国内外研究现状2 1 2 1 纯x m l 数据库系统2 1 2 2x m l 广e n a b l e d 数据库系统3 1 2 3 商业数据库对x m l 的支持。5 1 3 本文研究内容和组织结构5 第二章x m l 相关标准和技术卅7 2 1 引言。7 2 2x m l 推荐标准7 2 2 1x m l 标准7 2 2 2x ：m l 语法8 2 2 3x m l 模式1 0 2 2 4x m l 查询语言1 2 2 2 5x m l 解析技术1 3 2 3x m l 编码技术1 5 2 3 1 全局编码1 6 2 3 2 局部编码1 7 2 3 3d e w e y 编码1 7 2 3 4p b i l r c e 编码1 8 2 4 本章小结2 0 第三章x 2 r 系统概要2 1 3 1 需求分析2 1 3 1 1 电子商务对数据管理的需求2 1 3 1 2x m l 存取系统需求分析2 3 3 2x 2 r 总体设计。2 4 第四章模式映射和文档映射2 7 4 1 引言2 7 v 厂 目录 4 2 改进的共享内联技术2 8 4 2 1d t d 简化规则2 9 4 2 2 创建d t d 图和内联d t d 图3 1 4 2 3 生成关系模式和s 映射3 5 4 2 4 寸论3 7 4 3 基于p b i t r e e 编码的文档映射算法s a x d o c m a p 3 8 4 4 本章小结。4 3 第五章查询映射与l 重构4 7 5 1 引言4 7 5 2 查询映射一4 8 5 2 1 路径匹配4 9 5 2 2 查询转换5 4 5 3x m l 重构技术5 9 5 3 1 生成结构编码序列6 0 5 3 2 文档重构6 3 5 4 本章小结6 5 第六章实验结果及分析6 6 6 1 实验环境6 6 6 2x 2 r 测试6 6 6 2 1 模式映射测试6 6 6 2 2 文档映射测试6 8 6 2 3x 2 r 查询测试6 9 6 3 本章小结7 3 第七章结论。 7 1 全文总结7 4 7 2 工作展望7 5 致谢。 参考文献 7 6 7 7 第一章绪论 1 1 研究背景和意义 第一章绪论 i n t e m e t 的迅猛发展催生了一批数量庞大的互联网应用，同时，互联网中的信 息量也急剧膨胀。曾经对万维网发展做出巨大贡献的h t m l 语言，由于自身的缺 陷，已经无法满足新型互联网应用的需要。在这种背景下，1 9 9 8 年2 月，可扩展 标记语言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 ) 作为w 3 c 推荐标准应运而生，并迅速 成为互联网中的世界语言。如今，x 】l 语言及相关技术已经遍及网络世界里的各 个角落。 同h t m l 一样，x m l 源自标准通用标记语言s g m u s t 觚d a r dg e n e r a l i z e d m a r l 【l l pl a n g u a g e ) ，它是s g m l 的一个子集。相对于s g m l 的庞大复杂，x m l 既 具易用性，又继承了s g m l 丰富的功能。x m l 是自描述的，它既包含语义信息也 包含结构信息，) ( 1 讧l 具有语法与语义分离，内容和表现分离的特性o ，它所拥有 的灵活性和可扩展性使它广泛地应用于各个领域【2 】：在数据交换方面，x m l 可以 为w 曲上的不同应用之间或应用与用户之间提供统一的数据交换格式；在数据表 示方面，x m l 与样式表c s s 一起使用时，能够为终端用户提供丰富的表示形式； 而在数据集成方面，x m l 既能表示严格的、绝对的内容又能表示灵活的、自由的 文本。 虽然x m l 功能强大，但它采用了最简单的格式文本格式，如果没有工具 对它进行解析，讧l 仅仅是一个普通的文本文件【3 1 。使用文件系统管理x m l 文 档无疑是非常低效的，它在并发、查询、安全性、大规模数据处理上均存在缺陷。 因此，需要一种有效的手段来管理x m l 文档。 一种很自然的想法是借助传统的关系数据库管理系统来管理x m l 数据，这种 方法至少有两个优点，首先可以利用关系数据库成熟的技术【钔，例如内存管理、查 询服务、并发控制、数据恢复、访问控制及安全性等，这些技术都是x m l 数据管 理系统所不可或缺的。借助关系数据库，可以降低x m l 数据管理系统的开发成本， 缩短开发周期，并规避不必要的风险。其次，传统关系数据库在数据管理和商业 应用中占据着统治地位，这种格局在未来很长时间内并不会发生改变【5 】。而随着 x m l 数据的异军突起，关系数据和x m l 数据的双向集成和转换不可避免。使用 r。 电子科技大学硕士学位论文 关系数据库管理删l 数据正好为两者的转换集成提供了基础和依据。事实上，人 们已经提出了“以关系数据库为存储手段，以x m l 为交换载体”的数据管理模式。 使用关系数据库方法来管理x m l 数据已然成为学术界和工业界的热门话题。 使用关系数据库管理x m l 数据的难点在于，关系数据库所采用的关系模型和 x m l 数据模型并不匹配【6 】：关系模型是一种二维平面模型，它不具有嵌套和顺序 特征，而x m l 数据模型是一种树模型，它能够进行任意嵌套，结点之间存在先后 次序。如何在不损失结构信息情况下实现两种数据模型的相互转换，是基于关系 数据库的x m l 管理方法不可避免的话题。 深入研究使用关系数据库管理x m l 数据是一项意义重大且具有挑战性的工 作，将关系数据库和x m l 有效结合，将同时推动两种技术进一步发展，具有广阔 的应用前景和经济效益。 1 2 国内外研究现状 目前，x m l 数据管理技术是数据库领域的研究热点，近年与x m l 数据管理 有关的论文在a c ms i g m o d 、v l d b 、正e ei c d e 等国际顶级数据库学术会议上 占据了半壁江山【4 1 。归纳起来对x m l 数据管理的研究主要有两种途径：一是纯 x m l 数据库系统( n a t i v ex m l d a t a b a s es y s t e m s ) ，二是x m l 使能( x m l 广e n a b l e d ) 数据库系统。 1 2 1 纯x m l 数据库系统 纯) ( 】l 数据库系统是为x m l 数据量身定做的数据库管理系统，其特点是充 分考虑x m l 数据自身的特点，以自然的方式处理x m l 数据1 7 j 。纯x m l 数据库 系统专门设计了适合x m l 存储和查询的数据模型和方法，从其底层核心直至查询 都采取了与x m l 数据直接配套的技术。 “n a t i v e 垤ld a 切b a s e ”这个术语最初是在s o f t 、) l ，a r ea g 公司为t a m i n 0 【8 】所 做的营销宣传中露面，由于它的成功，这个术语成为同类产品和技术的通用叫法。 除了t a m i n o ，比较著名的纯x m l 数据库系统还包括密歇根大学开发的量m b e r 【引、 开源系统e ) 【i s t 【1 0 1 、嵌入式x m l 系统b e r k e l e vd bx m l 【1 1 l 以及中国人民大学的 o r i e n t x 系统1 1 z 】。 纯x m l 数据库系统的一些重要特性使它能在内容管理系统中发挥巨大作用， 例如它具有灵活的数据模型来建模文本文档，能够基于x m l 进行全文搜索 2 第一章绪论 ( x m 【，删a r ef u l l t e x ts e a r c h ) 等。这些特性使得纯x m l 数据库系统很好地支持文本 文档或者说以内容为中心( t o p i c c e n t r i c ) 的x m l 文档的存储和检索【1 3 】。而传统的关 系数据库在这方面的能力显得捉襟见肘。 然而研究表明，在管理结构良好的以数据为中心( d a t a c e n t r i c ) 的x m l 文档时， 纯x m l 数据库的查询性能反而不如关系数据库，它在面对大规模甚至超大规模数 据时表现出来的可扩展性也不尽人意【1 4 l 。此外，纯x m l 数据库仅能处理x m l 数 据，它必须借助更多的工具才能满足应用的需求。最后，纯x l l 数据管理系统缺 乏明确的标准，至今还没有形成一个固定的模式规范，它的成熟还需要经过更多 的时间和考验，建立统一的标准已经成为纯x 1 l 数据管理系统发展的当务之急。 因此，纯x m l 数据库不是一把万能钥匙，它与关系数据库相结合已成为一种发展 趋势。 1 2 2x m l - e n a b l e d 数据库系统 近年来，使用关系数据库管理x m l 数据得到了国内外学者的普遍关注，他们 提出了很多的方法和原型，并做了大量的实验。归纳起来，这些技术按照将生成 关系模式时是否使用x m l 模式信息又可以分为两类【4 】：一是模型映射( m o d e l m a p p i n 曲，二是结构映射( s t m c t l i 他m a p p i n g ) 。其中模型映射将x m l 文档树结构映 射为关系模式，关系模式表示删l 文档模型的构造，由于是模式无关的，它对所 有x m l 文档都使用固定的关系模式。结构映射则是将x m l 模式映射为关系模式， 它为拥有不同模式的x m l 文档产生不同的关系模式。关系模式用来表示x m l 文 档的逻辑结构。 模型映射 学术界在无模式x m l 广r d b 映射技术研究方面十分活跃，文献【1 5 h 2 3 】是典型代 表，其中，e d g e l l 5 】方法提出一个x m l 文档能够用一个有序的有向边标记图来表示， 并以此为依据，创建固定的关系表存储x m l 所有边的信息和结点值。作者虽然给 出了该方法的查询测试结果，但没未给出实现查询的算法。x r e l 【2 伽，x p a r c n t 【1 9 】 与e d g e 方法不同，它们设计固定的关系模式来存储x m l 文档的结点信息，而不 是边信息。其中x r e l 通过存储x m l 文档的区间编码来保持它的结构信息，同时 它专门设计了p a t h 表存储x m l 文档中的所有路径。恐e l 实现了称为x p a t h c o r c 的船a t h 语言的核心子集，它能够对存储在关系数据库中的x m l 文档进行有效查 询。香港大学提出的a r e n t 方法通过d a t a p a t h 表来维护x m l 文档所有结点的父 3 电子科技大学硕士学位论文 子关系，为了判断数据路径，可能需要对这个表作大量连接操作。但它的一个优 点是，使用d i d 代替区间编码的( s 呲锄d ) ，这使得，a r e i l t 在查询时仅需要等值连 接，而不像x r e l 那样使用0 连接，这样就能有效利用传统的索引机制从而提高查 询速度。万常选等提出了x r e s t o i 迮1 2 2 j 方法，它是一种基于结点编码的方法，但 容纳了其他很多技术，它在关系库中为x m l 文档建立了一种称为扩展先序列表的 索引结构，这种索引可加速路径表达式的计算，并支持x m l 文档的关键词搜索。 在查询方面，x i 逻s t o r e 改进了x r e l 的查询算法，实现了x p a t h 的一个核心子 集。 结构映射 文献【2 4 1 。【3 1 】的研究属于结构映射的范畴。其中，文献【2 4 1 提出了从d t d 中抽取 x m l 文档的结构信息，并以此生成好的关系模式的存储策略。其基本思路是首先 基于简化规则对d t d 进行简化，然后根据简化后的d t d 生成一个d t d 图，最后 再根据d t d 图中各种元素的关系产生一系列相关的关系模式。文献1 2 4 】讨论了三种 可行的元素内联法基本内联法、共享内联法和综合内联法。基本内联法尽可 能将一个元素的所有子孙都内联到一张表中，但同时还为每一个元素类型创建一 个独立的关系表，这种方法的缺点是将导致创建出大量的关系表，不便维护。共 享内联法和综合内联法的区别是在入度大于1 的d t d 图结点的处理上，共享内联 法为这种结点产生一个单独的关系表，而综合内联法则与基本内联法类似，它将 入度大于1 的结点内联至它所有父结点所在的关系表中。 文献【2 5 】针对共享内联法的不足，提出了一种改进的内联方法，它降低了共享 结点的存储冗余。周傲英l 冽则指出，共享内联法和综合内联法对入度大于1 的结 点的映射规则过于简单，这会影响查询效率。其次，如果关系模式固定，当查询 所访问的关系表中存在过多的无关数据时，其效率也会降低。从这两点出发提出 了一种存储模式的自适应调整机制，其依据是根据历史查询判断结点和父结点关 系的紧密程度，来决定采取共享内联法还是综合内联法。并采取冗余存储或者对 关系表进行垂直分割的方式来提高查询效率。这些研究的一个共同缺陷是没有提 及对混合内容元素的文本片段的支持。当d t d 中存在混合内容元素时，使用这些 技术产生的关系模式将无法保存混合内容元素的文本顺序，甚至会丢失混合内容 元素的文本内容。 自由撰稿人r o n a l db o t 脓t1 3 1 】提出了结构映射的另外一种不同的思路，这种方 式称为对象关系映射法，它分为两步，首先将x m l 模式映射为对象模式，再将 4 第一章绪论 对象模式映射为关系。这种方法的特点是利用了高级语言中对象的概念，其产生 的关系模式中使用大量的外键约束来表示x m l 的结构信息。 在x m l 查询方面，文献1 2 4 1 仅介绍了如何将x m l 广q l 查询翻译成s q l ，但没 有具体算法描述。文献【1 3 l 没有借助x m l 查询语言，而是使用d t d 定义了一个称 为a c t i o n 的语言，来指示系统如何对关系数据库进行操作。这种方式使用困难且 不具通用性。文献【3 2 l 【3 3 1 都借助了关系数据库某些特殊支持来实现递归d t d 上的 递归查询，其中文献1 3 2 】使用s q l9 9 的w i t h 语句，而文献1 3 3 】所提出的方法需要关 系数据库支持册运算符。然而目前并不是所有数据库都提供了上述两种特殊功 能，使得这些方法的通用性大打折扣。文献【矧提出将递归d t d 图中的所有环路断 开，可简化递归查询的处理，但没有给出简单路径匹配算法。 相对于模型映射的固定关系模式，结构映射法的优势是它利用了x m l 模式信 息来生成一个最适合的关系模式。使用它进行x m l 文档存储产生的文档片段较 少，在遍历路径时所需要的关系表的连接操作也相应减少，因此查询效率相对模 型映射要高。文献【3 5 】研究了不同存储方法的性能，结果表明，当存在d t d 时，采 取结构映射法能获得最高的查询效率。 1 2 3 商业数据库对x m l 的支持 目前，主流的商业数据库如m ss q ls e e r 、o r a c l e 、m md b 2 等都不同程度 地提供了对x m l 数据的支持【3 6 j - 矧。在s q l s e r v c r2 0 0 5 中，对x m l 的支持已经 集成到数据库本身的所有组件中。主要包括：支持x m l 格式的数据类型、实现了 x q i l e r y 以及增强了对x m l 操作语句和函数的功能。o r a c l e 针对不同x m l 的格式 要求，实现了几种x 舭存储策略：使用c l o b 对象进行非结构化存储；专门针对 x m l 数据设计的分析后二进制存储以及使用对象关系模型对x l l 进行基于模式 的关系存储。d b 2v 9 则摒弃了关系模型，在底层使用了层次模型来支持x m l ， 它提供了纯x m l 数据库类似的方法，d b 2 也因而变成了一种兼容关系模型和层次 模型的混合数据库。 1 3 本文研究内容和组织结构 x m l 存取原型系统x 2 r 本质上属于基于关系数据库的结构映射方法，论文以 x m l 数据在关系数据库中的“存储一查询一重构为主线，详细阐述原型系统 x 2 r 实现的各种算法，主要内容有： 电子科技大学硕士学位论文 ( 1 ) 模式映射。首先针对现有共享内联技术的不足，提出一种改进的共享内联 技术，它增加了d t d 简化规则，并定义新的d t d 图模型和内联d ，m 图模型，这 种内联d t d 图模型能够完整保存混合内容元素的所有文本片段并有效处理集合类 型属性。然后阐述了x 2 r 的模式映射算法d t d 2 r s c h e m a ，它以d t d 作为输入， 生成对应的关系模式和。映射。 ( 2 ) 文档映射。对比研究了几种流行的文档编码方案，并选取比较优秀的 p b i t r e e 编码来表示x m l 文档结构。p b i t r e c 编码是一种虚拟中序编码，这与s a x 解析x m l 采用的先序事件流不匹配，因此x 2 r 定义一种x m l 树模型来保存x m l 文档所有结点的编码和数据信息，这种逻辑树模型可采用d o m 和s a x 构建。x 2 r 的文档映射算法s 6 d o c m a p 自顶向下遍历x m l 树为每一个结点进行p b i t r e e 编 码，同时通过。映射将结点映射关系元组中，当一个关系元组所有相关结点都已 映射完毕，再将它插入到关系数据库。 ( 3 ) 查询映射。x 2 r 的查询映射分为路径匹配和查询转换两个阶段。路径匹配 算法p a t h m a t c h i n g 使用断环d t d 图来管理d t d 中存在的递归环路，并借助数据 结构r e c o r d e r 来处理递归d t d 图中的递归查询；查询转换算法c o n v e r t 2 s q l 则利 用。映射将路径匹配产生的简单路径表达式转换成s q l 查询。 ( 4 ) x m l 重构。查询映射仅返回结果结点的p b i t r e e 编码，因此还需要构造以 结果结点为根的x m l 子树。x 2 r 利用结构编码序列的概念进行x m l 文档重构， 首先由结构编码序列生成算法s e s g e n 从关系数据库查询结果结点的所有子孙结 点，并按照它们先序编码顺次排列形成结构编码序列，然后使用重构算法 r e c o n x m l 将结构编码序列还原成x m l 文档。 论文还从不同角度对x 2 r 进行测试和验证，分析了实验结果。最后提出几种 可改进的方案。 论文的后续章节安排如下： 第二章介绍本研究的背景知识。 第三章对原型系统x 2 r 的整体框架结构进行简要说明。 第四章论述了x 2 r 的模式映射技术和文档映射算法。 第五章阐述x 2 r 的查询映射和x m l 重构算法。 第六章从各种角度对) 【2 r 进行测试并分析结果。 第七章总结全文，并展望进一步工作。 6 第二章x m l 相关标准和技术 2 1 引言 第二章瑚l 相关标准和技术 目前已经制定出了很多与x m l 相关的规范和推荐标准，其中有些标准和技术 与论文的研究以及x 2 r 系统的设计和实现直接相关，它们是论文研究的基础。本 章主要描述与论文直接相关的这些x m l 标准和技术，但为了对比，也对某些无关 标准和技术做简要介绍。 2 2x m l 推荐标准 2 2 1x m l 标准 h t m l 和x m l 的成功可归功于它们的标准化。任何人只要遵从规范和解决方 案，就可以实现互操作。万维网联盟删b d dw i d ew 曲c o 璐o n i u m ，w 3 c ) 是h t m l 和x m l 标准的制定者。它对x m l 是这样描述的：“x m l 是s g m l 的子集，其目 标是允许普通的s g m l 在w - e b 上以目前h t m l 的方式被服务、接收和处理。x m l 被设计成易于实现，且可在s g m l 和m m l 之间相互操作。一w 3 c 制定标准是一 个开放的过程，任何公司和个人都可能成为w 3 c 组织制定标准的成员，这种开放 互惠的精神使得w 3 c 的标准被引用得非常普遍。 x m l 要想达到组织信息的目的，仅是定义一套语义标记的规则是远远不够的。 目前已经制定出了很多相关的规范和推荐标准，它们共同组成了x m l 的全部技 术。每一个规范仅仅涉及到信息交换的其中一个方面。下面列举其中几个重要的 规范： ( 1 ) x m l1 0 ：它是整套x m l 技术最底层的推荐标准，其他的规范都建立在它 之上。它规定x m l 文档必须遵从的语法、x m l 解析器必须遵守的规则以及读取 x m l 文档需要知道的规定。 ( 2 ) d t d 和模式( s c h e m a ) ：因为x m l 允许用户自定x m l 文档的结构以及元素 标签，d t d 和模式( s c h e m a ) 分别提供了一种定义文档类型的方式。使用它们可以 提供对x m l 文档的有效性检查，确保不同用户创建格式兼容的x m l 文档。 7 电子科技大学硕士学位论文 ( 3 ) a t h ：一种讧l 查询语言，它提供了在x m l 文档中检索某一片段的功 能。应用程序可以使用a t h 读取x m l 文档中想要的内容，而无需读取整个文档。 ( 4 ) x q u e r y ：是另外一种x m l 查询语言，比x p a t h 更复杂。它提供了一种直 接从w 曲上的x m l 文档查询数据的方法。 ( 5 ) d o m ：文档对象模型( d o m c u m e n to b j e c tm o d e l ，d o m ) 的制定是为了方便 应用程序访问x m l 文档，它定义了一组访问x m l 文档的接口。与d o m 功能类 似的还有x m l 的简单应用程序接口( s i i l l p l ea p if o rx m ls a ( ) ，但它提供了与 d o m 风格迥异的x m l 访问方式。 ( 6 ) 其他：还存在很多针对各种x m l 技术的规范和推荐标准以及针对某个具 体x m l 文档类型的规范。如命名空间、有显示功能的c s s 、兼有显示和转换功能 的x s l 、h t m l 的x m l 版本x h l m l 、有内容聚合功能的r d f 站点摘要( r d fs i t e s u m m a r ) r ，r s s ) 以及描述二维图形的可缩放矢量图形( s c a l a b l ev e c t o rg r a p h i c ，s v g ) 规范等。这些标准和本文研究内容无直接关系，因此不再作详细叙述。 2 2 2 坦l 语法 x m l 文档是一种树状结构。w 3 c 对x m l 文档的定义是：一个数据对象是一 个x m l 文档，首先它必须是良构的( w e l l f 0 珊e d ) ，其次，一个良构的x m l 文档 满足某种文档类型定义或者模式的约束条件才称为有效的x m l 文档。 x m l 文档在物理结构上由一些实体单元构成。一个实体可引用其他的实体， 一个x m l 文档从文档实体( 或称为根) 开始。从逻辑结构角度出发，x m l 文档由声 明、元素、注释、引用和处理指令组成。x m l 文档的物理结构和逻辑结构都必须 正确地嵌套。图2 1 给出了一个x m l 文档实例。 只有良构的x m l 文档才能被x m l 解析器所识别。一个良构的x 1 l 必须满 足以下规则： ( 1 ) x m l 文档必须以x m l 声明作为开始。x m l 声明可以看作是一个特殊的 处理指令，它的开始和结束界定符分别为“ ，“x m l ”为处理指令的名 称，它有一个必须的属性“v e r s i o n ”以及可选属性“e n c o d i l l g 和“s t 锄d a l o n e 等， 如图2 1 所示，第1 行为该订l 文档的声明部分。 ( 2 ) 一个x m l 文档有且仅有一个