Skyline queries with constraints: Integrating skyline and traditional query operators

Multi-objective optimization has been extensively studied in the machine learning literature. And recently the database community adapted the concept as skyline queries focusing mainly on retrieving optimal values from the full-space. In this paper, we consider sub-space skyline queries in a more general database environment, such that the skyline operator does not stand alone in users' queries. In particular, the skyline operator may commute with the selection operator which may express users' preferences or constraints on the skylines; we call this class skyline queries with constraints. Queries in this class are different from constrained skyline queries as described in the literature. We introduce an algorithm to answer sub-space skyline queries with constraints. We investigate the conditions under which the two classes of queries are equivalent; this allows for more efficient computation of skyline queries. Unlike the previous works, we do not design a new index specifically for handling the skylines. We try to make full use of the resources available in traditional relational databases for skyline computation. Further, we consider the case when the constraints are absent. We study the relationship between the skylines of different sub-spaces and record this information in a special data structure to help in pruning the search space. (C) 2009 Elsevier B.V. All rights reserved.