Abstract
We present a novel method for translating keyword queries over relational databases into SQL queries with the same intended semantic meaning. In contrast to the majority of the existing keyword-based techniques, our approach does not require any a-priori knowledge of the data instance. It follows a probabilistic approach based on a Hidden Markov Model for computing the top-K best mappings of the query keywords into the database terms, i.e., tables, attributes and values. The mappings are then used to generate the SQL queries that are executed to produce the answer to the keyword query. The method has been implemented into a system called KEYRY (from KEYword to queRY).
This work was partially supported by project “Searching for a needle in mountains of data” http://www.dbgroup.unimo.it/keymantic
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aditya, B., Bhalotia, G., Chakrabarti, S., Hulgeri, A., Nakhe, C., Parag, Sudarshan, S.: Banks: Browsing and keyword searching in relational databases. In: VLDB, pp. 1083–1086 (2002)
Agrawal, S., Chaudhuri, S., Das, G.: Dbxplorer: A system for keyword-based search over relational databases. In: ICDE, pp. 5–16. IEEE Computer Society, Los Alamitos (2002)
Bergamaschi, S., Domnori, E., Guerra, F., Lado, R.T., Velegrakis, Y.: Keyword search over relational databases: a metadata approach. In: SIGMOD. ACM, New York (2011)
Bergamaschi, S., Domnori, E., Guerra, F., Orsini, M., Lado, R.T., Velegrakis, Y.: Keymantic: Semantic keyword-based searching in data integration systems. PVLDB 3(2), 1637–1640 (2010)
Chakrabarti, S., Sarawagi, S., Sudarshan, S.: Enhancing search with structure. IEEE Data Eng. Bull. 33(1), 3–24 (2010)
Forney Jr., G.D.: The Viterbi algorithm. Proceedings of the IEEE 61(3), 268 (1973)
Hristidis, V., Papakonstantinou, Y.: Discover: Keyword search in relational databases. In: VLDB, pp. 670–681 (2002)
Kumar, R., Tomkins, A.: A Characterization of Online Search Behavior. IEEE Data Engineering Bulletin 32(2), 3–11 (2009)
Li, L., Shang, Y., Shi, H., Zhang, W.: Performance evaluation of hits-based algorithms. In: Hamza, M.H. (ed.) Communications, Internet, and Information Technology, pp. 171–176. IASTED/ACTA Press (2002)
Seshadri, N., Sundberg, C.-E.W.: List viterbi decoding algorithms with applications. IEEE Transactions on Communications 42(234) (1994)
Tata, S., Lohman, G.M.: SQAK: doing more with keywords. In: SIGMOD, pp. 889–902. ACM, New York (2008)
Yu, J.X., Qin, L., Chang, L.: Keyword Search in Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, San Francisco (2010)
Zenz, G., Zhou, X., Minack, E., Siberski, W., Nejdl, W.: From keywords to semantic queries-incremental query construction on the semantic web. Journal of Web Semantics 7(3), 166–176 (2009)
Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Computing Surveys 38(2) (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bergamaschi, S., Guerra, F., Rota, S., Velegrakis, Y. (2011). A Hidden Markov Model Approach to Keyword-Based Search over Relational Databases. In: Jeusfeld, M., Delcambre, L., Ling, TW. (eds) Conceptual Modeling – ER 2011. ER 2011. Lecture Notes in Computer Science, vol 6998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24606-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-24606-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24605-0
Online ISBN: 978-3-642-24606-7
eBook Packages: Computer ScienceComputer Science (R0)