PERSISTENT ITERATION OVER A DATABASE TREE STRUCTURE

• US 20130325902A1
• Filed: 06/05/2012
• Published: 12/05/2013
• Est. Priority Date: 06/05/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: BACHAR, Yariv, KUVENT, Aviv, LEVY, Asaf
• Granted Patent: US 8,650,219 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Persistent iteration is performed in stages on nodes arranged according to a node identification (ID) that is increasing in order under a parent node in database tree structure. While performing the persistent iteration, storing a start node ID of the node where the persistent iteration commenced, a current node ID of the node that is undergoing the persistent iteration, a parent node ID of the node that is undergoing the persistent iteration, and a numerical value representing the current level and all levels greater than the current level of nodes that are undergoing the persistent iteration. Upon completion of the persistent iteration on the nodes that are the children of the node with the parent node ID, returning to the first node among the children of the node with the parent node ID, as ordered by increasing node ID, and performing the persistent iteration for children nodes of each node.

Claims

1. A method for persistent iteration over a database tree structure having a plurality of levels by a processor device in a computing environment, the method comprising:

performing on a current level a first stage of the persistent iteration on those of the plurality of nodes having at least a node identification (ID) greater than a current node identification (ID) that is stored and a parent node identification (ID) equal to a parent node identification (ID) that is stored, wherein each of the plurality of nodes share a parent node and are increasingly ordered according to the node ID of each of the plurality of nodes;

wherein;

the first stage of the persistent iteration is performed if the numerical value of the current level is not equal to the numerical value of a previous level, further wherein the numerical value of the previous level is set equal to the numerical value of the current level if all of the plurality of nodes in a current level under a same parent node had the first stage of the persistent iteration performed thereon,

the persistent iteration is terminated if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level equals zero, and

if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level does not equal zero, at least one of;

a second stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with at least one child node not yet having the first stage of the persistent iteration performed thereon, and

a third stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with all child nodes having the first stage of the persistent iteration performed thereon.

2. The method of claim 1, further including storing during the first stage of the persistent iteration at least a start node identification (ID) of one of the plurality of nodes indicating where the persistent iteration commenced, a current node identification (ID) of one of the plurality of nodes that is undergoing the persistent iteration, a parent node identification (ID) of the one of the plurality of nodes that is undergoing the persistent iteration, and a numerical value corresponding to at least the current level and those of the plurality of levels greater than the current level.

3. The method of claim 2, further including initializing the start node ID to be a root of one of at least the database tree structure and a sub-tree of the database tree structure.

4. The method of claim 2, further including performing the first stage of the persistent iteration by at least one of:

initializing the parent node ID to be the start node ID,

initializing the current node ID to a minimal node ID value, and

initializing the numerical value for a pervious level to a zero value and the numerical value for the current level to a first value.

5. (canceled)

6. The method of claim 5, further including performing during the second stage of the persistent iteration at least one of:

initializing the parent node ID to be the current node ID,

initializing the current node ID to a minimal node ID value, and

incrementing the numerical value for the current level by a value of one.

7. The method of claim 5, further including obtaining the node ID for a grandparent node of the current node ID during the third stage of the persistent iteration.

8. The method of claim 5, further including performing during the third stage of the persistent iteration at least one of:

initializing the current node ID to be the parent node ID,

initializing the parent node ID to be a grand parent node ID, and

decrementing the numerical value for the current level and the numerical value for a previous level by a value of one.

9. (canceled)

10. A system for persistent iteration over a database tree structure having a plurality of levels in a computing environment, the system comprising:

an iterator used in the persistent iteration in levels in the data base tree;

a plurality of counters for maintaining a numerical value for each of the plurality of levels, wherein the plurality of counters is in communication with the iterator,

at least one processor device in communication with the iterator and the plurality of counters, wherein the processor device is adapted for;

performing on a current level a first stage of the persistent iteration on those of the plurality of nodes having at least a node identification (ID) greater than a current node identification (ID) stored in the iterator and a parent node identification (ID) equal to a parent node identification (ID) stored in the iterator, wherein each of the plurality of nodes share a parent node and are increasingly ordered according to the node ID of each of the plurality of nodes;

wherein;

the first stage of the persistent iteration is performed if the numerical value of the current level is not equal to the numerical value of a previous level, further wherein the numerical value of the previous level is set equal to the numerical value of the current level if all of the plurality of nodes in a current level under a same parent node had the first stage of the persistent iteration performed thereon,

the persistent iteration is terminated if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level equals zero, and

if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level does not equal zero, at least one of;

a second stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with at least one child node not yet having the first stage of the persistent iteration performed thereon, and

