Design a query evaluation algorithm for the ROLLUP operator. The objective of such an algorithm should be that the results of the previously computed aggregations are reused in subsequent aggregations and not recomputed from scratch.

What will be an ideal response?

The idea is based on the fact that to compute

SELECT A1,..., An aggr(B)

FROM SomeRelation

WHERE ...

GROUP BY A1,..., An

where aggr is min, max, sum, or count, we can first compute the relation
SomeRelation1,...,n,n+1

SELECT A1,..., An, An+1, aggr(B)

FROM SomeRelation

WHERE ...

GROUP BY A1,..., An, An+1

and then compute

SELECT A1,..., An, aggr(B)

FROM SomeRelation1,...,n,n+1

WHERE ...

GROUP BY A1,..., An

In this way, we are reusing the previous aggregation of aggr(B) over the attributes of SomeRelation minus A1,..., An, An+1, B and nowonly need to aggregate over the
attribute An+1.
If aggr is avg, we need to compute sum and count using the above optimization
and then divide one by the other.
We can thus start computing

GROUP BY ROLLUP (A1,..., An)

with an aggregation that groups by all the attributes, A1,..., An, then all but the last
attribute, etc. Thus, the following aggregates will be computed, where each successive aggregation utilizes the result of the previous one:

GROUP BY A1,..., An

GROUP BY A1,..., An?1

... ... ...

GROUP BY A1

The first GROUP BY above computes the relation SomeRelation1,...,n, the second
GROUP BY uses SomeRelation1,...,n to aggregate the values of B over the attribute
An, which produces the relation SomeRelation1,...,n?1. The third GROUP BY takes
SomeRelation1,...,n?1 and aggregates the values of B over the attribute An?1, etc.