Assessment 225: transporting a search position between stores

12 October 2026. Two-paper primary-proof review and a sharpened composition test. Construction 76 remains unchanged. No new native recognizer or native-language lower bound is claimed.

What the review changes

The missing operation is not merely finding two owners. It is carrying a source-specific search position to those owners before a literal query ends. Fractional cascading supplies a classical mechanism for transporting one search position through related catalogs. Its exact hypotheses expose what a native adaptation must still build and pay for.

A simple example isolates the issue. Regard stores as graph vertices and target names as graph edges. Selecting a store activates its vertex. A target is reachable precisely when at least one endpoint is active for the selected source. Each edge has only two owners, yet activating one high-degree vertex can change arbitrarily many target answers. Neither an endpoint-name directory nor eager enumeration automatically meets the deadline.

The next test is therefore an input-built, persistent version of this graph-activation interface, starting with full rows and no omissions. The review suggests carrying the already-read source key through the target route, rather than discovering owner names only at the end. This is a candidate mechanism, not a completed transfer.

Primary arguments studied

Chazelle and Guibas, 1986

Fractional Cascading: I. A Data Structuring Technique, Algorithmica 1, 133–162. The complete 30-page paper, including Appendix A, was studied from rendered-page OCR; ambiguous graph-transformation and rebuilding passages were checked against the scans.

A catalog graph has sorted catalogs and edge ranges. Local degree bounds the number of incident ranges containing a particular key. The same key is searched along a generalized path, which may be supplied online. Theorem 2 gives linear preprocessing/storage and query time $O(\log S+p\log d)$ for total catalog size $S$, path length $p$ and local degree $d$.

The proof uses sampled bridge pairs between augmented catalogs. Bounded gaps permit transfer of a located key; original-catalog successor pointers recover answers. Gap splitting propagates insertions. Separate time and space token arguments bound total construction. Star-tree replacement reduces high degree at a logarithmic traversal cost; gateway chains pay the initial search. The dynamic sections distinguish amortized insertion/deletion work from query guarantees. Rebuilding uses live query copies and a transcript, not free access to every historical version. Appendix A explicitly exhibits a large secondary-insertion cascade from one insertion. Thus its aggregate construction bound is not a strict arrival-time schedule.

Mehlhorn and Näher, 1990

Dynamic Fractional Cascading, Algorithmica 5, 215–241. An independent reviewer studied all 27 pages, including applications and the concluding persistence discussion; the parent checked the model and transfer claims.

Queries supply one atomic ordered key and a connected catalog subtree whose edge ranges contain it. Updates supply position pointers. Augmented lists maintain paired bridges and bounded block sizes. Dirty blocks undergo splitting/merging, possibly triggering further repairs. A block-defect potential bounds the total repair sequence. The underlying interval-list operations are cited primitives, not all proved within this paper.

With fixed local degree, the full-dynamic query bound is worst-case $O(\log(N+|E|)+s\log\log(N+|E|))$. The update bound from initially empty catalogs is aggregate $O(|E|+\sum_i\log\log(N_i+|E|))$. Here $N$ counts catalog entries and $s$ queried vertices, not encoded input symbols. Semi-dynamic simplifications do not supply native per-symbol worst-case updates. The applications explicitly charge graph-edge changes and balanced-tree rotations. The concluding connection to persistence supplies no immutable-old-top, strict-deadline compiler.

Why these are useful, and why direct transplantation fails

Both papers replace repeated global search by a maintained local correspondence. They therefore address the access cost that a semantic quotient alone omits. Their catalogs are not matching diagrams or positive-path interfaces from entry 129, and no entry-129 lower bound transfers through this comparison.

In the rejected two-stage design, the target key $q$ becomes an unrelated owner key $b$ before source lookup. A same-key bridge does not justify that change. But this does not rule out fractional cascading as a broader design idea. A different layout could keep the source name $a$ fixed throughout the query, use successive target bits to traverse a catalog graph, and end at catalogs of sources that activated the endpoint stores.

That redesign has concrete remaining costs. Shared store vertices can have unbounded incident degree even though each target has two owners. If all these incidence ranges must admit the same source key, their local degree is also unbounded. Splitting a hub into a balanced tree is legitimate, but its traversal must fit the remaining real input; a logarithmic path first exposed at the target endpoint is not paid. Copying a store catalog onto all its incident targets instead moves the cost to source updates. Neither observation rules out a different input-paid layout.

The static theorem assumes sorted catalogs and performs global preparation. Our right records need not arrive in that order, and source activations arrive afterward. Linear total work in catalog entries is not yet linear work in the actual encoded input, and even a linear total bound would not establish the required distribution of work across symbols.

