基于二分法的XML结构连接

在XML数据的查询处理过程中，基于区域划分的连接算法在处理XML数据无序和不存在索引时，是一个效率较高的算法。该文利用区域编码的特点对输入集合进行穷尽的递归划分，在划分的代价下，逐步定位祖先-后代的结构关系。使用二分法进行划分后，再完成结构连接，提高了结构连接的效率，实验表明该算法在XML数据的查询处理上是一个有效的方法。     

分布式数据库系统中的查询优化处理

分布式查询处理是用户与分布式数据库的接口,也是分布式数据库研究的主要问题之一。在分布式查询处理中基于不同的目标有不同的查询优化算法,文章主要讨论基于最小传输代价原则的半连接算法,分析了半连接算法的原理并给出了多关系半连接查询优化算法思考。     

混合MapReduce环境下大数据划分的查询优化

在MapReduce与数据库的混合架构中,数据划分是影响查询性能的重要因素。对于开销最大的连接和聚集操作,采用混合MapReduce的方式实现,需要大规模数据的跨结点传输,网络传输和I/O开销巨大。为了减少传输的数据量,并提高连接操作的查询效率,提出了划分建议器模型。实现了MapReduce和数据库混合架构上的划分建议器,并计算划分代价,生成最优的数据划分方案,提高了系统效率。为了减少查询时间,依据划分建议器模型,提出了基于代价优先的生成策略和空间搜索算法,减少了划分建议器生成最优方案的时间。通过实验验证了划分建议器的有效性,使系统的整体查询代价最小,显著提高了系统性能。     

一种基于多连接属性划分的查询优化算法

查询操作是数据库中最常用的操作,由于分布式数据库的数据分布性和冗余性,使得查询优化处理成为分布式数据库研究的核心问题之一。为了提高分布式数据库查询效率,分析讨论了基于直接连接的常见执行策略和查询优化算法,同时针对分布式数据库应用中多表连接时存在多连接属性,提出一种改进的直接连接查询优化策略。改进后的算法提高了查询执行的并行性,缩短了查询处理时间,提高了查询效率。     

分布式数据库系统的查询优化技术研究

数据库数据量日益增多,造成了用户在使用数据库系统查询时费时费力,传统的查询优化方式已无法满足如今的数据查询要求,提高数据库系统优化的效率也成为计算机研究工作的热点。提出基于半连接算法的分布式查询处理技术对数据库系统进行查询优化,提出半连接操作的查询优化算法(SDD-1),并采用实验分析的方法进行验证,计算查询算法的代价。结果表明,基于半连接的研究策略的分布式数据库查询优化可以显著降低传输代价,使查询总效率得到有效提高。     

并行框架下基于位图索引的多表星型连接算法

分析面向大数据平台的MapReduce分布式编程技术以及实现数据查询时的连接算法,针对SSB数据模型,提出基于分布式缓存的多表星型连接优化技术.利用谓词向量技术,将维表中间连接的数据依赖转化为表上的位图索引过滤,减少数据依赖产生的巨大网络开销;采用分布式缓存技术充分利用处理节点的内存,优化网络传输,减少查询代价.     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

MapReduce框架下基于B 树的高维索引

针对MapReduce数据块处理机制、高维数据分布特征和KNN查询需求,本文设计一种基于B 树的高维索引结构（iPartition）,创新性提出基于主成分区分度的优化数据划分策略和邻接数据域分散存储等原则,将数据均匀划分到不同的Slave节点,使尽可能多的数据域对计算共同贡献,提升MapReduce任务处理并行性;利用B 树构造分布式的双层索引实现查询时数据范围快速过滤,降低高维计算代价。实验表明,iPartition在高维数据近似查询环境下,具有良好的性能和扩展性。     

SMJ:基于大纲的数据流多连接操作

研究了Ad hoc网络的特点及应用情况,分析了在Ad hoc网络中传统数据流多连接查询处理策略所面临的问题,并在此基础上提出了一种基于大纲的多数据流连接优化算法(SMJ)。实验结果显示SMJ算法可以极大降低Ad hoc网络数据流连接查询处理的通信代价。     

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

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

分布式数据库下基于剪枝的并行合并连接策略

排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排序合并连接策略（parallel sort-merge join based on prune,简称Pr_PSMJ）.其特点是,连接发生之前高效完成对连接对象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种双边邻接表（bilateral adjacency list,简称BAL）,用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确性;剪枝完成后,利用BAL计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,由于BAL保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于Pr_PSMJ中的高效剪枝策略是在连接执行之前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于Pr_PSMJ的算法的正确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr_PSMJ相对于其他策略能够有效减少网络开销,并提高连接效率.     

Exploiting spatial indexes for semijoin-based join processing indistributed spatial databases

In a distributed spatial database system, a user may issue a query that relates two spatial relations not stored at the same site. Because of the sheer volume and complexity of spatial data, spatial joins between two spatial relations at different sites are expensive in terms of computational and transmission costs. In this paper, we address the problems of processing spatial joins in a distributed environment. We propose a semijoin-like operator, called the spatial semijoin, to prune away objects that do not contribute to the join result. This operator also reduces both the transmission and local processing costs for a later join operation. However, the cost of the elimination process must be taken into account, and we consider approaches to minimize these overheads. We also study and compare two families of distributed join algorithms that are based on the spatial semijoin operator. The first is based on multi-dimensional approximations obtained from an index such as the R-tree, and the second is based on single-dimensional approximations obtained from object mapping. We have conducted experiments on real data sets and report the results in this paper     

Cost based in-network join strategy in tree routing sensor networks

