Preference Queries

This material is based upon work supported by the National Science Foundation under Grant No. IIS-0307434. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

Principal Investigator: Jan Chomicki, University at Buffalo

Project Title: Preference Queries

Abstract:

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:

  1. Output-Sensitive Evaluation of Prioritized Skyline Queries. Proc. 36th International Conference on Management of Data (SIGMOD), to appear (with N. Meneghetti, D. Mindolin and P. Ciaccia).

  2. Skyline Queries, Front and Back. ACM SIGMOD Record, 42(3), September 2013, pp. 6-18 (with Paolo Ciaccia and Niccolo Meneghetti).

  3. Preference Queries over Sets. Proc. 27th International Conference on Data Engineering (ICDE), April 2011, Hannover, Germany, pp. 1019-1030 (with Xi Zhang).

  4. Preference Elicitation in Prioritized Skyline Queries. VLDB Journal 20(2), 2011, pp. 157-182. Special issue: selected papers from VLDB 2009 (with D. Mindolin). Also preprint arXiv:1008.5357v1 [cs.DB], August 31, 2010.

  5. Contracting Preference Relations for Database Applications. Artificial Intelligence Journal 175(7-8), May 2011, pp. 1092-1121. Special issue on Representing, Processing, and Learning Preferences (with Denis Mindolin). Also preprint arxiv:0903.1878v1 [cs.AI], March 10, 2009.

  6. Xi Zhang. Probabilities and Sets in Preference Querying. Ph. D. dissertation. UB CSE TR 2010-04, June 2010.

  7. Discovering Relative Importance of Skyline Attributes. Proc. 35th International Conference on Very Large Data Bases (VLDB), August 2009, Lyon, France, pp. 610-621 (with D. Mindolin).

  8. Denis Mindolin. Preference Construction for Database Querying.Ph. D. dissertation. UB CSE TR 2009-07, August 2009.

  9. Semantics and Evaluation of Top-k Queries in Probabilistic Databases. Distributed and Parallel Databases, 26(1), August 2009, pp. 67-126 (with Xi Zhang). Also preprint arXiv:0811.2250v1 [cs.DB], November 14, 2008.

  10. Minimal Contraction of Preference Relations. Proc. Association for the Advancement of Artificial Intelligence (AAAI), July 2008, Chicago, pp. 492-497 (with D. Mindolin).

  11. Profiling Sets for Preference Querying. Proc. International Workshop on Logic in Databases (LID), May 2008, Rome, Italy (with X. Zhang).

  12. On the Semantics and Evaluation of Top-k Queries in Probabilistic Databases. Proc. 2nd International Workshop on Database Ranking (DBRank), April 2008, Cancun, Mexico, IEEE Computer Society Press (with X. Zhang).

  13. Database Querying under Changing Preferences. Annals of Mathematics and Artificial Intelligence 50(1-2), June 2007 (special issue: selected papers from FOIKS'06), pp. 79-109. Also arXiv.org preprint cs.DB/0607013, July 5, 2006.

  14. Preference-Driven Querying of Inconsistent Relational Databases. Proc. International Workshop on Inconsistency and Incompleteness in Databases, March 2006, Munich, Germany (with S. Staworko and J. Marcinkowski). Earlier version: UB CSE Technical Report 2005-11 and arXiv.org preprint cs.DB/0506063, June 15, 2005.

  15. Semantic Optimization Techniques for Preference Queries. Information Systems, 32(5), July 2007, pp. 670-684. Also: UB CSE Technical Report 2005-22 and arXiv.org preprint cs.DB/0510036, October 14, 2005.

  16. Iterative Modification and Incremental Evaluation of Preference Queries. Proc. 4th International Symposium on Foundations of Information and Knowledge Systems (FoIKS), February 2006, Budapest, Hungary, Springer, LNCS 3861, pp. 63-82. Invited to a special issue of Annals of Mathematics and Artificial Intelligence.

  17. Monotonic and Nonmonotonic Preference Revision. Proc. IJCAI 2005 Multidisciplinary Workshop on Advances in Preference Handling, July 2005, Edinburgh, Scotland, UK (with Joyce Song).

  18. Semantic Optimization of Preference Queries. International Symposium on Applications of Constraint Databases, June 2004, Paris, France, Springer-Verlag, LNCS 3074, pp. 128--142.

  19. Preference Formulas in Relational Queries. ACM Transactions on Database Systems, 28(4), December 2003, pp.427-466. Earlier version: arXiv.org paper cs.DB/0207093.

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

Talks:

  1. Preference Queries over Sets. ICDE'11, April 2011, Hannover, Germany.

  2. Foundations of Preference Queries. Lectures given at University of Calabria, May 2010.

  3. Discovering Relative Importance of Skyline Attributes. VLDB'09, August 2009, Lyon, France.

  4. Semantics and Evaluation of Top-K Queries in Probabilistic Databases. September 2008.

  5. Semantic Optimization of Preference Queries. Symposium on Applications of Constraint Databases, June 2004, Paris, France.

  6. Towards a Decision Query Language. Italian Symposium on Databases (SEBD), June 2004, Pula, Italy. Invited talk.

  7. Optimization of Preference Queries. Dagstuhl seminar 04271 "Preferences," June 2004.

  8. Preference Queries in Relational Databases. May 2004.

Ph.D. students:

  1. Xi Zhang (est. 2009)
  2. Denis Mindolin (2009)

Documents: 

http://www.cse.buffalo.edu/~chomicki/prefs.html