基于区域划分的XML结构连接

结构连接是XML查询处理的核心操作,受到了研究界的关注.高效的算法是高效查询处理的关键.目前已经提出了许多结构连接的算法,它们中的大多数都基于如下的前提条件之一:输入元素集合存在索引或者有序.当这些条件不成立时，由于对输入数据临时排序或建索引的代价，这些算法的性能会大大下降.基于这样的观察，提出了一种基于区域划分的结构连接算法.该算法基于任务分解的思想，利用区域编码的特点对输入集合进行划分.给出了详细的算法设计，并对算法的I/O复杂性进行了分析.大量的实验结果显示，该算法具有良好的 性能，在输入数据无序或没有索引的情况下优于现有的排序合并算法，可以为查询计划提供更多的选择.     

XML查询的结构连接算法

针对目前多数XML结构连接方法在输入元素集合不存在索引或者无序的情况下,对输入数据临时排序或建立索引代价过高的问题,分析经典的Stack-Tree-Desc算法以及B 树索引的优化算法,提出不局限于外部索引结构的XML查询优化策略并给出算法实现.实验结果表明该算法较Stack-Tree-Desc算法查询效率更高.     

一种基于间接索引桶的OLAP查询算法

提高多表连接和聚集操作性能是OLAP查询中的关键问题之一。本文提出了一种基于间接索引桶的OLAP分组聚集查询算法MIBGA。该算法将维层次编码和事实表标识符分组集合进行有效结合，用间接索引桶代替目前流行的位图连接索引，并通过分组属性位图的位操作方式来快速完成OLAP查询。分析表明，该方法压缩了索引的存储空间，减少了I／O开销，有效地提高了多表连接的查询效率。     

一种XML数据流小枝模式查询算法

针对传统XML文档小枝模式查询算法系统开销大的问题,提出一种XML数据流小枝模式查询算法。该算法结合SAX数据流解析技术,将层次关系队列结构应用于XML文档查询中,采用动态生成区间编码的方式,免除建立编码索引文件的步骤。实验结果表明,在对相关数据集进行查询时,该算法可减少I/O操作,缩短查询响应时间,提高查询效率。     

基于层次位图连接索引的数据仓库查询优化

在数据仓库的联机分析处理的查询处理中,经常会涉及到大量数据的复杂即席查询.用户通过提交联机分析处理查询对数据进行分析和决策支持,这通常需要较快的查询响应速度.因此,提高联机分析处理的查询性能就成为了数据仓库领域的关键问题.为了提高数据仓库的查询性能,结合维表层次结构的特点,提出一种将分段位图索引和位图连接索引有效结合的方法.实验证明,该方法节省了位图索引的储存空间,减少了I/O开销,有效地提高了数据仓库的查询效率.     

MapReduce连接查询的I/O代价研究

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而MapReduce是一种用于大规模数据集并行处理的编程模型,研究基于MapReduce的连接查询代价评估和查询优化,有着学术意义和应用价值.MapReduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于MapReduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.     

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

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

基于路径表达式的XML索引查询技术

为减少结构连接操作时对输入数据大小的依赖、在大部分实际情况下提高算法效率,研究了当前结构连接算法产生大量中间结果而导致过多连接次数的问题,提出一种新的基于结构摘要的索引技术。对路径树和XML树分别编码,使用少量预先计算的路径信息。在结构连接时执行交叉操作,该操作由位图在较短时间内实现,并且只返回结点所在路径的位置信息,减少了I/O次数。实验结果表明了其具有较高的查询效率,并且查询时间不依赖于输入数据的规模。     

空间数据库中连接运算的处理与优化

空间数据库的性能问题严重制约了它的应用与发展 .由于空间连接运算是空间数据库中最复杂、最耗时的基本操作 ,因此其处理效率在很大程度上决定了空间数据库的整体性能 .尽管目前已经有许多空间连接算法 ,但空间连接运算的代价估计和查询优化仍然有待进一步研究 .众所周知 ,大部分空间连接算法都是基于 R树索引实现的 ,如果参与空间连接运算的关系上没有索引或只有部分索引 ,那么就需要使用特殊的算法来处理 .另外 ,各种算法的代价评估模型需要一个相对统一的计算方法 ,实践证明 ,根据空间数据库的实际情况 ,使用 I/ O代价来估计算法的复杂性较为合理 .在此基础上 ,针对复杂的空间查询中可能出现多个关系参与空间连接运算的情况 ,故还需要合理地应用动态编程算法来找出代价最优的连接顺序 ,以便最终形成一个通用的算法框架 .通过对该算法框架的复杂性分析可以看出 ,在此基础上实现的空间数据库查询优化系统将具有较高的时空效率 ,并且能够处理非常复杂的空间查询     

