Efficient Processing of X-Tuple Based Top-k Queries in Uncertain Database

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.