随着Web服务的发展和网络上的数据量呈几何式的增长,人们认识到将关系数据库和信息检索的技术融合到一起可以给用户提供更高效的信息检索服务。论文讨论了在关系数据库上进行基于q个关键词(k1,k2,k3,...,kq)的搜索方法。这里的关系数据库可以被建模为带权图模型G(V,E)。其中的V是指图上的结点(即数据库中的元组);E是指数据图上的边,它表示的是元组间的外主键关联。假设Si表示一组包含关键词ki的结点,并且Si?V。我们研究的问题是怎样找到权重最小的k个结果树,并且结果树要包含每个集合Si中的至少一个结点。当k等于1时,该问题等价于最小斯坦纳树问题(Steiner Tree Problem),该问题是NP难的。该问题还有两个前提,即关键词的个数q很小,因为用户一般不会输入过多的关键词;而且图中的边的数目m和结点数的关系,通常满足不等式m<<n2,即数据图是松散的。基于上述特性,本文最主要的工作是提出了一个在数据图上进行关键词搜索的算法,并以此为基础,实现了适用于带权数据图模型的关键词搜索系统DBSearch。通过本文的实验可以看到,该系统在搜索时间和结果质量上,比实验中的其他系统都有所提升。