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

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

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

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

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

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

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

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

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

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

一种新的XML文档更新计算

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

一种高效的动态XML文档树编码机制

针对现有XML编码机制时空效率不高、对XML文档动态更新支持不够等问题,结合素数和IBSL 2种编码机制,提出一种新的XML文档树编码机制——基于素数的二进制字符串编码机制。理论分析和实验均证明该编码机制具有较好的查询效率,能够高效地支持XML文档更新操作,大幅降低空间成本。     

一种支持动态XML文档上关键字查询的索引结构

在关键字查询领域,目前提出的大多数索引结构主要考虑的是静态的XML文档.当XML文档出现频繁更新时,这些索引结构可能面临着大范围的重新编码,从而增加了数据库索引维护的代价.为了能在XML文档动态更新的环境下保持其索引结构的稳定,提出了一种支持动态XML文档上关键字查询的索引结构DLSS( DDE Level Structure Summary).该索引结构采用了一种针对动态更新改进的Dewey编码,该编码只需在文档更新时对新的节点赋予相应的编码,而不需要调整原有的编码结构.实验证明,DLSS索引结构可以在XML文档频繁更新或者较少更新时都能保持索引结构的相对稳定,并能在其上实现较高的关键字查询效率.     

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

提出了一种新的支持XML文档更新的编码方法——DVLS(Dynamic Vector Labeling Scheme)。DVLS仅由3个向量组成,克服了传统前缀编码中编码长度随着XML文档树深度的增加而增长的缺陷,其主要思想是:利用向量的加法来支持XML节点数据的更新,并分别针对静态和动态XML文档提出优化方案,以提高查询效率。在向量序的基础上,通过与DDE编码的对比实验,验证了DVLS编码的高效性。     

高效查询的XML编码方案

在XML数据查询中,结构连接操作占用了大量时间。针对这个问题,提出一种高效查询的编码方案—LSEQ编码。它将节点路径信息进行分解,避免记录路径的重复信息,减小了编码长度;同时支持节点祖先后代关系,父子关系和兄弟关系的表示。LSEQ编码通过记录非叶节点的路径,在节点查询中避免了结构连接操作,提高了查询效率。实验表明LSEQ编码提高了空间利用率,在查询速度上具有出良好的性能。     

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文档更新环境下的区间编码方法——DCLS(dynamic containment labeling scheme).DCLS将基于整数的编码泛化到基于向量的编码,扩展了传统静态区间编码方法,有效避免了XML文档更新时的重新编码.不论文档更新与否,DCLS都显示了良好的性能:DCLS利用基于整数的静态区间编码方法进行初始编码,在文档不更新的环境下,具有较高的存储效率和查询性能;同时,DCLS将整数视为特殊向量,不仅能够支持文档更新,而且更新效率高;特别是倾斜插入时,DCLS可以避免编码位长的快速增加.实验结果表明,与已有的动态区间编码方法相比,DCLS具有更好的性能.     

XML数据更新编码机制——ITBI

编码技术是可扩展标记语言(XML)查询处理的基础,传统编码技术利用自然数进行编码,很难支持XML动态更新。提出了更新支持的编码方法——ITBI,该方法将整数映射到完全二叉树,利用二叉树的中序遍历定义整数新的序关系,通过新的序关系重排自然数序列将静态编码转化为动态编码。同时,基于ITBI前驱、后继、距离等定义,设计了最短位长动态编码分配算法,有效控制更新过程中编码位长的增加。最后通过实验验证了编码的有效性。     

一种基于编辑距离的XML查询方案

提出了一种新的XML查询方案，将内容查询置于结构查询之前，并在结构查询中提出M集合的概念，通过计算查询树的M集合和简化后的DTD的M集合之间的编辑距离，对XML文档进行排序，不仅减少了查询时间，而且在保证查全率的同时提高了查询的查准率。     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

Indexing and querying XML using extended Dewey labeling scheme

Finding all the occurrences of a tree pattern in an XML database is a core operation for efficient evaluation of XML queries. The Dewey labeling scheme is commonly used to label an XML document to facilitate XML query processing by recording information on the path of an element. In order to improve the efficiency of XML tree pattern matching, we introduce a novel labeling scheme, called extended Dewey, which effectively extends the existing Dewey labeling scheme to combine the types and identifiers of elements in a label, and to avoid the scan of labels for internal query nodes to accelerate query processing (in I/O cost). Based on extended Dewey, we propose a series of holistic XML tree pattern matching algorithms. We first present TJFast to answer an XML twig pattern query. To efficiently answer a generalized XML tree pattern, we then propose GTJFast, an optimization that exploits the non-output nodes. In addition, we propose TJFastTL and GTJFastTL based on the tag + level data partition scheme to further reduce I/O costs by level pruning. Finally, we report our comprehensive experimental results to show that our set of XML tree pattern matching algorithms are superior to existing approaches in terms of the number of elements scanned, the size of intermediate results and query performance.     

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.