4

查询优化器通常使用数据分布摘要来估计查询处理期间生成的中间表的大小。一种流行的此类汇总方案是直方图，其中输入范围被划分为桶，并保持每个桶中落入的元组数量的累积计数。出于估计的目的，假设桶内的分布是均匀的。

下面显示了一个R关于离散属性 a 与域的关系的直方图[1..10]：

Bucket 1: range = [1..2] Cumulative tuple count = 6 

Bucket 2: range = [3..8] Cumulative tuple count = 30

Bucket 3: range = [9..10] Cumulative tuple count = 10

自联接操作 R x R 的估计大小是多少

A) 46
B) 218
C) 248
D) 1,036
E) 5,672

解决方案中给出的答案：B

答案是如何计算的？

4

2 回答 2

2

一个自连接属性R的大小等于每个属性值的频率之和R。

这里频率以桶的形式给出，例如第一个桶有 2 个值 r，频率 = 6，所以我们可以假设桶一中每个值的频率是频率 = 3，类似地，桶二的频率 = 30/6 = 5、对于bucket的三个频率，每个值=10/2=5。

因此，尺寸为

Size =  [(3^2)*2] + [(5^2)*6] + [(5^2)*2]
     =  218
于 2012-06-15T18:41:56.110 回答
0

我一直在尝试自己解决这个问题（它来自 GRE 计算机科学科目考试准备考试）。到目前为止，我还没有找到为什么答案是 218 的答案，但我发现了给出的数字和正确答案之间的联系。

事实证明，累积元组计数的平方和除以每个桶中离散值的数量，得到 218。不太抽象：6²/2 + 30²/5 + 10²/2 = 218。

这不是一个答案，但至少有一个联系 =)

于 2011-11-11T16:08:21.590 回答