A relational database D is given with Ω as the set of attributes. The rows (tuples, data of one individual) are transmitted through a noisy channel.
It is supposed that at most one data in a row can be changed by the transmission. We say that A → b (A ⊂ Ω, b ∈ Ω) is an error-correcting functional dependency if the data in A uniquely determine the data in b in spite of the error. We investigate the problem how much larger a minimal error-correcting functional dependency can be
than the original one.
The work of the second and third author was supported by the Hungarian National Foundation for Scientific Research grant numbers
T016389, T029255