Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Relational Keyword Search (R-KWS) provides an intuitive way to query relational data without requiring SQL, or knowledge of the underlying schema. In this article we describe a comprehensive framework for R-KWS covering snapshot queries on conventional tables and continuous queries on relational streams. Our contributions are summarized as follows: (i) We provide formal semantics, addressing the temporal validity and order of results, spanning uniformly over tables and streams; (ii) we investigate two general methodologies for query processing, graph based and operator based, that resolve several problems of previous approaches; and (iii) we develop a range of algorithms and optimizations covering both methodologies. We demonstrate the effectiveness of R-KWS, as well as the significant performance benefits of the proposed techniques, through extensive experiments with static and streaming datasets.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: 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
• 3: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 4: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 5: 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
• 6: 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
• 7: Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S. R., Raman, V., Reiss, F., and Shah, M. A. 2003. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR).
• 8: Surajit Chaudhuri , Umeshwar Dayal , Tak W. Yan, Join queries with external text sources: execution and optimization techniques, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.410-422, May 22-25, 1995, San Jose, California, United States
• 9: Sara Cohen , Yaron Kanza , Benny Kimelfeld , Yehoshua Sagiv, Interconnection semantics for keyword search in XML, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099674]
• 10: Shaul Dar , Gadi Entin , Shai Geva , Eran Palmon, DTL's DataSpot: Database Exploration Using Plain Language, Proceedings of the 24rd International Conference on Very Large Data Bases, p.645-649, August 24-27, 1998
• 11: Ian De Felipe , Vagelis Hristidis , Naphtali Rishe, Keyword Search on Spatial Databases, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.656-665, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497474]
• 12: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, ACM SIGMOD Record, v.30 n.2, p.115-126, June 2001
• 13: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 14: 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]
• 15: Luis Gravano , Panagiotis G. Ipeirotis , Nick Koudas , Divesh Srivastava, Text joins in an RDBMS for web data integration, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775166]
• 16: 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]
• 17: 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]
• 18: 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
• 19: 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
• 20: Hristidis, V., Papakonstantinou, Y., and Balmin, A. 2003. Keyword proximity search on XML graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 367--378.
• 21: Vagelis Hristidis , Oscar Valdivia , Michail Vlachos , Philip S. Yu, Continuous keyword search on multiple text streams, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183738]
• 22: Utku Irmak , Svilen Mihaylov , Torsten Suel , Samrat Ganguly , Rauf Izmailov, Efficient query subscription processing for prospective search engines, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.35-35, May 30-June 03, 2006, Boston, MA
• 23: 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
• 24: Kimelfeld, B. and Sagiv, Y. 2005. Efficiently enumerating results of keyword search. In Proceedings of the International Symposium on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 3774, 58--73.
• 25: 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]
• 26: Jürgen Krämer , Bernhard Seeger, PIPES: a public infrastructure for processing and exploring streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007699]
• 27: 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]
• 28: 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]
• 29: Ziyang Liu , Yi Chen, Identifying meaningful return information for XML keyword search, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247518]
• 30: 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]
• 31: 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]
• 32: Alexander Markowetz , Yin Yang , Dimitris Papadias, Reachability Indexes for Relational Keyword Search, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1163-1166, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.191]
• 33: Sarda, N. L. and Jain, A. 2001. Mragyati: A system for keyword-based searching in databases. Tech. rep. CoRR, cs.DB/0110052.
• 34: Sayyadian, M., Lekhac, H., Doan, A., and Gravano, L. 2007. Efficient keyword search across heterogeneous relational databases. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 346--355.
• 35: Qi Su , Jennifer Widom, Indexing Relational Database Content Offline for Efficient Keyword-Based Search, Proceedings of the 9th International Database Engineering & Application Symposium, p.297-306, July 25-27, 2005 [doi>10.1109/IDEAS.2005.36]
• 36: Quang Hieu Vu , Beng Chin Ooi , Dimitris Papadias , Anthony K. H. Tung, A graph method for keyword-based selection of the top-K databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376707]
• 37: Ping Wu , Yannis Sismanis , Berthold Reinwald, Towards keyword-driven analytical processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247549]
• 38: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 39: Bei Yu , Guoliang Li , Karen Sollins , Anthony K. H. Tung, Effective keyword-based selection of relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247498]
• 40: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

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

General Terms:
Algorithms

Keywords:
Search, data graph, data streams, query processing, relational databases