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

• US 20050165772A1
• Filed: 03/18/2005
• Published: 07/28/2005
• Est. Priority Date: 03/10/2003
• Status: Active Grant

• Current Assignee: Jane Campbell Mazzagatti
• Original Assignee: Jane Campbell Mazzagatti
• Inventors: Mazzagatti, Jane Campbell
• Granted Patent: US 7,788,287 B2
• Time in Patent Office: Days
• 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 generating a tree-based datastore comprising:

a processor;

a memory coupled to the processor; and

a tree-based datastore generator for creating at least one level of a tree-based datastore, the at least one level of the tree-based datastore comprising a first tree 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.

2. The 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 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 comprise the elemental nodes of the second level.

4. The 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 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 system of claim 1, wherein the nodes comprise pointers to other nodes in the tree-based datastore and wherein said pointers are bi-directional.

7. The 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 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 system of claim 7, wherein the second root is associated with an end indicator and accesses the tree-based datastore in an inverted first hierarchical order.

10. The 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 system of claim 1, further comprising a tree-based datastore accessor for retrieving information from the tree-based datastore.

12. The 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 system for generating a datastore comprising:

a processor;

a memory coupled to the processor; and

a datastore generator for creating a datastore, wherein the datastore comprises;

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.

14. The 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 system of claim 14, wherein the first type tree records the sequential synthesis of an end product from 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 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.

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

24. The system of claim 23, 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.

17. (canceled)

18. (canceled)

19. (canceled)

20. (canceled)

21. (canceled)

22. (canceled)

25. A method for generating and accessing data from a datastore, comprising:

in response to receiving data, creating at least one level 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;

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.

26. The method of claim 25, 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.

27. The method of claim 26, 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.

28. The method of claim 27, 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.

29. The method of claim 27, 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.

30. The method of claim 27, 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.

31. The method of claim 26, wherein creating a new node comprises allocating space for a first pointer, a second pointer, a third pointer and a fourth pointer.

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

33. A method for accessing information from a tree-based datastore, 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 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.

34. The method of claim 33, 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.

35. 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;

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.

36. A structure comprising nodes and links between said nodes, said nodes having a plurality of data fields, at least two of said plurality of data fields containing a pointer, one of said at least two pointers being a Case pointer and the other of said at least two pointers being a Result pointer and at least one node having at least an additional pointer to a list of pointers, one of said additional pointers to said list of pointers being to an asCase list in instances where said node has associated asCase list and another being to asResult list in instances where said node has associated an asResult list, and wherein said nodes include root nodes of which there are at least one primary root node and at least one elemental root node and wherein said nodes may include other root nodes, said nodes further including at least one end of thought node, at least one subcomponent node, and at least one end product node, and wherein said asResult links point between a root node and any other node, and wherein said asCase links point between at least one primary root node and at least one end product node include in a path therebetween containing at least one subcomponent node and wherein said asResult links point between a root or end product node and a subcomponent node or end product node on said path therebetween, and wherein said elemental nodes also have a field having a value.

37. The structure of claim 36 wherein said structure is formed from a set of program instructions which configure a computer system when activated therein to produce said structure.

38. A computer readable medium containing the set of program instructions as set forth in claim 37.

39. An electronic system containing a data structure conforming to the structure of claim 36.

40. A structure as set forth in claim 36 wherein said asCase and said asResult lists are stored in a separate data structure from said interlocking trees structure and wherein said separate data structure is associated with related nodes in said interlocking trees structure by pointers.