STRUCTURE BASED STORAGE, QUERY, UPDATE AND TRANSFER OF TREE-BASED DOCUMENTS

• US 20120158790A1
• Filed: 02/28/2012
• Published: 06/21/2012
• Est. Priority Date: 11/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chowdhury, Sandeep
• Granted Patent: US 11,030,243 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/83 Querying

Abstract

Data is represented as a tree structure. A structure identifier (ID) that mathematically defines a structure of the tree structure is calculated. The structure ID is a representation of the structure of the tree structure and is independent of node names and node values of the tree structure. A mapping of the structure ID to the tree structure is stored.

Claims

1. A method for storing data, comprising:

representing the data as a tree structure;

calculating a structure identifier (ID) that mathematically defines a structure of the tree structure, the structure ID being a representation of the structure of the tree structure and independent of node names and node values of the tree structure; and

storing a mapping of the structure ID to the tree structure.

2. The method of claim 1, further comprising assigning integer node IDs to each node of the tree structure.

3. The method of claim 2, where assigning the integer node IDs to each node of the tree structure comprises assigning an integer node ID to each node of the tree structure beginning from a highest level to a lowest level and from a left to right within each level, where a unique node ID is assigned to each node of the tree structure.

4. The method of claim 2, further comprising storing a mapping of a node name of each node of the tree structure to a respective integer node ID.

5. The method of claim 2, further comprising storing a mapping of a node value of each node of the tree structure to a respective integer node ID.

6. The method of claim 2, where each parent node of the tree structure comprises at least one child node, and where calculating the structure ID that mathematically defines the structure of the tree structure comprises:

selecting, using the assigned integer node ID of a respective parent node as an index, a prime number within an indexed set of prime numbers that corresponds to the index;

calculating the structure ID by calculating a plurality of results, where each result represents one parent node and comprises the selected prime number raised to a power of the number of child nodes of the respective parent node; and

calculating the structure ID as a mathematical product of the plurality of results to represent the structure of the tree structure.

7. The method of claim 1, where the data is in the form of an XML document, the tree structure represents a structure of the XML document, and the calculated structure ID uniquely identifies the structure of the tree structure of the XML document.

8. A system for storing data, comprising:

a memory; and

a processor programmed to;

represent the data as a tree structure within the memory;

calculate a structure identifier (ID) that mathematically defines a structure of the tree structure, the structure ID being a representation of the structure of the tree structure and independent of node names and node values of the tree structure; and

store a mapping of the structure ID to the tree structure within the memory.

9. The system of claim 8, where the processor is further programmed to assign integer node IDs to each node of the tree structure.

10. The system of claim 9, where, in being programmed to assign the integer node IDs to each node of the tree structure, the processor is programmed to assign an integer node ID to each node of the tree structure beginning from a highest level to a lowest level and from a left to right within each level, where a unique node ID is assigned to each node of the tree structure.

11. The system of claim 9, where the processor is further programmed to store a mapping of a node name of each node of the tree structure to a respective integer node ID within the memory.

12. The system of claim 9, where the processor is further programmed to store a mapping of a node value of each node of the tree structure to a respective integer node ID within the memory.

13. The system of claim 9, where each parent node of the tree structure comprises at least one child node, and where, in being programmed to calculate the structure ID that mathematically defines the structure of the tree structure, the processor is programmed to:

select, using the assigned integer node ID of a respective parent node as an index, a prime number within an indexed set of prime numbers that corresponds to the index;

calculate the structure ID by calculating a plurality of results, where each result represents one parent node and comprises the selected prime number raised to a power of the number of child nodes of the respective parent node; and

calculate the structure ID as a mathematical product of the plurality of results to represent the structure of the tree structure.

14. The system of claim 8, where the data is in the form of an XML document, the tree structure represents a structure of the XML document, and the calculated structure ID uniquely identifies the structure of the tree structure of the XML document.

15. A computer program product comprising a computer readable storage medium including computer readable program code, where the computer readable program code when executed on a computer causes the computer to:

represent the data as a tree structure;

calculate a structure identifier (ID) that mathematically defines a structure of the tree structure, the structure ID being a representation of the structure of the tree structure and independent of node names and node values of the tree structure; and

store a mapping of the structure ID to the tree structure.

16. The computer program product of claim 15, where the computer readable program code when executed on the computer further causes the computer to assign integer node IDs to each node of the tree structure.

17. The computer program product of claim 16, where in causing the computer to assign the integer node IDs to each node of the tree structure, the computer readable program code when executed on the computer causes the computer to assign an integer node ID to each node of the tree structure beginning from a highest level to a lowest level and from a left to right within each level, where a unique node ID is assigned to each node of the tree structure.

18. The computer program product of claim 16, where the computer readable program code when executed on the computer further causes the computer to store a mapping of a node name of each node of the tree structure to a respective integer node ID.

19. The computer program product of claim 16, where the computer readable program code when executed on the computer further causes the computer to store a mapping of a node value of each node of the tree structure to a respective integer node ID.

20. The computer program product of claim 16, where each parent node of the tree structure comprises at least one child node, and where in causing the computer to calculate the structure ID that mathematically defines the structure of the tree structure, the computer readable program code when executed on the computer causes the computer to:

select, using the assigned integer node ID of a respective parent node as an index, a prime number within an indexed set of prime numbers that corresponds to the index;

calculate the structure ID by calculating a plurality of results, where each result represents one parent node and comprises the selected prime number raised to a power of the number of child nodes of the respective parent node; and

calculate the structure ID as a mathematical product of the plurality of results to represent the structure of the tree structure.

21. The computer program product of claim 15, where the data is in the form of an XML document, the tree structure represents a structure of the XML document, and the calculated structure ID uniquely identifies the structure of the tree structure of the XML document.