Gupta, H. (1997). Selection of views to materialize in a data warehouse. In F. Afrati and P. Kolaitis (eds.), Database Theory — ICDT ‘97, LNCS 1186, pp. 98–112. Springer. DOI 10.1007/3-540-62222-5_39
Key takeaways
Read in full (NOTE-889), from Gupta’s own March 1997 preprint. Gupta states view selection on general AND-OR view graphs as minimizing frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget. He proves greedy guarantees of 1 − 1/e (about 63%) of the optimal benefit, with the budget overrun by one view or up to double, but almost all of them assume no updates. Maintenance cost enters exactly one theorem: AND view graphs (each view has one way of being computed) in which every view is queried more often than it is updated. For OR view graphs, which include Harinarayan, Rajaraman and Ullman’s data cube, the paper sets update costs aside outright, so it does not add upkeep to that problem. Maintenance is an abstract per-update charge for keeping a view consistent. Nothing prices building a view, tolerated staleness or deferred refresh, and there are no experiments.
Why this is here
QUESTION-114: Harinarayan et al. (LIT-1094) price no upkeep. The question needs the cost of keeping a precomputed answer current, which is staleness’s price.