Index maintenance for operations involving indexed XML data

• US 20050228786A1
• Filed: 09/16/2004
• Published: 10/13/2005
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Thusoo, Ashish, Chandrasekar, Sivasankaran, Murthy, Ravi, Agarwal, Nipun
• Granted Patent: US 7,440,954 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 XML documents, the method comprising the steps of:

performing a piece-wise operation involving one or more nodes of an XML document, wherein the XML document is one of a plurality of XML documents indexed by said index; and

in response to performing the piece-wise operation, modifying the index to reflect changes made to the XML document by the piece-wise operation without altering entries for any nodes other than the one or more nodes involved in the piece-wise operation.

2. The method of claim 1 wherein:

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

the step of modifying the index includes 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.

4. The method of claim 3 wherein 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.

5. The method of claim 3 wherein 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.

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

7. The method of claim 1 wherein:

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

the step of modifying the index includes deleting an index entry that corresponds to the node.

8. The method of claim 1 wherein:

the piece-wise operation modifies a node that currently exists in the XML document; and

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

9. The method of claim 3 wherein:

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.

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 1.

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 2.

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 3.

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 4.

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 5.

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 6.

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 7.

17. 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.

18. 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 9.