  Restricted skyline (rskyline) query is widely used in multi-criteria decision
making. It generalizes the skyline query by additionally considering a set of
personalized scoring functions F. Since uncertainty is inherent in datasets for
multi-criteria decision making, we study rskyline queries on uncertain datasets
from both complexity and algorithm perspective. We formalize the problem of
computing rskyline probabilities of all data items and show that no algorithm
can solve this problem in truly subquadratic-time, unless the orthogonal
vectors conjecture fails. Considering that linear scoring functions are widely
used in practical applications, we propose two efficient algorithms for the
case where $\calF$ is a set of linear scoring functions whose weights are
described by linear constraints, one with near-optimal time complexity and the
other with better expected time complexity. For special linear constraints
involving a series of weight ratios, we further devise an algorithm with
sublinear query time and polynomial preprocessing time. Extensive experiments
demonstrate the effectiveness, efficiency, scalability, and usefulness of our
proposed algorithms.
