Converting a hierarchical data structure into a flat data structure

• US 6,502,101 B1
• Filed: 07/13/2000
• Issued: 12/31/2002
• Est. Priority Date: 07/13/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cahill, Jason, Allen, Jason, Verprauskus, Andy
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/615,905
• Time in Patent Office: 901 Days
• Field of Search: 707/2, 707/3, 707/4, 707/100, 707/1, 707/102, 707/101, 707/104, 707/200, 707/533, 707/7, 707/6, 716/8, 716/10, 382/240
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Upon receipt of the hierarchical data structure, a shape tree is constructed corresponding to the hierarchical data structure. The shape tree is an intermediate data structure containing only one unique node for each element of the hierarchical data structure. After the shape tree is constructed, it is annotated with properties describing the hierarchical relationships between elements of the hierarchical data structure. The annotated shape tree is used to create the structure of the flat data structure. Once the shape tree is annotated, the column names for the flat data structure are built utilizing the annotated shape tree. With the column names built, data is emitted from the hierarchical data structure into the proper columns and rows of the flat data structure.

Claims

1. In a computer system, a method for converting a hierarchical data structure into a flat data structure comprising the steps of:

a) converting said hierarchical data structure into an input data tree comprising nodes, said nodes containing the data elements of said hierarchical data structure and said nodes linked together in a parent-child relationship, said parent-child relationship derived from the hierarchical data structure;

b) constructing a shape tree corresponding to the input data tree by collapsing nodes of said input data tree containing redundant elements into one node;

c) annotating said shape tree nodes with properties describing the hierarchical relationships between elements of the input data tree;

d) building a list of column names for said flat data structure deriving said column names by tracing said shape tree; and

e) emitting data from said input data tree into proper columns and row of said flat data structure.

2. The method in claim 1, wherein said properties include a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree.

3. The method in claim 1, wherein said properties include a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree and a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes that have a second property set to false.

4. The method in claim 1, wherein said properties include a third property set to true if the node has any child nodes.

5. The method in claim 1, wherein said properties include a fourth property set to true if and only if every occurrence of the element corresponding to the node contains numeric data.

6. The method in claim 1, wherein the format of the data structure of said hierarchical data structure is XML.

7. The method in claim 1, wherein said flat data structure is readily usable by an electronic spreadsheet.

8. The method in claim 1, wherein:

said properties include;

a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree,

a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes and anyone of said child nodes have a second property set to false, and

a third property set to true if every occurrence of the element corresponding to the node contains numeric data; and

wherein a column name is generated for said flat data structure when said second and said third properties are both true.

9. The method in claim 1, wherein:

said properties include;

a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree, and

a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes that have a second property set to false; and

wherein a column name is generated for said flat data structure when said first and said second properties are both true.

10. A computer system for converting a hierarchical data structure into a flat data structure, the system comprising:

a memory for storing said hierarchical data structure and said flat data structure; and

a processing unit functionally coupled to the memory, for executing computer-executable instructions operable for;

converting said hierarchical data structure into an input data tree comprising nodes, said nodes containing the data elements of said hierarchical data structure and said nodes link together in a parent-child relationship in the same fashion as the data elements they contain were linked in the hierarchical data structure,

constructing a shape tree corresponding to the input data tree by collapsing nodes of said input data tree containing redundant elements into one node, said intermediate data structure retaining the same parent-child relationship of the input data tree,

annotating said shape tree nodes with properties describing the hierarchical relationships between elements of the input data tree,

building a list of column names for said flat data structure utilizing said intermediate data structure as annotated, and

emitting data from said input data tree into proper columns and row of said flat data structure.

11. The system in claim 10, wherein said properties include a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree.

12. The system in claim 10, wherein said properties include a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree and a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes that have a second property set to false.

13. The system in claim 10, wherein said properties include a third property set to true if the node has any child nodes.

14. The system in claim 10, wherein said properties include a fourth property set to true if and only if every occurrence of the element corresponding to the node contains numeric data.

15. The system in claim 10, wherein the format of the data structure of said hierarchical data structure is XML.

16. The system in claim 10, wherein said flat data structure is readily usable by an electronic spreadsheet.

17. The system in claim 10, wherein:

said properties include;

a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree,

a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes and anyone of said child nodes have a second property set to false, and

a third property set to true if every occurrence of the element corresponding to the node contains numeric data; and

wherein a column name is generated for said flat data structure when said second and said third properties are both true.

18. The system in claim 10, wherein:

said properties include;

a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree, and

a second property set equal to false if and only if the node'"'"'s first property is greater than zero or if the node has any child nodes that have a second property set to false; and

wherein a column name is generated for said flat data structure when said first and said second properties are both true.