Efficient Top-k Query Evaluation on Probabilistic Data

TLDR

Enterprise applications must handle unreliable, inconsistent, and imprecise data, and while probabilistic databases model such uncertainty, precise SQL query evaluation is theoretically hard and prior methods either restrict queries, approximate probabilities, or fail to scale. This work proposes a novel method to efficiently compute and rank the top‑k answers of a SQL query on a probabilistic database. The algorithm runs parallel Monte‑Carlo simulations for each candidate answer, approximating probabilities only as far as needed to determine the correct top‑k set.

Abstract

Modern enterprise applications are forced to deal with unreliable, inconsistent and imprecise information. Probabilistic databases can model such data naturally, but SQL query evaluation on probabilistic databases is difficult: previous approaches have either restricted the SQL queries, or computed approximate probabilities, or did not scale, and it was shown recently that precise query evaluation is theoretically hard. In this paper we describe a novel approach, which computes and ranks efficiently the top-k answers to a SQL query on a probabilistic database. The restriction to top-k answers is natural, since imprecisions in the data often lead to a large number of answers of low quality, and users are interested only in the answers with the highest probabilities. The idea in our algorithm is to run in parallel several Monte-Carlo simulations, one for each candidate answer, and approximate each probability only to the extent needed to compute correctly the top-k answers.