Answering approximate queries over autonomous web databases

ABSTRACT

To deal with the problem of empty or too little answers returned from a Web database in response to a user query, this paper proposes a novel approach to provide relevant and ranked query results. Based on the user original query, we speculate how much the user cares about each specified attribute and assign a corresponding weight to it. This original query is then rewritten as an approximate query by relaxing the query criteria range. The relaxation order of all specified attributes and the relaxed degree on each specified attribute are varied with the attribute weights. For the approximate query results, we generate users' contextual preferences from database workload and use them to create a priori orders of tuples in an off-line preprocessing step. Only a few representative orders are saved, each corresponding to a set of contexts. Then, these orders and associated contexts are used at query time to expeditiously provide ranked answers. Results of a preliminary user study demonstrate that our query relaxation and results ranking methods can capture the user's preferences effectively. The efficiency and effectiveness of our approach is also demonstrated by experimental result.

REFERENCES

• 1: Rakesh Agrawal , Ralf Rantzau , Evimaria Terzi, Context-sensitive ranking, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142517]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Agrawal, S., Chaudhuri, S., Das, G., and Gionis, A. Automated ranking of database query results. ACM Trans. Database Syst., 28(2): 140--174, 2003.
• 4: Patrick Bosc , Allel Hadjali , Olivier Pivert, Empty versus overabundant answers to flexible relational queries, Fuzzy Sets and Systems, v.159 n.12, p.1450-1467, June, 2008 [doi>10.1016/j.fss.2008.01.007]
• 5: Zhiyuan Chen , Tao Li, Addressing diverse user preferences in SQL-query-result navigation, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247551]
• 6: Kaushik Chakrabarti , Venkatesh Ganti , Jiawei Han , Dong Xin, Ranking objects based on relationships, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142516]
• 7: Marek Chrobak , Claire Kenyon , Neal Young, The reverse greedy algorithm for the metric k-median problem, Information Processing Letters, v.97 n.2, p.68-72, 31 January 2006 [doi>10.1016/j.ipl.2005.09.009]
• 8: Surajit Chaudhuri , Gautam Das , Vagelis Hristidis , Gerhard Weikum, Probabilistic information retrieval approach for ranking of database query results, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1134-1168, September 2006 [doi>10.1145/1166074.1166085]
• 9: Kaushik Chakrabarti , Surajit Chaudhuri , Seung-won Hwang, Automatic categorization of query results, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007653]
• 10: 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]
• 11: Cohen, W. W., Schapire, R. E. Learning to order things. Journal of Artificial Intelligence Research, 10, 243--270, 1999.
• 12: Gautam Das , Vagelis Hristidis , Nishant Kapoor , S. Sudarshan, Ordering the attributes of query results, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142518]
• 13: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 14: 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
• 15: Z. M. Ma , Li Yan, Generalization of strategies for fuzzy query translation in classical relational databases, Information and Software Technology, v.49 n.2, p.172-180, February, 2007 [doi>10.1016/j.infsof.2006.05.002]
• 16: Ullas Nambiar , Subbarao Kambhampati, Answering Imprecise Queries over Autonomous Web Databases, Proceedings of the 22nd International Conference on Data Engineering, p.45, April 03-07, 2006 [doi>10.1109/ICDE.2006.20]
• 17: Michael Ortega-Binderberger , Kaushik Chakrabarti , Sharad Mehrotra, An Approach to Integrating Query Refinement in SQL, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.15-33, March 25-27, 2002
• 18: Ortega, B. M. Integrating similarity based retrieval and query refinement in databases. Ph.D Dissertation, UIUC, 2003.
• 19: Ion Muslea, Machine learning for online query relaxation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014081]
• 20: Rui, Y., Huang, T. S., and Merhotra, S. Content-based image retrieval with relevance feedback in MARS. In Proceedings of the ICIP Conference, 815--818, 1997.
• 21: Stefanidis, K. and Pitoura, E. Adding context to preferences. In Proceedings of the ICDE Conference, 846--855, 2007.
• 22: Weifeng Su , Jiying Wang , Qiong Huang , Fred Lochovsky, Query result ranking over e-commerce web databases, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183697]
• 23: Leejay Wu , Christos Faloutsos , Katia P. Sycara , Terry R. Payne, FALCON: Feedback Adaptive Loop for Content-Based Retrieval, Proceedings of the 26th International Conference on Very Large Data Bases, p.297-306, September 10-14, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

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

General Terms:
Algorithms, Experimentation, Human Factors, Performance

Keywords:
query relaxation, query results ranking, top-k., web database