Method and apparatus for facilitating answering a query on a database

1. A method comprising:

accessing a database tree having a plurality of nodes, the database tree being a probabilistic tree;

receiving a set of input variable values, a non-empty set of output variables, and information indicative of a node in the database tree;

determining, by use of a processor, a traversal cost based on the node and the set of input variable values;

determining, by use of the processor, a lower bound for the traversal cost based on the node and the set of input variable values, wherein the lower bound corresponds to an upper-bound probability estimate based on one or more of the plurality of nodes and the set of input variable values, wherein the upper-bound probability estimate corresponds to an upper-bound on a probability of selecting the node;

pruning one or more of the plurality of nodes based on the traversal cost, the lower bound, and a pruning bound; and

returning a result including a non-empty set of output variable values based on the set of input variable values, the node, the traversal cost, and the lower bound.

2. The method of claim 1 wherein the non-empty set of output variable values corresponds to a most likely set of non-empty output variable values based on the set of input variable values.

3. The method of claim 1 wherein the node is not a leaf node.

4. The method of claim 1 wherein the pruning bound is based on a cost of reaching at least one child node of the node.

5. The method of claim 1 wherein each of the plurality of nodes is associated with a probability distribution function corresponding to one or more rows in a database.

6. The method of claim 5 wherein the probability distribution function comprises a mean vector and a covariance matrix.

7. The method of claim 1 wherein the set of input variable values and the non-empty set of output variables correspond to a database query.

8. A system comprising:

a processor;

a database query processor interface, in data communication with the processor, to receive a database query comprising a set of input variable values, a non-empty set of output variables, and information indicative of a node in a database tree, the database tree being a probabilistic tree; and

a database query processor, in data communication with the processor, to:

access the database tree having a plurality of nodes;

determine a traversal cost based on the node and the set of input variable values;

determine a lower bound for the traversal cost based on the node and the set of input variable values, wherein the lower bound corresponds to an upper-bound probability estimate based on one or more of the plurality of nodes and the set of input variable values, wherein the upper-bound probability estimate corresponds to an upper-bound on a probability of selecting the node;

prune one or more of the plurality of nodes based on the traversal cost, the lower bound, and a pruning bound; and

return a result including a non-empty set of output variable values based on the set of input variable values, the node, the traversal cost, and the lower bound.

9. The system of claim 8 wherein the non-empty set of output variable values corresponds to a most likely set of non-empty output variable values based on the set of input variable values.

10. The system of claim 8 wherein the node is not a leaf node.

11. The system of claim 8 wherein the pruning bound is based on a cost of reaching at least one child node of the node.

12. The system of claim 8 wherein each of the plurality of nodes is associated with a probability distribution function corresponding to one or more rows in a database.

13. The system of claim 12 wherein the probability distribution function comprises a mean vector and a covariance matrix.

14. The system of claim 8 wherein the set of input variable values and the non-empty set of output variables correspond to a database query.

15. An article of manufacture comprising a non-transitory machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a machine, cause the machine to:

access a database tree having a plurality of nodes, the database tree being a probabilistic tree;

receive a set of input variable values, a non-empty set of output variables, and information indicative of a node in the database tree;

determine a traversal cost based on the node and the set of input variable values;

determine a lower bound for the traversal cost based on the node and the set of input variable values, wherein the lower bound corresponds to an upper-bound probability estimate based on one or more of the plurality of nodes and the set of input variable values, wherein the upper-bound probability estimate corresponds to an upper-bound on a probability of selecting the node;

prune one or more of the plurality of nodes based on the traversal cost, the lower bound, and a pruning bound; and

return a result including a non-empty set of output variable values based on the set of input variable values, the node, the traversal cost, and the lower bound.

16. The article of manufacture of claim 15 wherein the non-empty set of output variable values corresponds to a most likely set of non-empty output variable values based on the set of input variable values.

17. The article of manufacture of claim 15 wherein each of the plurality of nodes is associated with a probability distribution function corresponding to one or more rows in a database.

18. The article of manufacture of claim 17 wherein the probability distribution function comprises a mean vector and a covariance matrix.