（计算机应用技术专业论文）基于索引的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 索引的动态更新技术。取得的成果体现在以下四个方面： ( ”设计了x m l 索引动态更新算法 目前x m l 路径索引已经得到较为全面的研究，但是x m l 索引地动态更新没有有效地 解决。本文设计了一种x m l 索引p a t h v a l u e i n d e x ，它由两部分组成：路径索引和属性索引。 其中路径索引查找正则路径，属性索引查找正则路径中带有谓词的等值查询。索引 p a t h v a l u e i n d e x 能够实现x m l 索引地动态更新，当x m l 文档中插入新的文档片断，或删除 x m l 文档中的某些结点或修改x m l 文档中某些结点值时，x m l 索引也能动态更新。 ( 2 ) 提出了x m l 多分支路径索引查询算法d e p t h j o i n 目前x m l 单路径查询和简单的分支路径查询已经得到了较好地解决，但如何高效地实 现x m l 多分支路径查询还没有较好的方法本文提出了基于索引的x m l 多分支路径查询 算法d e p t h j o i n 。该算法首先对x m l 文档进行编码并创建索引，然后在对查淘树进行查 询匹配的过程中采用多栈存储多分支路径中的单路径，对分支结点采用索引判定其孩子结 点是否具有共同的祖先结点或父结点与现有的x m l 分支查询算法相比算法d e p t h 1 0 i n 充分利用索引，不需要进行单路径的连接操作。 ( 3 ) 提出了x m l 多分支路径索引查询算法m b p q 解决多分支路径查询算法的一般思路是将多分支路径拆分成单路径，分别对单路径进行 查淘，然后将单路径的查陶结果进行多重循环匹配得到多分支路径查询结果，查询效率较低。 本章提出了一种高效的x m l 多分支查询算法m b p q 。该算法首先对x m l 文档树进行编码， 然后对多分支路径各结点进行编号。编号后将多分支路径拆分成单路径并对单路径进行查 询，利用栈匹配具有共同祖先结点的单路径查询结果，最后得剑多分支路径查询结果。与现 有的x m l 多分支查询算法相比，算法m s p q 充分利用多分支路径的特点，大大减少循环匹 配次数。 ( 4 ) 开发了x m l 路径索引查询及索引更新原型系统，通过功能测试表明系统能正确 运行。 关键词：x m l 索引，x m l 查询，x m l 索引更新，索引查询 南京师范大学硕i 论文 a b s t r a ( 玎 a b s t r a c t x m l q u e r yi sa ni m p o r t a n ta r e ao fx m lt e c h n o l o g y a l t h o u g ha c h i e v e m e n t so fx m l i n d e x q u e r yr e s e a r c ha r em a d e t h e r ea r es o m ep r o b l e m so fx m lq u e r yt e c h n o l o g yb e c a u s eo fx m l s i n h e r e n tc h a r a c t e r i s t i c t h i st h e s i st a k e sf o c u so nt h et e c h n o l o g yo fx m lq u e r y t h i st h e s i sa d d r e s s e ss e v e r a lk e y t e c h n i c a lp r o b l e m so f i n d e x i n ga n dq u e r y i n gx m l ，m a j o rc o n t r i b u t i o n so f t h i st h e s i si n c l u d e ： ( 1 ) d e s i g nax m li n d e xu p d a t i n ga l g o r i t h m x m li n d e xu p d a t i n gh a sb e e nr e s e a r c h e d d e e p l y b u tx m li n d e xu p d a t i n gi s n o tr e s o l v e dw e l l t h i sp a p e rp r e s e n t sax m li n d e x p a t h v a l u e i n d e xw h i c hi sc o n s i s t e do fp a t hi n d e xa n dv a l u ei n d e x , t h ei n d e xu p d a t i n ga l g o r i t h m r e s o l v e sx m l u p d a t i n gp r o b l e mw h e nt h ex m l d o c u m e n ti su p d a t e d ，t h ex m li n d e xe a nb e u p d a t ea tt h es a m et i m e ( 2 ) p r e s e n tax m lm u l t i p l eb r a n c hp a t h e sq u e r ya l g o r i t h md e p t h j o i nb a s e do ni n d e x x m ls i n g l ep a t hq u e r ym e t h o d sa n ds i m p l eb r a n c hp a t hq u e r ym e t h o d sh a v eb e e np r e s e n t e d ，b u t h o wt oq u e r ym u l t i p l eb r a n c hp a t h e sh a v en o tb e e ns o l v e dw e l l t h i sp a p e rp r e s e n t st h ea l g o r i t h m d e p t h j o i nf o rq u e r y i n gx m lm u l t i p l eb r a n c hp a t h e sb a s e do ni n d e x t h ea l g o r i t h me n c o d e s t h ex m ld o c u m e n ta n dc r e a t e st h ei n d e xf o rt h ex m ld o c u m e n t s i tr e s t o r e st h es i n g l ep a t h so f t h em u l t i p l eb r a n c hp a t h e su s i n gt h em u l t i p l es t a c k so nt h ep r o c e s so f m a t c h i n go f t h eq u e r yt r e e ， j u d g i n gt h eb r a n c hn o d e sh a v et h es a m ea n c e s t o r so rp a r e n to rn o tb yt h ei n d e x c o m p a r e dw i t h t h ee x i s t i n ga l g o r i t h m s ，t h ea l g o r i t h md o c s n tn e e d j o i nt h es i n g l ep a t h s ( 3 ) p r o p o s ea ne f f i c i e n ta l g o r i t h mm b p qf o rx m lm u l t i p l eb r a n c hp a t h e sq u e r y t h e a l g o r i t h me n c o d e st h ex m l d o c u m e n ta n dx m l q u e r yt r e e , d i s j o i n t st h em u l t i p l eb r a n c hp a t h e s i n t os i n g l ep a t h s ，q u e r i e st h es i n g ep a t h sa n du s e st h es t a c kt om a t c ht h es i n g l ep a t h e sw h i c hh a v e t h es a m ea n c e s t o r si nt h ep r o c e s so fm a t c h i n gt h es i n g l ep a t h st ot h em u l t i p l eb r a n c hp a t h e s c o m p a r e dw i t ht h ee x i s t i n ga l g o r i t h m st h ea l g o r i t h mm a k e sf u l lu s eo f t h et y p i c a lo f t h em u l t i p l e b r a n c hp a t h e s , r e d u c e st h el o o pn u m b e re x t r e m e l y ( 4 ) d e v e l o p eax m lq u e r y i n g p r o t o t y p es y s t e mu s i n gv c + + e x p e r i m e n tr e s u l t ss h o wt h a t t h i ss y s t e mc a l lr a nc o r r e c t l y k e y w o r d s ：x m li n d e x ；x m lq u e r y ；x m li n d e xu p d a t e ；i n d e xq u e r y l i 学位论文独创性声明 本人郑重声明： 1 、坚持以。求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定 作者签名： 日期： 南京师范人学硕i 。学位论文 第一章绪论 1 1 研究背景与意义 第一章绪论 1 9 9 6 年出现的可扩展的标记语言( e x t e n s i b l e m a r k u p l a n g u a g e ，x m l ) 目前被认为是 互联网上数据表示和数据交换的新标准，并被广泛接受，越来越多的网上资源将以x m l 的 格式表示。x m l 同h t m l 兼容，具有平台无关性，同时又是一种真正的扩展语言，能以可 读的格式提供数据而义不受到表现形式的限制，因此x m l 的灵活、开放和基丁：标准的格 式使它很快变成商业世界中用来交换商业数据的最j “泛使用的语言。通过x m l 数据发布和 交流信息已被企业j “泛采用。 目前x m l 技术被人t f j j “泛地接受，其原因是多方面的，但一个非常重要的，不可忽视 的因素是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 - q l l 2 1 ，x q l l 3 1 ，q u i t i q ， 及x q u e p i s 】等。x q u e r y 是w 3 c 所推荐的x m l 查询语言标准，它能够表达对各种数据源的 查询。这些查询语言尽管各有特点，但它们的一个共同特点是都将路径表达式作为其核心内 容，用户可以用路径表达式来描述在x m l 数据层次中的定位。x m l 查询中的路径表达式 可以表现为树状的查询能独立地描述查询要求。 如何有效的对x m l 文档树进行查询使得索引技术愈发重要，目前很多x m l 索引技术 已被提出，具体可以分为路径索引如：d a t a g u i d e t 6 1 、1 - i n d e x l 7 1 、a ( k ) m 、d ( k 尸、m ( k ) i “、 a p e x i “) ，f a b r i c 1 2 1 等，以及结构索引如：x r + x r s t a c k 13 】算法，a n cd c s cb + 【1 4 1 算法、 t s g e n c r i c + ”1 算法等。 路径查询最直接的方法就是对x m l 文档树进行遍历，即从根结点出发，沿着树中的边 搜索，寻找匹配路径表达式的结点。但这种方法的效率很低，当存在不确定路径经常会对整 个树进行遍历，特别是在查询路径的结构复杂如褒询多分支路径的情况下，并不能通过遍历 文档树来得到查询结果。 如何高效地对多分支路径查询成为本文研究的重点，本文在江苏省高校自然科学基金 ( 0 4 k j b 5 2 0 0 7 5 ) 资助下研究下列问题：( 1 ) 如何有效地解决多分支路径的杏询。( 2 ) 怎样 实现x m l 索引的动态更新技术。 3 南京师范人学硕i ：学位论文第一审绪论 1 2x i l 简介 1 2 1x 地基本概念 定义1 - 1x m l 文档：一篇x m l 文档由三部分组成：x m l 声明，文档类型定义和x m l 文档土体。其中，x m l 文档主体是由一个根元素( r o o t ) 构成它的内容不出现在任何其 他元素中。根元素内部由一组嵌套元素序列组成，每个元素由一组开始和结束标签对或是一 个空标签界定。每个元素还可以对应包含多个属性，用来描述该元素的特征。如图1 1 所示， 该文档只包含了x m l 声明( 第一行) 和x m l 文档主体，文档类型定义部分缺省 硎弱l o g c d e m p i r eb u r l e s q u e b o bd y l a n 司c o u n t r y u s a c o l u m b i a 1 0 9 0 1 9 8 5 q y e a r e r o s e r o sr a m a z z o t t i 口c o u n t r y e u b m g 9 9 0 k 时， 在a ( 1 ( ) 索引中无论采用自底向上或臼项向下的查淘策略所得到的奄询结果都有可能包含错 误的奄询结果。所以在这种情况f 还要将所得到的查询结果在x m l 数据图上进行验证，以 确保所得剑的奄询结果是正确的。 4 、d ( k ) 索引 a ( k ) 索引中每个索引结点的相似度都为k ；d 索引是对频繁使用的路径进行索引。而 频繁使用的路径跃度往往是不相同的，因此d ( k ) 索引中的每个结点的局部相似度k 也不相 同 d ( k ) 索引有如下两个性质：( 1 ) 每个索引结点与一个局部相似度k 有关( 2 ) 给定一 个索引结点的局部相似度k 它的父结点的局部相似度至少为k - 1 。 d ( k ) 索引主要由两个算法组成：( 1 ) 索引创建算法：首先根据频繁使用的路径决定每一 个索引结点所需的最大局部相似度k ，然后由a ( 0 ) 索引开始迭代，分裂每个索引结点，直到 它们的局部相似度达到最大局部相似度k 。( 2 ) 更新算法：对频繁使用的路径进行更新后， 现有索引中的结点的最大局部相似度也要进行相应的更新。 5 、m ( k ) 索引 d ( k ) 索引主要存在以下两个问题：( i ) 在更新算法中，对不相关结点的扩展集也进行分 裂操作。分裂后的索引大小比满足查询需要的最小索引的大小要大的多。( 2 ) 若结点v 的相 似度为k ，v 的父结点的相似度满足 k - 1 ，d ( k ) 索引更新算法对结点v 的扩展集进行分裂操作， 而实际上对于满足这类条件的结点v ，不要对其结点的扩展集进行再分裂操作。引起上述两 个问题的原因是d ( k ) 索引的k 值只能取一个值。 m ( k ) 1 5 索引的特点：( 1 ) 每个索引结点的相似度k 不相同。( 2 ) 为了避免对不相关结点 集进行分裂，m ( k ) 索引的更新算法除了使用路径表达式之外还使_ j 了频繁使用路径