Native XML数据库的文档编码机制研究

Native XML数据库快速查询的实现,可以采用基于XML文档编码的结构连接算法。而结构连接算法的实现需要对XML文档进行编码,以便于快速判断XML文档树结点之间的祖先后裔关系。在对现有编码机制进行综述的前提下,提出一种新的XML文档编码机制——前缀整除编码（PDIV）机制。该机制编码形式简单,只需要一个正整数即可充分表示结点在XML文档树中的位置信息;可以实现祖先后裔关系的快速查询;支持XML文档的更新操作;编码长度较短,编码长度约为o（ln（n））。     

一种新的高效XML树编码方案

在深入分析现有XML编码方案基础上,提出了一种新的编码方案—PSB,该方案能够快速准确地判断出XML文档结构树中任意两个结点之间的父子、祖先-后代以及兄弟关系。由于采用素数和序列编码,可有效支持XML文档更新,降低XML文档的二次编码率。实验表明PSB是一种高效的动态编码方法。     

一种支持动态 XML 文档的存储模式设计与应用

针对XRel模式无法有效支持动态XML文档存储的问题,在区间编码的基础上,引入向量方法提出一种支持XML文档动态更新的编码方案——NewDietz,设计可以存储NewDietz编码元素的关系模式,并给出新元素在关系模式下的更新方法。新模式既保证新元素的有效存储,又兼顾动态XML文档从该模式中重组需要对元素进行祖先-后裔判断的问题。为验证新模式的实际应用效果,开发一个水利空间数据存储与展示模块,并对空间数据分别采用2种存储模式进行验证。对比结果表明,新模式明显提升XML文档在关系数据库中的存储效率,并有效支持XML文档的动态更新,为基于XML的水利业务数据在关系数据库中的高效存储提供一种可能。     

一种基于二叉树的Native XML数据库文档编码机制

在对于现有编码机制进行综述的前提下,提出一种新的XML文档编码机制,该编码机制基于完全二叉树的结构顺序编码。在该XML文档编码机制下,判断节点之间祖先-后裔关系算法的时间复杂度仅为O(log n),完全支持更新,并且编码长度较短。     

支持数据更新的压缩编码研究

提出一种支持数据更新的XML压缩编码CXSU（Compact XML storage for Supporting Update processing）。CXSU编码将节点路径信息进行分解,避免了记录重复信息,同时支持节点祖先后代关系,父子关系和兄弟关系的表示。实验表明CXSU编码能节省存储空间,有效地支持XML数据动态更新。     

一种支持数据更新的前缀编码方案

目前大部分前缀编码方案都不能很好的支持XML文档的数据更新.提出的前缀编码方案不仅能高效地支持结构查询,快速准确的判断XML文档结构树中任意两个结点之间的父子、先后代以及兄弟关系,而且对插入的结点采用新的编码规则,避免了更新操作带来的编码调整问题,能有效支持XML文档更新.     

支持数据更新的XML编码方案研究

提出了一种新的支持数据更新的XML编码方案CSSU（Coding Scheme of Supporting for Updating XML data）,它支持祖先后裔关系、父子关系和兄弟关系的表示,能够有效支持XML文档的动态更新。     

一种分数前缀XML编码方案

针对XML数据的更新与查询问题,提出一种分数前缀编码方案(FPES)。将分数引入LSDX前缀编码中,在2个分数间可插入无穷多个分数,支持XML节点数据的无限更新,并可表示祖先后裔关系、父子关系和兄弟关系,避免二次编码。实验结果表明,FPES与LSDX相比,查询效率较高;与分数编码相比,编码时间与插入节点的时间较少。     

左儿子右兄弟链式相关的XML动态编码方案

针对可扩展标记语言(XML)数据的查询与更新问题,提出一种基于左儿子右兄弟节点链式关联的XML动态编码方案。通过左儿子右兄弟节点的链式相关信息,仅需在局部做简单的若干改动,就可实现XML数据的更新,并能方便快速地实现祖先后裔关系、父子关系和兄弟关系等各种轴操作。研究结果表明,该编码方案不仅能高效地支持结构查询,而且编码时间与插入节点的时间也较少,可快速准确地判断XML文档结构树中任意两节点之间的关系,从而避免更新操作带来的编码大量调整问题,且支持XML文档的查询与更新。     

一种支持更新的有序XML文档编码方法

