Reducing memory requirements needed to represent XML entities

• US 7,321,900 B1
• Filed: 06/14/2002
• Issued: 01/22/2008
• Est. Priority Date: 06/15/2001
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Karun, K., Manian, Anjana
• Primary Examiner(s): Lee; Wilson
• Assistant Examiner(s): Le; Michael
• Application Number:
  US10/173,466
• Time in Patent Office: 2,048 Days
• Field of Search: 707/103.R, 707/206, 711/101, 711/117, 711/216, 711/221
• US Class Current: 1/1
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Described herein are approaches that allow an XML entity to be accessed in a way that requires less memory. These approaches involve dynamically generating and maintaining an in-memory representation of only a portion of an XML tree. The in-memory representation of an XML tree is herein referred to as a node tree. The node tree contains data from the XML tree, and is generated by extracting data from a compressed form of an XML entity. In addition, the node tree contains information about the location of specific elements within the compressed XML entity. The approaches described herein allow an XML tree to be accessed without having to generate an in-memory representation of the whole XML tree, thus reducing the amount of memory needed to access the data in the XML tree.

Claims

1. A method used in accessing and storing a hierarchical tree representation of elements that reside in a body of data, the method comprising the steps of:

parsing said body of data to generate in memory a node tree that represents elements that reside in the body of data and that reflects a hierarchical tree relationship between said elements in said body of data;

after said generating said node tree, said body of data includes certain elements for which there is no corresponding node in the node tree;

wherein a first node in said node tree;

corresponds to a first element in said body of data, wherein said first element contains a second element, said first element being hierarchically related to the second element as an ascendant of said second element, and

includes first element location data identifying the location of the first element within said body of data;

after said generating in memory said node tree and while said node tree is in memory, receiving a request that requires access to a second node in said node tree, wherein said second node corresponds to the second element in said body of data;

in response to receiving said request, determining that said second node is not in memory; and

in response to determining that said second node is not in memory;

using said first element location data to locate where within said body of data to begin parsing to extract data that is contained within the first element for said second element, and

generating said second node based on said extracted data.

2. The method of claim 1, further including the step of:

loading at least a portion of said body of data into memory, wherein said body of data is a compressed form of another body of data defining said elements.

3. The method of claim 2, wherein said other body of data conforms to XML.

4. The method of claim 1, wherein the step of determining that said second node is not in memory is based on examining data in said first node that indicates whether said second node is in memory.

5. The method of claim 1, wherein the step of generating said second node includes generating within said second node second element location data identifying the location of the second element within said body of data.

6. A method used in accessing and storing a hierarchical tree representation of elements that reside in a body of data, the method comprising the steps of:

receiving a request that requires access to a first node in a node tree that reflects a hierarchical tree relationship between said elements in said body of data, said node tree residing in a memory, wherein said first node corresponds to a first element in said body of data;

wherein a second node in said node tree;

corresponds to a second element in said body of data, said second element being hierarchically related to the first element, and

includes a plurality of flags that include a certain flag, wherein;

each flag of said plurality of flags only indicates whether a node that corresponds to an element having a particular hierarchical relationship to said second element resides within said memory;

each flag of said plurality of flags represents a different hierarchical relationship than that represented by any other flag of said plurality of flags;

each flag of said plurality of flags is set to one of two states, said two states comprising a first state as TRUE and a second state as FALSE;

one of the TRUE and FALSE states indicates that said node that corresponds to an element having a particular hierarchical relationship to said second element resides within said memory; and

the other of the TRUE and FALSE states indicates that said node that corresponds to said element having a particular hierarchical relationship to said second element does not reside within said memory;

examining the certain flag of said second node to determine whether said first node resides in the memory; and

determining that said first node does not reside in said memory; and

in response to determining that said first node does not reside in said memory;

parsing said body of data to extract data for said first element, and

generating said first node in the memory based on the extracted data.

7. The method of claim 6, wherein the steps further include updating said certain flag to indicate that said first node resides in said memory.

8. The method of claim 6, wherein the steps further include updating a link, different than said certain flag, to refer to said first node.

9. The method of claim 6, wherein the steps further include updating another flag in said first node to indicate that said second node resides in said memory.

10. The method of claim 6, wherein

