Processing relational database problems using analog processors

• US 7,870,087 B2
• Filed: 10/31/2007
• Issued: 01/11/2011
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: D-Wave Systems Inc. (D-Wave Quantum, Inc.)
• Original Assignee: D-Wave Systems Inc. (D-Wave Quantum, Inc.)
• Inventors: Sham, Ivan King Yu, Macready, William G., Coury, Michael D.
• Primary Examiner(s): HOLMES, MICHAEL B
• Application Number:
  US11/932,261
• Publication Number:
  US 20080116449A1
• Time in Patent Office: 1,168 Days
• Field of Search: 706/62
• US Class Current: 706/62
• CPC Class Codes: B82Y 10/00 Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena

Abstract

Systems, methods and articles solve queries or database problems through the use of graphs. An association graph may be formed based on a query graph and a database graph. The association graph may be solved for a clique, providing the results to a query or problem and/or an indication of a level of responsiveness of the results. Thus, unlimited relaxation of constraint may be achieved. Analog processors such as quantum processors may be used to solve for the clique.

Claims

1. A method of obtaining answers to database queries, the method comprising:

determining a query graph representative of a query;

determining an association graph based on the query graph and based on a database graph, the database graph representative of at least a portion of information stored in a database; and

evolving an analog processor to a final state representative of a clique of the association graph.

2. The method of claim 1 wherein the clique of the association graph is a maximum clique.

3. The method of claim 1 wherein evolving an analog processor to a final state representative of a clique of the association graph includes evolving a quantum processor into which the association graph has been embedded.

4. The method of claim 1 wherein determining a query graph representative of a query includes converting a number of elements of information into a number of labeled nodes of a graph, and converting a number of relations between the elements of information into a number of labeled edges between pairs of nodes of the graph.

5. The method of claim 4 wherein converting a number of relations between the elements of information into a number of labeled edges between pairs of the nodes of the graph includes converting the number of relations between the elements of information into a number of directed edges between pairs of nodes of the graph.

6. The method of claim 1 wherein determining an association graph based on the query graph and based on a database graph includes, for all of a number of pairwise combinations of association vertices in the association graph, forming an edge between the association vertices in the association graph only if a respective pair of vertices in the query graph that the association vertices represent a same relation as a pair of vertices in the database graph that the association vertices represent.

7. The method of claim 1 wherein determining a query graph includes determining a query graph for an over-constrained query.

8. The method of claim 1 wherein the portion of information stored in the database is representative of at least two possible responses to the query.

9. The method of claim 8 wherein evolving the analog processor to a final state representative of a clique of the association graph includes evolving the analog processor a plurality of times to a plurality of final states, each final state representative of a maximal clique of the association graph.

10. The method of claim 9, further comprising:

ranking the plurality of final states according to a relative responsiveness of the clique associated with each final state.

11. The method of claim 1, further comprising:

providing a number of responses to the query in a ranked order based on a determined clique of the association graph.

12. The method of claim 1, further comprising:

determining the database graph from a database.

13. The method of claim 12 wherein determining the database graph from a database includes forming the database graph from only a portion of the database.

14. A method of solving database queries, the method comprising:

determining a query graph representative of a query, the query graph including a number of nodes and a number of edges between pairs of nodes;

determining an association graph based on the query graph and based on a database graph, the database graph representative of at least a portion of information stored in a database of information that does not represent three-dimensional geometry; and

determining a clique of the association graph.

15. The method of claim 14 wherein the clique of the association graph is a maximum clique.

16. The method of claim 14 wherein determining a clique of the association graph includes evolving an analog processor.

17. The method of claim 14 wherein determining a clique of the association graph includes evolving a quantum processor into which the association graph has been embedded.

18. The method of claim 14 wherein determining a query graph representative of a query includes converting a number of elements of information into a number of labeled nodes of a graph, and converting a number of relations between the elements of information into a number of labeled edges between pairs of nodes of the graph.

19. The method of claim 18 wherein converting a number of relations between the elements of information into a number of labeled edges between pairs of nodes of the graph includes converting the number of relations between the elements of information into a number of directed edges between pairs of the nodes of the graph.

20. The method of claim 14 wherein determining an association graph based on the query graph and based on a database graph includes, for all of a number of pairwise combinations of association vertices in the association graph, forming an edge between the association vertices in the association graph only if a respective pair of vertices in the query graph that the association vertices represent a same relation as a pair of vertices in the database graph that the association vertices represent.

21. The method of claim 14 wherein determining a query graph includes determining a query graph for an over-constrained query.

22. The method of claim 14 wherein the portion of information stored in the database is representative of at least two possible responses to the query.

23. The method of claim 14, further comprising:

determining the database graph from a database.

24. The method of claim 23 wherein determining the database graph from a database includes forming the database graph from only a portion of the database.

