Assessment139: late profile correction and dynamic join maintenance

8 October 2026. Dedicated primary-proof review45. The exact correction for a late anchor-induced row move contains a weighted overlap query. Boundedly many moves give linear total incidence-repair work, but not a worst-case symbol schedule. This is a written supporting calculation and a failed eager-transfer route, not a native lower bound or a new root admission. Arbitrary late refinement remains open.

Two primary proofs and their contracts

Berkholz, Keppeler and Schweikardt, Answering Conjunctive Queries under Updates, arXiv1702.06370v1 (2017). Pinned primary PDF. Complete31-page paper and appendix read. SHA256 2f08b37b42b5fe4ae05a69a2ee391c2fc63532a97ef2755a7efba53434d435cb.

Definition3.1 requires nested or disjoint variable-atom sets, with an additional free-variable condition. Lemma4.2 obtains a rooted query tree. Section6 and Lemma6.3 factor assignment counts into independent child sums; a tuple update changes boundedly many ancestor items. Theorem3.2 gives linear preprocessing and constant update/count/delay for fixed q-hierarchical queries. The RAM model includes word arithmetic, mutable lists and constant-time addressed arrays. Sections5.3-5.4 derive conditional OMv/OV barriers through online matrix/vector instances, typed domains and query cores. Enumeration necessity has a self-join-free restriction; Boolean and counting statements have different hypotheses. AppendixA shows how an easy enumeration block can fund rebuilding for a self-join example. This is output-funded work, not a one-bit deadline theorem.

Kara, Ngo, Nikolic, Olteanu and Zhang, Counting Triangles under Updates, arXiv1804.02780v2 (2019). Pinned primary PDF. Complete56-page full version and appendices read, not just the conference abstract. SHA256 cb3f46fcc338cbe32d5b1010484d8e7ac1b2d747f29dae2291bd9d5681cf7eb9.

Theorem3 maintains triangle counts over integer-weighted relations by degree partitioning and selected materialized joins. Light scans and the bounded population of heavy keys control delta work. With M tuples, preprocessing is O(M^1.5), amortized update O(M^max(epsilon,1-epsilon)), and answer time constant. Section4 charges threshold rebuilding and bucket migration through hysteresis; these are real costs. AppendixD, Theorem16, improves space to linear at epsilon=1/2 while retaining square-root amortized updates. The model assumes indexed tuple access, mutable views and integer arithmetic. AppendixC’s OMv reduction uses arbitrary online vector changes. AppendicesE-H analyze enumeration, larger joins and the hierarchical boundary. A materialized overlap provides fast readout only after its maintenance has been paid.

These imported results retain their hypotheses. Their online lower-bound reductions do not automatically apply to the Lab’s bounded, monotone anchor-bit insertions. Query size is fixed in both comparisons; database size is not encoded input length. Ordinary finite-alphabet names must still be read and routed. We neither question these proofs nor infer native membership from their RAM algorithms.

The exact missing correction

Fix one normalized key and its finite row-profile palette. Let W be the already present non-anchor targets and E the distinct row-target incidence relation restricted to W. For this calculation W and E are fixed while one existing row changes profile. Anchor incidences causing that change are outside E. This separates reclassification from insertion of the triggering anchor edge.

Write p(v) for a row’s profile, H_m for the number of rows of profile m, and

$$c_{wm}=|\{v:p(v)=m,\ (v,w)\in E\}|,\qquad e_m=\sum_{w\in W}c_{wm}.$$

The nonnegative coverage defect is

$$D=\sum_{w,m}c_{wm}(H_m-c_{wm}).$$

Each summand counts ordered pairs of same-profile rows for which one is incident to w and the other is not. Thus D=0 exactly when every target contains either all or none of each current profile class. Empty classes cause no problem. This does not check the separate bound on distinct target answer types and does not provide their current masks or composed answers.

Suppose row v moves from p to q, p != q. Put b_w=1 if (v,w) is in E, and d_v=sum_w b_w. All quantities on the right below refer to the old state. Then

