[1]周翔,金远平.用于关系数据库关键词查询的基于划分的候选网络生成算法[J].东南大学学报(自然科学版),2012,42(4):609-613.[doi:10.3969/j.issn.1001-0505.2012.04.006]
 Zhou Xiang,Jin Yuanping.A partition-based candidate network generation algorithm for keyword search on relational databases[J].Journal of Southeast University (Natural Science Edition),2012,42(4):609-613.[doi:10.3969/j.issn.1001-0505.2012.04.006]
点击复制

用于关系数据库关键词查询的基于划分的候选网络生成算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
42
期数:
2012年第4期
页码:
609-613
栏目:
计算机科学与工程
出版日期:
2012-07-20

文章信息/Info

Title:
A partition-based candidate network generation algorithm for keyword search on relational databases
作者:
周翔 金远平
东南大学计算机科学与工程学院, 南京 211189
Author(s):
Zhou Xiang Jin Yuanping
School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
关键词:
候选网络 关系数据库 关键词查询 划分策略
Keywords:
candidate network relational database keyword search partition strategy
分类号:
TP312
DOI:
10.3969/j.issn.1001-0505.2012.04.006
摘要:
为了提高关系数据库关键词查询的性能,提出了基于划分的候选网络生成算法,并分析对比了基于广度优先扩展的候选网络生成算法.利用候选网络的同一性,通过改写图的同构算法为查询结果生成算法提供无冗余的候选网络集合.分析和实验结果表明,当关键词个数与最大候选网络尺寸较小时,2种算法的执行时间和所生成的候选网络数量相近.随着关键词个数与最大候选网络尺寸的不断增大,采用划分策略的候选网络生成算法能够大幅度减少候选网络的冗余,缩短执行时间.当最大候选网络尺寸大于6,关键词个数大于4时,性能改进可达到10倍以上.可见,基于划分的候选网络生成算法适应于中、大规模数据库关键词查询系统.
Abstract:
In order to improve the performance of keyword search on relational databases, a partition-based candidate network generation algorithm is proposed and it is compared with the algorithm based on breadth-first expansion. With the identity of candidate network, an algorithm for graph isomorphism is adapted to generate the non-redundant candidate network for the query results generation. The experimental results and analysis show that when the number of keywords and the maximum candidate network’s size are small, the execution time and the numbers of candidate networks generated by the two algorithms are similar. With the constantly rising in the number of keywords and the maximum size of candidate network, the partition-based candidate network generation algorithm can reduce the redundancy of candidate network greatly, and decrease the execution time. The experiment results show a 10 times or more performance improvement when the maximum size of candidate network is above 6 and the number of keyword is above 4. Hence, the partition-based candidate network generation algorithm is suitable for medium and large-scale keyword search system on relational databases.

参考文献/References:

[1] Hristidis V,Gravano L,Papakonstantinou Y.Efficient IR-style keyword search over relational databases[C] //Proceedings of the 29th VLDB Conference.Berlin,Germany,2003:850-861.
[2] Qin Lu,Yu J X,Chang Liujun.Ten thousand SQLs:parallel keyword queries computing[C] //Proceedings of the VLDB Endowment.Singapore,2010:58-69.
[3] Luo Yi,Lin Xuemin,Wang Wei,et al.SPARK:top-k keyword query in relational databases[C] //Proceedings of the ACM SIGMOD International Conference on Management of Data.Beijing,China,2007:115-126.
[4] Liu Fang,Yu C,Meng Weiyi,et al.Effective keyword search in relational databases[C] //Proceedings of the ACM SIGMOD International Conference on Management of Data.Chicago,USA,2006:563-574.
[5] Qin Lu,Yu J X,Chang Liujun.Keyword search in databases:the power of rdbms[C] //Proceedings of the ACM SIGMOD International Conference on Management of Data.Rhode Island,USA,2009:681-694.
[6] Ding B,Yu J X,Wang S,et al.Finding top-k min-cost connected trees in databases[C] //Proceedings of the 23rd International Conference on Data Engineering.Istanbul,Turkey,2007:836-845.
[7] Hristidis V,Papakonstantinou Y.DISCOVER:keyword search in relational databases[C] //Proceedings of the 28th VLDB Conference.Hong Kong,China,2002:670-681.
[8] Agrawal S,Chaudhuri S,Das G.DBXplorer:a system for keyword-based search over relational databases[C] //Proceedings of the 18th International Conference on Data Engineering.California,USA,2002:5-16.
[9] Yu J X,Qin Lu,Chang Liujun.Keyword search in databases[M].Washington,USA:Morgan and Claypool Publishers,2010:12-21.
[10] Markowetz A,Yang Yin,Papadias D.Keyword search on relational data streams[C] //Proceedings of the ACM SIGMOD International Conference on Management of Data.Beijing,China,2007:605-616.
[11] Qin Lu,Yu J X,Chang Liujun,et al.Scalable keyword search on large data streams[C] //Proceedings of the 25th International Conference on Data Engineering.Shanghai,China,2009:1199-1202.
[12] Ley M,Herbstritt M,Hoffmann O,et al.The DBLP Computer Science Bibliography[EB/OL].(2011-05-01)[2011-05-20].http://www.informatik.uni-trier.de/~ley/db/.
[13] Ullman J R.An algorithm for subgraph isomorphism[J].Journal of the Association for Computing Machinary,1976,23(1):31-42.

相似文献/References:

[1]邓小鹏,周志鹏,李启明,等.地铁工程Near-miss知识库构建[J].东南大学学报(自然科学版),2010,40(5):1103.[doi:10.3969/j.issn.1001-0505.2010.05.042]
 Deng Xiaopeng,Zhou Zhipeng,Li Qiming,et al.Foundation of Near-miss knowledge base for metro projects[J].Journal of Southeast University (Natural Science Edition),2010,40(4):1103.[doi:10.3969/j.issn.1001-0505.2010.05.042]
[2]王能斌,孙明江,朱强.一种关系DBMS数据更改功能的实现策略[J].东南大学学报(自然科学版),1987,17(6):27.[doi:10.3969/j.issn.1001-0505.1987.06.003]
 Wang Nengbin Sun Mingjiang Zhu Qiang (Department of Computer Science and Engineering).A Method of Implementing Data Modification in a Relational DBMS[J].Journal of Southeast University (Natural Science Edition),1987,17(4):27.[doi:10.3969/j.issn.1001-0505.1987.06.003]
[3]王能斌,朱强.关于MicroSQL查询等价的若干定理及查询变换优化策略[J].东南大学学报(自然科学版),1986,16(5):44.[doi:10.3969/j.issn.1001-0505.1986.05.006]
 Wang Nengbin,Zhu Qiang.Some Theorems Relating to the Equivalence of Micro SQL Query Statements and Optimization via Query Transformation[J].Journal of Southeast University (Natural Science Edition),1986,16(4):44.[doi:10.3969/j.issn.1001-0505.1986.05.006]

备注/Memo

备注/Memo:
作者简介: 周翔(1989—),男,硕士生; 金远平(联系人),男,教授,ypjin@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(61073059).
引文格式: 周翔,金远平.用于关系数据库关键词查询的基于划分的候选网络生成算法[J].东南大学学报:自然科学版,2012,42(4):609-613. [doi:10.3969/j.issn.1001-0505.2012.04.006]
更新日期/Last Update: 2012-07-20