{"id":"70f9e9c8-23f4-4c9f-8ac5-f2472c65b1fd","arxiv_id":"2607.13875","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Lexicographic direct access under functional dependencies is characterized: unary FDs are tight via reordered extensions, general FDs have a PANDA/polymatroid-based algorithm and color-number lower bounds that meet exactly at the linear-preprocessing threshold.","lead":"Researchers prove new bounds for lexicographic direct access to join-query answers when databases satisfy functional dependencies, showing that a simple rewrite-then-ignore approach is optimal for unary dependencies but not for general ones. A PANDA-based algorithm with matching Zero-Clique-based lower bounds yields a complete conditional dichotomy for linear preprocessing time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound reduction for Theorem 6.1 is under-specified: Lemma 5.6 mixes the original order π with the Δ-reordering π′, and Lemma 5.5 sketches the encoding without handling atoms that carry only the new color k+1.","rationale":"The paper's central claim is a dichotomy for linear-preprocessing direct access under FDs, conditional on Zero-Clique. The upper bound (Theorem 4.3 plus Lemma 6.2) is supported by a coherent construction: materialize each bag of a disruption-free decomposition via PANDA or, when guarded, via linear-time lookup-table extension, then run the known direct-access algorithm on the acyclic bag query. The combinatorial Lemma 6.3, which turns color number 1 into Δ-guardedness, is argued through a dual LP and a closure construction; I checked the LP dualization in Lemma 6.4 and the contrapositive argument of Lemma 6.3, and they appear sound. The weakest point is the lower-bound pipeline. The reader flagged that Lemma 5.5 is a sketch and that Lemma 5.6 appears to use π where π′ is intended; I agree, and I think this is load-bearing rather than cosmetic. Theorem 5.7 states a lower bound for a Δ-reordering π′ of an arbitrary π, but the proof of Lemma 5.6 needs a single consistent order to define the color-introducing variable, the bags, and the chain of bags in Claim C.3. If that order is π′, the statement must say so explicitly and the ratio in condition 2 must use C_{Q,Δ}-width(Q,π′). If it instead uses π, the coloring ratio can be different, and the reduction to the star query would not yield the claimed exponent. In addition, Lemma 5.5's construction is not fully specified; atoms with only color k+1 are a genuine edge case that the current join-of-ℓ-relations description does not cover. Both issues are likely fixable by expanding the proof, and I found no evidence that the dichotomy itself is false. Therefore the correct verdict is the same as the reader's: conditional acceptance pending a complete proof of the lower-bound reduction. I do not see an internal inconsistency that would warrant rejection.","tokens_in":31382,"tokens_out":33065,"duration_ms":280963,"concrete_test":"Rewrite Lemma 5.6 with π′ substituted for π throughout: take L from a bag of the π′-decomposition, let v_t be the last variable in π′ introducing a color, and re-derive Claims C.2 and C.3 entirely within the π′-decomposition. Verify that condition 2 is exactly k / C_{Q,Δ}-width(Q,π′) and that no step silently uses C_{Q,Δ}-width(Q,π). Separately, instantiate Lemma 5.5 on a small query containing an atom whose variables are all assigned only color k+1, e.g., add D(v,w) with L(v)=L(w)={k+1} and connect v through another atom to a color in [k]. Check that the constructed D has the claimed size O(|D⋆|^{k/ι}) and that direct access on Q(D) still simulates Q⋆_k in the required order. If either test fails, Theorem 5.7 and the negative half of Theorem 6.1 need qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The negative direction of the central dichotomy (Theorem 6.1) inherits all of its hardness from Theorem 5.7, which in turn depends on Lemmas 5.5 and 5.6. Lemma 5.6 states a result for an arbitrary order π and a Δ-reordering π′, but its proof begins with a coloring L from a bag of 'the disruption-free decomposition' without specifying whether this is the π or the π′ decomposition. It then defines v_t as the last variable in π that introduces a color and reasons about bags B_t, S_t using π. If π is not consistent (the general case), the bag B from Lemma C.1 is a bag of the π′ decomposition, so the chain of bags in Claim C.3 need not be a valid chain in the π decomposition. The proof only works if all bags are taken with respect to the same, consistent order — presumably π′. As written, the lemma does not establish that the required coloring exists with the exact ratio k / C_{Q,Δ}-width(Q,π′). Lemma 5.5 is also only a proof sketch: it asserts 'It can be shown that the construction encodes...' and does not specify how to build facts for atoms whose variables have no colors from [k] (only the freshly added color k+1). Such atoms can occur in the Lemma 5.6 coloring, and the described join of zero star relations yields no value for x_{k+1}, so the construction would silently omit a constraint. These are gaps in the proof of the lower bound that licenses the 'only if' half of Theorem 6.1; they are likely repairable, but the central claim is not fully established in the submitted text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies lexicographic direct access to join query answers over databases satisfying functional dependencies (FDs). It proposes two approaches: (i) a reordered-extension reduction, for which it shows tight bounds for unary FDs but failure for general FDs; and (ii) an information-theoretic/PANDA-based algorithm whose preprocessing is governed by a new disruption-free polymatroid width, with matching lower bounds (up to gaps) expressed through an FD-aware incompatibility/color number. The main result, Theorem 6.1, is a dichotomy characterizing, under the Zero-Clique Conjecture, the self-join-free join queries with FDs that admit lexicographic direct access with linear preprocessing and logarithmic access time: the condition is that every bag of the disruption-free decomposition of a Δ-reordering is Δ-guarded. The paper is careful in stating its limitations: the general width bounds are not tight, and all lower bounds rely on the Zero-Clique Conjecture and exclude self-joins.","tokens_in":31694,"tokens_out":7600,"duration_ms":69234,"significance":"If the central claims are correct, the paper gives the first complete linear-preprocessing characterization for lexicographic direct access under general FDs, a substantial advance over prior unary-FD results. The unary-FD result (Corollary 3.7) is tight up to subpolynomial factors and generalizes earlier work cleanly. The use of the color number and polymatroid bound in the context of disruption-free decompositions is a natural and promising technical contribution, as is the modularization-lemma comparison of the two approaches. The paper is also honest about the fact that its upper and lower bounds are generally not tight, and that this is tied to the lack of worst-case optimal join algorithms for FDs. If the proof gaps identified below are repaired, the paper would be a strong fit for a top database theory venue.","major_comments":[{"comment":"The proof of Lemma 5.6 mixes the original order π and the Δ-reordering π′ in a way that is not justified by the statement. The lemma assumes only that π′ is a Δ-reordering of π; π itself need not be consistent with Δ. Yet the proof says 'Let vt be the last variable in π that introduces a color', defines Bt as 'the bag in which vt is the last variable with respect to π', uses the decomposition for π in Claim C.3, and in Claim C.2 asserts 'As π is consistent with the FDs'. The coloring from Lemma C.1 is obtained from 'some bag B of the disruption-free decomposition' without specifying whether the decomposition is for π or π′. Since C_{Q,Δ}-width(Q,π′) is defined using π′, the bag B must be a bag of the π′-decomposition. Unless π=π′, the chain of bags B_{i1},...,B_{iℓ} in Claim C.3 is not a valid chain in that decomposition, so the proof does not establish the stated coloring. Because Lemma","section":"Lemma 5.6, §5.2"},{"comment":"The proof of Lemma 5.5 is only a sketch, and the construction omits an important case. For an atom R(v1,...,vn) of Q, the construction joins the star relations corresponding to the colors of [k] appearing in L(v1)∪...∪L(vn). If this set is empty, the text says to compute the join of zero relations, which does not produce values for x_{k+1}; the construction would silently add a single fact with all coordinates set to ⊥. Such atoms can occur in the coloring produced by Lemma 5.6: after adding the fresh color k+1 to all variables of S_t, an atom entirely inside S_t may carry no colors from [k]. It would then fail to encode the different x_{k+1}-values of D⋆, breaking the claimed bijection. The sentence 'It can be shown that the construction encodes...' is not a substitute for handling this case. Since Lemma 5.5 is the reduction step for all lower bounds in Section 5 and for the 'only if' d","section":"Lemma 5.5, §5.2"},{"comment":"The 'only if' direction of Theorem 6.1 is stated as a proof sketch that relies directly on Lemma 6.3 and Theorem 5.7. Given the issues in Lemmas 5.5 and 5.6, the dichotomy's negative direction is not fully established in the submitted text. This is not a challenge to the upper bound, which follows from Lemma 6.2 and the decomposition argument, but it means the central 'if and only if' is currently conditional on repaired lower-bound proofs.","section":"Theorem 6.1, §6"}],"minor_comments":[{"comment":"Labeling these results as 'Proof sketch' is risky for results that carry the main lower-bound weight. The final version should include full proofs in the appendix, not sketches in the main text.","section":"Lemma 5.5/5.6, §5.2"},{"comment":"There is a typo: 'Deonte byQ+' should be 'Denote by Q+'.","section":"Section 7"},{"comment":"The lower bound in Corollary 3.7 states the optimality claim only for preprocessing O(|D|^{ι-ε}) and access O(|D|^δ). This is correct but could be stated more explicitly as 'up to subpolynomial factors' to match the informal discussion.","section":"Section 3.1, Corollary 3.7"},{"comment":"The second author affiliation line contains a typesetting artifact ('Carmeli/envel⌢pe'); this should be corrected.","section":"Author list"},{"comment":"The notation σ_{R_i(X_i)} as both a variable name and subscript is slightly confusing; consider using σ_i.","section":"Lemma 6.4"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a strong and interesting claim, and the algorithmic side appears sound. My main concern is that the lower-bound proof, which is essential to the dichotomy, has a specific order-consistency flaw in Lemma 5.6 and an incomplete reduction case in Lemma 5.5. Both look repairable, but the submitted text does not fully establish the 'only if' direction of Theorem 6.1. I would encourage the editor to send the manuscript back for a revision that supplies complete proofs for these lemmas, rather than rejecting, because the core ideas and the dichotomy statement are significant and appear likely to be correct."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline, quickly: this is a serious theory paper that gives the first general-FD treatment of lexicographic direct access, including a linear-preprocessing dichotomy under the Zero-Clique Conjecture. The new width measures — FD-aware incompatibility and disruption-free polymatroid bound — are natural, and the acyclic example showing that reordered extensions can be strictly suboptimal is a clean and genuinely informative result. The authors are also honest that the general upper and lower bounds are not tight, and that all lower bounds rest on Zero-Clique and self-join-freeness. That is a real limitation, but it is stated plainly and is standard for the area.\n\nI checked the LP-duality part of Lemma 6.3/6.4, as the reader did, and it looks correct: the dual derivation checks out, and the argument that a feasible solution of value 1 forces a guarded atom is sound. The positive direction of the dichotomy, built on Lemma 6.2, is straightforward and convincing.\n\nThe real soft spot is the lower-bound proof for Theorem 5.7. Lemma 5.5 is only a proof sketch, and the appendix does not fully spell out how the construction handles atoms whose variables only carry the freshly added color k+1. That omission is repairable in principle, but it is exactly the kind of detail that carries the reduction. More concretely, Lemma 5.6 states a result about a Δ-reordering π′, yet the proof defines the bag B_t and component S_t with respect to π, and the chain of bags in Claim C.3 silently switches between decompositions. As written, the lemma does not establish that the coloring ratio matches C_{Q,Δ}-width(Q,π′). This is load-bearing: it supports the only-if direction of the central dichotomy. It is likely fixable — the correct order is presumably π′ — but as submitted the proof is not fully established.\n\nWho should read this: database theory people working on enumeration, direct access, or fine-grained query complexity. The paper deserves a serious referee; the main results are probably right, and the gaps are localized and plausibly repairable. If I were the editor, I would send it to review with a specific request to provide complete proofs of Lemmas 5.5 and 5.6 and to resolve the π/π′ issue. My own verdict would be conditional accept pending that repair.","headline":"Solid conditional frontier result for direct access under FDs; the lower-bound proof has a real π/π′ gap that needs fixing before the dichotomy is fully established.","tokens_in":32271,"tokens_out":2621,"would_cite":true,"duration_ms":28021,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For FD-constrained join queries, lexicographic direct access with linear preprocessing is achievable exactly when every bag of the reordered disruption-free decomposition is determined by a single atom together with the dependencies.","keywords":["join queries","lexicographic direct access","functional dependencies","disruption-free decomposition","polymatroid bound","color number","Zero-Clique Conjecture","fine-grained complexity"],"falsifier":"Exhibit a self-join-free join query, an FD set, and a variable order such that some bag of the Δ-reordered disruption-free decomposition is not Δ-guarded, yet lexicographic direct access still runs in linear preprocessing time and logarithmic access time — that would refute the dichotomy's only-if direction, independent of the conjecture.","tokens_in":31180,"feed_emoji":"⚡","tokens_out":10193,"duration_ms":79191,"temperature":0.7,"pith_summary":"Lexicographic direct access asks a database system to answer, after a preprocessing phase, \"what is the j-th answer to a query in a chosen order?\" in logarithmic time. This paper asks how functional dependencies (FDs) change the minimum preprocessing needed, and gives a nearly complete answer. For unary FDs the optimal preprocessing exponent is now known exactly: it is the incompatibility number of the query after incorporating the FDs, tight up to sub-polynomial factors. For general FDs the paper proves a dichotomy: linear preprocessing suffices if and only if every bag of a certain decomposition, built after reordering variables to respect the FDs, is guarded by a single atom, meaning the atom's variables plus the FDs determine all bag variables. The negative direction is conditional on the Zero-Clique Conjecture, and the dichotomy covers all self-join-free join queries.","feed_headline":"FD-aware direct access is linear iff every bag is FD-guarded","feed_subtitle":"Functional dependencies fully determine when query answers can be indexed after linear preprocessing.","key_machinery":"The argument rests on three objects. (1) The Δ-reordering of the variable order places each FD-implied variable directly after the variables that determine it; it never changes the output order and never increases either width measure. (2) The disruption-free decomposition is a hypergraph whose bags record, for each variable, which earlier variables it interacts with through the query; the maximum polymatroid bound P_{Q,Δ}(B_i) over the bags bounds the preprocessing time of the algorithm, while the maximum color number C_{Q,Δ}(B_i) (the FD-aware incompatibility number) supplies the lower bound. (3) The dichotomy pivots on a lemma that C_{Q,Δ}(S)=1 exactly when S is Δ-guarded, i.e., when a si","core_discovery":"The paper's central result is a complete dichotomy for lexicographic direct access to self-join-free join queries under functional dependencies, assuming the Zero-Clique Conjecture (Theorem 6.1). After reordering the variable order to respect the FDs (a Δ-reordering), one builds the disruption-free decomposition of the query; preprocessing time O(|D|) with O(log |D|) access time is possible if and only if every bag of that decomposition is Δ-guarded — that is, some atom of the query together with the functional dependencies determines all variables of the bag. The positive direction is an algorithm that materializes each bag using the paper's information-theoretic evaluation algorithm, PANDA","pith_inferences":["The Δ-guarded condition reads like a query-language criterion — a bag is cheap when one atom, closed under FDs, determines it. A similar guardedness criterion may characterize other FD-constrained tasks such as constant-delay enumeration or counting, where the extension approach was previously believed sufficient.","The gap between the polymatroid width (upper bound) and the color-number width (lower bound) is left open and can be arbitrarily large; closing it would require knowing when the polymatroid bound coincides with the entropic bound, so tighter results for general FDs would likely need new information-theoretic inequalities, not just faster join algorithms.","A testable extension: the same machinery is expected to transfer to degree constraints and other cardinality constraints supported by the underlying evaluation algorithm; if so, the guarded-bag dichotomy may generalize to a broader class of integrity constraints.","The reordering observation — that FDs let dependent variables move earlier in the lexicographic order at no cost — is a property database optimizers could exploit beyond direct access, since it preserves answer order for any downstream task."],"forward_implications":["The linear-preprocessing frontier is fully mapped: any query, order, and FD set whose bags are not all Δ-guarded needs superlinear preprocessing (assuming the Zero-Clique Conjecture), so no cleverer algorithm can cross that boundary.","For unary FDs the optimal preprocessing exponent is exactly the incompatibility number of the reordered extension, an integer computable by linear programming, so the hardness of a concrete instance can be read off mechanically.","The information-theoretic algorithm is never worse than the extension-based reduction and sometimes strictly better, so the recommended pipeline is always: Δ-reorder, build the decomposition, materialize the bags.","FDs can substantially shrink the polymatroid width — from k−1 down to 1 in the paper's star-query example — meaning declared constraints can turn a high-polynomial preprocessing problem into a near-linear one.","Because direct access supports quantiles, histograms, and sampling without repetition, the dichotomy identifies exactly which FD-constrained databases admit these operations with near-linear preprocessing."],"fun_headline_variants":["FD-guarded bags make direct access linear","Linear direct access? Only with FD-guarded bags","FDs draw the line for linear join direct access","Dichotomy: FD-guarded bags ensure linear access"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"All lower bounds rest on the Zero-Clique Conjecture (that finding a zero-weight k-clique in an n-node graph requires near n^k time), and the dichotomy is proved only for queries without self-joins.","fun_headline_variants_meta":{"raw":{"variants":["FD-guarded bags make direct access linear","Linear direct access? Only with FD-guarded bags","FDs draw the line for linear join direct access","Dichotomy: FD-guarded bags ensure linear access"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000357,"raw_usage":{"total_tokens":1761,"prompt_tokens":719,"completion_tokens":1042,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":463,"completion_tokens_details":{"reasoning_tokens":980}},"tokens_in":463,"tokens_out":1042,"duration_ms":33990,"temperature":1.0,"reasoning_tokens":980,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T03:27:20.411886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a self-join-free join query, an FD set, and a variable order such that some bag of the Δ-reordered disruption-free decomposition is not Δ-guarded, yet lexicographic direct access still runs in linear preprocessing time and logarithmic access time — that would refute the dichotomy's only-if direction, independent of the conjecture.","supporting_citations":[],"review_version":1}