Primary key-foreign key relationship determination through machine learning

• US 10,692,015 B2
• Filed: 07/15/2016
• Issued: 06/23/2020
• Est. Priority Date: 07/15/2016
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Io-Tahoe LLC (Hitachi, Ltd.)
• Inventors: Xu, Yongming, Goyal, Ram Dayal
• Primary Examiner(s): Cassity, Robert A
• Assistant Examiner(s): Hoover, Brent Johston
• Application Number:
  US15/210,889
• Publication Number:
  US 20180018579A1
• Time in Patent Office: 1,439 Days
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 3/09 Supervised learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A method and a machine learning relationship determination system (MLRDS) for determining primary key-foreign key (PK-FK) relationships among data in tables of a target database through machine learning (ML) are provided. The MLRDS selects columns of the tables in the target database and identifies inclusion dependency (ID) pairs from the selected columns. The MLRDS receives training data and validation data from a source database, computes PK-FK features for the inclusion dependency pairs, the training data, and the validation data, and generates trained ML models and validated ML models using the PK-FK features. The MLRDS determines an optimum algorithm decision threshold for a selected machine learning classification algorithm (MLCA), using which the MLRDS determines a resultant on whether the inclusion dependency pair is a PK-FK pair or a non-PK-FK pair. The MLRDS performs majority voting on the resultant for multiple MLCAs to confirm the PK-FK relationships between the inclusion dependency pairs.

Claims

1. A method for determining primary key-foreign key relationships among data in a plurality of tables of a target database through machine learning, the method employing a machine learning relationship determination system comprising at least one processor configured to execute computer program instructions for performing the method comprising:

selecting a first column of data from a first table among the tables and a second column of data from a second table among the tables for each of the tables in the target database by the machine learning relationship determination system, wherein the first column of data comprises a first column name and the second column of data comprises a second column name different from the first column name;

identifying the selected first column of data as a prospective primary key and the selected second column of data as a prospective foreign key to form an inclusion dependency pair by the machine learning relationship determination system on determining presence of data elements of the selected second column of data in the selected first column of data in entirety;

receiving a plurality of predetermined inclusion dependency pairs comprising primary key-foreign key pairs classified as positive training data and positive validation data, and non-primary key-foreign key pairs classified as negative training data and negative validation data, by the machine learning relationship determination system from a source database, wherein the positive validation data and the negative validation data form a validation data set;

splitting the positive training data and the negative training data into training data sets by the machine learning relationship determination system;

computing a plurality of primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key, the training data sets, and the validation data set by the machine learning relationship determination system, wherein the primary key-foreign key features for the training data sets and the validation data set are computed by the machine learning relationship determination system using one of a plurality of items selected from the group consisting of data elements of the predetermined inclusion dependency pairs, a number of unique data elements of foreign keys in the predetermined inclusion dependency pairs, Levenshtein distance between names of primary keys and the foreign keys in the predetermined inclusion dependency pairs, a prefix matching score obtained from the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, sound codes obtained by applying a Metaphone algorithm on the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, patterns of the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, statistical measures, and any combination thereof;

generating trained machine learning models corresponding to the training data sets by the machine learning relationship determination system by training each of one or more machine learning classification algorithms using the training data sets and the computed primary key-foreign key features of the training data sets;

generating validated machine learning models for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system on testing the generated trained machine learning models corresponding to the training data sets with the validation data set using the computed primary key-foreign key features of the validation data set;

determining an optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system using the generated validated machine learning models;

determining a resultant of the inclusion dependency pair being one of a primary key-foreign key pair and a non-primary key-foreign key pair by the machine learning relationship determination system for the each of the one or more machine learning classification algorithms using the determined optimum algorithm decision threshold and the computed primary key-foreign key features of the inclusion dependency pair of the prospective primary key and the prospective foreign key; and

performing majority voting on the determined resultant for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system to determine a primary key-foreign key relationship among the data in the selected first column of data of the first table and the selected second column of data of the second table.

