考虑一个有k+1列的表R，其中前k列C1，…，Ci，…，Ck是分类(即非数值)属性，最后一列是数值属性。设Ci可能值的个数为ni, i = 1,2，…，k，考虑如下查询:select C1，…Ci，…，Ck, sum(Ck+1) from R group by rollup(C1，…Ci，…，Ck);设此查询生成的表为S。确定表S中元组的数量

首先，rollup操作会生成一系列的聚合操作，每个操作都会在原表R的基础上按照指定的分组属性进行聚合，最终得到的结果是一个多层次的汇总表。具体来说，对于k个属性，rollup操作将生成2^k-1个分组，其中包括空分组和所有的子分组。

对于每个分组，我们需要计算出相应的sum(Ck 1)的值。由于每个分组都是按照C1，…Ci，…，Ck的顺序进行的，因此我们可以采用类似动态规划的方式来计算。具体来说，我们对于每个属性Ci，都维护一个大小为ni的桶，用于记录该属性取每个可能值时对应的sum(Ck 1)的值。然后，对于每个分组，我们根据其包含的属性值，依次从对应属性的桶中取出对应的sum(Ck 1)的值，然后将其相加即可。

由于每个属性都有ni个可能值，因此对于每个分组，需要进行ni次查找和ni-1次加法。因此，对于所有的2^k-1个分组，总共需要进行的查找和加法操作次数为:

ni * (ni-1) * 2^(k-1)

因此，表S中元组的数量为:

2^k * Πni