nucleation

LIT-1086: The difficulty of optimum index selection

1 min read

Properties3
StatusUnfetched — filed 2026-10-15, not read. No NOTE is filed, and it stays Unfetched until it is read, not on merit. Lawful full texts exist but could not be fetched from this environment on 2026-10-15 ("found but could not be fetched"). Unpaywall, OpenAlex (W2058765797) and Semantic Scholar (CorpusId 1606952) all report it bronze open access, publishedVersion, at the ACM Digital Library (dl.acm.org/doi/pdf/10.1145/320289.320296); OpenAlex reports no repository full text. ACM returned HTTP 403 to every request from this environment (the /doi/pdf/, ?download=true, /doi/epdf/ and landing-page forms, by curl and by WebFetch). The Wayback Machine has no capture of the ACM PDF URL. A precursor exists as a Purdue technical report: Douglas E. Comer, "The Difficulty of Optimum Index Solution" [sic], Purdue Department of Computer Science Technical Report 77-248, 11 pp., in Purdue's institutional repository (docs.lib.purdue.edu/cstech/182; the record's date field, 1975, conflicts with the 1977 report number). The record page loaded, but its PDF (docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1181&context=cstech, and the /context/cstech/article/1181/viewcontent forms) returned a Cloudflare challenge (403) to curl, with and without browser headers and the landing page's cookie, and to WebFetch. The Wayback Machine holds a capture of that Purdue PDF (snapshot 20240708123022), but web.archive.org is blocked by this environment's egress policy ("Blocked by egress policy"; connection resets), and WebFetch refuses that host. Whether the technical report is the same text as the TODS article was not checked. Also tried: scholar.archive.org (no matching result), CORE (403 and 429), CiteSeerX (redirect, no record found), Google Scholar (no version other than ACM's surfaced), pdfs.semanticscholar.org (no file), cs.purdue.edu technical-report paths (404), and web searches for a course-hosted copy (none found). No shadow library was consulted. Finkelstein, Schkolnick and Tiberio 1988 (LIT-1084, read) cite it only as "Even a restricted version of the index-selection problem is in the class of NP-hard problems", so the record's description of it as proving "optimal index selection NP-complete" rests on secondary accounts, and its model, reduction and conditions are unconfirmed.
Version2
Tagsdatabases, mathematics

Graph View

Comer, D. (1978). The difficulty of optimum index selection. ACM Transactions on Database Systems 3(4), 440–445. DOI 10.1145/320289.320296

Key takeaways

Not read: no lawful copy could be fetched (status note). Until it is read, what it proves rests on secondary accounts, which disagree with how the record first described it.

Why this is here

QUESTION-114: is sorting a collection amortized search, and does physical database design give the joint cost model the question on amortized retrieval lacks?

Backlinks