  The handling of user preferences is becoming an increasingly important issue
in present-day information systems. Among others, preferences are used for
information filtering and extraction to reduce the volume of data presented to
the user. They are also used to keep track of user profiles and formulate
policies to improve and automate decision making.
  We propose here a simple, logical framework for formulating preferences as
preference formulas. The framework does not impose any restrictions on the
preference relations and allows arbitrary operation and predicate signatures in
preference formulas. It also makes the composition of preference relations
straightforward. We propose a simple, natural embedding of preference formulas
into relational algebra (and SQL) through a single winnow operator
parameterized by a preference formula. The embedding makes possible the
formulation of complex preference queries, e.g., involving aggregation, by
piggybacking on existing SQL constructs. It also leads in a natural way to the
definition of further, preference-related concepts like ranking. Finally, we
present general algebraic laws governing the winnow operator and its
interaction with other relational algebra operators. The preconditions on the
applicability of the laws are captured by logical formulas. The laws provide a
formal foundation for the algebraic optimization of preference queries. We
demonstrate the usefulness of our approach through numerous examples.
