Extracting semantics from data

• US 8,239,750 B2
• Filed: 09/15/2009
• Issued: 08/07/2012
• Est. Priority Date: 09/15/2008
• Status: Active Grant

• Current Assignee: Erik Thomsen
• Original Assignee: Erik Thomsen
• Inventors: Thomsen, Erik
• Primary Examiner(s): Ries, Laurie
• Assistant Examiner(s): Mills, Frank D
• Application Number:
  US12/560,389
• Publication Number:
  US 20100169758A1
• Time in Patent Office: 1,057 Days
• Field of Search: 715/212
• US Class Current: 715/212
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174

Abstract

Embodiments of the invention convert data from atomic tuples found in data sources such as spreadsheets (e.g., raw numbers, words, and formatted dates) into semantically enriched schemas and associated tuples. In addition to the data content, visual content, such as font and background color, is also analyzed as a part of the interpretation process. Embodiments of the invention also provide methods of interacting with the raw data via the semantically enriched schema tuples.

Claims

1. A computer-implemented method comprising:

(A) converting a plurality of atomic tuples, representing contents of a plurality of cells stored in a grid, into a plurality of schema tuples, comprising;

(A)(1) assigning a plurality of catalog-defined types to the plurality of atomic tuples;

(A)(2) assigning a role of locator to a first subset of the plurality of cells based on the plurality of catalog-defined logical types; and

(A)(3) determining whether a locator tuple slice in the plurality of cells contains a missing value.

2. The method of claim 1, wherein (A) (3) comprises:

(A) (3) (a) extracting from the plurality of atomic tuples a locator tuple slice, wherein the locator tuple slice comprises a plurality of locator values, wherein the locator tuple slice forms a 1XN shape within the grid; and

(A) (3) (b) determining, based on at least some of the plurality of locator values, whether any empty cell in the locator tuple slice implicitly contains a missing value.

3. The method of claim 2, wherein (A) (3) further comprises:

(A) (3) (c) if any of the empty cells is determined to implicitly contain a missing value, then storing a record of the missing value.

4. The method of claim 1, wherein the grid comprises a spreadsheet.

5. The method of claim 4, wherein (A) (1) comprises assigning the plurality of catalog-defined logical types to the plurality of atomic tuples by matching contents of the plurality of cells with a library of symbols.

6. The method of claim 1, wherein (A) (1) comprises assigning the plurality of catalog-defined logical types to the plurality of atomic tuples by matching data types of the plurality of cells with a library of logical data types.

7. The method of claim 1, further comprising:

(B) identifying a second subset of the plurality of cells, wherein the second subset contains a plurality of values of a plurality of logical types;

(C) identifying a third subset of the plurality of cells, wherein the third subset contains a plurality of names of the plurality of values in the second subset, wherein the third subset and the second subset are disjoint.

8. The method of claim 6, wherein the grid comprises a spreadsheet.

9. The method of claim 8, wherein the spreadsheet comprises a tab, and wherein the method further comprises:

(D) before (C), identifying contents of the tab; and

wherein (C) comprises identifying the plurality of names based on the contents of the third subset and the contents of the tab.

10. The method of claim 7, wherein the grid is stored in a file, and wherein the method further comprises:

(D) before (C), identifying a name of the file; and

wherein (C) comprises identifying the plurality of names based on the contents of the third subset and the name of the file.

11. The method of claim 7, wherein (C) comprises identifying a name that refers to a plurality of cells in the second subset.

12. The method of claim 7, wherein (C) comprises associating a plurality of names contained in a plurality of cells in the third subset with a value of one cell in the second subset.

13. The method of claim 12, wherein (C) comprises associating a combination of the plurality of names contained in the plurality of cells in the third subset with the value of the one cell.

14. The method of claim 7, wherein the second subset is arranged in a rectangular shape, and wherein the third subset is outside the rectangular shape.

15. The method of claim 7, further comprising:

(D) determining whether the plurality of values are consistent with the plurality of names.

16. The method of claim 15, wherein (D) comprises determining whether the plurality of values are consistent with the plurality of names based on semantic values of the second subset.

