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

• US 7,424,480 B2
• Filed: 09/29/2005
• Issued: 09/09/2008
• Est. Priority Date: 03/10/2003
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Mazzagatti, Jane Campbell
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): Morrison; Jay A
• Application Number:
  US11/239,177
• Publication Number:
  US 20060074947A1
• Time in Patent Office: 1,076 Days
• Field of Search: None
• US Class Current: 1/1
• 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 system for representing data, comprising:

at least one processor;

memory operatively coupled to said at least one processor; and

a program for providing nodes in an interlocking trees datastore, the interlocking trees datastore comprising root nodes and non-root nodes organized into a plurality of connected trees, the plurality of connected trees comprising an asCase tree comprising a first root and at least one of a plurality of non-root nodes, the at least one non-root node comprising a first Case node and at least one of a plurality of asResult trees, the at least one asResult tree comprising a second root node and at least one of a plurality of non-root nodes common with the nodes of the asCase tree, the at least one non-root node common with the nodes of the asCase tree comprising a first Result node, the nodes of the interlocking trees datastore including at least one elemental node representing a dataset element, at least one non-root node, the at least one non-root node comprising a first subcomponent node and at least one end product node, each node in the interlocking trees datastore comprising a Case pointer pointing to a first portion of a non-root node, a Result pointer pointing to a second portion of the non-root node, a pointer to an asCase list, the asCase list comprising a linked list of nodes for which the node is a first portion and a pointer to an asResult list, the asResult list comprising a linked list of non-root nodes for which the node is a second portion,

wherein said first subcomponent node (i) represents a logical relationship between said first Case node and said first Result node in accordance with said data and (ii) is adapted to serve as a second Case node.

2. The system for representing data of claim 1, further comprising:

a second Result node; and

a second subcomponent node, wherein said second subcomponent node represents a logical relationship between said first subcomponent node serving as said second Case node and said second Result node.

3. The system for representing data of claim 2, wherein said first Result node differs from said second Result node.

4. The system for representing data of claim 2, wherein said first Result node further comprises a root node.

5. The system for representing data of claim 1, wherein said first Result node comprises an end of thought node.

6. The system for representing data of claim 1, wherein said first Case node comprises a beginning of thought node.

7. The system for representing data of claim 1, further comprising a bidirectional link between said first Case node and said first subcomponent node.

8. The system for representing data of claim 7, further comprising a pointer pointing from said first subcomponent node to said first case node.

9. The system for representing data of claim 8, further comprising a pointer pointing from said first case node to said first subcomponent node.

10. The system for representing data of claim 7, further comprising a pointer from said first Case node to said first subcomponent node.

11. The system for representing data of claim 10, including a plurality of subcomponent nodes wherein said first Case node comprises an asCase list of pointers pointing to said plurality of subcomponent nodes.

12. The system for representing data of claim 1, further comprising a bidirectional link between said first Result node and said first subcomponent node.

13. The system for representing data of claim 12, further comprising a pointer pointing from said first subcomponent node to said first Result node.

14. The system for representing data of claim 13, further comprising a pointer pointing from said first Cast node to said first Result node.

15. The system for representing data of claim 13, further comprising a pointer pointing from said first Result node to said first subcomponent node.

16. The system for representing data of claim 15, including a plurality of subcomponent nodes wherein said first Result node further comprises an asResult list of pointers to subcomponent nodes.

17. The system for representing data of claim 1, including a plurality of subcomponent nodes further comprising a plurality of bidirectional links between said first Case node and said plurality of subcomponent nodes.

18. The system for representing data of claim 1, further comprising forming a data structure in accordance with said second Case node.

19. The system for representing data of claim 5, wherein said end of thought node is adapted to serve as a further Case node.