Skyline with presorting: Theory and optimization

Abstract. 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. In this work, we explore what the skyline means, and why skyline queries are useful, particularly for expressing preference. We describe the theoretical aspects and possible optimizations of an efficiant algorithm for computing skyline queries presented in [6].