（计算机应用技术专业论文）xml文档检索的索引结构研究.pdf

摘要 摘要 提出一种对x m l 文档建立索引的新方法。浚方法支持分支查询和 带有通配符的查询。同时设计了一种通过一次遍历x m l 文档就可以建 立索引的算法。 按照我们设计的线模型，x m l 文档被看作一条线，文档中各个元 素被看作这条线的线段。查询x m l 文档就相当于指定相应的线段。使 用一种基于区间的动态树标记模式，每个线段都被给予一个区间。然 后把x m l 文档中所有的路径插入到一个t r i e 结构中，并使用b + 树管 理这些区间。定义了三种运算，这些运算使不同b + 树上的区间集合可 以相互运算。三种运算对应算法的最差情况时间复杂度是0 ( m + n ) 。分 支查询最后的结果可以通过这些运算直接得到。 这种索引方法的创新处体现在如下几个方面：提出了用于查询 x m l 文档的线模型；定义了三种运算，并给出了相应的算法：在线模 型和三种运算的基础上，我们使这种索引方法支持分支查询：最可能 匹配的点在索引结构里有聚集效果，这种特性大大减少了磁盘i o ， 并同时使磁盘优化成为可能：提出一种动态的树标记算法，使我们的 索引结构支持数据插入和删除；并给出了通过一次扫描建立索引结构 的算法。 通过实验，我们把该索引方法和时下流行的技术进行比较。实验 证明该方法的查询处理开销和磁盘i o 与查询表达式的复杂度和查 询结果集的大小线性相关。实验结果表明了我们索引方法的显著性能 优势。 根据本文主要研究成果撰写的论文，l m i x ：ad y n a m i cx m li n d e x m e t h o du s i n gl i n em o d e l ，已经被l e c t u r en o t e si nc o m p u t e rs c i e n c e 收录出版发行，并被s c i 检索。 关键词：x m l 索引，n a t i v ex m l 数据库，数据管理，数据检索 a b s t t a c t a b s t r a c t an e w w a y o f i n d e x i n gx m l d o c u m e n ti sp r o p o s e d w h i c hs u p p o r t s t w i gq u e r i e sa n dq u e r i e sw i 出w i l d c a r d s a n o n c e - o v e ri n d e xc o n s t r u c t i o n a l g o r i t h mi s a l s o g i v e n a c c o r d i n gt o t h el i n em o d e lw ed e s i g n ，v e e c o n s i d e rx m ld o c u m e n ta sal i n e ，a n de v e r ye l e m e n t so ft h ed o c u m e n ta s t h el i n e s s e g m e n t s t oq u e r ya n x m ld o c u m e n ti st o i d e n t i f y t h e c o r r e s p o n d i n gs e g m e n t s u s i n g ar a n g e b a s e d d y n a m i c t r e e l a b e l i n g s c h e m e ，e a c hs e g m e n to f t h el i n ei sg i v e na r a n g e w ep u ta l lt h ep a t h so f x m ld o c u m e n ti n t oat d e ，a n do r g a n i z et h er a n g es e t sw i t hb + - t r e e s g r o u p i n gb yt h en o d e so nt h et r i e t h r e eo p e r a t i o n sa l ed e f i n e d ，w h i c h e n a b l et h er a n g es e t so nt h eb + - t r e e sc o r r e s p o n d i n gt od i f f e r e n tn o d e si n t h et r i et oo p e r a t ew i t he a c ho t h e r n 心w o r s t c a s et i m ec o m p l e x i t yo f t h e a l g o r i t h mw ed e s i g n e df o rt h eo p e r a t i o n si s0 ( m + n ) t h e f i n a lr e s u l t so f t w i gq u e r i e s c a nb e g o tt h r o u g h t h e s eo p e r a t i o n sd i r e c t l ya tas p e e ds i m i l a r t ot h es i m p l ep a t hq u e r y t h r o u g he x t e n s i v ee x p e r i m e n t s ，w ec o m p a r eo u r m e t h o dw i 血o t h e rp o p u l a rt e c h n i q u e s i np a r t i c u l a r , w es h o wt h a tt h e p r o c e s s i n gc o s ta n dd i s k i ，oo fo u ri n d e xm e t h o di sl i n e a r l yp r o p o r t i o n a l t ot h ec o m p l e x i t yo fq u e r ya n dt h es i z eo fq u e r yr e s u l t s e x p e r i m e n t a l r e s u l i sd e m o s t r a t et h e g r e a tp e r f o r m a n c e b e n e f i t so fo u r p r o p o s e d t e c l m i q l i e s p a p e r l m i x ad y n a m i cx m l i n d e xm e 伪o d u s i n g l i n em o d e l ，w h i c h i sw r o t ea c c o r d i n gt ot h em a i nr e s e a r c hm s u l t so ft h i st h e s i s ，h a sb e e n a c c e p t e db y l e c t u r en o t e si nc o m p u t e rs c i e n c ea n di n d e x e db ys c i k e y w o r d s ：x m li n d e x ，n a t i v ex m l d a t a b a s e ，d a t am a n a g e m e n t ，d a t a r e t r i e v a l 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名： 日期：年一月一 = j 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名： 日期：年一月一日 北京交通人学硕士学位论文 1 引言 1 1x m l 的产生 i n t e r n e t 的迅速发展，使其成为全球信息传递和共享日益重要和 最具潜力的资源。电子商务、电子图书、远程教育等全新领域的需求 和发展，使w e b 数据变的更加复杂和多样化，产生了大量的半结构化 数据。由于半结构化数据的特殊性，以往的一些结构化数据标准已不 适用，因此为了标识和存储半结构化数据，迫切需要制订新的标准。 1 9 9 6 年7 月，w 3 c ( w o r l dw i d ew e bc o n s o r t i u r n ) 在j o nb o s a k 的建议下成立了x m l 规范制订小组。在大批著名公司、学术机构代表 和s g m l 专家的共同努力下于1 9 9 8 年2 月1 0 日正式推出了x m l i 0 的 建议书。随即，x m l 成为近年来国内外许多科研机构、知名数据库厂 商和网络软件产品开发商的研发热点，投入了大量的人力和资金，开 发出了众多的相关产品。由于x m l 能针对特定的应用定义自己的标记 语言，这一特征使得x m l 可以在电子商务、电子文档、信息交换等众 多领域中获得广泛的应用。 x m l 技术从诞生之日就预示了它辉煌的未来，特别是随着近两年 w e bs e r v i c e 的蓬勃发展，x m l 越来越多地活跃在数据交换和存储领 域。 1 2x m l 的特点 x m l 具有以下优点： ( 1 ) x m l 允许各种不同的专业( 如音乐、化学、数学等) 丌发与自 北京交通人学硕七学位论文 已的特定领域有关的标记语言。这就使得该领域中的人们可以 交换笔记、数据和信息而不用担心接收端的人是否有特定的 软件来创建数据。 x m l 具有较好的保值性。过去4 0 年来的大多数计算机数据都丢 失了，不是因为自然损害或是备份介质的磨损，而只是因为没 有人来写出如何读取这些数据介质和格式的程序。以不常用的 格式保存的二进制数据，数据也许会永远地不可再读了。x m l 在基本水平上使用的是非常简单的数据格式。可以用1 0 0 的 纯a s c i i 文本来书写，也可以用几种其他定义好的格式来书写。 a s c i i 文本是几乎不会“磨损”的。 适合应用闻交换数据。由于x m l 是非专有的并易于阅读和编写， 就使得它成为在不同的应用间交换数据的理想格式。x m l 使用 的是非专有的格式，不受版权、专利、商业秘密或是其他种类 的知识产权的限制。x m l 的功能是非常强大的，同时对于人类 或是计算机程序来说，都容易阅读和编写。因而成为信息交换 语言的首选。 1 3 研究问题的提出 x m l 数据量指数级的增长，要求更有效的数据管理能力和更快、更 精确的查询。 我们可以把相关的x i d l 文档放在一个目录下，利用文件系统来管 理并提供查询、更改、增删操作。为更好地支持x m l ，w 3 c 还制定 了一些相关技术，如文档模式( d t d 、x m ls c h e m a ) ，查询语言( x p a t h 、 x q u e r y 等) ，编程接口( d o m 、s a x 等) ，来方便应用程序丌发。 ) ) 引言 但如果从更高的技术角度出发，就会发现，只对x m l 文档进行简 单的文件管理是远远不够的：低效的存储组织、索引查询技术，不提 供事务、安全恢复机制，无法保证数据的完整性和一致性，没有并发 控制、移植工具等。 随着x m l 标准的制订和推广，x m l 受到数据库界和w w w 界的广泛 重视，x m l 数据管理中的很多问题有待深入研究。由于以下几个方面 的原因，使得x m l 数据的存储问题仍然没能得到很好的解决： ( 1 ) 虽然文件系统是一个简单的存储x m l 数据的方式，但是由于文 件系统不提供查询处理、数据完整性和一致性检查、索引等辅 助功能，查询效率低，维护不方便。 ( 2 ) 面向对象数据模型是最类似x m l 数据模型的一种已有的数据模 型，面向对象数据库在支持x m l 数据应用方面具有优势。但目 前的面向对象产品还不够成熟和完善，而且通过面向对象模型 实现x q u e r y 也是一个难点，x m l 查询语言的能力要强于面向对 象查询语言。 ( 3 ) 利用关系数据库管理x m l 数据，通过把x m l 数据分解成关系存 放在关系数据库中，建立x m l 数据与关系模式的对应关系。但 是现在很多算法需要用户指定x m l 和关系之间的映射，这就需 要用户非常熟悉x m l 规范和关系模型，使普通用户满足这样的 要求显然比较困难。 ( 4 ) 还有一种策略是通过数据挖掘算法，分析x m l 数据的分布特点， 从而决定如何把x m l 数据映射到关系表中。一般来说，根据概 率分布进行的映射是有损的，因为对于那些小概率出现的数据 模式信息会被系统忽略，从而不能把它们存放到关系数据库 北京交通人学硕士学位论文 中。理论上，数据管理系统要求是无损( t o s s l e s s ) 的，也就 是所加载到数据库的数据要与原始文档中的数据一致，所以这 种方法在很多应用场合会受到限制。 ( 5 ) n a t i v ex m l 数据库产品通过从底层设计针对x m l 数据模型的数 据管理系统，实现存储和查询，有许多针对半结构化数据的特 殊索引和查询机制。但是这种设计策略很难在短期内达到可以 与关系数据库媲美的效率和功能。 1 4 本文研究内容 切合实际需求，我们将在对不同的x m l 文档索引方法进行理论研 究的基础上，改进或设计新的索引方法，并实现演示系统作为验证。 前文所述的研究成果为索弓f 算法的设计提供了深厚的理论基础，但还 有许多工作需要完成。初步设想如下： 1 、索引机制的设计 将x m l 文档作为文本迸行存储。对文本建立索引，使查询引擎可 以方便的跳到x m l 文档的任意位置。 使用高维索引或通过结构化文本序列的方式来建立索引。 使用b + 树建立动态索引。评价索引方法好坏的一个重要标准是索 引是否依赖d b m s 不能很好支持的特殊数据结构。使用b 树、b + 树设 计的索引方法，一般能够方便地移植到当前流行的数据库管理系统 中。而且，可以支持动悉的数据插入和删除操作。 2 、索引算法的实现 准备使用b e r k e l e yd b1i b r a r y 的b + 树a p i 啪1 来实现b 树、b + 树。计划采用c 十+ 开发演示系统。c + + 运行效率高，与其它语言接口方 4 j l 言 便，是处理索引建立这类底层操作的首选语言。 演示系统包括索引的建立和简单x m l 查询的实现两部分内容。 3 、索引效率的评估 对索引算法性能优劣的评估指标包括索引的大小，建立索引所需 时间，查询的速度，算法的伸缩性和稳定性等几个方面。 1 5 本章小结 x m l 是数据库研究者的一次契机，x m l 提供了这样一个机会，让中 国的研究与世界同步! 北京交通人学硕十学位论文 2 理论背景 2 1 信息检索与数据检索 信息检索作为一门学科的历史可以追溯到2 0 世纪5 0 年代。作为 一门现代技术，信息检索与计算机几乎同时问世，且关系密切。现代 信息检索理论就是建立在计算机信息检索理论的基础之上，并从数 学、物理学、语言学、人工智能等学科引入先进的科学方法和技术手 段，逐步形成的一门学科。 广义的信息检索是指对信息的表示、储存、组织和获取。按信息 的表现形式不同，可以分为文本信息检索、数据信息检索、图像检索 和语音信息检索。按检索结果的不同又可以分为文档检索、数据检索、 事实检索和概念检索。 同时，由于数据库技术的发展( 坚实的理论基础和由此产生的高 效率的算法) ，使数据库技术成为计算机科学中非常重要的组成部分。 这里把针对数据的信息检索归入数据库领域，以与信息检索( 狭义) 区 分。 在本课题的讨论中，我们需要区分信息检索和数据捡索这两个概 念。两者都是为满足用户的信息需求，根据一定的“查询请求”，从 计算机中获得用户想要的信息。它们的区别有以下几点： ( 1 ) 检索的模式：在数据检索中，用户在建立查询式的时候，他知 道数据的组织结构，或者他应该知道在什么地方能找到自己所 需要的信息；而在信息检索中，用户在建立查询式的时候，他 基本不了解信息的组织结构，只是按自己所想构建查询式。 6 理论背景 ( 2 ) 信息的组织模式：在数据检索中，信息被组织在一定的已知的 模式中；而信息检索所面对的是在大量不存在确定模式，或者 是模式各异的信息中进行检索。 ( 3 ) 信息的匹配：大多数情况下，数据检索的过程是一个对信息的 精确匹配过程：而信息检索的过程是对信息的一种模糊的、部 分匹配的匹配过程。 ( 4 ) 查询式：数据检索中，用户构建的查询式能完全描述信息的需 求：在信息检索中，查询式不能完全表达用户的信息需求。 ( 5 ) 检索结果：数据检索中，对于用户而言，所有的结果都是一样 的正确，都满足用户需要；信息检索的结果不一定全是用户所 需要的，而且不同的结果满足用户需要的程度也是不同的。 以上只是原始的数据检索与信息检索之间的区别。就目前数据库 技术与信息检索技术发展状况而言，它们之间的区别是不明显的。特 别是具体技术的运用和相关概念的互相引入，使这两个概念的区别更 加模糊。这里，暂以上面的区别对课题进行讨论。本文研究x m l 文档 数据检索的索引方法。 2 2x u l 文档的分类 x m l 文档可以分为两大类：以数据为中心的和以文档为中心的。 以数据为中心的x m l 文档( d a t a c e n t r i c ) 以数据为中心的x m l 文档着重于文档中的数据，而非文档格式， 如航班信息、销售定单、科学计算结果等。这种文档的数据一般由机 器产生，并为枫器使用而设计，也就是说主要是方便机器进行处理。 这类文档主要来源于传统数据库中的数据，主要应用在电子商务、 北京交通人学硕十学位论文 e r p 、e a i 等领域，用来集成f i 同数据源的数据和交换信息等。以数捌 为中心的x m l 文档具有以下特点： 结构化的数据 数据粒度大小适中 很少或没有混和内容( m i x e dc o n t e n t ) 文档顺序( d o c u m e n t - o r d e r ) 不重要 图2 - 1 就是一个典型的“以数据为中心”的x m l 文档，记录了学 生的信息。每个学生的信息都很规整，而且粒度适中，同级元素问的 顺序不重要，交换两个同级元素并不会破坏文档的可读性。 1 9 8 0 3 0 0 1 j o h n s o n j a e k j a e k i p e d o c o m l 图2 - 1 以数据为中心的x m l 文档 以文档为中心的x m l 文档( d o e u m e n t - c e n t r i c ) 以文档为中心的x m l 文档主要是用来表示人类自然语言描述的数 据，具有不规则的结构，而且数据的粒度通常比较大。如电子邮件、 书和用户手册。这类文档一般具有比较复杂的结构，一般不是机器自 动产生的。目前，w e b 上的大部分数据都可以表示成这种文档。以文 档为中心的x m l 文档具有以下特点： 半结构化或非结构化的数据 较多的混和内容( m i x e d c o n t e n t ) 理论背景 文档顺序( d o c u m e n t - o r d e r ) 重要 图2 2 就是典型的一个“以文档为中心”的x m l 文档。 t h e t p e d on a t i v ex m 【l d b f r o m i p e d o ，i n c i s l i k eat r u en a t i v ex m l d a t a b a s e ， ： 图2 - 2 以文档为中心的x m l 文档 下一节将介绍x m l 数据管理的两种方式x e d 和n x d 。对于以数据 为中心的x m l 文档，x e d 可以方便地将其中的数据抽取，存储在传统 数据库中，但对于以文档为中心的x m l 文档则显得力不从心了。n x d 由于无需在两种模型之间转换据，因此在处理以文档为中心的x m l 文 档时就很有优势。 2 3x m l 数据管理方式的分类 随着x m l 在数据交换应用中变的越来越重要，为了找到从x m l 文 档提取数据的灵活高效的方法，人们进行了大量的科学研究。从总体 上可以把当今的x m l 数据管理研究系统分为两类：x m le n a b l e d 数据 库方式( x e d ) ，n a t i v ex m l 数据库方式( n x d ) 。其中，x m le n a b l e d 数据库方式主要通过在文件系统、关系型存储器或对象存储器上构造 针对x m l 数据模式的数据管理系统：n a t i v ex m l 数据库方式就要从底 层设计针对x m l 数掘模型的数据管理系统。 x m l 文档具有很大的灵活性，通过把x m l 数据映射到现存关系数 北京交通大学硕士学位论文 掘库系统中存储，通常会产生大量的数据表或异常的关系表示。文献 2 6 通过对x m l 数据与关系数据模式映射关系的理论分析，指出寻找 x m l 数据在关系数据库中存储的最优方案是个n p 问题。 n x d 是专门为存储x m l 文档设计，也兼有一般数掘库的特性，例 如支持事务、并发控制、查询语言、安全机制和提供二次，r 发接口等。 唯一的不同之处在于其内部存储模型是基于x m l 文档树形结构，而非 关系模型。 下面我们将介绍几个常见的x e d 和n x d 数据库的例子，并加以比 较。 x m le n a b l e d 数据库 x m le n a b l e d 数据库是一个在瑚l 文档和关系表格之间转化数据 的关系数据库。它维护表格和x q l 文档接点域之间的对应关系属性， 而不是对x m l 文档建模。 图2 3 展示了x m l 在关系数据库中的存储方式。数据访闯定义文 件( d a d ) 用来定义x m l 文档的元素属性和关系数据库中表的列之间的 影射。d a d 用来把数据由关系表影射到x m l 文档，也用来帮助通过集 合数据构建或分解x m l 文档。 理论背景 图2 - 3 删l 在关系数据库中的存储方式 x m le n a b e d 数据库有关系数据库的引擘，并把x m l 数据保存为 一系列关系表。在访问相关的表格之前，必须把x m l 文档的模式转化 成关系模式。类似的，x m l 查询语言也必须转化成s q l 来访问关系表 格。图2 4 展示了x m le n a b l e d 数据库的体系结构。x m l q l ( x m lq u e r y l a n g u a g e ) 作为r d b m s 的附加功能函数实现。关系q e ( q u e r ye n g i n e ) 解析x m l q l 并转化成s q l 。s q l 在r d b m s 内执行，并在存储管理器内 执行操作。x m l q l 必须独立实现。既然x m l 数据被存储在关系表格 里，转换s o l 可能包含检索和联接操作。这些操作很可能需要比较多 的c p u 计算时问，最终造成查询性能的损失。 北京交通人学硕十学位论文 x m l o l r e t a t i o r , a io e i s t o r e , g e w m 咿 r d b m s r i d a l j 由d z s e l l 图2 - 4x m le n a b l e d 数据厍体系结构 图2 5 展示了s q ls e r v e r2 0 0 0x m l 支持的体系结构。按照系统 或服务体系结构的不同，可以使用多种访问组件和访问协议。如果商 业逻辑不是特别复杂，或者绝大多数的商业逻辑可以完全放在客户端 或服务器端，通过简单的h t t p 或s o a p 协议访问就足够了。对于两层 结构或需要在w e b 服务器上运行商业逻辑豹三层结构，为了性能和软 件开发的需要，商业逻辑和数据访问经常是紧密耦合在一起的。这时， 可以通过标准的访问组件，如o l e d b ，a d o ，和n e t 的a p i 实现x m l 数据访问。 理论背景 图2 - 5s q ls e r v e r2 0 0 0x m l 支持的体系结构 n a t i v ex m l 数据库 r o n a l db o u r r e t 在其 x m la n dd a t a b a s e s 一文中，对n x d 有如下 定义：“n x d 的逻辑模型建立在x m l 文档，而非文档中的数据之上， 并根据它来存取数据。该模型至少包括元素( e l e m e n t ) 、属性( a t t r i b u t e ) 、 p c d a t a 和文档顺序，例如x p a t h 的数据模型n x d 的最小存储 单位是x m l 文档，” n a t i v ex m l 数据库直接存储x m l 数据。数据库引擎直接访问 x m l 数据，而不做任何的转换。这是x m 乙e n a b l e d 数据库和n a t i v e x m l 数据库的主要区别。这种直接访问数据的方式可以减少处理时 间，提供更好的性能。在管理员定义模式的基础上，x m l 引擎直接从 相应的数据源存储和读取x m l 文档。图2 - 6 展示了通过x m l 引擎 存储和读取数据的过程。x m l 解析器验证模式的正确性，并确保输入 的x m l 数据是格式良好的，然后使用对象处理器把对象存储到n a t i v e x m l 存储器。查询语言是x m lq u e r yl a n g u a g e ( x q l ) 。查询解释器 分析输入的请求，并通知对象生成器读取并生成符合管理员定义模式 北京交通大学硕士学位论文 的x m l 对象。使用存储和读取模式，对象生成器构造查询结果对象 并作为x m l 文档返回。 x m i o u l p u t q r y x m lo b i 姗t d 1 陆、士 i ： f 量气l 一l 削 纛 图2 - 6n a t i v ex m l 数据库x m l 引擎体系结构 t a m i n o 和e x i s t 是两个比较有名的n a t i v e x m l 数据库。 t a m i n o 1 9 9 9 年，s o f t w a r ea g 发布了n a t i v ex m l 数据库服务器t a m i n o 的第一个版本。t a m i n o 数据库由多个被称为c o l l e c t i o n ( 参见图2 7 ) 的 对象组成。这些c o l l e c t i o n s 是把文档分缀存储的容器。每个文档只能 处于t a m i n o 数据存储器的一个c o l l e c t i o n 中。每个c o l l e c t i o n 有一个 对应的w 3 cx m l 模式描述。在每个模式描述里，文档类型可以通过 在w 3 cx m l 模式的扩展部分利用t a m i n o 指定的符号指定。文档类 型指定在w 3 cx m l 模式中作为根元素的全局元素。在每个c o l l e c t i o n 罩，每个文档只能作为一种文档类型存储。 理论背景 图2 - 7t a m i n ox m l 数据库中的数据组织 t a r n i n ox m l 服务器支持三种类型的索引：标准索引、文本索引 和结构索引。这些索引在存储、修改或删除文档的时候就会被修改。 标准索引是基于值的索引，和关系数据库的值索引是相同的。当 查找特定值的元素或属性时，这种索引提供快速的查找。标准索引是 数据类型相关的：对数值的索引支持对数的排序( i e 5 “1 0 ”) 。 文本索引是高效存取文本的先决条件。文本索引对元素或属性中 含有的文字建立索引，通过这种索引加速搜索元素或属性所含文字的 过程。 结构索引是另外一种和x m l 类型相关的索引。浓缩的结构索引 含有在指定文档类型里出现的所有路径的信息。在大部分情况下，这 种索引可以加速查询的执行过程。 t a m i n o 数据库在磁盘上由两个部分( 被称为空间) 组成： 数据空间含有所有的文档和存储在t a m i n o 里韵对象。为了加速顺 序访问速度，文档类型按簇组织。按照文档大小的不同，数据库 可以选择对指定的文档进行压缩。 索引空间含有存储在t a m i n o 数据库里文档的索引数据。 北京交通人学硕十学位论文 e x i s t e x i s t ( h t t p ：e x i s t d b o r g ) 是一个开放源代码的n a t i v ex m l 数抓 库系统。该数据库系统完全使用j a v a 语言实现，能够通过多种方式发 布，可以作为一个独立的服务器进程，也可以直接嵌入到应用的 s e r v e l e t 引擎中。e x i s t 在不使用x m l s c h e m a 信息的情况下，使用基 于层级集合的方式组织x m l 文档。使用扩展的x p a t h 表达式，用户 可以查询集合的任何一部分，甚至是数据库中所有的文档。尽管是一 个轻量级数据库，e x i s t 的查询引擎实现了一个高效的，基于索引的 查询处理。使用一种增强的索引模式柬快速确定节点间的结构关系， 比如父亲儿子，祖先后代或兄弟节点关系。基于路径联接算法，仅 仅使用索引信息就可以处理大多数的路径表达式查询。处理这种类型 的查询，不需要访问存储在x m l 文档中的实际节点。该数据库系统 特别适合处理各种大小的不经常更新的x m l 文档集合。e x i s t 使用扩 展的x p a t h 来高效的处理全文查询，这其中包括关键字搜索。开发人 员可以使用h r r p ，x m l - r p c ，s o a p 或w e b d a v 方式访问数据。 和普通的信息检索系统不同，x m l 数据库需要了解节点的位黄 和结构。因此，只存储单词的位置是不够的，e x i s t 使用节点标识来记 录节点出现的位置。为了支持x m l 查询语言的结构化查询，还需要 其他一些不同的索引。目前，e x i s t 在n a t i v e x m l 存储器内部使用四 种类型的索引文件： d o r a d b x 在分页的文件里记录d o m 节点，记录节点标识和 实际节点闻的对应关系。 c o l l e c t i o n s d b x 管理集合的分层结构。 e l e m e n t s d b x 针对元素和属性的索引。 w o r d s d b x 记录单词出现的位置，用来加速全文检索。 6 理论背景 e x i s t 查询处理器首先把正则路径表达式查询分解成一系列原子 路径，然后检索索引结构，最后得到查询结果。比如，x p a t h 表达式 p l a y s p e e c h s p e a k e r = h a m l e t 】被如图2 - 8 那样分解。 图2 - 8 路径表达式的分解 e x i s t 的索引模式把文档建模为完全k 叉树，k 等于树形结构中的 儿子节点的最大个数。这也就暗示树上所有非叶子节点都假设拥有相 等数目的儿子节点。通过层序遍历树，给每个节点一个标识。对于那 些含有少于k 个儿子节点豹节点，插入虚拟节点来填补空隙。因此， 一些标识因为必须构成完全k 叉树而被浪费了。图2 - 9 展示了对一个 简单的x m l 文档赋予的标识。 c t n ：翻c 州，n 图2 - 9 层序的标记模式 节点标识被影射至i j x m l 数据容器里( d o m d b x ) 相应的d o m 节点 上。x m l 数据容器是e x i s t n a t i v e 存储体系结构的中央部件。它由单页 的文件构成，按照d o m 结构存储了文档的所有节点。在数据容器罩使 用相同文件中的b + 树在节点标识和节点存储地址之间建立对应关系 ( 如图2 1 0 所示) 。存储地址由页面编号和节点在页面内的偏移量构成。 为了节省存储空间，只有顶层元素才插入到b 十树。其他节点通过遍历 最近的祖先节点得到。 北京交通人学硕士学侥论文 l s a l l i m o tb 卜1 。豫e 皇如耵篇 曰晴曰 刳疃剖 曰晴口 ：粤困巫五_ - i o o mi , o c l e s 图2 1 0x m l 数据存储的组织 索引文件e l e m e n t s d b x 在元素和属性名称同节点标识之间建立影 射( 如图2 1 1 所示) 。索引中的条目i 南 组成的键 和一个含有有序的文档i d 和节点i d y l j 表的数组构成。文档i 断口节点i d 对应于键中名称匹配的元素和属性。例如，查找b o o k sc o l l e c t i o n 中所 有c h a p t e r s ，查询引擎将需要查看一次索引，读取所有的 i 甸c h a p t e r 元素的节点信息。 嘛k 弹 x e d 和n x d 的比较 一x e d 的优、劣势 图2 - 1 i 元素和属性索引的组织 理论背景 优势： 用户不需要将传统数据库中原有数据重新移植到新系统中，只是 稍加改变，就可以支持x m l 应用。 传统数据库技术，例如并发控制、事务等，已经很成熟。 用户在传统数据库上的知识和经验依然有效，不需要为了应用 x m l 而再去学习一套新的数据库技术。 劣势： x m l 文档存入到数据库时需要将其“打碎”，取出时需要“组合”， 不仅耗时，而且文档的格式可能会发生变化。 x m l 文档和数据库之间的模式转换复杂，_ 丌发阶段需要较大投 入。 处理“以文档为中心”的、格式复杂的x m l 文档时，性能较差。 在采纳x m l 技术标准方面较落后。 一n x d 的优、劣势 优势： x m l 文档存取无需模式转换，存取速度快。 对格式复杂的x m l 文档支持比x e d 要好。 支持大部分最新的x m l 技术标准。 劣势： 在传统数据库技术方面比较薄弱，没有经过时间的考验。 知识比较新，相应的支持人员和文档资源都比较少。 应用范围仅局限在x m l 应用领域中。 事实上，两者的优劣并没有绝对的答案，而是和具体的应用相关。 在丌发格式较简单、数据内容比格式更重要的应用时，特别是需要在 已有传统数据库上提供x m l 访问接口时，x e d 是不错的选择。相反， 如果x m l 文档格式复杂，数据本身就有层次性关系，或在只有x m l 数据的时候，就可以考虑n x d 。因为它提供更好的性能，对x m l 标准 北京交通人学硕士学位论文 有更完备的支持。同时我们也应该看到，n x d 技术发展时间相对传统 数据库来说还很短，技术基础还不是很牢固。由于n x d 在事务、数据 恢复等传统数据库技术方面还未得到时日j 的检验凼此对数据安全要 求较高的应用，如银行、金融系统的数据库，建立在传统数据库上的 x e d 相对来说更有优势，n x d 并不具有比x e d 很明显的优势。 总的来说，n x d 在处理x m l 数据时拥有传统数据库所不能比拟 的天生优势，已促使越来越多的目光聚焦到它上面。 2 4x m l 索引结构的分类 x m l 数据的半结构化特性对数据库的索引方法提出了挑战。设计 针对x m l 的高效索引机制，显然是解决当前x m l 数据管理中众多问题 的一个有效方法。 目前有几种方法对x m l 文档建立索引。文献【1 0 】把结构化文档的 索引方法分为基于路径的、基于位置的和基于内容的三种。文献【9 】 按照索引方法使用文档结构信息的层度，把x m l 索引的类型分为以下 三种：平面文件索引，半结构亿索引和结构化索引。 平面文件索引( f l a t f i l ei n d e x i n g ) 把x m l 文档看作平面文本文件。最简单的索引方法是丢掉x m l 的标记，直接索引订l 文档的内容。这种方法最明显的好处是简单， 但它丢掉了蕴涵在x m l 标记中也许对检索过程非常有价值的附加信 息。 半结构化索引( s e m i s t r u c t u r e di n d e x i n g ) 使用半结构化索引，或者需要预先定义一个结构，然后把信息装 入，或者需要文档具有确定的结构用于建立索引。它包含以下几种索 理论背景 引方法。 基于域的索引( f i e l d b a s e di n d e x i n g ) ：通过把x m l 文档表示成域的 集合来建立索引。例如，x m l 文档也许含有a u t h o r 域，t i t l e 域平l j p u b l i s h e r 域。通过组合域的名字和内容建立索引，使检索限定在特定的域。 基于段的索引( s e g m e m b a s e di n d e x i n g ) ：通过把文档分成个个 的区段建立索引。s a l m i n e n 和t o m p a ( 1 9 9 2 ) 介绍的p a t 模型是这种方法 的一个高效实现。不过，它不允许区段的重叠。c l a r k e ，c o r m a c k ，& b u r k o w s k i f 1 9 9 5 ) 提出的重叠列表模型允许重叠，但它不支持任意嵌 套，而嵌套对x m l 文档是必须的。列表参考模型( m a c l e o d ，1 9 9 1 a ) 用 来处理层状结构的文档。然而，查询结果只返回文档顶层的元素，并 且所有的返回元素类型必须是相同的。 基于树的索i ( t r e e b a s e di n d e x i n g ) ：使用基于树的索引，x m l 文 档被看作树形或分层的结构。l e e ，y k ，3 ( 0 0 和y o o n ( 1 9 9 6 ) 研究了各 种用于s g m l 文档的基于树的索引模式。这些模式把文档看作完全的k 叉树。通过这种方法，每个节点被赋予一个唯一的整数值来建立索引。 结构化索引( s t r u c t u r e di n d e x i n g ) 结构化索引通常应用于具有固定结构的文档，这种结构通常表现 为某种模式。利用结构信息建立索引的好处是明显的：速度快，通常 可以优化，而且检索结果可以非常精确。 i r d b 索弓i ( i r d bi n d e x i n g ) ：这是目前关系数据库系统使用的索 引方式，它还包括通过把x m l 文档映射到关系表来存储的x m l 数据管 理方式。 基于路径的索 ( p a t h - b a s e di n d e x i n g ) ：使用基于路径的索引，要 分别对内容和结构建立两个索引。这样，x m l 中的每个元素和特定的 x p a t h ) e l 联系( w 3 c ) 【2 l 。每个x p a t h 被赋予一个唯一的标志，称为x l d 。 2 l 北京交通大学硕士学何论文 基于位置的索 ( p o s r i o n - b a s e di n d e x i n g ) ：空间索引( 比如r t r e e 或k d t r e e ) 可以用来建立x m l 文档的索引。基于位置的索引把文档看作 两维对象，不同的标记覆盖不同的矩形区域。x m l 文档的基本结构是 树形的，只有区内嵌套没有区间嵌套，x m l 元素问的逻辑关系能够方 便的转化成位置关系用于检索匹配。 多维索 ( m u k i d i m e n s i o n a li n d e x i n g ) ：为了满足空问数据库索引 空间数据的需要而产生了多维数据索引机制。b 树被一般化到高维空 间而变成r 树( g u t l m a n ，1 9 8 4 ) 。使用边界方框和关系机制定义对象的范 围和大小。空间被分成一个个区，使用r 树或r 树对x m l 文档建立索 引，提高检索效率。 2 5x m l 索引技术的最新成果 最近几年，许多新的x m l 索引方法被提出。我们把他们分为以下 三类： 基于路径的索引 第一类是基于路径( p ：a t h ) 的索引，比如d a 乜好u i d e s 【1 2 1 雨t l i n d e x f a b r i c l 9 1 。通过路径表达式进行查询一直是x m l 文档索引和查询研究 领域内主要的研究焦点之一。 d a t a g u i d e 试图提取x m l 文档的某种结构抽象，并通过这种结构 加速x m l 查询过程。使用结构指导查询处理，i 搬d a m o u i d e 名称 的由来。如图2 1 2 ，通过数据源( a ) ，可能得到( b ) 或( c ) 两种d a t a g u i d e s 。 理论背景 a 图2 1 2 数据源及其对应的两种d a t a g u i d c s 路径索引处理简单路径查询有非常高的效率。但它不能很好的支 持分支查询和带有通配符的查询。可以采取一些改进的策略来解决这 个问题，但那样往往使索引结构过大，以致于不能高效的执行查询。 基于联接的索引 另外一种是基于联接( j o i n ) 操作的索引方法。使用这种方法时， 一个复杂的路径表达式被分解成多个被称为原予表达式的基本路径 表达式。通过访问索引结构，可以直接得到原子表达