HK1211109B - Profiling data with location information - Google Patents

Description

Analyzing data using location information

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. Application No. 61/716,766, filed October 22, 2012, which is incorporated herein by reference.

Background Art

This specification relates to profiling data using location information.

Stored data sets often include data of various unknown characteristics. The data in a data set can be organized into records with values for different fields (also called "attributes" or "columns"). The values within a field can include strings, numbers, or any data encoded or formatted according to the relevant data format information for the field (including values that may be invalid). In some cases, the data format information for a field is known, but the actual value that appears in the field may not be known. For example, the value range or typical value of a field between records in a data set, the relationship between different fields of records in a data set, or the dependency of values in different fields may be unknown. Data profiling involves examining the source of the data set to determine such characteristics.

Summary of the Invention

In one embodiment, generally, a method for analyzing data stored in at least one data storage system includes: accessing at least one record collection stored in the data storage system via an interface connected to the data storage system; processing the record collection to generate result information, wherein the result information represents the values appearing in one or more specific fields of the record collection. The processing includes: generating corresponding position information for a first set of distinct values appearing in a first set of one or more fields of records in a set, the position information identifying, for each distinct value in the first set of distinct values, all records in which the distinct value appears; generating a corresponding list of entries for the first set of one or more fields, each entry identifying a distinct value from the first set of distinct values and position information for the distinct value; generating a corresponding list of entries for a second set of one or more fields of records in the set that is different from the first set of one or more fields, each entry identifying a distinct value from a second set of distinct values appearing in the second set of one or more fields; and generating result information representing values appearing in one or more particular fields of the set of records based at least in part on: locating at least one record in the set of records using the position information for at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

These solutions may include the following features.

Each entry further identifies a count of the number of records in which a unique value occurs in a set of one or more fields.

The processing further includes sorting the entries in each list by the identified count.

The processing further includes generating, for each of the second set of singular values, corresponding location information, the location information identifying, for each singular value in the second set of singular values, all records in which the singular value occurs. Each entry in the list corresponding to the second set of one or more fields in which a singular value is identified includes the location information for the singular value.

The processing further includes: generating corresponding position information for a set of unique value pairs, wherein the first value in each pair of values appears in the first set of one or more fields of the record, and the second value in each pair of values appears in the second set of one or more fields of the record, and the position information identifies all each record in which the unique value pair appears for each unique value pair.

Generating position information of a singular value pair from the set of singular value pairs includes determining an intersection between position information of a first singular value from the first set of singular values and position information of a second singular value from the second set of singular values.

Determining the intersection includes: using the position information of the first singular value to locate a record in the set, and using the located record to determine the second singular value.

The method further includes sorting a plurality of lists according to a number of unique values identified in entries of each list, the plurality of lists including lists corresponding to the first set of one or more fields and lists corresponding to the second set of one or more fields.

The processing further includes: generating corresponding position information for a set of unique value pairs, wherein the first value in each pair of values appears in the first set of one or more fields of the record, and the second value in each pair of values appears in the second set of one or more fields of the record, and the second set of one or more fields is different from the first set of one or more fields, and the position information identifies, for each unique value pair, all records in which the unique value pair appears; and generating a corresponding list of entries for the set of unique value pairs, wherein each entry identifies a unique value pair from the set of unique value pairs and the position information of the unique value pair.

The location information identifies a unique index value for each record in which the unique value occurs.

The location information identifies a specific unique index value by storing the specific unique index value.

The location information identifies the unique index value by encoding the unique index value within the location information.

Encoding the unique index value includes storing a bit at a position within the vector corresponding to the unique index value.

The collection includes a first subset of records having fields including the first set of one or more fields and a second subset of records having fields including the second set of one or more fields.

The processing further includes generating information that provides a mapping between: 1) a field index value of the first subset of records, which associates a unique index value with each record in the first subset; and 2) a key value of a field of the second subset of records, which associates a key value with each record in the second subset; wherein the key value links records in the second subset to records in the first subset.

The location information identifies a unique index value for each record in which the unique value occurs.

In another embodiment, a computer program, stored in a computer-readable medium, is used to analyze data stored in at least one data storage system, the computer program including instructions for causing a computing system to: access at least one record set stored in the data storage system via an interface connected to the data storage system; and process the record set to generate result information, wherein the result information represents the values appearing in one or more specific fields of the record set. The processing includes: generating corresponding position information for a first set of unique values appearing on a first set of one or more fields of records in a set, the position information identifying, for each unique value in the first set of unique values, all records in which the unique value appears, generating a corresponding list of entries for the first set of one or more fields, each entry identifying a unique value from the first set of unique values and position information for the unique value, generating a corresponding list of entries for a second set of one or more fields of records in the set that is different from the first set of one or more fields, each entry identifying a unique value from a second set of unique values appearing in the second set of one or more fields, and generating result information representing values appearing in one or more specific fields of the record set based at least in part on: locating at least one record in the record set using the position information of at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

In another embodiment, a computing system is provided for analyzing data stored in at least one data storage system, the computing system comprising: an interface connected to the data storage system for accessing at least one record set stored in the data storage system; and at least one processor for processing the record set to generate result information, wherein the result information represents values appearing in one or more specific fields of the record set. The processing includes: generating corresponding position information for a first set of unique values appearing on a first set of one or more fields of records in a set, the position information identifying, for each unique value in the first set of unique values, all records in which the unique value appears; generating a corresponding list of entries for the first set of one or more fields, each entry identifying a unique value from the first set of unique values and position information for the unique value; generating a corresponding list of entries for a second set of one or more fields of records in the set that is different from the first set of one or more fields, each entry identifying a unique value from a second set of unique values appearing in the second set of one or more fields; and generating result information representing values appearing in one or more specific fields of the record set based at least in part on: locating at least one record in the record set using the position information of at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

