Cooperative database retrieval is a challenging problem. In today?s information systems instead of just retrieving all objects from databases that exactly match a user?s query, often a set of objects best matching the query attributes is desired. Starting from a set of individual user preferences for each attribute, the query can be relaxed step by step until a satisfying result set can be returned. This avoids the notorious empty result effect of over-specified queries, while still respecting the user wishes. The prime paradigm for this kind of retrieval are skyline queries, where a Pareto optimal result set with respect to (partial-order) attribute preferences is returned. The price for this cooperative behavior is however usually a large result set size.