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

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

Minimum Steiner Tree Based Method to Keyword Search

In relational databases, keyword search needn't the users to study the knowledge of query language and database schema, and it extended the range of query in database effectively. Adopt tuple graph to describe the tuple relationship in database can trans-form this problem from keyword search to calculating minimum Steiner tree of tuple graph. This paper introduces similarity based edge-weight calculating method which make the edge-weight reflect the similarity between tuples, and then whereas the minimum Steiner tree problem is NP-complete problem, introduces an algorithm to calculate approximate answer of minimum Steiner tree by running Dijkstra algorithm according to greed strategy. Finally, the algorithm is analyzed and validated by experiments.