Incremental maintenance of an XML index on binary XML data

• US 20080098020A1
• Filed: 03/07/2007
• Published: 04/24/2008
• Est. Priority Date: 10/20/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Gupta, Nitin, Idicula, Sam, Chandrasekar, Sivasankaran, Agarwal, Nipun
• Granted Patent: US 7,739,251 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

Techniques are provided for incrementally maintaining an XML index built to access XML data that is encoded in binary XML form. Rather than delete and reinsert index entries of all the nodes of a modified XML document, only the index entries of the affected nodes are modified. Consequently, the order key values stored in the index may become inconsistent with the current hierarchical locations of the nodes to which the order key values correspond. Techniques are described for resolving the inconsistencies, and for addressing additional problems that result when the XML index is path-subsetted.

Claims

1. A machine-executed method for incrementally maintaining an index that indexes XML data, the method comprising:

identifying a node, within the XML data, that is to be deleted in response to a DML operation;

generating a hybrid key for the node;

converting the hybrid key to an index order key;

using the index order key to locate a set of index entries, within the index, for the node and any nodes that descend from the node; and

deleting the set of index entries from the index.

2. The method of claim 1 wherein:

the index is a path-subsetted index;

the step of converting the hybrid key to an index order key includes converting canonical components of the hybrid key to path-subsetted components; and

using the path-subsetted components to determine the index order key that corresponds to the hybrid key.

3. The method of claim 2 wherein the step of converting canonical components of the hybrid key to path-subsetted components includes determining how many sibling components (a) precede a canonical component, and (b) correspond to nodes that are not included in the index.

4. The method of claim 1 wherein:

the node belongs to an XML document that is indexed by said index; and

the set of index entries that are deleted from the index does not include index entries for any nodes of the XML document other than the node and any nodes that descend from the node.

5. The method of claim 1 further comprising:

maintaining, as part of the index, a descendant index that is built on index order key values; and

traversing the descendant index, based on the index order key, to identify the set of index entries to delete from the index.

6. The method of claim 1 wherein the DML operation is a delete operation.

7. The method of claim 1 wherein the DML operation is an update operation, and the method further comprises:

identifying a particular node that is to be added to the XML data in response to the DML operation;

generating a hybrid key for a parent node of the particular node;

converting the hybrid key to a first index order key;

adding a component to the first index order key to generate a second index order key for the particular node; and

storing, within the index, an index entry for the particular node;

wherein the index entry includes the second index order key.

8. The method of claim 1 wherein generating a hybrid key for the node includes obtaining a first set of one or more components of the hybrid key from the index, and obtaining a second set of one or more canonical components without using the index.

9. The method of claim 8 wherein the step of obtaining the second set of one or more canonical components includes using streaming evaluation to generate the second set of one or more canonical components.

10. The method of claim 8 wherein the step of converting the hybrid key to the first index order key includes:

a) initially establishing a current order key to include the first set of one or more components;

b) selecting, as a current component, a component of the second set of one or more components;

c) determining all immediate children of the current order key;

d) ranking the immediate children of the current order key;

e) identifying the child of the current order key that has a rank equal to the current component;

f) appending to the current order key a component associated with the child identified in step (e); and

g) repeating steps (b) to (f) until all components in the second set of components have been selected as the current component.

11. The method of claim 10 further comprising using a descendant index to determine all immediate children of the current order key.

12. The method of claim 1 wherein:

the node belongs to an XML document;

the XML document is encoded in binary XML format; and

the DML operation is performed on the XML data using a piece-wise operation that does not cause the XML document to be entirely rewritten.

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

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

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

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

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

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

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

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

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

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

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

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

13. A machine-executed method for incrementally maintaining an index that indexes XML data, the method comprising:

identifying a particular node that is to be added to the XML data in response to a DML operation;

generating a hybrid key for a parent node of the particular node;

converting the hybrid key to a first index order key;

adding a component to the first index order key to generate a second index order key for the particular node; and

storing, within the index, an index entry for the particular node;

wherein the index entry includes the second index order key.

14. The method of claim 13 wherein further comprising generating the component to add to the first index order key by:

identifying a last child node of the parent node;

identifying a last component of an index order key of the last child node; and

generating a value, to be used as said component, that is greater than the last component of the index order key of the last child node.

15. The method of claim 13 wherein further comprising generating the component to add to the first index order key by:

identifying two sibling nodes between which the particular node is to logically reside;

identifying last components of index order keys of the two sibling nodes; and

generating a value, to be used as said component, that is between the last components of the index order keys of the two sibling nodes.

16. The method of claim 13 wherein:

the index is a path-subsetted index;

the step of converting the hybrid key to an index order key includes converting canonical components of the hybrid key to path-subsetted components; and

using the path-subsetted components to determine the index order key that corresponds to the hybrid key.

17. The method of claim 16 wherein the step of converting canonical components of the hybrid key to path-subsetted components includes determining how many sibling components (a) precede a canonical component, and (b) correspond to nodes that are not included in the index.

18. The method of claim 13 wherein generating a hybrid key for the node includes obtaining a first set of one or more components of the hybrid key from the index, and obtaining a second set of one or more canonical components without using the index.

19. The method of claim 18 wherein the step of obtaining the second set of one or more canonical components includes using streaming evaluation to generate the second set of one or more canonical components.

20. The method of claim 18 wherein the step of converting the hybrid key to the first index order key includes:

a) initially establishing a current order key to include the first set of one or more components;

b) selecting, as a current component, a component of the second set of one or more components;

c) determining all immediate children of the current order key;

d) ranking the immediate children of the current order key;

e) identifying the child of the current order key that has a rank equal to the current component;

f) appending to the current order key a component associated with the child identified in step (e); and

g) repeating steps (b) to (f) until all components in the second set of components have been selected as the current component.

21. The method of claim 20 further comprising using a descendant index to determine all immediate children of the current order key.

22. The method of claim 13 wherein:

the node belongs to an XML document;

the XML document is encoded in binary XML format; and

the DML operation is performed on the XML data using a piece-wise operation that does not cause the XML document to be entirely rewritten.

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

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

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

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

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

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

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

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

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

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