Af strength does not reliably predict error detection quality
Strength Is Not Value: Rethinking Approximate Functional Dependency Measures for Error Detection
Databases
Summary
The authors found that measures used to rank approximate functional dependencies by how strong they appear don't consistently pick the best ones for finding data errors. While stronger measures tend to be better at correctly spotting errors (precision), they are less reliable at finding all errors (recall). This means the usual way of sorting these dependencies can miss important mistakes. They suggest treating strength and error detection ability as separate qualities that need their own evaluation.
What this means in practice
- •For data quality teams: Improve error detection by evaluating functional dependencies beyond strength measures alone to better balance precision and recall.
- •For database administrators: Select candidate dependencies with higher detection value rather than relying solely on strength rankings to reduce missed errors.
Authors
Xiaolong Wan, Xixian Han
Abstract
Approximate functional dependency (AFD) strength measures are commonly used to prioritize candidate dependencies, including when selected dependencies support downstream tasks such as error detection. This practice implicitly assumes that dependencies ranked higher by strength are also better candidates for the task they are intended to support. We test this assumption directly for error detection. We evaluate detection value through precision and recall without imposing a single weighting on different error types, and introduce an explicit false-positive/false-negative cost only when a single candidate-selection objective is required. Across three real-world relations from an established AFD benchmark, $1{,}155$ corruption-and-detection runs, and $513{,}480$ candidate-level evaluations, we find a clear asymmetry. Strength measures tend to track precision positively, but their associations with recall are substantially less stable, with both magnitude and direction varying across measures and experimental settings. Strength-based prioritization is also unreliable at the ranking level: top-$k$ sets chosen by strength often have little overlap with those favored by actual detection performance, and strength-based selections can incur substantial regret. An important part of the recall mismatch is associated with structural detection opportunity under the candidate equivalence-class partition, which tracks recall more consistently overall than the strength measures we evaluate. Corruption mechanism and several static structural properties account for selected effects but do not provide a common explanation across settings, leaving part of the mismatch unresolved. Overall, AFD strength and detection value are distinct and should be evaluated separately.