{"id":"249c0954-cfe7-40dd-8a37-1f3108799d02","arxiv_id":"2412.11661","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Consistent answers of self-join-free conjunctive queries over naturally ordered positive semirings are rewritable in the logic LK exactly when the query's attack graph is acyclic, generalizing the Boolean case.","lead":"The paper defines consistent answers for databases annotated with semiring values (minimum over all repairs) and introduces a logic, LK, to rewrite them. It proves that, for self-join-free conjunctive queries with key constraints, rewritability is exactly characterized by the acyclicity of the query's attack graph, and that strong cycles make bag-semiring answers impossible to approximate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.9's acyclic-to-rewritable direction rests on Lemma 4.15, whose Appendix B.3 proof is a sketch that imports [2, Lemma 4.5] and an unproved superfrugal-repair induction; the main equivalence is not fully verifiable from this preprint.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing concern: Lemma 4.15 is the pivotal decomposition in the acyclic-to-rewritable direction of Theorem 4.9, and its proof is not self-contained. I agree with that assessment. My independent reading confirms that the appendix imports [2, Lemma 4.5] without stating it, relies on the undefined-in-this-paper notion of superfrugal repairs, and replaces the crucial induction with the phrase 'similar to Claim 2'. This is not a trivial omission: the lemma asserts a min-sum interchange over repairs that is sensitive to the acyclicity and unattackedness conditions, and the adaptation from the Boolean/numerical results in [2] to arbitrary naturally ordered positive semirings is asserted rather than proved. The rest of the paper has genuine independent support: the non-approximability reduction in Proposition 5.1 is self-contained, and the right-to-left direction of Theorem 4.9 follows cleanly from Proposition 4.2 plus the known Koutris-Wijsen result. Those parts can be credited. But the main iff theorem cannot be fully verified from the preprint alone. This warrants the same CONDITIONAL verdict the reader gave: the paper should be accepted only after a complete proof of Lemma 4.15, or after the imported lemma is stated and proved in the appendix. No change to the verdict is needed because the reader's conditional already reflects this gap.","tokens_in":32354,"tokens_out":15276,"duration_ms":148114,"concrete_test":"Require a complete, self-contained proof of Lemma 4.15 that states and proves the needed version of [2, Lemma 4.5] and fills in the induction for Claim 3. As a supplementary computational check, enumerate all repairs for qpath and qsink over the bag and Viterbi semirings on small random databases, and verify for every unattacked variable x that mCA(q,D,alpha) equals sum_c mCA(q[x],D,alpha(c/x)); one failure falsifies the lemma, while many successes are supporting but not conclusive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the if-and-only-if characterization in Theorem 4.9. The right-to-left direction is solid: it composes Proposition 4.2 with the known Koutris-Wijsen result. The load-bearing step is the converse, whose proof is an induction that invokes Lemma 4.15 at every step: the base case uses it to decompose mCA(q), and the inductive step uses it to strip an unattacked atom. If Lemma 4.15 is false or has a missing hypothesis, the construction of the LK-rewriting collapses. Appendix B.3 does not give a complete proof of Lemma 4.15. It cites [2, Lemma 4.5] without stating that lemma, appeals to 'superfrugal repairs' and 'forall R_i-blocks' as imported notions, and then says the key induction is 'similar to that in Claim 2' rather than carrying it out. The lemma is semiring-sensitive: it asserts that min over repairs of a sum of q[x]-values equals the sum of the per-x minima, an interchange that is false in general without the acyclicity/unattackedness hypotheses. The proof sketch suggests the transfer from the Boolean/numerical setting of [2] to arbitrary naturally ordered positive semirings is routine, but that transfer is exactly what needs to be shown. Because this lemma is used in both the base case and the inductive step of Theorem 4.9, the preprint currently leaves the main rewritability theorem with an external, co-authored dependency and an incomplete argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies consistent query answering for databases annotated with values from a naturally ordered positive semiring. It defines repairs as maximal sub-databases whose support satisfies a set of key constraints, defines the consistent answers mCA_K(q,Σ,𝔇) as the semiring minimum of the query values over all repairs, and introduces the logic LK, an extension of first-order logic with a guarded minimization operator ∇ and a Supp operator that flattens annotations. The main result (Theorem 4.9) states that, for self-join-free conjunctive queries with one key constraint per relation, the attack graph of the query is acyclic if and only if mCA_K(q,Σ) is LK-rewritable. The paper also proves (Corollary 5.2) that for the bag semiring, a strong cycle in the attack graph makes constant-factor approximation of the consistent answers NP-hard under first-order reductions.","tokens_in":32630,"tokens_out":17377,"duration_ms":154575,"significance":"If correct, Theorem 4.9 yields a uniform generalization of the FO-rewritable case of the Koutris-Wijsen trichotomy to all naturally ordered positive semirings, with new consequences for the bag, tropical, Viterbi, and fuzzy semirings. The non-approximability result in Section 5 is a novel and plausible contribution that connects consistent query answering with approximation algorithms. The right-to-left direction of the main theorem is sound and concise, and the overall proof strategy is convincing. The main caveat is that the left-to-right direction depends on Lemma 4.15, whose proof in Appendix B.3 is a sketch rather than a complete, self-contained argument. Until that lemma is fully proved or replaced by a precise statement and proof of the imported external result, the central theorem is not fully verifiable from this manuscript. The definitions of LK and of the semiring semantics are otherwise carefully developed, and the connection to constant-depth circuit classes is a useful contribution.","major_comments":[{"comment":"Lemma 4.15 is load-bearing for the left-to-right direction of Theorem 4.9: it is used both in the base case and in the inductive step of the proof. Its proof in Appendix B.3 is not self-contained. The argument cites [2, Lemma 4.5] without stating the lemma, introduces 'superfrugal repairs' and '∀R_i-blocks' through informal definitions, and defers the central induction over decreasing i with the sentence 'The reasoning is similar to that in Claim 2.' Since the lemma is semiring-sensitive—it exchanges a minimum over repairs with a sum over the active domain—the transfer from the Boolean/numerical setting of [2] to arbitrary naturally ordered positive semirings is precisely the point that needs to be proved. As it stands, a reader cannot fully verify Theorem 4.9 from the preprint alone.","section":"Appendix B.3, Lemma 4.15"},{"comment":"The displayed definition of the guarded minimization shorthand appears inconsistent with the stated semantics and with Proposition 4.3. With Supp(φ) defined as 1 if φ = 0 and 0 otherwise, and χ := Supp(∃z′G(®y,z′)), the formula θ(®y,z) := (Supp(G(®y,z)) ∧ ∃z′φ(®y,z′) ∧ χ) ∨ (φ(®y,z) ∧ χ) evaluates to 0 for every z whenever ∃z′G is supported (since then χ = 0), and it evaluates to the sum of all φ-values plus φ(z) when no G is supported. This contradicts the surrounding explanation and Proposition 4.3. If the authors intend a typographically distinct 'double Supp' operator (the shorthand mentioned on page 9), that distinction must be made explicit in Eq. (7) and the formula corrected accordingly. This is not merely cosmetic, because the guarded minimization operator is used in the path-query example and in the rewritings built in Theorem 4.9.","section":"Section 4.2, Eq. (7)"}],"minor_comments":[{"comment":"The sentence defining FnAC0_K(+,×, min, Supp) writes 'max' instead of 'min'; the first class should be the functions computed by AC0_K(+,×, min, Supp) circuits.","section":"Section 4.3, Definition 4.7"},{"comment":"The statement of the qsink example uses the bound variables ρ and α that are not introduced, and the parameter ε is replaced by ρ; the claim should be stated uniformly for every ε ≥ 1.","section":"Section 5, qsink example"},{"comment":"The definition of PreCopy(ℜ,i) as 'the smallest subset of Rep(𝔇,Σ) that contains ℜ′ whenever ...' is unclear; it should be replaced by the explicit description 'the set of all repairs ℜ′ that agree with ℜ on R_j-facts for all j ≤ i'.","section":"Appendix B.3, proof of Lemma 4.15"},{"comment":"The step 'It is easy to see that ψ is an FO-rewriting of Cons(q,Σ)' would benefit from a sentence noting that for the Boolean semiring mCAB(q,Σ,𝔇) is always in {0,1} and that φ(𝔇) ≠ 0 holds exactly when Cons(q,Σ,𝔇) = 1.","section":"Section 4.4, proof of Proposition 4.12"},{"comment":"The grammar for LK includes ∇xφ and Supp(φ), but the guarded-minimization shorthand ∇_G z.φ is defined only in prose around Eq. (7); the shorthand should be either integrated into the syntax or explicitly designated as a definable abbreviation with a correctness proof.","section":"Section 4.2, grammar of LK"}],"recommendation":"major_revision","confidential_remarks":"The main theorem's proof relies on Lemma 4.15, whose appendix proof imports [2, Lemma 4.5] without stating the lemma; [2] shares an author with this submission. This is a verifiability concern rather than an allegation of misconduct, but the reviewing process should require the authors to either make the proof of Lemma 4.15 fully self-contained or provide the exact statement and a proof of the imported lemma. The apparent inconsistency in Eq. (7) may be an artifact of plain-text rendering, but it must be resolved before publication, since the guarded-minimization operator is central to all LK rewritings. The paper is a good fit for a database theory journal and the results are significant if the identified gaps are closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is a real result with a real gap. The paper generalizes the Koutris–Wijsen trichotomy from Boolean databases to every naturally ordered positive semiring, and adds a constant-factor inapproximability result for the bag semiring. If the main theorem holds, it's the right unifying statement and the first consistent-answering framework that covers bag, tropical, Viterbi, and fuzzy semantics at once.\n\nWhat is genuinely new: the semiring notion of consistent answers (min over repairs), the logic LK with guarded minimization and the suppression operator, the iff rewritability criterion in Theorem 4.9, and the inapproximability corollary. The path-query example is clean, and the right-to-left direction of the main theorem is a straightforward and sound reduction to the published Koutris–Wijsen result. The AC0_K circuit framework is a sensible way to argue that LK rewritings are parallelizable, and the non-approximability reduction is self-contained.\n\nThe soft spot is exactly where the stress-test note lands. The left-to-right direction of Theorem 4.9 is an induction that calls Lemma 4.15 in both the base case and the inductive step: it decomposes mCA_K(q) as a sum over the active domain of mCA_K(q[x]) for an unattacked variable x. That interchange—min over repairs of a sum equals sum of per-witness minima—is the load-bearing step, and it is semiring-sensitive. The proof in Appendix B.3 is a sketch: it imports Lemma 4.5 from [2] without stating it, appeals to 'superfrugal repairs' and '∀R_i-blocks' as established notions, and the key decreasing-i induction is described as 'similar to that in Claim 2' rather than carried out. Because both the base case and the inductive step of Theorem 4.9 depend on this lemma, a reader cannot fully verify the main theorem from this preprint. I don't think the lemma is false—the structure and the Boolean case make it credible—but the proof obligation has been deferred to a co-authored external result and an unfinished induction.\n\nMinor issues: typos in the theorem proof ('mCA_k', the guard condition in the final paragraph) and equation numbering. These are trivial.\n\nWho should read it: database theorists working on consistent query answering or semiring provenance. It deserves a serious referee. My recommendation is major revision: complete Lemma 4.15, state the imported lemma from [2], and fix the typos. I would not reject on the current evidence, and I would not build on the main theorem until the gap is closed.","headline":"Genuinely new framework for consistent answers over semirings, but the main rewritability theorem rests on a lemma whose proof is only sketched—worth serious review, not yet fully verifiable.","tokens_in":33253,"tokens_out":5060,"would_cite":false,"duration_ms":42237,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","03B70","68Q19"],"pacs":[],"model":"deepseek-v4-flash","headline":"Consistent answers on annotated semiring databases are rewritable in a first-order-like logic exactly when the query's attack graph is acyclic.","keywords":["consistent query answering","repairs","semirings","conjunctive queries","key constraints","first-order rewritability","attack graph","approximation hardness"],"falsifier":"Exhibit a self-join-free conjunctive query with an acyclic attack graph and a naturally ordered positive semiring, for instance the bag semiring, for which no LK formula equals the minimum of the query over all repairs; equivalently, find an instance where the identity mCA_K(q,D,α) = Σ_c mCA_K(q[x],D,α(c/x)) of Lemma 4.15 fails, since the inductive rewriting is built entirely on that identity.","tokens_in":32093,"feed_emoji":"🗄️","tokens_out":5468,"duration_ms":48006,"temperature":0.7,"pith_summary":"Over databases whose tuples carry values from a naturally ordered positive semiring, this paper defines the consistent answer to a query as the minimum, over all repairs of the inconsistent database, of the semiring value the query returns. The central result is an equivalence: for self-join free conjunctive queries with one key constraint per relation, these semiring-consistent answers can be evaluated by a single formula of a new logic LK — a first-order-like logic with a guarded minimization operator and a flattening negation — if and only if the query's attack graph is acyclic. This generalizes the known Boolean trichotomy of Koutris and Wijsen to every naturally ordered positive semiring, yielding concrete rewritings for the bag, tropical, Viterbi, and fuzzy semirings. For the bag semiring, the paper further shows that when the attack graph contains a strong cycle, computing the consistent answer is NP-hard even to approximate within any constant factor. A reader should care because the paper draws a sharp, syntactically checkable boundary between queries whose consistent answers are cheaply rewritable and queries whose answers are essentially intractable.","feed_headline":"Attack graphs decide when consistent answers are rewritable","feed_subtitle":"For all naturally ordered semirings, acyclic attack graphs give one-formula rewritings; strong cycles make bag-case approximation NP-hard.","key_machinery":"The central objects are the logic LK, which augments first-order logic with a guarded minimization operator ∇_G x.φ that returns the least semiring value of φ over elements where the guard G is non-zero, and a Supp operator that flattens every non-zero value to 0; the attack graph of a conjunctive query, whose vertices are the query atoms and whose directed edges record when one atom's non-key variables can determine a key value of another atom through the key constraints; and the notion of a naturally ordered positive semiring, whose total order makes the minimum over repairs well-defined. The proof carries the argument by showing that, for acyclic attack graphs, the minimum over exponentially many repairs decomposes one unattacked atom at a time into a guarded minimization inside an LK formula, and that any cyclic attack graph yields a Boolean instance where a rewriting would contradict the known trichotomy for ordinary databases.","core_discovery":"The paper establishes Theorem 4.9: for any naturally ordered positive semiring K, any self-join-free conjunctive query q, and any set Σ of key constraints with one key per relation of q, the consistent-answer problem mCA_K(q,Σ) is LK-rewritable if and only if the attack graph of q is acyclic. The forward direction builds an LK formula by induction on the query, peeling off an unattacked atom and rewriting the consistent answer as a guarded minimization over that atom's non-key values multiplied by the rewriting of the remaining query; the converse shows that any LK rewriting translates, via the embedding of LK into first-order logic on the Boolean semiring, into an FO rewriting, and the prior trichotomy implies that such a rewriting forces acyclicity. Corollary 5.2 adds that over the bag semiring, a strong cycle in the attack graph makes even constant-factor approximation of mCAN(q,Σ) NP-hard under first-order reductions. The contribution is a syntax-to-complexity transfer: the same graph condition separates rewritable from intractable consistently across all naturally ordered positive semirings.","pith_inferences":["If the central equivalence extends as stated, the acyclicity criterion is likely to govern rewritability for other semirings whose natural preorder is total, such as truncated or cap-product semirings, because the proof machinery of guarded minimization and superfrugal repairs is semiring-generic.","The strong-cycle inapproximability result for the bag semiring suggests that other infinite naturally ordered semirings, such as the tropical semiring, may admit analogous constant-factor inapproximability; a direct reduction would need to control how the semiring's order interacts with annotated constants.","For queries whose attack graph has only weak cycles, the Boolean case is polynomial-time but not first-order rewritable, and the analogous semiring question is left open; a plausible outcome is polynomial-time computability through a semiring Datalog variant rather than an LK rewriting.","The min-over-repairs semantics aligns with the greatest-lower-bound semantics used for range aggregation queries, so the LK rewritings here could be reused as building blocks for computing glb answers to SUM-like aggregate queries over bag databases."],"forward_implications":["For the bag, tropical, Viterbi, and fuzzy semirings, an acyclic attack graph yields an explicit LK rewriting, so consistent answers on those annotated databases are computable by evaluating one formula in the semiring analogue of uniform constant-depth circuits.","A query whose attack graph contains a strong cycle is, over bag databases, NP-hard to approximate even up to any constant relative factor, so no polynomial-time approximation scheme can exist unless P equals NP.","The Boolean trichotomy for self-join-free conjunctive queries under key constraints is subsumed as the special case K = B, with the same attack graph as the deciding criterion.","The data complexity of LK lies in a semiring variant of uniform AC0, meaning rewritable consistent answers retain the parallelizability of ordinary first-order query evaluation.","The paper supplies a uniform definition of repairs for annotated databases — maximal sub-databases whose supports satisfy the key constraints — so the same consistent-answer semantics applies across all naturally ordered positive semirings."],"supporting_citations":[{"why":"Supplies the Boolean trichotomy for self-join-free conjunctive queries under key constraints; the converse direction of Theorem 4.9 reduces LK-rewritability to this prior FO-rewritability result.","marker":"[26]"},{"why":"Provides Lemma 4.5 on superfrugal repairs, imported in the proof of Lemma 4.15, which is the load-bearing step of the acyclic-to-rewriting direction.","marker":"[2]"},{"why":"Gives the first FO-rewriting of consistent answers for the path query, the motivating example whose guarded minimization pattern the LK rewriting formalizes.","marker":"[15]"},{"why":"Supplies semiring semantics for first-order logic under interpretations, used to justify the flattening-based notion of satisfaction and repair.","marker":"[17]"},{"why":"Establishes the semiring-annotated database framework and the semantics of conjunctive queries over semirings, the underlying data model of the paper.","marker":"[19]"},{"why":"Introduces the attack graph notion that the paper adopts as the criterion for rewritability.","marker":"[36]"}],"fun_headline_variants":["Attack graph acyclicity decides semiring rewritability","No cycles? Consistent answers rewritable across semirings","Cyclic attack graphs make consistent answers intractable","Rewritable iff attack graph acyclic for semiring CQA","Bag semiring: strong cycles kill approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main construction depends on Lemma 4.15, whose proof is only sketched in an appendix and imports a lemma from a closely related paper with a shared author; if that lemma fails, the inductive rewriting in the central theorem collapses.","fun_headline_variants_meta":{"raw":{"variants":["Attack graph acyclicity decides semiring rewritability","No cycles? Consistent answers rewritable across semirings","Cyclic attack graphs make consistent answers intractable","Rewritable iff attack graph acyclic for semiring CQA","Bag semiring: strong cycles kill approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000154,"raw_usage":{"total_tokens":1240,"prompt_tokens":1004,"completion_tokens":236,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":173}},"tokens_in":620,"tokens_out":236,"duration_ms":3248,"temperature":1.0,"reasoning_tokens":173,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:42:56.206261+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a self-join-free conjunctive query with an acyclic attack graph and a naturally ordered positive semiring, for instance the bag semiring, for which no LK formula equals the minimum of the query over all repairs; equivalently, find an instance where the identity mCA_K(q,D,α) = Σ_c mCA_K(q[x],D,α(c/x)) of Lemma 4.15 fails, since the inductive rewriting is built entirely on that identity.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Boolean trichotomy for self-join-free conjunctive queries under key constraints; the converse direction of Theorem 4.9 reduces LK-rewritability to this prior FO-rewritability result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Lemma 4.5 on superfrugal repairs, imported in the proof of Lemma 4.15, which is the load-bearing step of the acyclic-to-rewriting direction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the first FO-rewriting of consistent answers for the path query, the motivating example whose guarded minimization pattern the LK rewriting formalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the attack graph notion that the paper adopts as the criterion for rewritability."}],"review_version":1}