Evaluation of Conditional Preference Queries

Abstract

The need for incorporating preference querying in database technology is a very important issue in a variety of applications ranging from e-commerce to personalizedsearch engines. A lot of recent  research work has been  dedicated to this topic in the artificial intelligence and database fields. Several formalisms allowing preferencereasoning and specification have been proposed in the AI domain. On the other hand, in the database field the interest has been focused mainly in extending standard SQL with preference facilities in order to provide personalized query answering. More precisely, the interest in the database context focuses on the notion of top-k preference queryand on the development of efficient methods for evaluating these queries. A top-k preference query returns k datatuples which are the most preferred accordingto the user's preference hierarchy. Of course, top-k preference query answering is closely dependent on the particular preference model underlying the semantics of the  operators responsible for selecting the best tuples. In this paper, we consider the  conditional preference queries (cp-queries) where preferences are specified by a set of rules expressed in a logical formalism. We propose the algorithms BNL** and R-BNL** for evaluating the top-k cp-queries and implement them in the core of the PostgreSQL query processor. An extensive set of  experiments demonstrates the efficiency of our method for computing the most preferred tuples according to the user's preferences. We also show the need to integrate the new Select-Best and SelectK-Best operators into a database system, rather than translating them into standard SQL queries.