（计算机软件与理论专业论文）基于区间编码的xml索引研究及优化.pdf

摘要 摘要 x m l 作为网络数据交换和信息集成的工具，以其自描述性、跨平台交换性 等特点，成为新一代的网络语言。互联网上越来越多的结构化或半结构化的数 据采用x m l 格式存储和交换，随着x m l 数据量的不断增长，要求更有效的数 据管理能力和更快、更精确的查询。因此，对x m l 数据的索引及其结构查询 的研究显得日益重要。 为了有效的支持x m l 查询，特别是结构查询，目前已有很多文献提出了 x m l 数据的各种编码方案。这些编码方案更多地是将关注点放在如何设计编码 结构以改进索引空间，以及在进行结构查询时所花费的时间代价较小，而对于 支持x m l 文档数据的更新问题则很少进行深入的探讨。如何既能改进x m l 索 引的结构查询效率，又能降低文档更新的维护代价，这是本文研究的主要内容。 本文基于区间编码的索引编码方案，提出了一种改进的优化方案，将从索 引结构、结构连接查询和文档更新维护三个方面对该方案进行研究。 本文的主要研究工作如下： ( 1 ) 改进区间预留算法。针对该算法中人为预留区间存在一定的缺陷与不 足，采用按照节点密度进行区间分配，从而对索引空间进行有效合理地分配， 提高其空间利用率。 ( 2 ) 在结构连接查询中，对参与连接的节点集进行先序排序，使其满足块间 有序；在s t a c k t r e e 算法的基础上利用分块有序的节点编码信息跳过那些无需 参与连接的祖先或后代节点，从而快速完成结构连接。 ( 3 ) 对于x m l 文档更新算法引入假设检验方法进行决策分析。在数据更新 时，通过判断当前的区间划分是否在可接受的范围内，来降低将来文档在更新 时需要重新划分区间的机率，从而达到对区间的有效划分和利用，降低对x m l 文档的维护代价。 最后，本文开发了原型系统对提出的索引方案进行了一系列实验。实验结 果表明基于区间编码的索引优化方案具有较好的性能。 关键词：x m l 区间编码结构连接假设检验 a b s t r a c t a b s t r a c t a sat o o lo fd a t ae x c h a n g ea n di n f o r m a t i o ni n t e g r a t i o ni nn e t w o r k ，x m lh a s b e c o m ean e wg e n e r a t i o no fw e bl a n g u a g ef o ri t sf e a t u r e so fs e l f - d e s c r i p t i v e ， e x c h a n g e i n c r o s s p l a t f o r m ，e t c a ni n c r e a s i n g n u m b e ro fs t r u c t u r e do r s e m i s t r u c t u r e dd a t aa r es t o r e da n de x c h a n g e da sx m lf o r m a ti ni n t e r n e t w i t ht h e v o l u m eo fx m ld a t ai s g r o w i n g ，w er e q u i r em o r ee f f i c i e n td a t am a n a g e m e n t c a p a b i l i t i e sa n df a s t e r , m o r ep r e c i s eq u e r i e s t h e r e f o r e ，t h es t u d yo fi n d e xa n di t s s t r u c t u r eq u e r i e sf o rx m ld a t ai si n c r e a s i n g l yi m p o r t a n t a tp r e s e n t ，m a n yp a p e r sp r o p o s e dav a r i e t yo fe n c o d i n gs c h e m ef o rx m ld a t a i no r d e rt os u p p o r tx m l q u e r i e se f f e c t i v e l y , e s p e c i a l l ys t r u c t u r eq u e r i e s m o s to f t h e mf o c u so nh o wt od e s i g nt h ee n c o d i n gs t r u c t u r et oi m p r o v et h ei n d e xe n c o d i n g s p a c ea n ds p e n dl e s st i m ei ns t r u c t u r a l - j o i nq u e r i e s h o w e v e r , t h e r ea r er a r eg o o d d i s c u s s e sf o rs u p p o r t i n gu p d a t e dx m ld o c u m e n t s h o wt oi m p r o v et h ee f f i c i e n c yo f x m ls t r u c t u r eq u e r i e sa sw e l la sr e d u c em a i n t e n a n c ec o s t sf o ru p d a t e dx m l d o c u m e n t s ，w h i c hi st h em a i nc o n t e n t so ft h i sp a p e r t h i sp a p e rr a i s e sa ni m p r o v e da n do p t i m i z e di n d e xe n c o d i n gs c h e m eb a s e do n r e g i o ne n c o d i n g o nt h r e ea r e a s ：i n d e xs t r u c t u r e ，s t r u c t u r a l - j o i nq u e r i e sa n d m a i n t e n a n c ef o ru p d a t e dx m ld o c u m e n t s t h em a i nr e s e a r c hw o r ki nt h i sp a p e ri sa sf o l l o w s ： ( 1 ) i m p r o v er e g i o n r e s e r v e a l g o r i t h m s a i m i n g a ts o m ed e f e c t sa n d s h o r t c o m i n g so fm a n - m a d er e s e r v e dr e g i o ni n t h i sa l g o r i t h m ，w ed i s t r i b u t er e g i o n b a s e do nn o d e sd e n s i t y i tw i l lm a k et h ei n d e xs p a c ea l l o c a t e dr a t i o n a l l ya n d e f f e c t i v e l y ，a sw e l la si m p r o v eu t i l i z a t i o nr a t eo fs p a c e ( 2 ) i ns t r u c t u r a l - j o i nq u e r i e s ，w et a x i st h en o d e sc o l l e c t i o nw i t hp r e o r d e rt o m e e ta no r d e r l ym a n n e ri ni n t e r - b l o c k s ，t h e nu s en o d e se n c o d i n gi n f o r m a t i o no f t h e s eo r d e r l yn o d e st os k i po v e ra n c e s t o r so rg e n e r a t i o n so fn o d e sw h i c hd o n tn e e d t op a r t i c i p a t ec o n n e c t i o nb a s e dt h es t a c k t r e ea l g o r i t h m ，t h e r e b yc o m p l e t er a p i d l y s t r u c t u r a lj o i n a b s t r a c t ( 3 ) i m p o r th y p o t h e s i st e s t i n gm e t h o d st od e c i s i o na n a l y s i sf o ru p d a t e d a l g o r i t h mi nx m l d o c u m e n t s w ec a nd e t e r m i n ew h e t h e rt h ec u r r e n tr e g i o np a r t i t i o n i sa c c e p t a b l ea f t e rx m ld a t ai s u p d a t e d t h u si t w i l lr e d u c eo c c a s i o n so ft h e p r o b a b i l i t yo fr e g i o nr e p a r t i t i o n ，a sw e l la sr e a l i z ee f f i c i e n tp a r t i t i o na n du t i l i z a t i o n r a t eo fr e g i o na n dr e d u c et h ef u t u r em a i n t e n a n c ec o s to fx m l d o c u m e n t s f i n a l l y , t h i sp a p e rd e v e l o p s ap r o t o t y p e s y s t e mw i t h t h e i m p r o v e da n d o p t i m i z e di n d e xe n c o d i n gs c h e m eb a s e dr e g i o ne n c o d i n g t h et e s tr e s u l t ss h o wt h i s s c h e m ah a sb e t t e rp e r f o r m a n c e k e yw o r d s ：x m lr e g i o ne n c o d i n g s t r u c t u r a lj o i n h y p o t h e s i st e s t i n g i l l 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文系本人在 南开大学工作和学习期间创作完成的作品，并己通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库”。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解直珏太堂图盘焦羞王堡叠! 焦旦堂鱼诠窒数笪堡查选! 同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文 在保密期限过后同样适用。 院系所名称： 作者签名： 学号： 日期：年月日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：肖璞 伽呷年歹月苍日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 目 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中已经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均己在文中以明确方式标明。本学位论文原创性声明的 法律责任由本人承担。 学位论文作者签名：商璞 巩。彳年歹月2 j 日 第一章绪论 第一章绪论 1 1 引言 随着互联网的发展和普及，人们从世界各地实时的接收和发送大量的最新 的信息，但在信息交换的过程中存在着一个突出的问题，就是多种多样的数据 格式，给信息的有效使用带来了障碍。所以，如何以最便捷、最可靠、最有效 的方式获取所需的信息是一个很大的困扰。人们期待着能够找到一种可以描述 任何逻辑关系的数据格式来统一电子数据的存储，从而不再为数据格式的不统 一而苦恼和困惑。于是，万维网协会( w o r l dw i d ew e bc o n s o r t i u m ，w 3 c ) 于1 9 9 8 年2 月发布了一种标准，即x m l ( e x t e n s i b l em a r k u pl a n g u a g e 可扩展标记语言) 。 它将s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e 标准通用标记语言) 的丰富功 能与h t m l 的易用性结合到w e b 的应用中，以一种开放的、自我描述方式定 义了数据结构。它在描述数据内容的同时能突出对结构的描述，从而体现出数 据之间的关系。这样所组织的数据对于应用程序和用户都是友好的、可操作的。 在x m l 中，用户可以自由的定义标记名以及与标记相关的元素及元素层 次，这是x m l 的主要特征。x m l 是以文本形式来描述的一种文件格式，所以 适合于各种平台环境的数据交换。同样，由于使用文本来描述内容，可以越过 不同平台的障碍进行正常的数据交换。但是，文本形式也会因为文字代码的不 同造成不能阅读的问题，在这一点上x m l 有着非常完美的解决方案。由于x m l 在可扩展性、可移植性和结构性等方面的突出优点，它的应用范围突破了h t m l 所达到的范卧1 1 。 随着i n t e m e t 的快速发展，尤其是电子商务、w e b 服务等应用的广泛使用， 越来越多的结构化或半结构化的数据采用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 数 据文件中，元素名将反复出现，这势必会影响到查询的效率。为了尽可能的提 高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 l 。 近些年，人们针对x m l 提出了很多索引结构，它们在存储媒质、构造索 引的方法以及所能够支持的查询种类等方面各不相同，总的来说可分为两种： 基于路径的索引和基于节点的索引p 】。 基于路径的索引是以x m l 树结构中节点的路径信息为基础，采取某种约 简方式，使得约简后的树结构只维护不同的路径信息，而不会存在具有相同路 径的两个节点1 3 。 基于节点的索引本质上是将x m l 数据分解为数据单元的记录集合，同时 在记录中保存该单元在x m l 数据中的位置信息。与基于路径的索引不同，基 于节点的索引打破了必须通过标签路径查找节点这一限制，将x m l 数据分解 成规范形式的节点记录。由于保存了节点的位置信息，而且能够很好地结合到 成熟的关系数据库管理系统中，因此它是目前应用最广泛的一种索引1 3 1 。 2 第一章绪论 很多研究x m l 索引的文献都将关注点放在如何改进索引空间和结构查询 中，而在支持x m l 文档数据更新的问题上则很少进行深入的探讨。然而，从 数据管理的角度而言，对x m l 数据修改的支持是非常必要的。特别是在采用 了节点编码的方案后，会降低存储空间的利用率。如何在文档数据更新时，采 用合理而有效的算法进行重新编码，这也是本文研究的主要内容之一。 正是由于x m l 索引在x m l 数据库领域中具有重要的理论意义和实践意 义，而且现有的基于节点编码的索引技术在同时解决结构查询和数据更新方面 存在一定的不足，本文将对x m l 索引进行深入探讨和研究，提出一种新的基 于区间编码的既能改进结构连接的效率又能改进x m l 文档更新算法的优化方 案。 1 3 本文主要内容 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 结构连接算法和文 档数据更新的算法，以节省索引存储空间，提高查询效率，降低文档维护代价。 以下是本文的主要研究内容： ( 1 ) 本文在研究x m l 文档结构特点和基于区间编码的索引的基础上，结合 x m l 节点有序的特点，给出一种改进的节点编码方案； ( 2 ) 借鉴区间预留规则，提出一种新的按照节点密度分配区间的改进算法， 以提高索引空间的利用率； ( 3 ) 利用本文给出的x m l 节点编码方案，对参与连接的节点集进行先序排 序，使其满足块间有序；在s t a c k t r e e 算法中利用区间编码的信息改进结构连 接算法，给出算法的具体实现过程，并结合实例验证该算法的性能； ( 4 ) 给出x m l 文档数据更新算法。在对x m l 索引树进行更新的时候，引 入概率论与数理统计中假设检验的基本思想与方法，判断当前索引树的区间划 分是否合理。这样的设计思想使得x m l 索引区间的分配在不合理的情况下， 能够得到及时的调整，以适应未来数据更新的需要。 3 第一章绪论 ( 5 ) 给出x m l 文档数据更新算法的具体实现过程，并对算法进行实验分析。 结果表明，该算法可以及时地判断区间分配是否在可以接受的程度内，并合理 地进行调整，使索引空间利用率得到了提高。 1 4 本文的组织结构 本文按照如下方式组织： 第一章绪论，该部分介绍了本文的研究背景、问题现状以及研究的内容， 并对本文的研究思路和章节安排进行简单的介绍。 第二章x m l 索引技术，对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 数据的索引及结构查询的研究显得日益 重要。 2 1 1x m l 的发展 2 1x m l 文档 早在1 9 6 9 年，m m 公司就开发了一种文档描述语言g m l ，用于解决不同 系统中文档格式不同的问题。g m l 是i b m 许多文档系统的基础，包括s c r i p t 和b o o k m a s t e r ，接下来的日子里，这个语言在1 9 8 6 年演变成一个国际标准 ( i s 0 8 8 7 9 ) ，并被称为s g m l 。s g m l 是很多大型组织的文档标准，是语言无关 的、结构化的、可扩展的语言，它允许内容和表示的分离。这些特点使得它在 很多公司受到欢迎，被用来创建、处理和发布大量的文本信息【4 】。 1 9 8 9 年，欧洲粒子物理研究中心的研究人员开发了基于s g m l 的超文本版 本，被称为h t m l 。h t m l 继承了s g m l 的许多重要的特点，比如结构化、实 现独立和可描述性。但是同时它也存在很多缺陷，比如它只能使用固定的有限 的标记，而且只侧重于对内容的显示。同时随着w e b 上数据的增多，这些h t m l 存在的缺点就变得不可被忽略。w 3 c 提供了h t m l 的几个扩展用来解决这些 问题，最后，它决定开发一个新的s g m l 的子集，称为x m l 。x m l 的出现就 是为了解决h t m l 的缺点而开发的一种标记语言。x m l 使得现有的i n t e m e t 协议和软件更为协调，从而简化了数据处理和传输。x m l 之所以较s g m l 更 为简化，很大程度上是出于易用性的考虑：人们对标记的读写过程应该使用现 有的、简便通用的工具，同时，我们也应当简化计算机对文档和数据交换的处 理。由于有太多的可选功能，s g m l 变得过于复杂，以至于很难编写出针对这 种语言的普通解释器，而x m l 的解释器则简单得多。作为一个不错的s g m l 5 第二章x m l 索引技术 子集，x m l 还保持了对现有的面向s g m l 的系统的向下兼容性。这样，用x m l 标记过的数据就仍然可以在这些系统中使用，为基于s g m l 的行业节省了大笔 的改造费用，同时，与w e b 的结合也使得它们更便于被访问。于是，1 9 9 8 年2 月，x m l l 0 成为了w 3 c 的推荐标准。 2 1 2x m l 文档结构 x m l 是用来描述诸如h t m l 之类的标记语言的规范。h t m l 是一种用来 对用w e b 浏览器表示的信息进行编码的特定标记语言，它定义了一套固定的 标记，用来描述一定数目的元素。而x m l 允许用户定义新的标记用来组织用 户想发送的任何类型的数据或文档。这些标记必须根据x m l 规范来创建，但 是在标记的意义上，也具有相当的灵活性。x m l 定义了一套元句法，与特定领 域有关的标记语言( m u s i c m l 、m a t h m l 和c m l ) 都必须遵守。如果一个应用程 序可以理解一套元句法，那么它也就能够自动地理解所有的由此元语言建立起 来的标记语言。浏览器不必事先了解多种不同的标记语言使用的每个标记【4 】。 x m l 规范规定了x m l 数据必须满足的条件，其基本的形式是x m l 文档。 x m l 文档的结构可以从物理和逻辑两方面来看【4 】。 从物理上而言，文档由称为实体( e n t i t i e s ) 的存储单元组成，实体都具有内容 并且都通过实体的名字进行标识。实体可以是一段文本，一个文件，一个数据 库记录或者其他包含数据的项目，一个实体可以引用其它的实体，从而将它们 包含在文档中。文档开始于“根( r o o t ) ”或者文档实体( d o c u m e n te n t i t y ) 。格式良 好的x m l 文档形成了一种层次树结构，这个树结构的树根就是文档实体，与 其它实体不同，文档实体没有名字，只是用于表示文档树的根。x m l 文档的根 元素被称为文档元素( d o c u m e n te l e m e n t ) ，它和在其外部出现的处理指令，注释 等作为文档实体的子节点，而根元素本身和其内部的子元素也是一棵树【4 】。 实体可以包含已分析( p a r s e d ) 或未分析i 拘( u n p a r s e d ) 数据。已分析的数据由字 符组成，其中一些字符组成字符数据，另一些字符组成标记。已分析的实体 ( p a r s e de n t i t y ) t 勾容被成为它的代替文本，这个文本被看称是文档整体的一部分， 在x m l 处理器分析x m l 文档时，凡是文档中出现引用已分析实体的地方，都 将被该实体的内容所替换。未分析的实体( u n p a r s e de n t i t y ) 是一种资源，它的内 容可以是也可以不是文本，并且如果是文本的话，可以不是x m l 文本，每一 6 第二章x m l 索引技术 个未分析的实体有一个相关联的用名字标识的记号( n o t a t i o n ) 。除了要求x m l 处理器能向应用程序提供可用的实体和记号的标志符之外，x m l 对未分析的实 体内容不做任何限制。已分析的实体以实体引用的方式通过名字来调用，未分 析的实体通过e n t l l r y 或e n t i t i e s 属性中给出的名字来调用1 4 。 从逻辑上而言，一个x m l 文档通常由五部分组成：声明、元素、注释、 字符引用和处理指令1 5 。它以声明开始，x m l 声明其实是一个处理指令，它指 定合适的工具来处理x m l 文档。元素是x m l 文档的基本结构，可以这么说， x m l 文档是由一些嵌套的元素结构所组成【2 1 。图2 1 表示的是一个有关书店藏 书信息的x m l 文档。 b o o kc a r e g o r v = ”c o o k i n g ”) - e v e r y d a yi r a li a n - - g l a d ad el a u r e l i t ；i i s 20 0 5 3 0 0 0 h a r r yp o t t e r dk r o w li n g 20 0 5 2 9 5 0 l e a r n i n gx i l e r i kt r a y 20 0 3 3 9 。9 5 图2 1x m l 文档示例 一个x m l 文档能够被建模为一个有序的、边标记的树。这棵树从根部开 始，并扩展到树的最底端。在树模型中，节点是最基本的概念，它可以表示文 档元素、属性或文本数据等 6 1 。一个x m l 文档有一个唯一的文档节点，称为根 节点。边表示元素一子元素( 或双亲一孩子关系) 。图2 2 表示的是图2 1 所示x m l 文档的一个树模型。 7 第二章x m l 索引技术 图2 2 x m l 文档树 实际上x m l 将数据组织成为一棵树，通过解析x m l 文档，为x m l 文档 在逻辑上建立一个树模型，树的节点是一个个的对象。这样通过操作这棵树和 这些对象就可以完成对x m l 文档的操作。 2 1 3x m l 文档的特点 与w e b 上最普遍的数据表形式h t m l 相比，x m l 具有以下特点 7 j ： ( 1 ) 更多的结构和语义。x m l 侧重于对文档内容的描述，而不是文档的显 示。用自定义的标记描述了数据的语义，便于对数据的理解和机器的自动处理。 ( 2 ) 可扩展性。x m l 允许用户自己定义标记和属性，可以有各种定制的数 据格式。 ( 3 ) 简单易用。与通用标记语言s g m l 相比，x m l 简单易用，便于掌握， 这是它得以推广的重要原因。 ( 4 ) 自描述性。x m l 将对数据的语义描述和数据内容本身都包含在x m l 文档中，使数据具有很大的灵活性。 ( 5 ) 数据与显示分离。x m l 所关心的是数据本身的语义，而不是数据的显 示方式，所以可以在同样的x m l 数据上定义多种显示形式，非常灵活。 x m l 的这些特点使得它不但迅速成为了网络数据交换的事实标准，而且正 在逐渐成为数据表示的标准。随着它的流行，一系列相关的标准( 如x m l s c h e m a ，x q u e r y ，x m l ，d a t am o d e l 等) 也不断出现，形成了围绕x m l 的标 8 第二章x m l 索引技术 准集合。x m l 是面向文档的h t m l 和面向模式的d b m s 之间的一个重要桥梁， 它具有使数据库管理系统和w e b 应用前所未有的紧密结合的潜力。 2 2x m l 索引技术介绍 x m l 类型的数据成为当前主流的数据形式，因此，x m l 数据的管理技术 成为当前的研究热点。 2 2 1x m l 与数据库 为什么要将x m l 和数据库相联系? 举例来说，如果有一个电子商务的应 用程序需要使用x m l 来进行数据传输，我们所关心的是数据本身应该具有的 结构，而不是它在文档中实际的存储结构。如果应用程序很简单，基本的文件 系统就可以满足需求。但如果应用本身很复杂的话，就需要一个完整的开发应 用环境来支持x m l 。另一方面，假设有一个w e b 站点，它的内容是由一系列 x m l 文档构成的，我们不仅要管理这个站点，同时还需要提供给用户一个搜索 该站点内容的机制。而这些都需要借助数据库来实现。选择一个数据库的最重 要的因素是是否需要数据库来存储数据或者文档，如果需要存储数据的话，则 需要一个关系数据库或者对象数据库来存储实际的数据，同时需要中间件在数 据库和x m l 文档之间建立桥梁关系。另外，如果想要存储文档，则需要一个 内容管理系统，通过它进行文档的存储【8 】。 当存在大量数据需要处理分析的话，最好是把这些数据放到数据库中，所 以几乎所有大型的商业应用系统都是和数据库相关联的。而且如果x m l 需要 在商业领域大展宏图的话，也必须要和数据库相联系【9 】。这里首先需要讨论的 一个问题是，x m l 本身是不是数据库，从严格的意义上来说，x m l 仅仅意味 着x m l 文档。因为尽管一个x m l 文档包含数据，但是如果不通过其他的软件 来进行数据处理的话，它本身只不过是一个文本文件，所以x m l 本身不能和 数据库挂上钩。但是加上一些其他的辅助工具，我们可以把整个x m l 看成是 一个数据库系统。x m l 文本本身可以看成是数据库中的数据区，d t d 或者 s c h e m a s 可以看成是数据库模式设计，x q l 可以看成是数据库查询语言，s a x 或d o m 可以看成是数据库处理工具。当然它还是缺少数据库所必须的一些东 9 第二章x m l 索引技术 西，比如有效的存储组织、索引结构、安全性、事务处理、数据完整性、触发 器、多用户处理机制等等1 8 1 。 随着w e b 技术的不断发展，信息共享和数据交换的范围不断扩大，传统的 关系数据库也面临着挑战。数据库技术的应用是建立在数据库管理系统基础上 的，各数据库管理系统之间的异构性及其所依赖操作系统的异构性，严重限制 了信息共享和数据交换范围；数据库技术的语义描述能力差，大多通过技术文 档表示，很难实现数据语义的持久性和传递性。而数据交换和信息共享都是基 于语义进行的，在异构应用数据交换时，不利于计算机基于语义自动进行正确 数据的检索与应用；数据库属于高端应用，需要昂贵的价格和运行环境。而随 着网络和i n t e r n e t 的发展，数据交换的能力已成为新的应用系统的一个重要要 求。x m l 的好处是数据的可交换性( p o r t a b l e ) ，同时在数据应用方面还具有如下 优点【1 】：x m l 文件为纯文本文件，不受操作系统、软件平台的限制；x m l 具有基于s c h e m a 自描述语义的功能，容易描述数据的语义，这种描述能为计 算机理解和自动处理；x m l 不仅可以描述结构化数据，还可有效描述半结 构化，甚至非结构化数据。 2 2 2x m l 索引技术 x m l 数据库的索引技术对x m l 数据查询处理起着至关重要的作用，如果 没有索引的支持可能带来很大的i o 代价和语意支持方面的限制。利用索引提 高查询效率实际上是用空间换时间的做法。 目前，x m l 索引技术分为基于路径的索引和基于节点的索引【3 】。 ( 1 ) 基于路径的x m l 索引 基于路径的索引是以x m l 树结构中节点的路径信息为基础，采取某种约 简方式，使得约简后的树结构只维护不同的路径信息，而不会存在具有相同路 径的两个节点。已经提出的这类索引有：d a t a g u i d e s 索引、i n d e xf a b r i c 索引、 x m l 数据的自适应路径索引( a d a p t i v ep a t hi n d e xf o rx m ld a t a ，a p e x ) 。 d a t a g u i d e s 索引是从根节点为起始的精练路径的一种结构摘要。边标签串 联在一起形成的字符串路径在d a t a g u i d e s 中只描述一次。d a t a g u i d e s 减少了遍 历路径查询时所需的部分节点，它对从根部遍历x m l 文档是有效的。但对于 l o 第二章x m l 索引技术 含有通配符的路径查询或对带有x p a t h 标准中定义的d e s c e n d a n t o r - s e l f 轴的路 径，查询要进行多次的连接操作，查询效率较低，并且存在数据冗余。 i n d e xf a b r i c 是在p a t r i c i at r i e 树上发展而来的一种索引结构，它把到每个 元素节点的每条标记路径都用一个字符串编码，再将这些编码值插入到p a t r i c i a t r i e 树中去，从而将按照路径方式对x m l 数据的查询转化为对字符串的查询。 在查询时先将查询路径编码成字符串的形式，再在索引树中进行查找。i n d e x f a b r i c 索引优点是存储了x m l 数据的层次结构信息，统一处理了有模式和无模 式信息情况下的x m l 数据的检索，并且对x m l 数据的查询和更新所需要的时 间与层次相关而不是与索引关键字的长度相关。i n d e xf a b r i c 索引的缺点在于丢 失了元素节点间的结构关系，因为它只保留了有文本值的元素节点的信息。因 此，与d a t a g u i d e s 索引类似，i n d e xf a b r i c 索引处理带有x p a t h 标准中定义的 d e s c e n d a n t o r - s e l f 轴的部分匹配查询表达式效率不高。 为此，a p e x 引入了依赖于x m l 数据查询分布的信息：将经常出现的x m l 查询语句对应的标签节点预先保存在一个哈希结构中，它的作用类似于c a c h e 的功能。当有新的查询要求处理时，首先在哈希表中搜索是否有满足的节点集 合，但它对于带有元素值或属性值的查询表达式的处理效率较低。 ( 2 ) 基于节点的索引 基于节点的索引本质上即是将x m l 数据分解为数据单元的记录集合，同 时在记录中保存该单元在x m l 数据中的位置信息。与基于路径的索引不同， 基于节点的索引打破了必须通过标签路径查找节点这一限制，将x m l 数据分 解成规范形式的节点记录。由于保存了节点的位置信息，而且能够很好地结合 到成熟的关系数据库管理系统中，因此它是目前应用最广泛的一种索引。 根据对位置信息的编码方式不同，基于节点的索引一般可以分为以下几类： 基于前缀的索引 基于前缀的索引主要是根据d e w e y 编码【l0 】生成的索引。前缀编码的基本思 想是直接将一个节点的双亲节点的编码作为该节点编码的前缀，对于前缀编码， 要判断一个节点v 是否是另一个节点u 的后代，只要判断u 的编码是否v 的编 码的前缀。前缀编码索引的一个重要性质是它们的字典有序：以节点r 为根的 子树中的任意一个节点u ，它的前缀编码c ( u ) 大于( 小于) 它的左兄弟子树( 右兄弟 子树) 中所有节点的前缀编码。因此，基于前缀的索引不仅能够有效地支持包含 关系的运算，而且能够有效地支持文档位置关系的计算。 第二章x m l 索引技术 基于区间编码( r e g i o n b a s e d ) 的索引 对于区间编码索引，树t 中的每一个节点被赋予一个区间编码 b e g i n ，e n d 】， 满足：一个节点的区间编码包含它的后代节点的区间编码。也就是说，树t 中 的节点u 是节点v 的祖先，当且仅当b e g i n ( u ) e n d ( v ) 。两个节 点的区间编码之间的关系为：它们要么完全不相交，要么完全包含。 第一个区间编码方案是d i e t z 编码【1 3 1 ，树t 中的每一个节点被赋予一个具 有先序遍历序号和后序遍历序号的二元组 。由于树t 中的一个祖先 节点u 在先序遍历( 后序遍历) 中必然出现在它的后代节点v 之前( 之后) 。因此， 节点u 和v 是祖先后代关系，当且仅当p r e ( u ) p o s t ( v ) 。因此， 树t 中的任意两个节点之间的祖先后代关系的检测能够在常数时间内被计算。 对于该编码方案，p r e 或p o s t 均可以作为节点的唯一标识。 另一个区间编码索引的典型例子是x i s s 索引【14 1 ，它为每个节点赋予一个 数字对 ，其中o r d e r 为扩展的前序编码，s i z e 为节点的子孙的范围。 对一棵文档树中的任意节点u 和v ，当且仅当为o r d e r ( u ) = o r d e r ( v ) ，则u 是v 的一个祖先。 x i s s 索引通过将原始查询语句分解为子表达式，然后分别针对这些子表达 式实现查询，最后对这些中间结果进行连接获得查询结果集，从而能较好地支 持含通配符的查询语句。不过，它是对每一个中间结果进行连接后得到最终查 询结果。虽然这种方法能够解决所有的通配符问题，可是这种中间结果的联结 很有可能是非常耗时的，特别是对于长路径的简单表达式。 以下是对两种索引机制的比较： 基于路径的索引采用基于节点合并的策略，通过节点等价、路径等价等技 术，得到比原始文档小得多的索引结构，它的结构仍然是树型的，所以在处理 查询时，基本上仍须遍历整个索引树才能得到结果。这种索引可以很好地支持 简单路径表达式的查询，但是对于正则路径表达式，它的效果不是很理想。 基于节点的索引通过编码技术索引每一个节点，节点之间的结构关系通过 编码可以在常数时间内确定。它可以很好地支持正则路径表达式，但是对于长 的路径表达式，尤其是在查询产生的中间结果很多的时候，节点索引的连接操 作代价高昂。 基于路径的索引和基于节点的索引各有优缺点，但可以优势互补。目前在 实际应用中，基于节点的索引应用更为广泛，研究得也比较成熟。 1 2 第二章x m l 索引技术 2 2 3 基于节点的索引 基于节点的索引主要有两种获取位置信息的方法【1 1 】，一种是节点序号方法 ( n o d en u m b e r i n gm e t h o d ) ，另一种是节点路径方法( n o d ep a t hm e t h o d ) 。对它们的 研究占了x m l 数据处理研究文献中相当大的部分。根据路径信息表现形式的 不同，基于节点的索引又分为3 大类：基于节点序号的索引、基于节点路径信 息的索引和二者相结合的混合索引。 这类索引中的位置信息是节点在某种遍历序列中的序号。对于一个x m l 文档，设计遍历x m l 文档的策略，遍历的最终结果表现为一个由节点组成的 序列；相应地，节点的标签在序列中就有一个序号，该序号表明了节点间的次 序关系，也能够反映节点间的结构关系，进而就可以基于该序号信息捕获节点 间的结构关系【2 1 。 节点序号类x m l 索引的基本思想是：基于x m l 文档设计某种遍历策略， 得到由元素组成的序列，节点的标签在序列中就具有唯一的次序，将序列与某 指标集( 最常用的就是自然数) 建立一一映射的关系，对应序列中某个标签