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).
12 of 371 QUESTION documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| QUESTION-114 | Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks? | The LEGO parable (CASE-094) is QUESTION-095’s trade in its plainest form. Sorting spends search once, against retrievals later, and leaves the result in the world, as the cockpit’s speed bugs do. CLAIM-310 adds that one set of bins realizes one partition, chosen against a query mix. A database table is stored in one physical order, and every further index costs space and work on every insert. Choosing indexes for a workload is a studied problem with explicit cost models. This asks whether that model is the one QUESTION-095 is looking for. | Open |
| QUESTION-187 | Does greedy layered search on the graph HNSW actually builds take expected O(log N) distance computations to a stated recall, under a stated condition on the data such as bounded doubling dimension? | The promotion condition formerly on THEORY-365, moved here when THEORY-365 was narrowed to what LIT-1098 measured and promoted on 2026-10-19 (ADR-047 v3). The paper derives O(log N) search only for exact Delaunay layers of bounded degree. It measures logarithmic scaling only at d = 8 and saturating ef only at d = 4, and at d = 128 its scaling departs from a logarithm. | Open |
| QUESTION-188 | Is delete-and-rederive correct for recursive Datalog views with stratified negation and aggregation, and how large is its overestimate of deletions against the deletions actually needed? | Filed when the promotion audit (batch 042, ADR-047 v2) narrowed and promoted THEORY-387. Theorem 7.1 of Gupta, Mumick and Subrahmanian (LIT-1114) was re-derived for positive recursive Datalog under set semantics. The paper asserts the extension to stratified negation and aggregation and leaves its proof to an unseen 1992 report; it measures no overestimate. This question holds both. | Open |
| QUESTION-194 | How far is a periodic greedy that switches a capped number of page fragments between caching and materializing, to keep the share of fresh fragments served above a threshold, from the best plan that meets the same threshold? | The promotion condition formerly on THEORY-382. THEORY-382 was promoted on 2026-10-19 (ADR-047 v3) on what Labrinidis and Roussopoulos measured: in one synthetic simulation with fixed costs, their OVIS greedy tracked the freshness threshold, answered faster than caching alone and recovered from overload. No run compares it with the best plan, and its optimality under the cap is asserted, not proved. | Open |
| QUESTION-224 | Is Bruno and Chaudhuri’s single-index online tuner within some constant, such as 3 + 2f, of the offline optimum on every workload whose per-statement savings and losses are at most a fraction f of the build cost? | The promotion condition formerly on THEORY-332. THEORY-332 was promoted on 2026-10-20 (ADR-047 v2) for the lower bound its construction proves: with every step at most fB, Online-SI can cost nearly 3 + 2f times the optimum, and one step above B makes the ratio unbounded. Whether any constant bounds it from above on such workloads is open. | Open |
| QUESTION-225 | Are why-provenance and, for traceable queries, where-provenance preserved by Buneman, Khanna and Tan’s rewrite system, and is traceability necessary for where-provenance to be preserved? | Formerly part of THEORY-367’s title. THEORY-367 was promoted on 2026-10-20 (ADR-047 v2) for what is re-derived: minimal witnesses are invariant across equivalent SPJU queries, and where-provenance is not. Whether the paper’s rewrite system preserves why- and where-provenance, and whether traceability is necessary, is open. | Open |
| QUESTION-227 | Does the widen-on-push, narrow-on-fetch rule for a cached interval’s width converge to within a stated factor of the best fixed width, and does it hold its cost against the best fixed width and an adaptive cache-or-not rule on data other than its authors’ traces? | The promotion condition formerly on THEORY-377. THEORY-377 was narrowed to Olston, Loo and Widom’s simulations and promoted on 2026-10-20 (ADR-047 v3). Whether their width-setting rule converges, and whether it holds up on other data, is open. | Open |
| QUESTION-230 | Do the released HNSW, NSG and fast-preprocessing DiskANN builds, run independently on Indyk and Xu’s published hard instances at the stated parameters, need a search queue of about a tenth of the points before recall@5 rises above zero, and does the same trap appear on natural data with adversarially chosen queries? | The promotion condition formerly on THEORY-368. THEORY-368 was promoted on 2026-10-20 (ADR-047 v3) for what Indyk and Xu’s one study measured. An independent replication on their instances, and the same test on natural data with adversarial queries, are open. | Open |
| QUESTION-237 | Does semantic caching keep its ordering against page caching once probe and remainder computation and region upkeep are charged, or in an implemented client-server system? | The promotion condition formerly on THEORY-376, moved unchanged when that account was narrowed and promoted on 2026-10-20 on the one simulation it rests on (ADR-047 v3). Open: whether semantic caching’s advantage survives charging the client for reasoning about what its cache holds. | Open |
| QUESTION-238 | Does database cracking keep its measured costs against a scan and an upfront sort in another implementation, measured over a long sequence of random range queries? | The promotion condition formerly on THEORY-333, moved unchanged when that account was promoted on 2026-10-20 on the one study it rests on (ADR-047 v3). Open: whether cracking’s measured first-query overhead, per-query convergence and break-even against sort-then-search hold outside Idreos, Kersten and Manegold’s MonetDB runs. | Open |
| QUESTION-340 | When does a cache replacement value based on distance from the current query beat recency-based eviction: does a competitive analysis, or an analysis under a stated distribution of query paths, say so, and do experiments in another system that vary cycle length relative to cache size recover the crossover with MRU? | The promotion condition formerly on THEORY-375, moved here when the status review of 2026-10-30 promoted it under ADR-065. Dar et al.’s crossover between distance and MRU is simulated on synthetic paths and not explained. | Open |
| QUESTION-347 | On another database and web stack with native materialized views and queries of graded cost, does a stored query result kept current on every update lose to recomputation exactly when reading it costs about as much as recomputing it and its refresh runs on the resource that serves requests, and win otherwise? | The promotion condition formerly on THEORY-383, moved here when the status review of 2026-10-30 promoted it under ADR-065. Labrinidis and Roussopoulos measured one testbed with cheap indexed selections; their cost model’s Eq. 9 was never evaluated against measurement. | Open |