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

Minimum Steiner Tree Based Method to Keyword Search

作　　者：张宇[1] 金顺福[1] 刘国华[1] 苑迎[1] 李丽乐[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《小型微型计算机系统》2010年第1期119-123,共5页Journal of Chinese Computer Systems

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

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]