Transitivity-preserving skylines for partially ordered domains

The skyline of a set P of multi-dimensional points (tuples) consists of those points in P for which no clearly better point in P exists, using component-wise comparison on domains of interest. The guiding idea is to prune large data sets to a more manageable size, while ensuring that points of interest are preserved. However, when domains are only partially ordered, it easily happens that the skyline is nearly as large as the original set (or at least of the same order of magnitude), since most of the time points are incomparable in at least some dimension. To obtain a smaller, more useful skyline set which better reflects actual user preferences, we propose a richer notion of dominance, based on two assumptions: that preference specifications are often incomplete, and that actual preferences are transitive.