Attribute value information for a data extent

• US 10,713,254 B2
• Filed: 09/07/2017
• Issued: 07/14/2020
• Est. Priority Date: 08/08/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bodziony, Michal, Gaza, Lukasz, Gruszecki, Artur M., Kazalski, Tomasz, Skibski, Konrad K.
• Primary Examiner(s): Le, Hung D
• Application Number:
  US15/697,614
• Publication Number:
  US 20180039660A1
• Time in Patent Office: 1,041 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses

Abstract

The invention relates to a method, computer program product and computer system for providing attribute value information for a data extent having a set of data entries. The method includes: determining a reference string value of a data-extent-specific reference point based on symbol frequencies at each sequence position of attribute string values in a subset of the set of data entries; calculating a distance between each of the attribute string values in the subset and the reference string value of the data-extent-specific reference point resulting in a set of distances; determining for each of the attribute string values an attribute-string-value-specific minimum distance for any reference string value of the data-extent-specific reference point resulting in a set of attribute-string-value-specific minimum distances for the set of data entries; storing for the data extent the minimum distance and the maximum distance of the set of attribute-string-value-specific minimum distances as attribute value information.

Claims

1. A computer-implemented method for providing attribute value information for a data extent comprising a set of data entries, each data entry comprising an attribute string value of at least a first attribute, each attribute string value comprising a sequence of symbols, the method comprising:

determining for the first attribute at least one reference string value of a data-extent-specific reference point based on symbol frequencies at each sequence position of the attribute string values of the first attribute in a subset of the set of data entries, the resulting reference string value comprising a sequence of symbols;

determining for each of the attribute string values of the first attribute in the set of data entries an attribute-string-value-specific minimum distance for any reference string value of the data-extent-specific reference point resulting in a set of attribute-string-value-specific minimum distances for the set of data entries;

storing for the data extent the minimum distance and the maximum distance of the set of attribute-string-value-specific minimum distances as attribute value information for further use with query processing.

2. The method of claim 1, the determining of the reference string value comprising:

determining for each sequence position of the respective attribute string values a most frequently used symbol which is selected to be the symbol of the reference string value at the respective sequence position.

3. The method of claim 1, the subset being equal to the set of data entries and the set of attribute-string-value-specific minimum distances for the set of data entries being equal to the set of distances.

4. The method of claim 1, further comprising:

using an initial reference string value of the data-extent-specific reference point for the determining of the reference string value, the initial reference string value comprising a sequence of symbols, wherein for determining the reference string value the method further comprises;

calculating a distance between each of the attribute string values of the first attribute in the set of data entries and the initial reference string value of the data-extent-specific reference point resulting in the set of attribute-string-value-specific minimum distances for the set of data entries;

determining the largest distance comprised by the set of attribute-string-value-specific minimum distances;

selecting for the subset all attribute string values with an attribute-string-value-specific minimum distance equal to the determined largest distance;

determining the reference string value using the attribute string values of the subset by determining for each sequence position of the attribute string values of the subset a most frequently used symbol which is selected to be the symbol of the reference string value at the respective sequence position.

5. The method of claim 4, the initial reference string value comprising a sequence of symbols selected based on symbol frequencies at each sequence position of the attribute string values of the first attribute in the set of data entries.

6. The method of claim 1, the method further comprising repeatedly determining in a sequential order additional reference string values of the data-extent-specific reference point based on symbol frequencies at each sequence position of the attribute string values for the first attribute until a predefined termination criterion is satisfied, the determining of each of the additional reference string values comprising:

calculating a distance between each of the attribute string values in the subset used for determining the latest reference string value according to the sequential order and the respective latest reference string value;

checking for each attribute string value in the subset whether the respective calculated distance is smaller than the attribute-string-value-specific minimum distance for the respective attribute string value in the set of attribute-string-value-specific minimum distances, in case the calculated distance is smaller, updating the respective attribute-string-value-specific minimum distance of the set of attribute-string-value-specific minimum distances with the calculated distance;

determining an updated largest distance comprised by the updated set of attribute-string-value-specific minimum distances;

selecting for an additional subset all attribute string values with an attribute-string-value-specific minimum distance equal to the determined updated largest distance;

determining the additional reference string value using the attribute string values of the additional subset by determining for each sequence position of the attribute string values of the additional subset a most frequently used symbol which is selected to be the symbol of the respective additional reference string value at the respective sequence position.

