论文库

原文摘要

Functional dependencies are used to flag erroneous cells, but without error labels the value of these flags is unknown. Dependency strength cannot settle it, because identical data and flags can have positive value in one clean state and negative value in another. We treat this value as partially identified and certify a fixed detector when its value is positive in every clean state compatible with the observation under an error model and budget. The largest such budget is the certification radius. For a detector that flags departures from the unique mode of each class, the worst case reduces to a 0/1 knapsack over class flips, yielding sharp bounds on true positives and the exact radius in polynomial time. Allowing bounded legitimate exceptions in the clean data, we derive an exact threshold for the existence of a positive certificate and compute the radius with the same knapsack. Across five relations and 21,981 candidate dependencies, rules with nearly equal $g_3$ and flag rate can have certification margins differing tenfold. Error injection confirms sound certification and shows that, at equal error counts, changing the organization of errors reverses certification outcomes for every tested rule.