In another embodiment, a computing system is provided for analyzing data stored in at least one data storage system, the computing system comprising: a device for accessing at least one record set stored in the data storage system; and a device for processing the record set to generate result information representing values appearing in one or more specific fields of the record set. The processing includes: generating corresponding position information for a first set of unique values appearing on a first set of one or more fields of records in a set, the position information identifying, for each unique value in the first set of unique values, all records in which the unique value appears; generating a corresponding list of entries for the first set of one or more fields, each entry identifying a unique value from the first set of unique values and position information for the unique value; generating a corresponding list of entries for a second set of one or more fields of records in the set that is different from the first set of one or more fields, each entry identifying a unique value from a second set of unique values appearing in the second set of one or more fields; and generating result information representing values appearing in one or more specific fields of the record set based at least in part on: locating at least one record in the record set using the position information of at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

In another aspect, a method, computer-readable medium, and system for profiling data stored in at least one data storage system includes: accessing at least one set of records stored in the data storage system via an interface connected to the data storage system; processing the set of records to generate result information representing values occurring in one or more specific fields of the set of records. The processing includes: generating a list of entries corresponding to a first set of unique values for a first set of two or more fields, each entry identifying a unique value combination of values occurring in the first set of two or more fields of a record in the set and profile information for the unique value combination; and generating the result information representing the values occurring in the one or more specific fields of the set of records based at least in part on: combining profile information from the list of entries for at least two unique value combinations occurring in the first set of two or more fields, and determining profile information for at least one value occurring in the at least one of the one or more specific fields based on the combined profile information.

These aspects may include one or more of the following advantages.

Some data profiling programs calculate a measure of the data quality of a dataset by compiling a census of outliers within a domain of the dataset's records, where a "domain" includes one or more fields, combinations of fields, or segments of fields of the dataset's records. When statistics are compiled for a domain, statistics are stored that enumerate the set of outliers for that domain and include a count of the number of records with each outlier. For example, the statistics may be set as a list of value count entries for a selected domain, each value count entry including the outlier that appears in the selected domain and the number of records in the selected domain that the outlier appears in. In some embodiments, each field is a separate domain. In some embodiments, the statistics are stored in a single dataset, optionally indexed by field for fast random access, while in other embodiments, the statistics may be stored in multiple datasets, e.g., one per field.

Measures of data quality may include the number and distribution of outliers, the number and distribution of values that are valid or invalid according to a particular validation rule, the number and distribution of values for one or more fields when the values for another set of one or more fields are held fixed (also known as "segments"), and the correlation between values for two or more fields (also known as "functional dependencies"). Each time a particular measure is calculated, appropriate statistics may be applied to the data in the dataset. However, in some cases, such as when calculating a data quality measure for a combination of fields, it is not necessary to perform a complete data processing, but rather to use stored statistics that have been calculated for individual fields to calculate the combination of fields.

In some embodiments, the statistics for a selected domain include position information that, for each outlier in the statistics, identifies each record in the selected domain in which the outlier occurs. The position information is calculated only once for all the data. Subsequent evaluations of data quality metrics involving combinations of fields (particularly, metrics involving segmentation, correlation, or validation rules involving multiple fields) can be performed directly from existing statistics with position information, without having to return to the source storing the dataset records to calculate new statistics. This makes the calculation of other data quality metrics much more efficient. In addition, statistics with position information can be used to drill down to data quality results, i.e., return the underlying data records related to the data quality results, such as invalid records or duplicate records for primary key fields. If domains of different datasets are profiled, an index map can be used to avoid the need for join operations to associate records from different datasets.

Other features and advantages of the invention will be apparent from the following description and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a block diagram of a system for profiling data.

FIG2A is a schematic diagram of the operation and data of a data analysis program;

FIG2B is a flow chart of the data analysis procedure;

Figure 3 is a schematic diagram of the data generated by the function dependency result

FIG4 is a flow chart of the combined statistical program;

FIG5 is a schematic diagram of data generated for combined statistics;

FIG6A is a flow chart of a procedure for determining functional dependencies;

FIG6B is an example of combined statistics with functional dependency information;

FIG7 is a schematic diagram of an edge drill-down procedure;

FIG8A is a schematic diagram of index map data;

FIG8B is a schematic diagram of function dependency result data;

FIG9 is a schematic diagram of a node drill-down procedure;

FIG10 is a schematic diagram of segmented statistics and segmented combined statistics;

FIG. 11 is a schematic diagram of data for segment data.

DETAILED DESCRIPTION

FIG1 illustrates an exemplary data processing system 100 in which data profiling techniques may be employed. System 100 includes a data source 102, which may include one or more data sources, such as a storage device or connected to an online data stream, each of which may store data in any of a variety of storage formats (e.g., a database table, a spreadsheet file, a plain text file, or a native format used by a host). An execution environment 104 includes a profiling module 106 and a processing module 108. The execution environment 104 may be hosted on one or more general-purpose computers controlled by a suitable operating system (e.g., a UNIX operating system). For example, the execution environment 104 may include a multi-node parallel computer system comprising a configuration of a computer system using multiple central processing units (CPUs), wherein the central processing unit may be a local CPU (e.g., a multi-processor system such as an SMP computer), a locally distributed CPU (e.g., multiple processors coupled as a cluster or MPP processor), a remote CPU, a remotely distributed CPU (e.g., multiple processors coupled via a local area network (LAN) or a wide area network (WAN)), or a combination thereof.

The profiling module 106 reads data from the data source 102 and stores profiling profile information in a profiling data store 110 accessible by the profiling module 106 and the processing module 108. For example, the profiling data store 110 may be stored in the storage of the data source 102 or in a separate data storage system accessible from the execution environment 104. Based on the profiling profile information, the processing module 108 can perform various processing tasks on the data in the data source 102, including cleaning the data, downloading the data to another system, or managing access to objects stored in the data source 102. The storage providing the data source 102 may be local to the execution environment 104, for example, stored in a storage medium connected to the computer running the execution environment 104 (e.g., hard drive 112), or remote to the execution environment 104, for example, hosted on a remote system (e.g., host 114) that communicates with the computer running the execution environment 104 via a remote connection or service (e.g., provided by a cloud computing infrastructure).

