Semi-Skyline Optimization of Constrained Skyline Queries

Proceedings of the 22nd Australasian Database Conference 2011 (ADC), 17-20 January, 2011, Australia, Perth

Abstract: Skyline evaluation techniques (also known as Pareto preference queries) follow a common paradigm that eliminates data elements by finding other elements in a data set that dominate them. Nowadays already a variety of sophisticated skyline evaluation techniques are known, hence skylines are considered a well researched area. On the other hand, the skyline operator does not stand alone in database queries. In particular, the skyline operator may commute with the selection operator which may express hard constraints on the skyline. In this paper, we address skyline queries that satisfy some hard constraints, so-called constrained skyline queries. We will present novel optimization techniques for such queries, which allow more efficient computation. For this, we propose semi-skylines which can be used effectively for algebraic optimizations of skyline queries having a mixture of hard constraints and soft preference conditions. All our efficiency claims are supported by a series of performance benchmarks.