随着用于描述数据的XML声望的迅速扩大,对符合树状形结构数据模型的处理过程有很大的兴趣,高效的找到XML数据库的分支模型是XML查询过程的主要关心的,最近整体的分支联合方式已经被作为一种有效的匹配分支模型方式,因为这种方法能有效的控制中间结果的数量,但是我们认识到关于整体的分支查询匹配存在工作仅仅考虑了无序分支查询。但是XPath定义了4种有序的轴线:following-sibling,preceding-sibling,following,preceding,例如:XPath://book/text/following-sibling::chapter是一个有序查询,这种有序查询发现所有章在数据设置中,这个数据设置是后继兄弟的文章,应该是一本小孩的书。
我们呼唤一种查询,这种是有序的匹配元素作为一种有序分支查询,在另一方面,我们指出一种分支查询,这种分支查询并不考虑有序匹配的元素而是一种无序查询,在这篇文章中,我们研究了怎样有效的去评估一种有序的分支查询。
处理一种有序的分支查询,天真的,我们能用已经存在的算法去输出中间路径为每个单独根—叶查询路径的解决方法,并且融入路径解决方法以便最终解决方法被确定去解决有序谓词的查询,虽然存在算法是适用的,那么这样一种发送—过程方法有一个严重的不利地位,很多中间结果不能控制最后的结果。
为了最近成功在有效过程无序的分支查询整体性的动机,我们在这篇文章中为有序分支查询提出一种新颖整体算法,叫OrderedTJ,这篇文章的贡献可以被概述为如下:
1、 我们揭露了一种新的整体的有序分支联合算法,名字叫OrderedTJ,是基于有序孩子扩展的新概念。由于OCE一种元素对最终结果的控制仅仅由于它孩子的顺序和对应查询节点的顺序相一致,因此为有序分支的有效整体算法被影响。
2、 如果我们认为在枝节点和它们孩子之间作为有枝的边,并且指出这个有枝的边连接的第n个枝边,我们经分析证明当有序分支仅仅含有祖先—后裔关系从第2个枝边,OrderedTJ是最佳的在所有读入全部的连续算法的I/O,另一方面,最佳OrderedTJ允许父—子关系的存在在无枝边和第一个枝边。
3、 我们实验性的结果展示我们整体性分支算法为有序分支模型的有效,可测量性和效率。
这篇文章的剩余物被组织为如下:第2部分提出连接工作,新颖有序的分支连接算法在第3部分被描述,第4部分是专注于我们实验的结果,在第5部分我们这篇文章收尾以结论和未来。
1. 连接工作
随着XML数据声望的扩大,为XML查询过程和最佳性已经吸引了很多研究的兴趣,有很丰富的文献关于匹配分支查询的有效性,下面我们描述这些文献的观点,这种目前的工作仅仅处理无序分支查询。
Zhang et al.建议一种多谓词混合连接算法基于XML元素的标签,以后的工作被Al-Khalifa et al给了一叠基于二进制结构的联合算法,不同于二进制结构联合方法,Bruno et al提议一种整体的分之联合算法,叫做TwigStack,为了避免产生中间大量结果。但是在TwigStack最佳查询类是非常小的,当一个分支查询包含任何父—子边,无用中间结果的大小可以是非常大的,Lu et al建议一种新的算法叫TwigStackList,他们用列表数据结构去存储有限的元素为了识别大量最佳查询类,TwigStackList是I/O最佳查询仅仅随着在所有的枝边的祖先—后裔关系,最近Jiang et al随着OR谓词研究有效的评估分支查询的问题,Chen et al为整体分之联合研究在不同数据分个策略和最佳查询类之间的关系,Lu et al为有效过程XML分支模型提出一种新的标签计划叫extended Dewey。