The profiling module 106 is capable of reading data stored in the data source 102 and efficiently performing various types of analysis, including, for example, analysis based on functional dependencies or segmentation to facilitate the calculation of data quality metrics. In some embodiments, the analysis includes generating statistical data for each individual field of a data set record stored in the data source 102, and storing the statistical data in the profile data store 110. As described above, the statistical data for a particular field of a record in a particular data set includes not only an entry for each unique value occurring in that field, but also positional information identifying the respective position (e.g., in terms of a record index value) of the record in the particular data set where the unique value occurs. In one embodiment, in generating statistical entries for associated values, a vector is assigned a unique record identifier for each record with the associated value. If the records in the raw data of the data set do not have unique record identifiers, such record identifiers can be generated and added to the records as part of the profiling process, for example, by assigning a continuous sequence of numbers to each record. This positional information can then be included in the statistical entries and used to generate other combined statistical data to calculate functional dependencies or segmentation, as described in more detail below.

Other implementations of the storage location information are also possible, some of which have advantages in terms of performance and/or reduced storage space. For example, a bit vector can be used instead of a vector of record identifiers. Each bit of the bit vector corresponds to a specific record identifier, and a bit is set if the associated record with the corresponding record identifier has an associated value. The correspondence between the bits of the bit vector and the record identifier can be explicit or implicit. For example, there can be an explicit mapping, which is not necessarily a one-to-one mapping, which associates the bit digits with the corresponding record identifiers, or it can be an implicit mapping, where the position of each bit digit corresponds to the order of the record positions. In some embodiments, the resulting bit vector is compressed to further save storage.

Position information can also be stored within a vector of bit vectors. For example, each bit of a bit vector may correspond to an associated record identifier via a mapping between bit positions and record identifiers stored in a cross-reference file. The vector index of a bit vector entry within a vector of bit vectors can be used to implicitly encode supplementary information, such as the number of words in the field or data partition (e.g., when processing statistics in parallel across multiple data partitions) in which the value appears. Explicit supplementary information can be specified in additional fields associated with the bit vector or with a bit vector entry within a vector of bit vectors. This supplementary information can be used to distinguish between sets of records containing the value for later use.

The example of Figure 2A describes the operations performed by the analysis module 106 on one or more data sets from the data source 102 during the data analysis process, as well as the data received and generated during the process. Figure 2B is a flow chart of the process. Referring to Figures 2A and 2B, the analysis module 106 performs an index operation 200 to ensure that each record in each data set 201 to be analyzed has an index value, which provides a clear location for each record that can be referenced by the location information to be generated. For example, the index value of a particular data set can be an increasing integer (e.g., starting from 1 and increasing by 1 each time) assigned to each record based on the number of rows in the table, the position in the delimited file, the storage address, the primary key value, or any other unique attribute of the record. The assigned index value can be explicitly added to each record to provide an index data set 203, for example, by adding the value as a field for each record to the original data set of the data source 102, or by storing it as a new data set in the data source 102 or the analysis data storage 110. In the case where the original dataset already includes a field that can be used as an index, the indexing operation 200 can be skipped or performed only to verify the ability of the field to be used as an index. The indexing operation 200 can include generating an index map that provides a correspondence between the index of one dataset and the index of another dataset, as described in detail below.

The profiling module 106 performs a statistical operation 205 that computes statistics with positional information for each selected set of domains. In this example, each domain is a single field. Thus, in this example, the result of the statistical operation 205 is a plurality of statistical data sets 207, each for a particular field of a particular dataset. Each dataset can have a set of fields already designated for profiling, or all fields of each dataset can be profiled by default. In other examples, a domain can be a fragment of a field, or a combination of multiple fields or field fragments. Each statistical data set (also referred to as a "statistic") for a particular domain contains a list of entries, including a count of unique values occurring within the domain, a count of the number of records in which the particular value occurs, and associated positional information regarding the occurrence of the particular value. In some embodiments, this count is not explicitly included in the statistic because it can be derived from the positional information if needed (e.g., the sum of the digits in the bit vector locating the records in which the value occurs can yield the number of records in which the value occurs). In some embodiments, the profiling module 106 accumulates additional information to augment the positional information, such as information that demonstrates or characterizes the location of the value within the domain.

The profiling module 106 receives input (e.g., user input) specifying a desired multi-domain data profiling result, which may be received at some time after generating the statistical data set 207. The input also specifies (explicitly or implicitly) the multiple domains involved in the calculation. To calculate the multi-domain data profiling result, the profiling module 106 selects a statistical set 209 for each field of a particular domain. One type of multi-domain data profiling result is a "combined statistic," which specifies the unique tuple values that appear in each field of the same record (i.e., at the same index). Other types of multi-domain data profiling results include functional dependency results or segmentation results, each of which begins with the calculation of a combined statistic, as described in more detail below.

Optionally, the profiling module 106 can sort the collection 209 so that the statistics and the statistical entries within each statistic are in an order that makes the calculation of current or future multi-domain data profiling results more efficient. In this example, each statistic is sorted (210) so that the entries are sorted in descending order by the number of occurrences, so that the most common values are ranked first. Additionally, in some embodiments, the entries can be further (sub-)sorted by position information, so that a value that first appears earlier than another value with the same number of occurrences in the data set appears earlier in the sorted statistic. This allows the statistical values to have a very clear ordering because, for two different values, the first occurrence (i.e., the smallest record index) of one value must be different from the first occurrence of the other value. The statistics collection 209 can also be sorted (220) by the number of unique values in each statistic and further sorted by the count of the most common values in descending order. This classification produces a sorted set of classification statistics 225, where shorter statistics (in terms of the number of outliers) appear earlier. For two statistics with the same number of outliers, the one with the larger count of the most common value appears earlier. For multi-domain data classification results corresponding to functional dependencies, fields with relatively low outlier counts are more likely to be functionally dependent. As the number of outliers increases, the field is more likely to represent a unique attribute, such as a primary key, or an attribute with a low number of identical values, which may be spuriously correlated with other values. By sorting shorter statistics before longer statistics, fields more likely to be relevant to functional dependency analysis are processed sooner. In some cases, a pause condition can even be identified, allowing calculation of the result without further processing of all entries in all statistics in classification set 225. For multi-domain data profiling results other than functional dependencies, it may be necessary to process the entire classification set 225 to calculate the result, in which case classification may not be necessary. In this example, classification 210 occurs before classification 220, but in other examples, classification 220 may occur before classification 210.

