Keyword search in databases: the power of RDBMS

ABSTRACT

Keyword search in relational databases (RDBs) has been extensively studied recently. A keyword search (or a keyword query) in RDBs is specified by a set of keywords to explore the interconnected tuple structures in an RDB that cannot be easily identified using SQL on RDBMS. In brief, it finds how the tuples containing the given keywords are connected via sequences of connections (foreign key references) among tuples in an RDB. Such interconnected tuple structures can be found as connected trees up to a certain size, sets of tuples that are reachable from a root tuple within a radius, or even multi-center subgraphs within a radius. In the literature, there are two main approaches. One is to generate a set of relational algebra expressions and evaluate every such expression using SQL on an RDBMS directly or in a middleware on top of an RDBMS indirectly. Due to a large number of relational algebra expressions needed to process, most of the existing works take a middleware approach without fully utilizing RDBMSs. The other is to materialize an RDB as a graph and find the interconnected tuple structures using graph-based algorithms in memory.

In this paper we focus on using SQL to compute all the interconnected tuple structures for a given keyword query. We use three types of interconnected tuple structures to achieve that and we control the size of the structures. We show that the current commercial RDBMSs are powerful enough to support such keyword queries in RDBs efficiently without any additional new indexing to be built and maintained. The main idea behind our approach is tuple reduction. In our approach, in the first reduction step, we prune tuples that do not participate in any results using SQL, and in the second join step, we process the relational algebra expressions using SQL over the reduced relations. We conducted extensive experimental studies using two commercial RDBMSs and two large real datasets, and we report the efficiency of our approaches in this paper.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 3: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 4: 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
• 5: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 6: S. Chaudhuri, R. Ramakrishnan, and G. Weikum. Integrating db and ir technologies: What is the sound of one hand clapping? In Proc. of CIDR, 2005.
• 7: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• 8: Bhavana Bharat Dalvi , Meghana Kshirsagar , S. Sudarshan, Keyword search on external memory data graphs, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453982]
• 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 Proc. of ICDE'07, 2007.
• 10: S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. In Networks, 1972.
• 11: Konstantin Golenberg , Benny Kimelfeld , Yehoshua Sagiv, Keyword proximity search in complex data graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376708]
• 12: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 13: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, BLINKS: ranked keyword searches on graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247516]
• 14: Vagelis Hristidis , Luis Gravano , Yannis Papakonstantinou, Efficient IR-style keyword search over relational databases, Proceedings of the 29th international conference on Very large data bases, p.850-861, September 09-12, 2003, Berlin, Germany
• 15: Vagelis Hristidis , Heasoo Hwang , Yannis Papakonstantinou, Authority-based keyword search in databases, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-40, March 2008 [doi>10.1145/1331904.1331905]
• 16: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 17: 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
• 18: Anastasios Kementsietsidis , Frank Neven , Dieter Van de Craen , Stijn Vansummeren, Scalable multi-query optimization for exploratory queries over federated scientific databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453864]
• 19: 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]
• 20: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering, p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 21: Guoliang Li , Beng Chin Ooi , Jianhua Feng , Jianyong Wang , Lizhu Zhou, EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376706]
• 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: Yi Luo , Xuemin Lin , Wei Wang , Xiaofang Zhou, Spark: top-k keyword query in relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247495]
• 24: Alexander Markowetz , Yin Yang , Dimitris Papadias, Keyword search on relational data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247548]
• 25: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 26: Lu Qin , Jeffrey Xu Yu , Lijun Chang , Yufei Tao, Querying Communities in Relational Databases, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.724-735, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.67]
• 27: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 28: Alkis Simitsis , Georgia Koutrika , Yannis Ioannidis, Précis: from unstructured keywords as queries to structured databases as answers, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.1, p.117-149, January 2008 [doi>10.1007/s00778-007-0075-9]
• 29: H. Yoo , S. Lafortune, An Intelligent Search Method for Query Optimization by Semijoins, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.226-237, June 1989 [doi>10.1109/69.87962]
• 30: Clement T. Yu , Weiyi Meng, Principles of database query processing for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 31: Jingren Zhou , Per-Ake Larson , Johann-Christoph Freytag , Wolfgang Lehner, Efficient exploitation of similar subexpressions for query processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247540]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
keyword search, relational database management systems