Preference structures and their lattice representations

Preferences are an important natural concept in real life and are well-known in the database and artificial intelligence community. The integration of preference queries in database systems enables satisfying search results by delivering best matches, even when no object in a dataset fulfills all preferences perfectly. Skyline queries are the most prominent representatives of preferences queries. The target is to select those tuples from a dataset that are optimal with respect to a set of designated preference attributes. But users do not only think of finding the Pareto frontier, they often want to find the best objects concerning an explicit specified preference order. While preferences themselves often are defined as general strict partial orders, almost all algorithms are designed to evaluate Pareto preferences combining weak orders, i.e., Skylines. In this paper, we consider general strict partial orders and we present a method to evaluate such explicit preferences by embedding any strict partial order into a lattice. This enables preference evaluation with specialized lattice based algorithms