Multi-entity normalization

• US 9,613,070 B2
• Filed: 03/15/2013
• Issued: 04/04/2017
• 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
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US13/842,072
• Publication Number:
  US 20140280130A1
• Time in Patent Office: 1,481 Days
• Field of Search: 707999102, 707E17005, 707999104, 707999001, 707999002, 707736, 707758, 707705, 707802, 707749, 707791, 707737, 707740, 707728, 707756, 707822, 707E17001, 707E17045, 707798, 707726
• 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, from a plurality of data providers, data representing entities and relationships linking the entities;

defining, a plurality of graph rules defined in a graph model, the graph rules including one or more graph patterns associated with the graph model, the graph model specifying how the data is expected to be patterned and interrelated;

searching the data representing entities and relationships linking the entities using the one or more graph patterns associated with the graph model, the searching including comparing the one or more graph patterns to a structure associated with the data;

and

in response to determining that the structure associated with the data matches at least one of the one or more graph patterns associated with the graph model, applying, in a continuous mode, the one or more graph rules by selecting an anchor entity and performing a graph walk from the anchor entity to determine violations to one or more of the graph rules, and correcting the data and the structure of the data, the correcting including updating the data representing the entities and relationships linking the entities that violate one or more of the plurality of graph rules.

2. The method of claim 1, further comprising automatically correcting one or more attributes associated with the data based on correcting the structure of the data.

3. The method of claim 1, further comprising validating the structure of the data using graph-based pattern matching across multiple entities in the data.

4. The method of claim 3, wherein the graph-based pattern matching includes using a generic pattern that applies to data values of applications associated with the entities and relationships linking the entities to correct the data.

5. The method of claim 1, wherein correcting the data and the structure of the data includes modifying the structure to adhere to a valid pattern defined in the graph rules and correcting the data to be modeled to the valid pattern.

6. The method of claim 1, further comprising:

detecting that the structure is incomplete;

generating and presenting, to a user, a notification about the incomplete structure; and

completing the structure based on at least one graph pattern in the plurality of graph rules.

7. A computer 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 configured to define a plurality of graph rules describing searchable characteristics for the data representing the entities and the relationships linking the entities, the searchable characteristics defining one or more patterns that specify how entities and relationships linking the entities are expected to be modeled and interrelated;

a rule application module configured to apply, in a continuous mode, the plurality of graph rules to ensure one or more sets of entities and the relationships linking the entities satisfy the plurality of graph rules including comparing the one or more patterns to a structure associated with the data representing entities and relationships linking the entities to determine whether the one or more patterns match the structure associated with the data representing the entities and relationships linking the entities; and

a rule action module configured to perform one or more actions on the data and on the structure associated with the one or more sets of entities and the relationships linking the entities, the actions being performed to update the data representing the entities and relationships linking the entities that violate one or more of the plurality of graph rules, the update including cleaning the data by performing at least one of modifying one or more relationships linking the entities, wherein the update is performed in response to determining that the structure matches at least one of the one or more patterns.

8. The system of claim 7, wherein the one or more actions further comprise automatically completing the incomplete structure.

9. The system of claim 7, wherein determining whether the structure associated with the data matches at least one of the one or more patterns further includes matching a pattern associated with the graph rules to the at least one structure;

and

in response to determining that the at least one structure does not match the pattern, generating and presenting, to a user, a notification regarding a violation of one or more graph rules.

10. The system of claim 7, wherein the one or more graph rules describing searchable characteristics include describing at least one semantic property related to the data representing the entities and the relationships linking the entities.

11. The system of claim 7, wherein the one or more graph rules describing searchable characteristics include specifying at least one of an inclusion dependency and an exclusion dependency related to the data representing the entities and the relationships linking the entities.

12. The system of claim 7, wherein the actions include automatically correcting the structure and the one or more sets of entities and the relationships linking the entities.

13. The system of claim 7, wherein:

the rule application module is further configured to identify one or more discrepancies between the one or more graph rules and the structure associated with the entities and the relationships linking the entities, detect that at least one of the entities and the relationships linking the entities is incomplete; and

the rule action module is further configured to perform one or more actions to mitigate the one or more discrepancies, the one or more actions including generating and presenting, to a user, a notification about the incomplete entities and the relationships linking the entities.

14. The system of claim 13, wherein identifying one or more discrepancies includes at least one of flagging and logging the one or more discrepancies as exceptions for analysis.

15. The system of claim 7, wherein performing the one or more actions to update the one or more sets of entities and the relationships linking the entities includes modifying one or more entities, generating one or more additional entities, and generating one or more additional relationships linking the entities.

16. A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable medium and comprising instructions that, when executed by at least one processor, are configured to:

retrieving, from a plurality of data providers, data representing entities and relationships linking the entities;

defining, a plurality of graph rules defined in a graph model, the graph rules including one or more graph patterns associated with the graph model, the graph model specifying how the data is expected to be patterned and interrelated;

searching the data representing entities and relationships linking the entities using the one or more graph patterns associated with the graph model, the searching including comparing the one or more graph patterns to a structure associated with the data;

and

in response to determining that the structure associated with the data matches at least one of the one or more graph patterns associated with the graph model, applying, in a continuous mode, the one or more graph rules by selecting an anchor entity and performing a graph walk from the anchor entity to determine violations to one or more of the graph rules and correcting the data and the structure of the data, the correcting including updating the data representing the entities and relationships linking the entities that violate one or more of the plurality of graph rules.

17. The computer program product of claim 16, further comprising validating the structure of the data using graph-based pattern matching across multiple entities in the data.

18. The computer program product of claim 16, further comprising:

detecting that the structure is incomplete;

generating and presenting, to a user, a notification about the incomplete structure; and

correcting the incomplete structure based on at least one graph pattern in the plurality of graph rules.