17. The method of claim 15, wherein (D) comprises determining whether the plurality of values are consistent with the plurality of names based on logical states of the second subset.

18. The method of claim 1, wherein cells in a second subset of the plurality of cells are associated with a plurality of content names, and wherein the method further comprises:

(B) identifying, based on contents of the plurality of cells and the plurality of content names, a formula having at least one term including at least one of the plurality of content names; and

(C) associating the formula with at least one of the plurality of cells.

19. The method of claim 18, wherein (B) comprises identifying a formula having a plurality of terms, wherein each of the plurality of terms includes at least one of the plurality of content names.

20. The method of claim 18, wherein (C) comprises associating the formula with the plurality of cells.

21. The method of claim 18, wherein the contents of the plurality of cells comprise formulas in the plurality of cells.

22. The method of claim 18, wherein (C) comprises replacing a cell reference in a formula in one of the plurality of cells with a logical tuple corresponding to a cell referenced by the cell reference.

23. The method of claim 1, wherein a second subset of the plurality of cells represent a plurality of values associated with a content name, and wherein the method further comprises:

(B) identifying, based on contents of the plurality of cells in the second subset and the content name, a formula having terms including at least two of the plurality of content names.

24. The method of claim 23, further comprising:

(C) receiving a type identifier, wherein the type identifier identifies a particular logical type; and

(D) identifying a collection of general formulas that calculate values having the particular logical type.

25. The method of claim 1, further comprising:

(B) identifying a first formula in a first one of the plurality of cells;

(C) identifying a second formula in a second one of the plurality of cells; and

(D) generating a general formula based on the first formula and the second formula.

26. The method of claim 25, wherein (D) comprises, for the first formula in the first one of the plurality of cells:

(D) (1) identifying, in the first formula, a reference to a referenced cell in the plurality of cells;

(D) (2) replacing the reference with a logical tuple corresponding to the referenced cell.

27. A non-transitory computer-readable medium comprising computer program instructions executable by a computer processor to perform a method, the method comprising:

(A) converting a plurality of atomic tuples, representing a plurality of cells stored in a grid, into a plurality of schema tuples, the method comprising;

(A) (1) assigning a plurality of logical types to theplurality of atomic tuples;

(A) (2) assigning a role of locator to a first subset of the plurality of cells based on the plurality of logical types;

(A) (3) extracting from the plurality of atomic tuples a locator tuple slice, wherein the locator tuple slice comprises a plurality of locator tuples corresponding to a plurality of contiguous cells, from the plurality of cells, having the role of locator and forming a 1XN shape within the grid;

(A) (4) determining, based on values of at least some of the plurality of contiguous cells, whether any empty cells in the plurality of contiguous cells implicitly contain missing values;

(A) (5) if any of the empty cells are determined to implicitly contain missing values, then storing the missing values of the locator tuples of the locator tuple slice corresponding to the cells which are determined to implicitly contain missing values; and

(A) (6) converting the plurality of locator tuples into a plurality of logical schema tuples corresponding to the plurality of locator tuples, wherein each of the plurality of logical schema tuples comprises a type of the corresponding locator tuple and a value of the corresponding locator tuple.

28. The computer-readable medium of claim 27, wherein (A) (3) comprises:

(A) (3) (a) extracting from the plurality of atomic tuples a locator tuple slice, wherein the locator tuple slice comprises a plurality of locator values, wherein the locator tuple slice forms a 1XN shape within the grid; and

(A) (3) (b) determining, based on at least some of the plurality of locator values, whether any empty cell in the locator tuple slice implicitly contains a missing value.

29. The computer-readable medium of claim 28, wherein (A) (3) further comprises:

(A) (3) (c) if any of the empty cells is determined to implicitly contain a missing value, then storing a record of the missing value.

30. The computer-readable medium of claim 27, wherein the grid comprises a spreadsheet.

31. The computer-readable medium of claim 30, wherein (A) (1) comprises assigning the plurality of catalog-defined logical types to the plurality of atomic tuples by matching contents of the plurality of cells with a library of symbols.

