（计算机软件与理论专业论文）基于分带索引存储结构的高效xml搜索算法的研究与应用.pdf

原创性声明 f i i nn l l l ! i i i i i fy 1 7 1 8 。嘈。蚶 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与共同 工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：墨孟丕日期：赴年上月翌日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 吼赴月粤日 摘要 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 文档的检索方法，分析 每种方法的优势和劣势，比较了各个方法的性能，对其技术特点进行 了讨论；其次，介绍了i t o s 存储结构及其结构信息存储与值信息存 储，在此基础上，提出了基于i t o s 存储结构的分支搜索算法和含值 搜索算法。本文提出的分支搜索算法一般无需存储搜索分支，只是得 到结果的节点集合，这样减小搜索结果所占空间；提出的含值搜索算 法滤去很多无用的中间结果，优化了搜索执行顺序。论文对比x p a t h 与x q u e r y 以及传统的分支搜索与含值搜索方法。通过理论分析，说 明了本文算法具有较好的伸缩性，基于实验结果，证明了算法改善了 x m l 文档的搜索执行效率。 论文最后讨论了在m y e c l i p s ei d e 开发环境下建立的一个试验 平台。该平台建立一个树形x m l 模型，用以生成x m l ，对其数据 进行了仿真，给出了压缩与查询结果。 关键词x m l ；分支搜索算法；含值搜索算法；x p a t h ；x q u e r y a b s t r a c t 舭h a sb e e nas t a n d a r dt od e n o t ea n dt o o lt oe x c h a n g ed a t ai n i n t e r n e t b u ti t sd a t ah a sab i gr e d u n d a n c y f i r s t r e d u n d a n c yw i l lw a s t e h u g es t o r i n gs p a c e ，s e c o n di tc a l li n c r e a s ei 0t i m ef o rq u e r y i n gm a n a g e a tp r e s e n t ，c o m p r e s si sag o o dm e t h o dt om i n i s hc a p a c i t yo fx 几b u t a f t e rc o m p r e s s i n g ，x m ln e e dt od e c o m p r e s s ，t h e ni ti sc a nb ev a l i d a t e d a n dq u e r i e d s o l v i n gt h ep r o b l e mt h a th o wt oc o m p r e s sx m ld o c u m e n t t h e na f t e rc o m p r e s s i n gt os e a c hi sv e r yi m p o r t a n t f i r s t ，an u m b e ro fe x i s t i n gx m lc o m p r e s s i o nm e t h o da n dt h e t e c h n i c a lc h a r a c t e r i s t i c so ft h es t r u c t u r eo fad e t a i l e dd e s c r i p t i o no fa n a n a l y s i so fv a r i o u st e c h n i c a la d v a n t a g e sa n dd i s a d v a n t a g e s ，c o m p a r e dt h e p e r f o r m a n c e o fv a r i o u sc o m p r e s s i o nm e t h o d s s e c o n d i n t r o d u c et h ei t o s s t o r es t r u c t u r ea n dt h es t r u c t u r ei n f o r m a t i o na n dv a l u ei n f o r m a t i o ni nt h e 1 1 o s t h i r d ，t h ep a p e rp u tf o r w a r db a t c hq u e r y i n ga l g o r i t h ma n dv a l u e q u e r y i n ga l g o r i t h mb a s eo ni t o s c o m p a r i n gx p a t h ，x q u e r y , t r a d i t i o n a l b a t c hq u e r y i n ga n dt r a d i t i o n a lv a l u eq u e r y i n g t h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t a lr e s u l t si l l u s t r a t et h ea l g o r i t h mh a sg o o ds c a l a b i l i t ya n dh i g h e f f i c i e n c yo fq u e r ye x e c u t i o n a tl a s t ，t h em y e c l i p s ei d ew i t ht h ee s t a b l i s h m e n to f at e s tp l a t f o r m f i r s to fa l l ，t h ep l a t f o r mt ob u i l dat r e e 1 i k ex m l m o d e lt og e n e r a t ex m l f o l l o w e db ys i m u l a t i o no ft h e i id a t a ，g i v e nt h ee s t a b l i s h m e n to ft h e p r i n c i p l eo f t h em o d e la n dd a t a ，a n da n a l y s i so ft h ed a t a k e yw o r d s x m l ；i t o s - b q ；i t o s - v q ；x p a t h ；x q u e r y i l 目录 第一章绪论1 1 1 课题背景与意义1 1 2 国内外研究现状1 1 3 论文的组织3 第二章x m l 技术及i t o s 存储结构5 2 1x m l 相关技术简介5 2 1 1 ) ( m l 概述5 2 1 2 ) ( m l 文档的d t d 和x s l t 6 2 1 3x p a t h 7 2 1 4x q u e r y 8 2 2d i l 数据压缩后检索的几种方法9 2 3i t o s 存储结构1 2 2 3 1i t o s 概述1 2 2 3 2 存储结构信息和值信息1 3 2 3 3 有效值和层次结构的对应1 7 、 2 4 本章小结1 7 第三章基于i t o s 的分支搜索算法1 8 3 1 概念与定义1 8 3 2 基于i t o s 的分支搜索算法1 9 3 2 1 节点筛选1 9 3 2 2 遍历步骤2 2 2 3 3 结果树2 4 3 3 算法比较2 5 3 3 1 传统分支搜索算法与i t o s - b q 效率分析比较2 7 3 3 2i t o s - b q 与x p a t h 、x q u e r y 算法效率分析比较2 7 3 4 算法实现2 8 3 4 1 实现方案2 9 3 4 2 实现过程与程序代码3 0 3 5 本章小结3 2 第四章基于i t o s 的含值搜索算法3 4 4 1 传统含值搜索算法3 4 4 1 1 传统l r v a l v f s l 与传统l r v a ls f v l 3 4 4 2 基于i t o s 的含值搜索算法：3 4 4 2 1 概述3 4 4 2 2 含值搜索各个阶段的选取3 5 4 2 3 含值搜索算法描述3 5 4 2 4v q0 s m a 的效率分析3 7 4 3 几种含值算法的分析比较3 8 4 3 1 三种含值搜索算法效率对比4 0 4 3 2 搜索算法综合比较4 0 4 4 含值算法的实现4 2 4 4 2 实现方案4 2 4 4 3 实现过程与程序代码4 3 4 5 本章小结4 7 第五章原型系统的实现4 8 5 1i t o s 存储结构的实现4 8 5 1 1 建立x m l 模型4 8 5 1 2x m l 数据压缩、存储及搜索4 9 5 2 变量定义及设计流程说明5 0 5 2 1 变量定义5 0 5 2 2 设计流程5 1 5 3 功能模块的实现5 2 5 3 1 鼠标事件响应函数实现5 2 5 3 2 生成树状控件函数实现5 3 5 3 3 控件属性表单设计5 4 5 3 4x m l 树状结构生成5 5 5 3 5 存储搜索5 7 5 4 本章小结5 8 第六章结束语5 9 6 1 工作总结5 9 6 2 展望5 9 参考文献6 0 致谢6 5 硕士学位论文第一章绪论 1 1 课题背景与意义 第一章绪论 i n t e r n e t 的飞速发展使w e b 数据成为全球信息传递与共享的最具潜力的资 源。与此同时，信息量的与日俱增和信息形式的多种多样，使得如何从海量w e b 数据中获取有用信息，己经成为人们最关注的问题。因此有效地组织和管理分布 于世界各地的海量数据，提高信息获取速度已逐渐成为数据管理领域的热门课 题。传统的数据模式已不适合表示这些数据【l 】。x m l 的出现引起了人们极大的 关注，x m l 是由嵌套的标记元素构成的自描述标记语言。目前，x m l 文档己经 成为i n t e m e t 上信息交换和处理的重要标准【2 】 x 1 l 产生的最初原动力是为了解决h t m l 作为w e b 数据交换标准而带来 的混乱局面。与h t m l 相比，x m l 具有很大的灵活性，不但可以表示无结构的 文本信息，还可以表示高度结构化的数据，它极大地推动了电子商务、电子数据 交换等多方面的应用p j 。 中国移动湖南分公司经营分析系统有一个重要的业务，该业务收集各地市的 数据，对其进行整理分析，找出需要的有用值，通过报表的形式展现出来，反馈 到市场部。由于各地区存储数据的格式不一致，为便于交换，需要统一转换成同 一种格式。因此，使用x m l 技术，把各地市异构的数据统一成格式，是一种较 好的解决办法。 x m l 数据的一个明显缺陷是数据冗余较大，数据冗余既造成了存储空间的 浪费，又降低了搜索处理的效率。目前，压缩是减小x m l 文档大小的一种行之 有效的方法，但是压缩后的x m l 文档需要解压后才能对其进行验证、搜索等操 作。所以如何在压缩后的x m l 文档上进行搜索操作，已成为基于x m l 的数据 交换中亟待解决问题。 1 2 国内外研究现状 x m l 数据文档，既含有结构特征的路径，又有无结构化的文本数据，所以 对x m l 数据的搜索优化等操作要分为两方面来考虑。下面分别就这两方面谈谈 当前的发展现状l g l 。 对于一般性的文本数据来说，压缩文件是用来减少资料占用的空间，使它变 得易于管理，但是这可能会改变资料的结构，从而导致不能正确地检索信息。对 于压缩文件的搜索一般有三种方法：( 1 ) 先对压缩文件解压缩【l o 】，然后再用一 般的查询算法检索。这个解压缩的过程可能是非常耗时的；( 2 ) 全文压缩模式匹 硕士学位论文第一章绪论 配方法，就是直接对压缩的文件搜索。这个方法的关键点就是对要搜索的模式用 同样的压缩算法压缩，然后在文档中搜索与之相同的字符串。如果字符串在压缩 算法中表示不唯一的话，则该方法是不适用的；( 3 ) 压缩域模式匹配【l u ，即对压 缩文件部分地解压缩。这种方法的核心思想就是避免不解压缩情况的障碍，同时 还具有不解压缩时的优点。 对于x m l 文档来说，结构数据和文本数据的两方面特征促使它的研究方向 呈现多样化。x m l 自身的特点决定了其数据冗余较大，由此造成了存储空间的 浪费、搜索效率的降低。x m l 压缩技术就是针对x m l 数据的特殊数据模型， 在x m l 结构特征和语义信息的帮助下对其进行压缩的过程。 其中，x m i l l 1 2 】是一种不支持搜索的x m l 压缩系统f 1 3 】。x m i l l 中压缩方 法的核心思想是将结构和内容分离，然后利用a p p r o x i m a t i o n m a t c h i n g 算法【1 4 】对 相似语义的数据项进行分组，形成数据容器( c o n t a i n e r ) 。对于结构，用字典编 码( d i c t i o n a r ye n c o d i n g ) 方法对属性( a t t r i b u t e ) 和元素( e l e m e n t ) 进行替换。 对每个容器，利用通常的l z 7 7 算法分别进行压缩，最后将已经压缩的片断合并 成一个完整的压缩文件，能够取得两倍于g z i p 的压缩效率。 x m l p p m 提出了一种基于p r e d i c t i o nb yp a r t i a lm a t c h ( p p m ) 1 5 j 的压缩方案。 与x m i l l 不同，x m l p p m 利用s a x 解析器将x m l 整理成一个数据流，作为 x m l p p m 的输入。根据语法，对元素或属性名、结构、属性值和数据项等分别 利用相应的p p m 算法进行编码压缩。由于p p m 算法是一种速度较慢的压缩方法， 所以x m l p p m 算法要比x m i l l 方法慢。但是在压缩率上，x m l p p m 要好于 x m i l l 。 尽管x m l 压缩技术已经取得了一些进展，但是对支持搜索的x m l 压缩技 术的研究却还不是很成熟。现有的x m l 压缩和搜索系统还不能够处理诸如 x q u e r y 等复杂的搜索语句【1 6 1 。在搜索速度和压缩率上还没有取得比较满意的成 果。所以有必要进一步研究支持搜索的x m l 压缩技术。 x m l 压缩搜索最初是作为信息论研究中的一个重要课题，在信息论中被称 为信源编码【1 7 】。但近年来，x m l 压缩搜索己不仅局限于编码方法的研究和讨论， 这门技术已经成为独立的体系。它主要研究数据的表示、传输和转换方法，目的 是减少数据所占的存储空间。 x m l 压缩搜索的3 个主要步骤： ( 1 ) 建立一个数学模型【1 8 l ，以便能更紧凑或更有效地“重新表达 【1 9 】原始 数据19 】； ( 2 ) 设法更简洁地表达利用该模型对原始数据建模所得到的模型参数，由 于这些参数可能会具有过高的表示精度，因此可以将其量化为有限的精度为区别 2 硕士学位论文第章绪论 对原始信号数字化时的量化，称之为“二次量化 【2 u 】； ( 3 ) 对模型参数的量化表示或消息流进行码字分配，以得到尽可能紧凑的 压缩码流。此时的编码要求能“忠实地 再现模型参数的量化符号，故称之为“熵 编码 【2 1 1 。 从实践中得知，一般的信息在用x m l 描述的时候都会存在冗余，这是不可 避免的，所以人们采取各种办法，减少这种不必要的冗余。早在7 0 年代，微软 公司和i b m 公司都相继有人提出了降低x m l 搜索的有效编码【2 2 1 。 有一种压缩程序叫做“静态统计模型”，这种方法可以预先扫描文件中的所 有字符，统计出每个字符出现的概率。但是，在不同的文件中，字符有不同的分 布概率，要么先花上大量的时间统计要压缩的所有文件中的字符概率，要么为每 一个单独的文件保存一份概率表，以便解压缩时使用1 2 5 1 。然而，这样不但扫描 文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。所以， 在实际应用中，“静态统计模型 应用的很少。 真正的压缩程序中使用的大多是“自适应模型 1 2 6 。自适应模型可以说是 一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每 个字符的出现概率均等，随着字符小断被输入统计并纪录已经出现过的字符的概 率并将这些概率应用于对后续字符的编码。也就是说，自适应模型在压缩开始时 压缩效果并不理想，但随着压缩的进行，会越来越接近字符概率的准确值，并达 到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可 以适应不同的文件中的字符分布而不需要保存概率表【2 7 ，2 引。 1 3 论文的组织 论文共分为六章。 第一章，介绍了本文选题的背景与意义，当前国内外相关技术的研究现状。 根据本文研究的方向，分别简介了x m l 压缩搜索的现状，以及x m l 的相关技 术等方面的背景知识。 第二章，首先介绍了x m l 技术，介绍了现有支持搜索的x m l 数据压缩方 法，分析了现有支持搜索的x m l 数据压缩检索方法的不足之处。同时提出了一 种新的x m l 压缩存储结构i t o s ，描述了其中的结构信息、值信息以及两者对 应关系的存储方法，并阐述了该存储结构的优点。为后两章的算法改进作好了铺 垫工作。 第三章，提出一种基于i t o s 存储结构的分支搜索优化算法。搜索处理的结 果是i t o s 中若干个满足搜索的分支，如果依次存储这些分支，通常需要占用大 量存储空间。并且，在很多情况下只需要得到满足搜索条件的某些节点，甚至只 硕士学位论文第一章绪论 需要判断树中是否存在满足搜索的分支。针对这些情况，以及出于减小搜索结果 所占空间的考虑，对本章提出的这种优化算法( 分支搜索优化算法) 与x p a t h 和x q u e r y 以及传统的分支搜索算法分别进行了对比，得出论文所提算法具有高 效准确的优点。 第四章，首先给出了传统的两种含值搜索方法，并分析了其存在的问题，进 而提出一种基于i t o s 存储结构的含值搜索的优化方法，该方法充分利用了前文 中结构信息匹配算法的优势，在高效的得到结构信息匹配中间结果的基础上，添 加了值信息的匹配，相对于其他存储结构上含值搜索的处理，其搜索效率的提高 很大一部分取决于结构信息匹配效率的提高。接着，对本章提出的这种优化算法 ( 含值搜索优化算法) 与x p a t h 和x q u e r y 以及传统含值搜索算法分别进行了对 比，得出本文所提算法具有高效准确的优点。 第五章，在前两章的基础上，给出本系统的详细实现结果及用m y e c l i p s e 实 现了整个模型架构及操作过程。 第六章，总结与展望。对已做工作的总结和对未来工作的展望。 4 硕士学位论文第二章x m l 技术及i t o s 存储结构 第二章x m l 技术及i t o s 存储结构 2 1x m l 相关技术简介 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 的缩写【2 9 】。扩展标记语言x m l 是一 种简单的数据存储语言，使用一系列简单的标记描述数据，而这些标记可以用方 便的方式建立，虽然x m l 占用的空间比二进制数据要占用更多的空间，但x m l 极其简单易于掌握和使用【3 0 1 。 2 1 1x m l 概述 x a 4 l 与a c c e s s ，o r a c l e 和s q ls e r v e r 等数据库不同，数据库提供了强有力 的数据存储和分析能力，例如：数据索引、排序、查找、相关一致性等，x m l 仅仅是表示数据【3 2 1 。事实上，x m l 与其它数据表现形式最大的不同是：它极其 简单。这正是它的优点，这点使x m l 与众不同。 x m l 的简单使其易于在任何引用程序中读取数据，这使x m l 很快成为数 据交换的唯一公共语言，虽然不同的应用软件也支持其它的数据交换格式，但不 久之后它都将支持x m l ，那就意味着程序可以更容易的与w i n d o w s ，m a co s ， l i n u x 以及其它平台下产生的信息结合，然后可以很容易的将x m l 数据加载到 程序中进行分析，并以x m l 格式输出结果。 x m l 的前身是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 ) 1 3 2 】。同h t m l 一样，x m l 是s g m l 的一个子集，它是描述网络上的数据内容和结构的标准。 尽管如此，x m l 与h t m l 不同，h t m l 仅仅提供了在页面上显示信息的通用方 法( 没有上下文和动态功能) ，x m l 则对数据赋予上下文相关功能，它继承了 s g m l 的大部分功能，却使用了不太复杂的技术【3 3 1 。 x m l 继承了s g m l 的许多特性。 首先是可扩展性p 引。x m l 允许使用者创建和使用他自己的标记而不是 h t m l 的有限量词汇表【35 1 。这一点至关重要，企业可以用x m l 为电子商务和供 应链集成等应用，定义自己的标记语言，甚至与特定行业一起来定义该领域的特 殊标记语言，作为该领域信息共享与数据交换的基础。 其次是灵活性1 3 6 。7 j 。h t m l 很难再进步发展，因为它是格式、超文本和图 形用户界面语义的混合，要同时发展这些混合在一起的功能是很困难的。而x m l 提供了一种结构化的数据表示方式，使得用户界面分离于结构化数据。所以， w e b 用户所追求的许多先进功能在x m l 环境下更容易实现【3 8 1 。 第三是自描述性1 3 9 “们。x m l 文档通常包含一个文档类型声明，因而x m l 硕士学位论文第二章x m l 技术及i t o s 存储结构 文档是自描述的。不仅人能读懂x m l 文档，计算机也能处理。x m l 表示数据 的方式真正做到了独立于应用系统，并且数据能够重用。x m l 文档被看作是文 档的数据库化和数据的文档化。 除了上述先进特性外，x m l 还具有简明性。它只有s g m l 约2 0 的复杂性， 但却具有s g m l 8 0 的功能。x m l 比完整的s g m l 简单得多，易学、易用并且 易实现。另外，x m l 也吸收了多年来在w e b 上使用h t m l 的经验。x m l 支持 世界上几乎所有的主要语言，并且不同语言的文本可以在同一文档中混合使用， 应用x m l 的软件能处理这些语言的任何组合。所有的这一切将使x m l 成为数 据表示的一个开放标准，这种数据表示独立与机器平台、供应商以及编程语言。 它为网络计算注入了新的活力，并为信息技术带来新的机遇。目前，许多大公司 和开发人员已经开始使用x m l ，包括b 2 b 在内的许多优秀应用已经证实x m l 将会改变今后创建应用程序的方式。 2 1 2x m l 文档的d t d 和x s l t d t d 的全称是( d o c u m e n tt y p ed e f i n i t i o n ) ，文档类型定义1 4 3 j 。它是一套关于 标记符的语法规则，是x m l 文件的验证机制，属于x m l 文档的一个组成部分。 d t d 是一种保证x m l 文档格式正确性的一种规范，可以通过比较x m l 文 档来看文档是否符合规范，元素和标签使用是否正确。一个d t d 文档包含：元 素的定义规则，元素之间的定义规则，元素可使用的属性，可使用的实体或符号 规则。 x m l 文件为应用程序提供了一个数据交换的格式。d t d 正是让x m l 文件 能够成为数据交换的标准，因为不同的公司只需定义好标准的d t d ，各公司都 能够依照d t d 建立x m l 文件，并且进行验证，如此就可以轻易的建立标准和 交换数据烨j ，这样也满足了网络共享和数据交换。d t d 文件是一个a s c i i 的文 本文件，后缀名为d t d 。 x s l t ( e x t e n s i b l es t y l e s h e e tt r a n s f o r m a t i o nl a n g u a g e ) 最p 可扩展的样式转换语 言，它的作用一般是用来转换x m l 格式的，比如p d f 等。 x m l 不容易读取数据，最好的办法是将文本数据显示，去掉结构。例如将 一个x m l 文档转换成各种格式：h t m l 、p d f 或者是一段音频。x s l t 主要的功 能就是把一种数据格式换成另一种数据格式，x s l t 的功能非常的强大，而且应 用也非常广泛，在很多业务中都会用到它，本文开发的经分系统大多数有效数据 的显示是用x s l t 将数据转化成h m t l 格式来展现的。 下面举一个最典型的x s l t 转化的例子：把其它的数据格式转化成h t m l 格 式。 6 硕士学位论文第二章x m l 技术及i t o s 存储结构 作为w e b 开发的程序员来说都会熟悉句戤( a s y n c h r o n yj a v a s c f i p ta n d x m l ) 通过名称可知a j a x 技术其实是以前的几项技术的合成应用，比如 j a v a s c r i p t 技术，d o m 技术以及d h t m l 技术。, a j a x 技术中的新技术只有 x m l h t t p r e q u e s t 。a j a x 技术的主要功能第一个就是客户端和服务器的异步交互， 实现局部刷新的功能。这些显示的功能如果使用x s l t 现实会更容易。 可以用层叠样式表来辅助x s l t 来完成一些数据的格式化现实，可以把数据 转化成h t m l 格式，p d f 格式，并且还可以把数据转化成e x c e l 格式，在下文 提到的经分系统中一些数据存放在本地的e x c e l 文件里，其转换技术就是 x s l t ，应用a j a x 技术可以从服务器端获取不同格式的数据然后响应给客户端， 这些数据的格式可能不一致，但是可以应用x s l t 将其统一转换成h t m l 格式 的文档。 2 1 3x p a t h x p a t h 是由w 3 c 创建的。在w 3 c 的规范里，对x p a t h 2 0 的描述是这样的： “x p a t h 致力于为x s l t 和x p o i n t e r 的公共功能提供一种共同的语法和语义的结 果1 4 9 1 。x p a t h 的主要目的是对一个x m l 文档进行寻址。为了支持这个主要目的， 它也为操纵字符串、u r l 和x m l 属性值里的数值和布尔值提供了一些基本的功 能。x p a t h 使用了一种紧凑的、非x m l 语法以方便x p a m 的使用。x p a t h 在x m l 文档的一个抽象的逻辑结构上进行操作，而不是在它的表面上的语法上。x p a t h 因为使用类似于u r l 的路径表示法，在一个x m l 文档的层次结构中进行导航 而得名。直以来，人们就要求将数据的内容和数据的表示分离，一般来说是 使用标记语言格式化来达到这个目的的。在这方面，w 3 c 最开始设计了 d s s s l ( d o c u m e n ts t y l es e m a n t i c sa n ds p e c i f i c a t i o nl a n g u a g e ) 规范，d s s s l 原本 是设计为与s g m l 协同工作的，然而，s g m l 并没有流行起来。 除了用于寻址之外，x p a t h 设计有一个可以用于匹配( 测试一个结点是否与 一个模式匹配) 的自然的子梨5 0 1 。x p a t h 将x m l 文档当成一个结点树模型。结 点类型有元素、属性、文本等不同类型。x p a t h 定义一个方式来计算每种结点类 型的值，某些类型的结点也有其名称，x p a t h 完全支持x m l 命名空间。这样， 一个结点的名字模型由本地部分和命名空间u r l 组成，称为扩展名。 x p a t h 的基础语法由表达式构成。在计算表达式的值之后产生一个对象，这 种对象有以下四种基本类型”j ：结点集合、布尔型、数字型和字符串型。 表达式的计算依据上下文出现，x s l t 和x p o i n t e r l 5 2 1 q b 分别规定了x p a t h 表 达式将在怎样的情况下出现。这些上下文关系包括：结点、一对正整数、一套变 量绑定集合、函数库以及规定表达式范围的名域声明。其中，变量绑定是从标量 7 硕士学位论文第二章x m l 技术及i t o s 存储结构 名称到变量值的映射。变量的值是一个对象，可以使表达式得到的各种类型，也 可以是其他没有规定的类型。在函数库中，每个函数有零个或多个参数，并返回 一个结果。x p a t h 定义了所有支持工具都必须实现的核心函数库。其中的函数的 参数和结果都是上面涉及的四种基本类型。 x p a t h 基本上和在文件系统中寻找文件类似，如果路径是以矿开头的，就表 明路径表示的是一个绝对路径，这和在u n i x 系统中关于文件路径的定义是一致 的。当然，x p a t h 本身有一套完整的语法说明，类似巴克斯诺尔范式。x p a t h 是 用路径表达式来选取x m l 文档中的结点或者结点集。结点是通过沿着某个路径 或者定位步来选取的。 2 1 4x o u e r y x q u e r y 也是由w 3 c 创建的。在w 3 c 的规范里，对x q u e r y 的描述是这样 的：“x m l 是一种通用的标记语言，它能够标记多种不同数据源的信息内容，包 括结构化和半结构化文档、关系数据库和对象库等【5 引。一种使用x m l 结构的智 能搜索语言能够表达所有基于这些数据的搜索，不管数据是物理存储在x m l 中， 还是通过中间件被看成是x m l 。这个规范描述了一种叫做x q u e r y 的搜索语言， 它是被设计成能够在多种x 】l 数据源中广泛应用的”。作为一种新型的搜索语 言，x q u e r y 汲取了其它多种搜索语言的优点，适用于各种类型的x m l 数据源 的搜索，不仅搜索功能强大，而且简洁灵活且易于实现。另外，x q u e r y 还具有 从多种数据库中检索信息的特点，它能对各种数据和文档进行搜索。 f l w r 是一种典型的能够完成具有某种实际意义的搜索表达式。f l w r 表达 式包含模式匹配、过滤选择和结果构造这三种操作【”j 。f l w r 语句是x q u e r y 所 具有的最接近于s q l 的语句。使用f l w r 语句，可以用比x p a t h l 0 语句更自然 的方法来创建特定的搜索。f l w r 表达式是由f o r l e t - w h e r e r e t u r n 四个 关键字定义的子句构成的，在最新的标准中则更新为f l w o r ，o 代表新加入的 o r d e r b y 子句。由此组成的f l w o r 表达式可以完成很多在x s l t 中难以完成的 任务。它支持迭代并且可以把变量绑定到中间结果。对两个或多个文档进行连接 和重构数据时这种表达式非常有用。每个f l w o r 表达式都有一个或多个f o r 子句、一个或多个l e t 子句、一个可选的w h e r e 子句、一个o r d e r b y 子句 以及一个r e t u r n 子句。f o r 子旬通过将结点绑定到变量，以便继续去循环遍 历序列中的每一个结点；l e t 子句为一个变量赋一个值或一个序列；r e t u r n 子句定义每个元组要返回的内容；对于w h e r e 子句，如果其有效布尔值为真， 那么该元组就被保留，并且它的变量绑定用在r e t r u n 子句中。如果其有效布 尔值为假，那么该元组就被废弃。 8 硕士学位论文第二章x m l 技术及i t o s 存储结构 x p a t h 和x q u e r y 都是比较原始的搜索方法，没有很好利用节点间的相互关 系，不具有智能搜索节点的特性，并且效率也很低，不适合实际工程的需要，这 也就使它成为大量改良的原型。 2 2x m l 数据压缩后检索的几种方法 x c q ( x m lc o m p r e s s i o na n dq u e r y i n gs y s t e m ) 试图在减少x m l 数据的膨 胀问题和支持x m l 数据搜索之间取得一种平衡，x c q 利用x m l 数据的 d t d ( d a t at y p ed e f m a t i o n ) 信息来辅助压缩，压缩的过程是依靠d s p ( d t dt r e e a n ds a xe v e n ts t r e a mp a r s i n g ) 技术得以实现。在对压缩数据的搜索方面，x c q 采取了两种有效策略：首先，x c q 采用了一种全新的存储策略，称为p p g ，这 种策略将基于路径的压缩文件存储在一系列的块流( s t r e a m so f b l o c k s ) d p 。其次， x c q 对压缩后的数据块流建立最小化索弓l ( m i n i m a li n d e x ) ，在压缩数据部分解压 ( p a r t i a ld e c o m p r e s s i o n ) 的情况下，这两种策略支持在压缩数据上的聚集搜索，并 且需要的时间和空间开销也非常低【俐。 每个p p g 数据流都被分配到它所属的，大小已经被定义好的数据块中，这 使得x m l 数据的压缩率大大提高了，每个数据流中的数据块被视为一个独立的 压缩和解压缩单元。p p g 策略使得在访问指定数据时，只需要解压该数据所在的 数据块，因此被称为部分解压。 o e l e m e n tn o d e ( ) a t t r i b u t en o d e 图2 - 1x m l 文档的d t d 树 9 硕士学位论文第二章x m l 技术及i t o s 存储结构 图2 2f a g 数据流 x m i l l 是一种用户可配置的x m l 数据压缩方法，在相同的压缩速度下， 它可以达到两倍于传统压缩算法g z i p 的压缩率，允许用户将现有的压缩方法组 合起来以压缩同类的x m l 数据。x m i l l 是可扩展的，即用户可以开发自己定 义的压缩方法来压缩一些较复杂的数据格式，如d n a 序列或者是图像格式。 x m i l l 设计原则如下1 6 h6 2 1 ： ( 1 ) 结构与数据分离。x m l 的结构是指x m l 数据中的标签和属性，而 x m l 的数据是指表示x m l 元素内容的文本和属性的值。结构和数据是作为独 立单位分别压缩的。 ( 2 ) 用一定的规则将数据分组。一条数据只能归入一个数据容器中，具体 归入哪一个容器取决于数据的路径和由用户指定的容器表达式。 ( 3 ) 提供语义压缩器。x m i l l 为不同的容器提供不同的压缩器，压缩器有 以下三种：基本数据类型原子压缩器，混合压缩器和用户定义压缩器。 x m i l l 的基本架构如图2 3 所示。s a xp a r s e r 的功能是负责解析x m l 数 据，然后将解析所得的标记送到x m i l l 压缩器的核心部分一路径处理器( p a t h p r o c e s s o r ) 。每一个标记都被分配到一个容器中。标签和属性被分配到结构容器 中，而不同的数据根据容器表达式被分配到不同的数据容器中，之后每个容器都 独立地进行压缩。路径处理器的功能就是把数据和结构映射到不同的容器中，用 户可以通过命令行提供自己的容器表达式来控制映射过程。容器表达式对每一条 数据都检查一次所有的容器表达式，然后决定是将数据分配到已经存在的容器， 还是创建一个新的容器。容器被置于一个固定大小的内存窗口中( m e m o r y w i n d o w ) ，当一个内存窗口被装满时，此窗口中的所有容器都开始压缩【6 。 1 0 硕士学位论文 第二章x m l 技术及i t o s 存储结构 ix m l 输入文件i 哼is a x 解析器fi 命令行容器袁达式 i 鼯径赤理器l i 匝委匿口砬1 函 l i 结构容器l 数掘容器li i 数据容器2lr 薮掘容器k 申中哮i g z 芦，pi 申 ilii 图2 3x l i l l 数据流 x g r i n d 是一个支持搜索的x m l 搜索器，这是因为压缩数据仍然保留着源 x m l 数据的结构。这种技术适用于像掌上电脑( p a l m t o p ) 、手机这类存储空间较 小的移动设备。x g r i n d 的思想是将数据和x m l 文档的数据和结构分离，但同时 保留了待压缩x m l 文件的结构信息。x g r i n d 的压缩粒度是x m l 数据库中的元 素属性，压缩数据中保持原有x m l 数据的结构；在搜索过程中，支持部分解压 数据回答搜索。但是，利用x g r i n d 系统压缩数据需要扫描x m l 数据两遍：第 一遍获取x m l 元素的频率统计并构造字典表，第二遍扫描完成数据压缩。 x g r i n d 的架构如图2 - 4 所示，x g r i n d 压缩器中有两个解析器：d t dp a r s e r 和x m lp a r s e r 。d t dp a r s e r 用以产生需要的装载枚举数据类型的表格，x m l p a r s e r 用来记录x m l 文档中每一个元素的出现频率，构造字典表【l l 】， x g r i n d k e m e l 的作用将d t dp a r s e r 产生的表格通过枚举编g - - 马器( e n u m e n c o d e r ) 进行编码，并且根据x m lp a r s e r 产生的字典表对x m l 文档的各元素进行哈夫 曼编码【l 引。x m lg e n e r a t o r 将两种编码组合起来，形成最后的压缩文件。 二 图2 - 4x g r i n d 压缩器架构图 x g r i n d 具备一些优点：首先，在搜索反应时间方面有相当大的优势。其次， 硕士学位论文 第二章x m l 技术及i t o s 存储结构 由于x g r i n d 使得信息密度的提高，磁盘带宽也相对增加了；再次，由于压缩粒 度小到了元素属性级别