VERIFYING CORRECTNESS IN GRAPH DATABASES

• US 20180089252A1
• Filed: 09/28/2016
• Published: 03/29/2018
• Est. Priority Date: 09/28/2016
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Long, Yejuan, Meyer, Scott M., Yang, Yiming, Vakharia, Mihir Sharad
• Application Number:
  US15/278,809
• Publication Number:
  US 20180089252A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

The disclosed embodiments provide a system that verifies correctness in a graph database. During operation, the system obtains a set of records from a source of truth for a graph database storing a graph, wherein the graph includes a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates. Next, the system uses the records to automatically generate a set of test cases containing a set of queries of the graph database. The system then transmits the queries to the graph database and receives, from the graph database, a set of query results in response to the queries. Finally, the system performs a comparison of the query results and a set of expected results of the test cases to verify a correctness of the graph database.

Claims

1. A method, comprising:

obtaining a set of records from a source of truth for a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates;

using the records to automatically generate, by one or more computer systems, a set of test cases comprising a set of queries of the graph database;

transmitting the queries to the graph database;

receiving, from the graph database, a set of query results in response to the queries; and

performing, by the one or more computer systems, a comparison of the query results and a set of expected results of the test cases to verify a correctness of the graph database.

2. The method of claim 1, further comprising:

outputting, during the comparison, one or more test results associated with the test cases.

3. The method of claim 2, wherein the one or more test results comprise at least one of:

a missing value;

an incorrect value; and

a regression in the graph database.

4. The method of claim 1, further comprising:

generating the set of expected results from the set of records and a schema associated with the records.

5. The method of claim 4, wherein the set of expected results is further generated using a search pattern for obtaining, from a log-based representation of the graph database, a subset of the records matching a query in the set of queries.

6. The method of claim 5, wherein performing the comparison of the query results and the set of expected results comprises:

using the search pattern to obtain the subset of the records from the log-based representation; and

comparing the query results, the expected results, and the subset of the records.

7. The method of claim 1, wherein using the records to generate the set of test cases comprises:

generating, from a record in the set of records, a subset of the queries comprising permutations of unfilled parameters from the record.

8. The method of claim 1, wherein the set of results comprises:

a subject;

a predicate; and

an object.

9. The method of claim 8, wherein the predicate is associated with at least one of:

a connection;

an employment;

a group membership;

a following of a company;

a following of a member;

a skill of the member;

an education of the member at a school; and

a location of the member.

10. The method of claim 8, wherein the subject is at least one of:

a member;

a score;

a date;

an employer;

an employee;

a position;

a group;

a membership;

a follower;

a followee;

an attribute; and

a flag.

11. The method of claim 1, wherein the set of queries comprises a subset of the nodes in the graph database.

12. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a set of records from a source of truth for a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates;

use the records to automatically generate a set of test cases comprising a set of queries of the graph database;

transmit the queries to the graph database;

receive, from the graph database, a set of query results in response to the queries; and

perform a comparison of the query results and a set of expected results of the test cases to verify a correctness of the graph database.

13. The apparatus of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

output, during the comparison, one or more test results associated with the test cases.

14. The apparatus of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

generate the set of expected results from the set of records and a schema associated with the records.

15. The apparatus of claim 14, wherein the set of expected results is further generated using a search pattern for obtaining, from a log-based representation of the graph database, a subset of the records matching a query in the set of queries.

16. The apparatus of claim 15, wherein performing the comparison of the query results and the set of expected results comprises:

using the search pattern to obtain the subset of the records from the log-based representation; and

comparing the query results, the expected results, and the subset of the records.

17. The apparatus of claim 12, wherein using the records to generate the set of test cases comprises:

generating, from a record in the set of records, a subset of the queries comprising permutations of unfilled parameters from the record.

18. The apparatus of claim 12, wherein the set of results comprises:

a subject;

a predicate; and

an object.

19. A system, comprising:

a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and

a testing module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to;

obtain a set of records from a source of truth for the graph database;

use the records to automatically generate a set of test cases comprising a set of queries of the graph database;

transmit the queries to the graph database;

receive, from the graph database, a set of query results in response to the queries; and

perform a comparison of the query results and a set of expected results of the test cases to verify a correctness of the graph database.

20. The system of claim 19, further comprising:

a scanning module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to generate the expected results using a search pattern for obtaining, from a log-based representation of the graph database, a subset of the records matching a query in the set of queries.