nucleation

LIT-1094: Implementing data cubes efficiently

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the authors' 25-page version on Stanford InfoLab's papers server (infolab.stanford.edu/pub/papers/cube.ps, TeX run of 8 January 1996), not the SIGMOD typesetting, which the ACM Digital Library refused (403); the two were not compared. Worth reading as the standard source on choosing which precomputed answers to store when each query is answered from its cheapest stored ancestor: the lattice of group-by views, the linear cost model (rows of the ancestor scanned), NP-completeness, and a greedy rule whose total benefit, the saving against storing the base view alone, is at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimum for a budget of k views, tight, unchanged with fixed query frequencies, and only 0.63 − f under a space budget when no view exceeds a fraction f of it. For QUESTION-114 and QUESTION-095 it shows the precomputed-answer term the four earlier readings lacked, with a stored answer's value counted over every query it serves and marginal on what is already stored (sharpening CLAIM-303's break-even); it does not price build cost (space is a proxy), upkeep or staleness (the data are static and derived answers exact), timing or deadlines, uncertain workloads, or the medium of retrieval, so it is a model of the speed bugs only in naming the category, an analogy with one usable term for filed arguments, silent on the bias of reused inferences, and not about LEGO bins.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-895 — Harinarayan, Rajaraman & Ullman — Implementing data cubes efficiently
Cited as “source” byTHEORY-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

Harinarayan, V., Rajaraman, A. and Ullman, J. D. (1996). Implementing data cubes efficiently. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pp. 205–216. DOI 10.1145/233269.233333

Key takeaways

Read in full (NOTE-895). Treats a data cube’s group-by queries as a lattice in which a query can be answered from any stored ancestor, prices a query at the number of rows of the smallest materialized ancestor, and chooses which views to precompute. Choosing k views to maximize the total reduction in query cost (the “benefit”) is NP-complete; a greedy rule that adds the view of largest marginal benefit gets at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimal benefit, a bound that is tight, holds unchanged with query-frequency weights, and weakens to 0.63 − f under a space budget when no view takes more than a fraction f of it. The cost of building views is represented only by their size, maintenance and updates are not modelled, the data are static, and the bound is on benefit, not on query cost. On TPC-D data the greedy order reaches nearly the minimum total query time with five views and barely more space than the base view.

Why this is here

QUESTION-114: the four works on physical design already read choose ways of reaching stored data. None covers a precomputed answer, which is the cockpit’s case (speeds computed before landing and left as bugs). This paper chooses which answers to precompute.

Backlinks