Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
2004 Technical Reports

Relational Preference Queries via Stable Skyline

Parke Godfrey and Wei Ning

Technical Report CS-2004-03

York University

August 2004


We advocate the extension of relational database systems to support preference queries. Many database applications today, from e-commerce to queries over scientific data-sets, are essentially "best-match" searches. Relational queries are ill-suited for these. Supporting preference criteria in the query language can extend its expresssiveness to cover best-match queries in a natural way.

We study skyline queries as a foundation for preference queries. Skyline offers a natural way to combine multiple preference criteria in parallel. Skyline as it was introduced, however, is limited in its expressiveness, and does not capture many types of preferences and compositions people would like to support. We present a formal model of skyline and motivate two extensions to skyline that greatly increase its expressiveness. These extensions destroy though the partial-order semantics of skyline as originally defined. We develop the stable skyline semantics that accommodates the extensions and the loss of transitivity in the preference relation in a natural manner. This also opens the door to other, potentially useful extensions. We present a high-level algorithm that computes the stable skyline set. Lastly, we show how skyline criteria can be grounded in a natural way in cases when the preference relation may otherwise have cycles.

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.