25. A system operable to solve database queries, the system comprising:

at least one processor operable to execute instructions;

at least one computer-readable medium storing instructions that cause the at least one processor to determine a query graph representative of a query and to determine an association graph based on the query graph and based on a database graph, the database graph representative of at least a portion of information stored in a database;

an analog processor operable to evolve to a final state representative of a clique of the association graph; and

a controller subsystem operable to embed the association graph into the analog processor.

26. The system of claim 25 wherein the analog processor includes a quantum processor including a plurality of qubits and a plurality of coupling devices coupling respective pairs of qubits and which is capable of natural physical evolution.

27. The system of claim 26 wherein the controller subsystem is operable to set parameters of at least some of the qubits and the coupling devices.

28. The system of claim 25, further comprising:

a storage device storing the database.

29. The system of claim 28 wherein the database stores information that does not represent three-dimensional geometry.

30. The system of claim 25, further comprising:

at least one of a server, a scheduler or a meta-optimizer.

31. A system operable to solve database queries, the system comprising:

at least one processor operable to execute instructions; and

at least one computer-readable medium storing instructions that cause the at least one processor to determine a query graph representative of a query, determine an association graph based on the query graph and based on a database graph, the database graph representative of at least a portion of information stored in a database of information that does not represent three-dimensional geometry, and determine a clique of the association graph.

32. The system of claim 31 wherein the at least one processor includes an analog processor operable to evolve to a final state representative of the clique of the association graph.

33. The system of claim 32 wherein the analog processor includes a quantum processor including a plurality of qubits and a plurality of coupling devices coupling respective pairs of qubits and wherein the quantum processor is capable of natural physical evolution, the system further comprising:

a controller subsystem operable to set parameters of at least some of the qubits and coupling devices.

34. The system of claim 32 wherein the at least one processor includes a digital processor operable to determine the query graph by converting a number of elements of information into a number of labeled nodes of a graph, and converting a number of relations between the elements of information into a number of labeled edges between pairs of nodes of the graph.

35. The system of claim 32 wherein the at least one processor includes a digital processor operable to determine the association graph by:

for all of a number of pairwise combinations of association vertices in the association graph, forming an edge between the association vertices in the association graph only if a respective pair of vertices in the query graph that the association vertices represent a same relation as a pair of vertices in the database graph that the association vertices represent.

36. The system of claim 32 wherein the portion of information stored in the database is representative of at least two possible responses to the query.

37. The system of claim 32 wherein the at least one processor includes at least one analog processor and the system further comprises:

a controller subsystem operable to embed the association graph into the at least one analog processor.

38. A method of converting a database including at least one n-arity relation, where n is greater than 2, into a labeled database pseudograph, the method comprising:

for each n-arity relation,

aggregating a set of attributes which uniquely identify a tuple into a single compound attribute; and

generating a respective table in the database for each of the attributes that is not a key such that each table in the database represents a 2-arity or less-arity relation;

identifying each element in a set of elements for each of the tables representing a 2-arity or less-arity relation with a respective vertex in the pseudograph;

for each 1-arity relation, adding a loop to the respective vertex; and

for each 2-arity relation, adding an edge between a respective pair of vertices.

39. The method of claim 38 wherein generating a respective table in the database for each of the attributes that is not a key such that each table in the database represents a 2-arity or less-arity relation includes generating a 2-arity table consisting of a compound attribute and an attribute that is not part of the compound attribute.

40. A computer-readable medium that stores instructions for causing at least one processor to convert a database including at least one n-arity relation, where n is greater than 2, into a labeled database pseudograph, by:

for each n-arity relation,

aggregating a set of attributes which uniquely identify a tuple into a single compound attribute; and

generating a respective table in the database for each of the attributes that is not a key such that each table in the database represents a 2-arity or less-arity relation;

identifying each element in a set of elements for each of the tables representing a 2-arity or less-arity relation with a respective vertex in the pseudograph;

for each 1-arity relation, adding a loop to the respective vertex; and

for each 2-arity relation, adding an edge between a respective pair of vertices.

41. The computer-readable medium of claim 40 wherein generating a respective table in the database for each of the attributes that is not a key such that each table in the database represents a 2-arity or less-arity relation includes generating a 2-arity table consisting of a compound attribute and an attribute that is not part of the compound attribute.

42. A method of converting a database including at least one n-arity relation, where n is greater than 2, into a labeled database pseudograph, the method comprising:

for each of a number of tables having a key and multiple attributes, splitting the table into a set of tables each consisting of a key and a single attribute;

identifying each element in a set of elements for each of the tables representing a 2-arity or less-arity relation with a respective vertex in the pseudograph;

for each 1-arity relation, adding a loop to the respective vertex; and

for each 2-arity relation, adding an edge between a respective pair of vertices.

