关键词: 关键字检索, 不确定, top-k, 可能世界

Abstract: The problems of keyword search on relational databases and uncertain data management have been considered extensively, however addressed in isolation in the past. This paper introduces a novel method that combines IR-style keyword query with uncertain relational databases, and defines an uncertain model and its query semantics. The paper also shows a top-k algorithm to perform keyword search query on the attribute level, and return k query results which have maximum rank scores. Rank score of a query result is well-defined, depending on its correlation with query keywords and its possibility under the possible world. An optimized algorithm is introduced to reduce the complexity of the top-k query. The experimental results demonstrate the practicality and efficiency of these methods.

Key words: keyword search, uncertainty, top-k, possible world