Indexing XML documents efficiently

• US 20050055334A1
• Filed: 05/18/2004
• Published: 03/10/2005
• Est. Priority Date: 09/04/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Krishnamurthy, Sanjay M.
• Granted Patent: US 8,694,510 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/86 Mapping to a database

Abstract

Information hierarchies are efficiently stored and accessed in a relational or object-relational database system. A path signature, similar to a pathname, is stored in a database system in association with data for the node identified by the pathname. For example, a path signature identifying an element is stored in a row that holds data for the element. To retrieve data for a hierarchical query that identifies the data requested using, for example, an XPATH string, a string pattern is generated that is matched by path signatures identified by the XPATH string. Pattern matching is then used to select rows associated with matching path signatures, and data from the selected rows is used to compute the XPATH query. Furthermore, hash values representing path signatures are generated in a way that preserves the ordering of data in an information hierarchy. The hash values can be indexed to provide quick access.

Claims

1. A method for providing access to data for nodes of an information hierarchy, wherein said data for said nodes are stored in a plurality of rows of a table, the method comprising the steps of:

generating a plurality of hash values that reflects an order of a plurality of pathnames associated with said nodes;

wherein each pathname of said plurality of pathnames corresponds to a row of said plurality of rows and identifies a location within the information hierarchy of a node whose data is stored in the row; and

storing said plurality of hash values in a data structure that associates said plurality of hash values with said plurality of rows.

2. The method of claim 1, wherein said data structure is an index having said plurality of hash values as key values.

3. The method of claim 2, further comprising:

calculating a range of hash values based on a set of nodes requested by a query;

scanning the index based on the range to find entries corresponding to the range; and

retrieving data from the rows corresponding to the entries.

4. The method of claim 2, wherein said plurality of hash values are stored in a column of said table.

5. The method of claim 1, wherein said data for nodes of said information hierarchy includes data that conforms to XML.

6. The method of claim 1, wherein said plurality of hash values are generated by a hash value function that conforms to DOMHASH.

7. The method of claim 1, wherein:

said information hierarchy includes a first node and a second node that is a sibling of said first node, wherein said first node has descendant nodes;

the first node is first in said order relative to the second node; and

the step of generating a plurality of hash values guarantees that the plurality of hash values associated with descendant nodes is less than a hash value associated with said second node.

8. The method of claim 7, wherein:

said information hierarchy includes a third node that is a sibling of said first node;

the third node is first in said order relative to said first node; and

the step of generating a plurality of hash values guarantees that the plurality of hash values associated with both said first node and said descendant nodes are greater than a hash value generated for said third node or all descendants of said third node.

9. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

10. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

11. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

12. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

13. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

14. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

17. A computer-readable medium, comprising:

a table with a plurality of rows, each row of said plurality of rows storing data for a node of a plurality of nodes in an information hierarchy;

an index of said table having a plurality of hash values as key values within said index, wherein each hash value of said plurality of hash values corresponds to a pathname associated with a node of said plurality of nodes;

wherein the pathnames associated with the plurality of the nodes have an order; and

wherein said plurality of hash values reflects said order.

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

said information hierarchy includes a first node and a second node that is a sibling of said first node, wherein said first node has descendant nodes;

the first node is first in said order relative to the second node; and

each hash value of said plurality of hash values that is associated with the descendant nodes is less than the hash value associated with said second node.

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

said information hierarchy includes a third node that is a sibling of said first node;

the third node is first in said order relative to said first node; and

each hash value of said plurality of hash values that is associated with both said first node and said descendant nodes is greater than a hash value generated for said third node or all descendants of said third node.