There has been interest recently in skyline queries, also called Pareto queries, on relational databases. Relational query languages do not support search for "best" tuples, beyond the ORDER BY statement. The proposed skyline operator allows one to query for best tuples with respect to any number of attributes as preferences.

The skyline operator offers a powerful mechanism for expressing preference queries over relational databases. Straightforward evaluation of skyline queries by current relational engines, however, is prohibitively expensive. An efficient algorithm for skyline is needed.

In this work, we explore what the skyline means, and why skyline queries are useful, particularly for expressing preference. We develop an algorithm for computing skyline queries that is well-behaved and efficient, particularly within a relational setting. There have been two substantial efforts to date to develop algorithms for computing skyline in the relational context. Our algorithm improves on these in efficiency, pipelinabilty of output (of the skyline tuples), stability of run-time performance, and being applicable in any context.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.