The full-row graph-activation test

Let $G=(V,E)$ be any finite simple graph after deleting isolated vertices. Choose distinct nonempty ordinary store names $b_v$ and distinct nonempty ordinary edge names $q_e$ of one common edge width. These are actual input fields, not free addresses. Within each once-only store group $v$, give its sole observed local alias 0 exactly the row

$$X_v=\{q_e:e\text{ is incident to }v\}.$$

The store has zero omissions relative to its own support, and every target has exactly two owners. For a source $a$, ordinary left selections of alias 0 specify an arbitrary active set $A_a\subseteq V$. Direct relation composition gives

$$q_{\{v,w\}}\in U_a\quad\Longleftrightarrow\quad v\in A_a\ \lor\ w\in A_a.$$

Consequently the ordinary positive-source/negative-target Horn wrapper is satisfiable exactly when both endpoints are inactive. This follows by the same implication-path semantics as the retained bridge: an active endpoint supplies a path to the pinned-negative target, and without either path the Horn closure leaves that target false.

This is a restriction of the unresolved arbitrary-overlap extension, not a claim that construction 76 already handles unbounded selected vertices. Its existing overlapping clause still has a fixed per-source store bound. Nor is this an access-preserving reduction from a model that supplies a ready graph: every incidence, store name, selection and query name is written in the input. No padding or post-input processing is introduced. A common-width choice defines this test family; it does not convert arbitrary unequal-width instances for free.

For one source and one final query, the actual serialization has length

$$N_{\mathrm{enc}}=\Theta\!\left(\sum_{v\in V}\deg(v)(|b_v|+n+1)+\sum_{v\in A_a}(|a|+|b_v|+1)+|a|+n+1\right),$$

where $n=|q_e|$ is the common edge width. Each incidence is an ordinary right clause, each selected vertex is an ordinary left clause, and both pins are included. This is an encoding account, not an algorithm: it grants neither preprocessing after the records nor extra work at the final delimiter.

For a star with $m$ leaves, activating the center changes $m$ edge answers while each edge still has two owners. This refutes only a bounded-fanout justification for eager materialization. It is not an update lower bound against shared predicates, prepared routes or richer persistent representations. The singleton materialization escape from assessment 224 remains a control.

The independent finite audit checks literal Horn closure against endpoint activation and includes growing stars. Its host sets and graphs are semantic oracles, not native execution. Exact counts and publication verification are recorded in integration state.

Next decisive contract

Attempt a source-key continuation that travels with the target prefix through an input-built incidence index. At every prefix, bound the number of active continuations and their remaining rank uncertainty. In addition, bound literal replay debt: each continuation must already have processed the consumed prefix, or the remaining actual symbols must pay routing and catch-up while servicing new input. Require coherent source-version identity across every bridge.

Start with the full-row graph test above. Account for right-input construction, source activation, initial source lookup, high-indegree store sharing and immediate final output. A complete positive construction must state fixed degree, radius, labels/control and old-top updates and charge preparation, retained storage, allocation, observations and name routing to the actual encoded length. A negative result must name the representation restriction it uses. Do not infer a native-language lower bound from the star example or the existing reversal cut.

Replay retains its per-traversal cost. Affine joins retain their coordinate conditions; causal sharing preserves histories without supplying synchronized current bridges; unary coherent algebra does not produce this branching index. The native SAT controls and the reversal direction of the PEG consequence remain unchanged.

Contribution, custody and continuity

The imported theorems are established fractional-cascading results. The graph test is a direct semantic specialization, and the transfer analysis is a written comparison of exact contracts. Neither is presented as an original external theorem or another native construction. The useful contribution of this review is a concrete candidate mechanism and a smaller decisive test with zero local omissions. Persistence, online input and strict deadlines are the unclosed transfer obligations.

Primary PDFs and OCR stay outside public source. Source pins: Chazelle–Guibas SHA-256 4d78ee32ff68ba58ac8a554c4037b1d1cc39e810e2da36709dd1540bc989aa17; Mehlhorn–Näher SHA-256 2a4ce210c98a9b7d1ce95169744fd8bb5a482def05c0b89e85952219e22668d1. Reviewed proof comparisons, checker and history remain in GitLab; HTML/KaTeX and readable source are generated Site projections.

Scheduled completion 129 to 130 counts once as a dedicated primary-proof review. Mathematical 139, window five, reassessment 134 and native construction 76 remain unchanged. Next 131 is research; editorial 132 and primary review 135. No root admission. Homepage research recency is unchanged. Installed reverse-writer retirement remains separate and unverified.