METHOD AND APPARATUS FOR FACILITATING ANSWERING A QUERY ON A DATABASE

• US 20130124502A1
• Filed: 11/16/2011
• Published: 05/16/2013
• Est. Priority Date: 11/16/2011
• Status: Active Grant

• Current Assignee: NeuStar IP Intelligence, Inc. (Neustar Incorporated)
• Original Assignee: Quova Inc. (Neustar Incorporated)
• Inventors: Prieditis, Armand Erik
• Granted Patent: US 8,965,934 B2
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/245 Query processing

Abstract

A method and apparatus for facilitating answering a query on a database. Example embodiments include: accessing a database tree having a plurality of nodes; 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 a traversal cost based on the node and the set of input variable values; determining a lower bound 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; 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.

Claims

1. A method comprising:

accessing a database tree having a plurality of nodes;

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 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;

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 database tree is a probabilistic tree.

8. 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.

9. 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; 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 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;

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.

10. The system of claim 9 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.

11. The system of claim 9 wherein the node is not a leaf node.

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

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

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

15. The system of claim 9 wherein the database tree is a probabilistic tree.

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

17. 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;

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 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;

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.

18. The article of manufacture of claim 17 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.

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

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