$$\boxed{\quad D'-D=e_q-e_p+(H_q-H_p)d_v+ 2\sum_{w:(v,w)\in E}(c_{wp}-c_{wq}).\quad}$$

Proof. The changed populations are H_p-1 and H_q+1; the changed target counts are c_wp-b_w and c_wq+b_w. Since b_w^2=b_w, the p-cell difference is -c_wp+b_w(2c_wp-H_p), and the q-cell difference is c_wq+b_w(H_q-2c_wq). Sum over W. All other cells cancel. This is an integer identity, independent of a storage implementation.

Define the overlap view

$$J_m(v)=\sum_w E(v,w)c_{wm} =\sum_{x:p(x)=m}|N(v)\cap N(x)|.$$

The boxed correction requires J_p(v)-J_q(v). This is a sufficient algebraic query for maintaining this chosen D, not a proof that every recognizer must compute J. Merely naming this view supplies no ready handle or paid query algorithm. Materializing all J_m(y) moves the obligation: reclassifying v changes each J_m(y) according to |N(y) intersect N(v)|. The overlap is a length-two incidence join. Its query-variable incidence fails the nested/disjoint test when the row profile predicate and a returned row endpoint are both retained. The repeated E and restricted update stream must not be silently replaced by independent relation inputs in a lower-bound argument.

Scalar margins do not determine the correction. A concrete finite witness uses rows a,b,v with profiles q,q,p and three targets0,1,2. In the first state their neighborhoods are {0,1,2}, {0,2}, {0,2}; in the second they are {0,1,2}, {0,1}, {0,2}. Both have H_p=1,H_q=2,e_p=2,e_q=5,d_v=2,D=1. Moving v from p to q changes D by1 in the first state and3 in the second. The overlap term distinguishes them. This disproves only a correction function of these scalar values; retained incidence or richer shared summaries remain available.

Why bounded changes help, and why that is insufficient

For k fixed anchors, a row’s profile changes at most k times under distinct anchor-edge insertions. Consider the abstract eager strategy that visits every previously inserted non-anchor edge of that row at each change. Each final edge is visited at most k times. Therefore the number of such visits is at most k|E_final|. Even if each visit replays its stored target spelling, the sum of replayed spelling lengths is at most k times the sum over distinct input edges of their target lengths, hence O(kN) for actual encoded length N.

This bounds only incidence visits and spelled replay, not arbitrary dictionary access, counters, reverse adjacency construction or immutable scheduling. No supplied neighbor handle is authorized by the counting argument. In particular total work, even when linear, is not spendable after the last symbol. Source preparation, all old-storage observations, routing, storage and allocations must fit their actual prefixes.

Here is a fixed-width counterexample to eager per-target mask repair and to a global remapping of old masks. Use rows v,x,y and two anchors A,B. First give A all three rows and B only y. Next give arbitrarily many non-anchor targets one of the two neighborhoods {v,x,y} and {v,y}, with both kinds represented. Last insert (v,B). Before this last edge the profiles are p(v)=p(x)=01, p(y)=11. Every non-anchor mask is {01,11}. Afterward p(v)=p(y)=11 and p(x)=01. The first target kind keeps mask {01,11}, while the second becomes {11}. All final profile cells are complete. Including the anchors, exactly two final predecessor types occur.

There can be L second-kind targets, so L materialized masks change on this single event. Equal old masks split into different new masks: a function of only the old mask and the global move cannot perform the correction. Counts, incidence, target-dependent receipts or richer shared indirection could do so. The example does not forbid them.

This family fits a fixed normalizer: take g(0^j1z)=z, distinct aliases for A,B and all non-anchors, fixed two-bit row names, and fixed two-bit z. Then normalized degree is one and row/key span is zero. Choose A and B as the two shortest aliases. The last (v,B) record and subsequent ordinary-name pins selecting a short alias have constant length, independent of L. The longer aliases are actual target names, not padding available after that event. A representation contract requiring a separate local write to every changed target before the next phase cannot meet a fixed per-symbol budget on this family. Shared lazy interpretation is expressly outside that failed contract. Indeed this witness uses only three literal rows, so the existing bounded literal-palette control handles it. It is a stress test for the chosen update representation, not an intrinsically hard language family.

Resource transfer audit and next decisive test

The reviewed methods clarify a choice: retain a factorization whose updates touch a bounded dependency chain, or charge the joins needed to correct a materialized view. Neither choice supplies the following native obligations for free:

Next target: test a target-directed correction receipt for bounded monotone profile moves. It must retain enough incidence to distinguish the two target kinds above, select the current mask during the target’s own name, and supply an exact shared coverage certificate. First attempt k=2 and two final target types. Bound both the number of simultaneously pending corrections and the work to consult or combine them; a fixed number of changes per row does not bound the number of changed rows. A global chain of correction events with an unbounded query scan fails the contract. Precomputed alternatives are allowed only with their construction, storage and routing charged.

The existing anchor-completion construction remains the positive control: freezing profiles before non-anchor grouping removes this correction altogether, while deferred left dispatch avoids premature source-lane writes. Arbitrary-order one-type coverage can bypass explicit masks through the batch deficit. Fixed row-key palettes avoid changing profile semantics. The native replay slices, affine joins, causal algebra and unary coherent cubical work retain their original hypotheses; none resolves this overlap readout merely by reusing a name or a root. Entry129’s matching and positive-path bounds remain conditional diagram results, with their growing relation alphabet. No native language bound follows from this review. A native recognizer yields a PEG for reversal of its language, not automatically the same orientation.

Evidence, continuity and disposition

The writing agent reconstructed both primary proof mechanisms and audited the transfers above. No independent reviewer, formal proof replay, or implementation of either published algorithm is claimed. The diagnostic check_late_profile_correction.py compares cell arithmetic against independently enumerated ordered mismatch witnesses: 13,824 states and82,944 profile moves. It also checks64 growing late-split families and24 insertion/move schedules. These are finite semantic checks, not native timing evidence or a proof of an infinite lower bound. The displayed identity and repair charge have general written proofs above.

Seven surfaces: primary PDFs/text remain private; CLAIMS.yaml is unchanged; this review owns the supporting calculation and finite evidence; the failed scalar/eager/global-mask routes and their reopen gates are explicit; the frontier is charged shared correction; the checkpoint/program/agenda link this review; public reader section25 and Site534 remain unchanged. Repository continuation metadata is not a deployed edition. No homepage, ranking, embargo or audience change. Installed reverse-writer retirement remains unverified and nonblocking.

Scheduled44->45 exactly once. Dedicated45 complete; next46 research, next dedicated50. Mathematical95/window3/last reassessment92 unchanged: this review and supporting identity are not a new major result. The standalone semantic diagnostic, Python syntax, local links, JSON/counters and whitespace checks passed. The full declared make verify gate was also attempted because this packet contains a supporting written identity: 1490 tests passed,1 skipped,5 failed in238.28s. Four failures are the retained custody-provenance mismatch; the frontier verifier fails because lake is unavailable. These are the same five failure names recorded in138; later make targets were not reached. No Site build, deployment or source-parity replay is claimed.