Efficient Processing of X-Tuple Based Top-k Queries in Uncertain Database
Liu Dexi, Wan Changxuan, and Liu Xiping
(School of Information Technology, Jiangxi University of Finance & Economics, Nanchang 330013) (Jiangxi Key Laboratory of Data and Knowledge Engineering, Nanchang 330013)
Abstract：Like top-k in traditional databases, top-k queries in uncertain databases are quite popular and useful due to its wide application usage. However, compared with top-k in traditional databases, queries over uncertain database are more complicated because of the existence of exponential possible worlds. Often, two kinds of generation rules are considered in the uncertain database: independent and mutually exclusive. An x-tuple is the union of the tuples mutually exclusive. U-kRanks queries consider each alternative in x-tuple as single one and return the tuple which has the highest probability appearing at top k or a given rank. However, no matter which alternative (tuple) of an x-tuple appears in a possible world, it is undoubtedly believed that this x-tuple appears in the same possible world accordingly. Thus, instead of ranking each individual tuple, the authors define a novel top-k query semantic in uncertain database, uncertain x-kRanks queries (U-x-kRanks), which return k x-tuples according to the score and the confidence of alternatives in x-tuples, respectively. In order to reduce the search space, they present an efficient algorithm to process U-x-kRanks queries, which can minimize the scan depth by terminating the scan process as soon as the answers are found. Comprehensive experiments on different data sets demonstrate the effectiveness of the proposed solutions.
刘德喜 万常选 刘喜平. 不确定数据库中基于x-tuple的高效Top-k查询处理算法[J]. , 2010, 47(8): 1415-1423.
Liu Dexi, Wan Changxuan, and Liu Xiping. Efficient Processing of X-Tuple Based Top-k Queries in Uncertain Database. Journal of Computer Research and Development, 2010, 47(8): 1415-1423.
