支持XML插入更新的编码方法

对有序XML文档进行编码,可以不用访问XML数据文件就能够实现对XML数据的处理。目前提出的编码方案在支持查询XML数据方面取得了较好的效果,针对已有编码方案在插入更新过程中存在查询性能或者更新性能偏低等问题,提出了一种新的支持插入更新的编码方案——EDL,EDL对前缀编码进行了扩展,利用数值表达节点的初始顺序关系,利用二进制字符串(BS)来支持更新计算。EDL在未降低查询性能的前提下,完全避免了插入更新后对其他节点进行重新编码,高效实现了XML文档的插入更新计算。实验结果表明EDL优于同类型的支持更新的编码方案。     

一种新的XML文档更新计算

当对XML文档进行插入操作时面临调整编码问题,目前提出的很多编码方案不能同时很好地支持XPath查询和XML文档更新。在分析现有编码方案的基础上,提出了基于完全树的编码方案,该编码方案采用序号冗余和虚拟节点两种冗余方式,不仅支持XPath的查询,而且能有效降低因插入节点需要对XML文档进行二次编码率。实验结果表明,完全树以及相应编码有效提高了XML文档插入节点的效率。     

VEMBP:支持更新的XML树编码方法

对有序XML文档树进行编码,不需要访问XML原始文件就能够实现对XML数据的管理,提高了XML管理系统的效率。针对查询提出的编码方案具有很高的查询性能,但更新效率很低。为提高更新性能而设计的方案存在查询效率低或者编码空间大等问题。为了在提高更新XML文档效率的同时不对查询性能和编码空间产生负面影响,提出了一种新的编码方法VEMBP(Vector Encoding Method Based of Prime),该方法利用向量表示有序XML节点之间的顺序关系,采用素数表示有序XML文档节点之间的结构信息;并设计了一种算法来实现在没有牺牲查询性能的前提下完全避免更新过程中的二次编码和重新计算,降低了更新代价,同时编码空间也得到了控制。实验结果显示,VEMBP具有较好的查询和更新性能。     

基于节点位置信息的降低更新代价前缀编码方案研究

分析了现有的几种XML文档前缀编码[1-4]方法,研究了在XML文档树不同位置插入节点时的更新代价,提出了一种基于位置信息的前缀编码方案,对更新代价较大的节点预留较大的空间.设计了更新算法,在产生新插入节点的编码的同时,为今后插入节点也预留空间,且采用"借"空间算法,减小插入操作造成重新编码的数量.充分的试验结果证明,采用提出的编码方法,具有相对较小的平均编码长度和编码时间,查询速度很快,更重要的是能够有效降低更新操作引起的编码长度增加、重新编码节点数以及更新时间.     

一种支持更新的XML编码方法

通过对有序XML文档进行编码,在不需要访问XML原始数据文件的条件下实现对XML数据的高效处理。但是目前提出的支持插入更新的编码方案存在牺牲查询性能或者编码空间偏大等问题。提出了一种基于素数的新的编码方案FOP（Float-Order based-on Prime）,FOP在没有降低查询性能的前提下,实现了XML文档的插入更新计算,并且编码空间得到了控制。实验结果表明FOP优于同类型的编码方案。     

一种新的基于区域的动态XML编码方案

在区间编码和前缀编码的基础上,提出了一种区间编码的改进的编码方案RSD（region-string-dinary）,采用二进制编码策略,可顺序友好的插入位串;提出了新的位串插入算法,可生成有序位串,且不影响已经存在位串的顺序。描述了R S D中节点间结构关系的判定方法。该二进制编码方案和位串插入算法是有效进行查询处理和避免更新时重新编码的基础。实验表明R S D使得更新时完全可避免重新编码,显示出合理的查询处理性能。     

基于分治策略的XML文档更新计算

