Preference Queries (09/03-09/06)

Project Award Number IIS-0307434

Principal Investigator

Department of Computer Science and Engineering
University at Buffalo
201 Bell Hall
716-645-3180 ext.103


Jarek Gryz
Department of Computer Science
York University


Query Languages
Query Optimization
Relational Algebra
Utility Functions

Project Summary

The notion of preference occurs naturally in every context where one talks about human decision or choice. This project studies preferences in the context of database queries. Faced with information overload, database users seek ways to obtain not necessarily all answers to queries but rather the best, most preferred answers.

In the framework of this project, user preferences are captured as preference formulas. Preference queries involve the use of a number of algebraic preference operators that have simple formal semantics. The most basic of those is winnow which, when applied to a relation, returns the set of the most preferred tuples -- those which are not dominated by any other tuples in the relation. The winnow operator is parameterized by a preference formula. For example, given a suitable formula and a database of books for sale winnow will return all the cheapest ways to purchase every book. Other preference operators include ranking (unbounded iteration of winnow) and preference range selection.

In the course of the project algorithms for evaluating preference operators are developed and studied. Algebraic properties of those operators are identified, in order to lay the foundation for the optimization of preference queries. Query optimization techniques for such queries are also developed and integrated with an existing query optimizer. The research addresses all the steps necessary to make preference queries a practical concept in the area of database management. As the result, a new dimension will be added to database support for decision-making, configuration and electronic commerce applications.

Publications and Products

Jan Chomicki. Preference Formulas in Relational Queries. Accepted to ACM Transactions on Database Systems. paper cs.DB/0207093.

Jan Chomicki. Querying with Intrinsic Preferences. Proc. 8th International Conference on Extending Database Technology, March 2002, Prague, Czech Republic. Springer-Verlag, LNCS 2287, pp. 34-51.

Project Impact

Human Resources. Two research assistants at the University at Buffalo will be hired.

Education and curriculum development. The PI is offering a graduate seminar on Foundations of Databases (Fall 2003), during which preference queries and logical modeling of preferences will be discussed. The PI also gave talks about the project at 3 universities.

Other. The PI is organizing a multidisciplinary seminar on Preferences, to be held at Dagstuhl in 2004.

Goals, Objectives and Targeted Activities

Currently, the PI and his team are working on the following issues:

  1. composition of preference relations
  2. algebraic optimization of preference queries
  3. evaluation of preference queries
  4. utility-function-based representation of preference relations.

Area Background

The handling of user preferences is becoming an increasingly important issue in present-day information systems. Among others, preferences are used for information filtering and extraction to reduce the volume of data presented to the user. They are also used to keep track of user profiles and formulate policies to improve and automate decision making.

The research literature on preferences is extensive. It encompasses, among others, preference logics [VWr63], preference reasoning [WeDo91], prioritized nonmonotonic reasoning and logic programming [BrEi99], and decision theory [Fish99] (the list is by no means exhaustive). The resarch on preferences in the context of database queries goes back to [LaLa87]. Nevertheless, only recently this area has attracted broader interest in the database research community. Two different approaches have been pursued: quantitative [AgWi00] and qualiitative [Kie02]. Our qualitative approach [edbt02][tods03] is unique because it relies on logical specification of preferences as preference relations.

Area References

[VWr63] G. von Wright. The Logic of Preference. Edinburgh University Press, 1963.

[WeDo91] M. P. Wellman and J. Doyle. Preferential Semantics for Goals. Proc. AAAI, 1991.

[BrEi99] G. Brewka and T. Eiter. Preferred Answer Sets for Extended Logic Programs. Artificial Intelligence, 109(1-2), 1999, pp.297-356.

[Fish99] P. Fishburn. Preference Structures and Their Numerical Representations. Theoretical Computer Science, 217, 1999, pp.359-383.

[LaLa87] M. Lacroix and P. Lavency. Preferences: Putting More Knowledge Into Queries. Proc. Very Large Data Bases, 1987, pp.217-225.

[AgWi00] R. Agrawal and E. Wimmers. A Framework for Expressing and Combining Preferences. Proc. SIGMOD, 2000, pp.297-306.

[Kie02] W. Kiessling. Foundations of Preferences in Database Systems. Proc. Very Large Data Bases, 2002.

Potential Related Projects

Web Querying, Ranking, Recommender Systems, Data Integration.

Project Websites

Preference Queries.

Main project website.