{"id":"c8709376-986f-4a7b-af6f-7ba4f79f66a0","arxiv_id":"2607.24021","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EviDC builds a prefix tree of existing denial constraints (DCTrie) and uses it to prune incremental evidence construction, reducing runtime and evidence size versus IncDC and 3DC on tested workloads.","lead":"This paper proposes EviDC, an algorithm that uses the structure of existing denial constraints to guide how evidence is built when new rows are added to a database, pruning work that cannot lead to a constraint violation. It reports large speedups and less intermediate evidence than two prior incremental methods on several real and synthetic datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DCTrie pruning cannot represent numerical predicates ≤, ≥, and ≠, which hold in more than one of the three direction branches; such DC violations are silently pruned.","rationale":"The reader identified the numerical predicate grouping as the weakest assumption, which is the same area as this objection. However, the reader framed it as a domain-modeling assumption about a tuple pair satisfying exactly one direction; the sharper problem is that a single predicate can be true under multiple mutually exclusive directions, so even if each tuple pair lies in exactly one direction, a DCTrie path labeled with that predicate cannot be reached from all relevant branches. This is not merely an efficiency risk: it makes the incremental discovery incomplete for ordinary DCs containing numerical ≠, ≤, or ≥. The experiments and brute-force verifier cannot surface the issue because the reported datasets/DCs apparently exercise only =, <, > on numerical attributes, and the verifier only checks detected invalid DCs against generated violations. This is more load-bearing than the baseline and workload concerns, because if the counterexample reproduces, the central theorem of the paper is false for the stated problem. I recommend REJECT unless the authors explicitly restrict the predicate space or extend DCTrie/refinement to handle implication across branches and prove completeness for that extension.","tokens_in":21346,"tokens_out":17091,"duration_ms":174086,"concrete_test":"Run the following unit test on the released or reimplemented EviDC code. Use schema (A int, B varchar, C int). Load r = {(1,'a',0), (1,'a',1), (2,'b',2)} and insert the DC φ = ¬(t.A ≠ s.A ∧ t.B = s.B) into DCTrie (the paper's construction must be able to encode it, since ≠ is in the predicate space). Insert tuple (0,'a',3). A brute-force verifier should report (0,'a',3) and (1,'a',0) as a violating pair, so φ is invalid. Check whether EviDC reports φ as invalid. If it does not, the pruning has lost a genuine violation path; repeat with φ = ¬(t.A ≤ s.A ∧ t.B ≠ s.B) and a violating equal-A pair to confirm the same failure for ≤. The test settles whether the algorithm is complete for the full predicate space.","verdict_should_be":"REJECT","load_bearing_attack":"Section IV-B groups numerical predicates into three truth sets {=,≥,≤}, {>,≥,≠}, {<,≤,≠}, but Algorithms 4–5 refine only along three concrete direction predicates: peq (equality), plt (less-than), pgt (greater-than). Meanwhile, Algorithm 2 stores each DC predicate as an exact node label on a single root-to-leaf path. This creates a mismatch: a predicate such as ≤ is true in both the equality and less-than branches; ≥ is true in both equality and greater-than; ≠ is true in both less-than and greater-than (and is the default in all three sets). A context whose actual direction is, say, less-than will call T.ADVANCE(A, plt), which follows nodes labeled exactly by plt and wildcard-only nodes, not nodes labeled ≤ or ≠. If the DC contains such a predicate, the context's Active set becomes empty and the context is pruned before later layers are tested. Theorem 4.1 therefore fails: real violations of DCs containing numerical ≤, ≥, or ≠ are silently missed.\n\nConcrete counterexample: let r = {t1=(1,'a',0), t2=(1,'a',1), t3=(2,'b',2)} with numeric attribute A, categorical B, and the minimal DC φ = ¬(t.A ≠ s.A ∧ t.B = s.B). φ holds on r: the pairs with equal B are t1,t2, and for those A is equal. Insert t4=(0,'a',3). The pair (t4,t1) satisfies A≠ (0≠1) and B= ('a'='a'), so φ is invalid on the updated instance. But at the A layer, (t4,t1) lies on the less-than branch, and T.ADVANCE(plt) does not follow a node labeled ≠. The context is pruned, and B is never tested. Symmetric insertion does not help because the symmetric form of this DC is the same predicate set.\n\nThe paper does not state any normalization of DC predicates to =,<,> or any duplication of a predicate node across multiple direction branches. As written, the algorithm is incomplete for the general DC predicate space defined in Section III.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes EviDC, an incremental denial-constraint discovery algorithm for tuple insertions. It organizes the existing DC set into a prefix trie called DCTrie, treats each root-to-leaf path as a potential violation path, and during incremental evidence construction advances only along active trie nodes, pruning contexts that cannot reach any remaining path. It then removes invalid DCs and repairs them by single-predicate extension. Experiments on eleven datasets compare runtime, intermediate evidence size, memory, and scalability against 3DC* and IncDC, reporting substantial savings in most settings, and a brute-force verifier reports exact precision/recall on four datasets.","tokens_in":21694,"tokens_out":12833,"duration_ms":144691,"significance":"If correct, the central idea is worthwhile: using the structure of existing DCs to guide evidence construction is a natural way to avoid materializing evidence that cannot match any DC, and the empirical results suggest the pruning can be effective. The paper provides correctness theorems, a brute-force invalid-DC check on four datasets, and comparisons against re-implemented and public baselines. However, the completeness claim currently fails for a common class of numerical predicates because the trie representation and the refinement directions are not aligned. The contribution is therefore conditional on a corrected representation and re-validated experiments.","major_comments":[{"comment":"The refinement procedure is incomplete for numerical predicates. Section IV-B groups the six numerical operators into three direction sets, but Algorithms 4–5 advance only with concrete peq/plt/pgt, and Algorithm 2 stores each DC predicate as an exact node label on one root-to-leaf path. Predicates ≤, ≥, and ≠ are true in more than one direction, so a path stored under one label cannot be reached when refinement follows another satisfying direction; the context is pruned. Concretely, for R(A numeric, B categorical) and φ=¬(t.A≠s.A ∧ t.B=s.B), which holds on r={(1,'a',0),(1,'a',1),(2,'b',2)}, inserting t4=(0,'a',3) violates φ via (t4,t1). The DCTrie path contains A≠, but the less-than refinement calls T.ADVANCE(plt), which does not follow a node labeled ≠, so the violating pair is pruned and Theorem 4.1 fails.","section":"§IV-B, Algorithms 2/4/5, Theorem 4.1"},{"comment":"The brute-force verification covers only FD15, Hospital, Claim, and Atom. It checks invalid-DC sets, but nothing in the paper indicates that those experiments exercise the numerical operators ≤, ≥, or ≠. Since the completeness bug above concerns exactly those operators, the reported precision/recall cannot validate Theorem 4.1. A targeted correctness test with DCs containing these predicates—or a corrected proof—is needed, and the evidence-size/runtime measurements should be repeated under the fixed representation, since a complete representation may require replicating paths across multiple direction branches.","section":"§V-A, Table IV"}],"minor_comments":[{"comment":"T.ADVANCE is never formally defined. The text says nodes correspond either to a predicate or to a set of simultaneously satisfied predicates, while Algorithm 2 creates nodes labeled by individual predicates. Clarify the mapping between DC predicates, direction groups, and trie labels; the correctness proof depends on this.","section":"§IV-B, Algorithm 2"},{"comment":"The proof reuses the variable e inconsistently: it first denotes a violating evidence in Eφ and later denotes an arbitrary evidence that falsifies the repaired DC. Rewrite the proof by observing that any evidence containing φ′ also violates φ, so it belongs to Eφ and cannot contain p ∈ Padd.","section":"§IV-E, Theorem 4.2"},{"comment":"If a DC contains more than one predicate from the same attribute group, the recursive insertion places only one of them on each resulting path. State explicitly that minimal DCs are assumed to have at most one predicate per attribute group, or handle multiple same-group predicates in the trie construction.","section":"Algorithm 2, lines 16–18"},{"comment":"The node labels D0–D15 and the green nodes in Figure 2 are not explained in the caption or text, making the worked example hard to follow. Also, Figure 1 contains the typo 'DCTire Builder'.","section":"Figures 2–3"},{"comment":"The reimplementation 3DC* is not released. Given the large reported speedups, releasing the artifact (EviDC and the 3DC* reimplementation) would substantially strengthen reproducibility.","section":"§V-A"}],"recommendation":"major_revision","confidential_remarks":"The numerical-predicate issue is load-bearing: as written, Theorem 4.1 is false and the algorithm silently misses real violations. I recommend major revision rather than rejection because the core idea is likely salvageable by a multi-label or replicated-branch DCTrie, but the authors must supply a correct representation, a revised completeness proof, and targeted experiments with ≤/≥/≠. If they cannot, the paper should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the EviDC paper carefully. The core idea is genuinely new: build a prefix trie from the existing DC set and use it to prune incremental evidence construction. That's a real departure from IncDC and 3DC, and the reported reductions in intermediate evidence are plausible. The experiments are substantial, and the brute-force verifier for invalid-DC detection is a good habit. If the pruning were sound, this would be a solid incremental-maintenance contribution.\n\nIt isn't sound for the problem as defined. The predicate space includes all six numeric operators (<, ≤, >, ≥, =, ≠), and Algorithm 2 stores each DC predicate as an exact node label. But Algorithm 5 advances numerical contexts only along three representative predicates: =, <, and >. T.ADVANCE follows children labeled exactly with that representative (plus wildcards). So a DC containing ≤, ≥, or ≠ is only reachable if a tuple pair's actual direction happens to be the representative that matches that node. For most pairs it isn't. Consider a dataset with tuples (1,'a',0), (1,'a',1), (2,'b',2) and the minimal DC ¬(t.A ≠ s.A ∧ t.B = s.B). Insert (0,'a',3). The pair (0,'a',3),(1,'a',0) violates the DC, but at the A layer it is on the less-than branch and T.ADVANCE(<) does not follow the node labeled ≠. The context is pruned; the violation is missed. The same happens for ≤ and ≥. Theorem 4.1's proof assumes the trie contains a path along the direction of the current refinement predicate; that assumption is false for these operators. I don't see a normalization or duplication step in the paper that fixes this. This is not a corner case: ≤, ≥, and ≠ are in the declared predicate space and can appear in minimal DCs.\n\nThe evaluation has additional soft spots: 3DC* is a reimplementation, IncDC OOMs in many of the settings where EviDC looks best, and the violation tuples are generated from the same initial DC set that builds the trie. The repaired DC set is only checked for soundness, not completeness or minimality. These are all addressable, and none of them would change the correctness issue above.\n\nBottom line: the idea is promising and worth a serious referee, but the paper as written is unsound for the full predicate space. The authors should either restrict the algorithm to <, =, > predicates or make the trie follow all predicates implied by a tuple pair's true direction. Then it could be a good paper. I'd send it to reviewers with the expectation of heavy revision, but I wouldn't accept it now.","headline":"The pruning idea is fresh, but the DCTrie traversal silently misses violations for numeric DCs containing ≤, ≥, or ≠ — a load-bearing correctness bug.","tokens_in":22293,"tokens_out":11228,"would_cite":false,"duration_ms":89420,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"EviDC claims that organizing existing denial constraints into a prefix tree and expanding evidence only along reachable violation paths reduces intermediate evidence and improves runtime in incremental DC discovery.","keywords":["denial constraints","incremental discovery","evidence construction","prefix tree","DCTrie","data quality","integrity constraints","violation-guided pruning"],"falsifier":"Log every pruned evidence context during an EviDC run and replay the same inserted tuples through an exhaustive verifier that checks all tuple pairs against every existing DC; if any tuple pair that violates a DC appears in a pruned context, the pruning has discarded a real violation. A cheaper spot-check: construct a DC containing t.A != s.A on a numerical attribute, insert a tuple pair with t.A < s.A, and verify that EviDC still reports the violation.","tokens_in":21158,"feed_emoji":"🚫","tokens_out":6640,"duration_ms":65596,"temperature":0.7,"pith_summary":"EviDC sets out to show that existing denial constraints can guide the construction of incremental evidence, rather than being checked only after evidence is built. The algorithm organizes the current constraint set into a prefix tree, DCTrie, whose root-to-leaf paths are potential violation paths, and expands evidence for inserted tuples only along reachable branches. The paper reports that this cuts intermediate evidence and runtime compared with IncDC and 3DC in most tested scenarios, with larger gains at higher insertion ratios and dataset sizes. A sympathetic reader would take away that incremental constraint maintenance can be made substantially cheaper by letting the constraints themselves steer the search.","feed_headline":"Prefix tree of violations speeds up incremental constraint checks","feed_subtitle":"EviDC expands data-pair evidence only along reachable violation paths, cutting runtime and memory.","key_machinery":"DCTrie is the load-bearing structure: a prefix-sharing tree in which each DC (and its symmetric form) is inserted as a path across attribute-group layers, with wildcard nodes for attributes a DC does not constrain. Evidence construction proceeds in the same layer order; each evidence context stores the current right-tuple set, partial evidence, and an Active set of trie nodes; context splitting and mask-based evidence refinement advance only along reachable nodes, and an empty Active set terminates the context.","core_discovery":"The central claim is that for incremental denial-constraint discovery under tuple insertions, the set of existing DCs can be repurposed as a trie of violation paths; during incremental evidence construction, each tuple-pair context is refined attribute group by attribute group, and whenever its active set of reachable trie nodes becomes empty, the context is pruned. EviDC is the concrete algorithm that implements this, and the experiments show that it reduces intermediate evidence and runtime in most scenarios, becoming more effective as insertion ratio and dataset size grow. The paper also shows that building DCTrie is far cheaper than building full evidence sets or indexes.","pith_inferences":["The same violation-path idea could be applied to other dependency types (FDs, UCCs, order dependencies) by encoding their violation witnesses as paths.","If DCTrie were updated incrementally as constraints are repaired, the preprocessing advantage could extend to continuous maintenance workloads.","The single-predicate repair strategy is a bottleneck; a multi-predicate extension guided by the trie could yield tighter repaired constraints, at higher enumeration cost.","The model assumes clean comparison semantics; null values or non-standard collations would break the direction grouping and would need explicit handling."],"forward_implications":["Intermediate evidence volume drops because tuple-pair contexts that cannot reach any DC leaf are pruned early.","Runtime is reduced by about 50% versus 3DC in most scenarios, and the gap grows with insertion ratio.","DCTrie construction is sub-second on most datasets, whereas 3DC and IncDC spend hundreds of seconds preprocessing.","Memory usage is lower because only surviving evidence contexts and the trie are kept, not full historical evidence sets.","The method scales roughly linearly with data size in the tested settings."],"fun_headline_variants":["Violation trie prunes evidence for faster incremental DC discovery","Incremental DC discovery speeds up via violation-path pruning","EviDC trie cuts evidence in dynamic data constraint updates","Reachability-aware trie trims evidence in DC updates","Violation prefix tree accelerates incremental DC discovery"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The pruning is sound only if the fixed attribute-group order, the three-direction grouping of numerical predicates, and wildcard inheritance preserve every way a tuple pair can satisfy a DC path; if any combination is missed, a real violation is silently pruned.","fun_headline_variants_meta":{"raw":{"variants":["Violation trie prunes evidence for faster incremental DC discovery","Incremental DC discovery speeds up via violation-path pruning","EviDC trie cuts evidence in dynamic data constraint updates","Reachability-aware trie trims evidence in DC updates","Violation prefix tree accelerates incremental DC discovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000708,"raw_usage":{"total_tokens":2998,"prompt_tokens":690,"completion_tokens":2308,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":434,"completion_tokens_details":{"reasoning_tokens":2227}},"tokens_in":434,"tokens_out":2308,"duration_ms":15430,"temperature":1.0,"reasoning_tokens":2227,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T23:13:03.327912+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Log every pruned evidence context during an EviDC run and replay the same inserted tuples through an exhaustive verifier that checks all tuple pairs against every existing DC; if any tuple pair that violates a DC appears in a pruned context, the pruning has discarded a real violation. A cheaper spot-check: construct a DC containing t.A != s.A on a numerical attribute, insert a tuple pair with t.A < s.A, and verify that EviDC still reports the violation.","supporting_citations":[],"review_version":1}