XML文档更新是XML数据管理的重要功能,对XML文档进行插入更新操作时面临编码调整问题,目前大部分编码方案并不能很好支持文档更新。在分析现有编码方案基础上,提出了OMPN(order, maxOrder, parentOrder, nextOrder)编码方案,采用分治策略和迟后更新方法,在插入节点过程中不需要调整编码,在计算资源空闲时,只需调整部分编码就可以完成对XML文档的更新。实验结果表明,基于分治策略和迟后更新方法提高了更新XML文档的性能。     

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

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

基于扩展Dewey编码的XML文档更新计算

针对在进行XML文档插入、删除等更新时因需要频繁调整相应的子树编码而导致更新低效问题.分析了低效的原因,提出了一种扩展的Dewey编码方案.该编码方案对Dewey编码的连续性进行扩展,使兄弟节点之间的编码不再连续,为插入新节点准备冗余空间.在此基础上,设计了支持该扩展编码方案的XML文档节点插入算法和分裂算法.实验结果表明,提出的扩展Dewey编码方案有效地实现了XML文档的更新计算.     

BSC：一种高效的动态XML树编码方案

确定一篇XML文档中任意两个节点之间是否存在某种结构关系,是XML查询处理过程的一个重要组成部分.XML树编码方案为每个节点分配唯一编号,仅通过比较节点编号而不必访问原XML文档,就可以快速有效地确定节点间的结构关系.随着XML应用不断普及,能否高效地支持更新操作,已成为XML树编码方案研究的一个重要课题.本文基于二进制小数的特性,提出了一种新的XML树编码方案-BSC,它可以完全高效地支持XML更新操作而不需要重新编码.实验结果证明,与已有的动态编码方案相比,BSC编码无论在静态编码方面还是在动态更新方面都具有很好的性能.     

Dynamic interval-based labeling scheme for efficient XML query and update processing

XML data can be represented by a tree or graph structure and XML query processing requires the information of structural relationships among nodes. The basic structural relationships are parent-child and ancestor-descendant, and finding all occurrences of these basic structural relationships in an XML data is clearly a core operation in XML query processing. Several node labeling schemes have been suggested to support the determination of ancestor-descendant or parent-child structural relationships simply by comparing the labels of nodes. However, the previous node labeling schemes have some disadvantages, such as a large number of nodes that need to be relabeled in the case of an insertion of XML data, huge space requirements for node labels, and inefficient processing of structural joins. In this paper, we propose the nested tree structure that eliminates the disadvantages and takes advantage of the previous node labeling schemes. The nested tree structure makes it possible to use the dynamic interval-based labeling scheme, which supports XML data updates with almost no node relabeling as well as efficient structural join processing. Experimental results show that our approach is efficient in handling updates with the interval-based labeling scheme and also significantly improves the performance of the structural join processing compared with recent methods.     

Efficient updates in dynamic XML data: from binary string to quaternary string

XML query processing based on labeling schemes has been thoroughly studied in the past several years. Recently efficient processing of updates in dynamic XML data has gained more attention. However, all the existing techniques have high update cost, they cannot completely avoid re-labeling in XML updates, and they will increase the label size which will influence the query performance. Thus, in this paper we propose a novel Compact Dynamic Binary String (CDBS) encoding to efficiently process updates. CDBS has two important properties which form the foundations of this paper: (1) CDBS supports that CDBS codes can be inserted between any two consecutive CDBS codes with orders kept and without re-encoding the existing codes; (2) CDBS is orthogonal to specific labeling schemes; thus it can be applied broadly to different labeling schemes or other applications to efficiently process updates. Moreover, because CDBS will encounter the overflow problem, we improve CDBS to Compact Dynamic Quaternary String (CDQS) encoding which can completely avoid re-labeling in XML leaf node updates no matter what the labeling schemes are. Meanwhile, we also discuss how to efficiently process internal node updates. We report the experimental results to show that our CDBS and CDQS are superior to previous approaches to process both leaf node and internal node updates.     

Efficiently supporting order in XML query processing

