
Incorporating Other Physical Structures 167
The set of subcubes to materialize should always include the top subcube
(see Figure 9.2), because there is no other subcube that can be used to answer
the corresponding query without going to the raw data. Even under the sim-
plifying assumptions previously discussed, the problem is shown to be NP-
complete from a reduction from set cover. Interestingly enough, however, there
is a greedy solution for this problem with good quality guarantees. Before in-
troducing the greedy algorithm, we define the benefit of a subcube relative
to a set of subcubes. Specifically, after selecting some set S of subcubes, the