System and method for storing and accessing data in an interlocking trees datastore

• US 7,788,287 B2
• Filed: 03/18/2005
• Issued: 08/31/2010
• Est. Priority Date: 03/10/2003
• Status: Expired due to Fees

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Mazzagatti, Jane Campbell
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/084,996
• Publication Number:
  US 20050165772A1
• Time in Patent Office: 1,992 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/101, 707/102, 707/103, 707/104, 707/803
• US Class Current: 707/803
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A tree-based datastore comprising a forest of interconnected trees is generated and/or accessed. The tree-based datastore comprises a first tree that depends from a first root node and may include a plurality of branches. Each of the branches of the first tree ends in a leaf node. Each leaf node may represent an end product, as described more fully below. A second root of the same tree-based datastore is linked to each leaf node representing an end product. Hence, the second root is essentially a root to an inverted order of the first tree, but the first tree is not duplicated. Finally, the tree-based datastore comprises a plurality of trees in which the root node of each of these trees is an elemental node, as described more fully below. The root node of each of these trees may be linked to one or more nodes in one or more branches of the first tree. The nodes of the tree-based datastore contain only pointers to other nodes in the tree-based datastore. The roots of the trees in the forest of trees comprising the tree-based datastore may be linked to data.

Claims

1. A computer processing system for generating a tree-based datastore within the data storage of a computing processing system comprising:

a processor;

a memory coupled to the processor; and

a tree-based datastore generator for creating at least one level of trees of a tree-based datastore, the at least one level of the tree-based datastore comprising a first tree comprising a first root and at least one node of a plurality of nodes, a second tree comprising a second root and the at least one node of the first tree and at least a third tree comprising a third root and at least one of the plurality of nodes of the first tree;

wherein the interlocking trees datastore comprising a plurality of nodes, and a K node of the plurality of nodes comprises a Case pointer and a Result pointer, said Case pointer and said Result pointer pointing to two nodes from which the K node is formed, the K node also comprising pointers to an asCase array and an asResult array, the asCase array comprising pointers to nodes whose Case pointers point to said K node and wherein the asResult array comprises pointers to nodes whose Result pointers point to said K node.

2. The computer processing system of claim 1, wherein the nodes of the datastore include at least one elemental node, one subcomponent node and one end product node.

3. The computer processing system of claim 2, wherein the tree-based datastore comprises at least a first level and a second level and the end products of the first level are decomposed to create the elemental nodes of the first level.

4. The computer processing system of claim 2, wherein the tree-based datastore comprises at least a first level and a second level and the end products of the first level are decomposed to create the elemental nodes of the first level.

5. The computer processing system of claim 2, wherein the tree-based datastore comprises at least a first level and a second level and the elemental nodes of the second level are decomposed to create the elemental nodes of the first level.

6. The computer processing system of claim 1, wherein the nodes comprise pointers to other nodes in the tree-based datastore and wherein said pointers are bidirectional.

7. The computer processing system of claim 1, wherein the first root and second root comprise pointers to other nodes in the tree-based datastore and include non-pointer information.

8. The computer processing system of claim 7, wherein the first root is associated with a begin indicator and accesses the tree-based datastore in a first hierarchical order.

9. The computer processing system of claim 7, wherein the second root is associated with an end indicator and access the tree-based datastore in an inverted first hierarchical order.

10. The computer processing system of claim 7, wherein the third root includes non-pointer information associated with an element of a dataset and accesses the tree-based datastore in a third hierarchical order based on the dataset element.

11. The computer processing system of claim 1, further comprising a tree-based datastore accessor for retrieving information from the tree-based datastore.

12. The computer processing system of claim 11, wherein the tree-based datastore accessor further comprises:

means for receiving a request for information to be retrieved from the tree-based datastore;

means for retrieving the requested information from the tree-based datastore; and

means for returning the retrieved information from the tree-based datastore.

13. A computer processing system for generating an interlocking trees datastore within the data storage of a computing processing system, the computer processing system comprising:

a processor;

a memory coupled to the processor; and

root nodes and non-root nodes organized into a plurality of connected trees, the plurality of connected trees comprising a tree of a first type comprising a first root and at least one of a plurality of non-root nodes and at least one of a plurality of trees of a second type;

wherein the second tree type comprises a second root node and a plurality of non-root nodes common with the nodes of the tree of the first type; and

the interlocking trees datastore comprising a plurality of nodes, and a K node of the plurality of nodes comprises a Case pointer and a Result pointer, said Case pointer and said Result pointer pointing to two nodes from which the K node is formed, the K node also comprising pointers to an asCase array and an asResult array, the asCase array comprising pointers to nodes whose Case pointers point to said K node and wherein the asResult array comprises pointers to nodes whose Result pointers point to said K node.

14. The computer processing system of claim 13, wherein the nodes of the datastore include at least one elemental node, one subcomponent node and one end product node.

15. The computer processing system of claim 14, wherein the first type tree records the sequential synthesis of an end product form at least one combination of a subcomponent node with an elemental node and provides access to data in the datastore in a first context.

16. The computer processing system of claim 13, wherein at least one tree of the plurality of trees of the second type provides access to the data in the datastore in a second context.