7. The method of claim 6, the criterion being that all attribute-string-value-specific minimum distances comprised by the updated set of attribute-string-value-specific minimum distances are equal to or smaller than a predefined threshold distance.

8. The method of claim 6, the criterion being that a maximum total number of reference string values of the data-extent-specific reference point is reached.

9. The method of claim 1, for calculating distances between the attribute string values and the reference string value of the data-extent-specific reference point the method further comprising:

replacing in the attribute string values infrequently used symbols of a set of symbols from which the symbols of the attribute string values are selected by more frequently used symbols of the set of symbols.

10. The method of claim 1, for calculating distances between the attribute string values and the reference string value of the data-extent-specific reference point the method further comprising:

in case the number of symbols of one of the attribute string values is smaller than a predefined number of symbols adding to the respective attribute string value one or more symbols which are no elements of a set of symbols from which the symbols of the attribute string values are selected such that the predefined number of symbols is reached.

11. The method of claim 1, the calculated distances being minimum edit distances.

12. The method of claim 1, the minimum edit distance being calculated using one of the following metrics:

Hamming-Metric, Levenshtein-Metric, Damerau-Levenshtein-Metric.

13. The method of claim 1, in case a new attribute string value of the first attribute is added to the data extent, the method further comprising maintaining the data-extent-specific reference point at data extent level by:

calculating a distance between the new attribute string value and each reference string value of the data-extent-specific reference point;

determining the minimum distance of the distances calculated for the new attribute string;

checking whether the minimum distance of the new attribute string value satisfies one of the following two criteria;

being larger than the maximum distance or being smaller than the minimum distance of the attribute value information of the data extent;

in case the minimum distance of the new attribute string value satisfies one of the two criteria, determining the reference string values of the data-extent-specific reference point.

14. The method of claim 1, in case a new attribute string value of the first attribute is added to the data extent, the method further comprising maintaining the attribute value information for the data extent by calculating a distance between the new attribute string value and each reference string value of the data-extent-specific reference point;

determining the minimum distance of the distances calculated for the new attribute string;

checking whether the minimum distance of the new attribute string value is larger than the maximum distance of the attribute value information of the data extent, in case the minimum distance of the new attribute string value is larger replacing the maximum distance by the respective lager distance;

checking whether the minimum distance of the new attribute string value is smaller than the minimum distance of the attribute value information of the data extent, in case the minimum distance of the new attribute string value is smaller replacing the minimum distance by the respective smaller distance.

15. The method of claim 1, in case an attribute string value of the first attribute is deleted from the data extent, the data-extent-specific reference point being retained unaltered.

16. The method of claim 1, in case an attribute string value of the first attribute is deleted from the data extent, the method further comprising maintaining the attribute value information for the data extent by:

calculating the distance between each of the remaining attribute string values of the first attribute in the set of data entries and each of the reference string values of the data-extent-specific reference point;

determining for each of the remaining attribute string values the minimum distance of the calculated distances resulting in a reduced set of attribute-string-value-specific minimum distances;

determining the minimum distance and the maximum distance of the reduced set of attribute-string-value-specific minimum distances;

checking whether the determined maximum distance is smaller than the maximum distance of the attribute value information of the respective data extent, in case the determined maximum distance is smaller replacing the maximum distance of the attribute value information by the determined maximum distance;

checking whether the determined minimum distance is larger than the minimum distance of the attribute value information of the respective data extent, in case the determined minimum distance is larger replacing the minimum distance of the attribute value information by the determined minimum distance.

17. The method of claim 1 being performed for a plurality of the data extents resulting in a data-extend-specific reference point for each of the respective data extents.

18. The method of claim 17, the method further comprising processing a query, the query comprising a search value, processing the query comprising:

determining a reference-point-specific search distance between the search value and each data-extend-specific reference point resulting in a set of reference-point-specific search distances, each reference-point-specific search distance being the minimum distance between the search value and any reference string value of the respective data-extent-specific reference point;

determining a query-specific set of data extents of the plurality of data extents, the query-specific set of data extents comprising all data extents for which the reference-point-specific search distance of a data-extend-specific reference point of the respective data extend lies within the limits provided by the minimum reference-point-specific distance and the maximum reference-point-specific distance of the respective data-extend-specific reference point stored as attribute value information for the respective data extent;

searching for the search value in the data entries of the data extents of the query-specific set.