Minimum Steiner Tree Based Method to Keyword Search
LI Li-le · Journal of Chinese Computer Systems · 2010
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.