Anytime Algorithms for Approximate Functional Dependencies

摘要

We propose a computational framework for identifying approximate functional dependencies (AFDs) in a relation, leveraging the frequency distribution information of individual attributes. This framework operates without requiring access to the full database, processing records one at a time as necessary. Our approach generalizes existing measures for quantifying errors in perfect dependencies and formalizes two primary problems: finding top-k AFDs and identifying all AFDs within a specified error threshold, ε. Our pro posed framework provides anytime solutions, meaning it returns results after processing each record. A key innovation of our work lies in effectively estimating error bounds of the candidate AFDs, which allows to produce anytime solutions. We present an exact algorithm that delivers precise solutions when possible. We also develop an algorithm that always returns a solution albeit with some imprecision in the output. We demonstrate the applicability of these algorithms under various data organization strategies, such as indexing by key or key-like attributes. Our experimental results, based on both real-world and synthetic datasets, validate the effectiveness of our approach and show that it outperforms state-of-the-art solutions.