Efficient Discovery of Relaxed Functional Dependencies

This paper studies the discovery of relaxed functional dependen-cies (RFDs). We consider RFDs that relax restrictions in both value equality and constraint satisfaction: treating values as equal if their distance is less than a given similarity threshold, and consider-ing RFDs with violations below a given error threshold as valid. As a highly non-trivial extension of the row-based approach to functional dependency (FD) discovery, we present the first algo-rithm capable of discovering all valid and minimal RFDs. We extend the structure called “difference-set” for predicates that are combina-tions of attributes and similarity thresholds. We present an efficient method for difference-set construction, incorporating optimizations for both time and space complexity.