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.
Jan Chomicki. Preference Formulas in Relational Queries. Accepted to ACM Transactions on Database Systems. arXiv.org 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.
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.
Currently, the PI and his team are working on the following issues:
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.
[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.
Web Querying, Ranking, Recommender Systems, Data Integration.