System, service, and method for automatically discovering universal data objects

• US 20070005658A1
• Filed: 07/02/2005
• Published: 01/04/2007
• Est. Priority Date: 07/02/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Myllymaki, Jussi
• Application Number:
  US11/174,212
• Publication Number:
  US 20070005658A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

A universal data object discovery system automatically identifies candidate universal data objects, ranks the candidate universal data objects according to predetermined criteria, and merges source schemas into unified universal data objects within a set of data sources. From data inputs and a set of control parameters, the system computes a degree of sharing score for composite structures in the source schemas. The data inputs comprise source schemas, similarity values for data structures, and foreign key relationships. The system identifies as candidate universal data objects those structures whose degree of sharing score exceeds a threshold. The system calculates a similarity between candidate universal data objects and merges candidate universal data objects that are similar. The merged universal data objects are the output of the system.

Claims

1. A method of automatically discovering a plurality of universal data objects, comprising:

generating an object graph from a set of source schemas, a plurality of similarities between objects in the set of source schemas, and a plurality of additional metadata describing the set of source schemas;

calculating a degree of sharing score for a plurality of objects in the object graph;

selecting a plurality of candidate universal data objects from the objects in the object graph;

clustering the candidate universal data objects to select a plurality of universal data objects; and

merging the selected universal data objects to allow sharing of data between the set of source schemas.

2. The method of claim 1 wherein generating the additional the additional metadata comprises identifying foreign keys between two objects in the set of source schemas, and further identifying the strength of each foreign key.

3. The method of claim 1 wherein generating the additional the additional metadata comprises identifying a relative cardinality between an object and a parent of the object in the set of source schemas.

4. The method of claim 1 wherein generating the additional the additional metadata comprises identifying the size of each of the objects in the set of source schemas.

5. The method of claim 1 wherein calculating the degree of sharing score for each object comprises calculating the sum of:

a structural sharing score for the object;

a value relationship score for the object; and

a foreign key relationship score for the object.

6. The method of claim 5 wherein calculating the structural sharing score comprises calculating a value dependent on the position of the object relative to a root in the object graph.

7. The method of claim 6 wherein calculating the position-dependent structural sharing score comprises calculating the sum of the distances from the object to each of the ancestors of the object according to the following equation:

Score=Σ

(½

)<sup>(n−

1)</sup>,

where n is the distance from the object to the ancestor measured as the number of links.

8. The method of claim 5 wherein calculating the value relationship score comprises calculating the sum of the similarity of the object to another object times the structural sharing score of that other object.

9. The method of claim 5 wherein calculating the foreign key score comprises calculating, for each object that is an instance referenced by another object, the sum of the foreign key strength between a primary key of the object and a foreign key of the referencing object times the structural sharing score of the foreign key of the referencing object.

12. The method of claim 1 wherein clustering the candidate universal data objects comprises:

splitting a universal data object from its parent; and

inserting a foreign key in each universal data object if the relationship to its parent is as follows;

one parent has multiple children.

13. The method of claim 1 wherein clustering the candidate universal data objects comprises:

splitting a universal data object from its parent; and

inserting a foreign key in each parent if the relationship of the universal data object to its parent is as follows;

one parent has one child.

14. The method of claim 1 wherein clustering the candidate universal data objects comprises:

splitting a universal data object from its parent;

generating a separate relationship object if the relationship of the universal data object to its parent is as follows;

one parent has multiple children and one child has multiple parents; and

inserting a first foreign key in the separate relationship object pointing to the parent and a second foreign key in the separate relationship object pointing to the universal data object.

15. The method of claim 1 wherein merging the selected universal data objects comprises merging attributes that are common to all the universal data objects being merged.

16. The method of claim 1 wherein merging the selected universal data objects comprises merging attributes that are in any of the universal data objects being merged.

10. The method of claim wherein selecting candidate universal data objects comprises filtering objects with respect to control parameters.

11. The method of claim 10 wherein the control parameters comprise:

a minimum size and a maximum size of a candidate universal data object type;

a minimum and a maximum relative cardinality between the candidate universal data object and a parent of the candidate universal data object; and

a minimum value of a degree of sharing score of the candidate universal data object.

17. A system for automatically discovering a plurality of universal data objects, comprising:

a schema processing module for generating an object graph from a set of source schemas, a plurality of similarities between objects in the set of source schemas, and a plurality of additional metadata describing the set of source schemas;

the schema processing module further calculating a degree of sharing score for a plurality of objects in the object graph;

a selection module for selecting a plurality of candidate universal data objects from the objects in the object graph;

a clustering module for clustering the candidate universal data objects to select a plurality of universal data objects; and

a merging module for merging the selected universal data objects to allow sharing of data between the set of source schemas.

18. The system of claim 17 wherein the schema processing calculates the degree of sharing score for each object by calculating the sum of:

a structural sharing score for the object;

a value relationship score for the object; and

a foreign key relationship score for the object.

19. A computer program product having a plurality of executable instruction codes embedded on a computer-readable medium, for automatically discovering a plurality of universal data objects, comprising:

a first set of instruction codes for generating an object graph from a set of source schemas, a plurality of similarities between objects in the set of source schemas, and a plurality of additional metadata describing the set of source schemas;

a second set of instruction codes for calculating a degree of sharing score for a plurality of objects in the object graph;

a third set of instruction codes for selecting a plurality of candidate universal data objects from the objects in the object graph;

a fourth set of instruction codes for clustering the candidate universal data objects to select a plurality of universal data objects; and

a fifth set of instruction codes for merging the selected universal data objects to allow sharing of data between the set of source schemas.

20. A method of providing a service for automatically discovering a plurality of universal data objects, comprising:

specifying a set of data sources for which universal data objects are identified;

specifying a set of control parameters and additional metadata;

invoking an automatic universal data object discovery utility, wherein the specified set of data sources, the specified control parameters, and the additional metadata are made available to the automatic universal data object discovery utility for consideration; and

receiving an object graph with identified universal data objects from the automatic universal data object discovery utility.