Effective keyword-based selection of relational databases

ABSTRACT

The wide popularity of free-and-easy keyword based searches over World Wide Web has fueled the demand for incorporating keyword-based search over structured databases. However, most of the current research work focuses on keyword-based searching over a single structured data source. With the growing interest in distributed databases and service oriented architecture over the Internet, it is important to extend such a capability over multiple structured data sources. One of the most important problems for enabling such a query facility is to be able to select the most useful data sources relevant to the keyword query. Traditional database summary techniques used for selecting unstructured datasources developed in IR literature are inadequate for our problem, as they do not capture the structure of the data sources. In this paper, we study the database selection problem for relational data sources, and propose a method that effectively summarizes the relationships between keywords in a relational database based on its structure. We develop effective ranking methods based on the keyword relationship summaries in order to select the most useful databases for a given keyword query. We have implemented our system on PlanetLab. In that environment we use extensive experiments with real datasets to demonstrate the effectiveness of our proposed summarization method.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A system for keyword-based search over relational databases. In ICDE, 2002.
• 2: A. Balmin, V. Hristidis, and Y. Papakonstantinou. ObjectRank: Authority-based keyword search in databases. In VLDB, 2004.
• 3: G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE, 2002.
• 4: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 5: J. P. Callan, Z. Lu, and W. B. Croft. Searching distributed collections with inference networks. In SIGIR, 1995.
• 6: G. Cao, J. Y. Nie, and J. Bai. Integrating word relationships into language models. In SIGIR, 2005.
• 7: Brent Chun , David Culler , Timothy Roscoe , Andy Bavier , Larry Peterson , Mike Wawrzoniak , Mic Bowman, PlanetLab: an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956995]
• 8: P. Domingos and M. Pazzani. Beyond independence: Conditions for the optimality of the simple Bayesian classifier. In Proc. 1996 Int. Conf. Machine Learning (ML'96), pages 105--112, 1996.
• 9: Daryl D'Souza , James A. Thom , Justin Zobel, Collection selection for managed distributed document databases, Information Processing and Management: an International Journal, v.40 n.3, p.527-546, January 2004 [doi>10.1016/S0306-4573(03)00008-6]
• 10: C. Fellbaum, editor. WordNet: An Electronic Lexical Database. Bradford Books, 1998.
• 11: J. Gao, J. Y. Nie, G. Wu, and G. Cao. Dependence language model for information retrieval. In SIGIR, 2004.
• 12: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 13: V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient IR-style keyword search over relational databases. In VLDB, 2003.
• 14: V. Hristidis and Y. Papakonstantinou. DISCOVER: Keyword search in relational databases. In VLDB, 2002.
• 15: F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. Annals of Discrete Mathematics. North-Holland, 1992.
• 16: P. G. Ipeirotis, E. Agichtein, P. Jain, and L. Gravano. To search or to crawl?: towards a query optimizer for text-centric tasks. In SIGMOD, 2006.
• 17: P. G. Ipeirotis and L. Gravano. Distributed search over the hidden web: Hierarchical database sampling and selection. In VLDB, 2002.
• 18: H. V. Jagadish, B. C. Ooi, and Q. H. Vu. Baton: a balanced tree structure for peer-to-peer networks. In VLDB, 2005.
• 19: B. Kimelfeld and Y. Sagiv. Finding and approximating top-k answers in keyword proximity search. In PODS, 2006.
• 20: A. Y. Levy, A. Rajaraman, and J. J. Ordille. Querying heterogeneous information sources using source descriptions. In VLDB, 1996.
• 21: F. Liu, C. Yu, W. Meng, and A. Chowdhury. Effective keyword search in relational databases. In SIGMOD, 2006.
• 22: Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002 [doi>10.1145/505282.505284]
• 23: R. Nallapati and J. Allan. Capturing term dependencies using a language model based on sentence trees. In CIKM, 2002.
• 24: Felix Naumann , Johann-Christoph Freytag , Ulf Leser, Completeness of integrated information sources, Information Systems, v.29 n.7, p.583-615, October 2004 [doi>10.1016/j.is.2003.12.005]
• 25: W. S. Ng, B. C. Ooi, and K. L. Tan. BestPeer: A self-configurable peer-to-peer system. In ICDE, 2002.Poster Paper.
• 26: Allison L. Powell , James C. French, Comparing the performance of collection selection algorithms, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.412-456, October 2003 [doi>10.1145/944012.944016]
• 27: A. Singhal. Modern information retrieval: A brief overview. IEEE Data Engineering Bulletin, 24(4):35--43, 2001.
• 28: I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, 2001.
• 29: C. Yu, W. Meng, W. Wu, and K. L. Liu. Efficient and effective metasearch for text databases incorporating linkages among documents. In SIGMOD, 2001.
• 30: Budi Yuwono , Dik Lun Lee, Server Ranking for Distributed Text Retrieval Systems on the Internet, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.41-50, April 01-04, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Design

Keywords:
database selection, keyword query, summarization