Article

Keyword search on relational data streams

Authors:

Alexander Markowetz,

Dimitris PapadiasAuthors Info & Claims

SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Pages 605 - 616

https://doi.org/10.1145/1247480.1247548

Published: 11 June 2007 Publication History

Abstract

Increasing monitoring of transactions, environmental parameters, homeland security, RFID chips and interactions of online users rapidly establishes new data sources and application scenarios. In this paper, we propose keyword search on relational data streams (S-KWS) as an effective way for querying in such intricate and dynamic environments. Compared to conventional query methods, S-KWS has several benefits. First, it allows search for combinations of interesting terms without a-priori knowledge of the data streams in which they appear. Second, it hides the schema from the user and allows it to change, without the need for query re-writing. Finally, keyword queries are easy to express.

Our contributions are summarized as follows. (i) We provide formal semantics for S-KWS, addressing the temporal validity and order of results. (ii) We propose an efficient algorithm for generating operator trees, applicable to arbitrary schemas. (iii) We integrate these trees into an operator mesh that shares common expressions. (iv) We develop techniques that utilize the operator mesh for efficient query processing. The techniques adapt dynamically to changes in the schema and input characteristics. Finally, (v) we present methods for purging expired tuples, minimizing either CPU, or memory requirements.

References

[1]

Arasu, A., Babu, S., Widom, J. The CQL Continuous Query Language: Semantic Foundations and Query Execution. VLDB Journal, 15(2): 121--142, 2006.

Digital Library

[2]

Abadi, D. J., Carney, D., Çetintemel, U., Cherniack, M., Convey, C., Lee, S., Stonebraker, M., Tatbul, N., Zdonik, S. B. Aurora: a New Model and Architecture for Data Stream Management. VLDB Journal, 12(2): 120--139, 2003.

Digital Library

[3]

Agrawal, S., Chaudhuri, S., Das, G. DBXplorer: A system for keyword-based search over relational databases. ICDE, 2002.

[4]

Avnur, R., Hellerstein, J. M. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.

Digital Library

[5]

Balmin, A., Hristidis, V., Papakonstantinou, Y. ObjectRank: Authority-based keyword search in databases. VLDB, 2004.

Digital Library

[6]

Babock, B., Babu, S., Datar, M., Motwani, R., Widom, J. Models and Issues in Data Stream Systems, PODS, 2002.

Digital Library

[7]

Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S. R., Raman, V., Reiss, F., Shah, M. A. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. CIDR, 2003.

[8]

Chaudhuri, S., Das, G., Hristidis, V., Weikum, G. Probabilistic ranking of database query results. VLDB, 2004.

Digital Library

[9]

Cohen, S., Kanza, Y., Kimelfeld, B. Sagiv, Y. Interconnection semantics for keyword search in XML. CIKM, 2005.

Digital Library

[10]

Dar, S., Entin, G., Geva, S., Palmon, E. DTL's DataSpot: Database exploration using plain language. VLDB, 1998.

Digital Library

[11]

Fabret, F., Jacobsen, H. A., Llirbat, F., Pereira, J., Ross, K. A., Shasha, D. Filtering algorithms and implementation for very fast publish/subscribe systems. SIGMOD Record, 30(2): 115--126, 2001.

Digital Library

[12]

Golab, L., Öszu, T. M. Issues in Data Stream Management. SIGMOD Record, 32(2): 5--14, 2003.

Digital Library

[13]

Guo, L., Shao, F., Botev C., Shanmugasundaram J. XRANK: Ranked keyword search over XML documents. SIGMOD, 2003.

Digital Library

[14]

Hulgeri, A., Bhalotia, G., Nakhe, C., Chakrabarti, S., Sudarshan, S. Keyword search in databases. IEEE Data Engineering Bulletin 24(3): 22--32, 2001.

[15]

Hristidis, V., Gravano, L., Papakonstantinou, Y. Efficient IR-style keyword search over relational databases. VLDB, 2003.

Digital Library

[16]

Hristidis, V., Papakonstantinou, Y. DISCOVER: Keyword search in relational databases. VLDB, 2002.

Digital Library

[17]

Hristidis, V., Papakonstantinou, Y., Balmin, A. Keyword proximity search on XML graphs. ICDE, 2003.

[18]

Hristidis, V., Valdivia, O., Vlachos, M., Yu, P. Continuous Keyword Search on Multiple Text Streams. Poster, CIKM, 2006.

Digital Library

[19]

Irmak, U., Mihaylov, S., Suel, T., Ganguly, S., Izmailov, R. Efficient Query Subscription Processing for Prospective Search Engines. USENIX Annual Technical Conference, 2006.

Digital Library

[20]

Kramer, J., Seeger, B. PIPES: a public infrastructure for processing and exploring streams. SIGMOD, 2004.

Digital Library

[21]

Liu, F., Yu, C., Meng, W., Chowdhury, A. Effective Keyword Search in Relational Databases. SIGMOD, 2006.

Digital Library

[22]

Sarda N. L., Jain, A. Mragyati: A system for keyword-based searching in databases. TR CoRR cs.DB/0110052, 2001.

[23]

