  Preference queries are relational algebra or SQL queries that contain
occurrences of the winnow operator ("find the most preferred tuples in a given
relation"). Such queries are parameterized by specific preference relations.
Semantic optimization techniques make use of integrity constraints holding in
the database. In the context of semantic optimization of preference queries, we
identify two fundamental properties: containment of preference relations
relative to integrity constraints and satisfaction of order axioms relative to
integrity constraints. We show numerous applications of those notions to
preference query evaluation and optimization. As integrity constraints, we
consider constraint-generating dependencies, a class generalizing functional
dependencies. We demonstrate that the problems of containment and satisfaction
of order axioms can be captured as specific instances of constraint-generating
dependency entailment. This makes it possible to formulate necessary and
sufficient conditions for the applicability of our techniques as constraint
validity problems. We characterize the computational complexity of such
problems.
