Processing diff-queries on property graphs

Abstract

A system, computer-implemented method, and a computer-readable medium for determining why a query returns a null set in a database management system. When the database management system receives a query graph, database management system compares the query graph to the data graph. Based on the comparison, database management system identifies a discovered component of the query graph and a missing component of the query graph, wherein the missing query component indicates a reason for the null set.

What is claimed is: 
     
       1. A computer-implemented method comprising:
 accessing a data graph stored in memory of a database management system, wherein the data graph comprises a first plurality of vertices; 
 receiving a query graph, wherein the query graph comprises a second plurality of vertices, and wherein the query graph causes the database management system to retrieve data from the data graph as specified in the query graph; 
 executing in the database management system, the query graph against the data graph stored in the memory, wherein the execution generates an empty data set indicating data specified in the query graph does not exist in the data graph when the data specified in the query graph exists in the data graph; and 
 based on the empty data set, generating a discovered component and a missing component of the query graph, wherein the discovered component includes a first vertex from the first and second plurality of vertices, and the missing component includes a second vertex from the second plurality of vertices that causes the database management system to generate the empty data set when executing the query graph. 
 
     
     
       2. The computer-implemented method of  claim 1 , further comprising:
 receiving a query specifying the data in the data graph; and 
 converting the query into the query graph. 
 
     
     
       3. The computer-implemented method of  claim 1 , wherein the generating further comprises:
 generating a maximum common sub-graph between the query graph and the data graph, wherein the maximum common sub-graph includes a maximum number of vertices that are common to the first and second plurality of vertices and wherein the maximum common sub-graph is the discovered component of the query graph. 
 
     
     
       4. The computer-implemented method of  claim 3 , wherein the generating further comprises:
 generating a difference graph between the maximum common sub-graph and the query graph, wherein the difference graph indicates the missing component of the query graph. 
 
     
     
       5. The computer-implemented method of  claim 4 , further comprising:
 adding one of the vertices in the maximum common sub-graph to the difference graph, wherein the one of the vertices is associated with an edge that is included in the difference graph. 
 
     
     
       6. The computer-implemented method of  claim 3 , wherein generating the maximum common sub-graph further comprises:
 generating a list of maximum common sub-graphs, wherein the list includes a first maximum common sub-graph generated using the first vertex of the second plurality of vertices in the query graph and a second maximum common sub-graph generated using a third vertex of the second plurality of vertices; and 
 selecting the maximum common sub-graph from the list. 
 
     
     
       7. The computer-implemented method of  claim 1 , wherein the data graph is a property graph and the database management system includes a column-based graph database. 
     
     
       8. The computer-implemented method of  claim 7 , wherein the property graph is represented as a set of tables including a first plurality of vertices and a plurality of edges in the property graph. 
     
     
       9. A system, comprising:
 a memory configured to store a data graph of a database management system, wherein the data graph comprises a first plurality of vertices; and 
 one or more processors coupled to the memory and operable to:
 receive a query graph, wherein the query graph comprises a second plurality of vertices, and wherein the query graph causes the one or more processors of the database management system to retrieve data from the data graph as specified in the query graph; 
 execute the query graph against the data graph stored in the memory, wherein the execution generates an empty data set indicating data specified in the query graph does not exist in the data graph when the data specified in the query graph exists in the data graph; and 
 based on the empty data set, generating a discovered component and a missing component of the query graph, wherein the discovered component includes a first vertex from the first and second plurality of vertices, and the missing component includes a second vertex from the second plurality of vertices that causes the one or more processors to generate the empty data set when executing the query graph. 
 
 
     
     
       10. The system of  claim 9 , wherein the one or more processors are further configured to:
 receive a query specifying the data in the data graph; and 
 convert the query into the query graph. 
 
     
     
       11. The system of  claim 9 , wherein to generate the discovered component the one or more processors are further configured to:
 generate a maximum common sub-graph between the query graph and the data graph, wherein the maximum common sub-graph includes a maximum number of vertices that are common to the first and second plurality of vertices and wherein the maximum common sub-graph is the discovered component of the query graph. 
 
     
     
       12. The system of  claim 11 , wherein to generate the missing component the one or more processors are further configured to:
 generate a difference graph between the maximum common sub-graph and the query graph, wherein the difference graph indicates the missing component of the query graph. 
 
     
     
       13. The system of  claim 12 , wherein the one or more processors are further configured to:
 add one of the vertices from the maximum common sub-graph to the difference graph, wherein the one of the vertices is associated with an edge that is included in the difference graph. 
 
     
     
       14. The system of  claim 11 , wherein to generate the maximum common sub-graph the one or more processors are further configured to:
 generate a list of maximum common sub-graphs, wherein the list includes a first maximum common sub-graph generated using the first vertex of the second plurality of vertices in the query graph and a second maximum common sub-graph generated using a third vertex of the second plurality of vertices in; and 
 select the maximum common sub-graph from the list. 
 
     
     
       15. The system of  claim 9 , wherein the data graph is a property graph and the database management system includes a column-based graph database. 
     
     
       16. The system of  claim 15 , wherein the property graph is represented as a set of tables including a first plurality of vertices and a plurality of edges in the property graph. 
     
     
       17. A computer-readable medium having instructions stored thereon, that when executed by a computing device, causes the computing device to perform operations, the operations comprising:
 accessing a data graph stored in memory of a database management system, wherein the data graph comprises a first plurality of vertices; 
 receiving a query graph, wherein the query graph comprises a second plurality of vertices, and wherein the query graph causes the database management system to retrieve data from the data graph as specified in the query graph; 
 executing in the database management system, the query graph against the data graph stored in the memory, wherein the execution generates an empty data set the query graph does not exist in the data graph when the data specified in the query graph exists in the data graph; and 
 based on the empty data set, generating a discovered component and a missing component of the query graph, wherein the discovered component includes a first vertex from the first and second plurality of vertices and the missing component includes a second vertex from the second plurality of vertices that causes the database management system to generate the empty data set when executing the query graph. 
 
     
     
       18. The computer-readable medium of  claim 17 , further comprising:
 receiving a query specifying the data in the data graph; and 
 converting the query into the query graph. 
 
     
     
       19. The computer-readable medium of  claim 17 , wherein to generate the discovered component the computing device further performs operations, the operations comprising:
 generating a maximum common sub-graph between the query graph and the data graph, wherein the maximum common sub-graph includes a maximum number of vertices that are common to the first and second plurality of vertices and wherein the maximum common sub-graph is the discovered component of the query graph. 
 
     
     
       20. The computer-readable medium of  claim 17 , wherein to generate the missing component the one or more processors are further configured to:
 generate a difference graph between the maximum common sub-graph and the query graph, wherein the difference graph indicates the missing component of the query graph.