nucleation

THEORY-1244: No access method is optimal on read, update and memory overhead at once: bounding any two of the three forces the third above a hard lower bound that cannot be further reduced

1 min read

Properties4
StatusProposed
Tagsdatabases
SourceLIT-1085 — Designing Access Methods: The RUM Conjecture
ExtendsTHEORY-344 — An access method's read, update and memory overheads, each a ratio to the base data alone with a floor of 1.0, are conjectured to trade so that bounding any two forces a lower bound on the third; the conjecture is unproved, its formal wording says no more than the floor already does, and the paper's extreme designs show conflicts between pairs, read against memory and update against read, not a symmetric three-way trade

Graph View

Source

Athanassoulis et al. (2016), LIT-1085, read in full in NOTE-888. The paper asserts the trade: designing access methods “that set an upper bound for two of the RUM overheads, leads to a hard lower bound for the third overhead which cannot be further reduced” (§1), and “optimizing in any two areas negatively impacts the third” (abstract).

Where the evidence stands

Nothing is proved. What the paper states, and what its formal wording and its three extreme designs do and do not show, is THEORY-344, Active, which this entry extends: that entry is the reading, this one the thesis. The promote_when above is THEORY-344’s condition before the status review of 2026-10-30 promoted it, carried here word for word: a proof of a quantified version in a stated cost model.

What this does not say

  • How large the forced bound is, or how it grows as the other two are tightened. That is what a proof would have to supply.
  • That the trade is symmetric. At the paper’s extremes the memory-minimal design is also update-minimal (THEORY-344).

Backlinks