FastFDs

FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances. The problem of discovering functional dependencies (FDs) from an existing relation instance has received considerable attention in the database research community. To date, even the most efficient solutions have exponential complexity in the number of attributes of the instance. We develop an algorithm, FastFDs, for solving this problem based on a depth-first, heuristic-driven (DFHD) search for finding minimal covers of hypergraphs. The technique of reducing the FD discovery problem to the problem of finding minimal covers of hypergraphs was applied previously by Lopes et al. in the algorithm Dep-Miner. Dep-Miner employs a levelwise search for minimal covers, whereas FastFDs uses DFHD search. We report several tests on distinct benchmark relation instances involving Dep-Miner, FastFDs, and TANE</font size=-1>. Our experimental results indicate that DFHD search is more efficient than Dep-Miner’s levelwise search or TANE</font size=-1>’s partitioning approach for many of these benchmark instances.