System and method for recursively iterating over a loosely associated data structure
A data structure and its characteristics, and an associated process for searching the structure in a manner that ensures that each node or data location is traversed regardless of which node is the starting point of the traversal process. An embodiment of the invention may be used to locate a node of a data structure so that it may be processed or otherwise manipulated, such as by eliminating a node, moving a node, processing the data associated with a node, etc. In some embodiments, a combination of a “loosely associated” data structure and a specified method of traversing the data structure provide an efficient way to structure and administer a database, and provide a scalable and computationally efficient solution to the problems posed by conventional and more “tightly associated” structures.
1. A method of performing a processing step on each node of a loosely associated data structure, the method comprising:
(a) arbitrarily identifying an initial node from a plurality of nodes of the loosely associated data structure, wherein each one of the plurality of nodes comprises a single association identifier storing information about an originating node of the one of the plurality of nodes, where the originating node has a parent association to the one of the plurality of nodes in the loosely associated data structure;
(b) receiving a single association identifier of the initial node of the loosely associated data structure;
(c) checking a processed flag associated with the initial node in a globally accessible cache memory to determine whether the processing step has already been performed on the initial node;
(d) if the processed flag associated with the initial node is absent in the globally accessible cache memory, then performing sub-steps, comprising:
(i) identifying an originating node of the initial node based on the single association identifier;
(ii) performing a database query and determining one or more associated nodes that refer to the initial node as an originating node;
(iii) adding the associated nodes and the originating node of the initial node to a stored list;
(iv) filtering the stored list to remove one or more duplicates of the associated nodes and one or more duplicates of the originating node, and removing associated node references to each of the remaining nodes that initiated the processing step in the list; and
(v) setting a processed flag to the initial node in the globally accessible cache memory;
(e) if the processed flag associated with the initial node is present in the globally accessible cache memory, then performing sub-steps, comprising:
(i) receiving a single association identifier of at least one of the originating nodes of the initial node in the loosely associated data structure;
(ii) checking a processed flag of the at least one of the originating nodes of the initial node in the globally accessible cache memory to determine whether the processing step has already been performed on the at least one of the originating nodes of the initial node;
(iii) if the processed flag associated with the at least one of the originating nodes is absent, then performing step (d); and
(iv) if the processed flag associated with the at least one of the originating nodes is present, then performing step (e);
(f) performing steps (a) through (e) for at least one node identified in the stored list until all the nodes in the loosely associated data structure are associated with the processed flags and ceasing to repeat steps (a) through (e); and
(g) performing the processing step on the initial node.
2. The method of claim 1 , wherein the processing step is one of deleting a node of the loosely associated data structure or performing a data processing operation on data associated with a node of the loosely associated data structure.
3. The method of claim 1 , wherein filtering the stored list to remove one or more duplicate nodes further comprises filtering the stored list to remove the initial node.
4. The method of claim 1 , wherein prior to performing the processing step on the initial node, the method further comprises determining if one or more conditions related to the processing of the node are satisfied.
5. The method of claim 1 , wherein the single association identifier further comprises a memory address of the one of the plurality of nodes and the memory address of the originating node of the one of the plurality of nodes, and wherein the memory addresses of the one of the plurality of nodes and the originating node of the one of the plurality of nodes are stored in the cache memory, and further wherein the checking the processed flag in the cache memory is performed using at least in part the stored memory addresses.
6. A system, comprising:
a loosely associated data structure containing a plurality of nodes;
a processor programmed to implement a search process in response to a search query, wherein the search process comprises
(a) arbitrarily identifying an initial node from a plurality of nodes of the loosely associated data structure, wherein each one of the plurality of nodes comprises a single association identifier storing information about an originating node of the one of the plurality of nodes, where the originating node has a parent association to the one of the plurality of nodes in the loosely associated data structure;
(b) receiving a single association identifier of the initial node of the loosely associated data structure;
(c) checking a processed flag associated with the initial node in a globally accessible cache memory to determine whether the processing step has already been performed on the initial node;
(d) if the processed flag associated with the initial node is absent in the globally accessible cache memory, then performing sub-steps, comprising:
(i) identifying an originating node of the initial node based on the single association identifier;
(ii) performing a database query and determining one or more associated nodes that refer to the initial node as an originating node;
(iii) adding the associated nodes and the originating node of the initial node to a stored list;
(iv) filtering the stored list to remove one or more duplicates of the associated nodes and one or more duplicates of the originating node, and removing associated node references to each of the remaining nodes that initiated the processing step in the list; and
(v) setting a processed flag to the initial node in the globally accessible cache memory;
(e) if the processed flag associated with the initial node is present in the globally accessible cache memory, then performing sub-steps, comprising:
(i) receiving a single association identifier of at least one of the originating nodes of the initial node in the loosely associated data structure;
(ii) checking a processed flag of the at least one of the originating nodes of the initial node in the globally accessible cache memory to determine whether the processing step has already been performed on the at least one of the originating nodes of the initial node;
(iii) if the processed flag associated with the at least one of the originating nodes is absent, then performing step (d); and
(iv) if the processed flag associated with the at least one of the originating nodes is present, then performing step (e);
(f) performing steps (a) through (for at least one node identified in the stored list until all the nodes in the loosely associated data structure are associated with the processed flags and ceasing to repeat steps (a) through (e); and
(g) performing the processing step on the initial node.
7. The system of claim 6 , wherein the processing step is one of deleting a node of the loosely associated data structure or performing a data processing operation on data associated with a node of the loosely associated data structure.
8. The system of claim 6 , wherein filtering the stored list to remove one or more duplicate nodes further comprises filtering the stored list to remove the initial node.
9. The system of claim 6 , wherein prior to performing the processing step on the initial node, the method further comprises determining if one or more conditions related to the processing of the node are satisfied.
10. The system of claim 6 , wherein the single association identifier further comprises a memory address of the one of the plurality of nodes and the memory address of the originating node of the one of the plurality of nodes, and wherein the memory addresses of the one of the plurality of nodes and the originating node of the one of the plurality of nodes are stored in the cache memory, and further wherein the checking the processed flag in the cache memory is performed using at least in part the stored memory addresses.
11. An apparatus operable to implement a search of a data structure in response to a search query, comprising:
a processor programmed to execute a set of instructions;
a data storage element in which the set of instructions are stored; and
a database comprising a plurality of nodes, wherein each node is associated with an originating node, and wherein when executed by the processor the set of instructions cause the apparatus to
(a) arbitrarily identifying an initial node from a plurality of nodes of the loosely associated data structure, wherein each one of the plurality of nodes comprises a single association identifier storing information about an originating node of the one of the plurality of nodes, where the originating node has a parent association to the one of the plurality of nodes in the loosely associated data structure:
(b) receiving a single association identifier of the initial node of the loosely associated data structure;
(c) checking a processed flag associated with the initial node in a globally accessible cache memory to determine whether the processing step has already been performed on the initial node;
(d) if the processed flag associated with the initial node is absent in the globally accessible cache memory, then performing sub-steps, comprising:
(i) identifying an originating node of the initial node based on the single association identifier,
(ii) performing a database query and determining one or more associated nodes that refer to the initial node as an originating node;
(iii) adding the associated nodes and the originating node of the initial node to a stored list;
(iv) filtering the stored list to remove one or more duplicates of the associated nodes and one or more duplicates of the originating node, and removing associated node references to each of the remaining nodes that initiated the processing step in the list; and
(v) setting a processed flag to the initial node in the globally accessible cache memory;
(e) if the processed flag associated with the initial node is present in the globally accessible cache memory, then performing sub-steps, comprising:
(i) receiving a single association identifier of at least one of the originating nodes of the initial node in the loosely associated data structure;
(ii) checking a processed flag of the at least one of the originating nodes of the initial node in the globally accessible cache memory to determine whether the processing step has already been performed on the at least one of the originating nodes of the initial node;
(iii) if the processed flag associated with the at least one of the originating nodes is absent, then performing step (d); and
(iv) if the processed flag associated with the at least one of the originating nodes is present, then performing step (e);
(f) performing steps (a) through (e) for at least one node identified in the stored list until all the nodes in the loosely associated data structure are associated with the processed flags and ceasing to repeat steps (a) through (e); and
(g) performing the processing step on the initial node.
12. The apparatus of claim 11 , wherein the processing step is one of deleting a node of the loosely associated data structure or performing a data processing operation on data associated with a node of the loosely associated data structure.
13. The apparatus of claim 11 , wherein filtering the stored list to remove one or more duplicate nodes further comprises filtering the stored list to remove the initial node.
14. The apparatus of claim 11 , wherein prior to performing the processing step on the initial node, the method further comprises determining if one or more conditions related to the processing of the node are satisfied.
15. The apparatus of claim 11 , wherein the single association identifier further comprises a memory address of the one of the plurality of nodes and the memory address of the originating node of the one of the plurality of nodes, and wherein the memory addresses of the one of the plurality of nodes and the originating node of the one of the plurality of nodes are stored in the cache memory, and further wherein the checking the processed flag in the cache memory is performed using at least in part the stored memory addresses.