Inferring Approximate Functional Dependencies from Example Data

Discovery of Dependencies and Models

This paper proposes a kind of PAC (Probably Approximately Correct) learning framework for inferring a set of functional dependencies. A simple algorithm for inferring the set of approximate functional dependencies from a subset of a full tuple set (i.e. a set of all tuples in the relation) is presented. An experimental result, which confirms the theoretical analysis, is also presented.