Preference formulas in relational queries

ABSTRACT

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.We propose here a simple, logical framework for formulating preferences as preference formulas. The framework does not impose any restrictions on the preference relations, and allows arbitrary operation and predicate signatures in preference formulas. It also makes the composition of preference relations straightforward. We propose a simple, natural embedding of preference formulas into relational algebra (and SQL) through a single winnow operator parameterized by a preference formula. The embedding makes possible the formulation of complex preference queries, for example, involving aggregation, by piggybacking on existing SQL constructs. It also leads in a natural way to the definition of further, preference-related concepts like ranking. Finally, we present general algebraic laws governing the winnow operator and its interactions with other relational algebra operators. The preconditions on the applicability of the laws are captured by logical formulas. The laws provide a formal foundation for the algebraic optimization of preference queries. We demonstrate the usefulness of our approach through numerous examples.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.297-306, May 15-18, 2000, Dallas, Texas, United States
• 3: Andreka, H., Ryan, M., and Schobbens, P.-Y. 2002. Operators and laws for combining preference relations. J. Logic Comput. 12, 1, 13--53.
• 4: 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
• 5: Boutilier, C., Brafman, R. I., Hoos, H. H., and Poole, D. 1999. Reasoning with conditional ceteris paribus preference statements. In Proceedings of the Symposium on Uncertainty in Artificial Intelligence.
• 6: Gerhard Brewka , Thomas Eiter, Preferred answer sets for extended logic programs, Artificial Intelligence, v.109 n.1-2, p.297-356, April 1999 [doi>10.1016/S0004-3702(99)00015-6]
• 7: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 8: Burke, R. 1999. Integrating knowledge-based and collaborative-filtering recommender systems. In Proceedings of the AAAI Workshop on AI and Electronic Commerce.
• 9: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 10: Chernoff, H. 1954. Rational selection of decision functions. Econometrica 22, 422--443.
• 11: Jan Chomicki, Querying with Intrinsic Preferences, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.34-51, March 25-27, 2002
• 12: Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with presorting. In Proceedings of the IEEE International Conference on Data Engineering. Poster. IEEE Computer Society Press, Los Alamitos, Calif.
• 13: Creignou, N., Hermann, M., and Pichler, R. 2001. Complexity of Constraint Solving Problems. In Proceedings of the International Conferences on Constraint Programming and Logic Programming. Tutorial Notes.
• 14: Cristani, M. 2002. Many-sorted preference relations. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning.
• 15: Delgrande, J. P., Schaub, T., and Tompits, H. 2000. Logic programs with compiled preferences. In Proceedings of the European Conference on Artificial Intelligence.
• 16: Andrew Eisenberg , Jim Melton, SQL: 1999, formerly known as SQL3, ACM SIGMOD Record, v.28 n.1, p.131-138, March 1999 [doi>10.1145/309844.310075]
• 17: Fishburn, P. C. 1970. Utility Theory for Decision Making. Wiley, New York.
• 18: Peter Fishburn, Preference structures and their numerical representations, Theoretical Computer Science, v.217 n.2, p.359-383, April 6, 1999 [doi>10.1016/S0304-3975(98)00277-1]
• 19: Fosca Giannotti , Sergio Greco , Domenico Saccà , Carlo Zaniolo, Programming with non-determinism in deductive databases, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.97-125, 1997 [doi>10.1023/A:1018999404360]
• 20: Govindarajan, K., Jayaraman, B., and Mantha, S. 1995. Preference logic programming. In Proceedings of the International Conference on Logic Programming. 731--745.
• 21: Kannan Govindarajan , Bharat Jayaraman , Surya Mantha, Preference queries in deductive databases, New Generation Computing, v.19 n.1, p.57-86, March 2001 [doi>10.1007/BF03037534]
• 22: Sha Guo , Wei Sun , Mark A. Weiss, Solving satisfiability and implication problems in database systems, ACM Transactions on Database Systems (TODS), v.21 n.2, p.270-293, June 1996 [doi>10.1145/232616.232692]
• 23: Hansson, S. O. 2001. Preference logic. In Handbook of Philosophical Logic, D. Gabbay, Ed. Vol. 8.
• 24: 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
• 25: Huet, G. 1976. Ph.D. dissertation. Univ. de Paris VII, Paris, France.
• 26: Hughes, R. 1980. Rationality and intransitive preferences. Analysis 40, 132--134.
• 27: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 28: Kieβling, W. 2002. Foundations of preferences in database systems. In Proceedings of the International Conference on Very Large Data Bases.
• 29: Werner Kießling , Ulrich Güntzer, Database Reasoning - A Deductive Framework for Solving Large and Complex Problems by Means of Subsumption, Proceedings of the Third Workshop on Information Systems and Artificial Intelligence: Management and Processing of Complex Data Structures, p.118-138, February 28-March 02, 1994
• 30: Kieβling, W. and Hafenrichter, B. 2002. Optimizing preference queries for personalized web services. In Proceedings of the IASTED International Conference on Communications, Internet and Information Technology. Also Tech. Rep. 2002-12, July 2002, Institute of Computer Science, University of Augsburg, Germany.
• 31: Kieβling, W. and Hafenrichter, B. 2003. Algebraic optimization of relational preference queries. Tech. Rep. 2003-1, Institut für Informatik, Universität Augsburg.
• 32: Kieβling, W., Hafenrichter, B., Fischer, S., and Holland, S. 2001. Preference XPATH---A query language for E-commerce. In Proceedings of the 5th International Conference Wirtschaftsinformatik. Augsburg, Germany, 43--62.
• 33: Kieβling, W. and Köstler, G. 2002. Preference SQL - Design, implementation, experience. In Proceedings of the International Conference on Very Large Data Bases.
• 34: Kevin Knight, Unification: a multidisciplinary survey, ACM Computing Surveys (CSUR), v.21 n.1, p.93-124, March 1989 [doi>10.1145/62029.62030]
• 35: Kossmann, D., Ramsak, F., and Rost, S. 2002. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the International Conference on Very Large Data Bases.
• 36: Gerhard Köstler , Werner Kiessling , Helmut Thöne , Ulrich Güntzer, Fixpoint iteration with subsumption in deductive databases, Journal of Intelligent Information Systems, v.4 n.2, p.123-148, March 1995 [doi>10.1007/BF00961871]
• 37: Kuper, G., Libkin, L., and Paredaens, J., Eds. 2000. Constraint Databases. Springer-Verlag.
• 38: M. Lacroix , Pierre Lavency, Preferences; Putting More Knowledge into Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.217-225, September 01-04, 1987
• 39: Suryanarayana Murthy Mantha, First-order preference theories and their applications, University of Utah, Salt Lake City, UT, 1992
• 40: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 41: Chiaki Sakama , Katsumi Inoue, Prioritized logic programming and its application to commonsense reasoning, Artificial Intelligence, v.123 n.1-2, p.185-222, Oct. 2000 [doi>10.1016/S0004-3702(00)00054-0]
• 42: Stolze, M. 2000. Soft navigation in product catalogs. Int. J. Digital Lib. 3, 1, 60--66.
• 43: Tan, S.-W. and Pearl, J. 1994. Specification and evaluation of preferences under uncertainty. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning.
• 44: Torlone, R. and Ciaccia, P. 2002. Which are my preferred items? In Proceedings of the Workshop on Recommendation and Personalization in E-Commerce.
• 45: Torlone, R. and Ciaccia, P. 2003. Management of user preferences in data intensive applications. In Proceedings of the 11th Italian Symposium on Advanced Database Systems (SEBD).
• 46: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 47: von Wright, G. H. 1963. The Logic of Preference. Edinburgh University Press.
• 48: Wellman, M. P. and Doyle, J. 1991. Preferential semantics for goals. In Proceedings of the National Conference on Artificial Intelligence. 698--703.
• 49: Stephen T. C. Wong, Preference-based decision making for cooperative knowledge-based systems, ACM Transactions on Information Systems (TOIS), v.12 n.4, p.407-435, Oct. 1994 [doi>10.1145/185462.185484]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Languages, Theory

Keywords:
Preference queries, preferences, query optimization, relational algebra