XML is an ordered data model and XQuery expressions return results that have a well-defined order. However, little work on how order is supported in XML query processing has been done to date. In this paper we study the issues related to handling order in the XML context, namely challenges imposed by the XML data model, the variety of order requirements of the XQuery language, and the need to maintain order in the presence of updates to the XML data. We propose an efficient solution that addresses all these issues. Our solution is based on a key encoding for XML nodes that serves as node identity and at the same time encodes order. We design rules for encoding order of processed XML nodes based on the XML algebraic query execution model and the node key encoding. These rules do not require any actual sorting for intermediate results during execution. Our approach enables efficient order-sensitive incremental view maintenance as it makes most XML algebra operators distributive with respect to bag union. We prove the correctness of our order encoding approach. Our approach is implemented and integrated with Rainbow, an XML data management system developed at WPI. We have tested the efficiency of our approach using queries that have different order requirements. We have also measured the relative cost of different components related to our order solution in different types of queries. In general the overhead of maintaining order in our approach is very small relative to the query processing time.     

An encoding scheme based on fractional number for querying and updating XML data

In order to facilitate the XML query processing, several labeling schemes have been proposed to directly determine the structural relationships between two arbitrary XML nodes without accessing the original XML documents. However, the existing XML labeling schemes have to re-label the pre-existing nodes or re-calculate the label values when a new node is inserted into the XML document during an update process. In this paper, we devise a novel encoding scheme based on the fractional number to encode the labels of the XML nodes. Moreover, we propose a mapping method to convert our proposed fractional number based encoding scheme to bit string based encoding scheme with the intention to minimize the label size and save the storage space. By applying our proposed bit string encoding scheme to the range-based labeling scheme and the prefix labeling scheme, the process of re-labeling the pre-existing nodes can be avoided when nodes are inserted as leaf nodes and sibling nodes without affecting the order of XML nodes. In addition, we propose an algorithm to control the increment of label size when new nodes are inserted frequently at a fix place of an XML tree. Experimental results show that our proposed bit string encoding scheme provides efficient support to the process of XML updating without sacrificing the query performance when it is applied to the range-based labeling schemes.     

XML文档存取控制研究

提出了一种基于授权树的XML存取控制标记算法，通过①避免在每个XML结点上进行授权匹配；②避免在每个结点上进行授权冲突解决；③避免标记每个结点，有效地改善了处理性能，另外，提出了一种灵活的、用户可配置的授权冲突解决模式，并且将这种解决模式自然地集成到授权树算法之中。     

A Dynamic Labeling Scheme for XML Document

Efficient evaluation of XML queries requires the determination of whether a relationship exists between two dements, A number of labeling schemes have been designed to meet the need. However, most of them have poor updating performance. In this paper, a new dynamic region-based labeling scheme is proposed which uses real numbers instead of integers to represent the region. Moreover, the scheme can adjust the codes of some nodes in some parts of the document tree according to the condition of updates. Our analysis shows this new labeling scheme provides efficient support for updates.     

SXBP：基于Pri—order编码的XML文档存储方法

随着XML技术的发展，如何利用现有的数据库技术存储和查询XML文档已成为XML数据管理领域研究的热点问题。本文介绍了一种新的文档编码方法，以及基于这种编码方式提出了一种新的XML文档存储方法。方法按照文档中结点类型将XML文档树型结构分解为结点，分别存储到对应的关系表中，这种方法能够将任意结构的文档存储到一个固定的关系模式中。同时为了便于实现数据的查询，将文档中出现的简单路径模式也存储为一个表。这种新的文档存储方法能够有效地支持文档的查询操作，并能根据结点的编码信息实现原XML文档的正确恢复。最后，对本文提出的存储方法和恢复算法进行了实验验证。     

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

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

一种新的基于区域的动态编码方案

为了提高查询效率，许多XML文档编码方案相继被提出。目前大部分编码方案并不能很好地支持文档更新。在分析比较现有编码方案的基础上，提出了一种新的动态编码方案(DNS)。该方案用实数表示XML文档树中的节点编码，能够利用连续数值间的区域为新插入的节点或子树编码，并能够根据文档的更新情况动态调整部分节点的编码。