External system integration into automated attribute discovery

• US 20090144319A1
• Filed: 01/14/2008
• Published: 06/04/2009
• Est. Priority Date: 11/29/2007
• Status: Abandoned Application

• Current Assignee: Abe Achkinazi, Rajendra Bhagwatisingh Panwar
• Original Assignee: Abe Achkinazi, Rajendra Bhagwatisingh Panwar
• Inventors: Achkinazi, Abe, Panwar, Rajendra Bhagwatisingh
• Application Number:
  US12/008,954
• Publication Number:
  US 20090144319A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/212 with details for data modelling support
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

Methods and apparatus to transform attribute data about assets in a source system data model into attribute data about the same assets in a target system data model. The first step is to extract the necessary attribute data from attribute data collected about inventory assets of a business entity needed to populate the attributes in objects representing those inventory assets in a target system data model. Transformation rules are written which are designed to make all conversions necessary in semantics, units of measure, etc. to transform the source system attribute data into attribute data for the target system which has the proper data format. These transformation rules are executed on a computer on the extracted attribute data and the transformed attribute data is stored in an ER model. In the preferred embodiment, the transformation rules are object-oriented in that transformation rules for subtypes can be inherited from their parent types or classes. An export adapter which is capable of invoking the application programmatic interface of the target system CMDB is then used to export the transformed attribute data stored in the ER model to the target system CMDB. A heuristic method to create self-consistent data blocks without exceeding a maximum size limit involves loading instances of entity types and all related instances in the order of decreasing connectivity metric.

Claims

1. A process to build self-consistent data blocks for a CMDB system or any other external system using a data block maximum size, comprising:

A) dividing a graph of entity types into independent groups, each group including entity types related to other entity types by parent-child relationships;

B) computing the cardinality of each relationship;

C) computing a connectivity metric for each entity type;

D) sorting the entity types into decreasing order of connectivity metric;

E) loading related instances of related entity types into one or more data blocks so as to not substantially exceed a maximum data size for each block starting with the entity type of highest connectivity metric and working downward on the sorted list of entity types generated in step D;

F) loading into said one or more data blocks any instances of entity types not related to any other entity types;

G) marking each instance which has been loaded into a data block as done; and

H) repeating steps E, F and G until all instances of all entity types of all independent groups have been loaded into one or more data blocks.

2. The process of claim 1 further comprising a step B1 comprising calculating a weighting ratio for each parent-child relationship by computing the ratio S2 divided by S1, where S2 is the data size of an instance of the child type entity in said relationship and S1 is the data size of an instance of the parent type entity, and further comprising a step B2 of multiplying said cardinality of each said relationship by said weighting ratio of said relationship so as to generate a normalized cardinality for each said relationship before computing said connectivity metric for each said entity type, and wherein step C comprises computing said connectivity metric for each entity types using said normalized cardinality for each relationship of said entity type.

3. The process of claim 1 wherein step E comprises:

I) starting with the independent group which contains the entity type with the highest connectivity metric, hereafter referred to as Tmax;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock.

4. The process of claim 2 wherein step E comprises:

I) starting with the independent group which contains the entity type with the highest connectivity metric calculated using said normalized cardinalities;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock.

5. The process of claim 2 wherein step E comprises:

I) starting with the independent group which contains the entity type with the highest connectivity metric calculated using said normalized cardinalities;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock;

P) starting with the group in which the entity type with the second highest connectivity metric resides, repeat steps J through O until all instances of said entity type with said second highest connectivity metric resides and instances related thereto at all levels of relation are loaded into a data block; and

Q) repeating processing like step P as many times as necessary for all entity types in all groups until all instances of all entity types have been loaded into one or more data blocks.

6. The process of claim 1 wherein step E comprises:

I) starting with the independent group which contains the entity type with the highest connectivity metric;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock;

P) starting with the group in which the entity type with the second highest connectivity metric resides, repeat steps J through O until all instances of said entity type with said second highest connectivity metric resides and instances related thereto at all levels of relation are loaded into a data block; and

Q) repeating processing like step P as many times as necessary for all entity types in all groups until all instances of all entity types have been loaded into one or more data blocks.

7. The process of claim 1 wherein step A comprises:

A1) adding data to relationship tables that record parent-child entity relationships between entity types in said graph so as to make the graph non-directed such that the parent entity type of any entity type may be determined from information in said relationship table;

