Effective keyword search in relational databases

ABSTRACT

With the amount of available text data in relational databases growing rapidly, the need for ordinary users to search such information is dramatically increasing. Even though the major RDBMSs have provided full-text search capabilities, they still require users to have knowledge of the database schemas and use a structured query language to search information. This search model is complicated for most ordinary users. Inspired by the big success of information retrieval (IR) style keyword search on the web, keyword search in relational databases has recently emerged as a new research topic. The differences between text databases and relational databases result in three new challenges: (1) Answers needed by users are not limited to individual tuples, but results assembled from joining tuples from multiple tables are used to form answers in the form of tuple trees. (2) A single score for each answer (i.e. a tuple tree) is needed to estimate its relevance to a given query. These scores are used to rank the most relevant answers as high as possible. (3) Relational databases have much richer structures than text databases. Existing IR strategies to rank relational outputs are not adequate. In this paper, we propose a novel IR ranking strategy for effective keyword search. We are the first that conducts comprehensive experiments on search effectiveness using a real world database and a set of keyword queries collected by a major search company. Experimental results show that our strategy is significantly better than existing strategies. Our approach can be used both at the application level and be incorporated into a RDBMS to support keyword-based search in relational databases.

REFERENCES

• 1: S Agrawal, S Chaudhuri, G Das: DBXplorer: A system for keyword-based search over relational databases. ICDE 2002
• 2: 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
• 3: A. Balmin, V. Hristidis,Y. Papakonstantinou: Authority Based Keyword Queries in Databases using ObjectRank. VLDB 2004
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: S. Cohen, Jonathan Mamou, Yaron Kanza, Yehoshua Sagiv: XSEarch: A Semantic Search Engine for XML. VLDB 2003
• 6: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 7: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 8: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 9: Lin Guo , Jayavel Shanmugasundaram , Kevin Beyer , Eugene Shekita, Efficient Inverted Lists and Query Algorithms for Structured Value Ranking in Update-Intensive Relational Databases, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.298-309, April 05-08, 2005 [doi>10.1109/ICDE.2005.59]
• 10: V. Hristidis and Y. Papakonstantinou. DISCOVER: Keyword search in relational databases. VLDB 2002.
• 11: V. Hristidis,L. Gravano,Y. Papakonstantinou:Efficient IR-Style Keyword Search over Relational Databases.VLDB 2003
• 12: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 13: Y. Li, Cong Yu, H. V. Jagadish: Schema-Free XQuery. VLDB 2004
• 14: Shuang Liu , Fang Liu , Clement Yu , Weiyi Meng, An effective approach to document retrieval via utilizing WordNet and recognizing phrases, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009039]
• 15: L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web, Technical Report, 1998
• 16: R. Sacks-Davis, Tuong Dao, James A. Thom, Justin Zobel Indexing documents for queries on structure, content and attributes. ISDM 1997
• 17: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 18: A. Singhal. Modern information retrieval: A brief overview. IEEE Data Eng. Bull. 24(4), 2001
• 19: E. M. Voorhees. Overview of the TREC-9 Question Answering Track. TREC 2000
• 20: Pew Internet & American Life Project Report: Search Engine Users, 2005. www.pewinternet.org/pdfs/PIP_Searchengine_users.pd
• 21: Google. www.google.com/ 2005
• 22: DB2 Text Information Extender. 2005 http://www.ibm.com/software/data/db2/extenders/textinformation/index.html
• 23: Micorsoft SQL Server 2000. www.microsoft.com/sql/ 2005
• 24: MySQL. dev.mysql.com/doc/mysql/en/Fulltext_Search.html.
• 25: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 26: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 27: David A. Grossman , Ophir Frieder, Information Retrieval: Algorithms and Heuristics, Kluwer Academic Publishers, Norwell, MA, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Experimentation

Keywords:
effectiveness, information retrieval (IR), keyword search, relational database, term weighting