Name
Abstract | ||
|---|---|---|
A relational database D is given with @W 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@?@W,b@?@W) 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2007.05.038 | Discrete Applied Mathematics |
Keywords | Field | DocType |
observed data,real value,noisy channel,original size,relational database,low probability,functional dependencies,lower bound,error-correcting functional dependency,minimal error-correcting functional dependency,data mining application,error correction,functional dependency,upper and lower bounds | Row,Discrete mathematics,Combinatorics,Polynomial,Relational database,Tuple,Upper and lower bounds,Communication channel,Functional dependency,Probability of error,Mathematics | Journal |
Volume | Issue | ISSN |
156 | 6 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.48 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Demetrovics | 1 | 414 | 163.60 |
| Gyula O. H. Katona | 2 | 264 | 66.44 |
| Dezs Miklós | 3 | 5 | 0.48 |