（计算机应用技术专业论文）基于纯xml数据库natix系统存储技术研究.pdf

哈尔滨- ：稃火学硕十学何论文 摘要 随着x m l 相关标准的推广与应用，w e b 上出现了大量的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 和纯x m l 数据库等基础知识入手，分析了x m l 数据在原 生数据库的存储方式，并深入研究了纯x m l 数据库n a t i x 系统。发现其中存 在的问题，记录之间往往要保存一定数量的“结构信息”以保证数据还原的 正确性，这就使得记录之间不是相互独立的，记录间的不独立将会影响到 x m l 更新的效率。本文针对n a t i x 系统不足之处进行改进，将改进后的系统 命名为n a t i x u p 系统，它可以完全保留x m l 树结构信息，同时具有如下特 点：为便于查询结点结构信息并有效支持更新，对x m l 文档数据给出基于 前缀整除的编码方案；存储记录问相互独立，进行更新时可以减少x m l 存 储及索引的修改，减少了更新的代价；并给出一种基于空间利用率的x m l 存储更新算法及基于父子关系聚簇的分裂子树算法。n a t i x u p 系统能够从理 论上有效的支持更新。 最后，通过实验对n a t i x u p 系统进行了验证，实验结果表明，n a t i x u p 系统和n a t i x 系统相比较具有较高的更新效率。 关键词：x m l ：纯x m l 数据库；存储；树形结构：结点；索弓 哈尔滨i i 稃人学硕十学位论文 a b s tr a c t w i t ht h eg r o w i n gp o p u l a r i t ya n da p p l i c a t i o no fx m lr e l a t e ds t a n d a r d s ，l a r g e r e p o s i t o r i e so fx m l d o c u m e n t sh a v ee m e r g e do nt h ew e b i ti sn e c e s s a r yt os t o r e t h e s ed o c u m e n t si n t oad a t a b a s et om a k et h e mm a n a g e a b l e s t o r a g es c h e m e sh a v e b e c o m ea ni m p o r t a n tr e s e a r c ht o p i ci nt h ex m ld a t am a n a g e m e n tf i e l d n a t i v e x m ld a t a b a s ec o u l dt a k ei n t oa c c o u n tt h ec h a r a c t e r i s t i c so fx m ld a t af u l l y , d e a l w i t l lt h ex m ld a t ai nan a t u r a lw a y , s u p p o r ts t o r a g ea n dq u e r yw e l li na l l a s p e c t s ，a n d a c h i e v eg o o dr e s u l t s t h e r e f o r e ，t h en a t i v ex m ld a t a b a s es t o r a g e m e a n sa g r e a td e a lo fr e s e a r c hv a l u e t h i st h e s i si sb a s e do na c k n o w l e d g eo fx m la n dr e l a t i o nd a t a b a s e ， a n a l y z e st h es t o r i n gm e t h o do fx m l d a t ai nn a t i v ex m ld a t a b a s ea n dr e s e a r c h e s d e p p l yn a t i v ex m ld a t a b a s en a t i x b u tt h e r ea r e s t i l ls o m ep r o b l e m s ：r e c o r d s o f t e nh a v et os a v eac e r t a i nn u m b e ro f “s t r u c t u r ei n f o r m a t i o n ”t oe n s u r et h e a c c u r a c yo ft h ed a t ar e d u c t i o n ，t h i sm a k e st h a tr e c o r d sa r en o ti n d e p e n d e n to f e a c h o t h e r , a n dn oi n d e p e n d e n c eb e t w e e nt h er e c o r d sw i l la f r e c tt h ee f f i c i e n c yo f u p d a t i n gx m l t h i st h e s i si m p r o v e sn a t i xa c c o r d i n gt oi n a d e q u a c i e s o ft h e s y s t e m ，n a m e d t h ei m p r o v e dn a t i xs y s t e mn a t i x u p s ow h i l ek e e p i n gt h e s t r u c t u r er e l a t i o nb e t w e e nt h en o d e s ，n a t i x u pa l s od o e st h ef o l l o w i n gt h i n g s ：i n o r d e rt oq u e r yt h ei n f o r m a t i o no ft h en o d es t r u c t u r ef a c i l i t a t e l ya n ds u p p o r tf o r u p d a t i n g x m lf i l e e f f e c t i v e l y , i n t h i st h e s i s ，an e w c o d i n g s c h e m ei s p r o p o s e d ，w h i c h i sn a m e da sp r e f i xd i v i s i o nc o d i n gs c h e m e ；t h er e c o r d sa r e i n d e p e n d e n t ，w h i c h c a l lr e d u c et h em o d i f i c a t i o nt ot h es t o r a g ed a t aa n di n d e xa f t e r u p d a t e ，t h a tw e c a nr e d u c et h eu p d a t ec o s t ；an e wu p d a t ea l g o r i t h mw h i c hi sb a s e d o nt h es p a c eu s a g er a t i oa n dan e ws p l i t - t r e ea l g o r i t h mw h i c hi sb a s e do nt h e r e l a t i o n s h i pb e t w e e nf a t h e ra n ds o nc l u s t e r i n g 。i nt h e o r y , n a t i x u ps y s t e mc a n s u p p o r tt h eu p d a t e se f f e c t i v e l y a tl a s t ，t h i st h e s i sv e r i f i e st h ei m p r o v e m e n to ft h en a t i x u ps y s t e mt h r o u g h 哈尔滨下程人学硕十学何论文 e x p e r i m e n t s t h er e s u l t ss h o wt h a t t h e n a t i x u ps y s t e mh a sb e t t e ru p d a t e e f f i c i e n c yc o m p a r e dw i t ht h en a t i xs y s t e m k e y w o r d s ：x m l ，n a t i v ex m ld a t a b a s e ，s t o r a g e ，t r e es t r u c t u r e ，n o d e ，i n d e x 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体己经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：伤丹 日期：2 川年弓月，日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 、 厂。b 作者( 签字) ：仿廿导师( 签字) ：蒙法王 日期：沙嘭年弓月i 日冽年专月力日 |1 哈尔滨工程大学硕士学位论文 一i | 1 i i ii - _ _ _ 1 1 引言 第1 章绪论 互联网自上世纪八十年代开始，经过二十几年的发展，已经成为新经济 时代的标志，它遍及到人们的生活、工作和学习当中，甚至引起了人们思维 观念的转变。互联网的飞速发展，很大程度归功于简单易学的 h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本标记语言) 的广泛应用，它使得非 专业人士能轻松构建自己的网站。删，是欧洲粒子物理研究中心的研究人 员t i mb e m e r sl e e 于1 9 8 9 年设计的，它是基于s g m l 的超文本版本。 h t m l 继承了s g m l 的结构化、实现独立和可描述等特点，同时对s g m l 作了极大简化。它还引入了超链接概念，使用尖括号作为标记以便任何文本 编辑器都可创建。伴随着互联网的发展h t m l 成为了主要的信息发布形式。 h t m l 以其简单易学、灵活通用的特性，使人们发布、检索、交流信息 都变得非常简单，从而使w e b 成了最大的环球信息资源库。然而，电子商 务、电子出版、远程教育等基于w e b 新兴领域的全面兴起使得传统的w e b 资源更加复杂化、多样化，数据量的日趋庞大对网络的传输能力也提出更高 的要求。同时，人们对w e b 服务功能的需求也达到更高的标准，比如：用 户需要对w e b 进行智能化的语义搜索和对数据按照不同的需求进行多样化 显示等个性化服务；企业要为客户创建和分发大量有价值的文档信息，以降 低生产成本，以及对不同平台、不同格式的数据源进行数据集成和数据转化 等等，这些需求越来越广泛和迫切。 传统的h t m l 由于自身特点的限制，不能有效地解决上述问题。尽管 h t m l 推出了一个又个新版本，已经有了脚本、表格和帧等功能，但始终 满足不了不断增长的需求。另一方面，这几年来计算机技术的发展也十分迅 速，已经可以实现更为复杂的w e b 浏览器，所以开发一种新的w e b 页面语 言既是必要的，也是可行的。有人建议直接使用s g m l ( s t a n d a r d i z e d g e n e r a l i z e dm a r k u pl a n g u a g e ) 作为w e b 语言，这固然能解决h t m l 遇到的 哈尔滨工程大学硕士学位论文 困难，但是s o m l 太庞大了，用户使用不方便。而且，要全面实现s g m l 的 浏览器就非常困难，于是人们自然会想到仅仅使用s g m l 的子集，使新的 语言既方便使用又实现容易。正是在这种形势下，w e b 标准化组织 w 3 c ( w o r l dw i d ew e bc o n s o r t i 哪，全球互联网联盟) 建议使用一种精简的 s g m l 版本一l 1 】( 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 是由w 3 c 于1 9 9 8 年2 月发布的一种标准。它同样是s g m l 的一个简化子 集，它将s g m l 的丰富功能与h t m l 的易用性结合到w r e b 的应用中。 x m l 应用的飞速发展使得x m l 有关的数据和文档大量出现，这种需求要 求以数据库方式实现x m l 数据的有效存储管理。在传统数据库厂商纷纷支持 x m l 的同时，一种专门用于处理x m l 的数据库n a t i v ex m l 数据库正在 快速发展，已经成为一个新的研究热点。纯x m l 数据库充分考虑到儿数据 的特点，以一种自然的方式来处理x m l 数据，能够从各方面较好地支持x m l 的存储和查询，并且能够达到较好的效果，但是，纯x m l 数据库要走向成熟 还要有很长的路。 底层存储和索引策略是n a t i v ex m l 数据库的核心技术之一。一个良好的 底层存储和索引策略，是n a t i v ex m l 数据库进行高效的查询和读写的关键。 但是一个成功的数据库系统要高效的支持更新，目h - 盯n a t i v ex m l 数据库实例 对x m l 数据的更新情况并不好，对支持高效更新情况的存储结构的研究是很 有价值的。 1 2 x m l 存储技术的研究现状 目前x m l 数据的存储方式有：文本文件方式、关系数据库方式、对象数 据库方式和纯x m l 数据库方式。 1 文件系统 使用文件系统来存储x m l 就是把x m l 直接存储为文本文件，访问时首先 通过文件系统的目录结构，然后通过儿文档的元素结构来提供对数据的层 次访问。基于文件的x m l 系统简单而容易实现，无需使用底层的数据库或对 象存储管理。同时由于x m l 文档被直接存储为文本文件，文件存储方式无需 存储转换和重构查询结果。 2 哈尔滨工程大学硕士学位论文 2 关系数据库 将x m l 存储到关系数据库中就是利用x m l 文档模式信息设计关系表结 构，然后解析x m l 文档，结合模式信息，将x m l 的内容分别存储到对应的 关系表中。利用关系数据库系统来处理x m l 数据的方式具有如下的优点：一 方面，当前的关系数据库的技术十分成熟，商用关系数据库系统都具有高性 能的查询引擎，良好的可扩展性、安全性和健壮性，因此利用关系数据库系 统管理x m l 数据可以重用数据库的查询优化器和事务处理机制，能够保证 x m l 数据的一致性和完整性；另一方面，目前大量的w e b 数据主要存放在 关系数据库中，采用龇一关系系统便于在关系数据库上建立适于二者的应 用，使关系数据库进入w e b 领域成为可能。 实现舳文档在关系型数据库中的存储，关键是要弄清楚x m l 结构与 关系型数据库结构之间的映射。其过程一般是：先创建用于存储x m l 文档的 r d b 模式；然后拆分x m l 文档，将其中的数据存储于已创建的r d b 模式。对 数据的操作既可使用x m l 方法( 如：x p a t h ，d o m 或s a x ) ，也可用数据库 方法( 如：s q l ) ，数据库中基本的存储单元独立于程序实现。 3 面向对象数据库 面向对象的x m l 存储方法以对象数据库作为底层存储，在面向对象数据 模型中，所有现实世界中的实体和概念都模拟为对象，利用面向对象数据库， x m l 将不再被拆分而是被描述成一个对象存入数据库。面向对象的方法首先 建立x m l 数据的o o d b ( 面向对象数据库，o b j e c t - o r i e n t e dd a m b 弱e ) 模式， 再将文档按照一定的规则将x m l 文档的元素映射成为对象数据库中的一系列 对象。x m l 文档结构中的元素和属性被映射成类或列，元素和属性的关系被 映射为类和列之间的关系，元素间的关系则映射为类间的关系。面向对象的 存储方法支持复杂数据类型，可以较为直观地建立) ( m l 数据的对象模式，从 而可以利用对象查询语言( o o l ) 实现对x m l 数据的结构化查询，具有较高的 存储与查询效率。 4 纯x m l 数据库存储 纯x m l 数据库( n a t i v e x m ld a t a b a s e ) 的基本存储单元是x m l 文档， 通过帆相关的标准进行数据库的存储。这种数据库维持原有x m l 文档的 数据结构和相关的元数据，而不关心数据的底层存储格式，只能通过帆特 3 哈尔滨工程大学硕士学位论文 i i i 有的相关技术对数据进行存储。近来出现了一些这样的数据库系统，如： t a m i n o ，n a t i 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 文档。 5 x l v i l 数据存储对比分析 以上4 种是目前x m l 数据存储的主要方法，从表1 1 中可以看出不同存储 方法具有不同的特点，在基于文件系统存储中，由于访问时需要加载整个文 档并读入内存，数据大小受到内存的限制，且不能直接对x m l 中的元素进行 访问，和其他方法相比灵活性不够。在基于数据库的存储方法中，存储则受 到d b m s 的数据模型和系统映射x m l 文档方法等因素影响。由于从x m l 数据 映射到关系数据表容易实现，目前大多数存储策略是基于关系数据库的，少 数是面向对象数据库的。应用数据库技术的优点是能够让系统充分利用数据 库管理系统本身的许多性能，比如说数据的可靠性、并发控制和数据恢复等。 用数据库方法存储x m l 时需要对x m l 内容进行拆分，这也使得数据处理时 相对低效。与此相反，n a t i v o - - - x m l 数据存储是完全以x m l 格式进行信息存 入和取出的，所以存取速度较快，有高效的空间利用和灵活性。 表i 1 舭存储方法对比 存储方法存储格式主要优点主要缺点 文件系统a s c 文本文件、易管理、易存储、适用于访问和更新困难 b l o b s 或c l o b s x m l 数据文档较小时 关系数据库 表 具有可扩展性、可靠性、简单的查询也要 强大的安全机制多重链接来实现 o o 数据库表和对象易实现、支持抽象数据类x y l 文档分解困难 型 n a t i v e - x m 艮 特殊抽象数据类型具有灵活性、有很高的访和商业数据库比 或典型数据库类型问和查询速度 还不够成熟 通过儿主要存储方法的对比，可以看出纯l 擞据库系统还不成熟， 数据处理的效率也差强人意，还需要进一步的研究，但是与传统数据库相比， 4 哈尔滨工程大学硕士学位论文 原生x m l 数据库具有以下优势： ( 1 ) 原生x m l 数据库在异构数据库的共享、移植性等方面具有传统数据 库无法比拟的优势。如果需要在已有的传统数据库中提供x m l 访问时，可选 用原生x m l 数据库。 ( 2 ) 由于x m l 数据库是基于层次数据模型的，因此开发模式较简单，或 者数据本身就具有层次模型特点，原生，数据库存取速度更快。 ( 3 ) 对基于w e b 的数据库开发，将x m l 数据库与w e b 服务器结合，可实 现动态的数据处理。因此原生x m l 数据库在i n t e r n e t i n t r a e t 开发中得到广泛的 应用。 因此原生的x m l 数据库存储技术必然成为x m l 存储发展的趋势。 1 3 论文主要研究内容及组织结构 本文立足于纯x m l 数据存储领域，主要阐述了目前比较成功的纯x m l 数据库系统n a t i x 存储的相关技术，由于原n a t i x 的存储记录不独立，其更 新代价很大，本文以此为基础进行改进，将改进后n a t i x 系统命名为n a t i x u p 系统即具有一种支持高效更新的存储结构的n a t i x 系统。本文的研究内容主 要包括以下几个方面： ( 1 ) 分析了x m l 数据存储技术的研究现状，对不同的存储策略分析了 它们的优缺点，得出纯x m l 数据库是x m l 存储技术的发展趋势，了解x m l 及其相关的基本概念和基本技术，为课题的研究奠定理论基石。 ( 2 ) 研究x m l 数据在纯x m l 数据库中的存储方法，并基于高效更新深 入分析了纯x m l 数据库n a t i x 系统存储的相关技术。n a t i x 系统存储方法的 关键问题是存储记录之间的独立性很差，更新代价高，所以将其存储结构进 行改进，将存储记录的地址处转换为相应的编码进行存储，给出了基于前缀 整除编码方案，通过建立索引引进编码到地址的映射关系。而且原n a t i x 系 统插入结点的存储算法中分裂矩阵、分裂轴、分裂容忍度这些参数具有动态 不稳定性，给出基于父子关系的聚簇算法及更新存储算法。对改进后的n a t i x 系统n a t i x u p 进行详细的分析研究。 ( 3 ) 设计实验，验证改进的可行性，最后通过对实验结果数据的分析， 哈尔滨工程大学硕士学位论文 评价n a t i x u p 系统的性能，利用v c + + 6 0 进行实验验证。 本论文组织结构如下： 第1 章分析课题的来源和背景以及x m l 文档数据存储技术的研究现状， 阐述了纯x m l 数据库发展的必然性，确定课题的研究内容。 第2 章了解x m l 基础包括文档结构和特点等，同时研究了纯x m l 数 据库概念及其存储的相关技术。 第3 章阐述了纯x m l 数据库n a t i x 系统的系统结构，基于高效更新研 究了其存储的相关技术包括解析技术，编码方案，存储结构及其索引结构。 通过对n a t i x 系统的研究指出n a t i x 系统的不足，为第四章n a t i x u p 系统奠定 了基石。 第4 章阐述了n a t i x u p 系统对n a t i x 系统改进的具体实现方案，得出 n a t i x u p 是一种支持高效更新的纯x m l 数据库系统。 第5 章阐述实验数据的来源和实验环境的大致情况，最后介绍实验的过 程及对实验的结果进行分析。 6 哈尔滨工程大学硕士学位论文 第2 章纯x m l 数据库技术的研究 2 1x m l 文档及其特点 1 舭文档简例 如果一个文本对象满足下列条件，那么它是一个规范的x m l 文档，它匹 配文档( d o c u m e n t ) 产生式： d o c u m e n t ：= p r o l o ge l e m e n tm i s c 它满足x m l1 0 规范中定义的所有规范性约束，此文件中直接或间接地 引用每一个已解析的实体都是规范的。 匹配文档产生式意味着这个文档包含一个或多个元素，有且仅有一个称 为根( r o o t ) 或文档元素的元素，它不出现在其他任何元素的内容( c o n t e n t ) 中。 对于其他所有元素，如果起始标签在另一个元素中，则其结束标签也在同一 元素的内容中。换一个更简单的说法，以起始标签和结束标签为界的各个元 素，必须严格的嵌套。下面给出一个规范的x m l 文档。 序言 主体 j a c k x m l z u o d a n p a p e r 7 哈尔滨工程大学硕士学位论文 尾声 2 x m l 文档的构成 声明( d e c l a r a t i o n ) ：x m l 文档以一个x m l 声明开始，用来说明关于文 档的基本信息。 元素( e l e m e n t ) ：x m l 文档的基本单元。一个x m l 元素由开始标签 ( s t a g ) 、结束标签( e t a g ) 以及标签之间的数据构成，元素标签的格式与h t m l 中的标签格式相同。舳文档数据必须包含在一个单一元素中。这个单一 元素称为根( r o o t ) 元素，或文档实体。文档实体代表整个文档的内容。 一个x m l 文档的核心是它的元素( e l e m e n t ) ，元素的定义为： e l e m e n t ：= e m p t y e l e m t a g l s t a gc o n t e n te t a g 一个x m l 元素由开始标记和结束标记来定界，在开始标记和结束标记 之间是元素的内容( c o n t e n t ) ；如果元素为空，则用空元素标记( e m p t y e l e m t a g ) 来表示。一个元素的内容可以是一个或多个子元素。 属性( a t t r i b u t e ) ：一个元素可以包含一个或多个属性，属性是一个在元素 的开始标签中的属性名称一属性值对。属性有两个规则，属性必须有值，值 必须用引号括起。x m l 有3 种类型的属性，字符串类型( s t r i n g t y p e ) 、记号 类型和枚举类型。字符串类型可以以任意的常量字符串作为值，各个记号类 型有不同的词法和语义约束。 字符数据( c h a r a c t e rd a t a ) ：x m l 文档中除去标记的部分就是字符数据。 一般的字符用它本身来表示，对于x m l 中的保留字则需要用字符引用或相 应的特定字符串来表示。 引用( r e f e r e n c e ) ：包括实体引用( e n t i t yr e f e r e n c e ) 和字符引用( c h a r a c t e r r e f e r e n c e ) 。实体引用以“& 开始，以“； 结束，中间是引用的实体名。字 符引用代表了i s o i e c l 0 6 4 6 字符集中的一个特定字符，它是一个十六进制 代码。 c d a t a 段( c d a t as e c t i o n ) ：是一段字符序列，以“ 一结束，中间为字符内容。c d a t a 段中的内容不被解析器所解析， 为x m l 的后续处理提供了编程接口。 哈尔滨工程大学硕士学位论文 处理指令( p r o c e s si n s t r u c t ) ：是x m l 文档中为应用准备的指令，以 结束，中间是处理指令目标。处理指令并不是x m l 文档中的字符数据， 它的作用是为解析器和其他应用程序提供信息。 注释( n o t e ) ：可以在标记之外的任何地方增加注释，以“ 一结束，中间是注释内容。为了保持兼容，在注释中不能加入“一 一”。 3 x m l 特点 x m l 不仅提供关于数据本身的信息而且侧重于提供对数据结构的描述， x m l 是标志和描述的集合，具有自描述性。x m l 数据由嵌套和标记元素组 成，标记包含对文档存储形式和逻辑结构的描述，这种嵌套标记元素结构使 沮彳艮适合描述w | e b 上的半结构化数据。此外，这种标记代表数据的含义而 不是显示数据结构，也使x m l 可用来描述内容而非表现形式，再加上x m l 文档一般是成型的合法结构文档，使一般的应用软件能解读它，并通过标记 语言的意义对其进行特定的处理，使x m l 具有良好的可扩展性。 x m l 具有客户定制标记词表，因此x m l 使得描述数据以及数据片之间 的关系成为可能。事实上，x m l 的主要目标之一就是将w e b 文件的内容( 数 据) 和描述( 数据的表示形式) 分割开来。 正是x m l 的特点决定了其卓越的性能表现。x m l 作为一种标记语言， 有许多特点嘲。 ( 1 ) 简单性。x m l 经过精心设计，整个规范简单明了，它由若干规则组 成，这些规则可用于创建标记语言，并能用一种常常称作分析程序的简明程 序处理所有新创建的标记语言。 ( 2 ) 开放性。x m l 在市场上有许多成熟的软件可用来帮助编写、管理等， 开放式标准x m l 的基础是经过验证的标准技术，并针对网络做最佳化。 ( 3 ) 可扩展性。x m l 有两个意义上的可扩展性。首先，它允许创建者建 立自己的标签，所以就有多种应用的可扩展标志集。其次，用户可以使用几 个附加的标准对x m l 进行扩展，这些附加标准可以向核心的x m l 功能集 增加样式、链接和参照能力。 ( 4 ) 互操作性。由于x m l 是一种平台无关的标准，所以可以在多种平台 上使用，并且已经可以用多种工具进行解释。x m l 支持用于字符编码的许 9 哈尔滨工程大学硕士学位论文 多主要标准，允许它在全世界许多不同的计算机环境中使用。 2 2 纯x f l l 数据库 1 为什么使用纯x m l 数据库 早期的x m l 数据以文档( 文本文件) 的方式存储，以关健字查询等信息检 索手段进行查询，简单易用，适合x m l 文档不频繁更新的场合。由于缺乏系 统的存储和查询机制的支持，造成查询能力低，不能满足复杂条件的查询， 更谈不上查询优化。一些现有的商业数据库管理系统扩充了处理x m l 数据的 功能。利用现有数据库成熟的技术，把儿查询要求转换为数据库的查询表 达，如s q l ，由数据库的查询引擎优化查询表达，产生查询执行计划并执行， 最后再将查询的结果转换为x m l 数据。这种方法在一定程度上解决了查询复 杂性的要求，但是多次转换带来的问题是效率的降低和查询语义的混淆t z o 。 ( 1 ) 从本质上讲，传统的r d b m s 不支持层次的和半结构化的数据形式， 只有经过转换处理才能把嵌套的x m l 数据放到简单的关系表中。x m l 是具 有动态结构的数据，这正是x m l 可扩展性的关键，而传统的r d b m s 不能处 理这种数据。 ( 2 ) s q l 适合于查询受确定模式支配的表，它不是为具有动态、复杂特 性的x m l 设计的。 ( 3 ) 传统的r d b m s 查询引擎需要把针对x m l 的查询翻译成很多关系表 的检索和连接运算，这不仅造成查询性能的下降，而且往往不能产生代价较 小的查询执行计划。 纯x m l 数据库管理系统- n x d b m s 以自然的方式处理x m l 数据，没有因 数据模型转换而带来信息丢失和性能下降。n x d b m s 与非m j b m s 的区别 在于脚，：有效地支持x m l 数据的自描述性、半结构化和有序性；系统直接存 储x m l 数据，而不是把x m l 数据转换成关系模型或者面向对象模型，由关系 数据库或面向对象数据库存储；直接支持x m l 查询语言，如x q u e r y ，x p a t h ， 而不是转换成s q l 或o q l ( 对象查询语言) 。 2 n a t i v ex m l 数据库的基本概念 关于纯x m l 数据库，r b o u r r e t 给出了一个定义，即只有满足以下三个条 1 0 啥尔滨工程大学硕士学位论文 一i 一一 i i | i i i i 一 件的x m l 数据库才能称为纯 l 数据库昭“： ( 1 ) 为x m l 文档定义了一个( 逻辑) 模型，x m l 数据的存储和查询都基于 这个模型。这个模型至少要包含元素、属性等，并保持文档顺序。 ( 2 ) 将x m l 文档作为( 逻辑) 存储的基本单位，正如关系数据库将行( 元组) 作为存储的基本单位一样。 ( 3 ) 不要求只能使用某一特定的底层物理模型或某种专有的存储格式。 第一个条件要求纯x m l 数据库必须基于某种模型。这是因为各种数据库 都基于不同的模型，就像关系数据库基于关系模型、层次数据库基于层次模 型一样。第二个条件的含义是：在纯x m l 数据库中，数据只有在一个x m l 文档中才有意义，当然这并不妨碍查询一个文档的片段，就像在关系数据库 中仍然可以查询一个元祖的片段( 属性值) 一样。第三个条件的含义是：底层 的存储格式并不重要。事实上，很多纯儿数据库是采用一些传统的数据库 作为底层存储引擎的，当然也有采用专有存储格式( p r o p r i e t a r ys t o r a g ef o r m a t ) 的。 从上述定义可以看出，纯龇数据库的核心在于其模式，即它的逻辑模 式必须是某种特殊的模型，而不能是关系或面向对象的。换句话说，纯x m l 数据库与x m l 使能数据库的本质区别是其逻辑模式不同，而不是其底层的存 储方式不用。 3 纯x m l 数据库的特点 纯x m l 数据库的逻辑模型建立在x m l 文档之上，并根据它来存取数据。 一个数据库模型应该具有以下几个特性：文档集合、查询、更新、事务、锁 和并发控制、二次开发接口等。 ( 1 ) 文档集合 很多纯x m l 数据库产品都支持“文档集合”的概念，就像文件系统中的 一个目录或r d b m s 中的一张表，一个“文档集合把一类文档聚集在一起， 方便用户操作。集合级别上的查询、修改操作都会反映到集合内的每个文档。 一个“文档集合 关联一种模式。将文档加入到有模式的“文档集合时， 会对要加入的文档进行模式检查。只有符合“文档集合一模式的文档才可以 加入。不同于r d b m s 中的表必须要具有模式，纯x m l 数据库还提供“无模 式刀的文档集合，即将一个文档放人该集合中时，不必检查该文档的模式。 哈尔滨工程大学硕士学位论文 l i i li !i _ “无模式”的文档集合方便了用户存储格式很难统一、半结构化的x m l 文档。 ( 2 ) 查询 x p a t h 和x q u e r y 是针对x m l 文档的查询语言。目前大部分纯x m l 数据库 产品都支持x p a t h ，另外还有一些纯x m l 数据库提供专门的查询语言。x p a t h 是基于x m l 文档的树形模型，给出从某个结点起的查询路径，搜索文档。目 前，x p a t h 作为数据库查询语言还有不少缺陷：不能分组、排序、连接等。 面x q u e r y 更像一种编程语言，支持循环等逻辑，支持分组、排序、连接等。 相对于传统数据库的标准s q l 语句，x q u e r y 在对x m l 数据的查询方面，是一 种功能更强大，更易于编程的方法。 ( 3 ) 事务、锁和并发控制 同传统数据库一样，纯x m l 数据库同样支持事务处理。但是，锁的粒度 通常比较大，针对的是整个文档而不是文档片断，所以多用户并发性的支持 相对较低。具体的并发程度取决于应用程序以及“文档 的构成。 ( 4 ) 二次开发接口 纯x m l 数据库提供编程接口：提供数据库连接、浏览元数据、执行查询 和返回结果的方法。返回结果通常是x m l 字符串。如果查询返回结果是多个 文档或文档片断( f m g m e m ) 的话，通常都会提供枚举这些结果的方法。对于 以c l i e n t s e r v e r 模式运行的数据库产品，还可以将结果通过网络协议( 如 h w 曙) 回传给客户端。 2 3 纯x m l 数据库存储的相关技术 2 3 1x m l 数据的编码方案 为了能够高效的查询求解，已经提出多种x m l 文档编码机制。所谓x m l 文档编码机制，是指为x m l 文档树的每个结点赋予一个特定的编码，以便 于通过编码直接判断x m l 文档树中祖先后裔关系，而不需要对原x m l 文 档进行导航遍历。编码方案可以分为基于区间的编码机制和基于路径的编码 机制。基于区间的编码机制将每一个结点编码为一个区间，而基于路径的编 码机制则是依据结点的路径将每一个结点编码为一个数字。 ( 1 ) 基于区间的编码方案 1 2 哈尔滨工程大学硕士学位论文 有关文档编码的早期研究多集中在区i 茸q ( r a n g e b a s e d ) 编码法上。其主要 思想在于为x m l 文档树中的每一个结点赋予一对正整数b e g i n 和e n d ，编码 形式为 b e g i n ，e n d 。所有结点的编码区间都是其祖先结点的编码区间的子 集。也就是说，结点a 是结点d 的祖先的充分必要条件是a b e g i n = d e n d 。 l i m o o n ( x i s s ) 编码机制。其主要编码方案是：x m l 文档树t 中的每一 个结点被赋予二元组 ，o r d e r 是结点的扩展先序遍历序号，s i z e 是结点的后裔范围。因此，文档树中结点a 和结点d 存在祖先一后裔关系， 当且仅当a o r d e r d o r d e r 且d o r d e r + d s i z e = a o r d e r + a s i z e 。另外，每个结 点被赋予一个大于或者等于零的值d e p t h ，其表示该结点在文档树中的层次。 z h a n g 编码机制。其主要编码方案是：x m l 文档树t 中的每个结点被赋 予二元组 ，b e g i n 是x m l 文档中的开始位置，e n d 是结点在x m l 文档中的结束位置。因此，文档树中结点a 和结点d 存在祖先后裔关系，当 且仅当a b e g i n d e n d 。另外，每个结点被赋予一个大于或者 等于零的值d e p t h ，其表示该结点在文档树中的层次。 w a n ( a p p r o x q l ) 编码机制。其主要编码方案是：x m l 文档树t 中的每 个结点被赋予二元组 。o r d e r 是结点的扩展先序遍历序号。 m a x o r d e r 是结点的后裔编码中扩展先序遍历序号的最大值。因此，文档树中 结点a 和结点d 存在祖先一后裔关系，当且仅当a o r d e r d o r d e r 且 d m a x o r d e r = a m a x o r d e r 。 d i e t s 编码机制。其主要编码方案是：x m l 文档树t 中的每个结点被赋 予二元组 ，p r e 是结点的先序遍历序号，p o s t 是结点的后序遍历序 号。因此，文档树中结点a 和结点d 存在祖先一后裔关系，当且仅当 a p r e d p r e 且dp o s t a p o s t 。 区间编码机制根据区间判断结点关系，其优点是编码简单，结点编码的 平均长度为0 ( 1 0 甙n ) ) ；缺点是使用非等值比较进行结点关系判断，并且需要 单独提供层次信息。 ( 2 ) 位向量编码机制 位向量编码机制的主要编码方案是：x m l 文档树t 中的每个结点与一 个1 1 位向量v 对应，1 1 是树t 中结点的数目。在向量的某个位置i 上的一个 1 3 哈尔滨工程大学硕士学位论文 “1 ”位唯一地标识了第i 个结点。并且在一个自顶向下( 或者自底向上) 的编 码方案中，每一个结点继承标识它祖先( 或后裔) 的所有位上“1 一。例如：树 t 的一个结点u 的位向量编码记为c ( u ) = ( b l ，b 2 ，g oe ) b n ) ，如果树t 的第i 个 结点是结点u 或它的祖先( 或后裔) 结点，则b i = l ，否则b i = 0 。其优点是容 易判断结点间的层次关系，缺点是不支持更新操作编码空间较大。 ( 3 ) p b i t r e e 编码机制 p b i t r e e 编码机制的主要编码方案是：将x m l 文档树t 转化为完全二叉 树。然后按照“自底向上，自左至右”的顺序为每个结点进行编码。p b i t r e e 编码按照结点在文档树中的位置进行编码，其优点在于编码简单，结点编码 的平均长度为o ( n ) ；并且使用等值比较进行结点关系判断。缺点是不支持更 新操作，需要单独提供层次信息。 ( 4 ) d e w e y 编码机制 d e w e y 编码机制的主要编码方案是：将x m l 文档树中父结点的编码直 接作为其子结点编码的前缀，也称为前缀编码。因此，文档树中结点r n 和结 点d 存在祖先一后裔关系，当且仅当a c o d e 是d c o d e 的前缀。d e w e y 编码 将x m l 文档树中父结点的编码直接作为其子结点编码的前缀，其优点是编 码简单，结点编码的平均长度为o ( n