（计算机软件与理论专业论文）支持数据更新的xml压缩编码研究.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 数据编码方法并指出其中的不足， 提出了一种支持数据更新的压缩编码方案。该编码方案将结点路径信 息进行分解，避免记录重复的路径信息，节省了存储空间；同时支持 数据更新，对更新结点的数量没有限制，完全避免了重新编码。 本文的主要工作如下： ( 1 ) 对现有的数据编码和查询技术进行深入的分析。现有编码存 储空间利用率不高；不能有效的支持结点动态更新；查询技术频繁使 用结构连接操作，查询性能受路径表达式长度的影响。 ( 2 ) 提出一种支持数据更新的压缩编码方案并给出更新方法。该 编码方案通过分解结点路径信息，避免了记录重复信息，同时又提高 了编码的灵活性，能有效的节省存储空间和支持数据动态更新。 ( 3 ) 提出一种高效的查询方法，该查询方法完全避免了结构连接 操作，查询时间不受查询路径长度和中间结果集大小的影响，提高了 查询效率。 ( 4 ) 通过实验，将本文的编码方案和已有的编码做了比较，实验 结果表明：与已有的编码方案相比，本文提出的编码方案在存储空间 利用率、结点更新效率和查询速度方面都有明显的优势。 关键词：x m l 编码，数据存储，数据更新，路径表达式，数据查询 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o ft h ei n t e r a c tt e c h n o l o g y ，t h e e x t e n s i b l em a r k u pl a n g u a g ex m lh a sb e e nt r e m e n d o u sp r o g r e s s ，x m l h a sb e c o m et h ew i d e l yp o p u l a rs t a n d a r do fr e p r e s e n t i n ga n de x c h a n g i n g d a t a t h em a i na d v a n t a g eo fx m li st h a tt h es t r u c t u r ea n ds e m a n t i c so fa c l e a ri n f o r m a t i o n - r i c h ，t h e r e f o r e ，m o r ea n dm o r ei n f o r m a t i o nt ot h ef o r m o fx m ld o c u m e n t ss t o r e da n de x c h a n g e d h o w e v e r ，b e c a u s ex m lh a sa s e l f - d e s c r i p t i v e ，m u l t i b r a n c hs t r u c t u r em a k e sx m ls e e ml o n g ，t ot h e d a t as t o r a g ea n dq u e r yc a u s eg r e a ti n c o n v e n i e n c e t h e r e f o r e ，h o wt o e f f i c i e n t l ys t o r ea n dq u e r yx m l d a t ah a sb e c o m eah o ti s s u eo fd a t a b a s e r e s e a r c hi nt h ef i e l d i no r d e rt oe f f e c t i v e l ys t o r ea n dq u e r yx m ld a t a ，t ob e t t e rp r o m o t e t h ea p p l i c a t i o no fx m l ，t h er e s e a r c h e r sm a d ean u m b e ro fx m ld a t a e n c o d i n gs c h e m e ，w h i c hi m p r o v e sc o d i n ge f f i c i e n c yo fx m l d a t as t o r a g e a n dq u e r y ，b u tt h e ya r ei nt h es t o r a g es p a c eu t i l i z a t i o n ，t h en o d eu p d a t e s e f f i c i e n c ya n dq u e r yi ss t i l ld e f i c i e n ti nt e r m so fs p e e d ，t h i sp a p e rc a r r i e d o u tt h er e l e v a n ta s p e c t so ft h i sr e s e a r c h s o ，i nt h i sp a p e r ，x m ld o c u m e n te n c o d i n gt e c h n o l o g yh a sb e e n t h o r o u g h l ya n a l y z e d ，a n dp r o p o s e dan e wn u m b e r i n gs c h e m ef o rx m l d o c u m e n t s t h ec o d i n gs c h e m eb r e a kd o w nt h en o d ep a t hi n f o r m a t i o nt o a v o i dd u p l i c a t er e c o r d s ，s a v i n gs t o r a g es p a c e ；a l s os u p p o r t sd a t au p d a t e ， b e t w e e na n yt w oc o d e sc a nb ei n s e r t e da n yn u m b e ro fn e wn o d e sw i l ln o t b er e s e r v e ds p a c ei su s e du pa n dc o d i n gc o n f l i c tc o m p l e t e l ya v o i d r e e n c o d i n go ft h en o d e t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) w ec a r e f u l l ya n a l y z ee x i s t i n gd a t ac o d i n ga n dq u e r yt e c h n i q u e s i i i s t o r a g es p a c e u t i l i z a t i o no fe x i s t i n gc o d ei si n e f f i c i e n t ；c a l ln o t e f f e c t i v e l ys u p p o r tt h en o d ed y n a m i c a l l yu p d a t e d ；q u e r yt e c h n i q u e f r e q u e n t l yu s e ds t r u c t u r a lj o i no p e r a t i o n ，t h eq u e r yp e r f o r m a n c eb yt h e i m p a c to f t h el e n g t ho fp a t he x p r e s s i o n ( 2 ) w ep r o p o s eac o d i n gm e t h o do fs u p p o r tf o rd a t au p d a t ea n d u p d a t e m e t h o d t h ec o d i n gs c h e m eb r e a kd o w nt h en o d e p a t h i n f o r m a t i o n ，a v o i d i n gd u p l i c a t i o no fi n f o r m a t i o nr e c o r d e da tt h es a m e t i m ei n c r e a s i n gt h ef l e x i b i l i t yo fc o d i n g ，w h i c hc a ne f f e c t i v e l ys a v e s t o r a g es p a c ea n ds u p p o r tf o rd y n a m i cd a t au p d a t e s ( 3 ) w ep r o p o s e da ne f f i c i e n tq u e r ym e t h o d s ，t h eq u e r ym e t h o d c o m p l e t e l y a v o i d st h es t r u c t u r a l j o i no p e r a t i o n ，t h eq u e r y t i m e i n d e p e n d e n to fp a t hl e n g t ha n ds e tt h es i z eo ft h ei n t e r m e d i a t er e s u l t s ，t o i m p r o v et h ee f f i c i e n c yo ft h eq u e r y ( 4 ) i nt h ee x p e r i m e n t ，t h ec o d i n gs c h e m eo ft h i sa r t i c l ea n dt h ec o d e h a sb e e nd o n eac o m p a r i s o nr e s u l t ss h o wt h a t ：i nc o m p a r i s o nw i t h e x i s t i n gc o d e s ，t h i sp a p e rp r e s e n t sac o d i n gs c h e m ei nt h es t o r a g es p a c e u t i l i z a t i o n ，t h en o d eu p d a t e sb o t ht h ee f f i c i e n c ya n dq u e r ys p e e dac l e a r a d v a n t a g e k e yw o r d s ：x m lc o d i n g ，d a t as t o r a g e ，d a t au p d a t i n g ，p a t he x p r e s s i o n ， d a t aq u e r y 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：哞南加归年夕月留日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密呱 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 友竿市 h 鼍旨 日期：2 , o c 年 日期：2 , o o 年 工，月2 ，莎日 t 月z 多日 支持数据更新的x d l 压缩编码研究 1 1 研究背景及意义 1 绪论 x m l 1 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 的格式表示。x m l 同h t 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 i v i l 数据模式 2 , 3 , 4 1 、x m l 查询 技术 5 , 6 , 7 1 以及x m l 数据存储1 8 , 9 , 1 0 , 1 1 1 。 在x m l 数据处理的众多问题中，数据存储和查询技术是非常关 键的。针对x m l 这种树状数据的查询，学者们己经提出了多种x m l 查询语言，女 1 x p a t h l l 2 】和x q u e 巧f 1 3 】。其q b x q u e r y 是w 3 c 所推荐的x m l 查询语言标准，它能够表达对各种数据源的查询。这些查询语言尽管 各有特点，但它们的一个共同特点是都将路径表达式作为其核心内 容。路径查询最直接的方法就是对x m l 文档树进行遍历，即从根结 点出发，沿着树中的边搜索，寻找匹配路径表达式的结点。文献1 1 4 , 1 5 1 硕士学位论文 对这种方式进行了探讨，它简单、直接，但执行效率不能得到保证， 尤其是在存在不确定路径和数据量大的情况下，需要对每条路径进行 遍历，该方法的效率几乎不能令人接受。如何高效地对x m l 数据进 行查询成为本课题研究的一个重点。 由于关系数据库系统有使用广泛、数据处理能力强、查询性能好 的优势，研究者提出用关系数据库来存储x m l 数据，对数据的查询也 在关系数据库上进行。目前，面向缸数据的存储 1 6 , 1 7 , 1 8 , 1 9 】和查询 【2 0 ，2 1 ，2 2 ，2 3 1 已经有大量的技术提出，这些技术提高了儿数据的存储和 查询效率，但这些技术存在一些不足：不能很好的解决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 数据处理的众多问题中， 2 支持数据更新的x m l 压缩编码研究 实现对x m l 数据的有效存储和查询是非常关键的一个。 在x m l 数据存储方面，研究者提出许多编码方案，这些方法都 是使用特定的编码方式对x m l 文档树中的元素、属性和其他语义实 体进行编码，使用编码唯一标识实体，从而判断文档树中结点间的基 本结构关系。目前已经提出的编码方法根据其特点主要可以分为区间 编码 2 4 , 2 5 , 2 6 , 2 7 , 2 8 1 和前缀编码 2 9 , 3 0 , 3 1 】。 区间编码是目前应用最普遍的一类，x m l 文档树t 中的每一个 结点被赋予一个区间编码 ，并且满足：一个结点的区间编 码包含它的后裔结点的区间编码。也就是说，文档树t 中的结点u 是结点v 的祖先，当且仅当s t a r t ( u ) s t a r t ( v ) e n d ( v ) 8 0 r e t u r n $ i t i t l e ，$ i p r i c e ) 其语义为：在名为b i b x m l 的x m l 文档中从根结点开始，选择 所有b i b 结点的v e n d o r 子结点，然后选择所有v e n d o r 的b o o k 子结点， 并且要求最终选择的b o o k 结点须满足条件：它的价格p r i c e 需大于 8 0 ，最终输出每一个满足条件的b o o k 结点的t i t l e 和p r i c e 。该查询中， $ i 为绑定的变量，用以帮助构造查询结果。这一查询返回的结果为： j 斟k 9 9 硕士学位论文 2 3x m l 文档解析器 x m l 是一种数据格式，每一种数据格式都需要一个解析器将其 中的信息解析出来，x m l 当然也不会例外，本节我们介绍几种常用 的文档解析器。 2 3 1d o m 解析器 d o m 4 6 1 解析器是用与平台和语言无关的方式表示x m l 文档。 d o m 是以层次结构组织的结点或信息片断的集合，这个层次结构允 许开发人员在树中寻找特定信息，分析该结构通常需要加载整个文档 和构造层次结构，然后才能做任何工作。由于它是基于信息层次的， 因而d o m 解析器被认为是基于树或基于对象的。d o m 以及广义的 基于树的处理具有几个优点：首先，由于树在内存中是持久的，因此 可以修改它以便应用程序能对数据和结构作出更改。d o m 解析器把 x m l 文档转化为一个包含其内容的树，并可以对树进行遍历。用 d o m 解析模型的优点是编程容易，然而由于使用d o m 解析器的时 候需要处理整个x m l 文档，所以对计算机的性能和内存的要求比较 高，尤其是遇到很大的x m l 文件时。由于它的遍历能力，d o m 解 析器常用于x m l 文档需要频繁改变的服务中。 2 3 2s a x 解析器 s a x 4 7 】解析器分析数据的过程非常类似于流媒体，当处理x m l 数据时分析能够立即开始，而不是等待所有的数据被处理，而且，由 于应用程序只是在读取数据时检查数据，因此不需要将数据存储在内 存中，这对于大型文档来说是个巨大的优点。事实上，应用程序甚至 不必解析整个文档，它可以在某个条件得到满足时停止解析。一般来 说，s a x 解析器处理数据比d o m 解析器速度快。d o m 解析器采用 建立树形结构的方式访问x m l 文档，而s a x 解析器采用的事件模 型。s a x 解析器在解析x m l 文档的时候可以触发一系列事件，当 1 4 支持数据更新的l 压缩编码研究 发现给定的t a g 标签时，它可以激活一个回调方法，告诉该方法制定 的标签已经找到。s a x 解析器对内存的要求通常会比较低，因为它 让开发人员自己来决定所要处理的t a g 。特别是当开发人员只需要处 理文档中所包含的部分数据时，s a x 解析器这种扩展能力得到了更 好的体现，但用s a x 解析器的时候编码工作会比较复杂，而且很难 同时访问同一个文档中的多处不同数据。 2 3 3j d o m 解析器 j d o m 4 8 1 解析器的目的是成为j a v a 语言的特定文档模型，它简化 与x m l 的交互并且比使用d o m 实现更快。j d o m 与d o m 主要有 两方面不同：首先，j d o m 仅使用具体类而不使用接口，这在某些方 面简化了a p i ，但是也限制了灵活性；第二，a p i 大量使用了c o l l e c t i o n s 类，简化了那些已经熟悉这些类的j a v a 开发者的使用。j d o m 自身 不包含解析器，它通常使用s a x 2 解析器来解析和验证输入x m l 文 档。它包含一些转换器以将j d o m 表示输出成s a x 2 事件流、d o m 模型或x m l 文本文档。 2 3 4d o m 4 j 解析器 d o m 4 j t 4 9 1 解析器最初是j d o m 的一种分支，但后来代表了完全 独立的开发结果。它合并了许多超出基本x m l 文档表示的功能，包 括集成的x p a t h 支持、x m ls c h e m a 支持以及用于大文档或流化文档 的基于事件的处理，它还提供了构建文档表示的选项，它通过d o m 4 j a p i 和标准d o m 接口具有并行访问功能。d o m 4 j 解析器使用接口和 抽象基本类方法。d o m 4 j 大量使用了a p i 中的c o l l e c t i o n s 类，d o m 4 j 是一个非常优秀的j a v ax m la p i ，具有性能优异、功能强大和容易 使用的特点，同时它也是一个开放源代码的软件。 硕士学位论文 x m l 数据是近年来研究的热点，很多研究者都在这方面做了大 量的工作，取得了不错的进展，本章对x m l 数据的相关技术进行了 介绍。首先介绍x m l 文档的定义、语法规则，然后介绍了两种基本 的查询语言x p a t h 和x q u e r y ，最后介绍了几种常用的x m l 文档解析 器。 支持数据更新的x m l 压缩编码研究 3 支持数据更新的x m l 压缩编码( c x s u ) 3 1x 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 ) 动态性。编码能够支持x m l 数据的动态更新，而不用重新 改变任何已经存在的结点编号。 ( 3 ) 压缩性。编码存储空间的需求应该尽量小。 ( 4 ) 查询高效性。编码应能有效的支持数据查询。 3 2x m l 编码研究现状 本节对x m l 编码的研究现状进行介绍和分析，其中重点介绍区 间编码和前缀编码并分析他们的优点和不足，为后续研究打下基础。 区间编码的基本原理是利用x m l 文档有序的特点，根据结点在 文档树中的遍历顺序给每个结点赋予一个编码。区间编码的格式一般 用 表示，s t a r t 表示结点的前序遍历序号，e n d 表示结点的 后序遍历序号，区间编码满足如下条件：一个结点的区间编码包含它 的后裔结点的区间编码，也就是说，在x m l 文档树t 中的结点u 是 结点v 的祖先，当且仅当s t a r t ( u ) s t a r t ( v ) e n d ( v ) e n d ( u ) 。 d i e t z 2 4 1 编码是e f d i e t z 提出的，它的编码规则是：x m l 文档可 以表示为一个树型结构，树t 中的每一个结点被赋予一个先序遍历序 硕士学位论文 号和后续遍历序号，用二元组 来表示。d i e t z 编 码有以下定义：一棵x m l 文档树t ，在先序遍厉中，假如结点x 先于 结点y 被访问p e r o r d e r ( x ) p o s t o r d e r ( y ) ， 即 p e r o r d e r ( x ) p e r o r d e r ( y ) p o s t o r d e r ( y ) p o s t o r d e r ( x ) ，则结点x 是结点y 的祖先，图3 1 显示x m l 文档树的d i e t z 编码。 ( 3 ，1 ) ( 7 ，5 ) 图3 1 d i e t z 编码 d i e t z 编码通过检测x m l 文档树中结点的前序和后序顺序能有 效的判断结点间的祖先后代关系，例如：结点a 的区间编码为 ，结点b 的区间编码为 ，有p e r o r d e r ( a ) p e r o r d e r ( b ) p o s t o r d e r ( b ) p o s t o r d e r ( a ) ，可以判断结点a 是结点b 的祖先结点。d i e t z 编码可以 通过编码的区间值判断结点间的关系，但这种编码模式缺少灵活性， 当插入新结点时，原结点的前序和后序顺序会发生变化，需要对原结 点重新编码。例如插入一个新结点h 作为结点d 的左兄弟，如图3 - 2 所示，其它结点的前序和后序发生了改变，需要对其它结点重新编码， 造成数据更新效率低。 固 ( 3 ，1 ) 图3 2 数据更新 1 8 ( 8 ，6 ) 支持数据更新的x m l 压缩编码研究 虽然d i e t z 编码存在许多不足，但d i e t z 提出的使用前序和后序来 判断结点间关系的方法得到了广泛的应用，目前许多研究者已经设计 出许多改进的编码方案都是以d i e t z 编码为基础。 文献 2 5 提出x i s s 编码，x i s s 编码以d i e t z 编码为基础，提出 一种基于扩展前序编码模式。该编码用扩展前序和后代范围来描述结 点，通过比较结点的扩展前序和后代范围来确定结点间的祖先后代 关系( 包括父子关系) 。结点用二元组 表示，o r d e r 表示 结点的扩展前序，s i z e 表示结点后代的范围。x i s s 编码有如下性质： ( 1 ) 如果结点x 是结点y 的祖先结点，则o r d e r ( x ) o r d e r ( y ) ， o r d e r ( y ) + s i z e ( y ) o r d e “x ) + s i z e ( x ) ，即区间 o r d e r ( x ) ，o r d e r ( x ) + s i z e ( x ) 】 包含区间 o r d e r ( y ) ，o r d e r ( y ) + s i z e ( y ) 。 ( 2 ) 如果结点x 是结点y 的兄弟结点，且o r d e r ( x ) o r d e r ( y ) ，则 o r d e r ( x ) + s i z e ( x ) o r d e r ( y ) 。 x i s s 编码模式如图3 3 所示，从图可以看出，一个结点x 的s i z e ( x ) 值大于或等于x 的所有子结点( 仅指当前子结点) 的s i z e 值之和，因此 应该使结点x 的s i z e 值大于x 直接子结点的s i z e 值之和，这样就给将 来插入的结点预留空间。例如结点a 、b 、c ，有o r d e r ( a ) o r d e r ( b ) ， o r d e r ( b ) + s i z e ( b ) o r d e r ( a ) + s i z e ( a ) ，根据结点的性质可知结点a 是结点 b 的父亲结点；又如结点b 是结点c 的兄弟结点，且o r d e r ( b ) o r d e r ( c ) ， 有o r d e r ( b ) + s i z e ( b ) ， ，= ) 来确定结点间的关系，例如：结点2 a b b 的父 结点编码是a b ，l a b 结点编码是a b ，所以2 a b b 的父结点是l a b ；再 如，2 a b b 的右兄弟是2 a b c ，因为它们有共同的父结点a b ，且b 图3 1 0 结点位置信息 c x s u 编码具有以下4 个性质： 硕士学位论文 性质l ：结点u 和v ，如果u p a t h p o s t i o n = v p a t