偏序时态XML索引TempPartialIndex

时态数据管理是常规数据管理的深化和扩展,具有理论研究的意义与实践应用的价值.时态数据索引是时态数据管理的重要技术支撑,是其中的一个研究热点.首先,提出了一种时态数据结构,通过数据节点间的偏序关系,可将常规的二维时间区间的处理转化为基于偏序的时态等价类上的一维的处理,该数据结构可以快速有效地处理时态操作;其次,在该新型时态数据结构基础上研究了时态XML索引Temp Partial Index,其基本特征是将时态数据结构整合到非时态的XML索引中,即,将其整合到语义层之中,通过时态过滤和语义过滤掉大量节点之后,再进行结构连接;另外,着重讨论了基于Temp Partial Index"一次一集合"及其时态变量查询和增量式的动态更新机制.同时,仿真结果表明:Temp Partial Index能够有效地支持时态XML的各类查询及更新操作,技术上具有可行性和有效性.

XCluster:基于聚类支持查询的XML多文档压缩方法

XML已成为各种网络应用中数据存储和数据交换的标准.XML数据管理面临的最大困难在于结构与数据混合存储导致大量数据冗余,这极大地增加了XML数据存储、交换和处理的代价.对XML文档进行压缩可以在一定程度上解决这个问题.但现有XML压缩方法大都仅压缩单文档中的冗余信息.利用XML文档间的相似性,提出一种支持查询的多XML文档压缩存储方法XCluster.XCluster先利用XML有根有序标签树上改进的pq-gram近似距离对XML文档集进行层次聚类;然后合并每个聚类结果子集中文档的结构得到结构代表并进行字典编码压缩;同时合并不同文档内同一标签下的值内容,并根据其数据类型进行相应编码压缩.实验结果表明,在真实和生成的XML多文档数据集上,XCluster比XGrind和XQilla具有更好的压缩效果和查询效率.

对加密的XML数据查询算法的研究与实现

对于XML加密数据的查询,文献[1]提出了一种"有查询意识的解密"方法,它只解密与查询结果有关联的部分。改进了关于XML加密数据的查询处理方法,利用哈希表、链接表来构建用户密钥索引。在XML文档加密过程中,将XML加密数据与加密的XML索引存储在一起,以便解密后的索引能提供查询结果在XML加密数据中的位置。并提出新的方案,其主要内容包括XML索引设计、用户密钥索引设计、算法设计。实验结果表明,本文方法提高了查询的效率,无需解密无关的加密数据,有效地解决了用户密钥交换次数多和安全的问题。

基于结构化联接的多版本XML文档查询处理

结构连接是XML查询处理的核心操作,受到了研究界的关注。高效的算法是高效查询处理的关键。目前已经提出了许多结构连接的算法,但都不支持多版本的XML文档。文章对经典结构连接算法进行了扩充,使之支持多版本的XML文档。

基于DOM的XML数据库的索引技术研究

XML作为一种数据交换的国际标准 ,已经贯穿于Internet应用的各个领域之中 ,如何快速准确地存储和查询XML数据的数据库技术是一个重要的研究课题 XML索引技术对XML数据库查询处理起着至关重要的作用 提出了基于DOM的XML数据库的索引技术 (路径连接索引、值索引和引用索引 ) ,解决了传统的基于树的遍历的XML数据查询方法性能上的不足 ,并着重对处理含有谓词和引用关系等较复杂的查询路径的不同处理方法进行了对比和分析 还给出了索引空间利用率、查询性能和索引维护代价 3个方面的标准测试结果 。

有效的非完全结构XML查询

讨论了有意义的非完全结构XML查询(NFS)结果的定义,提出了一种易于扩展的基于模式和实体的有意义判断模型———PE模型;基于PE模型,设计了具体的等价模式和等价查询项判断方法,提出了PE索引和I2P倒排索引,设计了一种有效的NFS查询算法来处理有意义的判断以及路径查询和关键字查询.实验表明,文中方法的查询质量和效率要优于XSEarch系统和Timber系统.

对XML数据索引的回顾

随着Internet的迅速发展,XML已成为Internet网上数据表示与交换的事实标准,大量应用采纳了XML,例如Web Service中的数据表示和交换、MPEG7中定义的多媒体特征描述子等。日前,查询XML数据需要用XPath,由于查询语句的复杂性,很难找到一种通用的索引结构能有效支持任意查询。因此,在近十年的研究历程中,为了实现XML数据的快速查询,人们提出了大量索引结构。本文就是对已经提出的一些代表性的索引结构进行分类和总结,并指出其优缺点和所能支持的查询。

面向对象XML数据索引技术

提出了一种面向对象XML数据的索引模式路径仓,路径仓是紧凑地、准确地表示面向对象的XML数据的一棵树,是两级双向树:组级和元素级.在组级上,路径仓提供路径信息、类层次信息,类层次信息存储以索引类为根的类层次子树上特有的元素和属性的对象标识符,而继承的元素和属性的对象标识符存在较高的层次中,可以在查询早期阶段减少大量存储空间;在元素级,它保存从孩子元素到父亲元素的信息,快速存取元素的父亲,提高查询处理效率.不使用全局标志符而是用基于组的引用,可以按组区分不同类型的元素值聚簇相同类型元素值并且索引它们.

一种基于结构特征的XML数据查询方法