2. The method of claim 1, wherein the validated machine learning models for the each of the one or more machine learning classification algorithms are generated by the machine learning relationship determination system when the generated trained machine learning models corresponding to the training data sets meet a predetermined criterion on testing the generated trained machine learning models with the validation data set.

3. The method of claim 2, further comprising retraining the generated trained machine learning models on the training data sets until the generated trained machine learning models meet the predetermined criterion for the generation of the validated machine learning models for the each of the one or more machine learning classification algorithms.

4. The method of claim 1, wherein the determined optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms is stored in a threshold database by the machine learning relationship determination system.

5. The method of claim 1, wherein the primary key-foreign key features comprise a normalized rank sum, a unique foreign key ratio, a unique foreign share, a name similarity index, a name pattern acceptance, a distribution displacement, and an element count ratio.

6. The method of claim 1, wherein the primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key are computed by the machine learning relationship determination system using one of a plurality of items selected from the group consisting of data elements of the prospective primary key identified by the selected first column of data, the data elements of the prospective foreign key identified by the selected second column of data, a number of unique data elements of the prospective foreign key, Levenshtein distance between names of the prospective primary key and the prospective foreign key, a prefix matching score obtained from the names of the prospective primary key and the prospective foreign key, sound codes obtained by applying a Metaphone algorithm on the names of the prospective primary key and the prospective foreign key, patterns of the names of the prospective primary key and the prospective foreign key, statistical measures, and any combination thereof.

7. The method of claim 1, wherein the one or more machine learning classification algorithms comprise J48 algorithm, k-Nearest Neighbors algorithm, Naive Bayes algorithm, Random Forest algorithm, Bayes network model, a multilayer perceptron model, and a support vector machine model.

8. A system for determining primary key foreign key relationships among data in a plurality of tables of a target database, the system comprising:

a non-transitory computer readable storage medium configured to store computer program instructions; and

at least one processor connected to the non-transitory computer readable storage medium, the computer program instructions when executed by the at least one processor configure the system to;

select a first column of data from a first table among the tables and a second column of data from a second table among the tables for each of the tables in the target database, wherein the first column of data comprises a first column name and the second column of data comprises a second column name different from the first column name;

identify the selected first column of data as a prospective primary key and the selected second column of data as a prospective foreign key to form an inclusion dependency pair on determining presence of data elements of the selected second column of data in the selected first column of data in entirety;

receive a plurality of predetermined inclusion dependency pairs comprising primary key-foreign key pairs classified as positive training data and positive validation data, and non primary key-foreign key pairs classified as negative training data and negative validation data, from a source database, wherein the positive validation data and the negative validation data form a validation data set;

split the positive training data and the negative training data into training data sets;

compute a plurality of primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key, the training data sets, and the validation data set, wherein the system is further configured to compute the primary key-foreign key features for the training data sets and the validation data set using one of a plurality of items selected from the group consisting of data elements of the predetermined inclusion dependency pairs, a number of unique data elements of foreign keys in the predetermined inclusion dependency pairs, Levenshtein distance between names of primary keys and the foreign keys in the predetermined inclusion dependency pairs, a prefix matching score obtained from the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, sound codes obtained by applying a Metaphone algorithm on the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, patterns of the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, statistical measures, and any combination thereof;

generate trained machine learning models corresponding to the training data sets by training each of one or more machine learning classification algorithms using the training data sets and the computed primary key-foreign key features of the training data sets;

generate validated machine learning models for the each of the one or more machine learning classification algorithms on testing the generated trained machine learning models corresponding to the training data sets with the validation data set using the computed primary key-foreign key features of the validation data set;

determine an optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms using the generated validated machine learning models;

determine a resultant of the inclusion dependency pair being one of a primary key foreign key pair and a non-primary key-foreign key pair for the each of the one or more machine learning classification algorithms using the determined optimum algorithm decision threshold and the computed primary key foreign key features of the inclusion dependency pair of the prospective primary key and the prospective foreign key; and

