On PAC Learnability of Functional Dependencies

Abstract

This paper presents a PAC learning framework for inferring a set of functional dependencies from example tuples. A simple algorithm which outputs a set of all the functional dependencies consistent with example tuples is considered. Let T be a set of the whole tuples. The error is defined as the minimum $\sum\limits_{t \in V} {p\left( t \right)}$ where V is a set such that a set of functional dependencies is consistent with T−V and p(t) denotes the probability of a tuple t . The number of examples required to infer a set of functional dependencies whose error does not exceed ε with probability at least 1−δ under an arbitrary probability distribution is shown to be $O(\frac{{\sqrt {\ln \tfrac{1}{\delta }} }}{\varepsilon }\sqrt {\left| T \right|} )$ .