论文摘要
越来越多的信息被存储在关系数据库中,面向关系数据库的关键字查询的需求也随之增多。尽管许多数据库管理系统支持全文本信息搜索，但是,在这些系统中,用户必须预先知道所要查询的关系数据库的模式结构,并且通过某种结构化的查询语言查询数据库。Web关键字搜索的巨大成功,使面向关系数据库的关键字查询成为一个崭新的研究领域。然而,面向关系数据库的关键字查询面临着三个挑战：（1）查询结果是由分散在不同关系表中的元组连接而成。（2）计算结果的相关度时,必须计算分散在各个关系表中的关键字与查询关键字之间的相关度。（3）与文本数据库相比,关系数据库的结构更复杂。因此,传统信息搜索领域的评分函数以及搜索算法不能直接应用到数据库关键字搜索中。本文通过研究元组的语义特性以及元组间的语义关系,提出一种新的评分函数。该评分函数不仅涵盖了当前的评分思想,并且用一些新的指标来衡量查询结果与查询关键字之间的相关性,从而更贴切和准确地衡量查询结果与查询关键字间的相关度。基于新的评分函数,主要提出四种Top-k搜索算法。分别为基本算法、EBA（Early-stopping Block Algorithm）算法、AEBA （Advanced Early-stopping Block Algorithm）算法、GAEBA算法（Global Advanced Early-stopping Block Algorithm）。后三种算法以数据块为处理单位,避免频繁访问数据库,因而提高搜索效率。AEBA算法在EBA算法基础上运用多表连接优化策略,避免了EBA算法存在的重复连接问题,从而进一步提高效率。EBA算法和AEBA算法主要针对单个连接查询计划,‘而GAEBA算法利用一种优先调度机制,有效处理多个连接查询计划。另外,本文对当前的存在的稀疏算法进行了改进,使之能适应本文提出的评分函数。实验和分析证明,本文提出的评分函数的合理性以及EBA算法、AEBA算法、GAEBA算法的高效性。