A diverse class of applications needs to manage large volumes of uncertain data. Examples of such data include incompletely cleaned data, data from acquisition systems such as sensor nets or RFID deployments, data generated by information extraction systems, data inferred from a synopsis or statistical summary, data obtained as a result of imprecise data mappings, data that has been blurred or anonymized to protect privacy, and missing data that has been interpolated or extrapolated. The ability to manage uncertain data is crucial for evaluating the quality of query results, assessing and managing risks arising from data uncertainty, and, more broadly, making sound scientific, engineering, and business decisions in an uncertain world.Data uncertainty is naturally represented by means of a probabilistic data model. Virtually every model of this type considers all possible instantiations of an uncertain database and assigns a probability to each such "possible world." The models differ in the mechanism used to specify the possible-world probabilities; often, probabilities are assigned to individual data items or sets of data items, and these probabilities in turn induce probabilities over possible worlds. A given database query will have a different answer in each possible world, and the possible-world probability distribution therefore gives rise to a probability distribution over query answers. In this setting, "query processing" no longer means simply returning a deterministic set of records that satisfy a query, but rather determining interesting features of