CPref-SQL: a query language supporting conditional preferences

ABSTRACT

Nowadays, the need for incorporating preference querying in database technology is a very important issue in a variety of applications ranging from e-commerce to personalized search engines. A lot of recent research work has been dedicated to this topic in the artificial intelligence and database communities. Several formalisms allowing preference reasoning and specification have been proposed in the AI field. On the other hand, in the database field the interest has been focused mainly in extending standard SQL with preference facilities in order to provide personalized query answering. In this paper, we propose to build a bridge between these two approaches, by using a logic formalism originally designed to specify and reason with preference in order to extend SQL with conditional preference constructors. Such constructors allow to express a large class of preference statements with a ceteris-paribus semantics.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 3: C. Boutilier, R. Brafman, H. Hoos, and D. Poole. Cp-nets: A tool for representing and reasoning about conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research, 21: 135--191, 2004.
• 4: R. Brafman, C. Domshlak, and S. Shimony. On graphical modeling of preference and importance. Journal of Artificial Intelligence Research, 25: 389--424, 2006.
• 5: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 6: Jan Chomicki, Preference formulas in relational queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.427-466, December 2003 [doi>10.1145/958942.958946]
• 7: Jan Chomicki, Semantic optimization techniques for preference queries, Information Systems, v.32 n.5, p.670-684, July, 2007 [doi>10.1016/j.is.2006.05.002]
• 8: Sandra de Amo , Arnaud Giacometti, Temporal Conditional Preferences over Sequences of Objects, Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, p.246-253, October 29-31, 2007 [doi>10.1109/ICTAI.2007.173]
• 9: M. Endres and W. Kießling. Transformation of tcp-net queries into preference database queries. In Proc. of the ECAI 2006 Multidisciplinary Workshop on Advances in Preference Handling, pages 23--30, 2006.
• 10: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 11: Werner Kießling, Foundations of preferences in database systems, Proceedings of the 28th international conference on Very Large Data Bases, p.311-322, August 20-23, 2002, Hong Kong, China
• 12: Werner Kießling , Gerhard Köstler, Preference SQL: design, implementation, experiences, Proceedings of the 28th international conference on Very Large Data Bases, p.990-1001, August 20-23, 2002, Hong Kong, China
• 13: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering, p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 14: Kostas Stefanidis , Evaggelia Pitoura, Fast contextual preference scoring of database tuples, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353387]
• 15: K. Stefanidis, E. Pitoura, and P. Vassiliadis. A context-aware preference database system. J. Pervasive Compu. & Comm., Troubador Publishing Ltda., 1 (1), 2005.
• 16: T. Preisinger and W. Kießling. The hexagon algorithm for pareto preference queries. In 3rd Multidisciplinary Workshop on Advances in Preference Handling, VLDB 2007, 2007.
• 17: T. Preisinger, W. Kießling, and M. Endres. The bnl⁺⁺ algorithm for evaluating pareto preference queries. In 2nd Multidisciplinary Workshop on Advances in Preference Handling, ECAI 2006, 2006.
• 18: N. Wilson. Extending cp-nets with stronger conditional preference statements. In AAAI, pages 735--741, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Languages, Theory

Keywords:
SQL extension, preferences, query language, relational algebra