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

摘要

为了提高关系数据库关键词查询的性能,提出了基于划分的候选网络生成算法,并分析对比了基于广度优先扩展的候选网络生成算法.利用候选网络的同一性,通过改写图的同构算法为查询结果生成算法提供无冗余的候选网络集合.分析和实验结果表明,当关键词个数与最大候选网络尺寸较小时,2种算法的执行时间和所生成的候选网络数量相近.随着关键词个数与最大候选网络尺寸的不断增大,采用划分策略的候选网络生成算法能够大幅度减少候选网络的冗余,缩短执行时间.当最大候选网络尺寸大于6,关键词个数大于4时,性能改进可达到10倍以上.可见,基于划分的候选网络生成算法适应于中、大规模数据库关键词查询系统.%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.