System and method for efficient maintenance of indexes for XML files
View Patent ↗System and method for efficient maintenance of indexes for XML and other documents comprising semi-structured, hierarchical data are described. In one embodiment, the method comprises providing a first index definition document (“IDD”) for defining a first index for the document, wherein the first IDD is applied to the document to create a first set of index keys for the document stored in the database and wherein the first IDD defines at least one set of relationships among nodes in the document; responsive to a change to the document affecting an update node thereof, performing a limited, localized traversal of the document around the update node to determine whether the change affects the first set of index keys; and updating the first set of index keys as necessitated by the change.
1. A method of efficiently managing indexes for an XML document stored in an XML database, the method comprising:
providing a first XML index definition document (“XIDD”) for defining a first index for the XML document, the first XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another, wherein the first X1DD is applied to the XML document to create a first set of index keys for the XML document stored in the XML database;
responsive to a change to the XML document affecting an update node thereof, performing a limited, localized traversal of the XML document around the update node to determine whether the change affects the first set of index keys; and
updating the first set of index keys as necessitated by the change;
the method further comprising:
providing at least one additional X1DD for defining at least one additional index for the XML document, each additional XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another, wherein the at least one additional XIDD is applied to the XML document to create at least one additional set of index keys for the XML document stored in the XML database; and
providing a master table comprising, for each node in each of the XIDDs, an entry that points to the X1DD node, wherein one of the entries of the master table points to at least one node of the first XIDD and to at least one node of the additional XIDD.
2. The method of claim 1 further comprising providing a master table that includes, for each node in the XIDD, an entry that points to the XIDD node.
3. The method of claim 1 wherein the performing a limited localized traversal of the XML document comprises:
determining whether the XIDD includes a node corresponding to the update node; and
responsive to a determination that the XIDD includes a node corresponding to the update node, determining whether the update node is hierarchically related to other nodes of the XML document as defined by the XIDD.
4. The method of claim 3 wherein the updating the first set of index keys as necessitated by the change further comprises:
determining a before set of index keys for the XML document;
determining an after set of index keys for the XML document;
deleting from the first set of index keys the before set of index keys and adding to the first set of index keys the after set of index keys.
5. The method of claim 4 further comprising, prior to the deleting and adding, eliminating keys that are included in both the before and the after sets of index keys from the before set of index keys and the after set of index.
6. The method of claim 1 wherein the change to the XML document comprises an operation selected from a group consisting of updating a value of the update node, deleting the update node, or inserting the update node.
7. A system for efficient management of indexes for XML documents comprising:
an XML database comprising a storage device for storing an XML document;
a database engine for performing operations on and in connection with data stored in the XML database;
a first XML index definition document (“XIDD”) for defining a first index for the XML document, the first XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another; and
a first set of index keys for the XML document stored in the XML database, the first set of index keys corresponding to the first XIDD;
wherein responsive to a change to the XML document affecting an update node thereof, a limited, localized traversal of the XML document is performed to determine whether the change affects the first set of index keys and to update the first set of index keys as necessitated by the change;
the system further comprising:
at least one additional XIDD for defining at least one additional index for the XML document, the additional XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another;
at least one additional set of index keys for the XML document stored in the XML database corresponding to the at least one additional XIDD; and
a master table comprising, for each node in each of the XIDDs, an entry that points to the XIDD node, wherein one of the entries of the master table points to at least one node of the first XIDD and to at least one node of the additional XIDD.
8. The system of claim 7 further comprising a master table comprising, for each node in the XIDD, an entry that points to the XIDD node.
9. The system of claim 7 wherein the XIDD defines at least one node of the XML document as a key component node.
10. The system of claim 9 wherein the XIDD defines at least one node of the XML document as a context-only node, wherein the context-only node defines a context for the key component node within the XML document.
11. The system of claim 7 wherein the XIDD defines at least one relationship among nodes in the XML document.
12. The system of claim 7 wherein the change to the XML document comprises an operation selected from a group consisting of updating a value of the update node, deleting the update node, or inserting the update node.
13. A system of efficiently managing indexes for XML documents comprising:
a storage device for storing an XML document;
a first XML index definition document (“XIDD”) for defining a first index for the XML document, the first XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another, wherein the first XIDD is applied to the XML document to create a first set of index keys for the XML document stored in the storage device;
a module responsive to a change to the XML document affecting an update node thereof for performing a limited, localized traversal of the XML document around the update node to determine whether the change affects the first set of index keys; and
a module for updating the first set of index keys as necessitated by the change;
the system further comprising:
at least one additional XIDD for defining at least one additional index for the XML document, the additional XIDD comprising an in-memory tree structure for identifying elements and attributes to be indexed, including a context of the elements and attributes with respect to one another;
at least one additional set of index keys for the XML document stored in the XML database corresponding to the at least one additional XIDD; and
a master table comprising, for each node in each of the XIDDs, an entry that points to the XIDD node, wherein one of the entries of the master table points to at least one node of the first XIDD and to at least one node of the additional XIDD.
14. The system of claim 13 further comprising a master table that includes, for each node in the XIDD, an entry that points to the XIDD node.
15. The system of claim 13 wherein performing a limited localized traversal of the XML document comprises:
determining whether the XIDD includes a node corresponding to the update node; and
responsive to a determination that the XIDD includes a node corresponding to the update node, determining whether the update node is hierarchically related to other nodes of the XML document as defined by the XIDD.
16. The system of claim 13 wherein updating the set of index keys as necessitated by the change further comprises:
determining a before set of index keys for the XML document;
determining an after set of index keys for the XML document; and
deleting from the set of index keys the before set of index keys and adding to the set of index keys the after set of index keys.
17. The system of claim 16 wherein keys that are included in both the before and the after sets of index keys from the before set of index keys and the after set of index keys are eliminated prior to the deleting and adding.