17. The computer processing system of claim 13, further comprising an accessor for accessing information stored in the interlocking tree datastore.

18. The computer processing system of claim 17, wherein the accessor further comprises:

means for receiving a request for information to be retrieved from the tree-based datastore;

means for retrieving the requested information from the tree-based datastore; and

means for returning the retrieved information from the tree-based datastore.

19. A computer implemented method executing programmable instructions within a computing system for generating and accessing data from a datastore within data storage of the computing system, the method comprising:

in response to receiving data, creating at least one level of trees of an interlocking tree-based datastore, the at least one level of the interlocking tree-based datastore comprising a first tree comprising a first root and at least one node of a plurality of nodes, a second tree comprising a second root and the at least one node of the first tree and at least a third tree comprising a third root and at least one of the plurality of nodes of the first tree;

receiving an information request for information accessible from the at least one level of the tree-based datastore; and

retrieving the information from the at least one level of the tree-based datastore;

wherein the interlocking trees datastore comprising a plurality of nodes, and a K node of the plurality of nodes comprises a Case pointer and a Result pointer, said Case pointer and said Result pointer pointing to two nodes from which the K node is formed, the K node also comprising pointers to an asCase array and an asResult array, the asCase array comprising pointers to nodes whose Case pointers point to said K node and wherein the asResult array comprises pointers to nodes whose Result pointers point to said K node.

20. The computer implemented method of claim 19, comprising:

in response to receiving data to be added to the tree-based datastore, creating a new node in the tree-based datastore for storing information associated with the received data;

creating links from the new node to a first node comprising a first portion of the new node and a second node comprising a second portion of the new node;

adding a link back to the new node to a first list of pointers of the first node; and

adding a link back to the new node to a second list of pointers of the second node.

21. The computer implemented method of claim 20, wherein creating a new node in the tree-based datastore comprises combining a first node representing a begin indicator with a second node representing a dataset element to generate a third node representing an incomplete product.

22. The computer implemented method of claim 21, wherein creating a new node in the tree-based datastore comprises combining a first node representing a first incomplete product with a second node representing a dataset element to generate a third node representing a second incomplete product.

23. The computer implemented method of claim 21, wherein creating a new node in the tree-based datastore comprises combining a first incomplete product with a fourth node representing an end indicator to generate a fifth node representing an end product.

24. The computer implemented method of claim 21, wherein creating a new node in the tree-based datastore comprises combining a second incomplete product with a fourth node representing an end indicator to generate a fifth node representing an end product.

25. The computer implemented method of claim 20, wherein creating a new node comprises allocating space for a first pointer, a second pointer, a third pointer and a fourth pointer.

26. The computer implemented method of claim 20, wherein the third pointer and fourth pointer are null pointers.

27. A computer implemented method executing programmable instructions stored in a computer storage media for generating and accessing data from a datastore within data storage of the computing system, the method comprising:

in response to receiving a request for information from a datastore, the information request comprising at least one constraint, the datastore comprising at least one level of trees of a tree-based datastore, the at least one level of the tree-based datastore comprising a first tree comprising a first root and at least one node of a plurality of nodes, a second tree comprising a second root and the at least one node of the first tree and at least a third tree comprising a third root and at least one of the plurality of nodes of the first tree;

retrieving a list of nodes associated with the third root, each node in the list of nodes comprising a first portion and a second portion, wherein the third root comprises the at least one constraint; and

following the branch of each node in the first tree to the at least one node of the second tree;

wherein the interlocking trees datastore comprising a plurality of nodes, and a K node of the plurality of nodes comprises a Case pointer and a Result pointer, said Case pointer and said Result pointer pointing to two nodes from which the K node is formed, the K node also comprising pointers to an asCase array and an asResult array, the asCase array comprising pointers to nodes whose Case pointers point to said K node and wherein the asResult array comprises pointers to nodes whose Result pointers point to said K node.

28. The computer implemented method of claim 27, wherein the request for information comprises a first constraint and a second constraint and the intersection of the sets of nodes of the second tree is returned.

29. A computer-readable medium comprising computer-executable instructions for generating an interlocking tree database, including instructions for:

in response to receiving data to be added to the tree-based datastore, creating a new node in the tree-based datastore for storing information associated with the received data, the tree-based datastore comprising a first tree comprising a first root and at least one node of a plurality of nodes, a second tree comprising a second root and the at least one node of the first tree and at least a third tree comprising a third root and at least one of the plurality of nodes of the first tree;

creating links from the new node to a first node comprising a first portion of the new node and a second node comprising a second portion of the new node;

adding a link back to the new node to a first list of pointers of the first node; and

adding a link back to the new node to a second list of pointers of the second node

wherein the interlocking trees datastore comprising a plurality of nodes, and a K node of the plurality of nodes comprises a Case pointer and a Result pointer, said Case pointer and said Result pointer pointing to two nodes from which the K node is formed, the K node also comprising pointers to an asCase array and an asResult array, the asCase array comprising pointers to nodes whose Case pointers point to said K node and wherein the asResult array comprises pointers to nodes whose Result pointers point to said K node.