（计算机软件与理论专业论文）支持xml数据更新的编码方案与索引技术研究.pdf

摘要 x m l 已经成为i n t e r n e t 上数据表示和数据交换的标准格式。近 年来，在w e b 上涌现了大量的x m l 数据。为了更容易的操作x m l 文档中的数据，专家和学者们在编码、索引、查询等方面做了积极 深入的研究，已经提出了大量的编码方案和索引技术，但当x m l 数据需要频繁的更新时，由于这些编码方案和索引技术都不支持 x m l 数据的动态更新，需花很大的代价去重新编码和建立索引，严 重影响了它们的效率。为此，本文在支持x m l 数据动态更新的编码 方案和索引技术方面进行了有益的探索。 本文深入分析了x m l 文档的结点编码技术，提出了一种支持 x m l 数据动态更新的结点编码方案c s s u 。c s s u 编码采用字母、 数字和下划线对结点进行编码，改变了传统编码方案主要采用数字 序号进行编号的特点。由于插入和删除结点，不影响其他结点的编 码，完全不需要重新编码。c s s u 编码在任意两编码之间存在无穷大 的编码空间，不会出现l i m o o n 编码那样通过预留编码空间的方 式存在编码空间会用完和预留空间大小不容易确定的问题。所以当 x m l 数据需要频繁的更新时，可以成倍地提高结点编码的效率。 以c s s u 编码为基础，本文提出了一种新的支持x m l 数据动态 更新的索引d u i x 。d u i x 索引可以快速确定任意两结点间的结构关 系，同时保存了孩子一双亲元素的详细信息，并把相同标签路径的结 点聚簇在一起。d u i x 索引支持分支查询，不再依赖x m l 文档，访 问一条路径可得到该标签路径下的所有结点，跳过了大量不相关的 结点。与其他索引技术相比d u i x 索引的效率更高。 最后，本文对c s s u 编码和d u i x 索引与基于c t r e e 的索引和 x i s s 索引做了大量的对比性实验。结果表明，c s s u 编码和d u i x 索引是有效的。 关键词：路径摘要，编码方案，索引 a b s t r a c t x m lh a sb e c o m ean e ws t a n d a r df o r m a tt oe x p r e s sa n de x c h a n g e d a t ai nt h ei n t e r n e t i nr e c e n ty e a r s ，al a r g en u m b e ro fx m ld a t ah a s e m e r g e n c e d i no r d e rt op r o c e s st h ed a t ai n t h ex m l d o c u m e n t ，e x p e r t a n dr e s e a r c h e rh a v ed o n ep o s i t i v ea n dd e p t h s t u d yo ne n c o d i n g ， i n d e x i n g ，q u e r y i n ga n ds oo n ，al a r g en u m b e ro fc o d i n gs c h e m e sa n d i n d e x i n gt e c h n i q u e sh a v eb e e np r o p o s e d i t se x p e n s i v et or e - c o d ea n d r e i n d e xw h e nt h ex m ld a t au p d a t e df r e q u e n t l y w h i c ha f f e c t e dt h e e f f i c i e n c ys e r i o u s l y b e c a u s e t h e s e c o d i n g s c h e m e sa n d i n d e x i n g t e c h n i q u e s c o u l d n ts u p p o r td y n a m i c a lu p d a t i n gx m ld a t a i nt h i s p a p e qw eh a v e r e s e a r c h e d u s e f u l l y o nx m lc o d i n gs c h e m e sa n d i n d e x i n gt e c h n i q u e s ，w h i c he f f i c i e n t l ys u p p o r t e d t h a tx m ld a t a d y n a m i c a l l yu p d a t e t h i sp a p e ra n a l y s e de n c o d i n gt e c h n o l o g yo fx m ld o c u m e n t sa n d p r o p o s e d ac o d i n gs c h e m eo fs u p p o r t i n gx m ld a t ad y n a m i c a l u p d a t i n g ( c s s u ) c s s uc o d es c h e m ee n c o d e st h en o d ew i t hl e t t e r s ， d i g i t a l sa n du n d e r l i n e sw h i l et h o s et r a d i t i o n a lc o d i n gs c h e m e se n c o d e t h en o d ew i t hd i g i t a l t oi n s e r ta n dd e l e t en o d e sc o d i n g ，c s s ud o e sn o t a f f e c tt h eo t h e rn o d e sc o d i n ga n dn e e d n tr e c o d ea ta 1 1 i te x i s t si n f i n i t e c o d i n gs p a c eb e t w e e na n yt w oc o d i n g sa n dw o u l dn o ta p p e a r t h e p r o b l e m st h a tl i m o o nc o d i n gr e s e r v e dc o d i n gs p a c ea n dw o u l dr u n o u to fc o d i n gs p a c ea n dt h es i z ei sn o te a s yt od e t e r m i n e t h ec s s u c o d i n ge f f i c i e n c yc a nm u l t i p l yi m p r o v ew h e nt h ex m l d a t au p d a t e s f r e q u e n t l y an e wi n d e xd u i xb a s e do nc s s uc o d i n gw a sp r o p o s e di nt h i s p a p e r , w h i c hs u p p o r t e dd y n a m i c a lu p d a t i n gx m l d a t a d u i xc o u l d q u i c k l yd e t e r m i n et h e s t r u c t u r er e l a t i o n sb yc o d i n gb e t w e e na n yt w o i i i n o d e s ，a n dp r e s e r v ed e t a i l e dc h i l d p a r e n ti n f o r m a t i o n ，a n dc l u s t e rn o d e s o ft h es a m el a b l ep a t h d u i xs u p p o r t e db r a n c hq u e r y ，w h i c hn ol o n g e r r e l i e do nx m l d o c u m e n t s ，a n di tg o ta l ln o d e sb yv i s i t i n gap a t h ，a n d s k i p p e da b u n d a n to fi r r e l e v a n tn o d e s i t sm o r ee f f i c i e n c yt h a no t h e r i n d e xt e c h n i q u e s f i n a l l y , t h i sp a p e rd i dal a r g en u m b e ro fe x p e r i m e n t st oc o m p a r e c s s ua n dd u i xw i t hi n d e x b a s e dc t r e ea n dx i s s t h er e s u l t s d e m o n s t r a t e dt h a tt h ec s s ，a n dd i1 1 xw e r ee f f e c t i v e k e yw o r d s ：p a t hs u m m a r y , c o d i n gs c h e m e s ，i n d e x i n g 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：缘体绰劢听- o r - 6 月j 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大 学。同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ，( 请在以上相应方框内打“ ) 作者签名：莽舔彳日期：砷年否月日 导师签名：纠屹睁日期：加7 年b 月士日 支持x m l 数据更新的编码方案与索引技术研究 1 绪论 1 1 论文选题及研究意义 x m l l l l ( 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 组织提出的，一个在i n t e r n e t 上进行数据表示和数据交换的新 标准。x m l 已经取得了巨大的成功，特别是在w w w 上被广泛接 受和采用，其目标是定义计算机和人都方便识别的数据类型。随着 w e b 技术的快速发展，x m l 数据已大量的存在于当前信息社会中。 x m l 数据的管理和查询问题也越来越引起人们的重视。尽管x m l 数据表现形式灵活，可以描述非常复杂的结构，但其本质仍然是树 状的模型。树中的每个节点对应于一个元素，树中的边描述了元素 之间的父子关系【2 1 。 由于x m l 数据的嵌套结构和模式信息不全的特点，使得其结构 非常复杂，对它的查询处理也比较困难【3 1 。现有的查询语言如x p a t h 、 x q u e r y 都是通过路径表达式对x m l 文档进行查询。从x m l 文档 中快速地提取信息成为了各个领域的迫切需要，因此，怎样对x m l 文档进行高效索引和快速查询就成为了当今数据库领域的一个重要 而且非常紧迫的研究课题。 为了使得其它应用程序更容易对x m l 文档中的数据进行操作， 人们从存储、索引、查询等方面做了积极深入的研究。这些研究促 进了x m l 的发展，解决了现实中的诸多问题，许多优秀的研究成果 也已经有了一定规模的应用，比如s t a n f o r d 大学的l o r e 4 】系统。针 对不同的x m l 应用，人们提出了不同的x m l 索引结构，这些索引 结构能够满足特定环境下的需求，他们各有优点和适用范围。 但目前大多数索引结构没有考虑x m l 数据动态更新问题，当文 档的内容动态地增加、删除或更新时，这些索引将消耗大量的存储 空间和时间来重建索引。虽然有很少一部分索引算法支持x m l 数据 的动态更新，但仍存在不同程度的缺限，如文献【5 】通过预留编码空间 硕十学位论文 来支持x m l 数据更新，由于预留编码空间总有用完的时候，当预留 编码空间用完以后，不得不对x m l 文档树结点重新进行编码，并重 新建立索引。 因此，支持x m l 数据动态更新的结点编码方案及其索引结构的 研究对x m l 数据库领域具有非常重要的理论意义和实践意义。 本文将主要对x m l 结点编码和x m l 索引进行有益的探讨： 首先，深入分析了x m l 数据的结点编码技术，提出了支持x m l 数据动态更新的结点编码方案c s s u 。通过编码可以直接快速有效的 判断孩子与双亲结点，兄弟结点间的结构关系，降低结点对树型结 构的依赖程度，使得在执行查询表达式时不必遍历整个x m l 结构 树；c s s u 编码支持x m l 数据的动态更新，当x m l 数据进行插入 操作时，不需要改变任何已经存在的编码，只需要对新插入的结点 进行编码，当删除x m l 树结点时，只要将该结点的记录从数据库中 删除即可，删除结点不影响其他结点的编码，而且删除结点的编码 可以用于将来在此位置上插入x m l 结点的编码。由于在x m l 数据 进行更新操作时不需要对已经编码的结点重新进行编码，因此，当 x m l 数据需要频繁的进行更新是，c s s u 编码可以成倍地提高x m l 编码的效率。c s s u 编码另外一个重要特征就是：改变了传统编码方 案主要采用数字序号进行编号的特点，c s s u 编码主要是采用英文字 母对结点进行编码，并且可以按字典序排序，结点编码所占的空间 小于传统编码方案所占的空间。 其次，研究人员开发了许多查询语言，包括l o r e l ，x m l - q l ， x m l g l ，q u i l t ，x p a t h ，x q u e r y ，它们共同的特征为：采用正则路 径表达式的形式，其中，x p a t h 是实现x m l 数据遍历的基本语言， x p a t h 查询语句的处理方式只能采取遍历的方式在x m l 文档中寻找 满足查询语句结构关系的数据单元，效率不高。 同时基于结构摘要的索引构造技术，合并相同标签路径的结点， 建立了新的支持x m l 数据动态更新的索引结构( a nd y n a m i c a l l y u p d a t i n gi n d e xf o rx m ld a t a ，d u i x ) 。d u i x 充分利用成熟的关系数 支持x m l 数据更新的编码方案与索引技术研究 据库技术，解决访问一条路径即可得到该标签路径下的所有结点， 避免了相同标签路径的重复访问的缺陷，并减少早期处理过程中的 搜索空间。索引结构中保存了孩子双亲元素的详细信息，提高了访 问元素双亲的速度，因此，这是一种处理x m l 结构约束的有效索引 方法。 所以，本文的研究内容具有一定的实用价值和理论意义。 1 2 国内外主要研究现状 当前对x m l 查询和索引的研究非常多，比较有代表性的大致有 以下几种1 6 j ： 1 路径合并法 将相同或相似路径进行合并，一方面压缩了x m l 树型结构，另 一方面减少了查询遍历的分支数。s t a n f o r d 大学的l o r e 系统是较早 的面向半结构化数据的工程，其中的d a t a g u i d e s 7 是为半结构化数据 设计的索引技术，其中包含4 种不同的索引结构：值索引、标签索 引、边索引、路径索引。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 文档是有效的。但是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 可 能出现时间和空间的消耗呈指数膨胀的情况。 文献 8 】对有限的路径抽取结构摘要信息来建立索引，1 - i n d e x 精 确性最高，但其索引结构图的规模通常很大，影响了查询速度。 a ( k ) i n d e x 采用局部相似性概念，权衡查询准确性和结构大小。它能 准确查询长度不大于k 的路径，但当路径长度大于k 是，一般需要 遍历整个数据图以进行验证，运算代价很高。f & b i n d e x 能处理较 复杂、含有谓词修饰的路径表达式，但它与1 - i n d e x 相似，结构较大。 d ( k ) i n d e x 可以根据不同长度的查询调整索引结构中某些节点的相 硕士学位论文 似度，具有动态性。但d ( k ) i n d e x 对不相关节点作了分隔处理，增 大了存储代价，降低了查询效率。m 术( k ) i n d e x 是d ( k ) i n d e x 的改进 结构，它在保持动态特性的同时，有效抑制了对不相关节点的处理。 但对其序列结构的存储导致空间浪费，影响了查询性能。 m ，- c 宰( k ) i n d e x 1 9 】用单一结构取代了m = t = ( k ) i n d e x 的序列结构，避免存 储序列成员中的节点与边及序列成员之间的链接，提高其存储性和 查询效率 2 树结构分片索引法 将树型结构分片，然后对每个树结构片建立索引，这样就可以 随机访问树型结构的一些内部结点。其代表是i n d e x f a b r i c 。i n d e x f a b r i c 索引是在p a t r i c i at r e e 基础上采用关键字压缩机制为大量的字 符串建立索引，它通过前缀编码的方式将r a wp a t h 和r e f i n e dp a t h 编码成字符串，然后插入索引中。i n d e xf a b r i c 索引树是一种平衡树， 对索引的所有访问都只需要同样小的i o 资源。在检索i n d e xf a b r i c 索引时，从最左边的水平层的根结点开始，在一个块内部，沿着这 些边将所要查找的字符串与边标签进行比较。如果带标签的边是远 程连接，搜索处理就向右在下一层的某个不同块中进行查找。如果 没有带标签的边与所要查询的关键字字符串相匹配，搜索处理就沿 着非标签边到下一层中一个新的块中进行查找。查询处理就这样一 层一层地进行查询，直到最底层即o 层。在o 层中进行搜索期间， 如果没有标签边与所要查找的字符串相匹配，则该关键字的索引就 不存在。否则，顺着路径就能够找到该关键字字符串。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 的问题在于处理相对路径查询的 效率不高，并且由于使用层次化的p a t r i c i a 树，因而不适合基于范围 的查询。 3 结点相对位置编码索引法 该方法是当前国际上的研究热点之一，其主要思想是将x m l 文 支持x m l 数据更新的编码方案与索引技术研究 档树的各个结点的相对位置进行编码，编码一般采用前序后序遍历 或文档序等等，然后用b + 树或其变形存储这些结点口其代表有 x i s s i 5 1 、整枝连接技术【1 肚1 5 l ( h o l i s t i ct w i gj o i n ) 等，s o ls e r v e r 2 0 0 5 也对其进行了实现。 x i s s 系统利用了n u m b e r i n gs c h e m a 的能够快速地确定元素和 ( 或) 属性之间的祖先后代关系的优点，但是该索引系统所采用的 n u m b e r i n gs c h e m a 的 对中的o r d e r 和s i z e 值都是任意的 整数，这样不便于为以后插入的元素分配 值。另外， 一些重复出现的元素会在n a m ei n d e x 和e l e m e n ti n d e x 以及a t t r i b u t e i n d e x 中重复建立索引、重复存储，这样会浪费存储空间、增加检索 的时间，降低检索效率。 x i s s 索引的主要特点是将数字模式作用于数据文档，从而有助 于高效地获取结点间的依赖关系。为了处理基于r p e ( r e g u l a rp a t h e x p r e s s i o n 正则路径表达式) 的x m l 数据的查询，x i s s 提出了3 种索引结构：元素索引( e l e m e n ti n d e x ) 、属性索引( a t t r i b u t ei n d e x ) 矛l 结构索引( s t r u c t u r ei n d e x ) ，分别用来支持3 种必须的功能。通过元素 索引可以找到所有具有相同元素名字的元素实例。同样通过属性索 引可以找到具有相同属性名的属性实例。结构索引用来查找某一给 定元素的父元素和子元素。但是在这种现有的设计中存在着不足之 处。因为基于这种设计提出的快速确定x m l 数据层次结构中，祖先 子孙关系的编号机制很难从一般的祖先子孙关系区分出父亲孩子 关系，因此很难建立结构索引。祖先子孙关系可以从父亲孩子关系 演化而来，反之则不能。这将无法支持表示路径中父子关系的元素 元素的连接操作。同样，元素属性间的连接操作也存在同样的问题。 b r u n o 1 0 】提出了一种t w i g s t a c k 算法，采用x m l 文档标签聚集 索引，通过对与查询结点匹配的文档结点实例的一次扫描获得查询 结果，不会产生大量中间结果。文献【1 1 】提出基于运行栈的复杂t w i g p a t t e r n 查询处理算法，通过d t d 对查询语句进行逻辑优化，将查询 中的不确定路径转化为确定路径，算法需要遍历整个文档，且建立 硕士学位论文 索引的时间效率比较低，查询效率不高。文献 1 2 】用d e w e y 编码对 x m l 文档进行编码，提出一种基于d t d 的复杂x m lt w i g 查询处 理算法，通过d t d 有效的减少查询处理的规模，提高查询效率。文 献【1 3 】提出了一种新的分枝连接算法t r a c k ，采用叶子到根节点的查 询处理策略，合并了查询结点相同的树，并对分枝查询的最终结果 使用森林链进行压缩，在大部分情况下算法非常有效，当算法处理 父子结构时，由于使用了结果连接算法导致效率不高。 结构编码不同于其他的索引结构，需要先将查询拆分成若干子 查询，然后将子查询的结果进行结构连接。结构编码通过对x m l 数据和查询同时编码，将对x m l 的查询转变为对查询编码序列的搜 索，在一定程度上避免了复杂的结构连接。结构编码还支持包含通 配符路径的查询。应该说，将结构编码用于x m l 文档的查询是一种 新颖的索引方法，但还存在一些不足：a ) 没有按结点属性构建簇集 索引，当查询某结点是否存在时需要遍历整个文档。b ) 其索引结构 忽略了x m l 文档中的一些结构信息，查询结果与x m l 文档中相关 部分不同。c ) 不支持对关键字的查询。本文将在结构编码的基础上 结合簇集索引提出一种新的索引结构来弥补结构编码的不足。 4 全文索引法 利用现有的全文索引技术对x m l 进行索引。在o r a c l e1 0 9 ，s q l s e r v e r 2 0 0 5 中都有实现。 5 关系数据库存储法 主要思想是将x m l 数据拆分存入关系表，从而利用关系数据库 的强大功能对x m l 数据进行查询。其代表是s t o r e d ，o r a c l e1 0 9 对此进行了实现。 1 3 论文的主要研究内容和结构安排 1 3 1 主要研究内容 本文的研究工作和创新主要有： 第一，对x m l 树结点编码方案进行了较深入的分析，目前对 x m l 树结点的编码方案主要包括：基于路径的编码方案和基于区间 支持x m l 数据更新的编码方案与索引技术研究 的编码方案两大类，基本上都存在这样的一个缺点，当x m l 数据进 行动态更新时这些编码方案都需要重新编码，导致效率较低。为了 解决这个问题，本文提出了一种新的能有效的支持x m l 数据的动态 更新编码方案c s s u t l 6 1 ，当x m l 数据进行插入操作时，不需要改变 任何已经存在的编码，只需要对新插入的结点进行编码，在任意两 个结点之间可插入的结点个数是没有限制的，不存在编码空间会用 完的问题，当删除x m l 树结点时，只要将该结点的记录从数据库中 删除即可，删除结点不影响其他结点的编码，而且删除结点的编码 可以用于将来在此位置上插入x m l 结点的编码。由于在x m l 数据 进行更新操作时不需要对已经编码的结点重新进行编码，因此，当 x m l 数据需要动态的进行更新是，c s s u 编码可以成倍地提高x m l 结点编码的效率。c s s u 编码在完全避免重新编码的前提下，使编码 长度尽量减小，从而大大提高空间效率。c s s u 编码另外一个重要特 征就是：改变了传统编码方案主要采用数字序号进行编号的特点， c s s u 编码主要是采用英文字母、数字和下划线的组合对结点进行编 码，并且可以按字典序排序，结点编码所占的空间小于传统编码方 案所占的空间。 第二，本文将x m l 索引技术分为三类，基于结点记录的索引技 术、基于结构摘要的索引技术、基于序列的x m l 索引技术。分析典 型的x m l 索引技术，如基于c t r e e 1 7 1 树的索引技术、x i s s 索引技 术等，x m l 索引技术研究的主要方面包括：索引的数据结构、索 引的检索过程、索引的更新机制和索引的存储等。本文所提出一种 新的能有效支持x m l 数据动态更新的索引技术d u i x ，d u i x 索引 以在关系数据库为依托，以c s s u 编码为基础，将x m l 文档结点进 行分组，具有相同标签路径的等价结点置于同一组，按组号g i d 建 立聚簇索引，所有组号相同的记录在物理位置上相邻，每一条路径 都有一个唯一的组号与之对应。利用d u i x 索引进行查询时可以跳 过对大量无关元素的处理，从而提高了查询的效率。d u i x 索引结构 中保存了孩子双亲元素的详细信息，有利于进行分支查询。 硕士学位论文 最后，通过实验证明新的索引方案在性能方面是很好的。 1 3 2 论文结构安排 论文的结构安排如下： 第一章，从论文的选题和研究意义方面进行了阐述，对目前国 内外在x m l 索引和查询技术方面的研究进行了深入的分析。 第二章，介绍本篇论文相关的一些基础知识，包括x m l 数据的 产生与发展以及x m l 的相关技术标准，最后对x m l 索引和查询研 究领域的一些相关研究工作进行了分析。 第三章，对x m l 树结点编码方案进行了较深入的分析，提出了 一种新的能有效支持x m l 数据动态更新的编码方案，并给出了相应 的编码算法和x m l 数据动态更新的编码算法。 第四章，研究了目前存在的索引技术，对两种典型的索引作了 详细的介绍，提出了一种新的索引d u i x ，并给出了相应的查询处理 方法。 第五章，通过实验证明了新的索引d u i x ，在支持x m l 数据动 态更新方面比其它索引效率更快。 第六章，对本文工作加以总结，并提出今后的研究方向。 支持x m l 数据更新的编码方案与索引技术研究 2x m l 理论基础概述 2 1x m l 数据的产生和发展 i n t e r n e t 的迅速发展，使其成为了信息传递与共享的最重要和最 具潜力的媒介。在i n t e r n e t 上存在着大量内容丰富的的数据，这些数 据的内容包罗万象，包括数字图书馆，电子商务数据，新闻，生活 资讯等等，覆盖了人类知识的各个方面，而且形式各异，具有不同 的表现形式，如文本文件，多媒体文件，h t m l 文档，各种数据库 等。它们与传统的数据形式存在着明显的不同，具有面向显示，结 构灵活，形式多样，动态变化，以及数据海量等特点。除了数据的 新特点以外，应用需求也有许多新的特点。不断涌现的新型w e b 应 用，如网上购物，网络银行，数字图书馆，电子商务，远程教育等， 提出了许多新的数据处理要求，原有的最普遍的信息浏览功能不再 能满足人们的需求。如何管理w e b 上的大量信息，以满足用户对信 息的需求，成为了一个非常迫切的研究课题，为传统的计算机科学 技术提出了新的方向。 w e b 数据管理的研究吸引了来自许多研究领域的研究人员，其 中来自数据库领域的研究人员近年来试图从数据库的角度，运用数 据库中的许多概念来解决w e b 数据管理中的问题。数据库技术经过 经过二三十年的发展，已经较为成熟，但它所研究的对象是规则的， 具有良好结构的数据，而w e b 上数据的高度不规则性，灵活多变的 特点使得数据库技术的运用非常困难。w e b 数据的灵活多变与高效 的管理和查询之间似乎存在着不可逾越的鸿沟，x m - l 的出现为问题 的解决带来了新的契机。 x m l ( e x t e n d e dm a r k u pl a n g u a g e ) 是w 3 c 在1 9 9 8 年制定的一 项标准，用于网上数据交换。它是标准通用标记语言s g m l 的一个 子集，是一种元语言，用户可以定义自己的标记，用来描述文档的 结构。从s g m l 中经过精心修剪而来的x m l 既保持了s g m l 的功 硕士学位论文 能，同时又减少了s g m l 的复杂性。图2 - 1 是一个x m l 文档样例。 图2 - 1x m l 文档样例 与w e b 上已有的最普遍的数据表现形式h t m l 相比，x m l 具 有如下的一些特点： ( 1 ) 更多的结构和语义。x m l 侧重于对文档内容的描述，而 不是文档的显示。用户自定义的标记描述了数据的语义，便于对数 据的理解和机器的自动处理。 ( 2 ) 可扩展性。x m l 允许用户自己定义标记和属性，可以有 各种定制的数据格式。 ( 3 ) 简单易用。与通用标记语言s g m l 相比，x m l 简单易用， 便于掌握，这是它得以推广的重要原因。 支持x m l 数据更新的编码方案与索引技术研究 ( 4 ) 自描述性。x m l 将对数据的语义描述和数据内容本身都 包含在x m l 文档中，使数据具有很大的灵活性。 ( 5 ) 数据与显示分离。x m l 所关心的是数据本身的语义，而 不是数据的显示方式，所以可以在同样的x m l 数据上定义多种显示 形式，非常灵活。 x m l 的这些特点使得它不但迅速成为了网络数据交换的事实 标准，而且正在逐渐成为数据表示的标准。随着它的流行，一系列 相关的标准( 如x m ls 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 的标准集合，这反映了工业界对x m l 的 巨大支持。越来越多的w e b 应用，如电子商务，数字图书馆，信息 服务等采用x m l 作为数据表现形式，也有很多的网站采用x m l 作 为信息发布的形式，可以预见到将有越来越多的x m l 数据出现在 i n t e m e t 上。 由于x m l 具有很多不同于传统数据形式的特点，传统的数据处 理技术不能直接应用在x m l 数据上，许多问题都需要重新考虑。针 对x m l 数据处理技术，工业界和学术界都有着巨大的热情。工业界 在商用系统的扩展，针对x m l 数据处理的产品的开发，新的技术标 准的制定方面都做出了巨大的努力，也取得了很大的进展。而学术 界则针对一些基本的问题，如x m l 数据的数据模型和理论研究，新 的查询处理技术，数据的高效存储和索引机制等进行了深入地研究。 目前这个领域的工作受到了广泛的重视，而且还在不断的发展，新 的研究方向层出不穷。 2 2x m l 相关理论基础 x m l 数据模型与半结构化数据模型有很多相似性。可以说， x m l 是w w w 上的半结构数据。包含三要素：文档类型定义 d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 或模式( s c h e m a ) 、可扩展的样式语言 ( e x t e n s i b l es t y l el a n g u a g e ：x s l ) 以及可扩展链接语言( ( e x t e n s i b l e l i n kl a n g u a g e ：x l l ) 。其中，x s l 用于规定x m l 文档呈现样式的 语言，它使数据与表现形式相互独立；而x l l 用于扩展目前w e b 硕+ 学位论文 上已有的简单链接。下面就本文主要涉及的与x m l 相关的概念及相 关技术标准做个简要介绍。 2 2 1 x m l 文档格式定义语言 1 文档类型定义( d t d ) d t d 是一套关于标记符的语法规则。d t d 使用几个操作符：宰 ( 表示o 个或多个) 、+ ( 表示1 个或多个) 、? ( 表示o 个或1 个) 和! ( 表示选择) 来描述元素和子元素间的关系。d t d 原来是为s g m l 使用开发的，它可以是x m l 文档的一部分，但是它通常是一份单独 的文档或者一系列文档。因为x m l 本身不是一种语言，而是定义语 言的一个系统，想使用x m l 进行数据交换的工业或组织可以定义它 们自己的d t d 。d t d 的局限性：d t d 几乎没有数据类型的定义， d t d 的定义不符合x m l 语法，d t d 只能进行有限的扩展，d t d 的 约束能力不足，d t d 不够结构化，重用的代价相对较高。 2 模式s c h e m a s c h e m a 是作为d t d 的替代物出现的，相对于d t d 的明显好处 是x m ls c h e m a 文档本身也是x m l 文档，而不是象d t d 一样使用 特殊格式。这大大方便了用户和开发者，因为他们可以使用相同的 工具来处理x m ls c h e m a 和其他x m l 信息，而不必专门为s c h e m a 使用特殊工具。另外，s c h e m a 支持数据类型的定义。 2 2 2 查询语言 1 x p a t h x p a t h 是用作x s l t 和x o u e r y 对x m l 各部分进行定位的语言， 用来定位x m l 文档中各个部位，选择文档中的各个构成部分( 元素， 属性，文字内容等) 。x p a t h 除了提供一套定位语法外，还包括一些 函数，提供基本的数字运算，布尔运算和字符串处理功能。 2 x q u e r y x q u e r y 是一个从x m l 格式的数据源中获取数据的查询语言， 起源于x m l 数据查询语言q u i l t 1 8 】，并将x p a t h 2 0 作为其子集。q u i l t 有很多非常优秀的特性，集s q l 、o d m g 、x p a t h l 0 、x q l t l 9 】以及 1 2 支持x m l 数据更新的编码方案与索引技术研究 x m l - q l t 2 0 】等诸多特性于一身，然而随着存储在x m l 文档中的信息 量的增长，为了能够高效存取和查询x m l 信息，q u i l t 显示出了它 的不足。于是全新的x q u e r y 数据查询语言诞生了。 2 2 3 编程接口 1 d o m ( d o c u m e n to b j e c tm o d u l e ) d o m 是一个由w 3 c 定义的独立于语言和平台的抽象a p i ，以 处理x m l 文档。采用d o m 模型的x m l 解析器，把整个x m l 文 档当作一个树，一次加载到内存中，可以根据用户的需要访问、搜 索和修改文档中的元素。 2 s a x ( s i m p l ea p i f o rx m l ) s a x 是一个独立于语言和平台的抽象a p i ，以处理x m l 文档。 和d o m 不同之处在于，s a x 并不是把整个文档加载到内存中，它 是采用一个流模型，逐个字符的读取文档，在遇到元素和属性时生 成事件。采用s a x 模型的x m l 解析器，通过各种通知接口把事件 传递给应用程序。 2 3x m l 查询研究概述 w 3 c 专门为x m l 数据的查询成立了x m l 查询工作组( x m l q u e r yw o r k i n g g r o u p ) ，负责制定有关查询的数据模型、查询语言等 方面的规范。当前x m l 查询研究许多方面得益于传统数据库和半结 构化数据的研究成果。研究主要涉及：数据模型、模式建立与维护、 查询语言、查询处理、x m l 数据存储、视图的建立与维护等。 随着研究的深入，上述领域的问题已经得到了不同程度的解决， 或是解决方法趋于规范化。 1 数据模型 x m l 数据与半结构化数据非常类似，所以x m l 数据可以被看 成是半结构化数据的特例。但由于x m l 是一种文档标记语言，它具 有自身的一些特点，如x m l 元素的有序性，文本与元素的混合等， 使得半结构化数据模型不能很好地描述x m l 的特征。为了描述 x m l 数据，需要提出新的数据模型。 硕十学位论文 早期对x m l 数据模型的研究主要有：文献 2 1 2 2 将x m l 数据 映射到关系模型；文献 2 3 】将x m l 数据映射为面向对象的半结构化 数据模型；研究【2 4 】采用o o d b 数据模型；文献【2 5 】将x m l 数据映 射为关系一对象模型；文献【2 6 】采用r a n k e d a w a r e 数据模型。目前还 没有公认的x m l 数据模型。鉴于x m l 数据自身的特点和传统数据 模型的差别，w 3 c 的x m l 查询工作组提出的数据模型有：x m l i n f o r m a t i o ns e t ，x p a t h1 0d a t am o d e l ，d o mm o d e l 和x m lq u e r y d a t am o d e l ，这四种模型都采用树结构，x m lq u e r yd a t am o d e l 是 其中较为完全的一种。 2 。模式建立与维护 传统的数据库中，数据的定义、查询表达、查询的处理与优化 等都依赖于模式。对于x m l 数据的查询，模式同样是非常重要。早 期，文档类型定义( d t d ) n - f f j 以被看作x m l 数据的模式，描述x m l 文档中元素的结构信息；2 0 0 1 年5 月，w 3 c 提出将x m ls c h e m a 作为制定x m l 文件的一种模式，成为正式的推荐标准。关于x m l 模式的建立与维护方面的研究工作有：根据x m l 的d t d 、模式定 义和传统数据库模式( 关系的或面向对象的等) 之间的关系，文献 2 1 】 将x m l 的模式映射转换为传统数据库模式；对于不带d t d 和模式 的x m l 文档，研究 2 3 】从x m l 文档中抽取其中的元素、结构信息 建立模式；文献【2 1 】 2 3 等分别讨论了可用于x m l 数据映射的关系 模式、半结构化的数据库模式的更新问题。 3 查询语言 为了从x m l 以及半结构化数据中获取所需要的信息，研究人员 开发了许多查询语言，包括l o r e l 7 1 、q u i l t 1 8 1 、x q l 1 9 】、x m l q l 2 0 1 、 x m l - g l 2 刀、a t h 、x q u e r y 等。 这些语言各有优点【2 8 】：l o r e l 在半结构化数据的查询语言的基础 上，针对x m l 的特点作了必要的扩展，功能比较强大，x m l q l ， x q l 及q u i l t 等则专门针对x m l 做了查询语言的研究。x m l q l 和x m l 文档的集成性比较好，而x m l g l 在图形化界面方面做得 1 4 支持x m l 数据更新的编码方案与索引技术研究 比较好。q u i l t 综合先前各种语言的优点：它的路径表达式参考了 x p a t h ，变量绑定借鉴了x m l q l ，f l w r 表达式类似于s q l ，而且 它还支持用户自定义函数。q u i l t 不仅可以查询x m l 数据，也可以 方便地查询关系数据，因此它的表达能力是很强的。w 3 cx m l 查 询工作组在q u i l t 的基础上提出了查询语言x q u e r y ，该语言借鉴了 结构化、半结构化数据查询语言的很多特性，并且较多的考虑了对 不同类型数据源( 包括传统的数据库系统及文档系统等) 的访问能力 以及在小型化、