Indexing XML documents efficiently

• US 8,694,510 B2
• Filed: 05/18/2004
• Issued: 04/08/2014
• 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.
• Primary Examiner(s): PHAM, KHANH B
• Application Number:
  US10/848,640
• Publication Number:
  US 20050055334A1
• Time in Patent Office: 3,612 Days
• Field of Search: 707/2, 707/102, 707741-747
• US Class Current: 707/747
• 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, each node of said nodes belonging to 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 hash value in the plurality of hash values is generated based on character values of a particular pathname in the plurality of pathnames, the order being character-based;

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

storing, in a database, said plurality of hash values in an index that associates said plurality of hash values with said plurality of rows;

wherein said index is ordered by said plurality of hash values as key values;

identifying a range of hash values based on a path that includes one or more nodes;

scanning said index based on said range of hash values to find one or more rows corresponding to said range of hash values, wherein said one or more rows store data of one or more descendant nodes to said one or more nodes; and

retrieving said data of said one or more descendant nodes from said one or more rows;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

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

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

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

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

6. The method of claim 1, wherein:

wherein a particular information hierarchy includes a first node of said nodes and a second node of said nodes

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.

7. The method of claim 6, 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.

8. A non-transitory computer-readable storage medium storing one or more sequences of instructions for providing access to data for nodes, each node of said nodes belonging to an information hierarchy, wherein said data for said nodes are stored in a plurality of rows of a table, wherein said one or more sequences of instructions, when executed by one or more processors, causes the one or more processors to perform:

generating a plurality of hash values that reflects an order of a plurality of pathnames associated with said nodes, wherein each hash value in the plurality of hash values is generated based on character values of a particular pathname in the plurality of pathnames, the order being character-based;

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

storing, in a database, said plurality of hash values in an index that associates said plurality of hash values with said plurality of rows;

wherein said index is ordered by said plurality of hash values as key values;

identifying a range of hash values based on a path that includes one or more nodes;

scanning said index based on said range of hash values to find one or more rows corresponding to said range of hash values, wherein said one or more rows store data of one or more descendant nodes to said one or more nodes; and

retrieving said data of said one or more descendant nodes from said one or more rows.

9. The medium of claim 8, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, causes the one or more processors to perform:

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

10. The medium of claim 8, wherein said plurality of hash values are stored in a column of said table.

11. The medium of claim 8, wherein said data for nodes of said information hierarchy includes data that conforms to XML.

12. The medium of claim 8, wherein said plurality of hash values are generated by a hash value function that conforms to DOMHASH.

13. The medium of claim 8, wherein:

wherein a particular information hierarchy includes a first node of said nodes and a second node of said nodes 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.

14. The medium of claim 13, 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.