A2) starting with any first entity on said non-directed graph, find all other entities on said graph which are either parent or child to said first entity and putting all the entities found in a first group along with their relationships;

A3) proceeding to a parent or child entity type found in step A2, referred to hereafter as the second entity, finding all entity types which are related to said second entity as either parent or child, and adding the entity types so found to said first group along with their relationships;

A4) repeating step A3 for every other parent or child entity of said first entity and putting all found entities in said first group along with their relationships;

A5) proceeding to another entity type node in said graph which is one of the entity types found in steps A3 or A4, which will hereafter be referred to as the third entity, and finding all entity types which are related to said third entity as either parent or child, and adding said entity types so found to said first group along with their relationships;

A6) repeating the steps of selecting an entity node, finding all parent and child entities types of said selected entity node, and adding the found entity types to said first group along with their relationships until no further new entity types not previously found can be found, and declaring said first group completed; and

A7) repeating steps A1 through A6 to create another independent group; and

A8) repeating step A7 as many times as necessary to create as many independent groups as are necessary to include all entity types on said graph.

8. The process of claim 2 wherein step C comprises adding up the normalized cardinality for all incoming and outgoing relationships of an entity to calculate said connectivity metric.

9. A computer-readable medium which bears instructions which, when executed by a computer causes said computer to carry out a process to build self-consistent data blocks for a CMDB system or any other external system using a data block maximum size, said process comprising:

A) dividing a graph of entity types into independent groups, each group including entity types related to other entity types by parent-child relationships;

B) computing the cardinality of each relationship;

C) computing a connectivity metric for each entity type;

D) sorting the entity types into decreasing order of connectivity metric;

E) loading related instances of related entity types into one or more data blocks so as to not substantially exceed a maximum data size for each block starting with the entity type of highest connectivity metric and working downward on the sorted list of entity types generated in step D;

F) loading into said one or more data blocks any instances of entity types not related to any other entity types;

G) marking each instance which has been loaded into a data block as done; and

H) repeating steps E, F and G until all instances of all entity types of all independent groups have been loaded into one or more data blocks.

10. The computer-readable medium of claim 9 further bearing computer-readable instructions which, when executed, cause a computer to carry out a further step B1 comprising calculating a weighting ratio for each parent-child relationship by computing the ratio S2 divided by S1, where S2 is the data size of an instance of the child type entity in said relationship and S1 is the data size of an instance of the parent type entity, and further bearing computer-readable instructions which, when executed, cause a computer to carry out a further step B2 of multiplying said cardinality of each said relationship by said weighting ratio of said relationship so as to generate a normalized cardinality for each said relationship before computing said connectivity metric for each said entity type, and further bearing computer-readable instructions which, when executed, cause a computer to carry out step C by computing said connectivity metric for each entity types using said normalized cardinality for each relationship of said entity type.

11. The computer-readable medium of claim 9 further bearing computer-readable instructions which, when executed, cause a computer to carry out step E by performing the following steps:

I) starting with the independent group which contains the entity type with the highest connectivity metric, hereafter referred to as Tmax;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock.

12. The computer-readable medium of claim 9 further bearing computer-readable instructions which, when executed, cause a computer to carry out step E by performing the following steps:

I) starting with the independent group which contains the entity type with the highest connectivity metric calculated using said normalized cardinalities;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock.

13. The computer-readable medium of claim 10 further bearing computer-readable instructions which, when executed, cause a computer to carry out step E by performing the following steps:

I) starting with the independent group which contains the entity type with the highest connectivity metric calculated using said normalized cardinalities;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock;

P) starting with the group in which the entity type with the second highest connectivity metric resides, repeat steps J through O until all instances of said entity type with said second highest connectivity metric resides and instances related thereto at all levels of relation are loaded into a data block; and

Q) repeating processing like step P as many times as necessary for all entity types in all groups until all instances of all entity types have been loaded into one or more data blocks.

14. The computer-readable medium of claim 9 further bearing computer-readable instructions which, when executed, cause a computer to carry out step E by performing the following steps:

I) starting with the independent group which contains the entity type with the highest connectivity metric;

J) calculating N divided by K where N is the maximum block size expressed as the maximum number of entities and K is the number of entities in the group;

K) load N/K instances of entity type Tmax into a data block referred to as currentBlock;

