ON PAC LEARNABILITY OF FUNCTIONAL-DEPENDENCIES

This paper proposes a kind of probably approximately correct (PAC) lea rning framework for inferring a set of functional dependencies (FDs) f rom example tuples. A simple algorithm is considered that outputs a se t of all FDs which hold in a set of example tuples. Let r be a relatio n (a set of tuples). We define the error for a set of FDs FS as the mi nimum SIGMA(t is-an-element-of nu P(t); where nu (nu subset-of r) is a set such that FS holds in r - nu, and P(t) denotes the probability th at tuple t is picked from r. Our attention is focused on the sample co mplexity, and we show that the number of example tuples required to in fer a set of FDs whose error does not exceed epsilon with probability at least 1 - delta under an arbitrary probability distribution is O((s quare-rootln(1/delta)/epsilon)square-root\r\).