Keyword Queries over Relational Databases Based on Tuple Combination

Databases have been used to organize and retrieve information for many years. In traditional ways, users have to use retrieve languages like SQL to get certain information, this is unfriendly to those who don’t know such languages. So recently, researchers develop a new way to retrieve information from database by the method of keyword query, some works extend the research to aggregate query. However, most of these works by now are aimed to obtain individual tuples to answer the query. In some scenarios, people want to get multiple tuples to make the decision. In order to meet the need of returning multiple tuples, this paper firstly proposes a new concept called combination query to answer keyword query by returning tuple combinations. Some heuristic prune methods are proposed through analysis of the problem, and are integrated to an optimization algorithm. An empirical evaluation on both real data sets and synthetic data sets verifies that the optimization algorithm outperforms the initial algorithm obviously in most cases.