Preference Queries

当人们谈论人类的决定或选择时，偏好的概念自然会出现。这个项目研究数据库查询上下文中的首选项。面对信息过载，数据库用户寻求的方法不一定是获得查询的所有答案，而是最好的、最受欢迎的答案。在本项目的框架中，用户偏好被捕获为偏好公式。首选项查询涉及使用许多具有简单形式语义的代数首选项操作符。其中最基本的是winnow，当它应用于一个关系时，返回最受欢迎的元组集合——那些不受关系中任何其他元组支配的元组。winnow操作符由首选项公式参数化。例如，给定一个合适的公式和一个待售图书的数据库，winnow将返回购买每本书的所有最便宜的方式。其他首选项操作符包括排序（winnow的无界迭代）和首选项范围选择。在项目过程中，开发和研究了优选算子的评价算法。识别了这些运算符的代数性质，为优化偏好查询奠定了基础。还开发了用于此类查询的查询优化技术，并与现有的查询优化器集成在一起。该研究解决了所有必要的步骤，使首选项查询在数据库管理领域成为一个实用的概念。更多信息可在项目网站（http://www.cse.buffalo.edu/~chomicki/prefs.html）获得。更广泛的影响包括为学生开设的新课程，使数据库更好的新应用程序，以及新研究的基础和方向。

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. Further information can be obtained at the project web site (http://www.cse.buffalo.edu/~chomicki/prefs.html). Broader impacts include new courses for students, new applications to make databases better, and foundation and directions for new research.