Finding Top-k Answers in Keyword Search over Relational Databases Using Tuple Units

Existing studies on keyword search over relational databases usually find Steiner trees composed of connected database tuples as answers. They on-the-fly identify Steiner trees by discovering rich structural relationships between database tuples, and neglect the fact that such structural relationships can be precomputed and indexed. Recently, tuple units are proposed to improve search efficiency by indexing structural relationships, and existing methods identify a single tuple unit to answer keyword queries. However, in many cases, multiple tuple units should be integrated to answer a keyword query. Thus, these methods will involve false negatives. To address this problem, in this paper, we study how to integrate multiple related tuple units to effectively answer keyword queries. To achieve a high performance, we devise two novel indexes, single-keyword-based structure-aware index and keyword-pair-based structure-aware index, and incorporate structural relationships between different tuple units into the indexes. We use the indexes to efficiently identify the answers of integrated tuple units. We develop new ranking techniques and algorithms to progressively find the top-k answers. We have implemented our method in real database systems, and the experimental results show that our approach achieves high search efficiency and result quality, and outperforms state-of-the-art methods significantly.