Method and system for inferring a schema from a hierarchical data structure for use in a spreadsheet

• US 8,086,959 B2
• Filed: 01/06/2006
• Issued: 12/27/2011
• Est. Priority Date: 02/28/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rothschiller, Chad, McCormack, Michael J., Burke, Eoin, Lynch, Kelly J., Dumas, Roy E.
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Nazar, Ahamed I
• Application Number:
  US11/326,853
• Publication Number:
  US 20060117250A1
• Time in Patent Office: 2,181 Days
• Field of Search: 715/234, 715/212, 715/213, 715/215, 715/255, 707/E17.124
• US Class Current: 715/255
• CPC Class Codes: G06F 16/84 Mapping; Conversion

Abstract

A method and system are provided for inferring a schema from an electronic document containing hierarchical data for use in a spreadsheet application program. The electronic document containing the hierarchical data is received into an application program. The application program may be a spreadsheet application program. The format of the hierarchical data structure may be XML. The hierarchical data includes a set of nodes making up the structure of the hierarchical data. The nodes may be XML elements and attributes. The hierarchical data is then parsed to discover one of the nodes in the hierarchical data. Once the node has been discovered, content associated with the discovered node is saved to a memory location in the computer system. The content may include data associated with the discovered node and the type of data associated with the node. The hierarchical data is then parsed again to discover subsequent nodes until the content for all of the nodes has been saved to the memory location. Then a schema generator generates schema elements using complex rules based on the particular qualities of each discovered node for each discovered node until a schema is generated for the hierarchical data.

Claims

1. A method for inferring a schema from hierarchical data within an electronic document, comprising:

in an application program, receiving the electronic document containing the hierarchical eXtensible Markup Language (XML) data and determining from the electronic document that the hierarchical data within the electronic document does not reference a schema, wherein the hierarchical data includes one or more nodes;

(a) discovering one of the nodes in the hierarchical data;

(b) saving content associated with the discovered node when the node is not determined to be repeating;

(c) repeating tasks (a)-(b) until the content for each discovered node has been saved; and

generating the schema based on the content saved for each discovered node;

wherein generating the schema comprises writing a schema definition for each node that includes specifying a maximum occurrence of repeating nodes that are out of sequence as unbounded by checking for a repeating indicator and a sequence indicator, wherein the schema is an XML schema that provides the XML data a set of grammatical and data type rules that govern types and a structure of data that may be included in the electronic document.

2. The method of claim 1, wherein saving the content associated with the discovered node comprises:

determining whether the discovered node has previously been discovered;

if the discovered node has been previously discovered, then storing a first indicator indicating that the node is a repeating node; and

examining the content associated with the repeating node and updating a memory location with a data type of the repeating node; and

if the discovered node has not been previously discovered, then saving the content associated with the discovered node.

3. The method of claim 1, wherein the content comprises data associated with the discovered node, wherein the data includes information for locating the discovered node.

4. The method of claim 3, further comprising determining a data type for the data associated with each discovered node.

5. The method of claim 4, wherein determining a data type for the data associated with each discovered node comprises:

comparing the data associated with the discovered node to a list of known data types; and

determining the data type based on the list of known data types.

6. The method of claim 5, wherein determining the relationship between each discovered node prior to generating the schema comprises:

determining at least one hierarchical relationship among the discovered nodes by examining the content saved for the discovered nodes, wherein the at least one hierarchical relationship includes a parent-child relationship.

7. The method of claim 1, wherein the application program is a spreadsheet application program.

8. A computer system for inferring a schema from an electronic document containing hierarchical data comprising:

an application program that determines that the electronic document containing hierarchical data does not reference a schema;

a memory for storing the hierarchical data, wherein the hierarchical data includes one or more nodes;

a parser for receiving the hierarchical data from the memory and parsing the hierarchical data in the electronic document to discover the one or more nodes;

a logical memory module for;

(a) receiving one of the discovered nodes from the parser;

(b) determining content associated with the discovered node; and

(c) saving the content associated with the discovered node in the memory;

(d) repeating tasks (a)-(c) until the content for each discovered node has been saved in the memory; and

a schema generator module for generating the schema based on the content saved for each discovered node that includes specifying repeating nodes that are out of sequence as unbounded by checking at least a repeating indicator, wherein the schema provides the electronic document a set of grammatical and data type rules that govern types and a structure of data that may be included in the electronic document.

9. The system of claim 8, wherein in saving the content associated with the discovered node in the memory, the logical memory module:

determines whether the discovered node has previously been discovered;

if the discovered node has been previously discovered, then

stores a first indicator indicating that the discovered node is a repeating node in the memory; and

saves the content associated with the repeating node in the memory; and

if the discovered node has not been previously discovered, then saves the content associated with the discovered node in the memory.

10. The system of claim 8, wherein the content comprises data associated with the discovered node, wherein the data includes information for locating the discovered node.

11. The system of claim 10, wherein the logical memory module determines a data type for the data associated with each discovered node.

12. The system of claim 11, wherein in determining a data type for the data associated with each discovered node, the logical memory module:

compares the data associated with each discovered node to a list of known data types; and

determines the data type based on the list of known data types.

13. The system of claim 8, wherein the logical memory module determines at least one hierarchical relationship among the discovered nodes by examining the content saved for the discovered nodes, wherein the at least one hierarchical relationship includes a parent-child relationship.

14. A tangible computer-readable storage medium having computer-executable instructions, which when executed on a computer, perform a method for inferring a schema from hierarchical data comprising:

in an application program, receiving the electronic document containing the hierarchical data and determining that the hierarchical data within the electronic document does not reference a schema, wherein the hierarchical data includes one or more nodes;

(a) discovering one of the nodes in the hierarchical data;

(b) saving content associated with the discovered nodes;

(c) repeating tasks (a)-(b) until the content for each discovered node has been saved; and

generating the schema based on the content saved for each discovered node that includes specifying repeating nodes that are out of sequence as unbounded by checking at least a repeating indicator, wherein the schema provides the electronic document a set of grammatical and data type rules that govern types and a structure of data that may be included in the electronic document.

15. The tangible computer-readable storage medium of claim 14, wherein saving the content associated with the discovered node comprises:

determining whether the discovered field has previously been discovered;

if the discovered node has been previously discovered, then storing a first indicator indicating that the node is a repeating node; and

examining the content associated with the repeating node and updating a memory location with a data type of the repeating node; and

if the discovered field has not been previously discovered, then saving the content associated with the discovered node.

16. The tangible computer-readable storage medium of claim 14, wherein the content comprises data associated with the discovered node, wherein the data includes information for locating the discovered node.

17. The tangible computer-readable storage medium of claim 16, further comprising determining a data type for the data associated with each discovered node.

18. The tangible computer-readable storage medium of claim 17, wherein determining a data type for the data associated with each discovered node comprises:

comparing the data associated with the discovered node to a list of known data types; and

determining the data type based on the list of known data types.

19. The tangible computer-readable storage medium of claim 14, wherein the application program is a spreadsheet application program.