Efficient Processing of Global Top-k Aggregate Queries in Uncertain Database

Top-k queries in uncertain databases are quite popular and useful due to its wide application usage. However, compared to top-k in traditional databases, queries over uncertain database are more complicated because of the existence of exponential possible worlds. A Top-k aggregate query ranks groups of tuples by their aggregate values, sum or average for example, and returns k groups with the highest aggregate values. As a powerful semantic of top-k, global top-k, returns A highest-ranked tuples according to their probabilities of being in the top-k anTopswers in possible worlds. We propose a dynamic programming based method to process global top-k aggregate queries in uncertain database, where the number of retrieved tuples and group states generated on these tuples are minimized. Experiment results show that our algorithm is effective.