Abstract
The WWW has become a huge repository of information. For almost any knowledge domain there may exist thousands of available sources and billions of data instances. Many of these sources may publish irrelevant data. User-preference approaches have been defined to retrieve relevant data based on similarity, relevance or preference criteria specified by the user. Although many declarative languages can express user-preferences, considering this information during query optimization and evaluation remains as open problem. SQLf, Top-k and Skyline are three extensions of SQL to specify user-preferences. The first two filter irrelevant answers following a score-based paradigm. On the other hand, the latter produces relevant non-dominated answers using an order-based paradigm. The main objective of our work is to propose a unified approach that combines paradigms based on order and score. We propose physical operators for SQLf considering Skyline and Top-k features. Properties of those will be considered during query optimization and evaluation. We describe a Hybrid-Naive operator for producing only answers in the Pareto Curve with best score values. We have conducted initial experimental studies to compare the Hybrid operator, Skyline and SQLf.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrawal, R., Wimmers, E.L.: A framework for expressing and combining preferences. In: Proc. of SIGMOD, pp. 297–306 (May 2000)
Agrawal, R., Chaudhuri, S., Das, G., Gionis, A.: Automated ranking of database query results. In: Proc. of CIDR (January 2003)
Aref, W.G., Elmagarmid, A.K., Ilyas, I.F.: Supporting Top-k join queries in relational databases. VLDB Journal, 207–221 (September 2004)
Balke, W.-T., Güntzer, U., Kiebling, W.: Optimizing multi-feature queries for image databases. In: VLDB, pp. 10–14 (September 2000)
Balke, W.-T., Güntzer, U., Kiebling, W.: Towards efficient multi-feature queries in heterogeneous environments. In: ITCC, pp. 622–628 (2001)
Balke, W.-T., Güntzer, U., Xin, J.: Efficient Distributed Skylining for Web Information Systems. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 256–273. Springer, Heidelberg (2004)
Balke, W.-T., Güntzer, U.: Multi-objetive Query Processing for Database Systems. In: Proceedings of VLDB, pp. 936–947 (September 2004)
Bentley, J.L., Kung, H.T., Schkolnick, M., Thompson, C.D.: On the average number of maxima in a set of vectors and applications. JACM 25(4), 536–543 (1978)
Börzönyi, S., Kossman, D., Stocker, K.: The skyline operator. In: Proc. of ICDE, pp. 421–430 (April 2001)
Bosc, P., Brisson, A.: On the evaluation of some SQLf nested queries. In: Proceeding International Workshop on Fuzzy Databases and Information Retrieval (1995)
Bosc, P., Pivert, O.: SQLf: A Relational Database Language for Fuzzy Querying. IEEE Transactions on Fuzzy Systems 3(1) (February 1995)
Bosc, P., Pivert, O.: On the efficiency of the alpha-cut distribution method to evaluate simple fuzzy relational queries. Advances in Fuzzy Systems-Applications and Theory, 251–260 (1995)
Bosc, P., Pivert, O.: SQLf Query Functionality on Top of a Regular Relational Database Management System. Knowledge Management in Fuzzy Databases, 171–190 (2000)
Bosc, P., Pivert, O., Farquhar, K.: Integrating Fuzzy Queries into an Existing Database Management System: An Example. International Journal of Intelligent Systems 9, 475–492 (1994)
Bruno, N., Chaudhuri, S., Gravano, L.: Top-k selection queries over relational databases: Mapping strategies and performance evaluation. In: TODS, vol. 27(2), pp. 153–187 (2002)
Bruno, N., Gravano, L., Marian, A.: Evaluating top-k queries over web-accessible databases. In: ICDE (2002)
Chang, C.L.D.: A deductive query language for relational databases. In: Chen, C.H. (ed.) Pattern Rec. and Art. Int., pp. 108–134. Academic Press, New York (1976)
Chang, K., Hwang, S.-W.: Minimal Probing: Supporting Expensive Predicates for Top-k Queries. In: Proceedings of the ACM SIGMOD Conference (June 2002)
Chang, K., Hwang, S.-W.: Optimizing access cost for top-k queries over Web sources: A unified cost-based approach. Technical Report UIUCDS-R-2003-2324, University of Illinois at Urbana-Champaign (March 2004)
Chomicky, 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)
Chomicky, J.: Preference formulas in relational queries. ACM TODS 28(4), 427–466 (2003)
Chomicky, J.: Semantic optimization of preference queries. In: Kuijpers, B., Revesz, P.Z. (eds.) CDB 2004. LNCS, vol. 3074, pp. 128–142. Springer, Heidelberg (2004)
Chomicky, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: Proc. of ICDE, pp. 717–719 (March 2003)
Chomicky, J., Godfrey, P., Gryz, J., Liang, D.: On skyline Computation (June 2002)
Eng, P.K., Ooi, B.C., Tan, K.L.: Efficient progressive skyline computation. In: Proc. Of 27th VLDB, pp. 301–310 (2001)
Eng, P.K., Ooi, B.C., Tan, K.L.: Indexing for progressive skyline computation. Data and Knowl. Eng. 46(2), 169–201 (2003)
Fagin, R.: Combining fuzzy information from multiple systems. Journal of Computer and System Sciences (JCSS) 58(1), 216–226 (1996)
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. In: PODS, Santa Barbara, California, pp. 102–113 (May 2001)
Godfrey, P.: Skyline cardinality for relational processing. In: Proc. of FolKS, pp. 78–97. Springer, Heidelberg (2004)
Goncalves, M., Vidal, M.E.: Preferred Skyline: A hybrid approach between SQLf and Skyline. In: Andersen, K.V., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol. 3588, pp. 375–384. Springer, Heidelberg (2005)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: PREFER: A system for the efficient execution of multi-parametric ranked queries. In: Proc. of SIGMOD, pp. 259–270 (May 2001)
Ilyas, I.F., Shah, R., Aref, W.G., Vitter, J.S., Elmagarmid, A.K.: Rank-aware Query Optimization. In: Proceedings of the 2004 ACM SIGMOD Conf. on Mgmt. of Data, Paris, France, pp. 203–214 (June 2004)
Kiessling, W.: Foundations of preferences in database systems. In: Proc. of VLDB, pp. 311–322 (August 2002)
Kiessling, W., Köstler, G.: Preference SQL: Design, implementation, experiences. In: Proc. of VLDB, pp. 900–1001 (August 2002)
Kossman, D., Ransak, F., Rost, S.: Shooting stars in the sky: An online algorithm for skyline queries. In: Proc. of VLDB, pp. 275–286 (August 2002)
Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. JACM 22(4), 469–476 (1975)
Lacroix, M., Lavency, P.: Preferences: Putting more knowledge into queries. In: Proc. of VLDB, pp. 217–225 (September 1987)
Motro, A.: Supporting goal queries in relational databases. In: Proc. of the 1st Int. Conf. on Expert Database Sys., pp. 85–96 (April 1986)
Papadimitriou, C.H., Yannakakis, M.: Multiobjective Query Optimization. In: Proc. ACM SIGMOD/SIGACT Conf. Princ. Of Database Syst (PODS), Santa Barbara, CA, USA (May 2001)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1985)
Yalamanchi, A., Srinivasan, J., Gawlick, D.: Managing expressions as data in relational, database systems. In: Proc. of CIDR (January 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goncalves, M., Vidal, ME. (2005). Top-k Skyline: A Unified Approach. In: Meersman, R., Tari, Z., Herrero, P. (eds) On the Move to Meaningful Internet Systems 2005: OTM 2005 Workshops. OTM 2005. Lecture Notes in Computer Science, vol 3762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575863_99
Download citation
DOI: https://doi.org/10.1007/11575863_99
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29739-0
Online ISBN: 978-3-540-32132-3
eBook Packages: Computer ScienceComputer Science (R0)