Exploiting Indifference for Customization of Partial Order Skylines

TitleExploiting Indifference for Customization of Partial Order Skylines
Publication TypeConference Paper
Year of Publication2006
AuthorsBalke, W. - T., U. Güntzer, and W. Siberski
Conference Name10th International Database Engineering & Applications Symposium (IDEAS)
Conference LocationDelhi, India

Unlike numerical preferences, preferences on at-tribute values do not show an inherent total order, but skyline computation has to rely on partial orderings explicitly stated by the user. In such orders many object values are incomparable, hence skylines sizes become unpractical. However, the Pareto semantics can be modified to benefit from indifferences: skyline result sizes can be essentially reduced by allowing the user to declare some incomparable values as equally desirable. A major problem of adding such equivalences is that they may result in intransitivity of the aggregated Pareto order and thus efficient query processing is hampered. In this paper we analyze how far the strict Pareto semantics can be relaxed while always retaining transitivity of the induced Pareto aggregation. Extensive practical tests show that skyline sizes can indeed be reduced about two orders of magnitude when using the maximum possible relaxation still guaranteeing the consistency with all user preferences.

ideas06.pdf353.98 KB