基于双路索引的XML查询优化研究

为实现各种形式的XML数据查询,介绍一种双路索引方法,采用倒排序技术建立绝对索引模型和相对索引模型,并提出相关查询处理的算法。绝对索引模型将查询路径表达式缩短,减少比较次数,相对索引模型建立父子索引表补全路径,用较小的索引结构替代原始查询。采用DBLP数据集进行测试,实验结果表明,该方法可以提高查询处理的性能。     

混合散列连接算法随机I/O消除

混合散列连接算法(HHJ)是数据库管理系统查询处理中一种重要的连接算法. 本文提出通过缓存优化来减少随机I/O的缓存优化混合散列连接算法(OHHJ), 即通过合理优化分区阶段桶缓存的大小来尽量减少分区过程中产生的随机I/O. 文章通过对分区(桶)大小、桶缓存大小、可用缓存大小、关系表大小与硬盘随机I/O访问特性之间的关系进行定量分析, 得出桶大小以及桶缓存大小最优分配的启发式. 实验结果表明OHHJ可以较好地减少传统HHJ算法分区阶段产生的随机I/O, 提升了算法性能.     

An evaluation of relational join algorithms in a pipelined queryprocessing environment

A query processing strategy which is based on pipelining and data-flow techniques is presented. Timing equations are developed for calculating the performance of four join algorithms: nested block, hash, sort-merge, and pipelined sort-merge. They are used to execute the join operation in a query in distributed fashion and in pipelined fashion. Based on these equations and similar sets of equations developed for other relational algebraic operations, the performance of query execution was evaluated using the different join algorithms. The effects of varying the values of processing time, I/O time, communication time, buffer size, and join selectively on the performance of the pipelined join algorithms are investigated. The results are compared to the results obtained by employing the same algorithms for executing queries using the distributed processing approach which does not exploit the vertical concurrency of the pipelining approach. These results establish the benefits of pipelining     

XML查询结构连接顺序选择算法分析与优化

如今对XML查询的优化是对XML的热点研究方向。其中的结构连接操作是XML数据库查询的主要操作。和关系数据库中的连接运算一样,结构连接顺序的选择是XML数据库查询优化的核心。文中主要通过对XML查询优化中各种选择连接顺序算法的研究,提出了一种优化的算法,在规模较大的XML查询中能够有效缩减搜索空间,提高效率。     

PI-Join: Efficiently processing join queries on massive data

The ratio of disk capacity to disk transfer rate typically increases by 10× per decade. As a result, disk is becoming slower from the view of applications because of the much larger data volume that they need to store and process. In database systems, the less the data volume that is involved in query processing, the better the performance that is achieved. Disk-based join operation is a common but time-consuming database operation, especially in an environment of massive data in which I/O cost dominates the execution time. However, current join algorithms are only suitable for moderate or small data volume. They will incur high I/O cost when performing on massive data because of multi-pass I/O operations on the joined tables and the insensitivity to join selectivity. This paper proposes PI-Join a novel disk-based join algorithm that can efficiently process join queries involving massive data. PI-Join consists of two stages: JPIPT construction stage (JCS) and result output stage (ROS). JCS performs a cache-conscious construction algorithm on join attributes which are kept in column-oriented model to obtain join positional index pair table (JPIPT) of join results faster. The obtained JPIPT is used in ROS to retrieve results in a one-pass sequential selective scan on each table. We provide the correctness proof and cost analysis of PI-Join. Our experimental results indicate that PI-Join has a significant advantage over the existing join algorithms.     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

基于结构化联接的多版本XML文档查询处理

结构连接是XML查询处理的核心操作,受到了研究界的关注。高效的算法是高效查询处理的关键。目前已经提出了许多结构连接的算法,但都不支持多版本的XML文档。文章对经典结构连接算法进行了扩充,使之支持多版本的XML文档。     

Performance analysis of three text-join algorithms

When a multidatabase system contains textual database systems (i.e., information retrieval systems), queries against the global schema of the multidatabase system may contain a new type of joins-joins between attributes of textual type. Three algorithms for processing such a type of joins are presented and their I/O costs are analyzed in this paper. Since such a type of joins often involves document collections of very large size, it is very important to find efficient algorithms to process them. The three algorithms differ on whether the documents themselves or the inverted files on the documents are used to process the join. Our analysis and the simulation results indicate that the relative performance of these algorithms depends on the input document collections, system characteristics, and the input query. For each algorithm, the type of input document collections with which the algorithm is likely to perform well is identified. An integrated algorithm that automatically selects the best algorithm to use is also proposed