| Creator |
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Crossref DOI |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
In this paper we consider incomplete tables over some attribute set and discuss the recovery problem under functional dependencies. An incomplete table is introduced as a table over an attribute set s...uch that each table entry is a subset of the attribute domain instead of just a single value. The recovery problem we consider is to extend the given incomplete table so that each table entry contains only one value and the resulting table will be consistent with a given set of functional dependencies. We show that the recovery problem for incomplete tables such that each table entry is finite is NP-complete. We also give some observation on the unique recoverability. Furthermore, we consider timevariant tables. The recovery problem for time-variaut tables is shown to be PSPACE-complete.show more
|
Export Mendeley
p025