Incremental maintenance of an XML index on binary XML data
First Claim
1. A machine-executed method for incrementally maintaining an index that indexes Extensible Markup Language (XML) data, the method comprising:
- identifying a node, within the XML data, that is to be deleted in response to a Data Manipulation Language (DML) operation;
generating a hybrid key for the node;
wherein the hybrid key includes (a) a first set of one or more index order key components and (b) a first set of one or more canonical order key components;
wherein the first set of index order key components reflects a portion of an index order key by which the node is indexed in the index;
wherein the first set of canonical order key components reflects the actual position of the node within the XML data;
converting the hybrid key to the index order key;
wherein the index order key includes a second set of one or more index order key components and a third set of one or more index order key components;
wherein the second set of index order key components equals the first set of index order key components;
wherein converting the hybrid key to an index order key comprises converting the first set of canonical order key components to the third set of index order key components;
wherein the first set of canonical order key components differs in value from the third set of index order key components;
using the index order key to locate a set of one or more index entries within the index;
wherein one of the set of one or more index entries indexes the node; and
deleting the set of index entries from the index.
1 Assignment
0 Petitions
Accused Products
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.
56 Citations
42 Claims
-
1. A machine-executed method for incrementally maintaining an index that indexes Extensible Markup Language (XML) data, the method comprising:
-
identifying a node, within the XML data, that is to be deleted in response to a Data Manipulation Language (DML) operation; generating a hybrid key for the node; wherein the hybrid key includes (a) a first set of one or more index order key components and (b) a first set of one or more canonical order key components; wherein the first set of index order key components reflects a portion of an index order key by which the node is indexed in the index; wherein the first set of canonical order key components reflects the actual position of the node within the XML data; converting the hybrid key to the index order key; wherein the index order key includes a second set of one or more index order key components and a third set of one or more index order key components; wherein the second set of index order key components equals the first set of index order key components; wherein converting the hybrid key to an index order key comprises converting the first set of canonical order key components to the third set of index order key components; wherein the first set of canonical order key components differs in value from the third set of index order key components; using the index order key to locate a set of one or more index entries within the index; wherein one of the set of one or more index entries indexes the node; and deleting the set of index entries from the index. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A machine-executed method for incrementally maintaining an index that indexes Extensible Markup Language (XML) data, the method comprising:
-
identifying a particular node that is to be added to the XML data in response to a Data Manipulation Language (DML) operation; generating a hybrid key for a parent node of the particular node; wherein the hybrid key includes (a) a first set of one or more index order key components and (b) a first set of one or more canonical order key components; wherein the first set of index order key components reflects a portion of an index order key by which the parent node is indexed in the index; wherein the first set of canonical order key components reflects the actual position of the parent node within the XML data; converting the hybrid key to a first index order key; wherein the index order key includes a second set of one or more index order key components and a third set of one or more index order key components; wherein the second set of index order key components equals the first set of index order key components; wherein converting the hybrid key to the first index order key comprises converting the first set of canonical order key components to the third set of index order key components; wherein the first set of canonical order key components differs in value from the third set of index order key components; 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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A computer-readable volatile or non-volatile storage medium storing computer-executable instructions for:
-
identifying a node, within the XML data, that is to be deleted in response to a Data Manipulation Language (DML) operation; generating a hybrid key for the node; wherein the hybrid key includes (a) a first set of one or more index order key components and (b) a first set of one or more canonical order key components; wherein the first set of index order key components reflects a portion of an index order key by which the node is indexed in the index; wherein the first set of canonical order key components reflects the actual position of the node within the XML data; converting the hybrid key to the index order key; wherein the index order key includes a second set of one or more index order key components and a third set of one or more index order key components; wherein the second set of index order key components equals the first set of index order key components; wherein converting the hybrid key to an index order key comprises converting the first set of canonical order key components to the third set of index order key components; wherein the first set of canonical order key components differs in value from the third set of index order key components; using the index order key to locate a set of one or more index entries within the index; wherein one of the set of one or more index entries indexes the node; and deleting the set of index entries from the index. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A computer-readable volatile or non-volatile storage medium storing computer-executable instructions for:
-
identifying a particular node that is to be added to the XML data in response to a Data Manipulation Language (DML) operation; generating a hybrid key for a parent node of the particular node; wherein the hybrid key includes (a) a first set of one or more index order key components and (b) a first set of one or more canonical order key components; wherein the first set of index order key components reflects a portion of an index order key by which the parent node is indexed in the index; wherein the first set of canonical order key components reflects the actual position of the parent node within the XML data; converting the hybrid key to a first index order key; wherein the index order key includes a second set of one or more index order key components and a third set of one or more index order key components; wherein the second set of index order key components equals the first set of index order key components; wherein converting the hybrid key to the first index order key comprises converting the first set of canonical order key components to the third set of index order key components; wherein the first set of canonical order key components differs in value from the third set of index order key components; 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. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42)
-
Specification