基于最小Steiner树的关键词查询方法

摘要：

在关系数据库中,关键词查询无需用户学习查询语言和数据库模式相关知识,而且有效地扩大了查询范围.采用元组图描述关系数据库中元组关系,可使关键词查询问题转化为元组图的最小Steiner树求解问题.本文提出元组图上基于相似度的边权重计算方法,使边权重能够反映元组与关键词相似度的大小.然后,鉴于最小Steiner树求解问题是NP-完全问题,提出按照贪心策略执行Dijkstra算法的最小Steiner树较优解求解算法.最后,通过实验对算法进行了分析和验证.

关键词：关系数据库、关键词查询、元组图、最小Steiner树

所属期刊栏目：31

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金项目60773100;国家"十一五"科技支撑计划项目2006BAK05B02

在线出版日期：2010-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：119-123