The profiling module 106 performs a combined statistics generation operation 230, in which the statistics entries in the sorted set 225 are sequentially read and combined with information from other statistics entries to generate combined statistics 240. To efficiently combine information from different statistics entries, the profiling module 106 uses location information to locate records in the indexed dataset 203, which is closely related to the generation of combined statistics 240, as described in detail below. Multiple paths of the combined statistics generation operation 230 can be performed. For example, if a combined statistics 240 tuple includes values from more than two fields, then when constructing statistics entries within combined statistics 240 for that tuple, the profiling module 106 may perform a pairwise combination of the two fields in a first path. In subsequent paths, the statistics entries may be combined with any entries in the previously formed version of combined statistics 240.

Referring to FIG3 , an example of a profiling process is described. A source dataset 300 is indexed (in index operation 200 ) to provide an A index dataset 310 . A source dataset 300 has three fields, corresponding to the three illustrated columns, and six records, corresponding to the six illustrated rows. The first record in the dataset has values "d," "q," and "d8," corresponding to the three fields, respectively. A surrogate key field, a continuously increasing integer value, is added to the beginning of the record to serve as a positional index to uniquely identify each record in A index dataset 310 . In this example, profiling module 106 calculates a sorted A statistics set 320 for the first two fields of A source dataset 300 . The first field (i.e., the first column) is named "g," the second field (i.e., the second column) is named "f," and the name of the third field is irrelevant in this example because it is not profiled. Thus, there are two statistics in the A statistics set: one for the g field (referred to as g-statistics) and the other for the f field (f-statistics). Each statistic in the A statistics set 320 includes a sorted list of entries, where each entry includes a value, a count of the number of times the value appears, and a record index vector representing the location information of the value. Thus, for the f-statistic, the first statistic entry described in this example by the space-delimited string "q 3 A[1,4,5]" indicates that the value "q" appears three times in the A source dataset 300, appearing in the first, fourth, and fifth records of the A index dataset 310, represented by the vector A[1,4,5]. The statistics for each field are sorted in descending order by the value occurrence count and further sorted in ascending order by the first index in the location information vector. The statistics in the A statistics set 320 are also sorted by the number of unique values in each statistic, with the shortest statistic placed first. In this example, the statistics for the f field are placed before the statistics for the g field.

The profiling module 106 performs a combined statistics generation operation to calculate a combined statistics 330. In this example, a tuple in the combined statistics is a pair of values. In this example, the first entry in the combined statistics, represented by the space-delimited string "g f d q 2 3 2 A[1,4]", indicates that the first field of the pair is "g", the second field of the pair is "f", the first field value is "d", the second field value is "q", the first value occurs twice, the second value occurs three times, and there are two records in which the first field has the first value (i.e., the g value of "d") and the second field has the second value (i.e., the f value of "q"). These records are the first and fourth records in the A-indexed dataset 310, represented by the vector "A[1,4]". Subsequently, the combined statistics 330 can be used to calculate various data profiling analysis results, as described in detail below.

In some embodiments, results based on combined statistics can be graphically displayed on the user interface, such as the functional dependency results 340 in the above example. Each circle contains a unique value, located below the labels of the fields "g" and "f", and the count of the value is displayed next to the circle (to the left of the g field and to the right of the f field). Each directed edge between the circles indicates a pair of values at both ends, and the count above the edge is the number of records that share this pair of values. From the different counts, the associated evaluation of the individual value and field pairs can be determined and displayed by the analysis module 106. In this example, the analysis module 106 displays the evaluation as "g determines f".

In some embodiments, the combined statistics generation operation 230 can generate combined statistics for pairs of unique values that appear together (i.e., are located in the same record) in two fields without forming a Cartesian product of the unique values that appear in the independent statistics of the fields. The Cartesian product can be used to calculate the combined statistics, for example, obtaining the position information of all pairs of values formed from the Cartesian product, and calculating the intersection of the relevant position information to locate records that share both values. However, the process of using the entire Cartesian product may be ineffective because the position information of many pairs may not overlap. The flowchart of Figure 4 and the schematic diagram of Figure 5 describe steps that can be used for the combined statistics generation operation 230, which can effectively identify and combine those pairs that do have overlapping position information and avoid pairs whose position information does not overlap. In this example, the position information can be represented and described by a record index vector, but other methods of representing position information can be used to calculate the vector. For example, for the f-value position information "f-A[]" and the g-value position information "g-A[]", the intersection of "f-A[]" and "g-A[]" can be obtained. Both vectors are represented by bit vectors, and logical "AND" operations are performed on the bit vectors respectively.

The steps in the flowchart of FIG4 begin after the statistics set 320 has been prepared, as described above, and iteration is performed on the classification entries of the first statistics (in this case, the f-statistic) for the fields f and g. The parsing module 106 reads (400) the next statistics entry of the f-statistic (i.e., the first statistics entry for the first iteration). From the position information associated with the f value of the current entry, the A index data set 310 is searched (410) for the first record in which the value appears, to find the matching g value that appears in the g field of the record. The parsing module 106 retrieves (420) the position information from the g-statistic associated with the g value. The resulting g-value position information (g-A[]) is combined with the f-value position information (f-A[]) to store (430) information identifying all records that share the pair (f-A[]' and 'g-A[]) and to store (440) information for updating the position information for the remaining set of records that have the current f-value but a different g-value (f-A[] = f-A[]' and '(not g-A[])). The paired values are written (450) to the combined statistics 330. The position information of the remaining set is checked (460) to determine if it is empty. If not, the first record in the remaining set is consulted (410) to find another g-value that is paired with the current f-value from the A index data set 310. If the position information of the remaining set is empty, the next statistic entry is read from the f-statistics for another iteration. After all entries in the f-statistics have been read and processed through a complete iteration of this process step, the combined statistics 330 is complete.

