Patent ID: 7363299

Claim:
A method for determining a result for a query of data in a probabilistic database, wherein elements of the data are each associated with a probability, a result for the query including a probability for each answer of the result to indicate a relative likelihood that the answer satisfies the query, comprising the steps of: (a) determining if a safe extensional plan defining an order for operators employed in the query can be identified, wherein for conjunctive queries q, q′ that include any union operator, any difference operator, or any group-by-aggregate operator: (i) a selection operator, σ c e , which returns a probability, is always safe in σ c (q); (ii) a join operator, x e , is always safe in q×q′; and (iii) where A 1 , . . . , A k are attributes of relations in q, a project operator Π A 1 , . . . , A k e is safe in Π A 1 , . . . , A k (q) if and only if, for every probabilistic relation, R p , which is an element of probabilistic relation names occurring in q for said attributes, as denoted by R p εPRels(q), A 1 , . . . , A k , a probabilistic event yielding head attributes, as indicated by R p .E→Head(q), can correctly be inferred from a set of induced functional dependencies on q, indicated by Γ p (q); and (1) if a safe extensional plan can be identified, employing the safe extensional plan to evaluate the query and determine the result that includes a correct probability for each potential answer within the data; and (2) if a safe extensional plan cannot be identified, selecting an alternative plan that will produce the result with an acceptable error in the probability for each potential answer within the data, and employing the alternative plan to produce the result; and (b) providing the result to a user.