nucleation

LIT-1117: Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the VLDB Endowment's open copy of the proceedings paper (www.vldb.org/conf/2000/P144.pdf, pp. 144–155; the server needs a browser User-Agent). Worth reading as the source of the idea that a cached value can be held as an interval its source guarantees, so that staleness becomes a bounded, stated imprecision instead of an unknown error, and a query buys precision down by paying for exact reads; for SUM, choosing the cheapest reads that meet a width R is a 0/1 knapsack problem (THEORY-364). For QUESTION-114 it gives staleness a unit (bound width against a query's tolerance) and prices only the query side: the source's upkeep that makes the bound a guarantee, and the choice of bound widths, are assumed and uncosted, imprecision is a hard constraint rather than a loss, and a stale read can never be wrong. For CLAIM-303 it sharpens "verification" into a per-use decision against a stated tolerance, but rests on a source that watches every copy, which a filed argument lacks, so it does not price the cost of reusing an obsolete conclusion; it does not bear on CLAIM-308's rent-or-buy argument. LIT-1109 prices the upkeep side.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-922 — Olston & Widom — Offering a precision-performance tradeoff for aggregation queries over replicated data
Cited as “source” byTHEORY-364 — When each cached value is an interval its source guarantees to contain the current value, and a query must return an answer interval no wider than R whatever the true values, choosing the cheapest set of exact reads for a SUM is a 0/1 knapsack problem, NP-complete in general and solved by taking the narrowest intervals first when read costs are equal, and for a COUNT with a selection predicate the cheapest choice is the ⌈|T?| − R⌉ cheapest undecided tuples

Graph View

Olston, C. and Widom, J. (2000). Offering a precision-performance tradeoff for aggregation queries over replicated data. In Proc. VLDB 2000, pp. 144–155.

Key takeaways

Read in full (NOTE-922). Olston and Widom propose TRAPP: caches hold, for each numeric value, an interval its source guarantees to contain the current value, the source pushing a refresh whenever the value leaves it. A query carries a precision constraint R, and the system chooses which values to fetch exactly so that the answer interval is at most R wide whatever the true values, at least total refresh cost. For SUM (and AVG without a predicate) that choice is a 0/1 knapsack problem, NP-complete in general and polynomial with equal costs; COUNT and MIN have simple rules. Staleness becomes bounded imprecision, never error, and the cost of the source-side upkeep that guarantees this, and of setting the bound widths, is outside the optimization. The one experiment is 90 stock prices with random costs.

Why this is here

QUESTION-114: cached values are held as intervals the source keeps valid, so a cached value is never wrong, only imprecise, and each query fetches the cheapest exact values that meet its precision. Staleness is a hard bound per query here; the trade against refresh cost is in LIT-1109.

Backlinks