L) load said currentBlock with all instances related to said N/K instances of entity type Tmax at relation distance one from said instances of entity type Tmax loaded in step K;

M) for each related instance loaded in step L, determine other related instances of entity types at relation distance one from said instances of entity types loaded in step L;

N) load into said current block all instances determined in step M which are related to instances loaded in step L;

O) repeat search and loading processing like that of step M and N as many times as necessary to load instances related to said instances of entity type Tmax loaded in step K at each level of relation in said group until all instances of said group are loaded into said currentBlock;

P) starting with the group in which the entity type with the second highest connectivity metric resides, repeat steps J through O until all instances of said entity type with said second highest connectivity metric resides and instances related thereto at all levels of relation are loaded into a data block; and

Q) repeating processing like step P as many times as necessary for all entity types in all groups until all instances of all entity types have been loaded into one or more data blocks.

15. The computer-readable medium of claim 9 further bearing computer-readable instructions which, when executed, cause a computer to carry out step A by performing the following steps:

A1) adding data to relationship tables that record parent-child entity relationships between entity types in said graph so as to make the graph non-directed such that the parent entity type of any entity type may be determined from information in said relationship table;

A2) starting with any first entity on said non-directed graph, find all other entities on said graph which are either parent or child to said first entity and putting all the entities found in a first group along with their relationships;

A3) proceeding to a parent or child entity type found in step A2, referred to hereafter as the second entity, finding all entity types which are related to said second entity as either parent or child, and adding the entity types so found to said first group along with their relationships;

A4) repeating step A3 for every other parent or child entity of said first entity and putting all found entities in said first group along with their relationships;

A5) proceeding to another entity type node in said graph which is one of the entity types found in steps A3 or A4, which will hereafter be referred to as the third entity, and finding all entity types which are related to said third entity as either parent or child, and adding said entity types so found to said first group along with their relationships;

A6) repeating the steps of selecting an entity node, finding all parent and child entities types of said selected entity node, and adding the found entity types to said first group along with their relationships until no further new entity types not previously found can be found, and declaring said first group completed; and

A7) repeating steps A1 through A6 to create another independent group; and

A8) repeating step A7 as many times as necessary to create as many independent groups as are necessary to include all entity types on said graph.

16. The computer-readable medium of claim 10 further bearing computer-readable instructions which, when executed, cause a computer to carry out step C by adding up the normalized cardinality for all incoming and outgoing relationships of an entity to calculate said connectivity metric.

17. An apparatus comprising a computer programmed with an operating system and one or more application programs which interact with said computer and said operating system so as to control said computer to carry out the following process:

A) dividing a graph of entity types into independent groups, each group including entity types related to other entity types by parent-child relationships;

B) computing the cardinality of each relationship;

C) computing a connectivity metric for each entity type;

D) sorting the entity types into decreasing order of connectivity metric;

E) loading related instances of related entity types into one or more data blocks so as to not substantially exceed a maximum data size for each block starting with the entity type of highest connectivity metric and working downward on the sorted list of entity types generated in step D;

F) loading into said one or more data blocks any instances of entity types not related to any other entity types;

G) marking each instance which has been loaded into a data block as done; and

H) repeating steps E, F and G until all instances of all entity types of all independent groups have been loaded into one or more data blocks.

18. An apparatus comprising a computer programmed with an operating system and one or more application programs which interact with said computer and said operating system so as to control said computer to carry out the following process on a collection of data objects which can be represented by a graph of entity types which has been divided into independent groups, each group including entity types related to other entity types by parent-child relationships, each entity type representing one or more instances of the entity, each instance represented by a data object which, if said instance has any parent or child relationship, has data recording at least some of its relationship(s) with one or more instances of another type, said process comprising

A) computing the cardinality of each relationship;

B) computing a connectivity metric for each entity type;

C) sorting the entity types into decreasing order of connectivity metric;

D) loading related instances of related entity types into one or more data blocks so as to not substantially exceed a maximum data size for each block starting with the entity type of highest connectivity metric and working downward on the sorted list of entity types generated in step C;

E) loading into said one or more data blocks any instances of entity types not related to any other entity types;

F) marking each instance which has been loaded into a data block as done; and

G) repeating steps D, E and F until all instances of all entity types of all independent groups have been loaded into one or more data blocks.