the steps further include updating the plurality of flags to indicate whether the node corresponding to each of the plurality of flags resides in the memory.

11. The method of claim 6, wherein:

each record of a body of records indicates that a node for a particular element of said elements resides in the memory; and

the steps further include updating said body of records to indicate that the first node resides in the memory.

12. The method of claim 11, wherein:

said certain flag does not indicate that said first node resides in the memory; and

the steps further include examining said body of records to determine whether said first node resides in said memory.

13. A computer-readable storage medium carrying one or more sequences of instructions for accessing and storing a hierarchical tree representation of elements that reside in a body of data, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

parsing said body of data to generate in memory a node tree that represents elements that reside in the body of data and that reflects a hierarchical tree relationship between said elements in said body of data;

after said generating said node tree, said body of data includes certain elements for which there is no corresponding node in the node tree;

wherein a first node in said node tree;

corresponds to a first element in said body of data, wherein said first element contains a second element, said first element being hierarchically related to the second element as an ascendant of said second element, and

includes first element location data identifying the location of the first element within said body of data;

after said generating in memory said node tree and while said node tree is in memory, receiving a request that requires access to a second node in said node tree, wherein said second node corresponds to the second element in said body of data;

in response to receiving said request, determining that said second node is not in memory; and

in response to determining that said second node is not in memory;

using said first element location data to locate where within said body of data to begin parsing to extract data that is contained within the first element for said second element, and

generating said second node based on said extracted data.

14. The computer-readable storage medium of claim 13, the steps further including:

loading at least a portion of said body of data into memory, wherein said body of data is a compressed form of another body of data defining said elements.

15. The computer-readable storage medium of claim 14, wherein said other body of data conforms to XML.

16. The computer-readable storage medium of claim 13, wherein the step of determining that said second node is not in memory is based on examining data in said first node that indicates whether said second node is in memory.

17. The computer-readable storage medium of claim 13, wherein the step of generating said second node includes generating within said second node second element location data identifying the location of the second element within said body of data.

18. A computer-readable storage medium carrying one or more sequences of instructions for accessing and storing a hierarchical tree representation of elements that reside in a body of data, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a request that requires access to a first node in a node tree that reflects a hierarchical tree relationship between said elements in said body of data, said node tree residing in a memory, wherein said first node corresponds to a first element in said body of data;

wherein a second node in said node tree;

corresponds to a second element in said body of data, said second element being hierarchically related to the first element, and

includes a plurality of flags that include a certain flag, wherein;

each flag of said plurality of flags only indicates whether a node that corresponds to an element having a particular hierarchical relationship to said second element resides within said memory;

each flag of said plurality of flags represents a different hierarchical relationship than that represented by any other flag of said plurality of flags;

each flag of said plurality of flags is set to one of two states, said two states comprising a first state as TRUE and a second state as FALSE;

one of the TRUE and FALSE states indicates that said node that corresponds to an element having a particular hierarchical relationship to said second element resides within said memory; and

the other of the TRUE and FALSE states indicates that said node that corresponds to said element having a particular hierarchical relationship to said second element does not reside within said memory;

examining the certain flag of said second node to determine whether said first node resides in the memory; and

determining that said first node does not reside in said memory; and

in response to determining that said first node does not reside in said memory;

parsing said body of data to extract data for said first element, and

generating said first node in the memory based on the extracted data.

19. The computer-readable storage medium of claim 18, wherein the steps further include updating said certain flag to indicate that said first node resides in said memory.

20. The computer-readable storage medium of claim 18, wherein the steps further include updating a link, different than said certain flag, to refer to said first node.

21. The computer-readable storage medium of claim 18, wherein the steps further include updating another flag in said first node to indicate that said second node resides in said memory.

22. The computer-readable storage medium of claim 18, wherein

the steps further include updating the plurality of flags to indicate whether the node corresponding to each of the plurality of flags resides in the memory.

23. The computer-readable storage medium of claim 18, wherein:

each record of a body of records indicates that a node for a particular element of said elements resides in the memory; and

the steps further include updating said body of records to indicate that the first node resides in the memory.

24. The computer-readable storage medium of claim 23, wherein:

said certain flag does not indicate that said first node resides in the memory; and

the steps further include examining said body of records to determine whether said first node resides in said memory.