针对XML数据特有的树型结构模式,提出了一种将树型结构的XML数据和查询语句转化为特定格式的字符串,基于串匹配原理对结构复杂的XML数据进行查询的方法,避免了传统的基于路径的查询方式所必需的路径之间的连接(join)操作,从而提高查询效率。利用本文提出的编码方式,可以建立关于XML数据结构和数据内容合为一体的索引。实验显示,本文使用的针对XML数据查询的方法比传统的基于连接操作的数据查询方式高效,且本方法具有良好的扩展性。

XML数据库结构连接算法之分析

结构连接是XML查询处理的核心操作,受到了计算机研究界的高度关注。高效的算法是高效查询处理的关键,目前已经提出许多结构连接的算法。本文介绍了几种典型的算法,并分析了这几种算法的优缺点。

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段。文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index。RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符"*"和后代轴"//"的查询以及兄弟节点无序的模式树的查询。仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构。

基于结构标记树的XML可查询压缩方法

针对支持查询的XML数据压缩方法存在的路径和数据重复等问题,通过去除XML数据中的重复路径,简化XML数据结构,提出结构标记树的概念及其生成算法,设计一种基于结构标记树的可查询XML数据压缩方法SSTQC,对XML数据进行压缩和组织查询。SSTQC一次扫描XML文档,具有较好的的压缩性能和查询效率。

基于扩展区间编码的XML结构连接算法

结构连接的效率直接影响XML查询的性能。经典的Anc-Des-B+算法在判断双亲/孩子关系时跳过双亲节点的后裔(非孩子)节点的能力不强。为此,基于区间编码的思想提出一种改进的编码方法,把每个节点译码为六元组,并增加双亲节点的信息。给出的ZParent算法可以跳过孩子列表中所有不参与连接的元素节点,只需要扫描一次列表P和列表C,即可实现基于该编码的结构连接计算。实验结果表明,该方法具有较好的时间性能。

基于路径仓的面向对象XML查询处理技术

XML正在迅速成为Internet上数据表示和交换的标准,存储与查询XML数据变得日益重要,如何快速、准确地查询面向对象的XML数据成为当前研究的热点,索引技术是提高查询效率的有效方法。该文基于路径仓索引模式,提出了一种面向对象的XML数据的查询处理技术。

高效不确定XML复杂Twig查询处理算法

针对目前普通XML复杂Twig查询处理算法易造成大量空间和时间浪费,且不能完全适用于不确定XML的问题,提出一种基于P-文档模型的不确定XML复杂Twig查询处理算法Prob-BooleanTwig,处理包含AND,NOT和OR复杂谓词的查询模式。算法在扩展了EDewey编码的基础上,构建路径叶子节点索引,进行自底向上的查询模式匹配,避免了对查询模式的多次扫描。理论分析和实验结果表明,Prob-BooleanTwig算法具有高效性。

一种支持高效XML路径查询的自适应结构索引

提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index建立在F&B-Index的基础之上,其索引结构包括F&B-Index,Query-Table和Part-Table.Query-Table能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML元素节点,调整过程往往需要遍历整个文档.而AS-Index是基于F&B-Index节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index在查询和调整性能上优于现有的XML结构索引.同时,相比于现有的自适应结构索引,AS-Index针对大规模文档具有更加优良的可扩展性.

基于全文检索的XML存储查询系统

XML数据库已经成为数据库领域的重要成员,但是在商业数据库产品中它主要构建在关系数据库基础之上,这自然引入很多难题。针对XML的关系数据库存储,提出一种新的XML索引编码,解决了在关系数据库中集成全文检索技术和XML结构连接查询算法的问题,同时借助全文检索技术达到XML查询加速的效果。该方案应用于实际软件开发项目中,很好地解决了XML文档的关系数据库存储管理工作,并且具有很高的查询效率。

基于元表的XML可查询压缩方法

将XML的树形结构转换为元表这种数据结构,提出XML元表、结构统计表的概念及其生成算法,结合元表来保存XML文档的结构数据,设计一种基于元表的可查询XML压缩方法MTQC(MetaTable Queryable Com-pression),对XML数据进行压缩和查询.经实验证明,在元表、结构统计表上的查询处理过程更加简单,且MTQC具有较好的压缩性能和查询效率.

XML/GML非空间数据查询的结构连接算法

为利用Dewey前缀编码索引方案实现对XML/GML文档的编码并消除其缺点,提出一种扩展的Dewey编码方案——Ex-Dewey。在保留Dewey前缀编码优点的同时提出节点插入及删除对已有节点编码值串无影响的更新策略。针对Ex-Dewey编码方案提出一种在XML/GML非空间数据查询时快速确定候选节点间先辈-子孙、父-子关系的结构化连接算法——ED-XQ-SJ。给出算法思想、描述与验证。该算法无须访问实际存储的节点,算法复杂度较低且I/O开销减少。

移动对象XML数据库的存储与索引

如何对移动对象的XML数据记录进行快速的查找,关键在于合理地存储模型与索引结构。为了减少时空条件索引时的文件I/O操作,提出一个移动对象XML数据存储模型(时空XML存储模型),基于这个模型给出了通过一定时空条件对XML数据记录进行聚集的ATS(Append Track node to Spatial node)算法。针对3DR树的缺点与时态条件在移动对象索引中的重要性,提出了HSTR(Hashing-Spatio-Temporal-Rtree)与HC3DR(Hashing-Changing-3DRtree)两种复合索引结构,能够有效地支持涉及时空条件的查询。实验结果表明,时空XML存储模型与两种索引提高了查询效率。