Preference queries are crucial for various applications (e.g. digital libraries) as they allow users to discover and order data of interest in a personalized way. In this work, we define preferences as preorders over relational attributes and their respective domains.
Then, we rely on appropriate linearizations to provide a natural semantics for the block sequence answering a preference query. Moreover, we introduce two novel rewriting algorithms (called LBA and TBA) which exploit the semantics of preference expressions for constructing progressively each block of the answer.

We demonstrate experimentally the scalability and performance gains of our algorithms (up to 3 orders of magnitude) over generic ones, for variable database and result sizes, as well as for preference expressions of variable size and structure. To the best of our knowledge, LBA and TBA are the first algorithms for evaluating efficiently arbitrary preference queries over voluminous databases.