Index maintenance for operations involving indexed XML data

• US 7,921,101 B2
• Filed: 07/15/2008
• Issued: 04/05/2011
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chandrasekaran, Sivasankaran, Sedlar, Eric, Thusoo, Ashish, Murthy, Ravi, Agarwal, Nipun
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Hwa; Shyue Jiunn
• Application Number:
  US12/173,323
• Publication Number:
  US 20080275919A1
• Time in Patent Office: 994 Days
• Field of Search: None
• US Class Current: 707/715
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method and system are provided for maintaining an XML index in response to piece-wise modifications on indexed XML documents. The database server that manages the XML index determines which nodes are involved in the piece-wise modifications, and updates the XML index based on only those nodes. Index entries for nodes not involved in the piece-wise modifications remain unchanged.

Claims

1. A method for maintaining an index for extensible markup language (XML) documents, the method comprising the steps of:

updating an XML document in response to a request to perform a piece-wise operation involving one or more nodes of the XML document, wherein the XML document is one of a plurality of XML documents indexed by said index, wherein a piece-wise operation is an operation that specifies a strict subset of the XML document and that only modifies the strict subset of the XML document, wherein the piece-wise operation modifies a node that currently exists in the XML document; and

in response to updating the XML document, modifying the index to reflect changes, made to the XML document, that were specified by the piece-wise operation, without altering entries of the index for any nodes other than the one or more nodes involved in the piece-wise operation;

wherein the step of modifying the index includes modifying an index entry that corresponds to the node;

wherein, prior to updating the XML document, the index includes one or more index entries for nodes of the XML document that are not involved in the piece-wise operation;

wherein the one or more index entries for the nodes of the XML document that are not involved in the piece-wise operation are not modified in response to updating the XML document;

wherein modifying the index involves storing changes to a computer-readable storage medium.

2. The method of claim 1 wherein:

a second piece-wise operation adds a new node to an XML document; and

the method further comprising adding to the index an index entry for the new node.

3. The method of claim 2, wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value; and

the step of determining an order key value for the new node includes;

determining a parent node of the new node;

determining a highest order key value of existing children of the parent node; and

determining an order key value for the new node based on the highest order key value of existing children of the parent node.

4. The method of claim 2, wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value; and

the step of determining an order key value for the new node includes;

determining two nodes between which the new node is to reside; and

determining an order key value for the new node based on order key values of the two nodes between which the new node is to reside.

5. The method of claim 4, wherein the step of determining an order key value for the new node based on the order key values of the two nodes between which the new node is to reside includes assigning to the new node an order key value that averages the order keys of the two nodes between which the new node is to reside.

6. The method of claim 2 wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value;

a plurality of routines are provided which, when invoked, result in a piece-wise addition of a node; and

the order key value for the new node is determined based on which of the plurality of routines was invoked to cause the piece-wise addition of the new node.

7. The method of claim 1, wherein:

a second piece-wise operation deletes a node from the XML document; and

the method further comprising deleting an index entry that corresponds to the node.

8. A computer-readable storage medium carrying instructions for maintaining an index for extensible markup language (XML) documents, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

updating an XML document in response to a request to perform a piece-wise operation involving one or more nodes of the XML document, wherein the XML document is one of a plurality of XML documents indexed by said index, wherein a piece-wise operation is an operation that specifies a strict subset of the XML document and that only modifies the strict subset of the XML document, wherein the piece-wise operation modifies a node that currently exists in the XML document; and

in response to updating the XML document, modifying the index to reflect changes, made to the XML document, that were specified by the piece-wise operation, without altering entries of the index for any nodes other than the one or more nodes involved in the piece-wise operation;

wherein the step of modifying the index includes modifying an index entry that corresponds to the node;

wherein, prior to updating the XML document, the index includes one or more index entries for nodes of the XML document that are not involved in the piece-wise operation;

wherein the one or more index entries for the nodes of the XML document that are not involved in the piece-wise operation are not modified in response to updating the XML document;

wherein modifying the index involves storing changes to a computer-readable storage medium.

9. The computer-readable storage medium of claim 8 wherein:

a second piece-wise operation adds a new node to an XML document; and

the method further comprising adding to the index an index entry for the new node.

10. The computer-readable storage medium of claim 9, wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value; and

the step of determining an order key value for the new node includes;

determining a parent node of the new node;

determining a highest order key value of existing children of the parent node; and

determining an order key value for the new node based on the highest order key value of existing children of the parent node.

11. The computer-readable storage medium of claim 9, wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value; and

the step of determining an order key value for the new node includes;

determining two nodes between which the new node is to reside; and

determining an order key value for the new node based on order key values of the two nodes between which the new node is to reside.

12. The computer-readable storage medium of claim 11, wherein the step of determining an order key value for the new node based on the order key values of the two nodes between which the new node is to reside includes assigning to the new node an order key value that averages the order keys of the two nodes between which the new node is to reside.

13. The computer-readable storage medium of claim 9 wherein:

the step of adding an index entry includes;

determining an order key value for the new node; and

adding to the index an index entry that contains the order key value;

a plurality of routines are provided which, when invoked, result in a piece-wise addition of a node; and

the order key value for the new node is determined based on which of the plurality of routines was invoked to cause the piece-wise addition of the new node.

14. The computer-readable storage medium of claim 8, wherein:

a second piece-wise operation deletes a node from the XML document; and

the method further comprising deleting an index entry that corresponds to the node.