Abstract
Preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator (find the most preferred tuples in a given relation). We present here a number of semantic optimization techniques applicable to preference queries. The techniques make it possible to remove redundant occurrences of the winnow operator and to apply a more efficient algorithm for the computation of winnow. We also study the propagation of integrity constraints in the result of the winnow. We have identified necessary and sufficient conditions for the applicability of our techniques, and formulated those conditions as constraint satisfiability problems.
Research supported by NSF Grant IIS-0307434.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Wimmers, E.L.: A Framework for Expressing and Combining Preferences. In: ACM SIGMOD International Conference on Management of Data, pp. 297–306 (2000)
Baudinet, M., Chomicki, J., Wolper, P.: Constraint-Generating Dependencies. Journal of Computer and System Sciences 59, 94–115 (1999) (Preliminary version in ICDT 1995)
Börzsönyi, S., Kossmann, D., Stocker, K.: The Skyline Operator. In: IEEE International Conference on Data Engineering (ICDE), pp. 421–430 (2001)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with Presorting. In: IEEE International Conference on Data Engineering, ICDE (2003); Poster
Cheng, Q., Gryz, J., Koo, F., Leung, C., Liu, L., Qian, X., Schiefer, B.: Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. In: International Conference on Very Large Data Bases, VLDB (1999)
Chakravarthy, U.S., Grant, J., Minker, J.: Logic-Based Approach to Semantic Query Optimization. ACM Transactions on Database Systems 15(2), 162–207 (1990)
Chomicki, J.: Querying with Intrinsic Preferences. In: Jensen, C.S., Jeffery, K., Pokorný, J., Šaltenis, S., Bertino, E., Böhm, K., Jarke, M. (eds.) EDBT 2002. LNCS, vol. 2287, pp. 34–51. Springer, Heidelberg (2002)
Chomicki, J.: Preference Formulas in Relational Queries. ACM Transactions on Database Systems 28(4), 427–466 (2003)
Fishburn, P.C.: Utility Theory for Decision Making. Wiley & Sons, Chichester (1970)
Fishburn, P.C.: Preference Structures and their Numerical Representations. Theoretical Computer Science 217, 359–383 (1999)
Govindarajan, K., Jayaraman, B., Mantha, S.: Preference Queries in Deductive Databases. New Generation Computing, 57–86 (2001)
Guo, S., Sun, W., Weiss, M.A.: Solving Satisfiability and Implication Problems in Database Systems. ACM Transactions on Database Systems 21(2), 270–293 (1996)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries. In: ACM SIGMOD International Conference on Management of Data, pp. 259–270 (2001)
Kießling, W., Güntzer, U.: Database Reasoning – A Deductive Framework for Solving Large and Complex Problems by means of Subsumption. In: Luck, K.v., Marburger, H. (eds.) IS/KI 1994 and KI-WS 1994. LNCS, vol. 777, pp. 118–138. Springer, Heidelberg (1994)
Kießling, W., Hafenrichter, B.: Optimizing Preference Queries for Personalized Web Services. In: IASTED International Conference on Communications, Internet and Information Technology (November 2002); Also Tech. Rep. 2002-12, July 2002, Institute of Computer Science, University of Augsburg, Germany
Kießling, W., Hafenrichter, B.: Algebraic Optimization of Relational Preference Queries. Technical Report 2003-1, Institut für Informatik, Universität Augsburg (2003)
Kießling, W.: Foundations of Preferences in Database Systems. In: International Conference on Very Large Data Bases, VLDB (2002)
Kießling, W., Köstler, G.: Preference SQL - Design, Implementation, Experience. In: International Conference on Very Large Data Bases, VLDB (2002)
Köstler, G., Kießling, W., Thöne, H., Güntzer, U.: Fixpoint Iteration with Subsumption in Deductive Databases. Journal of Intelligent Information Systems 4, 123–148 (1995)
Kuper, G., Libkin, L., Paredaens, J. (eds.): Constraint Databases. Springer, Heidelberg (2000)
Klug, A.: Calculating Constraints on Relational Tableaux. ACM Transactions on Database Systems 5, 260–290 (1980)
Klug, A., Price, R.: Determining View Dependencies Using Tableaux. ACM Transactions on Database Systems 7 (1982)
Kossmann, D., Ramsak, F., Rost, S.: Shooting Stars in the Sky: An Online Algorithm for Skyline Queries. In: International Conference on Very Large Data Bases, VLDB (2002)
Lacroix, M., Lavency, P.: Preferences: Putting More Knowledge Into Queries. In: International Conference on Very Large Data Bases (VLDB), pp. 217–225 (1987)
Maher, M., Wang, J.: Optimizing Queries in Extended Relational Databases. In: Ibrahim, M., Küng, J., Revell, N. (eds.) DEXA 2000. LNCS, vol. 1873, pp. 386–396. Springer, Heidelberg (2000)
Papadias, D., Tao, Y., Fu, G., Seeger, B.: An Optimal and Progressive Algorithm for Skyline Queries. In: ACM SIGMOD International Conference on Management of Data, pp. 467–478 (2003)
Simmen, D.E., Shekita, E.J., Malkemus, T.: Fundamental Techniques for Order Optimization. In: ACM SIGMOD International Conference on Management of Data, pp. 57–67 (1996)
Torlone, R., Ciaccia, P.: Which Are My Preferred Items? In: Workshop on Recommendation and Personalization in E-Commerce (May 2002)
Zhang, X., Ozsoyoglu, Z.M.: Implication and Referential Constraints: A New Formal Reasoning. IEEE Transactions on Knowledge and Data Engineering 9(6), 894–910 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chomicki, J. (2004). Semantic Optimization of Preference Queries. In: Kuijpers, B., Revesz, P. (eds) Constraint Databases. CDB 2004. Lecture Notes in Computer Science, vol 3074. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25954-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-25954-1_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22126-5
Online ISBN: 978-3-540-25954-1
eBook Packages: Springer Book Archive