Abstract
Keyword search over relational streams is useful when allowing users to query on streams without understanding the details about the streams and query language as well. There have been several research works on this direction, and the state-of-the-art approaches exploit Candidate Networks (CNs), which are schema-level descriptions of possible joining networks of tuples, and generate query plans based on CNs. However, in fact, the performance of these approaches seriously degrades in particular when the maximum size of CNs (\(T_{max}\)) and/or the number of query keywords are large due to the explosive increase in number of CNs. To cope with this problem, we propose a novel query plan called MX-structure to consolidate all CNs as much as possible. We suppress explosive blowup of nodes in query plans by consolidating all common edges among CNs. The experimental results prove that the proposed algorithm performs much better than the state-of-the-art approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
We have \(cn_{edge}=\{1\}\) (edge C{k2}-PS{k3} belongs to CN 1), \(cn_{leaf}=\{1\}\) (node C{k2} is leaf node of CN 1), and \(cn_{ecsubspace}=\{\}\) (t1 is currently in sub-buffer N). As a result, we get \(cn_{active}=\{1\}\).
- 2.
We have \(cn_{edge}=\{1, 2\}\) (edge PS{k3}-P{} belongs to CNs 1 and 2), \(cn_{leaf}\) is empty (node PS{k3} is not leaf node), and \(cn_{ecsubspace}=\{1\}\) (t2 is currently in sub-space \(\{1\}\)). As a result, we get \(cn_{active}=\{1\}\).
- 3.
Notice that buffers of nodes C{k1} and PS{} are not shown here for simplicity.
References
TPC-H benchmark dataset (2015). http://www.tpc.org/tpch/
Agrawal, S., Chaudhuri, S., Das, G.: DBXplorer: a system for keyword-based search over relational databases. In: ICDE (2002)
Arasu, A., Babcock, B., Babu, S., Cieslewicz, J., Datar, M., Ito, K., Srivastava, U., Widom, J.: STREAM: the Stanford data stream management system. Technical report, Stanford InfoLab (2004). http://ilpubs.stanford.edu:8090/641/
Arasu, A., Babu, S., Widom, J.: CQL: a language for continuous queries over streams and relations. In: Lausen, G., Suciu, D. (eds.) DBPL 2003. LNCS, vol. 2921, pp. 1–19. Springer, Heidelberg (2004)
Chaudhuri, S., Das, G., Hristidis, V., Weikum, G.: Probabilistic ranking of database query results. In: VLDB, Toronto, Canada (2004)
Dyk, M., Najgebauer, A., Pierzchała, D.: Agent-based M&S of smart sensors for knowledge acquisition inside the Internet of Things and sensor networks. In: Nguyen, N.T., Trawiński, B., Kosala, R. (eds.) ACIIDS 2015. LNCS, vol. 9012, pp. 224–234. Springer, Heidelberg (2015)
Edward, L.: Cyber physical systems: design challenges. Technical report no. UCB/EECS-2008-8, University of California, Berkeley (2008). Accessed 07 June 2008
Hogan, K.: Interpreting hitwise statistics on longer queries. Technical report, Ask.com (2009)
Hristidis, V., Gravano, L., Papakonstantinou, Y.: Efficient IR-style keyword search over relational databases. In: VLDB (2003)
Hristidis, V., Papakonstantinou, Y.: Discover: keyword search in relational databases. In: VLDB, Hong Kong, China (2002)
Markowetz, A., Yang, Y., Papadias, D.: Keyword search on relational data streams. In: SIGMOD, Beijing, China (2007)
Mehdi, K., Aijun, A., Nick, C., Parke, G., Jaroslaw, S., Xiaohui, Y.: Meaningful keyword search in relational databases with large and complex schema. In: ICDE, Seoul, Korea (2015)
Niggermann, O., Lohweg, V.: On the diagnosis of cyber-physical production systems. In: AAAI, Austin, Texas, USA (2015)
Pericles, O., Altigran, S., Edleno, M.: Ranking candidate networks of relations to improve keyword search over relational databases. In: ICDE, Seoul, Korea (2015)
Qin, L., Yu, J.X., Chang, L.: Scalable keyword search on large data streams. VLDB J. 20, 35–57 (2011)
Shaul, D., Gadi, E., Shai, G., Eran, P.: DTL’s DataSpot: database exploration using plain language. In: VLDB, San Francisco, CA, USA (1998)
Xu, Y., Guan, J., Ishikawa, Y.: Scalable top-k keyword search in relational databases. In: Lee, S., Peng, Z., Zhou, X., Moon, Y.-S., Unland, R., Yoo, J. (eds.) DASFAA 2012, Part II. LNCS, vol. 7239, pp. 65–80. Springer, Heidelberg (2012)
Zhang, H., Sanin, C., Szczerbicki, E.: Experience-oriented enhancement of smartness for Internet of Things. In: Nguyen, N.T., Trawiński, B., Kosala, R. (eds.) ACIIDS 2015. LNCS, vol. 9012, pp. 506–515. Springer, Heidelberg (2015)
Acknowledgments
This research was partly supported by the Grant-in-Aid for Scientific Research (B) (#26280037) by JSPS and the program Research and Development on Real World Big Data Integration and Analysis of the Ministry of Education, Culture, Sports, Science and Technology, Japan.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Bou, S., Amagasa, T., Kitagawa, H. (2016). An Improved Method of Keyword Search over Relational Data Streams by Aggressive Candidate Network Consolidation. In: Hartmann, S., Ma, H. (eds) Database and Expert Systems Applications. DEXA 2016. Lecture Notes in Computer Science(), vol 9827. Springer, Cham. https://doi.org/10.1007/978-3-319-44403-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-44403-1_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44402-4
Online ISBN: 978-3-319-44403-1
eBook Packages: Computer ScienceComputer Science (R0)