互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

结构编码与簇集索引相结合的XML混合索引杨进才 张 遴 李国徽



  摘要:提出了一种结构编码与簇集索引相结合的XML混合索引结构(HiSC)。引入簇集索引结构,将XML节点分类,尽量多地保存XML数据的结构信息,缩小查询范围,提高了查询效率并能支持关键字的查询。实验表明此索引结构可以高效并准确地查询XML数据中的结构信息。
  关键词:可扩展标记语言; 索引结构; 簇集索引结构; 结构编码; 关键字查询
  中图分类号:TP311;132.4 文献标志码:A
  文章编号:1001-3695(2008)05-1415-04
  
  XML标准被广泛运用于Web数据交换[1],现有的查询语言如Xpath[2]、Xquery[3]都是通过路径表达式对XML文档进行查询。专家和学者针对提高路径表达式的查询效率进行了大量研究,并提出了多种XML索引结构,这些索引结构各有优点和适用范围。Dataguide[4]仅适用于简单的自根而下的路径表达式,对于复杂的表达式则无法解决。文献[5]提出两种相似的结构连接算法Tree-Merge与Stack-Tree;XISS[6]用元素、属性作为查询的基本单元,将复杂路径分解为简单路径,然后对各简单路径的处理结果进行连接。文献[7~9]运用了区间编码,通过区间编码可以有效地找到与某个节点相关的节点区间码,并运用B+树来优化索引结构。尽管对索引的结构和查询算法进行了优化,但只能减少查询中结构连接的次数,不能避免复杂的结构连接运算。DBXI[10]利用DTD的结构信息对XML文档及其遵循的DTD同时建立索引,结合了区间码的思想,减少了XML文档的遍历。Apex[11]是一种基于工作流的索引结构,运用数据挖掘的方法将常用的查询数据挖掘出来建立索引,当工作流改变时索引结构也会随之更新;HOPI[12]基于2-Hop包含的有向图在XML上建立面向连接的索引,提高了查询的空间和时间效率,并能很好地支持XLink,但查询算法过于复杂。结构编码[13]不同于其他的索引结构,需要先将查询拆分成若干子查询,然后将子查询的结果进行结构连接。结构编码通过对XML数据和查询同时编码,将对XML的查询转变为对查询编码序列的搜索,在一定程度上避免了复杂的结构连接。结构编码还支持包含通配符路径的查询。应该说,将结构编码用于XML文档的查询是一种新颖的索引方法,但还存在一些不足:a)没有按节点属性构建簇集索引,当查询某节点是否存在时需要遍历整个文档。b)其索引结构忽略了XML文档中的一些结构信息,查询结果与XML文档中相关部分不同。c)不支持对关键字的查询。本文将在结构编码的基础上结合簇集索引提出一种新的索引结构来弥补结构编码的不足。
  
  1XML文档结构及结构编码
  
  XML文档是由嵌套的元素结构组成,XML数据通常被描述成树结构,元素及其属性由DTD定义。图1(a)描述了一个交易文档的结构;(b)表示的是一份由(a)定义的交易XML文档树结构。在图1(b)中,V1~V8表示叶节点标志,即文档中元素的属性节点值和元素节点值,非叶节点的标志为元素的首字母。每个节点都加入了区间码(begin, end),用来标志XML文档树中节点的结构关系。节点间的祖先/后裔、双亲/孩子关系可以通过区间码进行判断。图1(b)中,节点S(2,70)与节点I(8, 45),(S.begin=2)<(I.begin=8),(S.end=70)>(I.end=45),由此可以判断出节点I为S的后裔节点。 XML文档中的每个节点与区间码是一一对应的,可以引入传统关系数据库成熟的技术如B+树。 ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017