The tiny and smart sensors enable applications which access a network of hundreds or thousands of sensors. In many applications, joins are used frequently to find relationships of readings of different sensors such as the correlation of sensor readings in distinct regions.In this paper, we present a cost based in-network join strategy called INJECT. Since the optimal join plan is determined according to various conditions such as data distributions and predicates of joins, it wastes the energy of sensors to use a fixed join plan blindly. Based on the analysis on how join queries can be handled in sensor networks, we devise several join plans. In particular, since the data transmission dominates the energy consumption of a sensor, we devise cost models each of which reflects the transmission cost of a join plan. Experimental results confirm that INJECT chooses the optimal or near optimal plan under various conditions.     

基于数据网格环境的连接操作算法

数据网格是一种分布式数据管理体系结构，能够为分布在网格中的资源提供协同的管理机制．数据库管理系统在数据网格中发挥着重要作用，在各种数据库操作中，连接操作是一种最常用也是最耗时的操作，到目前为止，尚未有文献提出数据网格环境下的连接操作算法．主要对数据网格环境下海量数据的连接操作算法进行了研究，针对网格中各结点之间网络带宽异构的特点，采取关系缩减算法、行分块传输技术和流水线并行机制来减少查询的响应时间．理论分析和实验结果证明，算法在减少网络通信开销、增加I／0和CPU并行、降低响应时间方面具有较好的性能．     

Data Partitioning for Parallel Spatial Join Processing

The cost of spatial join processing can be very high because of the large sizes of spatial objects and the computation-intensive spatial operations. While parallel processing seems a natural solution to this problem, it is not clear how spatial data can be partitioned for this purpose. Various spatial data partitioning methods are examined in this paper. A framework combining the data-partitioning techniques used by most parallel join algorithms in relational databases and the filter-and-refine strategy for spatial operation processing is proposed for parallel spatial join processing. Object duplication caused by multi-assignment in spatial data partitioning can result in extra CPU cost as well as extra communication cost. We find that the key to overcome this problem is to preserve spatial locality in task decomposition. In this paper we show that a near-optimal speedup can be achieved for parallel spatial join processing using our new algorithms.     

一种并行多路空间连接处理方法

空间连接查询是最耗时,最重要的空间查询、空间多路连接是涉及多个空间关系的连接查询,顺序空间连接查询的效率还是不能令人满意,研究利用并行机制提高空间连接查询效率成为有吸引力的方向,并行空间连接处理由三个阶段组成;任务创建,任务分配和任务并行执行,本文提出一种新的平面扫描方法用于多路并行处理的任务创建过程,随机提出基于花费估计的动态任务分配策略,给出了花费模型,并将其推到处理多路并行连接查询处理以实现负荷平衡。     

Efficient Processing of Distributed Twig Queries Based on Node Distribution

Massive XML data are increasingly generated for the representation, storage and exchange of web information. Twig query processing over massive XML data has become a research focus. However, most traditional algorithms cannot be directly implemented in a distributed manner. Some of the existing distributed algorithms generate a lot of useless intermediate results and execute many join operations of partial results in most cases; others require the priori knowledge of query pattern before XML partition, storage and query processing, which is impractical in the cases of large-scale data or frequent incoming new queries. To improve efficiency and scalability, in this paper, we propose a 3-phase distributed algorithm DisT3 based on node distribution mechanism to avoid unnecessary intermediate results. Furthermore, we propose a lightweight local index ReP with an enhanced XML partitioning approach using arbitrary partitioning strategy, and based on ReP we propose an improved 2-phase distributed algorithm DisT2ReP to further reduce the communication cost. After the performance guarantees are analyzed, extensive experiments are conducted to verify the efficiency and scalability of our proposed algorithms in distributed twig query applications.     

分布式空间数据分片与跨边界拓扑连接优化方法

研究分布式空间数据库(distributed spatial database,简称DSDB)中数据按区域分片时的跨边界片段拓扑连接查询问题,并提出相应的优化方法.首先研究了分布式环境下的空间数据的分片与分布,提出了空间数据分片的扩展原则:空间聚集性、空间对象的不分割性、逻辑无缝保持性.然后,将区域分割分片环境下的片段连接分为跨边界和非跨边界两类;同时,将拓扑关系分为两类,重点研究跨边界的两类片段拓扑连接.提出了跨边界空间片段拓扑连接优化的两个定理,并给出了证明.以此为基础,给出了跨边界空间拓扑连接优化规则,包括连接去除规则和连接优化转化规则.最后设计了详细的实验,对自然连接策略、半连接策略以及所提出的连接策略进行效率比较,结果表明,所提出的方法对跨边界连接优化有明显优势.因此,所提出的理论和方法可以用于分布式跨边界拓扑关系查询的优化.     

Optimising the distributed execution of join queries in polynomial time

It is proposed that an optimal strategy for executing a join query in a distributed database system may be computed in a time which is bounded by a polynomial function of the number of relations and the size parameters of the network. The solution so unveiled considers both the transmission costs and the processing costs incurred in delivering the required result to the user that issued the query.The query specifies that several relational tables are to be coalesced and presented to the appropriate user. Undertaking this task demands the utilisation of limited system resources, so that a strategy for fulfilling the request that imposes minimal cost to the system should be devised. Both the processor sites, and the communications links that interconnect them, are utilised; an optimal strategy is one that minimises a weighted sum of processing and data transmission costs.An integer linear programming model of this problem was originally proposed in [1]; however, no suggestion was given as to how this model might be efficiently solved. By extending the earlier analysis, the recursive nature of the join computation is revealed. Further investigations then produce a modified relationship amenable to algorithmic solution; the resultant procedure has polynomial time and space requirements.