Detecting Inconsistent Data Records

• US 20130226879A1
• Filed: 03/29/2012
• Published: 08/29/2013
• Est. Priority Date: 02/28/2012
• Status: Active Grant

• Current Assignee: Qatar Foundation
• Original Assignee: Qatar Foundation
• Inventors: YAKOUT, Mohamed, OUZZANI, Mourad, TALUKDER, Nilothpal, ELMAGARMID, Ahmed
• Granted Patent: US 9,037,550 B2
• Time in Patent Office: Days
• US Class Current: 707/690
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• 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 21/60 Protecting data
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes

Abstract

A computer-implemented method for detecting a set of inconsistent data records in a database including multiple records, comprises selecting a data quality rule representing a functional dependency for the database, transforming the data quality rule into at least one rule vector with hashed components, selecting a set of attributes of the database, transforming at least one record of the database selected on the basis of the selected attributes into a record vector with hashed components, computing a dot product of the rule and record vectors to generate a measure representing violation of the data quality rule by the record.

Claims

1. A computer-implemented method for detecting a set of inconsistent data records in a database including multiple records, comprising:

selecting a data quality rule representing a functional dependency for the database;

transforming the data quality rule into at least one rule vector with hashed components;

selecting a set of attributes of the database;

transforming at least one record of the database selected on the basis of the selected attributes into a record vector with hashed components;

computing a dot product of the rule and record vectors to generate a measure representing violation of the data quality rule by the record.

2. A computer-implemented method as claimed in claim 1, wherein hashed components of the vectors are fixed-size hashcodes.

3. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database.

4. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the CFD is a constant CFD including rule attributes which are constants.

5. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the CFD is a variable CFD including rule attributes which are variable.

6. A computer-implemented method as claimed in claim 1, wherein the measure representing violation of the data quality rule by the record is provided only to the owner of the database.

7. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the record includes an attribute matching a corresponding determinant attribute for the CFD.

8. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the record includes an attribute matching a corresponding determinant attribute for the CFD, and wherein a violation occurs if there is a disagreement between a dependent attribute of the record and the corresponding attribute of the CFD.

9. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the CFD is a constant CFD including rule attributes which are constants, and wherein a pair of records of the database is transformed into the record vector, the hashed components of the vector determined from a random selection of attribute values from the pair of records.

10. A computer-implemented method as claimed in claim 1, wherein the data quality rule is a conditional functional dependency (CFD) representing a functional dependency of the database which is extended with a pattern tableau specifying conditions under which the functional dependency holds for records of the database, and wherein the CFD is a variable CFD including rule attributes which are variable, and wherein a pair of records of the database is transformed into the record vector, the hashed components of the vector determined from a random selection of attribute values from the pair of records.

11. A computer-implemented method as claimed in claim 1, wherein the privacy of a data quality rule is preserved in the case where it is not violated by the records.

12. A computer-implemented method as claimed in claim 1, wherein transforming the data quality rule includes generating a pair of vectors for a rule representing components for the left and right hand sides of the rule.

13. A computer-implemented method as claimed in claim 1, wherein transforming the data quality rule includes generating a pair of vectors for a rule representing components for the left and right hand sides of the rule, and wherein the pair of vectors for a data quality rule which is a variable conditional functional dependency are concatenated to form a single vector.

15. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 13, the computer program including machine readable instructions that, when executed by a processor, implement a method for detecting a set of inconsistent data records in a database including multiple records, wherein:

generating a rule vector includes generating respective vectors for constants of the left and right sides of the rule, and wherein computing a secure dot product includes computing a dot product using each such vector with the data vector for a constant CFD inconsistency detection.

16. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 13, the computer program including machine readable instructions that, when executed by a processor, implement a method for detecting a set of inconsistent data records in a database including multiple records, wherein:

generating a rule vector includes generating respective vectors for constants of the left and right sides of the rule and concatenating the vectors to provide a rules vector for a variable CFD inconsistency detection.

14. A computer program embedded on a non-transitory tangible computer readable storage medium, the computer program including machine readable instructions that, when executed by a processor, implement a method for detecting a set of inconsistent data records in a database including multiple records, comprising:

selecting a set of attributes and generating a set of data vectors from hashcodes of the corresponding attribute values of a set of records of the database;

selecting a conditional functional dependency rule and generating a rule vector from hashcodes of the rule;

computing a secure dot product of the data and rule vectors to determine an inconsistent record in the database.