43. A computer-readable medium that stores instructions for causing at least one processor to convert a database including at least one n-arity relation into a labeled database pseudograph, where n is greater than 2, by:

for each of a number of tables having a key and multiple attributes, splitting the table into a set of tables each consisting of a key and a single attribute;

identifying each element in a set of elements for each of the tables representing a 2-arity or less-arity relation with a respective vertex in the pseudograph;

for each 1-arity relation, adding a loop to the respective vertex; and

for each 2-arity relation, adding an edge between a respective pair of vertices.

44. A system to process queries of databases, the system comprising:

an analog processor;

a conversion subsystem that receives a problem and parses the problem into subproblems suitable for processing by the analog processor; and

a controller subsystem that receives the subproblems and is operable to set at least one parameter of the analog processor to embed the subproblems into the analog processor.

45. The system of claim 44 wherein the analog processor includes a quantum processor including a plurality of qubits and a plurality of coupling devices coupling respective pairs of qubits, the quantum processor being capable of natural physical evolution and wherein the controller subsystem is operable to set parameters of at least some of the qubits and the coupling devices.

46. The system of claim 44 wherein the conversion subsystem includes a server configured to receive the problem and to provide at least one answer to the problem based on the processing of the subproblems by the analog processor.

47. The system of claim 46 wherein the server is configured to receive multiple problems and the conversion subsystem further includes a scheduler configured to schedule the received problems for processing by the analog processor.

48. The system of claim 44 wherein the conversion subsystem includes a meta-optimizer configured to facilitate the parsing of the problem into subproblems.

49. The system of claim 44 wherein the conversion subsystem is further operable to convert an output parameter of the analog processor into a respective subanswer of a respective subproblem.

50. The system of claim 49 wherein the conversion subsystem is further operable to determine whether the subanswer is valid, and to resubmit the subproblem if the subanswer is determined to be invalid.

51. The system of claim 50 wherein the conversion subsystem is further operable to determine whether all subproblems have valid subanswers, and to combine a plurality of subanswers to the subproblems into an answer to the problem if all of the subproblems have valid subanswers.

52. The system of claim 51 wherein the conversion subsystem is further operable to determine whether the answer to the problem is adequate, and to resubmit the problem if the answer is determined to be inadequate.

53. The system of claim 52 wherein the conversion subsystem is further operable to determine if a subsequent answer to the problem is better than a previous answer to the problem, and to store the subsequent answer if the subsequent answer is determined to be better than the previous answer.

54. The system of claim 44 wherein the conversion subsystem is further operable to combine a plurality of subanswers to the subproblems into an answer to the problem.

55. The system of claim 44, further comprising:

a memory storing a set of instructions to interface with an end user application.

56. The system of claim 55 wherein the memory is local with respect to the conversion subsystem.

57. The system of claim 55 wherein the memory is local with respect to the end user application.

58. The system of claim 44, further comprising:

a memory storing a database which is subject to queries.

59. A method of processing queries of databases, the method comprising:

receiving a problem;

parsing the problem into subproblems of suitable size to be processed by an analog processor;

for each of the subproblems,

setting a number of parameters of the analog processor to embed the subproblem into the analog processor;

determining a subanswer to the subproblem from a final state of the analog processor.

60. The method of claim 59 wherein the analog processor includes at least one quantum processor including a plurality of qubits and a plurality of coupling devices coupling respective pairs of qubits, the at least one quantum processor capable of evolving to the final state, and wherein setting a number of parameters of the analog processor to embed the subproblem into the analog processor includes setting parameters of at least some of the qubits and the coupling devices.

61. The method of claim 60, further comprising:

evolving the quantum processor to the final state.

62. The method of claim 59, further comprising:

scheduling the received problem for processing by the analog processor.

63. The method of claim 59 wherein parsing the problem into subproblems of suitable size to be processed by the analog processor includes optimizing the subproblems for processing on the analog processor.

64. The method of claim 59, further comprising:

converting parameters of the analog processor into subanswers to the subproblems.

65. The method of claim 59, further comprising:

determining whether at least one of a number of subanswers is valid or invalid; and

resubmitting a respective subproblem if the respective subanswer is determined to be invalid.

66. The method of claim 59, further comprising:

determining whether all subproblems have a respective subanswer; and

combining the subanswers to the subproblems into an answer to the problem if all of the subproblems have subanswers.

67. The method of claim 59, further comprising:

determining whether an answer to a problem is adequate; and

resubmitting the problem for processing by the analog processor if the answer is determined to be inadequate.

68. The method of claim 59, further comprising:

determining if an answer to the problem is better than a previous answer to the problem; and

storing the answer if the answer is determined to be better than the previous answer to the problem.

69. The method of claim 59 further comprising:

converting a problem from an end user application format into a generalized format.