perform majority voting on the determined resultant for the each of the one or more machine learning classification algorithms to determine a primary key-foreign key relationship among the data in the selected first column of data of the first table and the selected second column of data of the second table.

9. The machine learning relationship determination system of claim 8, wherein the system is further configured to generate the validated machine learning models for the each of the one or more machine learning classification algorithms when the generated trained machine learning models corresponding to the training data sets meet a predetermined criterion on testing the generated trained machine learning models with the validation data set.

10. The machine learning relationship determination system of claim 9, wherein the system is further configured to retrain the generated trained machine learning models on the training data sets until the generated trained machine learning models meet the predetermined criterion for the generation of the validated machine learning models for the each of the one or more machine learning classification algorithms.

11. The machine learning relationship determination system of claim 8, wherein the system is further configured to store the determined optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms in a threshold database.

12. The machine learning relationship determination system of claim 8, wherein the primary key-foreign key features comprise a normalized rank sum, a unique foreign key ratio, a unique foreign share, a name similarity index, a name pattern acceptance, a distribution displacement, and an element count ratio.

13. The machine learning relationship determination system of claim 8, wherein the system is further configured to compute the primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key using one of a plurality of items selected from the group consisting of data elements of the prospective primary key identified by the selected first column of data, the data elements of the prospective foreign key identified by the selected second column of data, a number of unique data elements of the prospective foreign key, Levenshtein distance between names of the prospective primary key and the prospective foreign key, a prefix matching score obtained from the names of the prospective primary key and the prospective foreign key, sound codes obtained by applying a Metaphone algorithm on the names of the prospective primary key and the prospective foreign key, patterns of the names of the prospective primary key and the prospective foreign key, statistical measures, and any combination thereof.

14. The machine learning relationship determination system of claim 8, wherein the one or more machine learning classification algorithms comprise J48 algorithm, k-Nearest Neighbors algorithm, Naive Bayes algorithm, Random Forest algorithm, Bayes network model, a multilayer perceptron model, and a support vector machine model.

15. A non-transitory computer readable storage medium having stored thereon instructions for causing one or more processing units to execute a process for determining primary key-foreign key relationships among data in a plurality of tables of a target database, the process comprising:

selecting a first column of data from a first table among the tables and a second column of data from a second table among the tables for each of the tables in the target database, wherein the first column of data comprises a first column name and the second column of data comprises a second column name different from the first column name;

identifying the selected first column of data as a prospective primary key and the selected second column of data as a prospective foreign key to form an inclusion dependency pair on determining presence of data elements of the selected second column of data in the selected first column of data in entirety;

receiving a plurality of predetermined inclusion dependency pairs comprising primary key-foreign key pairs classified as positive training data and positive validation data, and non-primary key-foreign key pairs classified as negative training data and negative validation data, from a source database, wherein the positive validation data and the negative validation data form a validation data set;

splitting the positive training data and the negative training data into training data sets;

computing a plurality of primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key, the training data sets, and the validation data set, wherein the primary key-foreign key features for the training data sets and the validation data set are computed by the machine learning relationship determination system using one of a plurality of items selected from the group consisting of data elements of the predetermined inclusion dependency pairs, a number of unique data elements of foreign keys in the predetermined inclusion dependency pairs, Levenshtein distance between names of primary keys and the foreign keys in the predetermined inclusion dependency pairs, a prefix matching score obtained from the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, sound codes obtained by applying a Metaphone algorithm on the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, patterns of the names of the primary keys and the foreign keys in the predetermined inclusion dependency pairs, statistical measures, and any combination thereof;

generating trained machine learning models corresponding to the training data sets by training each of one or more machine learning classification algorithms using the training data sets and the computed primary key-foreign key features of the training data sets;

generating validated machine learning models for the each of the one or more machine learning classification algorithms on testing the generated trained machine learning models corresponding to the training data sets with the validation data set using the computed primary key foreign key features of the validation data set;

determining an optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms using the generated validated machine learning models;

