A system that supports arbitrarily complex SQL queries with "uncertain" predicates. The query semantics are based on a probabilistic model and the results are ranked, much like in Information Retrieval, based upon their probability. An optimization algorithm is employed that can efficiently compute most queries. The algorithm attempts to determine whether a proposed plan is a safe plan that can be used for correctly evaluating the query. Operators such as the project operator in the proposed plan are evaluated to determine if they are safe. If so, the proposed plan is safe and will produce correct answers in a result. Due to the data complexity of some queries, a safe plan may not exist for a query. For these queries, either a "least unsafe plan," or a Monte-Carlo simulation algorithm can be employed to produce a result with answers that have an acceptable error.