FIG5 shows an example of the program of FIG4 , with arrows indicating the order in which the analysis module 106 performs operations until the point at which the partially completed combined statistics 330 ′ is reached. The statistical entries in the f statistics within the A statistics set 320 are considered sequentially, starting with the first entry with an f value of “q”, which is the most common f value based on the previous classification. The first element “l” in the position information vector is used to look up (522) the g field value of the corresponding record in the A index data set 310. In this example, the g field value in the corresponding record (i.e., the record at index position 1) is “d”. The g statistics entry with this value “d” is searched to retrieve all the record sets with the value “d”, which are represented by the position information vector. The position information vector for the f value “q” is compared with the position information for the g value “d”, thereby forming the position information for two record sets: a record set 527 with paired values “q” and “d” (g and f); and a record set 528 with the value “q” but not the value “d” (f and non-g). The position information of the shared values is stored as a vector of appropriate entries in the combined statistics 330' (529). In this example, the entries in the combined statistics have the source of each value, the value and its statistical count, the position information of all records that contain both values, and the number of such records. The entry "g f d q 2 3 2 A[1,4]" indicates that the g value "d" occurs 2 times, the f value "q" occurs 3 times, and there are 2 records with both values, corresponding to position indices 1 and 4.

The parsing module 106 processes the remaining set of records 528 with the value "q". The first (and only) element "5" of the position information vector is used to look up (540) the g field value of the corresponding record in the A index data set 310, which obtains the value "b" from the g field. The g statistics entry with the value b is looked up (544) to obtain the position information A[5], which is compared with the set 528. The intersection of these sets is calculated (546) and stored in the appropriate entry of the combined statistics 330'. The difference between the sets is null in this example, but if it is not, the program is iterated to find other values of the g field that are paired with this particular value "q" of the f field. When the set of records with the f value "q" is exhausted, the program moves to the next entry in the f statistics and repeats the process.

6A and 6B , the analysis module 106 can perform the process steps of determining the correlation (functional dependency) between paired field values and expanding the combined statistics to include a correlation score that quantifies the functional dependency results. As described above, the combined statistics of the paired fields are calculated (600) based on the individual statistics of the fields, and the paired fields are analyzed for potential functional dependencies. For each value in each pair of values included in the entry of the combined statistics, a "correlation score" is calculated (610), which represents the ratio of the number of records with that paired value ("pair count") to the number of records with that value ("value count"). The analysis module 106 stores the correlation score (in this example, "1" and "2/3") in the entry to generate the expanded combined statistics 615. For example, the combined statistics entry "g f d q 2 3 2 A[1,4]" indicates that in the A index data set 310, there are 2 records with the field g value d, 3 records with the field f value q, and 2 records with the paired value "d q" with indexes 1 and 4. The g-value "d" (paired with "q") has a correlation score of 2/2 = 1, while the f-value "q" (paired with "d") has a correlation score of 2/3.

The correlation score for each value is compared to a threshold to determine (620) which values are correlated at that threshold. For example, if the correlation score exceeds a threshold of 0.95, fewer than 5 out of 100 examples have a value that is different from the current value. Here, "d" is correlated with "q" at a threshold of 0.95, but not vice versa: if the g value is "d", the corresponding f value is determined to be "q", but if the f value is "q", the probability that the corresponding q value is "d" is only 2/3.

The total number of records (in a field) that are correlated at a given threshold can be counted (630) and divided by the total number of records to determine (640) the fraction of records in the entire data set that are correlated at the given threshold. If the fraction exceeds a second field correlation threshold, the entire field can be considered correlated with the other field. In some embodiments, the number of records contributing to determining field correlation can exclude records with a value that has a lower number of instances than the threshold, or report correlations based on the likelihood that the value is erroneous. This is because if the number of instances is too small, the correlation may be accidental or insignificant, such as when there is only one instance where a value is correlated with its paired value.

Repeat the field association calculation for other fields to determine the fraction of records associated in the other direction. In this example, all g values are correlated with f values one by one, so that the total number of associated records is 6. The total number of records is 6, and the record association score is 6/6 = 1. The conclusion is that g determines f: knowing the g value ensures that the corresponding f value (at the field association threshold) is known. Conversely, if no f value exceeds the association threshold, the f field is not associated with the g field.

