Spark: top-k keyword query in relational databases

ABSTRACT

With the increasing amount of text data stored in relational databases, there is a demand for RDBMS to support keyword queries over text data. As a search result is often assembled from multiple relational tables, traditional IR-style ranking and query evaluation methods cannot be applied directly.

In this paper, we study the effectiveness and the efficiency issues of answering top-k keyword query in relational database systems. We propose a new ranking formula by adapting existing IR techniques based on a natural notion of virtual document. Compared with previous approaches, our new ranking method is simple yet effective, and agrees with human perceptions. We also study efficient query processing methods for the new ranking method, and propose algorithms that have minimal accesses to the database. We have conducted extensive experiments on large-scale real databases using two popular RDBMSs. The experimental results demonstrate significant improvement to the alternative approaches in terms of retrieval effectiveness and efficiency.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A system for keyword-based search over relational databases. In ICDE, pages 5--16, 2002.
• 2: Holger Bast , Debapriyo Majumdar , Ralf Schenkel , Martin Theobald , Gerhard Weikum, IO-Top-k: index-access optimized top-k query processing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 4: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, pages 421--430, 2001.
• 5: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 6: S. Chaudhuri, R. Ramakrishnan, and G. Weikum. Integrating db and ir technologies: What is the sound of one hand clapping? In CIDR, pages 1--12, 2005.
• 7: R. Cyganiak. D2RQ benchemarking. http://sites.wiwiss.fu-berlin.de/suhl/bizer/d2rq/benchmarks/.
• 8: Gautam Das , Dimitrios Gunopulos , Nick Koudas , Dimitris Tsirogiannis, Answering top-k queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 9: B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin. Finding top-k min-cost connected trees in databases. In ICDE, 2007.
• 10: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 11: R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001.
• 12: R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. Proximity search in databases. In VLDB, 1998.
• 13: Torsten Grabs , Klemens Böhm , Hans-Jörg Schek, PowerDB-IR: information retrieval on top of a database cluster, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502655]
• 14: P. J. Haas and J. M. Hellerstein. Ripple joins for online aggregation. In SIGMOD 1999, pages 287--298, 1999.
• 15: V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient IR-Style Keyword Search over Relational Databases. In VLDB, 2003.
• 16: V. Hristidis and Y. Papakonstantinou. DISCOVER: Keyword search in relational databases. In VLDB, pages 670--681, 2002.
• 17: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 18: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: B. Kimelfeld and Y. Sagiv. Efficient engines for keyword proximity search. In WebDB, pages 67--72, 2005.
• 20: Benny Kimelfeld , Yehoshua Sagiv, Finding and approximating top-k answers in keyword proximity search, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142377]
• 21: G. Koutrika, A. Simitsis, and Y. Ioannidis. Précis: The essence of a query answer. In ICDE, 2006.
• 22: Fang Liu , Clement Yu , Weiyi Meng , Abdur Chowdhury, Effective keyword search in relational databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142536]
• 23: Y. Luo, X. Lin, W. Wang, and X. Zhou. SPARK: Top-k keyword query in relational databases. Technical Report 0708, School of Computer Science and Engineering, University of New South Wales, 2007.
• 24: N. Mamoulis, K. H. Cheng, M. L. Yiu, and D. W. Cheung. Efficient aggregation of ranked inputs. In ICDE, 2006.
• 25: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 26: Stephen Robertson , Hugo Zaragoza , Michael Taylor, Simple BM25 extension to multiple weighted fields, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031181]
• 27: D. E. Rose and D. R. Cutting. Ranking for usability: Enhanced retrieval for short queries. Technical Report 163, Apple Technical Report, 1996.
• 28: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 29: M. Sayyadan, H. LeKhac, A. Doan, and L. Gravano. Efficient keyword search across heterogeneous relational databases. In ICDE, 2007.
• 30: Q. Su and J. Widom. Indexing relational database content offline for efficient keyword-based search. In IDEAS, 2005.
• 31: R. Wilkinson, J. Zobel, and R. Sacks-Davis. Similarity measures for short queries. In TREC, 1995.
• 32: Dong Xin , Chen Chen , Jiawei Han, Towards robust indexing for ranked queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance

Keywords:
information retrieval, keyword search, relational database, top-k