determining a resultant of the inclusion dependency pair being one of a primary key-foreign key pair and a non-primary key-foreign key pair for the each of the one or more machine learning classification algorithms using the determined optimum algorithm decision threshold and the computed primary key-foreign key features of the inclusion dependency pair of the prospective primary key and the prospective foreign key; and

performing majority voting on the determined resultant for the each of the one or more machine learning classification algorithms to determine a primary key-foreign key relationship among the data in the selected first column of data of the first table and the selected second column of data of the second table.

16. The non-transitory computer readable storage medium of claim 15, wherein the process further comprises generating the validated machine learning models for the each of the one or more machine learning classification algorithms when the generated trained machine learning models corresponding to the training data sets meet a predetermined criterion on testing the generated trained machine learning models with the validation data set.

17. The non-transitory computer readable storage medium of claim 16, wherein the process further comprises retraining the generated trained machine learning models on the training data sets until the generated trained machine learning models meet the predetermined criterion for the generation of the validated machine learning models for the each of the one or more machine learning classification algorithms.

18. The non-transitory computer readable storage medium of claim 15, wherein the primary key-foreign key features comprise a normalized rank sum, a unique foreign key ratio, a unique foreign share, a name similarity index, a name pattern acceptance, a distribution displacement, and an element count ratio.

19. A method for determining primary key-foreign key relationships among data in a plurality of tables of a target database through machine learning, the method employing a machine learning relationship determination system comprising at least one processor configured to execute computer program instructions for performing the method comprising:

selecting a first column of data from a first table among the tables and a second column of data from a second table among the tables for each of the tables in the target database by the machine learning relationship determination system, wherein the first column of data comprises a first column name and the second column of data comprises a second column name different from the first column name;

identifying the selected first column of data as a prospective primary key and the selected second column of data as a prospective foreign key to form an inclusion dependency pair by the machine learning relationship determination system on determining presence of data elements of the selected second column of data in the selected first column of data in entirety;

receiving a plurality of predetermined inclusion dependency pairs comprising primary key-foreign key pairs classified as positive training data and positive validation data, and non-primary key-foreign key pairs classified as negative training data and negative validation data, by the machine learning relationship determination system from a source database, wherein the positive validation data and the negative validation data form a validation data set;

splitting the positive training data and the negative training data into training data sets by the machine learning relationship determination system;

computing a plurality of primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key, the training data sets, and the validation data set by the machine learning relationship determination system, wherein the plurality of primary key-foreign key features for the inclusion dependency pair of the prospective primary key and the prospective foreign key are computed by the machine learning relationship determination system using one of a plurality of items selected from the group consisting of data elements of the prospective primary key identified by the selected first column of data, the data elements of the prospective foreign key identified by the selected second column of data, a number of unique data elements of the prospective foreign key, Levenshtein distance between names of the prospective primary key and the prospective foreign key, a prefix matching score obtained from the names of the prospective primary key and the prospective foreign key, sound codes obtained by applying a Metaphone algorithm on the names of the prospective primary key and the prospective foreign key, patterns of the names of the prospective primary key and the prospective foreign key, statistical measures, and any combination thereof;

generating trained machine learning models corresponding to the training data sets by the machine learning relationship determination system by training each of one or more machine learning classification algorithms using the training data sets and the computed primary key-foreign key features of the training data sets;

generating validated machine learning models for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system on testing the generated trained machine learning models corresponding to the training data sets with the validation data set using the computed primary key-foreign key features of the validation data set;

determining an optimum algorithm decision threshold for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system using the generated validated machine learning models;

determining a resultant of the inclusion dependency pair being one of a primary key-foreign key pair and a non-primary key-foreign key pair by the machine learning relationship determination system for the each of the one or more machine learning classification algorithms using the determined optimum algorithm decision threshold and the computed primary key-foreign key features of the inclusion dependency pair of the prospective primary key and the prospective foreign key; and

performing majority voting on the determined resultant for the each of the one or more machine learning classification algorithms by the machine learning relationship determination system to determine a primary key-foreign key relationship among the data in the selected first column of data of the first table and the selected second column of data of the second table.