Systems and methods for data quality management

• US 5,842,202 A
• Filed: 11/27/1996
• Issued: 11/24/1998
• Est. Priority Date: 11/27/1996
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Kon, Henry B.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Jung, David Yiuk
• Application Number:
  US08/757,759
• Time in Patent Office: 727 Days
• Field of Search: 707/1-10, 707/102, 707/100-104, 707/200-206, 707/500-536
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Systems and methods that model and measure the propagation of error within information systems. The invention provides data management systems that determine an error measure that represent the accuracy, or inaccuracy of a query result achieved for processing a structured data set. In one embodiment, the invention provides systems that have a model of error which exists within a structured data set. The system can further include an error propagation monitor that processes the error model and the structured data set to determine errors within the structured data set that will propagate to a query result generated by performing a query process on the structured data set. The propagated error represents the error that exists within the query result signal.

Claims

1. A system for performing data processing on a structured data set, comprising

a query mechanism for providing logical operations for selectively processing said structured data set to generate a query result signal,

a memory device having storage for an error model, said error model comprising error model data representative of error in said structured data set and probability data representative of a probability distribution of said error in said structured data set, and

a propagation monitor for detecting propagation of said error from said structured data set to said query result signal and for generating in response thereto an error measure signal representative of error in said query result signal.

2. A system according to claim 1 wherein said propagation monitor includes

a query interface, coupled to said query mechanism, for monitoring said logical operations, and

a memory interface, coupled to said memory device, for accessing said error model data and wherein said propagation monitor processes said error model data as a function of said logical operations to generate said error measure signal.

3. A system according to claim 1 further comprising

an instruction parser responsive to said logical operations, for generating a set of query instructions for processing said error model and said structured data set to generate said error measure signal.

4. A system according to claim 1 further comprising

a table generator for providing said error measure signal as a table having storage for error tuples each being representative of an error in associated tuples of said query result signal.

5. A system according to claim 1 wherein said structured data set includes classification data and attribute data, and wherein said system further comprises

means for generating said error measure as a set of tables that store classification errors and attribute errors of said query result signal.

6. A system according to claim 1 wherein said propagation monitor comprises

an attribute monitor for detecting propagation of an attribute inaccuracy from said error model to said query result signal.

7. A system according to claim 1 wherein said propagation monitor comprises

a class mismember monitor for monitoring propagation of a class mismember error to said query result signal.

8. A system according to claim 1 wherein said propagation monitor comprises

a class incompletion monitor, for monitoring propagation of a class incompleteness error to said query result signal.

9. A system according to claim 1 wherein said error model comprises storage for possibility data representative of a non-zero probability of error in said structured data set.

10. A system according to claim 1 further comprising

an iteration processor for iteratively processing said error model, as a function of said probability data, to generate a plurality of error measure signals representative of a probability distribution of error in said query result signal.

11. A system according to claim 1 further comprising:

a functional processor for selecting, responsive to said probability data, a closed-form statistical function for processing said probability data.

12. A system according to claim 1 farther comprising:

a data characteristic processor for generating portions of said probability data as a function of a predetermined characteristic of a data element in said structured data set.

13. A system according to claim 5 further comprising:

means for modifying portions of said error model data as a function of an interpretation map.

22. A system according to claim 1 wherein said error model is defined as a mathematical difference between a given state of said structured data set and a true world state of said structured data set.

23. A system according to claim 1, wherein said error model is defined as a correction mapping from a given state of said structured data set to a true world state of said structured data set.

24. A system according to claim 1 wherein

said logical operations select at least one input table from said structured data set, said at least one input table comprising input columns and input rows, said input columns comprising at least one input key column identifying input functional dependencies among said input columns, and

said query result signal comprises at least one output table comprising an output structure comprising output columns, output rows, and output functional dependencies, said output structure being determined by said logical operations and by said input functional dependencies.

25. A system according to claim 24, wherein

said output columns comprise at least one output key column for identifying said output functional dependencies among said output columns, wherein said output key column is different from said at least one input key column.

26. A system according to claim 25 wherein

said at least one input table comprises an input row number representing the number of said input rows in said at least one input table,

said at least one output table comprises an output row number representing the number of said output rows in said at least one output table, and

said output structure determines said output row number, wherein said output row number is less than said input row number responsive to removal of a portion of said input key column.

14. A method for measuring error in a query result signal generated from a structured data set, comprising the steps of

providing an error model representative of error in said structured data set and probability data representative of a probability distribution for said error in said structured data set,

identifying an instruction signal representative of logical operations for processing said structured data set to generate said query result signal, and

processing said structured data set and error model as a function of said instruction signal to generate an error measure representative of error in said query result signal.

15. A method according to claim 14 wherein said step of providing said error model includes the steps of

providing a reference data set having reference data for comparison, and

comparing said reference data set with said structured data set to determine differences therebetween.

16. A method according to claim 14 wherein said step of providing said error model includes the step of

organizing said error model as a data table having class level and attribute level characteristics and having a plurality of tuples each corresponding to a set of tuples within said structured data set.

17. A method according to claim 16 wherein said step of providing said error model includes the further step of

providing a plurality of said data tables to store class-level and attribute level error data.

18. A method according to claim 14 wherein said step of providing said error model includes the further step of

providing tuple level error measures.

19. A method according to claim 16 wherein said step of providing probability data comprises the further steps of

identifying a portion of said data table having a selected characteristic, and

providing conditional probability data for said identified portion.

20. A method according to claim 14 including the further steps of

processing said probability data to generate a plurality of error state tables, each being representative of a set of possible errors in said structured data set, and

processing said error state tables to generate a plurality of error measures, each being representative of possible errors within said query result signal.

21. A method according to claim 14 including the further step of

processing said probability data as a function of said instruction signal to generate an error measure representative of a probability distribution for error in said query result signal.

27. A method according to claim 14 further comprising the steps of

selecting at least one input table from said structured data set, said at least one input table comprising input columns and input rows,

identifying input functional dependencies among said input columns using at least one input key column, and

determining an output structure for at least one output table comprising output columns, output rows, and output functional dependencies, using said logical operations and said input functional dependencies.

28. A method according to claim 27 further comprising the step of

identifying output functional dependencies among said output columns using at least one output key column, wherein said output key column is different from said input key column.

29. A method according to claim 27 further comprising the steps of

determining in input row number representing the number of said input rows in said at least one input table, and

determining by said output structure an output row number representing the number of said output rows in said at least one output table, wherein said output row number is less than said input row number responsive to removal of a portion of said input key column.