nucleation

LIT-1092: Selection of Views to Materialize Under a Maintenance Cost Constraint

1 min read

Properties4
StatusActive — read in full 2026-10-15 from the authors' PostScript copy on Stanford InfoLab's papers server (infolab.stanford.edu/pub/papers/update.ps, 18 pages, dated 8 October 1998, the ICDT '99 camera-ready, not the 2005 TKDE journal version; not compared with Springer's typeset pages). Worth reading as the first view-selection result that budgets maintenance time instead of space, and for its demonstration that upkeep is not additive: storing one view can make others cheaper to maintain, so benefit per unit of maintenance is not monotone and single-view greedy can be arbitrarily bad. For QUESTION-114 it shows upkeep priced as a budget, U(M) = Σ update frequency × per-update maintenance cost given the other stored views, with query cost the only objective; build cost, storage and staleness are not modelled (every view is refreshed in a nightly batch). Its guarantee answers the open problem of LIT-1091 only for OR view graphs: 1 − 1/e of an optimum's benefit while using up to twice the budget, under an assumption on the optimum, or half the optimum's benefit per unit of maintenance without it, with the theorems stated but not proved and a greedy whose stages are exponential in general (including on data cubes). General AND-OR graphs get only an exact A* search. It does not close the question, and comes no closer to a joint cost model than LIT-1095.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-890 — Gupta & Mumick — Selection of views to materialize under a maintenance cost constraint
Cited as “source” byTHEORY-350 — Under a budget on maintenance time, a stored view's upkeep depends on which other views are stored, so upkeep is not additive and adding a view can lower it, and greedily adding the single view of best saving per unit of upkeep can be arbitrarily bad; on OR view graphs a greedy over inverted tree sets gets 1 − 1/e of the saving of an optimum given as much upkeep, using up to twice the budget, if no tree-piece of the optimum alone exceeds the budget

Graph View

Gupta, H. and Mumick, I. S. (1999). Selection of views to materialize under a maintenance cost constraint. In C. Beeri and P. Buneman (eds.), Database Theory — ICDT’99, LNCS 1540, pp. 453–470. Springer. DOI 10.1007/3-540-49257-7_28

Key takeaways

Read in full (NOTE-890), from the authors’ camera-ready on Stanford InfoLab’s papers server. The paper minimizes frequency-weighted query cost subject to a cap on total maintenance time. Maintenance is not additive: storing one view can make another cheaper to keep current, so single-view greedy can be arbitrarily bad. For OR view graphs, a greedy over “inverted tree sets” reaches 1 − 1/e of an optimum’s benefit while using up to twice the budget, or half the optimum’s benefit per unit of maintenance; the theorems are stated without proof. General AND-OR graphs get only an exact A* search. Upkeep is a constraint, not a cost traded against savings, and staleness, build cost and storage are not modelled.

Why this is here

QUESTION-114: Gupta 1997 (LIT-1091) put upkeep in the objective but used it in one result only. This paper makes upkeep the budget.

Backlinks