Scalable computation of acyclic joins
Scalable computation of acyclic joins
复制标题
非循环连接的可扩展计算
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Pagh
中科院分区：
文献类型：
--
作者：
Anna Pagh;R. Pagh
关系代数的连接操作是关系数据库系统的基石。计算多个关系的连接一般是NP困难的，而特殊（和典型）情况是容易处理的。本文考虑具有非循环连接图的连接，对于该连接图，当前方法最初应用完全缩减器来有效地消除对连接结果没有贡献的元组。从最坏情况的角度来看，以前的算法用于计算k个完全约简关系的非循环连接，在磁盘上总共占用n≥k个块，使用Ω（（n+z）k）I/O，其中z是连接结果的大小。在本文中，我们展示了如何在运行完全约简器加上排序输出的成本的常数因子内的时间范围内计算连接。对于广泛的一类非循环连接图，这是O（sort（n+z））I/O，从以前的边界中去除对k的依赖。传统的方法将连接分解为若干个二进制连接，然后逐个执行。最后，作为I/O模型中循环连接的初步研究，我们展示了如何在O/O模型中计算连接图为3-循环的连接，并给出了一个实例，证明了该方法的有效性。（n2/m+sort（n+z））I/O，其中m是内部存储器中的块数。
The join operation of relational algebra is a cornerstone of relational database systems. Computing the join of several relations is NP-hard in general, whereas special (and typical) cases are tractable. This paper considers joins having an acyclic join graph, for which current methods initially apply a full reducer to efficiently eliminate tuples that will not contribute to the result of the join. From a worst-case perspective, previous algorithms for computing an acyclic join of k fully reduced relations, occupying a total of n≥k blocks on disk, use Ω((n+z)k) I/Os, where z is the size of the join result in blocks.In this paper we show how to compute the join in a time bound that is within a constant factor of the cost of running a full reducer plus sorting the output. For a broad class of acyclic join graphs this is O(sort(n+z)) I/Os, removing the dependence on k from previous bounds. Traditional methods decompose the join into a number of binary joins, which are then carried out one by one. Departing from this approach, our technique is based on computing the size of certain subsets of the result, and using these sizes to compute the location(s) of each data item in the result.Finally, as an initial study of cyclic joins in the I/O model, we show how to compute a join whose join graph is a 3-cycle, in O(n2/m+sort(n+z)) I/Os, where m is the number of blocks in internal memory.