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

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

XML数据流中祖先-后裔关系匹配算法

在祖先-后裔关系匹配算法中,多数都是首先利用XML解析器将XML文档解析分裂为元素(或属性) 列表进行存储,然后在这些分裂得到的元素(或属性) 列表之间进行祖先-后裔关系的结构连接.该文的算法SSD不需要事先将源XML文档分裂为元素(或属性) 列表进行存储,而是直接将源XML文档作为输入,采用SAX来产生XML数据流,然后基于XML数据流实现祖先-后裔关系匹配.通过分析可知,该算法适用面广,仅需要对源XML文档进行一次扫描,占用系统资源少,且具有很高的匹配效率.     

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

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

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

为有效实现XML文档查询,减少查询时结构连接的扫描代价,分析了基于归并思想的结构连接算法查询效率低的原因,充分利用XML数据的结构特点,提出了能够直接判断结点间结构关系的扩展Dewey编码,基于该编码的改进的Stack-Tree-Desc结构连接算法.应用扩展的Dewey编码,缩短了编码长度,降低了空间成本.改进的Stack-Tree-Desc算法引入二分查找快速跳过不需要参与连接的结点,减少了AList和DList列表中被扫描的结点数量,提高了查询效率.理论分析和实验结果表明了该编码方案以及结构连接算法的准确性和有效性.     

Native XML数据库的结构连接算法研究

Native XML数据库的快速查询,可以通过基于XML文档编码的结构连接算法实现。在对现有结构连接算法进行综述的前提下,提出一种新的Native XML数据库的结构连接算法——基于深度均匀划分的结构连接算法(DRIAM)。该算法不要求输入数据AList和DList有序或在其节点编码上建有索引,避免了排序和索引所增加的额外开销;不需要输入数据AList和Dlist全部加载到内存中,可以适应不同内存大小限制的情况,并且该算法时间复杂度非常低。     

基于模型映射方法实现XML与关系数据的相互转换

基于模型映射方法可以独立于XML文档的DTD或Schema,在关系型数据库中设计固定的关系模式用于存储XML文档。采用Dietz编码方法对XML文档中的元素进行编码,通过编码值对反应元素之间的祖先/后裔关系,并在关系表中存储元素的Dietz编码值,并依此作为依据设计算法将存储于关系数据库中的XML文档进行还原。     

一种高效的XML路径查询索引

XML文档的查询索引是当前研究的热点。提出一种高效的XML路径查询索引KDXI,首先对XML文档进行编码,然后建立结构索引并对结构索引进行编码。研究了基于KDXI索引结构的半结构连接算法和路径查询处理过程。通过KDXI索引机制,可以有效执行一般的路径查询语句,并避免冗余的结构连接操作。实验证明了KDXI索引机制的优越性。     

面向方面XML查询技术

提出一种有效的方法对XML文档进行描述,解决原有方法中改变XML文档结点时需要对XML文档结点进行重新编码,并改进结构连接查询效率.提出利用面向方面编程方式对XML文档进行定义.在XML文档定义中引入织入,并通过实现对XML Schema的扩充,使XML文档定义具有面向方面编程技术的功能,给出相关结构连接算法.方法避免了由于扩充XML文档而对结点重新编码,减少了修改结点信息的次数,提高文档的重用性.提供了不同织入文档情况下的实验结果,比较不同结构连接算法的性能,实验结果表明该文工作有意义.     

有效支持XML结构化连接的索引——CATI

结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接.     

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

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

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

基于聚簇的XML文档近似连接方法

XML文档近似连接操作是在两个XML文档集合中发现近似的XML文档,其在基于XML数据的信息集成、XML数据清洗等系统中有着广泛的应用.然而,目前XML文档近似连接操作的一个显著问题在于:当文档之间存在较大差异时,存在大量的重复计算,降低了处理效率.对于这个问题,提出了基于聚类的XML文档近似连接方法,基本思想是为每个XML文档建立一个索引,如果两个数据集中若干文档的索引较相似,可以把它们组成一簇,然后在每一簇中执行近似连接.而不在任何簇中的文档,则无需对其进行任何计算.实验结果表明,提出的方法在保证正确率的前提下具有高效性.     

基于关系数据库的XML分解存储方案

本文给出了一个基于关系数据库的XML分解存储方案。首先,通过对XML语法的分析,定义了XML树,XML树是一棵结构规则的树：所有的节点都具有相同的格式。通过XML树可以把结构不规则的XML文档映射成结构规则的XML树。其次,通过定义关系XSR,将XML树存储到关系数据库中去。该方案可以保证数据的完整性。在分解存储时,一个XML文档只需映射到一个关系表,而其它分解方案一般需要映射到多个关系表。该方案是一个通用方案,可以处理任意的XML文档。     

一种基于结构索引的XML模式匹配方法

XML文档采用了树型的数据模型,对其查询通常是用带有选择谓词的模式树在XML数据中进行匹配.因此,找出XML文档中所有符合模式树结构的元素集,是XML查询处理的核心操作.本文提出了结构索引JoinGuide,并在此基础上提出了一种新的XML模式匹配方法.它使用JoinGuide来对模式树进行预匹配,这样在XML文档上查询时可以利用索引上的匹配结果来忽略部分连接谓词和不必要的候选XML元素序列.本文还提出了三种具体算法来利用索引匹配结果进行进一步的查询.实验结果表明本文中的模式树匹配方法优于以往的匹配方法,并且索引所需的空间很小.     

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

提出了一种新的支持数据更新的XML编码方案CSSU（Coding Scheme of Supporting for Updating XML data）,它支持祖先后裔关系、父子关系和兄弟关系的表示,能够有效支持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.