摘  要：在XML查询中,为了快速判断节点之间祖先后裔关系和双亲孩子关系,提出了一些编码方案,然而,当对顺序敏感的有序XML文档进行插入更新操作的时候,现有的编码方案必须重新对存在的节点进行编码或者重新计算节点编码的值,导致了很高的更新代价。在路径编码方法的基础上,提出了一种新的编码方案BSEPS（Binary String Encoding based on Path Scheme）,该方案支持在不重新编码或者重新计算的情况下完成顺序敏感的插入更新操作。实验结果表明,BSEPS编码能有效处理顺序敏感查询和叶节点/子树更新。     

Dynamically Updating XML Data: Numbering Scheme Revisited

Almost all existing approaches use certain numbering scheme to encode XML elements to facilitate query processing when XML data is stored in databases. For example, under the most popular region-based numbering scheme, the starting and ending positions of an element in a document are used as the code to identify the element so that the ancestor/descendant relationship between two elements can be determined by merely examining their codes. While such numbering scheme can greatly improve query performance, renumbering large amount of elements caused by updates becomes a performance bottleneck if XML documents are frequently updated. Unfortunately, no satisfactory work has been reported for efficient update of XML data. In this paper, we first formalize the XML data update problem by defining the basic operators to support most XML update queries. We then present a new numbering scheme that not only requires minimal code-length in comparison with existing numbering schema but also improves update performance when XML data is frequently updated at arbitrary positions. The fundamental difference between our new scheme and existing ones is that, instead of maintaining the explicit codes for elements, we only store the necessary information and generate the codes when they are needed in query processing. In addition to present the basic scheme, we also discuss some optimization techniques to further reduce the update cost. Results of a comprehensive performance study are provided to show the advantages of the new scheme.     

一种有效的XML数据库的小枝模式匹配算法

目前,XML文档查询是研究的热点,其中小枝模式匹配方法是重要的研究方向,但是大多数基于这种思想的算法只能处理包含祖先／后代关系的查询。为此,提出了一种新的小枝模式匹配算法——TwigStackPC,它能够有效地处理包含祖先／后代和父／子关系的查询。     

一种具有多模态索引结构的XML查询算法

将编码方案、路径索引和名字外延思想相结合,提出一种针对XML数据检索的多模态索引结构.它既可支持结构连接计算,用以判断任意结点之间的子孙后代关系,也可支持基于名字外延的路径连接算法,用以判断任意结点之间的父子关系,同时可支持包含拥有关系的小枝查询;进而给出基于该结构的外延连接算法,使得对于长度为n的Xpath绝对路径查询,最多只需n/2-1次外延连接.实验结果表明,本文提出的索引结构可有效提高查询处理性能.     

基于复杂模式索引的XML查询优化*

分析了XML模式与XML文档之间的关系以及XML查询的特点,提出了一种基于复杂模式索引的XML查询优化方法.该方法对XML模式中的节点建立索引,查询时考虑XML模式中带有环的情况.首先对查询树进行去除重复元素的预处理,并将查询树分解成主路径和分支路径;然后利用索引查找潜在目标节点的XML模式编号;最后在XML文档中对对应节点进行筛选,找到目标节点.该方法可以减少连接操作的次数,提高查询操作的效率,能处理较复杂的XML模式.     

一种新的XML数据库的索引机制

XML文档的路径查询通常是节点间关系的判断,其中最主要的是祖先、子孙关系的判断。该文通过借鉴R树的构造特点提出了一种新的基于R树的XML数据库的索引机制,解决了快速判断XML文档中节点间祖先、子孙关系的问题。     

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

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

基于局部路径加锁的XML并发控制协议

传统XML数据库并发控制协议大多采用基于XML文档树的路径加锁方式,并发度不高。针对该问题,提出一种基于局部路径加锁模型的XML数据库并发控制协议。该协议基于XML的节点编码,利用查询函数对目标节点的祖先后裔加锁情况进行快速判断,并根据操作类型对目标节点或者其父节点进行加锁,从而减少对锁的频繁请求,提高事务并发度以及实现大规模XML数据的有效管理。     

基于扩展前缀编码的左孩子右兄弟结构连接算法

为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好.     

CSBTT:一种基于二叉树遍历的XML文档编码模式

XML文档数据编码模式是XML文档查询处理的基础, 好的文档编码模式有利于提高文档的查询效率. 为了解决XML数据查询效率低、支持动态更新等问题. 本文在二叉树遍历的编码基础上, 引入二叉树的三叉链表存储结构对XML文档结点进行编码. 该编码利用自然数作为编码序号, 因此编码长度较短; 引入结点双亲指针, 方便结点之间结构关系的判定, 结点采用三叉树链式存储, 方便文档的更新操作.