7 , an edge drill-down (700) is performed from the functional dependency result 340 to the A-query result 710 (e.g., based on a user's interaction with the illustrated result 340 in a graphical user interface) to display more detailed information related to the records, which are represented in the illustrated result 340 by edges indicating the pairing values that appear in those records. The pairing values "d q" represented by the edges are looked up (725) in the combined statistics 330 (which is the same as the combined statistics 330 sorted by frequency of occurrence and further sorted by the first index of position information) to obtain the position information for the pair. The position information is then used to extract (735) the relevant records from the A-index dataset 310. These records are displayed (745) in the A-query result 710.

In the aforementioned example, the correlation between two fields (g and f) in the same dataset was calculated. For the calculation of the correlation between two fields in different datasets linked by a key field, see Figures 8A and 8B. Source dataset A 800 and source dataset B 820 each have three fields, sharing a common key field. The key value of this shared key field is not necessarily unique. However, the key value of the key field is used to link corresponding records in the two datasets via the same key value in their respective key fields. A unique identifier for each record in source dataset A 800 (called A-record_id) is added as a field to each record, thereby generating index dataset A 810. Similarly, a unique identifier for each record in source dataset B 820 (called B-record_id) is added as a field to each record, thereby generating index dataset B 830. Index map 840 links each A-record_id to the key value of the key field in the same record. Therefore, index map 840 is a copy of the first two columns of index dataset A 810. The index map 840 may be stored separately from the A-index dataset 810 , for example, in a file in the profile data storage 110 .

In this example, the key field is the primary key of the A source dataset 800 (shown in the first column of the A source dataset 800 in Figure 8A) and the foreign key of the B source dataset 820 (shown in the second column of the B source dataset 820 in Figure 8A). The A-record_id value can be selected to map to its key field (rather than using the B-record_id to map to its key field) because the key field is the primary key. However, the datasets do not necessarily need to have this primary key/foreign key relationship as long as a field in each dataset is designated as the key field. The index map 840 is useful because there are duplicate primary key values in the A dataset, such as in this example where both datasets have duplicate key field values in two different records. Using the index map 840, the analysis module 106 generates a new version of the B index dataset 830, which has a new field containing the A-record_id value so that the two datasets have a common reference frame to determine location information. To do this, the parsing module 106 compares the key field values in the B-index dataset 830 with the key values in the index map 840 to find the number of matches with the corresponding A-record_id values. In this example, one record in the B-index dataset 830 (with the foreign key value k4) matches two different A-record_id values. When the A-record_id is added to the B-index dataset 830 record to generate the B/A index dataset 850, the parsing module adds (847) two corresponding records (one with "A4" added to the index and the other with "A6" added to the index). The other records of the B-index dataset 830 match a single A-record_id value in the index map 840, so that each of them corresponds to a single record added to the B/A index dataset 850, with the corresponding A-record_id value added to the index.

Referring now to Figure 8B, an A-statistic 860 is calculated for the third field of the A index dataset 810, with location information referenced by the A-record_id value (first field), and a B-statistic 870 is calculated for the fifth field of the B/A index dataset 850, with location information also referenced by the A-record_id value (first field) added using the index map 840. The location information of the two statistics is combined as described above, thereby calculating a combined statistic 880 for the field pairs represented by these statistics (fields from the A-statistic are labeled "A" and fields from the B-statistic are labeled "B"), which is then used to display the functional dependency results 890, concluding that the A and B fields are uncorrelated.

9 , a node drill-down (900) is performed from the functional dependency result 890 (e.g., based on a user's interaction with the result 340 shown in the graphical user interface) to display more detailed information related to the record represented by the value shown in the node. The node displaying the value "p" from the B field is selected, and the records corresponding to this value are extracted in both the A source dataset 800 and the B source dataset 820 and displayed in the node query result 910. First, the p value is searched (915) in the combined statistics 880 to find each matching entry (containing the B field as "p"), thereby achieving a drill-down. The position information of these entries is combined to generate the position information A[1, 3, 4, 6] (relative to the A-record_id value). Each of these positions is then searched in the A index dataset 810 and the B/A index dataset 850 to extract any records at these positions. The extracted records in the A index dataset 810 are displayed (935) in the node query result 910, marked with "A". The extracted records in the B source dataset 820 are compared to find any records with the same B-record_id value, and duplicates are removed (945) so that only one is displayed in the node query result 910. In this example, records with A-record_id values of A4 and A6 have the same B-record_id value of B2. By having multiple A source dataset 800 records corresponding to a single B source dataset 820 record, duplicate key field values in the A source dataset 800 records are displayed in the node query result 910.

FIG10 illustrates an example of calculating statistics using a segmentation approach. A source dataset 100 has three fields: f, g, and h. A unique identifier (referred to as record_id) for each record in source dataset 100 is added as a field to each record to generate index dataset 1010. A sorted set of statistics 1020 is calculated, which includes positional information for each of the three fields. In some embodiments, system 100 can enable a user to formulate queries to answer business questions, such as, "What is the data binning (i.e., distribution of values) for the h field, obtained by segmenting the combination of the f and g fields to include specific values?" For example, the f field may represent gender, with records having the possible values "f" or "m," respectively; while the g field may represent "foreign" or "domestic," with records having the values "p" or "q," respectively. Segmenting the data binning (e.g., expressed as statistics) for the f and g fields can help answer questions such as, "What is the most common value for the h field for a "foreign male" or "domestic female"?"

The set 1020 can be used to calculate the segmented bins without processing all records in the A source data set 1000. The segmented statistics 1030 can be constructed into combined statistics using the f field and g field statistics and the above-mentioned process steps of calculating combined statistics. In some embodiments, each entry of the segmented statistics 1030 is assigned a unique value (called segment_id) to facilitate identification of the segment associated with the entry. The process steps of calculating combined statistics are again used to form segmented combined statistics 1040, which is a combination of the h field statistics from the A statistics set 1020 and the segmented statistics 1030. For example, first extract the s1 entry of the segmented statistics 1030, read the relevant energy position information A[1,4], and calculate the h-s1 entry of the segmented combined statistics 1040. In the statistics, search for the first element "1" of the position vector for the h field of the A statistics set 1020 to find the h field value "d" and the corresponding position information A[1,4]. Compare the position information A[1,4] of the entry labeled s1 in segment statistics 1030 with the position information A[1,4] of the entry d in the h statistics. Because all elements of the position information between these two entries match, the resulting combined statistics entry vector for segment s1 is "d 2 A[1,4]," with no remaining position entries in segment s1. This indicates that segment s1 consists of only a single h field value, d. Combined statistics are continuously constructed using other segment values combined with h statistics records to achieve segmented combined statistics 1040.

FIG11 shows an example of a segmented cube calculation. When segmentation is based on a combination of multiple field values, as in the example of FIG10 , a segmented cube can be constructed in which the statistics of the segmentation are reassembled into statistics where the segmentation involves each combination of fewer fields. For the example of FIG10 , the calculated segmented combination statistics 1040 represent, for example, the segmentation of “foreign males” (i.e., segment s4) and “domestic males” (i.e., s1). The user can request that the segment “foreign” or “males” be profiled. For a new segmentation, rather than returning directly to repeat the calculation of FIG10 , the previous segmentation results are combined with the h-statistic to calculate other entries in the “segmented cube”, as described below.

To form segment cube 1020, each subset of the original segment fields is first formed. In this example, full segmentation is performed based on two segment fields, f and g. The two field sets form two subsets: one consisting only of f, and the other consisting only of g. Each set is called a segment cube field. If the original segment field consists of three fields, f, g, and h, the segment cube field can be the set {f, g}, {f, h}, {g, h}, {f}, {g}, and {h}. That is, the segment cube field is a member of all non-empty subsets of the segment field.

An entry in segment cube 1120 consists of each unique value (or combination of values) associated with each segment cube field. In some embodiments, for each value of a segment cube field, the set of segments containing that value is determined and used as segment location information in a data structure to store segment cube 1120 and the count of the segment. Another alternative approach is to merge each corresponding entry in segment statistics 1030 (referred to as a segment-statistics entry) and combine the location information with the record_id added to the A-index dataset 1010. Using segment location information (i.e., location information relative to segment_id) rather than A-location information (i.e., location information relative to record_id) is more efficient because there are typically far fewer segments than records, so their location information is more compact. In some embodiments, a field is added to each entry in segment cube 1120 to identify the entry.

In this example, the segment cube field f has the value f in segments s1 and s2, so the associated segment position information is S[s1,s2]. This forms the segment cube entry "c1f f 2 S[s1,s2]." Here, c1 is the segment cube entry's tag, the first f is the segment cube field, and f is its value. This value appears in both segments, indicated by the position information S[s1,2]. Alternatively, the segment cube field g has the value "q" in segments s1 and s4, so the associated segment position information is S[s1,s4]. This forms the segment cube entry "c4g q 2 S[s1,s4]."

The segmented combined statistics 1040 are combined with the segmented cube 1120 to form the segmented-cube A statistics set 1150 through the following process steps. Each entry in the segmented cube 1120 contains segment location information, which is used to determine which segment contains the associated segmented cube field value. The merging of the set of segmented statistics entries in each reference segment gives a set of statistics entries with the segmented cube field value. For example, the segmented cube entry c1 has segment location information S[s1,s2]. The set of statistics entries for the s1 and s2 results in the segmented combined statistics 1040 are merged to produce the c1 segmented results. The s1 segment consists of a single entry "d 2 A[1,4]", while the s2 segment consists of two entries "a 1 A[2]" and "e 1 A[6]". The merging of these entries into a set of all three entries forms the c1 segment of the h statistics for the segmented cube A statistics set 1150. As can be seen from the segmented cube, the c1 segment consists of records whose f field has a value of f. Therefore, the c1 segment of the h-statistics is the h-statistics segment whose f field has the value f. This can be verified by examining the A-statistics set 1020 in Figure 10. The f field of record A[1, 2, 4, 6] has the value "f", while the h field of record A[1, 4] has the value "d", the h field of record A[2] has the value "a", and the h field of record A[6] has the value "e".

If a value appears in more than one segment, the resulting A position information is obtained by combining the A position information of each segment. This does not occur in the illustrated segment cube 1120, but if the segment position information of the segment cube entry is S[s2,s4], then since the h value of segments s2 and s4 is both "e", the A position information of the h value "e" in the segment cube statistics is A[3,6], which is the combination of A[6] from segment s2 and A[3] from segment s4.

A segment cube entry such as S[s2,s4] is an example of a segment cube entry within a broader segment cube that is formed by combining segments rather than simply combining fields. In some embodiments, such segment combinations are permitted. In the entry, the permitted segment field values correspond to the values associated with each segment of the selected segment combination. In this example, the segment cube entry S[s2,s4] corresponds to a segment where the value of the f-g field is either "fp" or "m q." This allows for the formation of complex segments where conditional combinations of fields and field values are permitted.

Multi-field validation rules can be calculated from statistics with location information without the requirement to process all records in the original data set. Multi-field validation rules apply conditions to two or more field values, and a record must meet the conditions at the same time to be considered valid. Records that do not meet the conditions are considered invalid. An example of a multi-field validation rule is: if the f value (gender) is "f", then the g value (foreign/domestic) must be "p". In some embodiments, the validation rule is expressed in a negative form, that is, a rule for a combination of two field values is given, and if it is met, the record is deemed invalid. In this example, the rule for determining invalid records can be: if the f value is "f" and the g value is not "p", then the record is invalid.

The data quality report may include the number of valid and invalid records for one or more validation rules. If validation rules are established before the initial statistics are performed, the rules can be tested in the process of collecting statistics and performing statistics on the relevant valid and invalid records. However, validation rules are usually proposed after the initial statistics in response to values and value combinations that are not covered by the statistics. In this case, instead of re-performing statistics and applying new validation rules, statistics with position information are used to determine valid and invalid records without the need to recalculate the statistics. Since multi-field validation rules are expressed as conditional combinations of field values, the statistical entries corresponding to each value in the validation rule can be combined, typically using Boolean operations on the position information to check the rule. Any value combination that is deemed invalid can be marked as invalid and counted in the invalid record set. Position information can also be used to drill down to determine specific records that are either invalid or valid under the validation rules.

With respect to the following validation rule, if the value of f is "f", the value of g must be "p". The A statistical set 1020 can be used to calculate Boolean 'f = "f" and g = "p"'. The position information of the record with f = "f" is A[1,2,4,6], and the position information of the record with g = "p" is A[2,3,6]. A valid record can be formed by the intersection A[2,6] of these two sets of position information. The invalid record is the invalid record located by the vector A[1,4] obtained by the operation of Boolean 'f = "f" and g! = "p"'. The obtained position information can then be used to extract valid or invalid records. For example, records 2 and 6 can be extracted from the A index file 1010, and two records with f = "f" and g = "p" can be returned.

The above techniques can be implemented using a computing system that executes appropriate software. For example, the software can include one or more computer programs that are run on one or more programmed or programmable computing systems (which can have various architectures, such as distributed, client/server, or grid), each including at least one processor, at least one data storage system (including volatile memory and/or non-volatile memory and/or storage elements), and at least one user interface (using at least one input device or port to receive input and at least one output device or port to provide output). The software can include one or more modules of a larger program, for example, providing services related to the design, construction, and operation of data flow graphs. The modules of a program (e.g., elements of a data flow graph) can be data structures or other organized data that conform to a data model stored in a data repository.

The above-mentioned data analysis method can be implemented using a computer system that executes appropriate software. For example, the software may include processes in one or more computer programs executed on one or more programmed or programmable computing systems (which may have various architectures, such as distributed, client/server, or grid formats), each computing system including at least one processor, at least one data storage system (including volatile and/or non-volatile memory and/or storage elements), and at least one user interface (for receiving input using at least one input device or port, and for providing output using at least one output device or port). The software may include one or more modules of a large program, for example, the large program provides other services related to the design, configuration, and execution of data flow graphs. The modules of the program (e.g., elements of a data flow graph) may be implemented as data structures or other organized data that conform to a data model stored in a database.

The software can be provided on a tangible permanent storage medium (e.g., a medium that can be read by a general or special computer system or device) such as a CD-ROM or other computer-readable medium, or delivered (e.g., encoded into a transmission signal) to a tangible permanent medium of a computer system that executes the software via a communication medium of a network. Some or all of the processing can be performed on a dedicated computer, or performed using dedicated hardware such as a coprocessor or a field programmable gate array (FPGA) or an application-specific integrated circuit (ASIC). The processing can be implemented in a distributed manner in which different computing parts specified by the software are performed by different computing elements. Each such computer program is preferably stored in or downloaded to a computer-readable storage medium (e.g., a solid-state memory or medium, or a magnetic or optical medium) of a storage device that can be read by a general or special programmable computer, for configuring and operating the computer when the computer reads the storage medium or device to perform the processing described herein. It is also contemplated that the system of the present invention can be implemented as a tangible permanent storage medium configured with a computer program, wherein the storage medium so configured causes the computer to operate in a specific and predefined manner to perform one or more processing steps described herein.

Several embodiments of the present invention have been described. However, it should be understood that the foregoing description is intended to illustrate, not to restrict, the scope of the present invention, which is defined by the following claims. Therefore, other embodiments are also within the scope of the following claims. For example, various modifications may be made without departing from the scope of the present invention. Furthermore, some of the steps described above may be performed in an unrelated order and, therefore, may be performed in an order different from that described.

Claims (17)

1. A method for profiling data stored in at least one data storage system, the method comprising: Access at least one set of records stored in the data storage system via an interface connected to the data storage system; and The record set is processed to generate result information, the result information representing values appearing in one or more specific fields of the record set, the processing including: For the first set of outliers appearing in the first set of one or more fields of the records in the set, The corresponding location information is generated, which identifies all records containing each outlier in the first set of outliers. For one or more fields in the first group, a corresponding list of entries is generated. Each entry identifies an outlier from the outliers in the first group, along with the location information of that outlier. For a second group of one or more fields in the set that are different from the first group of one or more fields, a corresponding list of entries is generated. Each entry determines a unique value from the unique values appearing in the second group of one or more fields. At least in part, the following is used to generate result information characterizing values appearing in one or more specific fields of the record set: at least one record in the record set is located using positional information of at least one value appearing in at least one value in the first set of one or more fields; and at least one value appearing in the second set of one or more fields of the located record is determined. For the second set of outliers, corresponding location information is generated, which identifies all records where each outlier occurs for each outlier in the second set of outliers. Wherein, for a list corresponding to one or more fields of the second group, each entry identifying an outlier from the second group of outliers includes the location information of that outlier, and The processing further includes: for a set of outlier pairs, generating corresponding location information, wherein a first value in each pair appears in one or more fields of the first group of the record, and a second value in each pair appears in one or more fields of the second group of the record, the location information identifying all records in which the outlier pair appears for each outlier pair. 2. The method of claim 1, wherein each entry further identifies a count of the number of records in which a particular value appears in one or more sets of fields. 3. The method of claim 2, wherein the processing further comprises classifying the entries in each list by means of the identified count. 4. The method of claim 1, wherein generating location information of a pair of outliers from the set of outlier pairs comprises: determining the intersection between location information of a first outlier from the first set of outliers and location information of a second outlier from the second set of outliers. 5. The method of claim 4, wherein determining the intersection comprises: using the location information of the first outlier to locate a record in the set, and using the located record to determine the second outlier. 6. The method of claim 1, further comprising: classifying a plurality of lists according to the number of outliers identified in the entries of each list, the plurality of lists including lists corresponding to one or more fields of the first group and lists corresponding to one or more fields of the second group. 7. The method of claim 1, wherein the process further comprises: For a set of outlier pairs, corresponding location information is generated, wherein the first value in each pair appears in one or more fields of the first group of records, and the second value in each pair appears in one or more fields of the second group of records, which are different from the one or more fields of the first group. The location information identifies all records in which each outlier pair appears. For the set of outlier pairs, a corresponding list of entries is generated, where each entry identifies an outlier pair and its location information from the set of outlier pairs. 8. The method of claim 1, wherein the location information identifies a unique index value for all records in which the particular value occurs. 9. The method of claim 8, wherein the location information is identified by storing a specific unique index value. 10. The method of claim 8, wherein the location information is identified by encoding a unique index value within the location information. 11. The method of claim 10, wherein encoding the unique index value comprises storing a bit at a location within a vector corresponding to the unique index value. 12. The method of claim 1, wherein the set comprises a first subset of records and a second subset of records, the first subset of records having fields including one or more fields of the first group, and the second subset of records having fields including one or more fields of the second group. 13. The method of claim 12, wherein the processing further comprises generating information that provides a mapping between: 1) a field index value of the first subset of records, which associates a unique index value with every record in the first subset of records; and 2) a key value of a field of the second subset of records, which associates a key value with every record in the second subset of records; wherein the key value associates a record in the second subset of records with a record in the first subset of records. 14. The method of claim 13, wherein the location information identifies a unique index value for all records in which an outlier occurs. 15. A computer-readable medium for storing a computer program for profiling data stored in at least one data storage system, the computer program comprising causing a computing system to perform the method as described in any one of claims 1-14. 16. A computing system for profiling data stored in at least one data storage system, the computing system comprising: An interface connected to the data storage system, used to access at least one set of records stored in the data storage system; and At least one processor is configured to process the record set to produce result information, the result information representing values appearing in one or more specific fields of the record set, the processing including: For the first set of outliers appearing in the first set of one or more fields of the records in the set, The corresponding location information is generated, which identifies all records containing each outlier in the first set of outliers. For one or more fields in the first group, a corresponding list of entries is generated. Each entry identifies an outlier from the outliers in the first group, along with the location information of that outlier. For one or more fields in a second group that are different from the first group of fields, a corresponding list of entries is generated. Each entry determines a unique value from the unique values appearing in the second group of fields. At least in part, the following is used to generate result information characterizing values appearing in one or more specific fields of the record set: at least one record in the record set is located using positional information of at least one value appearing in at least one value in the first set of one or more fields; and at least one value appearing in the second set of one or more fields of the located record is determined. For the second set of outliers, corresponding location information is generated, which identifies all records where each outlier occurs for each outlier in the second set of outliers. Wherein, for a list corresponding to one or more fields of the second group, each entry identifying an outlier from the second group of outliers includes the location information of that outlier, and The processing further includes: for a set of outlier pairs, generating corresponding location information, wherein a first value in each pair appears in one or more fields of the first group of the record, and a second value in each pair appears in one or more fields of the second group of the record, the location information identifying all records in which the outlier pair appears for each outlier pair. 17. A computing system for profiling data stored in at least one data storage system, the computing system comprising: A means for accessing at least one set of records stored in the data storage system; and Apparatus for performing the method according to any one of claims 1-14.