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

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

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

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

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

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

一种新的XML文档更新计算

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

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

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

基于扩展字节进位的动态XML树编码方案

为提高可扩展标记语言(XML)文档树编码的效率、支持XML数据动态更新,提出一种基于扩展字节进位的动态XML树编码方案(EBCL)。结合前缀编码和加法运算的思想,采用分段与分节的方式组成编码,给出静态前缀编码与动态前缀编码的算法流程。对编码大小与静态动态性能进行测试,实验结果表明,EBCL编码性能较优,能高效地支持XML文档的动态更新。     

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

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

一种支持动态插入的XML文档树编码IFED

XML文档树编码用来标识节点在文档树中的位置,XML文档查询算法通常通过编码来判断节点的祖先后代和兄弟关系,编码的好坏对查询效率影响很大.目前提出的编码主要分为两大类:区间编码和前缀编码,最近提出的扩展的前缀编码-Extended Dewey,由于通过单个节点的编码能够得到节点对应的路径,所以它支持有效的查询,但不支持动态插入.提出了一种新的XML文档树编码-IFED,它由Extended Dewey编码改进而来,既支持高效地查询,又支持动态插入.     

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

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

一种支持XML文档更新的编码方案

目前现有的前缀编码、区间编码等编码方案均不能很好地支持XML文档的更新计算。为此,提出一种新的前缀编码方案TDE。将实数映射为二维元组,利用任意2个实数间存在无限个实数的特点,对XML文档进行插入节点操作而无需对其他节点进行二次编码,并采用压缩存储减小编码的存储空间。实验结果表明,该方案能有效支持XML文档的更新计算。     

SLS: A numbering scheme for large XML documents

In view of the efficiency requirements for query and update processing in XML databases, implementation of the robust node labeling (numbering) scheme becomes an increasingly important research issue. In order to process XML queries efficiently, it is necessary to detect the ancestor-descendant relationship between the nodes and restore the sequence order of nodes in the document. To solve this problem, the technique of labeling the document nodes is used. As a result, the so-called numbering scheme is created. The nodes of the documents are labeled with certain unique identifiers. Comparing these identifiers, one can restore the sequence order of the nodes and to establish the hierarchical relationships. In this paper, we give a survey of the most efficient numbering schemes and introduce a numbering scheme proposed by the authors and employed in the Sedna DBMS [1].     

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.     

优化索引XML数据研究

介绍了文档树中嵌入编码机制的思想和扩展编码方法，提出了采用改进的扩展编码方式来对XML文档进行编码，并使用改进的B 树构造算法构建索引树，以期提高存储空间利用率并减少B 树节点分裂次数；最后，在理论和实验的基础上分析了数据查询的执行效率。     

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.     

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查询算法

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

基于二分法的XML结构连接

在XML数据的查询处理过程中，基于区域划分的连接算法在处理XML数据无序和不存在索引时，是一个效率较高的算法。该文利用区域编码的特点对输入集合进行穷尽的递归划分，在划分的代价下，逐步定位祖先-后代的结构关系。使用二分法进行划分后，再完成结构连接，提高了结构连接的效率，实验表明该算法在XML数据的查询处理上是一个有效的方法。     

基于扩展编码的在线XML文档加载机制

Webservices应用中存在大量在线XML文档处理的需求，利用现行的XML数据处理方法来处理上述在线文档是一项可行方案，在线文档的加载问题应运而生；目前对XML数据的存储和查询都是基于对XML文档树的某种编码方法，使用扩展编码方法以提高文档更新性能；如何基于扩展编码方法完成对在线文档加载的研究目前还比较少．提出一种新的扩展编码方法，在此编码的基础上，提出一种适合在线XML文档的加载方法，通过统计同模式的XML文档特征和更新特征，一遍解析文档完成扩展编码和加载；实验结果表明，加载效率和更新性能较好．