32. The computer-readable medium of claim 27, wherein (A) (1) comprises assigning the plurality of catalog-defined logical types to the plurality of atomic tuples by matching data types of the plurality of cells with a library of logical data types.

33. The computer-readable medium of claim 27, wherein the method further comprises:

(B) identifying a second subset of the plurality of cells, wherein the second subset contains a plurality of values of a plurality of logical types;

(C) identifying a third subset of the plurality of cells, wherein the third subset contains a plurality of names of the plurality of values in the second subset, wherein the third subset and the second subset are disjoint.

34. The computer-readable medium of claim 32, wherein the grid comprises a spreadsheet.

35. The computer-readable medium of claim 34, wherein the spreadsheet comprises a tab, and wherein the method further comprises:

(D) before (C), identifying contents of the tab; and

wherein (C) comprises identifying the plurality of names based on the contents of the third subset and the contents of the tab.

36. The computer-readable medium of claim 33, wherein the grid is stored in a file, and wherein the method further comprises:

(D) before (C), identifying a name of the file; and

wherein (C) comprises identifying the plurality of names based on the contents of the third subset and the name of the file.

37. The computer-readable medium of claim 33, wherein (C) comprises identifying a name that refers to a plurality of cells in the second subset.

38. The computer-readable medium of claim 33, wherein (C) comprises associating a plurality of names contained in a plurality of cells in the third subset with a value of one cell in the second subset.

39. The computer-readable medium of claim 38, wherein (C) comprises associating a combination of the plurality of names contained in the plurality of cells in the third subset with the value of the one cell.

40. The computer-readable medium of claim 33, wherein the second subset is arranged in a rectangular shape, and wherein the third subset is outside the rectangular shape.

41. The computer-readable medium of claim 33, further comprising:

(D) determining whether the plurality of values are consistent with the plurality of names.

42. The computer-readable medium of claim 41, wherein (D) comprises determining whether the plurality of values are consistent with the plurality of names based on semantic values of the second subset.

43. The computer-readable medium of claim 41, wherein (D) comprises determining whether the plurality of values are consistent with the plurality of names based on logical states of the second subset.

44. The computer-readable medium of claim 27, wherein cells in a second subset of the plurality of cells are associated with a plurality of content names, and wherein the method further comprises:

(B) identifying, based on contents of the plurality of cells and the plurality of content names, a formula having at least one term including at least one of the plurality of content names; and

(C) associating the formula with at least one of the plurality of cells.

45. The computer-readable medium of claim 44, wherein (B) comprises identifying a formula having a plurality of terms, wherein each of the plurality of terms includes at least one of the plurality of content names.

46. The computer-readable medium of claim 44, wherein (C) comprises associating the formula with the plurality of cells.

47. The computer-readable medium of claim 44, wherein the contents of the plurality of cells comprise formulas in the plurality of cells.

48. The computer-readable medium of claim 44, wherein (C) comprises replacing a cell reference in a formula in one of the plurality of cells with a logical tuple corresponding to a cell referenced by the cell reference.

49. The computer-readable medium of claim 27, wherein a second subset of the plurality of cells represent a plurality of values associated with a content name, and wherein the method further comprises:

(B) identifying, based on contents of the plurality of cells in the second subset and the content name, a formula having terms including at least two of the plurality of content names.

50. The computer-readable medium of claim 49, further comprising:

(C) receiving a type identifier, wherein the type identifier identifies a particular logical type; and

(D) identifying a collection of general formulas that calculate values having the particular logical type.

51. The computer-readable medium of claim 27, further comprising:

(B) identifying a first formula in a first one of the plurality of cells;

(C) identifying a second formula in a second one of the plurality of cells; and

(D) generating a general formula based on the first formula and the second formula.

52. The computer-readable medium of claim 51, wherein (D) comprises, for the first formula in the first one of the plurality of cells:

(D) (1) identifying, in the first formula, a reference to a referenced cell in the plurality of cells;

(D) (2) replacing the reference with a logical tuple corresponding to the referenced cell.