Source
Dar, Franklin, Jónsson, Srivastava and Tan (1996), LIT-1113, VLDB 1996, pp. 330–341, read in full in NOTE-904 from the VLDB Endowment’s copy.
What was actually shown
The cached part of a relation is described by a constraint formula V. A query Q splits into a probe Q ∧ V, answered locally, and a remainder Q ∧ ¬V, sent to the server as a query. Cached tuples are grouped into disjoint semantic regions shaped by past queries; a query overlapping n regions can leave 2n + 1. Regions with equal replacement values are merged when one is under 1% of the cache.
A simulation (CSIM; 250 Kb client cache; 4 Kb pages; 50 warm-up and 500 measured queries, three runs) compared this with page and tuple caching. On the clustered indexed attribute all three were similar, tuple caching worst through overhead. On the unclustered indexed attribute page caching “performs far worse”. On an unindexed attribute with a disk cache, where every server request costs a full scan, “over 60% of the small (1%) queries are answered completely from the client’s cache”, and semantic caching was faster for small queries; once no query fits wholly in cache it equals ignoring the cache. Overhead was 6.5% of the cache for page caching and 15.2% for tuple caching; for semantic caching it depended on query size and coalescing (“For 1% queries, there are 55 regions and nearly 275 factors” without coalescing), and was over four times higher in a two-attribute space than in one, for small queries without coalescing.
Could have come out otherwise: the probe-and-remainder mechanism could have lost to tuple caching through region overhead, or failed to find whole answers in cache often enough to avoid server scans.
What this does not say
- That finding the reusable part is cheap. “We also do not model the CPU cost of cache management at the client.” The containment and difference computations on formulas, which need not be convex or connected, are free in every result.
- Anything with updates. The study is read-only; consistency, invalidation and staleness are absent.
- Anything beyond selections on one relation. Joins and general queries are future work in the paper.
- That it holds outside one simulator. No implemented system, one synthetic relation, one skewed workload; a tenfold scale-up gave “nearly identical” relative results.
- That partial reuse of an argument works the same way. The mechanism needs answers stored with a description in the language questions arrive in, so that overlap is computable.
Connections
- CLAIM-303 prices reuse per use at a fixed reconstruction cost; here the saving per use is the overlap of the new question with what is stored, and the access term c_a is a containment test, which the paper does not cost.
- THEORY-375: the same paper’s replacement results.
- THEORY-356 and THEORY-350 (view selection under space and upkeep budgets) choose what to store ahead of queries; here everything fetched is stored and the question is what to drop.
Note of 2026-10-20: narrowed and promoted
The promotion audit (batch 073) narrowed the title and promoted it on the one study it rests on, under ADR-047 v3. LIT-1113 was read in full in NOTE-904, with its tables and figures read from page images. The old title gave “answered over 60% of small queries without contacting the server” without its condition; the paper reports it for 1% queries on an unindexed attribute with a disk cache, where every server request is a full scan, and the title now says so (a correction, not a dropped thesis). “Good” and “bad clustering” become the clustered and unclustered indexed attributes the paper compared. The former promote_when moves unchanged to QUESTION-237.