{"id":"469ab5af-69d2-4921-9a08-e00e601b37ae","arxiv_id":"2607.23636","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.5,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"pFD discovery (PerValue and PerTuple) is implemented in Desbordante and shown to find different dependencies than AFDs, at higher runtime and usually lower memory.","lead":"The authors add probabilistic functional dependency (pFD) discovery to the Desbordante profiler and compare it with approximate FDs. The work shows pFDs and AFDs are not interchangeable and reports runtime, memory, and output differences on real datasets.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"Table VI's \"non-inferable pFD\" counts — the paper's core evidence that AFDs can't proxy pFDs — compare metrics at numerically equal but semantically mismatched thresholds, and the residue rests almost entirely on PerValue, whose non-monotonicity the unchanged TANE pruning never addresses.","rationale":"The reader's weakest assumption and mine occupy the same region — the sufficiency of the RQ1 quantitative evidence — but identify different mechanisms, hence \"partial.\" The reader asked: even if the extra/missing rules are real, do they help users (no gold-standard recovery, no cleaning/dedup task)? My concern is upstream: the \"extra/missing rules are real and essential\" evidence (Table VI's non-inferable column) is itself confounded, because numerically matched thresholds do not correspond to matched strictness across a pair-fraction metric (e), a tuple-fraction metric (g3/PerTuple), and an unweighted per-group average (PerValue). The overlap of only 9–10 dependencies at ε=0.01 out of ~130 is exactly what one would expect from operating-point divergence, and the fact that PerTuple contributes ≤2 non-inferable dependencies at every threshold means the headline \"discovery returns dependencies neither minimal AFDs nor inferable from them\" is carried almost entirely by PerValue at high error thresholds — the least decision-relevant regime by the paper's own framing. I also flag, as a correctness risk rather than an established flaw, that the paper's own observation that PerValue is non-monotone under LHS extension is never reconciled with the pruning machinery of the modified TANE it reuses; §IV describes changing only the validation functions. This is checkable cheaply because monkeypox has only 14 attributes, making exhaustive ground truth feasible.\n\nI do not raise the performance/memory half of the claim as load-bearing, though one detail is worth the authors' attention: AFDTane memory in Table VII is ~1490 MB for five very different datasets (EpicVitals 1.2M rows/7 attrs; nuclear explosions 2K rows/16 attrs), a constant suggestive of a fixed allocation rather than algorithmic demand, which could make the favorable memory ratios in Tables XI–XII partly an implementation artifact. This is secondary to the threshold-calibration concern.\n\nVerdict stays UNCHANGED (reader's CONDITIONAL): no mathematical contradiction exists — the qualitative non-containment is proven by the toy examples and the metric definitions — the implementation and measurement contribution stands regardless, and my concern is fixable with one inexpensive computation. But the condition for acceptance should be sharpened from the reader's \"add a value evaluation\" to include the exact check described: verify pruning soundness against exhaustive ground truth on monkeypox and recompute the non-inferable residue at strictness-matched thresholds. If the residue survives matching, the paper's central empirical claim is genuinely supported and the CONDITIONAL can resolve toward accept; if it collapses, Table VI should be reframed as demonstrating threshold non-transferability rather than essential representational difference.","tokens_in":31234,"tokens_out":1501,"duration_ms":1257895,"concrete_test":"Exploit monkeypox's small width (14 attributes, 5875 rows): enumerate all X→A candidates (2^14 × 13) and compute e, PerValue, PerTuple exactly. (a) Verify pFDTane-PerValue/PerTuple and AFDTane outputs equal the true minimal sets at each Table VI threshold; any missing/extra minimal pFD localizes unsound pruning. (b) For every true minimal pFD, look up its exact g1 error, and recount \"non-inferable pFDs\" after matching thresholds by output size (e.g., AFD ε′ chosen so |AFDs|=|pFDs|). If the 29–30 residue collapses toward PerTuple levels (0–2) under size-matched thresholds, the essential-difference evidence is a calibration artifact; if a residue persists at matched operating points with verified-correct outputs, the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim has a qualitative half (minimal pFDs and minimal AFDs are mutually non-contained), which the toy tables (Obs. 1–2, arithmetic checks out: 0.625, 3/11, 3/55) establish by construction, and a quantitative half carried by Table VI on monkeypox.csv. The load-bearing condition for the quantitative half is that the set differences — especially the \"Non-inferable pFDs\" column the paper itself introduces to \"highlight the essential difference\" — reflect genuine semantic divergence rather than a calibration artifact. That condition is insecure on two grounds.\n\n(1) Threshold-scale mismatch. The AFD error e is a fraction of violating tuple pairs (normalized by |r|²−|r|); PerTuple error is the fraction of tuples to delete (g3); PerValue is an unweighted average of per-group majority fractions. The same number means different strictness in each metric (for a size-n cluster with one bad tuple, e ≈ 2(n−1)/(|r|−1) while g3 = 1/|r|; PerValue doesn't weight by cluster size at all). A red flag in Table VI itself: at ε=0.01 only 9–10 of ~130 minimal deps overlap. That pattern is consistent with the algorithms simply operating at different points of their respective scales, in which case the dramatic |pFDs\\AFDs| counts (133, 153) quantify \"0.01 means different things\" more than \"pFDs capture different knowledge.\" Notably the PerTuple non-inferable residue is ≤2 at every threshold; the claim that discovery returns non-inferable dependencies is carried almost wholly by PerValue at ε=0.2–0.3 (29, 30) — precisely the high-threshold regime the paper elsewhere says is of least user value.\n\n(2) PerValue non-monotonicity vs. unchanged pruning. The paper states PerValue error can increase when extending the LHS, and that only the validation functions were changed in its modified TANE. TANE-style candidate pruning (C+ intersection rules, superkey/vertex pruning) is justified by error monotonicity under LHS augmentation, which holds for g1/g3 but not PerValue. If any pruning of","agreement_with_reader":"partial"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The manuscript adds probabilistic functional dependency (pFD) discovery to the Desbordante profiler and studies pFDs relative to approximate functional dependencies (AFDs). The authors (i) review the g1/g2/g3 metric family and the relaxed-dependency literature built on it; (ii) give qualitative toy examples (Tables IV–V, Observations 1–2) showing that the PerValue and PerTuple measures respond differently to error patterns than the g1-based AFD error e; (iii) implement pFDTane by swapping the candidate-validation function of their TANE implementation with PLI-based PerValue/PerTuple validators; and (iv) evaluate run time and memory across nine public datasets with repeated runs and 95% confidence intervals (RQ2–RQ4), and compare the sets of minimal dependencies returned by AFDTane and pFDTane on monkeypox.csv (Table VI, RQ1). The headline claims are that minimal pFDs and minimal AFDs are mutually non-contained at a fixed error threshold — including pFDs not inferable from the minimal AFD set — and that pFDTane is typically slower but more memory-frugal than AFDTane.","tokens_in":19817,"tokens_out":3416,"duration_ms":69587,"significance":"If the results hold, the paper makes a useful systems contribution: to the authors' knowledge the first open-source C++ pFD discovery implementation, integrated into a maintained profiler and released via a public pull request (PR 300), with dataset links provided. The empirical methodology is a strength for this venue: nine external datasets spanning three orders of magnitude in size, 10–30 repeated runs per configuration, reported confidence intervals, and both time and memory metrics. The qualitative analysis (Observations 1–2) is correct — I verified the arithmetic (PerValue 5/8, g3 3/11, e 3/55) — and cleanly establishes by construction that the measures weight violations differently. The related-work survey of g1/g2/g3-based primitives is a serviceable reference. The main risk to significance is that the quantitative half of RQ1 (Table VI) may partly measure threshold-scale mismatch rather than semantic divergence, and that the correctness of the PerValue discovery results rests on a monotonicity property the paper itself notes does not hold.","major_comments":[{"comment":"The set-difference counts compare AFDs and pFDs at numerically equal error thresholds, but the three measures have different scales and semantics: e is a fraction of violating tuple pairs (normalized by |r|²−|r|), PerTuple = 1−g3 is a fraction of tuples to delete, and PerValue is an unweighted average of per-group majority fractions. For a size-n cluster with one offending tuple, e ≈ 2(n−1)/(|r|−1) while g3 = 1/|r|, and PerValue ignores cluster size entirely. Table VI itself shows the symptom: at ε=0.01 only 9–10 of ~130 minimal dependencies overlap. The large |pFDs \\ AFDs| counts (133, 153) may therefore quantify '0.01 means different things in each metric' rather than genuine semantic divergence. The paper's own 'Non-inferable pFDs' column mitigates this only partially, and that residue is carried almost entirely by PerValue (PerTuple non-inferable counts are 1, 2, 0, 0, 2). The claim","section":"§V.B, Table VI (RQ1 quantitative part)"},{"comment":"The paper correctly notes that PerValue is not preserved under LHS extension ('this is not always true in case of pFD PerValue'), i.e., the error measure is not anti-monotone in X. TANE's lattice pruning (vertex exclusion based on discovered minimal dependencies, and the C⁺-based candidate filtering) is sound only for anti-monotone error measures. The manuscript states that 'error measurement functions ... [are] the essentially only part which had to be changed' — i.e., the pruning logic is unchanged — but never discusses whether the pruning remains correct for PerValue. If it does not, the reported 'minimal pFD PerValue' sets (Tables VI and VIII) may be incomplete (missed minimal pFDs) or contain non-minimal ones, which would directly undermine the PerValue columns of Table VI that carry the RQ1 conclusion. The authors must either prove that the specific prunings they retain are safe fo","section":"§II (minimality remark) and §IV (Candidate Validation)"},{"comment":"The pseudocode iterates over all tuples t ∈ R and appears to require the relation sorted by (X, A), which contradicts the surrounding text claiming PLI-based validation that 'does not iterate over single value clusters'. This matters specifically for PerValue: stripped partitions drop singleton clusters, but singletons both contribute probability 1 to the numerator and count toward |DX| in the denominator, so a validator over stripped PLIs cannot compute PerValue without separately tracking the number of stripped clusters. As written it is unclear what the implementation actually does. Additionally, both listings omit the final-group flush (the last cluster's maxCount/count is never added to sum after the loop ends), and count(c′) is reset to 0 rather than 1 on group transitions. Please reconcile the pseudocode with the PLI-based implementation and state precisely how singleton clusters","section":"§IV, Algorithms 3 and 4"}],"minor_comments":[{"comment":"The set-difference analysis is performed on a single dataset (monkeypox.csv). Even a qualitative spot-check on one or two additional datasets from Table VIII would strengthen the generalizability of the RQ1 conclusion, and would help separate threshold artifacts from dataset-specific effects.","section":"§V.B, Table VI"},{"comment":"The caption reads 'EXACT FDs DISCOVERY TIME AND MEMORY' but the section measures candidate-validation cost of the three validators at error 0 as a proxy. Since error 0 collapses all three measures to exact FD checking, the table primarily reflects per-candidate validator overhead; please state this interpretation explicitly and clarify that lattice traversal is identical by construction.","section":"§V.C, Table VII"},{"comment":"Memory ratios are constant (to three decimals) across nearly all error thresholds for most datasets (e.g., 0.356 for jena_climate, 0.127 for nuclear_explosions). This suggests memory is dominated by threshold-independent structures (PLIs); a one-sentence explanation would preempt reader confusion. Also, absolute AFDTane memory in Table VII is suspiciously flat (1490–1491 MB across five datasets of very different sizes) — worth a comment on the measurement method.","section":"§V.E, Tables XI–XII"},{"comment":"The AFD threshold subset (captions of Tables IX–XII, 0.025–0.5) is justified by user relevance, but Table VI uses 0.01–0.3 and Table VIII uses 0.01; please harmonize or explain the three different grids. Also state explicitly whether 'error threshold' for pFDs means 1−p throughout.","section":"§V.A"},{"comment":"Axis labels and legends are partly garbled in the rendered figures (e.g., 'nuclear_expl si ns', 'E icVitals', ' arking_citations'), and Figure 4's y-axis mixes 'MB' and 'bytes' units. Legends in Figures 3–4 are dense; consider per-dataset panels or tables.","section":"Figures 2–4"},{"comment":"Minor language issues: 'quantatively' (§V.B), 'how much AFDs are lost by it', 'lets denote', 'data interpretation and data context leave room for both of them' (§VI). The UML diagram (Fig. 1) is low-resolution and its caption does not explain the aggregation/composition relations the text refers to.","section":"Throughout"},{"comment":"The pFD definition block has notational rough edges: '(VY, VX1)' is used as a set name, 'X1 attributes of X' is garbled, and the argmax in the definition of the majority-value subset is not defined for ties. A cleaner restatement in terms of per-equivalence-class majority frequency would help readers.","section":"§II"}],"recommendation":"major_revision","confidential_remarks":"The systems contribution (open-source pFD support in Desbordante, PR 300) and the performance study are solid and in scope. The two correctness-adjacent concerns — threshold-scale mismatch in Table VI and the unaddressed interaction between PerValue's non-monotonicity and TANE pruning — are both fixable within the manuscript's scope (a threshold-sweep recovery analysis and either a correctness argument or a completeness check), but they are load-bearing for the RQ1 headline and should not be waved through. I did not verify the PR code; if the editor can solicit an artifact check, the pseudocode/PLI inconsistency in §IV could be settled quickly."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The useful core is straightforward: they put PerValue and PerTuple pFD discovery into Desbordante’s TANE/PLI stack (claimed as the only open C++ path), correctly tie PerTuple to 1−g3, and run a head-to-head against their g1-AFD TANE on time, memory, and minimal-set overlap across several public CSVs with repeats and CIs. The two toy tables check out arithmetically and make the qualitative point that PerValue tolerates different violation patterns than pair-error AFDs. The g1/g2/g3 survey is also a clean, usable catalogue. Code and data links are there.\n\nWhat is actually new is the integrated implementation plus the systematic side-by-side numbers (Tables VI–XII), not the definitions themselves. On the strongest claim—minimal pFDs and AFDs are not subsets of each other at a fixed numeric threshold—the toys establish mutual non-containment by construction, and monkeypox shows non-empty residues. That is enough to stop people treating AFD discovery as a free proxy.\n\nThe soft spots are real but proportionate. The end-user-value half of RQ1 rests on those toys plus set-difference counts, not a gold-standard recovery, cleaning, or dedup task; that is the weakest link. The stress-test point on threshold semantics also lands: e, g3, and PerValue are not the same scale, so large |pFD\\AFD| at ε=0.01 partly reflects calibration, and the “non-inferable” column is carried almost entirely by PerValue at higher ε where the paper itself says users care less. Separately, they note PerValue is not always monotonic under LHS growth yet only swapped the validators; classic TANE pruning assumptions are left unexamined. Minor: AFD baseline is their TANE, not PYRO, though they own both.\n\nMath and citations look solid; no circularity. This is for people building or choosing profilers and relaxed-dependency miners. I would send it to referees—engineering contribution is checkable and the comparison is worth having—while expecting them to demand a clearer value experiment and a note on PerValue pruning. Engage if you care about Desbordante or dirty-data FDs; otherwise skim the tables and move on.","headline":"Real open pFD implementation plus careful cost/output comparison to g1-AFDs; the non-interchangeability claim is directionally right but the value evidence and PerValue/TANE fit are thinner than the tables suggest.","tokens_in":20829,"tokens_out":596,"would_cite":false,"duration_ms":23186,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Probabilistic functional dependencies are not interchangeable with approximate ones: at the same error threshold they return different minimal rules, so AFD discovery cannot serve as a proxy for pFDs.","keywords":["data profiling","probabilistic functional dependencies","approximate functional dependencies","TANE","g3 metric","relaxed dependencies","position-list index"],"falsifier":"Run both discoverers on a data set that has a known gold-standard set of true functional dependencies (or a downstream cleaning/deduplication task with a measurable quality metric) and check whether the pFD-only rules improve recall, precision or end-task accuracy relative to the AFD-only rules at matched error thresholds.","tokens_in":20418,"feed_emoji":"📊","tokens_out":910,"duration_ms":23019,"temperature":0.7,"pith_summary":"Real tables are dirty, so exact functional dependencies almost never hold and profilers must relax them. The popular relaxation is the approximate functional dependency (AFD) based on a g1-style pair-error; another, less-studied relaxation is the probabilistic functional dependency (pFD) based on the g3-style fraction of tuples that must be deleted. This paper shows, with both hand-built examples and counts on public CSVs, that the two notions tolerate different violation patterns and that the sets of minimal rules they return are not subsets of each other. It then supplies the first open-source C++ implementation of pFD discovery (a TANE variant supporting both PerValue and PerTuple probabilities), measures its run-time and memory against an AFD baseline, and concludes that both primitives belong in a science-intensive profiler because neither can substitute for the other.","feed_headline":"pFDs and AFDs return different dirty-data rules","feed_subtitle":"Same error threshold, different minimal dependencies—so one discovery algorithm cannot replace the other","key_machinery":"pFDTane — a lattice-traversal algorithm obtained from TANE by replacing the candidate-validation step with the PerValue or PerTuple probability (equivalently 1-g3) computed from position-list indexes.","core_discovery":"With a fixed numeric error threshold, the minimal non-trivial pFDs (PerValue or PerTuple) discovered on a relation are in general neither a subset nor a superset of the minimal AFDs; some pFDs are not even inferable from the AFD set. Consequently an AFD discovery algorithm cannot be used as a faithful proxy for pFD discovery, and vice versa. Empirically the pFD validator is slower than the AFD validator yet often consumes less memory.","pith_inferences":["The same lattice infrastructure can be reused for any other g3-based primitive (approximate INDs, GEDs, AITFDs) simply by swapping the validation oracle.","A hybrid error measure that mixes PerValue and pair-counting could give analysts a continuous knob between the two violation styles the paper separates.","If downstream tools begin to consume pFD confidence scores rather than binary AFD flags, the slower validation cost may be amortised by richer ranking and explanation features."],"forward_implications":["A profiler that already offers AFDs should also offer pFDs if it wants to cover the full range of g1/g3-style relaxations.","Users who care about “local” sensor-style faults (few distinct LHS values that are heavily corrupted) will prefer PerValue pFDs; users who care about global tuple deletion will prefer PerTuple or AFDs.","Because pFD discovery is slower but leaner in memory, implementers can trade the two resources by choosing which primitive to expose first.","Existing AFD result sets cannot be post-processed into pFD result sets without re-running validation under the other metric."],"fun_headline_variants":["pFDs and AFDs yield different minimal dirty-data dependencies","Fixed error threshold: pFD and AFD minimal sets diverge","Neither pFD nor AFD discovery can proxy the other","Minimal pFDs neither subset nor superset of AFDs","pFD validator slower than AFD yet often leaner on memory"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"That counting extra or missing minimal rules on a handful of public CSVs, plus two toy tables, is enough to prove that the two notions give end-users genuinely different value.","fun_headline_variants_meta":{"raw":{"variants":["pFDs and AFDs yield different minimal dirty-data dependencies","Fixed error threshold: pFD and AFD minimal sets diverge","Neither pFD nor AFD discovery can proxy the other","Minimal pFDs neither subset nor superset of AFDs","pFD validator slower than AFD yet often leaner on memory"]},"model":"grok-4.5","effort":"low","cost_usd":0.003977,"raw_usage":{"total_tokens":1294,"prompt_tokens":838,"num_sources_used":0,"completion_tokens":74,"cost_in_usd_ticks":39768000,"prompt_tokens_details":{"text_tokens":838,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":382,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":838,"tokens_out":74,"duration_ms":6167,"temperature":1.0,"reasoning_tokens":382,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T16:58:25.744773+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run both discoverers on a data set that has a known gold-standard set of true functional dependencies (or a downstream cleaning/deduplication task with a measurable quality metric) and check whether the pFD-only rules improve recall, precision or end-task accuracy relative to the AFD-only rules at matched error thresholds.","supporting_citations":[],"review_version":1}