MTree an XPath multi-axis structure threaded index
First Claim
Patent Images
1. A method of creating an index data structure for one or more data objects having one or more nodes, the method comprising:
- a) traversing the one or more data objects to identify a plurality of nodes;
b) associating with each node an index key and a set of index attributes, wherein each set of index attributes comprises;
a first reference for locating a node in an ancestor axis, the ancestor axis containing ancestors of a context node;
a second reference for locating a preceding subtree root node, preceding subtree root node being a subtree root node of a preceding axis to a context node, the preceding axis containing all nodes in a same document as the context node that are before the context node in document order, excluding any ancestors and excluding attribute nodes and namespace nodes;
a third reference for locating a following subtree root node, the following subtree root node being a subtree root node of a following axis to a context node, the following axis containing all nodes in the same document as the context node that are after the context node in document order excluding any descendants, attribute nodes, or namespace nodes; and
a fourth reference for locating a node in a descendent axis, the descendent axis being an axis that contains the descendants of a context node; and
wherein the index key uniquely identifies potential context nodes; and
c) storing the index key and the associated set of index attributes on a digital storage medium.
0 Assignments
0 Petitions
Accused Products
Abstract
An index data structure (“MTree”) useful in creating indices for structured data is provided. The MTree index data structure is designed to meet the needs of the hierarchical XPath query language. The primary feature of MTree is the next subtree root node in document order for all axes are available to each context node in O(1). The MTree index data structure supports modification operations such as insert and delete. The MTree index structure is implemented in memory or in a digital storage medium. Improved performance in the MTree index structure utilizing a threading scheme is also provided.
181 Citations
10 Claims
-
1. A method of creating an index data structure for one or more data objects having one or more nodes, the method comprising:
-
a) traversing the one or more data objects to identify a plurality of nodes; b) associating with each node an index key and a set of index attributes, wherein each set of index attributes comprises; a first reference for locating a node in an ancestor axis, the ancestor axis containing ancestors of a context node; a second reference for locating a preceding subtree root node, preceding subtree root node being a subtree root node of a preceding axis to a context node, the preceding axis containing all nodes in a same document as the context node that are before the context node in document order, excluding any ancestors and excluding attribute nodes and namespace nodes; a third reference for locating a following subtree root node, the following subtree root node being a subtree root node of a following axis to a context node, the following axis containing all nodes in the same document as the context node that are after the context node in document order excluding any descendants, attribute nodes, or namespace nodes; and a fourth reference for locating a node in a descendent axis, the descendent axis being an axis that contains the descendants of a context node; and wherein the index key uniquely identifies potential context nodes; and c) storing the index key and the associated set of index attributes on a digital storage medium. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method of querying an index data structure, the index data structure comprising:
-
a) a plurality of index keys for uniquely identifying potential context nodes in a data object, each index key being associated with a potential context node; b) a set of index attributes associated with each index key, each set of attributes comprising; a first reference for locating a node in an ancestor axis, the ancestor axis containing ancestors of a context node; a second reference for locating a preceding subtree root node, preceding subtree root node being a subtree root node of a preceding axis to a context node, the preceding axis containing all nodes in a same document as the context node that are before the context node in document order, excluding any ancestors and excluding attribute nodes and namespace nodes; a third reference for locating a following subtree root node, the following subtree root node being a subtree root node of a following axis to a context node, the following axis containing all nodes in the same document as the context node that are after the context node in document order excluding any descendants, attribute nodes, or namespace nodes; and a fourth reference for locating a node in a descendent axis, the descendent axis being an axis that contains the descendants of a context node; and wherein the index data structure is stored on a digital storage medium, the method comprising; parsing a query into elementary steps; executing the elementary steps on the index data structure; and return results of the query. - View Dependent Claims (10)
-
Specification