Iterative generation of partial column schema

• US 9,104,707 B1
• Filed: 03/14/2013
• Issued: 08/11/2015
• Est. Priority Date: 03/14/2013
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Allen, Nicholas Alexander
• Primary Examiner(s): Phillips, III, Albert
• Assistant Examiner(s): Tran, Loc
• Application Number:
  US13/829,375
• Time in Patent Office: 880 Days
• Field of Search: 707/803, 707/809, 707/802
• US Class Current: 1/1
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/316 Indexing structures

Abstract

Systems and methods for iteratively generating a partial column schema indicative of semantic relationships in a corpus of key-value data are disclosed. A set of textual values is extracted from a pre-existing corpus of key-value data and potential column names are generated. Value reassignment and potential column pruning proceeds based on semantic fit quality, potential column utilization and random factors influenced by a decreasing system temperature.

Claims

1. A system comprising:

one or more storage devices comprising one or more database files configured to maintain a set of items comprising a key and one or more values associated with the key; and

one or more memories having stored thereon computer-readable instructions that upon execution cause the system at least to;

extract a set of values from the set of items;

generate a set of column names from the set of values;

assign a plurality of values from the set of items to a plurality of column names in the set of column names;

recursively reassign a first value to other column names in the plurality of column names based at least in part on a semantic fit quality and a utilization quality;

wherein the semantic fit quality is based at least in part on a solution constraint and semantic similarity of the first value to a column name to which the first value is assigned and the other values in the plurality of values assigned to the column name, the solution constraint based at least in part on the first value sharing a common key with a value from the set of items; and

wherein the utilization quality is based at least in part on a number of values currently assigned to the column name to which the first value is assigned and a comparison of the semantic fit quality to a prospective semantic fit quality.

2. The system of claim 1, the one or more memories having further stored thereon computer-readable instructions that upon execution cause the system at least to:

assign all values currently associated with the column name to which the first value is assigned to a different column name.

3. The system of claim 1, further comprising reducing a system temperature, wherein a random factor limited by the system temperature modifies one or more of the semantic fit quality and the utilization quality.

4. The system of claim 1, wherein the semantic fit quality is calculated based at least in part on a distance between related words in an ontology graph.

5. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by a computing device, cause the computing device at least to:

construct a first association between a first value extracted from a set of items and a first column name selected from a set of textual values that are ontologically related to one or more values in the set of items, the set of items comprising a key and one or more values associated with the key;

select the first value for association with a different column name based at least in part on a semantic fit quality for the first value; and

construct a second association between the first value and a second column name, the second column name selected by traversing a graph representative of ontological relationships between the first column name and one or more additional column names.

6. The non-transitory computer-readable storage medium of claim 5, wherein the set of textual values is generated using a dictionary of ontologically related values.

7. The non-transitory computer-readable storage medium of claim 5, wherein the traversing the graph is based at least in part on a utilization quality for the first column name.

8. The non-transitory computer-readable storage medium of claim 5, wherein the set of textual values comprises one or more of a synonym, antonym, or collective noun.

9. The non-transitory computer-readable storage medium of claim 5, having stored thereon instructions that, when executed by a computing device, cause the computing device to at least:

select the first value for association with the different column name based at least in part on a first random factor.

10. The non-transitory computer-readable storage medium of claim 9, having stored thereon instructions that, when executed by a computing device, cause the computing device to at least:

reduce a first system temperature, wherein the first system temperature limits the first random factor.

11. The non-transitory computer-readable storage medium of claim 5, having stored thereon instructions that, when executed by a computing device, cause the computing device to at least:

compute the semantic fit quality for the first value based at least in part on a solution constraint, the solution constraint indicative of the first value sharing a common key with another value in the set of items.

12. The non-transitory computer-readable storage medium of claim 5, having stored thereon instructions that, when executed by a computing device, cause the computing device to at least:

determine the semantic fit quality for the first value based at least in part on semantic similarity with a related value and semantic dissimilarity with an unrelated value, the related value associated with the first column name.

13. The non-transitory computer-readable storage medium of claim 5, having stored thereon instructions that, when executed by a computing device, cause the computing device to at least:

select the first column name for pruning, the selection based on a utilization quality and a second random factor, wherein pruning comprises removing all associations between the first column name and values extracted from the set of items.

14. The non-transitory computer-readable storage medium of claim 13, wherein the utilization quality is based at least in part on a comparison of prospective semantic fit qualities.

15. The non-transitory computer-readable storage medium of claim 5, wherein an initial association between the first value and the first column name is based on an identity function mapping the first value to a column name.

16. A method for grouping semantically related data stored in a database management system, the method comprising:

constructing a first association between a first value extracted from a set of items and a first column name selected from a set of textual values that are ontologically related to at least one value from the set of items, the set of items comprising a key and one or more values associated with the key;

selecting the first value for association with a different column name based at least in part on a semantic fit quality for the first value;

constructing a second association between the first value and a second column name selected by traversing a graph representative of ontological relationships between the second column name and one or more additional column names; and

determining that a utilization quality for the first column name is less than a utilization quality corresponding to the second column name.

17. The method of claim 16, wherein the traversing the graph comprises a directed random walk based at least in part on edge weightings.

18. The method of claim 16, further comprising reducing a system temperature, the system temperature influencing a degree of randomness.

19. The method of claim 16, wherein the utilization quality is based at least in part on a comparison of the semantic fit quality to a prospective semantic fit quality.

20. The method of claim 16, further comprising extracting the first value from the database management system and extracting one or more ontologically related values from a dictionary.

21. The method of claim 16, wherein traversing a graph is based at least in part on the utilization quality for the second column name.

22. The method of claim 16, further comprising:

calculating the semantic fit quality for the first value based on semantic similarity with a related value and semantic dissimilarity with an unrelated value, the related value associated with the second column name.

23. The method of claim 16, wherein a solution constraint is used to adjust one or more of the semantic fit quality, the utilization quality, and a branch of the ontological graph, the solution constraint calculated for a value based on associations between the value and other values sharing a common key with the first value.

24. A system comprising:

one or more storage devices comprising one or more database files configured to maintain a set of items comprising a key and one or more values associated with the key; and

one or more memories having stored thereon computer-readable instructions that upon execution cause the system at least to;

assign a first value corresponding to a value in the set of items to a first column name from a set of column names;

select the first value for reassignment, the selection based at least in part on a first degree of semantic similarity between the first value and other values currently assigned to the first column name;

determine a second degree of semantic similarity between the first value and other values currently assigned to a second column name; and

assign the first value to the second column name, the second column name selected for assignment based at least in part on the second degree of semantic similarity.

25. The system of claim 24, wherein the set of column names is generated based on semantic similarity with values in the set of items.

26. The system of claim 24, wherein the selection of the first value for reassignment is based at least in part on the first value sharing a common key with a value in the set of items.

27. The system of claim 24, wherein the selection of the first value for reassignment is based at least part on comparing the first degree of semantic similarity to a prospective degree of semantic similarity associated with prospectively assigning the first value to the second column name.

28. The system of claim 24, wherein a record of the assignment of the value to the first column name is retained for further evaluation.