a third stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with all child nodes having the first stage of the persistent iteration performed thereon.

11. The system of claim 10, wherein the processor device is further adapted for storing in the iterator during the first stage of the persistent iteration at least a start node identification (ID) of one of the plurality of nodes indicating where the persistent iteration commenced, a current node identification (ID) of one of the plurality of nodes that is undergoing the persistent iteration, a parent node identification (ID) of the one of the plurality of nodes that is undergoing the persistent iteration, and a numerical value corresponding to at least the current level and those of the plurality of levels greater than the current level.

12. The system of claim 11, wherein the processor device is further adapted for initializing in the iterator the start node ID to be a root of one of the database tree structure and the sub-tree of the database tree structure.

13. The system of claim 11, wherein the processor device is further adapted for initializing the iterator, for performing the first stage of the persistent iteration, by performing at least one of:

initializing the parent node ID to be the start node ID,

initializing the current node ID to a minimal node ID value, and

initializing the numerical value for a pervious level to a zero value and the numerical value for the current level to a first value.

14. (canceled)

15. The system of claim 14, wherein the processor device is further adapted for initializing the iterator, for performing the second stage of the persistent iteration, by performing at least one of:

initializing the parent node ID to be the current node ID,

initializing the current node ID to a minimal node ID value, and

incrementing the numerical value for the current level by a value of one.

16. The system of claim 14, wherein the processor device is further adapted for obtaining the node ID for a grandparent node of the current node ID during the third stage of the persistent iteration.

17. The system of claim 14, wherein the processor device is further adapted for initializing the iterator, for performing a third stage of the persistent iteration, by performing at least one of:

initializing the current node ID to be the parent node ID,

initializing the parent node ID to be a grand parent node ID, and

decrementing the numerical value for the current level and the numerical value for a previous level by a value of one.

18. (canceled)

19. A computer program product for persistent iteration over a database tree structure having a plurality of levels by a processor device, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion for performing on a current level a first stage of the persistent iteration on those of the plurality of nodes having at least a node identification (ID) greater than a current node identification (ID) that is stored and a parent node identification (ID) equal to a parent node identification (ID) that is stored, wherein each of the plurality of nodes share a parent node and are increasingly ordered according to the node ID of each of the plurality of nodes;

wherein;

the first stage of the persistent iteration is performed if the numerical value of the current level is not equal to the numerical value of a previous level, further wherein the numerical value of the previous level is set equal to the numerical value of the current level if all of the plurality of nodes in a current level under a same parent node had the first stage of the persistent iteration performed thereon,

the persistent iteration is terminated if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level equals zero, and

if the numerical value of the current level and the numerical value of the previous level are equal and the numerical value of the previous level does not equal zero;

a second stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with at least one child node not yet having the first stage of the persistent iteration performed thereon, and

a third stage of the persistent iteration is performed on one of the plurality of levels having those of the plurality of nodes with all child nodes having the first stage of the persistent iteration performed thereon.

20. The computer program product of claim 19, further including a second executable portion for storing during the first stage of the persistent iteration at least a start node identification (ID) of one of the plurality of nodes indicating where the persistent iteration commenced, a current node identification (ID) of one of the plurality of nodes that is undergoing the persistent iteration, a parent node identification (ID) of the one of the plurality of nodes that is undergoing the persistent iteration, and a numerical value corresponding to at least the current level and those of the plurality of levels greater than the current level.

21. The computer program product of claim 20, further including a third executable portion for initializing the start node ID to be a root of one of at least the database tree structure and a sub-tree of the database tree structure.

22. The computer program product of claim 21, further including a third executable portion for performing the first stage of the persistent iteration by at least one of:

initializing the parent node ID to be the start node ID,

initializing the current node ID to a minimal node ID value, and

initializing the numerical value for a pervious level to a zero value and the numerical value for the current level to a first value.

23. (canceled)

24. The computer program product of claim 23, further including a fourth executable portion for performing during the second stage of the persistent iteration at least one of:

initializing the parent node ID to be the current node ID,

initializing the current node ID to a minimal node ID value, and

incrementing the numerical value for the current level by a value of one.

25. The computer program product of claim 23, further including a fourth executable portion for obtaining the node ID for a grandparent node of the current node ID during the third stage of the persistent iteration.

26. The computer program product of claim 23, further including a fourth executable portion for performing during the third stage of the persistent iteration at least one of:

initializing the current node ID to be the parent node ID,

initializing the parent node ID to be a grand parent node ID, and

decrementing the numerical value for the current level and the numerical value for a previous level by a value of one.

27. (canceled)