Su Q., Widom, J. Indexing relational database content offline for efficient keyword-based search. IDEAS, 2005.

Digital Library

[24]

Wheeldon, R., Levene, M., Keenoy, K. DbSurfer: A search and navigation tool for relational databases. Annual British National Conference on Databases, 2004.

[25]

Yan, T. W., Garcia-Molina, H. The SIFT information dissemination system. ACM Transactions on Database Systems, 24(4): 529--565, 1999.

Digital Library

Cited By

de Oliveira Pda Silva Ade Moura Ede Freitas R(2022)Efficient Match-Based Candidate Network Generation for Keyword Queries Over Relational DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299804634:4(1735-1750)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.2998046
Ding GSun HLi JLi CWei RFei Y(2020)An Efficient Relational Database Keyword Search Scheme Based on Combined Candidate Network EvaluationIEEE Access10.1109/ACCESS.2020.29732178(30863-30872)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2973217
Bryson SDavoudi HGolab LKargar MLytvyn YMierzejewski PSzlichta JZihayat M(2020)Robust keyword search in large attributed graphsInformation Retrieval Journal10.1007/s10791-020-09379-9Online publication date: 22-Jul-2020
https://doi.org/10.1007/s10791-020-09379-9
Show More Cited By

Index Terms

Keyword search on relational data streams
1. Information systems
  1. Data management systems
    1. Query languages
  2. Information retrieval
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Efficient Top-k Keyword Search on XML Streams
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer Scientists

Keywords can be used to query XML data without schema information. In this paper, a novel kind of query is proposed, top-k keyword search over XML streams. According to the set of keywords and the number of results, such query can retrieve the top-k XML ...
Keyword search over relational tables and streams

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 ...
Keyword Search with Path-Based Filtering over XML Streams
SRDS '14: Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems

Recently, a great deal of attention has been focusing on processing keyword search over static and XML streams. Keyword search is becoming more popular for its simplicity and its user-friendliness in querying XML databases. However, it is hard to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

June 2007

1210 pages

ISBN:9781595936868

DOI:10.1145/1247480

General Chairs:
Lizhu Zhou
Tsinghua University, China
,
Tok Wang Ling
National University of Singapore, Singapore
,
Program Chair:
Beng Chin Ooi
National University of Singapore, Singapore

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS07

Sponsor:

SIGMOD/PODS07: International Conference on Management of Data

June 11 - 14, 2007

Beijing, China

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
48
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

de Oliveira Pda Silva Ade Moura Ede Freitas R(2022)Efficient Match-Based Candidate Network Generation for Keyword Queries Over Relational DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299804634:4(1735-1750)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.2998046
Ding GSun HLi JLi CWei RFei Y(2020)An Efficient Relational Database Keyword Search Scheme Based on Combined Candidate Network EvaluationIEEE Access10.1109/ACCESS.2020.29732178(30863-30872)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2973217
Bryson SDavoudi HGolab LKargar MLytvyn YMierzejewski PSzlichta JZihayat M(2020)Robust keyword search in large attributed graphsInformation Retrieval Journal10.1007/s10791-020-09379-9Online publication date: 22-Jul-2020
https://doi.org/10.1007/s10791-020-09379-9
Jacobs SWang XCarey MTsotras VUddin M(2020)BAD to the bone: Big Active Data at its coreThe VLDB Journal10.1007/s00778-020-00616-7Online publication date: 23-May-2020
https://doi.org/10.1007/s00778-020-00616-7
Lu XTheodoratos DDimitriou A(2020)Leveraging Pattern Mining Techniques for Efficient Keyword Search on Data GraphsWeb Information Systems Engineering10.1007/978-981-15-3281-8_10(98-114)Online publication date: 6-Feb-2020
https://doi.org/10.1007/978-981-15-3281-8_10
M.S. VHaritsa J(2019)Operator implementation of Result Set Dependent KWS scoring functionsInformation Systems10.1016/j.is.2019.101465(101465)Online publication date: Nov-2019
https://doi.org/10.1016/j.is.2019.101465
Bou SAmagasa TKitagawa H(2019)Scalable keyword search over relational data streams by aggressive candidate network consolidationInformation Systems10.1016/j.is.2018.12.00481(117-135)Online publication date: Mar-2019
https://doi.org/10.1016/j.is.2018.12.004
Lang KHan WLi TCai Z(2019)Authority-Based Ranking in Propaganda Summary Generation Considering ValuesAdvances in Computer Communication and Computational Sciences10.1007/978-981-13-6861-5_50(591-601)Online publication date: 22-May-2019
https://doi.org/10.1007/978-981-13-6861-5_50
Cui JShi LLi JLiu Z(2018)An Efficient Framework for String Similarity Continuous Query on Data Stream2018 5th International Conference on Systems and Informatics (ICSAI)10.1109/ICSAI.2018.8599504(1240-1247)Online publication date: Nov-2018
https://doi.org/10.1109/ICSAI.2018.8599504
Oliveira Pda Silva Ade Moura ERodrigues R(2018)Match-Based Candidate Network Generation for Keyword Queries over Relational Databases2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00146(1344-1347)Online publication date: Apr-2018
https://doi.org/10.1109/ICDE.2018.00146
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten