Skyline Queries for Preference-Based Information Systems.
Wolf‐Tilo Balke · Grundlagen von Datenbanken · 2008
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. In a decision scenario, like e.g., product search in e-commerce applications, users thus have to choose from a large set of alternatives where each alternative can be described with respect to a list of predefined attributes. The task is to pick the alternative having the highest value with respect to the user‟s personal preferences among all alternatives. For example, if one is looking for a new car, each alternative is a car offer described in terms of price, top speed, make, and many further attributes. Preferences may consist of simple statements like “I want a fast car”, “I want to pay as little as possible, and definitely at most € 30.000”, or “I don't mind whether the car color is red or blue, but it should not be black.” Since there usually is no brand-new Ferrari for free, the decision one is faced with is often getting complicated. Multi-criteria optimization is a discipline that deals with problems like the one described above. Unfortunately, although the discipline is several decades old now, there seem to be no method available that provides both high result quality and easiness of use. Only too often the proposed methods work on complex utility functions that cannot be provided by the user in an intuitive way. An important goal of current database research is therefore to develop methods that determine „optimal‟ choice selections and return reasonably small sets of alternatives to the user. H. Hopfner, F. Klan (Eds.): Proceedings of the 20. GI-Workshop on Foundations of Databases (GvDB), Apolda, Thuringen, Germany, May 13-16, 2008.