Functional dependencies distorted by errors

A relational database D is given with Q as the set of attributes. We assume that the rows (tuples, data of one individual) are transmitted through a noisy channel (or, as many times in case of the data mining applications, the observed data is distorted from the real values in a manner which we cannot know). In case of low probability of the error it may be supposed that at most one data in a row is changed by the transmission or observation. We say that A -> b (A subset of Omega, b epsilon Omega) is an error-correcting functional dependency if the data in A uniquely determine the data in b in spite of this error. We investigate the problem how much larger a minimal error-correcting functional dependency can be than the original one. We will give upper and lower bounds showing that it can be considerably larger than the original sizes, but the growth is only polynomial. (C) 2007 Elsevier B.V. All rights reserved.