|
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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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
|
|
| |
3
|
|
 |
4
|
|
| |
5
|
|
| |
6
|
|
| |
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
|
|
| |
10
|
|
| |
11
|
|
 |
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
|
|
 |
14
|
|
 |
15
|
|
 |
16
|
|
 |
17
|
|
| |
18
|
|
| |
19
|
|
| |
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
|
|
 |
26
|
|
 |
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
|
|
 |
30
|
|
 |
31
|
|
| |
32
|
|
| |
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
|
|
 |
36
|
|
 |
37
|
|
 |
38
|
|
 |
39
|
|
 |
40
|
|
|