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.
You might also like to view...
Which string matching algorithms are better suited (or can be extended to be better suited) to work with a set of patterns (check all that apply)?
a. Boyer-Moore b. Rabin-Karp c. Knuth-Morris-Pratt d. Aho-Corasick
The class JOptionPane is part of the package java.swing.
Answer the following statement true (T) or false (F)
The mysql_connect() function returns a ____________________ as an integer if it connects successfully to a database or a Boolean FALSE if it doesn't.
Fill in the blank(s) with the appropriate word(s).
Is DSL the best way to connect to the Internet?
a) Yes, because anyone who has a standard phone line can use DSL service.
b) It depends. DSL service is available in many but not all areas.
c) No, because DSL requires the use of fiber-optic cables.
d) No, because DSL connections are too expensive for home use.