Evaluating Queries on Mystiq, a Probabilistic Database

A probabilistic database represents a probability distribution of possible worlds.  
Queries over a probabilistic database are likely to be of the form "return the Top-K most likely answers". 
Query execution must thus be extended to handle probabilities correctly; a non trivial task. 
I will discuss work done by Dan Suciu, Nilesh Dalvi, and Chris Re on Mystiq, a probabilistic database.  
I will both provide a background and summary of the Mystiq project, and discuss some particular challenges 
they faced in query execution with respect to uncertain data.