Topics — What a work is about. Nucleation holds whatever reading the owner files here, whether or not an Anthology of the SOTA topic could also hold it; instruction for ML practice belongs to the anthology (ADR-048). The words are seeded from the clusters the reading-time triage of 2026-09-25 found, and grow by decision.
Databases and data structures — how stored data is organized so that it can be found and kept current — physical database design and index selection, materialized views and the choice of which answers to precompute, adaptive and self-organizing structures, lower bounds on lookup, caching and paging; and the cost of organizing ahead of use against organizing in use. Read for itself, not as ML practice: learned indexes and other machine-learning approaches go to the anthology (ADR-045).
40 of 1352 THEORY documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| THEORY-332 v2 | For one index with no space limit, Bruno and Chaudhuri’s online tuner, which builds the index once the savings it would have given have risen by its build cost above their last low and drops it once they have fallen by the build cost below their last high, is not three-competitive: when every statement’s saving or loss is at most a fraction f of the build cost, a repeated workload makes it cost nearly 3 + 2f times the offline optimum, and one statement whose saving exceeds the build cost makes the ratio unbounded; no upper bound is shown | Bruno and Chaudhuri (2007), LIT-1095, read in NOTE-896. An always-on index tuner keeps, per index, the running sum of what each statement would have saved (updates counting as losses) and creates or drops the index when that sum moves by the build cost from its last extreme. The paper calls the single-index rule three-competitive, but its proof is one workload on which the ratio approaches 3, a lower bound. The reading’s own check found ratios up to 4.7 when one statement’s saving is near the build cost, and an unbounded ratio when it exceeds it; with every saving at most a tenth of the build cost no random workload passed 2.4, but a constructed one with steps at most fB approaches 3 + 2f (note of 2026-10-20). The multi-index tuner with a space limit is heuristic, and all costs are optimizer estimates. | Active |
| THEORY-333 v2 | Database cracking, which partitions a copy of a column in place as a side effect of each range query, measured in memory on 10^7 integers under uniformly random ranges, costs about 40% more than a scan on the first query and far less than sorting, gets cheaper per query with use, and stays cumulatively cheaper than sort-then-search until about 10^5 queries; that only the queried ranges get organized is not tested | Idreos, Kersten and Manegold (2007), LIT-1090, read in NOTE-892. Each range select splits, in place, the pieces of a column copy that hold its bounds and records the boundaries in an AVL tree, so later queries touch only edge pieces. In MonetDB on 10^7 values the first such select took 0.38 s against 0.27 s for a scan and about 3.3 s for sort-then-search, later selects 10 to 100 microseconds, and sorting overtook cracking in total only after about 10^5 queries. Every workload is uniformly random, so the paper’s claim that only ranges of interest get organized is asserted from the mechanism, not measured; there is no cost model and no rule for when a reorganization pays. | Active |
| THEORY-338 | For a list searched from the front, where reaching the i-th item costs i, moving each found item to the front costs at most twice what any rule costs on the same sequence, including rules that know the future (four times counting its own moves), a fixed order by access frequency is within no constant factor, and paying to rearrange ahead of need never helps; for paging, no online rule beats the offline optimum by less than n/(n − n_MIN + 1), and LRU meets that bound | Sleator and Tarjan (1985), LIT-1093, read in NOTE-903. With no probabilistic assumption, move-to-front on a sequentially scanned list is within 2 of the best algorithm in its class on every sequence, the rival being free to rearrange as it goes and to know the whole future; a list sorted once by frequency, transpose and frequency count are not within any constant; and any algorithm can be replaced by one no more expensive that makes no paid rearrangement (Theorem 3). For paging the online price of not knowing the future is n/(n − n_MIN + 1), the size of fast memory when the memories are equal. It is one list, or one two-level memory, with uniform items: it says nothing about bins, partitions or search that is not a scan. | Active |
| THEORY-340 | For answering membership in a static set of n keys with the fewest worst-case cell reads, sorted order with binary search is optimal only when the key universe exceeds a Ramsey-number threshold and table cells may hold nothing but stored keys or pointer symbols; it is beaten for small universes, and by two probes once one cell may hold an encoded value | Yao (1981), LIT-1097, read in NOTE-891. In the setting later called the cell-probe model, where only cells read are counted and both the arrangement and the adaptive search are arbitrary, ⌈lg(n+1)⌉ probes are needed by any scheme whose cells hold only keys of the set or a fixed stock of pointer symbols, once the universe is astronomically large (Theorems 1 and 1′). One probe suffices for m ≤ 2n − 2 (Theorem 2), and with one extra cell holding any value two probes suffice for m ≥ 2^{16n²} (Theorem 3). Building the table is free, so the paper prices lookup only and says nothing about whether sorting pays for itself. | Active |
| THEORY-341 | Inferring not-P from failure to prove P is a deduction only under two separate conditions: Clark shows that when every branch of the search for a proof of P ends in failure, not-P is a theorem of the completed database, and a search that does not finish licenses nothing; Reiter’s closed-world assumption, adding the negation of every ground atom the database does not entail, keeps a consistent Horn database consistent and can make a disjunctive one inconsistent | Clark (1978), LIT-1087, read in NOTE-894, and Reiter (1978), LIT-1088, read in NOTE-899 from his 1977 workshop report. Clark proves negation as failure sound with respect to the completed database (the clauses read as if-and-only-if definitions, plus axioms that distinct names denote distinct things), given a finite failure tree for some selection rule; it is incomplete in general. Reiter defines the closed-world assumption by entailment, reduces closed-world query evaluation to open-world atomic queries when the assumption is consistent, and shows it consistent for Horn and definite databases but not for Pa ∨ Pb. Soundness here is relative to the completion, not to the world, and neither paper says anything about a search cut short by time. | Active |
| THEORY-344 v2 | 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 | Athanassoulis et al. (2016), LIT-1085, read in NOTE-888. A six-page vision paper defines read, update and memory amplification and conjectures that an access method optimal on one cannot be optimal on both others. Its evidence is three one-paragraph propositions about extreme designs on an integer array, a qualitative triangle and a table of asymptotic I/O costs. The formal statement asserts only some lower bound on the third overhead, which every design has. The extremes are not symmetric: the memory-minimal design is also update-minimal. Build cost, workload and time are outside the triangle. | Active |
| THEORY-345 | Choosing indexes for a known mix of queries and updates, to minimize query cost plus a per-index upkeep, is NP-hard as the number of attributes and query types grows, and the tools built for it choose one stored order and a set of secondary indexes per table by searching configurations costed with the query optimizer’s own estimates, optimal at best relative to those estimates, with no proved guarantee for their heuristics and no term for the one-time cost of building | Piatetsky-Shapiro (1983), LIT-1089, read in NOTE-902; Finkelstein, Schkolnick and Tiberio (1988), LIT-1084, read in NOTE-898; Chaudhuri and Narasayya (1997), LIT-1083, read in NOTE-900. Minimum set cover reduces to choosing single-attribute secondary indexes under a known workload with a fixed upkeep per index. DBDSGN chooses the one clustered order and the secondary indexes per table against a frequency-weighted sum of access, update and upkeep costs plus storage, read from the System R optimizer; AutoAdmin picks at most k indexes by greedy search over what-if indexes. The model is steady state over a fixed workload: it prices upkeep against per-query savings, not a one-off build or sort against later lookups, and its optimality is relative to the optimizer’s estimates, never to measured execution. | Active |
| THEORY-348 | When staying in one state costs a fixed amount per request and leaving it costs a fixed one-time price, switching once the extra cost paid for staying equals that price is within 2 of the offline optimum on every request sequence, and no deterministic online rule does better; with a third option the best guaranteed ratio rises to 3 | Karlin, Manasse, Rudolph and Sleator (1988), LIT-1096, read in NOTE-893. A snoopy cache holding a shared block pays 1 per write to keep it current, or drops it and pays p to fetch it again on a later read. Dropping once the writes charged since the last read have cost p is strongly 2-competitive (Theorems 3.1 and 4.1); with a read- or write-through option the deterministic lower bound is 3 (Theorem 3.3). It is the first competitive analysis of a rent-or-buy decision, though the paper never uses the name, and its instance is when to stop maintaining a copy. Prices are fixed and known, the guarantee is worst case only, stale reads are forbidden rather than priced, and the authors call the practical significance “unclear”. | Active |
| THEORY-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 | Gupta and Mumick (1999), LIT-1092, read in NOTE-890, with the proofs of the journal version (2005), LIT-1080, read in NOTE-901, and the superadditivity first noted by Gupta (1997), LIT-1091, read in NOTE-889. Minimizing query cost subject to a cap on total maintenance time, one stored view can make another cheaper to keep current, so saving per unit of upkeep is not monotone and single-view greedy fails without bound (Example 2). Grouping views into inverted tree sets restores a 1 − 1/e guarantee, proved in 2005 (Theorem 8), for OR view graphs only, bicriteria, under an assumption on the optimum, with greedy stages exponential in general. The proof does not treat the negative effective costs the paper allows. Upkeep is a budget, not a cost traded against savings, and staleness and build cost are not modelled. | Active |
| 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 | Harinarayan, Rajaraman and Ullman (1996), LIT-1094, read in NOTE-895; Gupta (1997), LIT-1091, read in NOTE-889; Gupta and Mumick (2005), LIT-1080, read in NOTE-901. A stored answer is worth the saving on every query derivable from it, less what answers already stored save, and greedy on that marginal saving gets 1 − ((k−1)/k)^k ≥ 1 − 1/e of the best saving for k views; under a space budget the same holds against the optimum in the space the greedy actually uses (up to one view over), or 0.63 − f when no view takes more than a fraction f of the budget. The bound is on saving against storing the base view alone, not on query cost, and it holds only with no updates: once upkeep enters the objective it is proved only for AND graphs in which every view is queried more often than it is updated. | Active |
| THEORY-361 | When every object but one has full grade in exactly one of two attribute-sorted lists and the one has full grade in both, finding it under min takes at least about half the objects’ worth of accesses for any algorithm that only reads the lists from the top and looks up objects already seen, and, with the tied objects in random order, about as many in expectation even for algorithms that may look up any object; a query on one attribute alone costs k accesses whatever the number of objects | Fagin, Lotem and Naor (2001; full version read as arXiv cs/0204046v1), LIT-1115, read in NOTE-924: Example 6.3 and Theorem 6.4, the paper’s proof that no algorithm is instance optimal once lucky lookups are allowed. With 2n + 1 objects, n + 1 high in each list and only one high in both, an algorithm that cannot guess must read at least n + 1 entries before it sees the target, and on a randomized family any deterministic algorithm needs at least n + 1 accesses in expectation. The paper uses the case to bound instance optimality. That it explains linear conjunction-search slopes in human vision is the record’s analogy, not the paper’s claim. | Active |
| THEORY-362 v2 | For nonrecursive Datalog or SQL views with safe stratified negation and stratified aggregation, under set or duplicate semantics, storing with each derived tuple only the number of its derivations suffices to maintain the view under insertions and deletions of base tuples: signed counts propagated through delta rules stratum by stratum give each tuple’s change as its new count minus its old, a tuple leaves when its count reaches zero, and a MIN or MAX group whose extreme is deleted is recomputed from the stored lower stratum | Gupta, Mumick and Subrahmanian (1993), LIT-1114, read in NOTE-915. Algorithm 4.1 evaluates delta rules in order of rule stratum and combines signed counts; Theorem 4.1 states it derives count(t^ν) − count(t) for every tuple, and Theorems 6.1 and 6.2 extend this to negated and aggregate subgoals. Its cost is argued to be close to evaluating the view and is not measured. All three theorems are stated without proof in this extended abstract. It does not say that a count suffices when support is cyclic: the paper keeps counting to nonrecursive views. | Active |
| THEORY-363 | For finding the top k objects under a monotone combining function from m lists each sorted by one attribute, with sorted and random accesses the only costs, the threshold algorithm is correct and on every database costs at most a constant times what any correct algorithm that makes no wild guesses costs; the constant is m + m(m−1)c_R/c_S, no deterministic algorithm does better when the function is strict, and once wild guesses are allowed no algorithm has such a guarantee on databases with ties | Fagin, Lotem and Naor (2001; full version read as arXiv cs/0204046v1), LIT-1115, read in NOTE-924. The threshold algorithm reads m attribute-sorted lists in parallel, looks up each new object’s other grades, and stops when k seen objects score at least the combined score of the last grades read. For every monotone combining function it is instance optimal among correct algorithms that make no wild guesses (Theorem 6.1), with ratio m + m(m−1)c_R/c_S, tight for strict functions (Corollary 6.2, Theorem 9.1). It is a guarantee relative to a class of algorithms under an access-cost model. It does not say that top-k queries are cheap: the absolute cost depends on the data, and is linear in N for some conjunctive queries. | Active |
| THEORY-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 | Olston and Widom (2000), LIT-1117, read in NOTE-922. In TRAPP a cache holds intervals that sources keep valid by pushing a refresh whenever a value escapes, and each query names a width R its answer may have. The SUM answer is the sum of the intervals, so meeting R at least read cost is knapsack (profit = read cost, weight = width, capacity = R); COUNT under a predicate has a greedy optimum. Staleness becomes bounded imprecision, never error, and only the query-time cost of buying it down is optimized: the sources’ upkeep, the choice of interval widths and any cost of imprecision are outside the model. The MIN rule’s optimality proof is in an unread technical report. | Active |
| THEORY-365 v3 | In one study of a stack of proximity graphs on nested random subsets of the data, each element’s top layer drawn geometrically, greedy search on uniform random data in 8 dimensions needed a number of distance computations that grew no worse than logarithmically with the number of items and stayed below a single-layer navigable graph’s at every size tested, and in 4 dimensions the beam width needed for a fixed recall saturated; the logarithmic bound is derived only for exact Delaunay graphs of bounded degree, which the index does not build, and on 200 million SIFT vectors the measured growth departs from it | Malkov and Yashunin (2020), LIT-1098, read in NOTE-916 from arXiv v4. They build an index like a skip list, with proximity graphs in place of linked lists, and argue that search costs a constant per layer over O(log N) layers. That holds if each layer is an exact Delaunay graph of bounded mean degree. HNSW does not build such graphs, and Delaunay degree grows exponentially with dimension. For the graphs it does build, cost no worse than logarithmic is measured on uniform random data at d = 8, a saturating beam width at d = 4, and at d = 128 (200M SIFT) the growth departs from a logarithm. A proof for the graphs HNSW builds is QUESTION-187. The paper gives no worst-case bound and no recall guarantee. Construction is argued to cost about N searches. | Active |
| THEORY-367 v2 | For SPJU relational queries, which Buneman, Khanna and Tan’s tree model encodes, the minimal witnesses of an output tuple, the inclusion-minimal sets of source facts from which the query still derives it, are the minimal sets matched by single derivations and so are the same for every equivalent query, while where-provenance, the source location a value was copied from, can differ between equivalent queries | Buneman, Khanna and Tan (2001), LIT-1104, read in NOTE-920. Two meanings of the provenance of output data: why it is there (the witness basis, the source structures matched by each valuation that produces it) and where a value came from (the source paths bound to the output variable). The first is preserved by the paper’s rewrite system and, cut down to minimal witnesses, agrees across equivalent queries with equality conditions; the second is shown by example to depend on how the query is written. Proofs are omitted. It is not a theory of revision: additions to the source, negation, aggregation and strengths of support are all outside it. | Active |
| THEORY-368 v2 | On two-dimensional point sets constructed for the purpose, the authors’ code for fast-preprocessing DiskANN, HNSW and NSG, at parameters from the original papers, in most cases found none or few of a query’s five nearest neighbours until the search queue held about 10% of the points, for n from 10⁵ to 2·10⁶, and at that queue length ten graph indexes averaged recall@5 between 0.0 and 0.42; this is shown by experiment on one query per instance, and no theorem bounds these algorithms | Indyk and Xu (2023), LIT-1112, read in NOTE-910. The instances are grids of points in the plane in which a large cluster, reached first from the start vertex, lies closer to the query than the only points linked to its nearest neighbour. At queue length 0.1n, average recall@5 ranged from 0.0 (DiskANN) to 0.42 (KGraph). The paper calls the query time linear and says so “empirically”; the only argument beyond the experiment is an informal Ω(n/R) for DiskANN’s fast build. It does not show that these indexes fail on natural data or natural queries. | Active |
| THEORY-369 v2 | Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance and a fixed number of points, an optimal nearest-neighbour search over any index that partitions points into blocks or convex clusters of at least two points must read a fraction of blocks that grows toward all of them as dimension rises; with a five-fold sequential advantage for scanning, estimates put the crossover at about 15–26 dimensions for rectangular and spherical bounding regions, and two tree indexes measured on 50,000 points lost to a scan beyond about 10 | Weber, Schek and Blott (1998), LIT-1107, read in NOTE-919. Under uniformity and independence, with the expected nearest-neighbour distance used as every query’s radius and integrals evaluated by Monte Carlo, the fraction of blocks read passes the 20% line at about d = 15–20 for rectangular regions and 26 for spherical ones. A crude bound for any convex clustering puts it below 610. The often-quoted “around 10” is the measured crossover for an R*-tree and an X-tree. The VA-file, a scan of compact per-vector approximations, is the paper’s alternative. Nothing is shown for data of low intrinsic dimension, and the finite-dimensional bounds are not rigorous as stated. The asymptotic statement, at fixed N and for clusters of two or more points, is proved by the record by a concentration argument. | Active |
| THEORY-371 | For conjunctive queries without equality or comparisons, two queries are equivalent exactly when homomorphisms run both ways between the queries read as small databases, every such query has a minimal equivalent query unique up to isomorphism obtained by deleting atoms, and evaluating one against a database is NP-complete when the query is part of the input | Chandra and Merlin (1977), LIT-1111, read in NOTE-907. Reading a conjunctive query as its natural model, equivalence becomes a pair of homomorphisms (Lemma 13), the minimal equivalent query is unique up to isomorphism (Theorem 12), and evaluation with the query as input is NP-complete (Theorem 7), as is deciding whether one query is a folding of another (Theorem 11). The paper states equivalence, not containment, and does not state that containment or equivalence is NP-complete; those are corollaries later work attributes to it. Nothing here reaches queries with equality, comparisons, negation or union. | Active |
| THEORY-372 | For c-approximate near-neighbour search over n points in Euclidean space, space n^{1+ρu+o(1)} and query time n^{ρq+o(1)} are achievable on any data set whenever c²√ρq + (c²−1)√ρu ≥ √(2c²−1) (c√ρq + (c−1)√ρu ≥ √(2c−1) in Hamming space), and no list-of-points structure, the model of known data-independent hashing, does better on random instances; without that model the curve is matched only at query time n^{o(1)} by one or two cell probes | Andoni, Laarhoven, Razenshteyn and Waingarten (2017), LIT-1120, read in NOTE-918 from the arXiv full version. A data-dependent tree of spherical caps, with different thresholds for filing points and for routing queries, realizes every pair of exponents on the curve, for worst-case data, with constant success probability; the equal-threshold point is LSH. On random instances with d = ω(log n), list-of-points structures cannot beat the curve (a lower bound the paper calls conditional), and one- or two-probe cell-probe structures need n^{(c/(c−1))²−o(1)} words, the curve’s space at ρq = 0. Optimality for data-dependent schemes, for more probes, and for d = Θ(log n) is not shown. The curve prices space against per-query time for one query at a time; it has no workload and no build cost beyond space. | Active |
| THEORY-373 | For positive relational algebra on relations whose tuples are annotated from a commutative semiring, every query’s annotated answer equals its answer over provenance polynomials N[X] in the input tuple ids, evaluated at the input annotations, so set, bag, c-table and event-table semantics all factor through the polynomials; revaluing inputs can remove output tuples but never add them, and nothing is shown for negation, difference or aggregation | Green, Karvounarakis and Tannen (2007), LIT-1110, read in NOTE-913. Union and projection add tags, join multiplies them; the usual RA identities hold exactly when the tags form a commutative semiring, and a map of tags commutes with every query exactly when it is a semiring homomorphism. The polynomials N[X] are the free commutative semiring, so the annotated answer in any semiring is the polynomial answer evaluated at the input annotations (Theorem 4.3). It is a sufficiency result for revisions that re-annotate existing inputs, not a minimality result, and it excludes added facts and every nonmonotone operation. | Active |
| THEORY-374 v2 | Given views with conjunctive definitions, deciding that they answer a conjunctive query exactly is NP-complete in the size of the query and definitions, while a maximally-contained rewriting can be built in time polynomial in that size without saying whether it is exact; and finding all certain answers from the stored contents is polynomial in their size under the open-world assumption when the views are conjunctive and the query conjunctive or datalog, but co-NP-hard in that size under the closed-world assumption even for conjunctive views and queries | Halevy (2001), LIT-1116, read in NOTE-921, reporting Levy et al. 1995 (LIT-1100, read), Duschka, Genesereth and Levy, and Abiteboul and Duschka 1998 (not read). Reuse of stored views is graded: certifying an exact rewriting is NP-complete in the size of the definitions, building everything the views give (maximally contained) is polynomial, and the certain answers can cost a co-NP-hard search in the size of the stored data. Promoted 2026-10-21 on a re-derivation of the last two parts (ADR-047 v2); the primary papers they come from are unread. None of it prices recognition for definitions outside conjunctive queries and datalog, or says how costly recognition is on typical queries. | Active |
| THEORY-375 v2 | In one simulator evicting whole query-shaped cache regions, no replacement value function was best on every workload: a value based on distance from the current query beat LRU where queries clustered around a hot region or wandered with loops, while MRU was best on regular cyclic paths, by up to 2.3 times over the distance value and 9.6 times over LRU; none of the functions weighs what a region would cost to fetch again, and nothing is proved | Dar, Franklin, Jónsson, Srivastava and Tan (1996), LIT-1113, read in NOTE-904. With semantic regions as the unit of eviction, Manhattan distance from the most recent query beat LRU at every query size on a skewed selection workload, and a directional variant was best or tied on random map paths (LRU within 1.06) and on lollipop paths circling a square five or more times; MRU won on a single circuit and on plain squares (Manhattan 2.29 and LRU 9.57 on the 32 × 32 square). The study is simulation only, with synthetic paths and no refetch cost in any value; it shows that the best forecast of reuse depends on the workload, not that semantic distance is a robust rule. | Active |
| THEORY-376 v2 | In a simulated single-client, read-only database answering selection queries on one relation, describing cached data by the predicates of past queries let each query be answered partly from cache, with only the remainder Q ∧ ¬V sent to the server; this matched page caching on a clustered index, beat it on an unclustered one, and, on an unindexed attribute with a disk cache, answered over 60% of 1% queries without contacting the server; the cost of computing probe and remainder queries was not charged | Dar, Franklin, Jónsson, Srivastava and Tan (1996), LIT-1113, read in NOTE-904. In one simulator (one client, one server, a 10,000-tuple relation, 90% of queries in a hot 10%), semantic caching performed about like page caching on a clustered index, far better on an unclustered one, and on an unindexed attribute answered over 60% of 1% queries with no server scan. Space overhead depended on coalescing: 55 regions and about 275 factors for 1% queries without it. The result is measured, not proved; updates, joins and the CPU cost of reasoning about the cache’s contents were left out, so it does not show that predicate-described storage pays when finding the reusable part is costly. | Active |
| THEORY-377 v2 | In Olston, Loo and Widom’s simulations, a rule that multiplies a cached interval’s width by 1 + α on a pushed refresh with probability min{ρ, 1}, and divides it by 1 + α on a query’s exact fetch with probability min{1/ρ, 1}, settled within 1% of the best fixed width on one random walk and within 5% over eight walk settings; on a 50-host network-traffic trace, restricted to exact copies, it almost matched a tuned adaptive cache-or-not rule, and with a 50-value cache, where queries tolerated imprecision, it cost less; that it converges to the best width is argued, not proved | Olston, Loo and Widom (2001), LIT-1109, read in NOTE-912. The rule treats a pushed refresh as “too narrow” and a fetch as “too wide”, weighted by ρ = 2C_vr/C_qr, and needs no measurement of update rates, query rates or precision demands. Within 1% of the best fixed width on one random walk and within 5% over eight settings; with α = 1 and thresholds it tracked a 50-host traffic trace. With every copy forced exact it decided cache-or-not as well as an adaptive exact-caching rule, and did better where imprecision was allowed, except with a small cache. Convergence is argued from the balance condition only, all evidence is the authors’ simulation, and there is no worst-case guarantee. | Active |
| THEORY-378 | When items change as independent Poisson processes with known rates and a fixed total refresh rate is shared among them, refreshing every item equally keeps the copy at least as fresh and at most as old, averaged over time, as refreshing in proportion to change rate, for any spread of rates; the freshness-optimal share rises and then falls with change rate and gives nothing to items that change too fast for the budget | Cho and Garcia-Molina (2000), LIT-1119, read in NOTE-906. Freshness is the fraction of items equal to their source, age the mean time since an unseen change, both averaged over time and over equally weighted items. With fixed-interval refresh, uniform refresh is never worse than proportional on either measure, by convexity (proof in the authors’ technical report). Under a fixed budget the freshness-optimal allocation starves the fastest-changing items; the age-optimal one refreshes them somewhat more. It prices staleness as an objective under a fixed budget: there are no reads, no query savings, no build cost and no cost of a stale use, so it is a staleness term and not a model trading staleness against upkeep. | Active |
| THEORY-379 v2 | Fagin’s Algorithm finds the top k of N objects held in m attribute-sorted lists under any monotone combining function, and when the lists’ orderings are independent with at least m − 1 of them uniformly random it does so with O(N^((m−1)/m) k^(1/m)) sorted and random accesses with arbitrarily high probability; with dependent orderings the bound can fail | Fagin (1996/1999), LIT-1108, as reported by Fagin, Lotem and Naor (2001), LIT-1115, read in NOTE-924. Fagin’s own paper could not be obtained, and the reporting paper declines to describe the probability model (“off track”). It does correct one misreading: the only probabilistic assumption is independence of the lists’ orderings, not a uniform distribution of grades. For two lists the bound is √(Nk). It does not hold for anti-correlated attributes, where any algorithm can need about half the objects. | Active |
| THEORY-380 v2 | For datalog over a finite input instance annotated from a commutative ω-continuous semiring, with an answer’s tag defined as the sum over its derivation trees of the product of its leaves’ tags, the tags are the least fixed point of a finite polynomial system and factor through formal power series N∞⟦X⟧ in the input tuple ids; an answer tuple’s series has an infinite coefficient exactly when one of its derivation trees contains a tuple lying on a cycle of unit rules | Green, Karvounarakis and Tannen (2007), LIT-1110, read in NOTE-913. A recursive query can derive a tuple in infinitely many ways, so polynomials do not suffice and the semiring needs infinite sums. With ω-continuous semirings and the provenance semiring N∞⟦X⟧ the paper states the analogues of the relational results: a fixed-point characterization (Theorem 5.6), factorization (Theorem 6.4), and a test for infinite coefficients (Theorem 6.5), with algorithms that decide finiteness and compute coefficients. Proofs are not given. Plain N and N[X] are excluded, the provenance can be an infinite object held only as equations, and negation remains outside. | Active |
| THEORY-381 | In the cell-probe model, a near-neighbour structure on n random points that answers in t probes with m cells of w bits must satisfy m^t·w/n ≥ the robust expansion of the metric’s neighbourhood graph at measure 1/m^t (and (mwt/n)^t ≥ its vertex expansion if deterministic), so in expanding spaces such as the hypercube fast queries need space polynomially larger than the data; the bounds are average case, approximate, and fall off exponentially in t | Panigrahy, Talwar and Wieder (2010), LIT-1102, read in NOTE-914 from the arXiv preprint. For graphical neighbour search, to which decision approximate near neighbour reduces, on data drawn so that neighbourhoods rarely overlap: deterministic t-probe structures satisfy (mwt/n)^t ≥ Φv and m^t·t·w/n ≥ Φv(1/m^t); randomized ones satisfy m^t·w/n ≥ Φr(1/m^t, γ/t) and (mwt⁴/n)^{2t} ≥ Φr(1/m, γ/t). On the hypercube this gives space n^{1+Ω(1/(ct))} at approximation c and n^{Ω(1/(tε²))} at 1 + ε; a one-probe structure matches on Cayley graphs; low-contention dynamic structures need update time at least Φr(τ, 1/(4t²)) over poly(t). Tight only for constant t; nothing about worst-case or structured data, workloads or build time. | Active |
| THEORY-382 v2 | When a web server keeps each page fragment either cached and invalidated by updates or stored and refreshed after them, materializing trades staleness for response time, and in one synthetic simulation with fixed costs a periodic greedy that moves a capped number of fragments between the two, to keep the share of fresh fragments served above a set threshold, tracked that threshold by the authors’ reading of its curves, answered faster than caching alone and recovered from overload by materializing everything; no bound on its distance from the best plan is shown | Labrinidis and Roussopoulos (2003), LIT-1105, read in NOTE-911. Quality of Data is the share of fresh fragments in served pages; OVIS(θ) estimates per fragment the change in response time (hits and misses against refresh load) and in QoD from switching policy, and each period greedily switches up to MAX_CHANGE fragments to spend a QoD surplus on speed or buy back a deficit. The paper asserts the greedy step is best under the cap and proves nothing; the evidence is one simulator with uniform costs and no comparison with an optimum. The reading the evidence does not support: that this is a joint cost model of build, upkeep, staleness and savings. Staleness is a user-set threshold, not a price, and switching and storage are free. | Active |
| THEORY-383 v2 | On one Apache and Informix server answering cheap indexed selections over 1000 pages, a page whose query result was stored in the DBMS and refreshed on every update answered more slowly than one recomputed on each request at five or more updates per second, which the authors explain by reading the stored result costing about as much as recomputing it and its refresh loading the same DBMS, while a finished page stored at the web server and rewritten on every update answered 10 to 230 times faster than either | Labrinidis and Roussopoulos (2000), LIT-1118, read in NOTE-908. Three ways to serve a database-generated page under online updates, with no stale reads allowed: compute on request, store the query result in the DBMS, or store the finished page at the web server. A cost model sums access and update costs by frequency; the per-page selection problem is stated and not solved. On their testbed the page stored at the web server won at every load, and the result stored in the DBMS lost to recomputation at five or more updates per second. The reading the evidence does not support: that storing an answer pays whenever it is reused enough. Where it is stored decided the outcome, and the generalization to other systems is the authors’ expectation, not a measurement. | Active |
| THEORY-384 | A nearest-neighbour graph built by pruning each point’s links against all other points with a factor α > 1, so that from every point some link is α times closer to any other point, lets greedy search from any start reach a ((α+1)/(α−1) + ε)-approximate nearest neighbour in O(log_α(∆/((α−1)ε))) steps of cost O((4α)^d log ∆), for doubling dimension d and aspect ratio ∆; the ratio is tight and the dependence on ∆ cannot be replaced by one on n, and the build takes O(n³) time done naively | Indyk and Xu (2023), LIT-1112, read in NOTE-910. Proved for DiskANN’s “slow preprocessing” build, not the build DiskANN implements. The guarantee rests on one property of the graph (α-shortcut reachability, α > 1), gives a constant approximation, not exact search, is logarithmic in the aspect ratio ∆, which can exceed n by far, and has a per-step cost exponential in the doubling dimension. HNSW and NSG prune with α = 1 and are not covered. | Active |
| THEORY-385 v2 | In HNSW over 10-dimensional data in 100 isolated clusters, linking each new item to its nearest neighbours leaves part of the bottom layer unreachable from the entry point and caps recall well short of 1 however wide the query search, while linking a candidate only when it is nearer the new item than to any neighbour already kept keeps that layer connected and reaches recall near 1 with about half the links; on uniform data at 10 and 64 dimensions the two rules differ little; shown in Malkov and Yashunin’s own tests on 10 million points and in an independent re-run on 30,000, which found the nearest-neighbour rule capped at a recall@10 of 0.72 to 0.83 against 0.999, at matched build cost too | Malkov and Yashunin (2020), LIT-1098, read in NOTE-916. In HNSW, each new element’s neighbours are chosen either as its M nearest candidates or by a pruning rule that keeps a candidate only if it is nearer the new element than to any neighbour already kept, a rule related to the relative neighbourhood graph. On 10M random d = 10 vectors in 100 isolated clusters, nearest-neighbour links failed to reach high recall and the pruning rule did not. In every test reported, the rule was at least as good. Its gain was largest at low dimension, at high recall, and on clustered data, and small on uniform or very high-dimensional data. These are the authors’ benchmarks: one clustered dataset, synthetic, with no independent replication in this reading. Re-run independently at smaller scale on promotion (2026-10-20), with the same result. | Active |
| THEORY-386 | When a cached interval of width W is kept valid by its source, which pushes a refresh at cost C_vr whenever the value leaves it, and queries fetch the exact value at cost C_qr whenever it is too wide, and the chances of the two per step go as 1/W² and as W, the expected refresh cost is least at W* = (ρK₁/K₂)^(1/3) with ρ = 2C_vr/C_qr, where ρ times the chance of a pushed refresh equals the chance of a fetch | Olston, Loo and Widom (2001), LIT-1109, read in NOTE-912. The cost rate Ω(W) = C_vr·K₁/W² + C_qr·K₂·W is least where ρ·P_vr = P_qr. The minimum is calculus on assumed forms. P_qr ∝ W follows exactly from uniform precision demands; P_vr ∝ 1/W² comes from a Chebyshev bound on a random walk used as an estimate, and the paper’s simulation of a random walk measured both proportionalities. Staleness here is priced as refresh traffic: the source guarantees validity, so a stale read is imprecise but never wrong, and there is no build cost and no cost of a wrong or imprecise answer. | Active |
| THEORY-387 v2 | For positive recursive Datalog views under set semantics, deleting every derived tuple that has any derivation through a deleted base fact, then restoring each deleted tuple that still has a derivation from what remains, then adding what insertions derive, leaves exactly the tuples derivable from the new base (E − Δ⁻) ∪ Δ⁺, with no derivation counts stored; the extension to stratified negation and aggregation is asserted, not shown, and the size of the overestimate is not measured | Gupta, Mumick and Subrahmanian (1993), LIT-1114, read in NOTE-915. DRed runs stratum by stratum: semi-naive Δ⁻-rules compute an overestimate of deletions, δ⁺-rules put back those with a derivation in the reduced database, and Δ⁺-rules add insertions. Theorem 7.1 states the result contains t if and only if t has a derivation in (E − Δ⁻) ∪ Δ⁺; the proof is in a 1992 AT&T report the record has not seen. The paper asserts, and does not show, that DRed handles stratified negation, aggregation and rule changes, that it beats the PF algorithm by up to an order of magnitude, and that it is slower than counting on nonrecursive views. | Active |
| THEORY-388 | Locality-sensitive hashing answers approximate near-neighbour queries over n points with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, where ρ = ln(1/p1)/ln(1/p2) is set by how much more often near pairs collide than far ones and is at most 1/(1+ε) for approximation 1+ε in Hamming space, with constant success probability per query; the paper gives upper bounds only and proves no limit on what organizing can buy | Indyk and Motwani (1998), LIT-1106, read in NOTE-905 from the authors’ 1999 expanded version, compared with the STOC text. A hash family under which points within r1 collide with probability at least p1 and points beyond r2 with at most p2 gives n^ρ random tables, each storing every point: O(dn + n^{1+ρ}) space and O(n^ρ) hash evaluations per query, ρ = ln(1/p1)/ln(1/p2), for the decision version, which ring-cover trees connect to approximate nearest neighbour with polylog overhead. Bit sampling gives ρ ≤ 1/(1+ε) in Hamming space and, by embedding, ℓ_p for p in [1, 2]; the STOC text states 1/ε and only for ε > 1. Grid bucketing gives Õ(d) queries for n·O(1/ε)^d preprocessing. Preprocessing is counted as space. Nothing is proved about whether these exponents can be beaten. | Active |
| THEORY-389 | For conjunctive queries and views without comparison predicates, a stored view can be used in an equivalent rewriting of a query exactly when the view’s body maps homomorphically into the query’s, a minimal rewriting needs no more literals than the query, and deciding whether a rewriting shorter than the query or one using only the views exists is NP-complete in the size of the query and view definitions; with comparisons in both, deciding whether any rewriting uses the views is Π2p-complete | Levy, Mendelzon, Sagiv and Srivastava (1995), LIT-1100, read in NOTE-909. Every use of a view in an equivalent rewriting comes from a containment mapping from the view into the query (Proposition 3.1); without comparisons a locally minimal complete rewriting has at most as many literals as the query (Lemma 3.5), which puts the problems in NP, and they are NP-complete (Theorems 3.7, 3.9, 3.10), with two independent sources of hardness. The results are worst case, in the size of the definitions rather than the stored data, for equivalent rewritings under set semantics only; they do not say recognizing reuse is costly in practice, and they do not cover contained (partial) rewritings. | Active |
| THEORY-815 | Layering a navigable small-world graph on nested random subsets of the data, with links separated by length scale and each layer’s degree capped, makes greedy nearest-neighbour search cost grow logarithmically with the number of items on data of low intrinsic dimension, where the single-layer graph’s cost grows polylogarithmically | Malkov and Yashunin (2020), LIT-1098, read in NOTE-916, argue that HNSW’s hierarchy is what makes greedy search logarithmic: constant cost per layer over O(log N) layers, against the polylogarithmic cost of their earlier flat graph. The record holds as measured, in THEORY-365, logarithmic-or-better cost on uniform data in 8 dimensions and a saturating beam width in 4. The bound is derived only for exact Delaunay layers, which HNSW does not build, and on 200 million SIFT vectors the paper’s own scaling departs from a logarithm, so the thesis is stated for low intrinsic dimension. | Proposed |
| THEORY-832 | For strict combining functions and m attribute-sorted lists of N objects whose orderings are probabilistically independent, no correct top-k algorithm does essentially better than Fagin’s Algorithm in the worst case with high probability: every one needs on the order of N^((m−1)/m) k^(1/m) accesses | Fagin (1996/1999), LIT-1108, as reported by Fagin, Lotem and Naor (2001), LIT-1115, Sections 1 and 3, read in NOTE-924: “his algorithm is optimal with high probability in the worst case if the aggregation function is strict … and if the orderings in the sorted lists are probabilistically independent.” Strict means the combined grade is 1 exactly when every grade is 1. Not read in the original; not re-derived. | Proposed |
| 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 | The RUM conjecture as its authors intend it, filed beside THEORY-344 by the status review of 2026-10-30 (ADR-065 §3; ADR-047 kind 1). THEORY-344, Active, reports the conjecture and what its formal wording and toy extremes do and do not show; whether the trade holds, quantified, is this entry’s question. | Proposed |