This paper presents a framework for evaluating complex SQL queries with uncertain predicates on probabilistic databases. The framework uses a probabilistic model to rank query results, similar to information retrieval. The main focus is on query evaluation, where an optimization algorithm is described to efficiently compute most queries. However, it is shown that some queries are #P-complete, implying they cannot be evaluated efficiently. For these queries, approximation and Monte-Carlo simulation algorithms are proposed. The paper discusses the challenges of evaluating probabilistic queries, particularly the issue of correlated probabilities in intermediate results. It introduces an approach that rewrites query plans to ensure correct evaluation. The framework supports complex queries with joins, nested subqueries, aggregates, and quantifiers. It defines a probabilistic semantics that is simple and easy to understand, but requires careful handling of correlations between tuples. The paper also presents a safe-plan optimization algorithm that finds a query plan where extensional evaluation is correct. This algorithm works by first attempting to perform safe projections late in the query plan, and if not possible, splitting the query into parts that can be safely joined. The algorithm is proven to be sound, ensuring that any plan it returns is safe. It is also shown to be complete, meaning it can find a safe plan for any safe query. The algorithm is applied to a probabilistic database example, demonstrating how it can correctly evaluate queries with uncertain predicates.This paper presents a framework for evaluating complex SQL queries with uncertain predicates on probabilistic databases. The framework uses a probabilistic model to rank query results, similar to information retrieval. The main focus is on query evaluation, where an optimization algorithm is described to efficiently compute most queries. However, it is shown that some queries are #P-complete, implying they cannot be evaluated efficiently. For these queries, approximation and Monte-Carlo simulation algorithms are proposed. The paper discusses the challenges of evaluating probabilistic queries, particularly the issue of correlated probabilities in intermediate results. It introduces an approach that rewrites query plans to ensure correct evaluation. The framework supports complex queries with joins, nested subqueries, aggregates, and quantifiers. It defines a probabilistic semantics that is simple and easy to understand, but requires careful handling of correlations between tuples. The paper also presents a safe-plan optimization algorithm that finds a query plan where extensional evaluation is correct. This algorithm works by first attempting to perform safe projections late in the query plan, and if not possible, splitting the query into parts that can be safely joined. The algorithm is proven to be sound, ensuring that any plan it returns is safe. It is also shown to be complete, meaning it can find a safe plan for any safe query. The algorithm is applied to a probabilistic database example, demonstrating how it can correctly evaluate queries with uncertain predicates.