  The notion of preference is becoming more and more ubiquitous in present-day
information systems. Preferences are primarily used to filter and personalize
the information reaching the users of such systems. In database systems,
preferences are usually captured as preference relations that are used to build
preference queries. In our approach, preference queries are relational algebra
or SQL queries that contain occurrences of the winnow operator ("find the most
preferred tuples in a given relation").
  We present here a number of semantic optimization techniques applicable to
preference queries. The techniques make use of integrity constraints, and make
it possible to remove redundant occurrences of the winnow operator and to apply
a more efficient algorithm for the computation of winnow. We also study the
propagation of integrity constraints in the result of the winnow. We have
identified necessary and sufficient conditions for the applicability of our
techniques, and formulated those conditions as constraint satisfiability
problems.

Databases