The paper introduces a framework for supporting complex SQL queries with uncertain predicates, using a probabilistic model to define query semantics. The main focus is on efficient query evaluation, with an optimization algorithm that can compute results for most queries. However, the data complexity of some queries is #P-complete, indicating that they do not admit efficient evaluation methods. For these queries, the paper describes both an approximation algorithm and a Monte-Carlo simulation algorithm. The introduction highlights the differences between databases and Information Retrieval (IR) in terms of query structure and semantics. Databases require precise knowledge to formulate complex queries, while IR queries are simpler and more flexible, offering ranked results and uncertain matches. The paper proposes a system that combines these features, allowing for structurally rich SQL queries with uncertain predicates and ranked results. The paper defines probabilistic databases and possible worlds semantics, explaining how to compute the probability of each tuple in the database. It discusses the limitations of extensional evaluation, which can lead to incorrect results due to correlated probabilities in intermediate query results. Instead, the paper proposes a safe-plan optimization algorithm that ensures correct probability computation by carefully selecting join orders and projection positions. The safe-plan algorithm is proven to be sound and complete, meaning it always returns a safe plan if one exists. The paper also provides examples and experimental results to illustrate the effectiveness of the proposed approach.The paper introduces a framework for supporting complex SQL queries with uncertain predicates, using a probabilistic model to define query semantics. The main focus is on efficient query evaluation, with an optimization algorithm that can compute results for most queries. However, the data complexity of some queries is #P-complete, indicating that they do not admit efficient evaluation methods. For these queries, the paper describes both an approximation algorithm and a Monte-Carlo simulation algorithm. The introduction highlights the differences between databases and Information Retrieval (IR) in terms of query structure and semantics. Databases require precise knowledge to formulate complex queries, while IR queries are simpler and more flexible, offering ranked results and uncertain matches. The paper proposes a system that combines these features, allowing for structurally rich SQL queries with uncertain predicates and ranked results. The paper defines probabilistic databases and possible worlds semantics, explaining how to compute the probability of each tuple in the database. It discusses the limitations of extensional evaluation, which can lead to incorrect results due to correlated probabilities in intermediate query results. Instead, the paper proposes a safe-plan optimization algorithm that ensures correct probability computation by carefully selecting join orders and projection positions. The safe-plan algorithm is proven to be sound and complete, meaning it always returns a safe plan if one exists. The paper also provides examples and experimental results to illustrate the effectiveness of the proposed approach.