nucleation

LIT-1080: Selection of Views to Materialize in a Data Warehouse

1 min read

Properties4
StatusActive — read in full 2026-10-15 from the first author's manuscript of the journal paper, linked from Gupta's publication list (www3.cs.stonybrook.edu/~hgupta/ps/sel-views-tkde.pdf, 41 single-column pages, read by OCR; not compared with IEEE's typeset pp. 24–43). Worth reading as the consolidated, proved account of Gupta's 1997 space-budget results (LIT-1091) and Gupta and Mumick's 1999 maintenance-budget results (LIT-1092): it is the journal version of both papers, not of the 1999 paper alone, and it adds proofs, not new problems or guarantees. The inverted-tree greedy's 1 − 1/e guarantee for OR view graphs under a maintenance budget (now Theorem 8, still bicriteria at up to 2S and still assuming no tree-piece of the optimum exceeds S) and the exactness of A* on AND-OR graphs (Theorem 10) are now proved; the assumption-free half-density bound (Theorem 9) is referred to Gupta's thesis; the guarantee is still for OR graphs only and the greedy still exponential in the worst case, data cubes included. For QUESTION-114 it changes nothing: the article holds two separate models, upkeep in the objective under a space budget (guaranteed only for AND view graphs in which every view is queried more often than updated, a lemma it now says fails for OR graphs) and upkeep as a budget with query cost alone in the objective, never both constraints together, and no build cost or staleness. LIT-1095 remains the closest to a joint model.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-901 — Gupta & Mumick — Selection of views to materialize in a data warehouse (TKDE 2005)
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, THEORY-356 — When stored views are never updated, greedily storing the view of largest marginal saving in query cost gets at least 1 − 1/e of the optimal saving on a data-cube lattice or any OR or AND view graph, against the optimum for the same number of views or for the space the greedy ends up using, which may exceed the budget by one view

Graph View

Gupta, H. and Mumick, I. S. (2005). Selection of views to materialize in a data warehouse. IEEE Transactions on Knowledge and Data Engineering 17(1), 24–43. DOI 10.1109/TKDE.2005.16

Key takeaways

Read in full (NOTE-901), from the first author’s manuscript of the journal paper, by OCR. It is the journal version of both ICDT papers, Gupta 1997 (LIT-1091) and Gupta and Mumick 1999 (LIT-1092), and it adds proofs, not new problems or guarantees. The maintenance-budget greedy for OR view graphs (now Theorem 8, still at up to twice the budget and still assuming no piece of the optimum exceeds it) and the exactness of A* (Theorem 10) are now proved; the assumption-free bound (Theorem 9) is referred to Gupta’s thesis. The guarantees still cover OR graphs only, the greedy is still exponential in the worst case, the space and maintenance constraints are never combined, and build cost and staleness are not modelled.

Why this is here

QUESTION-114: the conference version (LIT-1092) stated its guarantees without proof and covered OR view graphs only. This is the journal version.

Backlinks