微信服务号

微信订阅号

2025年3月24日 13:52 星期一
首页 > 过刊浏览>2010年第21卷第10期 >2454-2476
PDF HTML阅读 XML下载 导出引用 引用提醒
基于关系数据库的关键词查询
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.50604012 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2009AA01Z150 (国家高技术研究发展计划(863))

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [67]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    介绍了基于关系数据库的关键词查询问题的研究背景;阐述了解决该问题的两大类方法,即基于数据图的方法和基于模式图的方法,并详细介绍了各种方法的原理以及各自的优缺点;最后展望了未来的研究方向.

    Abstract:

    First, the research background of keyword search over relational databases is presented and is followed by a detailed description of two solutions to this problem, i.e., data graph based and schema graph based methods, and a discussion of the principles, advantages and disadvantages of these methods is also mentioned. Finally, some future trends in this area are discussed.

    参考文献
    [1] Bhalotia G, Hulgeri A, Nakhe C, Chakrabarti S, Sudarshan S. Keyword searching and browsing in databases using BANKS. In: Proc. of the 18th Int’l Conf. on Data Engineering (ICDE 2002). San Jose: IEEE Computer Society Press, 2002. 431?440. [doi: 10.1109/ICDE.2002.994756]
    [2] Dixon P. Basics of Oracle text retrieval. Bulletin of the Technical Committee on Data Engineering, 2001,24(4):11?14.
    [3] Maier A, Simmen DE. DB2 optimization in support of full text search. Bulletin of the Technical Committee on Data Engineering, 2001,24(4):3?6.
    [4] Hamilton JR, Nayak TK. Microsoft SQL server full-text search. Bulletin of the Technical Committee on Data Engineering, 2001, 24(4):7?10.
    [5] Chaudhuri S, Ramakrishnan R, Weikum G. Integrating DB and IR technologies: What is the sound of one hand clapping? In: Proc. of the 2nd Biennial Conf. on Innovative Data Systems Research (CIDR 2005). Asilomar, 2005. 1?12. http://www.cidrdb.org/ cidr2005/papers/P01.pdf
    [6] Qin L, Yu JX, Chang LJ. Keyword search in databases: The power of RDBMS. In: Cetintemel U, Zdonik SB, Kossmann D, Tatbul N, eds. Proc. of the 2009 ACM SIGMOD Conf. on Management of Data (SIGMOD 2009). Providence: ACM, 2009. 681?694.
    [7] Golenberg K, Kimelfeld B, Sagiv Y. Keyword proximity search in complex data graphs. In: Tsong J, Wang L, eds. Proc. of the 2008 ACM SIGMOD Conf. on Management of Data (SIGMOD 2008). Vancouver: ACM, 2008. 927?940. [doi: 10.1145/1376616. 1376708]
    [8] Goldman R, Shivakumar N, Venkatasubramanian S, Garcia-Molina H. Proximity search in databases. In: Gupta A, Shmueli O, Widom J, eds. Proc. of the 24th Int’l Conf. on Very Large Data Bases (VLDB’98). New York: Morgan Kaufmann Publishers, 1998. 26?37.
    [9] Agrawal S, Chaudhuri S, Das G. DBXplorer: A system for keyword-based search over relational databases. In: Proc. of the 18th Int’l Conf. on Data Engineering (ICDE 2002). San Jose: IEEE Computer Society Press, 2002. 5?16. [doi: 10.1109/ICDE.2002. 994693]
    [10] Hristidis V, Papakonstantinou Y. DISCOVER: Keyword search in relational databases. In: Proc. of the 28th Int’l Conf. on Very Large Data Bases (VLDB 2002). Hong Kong: Morgan Kaufmann Publishers, 2002. 670?681. http://www.informatik.uni-trier.de/ ~ley/db/conf/vldb/vldb2002.html
    [11] Hristidis V, Gravano L, Papakonstantinou Y. Efficient IR-style keyword search over relational databases. In: Freytag JC, Lockemann PC, Abiteboul S, Carey MJ, Selinger PG, Heuer A, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases (VLDB 2003). Berlin: Morgan Kaufmann Publishers, 2003. 850?861.
    [12] Kacholia V, Pandit S, Chakrabarti S, Sudarshan S, Desai R, Karambelkar H. Bidirectional expansion for keyword search on graph databases. In: B?hm K, Jensen CS, Haas LM, eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB 2005). Trondheim: ACM Press, 2005. 505?516.
    [13] Kimelfeld B, Sagiv Y. Efficient engines for keyword proximity search. In: Doan AH, Neven F, McCann R, eds. Proc. of the 8th Int’l Workshop on the Web & Databases (WebDB 2005). Baltimore: ACM Press, 2005. 67?72.
    [14] Wen JJ, Wang S. SEEKER: Keyword-Based information retrieval over relational databases. Journal of Software, 2005,16(7): 1270?1281 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/1270.htm. [doi: 10.1360/jos161270]
    [15] Kimelfeld B, Sagiv Y. Finding and approximating top-k answers in keyword proximity search. In: Vansummeren S, ed. Proc. of the 25th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS 2006). Chicago: ACM Press, 2006. 173?182. [doi: 10.1145/1142351.1142377]
    [16] Liu F, Yu CT, Meng WY, Chowdhury A. Effective keyword search in relational databases. In: Chaudhuri S, Hristidis V, Polyzotis N, eds. Proc. of the 2006 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD 2006). Chicago: ACM, 2006. 563?574. [doi: 10.1145/1142473.1142536]
    [17] Balmin A, Hristidis V, Papakonstantinou Y. ObjectRank: Authority-Based keyword search in databases. In: Nascimento MA, ?zsu MT, Kossmann D, Miller RJ, Blakeley JB, Schiefer KB, eds. Proc. of the 30th Int’l Conf. on Very Large Data Bases (VLDB 2004). Toronto: Morgan Kaufmann Publishers, 2004. 564?575.
    [18] Ding B, Yu JX, Wang S, Qin L, Zhang X, Lin XM. Finding top-k min-cost connected trees in databases. In: Proc. of the 23rd Int’l Conf. on Data Engineering (ICDE 2007). Istanbul: IEEE Computer Society Press, 2007. 836?845. http://www.informatik. uni-trier.de/~ley/db/conf/icde/icde2007.html
    [19] Luo Y, Lin XM, Wang W, Zhou XF. Spark: Top-k keyword query in relational databases. In: Chan CY, Ooi BC, Zhou AY, eds. Proc. of the 2007 ACM SIGMOD Conf. on Management of Data (SIGMOD 2007). Beijing: ACM, 2007. 115?126.
    [20] Dalvi BB, Kshirsagar M, Sudarshan S. Keyword search on external memory data graphs. PVLDB, 2008,1(1):1189?1204.
    [21] Hristidis V, Hwang H, Papakonstantinou Y. Authority-Based keyword search in databases. ACM Trans. on Database Systems, 2008,33(1):1?40. [doi: 10.1145/1331904.1331905]
    [22] Qin L, Yu JX, Chang LJ, Tao YF. Querying communities in relational databases. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 724?735. http://www.informatik.uni-trier.de/~ley/db/ conf/icde/icde2009.html
    [23] Li GL, Ooi BC, Feng JH, Wang JY, Zhou LZ. EASE: An effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In: Tsong J, Wang L, eds. Proc. of the 2008 ACM SIGMOD Conf. on Management of Data (SIGMOD 2008). Vancouver: ACM, 2008. 903?914.
    [24] Tao YF, Yu JX. Finding frequent co-occurring terms in relational keyword search. In: Kersten ML, Novikov B, Teubner J, Polutin V, Manegold S, eds. Proc. of the 12th Int’l Conf. on Extending Database Technology (EDBT 2009). Saint Petersburg: ACM Press, 2009. 839?850. [doi: 10.1145/1516360.1516456]
    [25] Florescu D, Kossmann D, Manolescu I. Integrating keyword search into XML query processing. Computer Networks, 2000, 33(1-6):119?135. [doi: 10.1016/S1389-1286(00)00069-4]
    [26] Guo L, Shao F, Botev C, Shanmugasundaram J. XRANK: Ranked keyword search over XML documents. In: Halevy AY, Ives ZG, Doan AH, eds. Proc. of the 2003 ACM SIGMOD Conf. on Management of Data (SIGMOD 2003). San Diego: ACM, 2003. 16?27.
    [27] Hristidis V, Papakonstantinou Y, Balmin A. Keyword proximity search on XML graphs. In: Proc. of the 19th Int’l Conf. on Data Engineering (ICDE 2003). Bangalore: IEEE Computer Society Press, 2003. 367?378. [doi: 10.1109/ICDE.2003.1260806]
    [28] Markowetz A, Yang Y, Papadias D. Keyword search on relational data streams. In: Chan CY, Ooi BC, Zhou AY, eds. Proc. of the 2007 ACM SIGMOD Conf. on Management of Data (SIGMOD 2007). Beijing: ACM, 2007. 605?616. [doi: 10.3745/KIPSTD.2009. 16D.6.859]
    [29] Qin L, Yu JX, Chang LJ, Tao YF. Scalable keyword search on large data streams. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 1199?1202. [doi: 10.1007/s00778-010-0190-x]
    [30] Vu QH, Ooi BC, Papadias D, Tung AK. A graph method for keyword-based selection of the top-k databases. In: Tsong J, Wang L, eds. Proc. of the 2008 ACM SIGMOD Conf. on Management of Data (SIGMOD 2008). Vancouver: ACM, 2008. 915?926. [doi: 10.1145/1376616.1376707]
    [31] Yu B, Li GL, Sollins KR, Tung AK. Effective keyword-based selection of relational databases. In: Chan CY, Ooi BC, Zhou AY, eds. Proc. of the 2007 ACM SIGMOD Conf. on Management of Data (SIGMOD 2007). Beijing: ACM, 2007. 139?150. [doi: 10.1145/1247480.1247498]
    [32] Sayyadian M, LeKhac H, Doan AH, Gravano L. Efficient keyword search across heterogeneous relational databases. In: Proc. of the 23rd Int’l Conf. on Data Engineering (ICDE 2007). Istanbul: IEEE Computer Society Press, 2007. 346?355. http://www.informatik.uni-trier.de/~ley/db/conf/icde/icde2007.html
    [33] Felipe ID, Hristidis V, Rishe N. Keyword search on spatial databases. In: Proc. of the 24th Int’l Conf. on Data Engineering (ICDE 2008). Cancún: IEEE Computer Society Press, 2008. 656?665. http://www.informatik.uni-trier.de/~ley/db/conf/icde/icde2008.html
    [34] Zhang DX, Chee YM, Mondal A, Tung AK, Kitsuregawa M. Keyword search in spatial databases: Towards searching by document. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 688?699. http://www.informatik.uni-trier.de/~ley/db/conf/icde/icde2009.html
    [35] Wu P, Sismanis Y, Reinwald B. Towards keyword-driven analytical processing. In: Chan CY, Ooi BC, Zhou AY, eds. Proc. of the 2007 ACM SIGMOD Conf. on Management of Data (SIGMOD 2007). Beijing: ACM, 2007. 617?628. [doi: 10.1145/1247480. 1247549]
    [36] Zhou B, Pei J. Answering aggregate keyword queries on relational databases using minimal group-bys. In: Kersten ML, Novikov B, Teubner J, Polutin V, Manegold S, eds. Proc. of the 12th Int’l Conf. on Extending Database Technology (EDBT 2009). Saint Petersburg: ACM Press, 2009. 108?119. [doi: 10.1145/1516360.1516374]
    [37] Shao QH, Sun P, Chen Y. WISE: A workflow information search engine. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 1491?1494. http://www.informatik.uni-trier.de/~ley/db/conf/icde/ icde2009.html
    [38] Song XM, Li GL, Feng JH, Zhou LZ. Effective fuzzy keyword search over uncertain data. In: Zhou XF, Yokota HR, Deng K, Liu Q, eds. Proc. of the 14th Int’l Conf. on Database Systems for Advanced Applications (DASFAA 2009). Brisbane: Springer-Verlag, 2009. 66?70. [doi: 10.1007/978-3-642-00887-0_6]
    [39] Wang S, Zhang J, Peng ZH, Zhan J, Du XY. Ontology-Based semantic search over relational databases. Journal of Frontiers of Computer Science and Technology, 2007,1(1):59?78 (in Chinese with English abstract). [doi: 10.3778/j.issn.1673-9418.2007.01. 005]
    [40] Wang S, Zhang KL. Searching databases with keywords. Journal of Computer Science Technology, 2005,20(1):55?62.
    [41] Chen Y, Wang W, Liu ZY, Lin XM. Keyword search on structured and semi-structured data. In: Cetintemel U, Zdonik SB, Kossmann D, Tatbul N, eds. Proc. of the 2009 ACM SIGMOD Conf. on Management of Data (SIGMOD 2009). Providence: ACM, 2009. 1005?1010.
    [42] Hulgeri A, Bhalotia G, Nakhe C, Chakrabarti S, Sudarshan S. Keyword search in databases. Bulletin of the Technical Committee on Data Engineering, 2001, 24(3):22?32.
    [43] Kimelfeld B, Sagiv Y. Efficiently enumerating results of keyword search over data graphs. Information System, 2008,33(4-5): 335?359. [doi: 10.1016/j.is.2008.01.002]
    [44] Simitsis A, Koutrika G, Ioannidis YE. Précis: From unstructured keywords as queries to structured databases as answers. The VLDB Journal, 2008,17(1):117?149. [doi: 10.1007/s00778-007-0075-9]
    [45] Wang S, Peng ZH, Zhang J, Qin L, Wang S, Yu JX, Ding BL. NUITS: A novel user interface for efficient keyword search over databases. In: Dayal U, Whang KY, Lomet DB, Alonso G, Lohman GM, Kersten ML, Cha SK, Kim YK, eds. Proc. of the 30th Int’l Conf. on Very Large Data Bases (VLDB 2006). Seoul: Morgan Kaufmann Publishers, 2006. 1143?1146.
    [46] Kimelfeld B, Sagiv Y. Efficiently enumerating results of keyword search. In: Bierman GM, Koch C, eds. Proc. of the 10th Int’l Symp. on Database Programming Languages (DBPL 2005). Trondheim: Springer-Verlag, 2005. 58?73. [doi: 10.1007/11601524_4]
    [47] Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine. Computer Networks, 1998,30(1-7):107?117. [doi: 10.1016/S0169-7552(98)00110-X]
    [48] Li GL, Zhou XF, Feng JH, Wang JY. Progressive keyword search in relational databases. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 1183?1186. [doi: 10.1007/978-3-540-70504-8]
    [49] Reich G, Widmayer P. Beyond Steiner’s problem: A VLSI oriented generalization. In: Nagl M, ed. Proc. of the 15th Int’l Workshop on Graph-Theoretic Concepts in Computer Science (WG’89). Castle Rolduc: Springer-Verlag, 1989. 196?210.
    [50] Robins G, Zelikovsky A. Improved Steiner tree approximation in graphs. In: Proc. of the 11th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2000). San Francisco: ACM, 2000. 770?779. http://www.informatik.uni-trier.de/~ley/db/conf/soda/ soda2000.html
    [51] He H, Wang HX, Yang J, Yu PS. BLINKS: Ranked keyword searches on graphs. In: Chan CY, Ooi BC, Zhou AY, eds. Proc. of the 2007 ACM SIGMOD Conf. on Management of Data (SIGMOD 2007). Beijing: ACM, 2007. 305?316.
    [52] Li GL, Feng JH, Zhou LZ. Retune: Retrieving and materializing tuple units for effective keyword search over relational databases. In: Li Q, Spaccapietra S, Yu ES, Olivé A, eds. Proc. of the 27th Int’l Conf. on Conceptual Modeling (ER 2008). Barcelona: Springer-Verlag, 2008. 469?483. [doi: 10.1007/978-3-540-87877-3]
    [53] Kazai G, Lalmas M. Extended cumulated gain measures for the evaluation of content-oriented XML retrieval. ACM Trans. on Information System, 2006,24(4):503?542. [doi: 10.1145/1185877.1185883]
    [54] Peng ZH, Zhang J, Wang S, Qin L. TreeCluster: Clustering results of keyword search over databases. In: Yu JX, Kitsuregawa M, Leong HV, eds. Proc. of the 7th Int’l Conf. on Advances in Web-Age Information Management (WAIM 2006). Hong Kong: Springer-Verlag, 2006. 385?396. [doi: 10.1007/11775300]
    [55] Peng ZH, Zhang J, Wang S. S-CBR: Presenting results of keyword search over databases based on database schema. Journal of Software, 2008,19(2):323?337 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/323.htm. [doi: 10.3724/SP.J. 1001.2008.00323]
    [56] Chakrabarti K, Chaudhuri S, Hwang SW. Automatic categorization of query results. In: Weikum G, K?nig AC, De?loch S, eds. Proc. of the 2004 ACM SIGMOD Conf. on Management of Data (SIGMOD 2004). Paris: ACM, 2004. 755?766. [doi: 10.1145/ 1007568.1007653]
    [57] Koutrika G, Zadeh ZM, Garcia-Molina H. Data clouds: Summarizing keyword search results over structured data. In: Kersten ML, Novikov B, Teubner J, Polutin V, Manegold S, eds. Proc. of the 12th Int’l Conf. on Extending Database Technology (EDBT 2009). Saint Petersburg: ACM Press, 2009. 391?402.
    [58] Wheeldon R, Levene M, Keenoy K. DbSurfer: A search and navigation tool for relational databases. In: Williams MH, MacKinnon LM, eds. Proc. of the 21st British National Conf. on Databases (BNCOD 2004). Edinburgh: Springer-Verlag, 2004. 144?149.
    [59] Raghavan P. Structured and unstructured search in enterprises. Bulletin of the Technical Committee on Data Engineering, 2001,24(4):15?18.
    [60] Zhan J, Wang S. ITREKS: Keyword search over relational database by indexing tuple relationship. In: Ramamohanarao K, Krishna PR, Mohania MK, Nantajeewarawat E, eds. Proc. of the 12th Int’l Conf. on Database Systems for Advanced Applications (DASFAA 2007). Bangkok: Springer-Verlag, 2007. 67?78. [doi: 10.1007/978-3-540-71703-4]
    [61] Su Q, Widom J. Indexing relational database content offline for efficient keyword-based search. In: Proc. of the 9th Int’l Database Engineering and Applications Symp. (IDEAS 2005). Montreal: IEEE Computer Society, 2005. 297?306. [doi: 10.1109/IDEAS. 2005.36]
    [62] Markowetz A, Yang Y, Papadias D. Reachability indexes for relational keyword search. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society Press, 2009. 1163?1166. http://www.informatik.uni-trier.de/~ley/db/ conf/icde/icde2009.html
    [63] Pu KQ, Yu XH. Keyword query cleaning. PVLDB, 2008,1(1):909?920.
    [64] Tata S, Lohman GM. SQAK: Doing more with keywords. In: Tsong J, Wang L, eds. Proc. of the 2008 ACM SIGMOD Conf. on Management of Data (SIGMOD 2008). Vancouver: ACM, 2008. 889?902.
    附中文参考文献: [14] 文继军,王珊.SEEKER:基于关键词的关系数据库信息检索.软件学报,2005,16(7):1270?1281. http://www.jos.org.cn/1000-9825/ 16/1270.htm. [doi: 10.1360/jos161270]
    [39] 王珊,张俊,彭朝晖,战疆,杜小勇.基于本体的关系数据库语义检索.计算机科学与探索,2007,1(1):59?78. [doi: 10.3778/j.issn. 1673-9418.2007.01.005]
    [55] 彭朝晖,张俊,王珊.S-CBR:基于数据库模式展现数据库关键词检索结果.软件学报,2008,19(2):323?337. http://www.jos.org.cn/ 1000-9825/19/323.htm. [doi: 10.3724/SP.J.1001.2008.00323]
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

林子雨,杨冬青,王腾蛟,张东站.基于关系数据库的关键词查询.软件学报,2010,21(10):2454-2476

复制
分享
文章指标
  • 点击次数:10760
  • 下载次数: 12171
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2009-09-22
  • 最后修改日期:2010-07-19
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19728040位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号