Multi-entity normalization

• US 10,324,912 B2
• Filed: 02/17/2017
• Issued: 06/18/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: Kumar, Ajoy, Mueller, Douglas, George, Josie
• Primary Examiner(s): Beausoliel, Jr., Robert W
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US15/436,144
• Publication Number:
  US 20170228403A1
• Time in Patent Office: 851 Days
• Field of Search: 707722, 707737, 707736, 707705
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

In accordance with aspects of the disclosure, systems and methods are provided for normalizing data representing entities and relationships linking the entities including defining one or more graph rules describing searchable characteristics for the data representing the entities and relationships linking the entities, applying the one or more graph rules to the data representing the entities and the relationships linking the entities, identifying one or more matching instances between the one or more graph rules and the data representing the entities and the relationships linking the entities, and performing one or more actions to update the one or more matching instances between the one or more graph rules and the data representing the entities and the relationships linking the entities.

Claims

1. A computer-implemented method, comprising:

retrieving data from a plurality of data providers, wherein the data represents entities and relationships between the entities;

defining a plurality of graph rules for a graph model, the graph model defining a plurality of data patterns and the relationships between the entities;

searching the data using the plurality of graph rules, the searching including comparing the plurality of data patterns in the graph rules to a structure associated with the data;

in response to determining that at least a portion of the structure associated with the data matches at least one of the plurality of data patterns in the graph rules, assessing whether the data includes missing relationships between the entities that result in a violation of at least one of the plurality of graph rules; and

in response to determining that the data includes missing relationships between at least two of the entities, correcting, using the at least one graph rule, the missing relationships in the structure to generate corrected data and corrected structure of the data,

wherein the correcting includes automatic correction of the graph model and generation of at least one additional relationship linking the at least two entities based on the portion of the structure matching at least one of the plurality of data patterns.

2. The method of claim 1, wherein correcting the data and the structure of the data includes performing graph based pattern matching to correct one or more discrepancies between one or more of the plurality of graph rules and the data.

3. The method of claim 1, further comprising:

converting one or more of the graph rules into a plurality of graph queries; and

applying the plurality of graph queries to the structure associated with the data to determine whether the data is patterned according to one or more of the graph rules.

4. The method of claim 3, wherein converting one or more of the graph rules into a plurality of graph queries includes generating a plurality of structured query language (SQL) queries using one or more of the graph rules, the plurality of the SQL queries being executed on the structure of the data to determine one or more violations of one or more of the graph rules.

5. The method of claim 3, wherein the plurality of graph queries are executed in a batch mode using a plurality of bulk queries to determine one or more violations of the plurality of graph rules.

6. The method of claim 1, wherein correcting the data and the structure of the data includes modifying the structure to adhere to at least one valid pattern defined in at least one of the plurality of graph rules and correcting the data by modifying the data to model the at least one valid pattern.

7. The method of claim 1, wherein correcting the data and the structure of the data includes adjusting one or more attributes related to the data determined to violate one or more of the plurality of graph rules.

8. A computer program product including instructions recorded on a non-transitory computer-readable storage medium and comprising instructions that, when executed by at least one processor, cause the at least one processor to:

retrieve data from a plurality of data providers, wherein the data represents entities and relationships between the entities;

define a plurality of graph rules for a graph model, the graph model defining a plurality of data patterns and the relationships between the entities;

search the data using the plurality of graph rules, the searching including comparing the plurality of data patterns in the graph rules to a structure associated with the data;

in response to determining that at least a portion of the structure associated with the data matches at least one of the plurality of data patterns in the graph rules, assessing whether the data includes missing relationships between the entities that result in a violation of at least one of the plurality of graph rules; and

in response to determining that the data includes missing relationships between at least two of the entities, correcting, using the at least one graph rule, the missing relationships in the structure to generate corrected data and corrected structure of the data,

wherein the correcting includes automatic correction of the graph model and generation of at least one additional relationship linking the at least two entities based on the portion of the structure matching at least one of the plurality of data patterns.

9. The computer program product of claim 8, wherein the at least one processor is further configured to:

convert one or more of the graph rules into a plurality of graph queries; and

apply the plurality of graph queries to the structure associated with the data to determine whether the data is patterned according to one or more of the graph rules.

10. The computer program product of claim 9, wherein converting the one or more of the graph rules into a plurality of graph queries includes generating a plurality of structured query language (SQL) queries using one or more of the graph rules, the plurality of the SQL queries being executed on the structure of the data to determine one or more violations of one or more of the graph rules.

11. The computer program product of claim 9, wherein the plurality of graph queries are executed in a batch mode using a plurality of bulk queries to determine one or more violations of the plurality of graph rules.

12. The computer program product of claim 8, wherein correcting the data and the structure of the data includes modifying the structure to adhere to at least one valid pattern defined in at least one of the plurality of graph rules and correcting the data by modifying the data to model the at least one valid pattern.

13. The computer program product of claim 8, wherein correcting the data and the structure of the data includes adjusting one or more attributes related to the data determined to violate one or more of the plurality of graph rules.

14. A computer implemented system including instructions recorded on a non-transitory computer-readable medium and executable by at least one processor, the system comprising:

a normalization engine configured to cause the at least one processor to validate and clean data representing entities and relationships linking the entities, the normalization engine including;

a rule definition module to define a plurality of graph rules based on a graph model describing searchable characteristics of a plurality of data patterns that specify how entities and relationships linking the entities are interrelated;

a rule application module to search the data using the plurality of graph rules, the searching including comparing one or more of the plurality of graph rules to a structure associated with the data and responsive to determining that at least a portion of the structure associated with the data matches at least one data pattern in the plurality of data patterns, assessing whether the data includes missing relationships between the entities that result in a violation of at least one of the plurality of graph rules; and

a rule action module to generate an indication to correct the data, the structure of the data, and the graph model in response to determining that the data violates one or more of the plurality of graph rules based on the determined missing relationships and to correct the missing relationships,

wherein the graph model is automatically corrected based on the portion of the structure matching the at least one data pattern.

15. The system of claim 14, wherein the rule action module is further operable to clean the data by modifying the structure of the data to conform to one or more of the plurality of graph rules.

16. The system of claim 14, wherein the rule application module is further operable to correct the data and the structure of the data that violates one or more of the plurality of graph rules, the correcting including performing graph based pattern matching to update the data and the structure of the data determined to violate one or more of the plurality of graph rules.

17. The system of claim 14, wherein correcting the data and the structure of the data includes modifying the structure to adhere to at least one valid pattern defined in at least one of the plurality of graph rules and correcting the data by modifying the data to model the at least one valid pattern.

18. The system of claim 14, wherein the rule action module is further operable to:

convert one or more of the graph rules into a plurality of graph queries by generating a plurality of structured query language (SQL) queries using one or more of the graph rules; and

execute the plurality of SQL queries on the structure associated with the data to determine one or more violations of the one or more graph rules.

19. The system of claim 18, wherein the plurality of graph queries are executed in a batch mode using a plurality of bulk queries to determine one or more violations of one or more of the graph rules.

20. The system of claim 18, wherein the rule application module is further operable to apply the plurality of graph queries to the structure in a batch mode to determine one or more violations of the one or more graph rules.