  Many practical scenarios make it necessary to evaluate top-k queries over
data items with partially unknown values. This paper considers a setting where
the values are taken from a numerical domain, and where some partial order
constraints are given over known and unknown values: under these constraints,
we assume that all possible worlds are equally likely. Our work is the first to
propose a principled scheme to derive the value distributions and expected
values of unknown items in this setting, with the goal of computing estimated
top-k results by interpolating the unknown values from the known ones. We study
the complexity of this general task, and show tight complexity bounds, proving
that the problem is intractable, but can be tractably approximated. We then
consider the case of tree-shaped partial orders, where we show a constructive
PTIME solution. We also compare our problem setting to other top-k definitions
on uncertain data.
