（计算机应用技术专业论文）xml数据索引技术与优化.pdf

辽宁师范人学硕士学位论文 摘要 近些年，随着互联网的不断发展，数据交换也变得频繁，由于x m l 的可移植性以 及自述性等特点，使得它逐渐成为商业、工业以及生活中重要的一种数据交换标准。 x m l 不断地被应用，从而使得x m l 数据量不断增加，这样也出现了查询数据效率的 问题，如何解决这一问题成为当今的热点问题，虽然不断有学者提出算法来提高查询性 能，如基于缓存、编码等方法，但同时这些的方法也具有相应的缺陷。本文对x m l 查询 进行了深入的研究，针对x m l 数据的管理、x m l 数据元素的编码以及索引问题进行了深 入的阐述，同时本文还提出了两种提高x m l 文档数据查询性能的算法f c - i n d e x 和算法 f s m ： ( 1 ) 支持合并操作的索引算法f c - i n d e x 为了提高x m l 数据查找性能，关键问题是能够避免对无关元素进行查询。通过对x m l 文档数据合并，可以减少文档中元素的数目，同时还能够避免查找冗余结点，有效的提 高查询效率。本文提出了一种基于c t r e e 的新索引结构f c - i n d e x ，它通过合并结构中“相 同 元素压缩结构，从而在查询过程中过滤掉与查找无关的元素，同时基于f c i n d e x 索引结构提出一种新的查询方法，能够有效的针对f c - i n d e x 进行快速的查找。 ( 2 ) 支持过滤操作的索引算法f s m 在对x m l 文档数据进行匹配过程中，重复扫描会产生许多中间路径；由于x m l 文档 数据的不确定性，使得过滤结点对查询效率提高不明显本文针对这两个问题提出了一 种新的索引算法f s m ，该算法能够有效地解决了不必要路径的归并问题，同时改进了过 滤结点方法提高效率不明显问题，通过大量实验表明，f s m 优于以前的算法，提高了查 询性能。 总之，本文提出了分别支持过滤结点以及能够避免中间路径的两个索引算法。通过 大量试验表明，这两种算法能够有效地提高x m l 数据查询性能。 关键词：x m l ；查询优化；过滤；分解；合并 ( 1 ) t h eq u e r ya l g o r i t h mf c i n d e xs u p p o r t i n gm e r g i n g f o ri m p o s e i n gx m lq u e r ye f f i c i e n c y ，t h ek e yo ft h eq u e s t i o ni sa v o i d i n gt oq u e r yt h e i r r e s p e c t i v ee l e m e n t s b yc o m b i n i n g t h ee l e m e n t s ，t h en u m b e ro ft h ee l e m e n t sc a nb e r e d u c e d ，a n dw ec a na v o i dt oq u e r yt h er e d u n d a n te l e m e n t s f o r q u e r y i n gq u i c k l ya n d c o r r e c t l y i no u ra r t i c l e ，an e w e f f i c i e n ti n d e xs t r u c t u r e - - f c - i n d e xb a s e do nc t r e ei sp r o p o s e d t ol e a c ht h ei r r e s p e c t i v ee l e m e n t si nt h eq u e r y i n g a tt h es a m et i m e ，w ea l s op r o p o s ean e w q u e r ya l g o r i t h mb a s e do nf c i n d e xw h i c h c a n i m p r o v et h eq u e r y sp e r f o r m a n c es i g n i f i c a n t l y f o rf c i n d e x ( 2 ) t h eq u e r ya l g o r i t h mf s ms u p p o r t i n gf i l t e r i n g m a t c h i n gx m l w h i c hi sb ys c a n n i n gr e p e a t e d l yc a nm a k eal o to fm i d d l er o u t e si nt h e p r o c e s so fm e r g i n g ；t h ex m l d a t a s e t si st o ou n c e r t a i nt oi m p o s et h ee f f i c i e n c yo fq u e r yw e l l b yf i l t e r i n g i no u ra r t i c l e ，an e w e f f i c i e n ti n d e xs t r u c t u r e - - f s mi sp r o p o s e d ，a n di tc a na v o i d m e r g i n gt h eu n n e c e s s a r yr o u t e s ，a n di m p o s et h ee f f i c i e n c y o ff i l t e r i n g t h r o u g hal o to f e x p e r i m e n t s ，t h ee f f i c i e n c yo ff s m i sb e t t e rt h a nt h ef o r m e ro n e s ，a n df s ma l s oi m p o s et h e e f f i c i e n c yo fq u e r y i ns h o r t ，w ep r o p o s et w oa l g o r i t h m sw h i c hs u p p o r tf i l t e r i n ga n da v o i d i n gm e r g i n gt h e u n n e c e s s a r yr o u t e sr e s p e c t i v e l yf o rt h ed e f e c t s t h r o u g ha l o to fe x p e r i m e n t s ，t h ea l g o r i t h m s c a ni m p o s et h ee f f i c i e n c yo fq u e r y k e yw o r d s ：x m l ；q u e r yo p t i m i z a t i o n ；f i l t e r i n g ；d e c o m p o s e ；m e r g e i i 辽宁师范人学硕十学位论文 目录 摘要i a b s t r a c t i i l 弓i 言1 1 1 研究背景1 1 1 1x m l 提出1 1 2x m l 简介：1 1 3 本文主要内容3 2x m l 文档管理和索引4 2 1 x m l 数据管理4 2 1 1 基于文本系统的管理技术4 2 1 2 基于关系数据库的管理技术4 2 1 3 基于对象数据库的管理技术4 2 2 x m l 数据编码5 2 2 1 位向量编码5 2 2 2 前缀编码5 2 2 3 区间编码5 2 2 4 二叉树编码6 2 3 x m l 查询处理7 2 3 1 基于外延连接查询处理技术：7 2 3 2 结构连接一8 3 一种压缩x m l 数据的索引结构9 3 1 相关工作一9 3 2 基于合并结点的查询处理9 3 3f c i n d e x 的组织结构1 0 3 4 基于f c i n d e x 的压缩算法13 3 5 基于f c i n d e x 的查询算法1 4 3 6 试验结果与分析1 5 3 6 1 实验环境和数据集1 5 3 6 2 对比实验1 5 3 7 结论：1 6 4 一种新的x m l 文档查询方法一f s m 1 7 x m l 数据索引技术与优化 4 1 相关工作17 4 2f s m 的结点编码17 4 3f s m 的结点过滤18 4 4 算法f s m 的实现19 4 4 1 分解输入路径和匹配x m l 文档树1 9 4 4 2 去除子集合中的重复路径2 0 4 4 3 合并子集合2 2 4 5 实验2 4 4 5 1 实验数据集2 4 4 5 2 实验结果与分析2 4 4 6 结论2 5 结论2 6 一i v 辽宁师范人学硕七学位论文 1 引言 随着社会的信息化，商业、生活、教育等多方面对互联网的依赖不断加深，促使了 大量不同信息的形成，其中包括完全结构化数据、无结构的文本数据以及半结构化数据， x m l 就是半结构化数据的典型。 1 1 研究背景 由于x m l 的自定义性和可描述性，使得x m l 在许多领域得到广泛应用，例如商业之 间的信息交流，图书馆中信息的查询等等。随着x m l 不断的应用，使得x m l 数据迅速增 加，如何有效地提高用户对x m l 数据的索引也成为了研究工作者讨论的热点问题。 1 1 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 ) ，即可扩展的标记语言，是由w 3 c 的x m l 工作组 定义的，是一套定义语义标记的规则，其目标是允许普通的s g m l ( s t a n d a r dg e n e r a li z e d m a r k u pl a n g u a g e ，标准通用标记语言) 在w e b 上以目前的h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ) 的方式被服务、接收与处理。x m l 作为一种半结构化数据模型具有自描述性、 可移植性等特点。 随着x m l 文档存储不断的被广泛应用，数据数目也随之不断增多，直接对x m l 文档 进行查询，效率很低，已经不能满足用户对性能的要求。如何利用索引、缓存或者是其 它技术来有效地提高查询性能已经成为当今学者研究的主要问题。 1 2x m l 简介 x m l 文档由标记和内容组成。标记分为六种：元素( e l e m e n t s ) 、属性( a t t r i b u t e s ) 、 实体引用( e n t i t yr e f e r e n c e s ) 、注释( c o m m e n t s ) 、处理指令( p r o c e s s i n gi n s t r u c t i o n s ) 以及c d a t a 段( c d a t as e c ti o n s ) 。 x m l 文档主要由元素构成，同时一个x m l 文档必须至少有一个元素。元素是由起始 标记和终止标记构成，起始标记记为 ，终止标记则记为 ：元素的其 它信息用属性保存，表示为属性名= 属性值，一个元素可以有多个属性，但是这些属性 的属性名不能相同。如图1 1 是一个x m l 文档实例。 x m l 文档是根据d t d 规定的结构模式，以顺序、嵌套的关系组成的。d t d 是被指定的 一种x m l 文档结构，同时也指定了元素、属性、实体以及符号表示法之间的相互关系以 及其它的规则。d t d 有三个用途：标记创建x m l 文档、规范标记参数、解释文档。 如图1 2 描述的是一个x m ld t d 实例。 元素类型定义的形式为： 图1 1x m l 文档实例 f i g 1 1x m l d o c u m e n t 在图1 2 中，d t d 的第一行定义了x m l 文档的跟元素p u b l i c 。p u b l i c 元素有四个子 元素l i b r a r y 、b o o k 、n a m e 以及y e a r 。其中，1 i b r a r y 是必需的，并且只能出现一次； b o o k 、n a m e 和y e a r 都是可选的。第二行定义了元素b e o k ，它包含了两个子元素：t i t l e ， p r i c e 。 在d t d 中定义属性时，使用下面的格式： 元素名是属性所属的元素的名字，属性名是属性的命名，属性类型则用来指定该属 性是属于有效属性类型中的哪种类型，默认声明用来说明该属性在x m l 文件中是否可以 一2 一 辽宁师范大学硕十学位论文 省略以及默认值是什么。共有三种默认声明，一是# r e q u i r e d ，表示该属性在x m l 文件 中是必须出现的；二是# i m p l i e d ，表示该属性在x m l 文件中是可以省略的；三是声明默 认属性值。 图1 2 x m ld t d 实例 f i g 1 2x m l d t d 1 3 本文主要内容 本文分为三部分，内容如下： 第一部分主要介绍x m l 数据的相关知识，如x m l 数据的管理、数据编码以及针对x m l 数据的查询方法。 第二部分主要介绍了基于压缩路径的索引方法f c - i n d e x 。通过该算法，可以有效的 过滤x m l 树中的重复结点，优化结构，从而提高查询效率。 第三部分主要介绍了一种索引方法f s m 。通过该算法，能够提高过滤结点的效率， 同避免了在匹配过程中产生中间路径的问题。 一3 一 x m l 数据索引技术与优化 2x m l 文档管理和索引 2 1x m l 数据管理 x m l 已经成为数据交流的一种标准，凭借x m l 的灵活性、可移植性的特性，在i n t e r n e t 的各个领域得到了广泛应用。对这些大量的x m l 文档数据进行存储和查询已经是一个重 要的研究问题。 x m l 数据管理方法目前主要分为四种，即基于文件系统的方法、基于关系的方法、 基于对象的方法和n a t i v ex m l 数据管理方法。 2 1 1 基于文本系统的管理技术 x m l 数据的一般表示形式是文本文档，存储于文件系统里，通过对文本系统的操作， 实现x m l 数据的管理，x m l 数据访问的入口即为文件系统的句柄。基于这种存储的查询 有三种：基于信息检索技术的关键词查询、采用x s l t 语言的文档格式转换形式的查询 以及定制的基于d o m 或s a x 接口的查询。 i r ( i n f o r m a t i o nr e t r i e v a l ，信息检索) 技术主要根据数据关键字的倒排索引为规 则，通过对关键字的查询，找到用户所要搜索的信息。基于i r 技术的索引方法的一个 缺陷是将x m l 文档看作为无结构的文本格式，去除了数据结点之间存在的关系。 2 1 2 基于关系数据库的管理技术 基于关系数据库的的管理法式主要分为两种：( 1 ) 依赖于文档的方法，即从x m i 。文 档对应的d t d 中提取出于x m l 数据对应的关系模式，不同的d t d ，其关系模式也不同。 ( 2 ) 独立于文档的方法，即x m l 文档信息不再依赖于d t d ，而是根据x m l 文档的逻辑结 构来创建关系模式。 关系数据库管理x m l 数据的基本思想是：将x m l 数据以某种规则进行转换，将转换 后的数据存储在关系表中；转换x m l 文档查询语言，即把x q u e r y 或者x p a t h 转化为s q l 语言；最后进行查询，得到用户所需要的结果。 基于关系数据库系统的管理方法有如下几种模型映射方法，即独立于文档方法： e d g e 、m o n e t 和x r e l 。 2 1 3 基于对象数据库的管理技术 o d m g 标准根据面向对象数据库，将数据结构映射成为嵌套的结构模型，同时，运用 o q l 语言对x m l 文档进行查询。文献 1 介绍了对象技术s g m l 的使用。 文献 2 介绍了两种基于对象数据库的存储映射技术。 一4 一 辽宁师范人学硕十学位论文 第一种方法是用固定的存储模式保存x m l 文档数据，存储方式与x m l 文档对象模型 ( d o m ) 相似。在该方法中，元素类型分为两种：t a g 和p c d a t a ，分别表示元素结点与 文本结点；a t t r i b u t e 分为四种：c d a t a 、i d r e f 、i d 与i d r e f ( s ) 。 第二种方法是将x m l 元素类型转化为对象类型，该方法使用o d m g 使x m l 元素之间实 现连接。这种方法能够处理具有某种模式的x m l 文档数据，但是在处理这种x m l 数据后， 会产生大量的类碎片，从而会严重影响系统的性能。 2 2 x m l 数据编码 一般的元素关系包括：祖先后裔( a n c e s t o r d e s c e n d a n t ) 关系、双亲孩子 ( p a r e n t c h i l d ) 关系之前之后( p r e c e d i n g f 0 1 1 0 w i n g ) 关系、左兄弟右兄弟 ( p r e c e d i n g s i b l i n g f o l l o w i n g s i b l i n g ) 关系等。 为了高效地对x m l 数据进行索引，特别是结构查询，可以对x m l 文档数据编码，通 过编码能够迅速判断出x m l 文档中任意两点在结构树中是否存在父亲或是祖先的关系。 x m l 数据编码的基本思想是：对x m l 数据树采用某种规则进行遍历，得到相应的结点 序列，相应地结点在序列中就具有唯一的序号( 编码) ：对于x m l 树中的任意两个结点， 对它们的序号可以构建某种运算，运算的结果可以表征结点之间的结构关系。 根据编码表现形式的不同，结点编码方法可分为4 类：位向量编码、前缀编码、区间 编码以及二叉树编码。 2 2 1 位向量编码。 龟 文献 3 提出了位向量编码：将树t 中的结点编译成m 位的向量，m 是树t 中的结点 个数，假设在位置i 上的某一位惟一地标识第i 个结点；并且在一个自顶向下( 或者自 底向上) 的编码方案中，结点继承标识它祖先( 或者后裔) 的所有位上的“l ”。 2 2 2 前缀编码 前缀编码，也即d e w e y 编码，它的主要思想是：假设x m l 树结构中的一个结点v ， 将它的父亲结点u 的编码作为该结点的前缀。编码的规则是：假设x m l 树中任意结点n ， 它的d e w e y 编码为c ( u ) ，则它的后裔结点m 相应的d e w e y 编码则为c ( m ) = c ( n ) d ，其中， d 为m 的结点i d 值。文献 4 深入介绍了对x m l 数据的d e w e y 编码的研究。 2 2 3 区间编码 区间编码的基本思想是：将x m l 结构树中的结点以前序或者是后序遍历的方法对结 点进行编号，即为区间编码( i n t e r v a l e o d i n g ) 。它的基本记录格式为( i d ，p r e ，p o s t ) ，其 中i d 表示结点的标签。比较经典的区间编码有l i - m o o n 编码以及z h a n g 编码。 x m l 数据索引技术与优化 ( 1 ) l i m o o n 编码 l i m o o n 编码的主要思想是：将x m l 结构树中的每一个结点进行编码，编码的格式 是 ，其中o r d e r 是非连续的结点扩展前序遍历序号，它是为结 点插入预留序号空间；s i z e o f 是结点的长度，l e n g t h 是结点的深度，即从根结点到该 结点的层数。 ( 2 ) z h a n g 编码 z h a n g 编码的基本思想是：对x m l 树中的结点进行前序遍历，任意结点都会在遍历 的过程中被遍历两次，并且产生两个序号。 ( 3 ) w a n 编码 w a n 编码的基本思想是：将x m l 数据树中的结点编码为二元组 的 形式。o r d e r 代表结点的扩展先序遍历序号；m a x o r d e r 则代表结点的后裔中最大的扩展 先序遍历序号即以该结点为根结点的子树中最右下角结点的扩展先序遍历序号。 2 2 4 二叉树编码 二叉树编码是基于树形结构的x m l 文档具有的嵌套特性，遍历树结构中的每一个结 点，同时赋予该结点一个编码。它的主要典型算法主要有：p b i t r e e 编码、k - a r y 编码。 ( 1 ) p b i t r e e 编码 文献 5 中介绍了一种有效的x m l 文档基于包含连接的查询处理p b i t r e e 编码。 p b i t r e e 树是p b i t r e e 编码将x m l 文档树根据某种规则映射得到的。p b i t r e e 树是一棵 图2 1p b i t r e e 树 f i g 2 1p b i t r e et r e e 辽宁师范人学硕士学位论文 完全二叉树，将树中的任意结点按照某种规则进行遍历，并对结点进行编排序号，称为 p b i t r e e 编码，记为1 c o d e ，1 在树中的高度是1 1 e n g t h ，1 在树中所处层数为m 1 e v e l 。 假设v 是n 在n 。l e v e l 层中所有结点的序号，那么n c o d e = ( 1 + 2 v ) 2 “k w 仆1 h ”：如果当 n c o d e = 2 “k 略曲”，那么结点n 和v 就是祖孙关系。 ( 2 ) k - a r y 编码 将x m l 树中的所有结点映射成为一棵完全k 叉树记为k - a r y 编码。k - a r y 编码的基 本思想是：假设x m l 树中的任意结点v ，将结点v 的k - a r y 编码为n c o d e ，那么结点v 的父亲结点编码是( ( v c o d e 一2 ) k ) + 1 ，v 的第h 个结点的编码就为k ( v c o d e - 1 ) + h + 1 。 2 3 x m l 查询处理 2 3 1 基于外延连接查询处理技术 路径表达式是对x m l 树进行的定位操作，从而得到所要查找的结果。外延连接的基 本思路是：将输入路径进行分解，得到若干个路径；将这些路径与一个x m l 外延、x m l 限定外或者x m l 外延过滤器相关联，所以根据路经查询顺序，对结点之间的关系进行相 关的连接操作；根据多路径得到的结果进行操作得到最终结果。 x e l e n g i n e 是一种x m l 路径表达式查询外延连接查询处理器，通过利用外延连接技 术，对x m l 数据树进行查询操作。图2 2 是x e l - e n g i n e 的结构示意图。 根据路径表达式进行查询相对比较容易，所以基于这种方法的解析过程也相对容易。 图2 2x e j e n g i n e 系统结构 f i g 2 2x e j - e n g i n es y s t e ms t r u c t u r e 对中间结果进行重构，目的是对不需要、重复的、不符合的部分进行去除处理，最后按 照某种预定的顺序执行物理查询计划。 x m l 数据索引技术与优化 2 3 2 结构连接 x m l 文档的查询可以通过结点之间的包含关系或者文档位置关系转化为结点之间的 结构连接操作，同时关键字操作也可以通过这种方法进行结构连接操作。所以，解决x m l 文档查询的关键问题是对结构连接的有效支持。 具有包含关系( 祖先后裔关系或双亲孩子关系) 所得到的结果有两种情况：具有 包含关系的元素( 如关系表的元组) 对的序列( 关系元组的有序集合) ，或者是具有包 含关系的后裔( 或祖先、孩子、双亲) 结点的序列。同样文档位置关系得到的结果也有 两种情况：具有文档位置关系的元素对的序列，或者具有文档位置关系的之后( 或之前、 左兄弟、右兄弟) 元素的序列。拥有关系得到的结果只能是拥有关系的祖先( 或双亲) 元素的序列。 结构连接算法可大体分为两类： ( 1 ) 包含关系的结构连接 直接归并结构连接算法； 基于缓存的归并结构连接算法； ( 2 ) 文档位置关系的结构连接。 c z h a n g 和j n a u g h t o n 等针对实现包含连接操作，提出了基于包含关系结构连接方 法的算法m p m g j n ( m u l t i p r e d i c a t em e r g ej o i n ) 。 m p m g j n 算法的基本思想是：假设两个关系表a 与b ，则外表a 中的第一个元素a ， 对b 进行顺序遍历，查找能够与a 。进行连接的元素集合，并将它作为扫描起始点( s c a r l s t a r tp o i n t ) ，之后再对内表b 中同样进行顺序遍历，查找满足b e g i n 1 9 9 5 从图3 6 ( a ) 和图3 6 ( b ) 来看，f c i n d e x 所用时间都少于c t r e e 和x i s s 。主要原因 是c t r e e 进行结点合并是根据结点等价来处理，在处理后的结构中包括不完全相同的结 点路径，这样在查找相应元素时，会对不相关的路径进行查找，从而影响查询效率。而 1 2 3 4 5 6 町 町 叽 町 叽 町 x m l 数据索引技术与优化 f c i n d e x 则是根据结点路径相同对元素进行处理，构建完整的、规范的树形结构，通过 这种规范化的结构，在对路径元素查找时，能够迅速的查找到结果，减少了查询时间。 对结构简单的文档进行索引，由于其文档结构的嵌套性较低，f c - i n d e x 能够直接查 ，一、 u 们 基 o e 卜 。m。f。c。-。i。n。d。e。1x。-v i - c t 。i i 旦苎! l ，、 u o c 力 昌 q g 卜 图3 6 过滤后的查询时间对比 f i g 3 6c o m p a r i s o no fr u n n i n gt i m ea f t e rf i l t e r i n g mf 面c - i n d e x i c t r e ef i 旦5 1 墅 找到结果，在性能方面与c t r e e 相差不多。当结构索引变得很大、复杂时，通过实验结 果来看，f c i n d e x 能够很好的适应复杂的结构文档，在查询结果时，利用我们提出的针 对f c i n d e x 的查询算法，能够迅速提取出满足条件的结果，很好的处理性能要求。 3 7 结论 本文在分析国内外的工作基础之上，针对已有的c t r e e 进行改进，提出了一种以结 点路径相同为原则的索引结构f c - i n d e x ，可以对x m l 文档进行规范的结构处理，从而提 高查询效率，针对合并后的结构，提出一种有效的查询算法，能够对合并后的元素进行 有效的查询。基于不同数据集的试验结果表明，本文提出的基于f c - i n d e x 的查询处理 方法可以有效提高查询效率。 - 女 龄? ? 辽j 叫币范大学硕十学位论文 4 一种新的x m l 文档查询方法f s m x m l 半结构化特点，使x m l 可以通过w e b 进行数据的交换，同时x m l 数据库可以同异构 数据库进行连接，但是随着存储数据量不断增加，对x m l 数据库中的数据查询也变得繁 琐，仅仅通过遍历结点的查询方法，严重影响查询效率，所以，有关x m l 文档查询问题 受到了众多学者的广泛关注，成为x m l 数据库的热点问题。 4 1 相关工作 近年来出现了许多优秀查询的方法，如文献 2 1 提出了一种基于栈的算法 s t a c k - t r e e ；文献 2 2 提出了一种完整的小枝模式匹配算法t w i g s t a c k ，通过对局部匹 配结果进行归并，得到查询结果，但是这种方法的代价是需要多次对中间结果进行存取； 文献 2 3 提出了一种基于结点流和栈链的连接算法p a t h s t a c k ；文献 2 4 提出了只需要 访问叶子结点的t j f a s t 算法；文献 2 5 提出了一种x r 树索引，它能够跳过后裔列表和 祖先列表中所有不匹配的结点。由于x m l 文档数据的不确定性，以及不可避免的不必要 路径的归并，影响了查询效率。文献 9 和文献 2 6 提出了1 - i n d e x 算法和f & b - i n d e x 算 法，它们通过过滤结点，减少结构中结点数量来提高查询效率，通过大量实验表明，由 于x m l 文档数据的不确定性，通过过滤结点并不能有效的提高查询效率。 对x m l 文档进行查询处理的关键两个问题：( 1 ) 如何避免对不必要路径的归并问题； ( 2 ) 如何解决当采用过滤方法对结构复杂、重复路径少的x m l 文档查询，查询效率的 效果不明显问题。针对这两个问题，本文提出了一种新的算法f s m ，采用分解后的输入 路径v 。对x m l 文档树进行模式匹配得到集合q 。，算法对集合q 。分解、过滤，最后得到查 询结果，整个过程有效地解决了这两个问题。 4 2f s m 的结点编码 为了对x m l 实现有效查询，可以对x m l 文档进行编码，编码能够快速确定x m l 文档树中 任意两点在结构树中的关系。 x m l 文档树的编码方案可分为两类：基于空间的编码和基于路径的编码。已经提出的 编码方案主要包括：位向量编码瞳引、前缀编码啪2 啪1 、区间编码乜刚和二叉树编码心3 1 等。 区间编码方法是对树中的结点赋予一个区间编码 s t a r t ，e n d ，同时每个结点的区i 日j 编 码中还包含它后裔结点的区间编码，即，树t 中结点u ，它祖先结点为结点v ，当且仪当 s t a r t ( v ) s t a r t ( u ) 八e n d ( u ) e n d ( v ) 。 x m l 数据索引技术与优化 算法f s m 采用 对x m l 文档树进行编码，s t a r t 采用升序排 列，l e v e l 代表结点所在的层数，p a r e n t 代表结点所在的层数的i d 值，它的作用是可以 直接查找到父亲结点。 4 3f s m 的结点过滤 过滤结点主要目的是过滤掉x m l 文档树中存在的重复路径，这样既能够避免对路径进 行重复查询，又减少结构中结点数量，压缩了x m l 文档。 f s m 采用的过滤方法是基于文献 2 7 提出的f c - l n d e x 算法，f c i n d e x 算法是通过判断 结点的父亲结点以及后代结点来决定是否过滤结点。图4 1 ( a ) 是一棵x m l 文档树，图 4 1 ( b ) 是利用算法f c i n d e x 对图4 1 ( a ) 过滤结点后的x m l 文档树结构图。 赢， 面5 澍 ( b ) f c - in d e x 图1 索引结构 f i g 4 iq u e r ys t r u c t u r e 性质4 1 ：f c - i n d e x 存储结构是采用深层遍历结点来存储x m l 文档，如果任意一个结 点q 的i d 值大于该结点之前的任何结点，同时又大于下一个结点的i d 值，那么结点q 就是 一个叶子结点，同时也是所在路径的最后一个结点。 辽宁师范人学硕士学位论文 图4 1 ( b ) 经过f c - i n d e x 算法对x m l 文档过滤结点后的树形结构，它的存储结构为 a 1 a 2 b 1 d 6 c 2 f 5 c 3 a 1 b 2 d 5 ，其中结点c 3 的i d 值大于它前面所有结点的i d 值， 又小于下一个结点a 1 的i d 值，那么c 3 就是一个叶子结点，同时也是路径m = a 1 a 2 b 1 d 6 c 2 f 5 c 3 的最后一个结点。 4 4 算法f s m 的实现 f s m 用 对x m l 文档进行编码，并用f c i n d e x 算法对它进行 过滤结点操作：对输入路径分解，用分解后的输入路径匹配过滤结点后的x m l 文档树， 把匹配的结果放到相应的子集合q 。中；去除子集合q 。中存在的重复路径：最后合并子集 合，得到查找结果。 4 4 1 分解输入路径和匹配x m l 文档树 定义4 1 ：如果一条查找路径q = ae d f b c ，那么在路径q 中每个分支路径的公 共结点叫做交叉结点。 通过输入路径中的交叉结点，把复合的路径分解成为单一路径，分解后的每一条路 径中不存在分支路径。如果在输入路径中存在多个交叉结点，那么根据交叉结点i d 值的 大小，采用由小到大的顺序进行分解。 如图4 2 ，路径q = a d f b c ，根据定义l ，结点a 是交叉结点，所以，路径q l i 丁 以分解为a d f 和a b c 。本文用“”代表结点之间的父亲关系，“”代表结点 之间的祖先后代关系。 图4 2 分解输入路径 f i g 4 2q u e r ys t r u c t u r e 定义4 2 ：如果把输入路径分解成为单一路径，那么单一路径的第一个结点就叫做头 结点。 在分解路径完成之后，为每条单一路径分配一个存储空间，本文把这个存储空间称 为子集合。子集合中存储的是x m l 文档树中跟相应单一路径匹配的路径结点。 x m l 数据索引技术与优化 对x m l 文档树过滤，根据性质4 1 ，把单一路径的头结点作为根结点，深层遍历x m l 文档树，进行模式匹配，把匹配的结果放到相应路径的子集合中。如图4 3 是图4 2 对图 4 1 ( b ) 匹配的结果，子集合q l 和q 2 分别是路径a b c 和路径a d f 匹配的结果。 4 4 2 去除子集合中的重复路径 性质4 2 ：对于任意路径u = a i i b c d ，用子路径b c d 、c d 查找得到的结果与用 路径u 查找得到的结果相同，即，u 的任意子路径都是u 的重复路径。 a n n cf q 1 0 2 考虑到单一路径的头结点在x m l 文档树的某条路径中可能多次出现的情况，所以在匹 配过程中，在同一条路径中可能出现多个结果，但实际这些查询是同一结果，即重复结 果。图4 3 ，在子集合q l 中，路径a = a 2 b 1 c 2 和路径b = a l a 2 b 1 c 2 都是路径a b c 的 查询结果，但是路径a 是路径b 中的一部分，路径a 既是重复结果。所以，在子集合合并 之前，f s m 对每个子集合中的重复路径进行过滤。 在过滤重复路径之前，先对子集合进行分解、合并路径处理，能够提高去除重复路 径效率。根据结点i d 值由小到大的顺序，每两个结点存储在一个块中，把块中最小的i d 作为这个块的i d 。但是，每条分解的路径的第一个块的i d 值有两个，分别为路径的头结 点和尾结点的i d 值：路径中的最后两个结点存储的块的i d 值也有两个值，分别是这两个 结点的i d 值；之后再存储到原来的子集合中。如图4 4 是针对图4 3 中子集合q l 的路径分 解合并。 甲尚芏甲囱 甲富 甲南王甲由 甲申黉台 印尚芏甲由 ；| 刊 甲由富们空薰 甲南芏甲崮 甲尚芏掣寓 甲寓 辽宁师范大学硕十学位论文 通过路径分解合并，使得子集合中的路径长度缩短，在过滤路径的过程中，直接通 过判断块中的i d 值来进行操作。通过大量实验表明，经过路径分解的过滤相对于不经过 ，佃f 匹配路径蟹合 图4 4 分解子集合路径 f i g 4 4d e c o m p o s i n gt h er o u t e so ft h es u b s e t 处理的子集合而直接进行过滤路径，在时间效率上前者明显优于后者。 算法4 1 ：r e m o v eo v e r l a p 0 输入：输入对x m l 文档树匹配得到的子集合q 。 输出：没有重复路径的子集合q 。 一 1 w h i l e ( e m p t y ( q 。) ) 2 c r e a t e li s t ( q 。) ： 分解子集合中路径； 3 f o r ( i a 2 ，函数i s l i s t 用短路径a l 对长路径a 2 进行比较，如果a 1 、a 2 是重复路径，返 回t r u e ，否则返回f a l s e ；如果a l a 2 ，函数i s l i s t 用短路径a 2 对长路径a 1 进行比 较，如果a l 、a 2 是重复路径，返回t r u e ，否则返回f a l s e 。 4 4 3 合并子集合 曲于各个子集合是单一路径从x m l 文档树中匹配得到的，所以只需合并这些子集合， 而合并的前提条件是合并的路径中存在公共结点，公共结点是通过判断两条路径中是否 存在i d 值相同的结点得到的。 性质4 3 ：如果两个子集合中任意的两条路径y 、x 存在公共结点，其中y 和x 的头结点 的i d 值分别为( y l jy 2 ) 和( x l ，x 2 ) ，那么，( y 1 ，y 2 ) n ( x 1 ，x 2 ) 一定能得到一个整数， 而这个整数就是公共结点的i d 值。 辽宁师范人学硕士学位论文 在子集合中路径的头结点存储两个i d 值( a 1 ，a 2 ) ，根据性质4 3 ，能够判断出两条路 径之间是否存在公共结点，从而避免对中间结果的操作。如图4 5 ，子集合l i s t l 中的路 径a 对子集合l i s t 2 中两条路径b 和c 合并，a 头结点的i d 值为( 2 、8 ) ，b 和c 的头结点分 l i l i l i 图4 5 合并路径 f i g 4 5m e r g i n gr o u t e s 别为( 1 、9 ) 和( 2 、1 1 ) ，显然a 分别与b 、c 存在着交叉整数2 ，也就说明存在i d 值为2 的公共结点b 2 ，所以a 可以同b 和c 合并。 算法4 3 f i n d r e s u l t0 输入：输入合并后的子集合q 。 输出：查询结果 1 w h i l e ( e m p t y ( q 1 ) ) “ 2 v k = g e t l is t ( q 1 ) ： 3 v g = g e t l i s t ( q n ) ： 4 i f ( i d l i s t ( v k ) ni d l i s t ( v g ) ) t h e ni i ! 殳r j 果两条路径有公共结点： 5 o = f i n d n o d e ( ) ：得到公共结点： 6 g e t r e s u l t ( 0 ) ： 合并路径，得到查询结果： 7 e ls e 8 v g = g e t l is t