Mtree an Xpath multi-axis structure threaded index

• US 20060064432A1
• Filed: 09/22/2005
• Published: 03/23/2006
• Est. Priority Date: 09/22/2004
• Status: Active Grant

• Current Assignee: Primo M. Pettovello
• Original Assignee: Primo M. Pettovello
• Inventors: Pettovello, Primo M.
• Granted Patent: US 9,171,100 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

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.

Claims

1. An index data structure for one or more data objects, 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; and

b) a set of index attributes associated with each index key, each set of attributes comprising a reference selected from the group consisting of;

a first reference for locating a preceding subtree root node;

a second reference for locating a following subtree root node; and

combinations thereof;

wherein the index data structure is stored on a digital storage medium.

2. The index data structure of claim 1 wherein the set of index attributes further comprises:

a third reference for locating a node in the ancestor axis; and

a fourth reference for locating a node in the descendent axis.

3. The index data structure of claim 1 wherein:

the first reference for locating a node in the ancestor axis is a reference to the parent node of the context node;

the second reference for locating a preceding subtree root node is a reference to a closest preceding subtree root node;

the third reference for locating a following subtree root node is a reference to a closest following subtree root node; and

the fourth reference for locating a node in the descendant axis is a reference to a child node of the context node.

4. The index data structure of claim 2 wherein the fourth reference is to a descendent subtree root node selected from the group consisting of a first descendant child node and a last descendant child node.

5. The index data structure of claim 1 wherein the data object is a hierarchical data object.

6. The index data structure of claim 1 wherein the data object is an object selected from the group consisting of an XML document, a collection of XML documents, a collection of distributed computers, a distributed service, a collection of distributed services, hierarchical file systems, tree data structures, XML file system, relational database tables, mutlidimensional tables, computer graphics geometry space, polygon space, and combinations thereof.

7. The index data structure of claim 1 wherein the set of attributes further comprises one or more additional references to data associated with one or more context nodes.

8. The index data structure of claim 7 wherein the set of attributes further comprises at least one reference to a node having data related to the context node.

9. The index data structure of claim 8 wherein the related data is selected from node attributes, qnames, and combinations thereof.

10. The index data structure of claim 1 wherein the index data structure is accessible to a computer system.

11. 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 the ancestor axis;

a second reference for locating a preceding subtree root node;

a third reference for locating a following subtree root node; and

a fourth reference for locating a node in the descendent axis; and

wherein the index key uniquely identifies each representation of the representation; and

c) storing the index key and the associated set of index attributes on a digital storage medium.

12. The method of claim 11 wherein the step of traversing the one or more data objects comprises a depth first search or a breadth first search.

13. The method of claim 11 wherein the step of traversing the one or more data objects comprises a depth first search that is preorder, in order, or post order.

14. The method of claim 11 wherein the set of index attributes further comprises one or more additional references to data associated with one or more context nodes.

15. The method of claim 14 wherein the set of attributes further comprises at least one reference to a node having data related to the context node.

16. The method of claim 14 wherein the related data is selected from node attributes, qnames, and combinations thereof.

17. The method of claim 11 further comprising adding an index key and a set of index attributes to the index data structure associated with a new node that is added to the data object.

18. The method of claim 11 further comprising removing an index key and a set of index attributes from the index data structure associated with a node that is removed from the data object.

20. The method of claim 18 wherein the query comprises one more location steps.

19. A method of querying an index data structure, the index 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 the ancestor axis;

a second reference for locating a preceding subtree root node;

a third reference for locating a following subtree root node; and

a fourth reference for locating a node in the descendent axis; 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.