  A probabilistic database with attribute-level uncertainty consists of
relations where cells of some attributes may hold probability distributions
rather than deterministic content. Such databases arise, implicitly or
explicitly, in the context of noisy operations such as missing data imputation,
where we automatically fill in missing values, column prediction, where we
predict unknown attributes, and database cleaning (and repairing), where we
replace the original values due to detected errors or violation of integrity
constraints. We study the computational complexity of problems that regard the
selection of cell values in the presence of integrity constraints. More
precisely, we focus on functional dependencies and study three problems: (1)
deciding whether the constraints can be satisfied by any choice of values, (2)
finding a most probable such choice, and (3) calculating the probability of
satisfying the constraints. The data complexity of these problems is determined
by the combination of the set of functional dependencies and the collection of
uncertain attributes. We give full classifications into tractable and
intractable complexities for several classes of constraints, including a single
dependency, matching constraints, and unary functional dependencies.
