共查询到19条相似文献,搜索用时 828 毫秒
1.
2.
结构连接的效率直接影响XML查询的性能。经典的Anc-Des-B+算法在判断双亲/孩子关系时跳过双亲节点的后裔(非孩子)节点的能力不强。为此,基于区间编码的思想提出一种改进的编码方法,把每个节点译码为六元组,并增加双亲节点的信息。给出的ZParent算法可以跳过孩子列表中所有不参与连接的元素节点,只需要扫描一次列表P和列表C,即可实现基于该编码的结构连接计算。实验结果表明,该方法具有较好的时间性能。 相似文献
3.
连接操作是最昂贵且常用的数据库操作.在传统数据库系统中,主要的连接操作是等值连接操作,因此,传统的并行连接算法主要集中于并行等值连接操作.另外,随着XML在Web应用中变得越来越重要,XML已经成为Internet上一种新的数据交换标准.对XML数据的连接操作不同于传统数据库中的等值连接操作,它属于结构连接操作.以前适合等值连接操作的并行连接算法并不能有效地解决结构连接问题.因此,第1次提出了并行结构连接问题,并且通过应用直方图的思想于并行连接中,从而提出两种基本的并行XML结构连接算法、等高直方图连接算法和等宽直方图连接算法.实验表明这两种算法具有较好的性能. 相似文献
4.
首先给出了XML文档树、元素外延和名字路径等的形式化定义.接着,将编码方案、路径索引和名字外延的思想相结合,提出了一种改进的XML数据的索引结构(类型索引集、名字索引集和外延索引),解决了基于传统索引技术的XML数据查询方法性能上的不足,它既可以有效地支持结构连接的计算以快速地判断任意结点之间的子孙后代关系,也可以有效地支持基于名字外延的路径连接算法以快速地判断任意结点之间的父子关系,然后还可以快速地支持对包含拥有关系的小枝查询;进而给出了基于该索引结构的外延连接算法,并着重对其处理含有父子关系和拥有关系等较复杂的XPath查询路径的不同处理过程进行了对比和分析,使得对于一条长度为n的XPath绝对路径查询,最多只需要n/z-1次外延连接,且能够根据双亲结构信息等利用外延索引尽可能跳过不需要参与连接的结点,实验结果表明,提出的新的索引结构可以有效地提高查询处理的性能. 相似文献
5.
结构连接作为XML查询的重要部分,对查询性能来说起着非常重要的作用.目前有几种结构连接算法已经被提出,例如Stack-Tree、XR-tree.这些算法主要集中在节点之间关系的确定上.与之不同,作者从分片的角度去解决结构连接问题,首先把节点间的关系引申到分片之间的关系,从而得出各分片之间的一些性质,再利用分片间的性质来提高结构连接操作的性能.文中提出了一种基于分片的结构连接算法和两种优化方法,实验表明该算法在性能上要优于Stack-Tree算法和XR-tree算法.设计了一个简单而又高效的索引结构来存储分片结果,实验结果表明该索引结构的维护代价要小于XR-tree的维护代价. 相似文献
6.
为有效实现XML文档查询,减少查询时结构连接的扫描代价,分析了基于归并思想的结构连接算法查询效率低的原因,充分利用XML数据的结构特点,提出了能够直接判断结点间结构关系的扩展Dewey编码,基于该编码的改进的Stack-Tree-Desc结构连接算法.应用扩展的Dewey编码,缩短了编码长度,降低了空间成本.改进的Stack-Tree-Desc算法引入二分查找快速跳过不需要参与连接的结点,减少了AList和DList列表中被扫描的结点数量,提高了查询效率.理论分析和实验结果表明了该编码方案以及结构连接算法的准确性和有效性. 相似文献
7.
主要讨论如何突破版本恢复的限制直接对任意版本的XMI、文件进行复杂的结构查询,围绕这个主题,首先介绍了目前XML文档版本管理的一般办法,然后在多版本XML文档的编码方式的基础上提出并实现了一种新的索引机制,进而将结构化连接的查询方法引入XML版本管理的领域,改进了3个经典的结构连接算法,这些算法均能在不恢复版本的前提下直接进行任意版本的结构查询。实验分析比较了它们的查询效能并证明了基于索引的算法能最大程度地避免查询中的冗余。 相似文献
8.
XPath的轴连接查询技术研究 总被引:3,自引:0,他引:3
XML查询处理比较流行的是解决祖先-后代、父亲-儿子关系的“结构连接”,其本身研究的是XPath中/和//轴的查询,不能支持XPath各种轴的查询.故本文扩展了结构连接的含义,进一步提出轴连接查询的定义,同时,基于可支持XPath定位轴的RaP编码,设计了两种轴连接算法:RaPMerge和RaPOneJoin.并通过Shakespeare和XMark两个数据集对两种算法进行了对比测试,表明了RaPOneJoin的查询性能在XPath某些轴的查询上同RaPMerge相比有很大的性能优势. 相似文献
9.
为了进一步提高eXist数据库的查询效率,针对数据库现有的数据存储特点和查询策略,提出一种快速定位的结构连接算法FL-Stack。算法采用栈缓存已遍历过的但仍可能与尚未遍历的后代结点匹配的祖先结点,并对能预先判断不可能满足结构连接匹配的祖先或后代结点,提出相应方法实现快速定位,以批量跳过这类结点。与现有算法必须逐个扫描祖先后代结点序列相比,这种快速定位的结构连接算法避免了逐个扫描带来的多次重复无意义的比较,可大大提高结构连接效率。 相似文献
10.
11.
有效的支持结构连接是实现数据库系统XML文件查询的关键。结构连接是用来查找所有满足基本的结构关系的元素对,即指定XML树型结构文件元素对的关系(父亲-孩子和祖先-子孙的关系)。文中在分析常见的XMLQuery模式匹配算法(Stack-Tree连接算法)的基础上,提出一种改进的Stack-Tree连接算法将Stack-Tree-Desc算法和Stack-Tree-Anc算法统一;并且采用动态分配存储空间方法,比Stack-Tree-Anc大大节省了存储空间。最后给出了改进的Stack-Tree连接算法分析和试验结果。 相似文献
12.
Cheng Luo Zhewei Jiang Wen-Chi Hou Feng Yan Qiang Zhu 《Knowledge and Information Systems》2008,16(1):97-127
XML structural joins, which evaluate the containment (ancestor-descendant) relationships between XML elements, are important
operations of XML query processing. Estimating structural join size accurately and quickly is crucial to the success of XML
query plan selection and the query optimization. XML structural joins are essentially complex θ-joins, which render well-known
estimation techniques for relational equijoins, such as discrete cosine transform, wavelet transform, and sketch, not applicable.
In this paper, we model structural joins from a relational point of view and convert the complex θ-joins to equijoins so that
those well-known estimation techniques become applicable to structural join size estimation. Theoretical analyses and extensive
experiments have been performed on these estimation methods. It is shown that discrete cosine transform requires the least
memory and yields the best estimates among the three techniques. Compared with state-of-the-art method IM-DA-Est, discrete
cosine transform is much faster, requires less memory, and yields comparable estimates. 相似文献
13.
在使用"不完全结构的约束查询(PSTP查询)"从XML文档中获取信息时,用户可以根据自身对XML文档结构的熟悉程度,在查询表达式中灵活地嵌入结构约束条件,从而满足完全不了解、完全了解及了解部分结构信息的各种用户的查询需求。提出一种基于扩展Dewey编码的查询处理算法,可以在仅扫描一遍元素的情况下,处理任意形式的PSTP查询。不同数据集上的实验结果表明,EDPS算法在处理twig查询、不包含"*"结点的PSTP查询及包含"*"结点的PSTP查询时,综合性能明显优于已有方法。 相似文献
14.
15.
16.
As a large number of corpuses are represented, stored and published in XML format, how to find useful information from XML databases has become an increasingly important issue. Keyword search enables web users to easily access XML data without the need to learn a structured query language or to study complex data schemas. Most existing indexing strategies for XML keyword search are based upon Dewey encoding. In this paper, we proposed a new encoding method called Level Order and Father (LAF) for XML documents. With LAF encoding, we devised a new index structure, called two‐layer LAF inverted index, which can greatly decrease the space complexity compared with Dewey encoding‐based inverted index. Furthermore, with two‐layer LAF inverted index, we proposed a new keyword query algorithm called Algorithm based on Binary Search (ABS) that can quickly find all Smallest Lowest Common Ancestor. We experimentally evaluate two‐layer LAF inverted index and ABS algorithm on four real XML data sets selected from Wikipedia. The experimental results prove the advantages of our index method and querying algorithm. The space consumed by two‐layer LAF index is less than half of that consumed by Dewey inverted index. Moreover, ABS is about one to two orders of magnitude faster than the classic Stack algorithm. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc. 相似文献
17.
XML信息检索中最小子树根节点问题的分层算法 总被引:10,自引:0,他引:10
最小子树根节点问题(smallest lowest common ancestor,简称SLCA)是实现XML信息检索研究中关键字查询的一个基本问题,其主旨就是求解所有包含给定关键字的紧致子树的根节点.XU等人给出了3种算法-基于索引的搜索算法(indexed lookup eager,简称ILE)、基于堆栈的算法以及基于扫描的算法(scan eager,简称SE),并通过实验证明ILE算法具有最好的表现.与基于B+树索引结构的ILE算法不同,所给出的新算法,称为LISA(layered intersec 相似文献
18.
优化的XML查询匹配:基于B^+-Tree索引的包含段的结构化联接算法 总被引:2,自引:0,他引:2
高效的结构化联接方法是XML查询的关键。本文提出一种新颖的结构化联接方法,使用了包含段结构化XML文档树,并且使用了B^ -Tree索引技术支持该新方法,从而在基于栈的结构化联接过程中得以忽略若干时空耗费,提高处理效率。 相似文献