The notion of preference occurs naturally in every context where one talks about human decision or choice. The proposed research 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 proposed research, user preferences are captured as preference formulas. The preferences can be composed using a variety of operators, including prioritized composition. 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 operators include ranking (unbounded iteration of winnow) and preference range selection.
In the course of the project algorithms for evaluating preference operators will be developed and studied. Algebraic properties of those operators will be identified, in order to lay the foundation for the optimization of preference queries. Query optimization techniques for such queries will also be developed and integrated with an existing query optimizer. The proposed research will address 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.
[TODS'03] Jan Chomicki. Preference Formulas in Relational Queries. ACM Transactions on Database Systems, 28(4), pp. 427-466.
[CDB'04] Jan Chomicki. Semantic Optimization of Preference Queries. Proc. International Symposium on Applications of Constraint Databases (CDB), June 2004, Paris, France, Springer, LNCS 3074, pp. 128-142.
Human Resources. Research assistants at the University at Buffalo: Joyce Song (Summer and Fall 04), Greg Ball (Summer 04), Duc Ha (Summer 04).
Education and curriculum development. Preference queries are one of the main topics of the graduate seminar on Foundations of Databases offered every year by the PI. Several student projects in this area have been completed. The PI supervised an M.S. project of Snehal Kasnodekar on Algorithms for Ranking.
Other. The PI co-organized a Dagstuhl seminar on Preferences (June 2004). This seminar provided a unique meeting place for preference researchers from many different areas: decision theory, artificial intelligence, databases, and philosophical logic, and stimulated interdisciplinary collaborative research on preferences. The PI also gave a tutorial on preference query optimization in this seminar. He gave invited talks on preference queries at Cornell University and Ecole Polytechnique Federale de Lausanne, Switzerland, as well as a keynote talk on the same topic at the 2004 Italian Conference on Databases (SEBD).
The PI has completed the study of the fundamental logical properties of preferences and algebraic properties of preference queries [TODS'03]. He has formulated sufficient and necessary conditions for the correctness of rewriting of such queries. This research lays the foundation for the algebraic optimization of preference queries and has immediate applications to special classes of such queries identified by other researchers: PreferenceSQL [Kie02], skyline queries [BKS01], queries with scoring functions [HKS01].
The PI has also studied semantic optimization of preference queries [CDB'04]. He has designed novel query evaluation and rewriting techniques that make use of integrity constraints.
Together with his students, the PI has obtained some preliminary results about:
Under the supervision of the PI, S. Staworko (a Ph. D. student) has been studying the computation of consistent query answers in the presence of preferences. This provides a connection to another project of the PI (IIS-0119186).
In present-day information systems preferences are more and more common. They are used to reduce the volume of data presented to the user and to personalize query results. Current research on preference queries involves the design and evaluation of general preference query languages [Kie02] and evaluation of special classes of preference queries: [BKS01], [HKS01]. The uniqueness of our approach comes from the fact that it is based on a clean logical framework. This makes it possible to study the properties of preference queries in a very general way and to obtain results that are broadly applicable.
[Kie02] W. Kiessling. Foundations of Preferences in Database Systems. Proc. VLDB'02.
[BKS01] S. Borzsonyi, D. Kossmann, K. Stocker. The Skyline Operator. Proc. ICDE'01.
[HKS01] V. Hristidis, N. Koudas, Y. Papakonstantinou. PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries. Proc. SIGMOD'01.
Ranking Queries, Query Personalization, Query Relaxation, Preference Revision and Aggregation, Query Optimization.